The Burnside ring of a group

[Newtech66]

trafficstars

Resolves #35475.

We implement the Burnside ring for a group $G$. We provide a few ways to construct elements, either directly as a formal sum of orbit types $[G/H]$ (where $H$ is a subgroup of $G$), or by providing a group action $\alpha: G \times X \rightarrow X$ on some set $X$. Finally, we implement addition and multiplication of ring elements.

:memo: Checklist

• [x] The title is concise and informative.
• [x] The description explains in detail what this PR is about.
• [x] I have linked a relevant issue or discussion.
• [ ] I have created tests covering the changes.
• [ ] I have updated the documentation and checked the documentation preview.

@mantepse

[github-actions[bot]]

Documentation preview for this PR (built with commit dccdfbfcc1243826b673c0756456e0785c0e77da; changes) is ready! :tada: This preview will update shortly after each push to this PR.

[mantepse]

@trevorkarn, I'm adding you here because of your request at https://github.com/sagemath/sage/issues/35475#issuecomment-1507434563

The current branch is a prototype, not yet ready for review.

[trevorkarn]

@trevorkarn, I'm adding you here because of your request at #35475 (comment)

The current branch is a prototype, not yet ready for review.

Thanks so much @mantepse! Just let me know when it is ready for review.

[mantepse]

You are down to 250 lines with more functionality!

You can now use

sage -tox -- src/sage/rings/burnside.py

to run most (perhaps even all) checks locally.

I think it would be good to have one test checking that the cache is populated only as necessary. Since BurnsideRing inerits from UniqueRepresentation, I guess it's best to use a group which doesn't occur in the tests otherwise, and maybe a big one. For example:

sage: G = SymmetricGroup(6)
sage: B = BurnsideRing(G)
sage: X = Subsets(6, 2)
sage: b = B.construct_from_action(lambda g, x: X([g(e) for e in x]), X)
sage: B.basis().keys()._cache
{720: [Symmetric group of order 6! as a permutation group],
 48: [Subgroup generated by [(3,5,4,6), (1,2)(4,5,6)] of (Symmetric group of order 6! as a permutation group)]}
sage: b^2
B[((3,5,4,6), (1,2)(4,5,6))] + B[((5,6), (4,6,5))] + B[((5,6), (3,4), (1,2))]
sage: B.basis().keys()._cache
{720: [Symmetric group of order 6! as a permutation group],
 48: [Subgroup generated by [(3,5,4,6), (1,2)(4,5,6)] of (Symmetric group of order 6! as a permutation group)],
 6: [Subgroup generated by [(5,6), (4,6,5)] of (Symmetric group of order 6! as a permutation group)],
 8: [Subgroup generated by [(5,6), (3,4), (1,2)] of (Symmetric group of order 6! as a permutation group)]}

[mantepse]

One other test:

sage: G = SymmetricGroup(4)
sage: B = BurnsideRing(G)
sage: X = Subsets(4, 2)
sage: b = B.construct_from_action(lambda g, x: X([g(e) for e in x]), X)
sage: b.tensor(b)
B[((3,4), (1,2), (1,2)(3,4))] # B[((3,4), (1,2), (1,2)(3,4))]
sage: (b.tensor(b))^2
4*B[((3,4), (1,2), (1,2)(3,4))] # B[((3,4), (1,2), (1,2)(3,4))] + 2*B[((),)] # B[((3,4), (1,2), (1,2)(3,4))] + 2*B[((3,4), (1,2), (1,2)(3,4))] # B[((),)] + B[((),)] # B[((),)]

[mantepse]

I just realised that you can remove BurnsideRing._element_constructor_ completely, and instead implement ConjugacyClassesOfSubgroups.__contains__ (which we should provide anyway):

    def __contains__(self, H):
        return H.is_subgroup(self._G)

[mantepse]

Here are the next steps (in this order), as I see them:

1. add docstrings and doctests to make sage -tox -- src/sage/rings/burnside.py pass
2. create a class MolecularDecompositionPolynomialSymmetricGroupAction (for lack of a better name), which is the graded algebra $\bigoplus_{n\geq 0} B(\mathfrak S_n)$, where $B$ denotes the Burnside ring, and the multiplication is the Cauchy product.
3. optimize the Burnside ring, most likely by using the functionality in https://docs.gap-system.org/doc/ref/chap41.html
4. define MolecularDecompositionSymmetricGroupAction (for lack of a better name) as the LazyCompletionGradedAlgebra(MolecularDecompositionPolynomialSymmetricGroupAction)

I'm not completely sure, but I think that MolecularDecompositionPolynomialSymmetricGroupAction will again inherit from CombinatorialFreeModule. The basis might be the set of pairs (n, H) such that H is a subgroup of $\mathfrak S_n$ - I think it is safer to remember n.

I am hesitant to call MolecularDecompositionPolynomialSymmetricGroupAction just PolynomialSpecies, although maybe we should do just that. The reason for my doubt is that we can do very many things without knowing the decomposition of a group action, that is, its representation in the Burnside ring. For example:

sage: Ep = species.SetSpecies(min=1)
sage: C = species.CycleSpecies()
sage: P = Ep(C)
sage: P.isotype_generating_series()
z + 2*z^2 + 3*z^3 + 5*z^4 + 7*z^5 + 11*z^6 + 15*z^7 + O(z^8)

should not create any conjugacy classes of subgroups - this would take forever.

[Newtech66]

I just realised that you can remove BurnsideRing._element_constructor_ completely, and instead implement ConjugacyClassesOfSubgroups.__contains__ (which we should provide anyway):

    def __contains__(self, H):
        return H.is_subgroup(self._G)

How is that working under the hood?

[mantepse]

I just realised that you can remove BurnsideRing._element_constructor_ completely, and instead implement ConjugacyClassesOfSubgroups.__contains__ (which we should provide anyway):

    def __contains__(self, H):
        return H.is_subgroup(self._G)

How is that working under the hood?

Not sure what exactly you mean here.

1. __contains__ is python magic https://docs.python.org/3/reference/datamodel.html#object.contains
2. CombinatorialFreeModule._element_constructor_ uses __contains__ here: https://github.com/sagemath/sage/blob/ffbbea9cb2360340f1c5517b590883fdaf02575c/src/sage/combinat/free_module.py#L763-L764

[Newtech66]

1. __contains__ is python magic https://docs.python.org/3/reference/datamodel.html#object.contains
2. CombinatorialFreeModule._element_constructor_ uses __contains__ here: https://github.com/sagemath/sage/blob/ffbbea9cb2360340f1c5517b590883fdaf02575c/src/sage/combinat/free_module.py#L763-L764

Ah, I see, that makes sense.

[Newtech66]

I propose we implement the conjugacy class renaming like B[Z3].rename_index("Z3"). We can make it fail if we try to call it on something that is not a basis element. Any alternative suggestions? Can the function be named better?

[mantepse]

I propose we implement the conjugacy class renaming like B[Z3].rename_index("Z3"). We can make it fail if we try to call it on something that is not a basis element. Any alternative suggestions? Can the function be named better?

Maybe, I don't know. I think we can delay thinking about this until we start to play with species.

[dimpase]

Does this use tables of marks? (With which it's much easier). GAP does have functionality to deal with tables of marks, and has a large library of them, packaged as tomlib package. (tomlib is a part of Sage)

[mantepse]

Does this use tables of marks? (With which it's much easier). GAP does have functionality to deal with tables of marks, and has a large library of them, packaged as tomlib package. (tomlib is a part of Sage)

Not yet, but eventually we will use it whenever available. However, as you certainly know, the table of marks works is only available for relatively small groups, e.g. the symmetric groups up to $\mathfrak S_{13}$. I hope that some operations will be possible even for larger groups, although, of course, they will be very slow.

[Newtech66]

Why are we adding SymmetricGroupAction in the name? The molecular decomposition of $F[n]$ is defined wrt $\mathfrak{S}_n$, so why the additional qualifier?

[mantepse]

Why are we adding SymmetricGroupAction in the name? The molecular decomposition of $F[n]$ is defined wrt $\mathfrak S_n$, so why the additional qualifier?

You are right, PolynomialMolecularDecomposition would be better. I admit, I don't care much about the name for the moment, and I didn't think much about it.

For me, the only question is whether we need this class at all, and I think that we do.

[Newtech66]

If we use the GradedAlgebrasWithBasis category then completion/formal_series_ring should be provided automatically.

[mantepse]

If we use the GradedAlgebrasWithBasis category then completion/formal_series_ring should be provided automatically.

Yes, that's correct, and that's the whole point of having a class PolynomialMolecularDecomposition (or whatever name we use). Is it clear to you how to implement it? It will inherit again from CombinatorialFreeModule, the only part which might involve work is to get the basis_keys right. Possibly you have to define a class for these, i.e., ConjugacyClassesOfSymmetricGroupSubgroups - which is in InfiniteEnumeratedSets.

[Newtech66]

(THIS IS NOW OUTDATED)

The naming facility has been reworked. The class SubgroupNameStore maintains the subgroup <-> name associations and provides functions to get, set, and unset names. BurnsideRing and PolynomialMolecularDecomposition now inherit from SubgroupNameStore (is this a good idea? We can alternatively create an instance of it in init).

The name printing is done in _repr_ of ConjugacyClassOfSubgroups. A default_name method is added for returning the default string if no name exists. The _namegetter attribute provides the interface between BurnsideRing/PolynomialMolecularDecomposition and their basis_keys. It is set to None by default, but if the relevant classes are created within one of the above, they are set to get_name in SubgroupNameStore. This lets _repr_ work correctly even if the ConjugacyClassesOfSubgroups(_SymmetricGroup)(_all) classes are created as standalone objects (but we cannot rename anything).

---

I'm worried the control flow is a bit confusing, even though it works.

[Newtech66]

Naming facility:

The class SubgroupStore provides caching and renaming facilities. The classes ConjugacyClassesOfSubgroups(_SymmetricGroup_all) inherit from it. Then we set _print_options['names'] = self._indices._names in BurnsideRing and PolynomialMolecularDecomposition to link changes in SubgroupStore to CombinatorialFreeModule's printing system. This means the syntax for naming goes like self._indices.set_name/get_name/... which might be somewhat unintuitive.

One side effect of this change is that if the unit of the ring is renamed to "1", it will print like a number. For example, if BurnsideRing's unit is renamed to "1", it prints as 1 and not B[1]. Similarly for PolynomialMolecularDecomposition.

[Newtech66]

One doctest _test_graded_components is still failing because the numbers chosen for the degree of the symmetric group are chosen to be [0, 1, 3, 42]. 42 is too large and GAP fails to generate the conjugacy classes of subgroups with the error: GAPError: Error, Range: <last> must be a small integer (not a large positive integer). Perhaps it will be fixed by #38300?

[mantepse]

One doctest _test_graded_components is still failing because the numbers chosen for the degree of the symmetric group are chosen to be [0, 1, 3, 42]. 42 is too large and GAP fails to generate the conjugacy classes of subgroups with the error: GAPError: Error, Range: <last> must be a small integer (not a large positive integer). Perhaps it will be fixed by #38300?

You can do TestSuite(XXX).run(skip="_test_graded_components") for now.

[mantepse]

I would suggest to make this pull request depend on #38371, and store instances of ConjugacyClassOfSubgroups_SymmetricGroup always in factored form.

I'm not sure whether this makes sense for Burnside rings of other groups than the symmetric group.

It's also important to me to prepare for conjugacy classes of subgroups of direct products of symmetric groups, corresponding to multivariate (in the book: "multisort") species. As I detailed in some email, it was wrong of me to believe that we could get multivariate species as tensor products of univariate species.

I hope that this will not be difficult, although some thought should go into the design. One thing I did not figure out yet: conjugacy classes of subgroups of $S_m \times S_n$ are essentially the same as the conjugacy classes of $S_n \times S_m$. Can - and should - the code take advantage of that?

[dimpase]

it's not realistic to compute the conjugacy classes of subgroups of $S_{42}$, these are way too many

[Newtech66]

This PR might be becoming too large, I think we should keep the scope of this PR to BurnsideRing and PolynomialMolecularDecomposition as it is right now and build it further in another PR.

[mantepse]

This PR might be becoming too large, I think we should keep the scope of this PR to BurnsideRing and PolynomialMolecularDecomposition as it is right now and build it further in another PR.

Sorry, I probably miscommunicated. I am not suggesting to add the multivariate part now (although this certainly should be added within the gsoc project). All I'm saying is that this should be kept in mind, so we don't take design decisions we regret later.

Storing the (conjugacy classes of) subgroups in factored form should not add much code. In fact, it should remove some, because multiplication becomes trivial.

Does this make more sense?

[Newtech66]

Why do we want to do the factorisation within ConjugacyClassOfSubgroups? I was thinking I could make a separate element class for PolynomialMolecularDecomposition named AtomicDecomposition that would handle the factorisations. We could handle printing and lazily computing factorisations better that way by separating responsibilities.

[mantepse]

Why do we want to do the factorisation within ConjugacyClassOfSubgroups? I was thinking I could make a separate element class for PolynomialMolecularDecomposition named AtomicDecomposition that would handle the factorisations. We could handle printing and lazily computing factorisations better that way by separating responsibilities.

OK, I'm not sure. I would have thought that it makes sense because the factorisation is very fast, and it is also easy to obtain the product from the factored object. I thought it would be easier to only provide the factored objects, but of course, I may be mistaken.

I think I have mentioned before that, from a combinatorialists point of view, one will probably mostly want to use custom names for atomic species. These are well-established, like $\mathcal E_n$ for the trivial action (perhaps with the exception of $\mathcal E_1 = X$), then $\mathcal C_n$ for the cyclic action, etc. Does this fit well into your design? Explicitly, it would be great to be able to do something like the following:

sage: for n in range(2, 100):
....:    AtomicConjugacyClass(PermutationGroup([], domain=list(range(1, n+1)))).rename("E_%s" % n)

and then get, automatically, output like

sage: PolynomialMolecularDecomposition().construct_from_action(a, X)
E_2 * E_4

(modulo many typos and omissions on my part)

[mantepse]

To make it completely clear: I think it would be really good if the design would allow us to use the standard renaming facility of sage. To make this work I think it would be sufficient to have a class ConjugacyClassOfConnectedSubgroups, such that a ConjugacyClassOfSubgroups is (essentially) a Factorization object of these.

If I made no mistake, connected makes sense for subgroups of arbitrary permutation groups. In particular, for the multisort species, the atomic species are precisely the connected subgroups of $\mathfrak S_n$ which are subgroups of $\mathfrak S_{n_1}\times\dots\times\mathfrak S_{n_d}$.

[Newtech66]

It's taking me a while to go through everything, but we can do something like this:

We have the set of atomic species. We could directly say we have the commutative ring on this set for characterising all species.

We can also take a more explicit approach. We can define the free commutative monoid on this set as the molecular species. Then finally the free module on that is the decomposition of any species.