ACDRepo/schubert_polynomial_structure_constants_5

1---2license: cc-by-2.03pretty_name: structure constants of schubert polynomials, n = 54---5 6# A Combinatorial Interpretation of Schubert Polynomial Structure Constants7 8Schubert polynomials [1,2,3] are a family of polynomials indexed by permutations of \\(S_n\\). 9Developed to study the cohomology ring of the flag variety, they have deep connections to 10algebraic geometry, Lie theory, and representation theory. Despite their geometric origins, 11Schubert polynomials can be described combinatorially [4,5], making them a well-studied object 12in algebraic combinatorics. An important open problem in the study of Schubert polynomials 13is understanding their *structure constants*. 14 15When two Schubert polynomials \\(\mathfrak{S}_{\alpha}\\) and \\(\mathfrak{S}_{\beta}\\) 16(indexed by permutations \\(\alpha \in S_n\\) and \\(\beta \in S_m\\)) are multiplied, 17their product can be written as a linear combination of Schubert polynomials18\\(\mathfrak{S}_{\alpha} \mathfrak{S}_{\beta} = \sum_{\gamma} c^{\gamma}_{\alpha \beta} \mathfrak{S}_{\gamma}\\). 19where the sum runs over permutations in \\(S_{n+m}\\). The question is whether the 20\\(c^{\gamma}_{\alpha \beta}\\) (the *structure constants*) have a combinatorial interpretation. 21To give an example of what we mean by combinatorial interpretation, when Schur polynomials 22(which are a subset of Schubert polynomials) are multiplied together, 23the coefficients in the resulting product are equal to the number of semistandard tableaux 24satisfying certain properties (this is known as the 25[Littlewood-Richardson rule](https://en.wikipedia.org/wiki/Littlewood%E2%80%93Richardson_rule)).26 27## Example28 29We multiply Schubert polynomials corresponding to permutations of \\(\{1,2,3\}\\), 30\\(\alpha = 2 1 3\\) and \\(\beta = 1 3 2\\), each written in one line notation. 31Writing these in terms of indeterminants 32\\(x_1\\), \\(x_2\\), and \\(x_3\\), we have \\(\mathfrak{S}_{\alpha} = x_1 + x_2\\) 33and \\(\mathfrak{S}_{\beta} = x_1\\). Multiplying these together we get34\\(\mathfrak{S}_{\alpha}\mathfrak{S}_{\beta} = x_1^2 + x_1x_2\\). As 35\\(\mathfrak{S}_{2 3 1} = x_1x_2\\) and \\(\mathfrak{S}_{3 1 2} = x_1^2\\) we can write 36\\(\mathfrak{S}_{\alpha}\mathfrak{S}_{\beta} = \mathfrak{S}_{2 3 1} + \mathfrak{S}_{3 1 2}\\). 37It follows that for these \\(\alpha\\) and \\(\beta\\), \\(c_{\alpha,\beta}^{\gamma} = 1\\) 38if \\(\gamma = 2 3 1\\) or \\(\gamma = 3 1 2\\) 39and otherwise \\(c_{\alpha,\beta}^{\gamma} = 0\\).40 41## Dataset 42Each instance in this dataset is a triple of permutations \\((\alpha,\beta,\gamma)\\), 43labeled by its coefficient \\(c^{\gamma}_{\alpha \beta}\\) in the expansion of the product 44\\(\mathfrak{S}_{\alpha} \mathfrak{S}_{\beta}\\). We call permutations \\(\alpha\\) and \\(\beta\\)45*lower index permutations 1* and *2* respectively. We call \\(\gamma\\) the *upper index 46permutation*. The datasets are organized so that 47\\(\alpha\\) and \\(\beta\\) are always drawn from the symmetric group on \\(n\\) elements, 48but \\(\gamma\\) may belong to a 49strictly larger symmetric group. Not all possible triples of permutations are included 50since the vast majority of these would be zero. The dataset consists of an approximately 51equal number of zero and nonzero coefficients (but they are not balanced between quantities 52of non-zero coefficients). 53 54**Statistics**55 56All structure constants in this case are either 0, 1, or 2. 57 58|Coefficient | 0 | 1 | 2 | Total number of instances |59|---|---|---|-----|---|60| Train |   42,810  |  42,603   |  175   | 85,588 |61| Test  |  10,696    | 10,661 | 39 | 21,396 |62 63## Data generation64The Sage notebook within this [directory](https://github.com/pnnl/ML4AlgComb/tree/master/schubert_polynomial_structure) 65gives the code used to generate these datasets. 66The process involves:67- For a chosen \\(n\\), compute the products \\(\mathfrak{S}_{\alpha} \mathfrak{S}_{\beta}\\) for \\(\alpha,\beta \in S_n\\).68- For each of these pairs, extract and add to the dataset all non-zero structure constants \\(c^{\gamma_1}_{\alpha,\beta}, \dots, c^{\gamma_k}_{\alpha,\beta}\\).69- Furthermore, for each \\(c^{\gamma_i}_{\alpha,\beta} \neq 0\\), randomly permute \\(\gamma_i \mapsto \gamma_i'\\) to find \\(c^{\gamma_i'}_{\alpha,\beta} = 0\\) and \\(c^{\gamma_i'}_{\alpha,\beta}\\) is not already in the dataset.70 71## Task 72 73**Math question:** Find a combinatorial interpretation of the structure constants \\(c_{\alpha,\beta}^\gamma\\)74based on properties of \\(\alpha\\), \\(\beta\\), and \\(\gamma\\).  75**Narrow ML task:** Train a model that, given three permutations \\(\alpha, \beta, \gamma\\), can 76predict the associated structure constant \\(c^{\gamma}_{\alpha,\beta}\\). Extract the rules 77the model uses to make successful predictions.78 79## Small model performance80Model and training details can be found in our paper.81 82| Size | Logistic regression | MLP | Transformer | Guessing majority class | 83|----------|----------|-----------|------------|------------|84| \\(n= 4\\) | \\(88.8\%\\) | \\(93.1\% \pm 2.6\%\\) | \\(94.6\% \pm 1.0\%\\) | \\(52.3\%\\) |85| \\(n= 5\\) | \\(90.6\%\\) | \\(97.5\% \pm 0.2\%\\) | \\(96.2\% \pm 1.1\%\\) | \\(49.9\%\\) |86| \\(n= 6\\) | \\(89.7\%\\) | \\(99.8\% \pm 0.0\%\\) | \\(91.3\% \pm 8.0\%\\) | \\(50.1\%\\) |87 88The \\(\pm\\) signs indicate 95% confidence intervals from random weight initialization and training.89 90## Further information91 92- **Curated by:** Henry Kvinge93- **Funded by:** Pacific Northwest National Laboratory94- **Language(s) (NLP):** NA95- **License:** CC-by-2.096 97### Dataset Sources98 99Data generation scripts can be found [here](https://github.com/pnnl/ML4AlgComb/tree/master/schubert_polynomial_structure).100 101- **Repository:** [ACD Repo](https://github.com/pnnl/ML4AlgComb/tree/master)102 103## Citation104 105**BibTeX:**106 107 108    @article{chau2025machine,109        title={Machine learning meets algebraic combinatorics: A suite of datasets capturing research-level conjecturing ability in pure mathematics},110        author={Chau, Herman and Jenne, Helen and Brown, Davis and He, Jesse and Raugas, Mark and Billey, Sara and Kvinge, Henry},111        journal={arXiv preprint arXiv:2503.06366},112        year={2025}113    }114 115 116**APA:**117 118Chau, 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.119 120## Dataset Card Contact121 122Henry Kvinge, acdbenchdataset@gmail.com123 124## References125 126\[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.  127\[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.  128\[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.  129\[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.  130\[5\] Bergeron, Nantel, and Sara Billey. "RC-graphs and Schubert polynomials." Experimental Mathematics 2.4 (1993): 257-269.