DefinitionDefinition: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 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.

$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.

Depends on

Used by

Dependency tree · two levels

12 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

G. Lusztig, Hecke Algebras with Unequal Parameters (revised book version, arXiv:math/0208154v2) — §8.1 defines the left, right, and two-sided relations and cells; §§8.4–8.6 prove descent-set monotonicity. The equal-parameter case is translated to this normalization. (standard reference, not scraped)
Susumu Ariki, Robinson–Schensted correspondence and left cells, arXiv:math/9910117 (18 pp.) — type-A Robinson–Schensted and Kazhdan–Lusztig cell conventions. (standard reference, not scraped)
Lars Thorge Jensen, p-Kazhdan–Lusztig Theory (Bonn dissertation 2017/18) — Kazhdan–Lusztig cell and star-operation conventions. (standard reference, not scraped)

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