Factorization of multivariate polynomials over the integers

[bgrenet]

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 non-fields 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)

Component: factorization

Keywords: multivariate integer polynomial

Author: Bruno Grenet

Branch: c41d743

Reviewer: Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/17840

[bgrenet]

Branch: u/bruno/factorization_of_multivariate_polynomials_over_the_integers

[bgrenet]

Commit: 60bffcb

[bgrenet]

New commits:

60bffcb

Add factorization of multivariate polynomials over the integers

[jdemeyer]

comment:3

Add a doctest with a negative sign to show that signs are preserved.

[sagetrac-git]

Changed commit from 60bffcb to 28f89b6

[sagetrac-git]

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

28f89b6

Sign are now preserved + improvements

[bgrenet]

comment:5

Replying to @jdemeyer:

Add a doctest with a negative sign to show that signs are preserved.

They were not! Thanks for spotting this :-).

[bgrenet]

comment:6

I have a question: Since the computation for non-fields 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 in sig_on()/sig_off()?
• Something else?

[jdemeyer]

comment:7

Use except Exception: instead of a bare except:

[sagetrac-git]

Changed commit from 28f89b6 to 2f1962e

[sagetrac-git]

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

2f1962e

Exception better handled

[bgrenet]

comment:9

Replying to @jdemeyer:

Use except Exception: instead of a bare except:

Thank you!

[jdemeyer]

comment:10

You should add an example where the factorisation currently fails (say, over the ring of integers of some number field).

[bgrenet]

comment:12

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 non-working 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.

[sagetrac-git]

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

0e773f4

Doctest ZZ/nZZ

[sagetrac-git]

Changed commit from 2f1962e to 0e773f4

[bgrenet]

comment:14

Replying to @bgrenet:

It would be interesting to have such an example of a non-working 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 non-field 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.

[jdemeyer]

comment:15

Some comments:

1. Replace raise Exception, "Message." by raise Exception("message").

2. Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.

3. Why did you add the check for symbolic ring? If it's needed, there should also be a doctest added for this case.

4. 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".

[jdemeyer]

Reviewer: Jeroen Demeyer

[sagetrac-git]

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

ffe8f45

Remove useless (?) tests

[sagetrac-git]

Changed commit from 0e773f4 to ffe8f45

[bgrenet]

comment:17

Replying to @jdemeyer:

1. Replace raise Exception, "Message." by raise Exception("message").

Done.

2. Is the check for integral domain really needed? If it's not an integral domain, it will be caught by the branch below.
3. 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 non-integral 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 non-integral 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.

4. 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. See #18054.

[mezzarobba]

comment:18

Related: #2179

[bgrenet]

comment:19

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?

[mezzarobba]

comment:20

Yes, probably, I was only pointing out the other ticket just in case there was something relevant there.

[jdemeyer]

Changed branch from u/bruno/factorization_of_multivariate_polynomials_over_the_integers to u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers

[jdemeyer]

Changed commit from ffe8f45 to c41d743

[jdemeyer]

New commits:

c41d743

Minor review changes

[vbraun]

Changed branch from u/jdemeyer/factorization_of_multivariate_polynomials_over_the_integers to c41d743

[fchapoton]

Changed commit from c41d743 to none

[fchapoton]

comment:24

see #20435 for something going wrong