Opened 7 years ago

Last modified 4 years ago

#14347 needs_work enhancement

Implement group cycle indices

Reported by: agd Owned by: agd
Priority: major Milestone: sage-6.9
Component: combinatorics Keywords: cycle index, species
Cc: sage-combinat Merged in:
Authors: Andrew Gainer-Dewar Reviewers: Martin Rubey
Report Upstream: N/A Work issues:
Branch: u/agd/gcis (Commits) Commit: fe2387c15e2460b14eb80760d52b0cf16f2c1a94
Dependencies: #14846 Stopgaps:

Description (last modified by agd)

Let G be a group. A G-cycle index is a map from G to the ring of cycle index series. These objects are useful for enumerating G-species (species equipped with an equivariant G-action), where they serve a role analogous to the cycle indices of species.

This patch offers an implementation of G-cycle indices with their most important algebraic features (sum, product, and composition/plethysm). (The plethysm of G-cycle indices is defined in a funny way that really depends on having access to the whole G-cycle 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)

group_cycle_index_series-agd.patch (9.4 KB) - added by agd 7 years ago.
Re-implement using CombinatorialFreeModule?
trac_14347_group_cycle_index_series.patch (14.7 KB) - added by agd 6 years ago.
Patch to implement group cycle index series

Download all attachments as: .zip

Change History (65)

comment:1 Changed 7 years ago by agd

  • Authors set to Andrew Gainer-Dewar

comment:2 follow-up: Changed 7 years ago by 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_series-agd.patch? Thanks!

comment:3 in reply to: ↑ 2 Changed 7 years ago by nthiery

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_series-agd.patch? Thanks!

Done!

comment:4 Changed 7 years ago by nthiery

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 G-cycle 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/index-sage-combinat.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 follow-up: Changed 7 years ago by agd

Nicolas,

Thanks for the feedback! I'll take a look at those tutorials.

Implementing the ring of G-cycle 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 nthiery

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 follow-up: Changed 7 years ago by agd

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 re-implementing it. The tutorials you linked were very helpful, although I expect I'm going to need some time figuring out the whole morphism-coersion 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 morphism-generation 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

Changed 7 years ago by agd

Re-implement using CombinatorialFreeModule?

comment:8 follow-up: Changed 7 years ago by agd

I've re-implemented 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 nthiery

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 nthiery

Replying to agd:

I've re-implemented 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 agd

  • Status changed from new to needs_review

comment:12 Changed 7 years ago by agd

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:13 Changed 7 years ago by agd

  • Description modified (diff)

Add bot instructions.

comment:14 Changed 7 years ago by chapoton

The bot instructions should be put here (namely in comments):

apply trac_14347_group_cycle_index_series.patch

Last edited 7 years ago by chapoton (previous) (diff)

comment:15 follow-up: Changed 7 years ago by chapoton

  • 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 6 years ago by agd

  • 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. It appears to be caused by a change in the misc.repr_lincomb method, which now assumes that the coefficients of abstract linear combinations can be compared to 0. I've submitted a ticket (#14751) to try to sort this out.

  • you need to add 3 missing doctests

I have uploaded a new version of the patch which adds the missing doctests.

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

comment:17 Changed 6 years ago by agd

  • Dependencies set to #14751

A preliminary patch has been submitted to fix the issue. I'm adding a dependency.

comment:18 Changed 6 years ago by agd

  • Description modified (diff)

Patchbot is still trying to apply both patches. Trying instruction again:

Apply trac_14347_group_cycle_index_series.patch

comment:19 follow-up: Changed 6 years ago by chapoton

syntax for the bot is like that :

apply trac_14347_group_cycle_index_series.patch

comment:20 in reply to: ↑ 19 Changed 6 years ago by agd

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 6 years ago by agd

  • Branch set to u/agd/gcisr

comment:22 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:23 Changed 6 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:24 Changed 6 years ago by agd

  • Branch u/agd/gcisr deleted

comment:25 Changed 6 years ago by agd

I have uploaded a new version of the patch which makes three changes:

  1. Removes a spurious modification to the RST files.
  2. Adds a define method to GroupCycleIndexSeries which, like its cousin in LazyPowerSeries, allows for recursively-defined series to be computed.
  3. Adjusts the implementation of composition to make the previous work.

Changed 6 years ago by agd

Patch to implement group cycle index series

comment:26 Changed 6 years ago by agd

  • Dependencies changed from #14751 to #14751 #14846
  • Description modified (diff)

comment:27 Changed 6 years ago by chapoton

apply only trac_14347_group_cycle_index_series.patch

comment:28 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

one failing doctest, see bot report

comment:29 Changed 6 years ago by agd

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

  • Milestone changed from sage-6.0 to sage-6.1

comment:31 Changed 6 years ago by git

  • Commit changed from e9ec2e1f198e62f3d6f96598bdf6fa2ac58619b3 to 30a57a72bd4496b318ac3a2d9d7d4dae78642068

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

30a57a7Add GCI library and load on Sage start
c339ea4Add functorial composition to GCIS code
c1fdd26Merge branch 'develop' into gcis

comment:32 Changed 6 years ago by git

  • Commit changed from 30a57a72bd4496b318ac3a2d9d7d4dae78642068 to 117f0992cb7ea4e1c6800b11270bb36bb56ed212

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

117f099Correct generators for example GCIs to use RationalField coefficients
3a8ef86Add restricted() method to GCIS

comment:33 Changed 6 years ago by mantepse

  • Dependencies changed from #14751 #14846 to #14751, #14846

comment:34 Changed 6 years ago by git

  • Commit changed from 117f0992cb7ea4e1c6800b11270bb36bb56ed212 to 51b74fd70074a1b585c8bf021f10ccafce46114d

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

51b74fdPut GCI docstring title on own line to please Sphinx
fa566a4Add more info to opening docstring about plethysm
51bf5c6Fix broken link in .restricted()
87b91adClarify grammar in docstring of .quotient()
d379008Add reference to Bousquet in .quotient()
7103affAdd gci_library to combinat rst
056d657Add better examples to L, C, and .composition()
cb6edabCorrect docstring typos

comment:35 Changed 6 years ago by mantepse

  • Reviewers set to mantepse

comment:36 Changed 6 years ago by git

  • Commit changed from 51b74fd70074a1b585c8bf021f10ccafce46114d to 3e076d2f460489b722319af8e3309b1b73a681da

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

3e076d2Specify location of .composition() method in docstring to suppress warning
327eb06Add SEEALSO link to gci_library in GCI top
96b800dMove GCI title to own line to please Sphinx
2542647Merge remote-tracking branch 'origin/develop' into gcis
9a72a00Mention class-functionality in GCI top docstring
12149b1Fix bad load in .composition() docstring
21aab83Update .define() example to use library GCIs
ddb26efRemove gci from global namespace
826b096Fix OEIS reference in .composition() docstring
00a1046Remove bogus functorial composition code

comment:37 Changed 6 years ago by git

  • Commit changed from 3e076d2f460489b722319af8e3309b1b73a681da to 4cc6fafb26b9a1c069bac4511bf7017ec1a44041

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

4cc6fafRename gci_library to group_cycle_index_series_library

comment:38 Changed 6 years ago by mantepse

  • Status changed from needs_review to positive_review

comment:39 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:40 Changed 6 years ago by mantepse

  • Reviewers changed from mantepse to Martin Rubey

comment:41 Changed 6 years ago by vbraun

Branch conflicts with #14846, merge that one in and resolve.

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

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

  • Milestone changed from sage-6.1 to sage-6.2

comment:44 in reply to: ↑ 42 Changed 6 years ago by agd

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 mhansen

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 vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:47 Changed 5 years ago by git

  • Commit changed from 4cc6fafb26b9a1c069bac4511bf7017ec1a44041 to 20b2d2954aee53bc867ebf7e86592e331445766f

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

20b2d29Merge remote-tracking branch 'origin/develop' into u/agd/gcis

comment:48 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:49 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.6

comment:50 Changed 5 years ago by git

  • Commit changed from 20b2d2954aee53bc867ebf7e86592e331445766f to 59285959a2bad2b0cbc4b5b7d775154e46f7eed9

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

186f4edMerge branch 'master' into u/agd/gcis
4e2048bRebase old work on current mainline Sage
ab9c7d1Rebase #14846 on current mainline Sage
9915229Merge remote-tracking branch 'origin/u/agd/cis/deriv' into u/agd/gcis
842e1aaFix an_element method in GroupCycleIndexSeriesRing
8d38594Mark OEIS tests optional
be3b843Remove spurious extra copy of GCI library
5928595Implement GCIS functorial composition

comment:51 Changed 5 years ago by agd

  • Milestone changed from sage-6.6 to sage-6.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 git

  • Commit changed from 59285959a2bad2b0cbc4b5b7d775154e46f7eed9 to acfd522f79735c65e07f1f77674d776baa05777a

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

acfd522Add explanation of GCIS functorial_composition() example

comment:53 Changed 4 years ago by mantepse

if its not too late, I'd review this in the first or second week of july, together with #14846)

Martin

comment:54 Changed 4 years ago by agd

That would be splendid! Please let me know if you have any questions or concerns.

comment:55 Changed 4 years ago by mantepse

I'm already two weeks late :-(

comment:56 Changed 4 years ago by mantepse

  • Branch changed from u/agd/gcis to u/mantepse/gcis

comment:57 Changed 4 years ago by git

  • Commit changed from acfd522f79735c65e07f1f77674d776baa05777a to a1ae1f78b60959f5cdd3699a074c33d59de4690e

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

a1ae1f7fix doc formatting

comment:58 Changed 4 years ago by mantepse

  • 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 4 years ago by chapoton

  • Milestone changed from sage-6.8 to sage-6.9

comment:60 Changed 4 years ago by vbraun

  • Dependencies changed from #14751, #14846 to #14846

comment:61 Changed 4 years ago by chapoton

  • Work issues coverage, doctest deleted

comment:62 follow-up: Changed 4 years ago by vbraun

  • 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 4 years ago by agd

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

ced31fcMerge branch 'develop' into u/mantepse/gcis
fe2387cMerge branch 'develop' into u/mantepse/gcis
Note: See TracTickets for help on using tickets.