Opened 9 years ago

Closed 8 years ago

#14543 closed enhancement (fixed)

Implement compositional inverses of cycle index series

Reported by: agd Owned by: sage-combinat
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords: species, cycle indices, LazyPowerSeries
Cc: sage-combinat, mantepse Merged in:
Authors: Andrew Gainer-Dewar Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues: documentation
Branch: a1d3536 (Commits, GitHub, GitLab) Commit: a1d35362dc7663a346971ab75c389b0e100ae9e7
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Attachments (3)

lazy_power_series-more_operations-nt.patch (8.2 KB) - added by nthiery 9 years ago.
trac_14543-suggestions-dg.patch (8.7 KB) - added by darij 9 years ago.
suggestions. please don't fold until you feel safe that they're correct!
trac_14543_cycle_index_compositional_inverse.patch (2.5 KB) - added by agd 9 years ago.
Implement compositional inverses of cycle index series

Download all attachments as: .zip

Change History (38)

comment:1 Changed 9 years ago by agd

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by 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.

comment:3 Changed 9 years ago by 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?

comment:4 Changed 9 years ago by chapoton

  • 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 agd

  • 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 follow-up: Changed 9 years ago by 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.)

Last edited 9 years ago by darij (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 9 years ago by 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?

comment:8 follow-up: Changed 9 years ago by 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.

Changed 9 years ago by nthiery

comment:9 follow-up: Changed 9 years ago by 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?).

comment:10 in reply to: ↑ 9 Changed 9 years ago by 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.

comment:11 in reply to: ↑ 8 Changed 9 years ago by 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

comment:12 Changed 9 years ago by agd

  • Branch set to u/agd/cis_comp_inv

comment:13 Changed 9 years ago by darij

EDIT: ignore

Last edited 9 years ago by darij (previous) (diff)

Changed 9 years ago by darij

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

comment:14 follow-up: Changed 9 years ago by 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.

Last edited 9 years ago by darij (previous) (diff)

comment:15 Changed 9 years ago by darij

  • Authors set to Andrew Gainer-Dewar
  • Reviewers set to Darij Grinberg

comment:16 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:17 Changed 9 years ago by jdemeyer

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

comment:18 Changed 9 years ago by agd

  • Branch u/agd/cis_comp_inv deleted

Changed 9 years ago by agd

Implement compositional inverses of cycle index series

comment:19 in reply to: ↑ 14 Changed 9 years ago by 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.

comment:20 Changed 9 years ago by 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 ).

comment:21 Changed 9 years ago by darij

  • Reviewers Darij Grinberg deleted

comment:22 Changed 9 years ago by chapoton

for the patchbots:

apply trac_14543_cycle_index_compositional_inverse.patch

comment:23 Changed 8 years ago by agd

  • Branch set to u/agd/cis/compinv
  • Commit set to df4d3f3668504897180334d5d63e718c6df76c03
  • Milestone changed from sage-5.13 to sage-6.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 vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:25 Changed 8 years ago by git

  • Commit changed from df4d3f3668504897180334d5d63e718c6df76c03 to 828c5ad975ab6c7e3d5927040cf2e9334a3e36a9

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

828c5adMerge branch 'develop' into cis/compinv

comment:26 Changed 8 years ago by mantepse

  • Cc mantepse added
  • Keywords LazyPowerSeries added

comment:27 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:28 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:29 Changed 8 years ago by rws

  • Status changed from needs_review to needs_work
Error building the documentation.
OSError: [combinat ] None:4: WARNING: citation not found: BLL-Intro

comment:30 Changed 8 years ago by chapoton

  • Work issues set to documentation

comment:31 Changed 8 years ago by chapoton

  • 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

I have corrected the failing doc, hopefully.


New commits:

d408ec0Merge branch 'u/agd/cis/compinv' of ssh://trac.sagemath.org:22/sage into 14543
5d403abtrac #14543 doc correction

comment:32 Changed 8 years ago by git

  • Commit changed from 5d403ab9c13177add932d71d074dd2cc1f8256e5 to a1d35362dc7663a346971ab75c389b0e100ae9e7

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

a1d3536trac #14543 changed behaviour when not invertible + doc

comment:33 Changed 8 years ago by chapoton

  • 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 agd

  • 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 vbraun

  • Branch changed from public/ticket/14543 to a1d35362dc7663a346971ab75c389b0e100ae9e7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.