CycleIndexSeries derivative, integral, exponential methods are not combinatorial

[sagetrac-agd]

The CycleIndexSeries class inherits derivative, integral, and exponential methods from its parent class LazyPowerSeries. However, these operations (which are perfectly reasonable at the LazyPowerSeries level) are not combinatorially natural. In fact, there is a differentiation operator on cycle index series, but it's something entirely different, and anti-differentiation is in general impossible!

In addition to being confusing, this discrepancy has the potential to hinder work using the CycleIndexSeries class. The combinatorial operation of cycle index differentiation is very useful in enumerative work.

All that said, the existing exponential and derivative methods are used for algebraic magic tricks in some of the existing code, so it's important not to take it away altogether.

The attached patch makes the following changes:

• Adds _lps_derivative, _lps_integral, and _lps_exponential methods to CycleIndexSeries which call up using super.

• Refactors the internal code which previously used exponential and derivative to use _lps_exponential and _lps_derivative instead.

• Implements a new derivative method which computes the combinatorial derivative of a cycle index series.

• Implements a new pointing method which implements a related combinatorial operation.

• Implements a new integral method which raises a NotImplementedError to prevent any user confusion (since, as explained in the docstring, there may be infinitely many very distinct cycle indices with a given derivative).

• Implements a new exponential method which returns the composition E(self) for E the cycle index series of SetSpecies.

• Implements a new logarithm method which returns the composition Ω(self) for Ω the cycle index series implemented in CombinatorialLogarithmSeries.

Docstrings and doctests are included for everything but the lps* methods, which just call up to super. I'm not sure what a doctest for these would even look like, but I'm open to suggestions.

Component: combinatorics

Keywords: LazyPowerSeries, species

Work Issues: documentation

Author: Andrew Gainer-Dewar

Branch/Commit: ab9c7d1

Reviewer: Martin Rubey

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

[sagetrac-agd]

comment:1

For the patchbot:

apply trac_14846_cis_deriv_int_exp_methods.patch

[sagetrac-agd]

comment:3

I have uploaded a new version of the patch which makes a small change: rather than building the terms of the derivative of a CycleIndexSeries using an opaque list concatenation, I have used the CycleIndexSeriesRing.term method.

[sagetrac-agd]

Branch: u/agd/cis_deriv_int_exp_methods

[jdemeyer]

comment:5

Please make it clear whether the patch or the git branch should be merged. In the latter case, change the milestone to sage-6.0.

[sagetrac-agd]

Changed branch from u/agd/cis_deriv_int_exp_methods to none

[sagetrac-agd]

comment:8

Rebased patch to apply over 5.12.beta4.

[sagetrac-agd]

Author: Andrew Gainer-Dewar

[fchapoton]

comment:9

Attachment: trac_14846_cis_deriv_int_exp_methods.patch.gz

Could you please add doctests to the three _lps functions ?

[fchapoton]

Work Issues: documentation

[sagetrac-agd]

comment:10

Skeletal doctests added for the three lps* functions. I have no idea whether this is the right way to test this sort of method, but at least it's a test.

Additionally, 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?

[sagetrac-agd]

Branch: u/agd/cis/deriv

[sagetrac-agd]

Commit: 5ce3389

[sagetrac-git]

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

5547d74

Merge branch 'develop' into cis/deriv

[sagetrac-git]

Changed commit from 5ce3389 to 5547d74

[mantepse]

Reviewer: mantepse

[sagetrac-agd]

Dependencies: 15673

[sagetrac-agd]

comment:25

Replying to @mwhansen:

One (minor) issue is the removal of combinatorial_logarithm.py which might need to be deprecated.

Ah, yes, this is an important point. I sometimes forget that other people might have used my code… =D

I've also done a "rebase" of this on top of #15673 which makes the code a little bit cleaner. This is in branch "u/mhansen/ticket/14846" . Ideally, I'd prefer to have #15673 go in first since the rebase/merge of this ticket is easier than the other way around.

I don't yet understand everything that's happening with #15673, but I'm starting to take a look at it. I'm definitely open to the idea, though—better series code will make all our work easier! I've taken a look at your rebased version of this, and have a few thoughts up-front:

• In the docstring for the deprecated CombinatorialLogarithmSeries(), you point the reader to CycleIndexSeriesRing(R).exponential(), but in fact this should be to CycleIndexSeriesRing(R).omega().

• Relatedly, I'd argue that the CycleIndexSeriesRing(R).omega() and CycleIndexSeriesRing(R).exponential() methods should instead be named logarithm_series() and exponential_series(). In the first place, the Ω notation is not totally standard (it's used by Labelle, but other authors have called this virtual species "Con" or other things); in the second, I think it's conceptually important to emphasize that these objects are series and not operations, since the operations are implemented as CycleIndexSeries().exponential() and CycleIndexSeries().logarithm() respectively. (Of course, the documentation should mention the relationship between the two!)

• CycleIndexSeriesRing.LogarithmStream appears to be internal, so the docstring of CycleIndexSeries.logarithm() should refer instead to CycleIndexSeriesRing.logarithm_series.

I've updated the ticket branch to use your code with these changes. I've also set a dependency on #15673. (Evidently, I bungled the ticket modifications a bit, but I think it's all sorted now.)

---

New commits:

6989f3f	Merge remote-tracking branch 'origin/develop' into cis-deriv
2d3b466	Merge remote-tracking branch 'origin/u/mhansen/ticket/14846' into cis-deriv
4efe9b0	Rename CycleIndexSeriesRing.omega() to logarithm_series
334c095	Rename CycleIndexSeriesRing().exponential() to exponential_series()

[mantepse]

Changed dependencies from 15673 to #15673

[sagetrac-git]

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

538dde7

Fix broken docstring in combinatorial_logarithm.py

[sagetrac-git]

Changed commit from 334c095 to 538dde7

[mwhansen]

comment:28

Cool, your changes look good to me!

[sagetrac-agd]

comment:30

While #15673 looks like it will bring some much-needed improvements to the algebraic machinery of species in Sage, it also looks like it's going to take a while to implement. I've been fielding questions from other researchers who would like to use the code in #14347, which definitely depends on this one, so I'd be very grateful if we could move forward on this one now. I will, of course, be happy to revisit the issue in the context of #15673 once that situation stabilizes!

[sagetrac-agd]

Changed dependencies from #15673 to none

[mantepse]

comment:32

I agree. I wonder what happened to #16137.

[sagetrac-git]

Changed commit from 538dde7 to ab9c7d1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ab9c7d1

Rebase #14846 on current mainline Sage

[sagetrac-agd]

comment:35

Since #15673 seems to have died on the vine, I have rebuilt the code for this commit on top of current mainline Sage 6.7. All doctests in combinat/species pass.

[mantepse]

comment:37

I played with the code and the examples, and found myself happy. For example,

sage: T = CombinatorialSpecies()
sage: X = species.SingletonSpecies()
sage: E = species.SetSpecies()
sage: T.define(X*E(T))
sage: s = T.cycle_index_series()
sage: oeis(s.logarithm().generating_series().counts(12))
0: A133297: a(n) = n!*Sum_{k=1..n} (-1)^(k+1)*n^(n-k-1)/(n-k)!.
sage: oeis(s.pointing().generating_series().counts(12)[1:])
0: A000312: Number of labeled mappings from n points to themselves (endofunctions): n^n.
1: A177885: (1-n)^(n-1).
2: A086783: Discriminant of the polynomial x^n - 1.
sage: oeis(s.pointing().isotype_generating_series().counts(12)[1:])
0: A000107: Number of rooted trees with n nodes and a single labeled node; pointed rooted trees; vertebrates.

Thanks for the code and thanks for the patience!

[vbraun]

Changed branch from u/agd/cis/deriv to ab9c7d1