#17840 closed enhancement (fixed)
Factorization of multivariate polynomials over the integers
Reported by:  Bruno Grenet  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  factorization  Keywords:  multivariate integer polynomial 
Cc:  Merged in:  
Authors:  Bruno Grenet  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  c41d743 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
Currently, Sage does not know how to factor multivariate polynomials over the integers:
sage: R.<x,y> = ZZ[] sage: p = 12 * (x*y  1) * (x + 2*y + 3) sage: p.factor() Traceback (most recent call last): ... NotImplementedError: Factorization of multivariate polynomials over nonfields is not implemented.
I propose to implement it using the factorization over QQ
. Of course it may not be the best possible solution, but at least it is some (temporary?) workaround. This now gives:
sage: R.<x,y> = ZZ[] sage: p = 12 * (x*y  1) * (x + 2*y + 3) sage: p.factor() 2^2 * 3 * (x + 2*y + 3) * (x*y  1)
Change History (24)
comment:1 Changed 8 years ago by
Branch:  → u/bruno/factorization_of_multivariate_polynomials_over_the_integers 

comment:2 Changed 8 years ago by
Commit:  → 60bffcb71e5220ecb07045c8870be8b84bc5d3bb 

Status:  new → needs_review 
comment:3 followup: 5 Changed 8 years ago by
Status:  needs_review → needs_work 

Add a doctest with a negative sign to show that signs are preserved.
comment:4 Changed 8 years ago by
Commit:  60bffcb71e5220ecb07045c8870be8b84bc5d3bb → 28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d 

Branch pushed to git repo; I updated commit sha1. New commits:
28f89b6  Sign are now preserved + improvements

comment:5 Changed 8 years ago by
Status:  needs_work → needs_review 

Replying to jdemeyer:
Add a doctest with a negative sign to show that signs are preserved.
They were not! Thanks for spotting this :)
.
comment:6 followup: 7 Changed 8 years ago by
I have a question: Since the computation for nonfields is enclosed inside a try
/except
construction, if a computation is long and interrupted with Ctrl+c
, a KeyboardInterrupt
exception is raised and caught by the except
to raise a NotImplementedError
exception.
What is a correct solution so that it does not return NotImplementedError
?
 Should the
KeyboardInterrupt
exception be filtered?  Should the
try
/except
be enclosed insig_on()
/sig_off()
?  Something else?
comment:7 followup: 9 Changed 8 years ago by
Status:  needs_review → needs_work 

Use except Exception:
instead of a bare except:
comment:8 Changed 8 years ago by
Commit:  28f89b6a73649d8c93c4ab0a5bb92f43b6ac785d → 2f1962e623f4ab8ae305e05306579dfd0b4c2ce8 

Branch pushed to git repo; I updated commit sha1. New commits:
2f1962e  Exception better handled

comment:9 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:10 followup: 12 Changed 8 years ago by
You should add an example where the factorisation currently fails (say, over the ring of integers of some number field).
comment:11 Changed 8 years ago by
Status:  needs_review → needs_work 

comment:12 followup: 14 Changed 8 years ago by
Replying to jdemeyer:
You should add an example where the factorisation currently fails (say, over the ring of integers of some number field).
Actually, polynomials over the ring of integers of a number field belong to the class MPolynomial_polydict
(defined in multi_polynomial_element.py
) and not to MPolynomial_libsingular
(defined in multi_polynomial_libsingular.pyx
). So it does not make sense to test this in this file.¹
It would be interesting to have such an example of a nonworking case. Though I do not know for which ring(s) do the polynomials belong to the class MPolynomial_libsingular
.
¹ One may do the same thing for rings of integers of a number field to obtain a factorization algorithm. The point is that the returned factors are not in the rings of integers in this case, so we have to reconstruct them. It's a bit more work than in the current case.
comment:13 Changed 8 years ago by
Commit:  2f1962e623f4ab8ae305e05306579dfd0b4c2ce8 → 0e773f480e56b1b6496ab99f0a9d34623c364998 

Branch pushed to git repo; I updated commit sha1. New commits:
0e773f4  Doctest ZZ/nZZ

comment:14 Changed 8 years ago by
Status:  needs_work → needs_review 

Replying to bruno:
It would be interesting to have such an example of a nonworking case. Though I do not know for which ring(s) do the polynomials belong to the class
MPolynomial_libsingular
.
I haven't been able to find a nonfield integral domain D
, different from ZZ
, such that D['x','y']
belongs to MPolynomial_libsingular
. So I add a doctest for Zmod(4)['x','y']
for which the factorization indeed fails.
comment:15 followup: 17 Changed 8 years ago by
Reviewers:  → Jeroen Demeyer 

Status:  needs_review → needs_work 
Some comments:
 Replace
raise Exception, "Message."
byraise Exception("message")
.
 Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.
 Why did you add the check for symbolic ring? If it's needed, there should also be a doctest added for this case.
 The message
Factorization of multivariate polynomials over Symbolic Ring is not implemented. Consider using multivariate polynomial rings instead.
is confusing, it essentially says "factorization of multivariate polynomials is not supported, use multivariate polynomials instead".
comment:16 Changed 8 years ago by
Commit:  0e773f480e56b1b6496ab99f0a9d34623c364998 → ffe8f4578766dc50cf648e94b7274dce2425318d 

Branch pushed to git repo; I updated commit sha1. New commits:
ffe8f45  Remove useless (?) tests

comment:17 Changed 8 years ago by
Status:  needs_work → needs_review 

Replying to jdemeyer:
 Replace
raise Exception, "Message."
byraise Exception("message")
.
Done.
 Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.
 Why did you add the check for symbolic ring? If it's needed, there should also be a doctest added for this case.
These both tests were not really needed. I added them in order to give more meaningful error messages. Now, the error message for the SymbolicRing
is kind of weird, but the test I added was probably not the right place where to correct this.¹
For nonintegral domains, you know have that multivariate factorization over Ring of integers modulo 4 is not implemented
(for instance) while with the previous version it said that the factorization over nonintegral rings is not implemented. I personally find the previous message more informative, but that is a matter of taste and I am also fine with the current message.
 The message
Factorization of multivariate polynomials over Symbolic Ring is not implemented. Consider using multivariate polynomial rings instead.
is confusing, it essentially says "factorization of multivariate polynomials is not supported, use multivariate polynomials instead".
Not relevant anymore, though I agree with the confusing aspect of this message!
¹ The main problem is that the SymbolicRing
has no is_finite()
method. Thus we get a NotImplementedError
which is not very informative.
comment:19 Changed 7 years ago by
It seems that the code proposed in #2179 is not in its current form ready to use (based on his author's comments). There was supposed to be some improved version, but since it is already 7 years old, we should maybe ignore it for now?
comment:20 Changed 7 years ago by
Yes, probably, I was only pointing out the other ticket just in case there was something relevant there.
comment:21 Changed 7 years ago by
Branch:  u/bruno/factorization_of_multivariate_polynomials_over_the_integers → u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers 

comment:22 Changed 7 years ago by
Commit:  ffe8f4578766dc50cf648e94b7274dce2425318d → c41d743d8733ab8ccd00aee7bde2312cb4751cbd 

Status:  needs_review → positive_review 
New commits:
c41d743  Minor review changes

comment:23 Changed 7 years ago by
Branch:  u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers → c41d743d8733ab8ccd00aee7bde2312cb4751cbd 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:24 Changed 6 years ago by
Commit:  c41d743d8733ab8ccd00aee7bde2312cb4751cbd 

see #20435 for something going wrong
New commits:
Add factorization of multivariate polynomials over the integers