Opened 9 years ago
Closed 8 years ago
#14543 closed enhancement (fixed)
Implement compositional inverses of cycle index series
Reported by:  agd  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  species, cycle indices, LazyPowerSeries 
Cc:  sagecombinat, mantepse  Merged in:  
Authors:  Andrew GainerDewar  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  documentation 
Branch:  a1d3536 (Commits, GitHub, GitLab)  Commit:  a1d35362dc7663a346971ab75c389b0e100ae9e7 
Dependencies:  Stopgaps: 
Description (last modified by )
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 loworder 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.
Attachments (3)
Change History (38)
comment:1 Changed 9 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
 Dependencies set to #14542
yes indeed, this is exactly what dependencies are for. I have added the dep. to #14542.
comment:5 Changed 9 years ago by
 Dependencies #14542 deleted
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?
comment:6 followup: ↓ 7 Changed 9 years ago by
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.)
comment:7 in reply to: ↑ 6 Changed 9 years ago by
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 nonzero 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
?
comment:8 followup: ↓ 11 Changed 9 years ago by
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.
Changed 9 years ago by
comment:9 followup: ↓ 10 Changed 9 years ago by
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?).
comment:10 in reply to: ↑ 9 Changed 9 years ago by
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 twosided ∘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 treelike structures" by Bergeron, Labelle, and Leroux, although it is discussed at some length in many other sources as well.
comment:11 in reply to: ↑ 8 Changed 9 years ago by
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 speciestheoretic 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 speciestheoretic derivative. Curiously, the LazyPowerSeries
derivative()
and integral()
methods are used several times in the existing codebase 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
comment:12 Changed 9 years ago by
 Branch set to u/agd/cis_comp_inv
comment:14 followup: ↓ 19 Changed 9 years ago by
I've uploaded a bunch of suggestions: trac_14543suggestionsdg.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 [BLLIntro]), 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.
comment:15 Changed 9 years ago by
 Reviewers set to Darij Grinberg
comment:16 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:17 Changed 9 years ago by
I am assuming the patch should be merged and the git branch is just there for reference.
comment:18 Changed 9 years ago by
 Branch u/agd/cis_comp_inv deleted
comment:19 in reply to: ↑ 14 Changed 9 years ago by
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.12beta3 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 [BLLIntro]), 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])])
byf = 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 beforet^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 thedefine
method inseries.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 userfacing output and shouldn't be set to something not useruseful like "res".
Perhaps one day we'll all ascend to the inner temple of define
and gain true wisdom.
comment:20 Changed 9 years ago by
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
).
comment:21 Changed 9 years ago by
 Reviewers Darij Grinberg deleted
comment:22 Changed 9 years ago by
for the patchbots:
apply trac_14543_cycle_index_compositional_inverse.patch
comment:23 Changed 8 years ago by
 Branch set to u/agd/cis/compinv
 Commit set to df4d3f3668504897180334d5d63e718c6df76c03
 Milestone changed from sage5.13 to sage6.0
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?
comment:24 Changed 8 years ago by
 Milestone changed from sage6.0 to sage6.1
comment:25 Changed 8 years ago by
 Commit changed from df4d3f3668504897180334d5d63e718c6df76c03 to 828c5ad975ab6c7e3d5927040cf2e9334a3e36a9
Branch pushed to git repo; I updated commit sha1. New commits:
828c5ad  Merge branch 'develop' into cis/compinv

comment:26 Changed 8 years ago by
 Cc mantepse added
 Keywords LazyPowerSeries added
comment:27 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:28 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:29 Changed 8 years ago by
 Status changed from needs_review to needs_work
Error building the documentation. OSError: [combinat ] None:4: WARNING: citation not found: BLLIntro
comment:30 Changed 8 years ago by
 Work issues set to documentation
comment:31 Changed 8 years ago by
 Branch changed from u/agd/cis/compinv to public/ticket/14543
 Commit changed from 828c5ad975ab6c7e3d5927040cf2e9334a3e36a9 to 5d403ab9c13177add932d71d074dd2cc1f8256e5
 Status changed from needs_work to needs_review
comment:32 Changed 8 years ago by
 Commit changed from 5d403ab9c13177add932d71d074dd2cc1f8256e5 to a1d35362dc7663a346971ab75c389b0e100ae9e7
Branch pushed to git repo; I updated commit sha1. New commits:
a1d3536  trac #14543 changed behaviour when not invertible + doc

comment:33 Changed 8 years ago by
 Reviewers set to Frédéric Chapoton
This looks good to me. Andrew, if you agree with my latest commit, you can set that to positive review.
comment:34 Changed 8 years ago by
 Status changed from needs_review to positive_review
Yes, this looks good to me as well! Positive review confirmed. Thanks for your help!
comment:35 Changed 8 years ago by
 Branch changed from public/ticket/14543 to a1d35362dc7663a346971ab75c389b0e100ae9e7
 Resolution set to fixed
 Status changed from positive_review to closed
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.