Re: algdep broken in CVS?

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

On Mon, 4 Nov 2002, Walter Neumann wrote:
> ? \p 100
>    realprecision = 105 significant digits (100 digits displayed)
> ? algdep(-0.4069120261052675797560574441231568535556673337801938479247370708077934235,9)
> %1 =
> 52775528730.27395999523634651512624857668174274102147702806403796806149593278872705789068364737873087
> ? algdep(-0.4069120261052675797560574441231568535556673337801938479247370708077934235,11)
> %2 = 420674172.111723046968544452271610476025831439935714920459
>
> Here is what 2.1.4 release says:
> gp >  algdep(-0.4069120261052675797560574441231568535556673337801938479247370708077934235,9)
> %1 = 662993*x^9 + 155978*x^8 - 966575*x^7 + 159262*x^6 + 612084*x^5 -
> 1115394*x^4 + 94188*x^3 - 337004*x^2 - 1341138*x - 448594
> gp > algdep(-0.4069120261052675797560574441231568535556673337801938479247370708077934235,11)
> %2 = x^11 - x^10 - 10*x^9 + 9*x^8 + 36*x^7 - 28*x^6 - 56*x^5 + 35*x^4 +
> 35*x^3 - 15*x^2 - 6*x + 1

The NEW result is the expected behaviour. The old one is "broken".

realprecision is '105', but your input has only 73 significant digits, so the
number which is actually sent to algdep has 32 '0' appended to its decimal
expansion. This is relatively far from an algebraic integer of degree <= 11 (
e.g. evaluating the "correct" polynomial on this floating point number yields
~ 1E-73, which is much larger than 1E-105 ).

At \p73, everything is fine.

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.

2.1.4 uses a different, heuristic, algorithm (variant of LLL, with
guesstimated precision). Nothing is guaranteed about the result. We may miss
an obvious polynomial, or return an artefact.

Hope this helps,

    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/