bug in revert method for lazy power series

[DavidAyotte]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**:
- **Sage Version**: 10.0.beta3

Steps To Reproduce

No response

Expected Behavior

sage: L = LazyPowerSeriesRing(QQ, 'z')
sage: f = lambda n: 1 if ZZ(n).is_power_of(2) else 0
sage: lazy_f = L(f); lazy_f
z + z^2 + z^4 + O(z^7)
sage: lazy_f.revert()
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)

Actual Behavior

sage: L = LazyPowerSeriesRing(QQ, 'z')
sage: f = lambda n: 1 if ZZ(n).is_power_of(2) else 0
sage: lazy_f = L(f); lazy_f
z + z^2 + z^4 + O(z^7)
sage: lazy_f.revert()
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7f3209489720>) failed: ValueError: inverse does not exist>

Additional Information

Strangely, when we ask for any slice of the coefficients, then method starts to work:

sage: L = LazyPowerSeriesRing(QQ, 'z')
sage: f = lambda n: 1 if ZZ(n).is_power_of(2) else 0
sage: lazy_f = L(f); lazy_f
z + z^2 + z^4 + O(z^7)
sage: lazy_f.revert()
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7f3209489720>) failed: ValueError: inverse does not exist>
sage: lazy_f[:1]
[]
sage: lazy_f.revert()
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)

@mantepse @dcoudert @tscrim

[mantepse]

For starters, here is a workaround:

sage: L = LazyPowerSeriesRing(QQ, 'z')
sage: lazy_f = L(f, valuation=1); lazy_f
z + z^2 + z^4 + O(z^8)
sage: lazy_f.revert()
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)

[mantepse]

The relevant bit of LazyPowerSeries.revert is as follows:

    def revert(self):
...
        if coeff_stream[0]:
            raise ValueError("cannot determine whether the compositional inverse exists")

        g = P.undefined(valuation=1)
        # the following is mathematically equivalent to
        # z / ((self / z)(g))
        # but more efficient and more lazy
        g.define((~self.shift(-1)(g)).shift(1))
        return g

Possibly, but I am not sure yet, the problem is that LazyPowerSeries.shift(-1) ignores that we know that self has valuation 1, and returns a series with (approximate) valuation -1:

sage: lazy_f = L(f); lazy_f
z + z^2 + z^4 + O(z^7)
sage: h = lazy_f.shift(-1)
sage: h._coeff_stream._approximate_order
-1

[mantepse]

It might be that #34556 helps, although, even if it does, it might not be the correct fix. @tscrim, do you think we could dedicate a few days of zoom meetings on this issue (eg., during the easter week)?

[mantepse]

Indeed, this would fix it. I'll prepare a pull request, however, as I said, I don't know whether it is a good idea. In particular, it might slow down the code significantly.

[tscrim]

The fact that it is returning a negative approximate order for the power series would be something to avoid in and of itself, but that might be a bit tricky and is not strictly necessary to do.

I don’t think #34556 will help, and even if it does, it is not the correct fix in my mind. I think the fact that the _approximate_order is not getting set correctly by the shift is something that needs to be fixed on its own. I will try to take a look to see what can be done in the next day or two.

@mantepse Yes, we can do a few Zoom calls, although the week before and after Easter is a bit tricky for me. However, I should be able to do at least one or two calls during that time. If we could do it at the beginning of this upcoming week, that would be much better for me.

[mantepse]

@tscrim, OK, let's see, would tomorrow (Monday) 16:00 Tokyo time work for you?

#34556 (= #35265) actually does fix the problem at hand, but not much more. I'm a bit foggy right now, however, so I may have made a mistake. In 10.0.beta3:

sage: L.<z> = LazyPowerSeriesRing(QQ)
sage: fun = lambda n: 1 if ZZ(n).is_power_of(2) else 0

sage: f = L(fun)
sage: f.revert()
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7fbe92512760>) failed: ValueError: inverse does not exist>

sage: f.shift(-1)._coeff_stream._approximate_order
-1

sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((~f.shift(-1)(g)).shift(1))
sage: g
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7fbe9283b6b0>) failed: ValueError: inverse does not exist>

sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((z - (f - z)(g)))
sage: g
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7fbe91a679d0>) failed: ValueError: generator already executing>

With #35265:

sage: L.<z> = LazyPowerSeriesRing(QQ)
sage: fun = lambda n: 1 if ZZ(n).is_power_of(2) else 0
sage: f = L(fun)
sage: f.revert()
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)
sage: f.shift(-1)._coeff_stream._approximate_order
0
sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((~f.shift(-1)(g)).shift(1))
sage: g
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7f4738bc9950>) failed: ValueError: inverse does not exist>
sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((z - (f - z)(g)))
sage: g
<repr(<sage.rings.lazy_series_ring.LazyPowerSeriesRing_with_category.element_class at 0x7f4738aa9ef0>) failed: ValueError: generator already executing>

[tscrim]

@mantepse Yes, that is good for me. Please email me a Zoom link.

I will look tomorrow morning/afternoon to see what’s going on and other possible fixes.

[tscrim]

Another issue with shifting:

sage: L.<x,y> = LazyPowerSeriesRing(QQ)
sage: x.shift(-1)
x

We probably just need to raise an error when the arity it greater than 1.

[mantepse]

It appears that with the following fixes this works also, without #35265. I am not sure what to do, but I think we should try to get a fix into 10.0. What do you think?

diff --git a/src/sage/data_structures/stream.py b/src/sage/data_structures/stream.py
index f8f6dc6a186..b86cb81be70 100644
--- a/src/sage/data_structures/stream.py
+++ b/src/sage/data_structures/stream.py
@@ -1853,16 +1853,19 @@ class Stream_cauchy_compose(Stream_binary):
         fv = self._left._approximate_order
         gv = self._right._approximate_order
         if n < 0:
-            return sum(self._left[i] * self._neg_powers[-i][n]
-                       for i in range(fv, n // gv + 1))
+            return sum(f_coeff_i * self._neg_powers[-i][n]
+                       for i in range(fv, n // gv + 1)
+                       if (f_coeff_i := self._left[i]))
         # n > 0
         while len(self._pos_powers) <= n // gv:
             # TODO: possibly we always want a dense cache here?
             self._pos_powers.append(Stream_cauchy_mul(self._pos_powers[-1], self._right, self._is_sparse))
-        ret = sum(self._left[i] * self._neg_powers[-i][n] for i in range(fv, 0))
+        ret = sum(f_coeff_i * self._neg_powers[-i][n] for i in range(fv, 0)
+                  if (f_coeff_i := self._left[i]))
         if n == 0:
             ret += self._left[0]
-        return ret + sum(self._left[i] * self._pos_powers[i][n] for i in range(1, n // gv+1))
+        return ret + sum(f_coeff_i * self._pos_powers[i][n] for i in range(1, n // gv + 1)
+                         if (f_coeff_i := self._left[i]))

I tested the following:

sage: L.<z> = LazyPowerSeriesRing(QQ)
sage: fun = lambda n: 1 if ZZ(n).is_power_of(2) else 0
sage: f = L(fun)
sage: f.revert()
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)
sage: f.shift(-1)._coeff_stream._approximate_order
-1
sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((~f.shift(-1)(g)).shift(1))
sage: g
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)
sage: f = L(fun)
sage: g = L.undefined(valuation=1)
sage: g.define((z - (f - z)(g)))
sage: g
z - z^2 + 2*z^3 - 6*z^4 + 20*z^5 - 70*z^6 + 256*z^7 + O(z^8)

[mantepse]

I think that #35291 is a good fix, and, if it really is, I'd like to get it into the 10.0 release.

I am open to have #35265 also.

[tscrim]

Sorry for being a be slow for this. I have approved #35291. I think it would be good to also do #35265 too as I think it is a net improvement even if it costs us a bit of speed in some cases. We can discuss there the specifics of the change. I still need to make a PR for the arity issue with shift, which I will do so now.