Opened 11 years ago

Closed 11 years ago

#10369 closed defect (fixed)

Yet another bug in factorization over number fields

Reported by: lftabera Owned by: tbd
Priority: critical Milestone: sage-4.6.2
Component: factorization Keywords: factorization, number fields
Cc: jdemeyer Merged in: sage-4.6.2.alpha2
Authors: Jeroen Demeyer Reviewers: Luis Felipe Tabera Alonso
Report Upstream: Fixed upstream, but not in a stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

I have found several issues factoring polynomials over number fields.

First issue, fixed by #10430 (see also #10279):

sage: K.<a> = NumberField(x^6+x^5+x^4+x^3+x^2+x+1); t=polygen(K)
sage: l = (-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7)*t^10 + (4/7*a^5 - 2/7*a^4 - 2/7*a^3 - 2/7*a^2 - 2/7*a - 6/7)*t^9 + (90/49*a^5 + 152/49*a^4 + 18/49*a^3 + 24/49*a^2 + 30/49*a + 36/49)*t^8 + (-10/49*a^5 + 10/7*a^4 + 198/49*a^3 - 102/49*a^2 - 60/49*a - 26/49)*t^7 + (40/49*a^5 + 45/49*a^4 + 60/49*a^3 + 277/49*a^2 - 204/49*a - 78/49)*t^6 + (90/49*a^5 + 110/49*a^4 + 2*a^3 + 80/49*a^2 + 46/7*a - 30/7)*t^5 + (30/7*a^5 + 260/49*a^4 + 250/49*a^3 + 232/49*a^2 + 32/7*a + 8)*t^4 + (-184/49*a^5 - 58/49*a^4 - 52/49*a^3 - 66/49*a^2 - 72/49*a - 72/49)*t^3 + (18/49*a^5 - 32/49*a^4 + 10/49*a^3 + 4/49*a^2)*t^2 + (2/49*a^4 - 4/49*a^3 + 2/49*a^2)*t
sage: factor(l)

Depending on the execution I get two answers. A wrong answer

(-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7) * t^4 * (t^6 + (-19/7*a^5 - 17/7*a^4 - 15/7*a^3 - 13/7*a^2 - 11/7*a - 9/7)*t^5 + (2*a^5 - 10/7*a^4 - 16/7*a^3 + 10/7*a^2 - 2/7*a + 18/7)*t^4 + (-40/7*a^5 - 8/7*a^4 - 40/7*a^3 - 48/7*a^2 - 32/7)*t^3 + (26/7*a^5 - 6/7*a^4 + 26/7*a^3 - 6/7*a^2 - 4/7*a + 34/7)*t^2 + (-20/7*a^5 - 4/7*a^4 - 20/7*a^3 - 4/7*a^2 - 20/7*a - 16/7)*t + 2/7*a^5 - 2/7*a^4 + 2/7*a^3 - 2/7*a^2 + 2/7*a - 2/7)

or a correct answer:

(-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7) * t * (t - a^5 - a^4 - a^3 - a^2 - a - 1)^4 * (t^5 + (-12/7*a^5 - 10/7*a^4 - 8/7*a^3 - 6/7*a^2 - 4/7*a - 2/7)*t^4 + (12/7*a^5 - 8/7*a^3 + 16/7*a^2 + 2/7*a + 20/7)*t^3 + (-20/7*a^5 - 20/7*a^3 - 20/7*a^2 + 4/7*a - 2)*t^2 + (12/7*a^5 + 12/7*a^3 + 2/7*a + 16/7)*t - 4/7*a^5 - 4/7*a^3 - 4/7*a - 2/7)

Second issue:

sage: K.<a> = NumberField(x^6+x^5+x^4+x^3+x^2+x+1); t=polygen(K)
sage: l2 = (1/7*a^2 - 1/7*a)*t^10 + (4/7*a - 6/7)*t^9 + (102/49*a^5 + 99/49*a^4 + 96/49*a^3 + 93/49*a^2 + 90/49*a + 150/49)*t^8 + (-160/49*a^5 - 36/49*a^4 - 48/49*a^3 - 8/7*a^2 - 60/49*a - 60/49)*t^7 + (30/49*a^5 - 55/49*a^4 + 20/49*a^3 + 5/49*a^2)*t^6 + (6/49*a^4 - 12/49*a^3 + 6/49*a^2)*t^5
sage: factor(l2)  # WARNING --- eats all memory

It is t5 times an ireducible polynomial. GP released with Sage computes the factorization without problems, but trying to compute the factorization with Sage the program starts to eat all available RAM and you have to kill the program. GP session of what actually happens (note that l2 is not monic):

K = nfinit(a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)
f = Mod(1, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^10 + Mod(4/7*a - 6/7, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^9 + Mod(9/49*a^2 - 3/7*a + 15/49, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^8 + Mod(8/343*a^3 - 32/343*a^2 + 40/343*a - 20/343, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^7 + Mod(5/2401*a^4 - 20/2401*a^3 + 40/2401*a^2 - 5/343*a + 15/2401, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^6 + Mod(-6/16807*a^4 + 12/16807*a^3 - 18/16807*a^2 + 12/16807*a - 6/16807, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^5
nffactor(K, f)

Second issue is PARI bug 1141. See #10430 for a fix.

Dependencies: #10430, #10279.

Attachments (1)

10369_nffactor.patch (7.8 KB) - added by jdemeyer 11 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 11 years ago by fwclarke

  • Cc jdemeyer added

I think this is very likely a pari bug, and is the same one (http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1132) that was fixed in response to #10279. If I'm right, it would be solved by #10430.

This is the simplest example (of the first problem) that I have found:

trousseau-bash% sage-4.6/sage
----------------------------------------------------------------------
| Sage Version 4.6, Release Date: 2010-10-30                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: L.<a> = QuadraticField(3)
sage: PL.<y> = L[]
sage: (y*(y^2 - (1 + a)/3)*(y^2 - a/2)^2).factor()
y^3 * (y^4 + (-5/6*a - 1/3)*y^2 + 1/6*a + 1/2)

This is the equivalent in pari (producing the same erroneous result):

trousseau-bash% sage-4.6/sage -gp
                   GP/PARI CALCULATOR Version 2.4.3 (development svn-12577:12605)
                    i386 running darwin (x86-64/GMP-4.2.1 kernel) 64-bit version
...
parisize = 8000000, primelimit = 500509
? K = nfinit(a^2 - 3);
? f = x*(x^2 + Mod(-(a + 1)/3, a^2 - 3))*(x^2 + Mod(-a/2, a^2 - 3))^2;
? nffactor(K, f)
%1 = 
[x 3]

[x^4 + Mod(-5/6*a - 1/3, a^2 - 3)*x^2 + Mod(1/6*a + 1/2, a^2 - 3) 1]

But with the version of pari in sage 4.5.3 the result is correct:

trousseau-bash% sage-4.5.3/sage -gp
                            GP/PARI CALCULATOR Version 2.3.5 (released)
                    i386 running darwin (x86-64/GMP-4.2.1 kernel) 64-bit version
 ...
parisize = 8000000, primelimit = 500000
? K = nfinit(a^2 - 3);
? f = x*(x^2 + Mod(-(a + 1)/3, a^2 - 3))*(x^2 + Mod(-a/2, a^2 - 3))^2;
? nffactor(K, f)
%1 = 
[x 1]

[x^2 + Mod(-1/2*a, a^2 - 3) 2]

[x^2 + Mod(-1/3*a - 1/3, a^2 - 3) 1]

comment:2 Changed 11 years ago by jdemeyer

To the submitter of the bug: your l and l2 in the report are the same and this is probably not what you meant.

I can confirm that the first bug involving l is indeed fixed by #10430.

comment:3 Changed 11 years ago by lftabera

  • Description modified (diff)

Interesting, I was not able to reproduce the problem in gp. But being a pari bug makes sense.

I have corrected the second example, with gp I have no problems to factor the polynomial. Maybe the problem is with libpari.

comment:4 Changed 11 years ago by jdemeyer

  • Description modified (diff)

comment:5 Changed 11 years ago by jdemeyer

  • Description modified (diff)

comment:6 Changed 11 years ago by jdemeyer

  • Description modified (diff)

comment:7 Changed 11 years ago by jdemeyer

  • Description modified (diff)

comment:8 Changed 11 years ago by jdemeyer

  • Description modified (diff)

Changed 11 years ago by jdemeyer

comment:9 Changed 11 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from new to needs_review

comment:10 Changed 11 years ago by lftabera

  • Authors set to Jeroen Demeyer
  • Reviewers set to Luis Felipe Tabera Alonso
  • Status changed from needs_review to positive_review

I confirm that the patch solves the problems mentioned for these cases and also some others I have found. With the latests versions of PARI we do not need to be so careful with non-monic polynomials. In the future we may consider eliminating the unit parameter from _factor_pari_helper. It is used right now in a few other places right now though.

The patch also includes some documentation corrections.

Depends on: #10430, #10279.

Positive review.

comment:11 Changed 11 years ago by jdemeyer

  • Report Upstream changed from N/A to Fixed upstream, but not in a stable release.

comment:12 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:13 Changed 11 years ago by jdemeyer

  • Merged in sage-4.6.2.alpha1 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

comment:14 Changed 11 years ago by jdemeyer

  • Status changed from new to needs_review

comment:15 Changed 11 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:16 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.