Re: Problem computing in an extension of Q_p

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

[Roland Dreier wrote:] (a long time ago; a mail crash prevented me from seeing
it sooner)
> While following Bjorn's advice on computing in extensions of Q_p, I
> came across the following behavior of gp, which I don't understand
> (apologies for the size of the example, I haven't been able to find a
> smaller example).  I make an element of such a ring, and try to invert
> it.  gp fails to find the reciprocal, even though one exists.  Is this
> a bug?
> 
> Thanks, Roland
> 
> (In the example, a is the element gp thinks is not invertible, and b
> is its inverse; also, lines are wrapped by me, not by gp).
> [...]
> ? a=Mod(Mod(250, 625)*s20^20 + Mod(300, 625)*s20^19 + Mod(600, 625)*s20^18
> + Mod(350, 625)*s20^17 + Mod(100, 625)*s20^16 + Mod(400, 625)*s20^15 +
> Mod(50, 625)*s20^14 + Mod(600, 625)*s20^13 + Mod(15, 625)*s20^12 +
> Mod(185, 625)*s20^11 + Mod(615, 625)*s20^10 + Mod(170, 625)*s20^9 +
> Mod(185, 625)*s20^8 + Mod(340, 625)*s20^7 + Mod(200, 625)*s20^6 + Mod(120,
> 625)*s20^5 + Mod(190, 625)*s20^4 + Mod(145, 625)*s20^3 + Mod(170,
> 625)*s20^2 + Mod(185, 625)*s20 + Mod(36, 625), Mod(1, 625)*s20^21 + Mod(1,
> 625)*s20^19 + Mod(1, 625)*s20^18 + Mod(3, 625)*s20^17 + Mod(2, 625)*s20^16
> + Mod(4, 625)*s20^15 + Mod(2, 625)*s20^14 + Mod(3, 625)*s20^12 + Mod(3,
> 625)*s20^10 + Mod(3, 625)*s20^9 + Mod(4, 625)*s20^8 + Mod(3, 625)*s20^6 +
> Mod(4, 625)*s20^5 + Mod(1, 625)*s20^3 + Mod(2, 625))
> [...]
> ? 1/a
>   ***   non-invertible polynomial in polinvmod.
> 
> ? b=subst(Pol(1/(1-x)+O(x^4)),x,1-a)
> [...]
> ? a*b
> %3 = Mod(Mod(1, 625), Mod(1, 625)*s20^21 + Mod(1, 625)*s20^19 + Mod(1,
> 625)*s20^18 + Mod(3, 625)*s20^17 + Mod(2, 625)*s20^16 + Mod(4, 625)*s20^15
> + Mod(2, 625)*s20^14 + Mod(3, 625)*s20^12 + Mod(3, 625)*s20^10 + Mod(3,
> 625)*s20^9 + Mod(4, 625)*s20^8 + Mod(3, 625)*s20^6 + Mod(4, 625)*s20^5 +
> Mod(1, 625)*s20^3 + Mod(2, 625))

It's not really a bug, rather a shortcoming of the underlying algorithm
(simple-minded extended gcd), which assumes that the euclidian remainder
sequence can be performed, i.e leading coeffs will be invertible. This works
nicely over a domain (possibly by going to the fraction field), but not here.

A (little bit stupid but) foolproof solution to invert your elements would be
to use:

  z = 1 / Mod(lift(a.pol), lift(a.mod))

then project back (simplifing the content (denominators) first then
multiplying at the end may speed up things a bit).


Given the current internal data structures, I won't include that in the
general algorithm though: it would be an inefficient ugly patch, which can
easily be emulated from the user's side. It'll have to wait for a (much
needed) implementation of finite fields / local fields (F_p and Q_p are ok,
but extensions are a pain), incuding specific types, e.g. "element in F_q",
which is very inefficiently handled by the "embedded Mod()" idiom.

   Karim.
--
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://pari.home.ml.org