Combinatorial Invariance of Kazhdan–Lusztig Polynomials

Combinatorial Invariance of Kazhdan–Lusztig Polynomials

OpenAI's claim

Kazhdan--Lusztig invariance: The manuscript claims equality of equal-parameter Kazhdan--Lusztig polynomials whenever two Bruhat intervals are isomorphic as posets. The intervals may lie in unrelated Coxeter systems.

Mathematical statement of the claimed result

Mathematical claim 1.

For arbitrary Coxeter systems $(W,S)$ and $(W^\prime,S^\prime)$, choose $u\le b$ and $u^\prime\le b^\prime$ in their Bruhat orders. If the finite interval posets $[u,b]$ and $[u^\prime,b^\prime]$ are abstractly isomorphic, then the claimed equal-parameter Kazhdan--Lusztig equality is \[P^W_{u,b}(q)=P^{W^\prime}_{u^\prime,b^\prime}(q).\] Neither the ambient Coxeter type nor a preservation of edge labels by the poset isomorphism is required.

Outline of the argument

Kazhdan--Lusztig invariance: Moment-graph sheaves encode the polynomials as graded ranks of vertex modules. A reflection order from the second interval supplies a transported edge schedule on the first. Induction proves both polynomial equality and freeness of kernels for terminal edge sets; the local edge step makes the sheaf calculation independent of the original labels.

Formal verification

Family 168 describes Lean coverage for preservation of equal-parameter polynomials under Bruhat-poset isomorphisms across Coxeter systems.

Kazhdan--Lusztig invariance: The manuscript links KLInvariance.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

• OpenAI, Combinatorial invariance of Kazhdan–Lusztig polynomials, 2026-09-24; citation key OAI:Combinatorial-Invariance-of-Kazhdan-Lusztig-Polynomials-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• Family 168: Lean scope.
• Comparator KLInvariance.json.
• Comparator KLInvariance.lean.
• OpenAI catalogue entry.

Combinatorial Invariance of Kazhdan–Lusztig Polynomials

Definitions and mathematical statement

A Coxeter system $(W,S)$ has generators $s^2=1$ and relations $(st)^{m_{st}}=1$; let $\ell$ be word length and $T$ the set of conjugates of simple reflections. Bruhat order is the subword order on reduced expressions. On an interval $[u,v]$, use the directed Bruhat graph with edges $x\to y$ whenever $yx^{-1}\in T$ and $\ell(x)<\ell(y)$, not just length-one covers. The Kazhdan--Lusztig polynomials $P_{x,y}(q)$ are the standard triangular coefficients of the bar-invariant basis of the Coxeter Hecke algebra, normalized by $P_{x,x}=1$ and $\deg P_{x,y}\le(\ell(y)-\ell(x)-1)/2$ for $x<y$. The conjecture says a directed-graph isomorphism $[u,v]\cong[w,z]$, even across different Coxeter systems, forces $P_{u,v}=P_{w,z}$. Reflection labels on edges are not supplied to the graph isomorphism.

Formulation and concept references: [S1].

Short English statement

Does the unlabelled directed Bruhat graph of an interval determine its Kazhdan--Lusztig polynomial, independently of the surrounding Coxeter group?

Research attempt

GPT-6 Astra Ultra; 27 September 2026. Status: UNRESOLVED.

I extract all the data needed for intervals of length at most three from the unlabelled directed reflection graph. This gives an explicit formula in length three and a finite test of its normalization. The calculation also identifies the obstacle to continuing the same argument: the known general path formula uses a reflection ordering, information which the proposed graph isomorphism does not supply.

Rank is intrinsic to the directed graph.

Every directed edge strictly increases Coxeter length. A directed path from $u$ to $x$ therefore has at most $\ell(x)-\ell(u)$ edges. On the other hand a saturated Bruhat chain from $u$ to $x$ has exactly that many edges, all of which are reflection edges. It follows that \[ r(x)=\ell(x)-\ell(u) =\max\{\text{number of edges in a directed path from }u\text{ to }x\}. \tag{1} \] The unique source and sink identify the interval endpoints. Thus graph isomorphisms preserve rank, length difference, atoms, and coatoms. Cover edges are precisely the edges whose ranks differ by one. The converse reconstruction is not immediate: the reflection graph may also contain longer edges, which must be retained.

For rank zero, $P_{u,u}=1$. For ranks one and two the degree bound and the standard constant-term identity $P_{u,v}(0)=1$ give $P_{u,v}=1$. These standard elementary properties of the Hecke normalization are used throughout, together with the bar relation \[ q^dP_{u,v}(q^{-1})= \sum_{u\le x\le v} R_{u,x}(q)P_{x,v}(q), \qquad d=\ell(v)-\ell(u). \tag{2} \] Here $R_{x,x}=1$, rank-one $R$-polynomials equal $q-1$, and rank-two ones equal $(q-1)^2$. The general recursion determining these polynomials is recalled in [E1].

An explicit graph formula in rank three.

Assume $d=3$. Let $a$ be the number of atoms of the interval and let $\varepsilon$ equal one if there is a directed edge $u\to v$, and zero otherwise. I claim \[ P_{u,v}(q)=1+(a-3+\varepsilon)q. \tag{3} \] To prove it, use Dyer's increasing-path formula [E1] for normalized $R$-polynomials. In its convention \[ R_{u,v}(q)=q^{d/2}\widetilde R_{u,v} (q^{1/2}-q^{-1/2}). \tag{4} \] The coefficient of $t^j$ in $\widetilde R$ counts paths of $j$ reflection edges whose labels increase in a reflection order. Each reflection changes the parity of length. A path with total length difference three therefore has either one or three edges. The one-edge path exists exactly when $\varepsilon=1$, and its label is automatically increasing. The leading coefficient of the monic degree-three $R$-polynomial gives coefficient one on $t^3$. Hence \[ \widetilde R_{u,v}(t)=t^3+\varepsilon t, \] and $4$ yields \[ R_{u,v}(q)=(q-1)^3+\varepsilon q(q-1) =q^3+(\varepsilon-3)q^2+(3-\varepsilon)q-1. \tag{5} \] The path formula and monicity are established inputs; the specialization to this low rank is the calculation here.

Bruhat intervals are Eulerian, so the number of coatoms in rank three also equals $a$: the alternating rank sum is $1-a+b-1=0$. Write $P_{u,v}=1+cq$. Every proper subinterval appearing in $2$ has length at most two and thus has $P=1$. Separating the four ranks in $2$ gives \[ q^3+cq^2=(1+cq)+a(q-1)+a(q-1)^2+R_{u,v}(q). \] Substitution of $5$, followed by comparison of the coefficient of $q$, gives $c=a-3+\varepsilon$. This proves $3$ for any Coxeter system, not just a symmetric group. Each quantity on the right side is visible in the unlabelled directed graph. The selected invariance assertion therefore holds for all intervals of length at most three.

Checks distinguishing reflection edges from covers.

In type $A_2$, the interval from the identity to the longest element has rank three and two atoms. The longest element is itself a reflection, so $\varepsilon=1$ and $3$ gives $P=1$. Dropping the long edge would instead give the incorrect coefficient $-1$. A rank-three Boolean interval has three atoms and no endpoint reflection edge, again giving $P=1$. These tests check both the sign and the need for the graph convention in the question.

An exact Python calculation enumerates all 24 permutations of $S_4$. It tests Bruhat order by sorted-prefix inequalities and computes $R$-polynomials by the usual simple-descent recurrence. It then reconstructs $P$ from $2$ and the degree bound, checking the entire polynomial identity rather than just its low coefficients. There are 213 comparable intervals in this enumeration, including 42 of rank three; all satisfy $3$, and two rank-three intervals have a nonconstant polynomial. This is a reproducible finite check of the formula and conventions. It is not a proof in other ranks or other Coxeter groups; the preceding symbolic argument supplies the stated general low-rank result.

Why the general path argument stops.

For larger rank, increasing paths of intermediate lengths contribute to $\widetilde R$. Their number is not the total number of directed paths of that length. Whether their successive reflections increase depends on an ordering of reflection labels. The unlabelled graph retains endpoints and adjacency, but an arbitrary ordering of its edges need not arise from a reflection order and has no justification in Dyer's formula. Using the formula with invented labels would not prove invariance under the isomorphisms in the question.

Likewise the familiar descent recurrence compares $u,v$ with $us,vs$ for a simple reflection $s$. The ambient system supplies that operation; the interval graph alone does not come with a distinguished $s$ or a map implementing those multiplications. A valid recursive proof must either reconstruct sufficient descent data intrinsically or show that all allowed choices produce the same result without those data.

Source scope and outcome.

[S1] discusses precisely the directed-graph formulation, which is retained here. The primary path formula [E1] provides a tool with additional labels, not the missing unlabelled invariance theorem. The first unresolved step in this route is a graph-intrinsic way to recover the intermediate increasing-path contributions, or an alternative intrinsic recurrence. The rank-three identity $3$ and its finite checks are the strongest conclusions of the attempt. The full combinatorial invariance conjecture remains UNRESOLVED.

Sources

• S1 Gurevich and Wang, Parabolic recursions for Kazhdan-Lusztig polynomials and the hypercube decomposition, Selecta Mathematica $2024$, Conjecture 5.1. https://link.springer.com/article/10.1007/s00029-024-00972-0. Formulation source. Consulted 24 September 2026: Full directed reflection Bruhat graphs and their combinatorial invariance conjecture.
• E1 Matthew J. Dyer, Hecke algebras and shellings of Bruhat intervals, Compositio Mathematica 89 $1993$, 91--115. https://www.numdam.org/item/CM_1993__89_1_91_0.pdf. Primary source for the reflection-order increasing-path formula and the Hecke-algebra conventions used in the rank-three calculation. The labels in that formula are additional data, not supplied by the conjecture's graph isomorphism. Consulted 27 September 2026.