Re: Query about factorpadic

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

In response to:
> Message-Id: <E0ywINe-0003ri-00@emu.dpmms.cam.ac.uk>
> From: Kevin Buzzard <K.M.Buzzard@dpmms.cam.ac.uk>
> Date: Wed, 15 Jul 1998 04:37:22 +0100

Elaborating a little further on Nigel's explanation:

> Here's a concrete example.
> 
> ? f=x^5 + 449691864*x^4 - 2209450184054433792*x^3 -
>  736010060393513697870348288*x^2 + 810634763334812972416233648439689216*x
>  + 263222216157060824115203098902237248565018624;
> 
> ? valuation(poldisc(f),2)
> %2 = 148

...it first occurs to me that the coefficients themselves are highly
divisible by 2:

---8<---
(10:25) gp > valuation(449691864,2)
%1 = 3
(10:25) gp > valuation(2209450184054433792,2)
%2 = 11
(10:25) gp > valuation(736010060393513697870348288,2)
%3 = 23
(10:25) gp > valuation(810634763334812972416233648439689216,2)
%4 = 37
(10:25) gp > valuation(263222216157060824115203098902237248565018624,2)
%5 = 56
(10:25) gp > {f=x^5 + 449691864*x^4 - 2209450184054433792*x^3 -
  736010060393513697870348288*x^2 + 810634763334812972416233648439689216*x
  + 263222216157060824115203098902237248565018624;}
(10:26) gp > subst(f,x,8*y)/2^15
%7 = y^5 + 56211483*y^4 - 34522659125850528*y^3 -
  1437519649206081441153024*y^2 + 197908877767288323343807043076096*y
  + 8032904545808740970312594570991126970368
(10:27) gp > valuation(poldisc(%),2)
%8 = 88
--->8---
(Similarly, you can get rid of a factor of 3 in the variable to kill
20 of the 38 factors 3 in the discriminant;  the 5^8 and 7^8, however,
seem to be there to stay.)

This is just one way in which a spuriously large prime power can creep
into the discriminant of a  (univariate, monic, integer-coefficients)
polynomial.

In general, a high valuation of the polynomial discriminant p indicates
some combination of two phenomena:
(a) the prime p is highly ramified in the field generated by a root of
    the polynomial,
(b) the order (ring) generated by the root has index highly divisible
    by p in the maximal order (ring of integers) of the field.
(Sometimes it's just (a) alone:  X^2-2, sometimes just (b) alone:
X^2-2*X-4.)  Integral closure or, equivalently, number field discriminant
algorithms like what Zassenhaus called `round 2' or `round 4' are all
about isolating the effect of (b).

The above was the simplest way in which (b) can happen.  Unfortunately,
it is not easy to tell (a) from (b) by just looking at the polynomial --
essentially you have to work out the p-adic factorization to a sufficient
precision... ;^)

However, as Nigel pointed out, once you have split f into distinct
factors mod p^k for some modest k, and no factor has a repeated root
mod p^k in the Q_p algebra Q_p[X]/(f), you have reached the shore -
factors will never coalesce when you increase k further, they may only
split into smaller pieces.  Once you have distinct linear factors, you
are definitely home.  If you are stuck with higher degree factors,
Newton polygons might help to tell you where in the p-adic realm the
roots are located  (and thus how far you need to increase k to make
further progress).

Enjoy, Gerhard