Return to Question

Question 2. What if we consider arbitrary words instead of permutations? Let us say we require $\sigma$ and $\tau$ to be distinct (because if they are equal, $Q\left(\sigma\right)$ and $Q\left(\tau\right)$ are just equal and cannot differ by a flip). Does the possibility of repeated letters break something?

• 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)=a$. 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:

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

• 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:

(Note that the reflexive-and-transitive closure of the "differ by a Knuth transformation" 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.)

(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.)

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). 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 $j$, for all $k$, 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.

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.