[proofplan]
We fix the equal-parameter Kazhdan-Lusztig cell convention for the Coxeter system $S_n$ and compare it with the Robinson-Schensted correspondence. The essential external input is the classical type $A$ Kazhdan-Lusztig cell theorem: right cells are Knuth equivalence classes and left cells are dual Knuth equivalence classes. The RSK facts then identify Knuth classes with insertion tableaux and dual Knuth classes with recording tableaux. Finally, the two-sided cell relation is generated by moving within left and right cells, so it forgets the individual tableaux and retains exactly the common RSK shape.
[/proofplan]
[step:Fix the cell and tableau conventions]
Let $S=\{s_i=(i,i+1):1\le i\le n-1\}$ be the standard Coxeter generating set of $W=S_n$. Let $\mathcal H$ be the equal-parameter Iwahori-Hecke algebra of $(W,S)$ over $\mathbb Z[q^{1/2},q^{-1/2}]$, and let $(C_w)_{w\in W}$ denote its Kazhdan-Lusztig basis.
We use the following standard cell convention. For $x,y\in W$, write $x\le_L y$ if $C_x$ occurs with nonzero coefficient in $hC_y$ for some $h\in\mathcal H$, and let $\sim_L$ be the [equivalence relation](/page/Equivalence%20Relation) generated by $\le_L$. Similarly, write $x\le_R y$ if $C_x$ occurs with nonzero coefficient in $C_yh$ for some $h\in\mathcal H$, and let $\sim_R$ be the equivalence relation generated by $\le_R$. Finally, let $\sim_{LR}$ be the equivalence relation generated by $\sim_L$ and $\sim_R$; its equivalence classes are the two-sided Kazhdan-Lusztig cells.
For $w\in S_n$, write
\begin{align*}
\operatorname{RSK}(w)=(P(w),Q(w))
\end{align*}
for the row-insertion Robinson-Schensted correspondence on the one-line word of $w$. By [citetheorem:8435], $P(w)$ and $Q(w)$ are standard Young tableaux of the same shape, and the map $w\mapsto (P(w),Q(w))$ is a bijection from $S_n$ to pairs of standard Young tableaux of common shape.
[guided]
The only convention-sensitive point in the theorem is the assignment of $P$ and $Q$ to right and left cells. We therefore fix all conventions before proving any equivalence.
The group is
\begin{align*}
W=S_n,
\end{align*}
with Coxeter generators
\begin{align*}
S=\{s_i=(i,i+1):1\le i\le n-1\}.
\end{align*}
The Kazhdan-Lusztig cells are the equal-parameter cells for this Coxeter system. Let $\mathcal H$ denote the corresponding Hecke algebra over $\mathbb Z[q^{1/2},q^{-1/2}]$, and let $(C_w)_{w\in W}$ be the Kazhdan-Lusztig basis. The left preorder is defined by left multiplication: $x\le_L y$ means that $C_x$ appears with nonzero coefficient in $hC_y$ for some $h\in\mathcal H$. The left cell relation $\sim_L$ is the equivalence relation generated by this preorder. The right preorder is defined by right multiplication: $x\le_R y$ means that $C_x$ appears with nonzero coefficient in $C_yh$ for some $h\in\mathcal H$, and $\sim_R$ is the generated equivalence relation. The two-sided relation $\sim_{LR}$ is generated by allowing both left and right cell moves.
For the tableau side, for each $w\in S_n$ we write
\begin{align*}
\operatorname{RSK}(w)=(P(w),Q(w)).
\end{align*}
Here $P(w)$ is the insertion tableau and $Q(w)$ is the recording tableau for row insertion applied to the one-line notation of $w$. By the [Robinson-Schensted-Knuth bijection theorem](/theorems/8435) [citetheorem:8435], this construction gives a bijection between permutations in $S_n$ and ordered pairs $(P,Q)$ of standard Young tableaux of the same shape. Thus every permutation has a well-defined insertion tableau, recording tableau, and common RSK shape.
[/guided]
[/step]
[step:Use the type $A$ cell theorem to translate cells into Knuth equivalence]
We use the classical type $A$ Kazhdan-Lusztig cell theorem of Kazhdan-Lusztig, Lusztig, and Vogan: for the above equal-parameter convention on $S_n$, the right Kazhdan-Lusztig cells are precisely the Knuth equivalence classes of one-line words, and the left Kazhdan-Lusztig cells are precisely the dual Knuth equivalence classes. This is a standard external theorem not yet in the wiki: Type A Kazhdan-Lusztig cell theorem.
Thus, for all $u,w\in S_n$,
\begin{align*}
u\sim_R w \iff u \equiv_K w,
\end{align*}
where $\equiv_K$ denotes Knuth equivalence of the one-line words. Also,
\begin{align*}
u\sim_L w \iff u \equiv_K^\vee w,
\end{align*}
where dual Knuth equivalence is defined by
\begin{align*}
u \equiv_K^\vee w \iff u^{-1}\equiv_K w^{-1}.
\end{align*}
[/step]
[step:Identify right cells with equal insertion tableaux]
By [citetheorem:8478], two words are Knuth equivalent if and only if they have the same Schensted insertion tableau. Applying this to the one-line words of $u,w\in S_n$, we obtain
\begin{align*}
u\equiv_K w \iff P(u)=P(w).
\end{align*}
Combining this equivalence with the type $A$ cell theorem gives
\begin{align*}
u\sim_R w \iff P(u)=P(w).
\end{align*}
This proves the right-cell classification.
[/step]
[step:Identify left cells with equal recording tableaux]
By the definition of dual Knuth equivalence,
\begin{align*}
u\equiv_K^\vee w \iff u^{-1}\equiv_K w^{-1}.
\end{align*}
By [citetheorem:8478], this is equivalent to
\begin{align*}
P(u^{-1})=P(w^{-1}).
\end{align*}
By [inverse symmetry of the Robinson-Schensted correspondence](/theorems/8437) [citetheorem:8437],
\begin{align*}
P(u^{-1})=Q(u)
\end{align*}
and
\begin{align*}
P(w^{-1})=Q(w).
\end{align*}
Therefore
\begin{align*}
u\equiv_K^\vee w \iff Q(u)=Q(w).
\end{align*}
Combining this with the type $A$ cell theorem gives
\begin{align*}
u\sim_L w \iff Q(u)=Q(w).
\end{align*}
This proves the left-cell classification.
[/step]
[step:Pass from left and right cells to common RSK shape]
Let $\operatorname{sh}(w)$ denote the common Young diagram shape of $P(w)$ and $Q(w)$. If $u\sim_R w$, then $P(u)=P(w)$ by the right-cell classification, hence $\operatorname{sh}(u)=\operatorname{sh}(w)$. If $u\sim_L w$, then $Q(u)=Q(w)$ by the left-cell classification, hence again $\operatorname{sh}(u)=\operatorname{sh}(w)$. Since $\sim_{LR}$ is generated by left and right cell moves, every two-sided cell is contained in a single RSK shape class.
Conversely, suppose $\operatorname{sh}(u)=\operatorname{sh}(w)=\lambda$. Write
\begin{align*}
\operatorname{RSK}(u)=(P_u,Q_u)
\end{align*}
and
\begin{align*}
\operatorname{RSK}(w)=(P_w,Q_w).
\end{align*}
By the RSK bijection [citetheorem:8435], there exists a unique permutation $v\in S_n$ such that
\begin{align*}
\operatorname{RSK}(v)=(P_w,Q_u).
\end{align*}
Then $Q(v)=Q_u=Q(u)$, so $u\sim_L v$ by the left-cell classification. Also $P(v)=P_w=P(w)$, so $v\sim_R w$ by the right-cell classification. Hence $u\sim_{LR}w$.
Thus
\begin{align*}
u\sim_{LR}w \iff \operatorname{sh}(u)=\operatorname{sh}(w).
\end{align*}
Since $\operatorname{sh}(u)$ is the shape of $P(u)$ and $\operatorname{sh}(w)$ is the shape of $P(w)$, this is exactly the assertion that $u$ and $w$ lie in the same two-sided cell if and only if $P(u)$ and $P(w)$ have the same shape. The three stated classifications follow.
[/step]
