bug in factoring univariate polynomial over number field?
Niels
I think the following is a bug (only complete factorization after 2 steps):
sage: R = PolynomialRing( QQ, var( 't' ), order = 'lex' )
sage: t = R.gens()[0]
sage: f = t^4 - t^2 + 1
sage: T = NumberFieldTower( [f], 'a0' )
sage: R1 = R.change_ring( T )
sage: a0 = T.gens()[0]
sage: t = R1.gens()[0]
sage: poly = t^3 + (-4*a0^3 + 2*a0)*t^2 - 11/3*a0^2*t + 2/3*a0^3 - 4/3*a0
sage: poly.factor()
(t - 2*a0^3 + a0) * (t^2 + (-2*a0^3 + a0)*t - 2/3*a0^2)
sage: fact = poly.factor()[1][0]
sage: fact.factor()
(t - 4/3*a0^3 + 2/3*a0) * (t - 2/3*a0^3 + 1/3*a0)
Kind regards,
Niels
Jeroen Demeyer
Version: 2.4.4 (development svn-12706M)
This was reported by Niels Lubbes as Sage bug on
sage-...@googlegroups.com:
gp> t; nf = nfinit(a^4 - a^2 + 1);
gp> poly = t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + 2/3*a^3 - 4/3*a
%1 = t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + (2/3*a^3 - 4/3*a)
gp> F = nffactor(nf, poly)
%2 =
[t + Mod(-2*a^3 + a, a^4 - a^2 + 1) 1]
[t^2 + Mod(-2*a^3 + a, a^4 - a^2 + 1)*t + Mod(-2/3*a^2, a^4 - a^2 + 1) 1]
However, the second factor is reducible:
gp> nffactor(nf, F[2,1])
%3 =
[t + Mod(-4/3*a^3 + 2/3*a, a^4 - a^2 + 1) 1]
[t + Mod(-2/3*a^3 + 1/3*a, a^4 - a^2 + 1) 1]
Cheers,
Jeroen.
Jeroen Demeyer
> Hi,
>
> I think the following is a bug (only complete factorization after 2 steps):
Yes, it is a bug. The problem is with the upstream package PARI/GP.
luisfe
gp: poly = t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + 2/3*a^3 - 4/3*a
[t + Mod(-2*a^3 + a, a^4 - a^2 + 1) 1]
[t + Mod(-2/3*a^3 + 1/3*a, a^4 - a^2 + 1) 1]
Note that with the new pari, it is not needed nfinit any more. We
should avoid calling R.nfinit in self.factor() and only use the
nffactor command if the nf structure is already computed and cached.
This is another issue that would not solve the problem though.
Jeroen Demeyer
> gp: poly = t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + 2/3*a^3 - 4/3*a
> t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + (2/3*a^3 - 4/3*a)
> gp: factornf(poly, a^4 - a^2 +1)
>
> [t + Mod(-2*a^3 + a, a^4 - a^2 + 1) 1]
>
> [t + Mod(-4/3*a^3 + 2/3*a, a^4 - a^2 + 1) 1]
>
> [t + Mod(-2/3*a^3 + 1/3*a, a^4 - a^2 + 1) 1]
>
> Which is the correct answer.
True. I never understood why there exists nffactor() and factornf()
which do the same thing (but apparently with different implementations!)
Jeroen.
John Cremona
According to Karim, one of these is now obsolete and should not be
used. But I can never remember which....
John
>
> Jeroen.
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
luisfe
On Nov 15, 3:21 pm, John Cremona <john.crem...@gmail.com> wrote:
>
> According to Karim, one of these is now obsolete and should not be
> used. But I can never remember which....
>
> John
http://trac.sagemath.org/sage_trac/ticket/7097
factornf uses Trager's trick and is deprecated in favor of nffactor,
which does not need any more nfinit structures to work.
luisfe
this problem?
Dr. David Kirkby
> About this problem. Should one open a new ticket or reopen 7097 for
> this problem?
>
Open a new one. This is closed an apparently fixed - don't reopen it. But put a
link to the other ticket if that seem appropiate
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing in e-mail?
Dave
Jeroen Demeyer
> About this problem. Should one open a new ticket or reopen 7097 for
> this problem?
I would say: let's wait and see what upstream says (I will keep an eye
on the PARI bug).
Jeroen.
Dr. David Kirkby
But surely if a bug is found, it should be on trac.
Dave
Jeroen Demeyer
> But surely if a bug is found, it should be on trac.
Should a PARI bug be on the Sage Trac? What's the point if it already
was reported to PARI?
Anyway, if you want you can go ahead and make the ticket but there is
not much we can do anyway besides waiting for PARI to fix the problem...
Jeroen.
John Cremona
> On 2010-11-15 17:23, Dr. David Kirkby wrote:
>> But surely if a bug is found, it should be on trac.
>
> Should a PARI bug be on the Sage Trac? What's the point if it already
> was reported to PARI?
I think the point is that another Sage user might come up against the
bug without knowing that it was caused by an upstream bug.
>
> Anyway, if you want you can go ahead and make the ticket but there is
> not much we can do anyway besides waiting for PARI to fix the problem...
>
When the bug is fixed upstream, Sage will have to change -- by
upgrading its PARI spkg. And that needs a ticket!
luisfe
This is now #10279