Re: Query about factorpadic

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In further response to our little thread:
> Date: Wed, 15 Jul 1998 15:39:52 +0100
> Message-Id: <647.199807151439@omega.ex.ac.uk.maths.exeter.ac.uk>
> From: "John Cremona (Maths)" <cremona@maths.ex.ac.uk>
[rearranging...] 
> I think that this discussion should probably not be going on via the
> pari users' list...?

Why not?  It's about how to use PARI/GP to do one's mathematics.

> Nigel is wrong: when x is odd, the valuation of 2x+2 can be anything
> positive, even infinite (x=-1).  For a quadratic there cannot be any
> distinction between lifting a root and lifting a factorization.

(The valuation of the discriminant can be computed in terms of the
valuations of f'(alpha) at each root alpha -- indeed, since the
discriminant of f, up to sign, is the resultant of f and f', it
is also the product of the f'(alpha), up to a constant which shouldn't
matter if f was monic to start with.  Everything with a pinch of salt
about normalizations of valuations etc when the roots do not lie in
Q_p itself but in an extension.)

> It seems that factorpadic(f,p,r) is not the same as factoring f mod
> p^r in (Z/p^r)[X], but rather the mod p^r approximation to the ACTUAL
> p-adic factorization.

Yes.  Let's have a glance at a chunk of code from factorpadic4()
in src/basemath/polarit1.c:
---8<---
  poly=squarefree(f,&ex); nbpoly=lg(poly)-1;
  res=cgetg(3,t_MAT);
  res[1]=lgetg(n+1,t_COL);
  res[2]=lgetg(n+1,t_COL);
  for (j=1,i=1; i<=nbpoly; i++)
  {
    long av1 = avma;
    fx=(GEN)poly[i]; mfx=ggval(discsr(fx),p);
    m = (r<=mfx)?mfx+1:r;
    w = factmod(fx,p); g = bestnu((GEN)w[1]);
    if (lg(w[1])==2)
      resint = nilordpadic(p,m,fx,mfx,g);
    else
      resint = Decomppadic(p,m,fx,mfx,polx[v],fx,g);
--->8---

We begin with squarefree factorization  (so Kevin's polynomial was
already squarefree)  followed by a loop over the factors obtained at
this first stage.  Then m is set as large as necessary based on the
input precision r as well as the valuation of the discriminant of
the current factor  (discsr is the subresultant algorithm),  the
factor is factored mod p, and each piece is processed further at
precision m...

In other words, the round4 implementation of factorpadic() (selected
by default) knows about the precision required in the worst case.

Gerhard