Opened 2 years ago

Closed 19 months ago

## #23344 closed enhancement (fixed)

Reported by: Owned by: lubicz major sage-8.2 padics roed, caruso Xavier Caruso David Lubicz N/A 3085538 (Commits) 30855382d325dabb77a7fb1033fa44ba58fbc2f1

This ticket implements square root over p-adic fields (i.e. finite extension of Qp)

### comment:1 Changed 2 years ago by kedlaya

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.

### comment:2 follow-up: ↓ 3 Changed 2 years ago by lubicz

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

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

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

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

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:
```
Last edited 2 years ago by roed (previous) (diff)

### comment:3 in reply to: ↑ 2 Changed 2 years ago by roed

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

### comment:5 Changed 22 months ago by git

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

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

### comment:7 Changed 22 months ago by git

• Commit changed from e64d891c19b4b5bb1b2b8d666f16f02ad405c67e to e3a1c866f8fa3bc534e3434ab2ca066d470b5d5d

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`

### comment:8 Changed 22 months ago by git

• Commit changed from e3a1c866f8fa3bc534e3434ab2ca066d470b5d5d to 65f28536ad731c289db6a150a200d179c4f80647

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`

### comment:12 Changed 22 months ago by caruso

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

### comment:13 follow-up: ↓ 14 Changed 21 months ago by caruso

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
```
Last edited 21 months ago by caruso (previous) (diff)

### comment:14 in reply to: ↑ 13 Changed 21 months ago by roed

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.

### comment:15 Changed 21 months ago by lubicz

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 :

• 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.
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 !

### comment:17 Changed 21 months ago by caruso

• Commit changed from 65f28536ad731c289db6a150a200d179c4f80647 to 61ba7013effe7fd0365f999562afc11e2386142e

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

### comment:18 Changed 21 months ago by git

• Commit changed from 61ba7013effe7fd0365f999562afc11e2386142e to 88e08b2d5d2956d0c4e33b3f4066478774d691d8

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

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

### comment:19 Changed 21 months ago by caruso

• Status changed from new to needs_review

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

Needs review.

### comment:21 Changed 21 months ago by git

• Commit changed from 88e08b2d5d2956d0c4e33b3f4066478774d691d8 to 332fe2c09953fd794804d7b4d9437e0c1ae5f059

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

 ​332fe2c `positive review`

### comment:22 Changed 21 months ago by lubicz

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).
Version 0, edited 21 months ago by lubicz (next)

### comment:23 Changed 21 months ago by lubicz

• Status changed from needs_review to positive_review

### comment:24 Changed 21 months ago by caruso

• Authors set to Xavier Caruso
• Reviewers set to David Lubicz

### comment:25 Changed 21 months ago by chapoton

• Status changed from positive_review to needs_work

patchbot reports failing doctests..

### comment:26 Changed 21 months ago by roed

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

### comment:28 Changed 21 months ago by git

• Commit changed from 332fe2c09953fd794804d7b4d9437e0c1ae5f059 to 30855382d325dabb77a7fb1033fa44ba58fbc2f1

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

### comment:29 Changed 21 months ago by caruso

• Status changed from needs_work to needs_review

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.

### comment:30 Changed 21 months ago by caruso

• Description modified (diff)

### comment:31 Changed 21 months ago by chapoton

• Milestone changed from sage-8.0 to sage-8.2

bot is green

### comment:32 Changed 21 months ago by caruso

• Status changed from needs_review to positive_review

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

### comment:33 Changed 19 months ago by vbraun

• Branch changed from u/caruso/23344/2adic_sqrt to 30855382d325dabb77a7fb1033fa44ba58fbc2f1
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.