ACDRepo/coefficients_of_kl_polynomials_7

1---2license: cc-by-2.03pretty_name: Coefficients on Kazhdan–Lusztig polynomials for permutations of size 74---5 6# The Coefficients of Kazhdan-Lusztig Polynomials for Permutations of Size 77 8Kazhdan-Lusztig (KL) polynomials are polynomials in a variable \\(q\\) and 9with integer coefficients that (for our purposes) are indexed by a pair of permutations [1]. 10We will write the KL polynomial associated with permutations \\(\sigma\\) and \\(\nu\\) as 11\\(P_{\sigma,\nu}(q)\\). For example, the KL polynomial associated with permutations 12\\(\sigma = 1 \; 4 \; 3 \; 2 \; 7 \; 6 \; 5 \; 10 \; 9 \; 8 \; 11\\) and 13\\(\nu = 4 \; 6 \; 7 \; 8 \; 9 \; 10 \; 1 \; 11 \; 2 \; 3 \; 5\\) is  14 15 16\\(P_{\sigma,\nu}(q) = 1 + 16q + 103q^2 + 337q^3 + 566q^4 + 529q^5 + 275q^6 + 66q^7 + 3q^8\\)  17 18(see [here](https://gswarrin.w3.uvm.edu/research/klc/klc.html) for efficient software to compute19these polynomials). KL polynomials have deep connections throughout several areas of mathematics. For example, 20KL polynomials are related to the dimensions of intersection homology in Schubert calculus, 21the study of the Hecke algebra, and representation theory of the symmetric group. They 22can be computed via a recursive formula [[1]](https://link.springer.com/article/10.1007/BF01390031), 23nevertheless, in many ways they remain mysterious. For instance, there is no known closed 24formula for the degree of \\(P_{\sigma,\nu}(q)\\).25 26One family of questions revolve around the coefficients of \\(P_{\sigma,\nu}(q)\\). 27For instance, it has been hypothesized that the coefficient on the largest possible monomial term 28\\(q^{(\ell(\sigma) - \ell(\nu)-1)/2}\\) (where \\(\ell(x)\\) is a statistic of the 29permutation \\(x\\) called the *length* of the permutation), which is known as the 30\\(\mu\\)-coefficient, has a combinatorial interpretation but currently this is not 31known. Better understanding this and other coefficients is of significant 32interest to mathematicians from a range of fields.33 34## Dataset details35 36Each instance in this dataset consists of a pair of permutations of \\(n,x \in S_n\\) 37along with the coefficients of the polynomial \\(P_{x,w}(q)\\). If \\(x = \;1 \;2 \;3\; 4\; 5\; 6\\),38\\(w=4 \;5\; 6\; 1 \;2 \;3\\) and \\(P_{v,w}(q) = 1 + 4q + 4q^2 + q^3\\) 39then the coefficients field is written as `1, 4, 4, 1`. Note that coefficients are listed 40by increasing degree of the power of \\(q\\) (e.g., the coefficient on \\(1\\) comes first, 41then the coefficient on \\(q\\), then the coefficient on \\(q^2\\), etc.)42 43We summarize the limited number of values coefficients on \\(P_{x,w}(q)\\) take when \\(x, w \in S_7\\). 44 45**Constant Terms:**46 47|  | 0 | 1 | Total number of instances | 48|----------|----------|----------|----------|49| Train | 17,479,910 | 2,841,370 | 20,321,280 |50| Test  | 4,370,771 | 709,549 | 5,080,320 |51 52**Coefficients on \\(q\\):**53 54|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | Total number of instances | 55|----------|----------|----------|----------|----------|----------|----------|----------|----------|56| Train | 19,291,150 | 660,600 | 266,591 | 80,173 | 18,834 | 3,221 | 711 | 20,321,280 |57| Test  | 4,822,214 | 165,768 | 66,593 | 19,963 | 4,762 | 819 | 201 | 5,080,320 |58 59**Coefficient on \\(q^2\\):**60 61|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | Total number of instances | 62|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|63| Train | 20,072,738 | 170,412 | 46,226 | 16,227 | 7,621 | 4,023 | 1,287 | 1,153 | 785 | 350 | 152 | 139 | 121 | 42 | 4 | 20,321,280 |64| Test  | 5,017,962 | 42,748 | 11,568 | 4,021 | 1,905 | 1,065 | 349 | 287 | 183 | 86 | 40 | 37 | 47 | 22 | 5,080,320 |65 66**Coefficient on \\(q^3\\):**67 68|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 15 | Total number of instances | 69|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|70| Train | 20,291,535 | 22,094 | 4,779 | 1,660 | 590 | 195 | 206 | 115 | 34 | 26 | 24 | 18 | 4 | 20,321,280 |71| Test  | 507,2831 | 5,498 | 1,213 | 442 | 146 | 61 | 50 | 37 | 14 | 6 | 8 | 14 | 5,080,320 |72 73**Coefficient on \\(q^4\\):**74 75|  | 0 | 1 | Total number of instances | 76|----------|----------|----------|----------|77| Train | 17,479,910 | 2,841,370 | 20,321,280 |78| Test  | 4,370,771 | 709,549 | 5,080,320 |79 80 81## Data Generation82 83Datasets were generated using C code from Greg Warrington's 84[website](https://gswarrin.w3.uvm.edu/research/klc/klc.html). The code we used can be found 85[here](https://github.com/pnnl/ML4AlgComb/tree/master/kl-polynomial_coefficients).86 87## Task 88 89**Math question:** Generate conjectures around the properties of coefficients appearing on KL polynomials.90 91**Narrow ML task:** Predict the coefficients of \\(P_{x,w}(q)\\) given \\(x\\) and \\(w\\). 92We break this up into a separate task for each coefficient though one could 93choose to predict all simultaneously. Since there are generally very few 94different integers that arise as coefficients (at least in these small examples), 95we frame this problem as one of classification. 96 97While the classification task as framed does not capture the broader math question exactly, 98illuminating connections between \\(x\\), \\(w\\), and the coefficients of \\(P_{x,w}(q)\\)99has the potential to yield critical insights.100 101## Further information102 103- **Curated by:** Henry Kvinge104- **Funded by:** Pacific Northwest National Laboratory105- **Language(s) (NLP):** NA106- **License:** CC-by-2.0107  108## Citation109 110**BibTeX:**111 112 113    @article{chau2025machine,114        title={Machine learning meets algebraic combinatorics: A suite of datasets capturing research-level conjecturing ability in pure mathematics},115        author={Chau, Herman and Jenne, Helen and Brown, Davis and He, Jesse and Raugas, Mark and Billey, Sara and Kvinge, Henry},116        journal={arXiv preprint arXiv:2503.06366},117        year={2025}118    }119 120**APA:**121 122Chau, 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.123 124## Dataset Card Contact125 126Henry Kvinge, acdbenchdataset@gmail.com127 128## References129 130\[1\] Kazhdan, David, and George Lusztig. "Representations of Coxeter groups and Hecke algebras." Inventiones mathematicae 53.2 (1979): 165-184.  131[2] Warrington, Gregory S. "Equivalence classes for the μ-coefficient of Kazhdan–Lusztig polynomials in Sn." Experimental Mathematics 20.4 (2011): 457-466.