Left equivalence forces equality of recording tableaux in type A

Recording descents match permutation descents. For a standard tableau $U$, define $\mathrm{Des}(U):=\{k:{\mathrm{row}}_U(k+1)>{\mathrm{row}}_U(k)\}$. Let $a=w_k$, $b=w_{k+1}$ and $T=P_{k-1}$; both letters are absent from $T$. By [F10], $T$ and $T\leftarrow a$ have strictly increasing rows, and the route for $a$ has increasing carried letters. Inserting $a$ follows rows $1$ through $m$: write $a_1=a$, and for $i<m$ let $p_i$ be the position where $a_i$ bumps the old entry $a_{i+1}$; in row $m$ it appends $a_m$ at position $p_m$. Let $b_i$ and $q_i$ be the corresponding carried letters and positions when $b$ is inserted into $T\leftarrow a$. If $b>a$, then $b_1>a_1$. Whenever this route reaches row $i<m$ with $b_i>a_i$, every entry left of $p_i$ in the current row is $<a_i$, and the entry at $p_i$ is $a_i$; thus $b$ either appends and stops in that row or bumps at a position $q_i>p_i$. In the latter case row strictness gives $b_{i+1}>a_{i+1}$. If it reaches row $m$, then $b_m>a_m$, so it appends at $p_m+1$; in all cases its new box is in a row at most $m$. If $b<a$, then $b_1<a_1$. Whenever the route reaches row $i<m$ with $b_i<a_i$, the entry at $p_i$ is $a_i>b_i$, so it bumps at $q_i\le p_i$. If $q_i<p_i$, the old entry there is $<a_{i+1}$; if $q_i=p_i$, it bumps $a_i<a_{i+1}$. Hence $b_{i+1}<a_{i+1}$ and it reaches row $m$. There $a_m$ was appended at $p_m$, so $b_m<a_m$ makes it bump at or before $p_m$ and continue to a lower row. Thus the box for $b$ is strictly below the box for $a$ exactly when $b<a$. By [F6], these are the boxes carrying $k+1$ and $k$ in $Q(w)$; by [F8], $b<a$ is equivalent to $s_k\in R(w)$. Therefore $\mathrm{Des}(Q(w))=\{k:s_k\in R(w)\}$.

The column-superstandard word. Let $\lambda$ have column lengths $l_1\ge \cdots \ge l_m>0$, put $L_0=0$ and $L_j=l_1+\cdots +l_j$, and let $P_{\lambda }$ fill column $j$ from top to bottom with $L_{j-1}+1,\dots ,L_j$. The word ${\omega }_{\lambda }=(L_1,\dots ,1,L_2,\dots ,L_1+1,\dots ,L_m,\dots ,L_{m-1}+1)$ has RSK pair $(P_{\lambda },P_{\lambda })$. Indeed the first decreasing block inserts as a column. Each later block has entries larger than all preceding blocks; its largest entry appends at the end of the first row, and each subsequent smaller entry bumps the preceding new-column entry down one row, where it appends after the entries from earlier blocks. Thus block $j$ fills column $j$ with $L_{j-1}+1,\dots ,L_j$ from top to bottom, and the recording labels fill that column in increasing order. By [F1], ${\omega }_{\lambda }$ is the unique permutation with pair $(P_{\lambda },P_{\lambda })$. Its right descent positions are precisely the positions inside its decreasing blocks, with ascents at $L_1,\dots ,L_{m-1}$.

The descent set determines the tableau of this fixed shape. Let $U$ be a standard tableau of shape $\lambda$, and put $D_{\lambda }:=\{1,\dots ,n-1\}\setminus \{L_1,\dots ,L_{m-1}\}=\mathrm{Des}(P_{\lambda })$. Suppose $\mathrm{Des}(U)=D_{\lambda }$. The cells carrying labels at most $k$ form a Young diagram contained in $\lambda$, since every cell to the left or above a cell has a smaller entry; the next label occupies an addable node of that prefix. Induct on the columns. Label $1$ occupies $(1,1)$. After columns $1,\dots ,j-1$ have been filled to their final heights $l_1,\dots ,l_{j-1}$, no further box can be added to those columns: such a box would lie outside $\lambda$. For $j>1$, the non-descent at $L_{j-1}$ requires label $L_{j-1}+1$ to lie in a row at most $l_{j-1}$; every such row of the prefix has length $j-1$, and the Young-prefix condition makes $(1,j)$ its only addable node in those rows. Thus column $j$ starts at its top. Suppose its first $r<l_j$ entries have filled rows $1,\dots ,r$. The next label is an internal descent, so its row is strictly greater than $r$. Earlier columns cannot grow, while an addable node in a later column would be in row one and hence cannot be a descent. In column $j$, skipping row $r+1$ would violate the Young-prefix condition, so the only possible node is $(r+1,j)$, which belongs to $\lambda$ because $r<l_j$. Therefore column $j$ is filled from top to bottom with $L_{j-1}+1,\dots ,L_j$. This completes every column and gives $U=P_{\lambda }$.

Replace by column-superstandard insertion tableaux. Suppose $x{\sim }_{L}y$, and let ${\lambda }_1,{\lambda }_2$ be the shapes of $Q(x),Q(y)$. By [F1] there are unique $\widehat{x},\widehat{y}$ with RSK pairs $(P_{{\lambda }_1},Q(x))$ and $(P_{{\lambda }_2},Q(y))$. Since $Q(\widehat{x})=Q(x)$ and $Q(\widehat{y})=Q(y)$, the recording-tableau implication of Equal insertion or recording tableaux imply right or left equivalence gives $x{\sim }_L\widehat{x}$ and $y{\sim }_L\widehat{y}$, hence $\widehat{x}{\sim }_L\widehat{y}$. By [F5], $R(\widehat{x})=R(\widehat{y})$.

Transport the two Knuth paths. By [F2] and [F1], take a finite Knuth path $\widehat{x}\to y^{\mathrm{\prime }}$ with RSK pair $(P_{{\lambda }_1},P_{{\lambda }_1})$ and a finite path $\widehat{y}\to w^{\mathrm{\prime }\mathrm{\prime }}$ with pair $(P_{{\lambda }_2},P_{{\lambda }_2})$. Apply the first path's successive star operations also to $\widehat{y}$, obtaining $w^{\mathrm{\prime }}$, and the second path's operations also to $\widehat{x}$, obtaining $y^{\mathrm{\prime }\mathrm{\prime }}$. These parallel paths are defined at every step: initially the paired elements have equal right descent sets by step 1.4; if one path step is a star on $D_{ij}$ or $D_{ji}$, [F3] shows the other element is in the same domain, and the transported pair remains left equivalent by [F4]. The left-cell descent property [F5] then keeps their right descent sets equal for the next step. Therefore $y^{\mathrm{\prime }}{\sim }_L{w}^{\mathrm{\prime }}$ and $y^{\mathrm{\prime }\mathrm{\prime }}{\sim }_L{w}^{\mathrm{\prime }\mathrm{\prime }}$, so $R(y^{\mathrm{\prime }})=R(w^{\mathrm{\prime }})$ and $R(y^{\mathrm{\prime }\mathrm{\prime }})=R(w^{\mathrm{\prime }\mathrm{\prime }})$. Knuth moves preserve insertion tableaux by [F2], hence $P(w^{\mathrm{\prime }})=P_{{\lambda }_2}$ and $P(y^{\mathrm{\prime }\mathrm{\prime }})=P_{{\lambda }_1}$.

Compare the column lengths. Write $l_1,l_2,\dots$ and $l_1^{\mathrm{\prime }},l_2^{\mathrm{\prime }},\dots$ for the column lengths of ${\lambda }_1$ and ${\lambda }_2$, padding both lists by zeros after their final columns. By step 1.2, $y^{\mathrm{\prime }}$ and $w^{\mathrm{\prime }\mathrm{\prime }}$ are concatenations of decreasing blocks of lengths $l_j$ and $l_j^{\mathrm{\prime }}$, respectively; since $R(y^{\mathrm{\prime }})=R(w^{\mathrm{\prime }})$ and $R(y^{\mathrm{\prime }\mathrm{\prime }})=R(w^{\mathrm{\prime }\mathrm{\prime }})$, [F8] implies the corresponding position blocks of $w^{\mathrm{\prime }}$ and $y^{\mathrm{\prime }\mathrm{\prime }}$ are also decreasing. The first $l_1$ letters of $w^{\mathrm{\prime }}$ insert to a column of height $l_1$, so the first column of $P(w^{\mathrm{\prime }})=P_{{\lambda }_2}$ has length $l_1^{\mathrm{\prime }}\ge l_1$; the first $l_1^{\mathrm{\prime }}$ letters of $y^{\mathrm{\prime }\mathrm{\prime }}$ similarly give $l_1\ge l_1^{\mathrm{\prime }}$, hence $l_1=l_1^{\mathrm{\prime }}$. Inductively suppose $l_j=l_j^{\mathrm{\prime }}$ for $j<k$ and the first $k-1$ blocks have filled exactly those first $k-1$ columns in each partial insertion tableau. Inserting block $k$ of $w^{\mathrm{\prime }}$ cannot add boxes to those columns, whose lengths already equal their final lengths in $P_{{\lambda }_2}$. All later columns are empty before that block. Its first new box must be at the top of column $k$; each subsequent letter is smaller, so by step 1.1 its new box lies strictly lower, and the Young-diagram condition forces the successive new boxes down column $k$. Thus $l_k^{\mathrm{\prime }}\ge l_k$; if $l_k^{\mathrm{\prime }}=0<l_k$, the forced new column would contradict the final shape, so this case is impossible as well. The same argument with $y^{\mathrm{\prime }\mathrm{\prime }}$ and target $P_{{\lambda }_1}$ gives $l_k\ge l_k^{\mathrm{\prime }}$, including the case $l_k=0<l_k^{\mathrm{\prime }}$. Induction yields ${\lambda }_1={\lambda }_2=:\lambda$.

Identify the recording tableau and conclude. By step 3.1, $P(w^{\mathrm{\prime }})=P_{\lambda }$ and $R(w^{\mathrm{\prime }})=R(y^{\mathrm{\prime }})$. The common-shape property in [F1] therefore gives $\mathrm{sh}(Q(w^{\mathrm{\prime }}))=\mathrm{sh}(P(w^{\mathrm{\prime }}))=\lambda$. Step 1.1 gives $\mathrm{Des}(Q(w^{\mathrm{\prime }}))=\{k:s_k\in R(w^{\mathrm{\prime }})\}=\{k:s_k\in R(y^{\mathrm{\prime }})\}=\mathrm{Des}(P_{\lambda })$, since step 1.2 identifies the block descent set with the descent set of $P_{\lambda }$. By step 1.3, $Q(w^{\mathrm{\prime }})=P_{\lambda }$. The RSK bijection [F1] then gives $w^{\mathrm{\prime }}=y^{\mathrm{\prime }}$. The first transported path is a composition of bijective star maps, so equality of its outputs on $\widehat{x},\widehat{y}$ implies $\widehat{x}=\widehat{y}$. Their recording tableaux are $Q(x),Q(y)$ by construction in step 1.4, whence $Q(x)=Q(y)$.