proof=False unnecessary in factor() #10902

zimmermann6 · 2011-03-10T09:04:47Z

There are currently no known counter examples where Singular would return an incorrect factorisation. It might be very very slow but does not return wrong answers as far as we know. Hence, we should drop proof=False.

Depends on #10903

CC: @malb @simon-king-jena

Component: commutative algebra

Keywords: sd34

Author: Martin Albrecht

Reviewer: Paul Zimmermann

Merged: sage-5.1.beta0

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

The text was updated successfully, but these errors were encountered:

malb · 2011-03-10T10:32:32Z

comment:1

I reported this upstream: http://www.singular.uni-kl.de:8002/trac/ticket/320

zimmermann6 · 2011-03-10T10:37:04Z

comment:2

Dear Martin,

Replying to @malb:

I reported this upstream: http://www.singular.uni-kl.de:8002/trac/ticket/320

this ticket is empty on my browser (firefox). Also, is there a workaround to factor bivariate
polynomials over a prime field from within Sage, in particular over GF(2)?

Paul

malb · 2011-03-10T10:51:59Z

comment:3

Paul, the Singular developers replied on that ticket and state that this bug is fixed in Singular 3-1-2. Updating to 3-1-2 is now #10903.

As for a workaround, I cannot immediately think of any. It's a pretty grim situation, but at least now there is a Singular developer working on factoring.

zimmermann6 · 2011-03-10T10:57:16Z

comment:4

Replying to @malb:

Paul, the Singular developers replied on that ticket and state that this bug is fixed in Singular 3-1-2. Updating to 3-1-2 is now #10903.

As for a workaround, I cannot immediately think of any. It's a pretty grim situation, but at least now there is a Singular developer working on factoring.

thanks Martin. Once Singular is updated to 3-1-2, I will try to find examples where the factorization returned by Singular is incomplete. It would help to have concrete examples
in the documentation.

Paul

malb · 2011-03-10T11:06:46Z

comment:5

3-1-2 should also improve this, but there are some issues that are only resolved in whatever is the next version of Singular, cf. http://www.singular.uni-kl.de:8002/trac/ticket/291#comment:4

sagetrac-dsm · 2011-03-10T11:17:58Z

comment:6

Is this really so bad?

def check(f0, f1):
    CP = CartesianProduct(*[f0.base_ring()]*len(f0.variables()))
    for xvec in CP:
        f0_val = f0.subs(dict((v, xv) for v, xv in zip(f0.variables(), xvec)))
        f1_val = f1.subs(dict((v, xv) for v, xv in zip(f0.variables(), xvec)))
        print xvec, f0_val, f1_val, f0_val == f1_val

sage: f0 = x^5 * y^8 * (x*y^4 + y^3 + 1)
sage: f1 = x^5 * y^6 * (x*y^4 + y^3 + 1)
sage: check(f0, f1)
[0, 0] 0 0 True
[0, 1] 0 0 True
[1, 0] 0 0 True
[1, 1] 1 1 True

The factor of y^2 has no effect, so aren't the two polynomials equivalent in GF(2)? This happens pretty frequently:

sage: f0 = x**8+y**8+1
sage: f1 = f0.factor(proof=False)
sage: f1
(x + y + 1)^6
sage: f1.expand()
x^6 + x^4*y^2 + x^2*y^4 + y^6 + x^4 + y^4 + x^2 + y^2 + 1
sage: check(f0, f1.expand())
[0, 0] 1 1 True
[0, 1] 0 0 True
[1, 0] 0 0 True
[1, 1] 1 1 True

Is there a case where the two expressions aren't equivalent as functions? Or am I missing something obvious like usual?

malb · 2011-03-10T11:40:40Z

comment:7

Replying to @sagetrac-dsm:

Is there a case where the two expressions aren't equivalent as functions? Or am I missing something obvious like usual?

But polynomials over GF(2) are not merely boolean functions. There's a one-to-one mapping between square-free polynomials over GF(2) and boolean functions, but polynomials are more than that. So I'd say it is very bad.

zimmermann6 · 2011-09-23T08:38:08Z

comment:8

here is another example over GF(2):

sage: R.<x,y> = GF(2)[]
sage: p=x^8 + y^8; q=x^2*y^4 + x; f=p*q
sage: lf = f.factor(proof=False)
sage: f-lf
x^10*y^4 + x^2*y^12 + x^8*y^4 + x^6*y^6 + x^4*y^8 + x^2*y^10 + x^9 + x*y^8 + x^7 + x^5*y^2 + x^3*y^4 + x*y^6

An example over GF(3):

sage: R.<x,y> = GF(3)[]
sage: p = -x*y^9 + x
sage: q = -x^8*y^2
sage: f = p*q
sage: f
x^9*y^11 - x^9*y^2
sage: f.factor(proof=False)
y^2 * (y - 1)^6 * x^6

zimmermann6 · 2011-09-23T09:35:09Z

comment:9

and an example over GF(5):

sage: R.<x,y> = GF(5)[]
sage: p=x^27*y^9 + x^32*y^3 + 2*x^20*y^10 - x^4*y^24 - 2*x^17*y
sage: q=-2*x^10*y^24 + x^9*y^24 - 2*x^3*y^30
sage: f=p*q; f-f.factor(proof=False)
-2*x^37*y^33 - 2*x^42*y^27 + x^36*y^33 - 2*x^30*y^39 + x^41*y^27 - 2*x^35*y^33 + x^30*y^34 + 2*x^29*y^34 + x^23*y^40 + 2*x^14*y^48 - x^13*y^48 + 2*x^7*y^54 + 2*x^37*y^18 + 2*x^42*y^12 - x^36*y^18 + 2*x^30*y^24 - x^41*y^12 + 2*x^35*y^18 - x^27*y^25 - 2*x^26*y^25 - x^20*y^31 - x^30*y^19 - 2*x^29*y^19 - x^23*y^25 - 2*x^14*y^33 + x^13*y^33 - 2*x^7*y^39 + x^27*y^10 + 2*x^26*y^10 + x^20*y^16

and one over GF(7):

sage: R.<x,y> = GF(7)[]
sage: p=-3*x^47*y^24
sage: q=-3*x^47*y^37 - 3*x^24*y^49 + 2*x^56*y^8 + 3*x^29*y^15 - x^2*y^33
sage: f=p*q
sage: f-f.factor(proof=False)
2*x^94*y^61 + 2*x^71*y^73 + x^103*y^32 - 2*x^59*y^61 - 2*x^76*y^39 - 2*x^36*y^73 + 3*x^49*y^57 - x^68*y^32 + 2*x^41*y^39 - 3*x^14*y^57

Examples can be constructed at will with the following code (change GF(7) by whatever you want):

R.<x,y> = GF(7)[]
nterms=2
for d in range(1,10^6):
   print d
   sys.stdout.flush()
   p = R.random_element(degree=d,terms=nterms)
   while p.degree()<=0:
      p = R.random_element(degree=d,terms=nterms)
   q = R.random_element(degree=d,terms=nterms)
   while q.degree()<=0:
      q = R.random_element(degree=d,terms=nterms)
   f = p*q
   lp = p.factor(proof=False)
   lq = q.factor(proof=False)
   lf = f.factor(proof=False)
   if lp*lq <> lf:
      print p, q
      raise ValueError

zimmermann6 · 2011-09-23T09:39:13Z

Changed keywords from none to sd34

malb · 2011-09-26T18:35:49Z

comment:12

I just tried all examples of this ticket with #10903 applied and they seem to return correct answers. I suggest we make this ticket dependent on #10903 and add Paul's examples as tests in this ticket.

malb · 2011-09-26T18:35:49Z

Dependencies: #10903

malb · 2011-09-29T14:35:04Z

Author: Martin Albrecht, Paul Zimmermann

malb · 2011-09-29T14:35:04Z

comment:13

The attached patch removes all proof=False from multivariate polynomial factor() calls (being bold!) and adds examples from this ticket as doctests. Paul, can you install #11339, #10903 and this patch and try to break it?

zimmermann6 · 2011-09-29T14:57:12Z

comment:14

Replying to @malb:

The attached patch removes all proof=False from multivariate polynomial factor() calls (being bold!) and adds examples from this ticket as doctests. Paul, can you install #11339, #10903 and this patch and try to break it?

the 2nd patch from #11339 fails to apply on 4.7.1:

sage: hg_sage.import_patch("/tmp/trac_11339_refcount_singular_polynomials.patch")
cd "/localdisk/tmp/install/sage/devel/sage" && hg status
cd "/localdisk/tmp/install/sage/devel/sage" && hg status
cd "/localdisk/tmp/install/sage/devel/sage" && hg import   "/tmp/trac_11339_refcount_singular_polynomials.patch"
applying /tmp/trac_11339_refcount_singular_polynomials.patch
patching file sage/rings/polynomial/multi_polynomial_libsingular.pyx
Hunk #12 FAILED at 765
Hunk #13 FAILED at 783
Hunk #15 FAILED at 820
Hunk #16 FAILED at 862
Hunk #17 FAILED at 883
Hunk #18 succeeded at 832 with fuzz 2 (offset -72 lines).
5 out of 103 hunks FAILED -- saving rejects to file sage/rings/polynomial/multi_polynomial_libsingular.pyx.rej
abort: patch failed to apply

I could try 4.7.2.alpha, where can I download it?

Paul

malb · 2011-09-29T15:13:12Z

comment:15

Yes, you'll need 4.7.2.alpha3:

http://boxen.math.washington.edu/home/release/sage-4.7.2.alpha3/sage-4.7.2.alpha3.tar

zimmermann6 · 2011-09-29T18:29:21Z

Work Issues: spkg fails to build

zimmermann6 · 2011-09-29T18:29:21Z

comment:16

Martin, with 4.7.2.alpha3 the two patches from #11339 apply ok, but the new skpg fails to compile
(on a 64-bit Core2 under Ubuntu):

...
make install in Singular
make[2]: Entering directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src/Singular'
svnversion >svnver
svnversion: relocation error: /usr/lib/libldap_r-2.4.so.2: symbol gnutls_certificate_get_x509_cas, version GNUTLS_1_4 not defined in file libgnutls.so.26 with link time reference
make[2]: *** [svnver] Error 127
make[2]: Leaving directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src/Singular'
make[1]: *** [install] Error 1
make[1]: Leaving directory `/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers/src'
make: *** [/localdisk/tmp/install/sage/local/bin/Singular-3-1-3] Error 2
Unable to build Singular.

real    5m33.608s
user    4m24.880s
sys     0m15.360s
sage: An error occurred while installing singular-3-1-3.svn-algnumbers
Please email sage-devel http://groups.google.com/group/sage-devel
explaining the problem and send the relevant part of
of /localdisk/tmp/install/sage/install.log.  Describe your computer, operating system, etc.
If you want to try to fix the problem yourself, *don't* just cd to
/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers and type 'make check' or whatever is appropriate.
Instead, the following commands setup all environment variables
correctly and load a subshell for you to debug the error:
(cd '/localdisk/tmp/install/sage/spkg/build/singular-3-1-3.svn-algnumbers' && '/localdisk/tmp/install/sage/sage' -sh)
When you are done debugging, you can type "exit" to leave the
subshell.

Any clue?

Paul

malb · 2011-09-29T21:06:19Z

comment:17

The new SPKG should fix this issue.

http://sage.math.washington.edu/home/malb/spkgs/singular-3-1-3-3.spkg

zimmermann6 · 2011-09-30T09:18:29Z

comment:18

I finally managed to apply the 4 patches, I ran sage -b, then installed the spkg, then ran
sage -b again.

However Proof=... seems to be still present somewhere:

sage: R.<x,y> = GF(2)[]
sage: p=x^8 + y^8; q=x^2*y^4 + x; f=p*q
sage: f.factor(proof=False)
x * (x + y)^8 * (x*y^4 + 1)
sage: f.factor()
...
NotImplementedError: proof = True factorization not implemented.  Call factor with proof=False.

Paul

zimmermann6 · 2011-09-30T09:18:29Z

Changed work issues from spkg fails to build to Proof=... still present

malb · 2011-09-30T09:35:17Z

comment:19

for the proof thingy you'll also need to apply the patch from this ticket, i.e.,attachment: trac_10902_factor_fixed.patch

malb · 2012-04-13T16:43:50Z

comment:22

I've rebased the patch to 5.0.beta13 and made sure that sig_on/sig_off are always called, so that one can interrupt the factorisation if it hangs.

zimmermann6 · 2012-04-16T07:14:51Z

comment:23

Sage 5.0.beta13 fails to build on my computer, thus I'll have to wait for beta14 to review that ticket...

Paul

zimmermann6 · 2012-04-16T14:58:09Z

comment:24

thanks to Jeroen, I've managed to build Sage 5.0.beta13. However the issue reported in comment
[comment:20] is still present, whereas it took about one second in Sage 4.8:

sage: K=GF(4,'a')                                                          
sage: a=K.gens()[0]
sage: R.<x,y> = K[]
sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
sage: time r=f.factor(proof=False)
Time: CPU 1.08 s, Wall: 1.23 s
sage: r
y^17 * x^32 * (y^67 + x^60) * ((a + 1)*x^113 + y^28)

I'll be happy when this will be reported in another ticket.

Paul

malb · 2012-04-16T15:11:37Z

comment:25

I've created #12846

zimmermann6 · 2012-04-17T06:51:46Z

Work Issues: doctest failure

zimmermann6 · 2012-04-17T06:51:46Z

comment:26

one doctest fails with sage-5.0.beta13:

tarte% ../../../sage -t devel/sage-10902/sage/categories/quotient_fields.py
...

Expected:
    Traceback (most recent call last):
    ...
    NotImplementedError: proof = True factorization not implemented.  Call factor with proof=False.
Got:
    (x + y)^-1 * y * x

Paul

malb · 2012-04-18T10:21:47Z

Attachment: trac_10902_factor.patch.gz

malb · 2012-04-18T10:22:12Z

comment:27

I've updated the patch.

malb · 2012-04-18T10:22:12Z

Changed keywords from sd34 to none

malb · 2012-04-18T10:22:12Z

Changed work issues from doctest failure to none

zimmermann6 · 2012-04-18T13:42:54Z

comment:28

Martin, why did you remove the sd34 keyword? I had put it since I worked on this ticket during SD34.

Paul

malb · 2012-04-18T13:56:55Z

Changed keywords from none to sd34

malb · 2012-04-18T13:56:55Z

comment:29

Oh, I figured I should remove it since it wasn't resolved at SD34. I added it back.

zimmermann6 · 2012-04-18T16:04:43Z

Reviewer: Paul Zimmermann

zimmermann6 · 2012-04-18T16:04:43Z

comment:30

good work, thanks Martin!

Paul

PS: I removed my name as author since the patch is entirely from you.

zimmermann6 · 2012-04-18T16:04:43Z

Changed author from Martin Albrecht, Paul Zimmermann to Martin Albrecht

jdemeyer · 2012-05-06T12:13:24Z

Merged: sage-5.1.beta0

zimmermann6 added this to the sage-5.0 milestone Mar 10, 2011

zimmermann6 added c: commutative algebra labels Mar 10, 2011

zimmermann6 assigned malb Mar 10, 2011

malb added the s: needs review label Sep 29, 2011

zimmermann6 added s: needs work and removed s: needs review labels Sep 29, 2011

malb added the s: needs review label Apr 13, 2012

zimmermann6 added s: needs work and removed s: needs review labels Apr 17, 2012

malb added s: needs review and removed s: needs work labels Apr 18, 2012

zimmermann6 added s: positive review and removed s: needs review labels Apr 18, 2012

jdemeyer modified the milestones: sage-5.0, sage-5.1 Apr 19, 2012

jdemeyer removed the s: positive review label May 6, 2012

jdemeyer closed this as completed May 6, 2012

malb mentioned this issue Oct 17, 2011

Update Singular to 3-1-3-3 #10903

Closed

saraedum mentioned this issue Jun 6, 2012

is_squarefree() incorrect over imperfect fields #12404

Closed

proof=False unnecessary in factor() #10902

proof=False unnecessary in factor() #10902

Comments

zimmermann6 commented Mar 10, 2011

malb commented Mar 10, 2011

zimmermann6 commented Mar 10, 2011

malb commented Mar 10, 2011

zimmermann6 commented Mar 10, 2011

malb commented Mar 10, 2011

sagetrac-dsm mannequin commented Mar 10, 2011

malb commented Mar 10, 2011

zimmermann6 commented Sep 23, 2011

zimmermann6 commented Sep 23, 2011

zimmermann6 commented Sep 23, 2011

malb commented Sep 26, 2011

malb commented Sep 26, 2011

malb commented Sep 29, 2011

malb commented Sep 29, 2011

zimmermann6 commented Sep 29, 2011

malb commented Sep 29, 2011

zimmermann6 commented Sep 29, 2011

zimmermann6 commented Sep 29, 2011

malb commented Sep 29, 2011

zimmermann6 commented Sep 30, 2011

zimmermann6 commented Sep 30, 2011

malb commented Sep 30, 2011

malb commented Apr 13, 2012

zimmermann6 commented Apr 16, 2012

zimmermann6 commented Apr 16, 2012

malb commented Apr 16, 2012

zimmermann6 commented Apr 17, 2012

zimmermann6 commented Apr 17, 2012

malb commented Apr 18, 2012

malb commented Apr 18, 2012

malb commented Apr 18, 2012

malb commented Apr 18, 2012

zimmermann6 commented Apr 18, 2012

malb commented Apr 18, 2012

malb commented Apr 18, 2012

zimmermann6 commented Apr 18, 2012

zimmermann6 commented Apr 18, 2012

zimmermann6 commented Apr 18, 2012

jdemeyer commented May 6, 2012