A *Kreweras walk* of length $3n$ is a word consisting of $n$ $A$'s, $n$ $B$'s, and $n$ $C$'s such that in any prefix there are at least as many $A$'s as $B$'s, and at least as many $A$'s as $C$'s. For example, with $n = 3$, one Kreweras walk is: $w = AABBCACCB$. These are the same as walks in $\mathbb{Z}^2$ from the origin to itself consisting of steps $(1,1)$, $(-1,0)$, and $(0,-1)$ which always remain in the nonnegative orthant (treat $A$'s as $(1,1)$ steps, $B$'s as $(-1,0)$ steps, and $C$'s as $(0,-1)$ steps). Kreweras in 1965 proved that the number of Kreweras walks is $\frac{ 4^n(3n)!}{(n+1)!(2n+1)!}$ (OEIS sequence A006335). Many years later, in the 2000's, the Kreweras walks became a motivating/foundational example in the theory of "walks with small steps in the quarter plane" as developed by Mireille Bousquet-Mélou and her school. They also are related to decorated planar maps and in particular are a key ingredient in recent breakthrough work relating random planar maps to Liouville quantum gravity.

I discovered a very interesting cyclic action on Kreweras walks, which apparently had not been noticed previously. Let me refer to this action as *rotation*. To perform rotation on a Kreweras walk $w$, first we literally rotate the word $w =(w_1,w_2,...,w_{3n})$ to $w' = (w_2,w_3,...,w_{3n},w_1)$. With the above example of $w$, we get $w' = ABBCACCBA$. This is, however, no longer a valid Kreweras walk. So there will be a smallest index $i$ such that $(w'_1,...,w'_i)$ has either more $B$'s than $A$'s, or more $C$'s than $A$'s. Then we create another word $w''$ by swapping $w'_i$ and $w'_{3n}$ (which is always an $A$). For example, with the previous example, we have $i = 3$ (corresponding to the second $B$ in the word), and we get $w'' = ABACACCBB$. It's not hard to see that the result is a Kreweras walk, which we call the rotation of the initial Kreweras walk. The sequence of iterated rotations of our initial $w = AABBCACCB$ example looks like
$$ 00 \; AABBCACCB \\
01 \; ABACACCBB \\
02 \; AACACCBBB \\
03 \; ACACABBBC \\
04 \; AACABBBCC \\
05 \; ACABBACCB \\
06 \; AABBACCBC \\
07 \; ABAACCBCB \\
08 \; AAACCBCBB \\
09 \; AACCBABBC \\
...$$
In particular, $3n = 9$ applications of rotation yields the Kreweras walk which is the same as our initial $w$ except that the $B$'s and $C$'s have swapped places. If we did another $9$ applications we would get back to our initial $w$.

**Conjecture**: For a Kreweras walk of length $3n$, $3n$ applications of rotation always yields the Kreweras walk which is the same as the initial walk except with the $B$'s and $C$'s swapped (so $6n$ applications of rotation is the identity).

(So my **question** is obviously: is my conjecture right?) I've thought about this conjecture a fair amount with little concrete progress. I've done a fair amount of computational verification of this conjecture: for all $n \leq 6$, and for many thousands more walks with various $n \leq 30$.

**Where this action comes from**: The Kreweras walks of length $3n$ are in obvious bijection with the linear extensions of a poset $P$, namely, $P=[n] \times V$, the direct product of the chain on $n$ elements and the 3-element ``$V$'' poset with relations $A < B$, $A < C$. I became aware of this poset thanks to this MO answer of Ira Gessel to a previous question of mine, which cited this paper of Kreweras and Niederhausen in which the authors prove not just a product formula for the number of linear extension of $P$, but for the entire order polynomial of $P$. The rotation of Kreweras walks as I just defined it is nothing other than the famous (Schützenberger) *promotion* operation on linear extension of a poset (see this survey of Stanley's for background on promotion). There are few non-trivial classes of posets for which the behavior of promotion is understood (see section 4 of that survey of Stanley's), so it is very interesting to discover a new example. In particular, all known examples are connected to tableaux and symmetric functions, etc.; whereas this Kreweras walks example has quite a different flavor.

**Some thoughts**: The analogous rotation action on words with only $A$'s and $B$'s (i.e., Dyck words) is well-studied; as explained in section 8 of this survey of Sagan's on the cyclic sieving phenomenon, it corresponds to promotion on $[2]\times[n]$, and in turn to rotation of noncrossing matchings of $[2n]$. There is a way to view a Kreweras walk as a pair of noncrossing partial matchings on $[3n]$ (basically we form the matching corresponding to the $A$'s and $C$'s, and to the $A$'s and $B$'s). But this visualization does not seem to illuminate anything about the rotation action (in particular, when we rotate a walk, one of the noncrossing partial matchings simply rotates, but something complicated happens to the other one).

As mentioned earlier, there is a bijection due to Bernardi between Kreweras walks and decorated cubic maps, but I am not able to see any simple way that this bijection interacts with rotation.

On a positive note, it seems useful to write the $3n$ rotations of a Kreweras walk in a cylindrical array where we indent by one each row, as follows: $$ \begin{array} \, A & A & B & b & C & A & C & C & B \\ & A & b & A & C & A & C & C & B & B \\ & & A & A & C & A & C & c & B & B & B \\ & & & A & c & A & C & A & B & B & B & C \\ & & & & A & A & C & A & B & B & b & C & C \\ & & & & & A & c & A & B & B & A & C & C & B \\ & & & & & & A & A & B & b & A & C & C & B & C \\ & & & & & & & A & b & A & A & C & C & B & C & B \\ & & & & & & & & A & A & A & C & C & B & c & B & B \\ & & & & & & & & & A & A & C & C & B & A & B & B & C \end{array} $$ In each row I've made lowercase the $B$ or $C$ that the initial $A$ swaps with. We can extract from this array a permutation which records the columns in which these matches occur (where we cylindrically identify column $3n+i$ with column $i$). In this example, the permutations we get is $p = [4,3,8,5,11,7,10,9,15] = [4,3,8,5,2,7,1,9,6]$. The fact that this list of columns is actually a permutation (which I don't know how to show) is equivalent to the assertion that the position of the $A$'s after $3n$ rotations is the same as in the initial Kreweras walk. Furthermore, this permutation $p$ determines position of $A$'s. Namely, the $A$'s are exactly the $p(i)$ for which $p(i) < i$. In our example, these are $2$, $1$, and $6$, corresponding to $i = 5,7,9$. Also, you can see how the $3n$ rotations "permute" the position of the $A$'s from $p$ as well. To do that, write down a new permutation $q$ from $p$: $q$ is the product of transpositions $q = (3n, p(3n)) \cdots (2, p(2)) \cdot (1, p(1))$. Then $q$ exactly tells us how the $A$'s are permuted. In our example, as we process the transpositions of $q = (9,6)(8,9)(7,1)(6,7)(5,2)(4,5)(3,8)(2,3)(1,4)$ right-to-left on the positions $\{1,2,6\}$ of $A$'s we see $1 \to 4 \to 5 \to 2$; $2 \to 3 \to 8 \to 9 \to 6$; and $6 \to 7 \to 1$. Note that the $A$'s end up changing places, and that they each are involved in a different number of swaps. Another thing worth noting is that the permutation $p$ does not determine the Kreweras walk (even after accounting for the $B \leftrightarrow C$ symmetry).

In spite of these observations, the lack of any connection to algebra (e.g., the representation theory of Lie algebras), and the lack of any good "model" for these words, makes it really hard to reason about how they behave under rotation.

**EDIT:**

Let me add one example which may indicate some subtlety. Let's define a *$k$-letter Kreweras word* of length $kn$ to be a word consisting of $n$ A's, $n$ B's, $n$ C's, $n$ D's, etc. for $k$ different letters such that in any prefix there are at least as many $A$'s as $B$'s, at least as many $A$'s as $C$'s, at least as many $A$'s as $D$'s, etc. So $3$-letter Kreweras words are the Kreweras walks discussed above, and $2$-letter Kreweras words are the Dyck words. We can define rotation for $k$-letter Kreweras words in exactly the same manner: literally rotate the word, find the first place the inequalities are violated, swap this place with the final $A$ to obtain a valid word (and this corresponds to promotion on a certain poset).

For the case $k=2$, note that $kn$ applications of rotation to a $k$-letter Kreweras word of length $kn$ results in a word with the $A$'s in the same position (because this is just rotation of noncrossing matchings). For the case $k=3$, apparently $kn$ applications of rotation results in a word with the $A$'s in the same position (because apparently the $B$'s and $C$'s switch). But for $k > 3$, it is not true necessarily that $kn$ applications of rotation results in a word with the $A$'s in the same position. For instance, with $k=4$ and $n=3$, starting from the word $w=AADACCDCBDBB$, 12 rotations gives us: $$ 00 \; AADACCDCBDBB \\ 01 \; ADACCDABDBBC \\ 02 \; AACCDABDBBCD \\ 03 \; ACADABDBBCDC \\ 04 \; AADABDBBCDCC \\ 05 \; ADABDBACDCCB \\ 06 \; AABDBACDCCBD \\ 07 \; ABDAACDCCBDB \\ 08 \; ADAACDCCBDBB \\ 09 \; AAACDCABDBBD \\ 10 \; AACDCABDBBDC \\ 11 \; ACDAABDBBDCC \\ 12 \; ADAABDBBDCCC $$ where the $A$'s do not end up in the same positions they started in. So something kind of subtle has to be happening in the case $k=3$ to explain why they do.

4more comments