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.
`