#10369: Yet another bug in factorization over number fields
-----------------------------+----------------------------------------------
Reporter: lftabera | Owner: tbd
Type: defect | Status: new
Priority: critical | Milestone: sage-4.6.2
Component: factorization | Keywords: factorization, number fields
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Description changed by jdemeyer:
Old description:
> 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 t**5 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)
> }}}
New description:
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 t**5 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 [http://pari.math.u-bordeaux.fr/cgi-
bin/bugreport.cgi?bug=1141 PARI bug 1141]. See #10430 for a fix.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10369#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
