Gerhard Niklasch on Wed, 15 Jul 1998 10:52:20 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Query about factorpadic |
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