Kevin Buzzard on Wed, 15 Jul 1998 15:11:47 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Query about factorpadic

Thanks Nigel, Gerhard.

Say I have a polynomial f in Z_p[X] and run factorpadic(f,p,pr) where
pr is smaller than the valuation of the discriminant of f.

Nigel says that the "shape" of the result might not be trusted.
While this sounds likely, after a little playing around I can't
find an f such that the shape of its factorisation changes
when you change the precision.
(try e.g. factorpadic(x^2 + 2*x - 1023 + 65536,2,2) to see an
example of factorpadic doing very well! It spots that the
roots are distinct even though they are the same mod 2^2)

So the precise question I have (which of course I should have asked
the first time round) is: if factorpadic(f,p,pr) as above tells me that
there is a factor g of f, then 

(a) is there a genuine factor G of f in Z_p[X] such that G mod p^pr is g?

(b) If so, is G going to be irreducible?

Presumably the answer to these questions is no, but random testing
shows that factorpadic does seem to have a good record on stuff
like this [of course this is probably just Nigel's motto that
an algorithm frequently works better than its worst possible case]

Gerhard---you're right that some of the 2's in this polynomial are
bogus (it's an old theorem that 2^3 divides all the roots
of these char polys!). But from your other comments, are
you implying that (a) above is true, at least if g is linear?


[PS regardless of whether factorpadic can be trusted in general, I have
solved my problem for the cases in hand---I use factorpadic with
a low precision to find (or should this be "guess"?) some roots mod p^r
in finite extensions of Q_p but *then* if r is large enough (say, a bit larger
than the valuation of the root), I can use Hensel to very quickly
both verify that these are roots and to find them mod p^N for
very large N very quickly. Even though the valuation of the disc is large,
this is, in my examples, because the valuations of some of the roots are
large, and I can find the roots with small valuation without too much trouble!
In fact this seems to give me a pseudoalgorithm which works rather well.]