Re: algdep broken in CVS?

[Walter Neumann <neumann@cpw.math.columbia.edu>]

On Thu, 17 Apr 2003, Karim BELABAS wrote:

> On Mon, 7 Apr 2003, Walter Neumann wrote:
> > There still seems to be a bug in algdep:
> >
> > Some time ago Karim wrote
> >
> >>2.2.5 uses PSLQ which either
> >>  * returns a polynomial which evaluates to 0 at the input precision [ I
> >>have just changed that. It used to be "at realprecision" which led to
> >>weird results if you changed the precision after approximating your
> >>algebraic number. Now PSLQ is insensitive to realprecision
> >>
> >>or
> >>
> >>  * returns a real number B and guarantees that no polynomial of height
> >>less than B can evaluate to 0.
> >
> > The following example contradicts this:
> >
> > ? \p 50
> >    realprecision = 57 significant digits (50 digits displayed)
> > ?  a=sqrt(2)+sqrt(3)-5^(1/3)
> > %1 = 1.4362884232652753529760261931717103356444220186443
> > ? algdep(a,12)
> > %2 = 235*x^12 - 479*x^11 + 361*x^10 - 278*x^9 + 1252*x^8 - 1922*x^7 +
> > 337*x^6 + 204*x^5 - 549*x^4 - 1096*x^3 + 1491*x^2 - 113*x + 1361
> > ? x=a
> > %3 = 1.4362884232652753529760261931717103356444220186443
> > ? eval(%2)
> > %4 = 2.171420994059481315 E-37
>
> My comment was unduly precise: "evaluates to 0 at the input precision" is
> something the algorithm cannot guarantee. It's more an expectation than a
> definition ...
>
> The problem is basically as follows: at some point one needs to decide
> whether some real number is "0 to the current precision". If I make this too
> stringent, legitimate relations are missed due to roundoff errors; in the
> other direction I get such artefacts as above.
>
> I have added another heuristic to reduce the likelihood of "spurious"
> relations. It doesn't seem to break anything and it at least cures the
> problem above.
>

Still not working:

 a=sqrt(2)+sqrt(3)-5^(1/2)+2^(1/4)*I
 algdep(a,16)
gives
 ***   precision too low in lindep.
regardless of input precision (I tried \p =  120, 500, 1000)



Even when the PSLQ algorithm works, it seems to be slower than the LLL on
most examples.

--walter