ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 10 Aug 2013 04:25:04 +0200Solving polynomial equations over p-adic fieldshttps://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/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".Wed, 27 Feb 2013 18:56:26 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/Comment by kcrisman for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18137#post-id-18137Hope I formatted these right - let me know...Wed, 27 Feb 2013 21:11:47 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18137#post-id-18137Comment by GaryMak for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18134#post-id-18134thanks - 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? :)Thu, 28 Feb 2013 03:59:55 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18134#post-id-18134Comment by ppurka for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18132#post-id-18132Use 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.Thu, 28 Feb 2013 11:54:14 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18132#post-id-18132Answer by dom for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=15332#post-id-15332Hi 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.
<pre>
# 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))
</pre>
Sat, 10 Aug 2013 04:25:04 +0200https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=15332#post-id-15332Answer by kcrisman for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=14609#post-id-14609Your 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.)Wed, 27 Feb 2013 21:15:31 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=14609#post-id-14609Comment by kcrisman for <p>Your second question is fairly easy to answer, though perhaps it's not a fun answer.</p>
<pre><code>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.
</code></pre>
<p><code>solve</code> only works with symbolic expressions, not polynomials, which Sage definitely distinguishes between. (E.g., <code>sin(a)</code> for this <code>a</code> won't work.)</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18123#post-id-18123I'm not sure, but I think in general any numeric thing is, but (apparently) not polynomials.Fri, 01 Mar 2013 20:25:44 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18123#post-id-18123Comment by GaryMak for <p>Your second question is fairly easy to answer, though perhaps it's not a fun answer.</p>
<pre><code>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.
</code></pre>
<p><code>solve</code> only works with symbolic expressions, not polynomials, which Sage definitely distinguishes between. (E.g., <code>sin(a)</code> for this <code>a</code> won't work.)</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18122#post-id-18122thanks again ... i have gone quiet while i experiment ....Sat, 02 Mar 2013 05:16:46 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18122#post-id-18122Comment by GaryMak for <p>Your second question is fairly easy to answer, though perhaps it's not a fun answer.</p>
<pre><code>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.
</code></pre>
<p><code>solve</code> only works with symbolic expressions, not polynomials, which Sage definitely distinguishes between. (E.g., <code>sin(a)</code> for this <code>a</code> won't work.)</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18125#post-id-18125Hi again - so what coefficient rings are allowed for these symbolic expressions? I guess this is the root of the difficulties I am having ....Fri, 01 Mar 2013 12:30:07 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?comment=18125#post-id-18125Answer by GaryMak for <p>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!! </p>
<p>There are 2 basic questions arising from the same thing:</p>
<p>(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. </p>
<p>(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:</p>
<pre><code>sage: R.<X> = Zq(3^4,2);
sage: RAB.< a,b> = R[];
</code></pre>
<p>and if I then try </p>
<pre><code>sage: solve([a+b==6,a-b==2],[a,b])
</code></pre>
<p>it tells me that "a is not a valid variable".</p>
https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=14620#post-id-14620Just 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/extensioncoercion-of-finite-rings-fields. It was also the reason for the questions http://ask.sagemath.org/question/2114/unitary-matrices-over-finite-fields and http://ask.sagemath.org/question/2059/explicit-finite-field-extensions.
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/questions/308031/multidimensional-hensel-lifting).
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!Sun, 03 Mar 2013 07:33:15 +0100https://ask.sagemath.org/question/9860/solving-polynomial-equations-over-p-adic-fields/?answer=14620#post-id-14620