Re: Preparing PARI 2.3

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

* Bill Allombert [2004-01-28 02:11]:
> Above is a mail I sent a year ago that listed some problems that needed
> to be addressed before releasing.
>
> > --- The polrootspadic(x^2+8*x+4, 2, 2) bug is still not fixed.
>
> It is rather annoying, since PARI 2.1 give the correct result while 2.2
> give another (incorrect) result.

I believe this can (and should!) wait. See final comments below.

Both stable and unstable usually give an "incorrect" inconsistent result
is the precision is small. E.g

(16:42) gp > for (i = 1, 4, print( polrootspadic((x+1)^2-27,3,i) ) )
[2 + O(3)]~
[2 + O(3^2), 2 + 3 + O(3^2)]~
[2 + 2*3 + 2*3^2 + O(3^3)]~
[]~

(16:45) gp > for(i = 1, 4, print( polrootspadic(x^2-27, 3, i) ) )
[O(3)]~
[]~      \\ because ( O(3^2) )^2 = O(3^4), not Mod(0, 9)
[]~
[]~

(16:45) gp > polrootspadic((x-1)^2 + O(3^3), 3, 100)
%1 = [1 + O(3^100)]~

The exact problem is: do we want polrootspadic(A, p, r) to return

1) an existing p-adic root of A (in Qp), given to relative accuracy r ?
[ consistent with polroots() ]

2) the roots of A in Z / p^r ? 

As for 1), it can already be optained via factorpadic. It is in general
impossible to answer the question if coefficients of A are (inexact) p-adic
numbers. It might require a huge amount of computation to decide whether a
root exists or not, even if r = 1. True, it is still much easier/faster than
factorpadic().

As for 2), polrootspadic currently does this for the roots which are not  0
mod p (because of the phenomenon described in the comment above). No other
routine does it and it would be straightforward to implement it consistently
(including 0 mod p !). We have a minor problem when A has non-p-integral
coefficients but one can always raise an error.

It should be fixed as 1) but 2) is also useful. Probably more so.

Notes:
1) padicappr() has the same problem.

2) the various polroots routine are inconsistent wrt multiplicities: polroots
and polrootsmod(,,1) repeat roots, the others don't.

3) we badly need a FqX_roots routine ( easy from factmod9 code ),
there's a ridiculous loop over Fq in padicappr(). Also we must rename

  factmod0 --> FpX_factor

and have factmod9 / rootmod be simple wrappers for

  factmod9 --> FqX_factor 
  rootmod  --> FpX_roots

In short, there's a lot of (simple but annoying) work to do to properly fix
the problem. The problem is not specific to the unstable branch (only a few
specific instances are), and has been with us since the beginning.

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/ 
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]