Nigel Smart on Wed, 15 Jul 1998 07:38:25 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Query about factorpadic |
Hi, (Sorry if none of this makes sense), Say I have a polynomial f \in \Q_p[x] with valuation of the discriminant v. I then factor this up to precision t<v to obtain f = f_1^e_1 f_2^e_2 .. f_r^e_r Now it is NOT true that you can lift this factorization via Hensel's Lemma since t<v. But this factorization does imply results about the `correct' valuation mod p^v. As you increase the exponenent of p you cannot combine the factors together. The only thing that can happen (for example) is that f_1^e_1 = g_1^h_1 g_2^h_2 or f_1^e_1 = g_1 (irreducible) and the such like. So, in your example, (07:32) gp > f=x^5 + 449691864*x^4 - 2209450184054433792*x^3 - 736010060393513697870348288*x^2 + 810634763334812972416233648439689216*x + 263222216157060824115203098902237248565018624; (07:32) gp > (07:32) gp > factorpadic(f,2,10) %2 = [(1 + O(2^10))*x + (2^14 + 2^15 + 2^17 + 2^18 + 2^19 + 2^21 + 2^23 + O(2^24)) 1] [(1 + O(2^10))*x + (2^19 + 2^20 + 2^24 + 2^25 + 2^26 + 2^28 + O(2^29)) 1] [(1 + O(2^10))*x + (2^12 + 2^13 + 2^15 + 2^18 + 2^20 + 2^21 + O(2^22)) 1] [(1 + O(2^10))*x + (2^8 + 2^11 + 2^12 + 2^13 + 2^14 + 2^16 + O(2^18)) 1] [(1 + O(2^10))*x + (2^3 + 2^4 + 2^6 + 2^7 + 2^8 + 2^9 + 2^10 + 2^12 + O(2^13)) 1] (07:32) gp > factormod(f,2) %3 = [Mod(1, 2)*x 5] So mod 2 you get f = f_1^5 mod 2 but when "lifted" (but not using Hensel) we get the factorization f = g_1 g_2 g_3 g_4 g_5 Now these cannot "split" or combine any further since the g_i are now irreducible and have no exponenents. Hence this factorization is gauranteed to lift, but it will not lift via Hensel's Lemma. What you have noticed is that for some examples an algorithm works better than theory predicts. This is because theory deals with worst case behaviour. Yours Nigel P.S. What is padicfactor doing ?(07:37) gp > ?factorpadic This is just ideal decomposition in the quintic field defined by f. See Cohen. (Buchmann-Lenstra) Another way of looking at this is via integral bases computation, the problem is the index divisors. (ROUND 4) This gives rise to the two flags of factorpadic... (07:37) gp > ?factorpadic factorpadic(x,p,r,{flag=0}): p-adic factorization of the polynomial x to precision r. flag is optional and may be set to 0 (use round 4) or 1 (use Buchmann-Lenstra). -- Nigel P. Smart | mail: nsma@hplb.hpl.hp.com Hewlett-Packard Laboratories | talk: +44 (0) 117 922 9338 Filton Road, Stoke Gifford | fax: +44 (0) 117 922 9285 Bristol BS34 8QZ, U.K.