Burnside ring of permutation representations

[trevorkarn]

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

Problem Description

The Burnside ring of a group encodes the permutation representations of the group. This could be implemented as a parent in Sage.

Proposed Solution

Implement a parent class for the Burnside ring of a finite group using GAP under the hood. This should also include a method which attempts to express a given representation in the Burnside ring by first checking that all the character values are positive (a necessary but not sufficient condition for a representation to be a permutation representation) and then attempting to express it as an element of the Burnside ring.

Alternatives Considered

One could work with symmetric functions directly or by hand/in an ad hoc manner, but implementing a parent class for the Burnside ring of a group is the way that makes sense in Sage.

Additional Information

No response

[mantepse]

Please communicate with @newtech66, who would possibly work on this and similar projects in the framework of google summer of code. See also #30727. You can find brute force code to find the marks of a group action in https://github.com/sagemath/sage/issues/30727#issuecomment-1492960119.

One remark: working with symmetric functions is not sufficient, because there may be several different group actions having the same character (but different marks).

[trevorkarn]

Oh great! Sorry I missed that. I'll leave it to @Newtech66 if they are accepted as a GSOC contributor. But I'd like to stay involved through the review process to the extent possible.

[Newtech66]

Hi! Could you please elaborate on the connection with symmetric functions? Also, please tell me how I could contact you if I want to discuss this topic further. @trevorkarn

[mantepse]

It would be wonderful if you could collaborate on this. It is probably not all that hard to make a simple version of the ring, but the better the better!

The link to symmetric functions is as follows (@Newtech66, I will elaborate on this in one of the next lectures, in case you can attend): a group action of $G$ on a finite set $X$ is a homomorphism $a: G\to \mathfrak S_X$ into the symmetric group on the set $X$. A group representation of $G$ is a homomorphism $\rho: G\to GL(\mathbb C X)$ into the group of invertible linear transformations of the complex vector space with basis $X$.

Thus, we can turn any group action into a representation, by setting $\rho(g)$ to be the permutation matrix encoding the permutation $a(g)$.

The character of a representation $\rho$ is the function $\chi: G\to\mathbb C$, $g\mapsto trace(\rho(g))$. Note that characters are constant on conjugacy classes of $G$, and that the sum of two characters corresponds to the direct sum of two representations. Finally note that the character of a representation that comes from a group action gives just the number of fixed points of $g$.

One can show that representations are isomorphic if and only if they have the same character. However, the character does not determine the group action (the only exception being the cyclic groups). This may not be so surprising, because we lost some information when passing from the group action to the representation.

Let us now fix $G=\mathfrak S_n$. In this case we have precisely one irreducible representations for each partition $\lambda$ of $n$. A fundamental result, Schur-Weyl duality, (essentially) tells us that therefore the irreducible representations of $GL_n(\mathbb C)$ are also encoded by these partitions. Finally, the characters of the irreducible representations of $GL_n$ can be seen (by the Weyl character formula) to be certain symmetric functions in the eigenvalues of the matrix, called Schur functions.

By Schur-Weyl duality, we can therefore use symmetric functions to play with representations of the symmetric group. However, when playing with group actions we need more information. The table of marks is the group action analogue of the character table, and the Burnside ring is the group action analogue of the character ring.

[trevorkarn]

Just to add one more thing which was my motivation for opening the issue, if a symmetric function corresponding to a representation is positive in the homogeneous basis, it is a sum of permutation representations, but the "h-positivity" is not a necessary condition for something to be a permutation representation. It would be nice to take a symmetric function and attempt to express it as a sum of permutation representations, that is, as an element of the Burnside ring. There is no guarantee one can do this for an arbitrary permutation representation, but for instance a mixed integer linear program can approximate the solution to see if it exists.

[mantepse]

For representations of the cyclic group there is an efficient characterisation due to Per Alexandersson and Nima Amini. I wondered for quite some time whether one can do something similar for the symmetric group.

However, it seems to me that this functionality (while it might use the Burnside ring) should rather be provided by the representation ring of a group. Oops, apparently sage doesn't have this ring either!

[trevorkarn]

For representations of the cyclic group there is an efficient characterisation due to Per Alexandersson and Nima Amini. I wondered for quite some time whether one can do something similar for the symmetric group.

Oh very cool, thanks for pointing that out.

However, it seems to me that this functionality (while it might use the Burnside ring) should rather be provided by the representation ring of a group. Oops, apparently sage doesn't have this ring either!

Seems like another potential GSOC contribution?

[mantepse]

However, it seems to me that this functionality (while it might use the Burnside ring) should rather be provided by the representation ring of a group. Oops, apparently sage doesn't have this ring either!

Seems like another potential GSOC contribution?

Well, if you had reserved time for implementing the Burnside ring, maybe you could slightly reallocate it?

[trevorkarn]

That works too.

[mantepse]

@trevorkarn, maybe - if you have time - could you collect (ideally in an initial commit) the methods BurnsideRing and CharacterRing you'd hope for? Can we somehow make them optionally Semirings? I'm not sure whether we gain anything with that, however.

It would also be good to make sure the user interface for these two and the user interface for WeylCharacterRing and SymmetricGroupRepresentations (which is only the set of irreducibles, however), and PermutationGroup do not diverge unnecessarily.

[mantepse]

See also #35500.