Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 11 results · all verified · 5 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 6 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Kazhdan–Lusztig Bases, Polynomials, and Cells

1 · Prerequisites

2 · Summary

This page records the full Kazhdan–Lusztig basis theorem and its coefficient positivity, followed by polynomial recursion, inversion and cell theory. The elementary Hecke, Bruhat, bar and triangular-basis constructions are developed on divided-powers-integral-forms-and-quantum-highest-weights. The local Soergel character and filtration-multiplicity argument on soergel-intersection-forms-and-hodge-theory supplies positivity. The recursion and inverse-basis identities provide the algebraic tools used below.

The final part identifies the type-A cells through Robinson–Schensted. Knuth and dual Knuth moves preserve the insertion and recording tableaux; rank-two star operations transport the Kazhdan–Lusztig graph and left-cell relations. For the two-sided forward implication, Geck’s shape-invariance result is used after identifying the algebra and coefficient-step conventions. The resulting classification states that left cells are the $Q$ -fibers, right cells are the $P$ -fibers, and two-sided cells are the common-shape fibers. The concrete calculations are collected on kazhdan-lusztig-bases-polynomials-and-cells-examples.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

Verma's sign identity over Bruhat intervals

Facts & Assumptions

Given: $n \geq 1$ and the Laurent coefficients $r_{x, z}$ from The $R$ -coefficient recursion, support, degree bounds and inversion.

[F1]

For all $a, b \in S_{n}$ , $\sum_{y} r_{a, y} \overline{r_{y, b}} = δ_{a, b}$ and $\overline{r_{y, b}} = s g n (y) s g n (b) r_{y, b}$ (The $R$ -coefficient recursion, support, degree bounds and inversion, parts (d),(e)).

[F2]

$r_{a, b} = 0$ unless $a \leq b$ ; for $a \leq b$ , with $d = ℓ (b) - ℓ (a)$ , the least-degree term of $r_{a, b}$ is $s g n (a) s g n (b) v^{- d}$ and all exponents are congruent to $- d$ modulo $2$ (The $R$ -coefficient recursion, support, degree bounds and inversion, parts (b),(c)).

[F3]

Bruhat order on $S_{n}$ is graded by $ℓ$ and has finite intervals; in particular $x < z$ implies $ℓ (x) < ℓ (z)$ (Basic properties of the Bruhat order on $S_{n}$ ).

Statement

For all $x < z$ in $S_{n}$ , with $s g n (y) = (- 1)^{ℓ (y)}$ , $\sum_{y \in S_{n}, x \leq y \leq z} s g n (y) = 0.$

Proof

technique · extract the lowest Laurent degree from the R-matrix identity

1.1F1F2F3algebra

Reduce to the interval. Fix $x < z$ and set $d : = ℓ (z) - ℓ (x)$ . Bruhat gradedness gives $d > 0$ . The R-matrix identity and bar symmetry yield $0 = \sum_{y} r_{x, y} \overline{r_{y, z}} = s g n (z) \sum_{y} s g n (y) r_{x, y} r_{y, z}$ . By support, a nonzero summand requires both $x \leq y$ and $y \leq z$ , so $0 = \sum_{x \leq y \leq z} s g n (y) r_{x, y} r_{y, z}$ .

2.1F1F2F3step 1.1algebra∎

Extract the lowest degree. For each $y \in [x, z]$ , let $d_{1} : = ℓ (y) - ℓ (x)$ and $d_{2} : = ℓ (z) - ℓ (y)$ , so $d_{1} + d_{2} = d$ . The least exponent in $r_{x, y} r_{y, z}$ is $- d$ and its coefficient is $s g n (x) s g n (y)^{2} s g n (z) = s g n (x) s g n (z)$ . The external factor $s g n (y)$ in step 1.1 makes the coefficient of $v^{- d}$ in that summand $s g n (x) s g n (z) s g n (y)$ . Since every other exponent in each factor is strictly above its least exponent, no other product terms contribute to degree $- d$ . Taking that coefficient in the zero sum of step 1.1 gives $0 = s g n (x) s g n (z) \sum_{x \leq y \leq z} s g n (y)$ . The prefactor is $\pm 1$ , proving the claim. The interval is finite, and no choice principle is used.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Existence and uniqueness of the Kazhdan–Lusztig basis

Statement

For each $w \in S_{n}$ there is a unique element ${\underline{H}}_{w} \in H_{v} (n)$ with (i) $\overline{{\underline{H}}_{w}} = {\underline{H}}_{w}$ and (ii) ${\underline{H}}_{w} \in H_{w} + \sum_{y < w} v Z [v] H_{y}$ (the sum over the lower Bruhat ideal of $w$ ). The elements ${{\underline{H}}_{w}}_{w \in S_{n}}$ form an $A$ -basis of $H_{v} (n)$ , and writing ${\underline{H}}_{w} = \sum_{y \leq w} p_{y, w} H_{y}$ one has $p_{w, w} = 1$ , $p_{y, w} = 0$ unless $y \leq w$ , $p_{y, w} \in v Z [v]$ for $y < w$ , the bar-duality $p_{x, w} = \sum_{y} r_{x, y} \overline{p_{y, w}}$ (matrix form $P = R \overset{ˉ}{P}$ ), and the symmetry $p_{y^{- 1}, w^{- 1}} = p_{y, w}$ . Moreover for $y < w$ , with $d = ℓ (w) - ℓ (y)$ : $p_{y, w} = v^{d} + terms of strictly smaller degree$ and $p_{y, w} \in v^{d} Z [v^{- 2}]$ ; in particular every ${\underline{H}}_{w}$ has integer nonnegative coefficients in the standard basis with $p_{y, w}$ of fixed parity $d m o d 2$ .

Facts & Assumptions

Given: $n \geq 1$ , the normalized Hecke algebra $H_{v} (n)$ , its standard basis and bar involution.

[F1]

The unique bar-invariant triangular basis has the locally proved existence, uniqueness, basis, support, bar-duality, degree, leading-term, parity and inverse-index symmetry clauses of The type-A Kazhdan–Lusztig basis has elementary triangular bar properties.

[F2]

The same uniquely normalized triangular basis has nonnegative standard-basis coefficients by the local Soergel character and filtration-multiplicity proof of Positivity of Kazhdan-Lusztig polynomials, mu-coefficients and structure constants. Its classical rescaling preserves every integer coefficient.

Proof

technique · combine the local elementary basis construction with the local multiplicity proof of positivity

1.1F1given

Apply [F1] to the given algebra. It constructs the unique ${\underline{H}}_{w}$ with the asserted bar-invariance and triangularity, proves that these elements form an $A$ -basis, and proves all support, coefficient, bar-duality, symmetry, leading-term and parity clauses in the Statement. Its construction does not assume coefficientwise positivity.

2.1F2step 1.1∎

The local character theorem used by [F2] identifies the normalized indecomposable Soergel character with these same unique triangular elements; their standard-basis coefficients are the actual nonnegative integer graded filtration multiplicities. Therefore $p_{y, w} \in Z_{\geq 0} [v]$ for $y \leq w$ , while the unsupported coefficients remain zero by step 1.1. The diagonal coefficient is one. Together with the degree and parity clauses of step 1.1 this proves the full Statement, including coefficientwise positivity, without an original-source fallback.

Remarks

The elementary construction precedes the local Soergel induction. Its trace, multiplication and character consumers use the elementary supplier directly, so the local positivity theorem is a later consequence and there is no circular positivity input.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

The Kazhdan–Lusztig polynomial descent recursion

Facts & Assumptions

Given: $n \geq 1$ , a simple reflection $s = s_{i}$ , a left descent $s w < w$ , and the polynomial normalization $q = v^{- 2}$ .

[F1]

$A = Z [v^{\pm 1}]$ , the standard elements $H_{x}$ form a basis and are products along reduced expressions, and $H_{s}^{2} = 1 + (v^{- 1} - v) H_{s}$ (The normalized type-A Hecke algebra and its bar involution).

[F2]

The Kazhdan–Lusztig basis and its generator multiplication formula are as stated in Multiplication by a generator in the Kazhdan–Lusztig basis.

[F3]

$p_{x, z} = v^{ℓ (z) - ℓ (x)} P_{x, z} (v^{- 2})$ when $x \leq z$ , and $μ (x, z)$ is the coefficient of $v$ in $p_{x, z}$ ; it is zero unless $ℓ (z) - ℓ (x)$ is odd (Kazhdan–Lusztig polynomials in the classical $q$ -normalization).

[F4]

Writing ${\underline{H}}_{t} = \sum_{x \leq t} p_{x, t} H_{x}$ , the basis coefficients vanish outside Bruhat order and satisfy $p_{y^{- 1}, w^{- 1}} = p_{y, w}$ (Existence and uniqueness of the Kazhdan–Lusztig basis).

[F5]

Bruhat order is graded by $ℓ$ , simple reflections change length by one, inversion preserves Bruhat order and length, and Bruhat comparison is characterized by reduced subwords; in particular $[i d, s] = {i d, s}$ for a simple reflection (Basic properties of the Bruhat order on $S_{n}$ ).

Statement

Let $s = s_{i}$ be a simple reflection, $w \in S_{n}$ with $s w < w$ , and $y \leq w$ . With $P_{x, z} : = 0$ whenever $x \leq̸ z$ , $P_{y, w} (q) = q^{1 - c} P_{s y, s w} (q) + q^{c} P_{y, s w} (q) - ⁣ ⁣ ⁣ \sum_{\begin{array}{c} y \leq z \leq s w \\ s z < z, μ (z, s w) \neq 0 \end{array}} ⁣ ⁣ ⁣ μ (z, s w) q^{(ℓ (w) - ℓ (z)) / 2} P_{y, z} (q),$ where $c = 1$ if $s y < y$ and $c = 0$ if $s y > y$ ; here $μ$ is the coefficient defined in Kazhdan–Lusztig polynomials in the classical $q$ -normalization (so the summand only occurs for $ℓ (s w) - ℓ (z)$ odd, and $(ℓ (w) - ℓ (z)) / 2$ is then an integer). The same recursion holds with $s \in R (w)$ (right descents) after replacing each index $x$ by $x^{- 1}$ , using $P_{y^{- 1}, w^{- 1}} = P_{y, w}$ and $μ (y^{- 1}, w^{- 1}) = μ (y, w)$ .

Proof

technique · compare the standard-basis coefficients in the left generator multiplication formula

1.1F1F2F3F4F5algebra

The coefficient equation. Since $s w < w$ , we have $s (s w) = w > s w$ . By [F2], ${\underline{H}}_{s} {\underline{H}}_{s w} = {\underline{H}}_{w} + \sum_{\begin{array}{c} z \leq s w \\ s z < z \end{array}} μ (z, s w) {\underline{H}}_{z} .$ By [F4], ${\underline{H}}_{s}$ is supported on ${x : x \leq s}$ , and [F5]'s reduced-subword characterization gives $[i d, s] = {i d, s}$ . The constant-term and degree clauses in [F3] give $P_{i d, s} = 1$ and $p_{i d, s} = v$ , so ${\underline{H}}_{s} = H_{s} + v H_{i d}$ . Expand each ${\underline{H}}_{t} = \sum_{x \leq t} p_{x, t} H_{x}$ using [F4]. Reduced words and the quadratic relation in [F1] give $H_{s} H_{x} = H_{s x}$ if $s x > x$ ; if $s x < x$ , then $x = s (s x)$ is reduced and $H_{s} H_{x} = H_{s}^{2} H_{s x} = H_{s x} + (v^{- 1} - v) H_{x}$ . Thus the coefficient of $H_{y}$ on the left is $p_{s y, s w} + v^{- 1} p_{y, s w}$ when $s y < y$ , and $p_{s y, s w} + v p_{y, s w}$ when $s y > y$ . The coefficient on the right is $p_{y, w} + \sum_{y \leq z \leq s w, s z < z} μ (z, s w) p_{y, z}$ . Therefore $p_{y, w} = {\begin{cases} p_{s y, s w} + v^{- 1} p_{y, s w}, & s y < y, \\ p_{s y, s w} + v p_{y, s w}, & s y > y, \end{cases} - \sum_{\begin{array}{c} y \leq z \leq s w \\ s z < z \end{array}} μ (z, s w) p_{y, z} .$

2.1F3F5step 1.1algebra

Convert to $q$ -polynomials. Put $d : = ℓ (w) - ℓ (y)$ . By [F5], $d \geq 0$ . If $s y < y$ , then $ℓ (s w) - ℓ (s y) = d$ and $ℓ (s w) - ℓ (y) = d - 1$ ; after substituting $p_{x, z} = v^{ℓ (z) - ℓ (x)} P_{x, z} (v^{- 2})$ in step 1.1 and dividing by $v^{d}$ , the first two terms become $P_{s y, s w} (q) + q P_{y, s w} (q)$ . If $s y > y$ , then $ℓ (s w) - ℓ (s y) = d - 2$ , so they become $q P_{s y, s w} (q) + P_{y, s w} (q)$ . These identities also hold when an index is outside the relevant Bruhat interval, using the zero convention for $P$ . For a sum term, $ℓ (z) - ℓ (y) - d = - (ℓ (w) - ℓ (z))$ , giving the factor $q^{(ℓ (w) - ℓ (z)) / 2}$ . Thus the two cases are the displayed formula with $c = 1$ and $c = 0$ , respectively. If $μ (z, s w) \neq 0$ , then $ℓ (s w) - ℓ (z)$ is odd; since $ℓ (w) = ℓ (s w) + 1$ by [F5], the exponent $(ℓ (w) - ℓ (z)) / 2$ is an integer.

3.1F4F5step 2.1algebra∎

Right descents. If $w s < w$ , inversion preserves Bruhat order by [F5], so $s w^{- 1} < w^{- 1}$ and $y^{- 1} \leq w^{- 1}$ . Apply the left formula to $y^{- 1}, w^{- 1}, s$ . Replace every inverted index using [F4]; lengths and length differences are unchanged by [F5], while $s z < z$ becomes $z s < z$ . This gives the right-descent recursion.

Remarks

The coefficient comparison uses the locally proved multiplication formula, normalization and inverse-index symmetry. Coefficientwise positivity is not required.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

The Kazhdan–Lusztig inversion formula

Facts & Assumptions

Given: $n \geq 1$ and the finite standard and Kazhdan–Lusztig bases of $H_{v} (n)$ .

[F1]

Bar-duality gives $P = R \overset{ˉ}{P}$ , and $R \overset{ˉ}{R} = \overset{ˉ}{R} R = I$ (Existence and uniqueness of the Kazhdan–Lusztig basis, The $R$ -coefficient recursion, support, degree bounds and inversion).

[F2]

The chain-defined matrix $Q^{'}$ is the two-sided inverse of $P$ , and the classical sign matrix $S$ gives $Q = S Q^{'} S$ (Inverse Kazhdan–Lusztig polynomials).

[F3]

Bruhat intervals in $S_{n}$ are finite (Basic properties of the Bruhat order on $S_{n}$ ).

Statement

Let $P = (p_{x, w})$ , $Q^{'} = (q_{x, w}^{'})$ and $R = (r_{x, y})$ be the triangular matrices of Existence and uniqueness of the Kazhdan–Lusztig basis, Inverse Kazhdan–Lusztig polynomials and The $R$ -coefficient recursion, support, degree bounds and inversion. Then (a) $P = R \overset{ˉ}{P}$ , $\overset{ˉ}{P} = \overset{ˉ}{R} P$ , and $R \overset{ˉ}{R} = \overset{ˉ}{R} R = 1$ ; (b) $Q^{'} P = P Q^{'} = 1$ , and the inversion formulas $\overline{q_{x, w}^{'}} = \sum_{x \leq z \leq w} q_{x, z}^{'} r_{z, w}, \overline{q_{x, w}} = \sum_{x \leq z \leq w} q_{x, z} \overline{r_{z, w}}$ hold, i.e. ${\overset{ˉ}{Q}}^{'} = Q^{'} R$ and $\overset{ˉ}{Q} = Q \overset{ˉ}{R}$ ; (c) for the dual basis $D_{x} ({\underline{H}}_{w}) = δ_{x, w}$ from Inverse Kazhdan–Lusztig polynomials, $D_{x} (H_{w}) = q_{x, w}^{'}$ . The inversion is proved from the bar-duality relations alone (no finite case check).

Proof

technique · compare the coefficient matrices and use the chain inverse defining $Q'$

1.1F1algebra

Bar-duality matrices. Entrywise bar applied to $P = R \overset{ˉ}{P}$ gives $\overset{ˉ}{P} = \overset{ˉ}{R} P$ , because bar is an involution and is multiplicative on matrices over the commutative coefficient ring. The R theorem gives both $R \overset{ˉ}{R} = I$ and $\overset{ˉ}{R} R = I$ . Thus (a) holds.

2.1F1F2F3step 1.1algebra

The inverse matrix identity. By [F2], $Q^{'} = P^{- 1}$ . From $P = R \overset{ˉ}{P}$ , inversion gives $Q^{'} = {\overset{ˉ}{P}}^{- 1} R^{- 1} = {\overset{ˉ}{Q}}^{'} \overset{ˉ}{R}$ , since ${\overset{ˉ}{P}}^{- 1} = \overline{P^{- 1}} = {\overset{ˉ}{Q}}^{'}$ and $R^{- 1} = \overset{ˉ}{R}$ . Applying entrywise bar yields ${\overset{ˉ}{Q}}^{'} = Q^{'} R$ . Its $(x, w)$ entry is $\overline{q_{x, w}^{'}} = \sum_{z} q_{x, z}^{'} r_{z, w}$ ; triangular support restricts this finite sum to $x \leq z \leq w$ .

3.1F1F2F3step 2.1algebra

The signed inverse formula. Let $S$ be diagonal with $S_{x, x} = s g n (x)$ , so $S^{2} = I$ . From [F2], $Q = S Q^{'} S$ ; from the R bar-symmetry, $\overset{ˉ}{R} = S R S$ . Therefore $\overset{ˉ}{Q} = S {\overset{ˉ}{Q}}^{'} S = S Q^{'} R S = (S Q^{'} S) (S R S) = Q \overset{ˉ}{R}$ , whose $(x, w)$ entry is $\overline{q_{x, w}} = \sum_{z} q_{x, z} \overline{r_{z, w}}$ . Triangular support again restricts to $x \leq z \leq w$ .

4.1F1F2F3step 1.1step 2.1algebra∎

Dual-basis interpretation. Since $({\underline{H}}_{w})$ is a basis of the finite free module $H_{v} (n)$ , its coordinate functionals $D_{x}$ form the dual basis and satisfy $D_{x} ({\underline{H}}_{w}) = δ_{x, w}$ . Put $d_{x, w} : = D_{x} (H_{w})$ . Evaluating on ${\underline{H}}_{w} = \sum_{z} p_{z, w} H_{z}$ gives $D P = I$ ; because $P$ is invertible, $D = P^{- 1} = Q^{'}$ , so $D_{x} (H_{w}) = q_{x, w}^{'}$ . Conversely, if the dual evaluations are $q_{x, w}^{'}$ , the identity $Q^{'} P = I$ gives $D_{x} ({\underline{H}}_{w}) = δ_{x, w}$ . This proves (c). All sums are finite by [F3], and no choice principle is used.

Remarks

The matrix inversion uses the locally proved basis/bar-duality clauses and the finite chain inverse with its sign convention. Coefficientwise positivity is not required.

DefinitionDefinition: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

$L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells

Definition

Let $n \geq 1$ , let $C_{w} : = {\underline{H}}_{w}$ be the Kazhdan–Lusztig basis from Existence and uniqueness of the Kazhdan–Lusztig basis, and let $S = {s_{1}, \dots, s_{n - 1}}$ be the simple reflections of $S_{n}$ . For $x, y \in S_{n}$ , write $x \leftarrow_{L} y$ if the coefficient of $C_{x}$ in $C_{s} C_{y}$ is nonzero for some $s \in S$ , and write $x \leftarrow_{R} y$ if the coefficient of $C_{x}$ in $C_{y} C_{s}$ is nonzero for some $s \in S$ . Define $x \leq_{L} y$ if there is a finite chain $x = w_{0}, \dots, w_{m} = y$ with $w_{i} \leftarrow_{L} w_{i + 1}$ for every $i < m$ ; define $\leq_{R}$ using $\leftarrow_{R}$ , and define $\leq_{L R}$ by allowing either kind of step at each place. The length-zero chain makes each relation reflexive. Define $x \sim_{L} y$ by $x \leq_{L} y$ and $y \leq_{L} x$ , and similarly $\sim_{R}$ and $\sim_{L R}$ . Their equivalence classes are the left cells, right cells, and two-sided cells.

For $w \in S_{n}$ , set $L (w) : = {s \in S : s w < w}$ and $R (w) : = {s \in S : w s < w}$ . The recorded properties are: $\leq_{L}, \leq_{R}, \leq_{L R}$ are preorders; $x \leq_{L} y$ iff $x^{- 1} \leq_{R} y^{- 1}$ ; $x \leq_{L} y$ implies $R (y) \subseteq R (x)$ and $x \leq_{R} y$ implies $L (y) \subseteq L (x)$ ; consequently, elements of one left cell have equal right descent sets and elements of one right cell have equal left descent sets.

The multiplication formula Multiplication by a generator in the Kazhdan–Lusztig basis gives the non-diagonal elementary left steps: if $s w > w$ , then $C_{s w}$ occurs with coefficient $1$ , and $C_{z}$ occurs with coefficient $μ (z, w)$ exactly for the terms $z < w$ , $s z < z$ , and $μ (z, w) \neq 0$ . If $s w < w$ , the product is $(v + v^{- 1}) C_{w}$ , so it gives only a diagonal step. (That diagonal coefficient is nonzero, but it adds no relation beyond the length-zero chain.)

Facts & Assumptions

Given: $n \geq 1$ , the normalized Hecke algebra $H_{v} (n)$ over $A = Z [v^{\pm 1}]$ , and its Kazhdan–Lusztig basis.

[F1]

The elements $C_{w}$ form an $A$ -basis, and in $C_{w} = \sum_{z} p_{z, w} H_{z}$ the inverse-index symmetry $p_{z^{- 1}, w^{- 1}} = p_{z, w}$ holds (Existence and uniqueness of the Kazhdan–Lusztig basis). The theorem's separate coefficientwise-nonnegativity clause is not used here.

[F2]

Left and right multiplication by a simple generator satisfy the ascent and descent formulas in Multiplication by a generator in the Kazhdan–Lusztig basis. In particular, with $λ : = v + v^{- 1}$ , the descent products are $C_{s} C_{w} = λ C_{w}$ when $s w < w$ and $C_{w} C_{s} = λ C_{w}$ when $w s < w$ .

[F3]

The scalar $λ$ is nonzero in the integral domain $A$ ; the algebra, its coefficient ring, and its generators are as in The normalized type-A Hecke algebra and its bar involution.

[F4]

There is an $A$ -linear anti-automorphism $♭$ with $♭ (H_{w}) = H_{w^{- 1}}$ (Reversal anti-involution commutes with the Hecke bar).

[F5]

The coefficient $μ (z, w)$ in the multiplication formula is the coefficient specified in Kazhdan–Lusztig polynomials in the classical $q$ -normalization.

Proof

technique · use finite chains of basis-coefficient steps, reversal for inversion, and the generator eigenvalue equations for descent sets

1.1algebra

Preorders and cell equivalence. A length-zero chain gives reflexivity of each relation. Concatenating a chain from $x$ to $y$ with one from $y$ to $z$ gives a chain from $x$ to $z$ , proving transitivity for $\leq_{L}$ , $\leq_{R}$ , and $\leq_{L R}$ . Hence each is a preorder, and the relation defined by mutual comparability is reflexive, symmetric, and transitive, so the three stated cell relations are equivalence relations.

1.2F1F4algebra

Reversal identifies left and right steps. Since $♭$ is $A$ -linear and sends $H_{z}$ to $H_{z^{- 1}}$ , the expansion of $♭ (C_{w})$ is $\sum_{z} p_{z, w} H_{z^{- 1}} = C_{w^{- 1}}$ by [F1]. For every simple $s = s^{- 1}$ , applying $♭$ to $C_{s} C_{y} = \sum_{x} a_{x} C_{x}$ gives $C_{y^{- 1}} C_{s} = \sum_{x} a_{x} C_{x^{- 1}}$ . Thus the coefficient of $C_{x}$ in $C_{s} C_{y}$ is nonzero exactly when the coefficient of $C_{x^{- 1}}$ in $C_{y^{- 1}} C_{s}$ is nonzero. Applying inversion term-by-term to finite chains in both directions proves $x \leq_{L} y ⟺ x^{- 1} \leq_{R} y^{- 1}$ .

1.3F1F2F3algebra

Right descents decrease along left steps. Fix an elementary left step $x \leftarrow_{L} y$ , witnessed by $u = C_{s} C_{y} = \sum_{z} a_{z} C_{z}$ with $a_{x} \neq 0$ . Let $t \in R (y)$ , so $C_{y} C_{t} = λ C_{y}$ by [F2]. Associativity gives $u C_{t} = λ u$ . If $x t > x$ , the coefficient of $C_{x}$ in $u C_{t}$ is zero: a descent row $C_{z} C_{t}$ contributes only its own diagonal basis term; an ascent row contributes its leading term $C_{z t}$ , which can equal $C_{x}$ only if $z = x t$ and then $z t = x < z$ , contrary to ascent, while each lower correction term has a $t$ -descent index. The coefficient of $C_{x}$ in $λ u$ is $λ a_{x}$ , so $λ a_{x} = 0$ , contradicting [F3] and $a_{x} \neq 0$ . Therefore $x t < x$ for every $t \in R (y)$ , or $R (y) \subseteq R (x)$ .

1.4F1F2F3algebra

Left descents decrease along right steps. For an elementary right step $x \leftarrow_{R} y$ , write $u = C_{y} C_{s} = \sum_{z} a_{z} C_{z}$ with $a_{x} \neq 0$ . If $t \in L (y)$ , then $C_{t} C_{y} = λ C_{y}$ , so associativity gives $C_{t} u = λ u$ . When $t x > x$ , the coefficient of $C_{x}$ in $C_{t} u$ is zero by the left multiplication formulas: an ascent row's leading term could equal $C_{x}$ only from the index $t x$ , whose left product by $t$ is a descent, and every lower correction has a $t$ -descent index; a descent row contributes only its diagonal term at its own index. Comparing with the coefficient $λ a_{x}$ in $λ u$ and using [F3] forces $t x < x$ . Thus $L (y) \subseteq L (x)$ . Applying these inclusions along finite chains gives the two recorded descent-set containments.

2.1step 1.3step 1.4

Descent sets are constant on cells. If $x \sim_{L} y$ , then $R (y) \subseteq R (x)$ and $R (x) \subseteq R (y)$ by step 1.3 applied in both directions; hence $R (x) = R (y)$ . If $x \sim_{R} y$ , step 1.4 in both directions gives $L (x) = L (y)$ .

3.1F2F5∎

The elementary left-step list. If $s w > w$ , the left multiplication formula is $C_{s} C_{w} = C_{s w} + \sum_{z < w, s z < z} μ (z, w) C_{z}$ , with terms of zero coefficient omitted, so its non-diagonal steps are exactly the Bruhat and $μ$ steps stated in the Definition. If $s w < w$ , the formula is $C_{s} C_{w} = λ C_{w}$ ; this supplies only the diagonal step already covered by reflexivity. Since $λ \neq 0$ , the statement's note about the diagonal coefficient is exact.

Remarks

The proof uses the locally proved basis, inverse-index symmetry and generator multiplication clauses. Coefficientwise positivity is not required.

The finite-chain and coefficient arguments use no choice principle.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Knuth and dual Knuth equivalence for permutations

Definition

Fix $n \geq 1$ . Use $S_{n} = Sym ({1, \dots, n})$ and its one-line notation from Permutation Weyl group and inversion length. The zero-based realization in The finite symmetric group $S_{n}$ , one-line notation, and cycle notation is identified with this one by the order-preserving relabelling $i \mapsto i - 1$ on inputs and values; this relabelling preserves the comparisons below.

For a permutation $x \in S_{n}$ , write its one-line word as $x_{1} x_{2} \dots x_{n}$ , where $x_{i} = x (i)$ . For $a < b < c$ , an elementary Knuth move replaces a contiguous three-letter factor $b c a$ by $b a c$ , or $c a b$ by $a c b$ , with all letters before and after that factor unchanged; either replacement may be reversed. These moves keep the word a permutation of ${1, \dots, n}$ .

The insertion tableau $P (x)$ is obtained by starting with the empty tableau and successively row-inserting $x_{1}, \dots, x_{n}$ as in Row insertion and the bumping route. Two permutations $x, y \in S_{n}$ are Knuth equivalent, written $x \sim_{K} y$ , if a finite sequence of elementary Knuth moves transforms $x$ into $y$ ; a sequence of length zero is allowed. They are dual Knuth equivalent, written $x \sim_{d K} y$ , if and only if $x^{- 1} \sim_{K} y^{- 1}$ . The relation $\sim_{K}$ is an equivalence relation because length-zero sequences give reflexivity, each move is reversible, and move sequences concatenate. Since inversion is a bijection of $S_{n}$ , $\sim_{d K}$ is also an equivalence relation. Each elementary Knuth move preserves $P$ ; more precisely, two permutations are Knuth equivalent if and only if their insertion tableaux agree, as proved in Knuth classes are the fibers of the insertion tableau ↗.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Knuth classes are the fibers of the insertion tableau

Facts & Assumptions

Given: $n \geq 1$ , permutations $x, y \in S_{n}$ in one-line notation, their iterated row-insertion tableaux $P (x), P (y)$ and recording tableaux $Q (x), Q (y)$ .

[F1]

Knuth equivalence is generated by reversible contiguous moves $b c a \leftrightarrow b a c$ and $c a b \leftrightarrow a c b$ for distinct $a < b < c$ ; dual Knuth equivalence is defined by $x \sim_{d K} y$ iff $x^{- 1} \sim_{K} y^{- 1}$ (Knuth and dual Knuth equivalence for permutations).

[F2]

Row insertion is deterministic; it appends a letter at the right end of the first row in which the letter exceeds every entry, and otherwise replaces the leftmost larger entry and carries that entry to the next row (Row insertion and the bumping route).

[F3]

The RSK map $x \mapsto (P (x), Q (x))$ is a bijection from permutations of ${1, \dots, n}$ to pairs of standard tableaux of common shape (The Robinson-Schensted correspondence).

[F4]

Inversion interchanges the RSK tableaux: $P (x^{- 1}) = Q (x)$ and $Q (x^{- 1}) = P (x)$ (RSK interchanges the insertion and recording tableaux under inversion).

[F5]

Inserting a distinct new letter into a standard tableau produces a standard tableau; its rows and columns remain strictly increasing (Monotonicity of the bumping route and standardness of the output).

Statement

For permutations $x, y \in S_{n}$ with RSK pairs $(P (x), Q (x))$ and $(P (y), Q (y))$ , $x \sim_{K} y$ iff $P (x) = P (y)$ , and $x \sim_{d K} y$ iff $Q (x) = Q (y)$ . Thus the Knuth and dual Knuth classes are exactly the insertion- and recording-tableau fibers, and the induced maps from classes to standard tableaux of size $n$ are bijections.

Proof

technique · row-bumping induction and a canonical row-reading word

For intermediate prefixes and row words, write $u \approx_{K} v$ when the same local moves connect two words of distinct letters from ${1, \dots, n}$ ; on words of length $n$ this is exactly $\sim_{K}$ .

1.1F1F2algebra

First row calculation for $c a b \leftrightarrow a c b$ . Let $a < b < c$ be absent from an increasing row $R$ of a tableau. Write a missing bumped letter as $\infty$ , meaning that insertion appends and does nothing in lower rows. Compare inserting $c a b$ with inserting $a c b$ . If inserting $a$ after $c$ does not bump that newly inserted $c$ , let $d$ be the old entry bumped by $a$ , $z$ the entry bumped by $c$ , and $q$ the last entry bumped by $b$ ; the row ends the same in both orders, the carried words are $z d q$ and $d z q$ , and whenever these are all finite their order is $d < q < z$ . If $a$ does bump the inserted $c$ , let $d, e$ be the first two old entries greater than $c$ (possibly $\infty$ ): the carried words are $d c e$ and $d e c$ , the final row is the same, and when $d, e$ are finite $c < d < e$ . Thus the carried words are equal after null insertions are removed or are related by one of the two Knuth moves.

1.2F1F2algebra

First row calculation for $b a c \leftrightarrow b c a$ . Let $a < b < c$ be absent from $R$ and let $y$ be the old entry first bumped by inserting $b$ , or $\infty$ if there is none. Compare $b a c$ with $b c a$ . If inserting $a$ does not bump the newly inserted $b$ , let $d \in (a, b)$ be the old entry bumped by $a$ and let $z$ be the entry bumped by $c$ (or $\infty$ ); the row ends the same, the carried words are $y d z$ and $y z d$ , and when finite $d < y < z$ . If $a$ bumps $b$ , the carried words are $y b z$ and $y z b$ , with the same final row and, when finite, $b < y < z$ . Deleting null insertions makes the two carried words equal or leaves a Knuth move.

2.1F1F2F5step 1.1step 1.2algebra

A local move preserves insertion into any tableau. Induct on the number of rows of the starting tableau $T$ . Steps 1.1 and 1.2 show that after either local move the first row is identical and the words carried to the remaining rows are equal or differ by a Knuth move; those carried letters are absent from the old lower tableau because all entries and inputs are distinct. By [F5], the intermediate lower tableaux remain standard, so the induction hypothesis applies; if the carried words differ by a move, it makes their insertions into the lower tableau identical, and if they agree, determinism does so. The base case has no lower rows. Therefore inserting either side of either Knuth move into $T$ gives the same resulting tableau. A common suffix of a word then preserves equality because subsequent row insertions are deterministic, so every finite Knuth chain preserves $P$ .

2.2F1F2F5step 1.1step 1.2algebra

One insertion changes the row-reading word by Knuth moves. For a standard tableau $T$ , let $u (T)$ read each row left to right, starting with the bottom row and moving upward. If $x$ appends to the top row, then $u (T) x = u (T \leftarrow x)$ . Otherwise the top row is $y_{1} < \dots < y_{m}$ and $y_{j}$ is the first entry greater than $x$ , so $y_{j - 1} < x < y_{j}$ when $j > 1$ . Starting with $y_{1} \dots y_{m} x$ , move $x$ left across $y_{j + 1}, \dots, y_{m}$ using $b c a \leftrightarrow b a c$ , then move $y_{j}$ left across $y_{j - 1}, \dots, y_{1}$ using $c a b \leftrightarrow a c b$ . This gives $y_{j} y_{1} \dots y_{j - 1} x y_{j + 1} \dots y_{m}$ , the bumped letter followed by the updated top row. By [F5], the lower tableau remains standard after insertion of the bumped letter; induction on its height transforms the lower-row word with that letter into the row-reading word after insertion. Hence $u (T) x \sim_{K} u (T \leftarrow x)$ .

3.1F1F2step 2.2algebra

Every word is equivalent to its tableau’s row word. Induct on the length of a permutation word $w = w^{'} x$ . The empty prefix has the empty tableau and empty row word. If $P (w^{'}) = T$ , the induction hypothesis gives $w^{'} \sim_{K} u (T)$ ; appending the same final letter preserves a chain of local moves, so $w \sim_{K} u (T) x$ . Step 2.2 gives $u (T) x \sim_{K} u (T \leftarrow x) = u (P (w))$ .

4.1F1step 2.1step 3.1algebra

Knuth equivalence iff insertion tableaux agree. If $x \sim_{K} y$ , step 2.1 shows each move in a witnessing finite chain preserves the insertion tableau, so $P (x) = P (y)$ . Conversely, if $P (x) = P (y) = T$ , step 3.1 gives $x \sim_{K} u (T)$ and $y \sim_{K} u (T)$ ; symmetry and transitivity of $\sim_{K}$ give $x \sim_{K} y$ . This proves the first equivalence.

5.1F1F4step 4.1algebra

Dual Knuth equivalence iff recording tableaux agree. By definition and step 4.1, $x \sim_{d K} y$ iff $P (x^{- 1}) = P (y^{- 1})$ . By [F4] this is equivalent to $Q (x) = Q (y)$ , proving the second equivalence.

6.1F1F3step 4.1step 5.1algebra∎

The induced maps on classes are bijections. Steps 4.1 and 5.1 identify Knuth and dual Knuth classes exactly with fibers of $P$ and $Q$ , respectively, so the induced maps are injective. Given any standard tableau $T$ of size $n$ , the pair $(T, T)$ has common shape; by [F3] it is the RSK pair of some permutation, so every such $T$ occurs as both an insertion and a recording tableau. The induced maps are therefore surjective as well. All inductions are on finite words or finite tableaux, and no choice principle is used.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Star operations on strings of adjacent simple reflections

Definition

Let $n \geq 3$ and $1 \leq i \leq n - 2$ , and put $r = s_{i}$ , $t = s_{i + 1}$ . These simple reflections satisfy $(r t)^{3} = 1$ . For $w \in S_{n}$ , let $R (w) : = {s : ℓ (w s) < ℓ (w)}$ be its right descent set, using the one-line convention and inversion length of Permutation Weyl group and inversion length. Define $D_{i} : = {w \in S_{n} : ∣ R (w) \cap {r, t} ∣ = 1} .$

The subgroup $P_{i} : = ⟨ r, t ⟩$ permutes the entries in positions $i, i + 1, i + 2$ . In each right coset $C = w P_{i}$ , let $a < b < c$ be the three entries in those positions, and let $\tilde{w}$ be the unique member whose entries there are $a, b, c$ in increasing order. Then $C$ consists of $\tilde{w}, \tilde{w} r, \tilde{w} t, \tilde{w} r t, \tilde{w} t r, \tilde{w} r t r$ , with lengths $ℓ (\tilde{w}), ℓ (\tilde{w}) + 1, ℓ (\tilde{w}) + 1, ℓ (\tilde{w}) + 2, ℓ (\tilde{w}) + 2, ℓ (\tilde{w}) + 3$ , respectively. Its intersection with $D_{i}$ is the four middle elements.

Right multiplying by $r$ and $t$ swaps the first two and last two block entries; the six words $1, r, t, r t, t r, r t r$ give the six distinct reorderings, so $P_{i} ≅ S_{3}$ and the displayed list exhausts $C$ . Sorting gives the unique member with no internal inversions. Reordering the block does not change the total number of inversions involving a position outside it: an outside position lies either before all three entries or after all three, so its comparisons with the block depend only on the set ${a, b, c}$ . The internal inversion counts of $a b c, b a c, a c b, b c a, c a b, c b a$ are $0, 1, 1, 2, 2, 3$ . Their right descent sets restricted to ${r, t}$ are respectively $\emptyset, {r}, {t}, {t}, {r}, {r, t}$ , so precisely the four length-one and length-two elements lie in $D_{i}$ .

The right star operation $w \mapsto w^{*}$ on $D_{i}$ is defined on each coset by

$w$	$w^{*}$
$\tilde{w} r$	$\tilde{w} r t$
$\tilde{w} r t$	$\tilde{w} r$
$\tilde{w} t$	$\tilde{w} t r$
$\tilde{w} t r$	$\tilde{w} t$

Thus $w \mapsto w^{*}$ is an involution of $D_{i}$ . The left star operation is $^{*} w : = ((w^{- 1})^{*})^{- 1}$ on $D_{i}^{- 1} : = {w^{- 1} : w \in D_{i}}$ ; it is also an involution.

In one-line notation, the sorted triple for $\tilde{w}$ is $a b c$ with $a < b < c$ . The four elements of $D_{i}$ have triples $b a c$ , $b c a$ , $a c b$ , $c a b$ , and the right star operation exchanges $b a c \leftrightarrow b c a$ and $a c b \leftrightarrow c a b$ . Hence for every $w \in D_{i}$ , the words $w$ and $w^{*}$ differ by exactly one elementary Knuth move in positions $i, i + 1, i + 2$ as defined in Knuth and dual Knuth equivalence for permutations.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

Star operations are Knuth moves and preserve the relevant cells

Facts & Assumptions

Given: $n \geq 3$ , $1 \leq i \leq n - 2$ , $r = s_{i}$ , $t = s_{i + 1}$ , $W_{I} = ⟨ r, t ⟩ ≅ S_{3}$ , and the corresponding right star operation.

[F1]

Each right coset of $W_{I}$ has a unique shortest representative $\tilde{w}$ ; its six elements have lengths $ℓ (\tilde{w}) + 0, ℓ (\tilde{w}) + 1, ℓ (\tilde{w}) + 1, ℓ (\tilde{w}) + 2, ℓ (\tilde{w}) + 2, ℓ (\tilde{w}) + 3$ , and the star involution pairs $\tilde{w} r \leftrightarrow \tilde{w} r t$ and $\tilde{w} t \leftrightarrow \tilde{w} t r$ . In one-line notation these pairs are $b a c \leftrightarrow b c a$ and $a c b \leftrightarrow c a b$ (Star operations on strings of adjacent simple reflections).

[F2]

A Knuth move preserves the insertion tableau, and Knuth equivalence is exactly equality of insertion tableaux (Knuth classes are the fibers of the insertion tableau).

[F3]

For a simple reflection $s$ , if $s w > w$ then $C_{s} C_{w} = C_{s w} + \sum_{z : s z < z < w} μ (z, w) C_{z}$ , and if $s w < w$ then $C_{s} C_{w} = (v + v^{- 1}) C_{w}$ ; on the right, if $w s > w$ then $C_{w} C_{s} = C_{w s} + \sum_{z s < z < w} μ (z, w) C_{z}$ , and if $w s < w$ then $C_{w} C_{s} = (v + v^{- 1}) C_{w}$ (Multiplication by a generator in the Kazhdan–Lusztig basis).

[F4]

A right coefficient step is a right preorder step, and $x \sim_{R} y$ iff $x^{- 1} \sim_{L} y^{- 1}$ ( $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells).

[F5]

In $C_{w} = \sum_{x \leq w} p_{x, w} H_{x}$ , the coefficients are supported on $x \leq w$ and $p_{w, w} = 1$ ; if $x ⋖ w$ is a Bruhat cover, then $p_{x, w} = v$ (Existence and uniqueness of the Kazhdan–Lusztig basis). The latter follows from the degree-one leading term and parity clauses.

[F6]

For $x \leq y$ , $p_{x, y} = v^{ℓ (y) - ℓ (x)} P_{x, y} (v^{- 2})$ , and for $x < y$ , $μ (x, y)$ is the coefficient of $v$ in $p_{x, y}$ (Kazhdan–Lusztig polynomials in the classical $q$ -normalization).

[F7]

The standard Hecke basis satisfies $H_{s}^{2} = 1 + (v^{- 1} - v) H_{s}$ (The normalized type-A Hecke algebra and its bar involution).

[F8]

Bruhat order on $S_{n}$ has the reduced-subword characterization and is graded by inversion length (Basic properties of the Bruhat order on $S_{n}$ ).

Statement

Let $D_{i}$ and $(-)^{*}$ be as in Star operations on strings of adjacent simple reflections. (a) For $w \in D_{i}$ , $w^{*}$ is obtained from $w$ by one elementary Knuth relation on the letters in positions $i, i + 1, i + 2$ ; in particular $P (w^{*}) = P (w)$ . Put $D_{i j} : = {w \in D_{i} : w s_{i} < w, w s_{i + 1} > w}$ and $D_{j i} : = {w \in D_{i} : w s_{i} > w, w s_{i + 1} < w}$ . The restriction $K_{i j}$ of $(-)^{*}$ is a bijection $D_{i j} \to D_{j i}$ whose inverse is $K_{j i}$ . (b) For every $w \in D_{i}$ , if $a$ and $b$ are the shorter and longer, respectively, of ${w, w^{*}}$ , then $μ (a, b) = 1$ and $w^{*} \sim_{R} w$ ; by inversion, $^{*} w \sim_{L} w$ whenever $w^{- 1} \in D_{i}$ . (c) Inside the rank-two subgroup $W_{I} = ⟨ s_{i}, s_{i + 1} ⟩ ≅ S_{3}$ , every Kazhdan–Lusztig polynomial $P_{x, y}$ with $x \leq y$ is $1$ , and $μ (x, y) = 1$ exactly for Bruhat covers $x ⋖ y$ . For every shortest representative $\tilde{w}$ of a right $W_{I}$ -coset, the ambient pairs $\tilde{w} s_{i} ⋖ \tilde{w} s_{i} s_{i + 1}$ and $\tilde{w} s_{i + 1} ⋖ \tilde{w} s_{i + 1} s_{i}$ therefore also have $μ$ -coefficient $1$ .

Proof

technique · use the explicit $S_3$ star table, compute its rank-two Kazhdan–Lusztig basis, and apply the left/right multiplication formulas to the two directed edges of each star pair

1.1F1F2

Knuth moves and the restricted bijection. In the sorted-coset notation of [F1], the four elements of $D_{i}$ have local triples $b a c, b c a, a c b, c a b$ , and the star table exchanges $b a c \leftrightarrow b c a$ and $a c b \leftrightarrow c a b$ . These are exactly the two elementary Knuth moves, so [F2] gives $P (w^{*}) = P (w)$ . The right descent of each pair is exchanged between $s_{i}$ and $s_{i + 1}$ ; hence $(-)^{*}$ maps $D_{i j}$ to $D_{j i}$ . Since $(-)^{*}$ is an involution, its restriction is a bijection with inverse $K_{j i}$ .

1.2F3F5F6F7F8algebra

The rank-two basis and coefficients. Write $e$ for the identity and $w_{0} = r t r = t r t$ . The six elements of $W_{I}$ are $e, r, t, r t, t r, w_{0}$ , and their Bruhat intervals follow from reduced subwords. Since $e ⋖ r, t$ , the support and diagonal clauses of [F5] give $C_{r} = H_{r} + v$ and $C_{t} = H_{t} + v$ . For $C_{r} C_{t}$ , the left multiplication formula has no correction term: $[e, t] = {e, t}$ and $r e = r > e$ . Similarly, $C_{t} C_{r}$ has no correction term because $[e, r] = {e, r}$ and $t e = t > e$ . Thus $C_{r t} = C_{r} C_{t}$ and $C_{t r} = C_{t} C_{r}$ ; expanding with [F7] gives $C_{r t} = H_{r t} + v (H_{r} + H_{t}) + v^{2} H_{e}$ and $C_{t r} = H_{t r} + v (H_{r} + H_{t}) + v^{2} H_{e}$ . The interval $[e, t r)$ consists of $e, t, r$ , and only $r$ satisfies $r z < z$ there; since $r ⋖ t r$ , [F5]–[F6] give $μ (r, t r) = 1$ . Thus $C_{w_{0}} = C_{r} C_{t r} - C_{r} = H_{w_{0}} + v (H_{r t} + H_{t r}) + v^{2} (H_{r} + H_{t}) + v^{3} H_{e}$ . Comparing these six expansions with $p_{x, y} = v^{ℓ (y) - ℓ (x)} P_{x, y} (v^{- 2})$ shows $P_{x, y} = 1$ for every $x \leq y$ in $W_{I}$ . For such pairs the coefficient of $v$ in $p_{x, y} = v^{ℓ (y) - ℓ (x)}$ is $1$ exactly when the length difference is $1$ , i.e. exactly on covers.

1.3F1F5F6F8

Ambient star-pair coefficients. The lengths in [F1] show that each of $\tilde{w} r ⋖ \tilde{w} r t$ and $\tilde{w} t ⋖ \tilde{w} t r$ is an ambient Bruhat cover: the upper element is the lower element multiplied on the right by one simple reflection and its length increases by one. Thus [F5]–[F6] give $μ (\tilde{w} r, \tilde{w} r t) = μ (\tilde{w} t, \tilde{w} t r) = 1$ . These are precisely the shorter-to-longer star-pair coefficients, so the Statement's coefficient claim holds for either choice of $w$ .

2.1F1F3F4step 1.3

Right-cell equivalence. Since the claim is symmetric in the star pair, take its shorter member $w$ . By [F1], either $w = \tilde{w} r$ and $w^{*} = w t = \tilde{w} r t$ , or $w = \tilde{w} t$ and $w^{*} = w r = \tilde{w} t r$ . In the first case [F3] gives a coefficient- $1$ right step from $w$ to $w^{*}$ ; also $w^{*} r = \tilde{w} r t r$ has length $ℓ (\tilde{w}) + 3$ , whereas $w r = \tilde{w}$ , so the right-ascent formula for $C_{w^{*}} C_{r}$ contains $C_{w}$ with coefficient $μ (w, w^{*}) = 1$ by step 1.3. In the second case the coefficient- $1$ step comes from $C_{w} C_{r}$ , and $w^{*} t = \tilde{w} t r t$ has length $ℓ (\tilde{w}) + 3$ while $w t = \tilde{w}$ , so $C_{w^{*}} C_{t}$ contains $C_{w}$ with coefficient $μ (w, w^{*}) = 1$ . Each case therefore gives both $w^{*} \leq_{R} w$ and $w \leq_{R} w^{*}$ , proving $w^{*} \sim_{R} w$ .

3.1F1F4step 2.1∎

The dual statement. For $w^{- 1} \in D_{i}$ , step 2.1 gives $(w^{- 1})^{*} \sim_{R} w^{- 1}$ . Inverting this equivalence by [F4] yields $^{*} w = ((w^{- 1})^{*})^{- 1} \sim_{L} w$ .

Remarks

The original scaffold's proposed identity $C_{\tilde{w} u} = \sum_{t \leq u} v^{ℓ (u) - ℓ (t)} H_{\tilde{w} t}$ for an arbitrary shortest right-coset representative is false: with $n = 4$ , $W_{I} = ⟨ s_{1}, s_{2} ⟩$ , $\tilde{w} = s_{3}$ , and $u = s_{2}$ , the left side is $H_{s_{3} s_{2}} + v H_{s_{3}} + v H_{s_{2}} + v^{2} H_{e}$ , whereas the displayed coset sum omits $v H_{s_{2}} + v^{2} H_{e}$ . The rank-two claim is stated for the subgroup itself, and the ambient star-pair coefficients follow separately from the cover property.

The star-pair and cell arguments use the locally proved multiplication formula, cover coefficient and inversion-of-cells clauses. Coefficientwise positivity is not required. No Choice is used.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

$μ$ -edges and left equivalence are transported by star operations

Facts & Assumptions

Given: $n \geq 3$ , adjacent simple reflections $s = s_{i}$ , $t = s_{i + 1}$ , the right star domain $D_{i}$ , and $D_{i j}, D_{j i}, K_{i j}$ as defined in Star operations are Knuth moves and preserve the relevant cells.

[F1]

The rank-two right cosets have six elements with relative lengths $0, 1, 1, 2, 2, 3$ . The domain $D_{i}$ consists of the four middle elements, and the star involution exchanges the two adjacent pairs; its restriction $K_{i j} : D_{i j} \to D_{j i}$ is a bijection with inverse $K_{j i}$ (Star operations are Knuth moves and preserve the relevant cells, Star operations on strings of adjacent simple reflections).

[F2]

Write $C_{w} = {\underline{H}}_{w} = \sum_{a \leq w} p_{a, w} H_{a}$ . For $a < w$ , $p_{a, w} \in v Z [v]$ has fixed parity $ℓ (w) - ℓ (a)$ , and $μ (a, w)$ is its coefficient of $v$ ; $μ (a ∣ w) \neq 0$ means that one of the two comparable orientations has nonzero coefficient (Existence and uniqueness of the Kazhdan–Lusztig basis, Kazhdan–Lusztig polynomials in the classical $q$ -normalization).

[F3]

If $b s < b$ , the right-descent polynomial recursion in The Kazhdan–Lusztig polynomial descent recursion applies to every $a \leq b$ , with coefficients $p_{a, b} = v^{ℓ (b) - ℓ (a)} P_{a, b} (v^{- 2})$ and $μ$ as in [F2].

[F4]

If $b s < b$ , the multiplication formula gives $C_{b} C_{s} = (v + v^{- 1}) C_{b}$ ; since [F2, F5] give $C_{s} = H_{s} + v$ , this yields $C_{b} H_{s} = v^{- 1} C_{b}$ . The same multiplication formula gives every simple-generator coefficient in $C_{s} C_{b}$ , and for an off-diagonal left step $a \leftarrow_{L} b$ the cell supplier gives $R (b) \subseteq R (a)$ (Multiplication by a generator in the Kazhdan–Lusztig basis, $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells).

[F5]

Every Bruhat cover $a ⋖ b$ has $p_{a, b} = v$ and hence $μ (a, b) = 1$ ; Bruhat order is graded, has the simple-reflection lifting properties, and is inversion invariant (Existence and uniqueness of the Kazhdan–Lusztig basis, Kazhdan–Lusztig polynomials in the classical $q$ -normalization, Basic properties of the Bruhat order on $S_{n}$ ).

[F6]

The $H_{s}$ generate the algebra, and the standard basis satisfies $H_{w} H_{s} = H_{w s}$ when $w s > w$ and $H_{w} H_{s} = H_{w s} + (v^{- 1} - v) H_{w}$ when $w s < w$ (The normalized type-A Hecke algebra and its bar involution).

[F7]

For every $w \in D_{i}$ , $w \sim_{R} w^{*}$ , and the star map preserves its right-coset domain and is involutive (Star operations are Knuth moves and preserve the relevant cells).

Statement

Fix $i$ , let $D_{i j}, D_{j i}, K_{i j}$ be as in Star operations are Knuth moves and preserve the relevant cells, and write $μ (u ∣ v)$ for $μ (u, v)$ if $u < v$ , for $μ (v, u)$ if $v < u$ , and for $0$ otherwise, so its nonzero predicate agrees with Kazhdan–Lusztig polynomials in the classical $q$ -normalization. (a) Edge transport. For $y, w \in D_{i j}$ with $y \neq w$ and $μ (y ∣ w) \neq 0$ one has $μ (K_{i j} (y) ∣ K_{i j} (w)) \neq 0$ , and in fact the transported leading coefficients agree: $μ (K_{i j} (y) ∣ K_{i j} (w)) = μ (y ∣ w)$ , the transported pair being taken in the Bruhat order in which it is comparable. (b) Transport of the preorder. For $x, y \in D_{i j}$ : $x \leq_{L} y ⟺ K_{i j} (x) \leq_{L} K_{i j} (y)$ and $x \leq_{R} y ⟺ K_{i j} (x) \leq_{R} K_{i j} (y)$ ; in particular $x \sim_{L} y ⟺ K_{i j} (x) \sim_{L} K_{i j} (y)$ and $x \sim_{R} y ⟺ K_{i j} (x) \sim_{R} K_{i j} (y)$ .

Proof

technique · compare constant terms of the right-recursion polynomials on the two star strings, then transport finite generator-coefficient chains

1.1F2F3F4algebra

Recursion notation and mixed descents. For $a < b$ put $π_{a, b} : = p_{a, b} / v$ , put $π_{a, a} : = v^{- 1}$ , and put $π_{a, b} : = 0$ if $a \leq̸ b$ ; then $π_{a, b} \in Z [v]$ and $π_{a, b} (0) = μ (a, b)$ . If $a < b$ , $a s > a$ , and $b s < b$ , coefficient comparison in $C_{b} H_{s} = v^{- 1} C_{b}$ gives $p_{a, b} = v p_{a s, b}$ , hence $π_{a, b} = v π_{a s, b}$ ; therefore $μ (a, b) = 0$ unless $a s = b$ , when it is $1$ . The right recursion from [F3], when $a s < a$ , $b s < b$ , and $a \neq b s$ , reads $π_{a, b} = π_{a s, b s} + (π_{a, b s} - μ (a, b s)) / v - \sum_{a < z < b s, z s < z} μ (z, b s) π_{a, z}$ . In particular, if $a \leq̸ b s$ , it gives $π_{a, b} = π_{a s, b s}$ .

1.2F1F5algebra

Pairs in one right coset. A right $⟨ s, t ⟩$ -coset meets $D_{i j}$ in two elements; the rank-two table shows these form a Bruhat cover, and their two star images form a Bruhat cover as well. By [F5], the $μ$ -coefficient is $1$ for both pairs. This proves (a) when $y, w$ belong to the same right coset.

1.3F1F2F4F5F6algebra

Left-preorder transport. Let $I_{s}$ (respectively $I_{t}$ ) be the $A$ -span of the $C_{w}$ with $w s < w$ (respectively $w t < w$ ), and put $J = I_{s} \cap I_{t}$ . For each simple reflection $r$ , if $r w < w$ then $C_{r} C_{w} = (v + v^{- 1}) C_{w}$ ; if $r w > w$ , the multiplication formula expresses $C_{r} C_{w}$ as $C_{r w}$ plus lower terms $C_{z}$ that are nonzero off-diagonal left steps. In the second case the leading term is itself a left step. By [F4], every such step preserves each right descent of $w$ , so $I_{s}$ and $I_{t}$ are stable under left multiplication by each $C_{r}$ . Since $i d < r$ is a Bruhat cover, [F2, F5] give $C_{r} = H_{r} + v$ ; [F6] says the $H_{r}$ generate the algebra, so $I_{s}$ and $I_{t}$ are left ideals. By the basis property in [F2], $J$ is spanned by elements with both descents, and the quotient bases of $I_{s} / J$ and $I_{t} / J$ are indexed by $D_{i j}$ and $D_{j i}$ . Right multiplication by $C_{t}$ maps $I_{s}$ into $I_{t}$ by the right multiplication formula in [F4], and maps $J$ into $J$ because $C_{w} C_{t} = (v + v^{- 1}) C_{w}$ for every both-descent basis vector; it is left-linear by associativity and induces $f : I_{s} / J \to I_{t} / J$ . For $x s < x$ , [F4] and $C_{s} = H_{s} + v$ from [F2, F5] give $C_{x} H_{s} = v^{- 1} C_{x}$ . If also $z s > z$ , comparison of the $H_{z}$ coefficients using [F6] gives $p_{z, x} = v p_{z s, x}$ . If $z s = x$ , then $z = x s$ and $μ (z, x) = 1$ ; if $z s < x$ , the right side lies in $v^{2} Z [v]$ and $μ (z, x) = 0$ ; if $z s \leq̸ x$ , both coefficients vanish by support. Thus in this mixed-descent situation $μ (z, x)$ can be nonzero only for $z = x s$ . In a right $⟨ s, t ⟩$ -coset with shortest representative $\tilde{w}$ , its two $D_{i j}$ elements are $x = \tilde{w} s$ and $x = \tilde{w} t s$ . For $x = \tilde{w} s$ , the right-ascent formula for $C_{x} C_{t}$ has leading term $C_{x t} = C_{\tilde{w} s t}$ . A correction index surviving modulo $J$ has $z s > z$ , so the mixed-descent identity forces $z = x s = \tilde{w}$ . But $\tilde{w} t > \tilde{w}$ , contradicting the condition $z t < z$ on correction indices; hence no correction survives and $f ([C_{x}]) = [C_{x^{*}}]$ . For $x = \tilde{w} t s$ , the leading term $C_{x t}$ has both descents and dies in $J$ ; any correction surviving modulo $J$ must have $z s > z$ , so the identity forces $z = x s = \tilde{w} t = x^{*}$ , with coefficient $1$ because $x^{*} s = x$ is a Bruhat cover. Thus again $f ([C_{x}]) = [C_{x^{*}}]$ . Exchanging $s, t$ gives the left-linear map $g : I_{t} / J \to I_{s} / J$ induced by right multiplication by $C_{s}$ ; it is well-defined since $C_{w} C_{s} = (v + v^{- 1}) C_{w}$ on $J$ , and the exchanged two-case table sends each quotient basis vector to its star. Thus $g f$ and $f g$ fix every quotient basis vector, so these maps are inverse. Hence for every simple $r$ and $x, z \in D_{i j}$ , left-linearity and comparison in the quotient bases give equality between the coefficient of $C_{z}$ in $C_{r} C_{x}$ and that of $C_{z^{*}}$ in $C_{r} C_{x^{*}}$ . Along a left-preorder chain $x = w_{0} \leftarrow_{L} \dots \leftarrow_{L} w_{m} = y$ with endpoints in $D_{i j}$ , [F4] gives $R (y) \subseteq R (w_{k}) \subseteq R (x)$ , so every intermediate has the same singleton descent set on ${s, t}$ . In particular $J$ is an absorbing left ideal: a step cannot enter both descents and then return to $D_{i j}$ . The chain stays in $D_{i j}$ and the coefficient equality transports every step; diagonal steps and zero-length chains transport as well. Applying $g$ gives the converse. Thus $x \leq_{L} y$ iff $K_{i j} (x) \leq_{L} K_{i j} (y)$ . This argument uses support and nonzero coefficients only, not positivity or Choice.

1.4F1F7algebra

Right-preorder transport. By [F7], $K_{i j} (x) \leq_{R} x$ and $y \leq_{R} K_{i j} (y)$ , so transitivity gives $x \leq_{R} y \Rightarrow K_{i j} (x) \leq_{R} K_{i j} (y)$ . Applying the same implication to the inverse star $K_{j i}$ gives the converse.

2.1F1F2F3F4F5algebra

Different cosets, stars moving by the same simple reflection. Let $a < b$ be a comparable pair with odd length difference in distinct right cosets. Suppose both stars move down by the same simple reflection, $a^{*} = a s < a$ and $b^{*} = b s < b$ . If $a \leq̸ b s$ , step 1.1 gives $π_{a, b} = π_{a s, b s}$ . Otherwise $a < b s$ because the cosets differ. Parity gives $μ (a, b s) = 0$ , and the right recursion gives $π_{a, b} \equiv π_{a s, b s} + π_{a t, b s} - \sum_{a < z < b s, z s < z} μ (z, b s) μ (a, z) (m o d v) .$ Here $b s t < b s$ and $a t > a$ , so mixed descent gives $π_{a, b s} / v = π_{a t, b s}$ . Bruhat lifting gives $a t \leq b s$ ; distinct cosets make the inequality strict. The rank-two table gives $a t s < a t$ . The only summand with nonzero constant term is $z = a t$ : if a summand has $z t > z$ , mixed descent for $μ (z, b s)$ forces $z = b s t$ , which has $z s > z$ and is excluded; hence $z t < z$ , and mixed descent for $μ (a, z)$ then forces $z = a t$ . Since $a ⋖ a t$ , $μ (a, a t) = 1$ , so this constant-term summand cancels $π_{a t, b s} (0)$ . Thus $μ (a, b) = μ (a s, b s)$ . If both stars move up by the same simple reflection, apply this calculation to the starred pair and use involutivity. When the common star multiplier gives opposite directions, mixed descent using the other generator rules out a nonzero coefficient, since each element of $D_{i j}$ has exactly one of the two right descents. These are the same-multiplier cases of Casselman's two-case calculation.

3.1step 1.2step 2.1F1F2F3F4F5algebrastep 1.1

Different cosets, stars moving in opposite directions. Take elements $a, b$ in distinct cosets with $a^{*} = a s < a$ and $b^{*} = b t > b$ , without initially assuming $a < b$ ; coefficients outside Bruhat order are zero. We prove equality whenever either $μ (a, b)$ or $μ (a s, b t)$ is nonzero. The rank-two table gives $b s < b < b t < b t s$ and $a s t < a s < a < a t$ , with $a s t s > a s t$ and $b s t > b s$ . If either $μ (a, b)$ or $μ (a s, b t)$ is nonzero, then $a s \leq b$ : this is immediate from $a < b$ in the first case; in the second, if $a s \leq̸ b$ , step 1.1 with right descent $t$ gives $π_{a s, b t} = π_{a s t, b}$ , whose constant term is zero by mixed descent with $s$ , because $a s t s$ lies in $a$ 's right coset while $b$ lies in a different one. Since $a s \leq b$ and $a s s = a > a s$ while $b s < b$ , Bruhat lifting also gives $a \leq b$ ; equality is excluded by the distinct cosets. Either nonzero coefficient makes $ℓ (b) - ℓ (a)$ odd, since the two coefficient length differences differ by $2$ . Thus $ℓ (b) - ℓ (a s)$ is even, so $μ (a s, b) = 0$ , and mixed descent gives $π_{a s, b} = v π_{a, b}$ . The recursion of step 1.1 applied to $(a s, b t)$ gives $π_{a s, b t} = π_{a s t, b} + π_{a s, b} / v - \sum_{a s < z < b, z t < z} μ (z, b) π_{a s, z},$ hence modulo $v$ it is $π_{a s t, b} + π_{a, b} - \sum μ (z, b) μ (a s, z)$ . This polynomial sum need not be empty, but its constant-term sum is zero. Indeed, if $μ (z, b) \neq 0$ , mixed descent with $s$ forces $z s < z$ unless $z = b s$ ; that exception has $b s t > b s$ , contrary to $z t < z$ . If also $μ (a s, z) \neq 0$ , mixed descent with $s$ and $a s s > a s$ forces $z = a$ , but $a t > a$ , again contrary to $z t < z$ . Also $μ (a s t, b) = 0$ : $a s t s > a s t$ , $b s < b$ , and equality $a s t s = b$ would put $a$ and $b$ in the same right coset. Thus $π_{a s, b t} (0) = π_{a, b} (0)$ . If neither coefficient is nonzero the equality is immediate; if either is nonzero this calculation proves the other is equal and nonzero. For the remaining original arrangement $a^{*} = a t > a$ , $b^{*} = b s < b$ , apply the same calculation with $s, t$ exchanged to $A = a t$ and $B = b s$ . These satisfy $A^{*} = A t = a < A$ and $B^{*} = B s = b > B$ in distinct cosets. Its conditional nonzero hypothesis is precisely that either $μ (a t, b s)$ or $μ (a, b)$ is nonzero, so the calculation establishes their equality and the required comparability even if $a t \leq b s$ was not initially known. If both vanish there is no edge to transport. Together with steps 1.2 and 2.1 this proves (a), including the symmetric convention for comparable orientations.

4.1step 1.3step 1.4step 3.1∎

Cell equivalences. The left and right cell equivalences are mutual comparability. The left-preorder iff in step 1.3 and the right-preorder iff in step 1.4 therefore give both cell iff statements in (b); with (a) proved in step 3.1, all claims of the Statement follow.

Remarks

The coefficient calculation in (a) follows Casselman, Theorem 6.2; its complete proof is at Proposition 4.4 and Corollary 4.5, printed p. 7; §§5.2–5.3, printed pp. 8–9; and Theorem 6.2, printed pp. 11–13. The right-recursion equations and mixed-descent vanishing were checked against the current normalized suppliers. Ariki, Proposition 3.6, supplies nonvanishing transport but not by itself the coefficient-equality proof.

This proof uses only the locally proved basis, parity, and Bruhat-cover coefficient clauses of Existence and uniqueness of the Kazhdan–Lusztig basis. The positivity clause and its authorized original-source fallback are unused. The quotient-module transport argument uses coefficient supports and nonzero edges, without $p$ -canonical bases or a sign assumption. No Choice is used.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Equal insertion or recording tableaux imply right or left equivalence

Facts & Assumptions

Given: $n \geq 1$ , permutations $x, y \in S_{n}$ , their insertion tableaux $P (x), P (y)$ , recording tableaux $Q (x), Q (y)$ , and the Kazhdan–Lusztig cell preorders.

[F1]

Knuth equivalence satisfies $x \sim_{K} y$ iff $P (x) = P (y)$ , and dual Knuth equivalence satisfies $x \sim_{d K} y$ iff $Q (x) = Q (y)$ (Knuth classes are the fibers of the insertion tableau).

[F2]

The star table exchanges exactly the four local triples in the two elementary Knuth relations; thus every elementary Knuth move is a right star pair, and each such pair satisfies $w^{*} \sim_{R} w$ (Star operations on strings of adjacent simple reflections, Star operations are Knuth moves and preserve the relevant cells).

[F3]

RSK is symmetric under inversion: $P (w^{- 1}) = Q (w)$ and $Q (w^{- 1}) = P (w)$ (RSK interchanges the insertion and recording tableaux under inversion).

[F4]

Inversion transports cell relations: $a \sim_{L} b$ iff $a^{- 1} \sim_{R} b^{- 1}$ ( $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells).

Statement

For $x, y \in S_{n}$ : (a) $P (x) = P (y) \Rightarrow x \sim_{R} y$ ; (b) $Q (x) = Q (y) \Rightarrow x \sim_{L} y$ . Equivalently, each Knuth class lies in a single right cell and each dual Knuth class lies in a single left cell.

Proof

technique · join equal-tableau permutations by elementary Knuth moves and transport the resulting cell equivalence through inversion

1.1F1F2algebra

Insertion tableaux give right-cell equivalence. Suppose $P (x) = P (y)$ . By [F1], $x \sim_{K} y$ , so there is a finite chain $x = w_{0}, \dots, w_{m} = y$ whose successive terms differ by an elementary Knuth move. By [F2], each adjacent pair satisfies $w_{k} \sim_{R} w_{k + 1}$ ; transitivity of the right-cell equivalence gives $x \sim_{R} y$ . If the chain has length zero, reflexivity gives the same conclusion.

2.1F3F4step 1.1algebra

Recording tableaux give left-cell equivalence. Suppose $Q (x) = Q (y)$ . By [F3], $P (x^{- 1}) = Q (x) = Q (y) = P (y^{- 1})$ , so step 1.1 applied to $x^{- 1}, y^{- 1}$ gives $x^{- 1} \sim_{R} y^{- 1}$ . Inverting this cell equivalence by [F4] yields $x \sim_{L} y$ .

3.1F1step 1.1step 2.1∎

Class formulation. By [F1], every pair in a Knuth class has equal insertion tableaux, so step 1.1 puts the whole class in one right cell. Every pair in a dual Knuth class has equal recording tableaux, so step 2.1 puts that class in one left cell. These are exactly the two equivalent class statements.

Remarks

The finite Knuth chains use the locally proved star-pair right-cell equivalence; recording-tableau equality is transported through inversion of cells. Coefficientwise positivity is not required.

No choice principle is used.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Left equivalence forces equality of recording tableaux in type A

Facts & Assumptions

Given: $n \geq 1$ , permutations $x, y \in S_{n}$ in one-line notation, their RSK tableaux $P (x), Q (x), P (y), Q (y)$ , and the left and right Kazhdan–Lusztig cells.

[F1]

The RSK map is a bijection from permutations in one-line notation to pairs of standard tableaux of the same shape (The Robinson-Schensted correspondence).

[F2]

Knuth equivalence is exactly equality of insertion tableaux; every equality of insertion tableaux is connected by a finite chain of elementary Knuth moves (Knuth classes are the fibers of the insertion tableau).

[F3]

Each elementary Knuth move is a right star operation on its domain, whose domain is determined by the right descents at the two adjacent simple reflections (Star operations on strings of adjacent simple reflections, Star operations are Knuth moves and preserve the relevant cells).

[F4]

If $u, v \in D_{i j}$ , then $u \sim_{L} v ⟺ K_{i j} (u) \sim_{L} K_{i j} (v)$ ; the same equivalence holds on $D_{j i}$ for the inverse $K_{j i}$ , by applying the $D_{i j}$ equivalence to the starred pair ( $μ$ -edges and left equivalence are transported by star operations).

[F5]

The right descent set is constant on a left cell, and the RSK pair of a permutation is unique for that permutation ( $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells, The Robinson-Schensted correspondence).

[F6]

In row insertion, label $k$ in the recording tableau is in the box added when the $k$ th letter is inserted (Row insertion and the bumping route, The recording tableau is standard).

[F7]

Row insertion replaces the leftmost entry greater than the carried letter, carries the displaced entry to the next row, and otherwise appends at the right end of the row (Row insertion and the bumping route).

[F8]

For a one-line permutation $w = w_{1} \dots w_{n}$ , $s_{k} \in R (w)$ iff $w_{k} > w_{k + 1}$ , since swapping adjacent positions changes only that inversion (Permutation Weyl group and inversion length).

[F9]

Standard tableaux have strictly increasing rows and columns, and their shapes are Young diagrams with weakly decreasing row lengths and column lengths (Tableaux and standard tableaux, Partitions, English diagrams, and conjugation).

[F10]

Inserting a distinct new letter into a standard tableau terminates at an addable node and produces a standard tableau of the enlarged Young shape; the bumped letters strictly increase (Monotonicity of the bumping route and standardness of the output).

Statement

For $x, y \in S_{n}$ , $x \sim_{L} y \Rightarrow Q (x) = Q (y)$ .

Proof

technique · replace the tableaux by column-superstandard insertion tableaux, transport Knuth paths through left cells, and compare the column lengths

1.1givenF6F7F8F10algebra

Recording descents match permutation descents. For a standard tableau $U$ , define $Des (U) : = {k : {row}_{U} (k + 1) > {row}_{U} (k)}$ . Let $a = w_{k}$ , $b = w_{k + 1}$ and $T = P_{k - 1}$ ; both letters are absent from $T$ . By [F10], $T$ and $T \leftarrow a$ have strictly increasing rows, and the route for $a$ has increasing carried letters. Inserting $a$ follows rows $1$ through $m$ : write $a_{1} = a$ , and for $i < m$ let $p_{i}$ be the position where $a_{i}$ bumps the old entry $a_{i + 1}$ ; in row $m$ it appends $a_{m}$ at position $p_{m}$ . Let $b_{i}$ and $q_{i}$ be the corresponding carried letters and positions when $b$ is inserted into $T \leftarrow a$ . If $b > a$ , then $b_{1} > a_{1}$ . Whenever this route reaches row $i < m$ with $b_{i} > a_{i}$ , every entry left of $p_{i}$ in the current row is $< a_{i}$ , and the entry at $p_{i}$ is $a_{i}$ ; thus $b$ either appends and stops in that row or bumps at a position $q_{i} > p_{i}$ . In the latter case row strictness gives $b_{i + 1} > a_{i + 1}$ . If it reaches row $m$ , then $b_{m} > a_{m}$ , so it appends at $p_{m} + 1$ ; in all cases its new box is in a row at most $m$ . If $b < a$ , then $b_{1} < a_{1}$ . Whenever the route reaches row $i < m$ with $b_{i} < a_{i}$ , the entry at $p_{i}$ is $a_{i} > b_{i}$ , so it bumps at $q_{i} \leq p_{i}$ . If $q_{i} < p_{i}$ , the old entry there is $< a_{i + 1}$ ; if $q_{i} = p_{i}$ , it bumps $a_{i} < a_{i + 1}$ . Hence $b_{i + 1} < a_{i + 1}$ and it reaches row $m$ . There $a_{m}$ was appended at $p_{m}$ , so $b_{m} < a_{m}$ makes it bump at or before $p_{m}$ and continue to a lower row. Thus the box for $b$ is strictly below the box for $a$ exactly when $b < a$ . By [F6], these are the boxes carrying $k + 1$ and $k$ in $Q (w)$ ; by [F8], $b < a$ is equivalent to $s_{k} \in R (w)$ . Therefore $Des (Q (w)) = {k : s_{k} \in R (w)}$ .

1.2F1F5F7F9F10algebra

The column-superstandard word. Let $λ$ have column lengths $l_{1} \geq \dots \geq l_{m} > 0$ , put $L_{0} = 0$ and $L_{j} = l_{1} + \dots + l_{j}$ , and let $P_{λ}$ fill column $j$ from top to bottom with $L_{j - 1} + 1, \dots, L_{j}$ . The word $ω_{λ} = (L_{1}, \dots, 1, L_{2}, \dots, L_{1} + 1, \dots, L_{m}, \dots, L_{m - 1} + 1)$ has RSK pair $(P_{λ}, P_{λ})$ . Indeed the first decreasing block inserts as a column. Each later block has entries larger than all preceding blocks; its largest entry appends at the end of the first row, and each subsequent smaller entry bumps the preceding new-column entry down one row, where it appends after the entries from earlier blocks. Thus block $j$ fills column $j$ with $L_{j - 1} + 1, \dots, L_{j}$ from top to bottom, and the recording labels fill that column in increasing order. By [F1], $ω_{λ}$ is the unique permutation with pair $(P_{λ}, P_{λ})$ . Its right descent positions are precisely the positions inside its decreasing blocks, with ascents at $L_{1}, \dots, L_{m - 1}$ .

1.3F9algebra

The descent set determines the tableau of this fixed shape. Let $U$ be a standard tableau of shape $λ$ , and put $D_{λ} : = {1, \dots, n - 1} ∖ {L_{1}, \dots, L_{m - 1}} = Des (P_{λ})$ . Suppose $Des (U) = D_{λ}$ . The cells carrying labels at most $k$ form a Young diagram contained in $λ$ , since every cell to the left or above a cell has a smaller entry; the next label occupies an addable node of that prefix. Induct on the columns. Label $1$ occupies $(1, 1)$ . After columns $1, \dots, j - 1$ have been filled to their final heights $l_{1}, \dots, l_{j - 1}$ , no further box can be added to those columns: such a box would lie outside $λ$ . For $j > 1$ , the non-descent at $L_{j - 1}$ requires label $L_{j - 1} + 1$ to lie in a row at most $l_{j - 1}$ ; every such row of the prefix has length $j - 1$ , and the Young-prefix condition makes $(1, j)$ its only addable node in those rows. Thus column $j$ starts at its top. Suppose its first $r < l_{j}$ entries have filled rows $1, \dots, r$ . The next label is an internal descent, so its row is strictly greater than $r$ . Earlier columns cannot grow, while an addable node in a later column would be in row one and hence cannot be a descent. In column $j$ , skipping row $r + 1$ would violate the Young-prefix condition, so the only possible node is $(r + 1, j)$ , which belongs to $λ$ because $r < l_{j}$ . Therefore column $j$ is filled from top to bottom with $L_{j - 1} + 1, \dots, L_{j}$ . This completes every column and gives $U = P_{λ}$ .

1.4F1F5algebra

Replace by column-superstandard insertion tableaux. Suppose $x \sim_{L} y$ , and let $λ_{1}, λ_{2}$ be the shapes of $Q (x), Q (y)$ . By [F1] there are unique $\hat{x}, \hat{y}$ with RSK pairs $(P_{λ_{1}}, Q (x))$ and $(P_{λ_{2}}, Q (y))$ . Since $Q (\hat{x}) = Q (x)$ and $Q (\hat{y}) = Q (y)$ , the recording-tableau implication of Equal insertion or recording tableaux imply right or left equivalence gives $x \sim_{L} \hat{x}$ and $y \sim_{L} \hat{y}$ , hence $\hat{x} \sim_{L} \hat{y}$ . By [F5], $R (\hat{x}) = R (\hat{y})$ .

2.1F1F2F3F4F5step 1.4algebra

Transport the two Knuth paths. By [F2] and [F1], take a finite Knuth path $\hat{x} \to y^{'}$ with RSK pair $(P_{λ_{1}}, P_{λ_{1}})$ and a finite path $\hat{y} \to w^{''}$ with pair $(P_{λ_{2}}, P_{λ_{2}})$ . Apply the first path's successive star operations also to $\hat{y}$ , obtaining $w^{'}$ , and the second path's operations also to $\hat{x}$ , obtaining $y^{''}$ . These parallel paths are defined at every step: initially the paired elements have equal right descent sets by step 1.4; if one path step is a star on $D_{i j}$ or $D_{j i}$ , [F3] shows the other element is in the same domain, and the transported pair remains left equivalent by [F4]. The left-cell descent property [F5] then keeps their right descent sets equal for the next step. Therefore $y^{'} \sim_{L} w^{'}$ and $y^{''} \sim_{L} w^{''}$ , so $R (y^{'}) = R (w^{'})$ and $R (y^{''}) = R (w^{''})$ . Knuth moves preserve insertion tableaux by [F2], hence $P (w^{'}) = P_{λ_{2}}$ and $P (y^{''}) = P_{λ_{1}}$ .

3.1F1F2F5F7F8F9F10step 1.1step 1.2step 2.1

Compare the column lengths. Write $l_{1}, l_{2}, \dots$ and $l_{1}^{'}, l_{2}^{'}, \dots$ for the column lengths of $λ_{1}$ and $λ_{2}$ , padding both lists by zeros after their final columns. By step 1.2, $y^{'}$ and $w^{''}$ are concatenations of decreasing blocks of lengths $l_{j}$ and $l_{j}^{'}$ , respectively; since $R (y^{'}) = R (w^{'})$ and $R (y^{''}) = R (w^{''})$ , [F8] implies the corresponding position blocks of $w^{'}$ and $y^{''}$ are also decreasing. The first $l_{1}$ letters of $w^{'}$ insert to a column of height $l_{1}$ , so the first column of $P (w^{'}) = P_{λ_{2}}$ has length $l_{1}^{'} \geq l_{1}$ ; the first $l_{1}^{'}$ letters of $y^{''}$ similarly give $l_{1} \geq l_{1}^{'}$ , hence $l_{1} = l_{1}^{'}$ . Inductively suppose $l_{j} = l_{j}^{'}$ for $j < k$ and the first $k - 1$ blocks have filled exactly those first $k - 1$ columns in each partial insertion tableau. Inserting block $k$ of $w^{'}$ cannot add boxes to those columns, whose lengths already equal their final lengths in $P_{λ_{2}}$ . All later columns are empty before that block. Its first new box must be at the top of column $k$ ; each subsequent letter is smaller, so by step 1.1 its new box lies strictly lower, and the Young-diagram condition forces the successive new boxes down column $k$ . Thus $l_{k}^{'} \geq l_{k}$ ; if $l_{k}^{'} = 0 < l_{k}$ , the forced new column would contradict the final shape, so this case is impossible as well. The same argument with $y^{''}$ and target $P_{λ_{1}}$ gives $l_{k} \geq l_{k}^{'}$ , including the case $l_{k} = 0 < l_{k}^{'}$ . Induction yields $λ_{1} = λ_{2} = : λ$ .

4.1F1step 1.1step 1.2step 1.3step 1.4step 3.1∎

Identify the recording tableau and conclude. By step 3.1, $P (w^{'}) = P_{λ}$ and $R (w^{'}) = R (y^{'})$ . The common-shape property in [F1] therefore gives $sh (Q (w^{'})) = sh (P (w^{'})) = λ$ . Step 1.1 gives $Des (Q (w^{'})) = {k : s_{k} \in R (w^{'})} = {k : s_{k} \in R (y^{'})} = Des (P_{λ})$ , since step 1.2 identifies the block descent set with the descent set of $P_{λ}$ . By step 1.3, $Q (w^{'}) = P_{λ}$ . The RSK bijection [F1] then gives $w^{'} = y^{'}$ . The first transported path is a composition of bijective star maps, so equality of its outputs on $\hat{x}, \hat{y}$ implies $\hat{x} = \hat{y}$ . Their recording tableaux are $Q (x), Q (y)$ by construction in step 1.4, whence $Q (x) = Q (y)$ .

Remarks

Ariki's §3.4 proof is the source route. This item proves locally the two facts his compressed argument uses at the end: adjacent descents of the word agree with descent positions in the recording tableau, and among standard tableaux of the same fixed shape, the column-superstandard tableau is determined by its block descent set. The row-insertion route comparison is derived from [F6]–[F8] and [F10], so no separate descent-set supplier is assumed.

The parallel finite Knuth paths use the locally proved star-cell transport and constant right descent sets on left cells. Coefficientwise positivity is not required.

The finite paths and inductions use no choice principle.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Kazhdan–Lusztig cells of type A are classified by RSK tableaux

Facts & Assumptions

Given: An integer $n \geq 1$ , permutations $x, y \in S_{n}$ , their RSK pairs $(P (x), Q (x))$ and $(P (y), Q (y))$ , and the left, right, and two-sided Kazhdan–Lusztig cell relations.

[F1]

The RSK map is a bijection between permutations and pairs of standard tableaux of the same shape (The Robinson-Schensted correspondence).

[F2]

Equality of recording tableaux implies left-cell equivalence, and equality of insertion tableaux implies right-cell equivalence (Equal insertion or recording tableaux imply right or left equivalence).

[F3]

Left-cell equivalence implies equality of recording tableaux (Left equivalence forces equality of recording tableaux in type A).

[F4]

Inversion interchanges left and right cell relations, while RSK interchanges insertion and recording tableaux: $a \sim_{L} b ⟺ a^{- 1} \sim_{R} b^{- 1}$ and $(P (w^{- 1}), Q (w^{- 1})) = (Q (w), P (w))$ ( $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells, RSK interchanges the insertion and recording tableaux under inversion).

[F5]

In Geck's parameter $u$ and original $C_{w}^{'}$ basis, two-sided cell equivalence implies equal Robinson–Schensted shapes (Corollary 5.6(c), printed p.29, forward implication only). His §§2.1–2.3 give $T_{s}^{2} = 1 + (u - u^{- 1}) T_{s}$ , $\overset{ˉ}{u} = u^{- 1}$ , $\overline{T_{s}} = T_{s}^{- 1}$ , and the bar-fixed triangular basis $C_{w}^{'} \in T_{w} + \sum_{z < w} u^{- 1} Z [u^{- 1}] T_{z}$ ; preorders use nonzero coefficients in simple $C^{'}$ -products. This is the single shape-invariance source fact authorized for this item; the Murphy/leading-matrix proof is not a local prerequisite.

[F6]

The two-sided preorder is generated by left- and right-preorder steps, and two-sided cell equivalence means mutual two-sided comparability ( $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells).

[F7]

The local algebra has standard basis $H_{w}$ , relation $H_{s}^{2} = 1 + (v^{- 1} - v) H_{s}$ , bar $\overset{ˉ}{v} = v^{- 1}$ and $\overline{H_{s}} = H_{s}^{- 1}$ , and a unique bar-fixed basis element in $H_{w} + \sum_{z < w} v Z [v] H_{z}$ (The normalized type-A Hecke algebra and its bar involution, The Hecke bar involution is well defined, Existence and uniqueness of the Kazhdan–Lusztig basis).

Statement

For $x, y \in S_{n}$ , with the RSK tableaux $P, Q$ of The Robinson-Schensted correspondence (insertion tableau and recording tableau of the one-line word): $x \sim_{L} y ⟺ Q (x) = Q (y), x \sim_{R} y ⟺ P (x) = P (y), x \sim_{L R} y ⟺ sh (Q (x)) = sh (Q (y)) .$ Here $\sim_{L}, \sim_{R}, \sim_{L R}$ are the cell equivalence relations of $L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells; the chosen convention is displayed: left cells are the fibers of the recording tableau, right cells are the fibers of the insertion tableau, and two-sided cells are the fibers of the shape map (note $sh (P (w)) = sh (Q (w))$ ). Consequently the left cells of $S_{n}$ are in bijection with the standard tableaux of size $n$ , the right cells likewise, and the two-sided cells with the partitions of $n$ .

Proof

technique · use the one-sided classifications, RSK inversion symmetry, and the exact authorized shape-invariance implication after a local normalization comparison

1.1F2F3

Left cells are exactly the $Q$ -fibers. If $x \sim_{L} y$ , [F3] gives $Q (x) = Q (y)$ . Conversely, if $Q (x) = Q (y)$ , [F2] gives $x \sim_{L} y$ .

1.2F1F5F6F7algebra

Normalize and apply the exact shape-invariance fact. Identify Geck's coefficient ring $Z [u^{\pm 1}]$ with $A$ by $u \mapsto v^{- 1}$ . Sending $T_{s}$ to $H_{s}$ preserves the quadratic relation because $u - u^{- 1}$ maps to $v^{- 1} - v$ , and preserves the braid relations. The inverse assignments $v \mapsto u^{- 1}$ and $H_{s} \mapsto T_{s}$ preserve the same relations, so these maps give inverse algebra isomorphisms. Standard reduced-word products correspond, and bar corresponds since it agrees on the coefficient parameter and on every generator by [F5, F7]. The image of $C_{w}^{'}$ is therefore bar-fixed and belongs to $H_{w} + \sum_{z < w} v Z [v] H_{z}$ ; local uniqueness in [F7] identifies it with ${\underline{H}}_{w}$ . Each simple-product coefficient is carried by an injective coefficient-ring isomorphism, so it is nonzero exactly when its image is nonzero. Consequently source and local elementary left and right steps agree, and so do their finite chains, two-sided preorders and mutual two-sided comparability by [F6]. Their RSK convention uses the same insertion and recording tableaux, hence the same common shape as [F1]. If $x \sim_{L R} y$ , the exact forward implication in [F5] now gives $sh (Q (x)) = sh (Q (y))$ . No stronger tableau-dominance assertion is used.

2.1F2F4step 1.1

Right cells are exactly the $P$ -fibers. If $x \sim_{R} y$ , [F4] gives $x^{- 1} \sim_{L} y^{- 1}$ , so step 1.1 gives $Q (x^{- 1}) = Q (y^{- 1})$ and [F4] gives $P (x) = P (y)$ . Conversely, if $P (x) = P (y)$ , [F2] gives $x \sim_{R} y$ .

3.1F1F6step 1.1step 2.1

Equal shape implies two-sided equivalence. Suppose $sh (Q (x)) = sh (Q (y))$ . By [F1], there is a unique permutation $z$ whose RSK pair is $(P (x), Q (y))$ . Then $P (z) = P (x)$ gives $x \sim_{R} z$ by step 2.1, and $Q (z) = Q (y)$ gives $z \sim_{L} y$ by step 1.1. By [F6], these equivalences give chains in both directions using left and right preorder steps, so $x \sim_{L R} y$ .

4.1F1step 1.1step 2.1step 3.1step 1.2∎

Count the cells. For each standard tableau $T$ of size $n$ , fill the boxes of its shape from left to right across each row, starting with the top row, by consecutive integers to obtain a canonical standard tableau $P_{sh (T)}$ . By [F1], the pair $(P_{sh (T)}, T)$ comes from a permutation, so every $Q$ -fiber is nonempty; step 1.1 identifies distinct such fibers with distinct left cells. The same argument with the pair $(T, P_{sh (T)})$ and step 2.1 counts right cells. For every partition $λ ⊢ n$ , [F1] gives a permutation with RSK pair $(P_{λ}, P_{λ})$ , so every shape fiber is nonempty; steps 3.1 and 1.2 identify exactly one two-sided cell for each shape. Hence the stated bijections hold.

Remarks

The scaffold's proposed justification that an elementary two-sided preorder step fixes $P$ or $Q$ is false: the coefficient of $C_{s_{1}}$ in $C_{s_{1}} C_{e}$ is $1$ , so the relation $s_{1} \leftarrow_{L} e$ in $S_{3}$ changes shape from $(3)$ to $(2, 1)$ . This follows from the unit property and the basis multiplication formula Multiplication by a generator in the Kazhdan–Lusztig basis. Step 1.2 instead applies only the exact shape-invariance implication from Geck after identifying the normalizations and elementary coefficient steps locally.

The one-sided classifications, equal-shape converse, counting and normalization/preorder comparison are proved locally. Only two-sided equivalence implies equal shape invokes the owner's original-source fallback recorded in research/frontier-43-complex-representation-15-kl-shape-citation-authorization.json. The generic Murphy/leading-matrix machinery is not proved here. Coefficientwise positivity is not required, and all local constructions are finite and use no Choice.

5 · Examples, counterexamples and false statements

None yet.

Kazhdan–Lusztig Bases, Polynomials, and Cells

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Verma's sign identity over Bruhat intervals

Facts & Assumptions

Statement

Proof

Existence and uniqueness of the Kazhdan–Lusztig basis

Statement

Facts & Assumptions

Proof

Remarks

The Kazhdan–Lusztig polynomial descent recursion

Facts & Assumptions

Statement

Proof

Remarks

The Kazhdan–Lusztig inversion formula

Facts & Assumptions

Statement

Proof

Remarks

LL-, RR- and two-sided Kazhdan–Lusztig preorders and cells

Definition

Facts & Assumptions

Proof

Remarks

Knuth and dual Knuth equivalence for permutations

Definition

Knuth classes are the fibers of the insertion tableau

Facts & Assumptions

Statement

Proof

Star operations on strings of adjacent simple reflections

Definition

Star operations are Knuth moves and preserve the relevant cells

Facts & Assumptions

Statement

Proof

Remarks

μμ-edges and left equivalence are transported by star operations

Facts & Assumptions

Statement

Proof

Remarks

Equal insertion or recording tableaux imply right or left equivalence

Facts & Assumptions

Statement

Proof

Remarks

Left equivalence forces equality of recording tableaux in type A

Facts & Assumptions

Statement

Proof

Remarks

Kazhdan–Lusztig cells of type A are classified by RSK tableaux

Facts & Assumptions

Statement

Proof

Remarks

5 · Examples, counterexamples and false statements

Sources

$L$ -, $R$ - and two-sided Kazhdan–Lusztig preorders and cells

$μ$ -edges and left equivalence are transported by star operations