Enumerative conjecture for minimally-sorted permutations

A recurrence for minimally sorted permutations

Let $S=s_{123,132}$ be the greedy stack map: read the input from left to right, pushing the next entry whenever the stack, read from top to bottom, avoids $123$ and $132$, and otherwise popping its top entry to the output. Flush the stack when the input is exhausted. Let $\mathfrak M_N$ be the permutations of $[N]$ taking the maximum number of iterations to reach a periodic point. We prove

$$\begin{gathered} |\mathfrak M_{2n}|=(n+1)|\mathfrak M_{2n-1}|,\\ n\geq1. \end{gathered}$$

This is Zhang, Conjecture 4.4. We use the prior results stated there as Theorems 1.1 and 1.2: writing $k=\lfloor(N-1)/2\rfloor$, periodicity is equivalent to

$$\pi_{N-2i+1}=i\quad(1\leq i\leq k),$$

and the maximum time to periodicity is $2k$. The bijection below does not assume the adjacent Conjecture 4.3.

1. Small entries and the first output

An incoming entry $x$ is pushed exactly when at most one entry already in the stack is larger than $x$. In particular, an entry already in the stack can be popped during input processing only by an incoming smaller entry: at its own push, at most one larger entry lay below it, and the entries below it do not change while it remains in the stack. Also, the first input entry is always the last output entry.

We need the following localization fact. If the first $L$ entries of an input are all larger than $r$, then the first $L-2$ output entries are all larger than $r+1$, when $L\geq2$. Indeed, an entry $x\leq r+1$ arriving after this prefix leaves at most one of its entries in the stack when it is pushed, so at least $L-1$ prefix entries precede it in the output. If such an $x$ lies inside the prefix, it is its unique minimum. Unless it is the first input entry, it stays in the stack until the whole prefix has been read; all prefix entries other than $x$ and the first input entry must be output before it. If it is the first entry, it is output last.

Starting with $r=0$ and iterating gives, for $2r<N$,

$$\begin{gathered} S^t(\pi)_j>r,\\ \text{if }t\geq r,\quad 1\leq j\leq N-2r. \end{gathered} \tag{1}$$

For $t>r$, apply the $r$-pass assertion to $S^{t-r}(\pi)$.

Write $\pi^{(t)}=S^t(\pi)$ and $f_t=\pi^{(t)}_1$. We claim that, for every $i$ with $N\geq2i+1$, entry $i$ is permanently in position $N-2i+1$ by time $2i$, and that it first becomes permanent at exactly that time if and only if

$$f_{i-1}=i. \tag{2}$$

For $i=1$, an input not beginning with $1$ sends $1$ to the penultimate position, where it remains. An input beginning with $1$ sends it to the last position and then to the penultimate position. Thus the claim holds.

Here is the tail calculation for the induction. If entries $1,\ldots,r$ are in their stated positions, write the input as

$$W\,r\,b_r\,(r-1)\,b_{r-1}\cdots1\,b_1,$$

where all entries of $W$ and all $b_j$ exceed $r$. Put $a=W_1$, and let $S(W)^-$ denote $S(W)$ with its last entry $a$ removed. Directly processing the successive minima gives

$$\begin{aligned} &S(W)^-\,b_r\,r\,b_{r-1}\,(r-1)\\ &\qquad\cdots b_1\,1\,a. \end{aligned} \tag{3}$$

Thus the fixed small entries remain fixed. Moreover, if

$$B_j(t)=\pi^{(t)}_{N-2j+2},$$

the induction hypothesis and (3) give

$$\begin{gathered} B_j(t)=f_{t-j},\\ t\geq2j-1. \end{gathered} \tag{4}$$

For $j=1$ this is the first-input/last-output rule. For $j\geq2$, entries $1,\ldots,j-1$ have settled by time $t-1$, so (3) gives $B_j(t)=B_{j-1}(t-1)$, and induction proves (4).

Now prove the claim for $i\geq2$, at time $T=2i-2$. All smaller entries have settled, and (1) confines $i$ to the final $2i$ positions. For $1\leq j\leq i-2$, equations (4) and (1) imply

$$B_j(T)=f_{T-j}>i,$$

since $T-j\geq i$. Consequently, putting $d=N-2i+1$, the only possible positions of $i$ are $d$, $d+1$, and $d+3$. In the first case it is already permanently placed. In the second case it is the last, and smallest, entry of $W$ in (3), with $r=i-1$, so the next pass places it in position $d$. In the third case it is $b_{i-1}$; the next pass puts it last in $W$, and the following pass puts it in position $d$. This third case takes exactly two further passes. By (4), it occurs exactly when

$$B_{i-1}(2i-2)=f_{i-1}=i.$$

This proves (2) and the induction. Therefore, for $N=2k+1$ or $2k+2$, with $k\geq1$,

$$\pi\in\mathfrak M_N \quad\Longleftrightarrow\quad S^{k-1}(\pi)_1=k. \tag{5}$$

Indeed, all smaller entries have settled by time $2k-2$, and (2) decides whether the last required entry takes the full $2k$ passes.

2. The event in (5) uses only an initial prefix

We first record an early-output observation. Suppose that the first $L$ entries of an input $v$ are all at least $q-1$, where $q\geq2$. If

$$S(v)_j=q,\qquad j\leq L-4,$$

then

$$\begin{aligned} v_{j+2}&=q-1,\\ S(v)_{[1:j]}&=S(v_{[1:j+2]})_{[1:j]}. \end{aligned} \tag{6}$$

To see this, consider the first input entry smaller than $q-1$, if one exists; its index is at least $L+1$. Before this entry arrives, the only possible entry below $q$ smaller than $q$ is $q-1$, and at most one larger entry can lie below $q$. Hence, if $q$ is first popped when that smaller entry arrives, its output position is at least $L-2$. If it arrives later, the first smaller entry has already flushed all but one of the first $L$ entries, again making an early output impossible. The same bound holds if $q$ survives to the final flush: at most two entries lie below it. These arguments also cover the case that no entry smaller than $q-1$ exists. If $q$ is the first input entry, it is output last.

Thus an output in position $j\leq L-4$ must be caused by the arrival of $q-1$, with $q$ already in the stack. Before $q-1$ arrives, all preceding entries except $q$ exceed $q$. Entry $q$ then lies immediately above the first input entry and is popped after all other preceding entries. If $q-1$ arrives in position $h$, this makes the output position of $q$ equal to $h-2$. Hence $h=j+2$. At that moment the first $j$ outputs have already been produced, proving (6). In particular, this input prefix has minimum $q-1$ at its end, and its first entry is the other entry not yet output.

Apply (6) backwards to (5). At the stage involving $S^{q-2}(\pi)$, use

$$\begin{aligned} L&=N-2q+4,\\ j&=2(k-q)+1,\\ q&=k,k-1,\ldots,2. \end{aligned}$$

Equation (1) supplies the hypothesis on the first $L$ entries, and $j\leq L-4$ follows from $N\geq2k+1$. We obtain prefixes

$$\begin{gathered} U_r=(S^r(\pi))_{[1:2(k-r)-1]},\\ 0\leq r\leq k-1. \end{gathered}$$

with $U_{k-1}=(k)$, such that for $0\leq r<k-1$:

• $U_r$ ends with its minimum $r+1$;
• $S(U_r)$ consists of $U_{r+1}$, followed by $r+1$ and the first entry of $U_r$.

Inducting backwards shows that $U_r$ contains every entry $r+1,\ldots,k$. Its first entry, which is removed in passing to $U_{r+1}$, must therefore exceed $k$. In particular, $U_0$ contains all of $1,\ldots,k$, and all entries outside this initial $2k-1$-letter prefix exceed $k$.

Crucially, these prefix relations also work forwards for any extension of $U_0$. When its final minimum $1$ is read, every entry of $U_0$ except that minimum and the first entry has already been output. Thus the output starts with $U_1$, regardless of the remaining input. Repeating this argument for the final minimum of each $U_r$ shows that the $(k-1)$-st output begins with $k$. The argument is unchanged under any increasing relabelling that fixes $1,\ldots,k$. For $k=1$, the same conclusion is immediate: the event is simply that the first entry is $1$.

3. The bijection

Let $n\geq2$ and put $k=n-1$. If $\pi\in\mathfrak M_{2n}$, its initial $2k-1$-letter prefix contains all entries $1,\ldots,k$, so its last entry $t$ belongs to $\{n,\ldots,2n\}$. Delete this last entry and standardize the remaining permutation, obtaining $\sigma\in S_{2n-1}$. Standardization fixes $1,\ldots,k$ and preserves the order of the initial prefix. Section 2 and (5) therefore give $\sigma\in\mathfrak M_{2n-1}$.

Conversely, given $\sigma\in\mathfrak M_{2n-1}$ and $t\in\{n,\ldots,2n\}$, increase each entry of $\sigma$ that is at least $t$ by one, and append $t$. The same prefix argument shows that the resulting permutation lies in $\mathfrak M_{2n}$. These two constructions are inverse. There are exactly $n+1$ choices for $t$, proving the recurrence for $n\geq2$.

For $n=1$, all permutations of lengths one and two are already periodic. Hence $|\mathfrak M_1|=1$ and $|\mathfrak M_2|=2$, proving the remaining case.