# Cyclic action on Kreweras walks

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 $$\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.

• Ah, I have a student working on very similar-sounding questions! I was inspired a bit by the paper arxiv.org/abs/1805.01254 which does not seem to have anything to do with walks at a glance, but it is there... Feb 1, 2020 at 21:47
• I really like this! Doing a few examples by hand, it seems like for $k=4$, after $4n$ steps, the former position of Bs and the new position of the Bs have zero overlap, and same for C and D. Your conjecture obviously implies a stronger statement for $k=3$. Feb 15, 2020 at 4:42
• @HughThomassupportsMonica: Very nice observation! Doing some large random examples it looks like this could be the case! Feb 15, 2020 at 4:49
• In fact my claim, for k=3, already implies your conjecture. Thinking in terms of promotion where we don't decrement the entries (so the each number just moves through the poset from maximum to minimum and is replaced by itself $+3n$ in a maximum position again) every number $t$ starts life as a maximum, and my conjecture then implies that when $t+3n$ appears in the filling, as a maximum again, it must be the other one. The rest follows. If my conjecture is true, that could be the explanation for $k>3$ being different from $k=3$. Feb 15, 2020 at 6:00
• Sorry, I retract what I said in my last comment. I no longer think that what I claimed allows you to prove your statement for $k=3$. I find it plausible that there could be something a bit stronger than my claim which does allow you to prove your claim for $k=3$ but which still leaves the door open to chaos when $k=4$, but that's just a feeling. (I should probably delete that comment and this one.) Feb 15, 2020 at 16:42

Martin Rubey and I solved my conjecture.

The basic idea of the proof is as follows. First to a Kreweras word $$w$$ we associate what we call its bump diagram, which is just the union of the two noncrossing partial matchings of $$\{1,2,...,3n\}$$ associated to $$w$$ (the one for the A's and B's and the one for the A's and C's), drawn as a graph in the obvious way. For example, with $$w=AABBCACCB$$ its bump diagram is We also think of this diagram as a set of ordered pairs ('arcs'); in this example that set is $$\{ (1,4),(1,8),(2,3),(2,5),(6,7),(6,9)\}$$

We extract a permutation $$\sigma_w$$ of $$\{1,2,...,3n\}$$ from the bump diagram as follows.

For $$i=1,2,...,3n$$, we take a trip from position $$i$$. We start traveling from position $$i$$ along the unique arc ending at $$i$$ (if $$w_i=B$$ or $$C$$), or the "shorter arc" beginning at $$i$$ (if $$w_i=A$$), and we continue until we reach a "crossing" of arcs. When we hit a crossing of arcs $$(i,k)$$ and $$(j,\ell)$$ with $$i \leq j < k < \ell$$ (note that we allow the case $$i=j$$), we follow the following "rules of the road":

• if we were heading towards $$i$$, then we turn right and head towards $$\ell$$;

• if we were heading towards $$\ell$$, then we turn left and head towards $$i$$;

• otherwise we continue straight to where we were heading.

When we finish our trip at position $$j$$ then we define $$\sigma_w(i) := j$$.

For example, to compute $$\sigma_w(3)$$: we start traveling along the arc $$(2,3)$$ heading towards $$2$$; then we come to the crossing of $$(2,3)$$ and $$(2,5)$$ and we turn right, heading towards $$5$$; then we come to crossing of $$(1,4)$$ and $$(2,5)$$ and we turn left, heading towards $$1$$; then we come to the crossing of $$(1,4)$$ and $$(1,8)$$ and we turn right, heading towards $$8$$; then we come to the crossing of $$(1,8)$$ and $$(6,9)$$, but we just continue straight to $$8$$; and so we finish our trip at $$8$$. So $$\sigma_w(3)=8$$.

Or to compute $$\sigma_w(7)$$: we start traveling along the arc $$(6,7)$$ heading towards $$6$$; then we come to the crossing of $$(6,7)$$ and $$(6,9)$$ and we turn right, heading towards $$9$$; then we come to the crossing of $$(1,8)$$ and $$(6,9)$$ and we turn left, heading towards $$1$$; and then we come to the crossing of $$(1,4)$$ and $$(1,8)$$, but we just continue straight to $$1$$; and so we finish our trip at $$1$$. So $$\sigma_w(7)=1$$.

We could compute the whole permutation is $$\sigma_w = [4,3,8,5,2,7,1,9,6]$$.

You might notice that this example $$w$$ is the same as the original post and that this permutation $$\sigma_w$$ is the same as the "permutation" $$p$$ defined in terms of the cylindrical rotation array.

Indeed, this always happens (that the trip permutation is the same as the permutation from the cylindrical rotation array). It follows from the main lemma behind the overall proof, which is

Lemma. If $$w'$$ is the rotation of $$w$$, then $$\sigma_{w'} = c^{-1} \sigma_w c$$ where $$c= (1,2,3,...,3n)$$ is the "long cycle."

As a remark, these trip permutations come from the theory of plabic graph (cf. Section 13 of Postnikov's paper https://arxiv.org/abs/math/0609764).

Since $$\sigma_w$$ does not completely determine $$w$$, to finish the proof we need to keep track of a little more data. For that purpose, we define $$\varepsilon_w=(\varepsilon_w(1),...,\varepsilon_w(3n))$$, a sequence of $$3n$$ letters which are B's or C's, defined by $$\varepsilon_w(i) := \begin{cases} w_{\sigma(i)} &\textrm{if w_{\sigma(i)}\neq A} \\ w_{\sigma(\sigma(i))} &\textrm{if w_{\sigma(i)}= A}. \end{cases}$$ Similarly to the previous lemma, we can show

Lemma. If $$w'$$ is the rotation of $$w$$, then $$\varepsilon_{w'} = (\varepsilon_w(2),\varepsilon_w(3),...,\varepsilon_w(3n),-\varepsilon_w(1))$$ with the convention that $$-B=C$$ and vice-versa.

The above lemmas easily imply that the $$3n$$th rotation of $$w$$ is obtained from $$w$$ by swapping B's and C's.

Martin and I will post a preprint to the arXiv with all the details soon.

EDIT: The paper is now on the arXiv at https://arxiv.org/abs/2005.14031.

This is not an answer, but too long for a comment.

This promotion operator is (apparently) governed by local rules, similar to https://arxiv.org/abs/1804.06736, as follows:

• regard each path as a sequence of coordinates, that is, $$A$$ adds $$(1,1)$$, $$B$$ adds $$(-1,0)$$ and $$C$$ adds $$(0,-1)$$ to the current coordinate

• create a cylindrical array from each promotion orbit, for example, for the path $$AABBCACCB$$ $${\scriptstyle\begin{array}{llllllllllllllllllll} 0,0 & 1,1 & 2,2 & 1,2 & 0,2 & 0,1 & 1,2 & 1,1 & 1,0 & 0,0 \\ &0,0 & 1,1 & 0,1 & 1,2 & 1,1 & 2,2 & 2,1 & 2,0 & 1,0 & 0,0 \\ &&0,0 & 1,1 & 2,2 & 2,1 & 3,2 & 3,1 & 3,0 & 2,0 & 1,0 & 0,0 \\ &&&0,0 & 1,1 & 1,0 & 2,1 & 2,0 & 3,1 & 2,1 & 1,1 & 0,1 & 0,0 \\ &&&&0,0 & 1,1 & 2,2 & 2,1 & 3,2 & 2,2 & 1,2 & 0,2 & 0,1 & 0,0 \\ &&&&&0,0 & 1,1 & 1,0 & 2,1 & 1,1 & 0,1 & 1,2 & 1,1 & 1,0 & 0,0 \\ &&&&&&0,0 & 1,1 & 2,2 & 1,2 & 0,2 & 1,3 & 1,2 & 1,1 & 0,1 & 0,0 \\ &&&&&&&0,0 & 1,1 & 0,1 & 1,2 & 2,3 & 2,2 & 2,1 & 1,1 & 1,0 & 0,0 \\ &&&&&&&&0,0 & 1,1 & 2,2 & 3,3 & 3,2 & 3,1 & 2,1 & 2,0 & 1,0 & 0,0 \\ &&&&&&&&&0,0 & 1,1 & 2,2 & 2,1 & 2,0 & 1,0 & 2,1 & 1,1 & 0,1 & 0,0 \\ &&&&&&&&&&0,0 & 1,1 & 1,0 & 2,1 & 1,1 & 2,2 & 1,2 & 0,2 & 0,1 & 0,0 \\ &&&&&&&&&&&0,0 & 1,1 & 2,2 & 1,2 & 2,3 & 1,3 & 0,3 & 0,2 & 0,1 & 0,0 \\ &&&&&&&&&&&&0,0 & 1,1 & 0,1 & 1,2 & 0,2 & 1,3 & 1,2 & 1,1 & 1,0 & 0,0 \\ &&&&&&&&&&&&&0,0 & 1,1 & 2,2 & 1,2 & 2,3 & 2,2 & 2,1 & 2,0 & 1,0 & 0,0 \\ &&&&&&&&&&&&&&0,0 & 1,1 & 0,1 & 1,2 & 1,1 & 1,0 & 2,1 & 1,1 & 0,1 & 0,0 \\ &&&&&&&&&&&&&&&0,0 & 1,1 & 2,2 & 2,1 & 2,0 & 3,1 & 2,1 & 1,1 & 1,0 & 0,0 \\ &&&&&&&&&&&&&&&&0,0 & 1,1 & 1,0 & 2,1 & 3,2 & 2,2 & 1,2 & 1,1 & 0,1 & 0,0 \\ &&&&&&&&&&&&&&&&&0,0 & 1,1 & 2,2 & 3,3 & 2,3 & 1,3 & 1,2 & 0,2 & 0,1 & 0,0 \end{array}}$$

• consider any square of four coordinate in this array $$\begin{array}{ll} \lambda & \nu\\ \kappa & \mu \end{array}$$ and let $$\tilde\mu = \kappa + \nu - \lambda$$. Then, apparently, we have $$\mu = \begin{cases} \tilde\mu &\text{if \tilde\mu has positive coordinates}\\ \tilde\mu + (2,1) &\text{if the first coordinate of \tilde\mu is negative}\\ \tilde\mu + (1,2) &\text{if the second coordinate of \tilde\mu is negative} \end{cases}$$

Possibly we can get a proof that the occurrences of $$\tilde\mu$$ with a negative coordinate yield a permutation, assuming that the local rules are correct.

First we paste the triangular region to the right of the first $$3n$$ rows into the empty region below the diagonal (and removing the final $$3n-1$$ rows). The pasting must be done in a way such that there is precisely one $$(0,0)$$ coordinate in each row and column: $${\scriptstyle\begin{array}{llllllllllllllll} 0,0 & 1,1 & 2,2 & 1,2 & 0,2 & 0,1 & 1,2 & 1,1 & 1,0 & 0,0 \\ 1,0 & 0,0 & 1,1 & 0,1 & 1,2 & 1,1 & 2,2 & 2,1 & 2,0 & 1,0 \\ 2,0 & 1,0 & 0,0 & 1,1 & 2,2 & 2,1 & 3,2 & 3,1 & 3,0 & 2,0 \\ 2,1 & 1,1 & 0,1 & 0,0 & 1,1 & 1,0 & 2,1 & 2,0 & 3,1 & 2,1 \\ 2,2 & 1,2 & 0,2 & 0,1 & 0,0 & 1,1 & 2,2 & 2,1 & 3,2 & 2,2 \\ 1,1 & 0,1 & 1,2 & 1,1 & 1,0 & 0,0 & 1,1 & 1,0 & 2,1 & 1,1 \\ 1,2 & 0,2 & 1,3 & 1,2 & 1,1 & 0,1 & 0,0 & 1,1 & 2,2 & 1,2 \\ 0,1 & 1,2 & 2,3 & 2,2 & 2,1 & 1,1 & 1,0 & 0,0 & 1,1 & 0,1 \\ 1,1 & 2,2 & 3,3 & 3,2 & 3,1 & 2,1 & 2,0 & 1,0 & 0,0 & 1,1 \\ 0,0 & 1,1 & 2,2 & 2,1 & 2,0 & 1,0 & 2,1 & 1,1 & 0,1 & 0,0 \end{array}}$$

(This array does not satisfy the local rules along the diagonal.)

Now we consider one square of four, but instead of its corners label the four edges with $$\lambda-\kappa$$, $$\nu-\lambda$$, $$\mu-\kappa$$ and $$\nu-\mu$$. There are 11 different squares occurring, two of which correspond to a $$b$$ or $$c$$ respectively. For these two, the labels on parallel edges are different, for the others, they are same. Put a bullet in the squares whose parallel edges have distinct labels.

In the case at hand, we obtain $${\def\x{\huge\bullet} \scriptstyle\begin{array}{llllllllllllllllll} & A & & A & & B & & B & & C & & A & & C & & C & & B &\\ B & & A & & A & & A & \x & B & & B & & B & & B & & B & & B\\ & B & & A & & B & & A & & C & & A & & C & & C & & B &\\ B & & B & & A & \x & B & & B & & B & & B & & B & & B & & B\\ & B & & B & & A & & A & & C & & A & & C & & C & & B &\\ C & & C & & C & & A & & A & & A & & A & & C & \x & C & & C\\ & B & & B & & C & & A & & C & & A & & C & & A & & B &\\ C & & C & & C & & C & & A & \x & C & & C & & C & & C & & C\\ & B & & B & & C & & C & & A & & A & & C & & A & & B &\\ A & & A & \x & B & & B & & B & & A & & A & & A & & A & & A\\ & B & & A & & C & & C & & B & & A & & C & & A & & B &\\ C & & C & & C & & C & & C & & C & & A & \x & C & & C & & C\\ & B & & A & & C & & C & & B & & C & & A & & A & & B &\\ A & \x & B & & B & & B & & B & & B & & A & & A & & A & & A\\ & A & & A & & C & & C & & B & & C & & B & & A & & B &\\ B & & B & & B & & B & & B & & B & & B & & B & & A & \x & B\\ & A & & A & & C & & C & & B & & C & & B & & B & & A &\\ A & & A & & A & & A & & A & & A & \x & C & & C & & C & & A\\ & A & & A & & C & & C & & B & & A & & B & & B & & C & \end{array}}$$

It remains to show that in each row of "vertical" labels only $$A$$ and one other letter occurs, and in each column of "horizontal" labels, only $$A$$ and one other letter occurs, except that for the "horizontal" labels below the diagonal, we have to swap $$B$$ and $$C$$.

I believe this follows from the local rules.

• Thanks for this, it is really nice. I think it should be straightforward to show that these local rules hold. Do you think that it is possible that this promotion operation fits into the tensor invariants picture, but for a rank 2 affine or other Kac-Moody algebra? Feb 13, 2020 at 15:24
• I have no idea. One further observation: the occurrences of $\tilde\mu$ with one coordinate negative are (apparently) precisely the entries of the permutation. Feb 13, 2020 at 15:42
• Right: when we remove the initial $A$ (1,1) step, the resulting path will go out of the 1st orthant exactly once, and precisely at the first $B$ or $C$ step to which this $A$ is matched. Feb 13, 2020 at 15:49
• I am still struggling with the final (crucial) step: that there is precisely one bullet in every column. Feb 13, 2020 at 20:52
• I checked the case $k=4$. Indeed, the local rules for this case are the most straightforward generalisation of the rules for $k=3$. Thus it is very unlikely that the local rules alone explain the order of promotion. Feb 14, 2020 at 16:45

Again not (quite) an answer, but too long for a comment:

Here is another way to obtain the (conjectural) permutation.

As running example, let $$p = A B A A C C B C A B B C$$.

The algorithm to obtain the permutation can be reformulated as follows:

• to determine the exceedences, proceed using promotion.

So we have, in one line notation and using $$x$$ for unknowns, $$\pi = [2, 8, 6, 5, x, 7, x, 11, 10, x, 12, x]$$.

• to determine the deficiencies,

• let "openers" be the positions of the $$A$$'s in the path: $$\{1, 3, 4, 9\}$$.

• let "closers" be the positions of the deficiencies (i.e., the indices of the unknowns) $$\{5, 7, 10, 12\}$$

• match each closer $$c$$ (beginning with the smallest) with the nearest opener $$o$$, such that $$p_{\pi(o)}$$ differs from $$p_c$$.

$$\pi(5) = 1$$ because $$p_{5}=C$$ and $$p_{\pi(4)}=p_5$$ and $$p_{\pi(3)}=p_6$$ equal $$C$$

$$\pi(7) = 4$$ because $$p_7=B$$ and $$p_{\pi(4)}=p_5=C$$

$$\pi(10) = 3$$ because $$p_{10}=B$$ and $$p_{\pi(3)}=p_6=C$$

$$\pi(12) = 9$$ because $$p_{12}=C$$ and $$p_{\pi(9)}=p_{10}=B$$

Although this looks much more complicated, it might be easier to prove that this algorithm works: we "only" have to show that there is a matching from closers to openers such that each closer is matched to a smaller opener with the correct label.

I think this goes as follows: consider the square diagram obtained from the cyclindrical growth diagram by appropriate use of scissors and glue: $$\begin{array}{lllllllll} A& b& A& A& C& C& B& C& A& B& B& C\\ B& A& A& A& C& C& B& c& A& B& B& C\\ B& C& A& A& C& c& B& A& A& B& B& C\\ B& C& C& A& c& A& B& A& A& B& B& C\\ b& C& C& C& A& A& B& A& A& B& B& C\\ A& C& C& C& B& A& b& A& A& B& B& C\\ A& C& C& c& B& B& A& A& A& B& B& C\\ A& C& C& A& B& B& C& A& A& B& b& C\\ A& C& C& A& B& B& C& B& A& b& A& C\\ A& C& c& A& B& B& C& B& B& A& A& C\\ A& C& A& A& B& B& C& B& B& C& A& c\\ A& C& A& A& B& B& C& B& b& C& C& A\\ \end{array}$$

It is an immediate consequence of the local rules (and probably also of the definition of promotion) that in every column above the main diagonal the letter in the first line repeats, until it is eventually replaced by an $$A$$, and the same holds for the letters below the diagonal. (At this point we do not know that the non-$$A$$ letter below the diagonal is different from the non-$$A$$ letter above the diagonal.)

Observe, however, that the non-$$A$$ letter in each column below the diagonal equals the replaced letter (indicated as lower-case $$b$$ or $$c$$ in the example) in the corresponding row. This is the case because promotion appends the replaced letter to the Kreweras walk.

It remains to show that promotion of the path intertwines with rotation of this permutation (regarded as a chord diagram).