[proofplan]
We prove that the fibres of the Schensted insertion map are exactly the Knuth equivalence classes. First we verify the local statement: inserting either side of an elementary Knuth relation into the same preliminary tableau gives the same final tableau. This proves that Knuth equivalent words have the same insertion tableau. For the converse, we use reverse row insertion to show that every word is Knuth equivalent to the row-reading word of its insertion tableau; two words with the same insertion tableau are therefore equivalent to the same normal form.
[/proofplan]
[step:Check that each elementary Knuth move preserves insertion]
Let $A^*$ denote the set of finite words in $A$. For a word $w=w_1\cdots w_m\in A^*$ and a semistandard tableau $T$, write
\begin{align*}
T \leftarrow w
\end{align*}
for the tableau obtained by successively row-inserting $w_1,\dots,w_m$ into $T$. Thus $P(w)=\varnothing \leftarrow w$, where $\varnothing$ denotes the empty tableau.
We use the following precise external result, Knuth's local compatibility lemma for semistandard row insertion. The lemma states: if $A$ is totally ordered, $T\in\operatorname{SSYT}(A)$, and row insertion uses the leftmost entry strictly larger than the inserted letter, then for all $x,y,z\in A$,
\begin{align*}
T \leftarrow xzy = T \leftarrow zxy \quad \text{whenever } x \le y < z,
\end{align*}
and
\begin{align*}
T \leftarrow yxz = T \leftarrow yzx \quad \text{whenever } x < y \le z.
\end{align*}
Its hypotheses match the present theorem: $A$ is totally ordered, $T$ is semistandard, and the insertion convention in the statement is exactly the leftmost-strictly-larger convention. Therefore the two displayed identities hold for every preliminary tableau $T$ and every admissible triple $x,y,z$.
[guided]
We need a local result strong enough to compare insertions into an arbitrary preliminary tableau, not merely into the empty tableau. The precise result being used is Knuth's local compatibility lemma for semistandard row insertion: for a totally ordered alphabet $A$, a semistandard tableau $T\in\operatorname{SSYT}(A)$, and the leftmost-strictly-larger row insertion rule, the two elementary Knuth triples have identical insertion outputs.
We verify its hypotheses in the present setting. The alphabet $A$ is totally ordered by the theorem statement. The preliminary tableau $T$ is assumed to lie in $\operatorname{SSYT}(A)$, so its rows are weakly increasing and its columns are strictly increasing. The theorem statement defines $T\leftarrow a$ using the convention that $a$ bumps the leftmost entry in the current row that is strictly larger than it, which is exactly the insertion convention required by the lemma.
For the first elementary relation, the additional hypothesis is $x\le y<z$. Applying the local compatibility lemma with the triple $(x,y,z)$ gives
\begin{align*}
T \leftarrow xzy = T \leftarrow zxy.
\end{align*}
For the second elementary relation, the additional hypothesis is $x<y\le z$. Applying the local compatibility lemma with the same named triple $(x,y,z)$ gives
\begin{align*}
T \leftarrow yxz = T \leftarrow yzx.
\end{align*}
These are identities of final tableaux after all three insertions, so the result includes all bumping and termination cases inside the row-insertion process.
[/guided]
[/step]
[step:Extend local invariance to arbitrary word contexts]
Let $r,s\in A^*$ be arbitrary words. If $x\le y<z$, then
\begin{align*}
P(rxzys)=\varnothing \leftarrow r x z y s.
\end{align*}
Set
\begin{align*}
T_r:=\varnothing \leftarrow r.
\end{align*}
By the local identity from the previous step,
\begin{align*}
T_r\leftarrow xzy = T_r\leftarrow zxy.
\end{align*}
Inserting the common suffix $s$ into equal tableaux gives equal final tableaux, so
\begin{align*}
P(rxzys)=P(rzxys).
\end{align*}
Applying the second local identity from the previous step to the tableau $T_r$ and to the letters $x,y,z$ satisfying $x<y\le z$ gives
\begin{align*}
T_r \leftarrow yxz = T_r \leftarrow yzx.
\end{align*}
Appending the common suffix $s$ to equal tableaux preserves equality, so
\begin{align*}
P(ryxzs)=P(ryzxs).
\end{align*}
Since Knuth equivalence is generated by a finite chain of such context moves, induction on the length of the chain gives
\begin{align*}
u\equiv_K v \implies P(u)=P(v).
\end{align*}
[/step]
[step:Define the row-reading normal form of a tableau]
Let $\mathcal{T}(A)$ denote the set of semistandard Young tableaux with entries in $A$. Define the row-reading map
\begin{align*}
\operatorname{row}:\mathcal{T}(A) \to A^*
\end{align*}
by letting $\operatorname{row}(T)$ be the word obtained by reading the rows of $T$ from bottom to top, and within each row from left to right. We shall prove that every word $w\in A^*$ satisfies
\begin{align*}
w\equiv_K \operatorname{row}(P(w)).
\end{align*}
This will give the reverse implication.
We prove the displayed assertion by induction on the length $m$ of $w$. If $m=0$, then $w$ is the empty word, $P(w)=\varnothing$, and $\operatorname{row}(P(w))$ is also empty.
Assume $m\ge 1$, write
\begin{align*}
w=w'a
\end{align*}
with $w'\in A^*$ and $a\in A$, and set
\begin{align*}
T':=P(w'), \qquad T:=P(w)=T'\leftarrow a.
\end{align*}
By the induction hypothesis,
\begin{align*}
w'\equiv_K \operatorname{row}(T').
\end{align*}
Appending the same final letter $a$ preserves equivalence, hence
\begin{align*}
w=w'a\equiv_K \operatorname{row}(T')a.
\end{align*}
It remains to compare $\operatorname{row}(T')a$ with $\operatorname{row}(T)$.
[/step]
[step:Move the final inserted letter along the reverse bumping path]
Let the row insertion of $a$ into $T'$ create a new outer corner in row $q$ and column $c_q$. For each row index $1\le i\le q$, let $c_i$ be the column in row $i$ changed by the insertion path. Let $b_i\in A$ denote the letter inserted into row $i$ during the forward insertion, so $b_1=a$, and for $i<q$ the entry bumped from position $(i,c_i)$ is $b_{i+1}$. Thus $T$ is obtained from $T'$ by replacing, for $1\le i<q$, the entry $b_{i+1}$ in position $(i,c_i)$ by $b_i$, and by adding $b_q$ in the new box $(q,c_q)$.
We use the row-word insertion lemma for semistandard row insertion. The lemma states: if $A$ is totally ordered, $S\in\operatorname{SSYT}(A)$, $a\in A$, and $R=S\leftarrow a$ is formed using the leftmost-strictly-larger row insertion rule, then
\begin{align*}
\operatorname{row}(S)a\equiv_K\operatorname{row}(R).
\end{align*}
More precisely, the proof of the lemma constructs a finite sequence of elementary Knuth moves along the reverse bumping path. At each visited pair of adjacent rows, the three letters in the affected word context are the moving letter, the row entry immediately adjacent to the insertion column in the row-reading order, and the column-comparison entry forced by the next row of the bumping path; row weak increase and column strict increase give exactly either $x\le y<z$ for a move $xzy\equiv_K zxy$ or $x<y\le z$ for a move $yxz\equiv_K yzx$. Thus the lemma includes the required finite construction of legal Knuth moves and the verification of the inequalities in every local context.
The hypotheses of the lemma match the present situation: $A$ is totally ordered, $T'\in\operatorname{SSYT}(A)$ because $T'=P(w')$, the inserted letter is $a\in A$, and $T=T'\leftarrow a$ is formed using the insertion convention fixed in the theorem statement. Applying the lemma with $S=T'$ and $R=T$ gives
\begin{align*}
\operatorname{row}(T')a \equiv_K \operatorname{row}(T).
\end{align*}
Combining this with the previous step yields
\begin{align*}
w\equiv_K \operatorname{row}(T')a \equiv_K \operatorname{row}(T)=\operatorname{row}(P(w)).
\end{align*}
This completes the induction.
[guided]
The point of reverse insertion is to identify exactly where the last inserted letter belongs in the row-reading word of the final tableau.
We have $T=T'\leftarrow a$. The insertion of $a$ follows a finite bumping path through the rows of $T'$ and ends by creating one new outer corner in row $q$. The symbols $c_i$ and $b_i$ record this path: $b_i$ is the letter inserted into row $i$, $c_i$ is the column changed in row $i$, $b_1=a$, and for $i<q$ the entry bumped from position $(i,c_i)$ is $b_{i+1}$. Thus the pair $(b_i,c_i)$ specifies the letter carried by the path and the precise row position affected at stage $i$.
The rigorous comparison of row words is supplied by the row-word insertion lemma for semistandard row insertion. This lemma says that whenever $A$ is totally ordered, $S\in\operatorname{SSYT}(A)$, $a\in A$, and $R=S\leftarrow a$ is formed by the leftmost-strictly-larger row insertion rule, one has
\begin{align*}
\operatorname{row}(S)a\equiv_K\operatorname{row}(R).
\end{align*}
The lemma is not merely a statement that such an equivalence exists: its proof constructs the equivalence by following the reverse bumping path. At each local slide, the affected part of the row-reading word is a three-letter context determined by the moving letter $b_i$, the adjacent row entry next to column $c_i$ in row-reading order, and the comparison entry in the neighbouring row at the next column of the path. Since rows of a semistandard tableau are weakly increasing, the two letters in the same row satisfy the required weak inequality. Since columns are strictly increasing, the vertically compared entries satisfy the required strict inequality. Therefore every local slide is exactly one of the legal Knuth moves
\begin{align*}
xzy \equiv_K zxy \quad \text{with } x\le y<z
\end{align*}
or
\begin{align*}
yxz \equiv_K yzx \quad \text{with } x<y\le z.
\end{align*}
The bumping path has finitely many rows, so the lemma gives a finite chain of legal Knuth moves.
We now verify the lemma's hypotheses in our setting. The alphabet $A$ is totally ordered by the theorem statement. The tableau $T'=P(w')$ is semistandard by the definition of the insertion map used in the theorem statement. The letter inserted is $a\in A$, and $T=T'\leftarrow a$ is formed using the leftmost-strictly-larger convention. Applying the row-word insertion lemma with $S=T'$ and $R=T$ gives
\begin{align*}
\operatorname{row}(T')a \equiv_K \operatorname{row}(T).
\end{align*}
Since the induction hypothesis gives
\begin{align*}
w'\equiv_K \operatorname{row}(T'),
\end{align*}
we may append $a$ to both words and obtain
\begin{align*}
w'a\equiv_K \operatorname{row}(T')a.
\end{align*}
Combining the two equivalences gives
\begin{align*}
w=w'a\equiv_K \operatorname{row}(T)=\operatorname{row}(P(w)).
\end{align*}
[/guided]
[/step]
[step:Identify the fibres of insertion with Knuth classes]
We have already proved that
\begin{align*}
u\equiv_K v \implies P(u)=P(v).
\end{align*}
Conversely, suppose
\begin{align*}
P(u)=P(v).
\end{align*}
Set
\begin{align*}
T:=P(u)=P(v).
\end{align*}
By the row-reading normal form proved above,
\begin{align*}
u\equiv_K \operatorname{row}(P(u))=\operatorname{row}(T)
\end{align*}
and
\begin{align*}
v\equiv_K \operatorname{row}(P(v))=\operatorname{row}(T).
\end{align*}
Since $\equiv_K$ is an [equivalence relation](/page/Equivalence%20Relation), symmetry and transitivity give
\begin{align*}
u\equiv_K v.
\end{align*}
Thus
\begin{align*}
P(u)=P(v) \iff u\equiv_K v,
\end{align*}
as required.
[/step]
