more testsuites for lazy series rings

[mantepse]

In this ticket we implement systematic tests for operations on lazy series.

Depends on #34470

CC: @tscrim

Component: combinatorics

Keywords: LazyPowerSeries

Author: Martin Rubey

Branch/Commit: 3e84c90

Reviewer: Travis Scrimshaw, Frédéric Chapoton

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

[mantepse]

Branch: u/mantepse/more_testsuites_for_lazy_series_rings

[mantepse]

Author: Martin Rubey

[mantepse]

Last 10 new commits:

e3e331c	add and correct some_elements for all rings, run all tests in the TestSuite (many fail)
00aaca0	introduce halting precision
f9dd62e	fix equality of exact series, do not produce coefficients of polynomials by iterating over them
b9a66be	implement missing required method lift_to_precision
88109cc	fix precision also in species directory, do not forget to switch it off after doctest
08baf9a	fix punctuation in docstrings
5bd0331	correct an_element and some_elements, implement is_unit, _test_invert
1722eca	fix is_unit
cdf821a	improve equality, raise errors when trying to invert series which are known not to be invertible, be more careful not to compute terms
cc48d4e	Merge branch 'u/mantepse/categories_of_lazy_series' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings

[mantepse]

Changed keywords from none to LazyPowerSeries

[mantepse]

Dependencies: #34470

[mantepse]

Commit: cc48d4e

[sagetrac-git]

Changed commit from cc48d4e to 54bb1d8

[sagetrac-git]

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

54bb1d8

add _test_revert and add more rings to test

[sagetrac-git]

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

60f0664

fix more _an_element and some_element with incorrect coefficients

[sagetrac-git]

Changed commit from 54bb1d8 to 60f0664

[mantepse]

comment:5

Apparently, reversion of symmetric functions with linear coefficient different from 1 is completely broken:

sage: g = L(2*s[1]+s[2])
sage: g
2*p[1] + (1/2*p[1,1]+1/2*p[2])
sage: g.revert()(g)
p[1] + (-1/4*p[1,1]-1/4*p[2]) + (1/4*p[1,1,1]+1/4*p[2,1]) + (-9/32*p[1,1,1,1]-5/16*p[2,1,1]+3/32*p[2,2]+1/8*p[4]) + (11/32*p[1,1,1,1,1]+7/16*p[2,1,1,1]-1/32*p[2,2,1]-1/8*p[4,1]) + (-57/128*p[1,1,1,1,1,1]-83/128*p[2,1,1,1,1]-7/128*p[2,2,1,1]-13/128*p[2,2,2]+5/32*p[4,1,1]-3/32*p[4,2]) + (77/128*p[1,1,1,1,1,1,1]+127/128*p[2,1,1,1,1,1]+27/128*p[2,2,1,1,1]+9/128*p[2,2,2,1]-7/32*p[4,1,1,1]+1/32*p[4,2,1]) + O^8

[mantepse]

comment:6

Obviously, there was a parenthesis missing. I thought I changed that already once.

[sagetrac-git]

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

fbccb39	normalize degree in Stream_exact for correct equality
b20eabf	Merge branch 'u/mantepse/categories_of_lazy_series' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings
7cbde49	fix reversion of symmetric functions, improve some_elements and tests

[sagetrac-git]

Changed commit from 60f0664 to 7cbde49

[sagetrac-git]

Changed commit from 7cbde49 to 6a46183

[sagetrac-git]

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

3d5b8cf	Last little things from the patchbot.
aa593b5	Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470
840539d	More tests, more bugs fixed.
b930f58	Merge branch 'u/mantepse/categories_of_lazy_series' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/categories_lazy_series-34470
6a46183	Merge branch 'u/tscrim/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings

[sagetrac-git]

Changed commit from 6a46183 to b15e36d

[sagetrac-git]

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

b15e36d

skip test_revert when base ring is not a field

[sagetrac-git]

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

8e7b76d

fix and simplify wrong doctest

[sagetrac-git]

Changed commit from b15e36d to 8e7b76d

[sagetrac-git]

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

b47407b	Implementing `_floordiv_`, Stream._true_order to boolean, first fraction field, more tests, marking long tests.
e077b66	Using dynamic classes for FPS gcd.
f8ea81b	Merge branch 'u/tscrim/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/more_testsuites_for_lazy_series_rings

[sagetrac-git]

Changed commit from 8e7b76d to f8ea81b

[mantepse]

comment:13

The following should work, but doesn't, because reversion is not lazy enough:

sage: L.<t> = LazyPowerSeriesRing(QQ)
sage: f = L.undefined()
sage: f.define(1+(t*f).revert())

In this case, f should have the coefficients of https://oeis.org/A067145.

[tscrim]

comment:14

Replying to Martin Rubey:

The following should work, but doesn't, because reversion is not lazy enough:

sage: L.<t> = LazyPowerSeriesRing(QQ)
sage: f = L.undefined()
sage: f.define(1+(t*f).revert())

In this case, f should have the coefficients of https://oeis.org/A067145.

This one is harder because of the nature of the tests being done. Nothing can be promised about the coefficients of the undefined series. It comes down to how much we want to promise that the code will not break on bad input. I am thinking we can change

-        if not coeff_stream[1]:
+        if coeff_stream._approximate_order > 1:
             raise ValueError("compositional inverse does not exist")
-
-        if coeff_stream[0]:
-            raise ValueError("cannot determine whether the compositional inverse exists")

Then we run into an issue with computing the exact order in Stream_cauchy_invert. So we are doing too many things not lazily enough. (For the invert, we can make _ainv a @lazy_attribute to fix this easily.)

[mantepse]

comment:15

In principle, I think it is more important that define works reliably when the input is valid than having helpful error messages. However, silently wrong output is probably equally bad as failures on good input.

For the issue at hand, I think we can rewrite

-        # TODO: shift instead of (self / z) should be more efficient
-        g.define(z / ((self / z)(g)))
+        # the following is mathematically equivalent to
+        # z / ((self / z)(g))
+        # but more efficient and more lazy
+        g.define((~self.shift(-1)(g)).shift(1))

Here is my thinking:

• in __invert__, and shift(-1) it is correct to fail on LazyPowerSeries with positive valuation (in contrast to _div_). In particular, f * ~ z is actually bad input for LazyPowerSeries

• I don't see how we can (without great effor) avoid the order computation in Stream_cauchy_invert.__init__, when we have no upper bound on the valuation of the input, because it's negative is passed to super().__init__. In our Aldor implementation, Ralf and I created a new domain which allowed computation with "unknowns". I am not sure whether we want this.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

1388b8a	Merge branch 'u/chapoton/34494' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_series_revert-34383
7bfe5f7	Merge branch 'public/rings/lazy_series_revert-34383' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_series_revert-34383
2039990	Updating doctest due to changes from #34494.
cdea820	Merge branch 'public/rings/lazy_series_revert-34383' of https://github.com/sagemath/sagetrac-mirror into u/tscrim/derivatives_lazy_series-34413
b7f04ed	Merge branch 'develop' of trac.sagemath.org:sage into t/34413/derivatives_lazy_series-34413
2325826	Merge branch 'u/mantepse/derivatives_lazy_series-34413' of trac.sagemath.org:sage into t/34422/implement_functorial_composition_of_lazy_symmetric_functiosn
ebcf5c3	Merge branch 'u/mantepse/implement_functorial_composition_of_lazy_symmetric_functiosn' of trac.sagemath.org:sage into t/34423/implement_arithmetic_product_of_lazy_symmetric_functions
4172688	Merge branch 'u/mantepse/implement_arithmetic_product_of_lazy_symmetric_functions' of trac.sagemath.org:sage into t/32367/replace_lazy_power_series-32367
41ca99b	Merge branch 'u/mantepse/replace_lazy_power_series-32367' of trac.sagemath.org:sage into t/34470/categories_lazy_series-34470
fb3a5cd	Merge branch 'u/mantepse/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/lazy_series_test_suite-34552

[sagetrac-git]

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

855d2bf

remove unused variable

[sagetrac-git]

Changed commit from fb3a5cd to 855d2bf

[sagetrac-git]

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

75c275c

add documentation and doctests for _approximate_order

[sagetrac-git]

Changed commit from 855d2bf to 75c275c

[mantepse]

comment:58

Essentially green bot.

The pyflakes warnings local variable 'res' is assigned to but never used are from #34345. Should I fix them here or elsewhere?

[mantepse]

comment:59

The codestylecheck warnings are as follows:

sage/rings/lazy_series.py:843:21: E711 comparison to None should be 'if cond is None:'
sage/rings/lazy_series.py:961:17: E711 comparison to None should be 'if cond is None:'
sage/rings/lazy_series.py:5452:9: E306 expected 1 blank line before a nested definition, found 0

The first two wouldn't work with is, because an option only compares equal to None:

            prec = self.parent().options.halting_precision
            if prec == None:
                raise ValueError("undecidable")

The E306 I disagree with, I am setting the "local" variables for the local function definition. (X is used later, but looks best at this spot)

        la = Partition([1])
        X = R(la)
        def coefficient(n):
            if n:
                return 0
            c = coeff_stream[1][la]
            if c.is_unit():
                return ~c
            raise ValueError("compositional inverse does not exist")

[mantepse]

comment:60

It is interesting that the github bots will not detect the unused variables.

[fchapoton]

comment:61

Sorry, but the linter must pass, no choice. Even if E306 is in some sense a matter of taste, it is currently required. Your def without empty line before would be the only one in the whole sage code base.

About the comparison to None, this is very strange. Could you use "if not prec" instead ? or some isinstance ? What is the type of "prec" that is equal but not None ?

[mantepse]

comment:62

Hi Frédéric!

Concerning the second question:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: L.options.halting_precision
None
sage: type(L.options.halting_precision)
<class 'sage.structure.global_options.Option'>
sage: L.options.halting_precision == None
True
sage: L.options.halting_precision is None
False

[mantepse]

comment:63

I'll add the missing line.

Could you please also respond to comment:58?

(these pyflakes warnings were missed in a completely unrelated ticket)

[fchapoton]

comment:64

the pyflakes warning are not your responsability, but you can fix them if you want

For the comparison to None, maybe this could fixed using the complicated syntax

sage: op = L.options.constant_length
sage: op._options[op._name]
3
sage: type(_)
<class 'int'>

or by adding in general a way to extract the bare value of an option somehow.

[fchapoton]

comment:65

simpler:

sage: Q=L.options
sage: type(Q['constant_length'])
<class 'int'>

[sagetrac-git]

Changed commit from 75c275c to 5393242

[sagetrac-git]

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

5393242

fixes for pycodestyle and pyflakes

[mantepse]

comment:67

Cool, thank you!

[sagetrac-git]

Changed commit from 5393242 to 3e84c90

[sagetrac-git]

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

67dff95	Merge branch 'develop' of trac.sagemath.org:sage into t/32367/replace_lazy_power_series-32367
4fc981b	fix for pyflakes and blocks
56cef07	Merge branch 'u/mantepse/replace_lazy_power_series-32367' of trac.sagemath.org:sage into t/34470/categories_lazy_series-34470
3e84c90	Merge branch 'u/mantepse/categories_lazy_series-34470' of trac.sagemath.org:sage into t/34552/lazy_series_test_suite-34552

[tscrim]

Reviewer: Travis Scrimshaw, Frédéric Chapoton

[tscrim]

comment:69

I am assuming Frédéric is now happy. LGTM. We can do more on further tickets.

[vbraun]

Changed branch from u/mantepse/lazy_series_test_suite-34552 to 3e84c90