Combinatorial invariance of Kazhdan–Lusztig polynomials
Let \((W,S)\) and \((W',S')\) be arbitrary Coxeter systems, with \(u\le b\) and \(u'\le b'\). If \[ \phi:[u,b]\simeq[u',b'] \] is an isomorphism of abstract partially ordered sets, then the ordinary equal-parameter Kazhdan–Lusztig polynomials satisfy \[ P^W_{u,b}(q)=P^{W'}_{u',b'}(q). \]
Relation to the OpenAI notes
Different proof route.
OpenAI notes: The simultaneous induction compares normalized KL vectors, obtains P-invariance from the strict half-degree bound, and then recovers bottom terminal-kernel freeness from endpoint equality. sec:induction, eq:comparison, eq:reciprocal-vector.
Lean (primary): The simultaneous induction first proves normalized R-invariance together with suffix-kernel freeness in both transported directions. It cancels known bottom R-row entries against one actual source-character vector. Canonical KL equality is proved afterwards in a separate induction using the now common R-matrix and the canonical degree bound. Invariance:136, Invariance:190, Invariance:427.
Role in the proof: Proper upper intervals supply kernel freeness, and proper initial intervals supply known R-entries. The new R-equality gives exact endpoints and then current-rank suffix freeness. The canonical degree bound enters the subsequent P-induction.
Proof
Step 1. The interval isomorphism
We have arbitrary Coxeter systems \(W,W'\), comparable endpoints \(u\le b\), \(u'\le b'\), and an order isomorphism \(\phi:[u,b]_W\simeq[u',b']_{W'}\). Neither generating set is assumed finite, and no realization or basis is part of the hypothesis.
Step 2. Replace each interval by a finite-generator model
Apply Existence and transport of finite-support interval models to obtain models \(W_J,W'_{J'}\), lifted endpoints \(\bar u,\bar b,\bar u',\bar b'\), and order isomorphisms \[ j:[\bar u,\bar b]_{W_J}\simeq[u,b]_W,\qquad j':[\bar u',\bar b']_{W'_{J'}}\simeq[u',b']_{W'}. \] The same result gives the two polynomial identities \[ P^{W_J}_{\bar u,\bar b}=P^W_{u,b}, \qquad P^{W'_{J'}}_{\bar u',\bar b'}=P^{W'}_{u',b'}. \]
Step 3. Form the comparison between the models
Compose the maps in the order \[ \psi=(j')^{-1}\circ\phi\circ j. \] For a model vertex \(x\), first \(j(x)\) lies in the source ambient interval, then \(\phi(j(x))\) lies in the target ambient interval, and finally \((j')^{-1}\) returns a target model vertex. Each factor is an order isomorphism, so \(\psi\) is an order isomorphism between the two model intervals.
Step 4. Apply the finite-generator theorem with internal choices
The sets \(J,J'\) are finite. Their extended real realizations are therefore finite-dimensional and admit bases. Choose such bases solely to invoke KL invariance for finite-generator Coxeter systems. The theorem gives \[ P^{W_J}_{\bar u,\bar b}=P^{W'_{J'}}_{\bar u',\bar b'}. \] Its conclusion is an equality of the canonical polynomials; it contains neither chosen basis.
Step 5. Write the final equality chain
Substitute the transport equalities from Step 2: \[ P^W_{u,b} =P^{W_J}_{\bar u,\bar b} =P^{W'_{J'}}_{\bar u',\bar b'} =P^{W'}_{u',b'}. \] The first and last equalities are parabolic transport, and the middle equality is finite-generator invariance. This proves the original assertion for the arbitrary systems in Step 1.
References
1. Introduction and conventions.
Lean formalization
OAI.KLInvariance.combinatorial_invariance: Invariance.lean:547.