ACDRepo/symmetric_group_characters_22

Characters of Irreducible Representations of the Symmetric Group, \\(S_{22}\\)

One way to understand the algebraic structure of the set of permutations of \\(n\\) elements (the symmetric group, \\(S_n\\)) is through its representation theory \[1\], which converts algebraic questions into linear algebra questions that are often easier to solve. A representation of group \\(G\\) on vector space \\(V\\), is a map \\(\phi:G \rightarrow GL(V)\\) that converts elements of \\(g\\) to invertible matrices on vector space \\(V\\) which respect the compositional structure of the group. A basic result in representation theory says that all representations of a finite group can be decomposed into atomic building blocks called irreducible representations. Amazingly, irreducible representations are themselves uniquely determined by the value of the trace, \\(\text{Tr}(\phi(g))\\), where \\(g\\) ranges over subsets of \\(G\\) called conjugacy classes. These values are called characters.

The representation theory of symmetric groups has rich combinatorial interpretations. Both irreducible representations of \\(Sn\\) and the conjugacy classes of \\(Sn\\) are indexed by partitions of \\(n\\) and thus the characters of irreducible representations of \\(Sn\\) are indexed by pairs of partitions of \\(n\\). For \\(\lambda,\mu \vdash n\\) we write \\(\chi^\lambda\mu\\) for the associated character. This combinatorial connection is not superficial, some of the most famous algorithms for computation of irreducible characters (e.g., the Murnaghan-Nakayama rule) are completely combinatorial in nature.

Dataset Details

Each instance of the dataset consists of two integer partitions of \\(22\\) (one corresponding to the irreducible representation and one corresponding to the conjugacy class) and the corresponding character (which is always an integer). For a small \\(n = 5\\) example, if the first partition is [3,1,1], the second partition is [2,2,1], and the character is -2, then this says that the character \\(\chi^{3,1,1}_{2,2,1} = −2\\).

In all cases the characters are heavily concentrated around 0 with very long tails. This likely contributes to the difficulty of the task and could be overcome with some simple pre- and post-processing. We have not chosen to do this in our baselines.

Characters of \\(S_{22}\\) | | Number of instances | |----------|----------| | Train | 763,109 | | Test | 190,726 |

Maximum character value 5,462,865,408, minimum character value −279,734,796.

Math question (solved): The Murnaghan–Nakayama rule is one example of an algorithm for calculating the character of an irreducible representation of the symmetric group using only elementary operations on the corresponding pair of partitions.

ML task: Train a model that can take two partitions of 22, \\(\lambda\\) and \\(\mu\\), and predict the corresponding character \\(\chi^{\lambda}_{\mu}\\). Identify the decision process that a performant model is running. Is this a known algorithm or a new algorithm?

Small model performance

We provide some basic baselines for this task framed as regression. Benchmarking details can be found in the associated paper.

The \\(\pm\\) signs indicate 95% confidence intervals from random weight initialization and training.

Further information

• —Curated by: Henry Kvinge
• —Funded by: Pacific Northwest National Laboratory
• —Language(s) (NLP): NA
• —License: CC-by-2.0

Dataset Sources

The dataset was generated using SageMath. Data generation scripts can be found here.

• —Repository: ACD Repo

Citation

BibTeX:

@article{chau2025machine, title={Machine learning meets algebraic combinatorics: A suite of datasets capturing research-level conjecturing ability in pure mathematics}, author={Chau, Herman and Jenne, Helen and Brown, Davis and He, Jesse and Raugas, Mark and Billey, Sara and Kvinge, Henry}, journal={arXiv preprint arXiv:2503.06366}, year={2025} }

APA:

Chau, H., Jenne, H., Brown, D., He, J., Raugas, M., Billey, S., & Kvinge, H. (2025). Machine learning meets algebraic combinatorics: A suite of datasets capturing research-level conjecturing ability in pure mathematics. arXiv preprint arXiv:2503.06366.

Dataset Card Contact

Henry Kvinge, acdbenchdataset@gmail.com

References

\[1\] Sagan, Bruce E. The symmetric group: representations, combinatorial algorithms, and symmetric functions. Vol. 203. Springer Science & Business Media, 2013.