Replace Lazy Power Series in species directory

[tejasvicsr1]

In this ticket we finalize the implementation of lazy series, and replace the old lazy series framework.

Depends on #34423

CC: @mantepse @tscrim @pfili @zimmermann6 @sagetrac-tmonteil

Component: combinatorics

Keywords: LazyPowerSeries, FormalSeries, gsoc2021

Author: Tejasvi Chebrolu, Martin Rubey, Travis Scrimshaw

Branch/Commit: 4fc981b

Reviewer: Martin Rubey, Travis Scrimshaw

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 89270eb to b76d8f4

[mantepse]

comment:39

There are a few further minor issues.

I think that for LazyTaylorSeries, LazyDirichletSeries, LazySymmetricFunction, etc. we really don't want

sage: L.<x> = LazyTaylorSeriesRing(QQ)
sage: (x^2/(1-x)^3)[:5]
[1, 3, 6]
sage: L(lambda n: n*(n-1)/2)[:5]
[0, 0, 1, 3, 6]

Instead, I think that for these classes we always want to start from degree 0. The current behaviour also breaks some doctests in the species directory.

I am also hesitant to encode a coefficients method with behaviour quite different from the other methods with the same name. In particular, we have

    def coefficients(self):
        """
        Return the nonzero coefficients of this polynomial in a list.
        The returned list is decreasingly ordered by the term ordering
        of ``self.parent()``, i.e. the list of coefficients matches the list
        of monomials returned by
        :meth:`sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.monomials`.

        EXAMPLES::

            sage: R.<x,y,z> = PolynomialRing(QQ,3,order='degrevlex')
            sage: f=23*x^6*y^7 + x^3*y+6*x^7*z
            sage: f.coefficients()
            [23, 6, 1]
            sage: R.<x,y,z> = PolynomialRing(QQ,3,order='lex')
            sage: f=23*x^6*y^7 + x^3*y+6*x^7*z
            sage: f.coefficients()
            [6, 23, 1]

        Test the same stuff with base ring `\ZZ` -- different implementation::

            sage: R.<x,y,z> = PolynomialRing(ZZ,3,order='degrevlex')
            sage: f=23*x^6*y^7 + x^3*y+6*x^7*z
            sage: f.coefficients()
            [23, 6, 1]
            sage: R.<x,y,z> = PolynomialRing(ZZ,3,order='lex')
            sage: f=23*x^6*y^7 + x^3*y+6*x^7*z
            sage: f.coefficients()
            [6, 23, 1]

As far as I can see, there is a single exception to the behaviour indicated by the doctests above, which is the definition in multi_power_series_ring_elemnt.py.

I could imagine returning a lazy_list and a list, if the support is known to be finite. Unfortunately, for the code in species, the default behaviour is sparse=False, whereas in all other cases, it is sparse=True.

Another minor issue: for L.<x> = LazyPowerSeriesRing(QQ) we had L([1,2,3]) what would now be L([1,2], constant = 3). However, I really do not want to replicate this behaviour.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b76d8f4 to 4eb4dbd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4eb4dbd

fix behaviour of `__getitem__` for slices, provide missing doctests, minor simplifications in species directory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4eb4dbd to 6f76b00

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6f76b00

replace LazyTaylorSeriesRing and LazyTaylorSeries with LazyPowerSeriesRing and LazyPowerSeries and add appropriate deprecations

[mantepse]

comment:43

This last push could be moved into a separate ticket if absolutely necessary.

Apart from that, the only thing missing is a decision about the semantics of the coefficients function.

[tscrim]

comment:44

Replying to Martin Rubey:

I think that for LazyTaylorSeries, LazyDirichletSeries, LazySymmetricFunction, etc. we really don't want

sage: L.<x> = LazyTaylorSeriesRing(QQ)
sage: (x^2/(1-x)^3)[:5]
[1, 3, 6]
sage: L(lambda n: n*(n-1)/2)[:5]
[0, 0, 1, 3, 6]

Instead, I think that for these classes we always want to start from degree 0. The current behaviour also breaks some doctests in the species directory.

I would say that is a bug and should be fixed (which I think is what you’re saying as well).

I am also hesitant to encode a coefficients method with behaviour quite different from the other methods with the same name. In particular, we have

    def coefficients(self):
        """
        Return the nonzero coefficients of this polynomial in a list.
        The returned list is decreasingly ordered by the term ordering
        of ``self.parent()``, i.e. the list of coefficients matches the list
        of monomials returned by
        :meth:`sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular.monomials`.

As far as I can see, there is a single exception to the behaviour indicated by the doctests above, which is the definition in multi_power_series_ring_elemnt.py.

I agree with you. It’s not a bug, so we are not justified in simply changing the behavior. Although I feel a general deprecation message every time this is call would be obtrusive (and bad). I am leaning towards just making the backwards incompatible change, documenting how to get the previous behavior [f[i] for i in range(n)], and dealing with the consequences, but it was used all over the examples. I can’t think of a good way out of this other than something convoluted with an extra argument. Thus, we probably just have to make the change and take our medicine.

I could imagine returning a lazy_list and a list, if the support is known to be finite. Unfortunately, for the code in species, the default behaviour is sparse=False, whereas in all other cases, it is sparse=True.

I don’t think it is so important whether the backend is sparse or dense. I think you’re intuition is correct in returning a lazy_list unless the series is known to be finite.

Another minor issue: for L.<x> = LazyPowerSeriesRing(QQ) we had L([1,2,3]) what would now be L([1,2], constant = 3). However, I really do not want to replicate this behaviour.

Eek, that is highly unexpected. Did we think that should be the behavior at some point? I (now?) think we should have list input be the corresponding finite to match what polynomials do.

[mantepse]

comment:45

Replying to Travis Scrimshaw:

Replying to Martin Rubey:

I think that for LazyTaylorSeries, LazyDirichletSeries, LazySymmetricFunction, etc. we really don't want

sage: L.<x> = LazyTaylorSeriesRing(QQ)
sage: (x^2/(1-x)^3)[:5]
[1, 3, 6]
sage: L(lambda n: n*(n-1)/2)[:5]
[0, 0, 1, 3, 6]

Instead, I think that for these classes we always want to start from degree 0.

I would say that is a bug and should be fixed (which I think is what you’re saying as well).

Yes, that's done already in the commit in comment:41.

I am also hesitant to encode a coefficients method with behaviour quite different from the other methods with the same name. In particular, we have

[in multi_polynomia.pyx]

    def coefficients(self):
        """
        Return the nonzero coefficients of this polynomial in a list.

As far as I can see, there is a single exception to the behaviour indicated by the doctests above, which is the definition in multi_power_series_ring_elemnt.py.

I agree with you. It’s not a bug, so we are not justified in simply changing the behavior. Although I feel a general deprecation message every time this is call would be obtrusive (and bad). I am leaning towards just making the backwards incompatible change, documenting how to get the previous behavior [f[i] for i in range(n)], and dealing with the consequences, but it was used all over the examples. I can’t think of a good way out of this other than something convoluted with an extra argument. Thus, we probably just have to make the change and take our medicine.

Just to be clear: making the definition as

def coefficients(self, n=None, sparse=False):

i.e., with default behaviour as it is now, but with an option that makes it in line with the other coefficient methods in sage is not what we should do?

I must say, if we make the default sparse=True, i.e., introduce a backwards incompatible change, then I think we really should provide a deprecation warning. One might not notice immediately that zeros are missing all of a sudden.

Possibly, to make this decision slightly less important, I could put the definition into the generating functions module only, or, alternatively, only into LazyPowerSeries, and raise a NotImplementedError for multivariate series.

Another minor issue: for L.<x> = LazyPowerSeriesRing(QQ) we had L([1,2,3]) what would now be L([1,2], constant = 3). However, I really do not want to replicate this behaviour.

Eek, that is highly unexpected.

As far as I remember we discussed this issue and decided that we cannot do anything sensible about it. I think I'll put a

.. WARNING::

    The behaviour of ``LazyPowerSeries(l)`` for a list ``l`` with non-zero last element `e` changed with :trac:`32367`.  To obtain the old behaviour, use ``LazyPowerSeries(l, constant=e)``.

into the docstring of the (new) LazyPowerSeries.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f5e3f2e

fix documentation

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6f76b00 to f5e3f2e

[mantepse]

comment:47

I added a warning for the new behaviour concerning the specification of the constant.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f5e3f2e to c5bfba5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c5bfba5

adapt a doctest

[tscrim]

comment:49

Replying to Martin Rubey:

Replying to Travis Scrimshaw:

Replying to Martin Rubey:

I am also hesitant to encode a coefficients method with behaviour quite different from the other methods with the same name.

[snip]

As far as I can see, there is a single exception to the behaviour indicated by the doctests above, which is the definition in multi_power_series_ring_elemnt.py.

I agree with you. It’s not a bug, so we are not justified in simply changing the behavior. Although I feel a general deprecation message every time this is call would be obtrusive (and bad). I am leaning towards just making the backwards incompatible change, documenting how to get the previous behavior [f[i] for i in range(n)], and dealing with the consequences, but it was used all over the examples. I can’t think of a good way out of this other than something convoluted with an extra argument. Thus, we probably just have to make the change and take our medicine.

Just to be clear: making the definition as

def coefficients(self, n=None, sparse=False):

i.e., with default behaviour as it is now, but with an option that makes it in line with the other coefficient methods in sage is not what we should do?

No, I agree with you that it is what we should do. The problem is how to do this with an effective and unobtrusive deprecation.

I must say, if we make the default sparse=True, i.e., introduce a backwards incompatible change, then I think we really should provide a deprecation warning. One might not notice immediately that zeros are missing all of a sudden.

Then we are introducing a new argument that we then have to add to code, which we will also want to deprecate later. This becomes a hassle on both the developer and user side.

Actually, maybe we can just issue a deprecation on the n parameter, where we also say this now will return only nonzero coefficients? If people are passing n, then they are expecting the old behavior.

Given the other backwards-incompatible change we are making (the one below), it isn’t much more painful to do a second one at the same time either.

Possibly, to make this decision slightly less important, I could put the definition into the generating functions module only, or, alternatively, only into LazyPowerSeries, and raise a NotImplementedError for multivariate series.

I think it is better to be consistent about this.

Another minor issue: for L.<x> = LazyPowerSeriesRing(QQ) we had L([1,2,3]) what would now be L([1,2], constant = 3). However, I really do not want to replicate this behaviour.

Eek, that is highly unexpected.

As far as I remember we discussed this issue and decided that we cannot do anything sensible about it. I think I'll put a

.. WARNING::

    The behaviour of ``LazyPowerSeries(l)`` for a list ``l`` with non-zero last element `e` changed with :trac:`32367`.  To obtain the old behaviour, use ``LazyPowerSeries(l, constant=e)``.

into the docstring of the (new) LazyPowerSeries.

Ah, I misread it initially. This was the behavior of the old LazyPowerSeries. Just two little things with this:

• Use L instead of l since it has a chance to be read as I depending on the font (like the one I am using to type this comment in fact).
• Make sure there is an easy to see example of the new constant behavior is clearly visible (in the class-level ring doc, its _element_constructor_, the element class’s class-level doc; the module-level doc if there are examples there).

[mantepse]

comment:50

Replying to Travis Scrimshaw:

• Use L instead of l since it has a chance to be read as I depending on the font (like the one I am using to type this comment in fact).

OK, I am using c now, for 'coefficients', since L is used for the parent usually.

• Make sure there is an easy to see example of the new constant behavior is clearly visible (in the class-level ring doc, its _element_constructor_, the element class’s class-level doc; the module-level doc if there are examples there).

There are several such examples, eg. line 1344 and beyond. Note that this change is not so bad as it may look: almost always, the old input was a list ending with 0, because this is the constant you usually want.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c5bfba5 to ceecc89

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ceecc89

don't use l

[fchapoton]

comment:52

Hello, we are supposed to be in maintenance mode today, as announced on sage-devel and trac main page. I think everything is now in order, but please try clicking around..

[tscrim]

comment:53

Everything seems to be okay.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9629b28

require the start value for `__getitem__` of LazyLaurentSeries

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ceecc89 to 9629b28

[tscrim]

comment:55

Replying to Martin Rubey:

Replying to Travis Scrimshaw:

• Use L instead of l since it has a chance to be read as I depending on the font (like the one I am using to type this comment in fact).

OK, I am using c now, for 'coefficients', since L is used for the parent usually.

Thank you.

• Make sure there is an easy to see example of the new constant behavior is clearly visible (in the class-level ring doc, its _element_constructor_, the element class’s class-level doc; the module-level doc if there are examples there).

There are several such examples, eg. line 1344 and beyond. Note that this change is not so bad as it may look: almost always, the old input was a list ending with 0, because this is the constant you usually want.

Thank you. I didn't have time to check when I posted that.

Given your comments, I think this is now at needs review, correct? Feel free to revert if more is still needed.

Actually, I think I am mostly ready to turn this to a positive review if the patchbot comes back green.

[tscrim]

comment:56

I take that back slightly. I think we should have uniformity with the get item and that f[:5] should work for all series because they all have an approximate valuation.

[mantepse]

comment:57

I am now (i.e., within the hour) implementing coefficients. Other than that, it is ready!

(to be honest: !!!!!!!!! with just as many smileys!)

Explanation for the last push: we actually change _aproximate_valuation already in a place, and I think we will want to do that more often, and I certainly do not want that the result of __getitem__ depends on that.

[mantepse]

comment:58

Actually, I just discovered something quite disturbing:

sage: L.<x> = PowerSeriesRing(QQ)
sage: f = x^-5/(1-2*x)
sage: f[:10]
<ipython-input-11-f66b5b8a9c22>:1: DeprecationWarning: polynomial slicing with a start index is deprecated, use list() and slice the resulting list instead
See http://trac.sagemath.org/18940 for details.
  f[:Integer(10)]
32 + 64*x + 128*x^2 + 256*x^3 + 512*x^4 + 1024*x^5 + 2048*x^6 + 4096*x^7 + 8192*x^8 + 16384*x^9 + O(x^15)

I find this rather hard to believe.

[tscrim]

comment:59

Replying to Martin Rubey:

Explanation for the last push: we actually change _aproximate_valuation already in a place, and I think we will want to do that more often, and I certainly do not want that the result of __getitem__ depends on that.

I was misremembering what we implemented as I thought it did strip the leading zeros, but this is not the case:

sage: L.<x> = LazyLaurentSeriesRing(QQ)
sage: f = L(lambda n: 1, valuation=0)
sage: fp = (f - 1)
sage: fp[:5]
[0, 1, 1, 1, 1]

I would say we should start from the approximate order up to the stop and then strip leading zeros (with updating the valuation accordingly). I find the f[:5] syntax really nice. It also means we promise you have all nonzero coefficients up to the stop without having to compute the valuation (in particular, this would work for zero series).

This could be made consistent with f[a:b] that does return the leading 0's because the input is clearly different (and we would not update the approximate valuation because we are not using it).

The major point with updating the current behavior is there is no other way to guarantee that we have computed enough using f[a:b] to guarantee all coefficients of degree less than a are zero because we have not made the approximate valuation part of the API. Otherwise I would want a way to get that so I can guarantee my computations. (Of course, I can but don't want to keep track of this by hand.)

[tscrim]

comment:60

Replying to Martin Rubey:

Actually, I just discovered something quite disturbing:

sage: L.<x> = PowerSeriesRing(QQ)
sage: f = x^-5/(1-2*x)
sage: f[:10]
<ipython-input-11-f66b5b8a9c22>:1: DeprecationWarning: polynomial slicing with a start index is deprecated, use list() and slice the resulting list instead
See http://trac.sagemath.org/18940 for details.
  f[:Integer(10)]
32 + 64*x + 128*x^2 + 256*x^3 + 512*x^4 + 1024*x^5 + 2048*x^6 + 4096*x^7 + 8192*x^8 + 16384*x^9 + O(x^15)

I find this rather hard to believe.

That is disturbing on many different levels for FPS. For polynomials, it probably would be better for them to be done as lists rather than polynomials, but it was somewhat natural there to return a polynomial as we often want to lop off terms. For FPS, I think slicing makes less sense to return a FPS because we are actually interested in a certain range of coefficients. We aren't really manipulating parts of the polynomial.

Since this is deprecated and could be removed now, we are free to implement our own version of slicing.

[mantepse]

comment:61

I am absolutely against starting with _approximate_order, since this is not well-defined.

ANd I absolutely want a method (I do not care which name it has) which gives me the list or lazy list of all coefficients, beginning with a specified degree. This is one of the most important use cases for me, for example, I feed this list to oeis, or to the guessing packages, or I plot it.

[mantepse]

comment:62

(Let me stress again that _approximate_order may change after certain operations, and may depend on the way we construct the series.)

[tscrim]

comment:63

Replying to Martin Rubey:

I am absolutely against starting with _approximate_order, since this is not well-defined.

With slicing returning leading zeros, I completely agree that we should not do this. My proposal would be to strip the leading zeros and start at the actual valuation (or return an empty list if the valuation is at least as large as stop).

ANd I absolutely want a method (I do not care which name it has) which gives me the list or lazy list of all coefficients, beginning with a specified degree. This is one of the most important use cases for me, for example, I feed this list to oeis, or to the guessing packages, or I plot it.

Big +1 as well. I am not proposing a change to the slicing f[start:stop], which would still return a list.

Basically, what I would have is a lazy series f with:

• approximate valuation a
• actual valuation v

behave as follows:

1. For f[:stop], then get the list of coefficients from f[a] to f[stop-1] and strip the leading zeros and update the approximate valuation as appropriate.
2. For f[start:start], return [f[i] for i in range(start, stop)].

As a concrete example, suppose we have g with approximate valuation -3 but actual valuation 2. Then doing the following (with a freshly created g):

1. g[:5] returns [2, 3, 4] and sets the approximate valuation to 2.
2. g[-1:5] returns [0, 0, 0, 2, 3, 4].
3. g[:1] returns [] and sets the approximate valuation to 1.

Does that clarify what I am proposing? How do you feel about that? I can implement this if you want too.

[mantepse]

comment:64

Yes, I think that distinguishing between start=None and start=d in this way is a good idea.

I'd also propose to propagate this change to all polynomial-like __getitem__ methods (in a later ticket).

I have roughly half an hour left, which I will invest into the coefficient method. The tricky part is to get multivariate and graded series right, to be consistent with

sage: P.<x,y> = QQ[]
sage: f = (x+2*y^3 +3*x*y + 5)
sage: f.coefficients()
[2, 3, 1, 5]

[tscrim]

comment:65

Hmm...that is a bit tricky. Can you just concatenate the coefficients() of each of the components by degree?

[mantepse]

comment:66

I'm almost there :-)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

037f3f7

implement coefficients

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9629b28 to 037f3f7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 037f3f7 to 787197e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

787197e

fix some bugs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 787197e to 8f46e12

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8f46e12

implement new semantics of __getitem__

[mantepse]

comment:70

Ready!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0de1c13	add a warning and an example for the arithmetic product with a constant term
8e5de35	add missing whitespace in docstring
f706c53	Merge branch 'u/mantepse/implement_arithmetic_product_of_lazy_symmetric_functions' of trac.sagemath.org:sage into t/32367/replace_lazy_power_series_in_species_directory_with_the_new_lazy_taylor_series

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8f46e12 to f706c53

[tscrim]

comment:72

The using you should use the approximate order instead of the actual order is that you do not need to compute it exactly. It should be “up to the (necessarily specified) stop” so it will still work for series that do not know they are zero (nor compute more than they need to).

I also think the result of coefficients() should all lie in the base ring.

I have a number of other small changes that I will do tomorrow, along with the above two if you don’t disagree.

[mantepse]

comment:73

Re stop: Oh, yes, I agree! I overlooked that!

Re base ring: indeed. (I thought they did.)

[mantepse]

comment:74

There is a bug in LazyModuleElement.map_coefficients: it applies the map to the coefficients of the stream, rather than the coefficients of the series. It is unfortunate that we call the elements of the stream coefficients, we should call them graded pieces or something like that.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f706c53 to 3410eda

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3410eda

fix map_coefficients

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3410eda to 8fc2dd1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8fc2dd1

fix doctests because of `__getitem__` change