[proofplan]
The proof is a dictionary extraction from the type $A$ Kazhdan-Lusztig cell classification. That classification identifies right cells with insertion tableaux and two-sided cells with RSK shapes. The left-cell statement is then obtained either directly from the same classification or by applying inversion and using the [inverse symmetry of the Robinson-Schensted correspondence](/theorems/8437).
[/proofplan]
[step:Apply the type $A$ cell classification to right and two-sided cells]
Let $\operatorname{SYT}_n$ denote the set of standard Young tableaux with $n$ boxes. Define maps
\begin{align*}
P:S_n\to \operatorname{SYT}_n
\end{align*}
and
\begin{align*}
Q:S_n\to \operatorname{SYT}_n
\end{align*}
by sending $w\in S_n$ to the insertion tableau $P(w)$ and recording tableau $Q(w)$ of $\operatorname{RSK}(w)$.
By the earlier theorem [Type A Kazhdan-Lusztig Cell Classification by the Robinson-Schensted Correspondence](/theorems/8471), [citetheorem:8471], the equal-parameter right cell relation satisfies
\begin{align*}
u\sim_R w \iff P(u)=P(w)
\end{align*}
for all $u,w\in S_n$. This cited theorem is the deeper classification result: it identifies the Kazhdan-Lusztig cell equivalence relations themselves, whereas the present theorem only rewrites those equivalences as explicit descriptions of the cells containing a fixed element. Its hypotheses match the present setting because both use the Coxeter system of type $A_{n-1}$ on $S_n$, the equal-parameter Hecke algebra, and the same left/right convention in which the right cell relation is the one classified by equality of insertion tableaux. The same classification also states that the two-sided Kazhdan-Lusztig cell relation is classified by the common RSK shape, hence
\begin{align*}
u\sim_{LR} w \iff \operatorname{shape}(P(u))=\operatorname{shape}(P(w)).
\end{align*}
[guided]
We first isolate exactly what the deep input supplies. The relevant external ingredient is the earlier theorem Type A Kazhdan-Lusztig Cell Classification by the Robinson-Schensted Correspondence, [citetheorem:8471]. Its hypotheses match the present setting: we are working with the symmetric group $S_n$, regarded as the Coxeter group of type $A_{n-1}$, with the equal-parameter Kazhdan-Lusztig left, right, and two-sided cell relations. We also use the same left/right convention as that theorem: in this convention, equality of insertion tableaux classifies the right cell relation, while equality of recording tableaux classifies the left cell relation. Thus the cited result is not being used with a hidden convention change.
Define
\begin{align*}
P:S_n\to \operatorname{SYT}_n
\end{align*}
by sending a permutation $w$ to its insertion tableau under RSK, and define
\begin{align*}
Q:S_n\to \operatorname{SYT}_n
\end{align*}
by sending $w$ to its recording tableau. The classification theorem says, in the left/right convention adopted here, that two permutations lie in the same right Kazhdan-Lusztig cell exactly when their insertion tableaux agree. Therefore, for every $u,w\in S_n$,
\begin{align*}
u\sim_R w \iff P(u)=P(w).
\end{align*}
The same classification theorem also identifies two-sided Kazhdan-Lusztig cells with RSK shapes. Since $P(w)$ and $Q(w)$ always have the same shape under the Robinson-Schensted correspondence, it is enough to write this invariant using $P(w)$. Thus, for every $u,w\in S_n$,
\begin{align*}
u\sim_{LR} w \iff \operatorname{shape}(P(u))=\operatorname{shape}(P(w)).
\end{align*}
This proves the right-cell and two-sided-cell parts of the dictionary.
[/guided]
[/step]
[step:Use inverse symmetry to identify left cells with recording tableaux]
The Kazhdan-Lusztig left and right relations are exchanged by inversion: for $u,w\in S_n$,
\begin{align*}
u\sim_L w \iff u^{-1}\sim_R w^{-1}.
\end{align*}
Applying the right-cell classification from the previous step gives
\begin{align*}
u^{-1}\sim_R w^{-1} \iff P(u^{-1})=P(w^{-1}).
\end{align*}
By the theorem [Inverse Symmetry Exchanges RSK Cells](/theorems/8450), [citetheorem:8450], applied first to $u$ and then to $w$,
\begin{align*}
P(u^{-1})=Q(u)
\end{align*}
and
\begin{align*}
P(w^{-1})=Q(w).
\end{align*}
Combining these equivalences yields
\begin{align*}
u\sim_L w \iff Q(u)=Q(w).
\end{align*}
[guided]
The right-cell part has already been proved, so we convert the left-cell question into a right-cell question by inversion. The Kazhdan-Lusztig left and right preorders are interchanged by the group inverse map $x\mapsto x^{-1}$; therefore, for the two permutations $u,w\in S_n$,
\begin{align*}
u\sim_L w \iff u^{-1}\sim_R w^{-1}.
\end{align*}
Now the right-cell classification from the previous step applies to the pair $u^{-1},w^{-1}\in S_n$. It gives
\begin{align*}
u^{-1}\sim_R w^{-1} \iff P(u^{-1})=P(w^{-1}).
\end{align*}
It remains to translate the insertion tableaux of inverses back into data attached to $u$ and $w$. By the theorem Inverse Symmetry Exchanges RSK Cells, [citetheorem:8450], inversion swaps the insertion and recording tableaux. Applying that theorem first to $u$ and then to $w$ gives
\begin{align*}
P(u^{-1})=Q(u)
\end{align*}
and
\begin{align*}
P(w^{-1})=Q(w).
\end{align*}
Substituting these two identities into the preceding right-cell equivalence gives
\begin{align*}
u\sim_L w \iff Q(u)=Q(w).
\end{align*}
This proves that left cells are the fibres of the recording tableau map $Q:S_n\to\operatorname{SYT}_n$.
[/guided]
[/step]
[step:Translate the equivalences into the stated dictionary]
The first equivalence says that the right Kazhdan-Lusztig cell containing $w$ is exactly the fibre
\begin{align*}
\{u\in S_n:P(u)=P(w)\}.
\end{align*}
The second says that the left Kazhdan-Lusztig cell containing $w$ is exactly the fibre
\begin{align*}
\{u\in S_n:Q(u)=Q(w)\}.
\end{align*}
The third says that the two-sided Kazhdan-Lusztig cell containing $w$ is exactly the set
\begin{align*}
\{u\in S_n:\operatorname{shape}(P(u))=\operatorname{shape}(P(w))\}.
\end{align*}
Since $P(w)$ and $Q(w)$ have the same shape by construction of the Robinson-Schensted correspondence, this is also the common shape of $P(w)$ and $Q(w)$. This proves the theorem.
[/step]
