Combinatorial invariance of Kazhdan–Lusztig polynomials

The explanation

Take the 24 orderings of the numbers 1, 2, 3, 4, which form the symmetric group S4. Each ordering has a length: the number of pairs that appear in the wrong order. Bruhat order says when one ordering sits below another, roughly by fixing wrong pairs one at a time. Now pick 3412, which has length 4. The orderings between 1234 and 3412 form its Bruhat interval. A computer count finds 14 orderings in it. Kazhdan and Lusztig attached a polynomial to each such pair. For this pair it is 1 + q. For the whole group, from 1234 to 4321, the interval has 24 orderings and the polynomial is 1. We computed these values with the standard recursion.

Kazhdan and Lusztig defined these polynomials through an algebra built from the groupSource 1. Later they found a geometric meaning, as local invariants of certain spaces called Schubert varietiesSource 2. The interval, by contrast, is just a finite ordered set. The combinatorial invariance conjecture is attributed to Lusztig and DyerSource 3. It says two intervals with the same order shape have the same polynomial. Before this paper, it was known for intervals starting at the identity, in every Coxeter groupSource 4. It was also known for all intervals of rank at most sixSource 5. Here rank is the difference in length between the two ends.

The paper proves the full conjecture. For any two Coxeter systems, an order-preserving match between two intervals forces equal polynomialsSource 6. A Coxeter system is a group generated by reflections, like S4 or the symmetries of a regular polygon. The result covers infinite and noncrystallographic groups tooSource 7. The obstacle is that a bare interval keeps no labels: no generators and no root dataSource 8. The proof works with sheaves on moment graphs, which recover the polynomial as a rank. It orders the edges of one interval using a reflection order from the other systemSource 9. A two-way comparison then forces every bound in the argument to be exactSource 10.

How sure is this? Lean, a computer proof checker, has a formal statement of the main theorem. It covers intervals from two different Coxeter systems. So the paper proves it, as far as the Lean statement matches the paper. No specialist review of the paper is published.

What it doesn't show. This does not give a simple recipe for computing the polynomial from the interval's shape. It also covers only the equal-parameter polynomials, not unequal-parameter versions.