Ask Your Question
1

Solving polynomial equations over p-adic fields

asked 2013-02-27 11:56:26 -0500

GaryMak gravatar image

updated 2013-02-27 14:11:37 -0500

kcrisman gravatar image

Hi - as usual I fear my naiv-IT is coming to the fore here, but I have been going around in circles on this for 3 days and I need help please!!

There are 2 basic questions arising from the same thing:

(1) Is "solve" supposed to be implemented for p-adic numbers at all? I can get solutions to things in finite fields but when I try to "lift" them using O(p^n) etc it all goes wrong.

(2) Quite apart from that, why can I not use "solve" using the "variables" (for which I want solutions) as the indeterminates in a polynomial ring over which the equations are already defined? For example, if I define my polynomial ring via:

sage: R.<X> = Zq(3^4,2);

sage: RAB.< a,b> = R[];

and if I then try

sage: solve([a+b==6,a-b==2],[a,b])

it tells me that "a is not a valid variable".

edit retag flag offensive close merge delete

Comments

Hope I formatted these right - let me know...

kcrisman gravatar imagekcrisman ( 2013-02-27 14:11:47 -0500 )edit

thanks - yes - where can I learn that strange hieroglyphics you all use for this stuff so you and @ppurka don't have to keep on correcting my mess please? :)

GaryMak gravatar imageGaryMak ( 2013-02-27 20:59:55 -0500 )edit

Use the toolbar and the live preview you get, before posting. You will see the hieroglyphics :) Use the "10101" like icon to post code. It ensures that the code is properly formatted and typeset in fixed/monospaced font and is syntax highlighted.

ppurka gravatar imageppurka ( 2013-02-28 04:54:14 -0500 )edit

3 answers

Sort by ยป oldest newest most voted
2

answered 2013-02-27 14:15:31 -0500

kcrisman gravatar image

Your second question is fairly easy to answer, though perhaps it's not a fun answer.

sage: type(a)
sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict

sage: solve(a,a)
TypeError: The first argument must be a symbolic expression or a list of symbolic expressions.

solve only works with symbolic expressions, not polynomials, which Sage definitely distinguishes between. (E.g., sin(a) for this a won't work.)

edit flag offensive delete link more

Comments

Hi again - so what coefficient rings are allowed for these symbolic expressions? I guess this is the root of the difficulties I am having ....

GaryMak gravatar imageGaryMak ( 2013-03-01 05:30:07 -0500 )edit

I'm not sure, but I think in general any numeric thing is, but (apparently) not polynomials.

kcrisman gravatar imagekcrisman ( 2013-03-01 13:25:44 -0500 )edit

thanks again ... i have gone quiet while i experiment ....

GaryMak gravatar imageGaryMak ( 2013-03-01 22:16:46 -0500 )edit
0

answered 2013-03-03 00:33:15 -0500

GaryMak gravatar image

Just in case anyone else struggles with these issues in future, here is how I got around the obstacles referred to above and in http://ask.sagemath.org/question/2312.... It was also the reason for the questions http://ask.sagemath.org/question/2114... and http://ask.sagemath.org/question/2059....

I am dealing with systems of equations over the "Hermitian" extensions of finite fields, and trying to lift them to p-adic fields.

For example, I have a vector x of solutions to a set of polynomial equations over GF(p^2) and would like to lift it to the ring O/(p^2) where O is the unique unramified quadratic extension of Z_p [so O/(p^2) may alternatively be described as extending the ring Z/(p^2) by some element t satisfying an irreducible equation of degree 2]. Let J be the Jacobian of my system of equations, and z a vector of unknowns. Let x' be the vector whose entries are 1/p times those of x, regarded either as elements of Z/(p^2) or of Z.

I had to solve the linear equation Jz=-x' mod p (see for example http://math.stackexchange.com/questio...).

Straightforward use of solve() with p-adic or finite ring elements would not work: firstly because of the distinction between polynomials and symbolic ring elements which @kcrisman kindly answered above; secondly (if I tried the p-adic approach) because of the non-implementation of solve with the O(p^n) structure; thirdly (using the finite characteristic approach) because coercing elements within towers of finite fields and/or rings is not yet possible (see http://trac.sagemath.org/11938).

So somehow the only way I could see to do this was to generate the polynomials as abstract expressions in a separate file, multiply them by their Gal(GF(p^2):GF(p))-conjugates if necessary to get rid of the non-integer coefficients, then expand() them and "print" them out (as "P1=...; P2=...;" etc). I then literally cut and paste this output into a completely different file in order to trick the machine into thinking we are dealing with integer coefficient symbolic expressions. Then all of the machinery of solve_mod() and solve_right() and coercion into finite field coefficients etc works wonderfully.

I admit this is clunky, and I would be delighted if anyone were able to point out where I could have done it better!

edit flag offensive delete link more
0

answered 2013-08-09 21:25:04 -0500

dom gravatar image

Hi all, I found very curious not to find any example of Hensel's lifting in p-adics on various SAGE pages (maybe because I am too much newbie in maths,Sage,ask,.. ??). I had same experience than others about the "solve()" : discovering than it's not an all purpose solver... Here is my example for Hensel lifting in p-adics. One hidden difficulty was about 'Symbolic Expression' : very difficult to cast one integer p-adic to constant Expression :-)...explaining why code has various "I want to stay inside Integer scope!" parts.

# Sample for 7-adics: search quadratic root of 2

# We define ring of p-adics here...but only for printing end result
# because Hensel lemma algorithm is NOT Taylor tangent approximation algorithm

w = Integer(7) ; q = 5 ; R = Zp(w,q) ; print 'Working in ring ',R

# Define function, symbolic expression over integer
f(x) = x^2 - 2 ; print 'f : ',f

# Compute derivate functions
F0 = f.diff(0) ; F1 = f.diff(1)

# Set one integer local solution of f(x) = 0 
r0 = Integer(3) ; f0r0 = F0(x=r0) ; f1r0 = F1(x=r0)
print 'Is ',r0,' one local solution ? ', (Mod(f0r0,w) == 0) and (Mod(f1r0,w) != 0)

# Get one new local solution from older one at each step of loop
rk = r0 ; wk = Integer(1)
for k in range(q-1):  
    print ; print '********** Step ',k,'***********' ; print

    # Compute k-th power of w
    wk = w * wk

    # Compute value of F0 and F1 for rk
    f0rk = Integer(F0(x=rk)) ; print 'F0(rk) = ', f0rk 
    f1rk = Integer(F1(x=rk)) ; print 'F1(rk) = ', f1rk 

    # Most important part: 
    #  - f0rk / wk is "Integer" division, removing the w^k factor
    #  - negative (-), multiply and inverse_mod operation in ring R
    t = Integer(f0rk / wk) * inverse_mod(-f1rk,w) ; print t
    rk = rk + Integer(t*wk) ; print rk

# Print result
print ; print  'Result in ring R,  f(',R(rk),') = ',R(f(rk))
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-02-27 11:56:26 -0500

Seen: 954 times

Last updated: Aug 09 '13