Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

Question

For the notations I am using, I refer to the Appendix at the end of this post.

Here is what, for the sake of this post, I consider to be Reifegerste's theorem:

Theorem 1. Let $n\in\mathbb N$ and $i\in\mathbb N$. Let $\sigma$ and $\tau$ be two permutations in $S_n$ such that $\sigma$ and $\tau$ differ by a Knuth transformation at positions $i-1,i,i+1$. Then, the recording tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$ differ only by the interchange of two entries. Specifically, one of the following two cases must hold:

Case 1: In one of the two tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$, the letter $i+1$ lies weakly northeast of $i-1$, which in turn lies weakly northeast of $i$. The other tableau is obtained from this one by switching $i$ with $i+1$.

Case 2: In one of the two tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$, the letter $i$ lies weakly northeast of $i+1$, which in turn lies weakly northeast of $i-1$. The other tableau is obtained from this one by switching $i-1$ with $i$.

Remark. Theorem 1 appeared first implicitly(!) in Astrid Reifegerste's paper "Permutation sign under the Robinson-Schensted correspondence" (also in an apparently older version as arXiv:0309266v1), where it serves as an auxiliary observation in the proof of Lemma 4.1 (formulated for dual Knuth transformations instead of Knuth transformations, but that is just a matter of inverting all permutations). Then, it was explicitly stated as Corollary 4.2.1 in Jacob Post's thesis "Combinatorics of arc diagrams, Ferrers fillings, Young tableaux and lattice paths. Both sources give rather low-level proofs which involve little theory but a lot of casework and handwaving (including references to pictures, sadly not in Zelevinsky's sense of this word). They seem to be very similar. I cannot say I fully understand either. Note that there are two cases depending on which of the Knuth relations is used, and one (the $bac$-$bca$ switch) is simpler than the other (the $acb$-$cab$ switch).

Question 1. Since Reifegerste and Post, has anyone found a slick proof of Theorem 1? I can't precisely define what I mean by "slick", but a good approximation would be "verifiable without a lot of pain" and possibly "memorable". I am not asking for it to be short or not use any theory. Indeed, I have a suspicion that an approach in the style of the proof of Corollary 1.11 in Sergey Fomin's appendix to EC1 could work: Since the recording tableau of a word $w$ is determined by the RSK shapes of the prefixes of $w$, it would be enough to show that for all but one $k$, the RSK shape of the $k$-prefix of $\sigma$ equals the RSK shape of the $k$-prefix of $\tau$. Due to Fomin's Theorem 11, this reduces to showing that for all but one $k$, for all $i$, the maximum size of a union of $i$ disjoint increasing subsequences of the $k$-prefix of $\sigma$ equals the maximum size of a union of $i$ disjoint increasing subsequences of the $k$-prefix of $\tau$. This is very easy to see when $\sigma$ and $\tau$ differ by a $bac$-$bca$ Knuth transformation. I'm unable to prove this for an $acb$-$cab$ Knuth transformation, though (I can only prove it with "all but two $k$" in that case). But the approach sounds very promising to me. Alternatively, the growth diagram view on RSK could help.

Question 2. What if we let $\sigma$ and $\tau$ be arbitrary words instead of permutations? Does the possibility of repeated letters break something?

Appendix: notations.

Here are definitions for some notations I am using above:

• A word over a set $A$ means an $n$-tuple of elements $A$ for some $n\in\mathbb N$ (where $0 \in \mathbb N$). The word $\left(a_1,a_2,...,a_n\right)$ is often written as $a_1a_2...a_n$. The entries of a word are called its letters. We identify every $a\in A$ with the one-letter word $\left(a\right)$. For any two words $u$ and $v$ over the same set $A$, we denote by $uv$ the concatenation of $u$ with $v$ (that is, the word $\left(a_1,a_2,...,a_n,b_1,b_2,...,b_m\right)$, where $\left(a_1,a_2,...,a_n\right)=u$ and $\left(b_1,b_2,...,b_m\right)=v$).

• For any $n\in\mathbb N$, any permutation $\sigma \in S_n$ is identified with the $n$-letter word $\sigma\left(1\right) \sigma\left(2\right) ... \sigma\left(n\right)$ over $\mathbb Z$.

• If $u$ and $v$ are two words over $\mathbb Z$, then we say that $u$ and $v$ differ by a Knuth transformation if either of the following four cases holds:

Case 1: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a < b \leq c$ such that $u = p bac q$ and $v = p bca q$.

Case 2: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a < b \leq c$ such that $u = p bca q$ and $v = p bac q$.

Case 3: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a \leq b < c$ such that $u = p acb q$ and $v = p cab q$.

Case 4: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a \leq b < c$ such that $u = p cab q$ and $v = p acb q$.

In either case, we say that $u$ and $v$ differ by a Knuth transformation at positions $i-1,i,i+1$, where $i$ is the length of the word $p$ plus $2$.

(Note that instead of "Knuth transformation", some authors say "elementary Knuth transformation" or "elementary Knuth equivalence". Contrary to what the latter wording might suggest, the "differ by a Knuth transformation" relation itself is not an equivalence relation. The reflexive-and-transitive closure of this relation is the well-known Knuth equivalence. Note also that Reifegerste's theorem is only formulated for permutations (which, viewed as words, have no two equal letters), which allows one to ignore the distinction between $a < b \leq c$ and $a \leq b < c$; but I am keeping the $\leq$s apart from the $<$s because of Question 2 which sets them apart again.)

• If $w$ is a word, then $Q\left(w\right)$ denotes the recording tableau of $w$ under the Robinson-Schensted-Knuth correspondence.

• Young diagrams and Young tableaux are written in English notation (so that the topmost row is the longest, and the leftmost column is the highest). Geographical terminology (like "northwest") refers to this orientation.

Answer 1

First, just for clarity about the question, the Reifegerste preprint dates from September 2003, her paper was published in 2004, and Jacob Post's thesis is from 2009.

But the theorem is easy to show from things known well before that (basically what can be found in Knuth's treatment in The Art of Computer Programming), though I'm not sure I can point precisely to where what I will mention appears (first, explicitly). So while I don't know if anyone explicitly showed this differently since, I'll discuss how it could (and should) have been prove before.

First, the answer to your question 2 is that everything indeed goes through for words in place of permutations. The Schensted correspondence for words (in which the input is an arbitrary word, but not a sequence of bi-letters as in RSK; this version is already in the Schensted paper) commutes with standardisation more or less by definition: replacing a word by its standardisation (which is a permutation) changes its (semi-standard) $P$-tableau into its standardisation (now a standard tableau), while not affecting the $Q$-tableau (recording tableau) at all. Also standardisation maps Knuth-equivalent pairs of words to Knuth-equivalent pairs of permutations. However, there is not really any need for this reduction, because the argument is actually easier for the even more general case of the full RSK correspondence (even if the statement is a bit more delicate: one applies a Knuth-equivalence involving the bottom entries of three consecutive bi-letters; then the $Q$-tableau changes by a permutation of two of the three of its entries corresponding to the top entries of those three bi-letters, where the definition of "corresponding" should be obvious, or can be avoided by assuming all top letters distinct).

Now for the first question, it is fairly obvious that a Knuth equivalence on positions $i-1,i,i+1$ will always affect the recording tableau by just some permutation of the entries $i-1,i,i+1$ (in the RSK version: a permutation of the top entries of the three consecutive bi-letters involved). The part of the recording tableau with strictly smaller entries records a part of the insertion process that does not yet involve any of the (bi-)letters affected by the Knuth-equivalence, so there is no change for entries${}<i-1$. Also, once those three consecutive letters have been inserted, the insertion tableaux ($P$) have become identical (again) because that is what Knuth-equivalence is about, and the recording tableaux have obtained the same shape (as$~P$); the remainder of the insertion process proceeds identically for both cases, so entries${}>i+1$ stay in place as well.

Now the main property of the RSK correspondence I will use is:

Lemma. Suppressing the first bi-letter in a bi-word affects the recording tableau by removing the minimal (top-left) entry, and then rectifying the resulting skew tableau by jeu de taquin.

This is quite standard, but as often occurs it may be hard to point to a clear statement in the literature (I don't have TAOCP at hand right now to check). Certainly Knuth makes a statement saying essentially that row-insertion of a bi-word on one hand, and column-insertion of its bi-letters in reverse order on the other (which basically reverses the order used for the bottom values in the bi-word that also appear in the recording tableau), give the same $P$-tableau, and mutually Schützenberger-dual $Q$-tableaux. Suppressing the first bi-letter only removes the last step of reverse-column-insertion, and so leads to dropping the maximal entry of the Schützenberger-dual $Q$-tableau; by the definition of the Schützenberger-dual, this has on the non-dual $Q$-tableau the effect described in the lemma. (But this is probably more roundabout than necessary; I think the proof of the cited statement actually involves proving the lemma or something equivalent.) Maybe the symmetric form of the lemma is easier to understand: suppressing the bi-letter that is minimal in bottom-first lexicographic ordering (which gives the first occurrence of the minimal entry that is being inserted) affects the insertion tableau by removing its top-left entry and rectifying.

Anyway, given the lemma we can reason as follows to prove the theorem. Let $(Q_0,Q'_0)$ be the recording tableaux of two bi-words related by an elementary Knuth equivalence; they are related by some permutation of the values that I will continue to call $i-1,i,i+1$. By successively suppressing all bi-letters that come before the triple where the elementary Knuth equivalence takes place, one gets pairs of recording tableaux $(Q_1,Q'_1),\ldots,(Q_{i-2},Q'_{i-2})$, the final pair corresponding to a case where the bi-letters involved in the Knuth equivalence come at are at the very beginning of the bi-word. By the lemma, $Q_k$ is obtained from $Q_{k-1}$ by suppressing the top-left entry and performing a jeu de taquin slide for $k=1,2,\ldots,i-2$, and a similar relation holds for $Q'_k$ and $Q'_{k-1}$. In the final pair $(Q_{i-2},Q'_{i-2})$ the entries $i-1,i,i+1$ are the three minimal ones, corresponding to the now initial bi-letters where the Knuth equivalence takes place; all higher entries occur in the same place in $Q_{i-2}$ as in $Q'_{i-2}$. From the cases allowed in a Knuth equivalence it follows that entries $i-1,i,i+1$ occupy a shape$~(2,1)$, with $i-1$ in the top left position, the entries $i,i+1$ interchanged in $Q'_{i-2}$ with respect to $Q_{i-2}$ (there had to be some difference, since the $P$ tableaux are equal). This pair is related as described in case 1 of the question.

The jeu de taquin slide leading from $Q_{k-1}$ to $Q_k$ can be restricted to the entries $i-1,i,i+1$, and involves a jeu de taquin slide on that skew tableau of size$~3$ as well. In the backward direction, an outward jeu de taquin slide is applied to the size$~3$ skew tableau extracted from $Q_k$ to obtain the one extracted from $Q_{k-1}$. Since we know the tableaux extracted from $(Q_{i-2},Q'_{i-2})$ are related by case 1 it will suffice to show that, given two $3$-entry skew tableaux of the same shape, and related as described by one of the cases 1 and 2, if one applies a reverse (outward) jeu-de-taquin slide to each of them, into the same square, then the results will still be of the same shape (actually we know this already in the case at hand) and related by one of the cases 1 and 2. This is quite easy to show by considering the possible configurations; most of the time nothing important changes, but when the three squares fit into a $2\times2$ square and the slide is into the fourth of its squares, there is a transformation of case 1 into case 2; this is why case 2 is needed in the first place. The same considerations occur in a rather detailed proof I gave, in the context of discussing dual equivalence (which is the equality-of-shape-preserving part): proposition 2.3.2 in The Littlewood-Richardson rule, and related combinatorics, in Math. Soc. of Japan Memoirs 11, available from my home page. (This paper it is dated 2001, and its arXiv version is from 1999.)

Added I finally came round to looking what Knuth says about this exactly. His 1970 paper (Pacific J. Math, 34(3)) mentions symmetry, but not reversal of the insertion order. However, in The Art of Computer Programming Vol 3. (1975) one finds in section 5.1.4 the following

Theorem C (M.P. Schützenberger). If $P$ is the tableau formed by the construction of Theorem A from the permutation $a_1~a_2~\ldots~a_n$, and if $a_i=\min\{ a_1~a_2,\ldots,a_n\}$, then Algorithm S changes $P$ into the tableau corresponding to $a_1~\ldots a_{i-1}~a_{i+1}\ldots~a_n$.

(Proof. See exercise 13, which naturally asks "Prove Theorem C".)

Here Theorem A states the Robinson-Schensted correspondence for permutations, and Algorithm S (Delete corner element) is one step of evacuation. So this is indeed the "symmetric form of the lemma" mentioned above.

Answer 2

The equivalent result is well known (and made explicit) in the literature on dual Knuth transformations. From there, you can use the fact that $P(\sigma) = Q( \sigma^{-1})$ to complete the proof. Haiman's paper is the standard reference.

Haiman says two skew tableaux are dual equivalent if they are always of the same shape when acted on by a sequence of jeu de taquin moves. Theorem 2.6 shows this is equivalent to saying they differ by a sequence of elementary dual equivalences, which by Proposition 2.2 act as described in Case 1 or Case 2. Theorem 2.12 shows these elementary dual equivalences can be thought of as dual Knuth transformations. Since

$$P(\sigma) = Q(\sigma^{-1}) \ \ \text{and} \ \ (k_i\sigma)^{-1} = d_i\sigma^{-1} $$

where $k_i$ is a Knuth transformation acting on positions $i-1, i, i+1$ and $d_i$ is a dual-Knuth transformation acting on values $i-1, i, i +1$, we can conclude that $k_i$'s action on $P(\sigma)$ is either Case 1 or Case 2. This can be seen directly by taking the row reading word of $P$ after applying a dual Knuth transformation. The arguments for the aforementioned results are relatively straightforward, and very similar to Marc's post.

I mention this to emphasize that there is no analysis of RSK in Haiman's approach. The only fact used is that the row reading word of a tableau inserts the same as the word itself.

Some additional comments:

1. Haiman's work also characterizes the actions possible for the shifted Schensted correspondence.

2. The proofs in Haiman's paper quite nice, especially when confined to the unshifted case. I've been told the goal of the paper was to get around the row-bumping lemmas you are trying to avoid.

3. In the interest of self-promotion, my paper with Ben Young shows an analogous result for Edelman-Greene insertion (Commenters: has this been done earlier?). Work in progress shows the same for Kraskiewicz insertion, a shifted analogue of Edelman-Greene. Our proofs are based on the messy analysis of row-bumping.

Update: To my knowledge, the earliest explicit proof of what is called Reifegerste's Theorem (for RS but not RSK) is implicit in the Edelman-Greene aforementioned paper (hat tip to Sami Assaf for pointing this out). Their proof is by brute force, and the Haiman approach is the slickest that I am aware of.