Implement compositional inverses of cycle index series

[agd]

In #14348, I submitted code which computes the cycle index of the virtual species Ω, which is the compositional inverse of the species E+ of nonempty sets. It is possible to compute the compositional inverse of (most) arbitrary cycle indices (subject to some conditions on the low-order terms). The attached patch implements this calculation by adding a compositional_inverse() method to the class CycleIndexSeries?. This code is doctested and builds HTML docs without errors.

It should be noted that this algorithm is very slow; however, it is the best one I know for the general case. The algorithm for computing the cycle index of Ω in #14348 is *much* faster, and that specific species has real computational utility, so I believe it is worthwhile to have both in Sage.

Apply trac_14543_cycle_index_compositional_inverse.patch​.

[chapoton]

This needs to be rebased on a recent version of sage. You need to import the patch on a recent sage, to look at the reject file (containing pieces of code that could not be put at their place), make the appropriate corrections, and then refresh and export it again.

[darij]

This patch applies fine for me (sage-main 5.10rc0) after #14542 is applied. Obviously the patch was made with #14542 applied, and inserts code directly before the method added by #14542, so I can see where the rejection comes from. Does this warrant adding a dependency?

[chapoton]

yes indeed, this is exactly what dependencies are for. I have added the dep. to #14542.

[agd]

I have uploaded a new version of the patch which moves the code to a different part of the class, eliminating the spurious dependency on #14542. I have also expanded and updated the documentation in two ways: by adding an ALGORITHM block explaining the (rather clumsy) method which is used here, and by adding a SEEALSO explaining the connection to CombinatorialLogarithmSeries?.

darij has suggested in discussion on #14542 that this use of assert may cause problems when CycleIndexSeriesRing? is based in a complicated ring (like another LazyPowerSeriesRing?). Is the best option here to add something like an optional check_input option which allows the user to suppress these assertions?

[darij]

On line 775, when you say 0 + p_{1} + \dots, does p_{1} just mean the variable X?

I'm surprised that this stuff is in a class named "CycleIndexSeries?" -- I'd expect it to be defined for LazyPowerSeries? in full generality? Of course, it makes sense to also have a wrapper in CycleIndexSeries? that gives back the answer in the correct type. (I fear this will have to depend on #13433.)

[agd]

Replying to darij:

On line 775, when you say 0 + p_{1} + \dots , does p_{1} just mean the variable X?

In a CycleIndexSeries as implemented in Sage, the coefficient on x^n is a symmetric function in the power sum basis whose terms are all of degree n. Of course, p_1 is the only such symmetric function for n=1, so the only actual freedom is the coefficient from the underlying base ring. This needs to be non-zero for this inversion method to work; assuming that it's 1 makes things much simpler and is, I think, not a significant restriction.

Or perhaps you meant the species X? If so, p_1 is indeed its cycle index series, but this code isn't running at the level of Species, so p_1 seemed clearer.

Either way, if you think there's a better way to write that docstring, I'm certainly open to it—I want the meaning to be as clear as possible!

I'm surprised that this stuff is in a class named "CycleIndexSeries? " -- I'd expect it to be defined for LazyPowerSeries? in full generality? Of course, it makes sense to also have a wrapper in CycleIndexSeries? that gives back the answer in the correct type. (I fear this will have to depend on #13433 .)

That would probably make sense; there's nothing about this algorithm that obviously depends on working at the level of CycleIndexSeries (at least to my eye). However, to do that, I'll need some mechanism for determining the compositional identity of an arbitrary LazyPowerSeriesRing, to stand in where X is now.

It's not clear to me how this should be done without some detailed knowledge of the specifics of the algebra in question. On the other hand, this does seem like information that each LazyPowerSeriesRing should know about itself. Maybe I should add a compositional_identity method to LazyPowerSeriesRing, move compositional_inverse there, and then override compositional_identity in CycleIndexSeriesRing?

[nthiery]

For the record: I recently needed the compositional inverse for Lazy power series, and a couple other related operations; they are in the patch I am about to attach; you can also find it in the queue. Feel free to take over / recycle whatever might be relevant.

[darij]

Ooh -- this is not literally the compositional inverse of a power series? Sorry then; please disregard what I wrote. It would still be nicer to have some explanation of what exactly this is, or a more precise reference (to a section number?).

[agd]

Replying to darij:

Ooh -- this is not literally the compositional inverse of a power series? Sorry then; please disregard what I wrote. It would still be nicer to have some explanation of what exactly this is, or a more precise reference (to a section number?).

Formally, this is the inverse of the operation of "cycle index plethysm", which is handled by the composition method of CycleIndexSeries. As an abstract operation, it has many of the same properties as power series composition, but at the computational level it is somewhat different; in particular, the induced operation on coefficients is something a bit more subtle than simply multiplying things out.

That said, the inversion procedure as I've written it out doesn't actually depend on any of the details of the operation ∘. It suffices that there is a two-sided ∘-inverse (call it X) and that ∘ distributes over addition. Thus, writing this procedure up at the LazyPowerSeries level and letting CycleIndexSeries inherit it should work fine, since CycleIndexSeries appropriately overrides composition.

The standard reference on the subject is section 1.4 of "Combinatorial species and tree-like structures" by Bergeron, Labelle, and Leroux, although it is discussed at some length in many other sources as well.

[agd]

Replying to nthiery:

For the record: I recently needed the compositional inverse for Lazy power series, and a couple other related operations; they are in the patch I am about to attach; you can also find it in the queue. Feel free to take over / recycle whatever might be relevant.

Unfortunately, I don't think this approach will work at the CycleIndexSeries level. The compose_inverse_with method from your patch, it appears that you're using the Inverse Function Theorem. This actually does work at the level of cycle index series (by a sort of combinatorial chain rule!), but the resulting differential equation is intractable in general, because taking species-theoretic derivatives of cycle index series destroys lots of information (in particular, every term without a p_1 is destroyed).

I haven't dug too deeply into the algebra, but I am fairly confident that using LazyPowerSeries derivatives instead is not mathematically meaningful and won't yield anything useful.

Looking this over has, however, brought to my attention that Sage does not have a method for CycleIndexSeries implementing the species-theoretic derivative. Curiously, the LazyPowerSeries derivative() and integral() methods are used several times in the existing code-base to pull off algebra tricks, so factoring out these (in my opinion) deceptive names would be a bit of a hassle, but it might still be worthwhile. This is probably at least as much a cultural question as a code one, though, so perhaps I should steer clear until I get to know the environment better?

Also, since the patchbot now seems to be confused:

apply trac_14543_cycle_index_compositional_inverse.patch

[darij]

EDIT: ignore

[darij]

suggestions. please don't fold until you feel safe that they're correct!

[darij]

I've uploaded a bunch of suggestions: trac_14543-suggestions-dg.patch​. Do you agree with them? I'm not sure of them myself, as some of them are just my guesses. And I have not filled in the definition of functorial composition since I don't fully understand it myself (I don't have the [BLL] reference, only [BLL-Intro]), but I've added a #TODO because it should eventually be filled in.

In the stretch doctest, I replaced f = CIS([p([1])]) by f = CIS([p([]), p([1]), p([2]), p.zero()]) because, as far as I understand, when you write a cycle index series as a power series in t, the coefficient before t^n has to be a symmetric polynomial homogeneous of degree n.

I have removed the reference to [BLL] from your method because the same reference appears in another method. Generally, every reference needs to exist only once in the source.

I added the res._name = 'res' line because the examples in the define method in series.py do that. Maybe it is cargo cult. I hope you can shed light on this.

In case you have troubles applying my patch: I've been working atop of #10227, #14685 and #14542. Maybe some of these are dependencies.

[jdemeyer]

I am assuming the patch should be merged and the git branch is just there for reference.

[agd]

Implement compositional inverses of cycle index series

[agd]

Replying to darij:

Thanks for your suggestions! I've uploaded a new version of my patch which incorporates some of your changes and applies on top of the current 5.12-beta3 source; see comments below.

And I have not filled in the definition of functorial composition since I don't fully understand it myself (I don't have the [BLL] reference, only [BLL-Intro]), but I've added a #TODO because it should eventually be filled in.

I cleaned this up in #14809, which will go live when 5.12 ships.

In the stretch doctest, I replaced f = CIS([p([1])]) by f = CIS([p([]), p([1]), p([2]), p.zero()]) because, as far as I understand, when you write a cycle index series as a power series in t, the coefficient before t^n has to be a symmetric polynomial homogeneous of degree n.

This sounds right to me, but I haven't rolled it in because it's not related to compositional inverses. I also left out your other small tweaks to other docstrings It looks like all of this documentation could use an overhaul, though.

I have removed the reference to [BLL] from your method because the same reference appears in another method. Generally, every reference needs to exist only once in the source.

Whoops!

I added the res._name = 'res' line because the examples in the define method in series.py do that. Maybe it is cargo cult. I hope you can shed light on this.

I don't claim to understand this entirely either, but I believe (presumably cultishly) that the _name field is meant for user-facing output and shouldn't be set to something not user-useful like "res".

Perhaps one day we'll all ascend to the inner temple of define and gain true wisdom.

[darij]

I fear I don't understand the species code well enough to complete the review. :( How on earth does the compose method know to do plethystic rather than usual composition? I assume the answer lies in _compose_term in generating.series.py, but that's some unreadable code with unreadable doc.

You are right about _name; what I wrote was bull. Sorry!

Please remove the trailing whitespace in your code (such as in return res ).

[chapoton]

for the patchbots:

apply trac_14543_cycle_index_compositional_inverse.patch

[agd]

I'll be glad to talk through the math of this code with any interested reviewers. It's not horribly complicated, but it's definitely going to look a bit weird if you're used to working with LazyPowerSeries? in different contexts. (CycleIndexSeries? is a strange creature, but it's super useful!)

Also, I've switched back over to using Git to manage this—the old Mercurial workflow is just too confusing. How do I tell the build bot to ignore the attachments and only use the branch?

[git]

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

​828c5ad

Merge branch 'develop' into cis/compinv

[rws]

Error building the documentation.
OSError: [combinat ] None:4: WARNING: citation not found: BLL-Intro

[chapoton]

I have corrected the failing doc, hopefully.

---

New commits:

​d408ec0	Merge branch 'u/agd/cis/compinv' of ssh://trac.sagemath.org:22/sage into 14543
​5d403ab	trac #14543 doc correction

[git]

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

​a1d3536

trac #14543 changed behaviour when not invertible + doc

[chapoton]

This looks good to me. Andrew, if you agree with my latest commit, you can set that to positive review.

[agd]

Yes, this looks good to me as well! Positive review confirmed. Thanks for your help!