Opened 11 years ago
Closed 10 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: |
Description (last modified by )
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.
Attachments (1)
Change History (17)
comment:1 Changed 11 years ago by
- Cc jdemeyer added
comment:2 Changed 11 years ago by
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
- 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
- Description modified (diff)
comment:5 Changed 11 years ago by
- Description modified (diff)
comment:6 Changed 11 years ago by
- Description modified (diff)
comment:7 Changed 11 years ago by
- Description modified (diff)
comment:8 Changed 11 years ago by
- Description modified (diff)
Changed 11 years ago by
comment:9 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:10 Changed 11 years ago by
- 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.
Positive review.
comment:11 Changed 11 years ago by
- Report Upstream changed from N/A to Fixed upstream, but not in a stable release.
comment:12 Changed 10 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:13 Changed 10 years ago by
- Merged in sage-4.6.2.alpha1 deleted
- Resolution fixed deleted
- Status changed from closed to new
comment:14 Changed 10 years ago by
- Status changed from new to needs_review
comment:15 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:16 Changed 10 years ago by
- Merged in set to sage-4.6.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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:
This is the equivalent in pari (producing the same erroneous result):
But with the version of pari in sage 4.5.3 the result is correct: