bug in multivariate factorization over prime fields

[zimmermann6]

after #11829, #11838, #12918, #12928, here is another bug in multivariate factorization over prime fields:

----------------------------------------------------------------------
| Sage Version 5.4.1, Release Date: 2012-11-15                       |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
----------------------------------------------------------------------
sage: U.<y,t> = GF(2)[]  
sage: f
y*t^8 + y^5*t^2 + y*t^6 + t^7 + y^6 + y^5*t + y^2*t^4 + y^2*t^2 + y^2*t + t^3 + y^2 + t^2
sage: f.factor()
y*t^8 + y^5*t^2 + y*t^6 + t^7 + y^6 + y^5*t + y^2*t^4 + y^2*t^2 + y^2*t + t^3 + y^2 + t^2
sage: f % (t^2+t+y+1)
0

When will Sage be usable for this kind of computation?

spkg: http://boxen.math.washington.edu/home/jdemeyer/spkg/singular-3-1-5.p9.spkg (spkg diff)

apply attachment: trac_13770.patch

See also upstream Singular/Singular#215

Upstream: Fixed upstream, but not in a stable release.

CC: @malb @simon-king-jena @alexanderdreyer

Component: commutative algebra

Keywords: sd53, singular, polynomial, factorization

Author: Paul Zimmermann, Jeroen Demeyer

Reviewer: Jean-Pierre Flori

Merged: sage-5.12.rc0

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

[zimmermann6]

comment:1

maybe one should consider replacing Singular by another more reliable component?

Paul

[malb]

comment:2

Paul,

to be fair #13672 isn't a bug in Singular but an issue with Pari and how we use it. Also, I am not sure there is a component we could use besides Singular for factoring. In any case, I've forwarded your bug report.

[koffie]

Upstream: Reported upstream. No feedback yet.

[alexanderdreyer]

comment:5

Replying to @zimmermann6:

maybe one should consider replacing Singular by another more reliable component?

If there were any (for multivariate polynomials etc.), we would immediately use it in Singular.
BTW: when reported upstream, the response time is quite good, I think.

[zimmermann6]

Changed upstream from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

[zimmermann6]

comment:7

from Martin Lee:

I have just committed a fix for this under 15453.

[zimmermann6]

comment:9

Martin Lee tells me the bug is fixed by this commit: Singular/Singular#215

Also it is fixed in Singular 3-1-6. Any plan to upgrade the Singular version?

Martin also tells me Singular 3-1-7 is planned within the next month.

Paul

[zimmermann6]

Attachment: trac_13770.patch.gz

[zimmermann6]

Author: Paul Zimmermann

[zimmermann6]

comment:10

on http://www.loria.fr/~zimmerma/singular-3-1-5.p8.spkg I've put an updated Singular spkg which includes the first patch of Singular/Singular#215. This seems to be enough to solve this bug.

The attached patch adds a non-regression test.

Paul

[jdemeyer]

comment:11

Replying to @zimmermann6:

on http://www.loria.fr/~zimmerma/singular-3-1-5.p8.spkg I've put an updated Singular spkg which includes the first patch of Singular/Singular#215.

Wouldn't it be safer to include all four commits? Did you check whether this solves #14658?

[zimmermann6]

comment:14

Jeroen,

Wouldn't it be safer to include all four commits?

indeed (maybe only the first three, since the last one only adds tests). But I didn't know how to extract the diff, thus I edited the Singular source file manually, it took then several hours on my laptop to recompile the spkg and rebuild Sage, thus I was quite happy it worked (currently running
sage -t --long).

Did you check whether this solves #14658?

unfortunately not. The first example of #14658 does no longer produce an error (same with vanilla 5.11 btw) but the factorization is incomplete:

sage: R.<x1,x2,x3> = QQ['x1,x2,x3']                              
sage: f = (x1+x2+x3)*(2*x1-x2+x3+2)*(4*x1+x2+x3+2)*(8*x1-x2+x3+4)
sage: f.factor()                                                 
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)

The other example still breaks with Floating point exception.

Paul

[zimmermann6]

comment:15

my Singular spkg was corrupted. I made a new one (same url).

Paul

[jdemeyer]

comment:16

When updating a spkg, you should add a Changelog entry in SPKG.txt. Also, changes should be committed to the Mercurial repo (hg add patches/singular_13770.patch and hg commit).

I will make these changes and try to use the 3 commits from the upstream pull request.

[jdemeyer]

Changed author from Paul Zimmermann to Paul ZImmermann, Jeroen Demeyer

[jdemeyer]

comment:17

To download patches from github, see http://stackoverflow.com/questions/6188591/download-github-pull-request-as-unified-diff (I agree it is hard to find out)

[jdemeyer]

comment:18

Also rebasing to #14737.

[zimmermann6]

comment:19

thank you Jeroen for the pointers. I thus let you continue on this ticket.

Paul

[jdemeyer]

Changed author from Paul ZImmermann, Jeroen Demeyer to Paul Zimmermann, Jeroen Demeyer

[zimmermann6]

comment:21

just answering to my own question:

Also it is fixed in Singular 3-1-6. Any plan to upgrade the Singular version?

this is planned in #14333

Paul

[zimmermann6]

Changed author from Paul Zimmermann, Jeroen Demeyer to Paul ZImmermann, Jeroen Demeyer

[jdemeyer]

Changed author from Paul ZImmermann, Jeroen Demeyer to Paul Zimmermann, Jeroen Demeyer

[jdemeyer]

Attachment: singular-3-1-5.p9.diff.gz

[jdemeyer]

comment:25

New spkg is up, but I still need to test it properly myself.

[zimmermann6]

comment:26

#14658 is still not fixed:

sage: R.<x1,x2,x3> = QQ['x1,x2,x3']
sage: f = (x1+x2+x3)*(2*x1-x2+x3+2)*(4*x1+x2+x3+2)*(8*x1-x2+x3+4)
sage: f.factor()
(x1 + x2 + x3) * (2*x1 - x2 + x3 + 2) * (32*x1^2 + 4*x1*x2 - x2^2 + 12*x1*x3 + x3^2 + 32*x1 + 2*x2 + 6*x3 + 8)

Note that we do not even get deterministic answers:

sage: f.factor()
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
sage: f.factor()
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
sage: f.factor()
(x1 + x2 + x3) * (2*x1 - x2 + x3 + 2) * (32*x1^2 + 4*x1*x2 - x2^2 + 12*x1*x3 + x3^2 + 32*x1 + 2*x2 + 6*x3 + 8)
sage: f.factor()
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
sage: f.factor()
(x1 + x2 + x3) * (8*x1 - x2 + x3 + 4) * (8*x1^2 - 2*x1*x2 - x2^2 + 6*x1*x3 + x3^2 + 12*x1 + 4*x3 + 4)
sage: f.factor()
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
sage: f.factor()
(x1 + x2 + x3) * (8*x1 - x2 + x3 + 4) * (8*x1^2 - 2*x1*x2 - x2^2 + 6*x1*x3 + x3^2 + 12*x1 + 4*x3 + 4)
sage: f.factor()
(x1 + x2 + x3) * (64*x1^3 - 24*x1^2*x2 - 6*x1*x2^2 + x2^3 + 56*x1^2*x3 - 8*x1*x2*x3 - x2^2*x3 + 14*x1*x3^2 - x2*x3^2 + x3^3 + 128*x1^2 - 20*x1*x2 - 4*x2^2 + 68*x1*x3 - 4*x2*x3 + 8*x3^2 + 80*x1 - 4*x2 + 20*x3 + 16)
sage: f.factor()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-25-429743410e57> in <module>()
----> 1 f.factor()

/localdisk/tmp/sage-5.11/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_libsingular.so in sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.factor (sage/rings/polynomial/multi_polynomial_libsingular.cpp:26013)()

RuntimeError: Segmentation fault

[jdemeyer]

comment:27

Passes all tests on the buildbot, so needs_review for real.

[jpflori]

Reviewer: Jean-Pierre Flori

[jpflori]

Changed keywords from none to sd53, singular, polynomial, factorization

[jpflori]

comment:28

Looks good.
Lets get this in even though updating to Singular 3-1-6 or even 3-1-7 should supersede it, but needs more serious work.
(Moreover singular website is down right now.)

[jdemeyer]

Merged: sage-5.12.rc0