Episode 168, October 2026

Shape is enough?

A preprint claims that the shape of a Bruhat interval alone determines its Kazhdan–Lusztig polynomial, in every Coxeter group

Covers result 168 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 168: Shape is enough? The Bruhat interval from 1234 to 3412 in the symmetric group, each step coloured by the two values it swaps (our drawing).

5:48. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Order the permutations of a few numbers by Bruhat order: one is below another if you can climb from it to the other by swapping two values, each swap increasing the length (the fewest neighbour swaps needed). Coxeter groups generalize this to groups generated by reflections with only pairwise relations, finite or infinite, and every interval [u, b] between two elements is a finite ordered set. “Kazhdan and Lusztig introduced these polynomials through the canonical basis of the Hecke algebra”, and in the Weyl-group setting they are local intersection-cohomology invariants of Schubert varieties. For four numbers, by our count, only 6 of the 213 intervals have a polynomial other than 1, all equal to 1 + q. The combinatorial invariance conjecture, “attributed to Lusztig and Dyer”, asks whether the abstract ordered set alone determines the polynomial. As the paper recounts, it was known for intervals starting at the identity in every Coxeter group (Brenti, Caselli and Marietti; Delanoy), in rank at most six (Barkley, Gaetz and Lam), and up to rank ten in finite Weyl groups and twelve in finite type A (Esposito, Marietti and Stella); Blundell, Buesing, Davies, Veličković and Williamson found a recurrence for symmetric groups “guided by analyses of trained machine-learning models”.

Result 168 is a single OpenAI preprint, Combinatorial invariance of Kazhdan–Lusztig polynomials (31 pages, dated September 24, 2026). Theorem 1.1: “Let (W,S) and (W′,S′) be arbitrary Coxeter systems, and let u ≤ b in W and u′ ≤ b′ in W′. If ι : [u,b] → [u′,b′] is an isomorphism of abstract Bruhat interval posets, then their equal-parameter Kazhdan–Lusztig polynomials satisfy P^W_u,b(q) = P^W′_u′,b′(q).” “The statement includes infinite and noncrystallographic groups”, and Corollary 6.1 extends it to every Kazhdan–Lusztig polynomial and R-polynomial on the subintervals. As our own illustration, [1234, 3412] and [2134, 4231] in S₄ have the same shape at different heights, and the same shape appears as [e, s₁s₃s₂s₁] in the infinite affine group Ã₂ and in the rank-3 group with no relations linking different generators; all have polynomial 1 + q.

What it doesn’t claim

No formula: the shape determines the polynomial, but the paper gives no recipe for reading it off, and it does not claim the machine-learning-guided recurrence conjecture or Caselli and Marietti’s proposed algorithm. One parameter q for all generators; order-preserving isomorphisms only; “no matching of root labels is asserted.” As our own illustration of why the whole shape matters, the interval [1324, 4231] of S₄ and the interval [s₂, s₂s₃s₁s₂s₁] of B₃ have the same number of elements at every rank (1, 4, 6, 4, 1) and the same 32 covers, but different shapes and different polynomials (1 and 1 + q). All of our small examples lie in ranges settled before this paper.

Where it stands

Posted as a preprint: OpenAI, 31 pages, dated September 24, 2026
Peer reviewed: Not yet
Checked in Lean: The main theorem, formalized by OpenAI; not run by us

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization whose comparator statement matches Theorem 1.1: arbitrary Coxeter systems, an order isomorphism of intervals, and the polynomial defined by the paper’s R-recursion, reciprocity and degree bound. By our count the proof takes 34 files and 42,948 lines excluding Mathlib (the development), with no unproved steps by our search; we have not rebuilt it. Corollary 6.1 is not part of the comparator, and the repository’s formalization list omits this result. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

The missing labels. “The defining recursion for Kazhdan–Lusztig polynomials uses the simple generators of a Coxeter system, while geometric and categorical constructions use root labels. An abstract Bruhat interval poset retains neither kind of data.”
Two separate worlds. After reducing to finite rank, each group gets a real reflection representation and a Braden–MacPherson sheaf on its Bruhat graph (following Fiebig and Soergel); with the character theorem of Elias and Williamson, the sizes of its pieces are given by Kazhdan–Lusztig polynomials.
Edges from the order. A closure rule on six points in four layers recovers every reflection edge, including the longer ones, from the poset alone (Theorem 3.4), but not their labels. Our check: it rebuilds the edges of all 213 intervals of S₄.
Borrowed labels. A reflection order in the second group, carried over by the isomorphism, schedules the edges of the first interval, though it “need not be a reflection order in the first system”. Rank-two pieces transport intact; in each, the borrowed order gives the right difference in later edges at the two ends of an edge, and these sum to (d − 1)/2. Localizing at root planes bounds each edge’s image in the sheaf.
The squeeze. Removing the edge conditions in the borrowed order bounds the polynomial through a count of label-ordered paths, which by Dyer’s formula is the second group’s R-polynomial. The inequality holds in both directions, and the degree bound forces equality; equality makes every bound exact and keeps the induction going.

The numbers in the video

Our counts: S₃ has 19 intervals, all with polynomial 1; S₄ has 213, of which 6 have 1 + q; S₅ has 3,781 with five different polynomials.
Our isomorphic intervals: [1234, 3412] and [2134, 4231] in S₄ (14 elements, rank sizes 1, 3, 5, 4, 1), and [e, s₁s₃s₂s₁] in Ã₂ and in the rank-3 group with no relations linking different generators, all with 1 + q.
Our equal counts with different shapes: S₄ [1324, 4231] (polynomial 1) and B₃ [s₂, s₂s₃s₁s₂s₁] (1 + q).
Our path count: from 1234 to 3412 with increasing labels, two paths, giving R̃ = T² + T⁴.
The Lean count: 34 files and 42,948 lines, our count of the import closure.

Read the source

Combinatorial invariance of Kazhdan–Lusztig polynomials (PDF), 31 pages.
The Lean scope note.
The collection’s catalog, where this is result 168.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Combinatorial invariance of Kazhdan–Lusztig polynomials

Transcript

Read the full script

0:00The question

Start with the symmetric group: all orderings of a few numbers, built by swapping neighbours. The fewest neighbour swaps needed to reach an ordering is its length. Bruhat order puts one ordering below another when you can climb from the first to the second by swapping two values, each swap increasing the length. For three numbers this gives six orderings on four levels, plus one longer step from the bottom straight to the top. For four numbers there are 24 orderings. An interval is everything between two elements, and it has a shape: a finite ordered set. Coxeter groups generalize all of this to groups generated by mirror-like flips, where the only rules say how each pair of flips combines, including infinite groups, and every interval in them is still finite. In 1979, Kazhdan and Lusztig attached a polynomial to each such interval, through a special basis of the Hecke algebra. In the Weyl-group setting, these polynomials record the singularities of Schubert varieties. For three numbers they all equal one. In our count for four numbers, only 6 of the 213 intervals have a different polynomial, all equal to 1 + q; one of them runs from the bottom up to 3412. The polynomial is defined using the group’s generators. The combinatorial invariance conjecture, attributed to Lusztig and Dyer, says the shape of the interval alone determines it. As the paper recounts, it was known for intervals starting at the bottom, in every Coxeter group; Barkley, Gaetz and Lam proved it up to rank 6, and Esposito, Marietti and Stella reached rank 10 in finite Weyl groups and 12 for permutations. Work guided by machine-learning models found a recurrence for permutations built on cube-shaped decompositions, proved for one decomposition and conjectured for all, and later proved for intervals starting at the bottom.

1:51The claim

Result 168 is a 31-page OpenAI preprint, dated September 24. Its theorem: take any two Coxeter systems, possibly different, and an interval in each. If the two intervals are isomorphic as ordered sets, their Kazhdan–Lusztig polynomials are equal. That includes infinite groups and groups with no Schubert varieties behind them. Applying it to every smaller interval, all the polynomials inside are determined too, and so are the related R-polynomials. In our example, the interval from 1234 up to 3412 and the interval from 2134 up to 4231 have the same shape, at different heights, and both polynomials are 1 + q. The same shape appears in an infinite affine group and in a group with no relations linking different generators, again with 1 + q. It does not claim a formula. The shape determines the polynomial, but the paper gives no recipe for reading it off, and the machine-learning-guided conjecture is not claimed. It covers one parameter q for all generators, and order-preserving isomorphisms. Simple counts are not enough: in our check, an interval of permutations of four numbers and one in the group B3 have the same number of elements at every rank and the same number of covers, yet different shapes and different polynomials. And our small examples lie inside ranges that were settled before.

3:22How the proof goes

The difficulty is missing labels. The polynomial’s recursion uses the group’s generators, and the geometric tools use root labels on edges; the bare ordered set has neither. The proof first reduces to finitely many generators. In each group separately, it uses sheaves on the Bruhat graph, from Braden and MacPherson and from Fiebig, and a theorem of Elias and Williamson identifies their sizes with Kazhdan–Lusztig polynomials. Then it recovers every reflection edge from the order alone, with a closure rule on six points in four layers; we checked that this rebuilds the edges of all 213 intervals for four numbers. But the order never says which reflection labels an edge. The new idea is to borrow labels. Choose a reflection order in the second group, and use it, through the isomorphism, to schedule the edges of the first interval, even though it need not be a reflection order there. Rank-two pieces carry over intact, and in each one the borrowed order gives the right difference in later edges at the two ends of each edge; summed over these planes, that difference is half of one less than the length gap. Localizing at each plane turns this into a bound comparing the two ends of each edge inside the sheaf. Removing the edge conditions in the borrowed order then bounds the polynomial through a count of label-ordered paths, which by Dyer’s formula gives the second group’s R-polynomial. In our example, the two paths up to 3412 with increasing labels give T² + T⁴. That is an inequality one way; swapping the two groups gives it the other way, and the degree bound then forces the polynomials to be equal; equality makes every bound exact, which keeps the induction going.

5:08Where it stands

The paper is a preprint, not peer reviewed, and not revised. Its main theorem is stated in Lean to match the paper’s theorem, and OpenAI’s files contain a proof of about 43,000 lines, with no gaps we could find by search; we did not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the shape of a Bruhat interval alone fixes its Kazhdan–Lusztig polynomial, in every Coxeter group, finite or infinite, though the paper gives no way to read the polynomial off the shape directly.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.