TheoremStatement: 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.

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.

Depends on

Used by

RSK cells in S₃ and S₄ Example

Dependency tree · two levels

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