# 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 $$[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.

• 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... – Per Alexandersson Feb 1 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$. – Hugh Thomas supports Monica Feb 15 at 4:42
• @HughThomassupportsMonica: Very nice observation! Doing some large random examples it looks like this could be the case! – Sam Hopkins Feb 15 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$. – Hugh Thomas supports Monica Feb 15 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.) – Hugh Thomas supports Monica Feb 15 at 16:42

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? – Sam Hopkins Feb 13 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. – Martin Rubey Feb 13 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. – Sam Hopkins Feb 13 at 15:49
• I am still struggling with the final (crucial) step: that there is precisely one bullet in every column. – Martin Rubey Feb 13 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. – Martin Rubey Feb 14 at 16:45

It is convenient to view the change of a string under rotations without actually rotating it (i.e., starting with what would be the first position in the initial string). So, 9 rotations of the given example $$AABBCACCB$$ form: $$\begin{split} \bar{A}ABBCACCB \\ BAB\bar{A}CACCB \\ BBA\bar{A}CACCB \\ BBC\bar{A}CACAB \\ BBCC\bar{A}ACAB \\ B\bar{A}CCBACAB \\ B\bar{A}CCBCAAB \\ A\bar{A}CCBCBAB \\ A\bar{A}CCBCBBA \\ A\bar{A}CCBABBC \\ \end{split}$$ where bars show positions of the first $$A$$ as it travels along the string.

Clearly, if we replace each $$A$$ in Kreweras walks with $$([$$, each $$B$$ with $$)$$, and each $$C$$ with $$]$$, then in the resulting string the subsequence formed by "(",")" and the subsequence formed by "[","]" both represent Dyck words. Matching parentheses and brackets in these Dyck words define a correspondence of each $$A$$ to one $$B$$ and one $$C$$. The corresponding letters come in order $$ABC$$ (type $$BC$$) or $$ACB$$ (type $$CB$$).

Claims:

• Every $$A$$ (like the one marked with bar above) moves in the string forward a number of times, then moves backward once, and stays at this position.
• When $$A$$ moves, it swaps with $$B$$ or $$C$$ depending on whether its type is $$BC$$ or $$CB$$, and the type of $$A$$ flips.
• Type of $$A$$ remains unchanged upon a move of any other $$A$$.
• Every position (i.e. column) that initially contains $$B$$ or $$C$$ is visited by exactly one $$A$$, which then leaves this position, and gets replaced by $$C$$ or $$B$$, respectively.

From these claims, it follows that $$B$$'s and $$C$$'s got reversed upon $$3n$$ rotations.

• This is an interesting perspective, but are you saying you know how to prove these claims? – Sam Hopkins Feb 11 at 0:55
• For instance, I know that if we do the analogous action but with four letters $A,B,C,D$, suddenly there is no good behavior at all, so something subtle has to be going on with the fact that there are only three letters. – Sam Hopkins Feb 11 at 0:58
• @SamHopkins: I have no idea about 4 letters, but with 3 letters everything is simple if we view the rotations as in my answer. – Max Alekseyev Feb 11 at 1:00
• Okay, thanks very much, I will reflect on this for a bit. – Sam Hopkins Feb 11 at 1:01
• The first claim is clear to me. For the second claim, I understand that each column which initially contains a B or C will be visited by an A, which then leaves the position. I don't see why the B's will be replaced by C's and vice-versa; but more concerning: I don't see why after this A leaves, another A moving backwards could not move into this column. – Sam Hopkins Feb 11 at 1:26

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