Re: GP: algdep() bug?

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Wed, 8 May 2002, Bill Allombert wrote:
> On Sun, May 05, 2002 at 10:49:04PM -0400, Michael Somos wrote:
> > Pari Developers,
> >
> > I don't know if this is exactly a bug, but perhaps there is some
> > other explanation why it won't find the polynomial :
> >
> > ? p=x^8+1+9424*(-x^7+x^5+x^3-x)+7740*(x^6+x^2)+15494*x^4;
> > ? p2=subst(p,x,I*x^2);
> > ? rp2=polroots(p2);
> > ? r2_7=rp2[7];
> > ? print(algdep(r2_7,16));
> >   ***   precision too low in lindep.
> Algdep can only find relations if there are some. If algdep find no relations,
> it assumes it is a precision problem, not that there are none. Maybe this
> behaviour will be changed when PSLQ is tuned.
>
> ? p=x^8+1+9424*(-x^7+x^5+x^3-x)+7740*(x^6+x^2)+15494*x^4;
> ? p2=subst(p,x,I*x^2);
> ? Q=simplify(p2*conj(p2))
> %3 = x^32 + 88796296*x^28 + 237562140*x^24 - 328674376*x^20 + 4632134*x^16 - 328674376*x^12 + 237562140*x^8 + 88796296*x^4 + 1
> ? factor(Q)
> %4 =
> [x^32 + 88796296*x^28 + 237562140*x^24 - 328674376*x^20 + 4632134*x^16 - 328674376*x^12 + 237562140*x^8 + 88796296*x^4 + 1 1]
>
> This means that there is no relations of degree less than 32, so
> algdep(r2_7,16) can't find anything. Increasing the precision make things
> "worse" since it reduce the chance that algdep find a false relation.
> (with \p9 you find x^5 - 1)
>
> However
> ? r=polroots(p2)[7];
> ? algdep(r,32)
>   ***   precision too low in lindep.
> With \p28 and onward.
>
> This a problem with PSLQ due to the fact that there is too much
> numerical instability, and there is no way to specify the number of correct
> digits in the input.

Actually, it's a problem in lindep, not PSLQ. If PSLQ had been used, a real
number would have been output [failure + lower bound for the height of a
relation].

The current implementation of PSLQ is not able to treat complex numbers at
all, so it calls plain old lindep, which fails less graciously than PSLQ
would.

Btw, PSLQ knows how to find relations with coefficients in Z[i] (not
implanted) but I don't see how to get an integral linear dependance from
there. It's not a problem for algdep, as Bill demonstrated; but for lindep
itself ?

    Karim.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas
--
PARI/GP Home Page: http://www.parigp-home.de/