Bill Allombert on Wed, 8 May 2002 20:00:10 +0200

 Re: GP: algdep() bug?

```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.
>
> It seems to me that 4000 digits should be enough, but I have been
> wrong before. Shalom, Michael

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.

For example, with \p28

? subst(Q,x,r)
%9 = -1.354506714903035381 E-19 - 3.97068706 E-20*I

Cheers,

Bill
```