ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 11 Nov 2013 03:39:31 -0600Roots of p-adic polynomialshttp://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/Hello again,
I want to get the roots of a p-adic polynomial. I wrote the following code:
p = 2
q = 4
K = Qp(p)
L.<omega> = Qq(q)
O_L = L. integer_ring()
pi = L.uniformizer()
q = L.residue_class_degree()
f = X^q + pi*X
f.roots()
This rises following error:
NotImplementedError: root finding for this polynomial not implemented
I still use version 5.10 of Sage. The compile of the latest version 5.12 is ongoing. Do I miss something or is there no way to get the roots in this case?
Will this be implemented in the future or does someone know a workaround?
Thanks for your time again!
Bye
Lars
Mon, 04 Nov 2013 07:54:57 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/Answer by Luca for <p>Hello again,</p>
<p>I want to get the roots of a p-adic polynomial. I wrote the following code:</p>
<pre><code>p = 2
q = 4
K = Qp(p)
L.<omega> = Qq(q)
O_L = L. integer_ring()
pi = L.uniformizer()
q = L.residue_class_degree()
f = X^q + pi*X
f.roots()
</code></pre>
<p>This rises following error:</p>
<pre><code>NotImplementedError: root finding for this polynomial not implemented
</code></pre>
<p>I still use version 5.10 of Sage. The compile of the latest version 5.12 is ongoing. Do I miss something or is there no way to get the roots in this case?</p>
<p>Will this be implemented in the future or does someone know a workaround?</p>
<p>Thanks for your time again!</p>
<p>Bye
Lars</p>
http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?answer=15655#post-id-15655I think polynomial factorization and roots are not implemented over the p-adics. Essentially, we miss Hensel lifting. Ticket [http://trac.sagemath.org/ticket/14828](#14828) will add some useful functions for this, but I doubt it will enter any distribution before 6.x.
Mon, 04 Nov 2013 08:58:20 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?answer=15655#post-id-15655Comment by lars.tennstedt for <p>I think polynomial factorization and roots are not implemented over the p-adics. Essentially, we miss Hensel lifting. Ticket <a href="#14828">http://trac.sagemath.org/ticket/14828</a> will add some useful functions for this, but I doubt it will enter any distribution before 6.x.</p>
http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16785#post-id-16785Thanks for your fast response.
This is too bad. I took a look at this ticket and it looks promising. Unfortunately my knowledge of Python is not enough to help you.
Is it even possible for me as a beginner in Python and Sage to implement Hensel lifting by myself or do I need deep knowledge of Python and Sage for this task?
Is there an alternative to Sage which offers the function to compute p-adic roots of p-adic polynomials? Maybe KASH, Octave, Maple or Magma?
Thanks again!
Bye Lars
Tue, 05 Nov 2013 06:29:22 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16785#post-id-16785Comment by Luca for <p>I think polynomial factorization and roots are not implemented over the p-adics. Essentially, we miss Hensel lifting. Ticket <a href="#14828">http://trac.sagemath.org/ticket/14828</a> will add some useful functions for this, but I doubt it will enter any distribution before 6.x.</p>
http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16784#post-id-16784here is a very simple and buggy Hensel lift I wrote a long time ago (I needed to lift square roots)
def hensel(P, r):
"Basic Hensel lifting. P'(r) must be invertible."
pK = P.base_ring()
w = pK.uniformiser()
r = r.lift_to_precision(min(2*r.precision_absolute(),
P[0].precision_absolute()))
zero = P(r)
v = zero.valuation()
if v <= 0:
raise ValueError, "Impossible to lift."
elif v >= P[0].precision_absolute():
return r
else:
return hensel(P, r - zero / P.derivative()(r))
It fails in many important border cases, but it did its job for me. If you understand it, you can certainly make it work for you.
Magma has Hensel lifting.Tue, 05 Nov 2013 22:39:41 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16784#post-id-16784Comment by lars.tennstedt for <p>I think polynomial factorization and roots are not implemented over the p-adics. Essentially, we miss Hensel lifting. Ticket <a href="#14828">http://trac.sagemath.org/ticket/14828</a> will add some useful functions for this, but I doubt it will enter any distribution before 6.x.</p>
http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16739#post-id-16739Thanks for your response!Mon, 11 Nov 2013 03:39:31 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?comment=16739#post-id-16739Answer by lars.tennstedt for <p>Hello again,</p>
<p>I want to get the roots of a p-adic polynomial. I wrote the following code:</p>
<pre><code>p = 2
q = 4
K = Qp(p)
L.<omega> = Qq(q)
O_L = L. integer_ring()
pi = L.uniformizer()
q = L.residue_class_degree()
f = X^q + pi*X
f.roots()
</code></pre>
<p>This rises following error:</p>
<pre><code>NotImplementedError: root finding for this polynomial not implemented
</code></pre>
<p>I still use version 5.10 of Sage. The compile of the latest version 5.12 is ongoing. Do I miss something or is there no way to get the roots in this case?</p>
<p>Will this be implemented in the future or does someone know a workaround?</p>
<p>Thanks for your time again!</p>
<p>Bye
Lars</p>
http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?answer=15658#post-id-15658Thanks for your fast response.
This is too bad. I took a look at this ticket and it looks promising.
Unfortunately my knowledge of Python is not enough to help you.
Is it even possible for me as a beginner in Python and Sage to implement Hensel lifting by myself or do I need deep knowledge of Python and Sage for this task?
Is there an alternative to Sage which offers the function to compute p-adic roots of p-adic polynomials? Maybe KASH, Octave, Maple or Magma?
Thanks again!
Bye
Lars
Tue, 05 Nov 2013 06:06:00 -0600http://ask.sagemath.org/question/10695/roots-of-p-adic-polynomials/?answer=15658#post-id-15658