proof=False unnecessary in factor()

[zimmerma]

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.

[malb]

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

[zimmerma]

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]

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.

[zimmerma]

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]

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

[dsm]

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]

Replying to 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.

[zimmerma]

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

[zimmerma]

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

[malb]

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]

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?

[zimmerma]

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]

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

[zimmerma]

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]

The new SPKG should fix this issue.

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

[zimmerma]

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

[malb]

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

[zimmerma]

it seems to work much better (no bug found so far) but some factorizations are very slow (or hang), for example:

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: f.factor()

[malb]

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.

[zimmerma]

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

Paul

[zimmerma]

thanks to Jeroen, I've managed to build Sage 5.0.beta13. However the issue reported in 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]

I've created  http://trac.sagemath.org/sage_trac/ticket/12846

[zimmerma]

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]

I've updated the patch.

[zimmerma]

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

Paul

[malb]

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

[zimmerma]

good work, thanks Martin!

Paul

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