Re: algdep broken in CVS?

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

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.

Any regression ?

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]