ACDRepo/coefficients_of_kl_polynomials_6
The Coefficients of Kazhdan-Lusztig Polynomials for Permutations of Size 6 Kazhdan-Lusztig (KL) polynomials are polynomials in a variable qqq and with integer coefficients that (for our purposes) are indexed by a pair of permutations [1]. We will write the KL polynomial associated with permutations σ\sigmaσ and ν\nuν as Pσ,ν(q)P_{\sigma,\nu}(q)Pσ,ν(q). For example, the KL polynomial associated with permutations σ=1 4 3 2 7 6 5 10 9 8 11\sigma = 1 \; 4 \; 3 \; 2 \;… See the full description on the dataset page: https://huggingface.co/datasets/ACDRepo/coefficients_of_kl_polynomials_6.
The Coefficients of Kazhdan-Lusztig Polynomials for Permutations of Size 6
Kazhdan-Lusztig (KL) polynomials are polynomials in a variable \\(q\\) and with integer coefficients that (for our purposes) are indexed by a pair of permutations [1]. We will write the KL polynomial associated with permutations \\(\sigma\\) and \\(\nu\\) as \\(P_{\sigma,\nu}(q)\\). For example, the KL polynomial associated with permutations \\(\sigma = 1 \; 4 \; 3 \; 2 \; 7 \; 6 \; 5 \; 10 \; 9 \; 8 \; 11\\) and \\(\nu = 4 \; 6 \; 7 \; 8 \; 9 \; 10 \; 1 \; 11 \; 2 \; 3 \; 5\\) is
\\(P_{\sigma,\nu}(q) = 1 + 16q + 103q^2 + 337q^3 + 566q^4 + 529q^5 + 275q^6 + 66q^7 + 3q^8\\)
(see here for efficient software to compute these polynomials). KL polynomials have deep connections throughout several areas of mathematics. For example, KL polynomials are related to the dimensions of intersection homology in Schubert calculus, the study of the Hecke algebra, and representation theory of the symmetric group. They can be computed via a recursive formula [[1]](https://link.springer.com/article/10.1007/BF01390031), nevertheless, in many ways they remain mysterious. For instance, there is no known closed formula for the degree of \\(P_{\sigma,\nu}(q)\\).
One family of questions revolve around the coefficients of \\(P_{\sigma,\nu}(q)\\). For instance, it has been hypothesized that the coefficient on the largest possible monomial term \\(q^{(\ell(\sigma) - \ell(\nu)-1)/2}\\) (where \\(\ell(x)\\) is a statistic of the permutation \\(x\\) called the length of the permutation), which is known as the \\(\mu\\)-coefficient, has a combinatorial interpretation but currently this is not known. Better understanding this and other coefficients is of significant interest to mathematicians from a range of fields.
Dataset details
Each instance in this dataset consists of a pair of permutations of \\(n,x \in Sn\\) along with the coefficients of the polynomial \\(P{x,w}(q)\\). If \\(x = \;1 \;2 \;3\; 4\; 5\; 6\\), \\(w=4 \;5\; 6\; 1 \;2 \;3\\) and \\(P_{v,w}(q) = 1 + 4q + 4q^2 + q^3\\) then the coefficients field is written as 1, 4, 4, 1. Note that coefficients are listed by increasing degree of the power of \\(q\\) (e.g., the coefficient on \\(1\\) comes first, then the coefficient on \\(q\\), then the coefficient on \\(q^2\\), etc.)
We summarize the limited number of values coefficients on \\(P{x,w}(q)\\) take when \\(x, w \in S6\\).
Constant Terms:
Coefficients on \\(q\\):
Coefficient on \\(q^2\\):
Coefficient on \\(q^3\\):
Data Generation
Datasets were generated using C code from Greg Warrington's website. The code we used can be found here.
Task
Math question: Generate conjectures around the properties of coefficients appearing on KL polynomials.
Narrow ML task: Predict the coefficients of \\(P_{x,w}(q)\\) given \\(x\\) and \\(w\\). We break this up into a separate task for each coefficient though one could choose to predict all simultaneously. Since there are generally very few different integers that arise as coefficients (at least in these small examples), we frame this problem as one of classification.
While the classification task as framed does not capture the broader math question exactly, illuminating connections between \\(x\\), \\(w\\), and the coefficients of \\(P_{x,w}(q)\\) has the potential to yield critical insights.
Small model performance
Since there are many possible tasks here, we did not run exhaustive hyperparameter searches. Instead, we ran ReLU MLPs with depth 4, width 256, and learning rate 0.0005.
Accuracy predicting coefficients for permutations of 6 elements:
The associated macro F1-scores are:
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
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\] Kazhdan, David, and George Lusztig. "Representations of Coxeter groups and Hecke algebras." Inventiones mathematicae 53.2 (1979): 165-184. [2] Warrington, Gregory S. "Equivalence classes for the μ-coefficient of Kazhdan–Lusztig polynomials in Sn." Experimental Mathematics 20.4 (2011): 457-466.