Opened 7 years ago
Last modified 5 years ago
#14347 needs_work enhancement
Implement group cycle indices
Reported by:  agd  Owned by:  agd 

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  cycle index, species 
Cc:  sagecombinat  Merged in:  
Authors:  Andrew GainerDewar  Reviewers:  Martin Rubey 
Report Upstream:  N/A  Work issues:  
Branch:  u/agd/gcis (Commits)  Commit:  fe2387c15e2460b14eb80760d52b0cf16f2c1a94 
Dependencies:  #14846  Stopgaps: 
Description (last modified by )
Let G be a group. A Gcycle index is a map from G to the ring of cycle index series. These objects are useful for enumerating Gspecies (species equipped with an equivariant Gaction), where they serve a role analogous to the cycle indices of species.
This patch offers an implementation of Gcycle indices with their most important algebraic features (sum, product, and composition/plethysm). (The plethysm of Gcycle indices is defined in a funny way that really depends on having access to the whole Gcycle index at once; otherwise, there wouldn't be much point in having this code.)
This code is (believed to be) complete and functional. It could use a bit of attention of someone who understand the coersion system better than I do, though.
(This code weakly depends on #14846; the class implemented here has a derivative
method which calls down to CycleIndexSeries.derivative
, which does not currently do what it should.)
Attachments (2)
Change History (65)
comment:1 Changed 7 years ago by
comment:2 followup: ↓ 3 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
Replying to agd:
I seem to have made a mess of the attachments. If someone with permissions to do so happens by, could you delete everything but group_cycle_index_seriesagd.patch? Thanks!
Done!
comment:4 Changed 7 years ago by
Hi Andrew!
Thanks for your patch; this sounds interesting! I am not sure I'll have the time to make a complete review, so if anyone wants to jump in, please do! In the mean time, here are some little comments:
A Gcycle index can be interpreted as a formal linear combination of elements of G, with coefficients which are symmetric powersum functions, right? If so, may I recommend to build on top of:
CombinatorialFreeModule(SymmetricFunctions(QQ).p(), G)
Then you would get the data structure and the additive structure for free. And all the neat little accessors and such provided by CombinatorialFreeModule?.
You may want to explore the tutorials "Using Free Modules and Vector Spaces" and "Implementing Algebraic Structures" from:
http://combinat.sagemath.org/doc/thematic_tutorials/indexsagecombinat.html
See also
http://combinat.sagemath.org/doc/thematic_tutorials/coercion_and_categories.html
which is now in Sage's official thematic tutorials.
You probably also want to link back to the cycle_index method of permutation groups.
Cheers,
Nicolas
comment:5 followup: ↓ 6 Changed 7 years ago by
Nicolas,
Thanks for the feedback! I'll take a look at those tutorials.
Implementing the ring of Gcycle indices as a CombinatorialFreeModule? is an interesting idea. It's definitely appropriate from a formal perspective. At first glance, I'm concerned that it will make it harder to work with the (ordinary) cycle indices associated to the various elements of G, which are really the point of these objects, but maybe that's actually more straightforward than it looks to my naïve eyes. I'll have a go at it, in any case.
comment:6 in reply to: ↑ 5 Changed 7 years ago by
Replying to agd:
At first glance, I'm concerned that it will make it harder to work with the (ordinary) cycle indices associated to the various elements of G, which are really the point of these objects, but maybe that's actually more straightforward than it looks to my naïve eyes.
If you stumble on a concrete use case where the syntax seems to go in your way, please post it here, and we will see what we can do!
By the way: we are in the process of finalizing those two first tutorials. If you want to use the occasion to proofread them and send feedback, that would be great!
Cheers,
Nicolas
comment:7 followup: ↓ 9 Changed 7 years ago by
Nicolas,
After spending a bit of time with the documentation, it looks like CombinatorialFreeModule? is a great foundation for this code. I'm currently working on reimplementing it. The tutorials you linked were very helpful, although I expect I'm going to need some time figuring out the whole morphismcoersion system (if only because there are some decisions to be made about how things should work with subgroups). If there's a straightforward way to bake morphismgeneration into a CombinatorialFreeModule?, it would be great to see that in the tutorials. (Specifically, if G1 has a natural morphism to G2, is there a way to make CombinatorialFreeModule?(R, G1) inherit a natural morphism to CombinatorialFreeModule?(R, G2)? It seems like a reasonable thing to want to do, but I have no idea how to approach it.)
It appears to me, though, that the correct structure to use is CombinatorialFreeModule?(CycleIndexSeriesRing?(QQ), G), because then I get to take advantage of (1) the CycleIndexSeries?(Ring) code for dealing nicely with these things being infinite (using LazyPowerSeries?(Ring)) and (2) lots of semantics for doing combinatorial enumeration with those objects. Is this obviously wrong in some way I haven't yet picked up on?
Thanks again for your help!
Andrew
comment:8 followup: ↓ 10 Changed 7 years ago by
I've reimplemented this class using CombinatorialFreeModule?(CycleIndexSeriesRing?(QQ), G). The new code is less than half the length of the old and is (in my opinion) much more readable and maintainable. Big props to Nicolas for that idea!
comment:9 in reply to: ↑ 7 Changed 7 years ago by
Replying to agd:
It appears to me, though, that the correct structure to use is CombinatorialFreeModule?(CycleIndexSeriesRing?(QQ), G), because then I get to take advantage of (1) the CycleIndexSeries?(Ring) code for dealing nicely with these things being infinite (using LazyPowerSeries?(Ring)) and (2) lots of semantics for doing combinatorial enumeration with those objects. Is this obviously wrong in some way I haven't yet picked up on?
That's probably correct! I have not looked enough at the details of what you are implementing to tell :)
Cheers,
Nicolas
comment:10 in reply to: ↑ 8 Changed 7 years ago by
Replying to agd:
I've reimplemented this class using CombinatorialFreeModule?(CycleIndexSeriesRing?(QQ), G). The new code is less than half the length of the old and is (in my opinion) much more readable and maintainable. Big props to Nicolas for that idea!
Glad to hear that was the right infrastructure for you!
For a quick implementation of morphism between the two things you can probably do something like:
KG2.module_morphism(KG1.monomial*G1, codomain=G1).register_as_coercion()
(where KG1 / KG2 are the cycle index rings for G1 / G2). I can be more precise later ...
Then comes the question of whether you want to have those morphism be defined automatically. I tend to be conservative and not add them until it really itches me so much that I can't do otherwise. It's easier for backward compatibility to add coercions than remove them!
Jumping on my train!
comment:11 Changed 7 years ago by
 Status changed from new to needs_review
comment:12 Changed 7 years ago by
Per discussions elsewhere, I've added a new version of the patch which was generated using "hg export tip". The content is the same.
comment:14 Changed 7 years ago by
The bot instructions should be put here (namely in comments):
apply trac_14347_group_cycle_index_series.patch
comment:15 followup: ↓ 16 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to coverage, doctest
 the bot has found a failing doctest, see bot report
 you need to add 3 missing doctests
comment:16 in reply to: ↑ 15 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to chapoton:
Thanks for your comments!
 the bot has found a failing doctest, see bot report
This appears to be a regression in 5.10 related to the string representations of linear combinations. I'm working on chasing it down.
 you need to add 3 missing doctests
I have uploaded a new version of the patch which adds the missing doctests.
comment:17 Changed 7 years ago by
 Dependencies set to #14751
A preliminary patch has been submitted to fix the issue. I'm adding a dependency.
comment:18 Changed 7 years ago by
 Description modified (diff)
Patchbot is still trying to apply both patches. Trying instruction again:
comment:19 followup: ↓ 20 Changed 7 years ago by
syntax for the bot is like that :
apply trac_14347_group_cycle_index_series.patch
comment:20 in reply to: ↑ 19 Changed 7 years ago by
Replying to chapoton:
syntax for the bot is like that :
apply trac_14347_group_cycle_index_series.patch
One day I'll get all this stuff figured out. Thanks for the correction.
comment:21 Changed 7 years ago by
 Branch set to u/agd/gcisr
comment:22 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:23 Changed 7 years ago by
Please make it clear whether the patch or the git branch should be merged. In the latter case, change the milestone to sage6.0.
comment:24 Changed 7 years ago by
 Branch u/agd/gcisr deleted
comment:25 Changed 7 years ago by
I have uploaded a new version of the patch which makes three changes:
 Removes a spurious modification to the RST files.
 Adds a
define
method toGroupCycleIndexSeries
which, like its cousin inLazyPowerSeries
, allows for recursivelydefined series to be computed.  Adjusts the implementation of
composition
to make the previous work.
comment:26 Changed 7 years ago by
 Dependencies changed from #14751 to #14751 #14846
 Description modified (diff)
comment:27 Changed 7 years ago by
apply only trac_14347_group_cycle_index_series.patch
comment:28 Changed 7 years ago by
 Status changed from needs_review to needs_work
one failing doctest, see bot report
comment:29 Changed 7 years ago by
 Branch set to u/agd/gcis
 Commit set to e9ec2e1f198e62f3d6f96598bdf6fa2ac58619b3
 Milestone changed from sage5.13 to sage6.0
 Status changed from needs_work to needs_review
I have fixed the broken doctest.
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:30 Changed 6 years ago by
 Milestone changed from sage6.0 to sage6.1
comment:31 Changed 6 years ago by
 Commit changed from e9ec2e1f198e62f3d6f96598bdf6fa2ac58619b3 to 30a57a72bd4496b318ac3a2d9d7d4dae78642068
comment:32 Changed 6 years ago by
 Commit changed from 30a57a72bd4496b318ac3a2d9d7d4dae78642068 to 117f0992cb7ea4e1c6800b11270bb36bb56ed212
comment:33 Changed 6 years ago by
 Dependencies changed from #14751 #14846 to #14751, #14846
comment:34 Changed 6 years ago by
 Commit changed from 117f0992cb7ea4e1c6800b11270bb36bb56ed212 to 51b74fd70074a1b585c8bf021f10ccafce46114d
Branch pushed to git repo; I updated commit sha1. New commits:
51b74fd  Put GCI docstring title on own line to please Sphinx

fa566a4  Add more info to opening docstring about plethysm

51bf5c6  Fix broken link in .restricted()

87b91ad  Clarify grammar in docstring of .quotient()

d379008  Add reference to Bousquet in .quotient()

7103aff  Add gci_library to combinat rst

056d657  Add better examples to L, C, and .composition()

cb6edab  Correct docstring typos

comment:35 Changed 6 years ago by
 Reviewers set to mantepse
comment:36 Changed 6 years ago by
 Commit changed from 51b74fd70074a1b585c8bf021f10ccafce46114d to 3e076d2f460489b722319af8e3309b1b73a681da
Branch pushed to git repo; I updated commit sha1. New commits:
3e076d2  Specify location of .composition() method in docstring to suppress warning

327eb06  Add SEEALSO link to gci_library in GCI top

96b800d  Move GCI title to own line to please Sphinx

2542647  Merge remotetracking branch 'origin/develop' into gcis

9a72a00  Mention classfunctionality in GCI top docstring

12149b1  Fix bad load in .composition() docstring

21aab83  Update .define() example to use library GCIs

ddb26ef  Remove gci from global namespace

826b096  Fix OEIS reference in .composition() docstring

00a1046  Remove bogus functorial composition code

comment:37 Changed 6 years ago by
 Commit changed from 3e076d2f460489b722319af8e3309b1b73a681da to 4cc6fafb26b9a1c069bac4511bf7017ec1a44041
Branch pushed to git repo; I updated commit sha1. New commits:
4cc6faf  Rename gci_library to group_cycle_index_series_library

comment:38 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:39 Changed 6 years ago by
Reviewer name must be full name. Also please fill in your name on the trac.sagemath.org homepage.
comment:40 Changed 6 years ago by
 Reviewers changed from mantepse to Martin Rubey
comment:41 Changed 6 years ago by
Branch conflicts with #14846, merge that one in and resolve.
comment:42 followup: ↓ 44 Changed 6 years ago by
 Status changed from positive_review to needs_info
One thing that needs to be done is that the "oeis" tests need to be marked as optional. I've made a branch which is this code based on #15637 at "u/mhansen/ticket/14347". It also contains some speed improvements by being a bit more pedantic about streams / series /etc.
comment:43 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:44 in reply to: ↑ 42 Changed 6 years ago by
Replying to mhansen:
One thing that needs to be done is that the "oeis" tests need to be marked as optional. I've made a branch which is this code based on #15637 at "u/mhansen/ticket/14347". It also contains some speed improvements by being a bit more pedantic about streams / series /etc.
I've looked over this branch. The stuff I understand looks great! The rebuild in 927418b, however, is kind of mysterious to me. However, the doctests check out, and some code I'm currently using for a research project still works (and is noticeably faster), so that's good news.
comment:45 Changed 6 years ago by
It primarily just splits the internal functions into methods on a class. It also does not produce intermediate series for the linear combination (LinearCombinationStream? vs. sum(coeff*monomial_composer(part, g) for part,coeff in term)
). map_item
does the job building the dict and using _from_dict
. Let me know if you have any specific questions.
comment:46 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:47 Changed 6 years ago by
 Commit changed from 4cc6fafb26b9a1c069bac4511bf7017ec1a44041 to 20b2d2954aee53bc867ebf7e86592e331445766f
Branch pushed to git repo; I updated commit sha1. New commits:
20b2d29  Merge remotetracking branch 'origin/develop' into u/agd/gcis

comment:48 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:49 Changed 5 years ago by
 Milestone changed from sage6.4 to sage6.6
comment:50 Changed 5 years ago by
 Commit changed from 20b2d2954aee53bc867ebf7e86592e331445766f to 59285959a2bad2b0cbc4b5b7d775154e46f7eed9
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
186f4ed  Merge branch 'master' into u/agd/gcis

4e2048b  Rebase old work on current mainline Sage

ab9c7d1  Rebase #14846 on current mainline Sage

9915229  Merge remotetracking branch 'origin/u/agd/cis/deriv' into u/agd/gcis

842e1aa  Fix an_element method in GroupCycleIndexSeriesRing

8d38594  Mark OEIS tests optional

be3b843  Remove spurious extra copy of GCI library

5928595  Implement GCIS functorial composition

comment:51 Changed 5 years ago by
 Milestone changed from sage6.6 to sage6.8
 Status changed from needs_info to needs_review
Since #15673 seems to have died on the vine, I have rebuilt this code on top of the current mainline Sage. My paper which presents this material and code has been accepted for publication, so I'd really love to get this up and running before too many more people email me wondering why the code doesn't work. (Note that this does depend on #14846, which I'm also currently trying to revive.)
comment:52 Changed 5 years ago by
 Commit changed from 59285959a2bad2b0cbc4b5b7d775154e46f7eed9 to acfd522f79735c65e07f1f77674d776baa05777a
Branch pushed to git repo; I updated commit sha1. New commits:
acfd522  Add explanation of GCIS functorial_composition() example

comment:53 Changed 5 years ago by
if its not too late, I'd review this in the first or second week of july, together with #14846)
Martin
comment:54 Changed 5 years ago by
That would be splendid! Please let me know if you have any questions or concerns.
comment:55 Changed 5 years ago by
I'm already two weeks late :(
comment:56 Changed 5 years ago by
 Branch changed from u/agd/gcis to u/mantepse/gcis
comment:57 Changed 5 years ago by
 Commit changed from acfd522f79735c65e07f1f77674d776baa05777a to a1ae1f78b60959f5cdd3699a074c33d59de4690e
Branch pushed to git repo; I updated commit sha1. New commits:
a1ae1f7  fix doc formatting

comment:58 Changed 5 years ago by
 Status changed from needs_review to positive_review
There were a few trivial formatting fixes to do, which I did (git trac
automatically switched to this modified branch, I hope I didn't mess up anything)
So, the code looks fine, thanks for contributing and thanks for your patience!
comment:59 Changed 5 years ago by
 Milestone changed from sage6.8 to sage6.9
comment:60 Changed 5 years ago by
 Dependencies changed from #14751, #14846 to #14846
comment:61 Changed 5 years ago by
 Work issues coverage, doctest deleted
comment:62 followup: ↓ 63 Changed 5 years ago by
 Status changed from positive_review to needs_work
Fails on OSX
sage t long src/sage/combinat/species/group_cycle_index_series.py ********************************************************************** File "src/sage/combinat/species/group_cycle_index_series.py", line 354, in sage.combinat.species.group_cycle_index_series.GroupCycleIndexSeries.functorial_composition Failed example: D.quotient().isotype_generating_series().counts(5) Expected: [1, 1, 3, 13, 144] Got: [1, 1, 1, 1, 1] ********************************************************************** 1 item had failures: 1 of 11 in sage.combinat.species.group_cycle_index_series.GroupCycleIndexSeries.functorial_composition
comment:63 in reply to: ↑ 62 Changed 5 years ago by
 Branch changed from u/mantepse/gcis to u/agd/gcis
 Commit changed from a1ae1f78b60959f5cdd3699a074c33d59de4690e to fe2387c15e2460b14eb80760d52b0cf16f2c1a94
Replying to vbraun:
Huh. I was unable to reproduce this on either my desktop or my buildbot/server, both running Debian. I have updated the branch with the latest develop
, just in case. I'll try to find a Mac to test with, but it may be some time.
New commits:
ced31fc  Merge branch 'develop' into u/mantepse/gcis

fe2387c  Merge branch 'develop' into u/mantepse/gcis

I seem to have made a mess of the attachments. If someone with permissions to do so happens by, could you delete everything but group_cycle_index_seriesagd.patch? Thanks!