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? Kevin [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.]