Opened 3 years ago

Closed 3 years ago

#28659 closed defect (fixed)

fix #28631

Reported by: vdelecroix Owned by:
Priority: critical Milestone: sage-9.0
Component: number fields Keywords:
Cc: tscrim, soehms Merged in:
Authors: Vincent Delecroix Reviewers: Sebastian Oehms
Report Upstream: N/A Work issues:
Branch: b21f548 (Commits, GitHub, GitLab) Commit: b21f548cc4b7c311c1b8c7b7d03d8f9ff5f511f3
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

The ticket #28631 introduced a vastly incomplete factorization of polynomials in the universal cyclotomic field.

sage: x = polygen(UCF)
sage: (x**2 - 3).factor()   # bug
x^2 - 3
sage: r = UCF(3).sqrt()
sage: r
E(12)^7 - E(12)^11
sage: (x - r) * (x + r)     # here is the factorization
x^2 - 3

Change History (15)

comment:1 Changed 3 years ago by vdelecroix

  • Description modified (diff)

comment:2 Changed 3 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/28659
  • Commit set to 6f0db178599db40c1ef9b893a3c4941fcd369371
  • Status changed from new to needs_review

New commits:

6f0db1728659: revert 28631

comment:3 Changed 3 years ago by soehms

I would prefer to have an implementation of _factor_univariate_polynomial remaining. Two reasons for this I've given in https://trac.sagemath.org/ticket/28631#comment:7 Another reason is to prevent developers in future of not becoming aware that there is a serious reason that the implementation of factorization over UCF is avoided in general (since it is a non trivial task).

This could be achieved by the following bug-fix of #28631:

         if len(F) == 1:
+            if cycl_pol.degree() > 1:
+                raise NotImplementedError('Cannot factor this polynomial' )
             return F

in addition with a doc-test for this ticket (with the example of the description)!

comment:4 Changed 3 years ago by vdelecroix

Your version is also "broken" on

((x^2 + x + 1)**2).factor()

I will try to make a reasonable partial implementation and add a note why this is non trivial.

Last edited 3 years ago by vdelecroix (previous) (diff)

comment:5 Changed 3 years ago by git

  • Commit changed from 6f0db178599db40c1ef9b893a3c4941fcd369371 to 9f4d6fb05e648b3944c778e132c758bb1801c54f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9f4d6fb28659: fix wrong univariate factorization over UCF

comment:6 Changed 3 years ago by vdelecroix

Here is a more reasonable fix. It factorizes into product of linear forms as long as it is a product of cyclotomic polynomials and degree 2 factors.

The case of degree 3 should be doable "by hand". For higher degree, one needs to go through more Galois theory.

comment:7 Changed 3 years ago by vdelecroix

  • Summary changed from revert #28631 to fix #28631

comment:8 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to needs_work

This should actually work

sage: (x^3 - 8).factor()

comment:9 Changed 3 years ago by git

  • Commit changed from 9f4d6fb05e648b3944c778e132c758bb1801c54f to b414cb75dfb3b8867985db5d81192c7bb3f49304

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b414cb728659: fix wrong univariate factorization over UCF

comment:10 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Indeed, I forgot degree one polynomials. Now it should be ok.

comment:11 Changed 3 years ago by git

  • Commit changed from b414cb75dfb3b8867985db5d81192c7bb3f49304 to 8cf8183c98cb9e692ffb76c35e9d4bb6c95d635d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8cf818328659: fix wrong univariate factorization over UCF

comment:12 Changed 3 years ago by soehms

  • Reviewers set to Sebastian Oehms

Thanks for your agreement and for improving the implementation more than I expected! Indeed, transferring the problem to the cyclotomic fields was no good idea! It is more reasonable (and surely more performant) to restrict to rational polynomials and do calculations inside the UCF, as you did. But maybe you should change the comment above that restriction:

find a common cyclotomic field for the coefficients and change base ring

since it might be misleading now. If this is done, you may switch to positive review!

comment:13 Changed 3 years ago by git

  • Commit changed from 8cf8183c98cb9e692ffb76c35e9d4bb6c95d635d to b21f548cc4b7c311c1b8c7b7d03d8f9ff5f511f3

Branch pushed to git repo; I updated commit sha1. New commits:

b21f54828659: expand comment and simplifies code

comment:14 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:15 Changed 3 years ago by vbraun

  • Branch changed from u/vdelecroix/28659 to b21f548cc4b7c311c1b8c7b7d03d8f9ff5f511f3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.