p-adic square root #23344

dlubicz · 2017-06-30T12:48:57Z

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

The text was updated successfully, but these errors were encountered:

kedlaya · 2017-08-24T21:25:29Z

comment:1

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.

dlubicz · 2017-08-28T07:06:50Z

comment:2

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:

roed314 · 2017-08-28T08:01:17Z

comment:3

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

dlubicz · 2018-03-01T15:25:49Z

Branch: u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields

sagetrac-git · 2018-03-01T15:34:20Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`e64d891`	`added square for unramified 2-adic fields`

sagetrac-git · 2018-03-01T15:34:20Z

Commit: e64d891

roed314 · 2018-03-01T15:38:25Z

Changed branch from u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/ramified_extensions_of_general_p_adic_rings_and_fields

sagetrac-git · 2018-03-01T15:46:04Z

Changed commit from e64d891 to e3a1c86

sagetrac-git · 2018-03-01T15:46:04Z

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`

sagetrac-git · 2018-03-01T15:52:01Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`e64d891`	`added square for unramified 2-adic fields`
`65f2853`	`Merge commit 'e64d891c19b4b5bb1b2b8d666f16f02ad405c67e' of git://trac.sagemath.org/sage into t/23344/sqrt_2`

sagetrac-git · 2018-03-01T15:52:01Z

Changed commit from e3a1c86 to 65f2853

dlubicz · 2018-03-01T15:57:28Z

Changed branch from u/roed/ramified_extensions_of_general_p_adic_rings_and_fields to u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields

roed314 · 2018-03-01T15:58:35Z

Changed branch from u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/ramified_extensions_of_general_p_adic_rings_and_fields

roed314 · 2018-03-01T16:01:08Z

Changed branch from u/roed/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/23344/2adic_sqrt

xcaruso · 2018-03-02T13:23:12Z

comment:12

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

xcaruso · 2018-03-08T20:05:58Z

comment:13

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

roed314 · 2018-03-08T20:22:59Z

comment:14

Replying to @xcaruso:

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

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.

dlubicz · 2018-03-08T20:50:42Z

comment:15

My answer to the first comments of Xavier:

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 ?
yes I will make the change
I have search through the square_root method and I could find only to lines with the keyword sqrt :

ans = self.parent()(self.pari().sqrt())
z = self._inv_sqrt(prec)
the first one is for calling the pari implementation and the second one is a call to the inverse square root method.

yes I will make the change
ok
Ok
I will extend the implementation for odd primes p.
Thanks for your comments and you help !

xcaruso · 2018-03-08T22:57:42Z

Changed branch from u/roed/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt

xcaruso · 2018-03-08T23:01:22Z

Changed commit from 65f2853 to 61ba701

xcaruso · 2018-03-08T23:01:22Z

comment:17

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

sagetrac-git · 2018-03-11T19:18:57Z

Branch pushed to git repo; I updated commit sha1. New commits:

`88e08b2`	`square root for all p-adic fields`

sagetrac-git · 2018-03-11T19:18:57Z

Changed commit from 61ba701 to 88e08b2

xcaruso · 2018-03-11T19:20:16Z

comment:19

I've extended my implementation to all p-adic fields (including ramified extensions of Q_2).

Needs review.

dlubicz · 2018-03-30T08:12:37Z

Changed branch from u/caruso/23344/2adic_sqrt to u/lubicz/23344/2adic_sqrt

sagetrac-git · 2018-03-30T08:13:05Z

Branch pushed to git repo; I updated commit sha1. New commits:

`332fe2c`	`positive review`

sagetrac-git · 2018-03-30T08:13:05Z

Changed commit from 88e08b2 to 332fe2c

dlubicz · 2018-03-30T08:28:36Z

comment:22

In
def _square_root(self):

replaced parent = self.parent() by ring = self.parent()
corrected a bug in the computation of Artin-Schreier equation (carac 2).
Pushed the changes on trac.

xcaruso · 2018-03-30T15:09:32Z

Author: Xavier Caruso

xcaruso · 2018-03-30T15:09:32Z

Reviewer: David Lubicz

fchapoton · 2018-03-31T06:27:12Z

comment:25

patchbot reports failing doctests..

roed314 · 2018-03-31T07:06:38Z

comment:26

It looks like many of the failures result from different choices of square root, but I agree that they need to be fixed.

xcaruso · 2018-03-31T10:36:22Z

Changed branch from u/lubicz/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt

sagetrac-git · 2018-03-31T10:41:13Z

Branch pushed to git repo; I updated commit sha1. New commits:

`44ae009`	`Better ordering of square roots`
`3085538`	`Redo David's changes (sorry: forgot to pull)`

sagetrac-git · 2018-03-31T10:41:13Z

Changed commit from 332fe2c to 3085538

xcaruso · 2018-03-31T10:42:56Z

comment:29

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.

fchapoton · 2018-03-31T16:52:47Z

comment:31

bot is green

xcaruso · 2018-04-02T10:31:36Z

comment:32

OK. So, I give a positive review to this ticket again.
Please change this if you disagree.

vbraun · 2018-05-08T17:27:19Z

Changed branch from u/caruso/23344/2adic_sqrt to 3085538

dlubicz mannequin added this to the sage-8.0 milestone Jun 30, 2017

dlubicz mannequin added c: padics labels Jun 30, 2017

xcaruso added the s: needs review label Mar 11, 2018

dlubicz mannequin added s: positive review and removed s: needs review labels Mar 30, 2018

fchapoton added s: needs work and removed s: positive review labels Mar 31, 2018

xcaruso added s: needs review and removed s: needs work labels Mar 31, 2018

This comment has been minimized.

Sign in to view

fchapoton modified the milestones: sage-8.0, sage-8.2 Mar 31, 2018

xcaruso added s: positive review and removed s: needs review labels Apr 2, 2018

vbraun removed the s: positive review label May 8, 2018

vbraun closed this as completed in d8c7427 May 8, 2018

alexjbest mentioned this issue Dec 29, 2022

Allow for p-adic n-th roots of 0 #26644

Open

p-adic square root #23344

p-adic square root #23344

Comments

dlubicz mannequin commented Jun 30, 2017

kedlaya commented Aug 24, 2017

dlubicz mannequin commented Aug 28, 2017

roed314 commented Aug 28, 2017

dlubicz mannequin commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

roed314 commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

sagetrac-git mannequin commented Mar 1, 2018

dlubicz mannequin commented Mar 1, 2018

roed314 commented Mar 1, 2018

roed314 commented Mar 1, 2018

xcaruso commented Mar 2, 2018

xcaruso commented Mar 8, 2018

roed314 commented Mar 8, 2018

dlubicz mannequin commented Mar 8, 2018

xcaruso commented Mar 8, 2018

xcaruso commented Mar 8, 2018

xcaruso commented Mar 8, 2018

sagetrac-git mannequin commented Mar 11, 2018

sagetrac-git mannequin commented Mar 11, 2018

xcaruso commented Mar 11, 2018

dlubicz mannequin commented Mar 30, 2018

sagetrac-git mannequin commented Mar 30, 2018

sagetrac-git mannequin commented Mar 30, 2018

dlubicz mannequin commented Mar 30, 2018

xcaruso commented Mar 30, 2018

xcaruso commented Mar 30, 2018

fchapoton commented Mar 31, 2018

roed314 commented Mar 31, 2018

xcaruso commented Mar 31, 2018

sagetrac-git mannequin commented Mar 31, 2018

sagetrac-git mannequin commented Mar 31, 2018

xcaruso commented Mar 31, 2018

This comment has been minimized.

fchapoton commented Mar 31, 2018

xcaruso commented Apr 2, 2018

vbraun commented May 8, 2018