Implement group cycle indices

[sagetrac-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.)

Depends on #14846

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: cycle index, species

Author: Andrew Gainer-Dewar

Branch/Commit: u/mantepse/gcis @ 7b3cb8b

Reviewer: Martin Rubey

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

[sagetrac-agd]

Author: Andrew Gainer-Dewar

[sagetrac-agd]

comment:2

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!

[nthiery]

comment:3

Replying to @sagetrac-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!

[nthiery]

comment:4

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

[sagetrac-agd]

comment:5

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.

[nthiery]

comment:6

Replying to @sagetrac-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

[sagetrac-agd]

comment:7

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

[sagetrac-agd]

Re-implement using CombinatorialFreeModule

[sagetrac-agd]

comment:8

Attachment: group_cycle_index_series-agd.patch.gz

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!

[nthiery]

comment:9

Replying to @sagetrac-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

[nthiery]

comment:10

Replying to @sagetrac-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!

[sagetrac-agd]

comment:12

Per discussions elsewhere, I've added a new version of the patch which was generated using "hg export tip". The content is the same.

[sagetrac-agd]

comment:13

Add bot instructions.

[fchapoton]

comment:14

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

apply trac_14347_group_cycle_index_series.patch

[fchapoton]

Work Issues: coverage, doctest

[fchapoton]

comment:15

• the bot has found a failing doctest, see bot report

• you need to add 3 missing doctests

[sagetrac-agd]

comment:16

Replying to @fchapoton:

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.

[sagetrac-agd]

Dependencies: #14751

[sagetrac-agd]

comment:17

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

[sagetrac-git]

Changed commit from 5928595 to acfd522

[sagetrac-git]

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

acfd522

Add explanation of GCIS functorial_composition() example

[mantepse]

comment:53

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

Martin

[sagetrac-agd]

comment:54

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

[mantepse]

comment:55

I'm already two weeks late :-(

[mantepse]

Changed branch from u/agd/gcis to u/mantepse/gcis

[sagetrac-git]

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

a1ae1f7

fix doc formatting

[sagetrac-git]

Changed commit from acfd522 to a1ae1f7

[mantepse]

comment:58

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!

[vbraun]

Changed dependencies from #14751, #14846 to #14846

[fchapoton]

Changed work issues from coverage, doctest to none

[vbraun]

comment:62

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

[sagetrac-agd]

Changed branch from u/mantepse/gcis to u/agd/gcis

[sagetrac-agd]

comment:63

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

[sagetrac-agd]

Changed commit from a1ae1f7 to fe2387c

[mantepse]

Changed branch from u/agd/gcis to u/mantepse/gcis

[sagetrac-git]

Changed commit from fe2387c to 7b3cb8b

[sagetrac-git]

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

684ccea	fix imports, make all tests pass
7b3cb8b	fix a few trivialities in documentation