Raise power/Laurent series to fractional powers

[BrentBaccala]

Currently (sage-8.1), only square roots can be taken of power series, and Laurent series don't even implement that. The goal is calculations like this:

sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
sage: (t^3)^(1/3)
t
sage: (1+t)^(1/3)
1 + 1/3*t - 1/9*t^2 + 5/81*t^3 - 10/243*t^4 + O(t^5)

sage: x = Frac(QQ[['x']]).0
sage: g = 1/x^10 - x + x^2 - x^4 + O(x^8)
sage: g^(1/2)
x^-5 - 1/2*x^6 + 1/2*x^7 - 1/2*x^9 + O(x^13)
sage: g^(1/5)
x^-2 - 1/5*x^9 + 1/5*x^10 - 1/5*x^12 + O(x^16)

CC: @videlec

Component: algebra

Keywords: PowerSeries, LaurentSeries

Author: Brent Baccala

Branch/Commit: b3ede94

Reviewer: Vincent Delecroix

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

[BrentBaccala]

Branch: u/gh-BrentBaccala/25209

[BrentBaccala]

comment:1

The patch works by renaming the PowerSeries sqrt() method to nth_root() and extending its logic to handle any integer root. sqrt() method is now just a wrapper around nth_root().

PowerSeries and LaurentSeries pow() methods now check for a fractional power and evaluate it by calling nth_root().

---

New commits:

f020949	Trac #25209: allow power and Laurent series to be raised to fractional powers
1cecfc0	Trac #25209: power series square roots: use sqrt if nth_root unavailable
724dad0	Trac #25209: clean up test cases

[BrentBaccala]

Author: Brent Baccala

[BrentBaccala]

Commit: 724dad0

[sagetrac-git]

Changed commit from 724dad0 to 2864e95

[sagetrac-git]

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

2864e95

Merge origin/develop (8.2.rc3) into u/gh-BrentBaccala/25209

[slel]

comment:3

Related tickets:

• Implement Puiseux polynomials #9289: Implement Puiseux polynomials
  Implement Puiseux polynomials #9289

• Puiseux series #4618: Puiseux series
  Puiseux series #4618

[BrentBaccala]

Changed branch from u/gh-BrentBaccala/25209 to public/25209

[BrentBaccala]

New commits:

f020949	Trac #25209: allow power and Laurent series to be raised to fractional powers
1cecfc0	Trac #25209: power series square roots: use sqrt if nth_root unavailable
724dad0	Trac #25209: clean up test cases
2864e95	Merge origin/develop (8.2.rc3) into u/gh-BrentBaccala/25209
33f3e80	Trac #25209: nth_root() test now returns negative of previous result

[BrentBaccala]

Changed commit from 2864e95 to 33f3e80

[seblabbe]

comment:6

This branch was not written with a recent enough version of Sage. It is adding a method nth_root to the class PowerSeries but a method called nth_root was recently (8.2.beta2, January 1st 2018) added to the same class in #10720. The merge commit 2864e95 is the commit which creates two methods with the same name in the same class.

With this brach, the git log on the file power_series_ring_element.pyx gives:

* 33f3e80 - (trac/public/25209) Trac #25209: nth_root() test now returns negative of previous result (il y a 3 jours) [Brent Baccala]
*   2864e95 - Merge origin/develop (8.2.rc3) into u/gh-BrentBaccala/25209 (il y a 10 jours) [Brent Baccala]
|\  
| * 8820e7b - Remove deprecated PowerSeries._floordiv_ (il y a 3 mois) [Jeroen Demeyer]
| * 3a3bd03 - Implement __pow__ in the coercion model (il y a 4 mois) [Jeroen Demeyer]
| * eddd45d - 10720: doc fixes (il y a 4 mois) [Vincent Delecroix]
| * 3a5d992 - 10720: more examples (il y a 4 mois) [Vincent Delecroix]
| * fc2bb60 - 10720: nth_root for (Laurent) power series (il y a 4 mois) [Vincent Delecroix]
| * ae7a93a - Fix iteritems() calls in Cython code (il y a 6 mois) [Jeroen Demeyer]
* | 724dad0 - Trac #25209: clean up test cases (il y a 10 jours) [Brent Baccala]
* | 1cecfc0 - Trac #25209: power series square roots: use sqrt if nth_root unavailable (il y a 10 jours) [Brent Baccala]
* | f020949 - Trac #25209: allow power and Laurent series to be raised to fractional powers (il y a 11 jours) [Brent Baccala]
|/  
* d24f03d - Typo corrections. (il y a 9 mois) [Jori Mäntysalo]
*   7629851 - Merge tag '8.0.beta9' into t/23103/move_richcmp_stuff_to_new_file (il y a 11 mois) [Jeroen Demeyer]

The branch must be rebased. Also what is the difference between methods sqrt and square_root ?

[sagetrac-git]

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

9045f2b	Trac #25209: allow power and Laurent series to be raised to fractional powers
45a4844	Trac #25209: bug fixes and additional tests in power series nth_root()

[sagetrac-git]

Changed commit from 33f3e80 to 45a4844

[BrentBaccala]

comment:8

OK, let's try this again...

I discarded my version of nth_root() and rebased the other changes to use the nth_root() that was added in December 2017.

There were some bugs in that version of nth_root() that I fixed. Not sure if that should be a separate ticket. I left it in with this one because otherwise the tests for this ticket's code would fail.

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:11

laurent_series_ring_element.pyx:

1. Add spaces around operators right=QQ(r) should be right = QQ(r) (idem right=int(r) in power_series_ring_element.pyx)

2. right = QQ(r) is very bad

sage: QQ(1.3)
13/10

You should rather use QQ.coerce(r).

3. ZZ(val / d) is a bad way of testing whether d divides val. Simply do

if val % d:
    raise ValueError

And then, don't use val / d (that produces rational number) but val // d.

3. You define P = self._parent but then never use it!

power_series_ring_element.pyx:

1. Remove the import of ZZ that you do not use.

2. In

Check precision on `O(x^r)`::

    sage: O(x^4).nth_root(2)
    O(x^2)
    sage: O(x^4).nth_root(4)
    O(x^1)

could you add tests for O(x^m).nth_root(k) where k does not divide m.

[sagetrac-git]

Changed commit from 45a4844 to f066615

[sagetrac-git]

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

f066615

Trac #25209: code cleanup; handle roots of O(x^m) better

[BrentBaccala]

comment:13

Suggested changes implemented.

I did puzzle for a while about how to handle something like O(x^4).nth_root(3). Should this return O(x^1) or O(x^2)?

An argument can be made for O(x^2). After all, if there's a first degree term, then cubing it will result in a third degree term, which is impossible. So maybe this calculation should be rounded up.

I opted for O(x^1) (rounding down), since it seems more conservative.

[videlec]

comment:14

The logic in

    right = int(r)
    if right == r:
        return type(self)(self._parent, self.__u**right, self.__n*right)
 
    try:
        right = QQ.coerce(r)

is quite strange. You first convert r to a Python integer, then test equality with the former right and then coerce to QQ. As a consequence you have misleading error messages

sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
sage: (t^3) ^ "3"
...
ValueError: exponent must be a rational number
sage: sage: (t^3) ^ "1/3"
...
ValueError: invalid literal for int() with base 10: '1/3'

I would rather do the other way around

1. coerce to QQ and raise appropriate error if not possible
2. then treat the case ZZ vs QQ in a if/else statement

[sagetrac-git]

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

b3ede94

Trac #25209: clarify error messages

[sagetrac-git]

Changed commit from f066615 to b3ede94

[BrentBaccala]

comment:16

Suggested change implemented.

[videlec]

comment:17

this is weird

sage: K.<t> = LaurentSeriesRing(QQ, 't', 5)
sage: (O(t^-2))^(1/2)
O(t^-1)
sage: (t^-4 + O(t^-2))^(1/2)
t^-2 + O(1)

[BrentBaccala]

comment:18

Replying to @videlec:

this is weird

sage: K.<t> = LaurentSeriesRing(QQ, 't', 5)
sage: (O(t^-2))^(1/2)
O(t^-1)
sage: (t^-4 + O(t^-2))^(1/2)
t^-2 + O(1)

I think that makes sense. The relative precision remains the same on powering operations.

sage: a = (t^-4 + O(t^-2))^(1/2)
sage: a
t^-2 + O(1)
sage: a^2
t^-4 + O(t^-2)

[videlec]

comment:19

Replying to @BrentBaccala:

Replying to @videlec:
I think that makes sense. The relative precision remains the same on powering operations.

I see. Though I am not completely convinced that this is the good thing to do.

[vbraun]

Changed branch from public/25209 to b3ede94