Closed 742ccff4-512f-43e4-bdd0-5df91c799a52 closed 6 years ago
Doesn't this already work? This field L
is an example from the docstring for Qp.extension
.
sage: F = list(Qp(19)['x'](cyclotomic_polynomial(5)).factor())[0][0]
sage: L = Qp(19).extension(F, names='a')
sage: L
Unramified Extension of 19-adic Field with capped relative precision 20 in a defined by (1 + O(19^20))*x^2 + (5 + 2*19 + 10*19^2 + 14*19^3 + 7*19^4 + 13*19^5 + 5*19^6 + 12*19^7 + 8*19^8 + 4*19^9 + 14*19^10 + 6*19^11 + 5*19^12 + 13*19^13 + 16*19^14 + 4*19^15 + 17*19^16 + 8*19^18 + 4*19^19 + O(19^20))*x + (1 + O(19^20))
sage: u = L(4+19).sqrt(); u
2 + 5*19 + 3*19^2 + 11*19^3 + 12*19^4 + 13*19^5 + 11*19^6 + 15*19^7 + 12*19^8 + 18*19^9 + 15*19^10 + 2*19^11 + 9*19^12 + 4*19^13 + 19^15 + 19^16 + 13*19^18 + 3*19^19 + O(19^20)
sage: u^2
4 + 19 + O(19^20)
The syntax sqrt(L(4+19))
also works.
If I am not mistaken, with the version of sage I am working with (8.0.rc0), the square root is working fine for elements of Qp (even if Qp is embeded in an extension) but not for elements of an extension of Qp (not in Q_p). Continuing your example :
sage: a=L.gen()
sage: sqrt(4+19*a)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call last)
<ipython-input-5-842761a28969> in <module>()
----> 1 sqrt(Integer(4)+Integer(19)*a)
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/functions/other.pyc in sqrt(x, *args, **kwds)
2002 except (AttributeError, TypeError):
2003 pass
-> 2004 return _do_sqrt(x, *args, **kwds)
2005
2006 # register sqrt in pynac symbol_table for conversion back from other systems
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/functions/other.pyc in _do_sqrt(x, prec, extend, all)
1903 z = I
1904 else:
-> 1905 z = SR(x) ** one_half
1906
1907 if all:
/home/lubicz/sagemath/sage/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/symbolic/expression.cpp:25800)()
3882 relational_operator(base._gobj))
3883 else:
-> 3884 x = g_pow(base._gobj, nexp._gobj)
3885 return new_Expression_from_GEx(base._parent, x)
3886
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/padics/CR_template.pxi in sage.rings.padics.qadic_flint_CR.CRElement.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:20012)()
672 elif exact_exp:
673 # exact_pow_helper is defined in padic_template_element.pxi
--> 674 right = exact_pow_helper(&ans.relprec, self.relprec, _right, self.prime_pow)
675 if ans.relprec > self.prime_pow.ram_prec_cap:
676 ans.relprec = self.prime_pow.ram_prec_cap
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/padics/padic_template_element.pxi in sage.rings.padics.qadic_flint_CR.exact_pow_helper (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:15216)()
545 exp_val = mpz_get_si((<Integer>right.valuation(p)).value)
546 elif isinstance(_right, Rational):
--> 547 raise NotImplementedError
548 ansrelprec[0] = relprec + exp_val
549 if exp_val > 0 and mpz_cmp_ui(p.value, 2) == 0 and relprec == 1:
NotImplementedError:
Another example which motivates my tickets since I am implementing in sagemath an improved version of the AGM algorithm :
sage: R.<x>=Zq(2^10, 20)
sage: sqrt(1+8*x)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call last)
<ipython-input-10-25d75e2ffffe> in <module>()
----> 1 sqrt(Integer(1)+Integer(8)*x)
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/functions/other.pyc in sqrt(x, *args, **kwds)
2002 except (AttributeError, TypeError):
2003 pass
-> 2004 return _do_sqrt(x, *args, **kwds)
2005
2006 # register sqrt in pynac symbol_table for conversion back from other systems
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/functions/other.pyc in _do_sqrt(x, prec, extend, all)
1903 z = I
1904 else:
-> 1905 z = SR(x) ** one_half
1906
1907 if all:
/home/lubicz/sagemath/sage/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/symbolic/expression.cpp:25800)()
3882 relational_operator(base._gobj))
3883 else:
-> 3884 x = g_pow(base._gobj, nexp._gobj)
3885 return new_Expression_from_GEx(base._parent, x)
3886
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/padics/CR_template.pxi in sage.rings.padics.qadic_flint_CR.CRElement.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:20012)()
672 elif exact_exp:
673 # exact_pow_helper is defined in padic_template_element.pxi
--> 674 right = exact_pow_helper(&ans.relprec, self.relprec, _right, self.prime_pow)
675 if ans.relprec > self.prime_pow.ram_prec_cap:
676 ans.relprec = self.prime_pow.ram_prec_cap
/home/lubicz/sagemath/sage/local/lib/python2.7/site-packages/sage/rings/padics/padic_template_element.pxi in sage.rings.padics.qadic_flint_CR.exact_pow_helper (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:15216)()
545 exp_val = mpz_get_si((<Integer>right.valuation(p)).value)
546 elif isinstance(_right, Rational):
--> 547 raise NotImplementedError
548 ansrelprec[0] = relprec + exp_val
549 if exp_val > 0 and mpz_cmp_ui(p.value, 2) == 0 and relprec == 1:
NotImplementedError:
Replying to @dlubicz:
If I am not mistaken, with the version of sage I am working with (8.0.rc0), the square root is working fine for elements of Qp (even if Qp is embeded in an extension) but not for elements of an extension of Qp (not in Q_p).
I agree. The current implementation just calls off to Pari (see line 2774 in padic_generic_element.pyx
). It would be good if we could have a native implementation that worked for general extensions (not just unramified ones).
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e64d891 | added square for unramified 2-adic fields |
Commit: e64d891
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
ce61f64 | Improve base ring injections for relative extensions of p-adic fields |
16477d3 | Make conversion from residue field work for two-step extensions of p-adics |
1c7cc71 | Fix typo in section method for base ring injection in p-adic two-step extensions |
8be1504 | Fix bugs in creduce and ccoefficients for two-step p-adic extensions |
d53df12 | Add coerce_list back in to the `_populate_coercion_lists_` call in pAdicExtensionGeneric.__init__ |
e68beee | Fix some p-adic doctests |
635021a | Change _poly_rep to always return the polynomial representing the element, not the unit |
67c1f14 | Change the internal base ring for two-step extensions to not show precision when printing, fix bug in base ring coercion |
8939981 | Fix problems in expansion code |
e3a1c86 | Merge commit '8939981e4b02ac12b86f943d93a8baef25e9af51' of git://trac.sagemath.org/sage into t/23218/general_extensions |
Changed branch from u/roed/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/23344/2adic_sqrt
Several comments:
you don't need your function _artin_schreier
since Sage has already methods (e.g. roots
) for solving algebraic equations in finite fields
in the square_root
method, prec
shouldn't be the precision cap of the parent but the actual precision of the element, no?
in the square_root
method, use the sqrt
method for computing the square root modulo p (by the way, I don't understand why this part is needed)
ceil((prec+1)/2.0)
is also 1 + prec // 2
, isn't it?
I would say that our recursive implementation is slower that an iterative one, but I'm not sure
maybe, you could at the same time complete the documentation of the method sqrt
By the way, this ticket only implements sqrt
for unramified extensions of Q2
, is that right? (It's not what is written in the description of the ticket.)
sage: R.<a> = Zq(5^2)
sage: sqrt(1+5*a)
Traceback (most recent call last):
...
NotImplementedError
Replying to @xcaruso:
By the way, this ticket only implements
sqrt
for unramified extensions ofQ2
, is that right? (It's not what is written in the description of the ticket.)
Yeah, I think that's correct. It would be nice to have it also include an implementation for other primes, but that's not currently in the code.
My answer to the first comments of Xavier:
1) artin schreier is very efficient to solve equations of the form x2=ax+b by using a square and multiply type algorithm it shoud perform in ln(n)2 (where n is the degree of Q_q / Q_p) operations in Q_2. I don't know what is the algorithm implemented in roots but it should be less efficient, no ?
2) yes I will make the change
3) I have search through the square_root method and I could find only to lines with the keyword sqrt :
4) yes I will make the change
5) ok
6) Ok
7) I will extend the implementation for odd primes p. Thanks for your comments and you help !
Changed branch from u/roed/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt
I've pushed a new implementation which works over any extension of Qp
for p > 2 and any unramified extension of Q2
(the case of ramified extensions of Q2
is much more subtle).
PS: I've deleted your code; feel free to revert my changes if you think that it's appropriate.
New commits:
830dbba | Merge branch 'develop' into t/23344/23344/2adic_sqrt |
61ba701 | square root over almost all p-adic fields (except ramified extension of Q2) |
Branch pushed to git repo; I updated commit sha1. New commits:
88e08b2 | square root for all p-adic fields |
I've extended my implementation to all p-adic fields (including ramified extensions of Q_2).
Needs review.
Changed branch from u/caruso/23344/2adic_sqrt to u/lubicz/23344/2adic_sqrt
Branch pushed to git repo; I updated commit sha1. New commits:
332fe2c | positive review |
In
def _square_root(self):
Author: Xavier Caruso
Reviewer: David Lubicz
patchbot reports failing doctests..
It looks like many of the failures result from different choices of square root, but I agree that they need to be fixed.
Changed branch from u/lubicz/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt
As David pointed out, the issue was due to the choice/ordering of square roots (which was not consistent when precision varies). I fixed it. Let's see what the patchbot says now.
Description changed:
---
+++
@@ -1 +1 @@
-This ticket will implement the square root over unramified entensions of Z_p
+This ticket implements square root over p-adic fields (i.e. finite extension of Qp)
bot is green
OK. So, I give a positive review to this ticket again. Please change this if you disagree.
Changed branch from u/caruso/23344/2adic_sqrt to 3085538
This ticket implements square root over p-adic fields (i.e. finite extension of Qp)
CC: @roed314 @xcaruso
Component: padics
Author: Xavier Caruso
Branch/Commit:
3085538
Reviewer: David Lubicz
Issue created by migration from https://trac.sagemath.org/ticket/23344