nth_root for (Laurent) power series

[sagetrac-pernici]

There is a nth_root method defined on univariate polynomial (via Newton method)

sage: R.<x> = QQ[]
sage: ((1 + x - x^2)**5).nth_root(5)
-x^2 + x + 1

We provide a more general implementation in a new method _nth_root_series that compute the series expansion of the n-th root for univariate polynomials. Using it we implement straightforward nth_root for univariate (Laurent) power series.

This branch will not consider support for extend=True (see this sage-devel thread). When extend=True the method will simply raise a NotImplementedError while waiting for Puiseux series in Sage (see #4618).

On multi-variate polynomials there is also a nth_root method but which is implemented via factorization (sic)! The multivariate case should just call the univariate case with appropriate variable ordering. This will be dealt with in another ticket.

CC: @robertwb @bgrenet

Component: commutative algebra

Keywords: power series

Author: Mario Pernici, Vincent Delecroix

Branch/Commit: eddd45d

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/10720

[sagetrac-pernici]

Attachment: trac_10720_power_series_nth_root.patch.gz

[sagetrac-pernici]

Description changed:

--- 
+++ 
@@ -40,4 +40,3 @@
 In particular it can be used in the multivariate series considered
 in ticket #1956 .
 
-

[sagetrac-pernici]

Changed keywords from none to power series

[sagetrac-pernici]

Author: mario pernici

[sagetrac-pernici]

Attachment: trac_10720_power_series_nth_root_2.patch.gz

[sagetrac-pernici]

Description changed:

--- 
+++ 
@@ -1,42 +1,4 @@
-In this patch the nth-root of power series `y = x^n` is introduced using
-the Newton method for `y = x^-n`
+computation of an nth root of a power series using the Newton method
 
-```
-x' = (1+1/n)*x - y*x^(n+1)/n               (1)
-```
+Apply trac_10720_power_series_nth_root_2.patch
 
-```
-sage: R.<t> = QQ[]
-sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^3
-sage: p.nth_root(3)
-1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)
-sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^-3
-sage: p.nth_root(-3)
-1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)
-```
-
-The iterations are division-free;
-in the case `n=2` one can compare this division-free iteration
-with the iteration used in the Newton method for `sqrt`
-
-```
-x' = (x +y/x)/2                            (2)
-```
-
-
-`nth_root` can be used to compute the square root of series which
-currently `sqrt` does not support
-
-```
-sage: R.<x,y> = QQ[]
-sage: S.<t> = R[[]]
-sage: p = 1 + x*t + (x^2+y^2)*t^2 + O(t^3)
-sage: p1 = p.nth_root(2); p1
-1 + 1/2*x*t + (3/8*x^2 + 1/2*y^2)*t^2 + O(t^3)
-sage: p1^2
-1 + x*t + (x^2 + y^2)*t^2 + O(t^3)
-```
-
-In particular it can be used in the multivariate series considered
-in ticket #1956 .
-

[sagetrac-pernici]

comment:3

The nth-root of power series y = x^n is computed using
the Newton method for y = x^-n

x' = (1+1/n)*x - y*x^(n+1)/n

sage: R.<t> = QQ[]
sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^3
sage: p.nth_root(3)
1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)
sage: p = (1 + 2*t + 5*t^2 + 7*t^3 + O(t^4))^-3
sage: p.nth_root(-3)
1 + 2*t + 5*t^2 + 7*t^3 + O(t^4)

With this patch nth_root works also for series on ZZ

sage: R.<t> = ZZ[[]]
sage: p = 1 + 4*t^2 + 3*t^3 + O(t^4)
sage: p.nth_root(2)
1 + 2*t^2 + 3/2*t^3 + O(t^4)
sage: p.sqrt(2)
1 + 2*t^2 + 3/2*t^3 + O(t^4)
sage: p.nth_root(3)
1 + 4/3*t^2 + t^3 + O(t^4)
sage: p = 4*t^2 + 3*t^3 + O(t^4)
sage: p.nth_root(2)
2*t + 3/4*t^2 + O(t^3)
sage: p.sqrt(2)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

there is a bug in sqrt in this case.

nth_root can be used to compute the square root of series which
currently sqrt does not support

sage: R.<x,y> = QQ[]
sage: S.<t> = R[[]]
sage: p = 4 + t*x + t^2*y + O(t^3)
sage: p.nth_root(2)
2 + 1/4*x*t + (-1/64*x^2 + 1/4*y)*t^2 + O(t^3)
sage: p = 32*t^5 + x*t^6 + y*t^7 + O(t^8)
sage: p.nth_root(5)
2*t + 1/80*x*t^2 + (-1/6400*x^2 + 1/80*y)*t^3 + O(t^4)
sage: p.sqrt()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' object has no attribute 'sqrt'

nth-root iteration formula is division-free, which is convenient in this
case; in this case sqrt could call nth_root.

nth_root can be used in the multivariate series considered
in ticket #1956 .

[sagetrac-pernici]

comment:4

in the above message there is a wrong example on where sqrt fails;
here is the corrected example

sage: R.<x,y> = QQ[]
sage: S.<t> = R[[]]
sage: p = 4 + t*x + t^2*y + O(t^3)
sage: p.nth_root(2)
2 + 1/4*x*t + (-1/64*x^2 + 1/4*y)*t^2 + O(t^3)
sage: p.sqrt()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' object has no attribute 'sqrt'
}