Opened 7 years ago

Closed 5 years ago

#14846 closed enhancement (fixed)

CycleIndexSeries derivative, integral, exponential methods are not combinatorial

Reported by: agd Owned by: agd
Priority: major Milestone: sage-6.8
Component: combinatorics Keywords: LazyPowerSeries, species
Cc: Merged in:
Authors: Andrew Gainer-Dewar Reviewers: Martin Rubey
Report Upstream: N/A Work issues: documentation
Branch: ab9c7d1 (Commits) Commit: ab9c7d161b8318bc5edffb3bb3dd66bc5c503318
Dependencies: Stopgaps:

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

Attachments (1)

trac_14846_cis_deriv_int_exp_methods.patch (9.0 KB) - added by agd 7 years ago.

Download all attachments as: .zip

Change History (39)

comment:1 Changed 7 years ago by agd

For the patchbot:

apply trac_14846_cis_deriv_int_exp_methods.patch

comment:2 Changed 7 years ago by agd

  • Status changed from new to needs_review

comment:3 Changed 7 years ago by agd

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.

comment:4 Changed 7 years ago by agd

  • Branch set to u/agd/cis_deriv_int_exp_methods

comment:5 Changed 7 years ago by jdemeyer

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.

comment:6 Changed 7 years ago by agd

  • Branch u/agd/cis_deriv_int_exp_methods deleted

comment:7 Changed 7 years ago by agd

  • Description modified (diff)

comment:8 Changed 7 years ago by agd

  • Authors set to Andrew Gainer-Dewar

Rebased patch to apply over 5.12.beta4.

comment:9 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues set to documentation

Could you please add doctests to the three _lps functions ?

comment:10 Changed 7 years ago by agd

  • Branch set to u/agd/cis/deriv
  • Commit set to 5ce33898e941771132cdf94837a4baf16a2cfddb
  • Milestone changed from sage-5.13 to sage-6.0
  • Status changed from needs_work to needs_review

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?

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:12 Changed 6 years ago by git

  • Commit changed from 5ce33898e941771132cdf94837a4baf16a2cfddb to 5547d749d9136f0eddf4400237183b78245e3f51

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

5547d74Merge branch 'develop' into cis/deriv

comment:13 Changed 6 years ago by mantepse

  • Reviewers set to mantepse

comment:14 follow-up: Changed 6 years ago by mantepse

Hi Andrew,

I'd suggest to really remove access to the three inherited methods, and rewrite the methods that use _lps_exponential accordingly:

  • in set_species, we really want to return the "true" exponential cycle index series
  • in partition_species, the "true" exponential of the "true" exponential - 1
  • in subset_species, the square of the "true" exponential

Finally, the implementation of the "true" exponential can be taken from what's in set_species in sage 6.0.

As far as I can see, the other two methods _lps_derivative and _lps_integral are not used anywhere.

This might have a speed penalty, but I'd worry about that only if it's serious. I think it's not a good idea to make the cycle index series depend on the species code, as in the proposed patch.

I would perhaps also put the definition for the combinatorial logarithm into the same file. I think at some point we should reorganise the files in the species directory..

Martin

Last edited 6 years ago by mantepse (previous) (diff)

comment:15 Changed 6 years ago by git

  • Commit changed from 5547d749d9136f0eddf4400237183b78245e3f51 to dd77e4ae6388bd8ad52d7f6a13848fe6490b25d2

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

dd77e4aMove log and exp series code to generating_series.py
ca21d87Redesign patch to eliminate _lps_* methods and bad dependencies
c1998f2Merge remote-tracking branch 'origin/develop' into cis/deriv

comment:16 in reply to: ↑ 14 Changed 6 years ago by agd

Thanks for the suggestions!

Replying to mantepse:

I'd suggest to really remove access to the three inherited methods, and rewrite the methods that use _lps_exponential accordingly:

Sounds good to me. Done, in the latest push.

  • in set_species, we really want to return the "true" exponential cycle index series
  • in partition_species, the "true" exponential of the "true" exponential - 1
  • in subset_species, the square of the "true" exponential

I have rewritten all of these to use algebraic operations on the exponential CIS.

As far as I can see, the other two methods _lps_derivative and _lps_integral are not used anywhere.

Seems to be true. I just included them for completeness. They're gone now.

This might have a speed penalty, but I'd worry about that only if it's serious. I think it's not a good idea to make the cycle index series depend on the species code, as in the proposed patch.

Actually, I think the new way should actually be *faster*, there's just one instance of the exponential series which gets cached and handed around.

I would perhaps also put the definition for the combinatorial logarithm into the same file.

Once I wrote the other stuff, this seemed very reasonable, so I've done that as well.

comment:17 Changed 6 years ago by mantepse

  • Status changed from needs_review to positive_review

comment:18 Changed 6 years ago by vbraun

Reviewer name must be full name. Also please fill in your name on the trac.sagemath.org homepage.

comment:19 Changed 6 years ago by mantepse

  • Reviewers changed from mantepse to Martin Rubey

comment:20 Changed 6 years ago by mantepse

  • Keywords LazyPowerSeries species added

comment:21 follow-up: Changed 6 years ago by mhansen

  • Status changed from positive_review to needs_info

One (minor) issue is the removal of combinatorial_logarithm.py which might need to be deprecated. 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.

See http://git.sagemath.org/sage.git/log/?h=u/mhansen/ticket/14846

Last edited 6 years ago by mhansen (previous) (diff)

comment:22 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:23 Changed 6 years ago by git

  • Commit changed from dd77e4ae6388bd8ad52d7f6a13848fe6490b25d2 to c7d73451550ce689a96668a210ab04b86d3a66ad

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

30fcfdeInitial work on new streams
96e4ea3Make streams know about their order / aorder
a076622Move generating_series over to new streams format
9e56173Fix issue in LazyPowerSeries.__repr__ with (eventually) constant streams
fa83cccMore work on moving generating_series over to new format
3b56620Fix repr in recursive species
ea1902aFix cycle species cis
458bdafFix bug in generating_series
9b038bbClean up order_operation and make the default to return 0
fefaacfStart making the basic species use Streams directly

comment:24 Changed 6 years ago by git

  • Commit changed from c7d73451550ce689a96668a210ab04b86d3a66ad to 334c0956250038eae2d6efc915231e650b13be79

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

a630924Implement combinatorial derivative, etc. for CycleIndexSeries
5ce3389Add doctests for _lps_* methods
5547d74Merge branch 'develop' into cis/deriv
c1998f2Merge remote-tracking branch 'origin/develop' into cis/deriv
ca21d87Redesign patch to eliminate _lps_* methods and bad dependencies
dd77e4aMove log and exp series code to generating_series.py
6989f3fMerge remote-tracking branch 'origin/develop' into cis-deriv
2d3b466Merge remote-tracking branch 'origin/u/mhansen/ticket/14846' into cis-deriv
4efe9b0Rename CycleIndexSeriesRing.omega() to logarithm_series
334c095Rename CycleIndexSeriesRing().exponential() to exponential_series()

comment:25 in reply to: ↑ 21 Changed 6 years ago by agd

  • Dependencies set to 15673

Replying to mhansen:

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:

6989f3fMerge remote-tracking branch 'origin/develop' into cis-deriv
2d3b466Merge remote-tracking branch 'origin/u/mhansen/ticket/14846' into cis-deriv
4efe9b0Rename CycleIndexSeriesRing.omega() to logarithm_series
334c095Rename CycleIndexSeriesRing().exponential() to exponential_series()
Last edited 6 years ago by agd (previous) (diff)

comment:26 Changed 6 years ago by mantepse

  • Dependencies changed from 15673 to #15673

comment:27 Changed 6 years ago by git

  • Commit changed from 334c0956250038eae2d6efc915231e650b13be79 to 538dde76d0e116f67e1115337193fe12c48ce62b

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

538dde7Fix broken docstring in combinatorial_logarithm.py

comment:28 Changed 6 years ago by mhansen

Cool, your changes look good to me!

comment:29 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:30 follow-up: Changed 6 years ago by agd

  • Dependencies #15673 deleted

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!

comment:31 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:32 in reply to: ↑ 30 Changed 6 years ago by mantepse

I agree. I wonder what happened to #16137.

comment:33 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.6

comment:34 Changed 5 years ago by git

  • Commit changed from 538dde76d0e116f67e1115337193fe12c48ce62b to ab9c7d161b8318bc5edffb3bb3dd66bc5c503318

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

ab9c7d1Rebase #14846 on current mainline Sage

comment:35 Changed 5 years ago by agd

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.

comment:36 Changed 5 years ago by agd

  • Milestone changed from sage-6.6 to sage-6.8
  • Status changed from needs_info to needs_review

comment:37 Changed 5 years ago by mantepse

  • Status changed from needs_review to positive_review

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!

comment:38 Changed 5 years ago by vbraun

  • Branch changed from u/agd/cis/deriv to ab9c7d161b8318bc5edffb3bb3dd66bc5c503318
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.