ACDRepo/schubert_polynomial_structure_constants_5

A Combinatorial Interpretation of Schubert Polynomial Structure Constants

Schubert polynomials [1,2,3] are a family of polynomials indexed by permutations of \\(S_n\\). Developed to study the cohomology ring of the flag variety, they have deep connections to algebraic geometry, Lie theory, and representation theory. Despite their geometric origins, Schubert polynomials can be described combinatorially [4,5], making them a well-studied object in algebraic combinatorics. An important open problem in the study of Schubert polynomials is understanding their structure constants.

When two Schubert polynomials \\(\mathfrak{S}{\alpha}\\) and \\(\mathfrak{S}{\beta}\\) (indexed by permutations \\(\alpha \in Sn\\) and \\(\beta \in Sm\\)) are multiplied, their product can be written as a linear combination of Schubert polynomials \\(\mathfrak{S}{\alpha} \mathfrak{S}{\beta} = \sum{\gamma} c^{\gamma}{\alpha \beta} \mathfrak{S}{\gamma}\\). where the sum runs over permutations in \\(S{n+m}\\). The question is whether the \\(c^{\gamma}{\alpha \beta}\\) (the *structure constants*) have a combinatorial interpretation. To give an example of what we mean by combinatorial interpretation, when Schur polynomials (which are a subset of Schubert polynomials) are multiplied together, the coefficients in the resulting product are equal to the number of semistandard tableaux satisfying certain properties (this is known as the [Littlewood-Richardson rule](https://en.wikipedia.org/wiki/Littlewood%E2%80%93Richardsonrule)).

Example

We multiply Schubert polynomials corresponding to permutations of \\(\{1,2,3\}\\), \\(\alpha = 2 1 3\\) and \\(\beta = 1 3 2\\), each written in one line notation. Writing these in terms of indeterminants \\(x1\\), \\(x2\\), and \\(x3\\), we have \\(\mathfrak{S}{\alpha} = x1 + x2\\) and \\(\mathfrak{S}{\beta} = x1\\). Multiplying these together we get \\(\mathfrak{S}{\alpha}\mathfrak{S}{\beta} = x1^2 + x1x2\\). As \\(\mathfrak{S}{2 3 1} = x1x2\\) and \\(\mathfrak{S}{3 1 2} = x1^2\\) we can write \\(\mathfrak{S}{\alpha}\mathfrak{S}{\beta} = \mathfrak{S}{2 3 1} + \mathfrak{S}{3 1 2}\\). It follows that for these \\(\alpha\\) and \\(\beta\\), \\(c{\alpha,\beta}^{\gamma} = 1\\) if \\(\gamma = 2 3 1\\) or \\(\gamma = 3 1 2\\) and otherwise \\(c{\alpha,\beta}^{\gamma} = 0\\).

Dataset

Each instance in this dataset is a triple of permutations \\((\alpha,\beta,\gamma)\\), labeled by its coefficient \\(c^{\gamma}{\alpha \beta}\\) in the expansion of the product \\(\mathfrak{S}{\alpha} \mathfrak{S}_{\beta}\\). We call permutations \\(\alpha\\) and \\(\beta\\) lower index permutations 1 and 2 respectively. We call \\(\gamma\\) the upper index permutation. The datasets are organized so that \\(\alpha\\) and \\(\beta\\) are always drawn from the symmetric group on \\(n\\) elements, but \\(\gamma\\) may belong to a strictly larger symmetric group. Not all possible triples of permutations are included since the vast majority of these would be zero. The dataset consists of an approximately equal number of zero and nonzero coefficients (but they are not balanced between quantities of non-zero coefficients).

Statistics

All structure constants in this case are either 0, 1, or 2.

Data generation

The Sage notebook within this directory gives the code used to generate these datasets. The process involves:

• —For a chosen \\(n\\), compute the products \\(\mathfrak{S}{\alpha} \mathfrak{S}{\beta}\\) for \\(\alpha,\beta \in S_n\\).
• —For each of these pairs, extract and add to the dataset all non-zero structure constants \\(c^{\gamma1}{\alpha,\beta}, \dots, c^{\gammak}{\alpha,\beta}\\).
• —Furthermore, for each \\(c^{\gammai}{\alpha,\beta} \neq 0\\), randomly permute \\(\gammai \mapsto \gammai'\\) to find \\(c^{\gammai'}{\alpha,\beta} = 0\\) and \\(c^{\gammai'}{\alpha,\beta}\\) is not already in the dataset.

Task

Math question: Find a combinatorial interpretation of the structure constants \\(c{\alpha,\beta}^\gamma\\) based on properties of \\(\alpha\\), \\(\beta\\), and \\(\gamma\\). **Narrow ML task:** Train a model that, given three permutations \\(\alpha, \beta, \gamma\\), can predict the associated structure constant \\(c^{\gamma}{\alpha,\beta}\\). Extract the rules the model uses to make successful predictions.

Small model performance

Model and training details can be found in our 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

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\] Bernstein, IMGI N., Israel M. Gel'fand, and Sergei I. Gel'fand. "Schubert cells and cohomology of the spaces G/P." Russian Mathematical Surveys 28.3 (1973): 1. \[2\] Demazure, Michel. "Désingularisation des variétés de Schubert généralisées." Annales scientifiques de l'École Normale Supérieure. Vol. 7. No. 1. 1974. \[3\] Lascoux, Alain, and Marcel-Paul Schützenberger. "Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux." CR Acad. Sci. Paris Sér. I Math 295.11 (1982): 629-633. \[4\] Billey, Sara C., William Jockusch, and Richard P. Stanley. "Some combinatorial properties of Schubert polynomials." Journal of Algebraic Combinatorics 2.4 (1993): 345-374. \[5\] Bergeron, Nantel, and Sara Billey. "RC-graphs and Schubert polynomials." Experimental Mathematics 2.4 (1993): 257-269.