#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: |
-----------------------------+----------------------------------------------
Old description:
> I have found several issues factoring polynomials over number fields.
> This time pari seems to work ok, so it is not related to #10279
>
> {{{
> sage: N.<a>=NumberField(x^6+x^5+x^4+x^3+x^2+x+1)
> sage: K.<t>=N[]
> 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
>
> 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)
> }}}
>
> solution that looks right:
>
> {{{
> (-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)
> }}}
>
> With pari I only get the second answer, so it looks like a sage problem.
>
> Next example is different:
>
> {{{
> sage: l2 = (-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
> }}}
>
> The pari 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.
New description:
I have found several issues factoring polynomials over number fields. This
time pari seems to work ok, so it is not related to #10279
{{{
sage: N.<a>=NumberField(x^6+x^5+x^4+x^3+x^2+x+1)
sage: K.<t>=N[]
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
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)
}}}
solution that looks right:
{{{
(-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)
}}}
With pari I only get the second answer, so it looks like a sage problem.
Next example is different:
{{{
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
}}}
It is t**5 times an ireducible polynomial. With the Gp pari 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.
--
Comment(by lftabera):
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10369#comment:3>
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.
