Re: Query about factorpadic

[Nigel Smart <nsma@hplb.hpl.hp.com>]

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.