revert for LazyTaylorSeries and LazySymmetricFunction is missing

[mantepse]

sage: L.<z> = LazyTaylorSeriesRing(ZZ)
sage: (z-z^2).revert()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
...
AttributeError: 'LazyTaylorSeriesRing_with_category.element_class' object has no attribute 'revert'

Same for LazySymmetricFunctions. compositional_inverse might be a good alias.

Depends on #32324
Depends on #34453
Depends on #34494

CC: @tscrim

Component: combinatorics

Keywords: LazyPowerSeries

Author: Martin Rubey

Branch/Commit: f3f011f

Reviewer: Travis Scrimshaw

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

[mantepse]

comment:1

Unfortunately, there seems to be an inaccuracy in Stream_plethysm:

sage: h = SymmetricFunctions(QQ).h()
sage: p = SymmetricFunctions(QQ).p()
sage: L = LazySymmetricFunctions(p)
sage: X = L(p[1])
sage: e = L(lambda n: h[n]) - 1 - X
sage: g = L(None, valuation=1)
sage: g.define(X - e(g))
sage: g[0]
0
sage: g[1]
p[1]
sage: g[2]
...booooom... (max recursion error)

[mantepse]

comment:2

In the example, h has valuation 2, so to compute the degree 2 piece of h(g) we only should be accessing the degree 1 piece of g. But in Stream_plethysm.get_coefficient, we compute self._compute_product(2, [1, 1], 1/2), which in turn accesses self._right[2].

[mantepse]

comment:3

An easy fix is as follows:

diff --git a/src/sage/data_structures/stream.py b/src/sage/data_structures/stream.py
index e54a90b8b88..b61d29544c2 100644
--- a/src/sage/data_structures/stream.py
+++ b/src/sage/data_structures/stream.py
@@ -1763,6 +1763,14 @@ class Stream_plethysm(Stream_binary):
         p = self._p
         ret = p.zero()
         for mu in wt_int_vec_iter(n, la):
+            if any(j < self._gv for j in mu):
+                continue
             temp = c
             for i, j in zip(la, mu):
                 gs = self._right[j]
                 if not gs:
                     temp = p.zero()
                     break
                 temp *= p[i](gs)
             ret += temp
         return ret

However, it would probably be better not to generate these integer vectors in the first place. Moreover, it is possibly a waste to compute p[i](gs) for each i in la separately, if la has many parts repeated.

[mantepse]

comment:4

I have to leave now, but I just saw that possibly the implementation of plethysm in the species directory is more efficient.

[mantepse]

comment:5

I slightly improved the implementation. In particular, we can now specify degree one elements in the same way as for plethysm, and it is (slightly :-) faster now:

sage: from sage.data_structures.stream import Stream_function, Stream_plethysm, Stream_plethysm_old
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: f = Stream_function(lambda n: s[n], s, True, 1)
sage: g = Stream_function(lambda n: s[[1]*n], s, True, 1)
sage: h = Stream_plethysm(f, g, p)
sage: %time _ = h[10]
CPU times: user 122 ms, sys: 6 µs, total: 122 ms
Wall time: 122 ms
sage: h2 = Stream_plethysm_old(f, g, p)
sage: %time _ = h2[10]
CPU times: user 2.13 s, sys: 0 ns, total: 2.13 s
Wall time: 2.13 s

[mantepse]

Branch: u/mantepse/revert_for_lazytaylorseries_and_lazysymmetricfunction_is_missing

[mantepse]

Last 10 new commits:

9d6579b	improve documentation, move zero, one, characteristic, etc. to ABC
feba6b8	Working more on `__call__` for LazySymFunc.
3f3e0f2	Merge branch 'public/rings/lazy_talyor_series-32324' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_talyor_series-32324
6727228	Merge branch 'public/rings/lazy_talyor_series-32324' of trac.sagemath.org:sage into t/32324/public/rings/lazy_talyor_series-32324
028796d	Fixing numerous issues with `__call__` and expanding its functionality. Moving plethysm to a Stream_plethysm.
9fb155f	Removing unused code from previous version.
7f9dbb1	Some last doc fixes and tweaks.
4e03fee	remove unused local variable
e780472	Addressing the linter complaint.
d5b86a8	implement revert, improve plethysm

[mantepse]

Changed keywords from none to LazyPowerSeries

[mantepse]

Commit: d5b86a8

[mantepse]

Author: Martin Rubey

[mantepse]

comment:8

Next I'd like to implement revert for TaylorSeries, derivative, derivative_with_respect_to_p1.

Still missing: functorial_composition, arithmetic_product, logarithm for SymmetricFunctions.

All of these are needed for #32367.

[mantepse]

comment:9

Should we def plethysm and make __call__ an alias instead? This is the way it is done in combinat/sf/sfa.py.

[tscrim]

comment:10

I agree that we should throw out integer vectors that are asking for things less than the valuation. Actually, this is simple to modify with the current code. Just subtract valuation * len(la) from n. Then you just add back in the valuation to each component of the integer vector.

It sure looks like you have just essentially duplicated the plethysm code, which I don't think we should do, especially for marginal speed gains. I think you are better off improving the symmetric functions code directly.

Another micro-optimization that can be done is to store len(l) in the integer_vector_weighted.iterator_fast code since this never changes (it can be surprising how much this extra little function call can affect speed).

[tscrim]

comment:11

Replying to @mantepse:

Should we def plethysm and make __call__ an alias instead? This is the way it is done in combinat/sf/sfa.py.

It doesn't make any difference to me.

[mantepse]

comment:12

I don't understand. My code is quite different, and I gain a factor 20 on the original example.

[tscrim]

comment:13

Sorry, I just read what you wrote and took it at face value rather than actually reading the example. Indeed, that is quite an impressive speedup. I think my comment still holds about integrating it directly into the symmetric functions code. Superficially it still looks generally like the symmetric functions code. What have you changed to get that improvement?

[mantepse]

comment:14

Oh, i am sorry, that teaches me a lesson! Could we perhaps do a zoom meeting today? Maybe at 5pm Japan time?

[tscrim]

comment:15

Sounds good. I responded via email as well.

[sagetrac-git]

Changed commit from d5b86a8 to 6eebb35

[sagetrac-git]

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

6eebb35

do not assume that the approximate valuation will not change over time

[mantepse]

Dependencies: #32324

[mantepse]

comment:18

NB: the new implementation of plethysm appears to be faster than the one in sage.combinat.sf.sfa!

[tscrim]

comment:19

Some things that should be fixed:

• _scale_part and _scale_c need doctests. I might just inline the code however as they are such small and simple functions (they are needs for the symmetric functions implementation, but I think that could be improved).

• I would explain the algorithm for revert in terms of (lazy) symmetric functions rather than species.

• Instead of sum_of_terms(), I would just directly create a dictionary and go through p._from_dict() to avoid the redirection.

• Even though its cached, I would make this change:

  -        if power[d]:
  -            terms = [(self._scale_part(m, i), self._raise_c(c, i)) for m, c in power[d]]
  +        val = power[d]:
  +        if val:
  +            terms = {self._scale_part(m, i): coeff for m, c in val if (coeff := self._raise_c(c, i)))}
           else:
  -            terms = []
  +            return self._p.zero()
   
  -        return self._p.sum_of_terms(terms, distinct = True)
  +        return self._p._from_dict(terms, remove_zeros=False)

  (I only very recently learned of the := syntax. it is so great to have a way to assign equality in a statement in Python. It makes writing code like the above so much easier.)

However, there is also a decent part of me that would like to see the code duplication with sfa.plethysm() reduced, in particular with the logic around the include/exclude. Although the same could be said for _scale_part and _scale_c, which are (essentially) the same as in the symmetric functions.

Lastly, shouldn't the compositional inverse also be implemented for lazy Laurent and Taylor series?

[sagetrac-git]

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

fc33cd4	add test for degree one elements
3958757	microoptimizations in stretched_power_restrict_degree

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

731072a

remove unnecessary code leftover from merge, and remove unneccesary import detected by pyflakes

[sagetrac-git]

Changed commit from dafdcb4 to 731072a

[mantepse]

comment:72

Back to positive review, these are only trivial modifications. Please excuse the noise.

[vbraun]

comment:74

sage -t --long --warn-long 48.0 --random-seed=123 src/sage/combinat/sf/sfa.py
**********************************************************************
File "src/sage/combinat/sf/sfa.py", line 3139, in sage.combinat.sf.sfa.SymmetricFunctionAlgebra_generic_Element.plethysm
Failed example:
    s(2*T.one())
Expected:
    (2*B[word:]#B[word:])*s[]
Got:
    (2*B[]#B[])*s[]
**********************************************************************
1 item had failures:
   1 of  48 in sage.combinat.sf.sfa.SymmetricFunctionAlgebra_generic_Element.plethysm
    [1238 tests, 1 failure, 18.82 s]
----------------------------------------------------------------------
sage -t --long --warn-long 48.0 --random-seed=123 src/sage/combinat/sf/sfa.py  # 1 doctest failed
----------------------------------------------------------------------

[sagetrac-git]

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

ab98f2e	less verbose monomials in shuffle algebras
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.

[sagetrac-git]

Changed commit from 731072a to 2039990

[tscrim]

Changed dependencies from #32324, #34453 to #32324, #34453, #34494

[tscrim]

comment:76

Same trivial fix that ended up on the later ticket #34413.

[sagetrac-git]

Changed commit from 2039990 to f3f011f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

f3f011f

Merge branch 'develop' of trac.sagemath.org:sage into t/34383/public/rings/lazy_series_revert-34383

[mantepse]

comment:78

Trivial merge, hence setting back to positive review.

[vbraun]

Changed branch from public/rings/lazy_series_revert-34383 to f3f011f