LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-10-08

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.

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.

Depends on

Used by

Dependency tree · two levels

24 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Susumu Ariki, Robinson–Schensted correspondence and left cells, arXiv:math/9910117 — Definition 3.2, Theorem 3.3, and the complete proof of Lemma 3.4: Knuth moves as star operations and the corresponding cell relation. (standard reference, not scraped)
G. Lusztig, Hecke Algebras with Unequal Parameters (revised version arXiv:math/0208154v2) — Corollary 6.7 and the rank-two equal-parameter calculation in Proposition 7.3. (standard reference, not scraped)
Donald E. Knuth, Permutations, Matrices, and Generalized Young Tableaux, Pacific J. Math. 34 (1970), 709–727 — Theorem 6 and the two local transformations. (standard reference, not scraped)