[name=Theorem,numberwithin=section]thm

# Dynamics of Pop-Tsack Torsing

Anqi Li  Massachusetts Institute of Technology, Cambridge, MA 02139, USA
<EMAIL_ADDRESS>
###### Abstract.

For a finite irreducible Coxeter group $(W,S)$ with a fixed Coxeter element
$c$ and set of reflections $T$, Defant and Williams define a pop-tsack torsing
operation $\operatorname{Pop_{T}}\colon W\to W$ given by
$\operatorname{Pop_{T}}(w)=w\cdot\pi_{T}(w)^{-1}$ where
$\pi_{T}(w)=\bigvee_{t\leq_{T}w,\ t\in T}^{NC(w,c)}t$ is the join of all
reflections lying below $w$ in the absolute order in the non-crossing
partition lattice $NC(w,c)$. This is a “dual” notion of the pop-stack sorting
operator $\operatorname{Pop_{S}}$ introduced by Defant as a way to generalize
the pop-stack sorting operator on $\mathfrak{S}_{n}$ to general Coxeter
groups. Define the forward orbit of an element $w\in W$ to be
$O_{\operatorname{Pop_{T}}}(w)=\\{w,\operatorname{Pop_{T}}(w),\operatorname{Pop_{T}}^{2}(w),\ldots\\}$.
Defant and Williams established the length of the longest possible forward
orbits $\max_{w\in W}|O_{\operatorname{Pop_{T}}}(w)|$ for Coxeter groups of
coincidental types and type $D$ in terms of the corresponding Coxeter number
of the group. In their paper, they also proposed multiple conjectures about
enumerating elements with near maximal orbit length. We resolve all the
conjectures that they have put forth about enumeration, and in the process we
give complete classifications of these elements of Coxeter groups of types
$A,B$ and $D$ with near maximal orbit lengths.

##  1\. Introduction

The study of _combinatorial dynamics_ investigates combinatorially defined
operations on sets of objects. Specifically, given a set $X$ and a function
$f\colon X\to X$, it is of interest to study the _forward orbit_ of an element
$x\in X$ denoted as $O_{f}(x)=\\{x,f(x),f^{2}(x),\ldots\\}$. A natural
question that one might ask is what the distribution of $|O_{f}(x)|$ looks
like.

One well-studied class of combinatorial operations is that of sorting
operations, where for the base set $X$ we take the symmetric group
$\mathfrak{S}_{n}$ – the set of all permutations of $[n]:=\\{1,2,\ldots,n\\}$.
There are many well-known sorting procedures in the literature (see for
instance [2, 3, 6, 8, 13] and the many references therein). Of most relevance
to us is the _pop-stack sorting_ operator $\operatorname{Pop_{S}}$, which
reverses all of the descending runs of a permutation while keeping different
descending runs in the same relative order. Ungar [14] proved that
$\max_{\pi\in\mathfrak{S}_{n}}|O_{\operatorname{Pop_{S}}}(\pi)|=n$. The
properties of the pop-stack sorting operator have recently been of interest to
enumerative combinatorialists, yielding more modern proofs of the maximum
length of forward orbits and other properties of $\operatorname{Pop_{S}}$ [2,
3, 9, 12].

Defant [10] gives a natural generalization of the $\operatorname{Pop_{S}}$
operator to an arbitrary Coxeter group $W$. When $W=A_{n-1}$, this
$\operatorname{Pop_{S}}$ operator recovers the usual pop-stack sorting
operator on $\mathfrak{S}_{n}$. We refer the interested reader to [10, Section
1, Section 2.2] for more details on the motivation for this construction.

We briefly describe this generalization here. Let $(W,S)$ be a finite Coxeter
group with corresponding set of simple reflections $S$. Denote the left weak
order on $W$ by $\leq_{S}$. Let $w_{\circ}$ be the longest element of $W$. For
$J\subset S$, let $w_{\circ}(J)$ be the longest element in the parabolic
subgroup of $W$ generated by $J$. We define the longest-element projection
$\pi_{S}\colon W\to\\{w_{\circ}(J):J\subset S\\}$ as

$\pi_{S}(w)=\bigvee_{s\leq_{S}w,s\in S}s,$

where the join is taken in the weak order lattice. With this notation in
place, we define the generalized pop-stack sorting operation
$\operatorname{Pop_{S}}:W\rightarrow W$ as
$\operatorname{Pop_{S}}(w):=w\cdot\pi_{S}(w)^{-1}$.

In [10], Defant gives a generalization of Ungar’s theorem. Defant proves
$\sup_{w\in W}|O_{\operatorname{Pop_{S}}}(w)|=h$, where $h$ is the Coxeter
number of $W$. Of note is that Defant’s proof is type-independent, and avoids
passing to combinatorial models of finite Coxeter groups.

Expanding on the classical theory of Coxeter groups, recent work [1, 5] in
this area considers substituting the set of simple reflections $S$ with a
larger generating set. More precisely, we can consider the conjugate closure
$T:=\\{wsw^{-1}:s\in S,w\in W\\}$ of $S$, usually called the generating set of
all reflections. In analogy with the weak order $\leq_{S}$, there exists an
_absolute order_ $\leq_{T}$. Let $\ell_{T}(w)$ for $w\in W$ denote the minimum
$T$-word length of $w$. The _absolute order_ $\leq_{T}$ on $W$ is defined by
$\pi\leq_{T}\mu$ if and only if
$\ell_{T}(\pi)=\ell_{T}(\mu)+\ell_{T}(\pi^{-1}\mu)$.

It turns out in general that $\leq_{T}$ does not contain a maximal element. In
order to construct a lattice out of $\leq_{T}$, we define the poset of _non-
crossing partitions_ relative to a Coxeter element $c$ in $W$, by
$NC(W,c):=[e,c]:=\\{w\in W:e\leq_{T}w\leq_{T}c\\}$. Brady and Watt [7] gave
the first uniform proof that $NC(W,c)$ is indeed a lattice. Bessis [5]
constructs a so-called “dual” Coxeter group where we consider $(W,T)$, and
replace the left weak order with $NC(W,c)$. With this set-up, Defant and
Williams [11] define a “dual” version of $\operatorname{Pop_{S}}$ which they
call _pop-tsack torsing_ and denote by $\operatorname{Pop_{T}}$. In what
follows, fix a Coxeter element $c$ of $W$. The _non-crossing projection_
$\pi_{T}\colon W\to NC(W,c)$ is defined to be

$\pi_{T}(w,c)=\bigvee_{t\leq_{T}w,t\in T}t$

where the join is taken in $NC(W,c)$.

######  Definition 1.1.

The _Coxeter pop-tsack torsing_ operator $\operatorname{Pop_{T}}\colon W\to W$
is the map

$\operatorname{Pop_{T}}(w,c)=w\cdot\pi_{T}(w,c)^{-1}.$

We may ask similar questions about the forward orbits under the
$\operatorname{Pop_{T}}$ operator as we did in the context of
$\operatorname{Pop_{S}}$. The astute reader may notice that our definition of
$\operatorname{Pop_{T}}$ is a priori dependent on the choice of the Coxeter
element $c$. Defant and Williams [11] prove that the dynamical structure of
$\operatorname{Pop_{T}}$ does not depend on $c$, leaving us free to pick $c$
in a way that simplifies our analysis.

The main results in [11] are the following analogues of Defant’s result on
maximum forward orbit length for $\operatorname{Pop_{S}}$ in the context of
$\operatorname{Pop_{T}}$.

######  Theorem 1.2 ([11, Theorem 5.1]).

Let $W$ be a Coxeter group of coincidental type with a fixed Coxeter element
$c$ and Coxeter number $h$. Then:

  * •

$\operatorname{Pop_{T}}^{h-1}(w)=e$ for all $w\in W$.

  * •

$\max_{w\in W}|O_{\operatorname{Pop_{T}}}(w)|=h$.

  * •

The only forward orbit of size $h$ is $O_{\operatorname{Pop_{T}}}(c^{-1})$.

######  Theorem 1.3 ([11, Theorem 6.1]).

Let $W$ be a Coxeter group of type $D_{n}$. Then:

  * •

$\operatorname{Pop_{T}}^{2n-3}(w)=e$ for all $w\in W$.

  * •

$\max_{w\in W}\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$.

Defant and Williams also establish results about $\operatorname{Pop_{T}}$
forward orbits for Coxeter groups of exceptional types. We refer the
interested reader to [11, Section 7] for further discussion.

Unlike in [10], where the proofs were type-independent, the proofs of [11,
Theorem 5.1, Theorem 6.1] rely on the combinatorial model description of the
non-crossing partition lattice in each of the settings. Another observation is
that while [11, Theorem 5.1] establishes that there is a unique forward orbit
of maximum length $h$, in type $D_{n}$ (see Section 4), where $h=2n-2$, there
could be multiple forward orbits of maximum length. For example, in $D_{4}$
there are 7 forward orbits of maximum length 6. It is therefore of interest to
enumerate elements in $D_{n}$ with maximum possible forward orbit length.

Defant and Williams [11] make conjectures for the number of elements with
forward orbits of size $h$ or $h-1$ when the Coxeter group $W$ is of types $A$
and $B$. They also conjecture a formula for the number of forward orbits of
size $h$ when $W$ is of type $D$. In this paper, we prove these conjectures.

######  Definition 1.4.

An _antiexceedance_ of a permutation $w\in\mathfrak{S}_{n}$ is an element
$i\in[n]$ such that $i<w^{-1}(i)$.

######  Definition 1.5.

If $w\in\mathfrak{S}_{n}$ has exactly $n-2$ antiexceedances and
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$ then we say that $w$ is _$A$
-splittable_.

[] An element $w\in\mathfrak{S}_{n}$ satisfies
$\left|O_{\operatorname{Pop_{T}}}(w)\right|=n-1$ if and only if $w$ is
$A$-splittable. In particular, there are $2^{n}-\binom{n}{2}-1$ permutations
with $\operatorname{Pop_{T}}$ forward orbit of length $n-1$.

Recall that the _hyperoctahedral group_ $B_{n}$ is the group of permutations
$w$ of $\pm[n]$ such that $w(\bar{i})=\overline{w(i)}$, where for notational
simplicity we denote $-i$ by $\bar{i}$. Define a total order on $\pm[n]$ by

$\bar{1}\prec\bar{2}\prec\cdots\prec\bar{n}\prec 1\prec 2\prec\cdots\prec n.$

In this setting, we have the following notion of antiexceedance, paralleling
the one in $A_{n}$, where we replace $<$ with $\prec$.

######  Definition 1.6.

An _antiexceedance_ of a permutation $w\in B_{n}$ is an element $i\in[n]$ such
that $i\prec w^{-1}(i)$.

######  Definition 1.7.

If $w\in B_{n}$ has exactly $2n-2$ antiexceedances and
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$ then we say that $w$ is _$B$
-splittable_.

[] An element $w\in B_{n}$ satisfies
$\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-1$ if and only if $w$ is
$B$-splittable. In particular, there are $2^{n}-n-1$ permutations with
$\operatorname{Pop_{T}}$ forward orbit of length $2n-1$.

Not only do we enumerate the permuations with the given forward orbit length,
we also give complete characterizations of these permutations. The formula
given in [11, Conjecture 6.6] is unfortunately incorrect; while Defant and
Williams conjecture that the number of elements $w\in D_{n}$ with
$|O_{\operatorname{Pop_{T}}}(w)|=2n-2$ is $n(2^{n-1}-2)+1$, we show here that
the actual value is $(n-1)(2^{n-2}-2)+1$. In the following theorem, we also
characterize the permutations exhibiting this property, but defer further
description to Section 4.

[] Fix the Coxeter element
$c=(\overline{1}\enspace\overline{2}\cdots\overline{n-1}\enspace 1\enspace
2\enspace\cdots\enspace n-1)(\overline{n}\enspace n)$. An element $w\in D_{n}$
satisfies $\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$ if and only if
either $w$ is a pre-$D$-splittable permutation or $w=c^{-1}$. In particular,
the number of elements of $D_{n}$ that require exactly $2n-3$ iterations of
$\operatorname{Pop_{T}}$ to reach the identity is $(n-1)(2^{n-2}-2)+1$.

Outline. In Section 2 we study type A Coxeter groups and in Section 3 we
handle type B Coxeter groups. The argument for type B Coxeter groups is near
verbatim that for type A. As noted in [11], type $A_{2n-1}$ folds to $B_{n}$
(refer to [11, Section 4.3] and references therein for more information on
folding). It is interesting to ask if there is a direct way to do enumeration
via folding, though in our case we choose to do the counting directly. In
Section 4 we handle the case of type D Coxeter groups, which is more complex
than types A and B. We end off with some avenues for further research in
Section 5, drawing inspiration from analogous questions in the setting of
$\operatorname{Pop_{S}}$.

##  2\. Type A

The Coxeter group of type $A_{n-1}$ is effectively the symmetric group
$\mathfrak{S}_{n}$. We fix the Coxeter element $c=(1\enspace 2\cdots n)$ in
this section.

Now, we briefly describe the combinatorial model for the noncrossing partition
lattice $NC(\mathfrak{S}_{n},c)$. Label $n$ equidistant points on a circle by
$1,2,\ldots,n$ in clockwise order.

######  Definition 2.1.

A set partition $\pi$ of $[n]$ is a _noncrossing set partition_ if the convex
hulls of the different blocks of $\pi$ do not have a common interior.

Given a noncrossing set partition $\pi$, we can recover a noncrossing
partition in $NC(\mathfrak{S}_{n},c)$ as follows: for each block of $\pi$,
form a cycle by ordering the elements of the block in a clockwise order around
the circle. In fact, this procedure we have described gives a bijection;
namely, every noncrossing partition in $NC(\mathfrak{S}_{n},c)$ arises in such
a fashion. The partial order on $NC(\mathfrak{S}_{n},c)$ corresponds to the
reverse refinement order on noncrossing set partitions. In particular, the
noncrossing projection of a permutation $w\in\mathfrak{S}_{n}$ is the smallest
noncrossing partition $v\in NC(\mathfrak{S}_{n},c)$ such that every cycle in
$w$ is contained (as a set) in a cycle of $v$. See Figure 1 for an example.

123456781234567812345678 Figure 1. The permutation $w:=(8\enspace 7\enspace
4\enspace 2)(6\enspace 5\enspace 3\enspace 1)\in\mathfrak{S}_{8}$ (left), its
non-crossing projection $\pi_{T}(w)=(1\enspace 2\enspace 3\enspace 4\enspace
5\enspace 6\enspace 7\enspace 8)\in\mathfrak{S}_{8}$ (middle), and its image
under $\operatorname{Pop_{T}}$ given by $\operatorname{Pop_{T}}(w)=(1\enspace
7\enspace 5\enspace 2\enspace 6\enspace 3\enspace 8\enspace
4)\in\mathfrak{S}_{8}$ (right)

Next, we recall some results from [11]. In the following, fix the Coxeter
element $c=(1\enspace 2\enspace\cdots\enspace n)$ of $A_{n-1}$. We will work
with $\operatorname{Pop_{T}}$ defined using this $c$; this is without loss of
generality since the orbit structure $\operatorname{Pop_{T}}$ is independent
of the choice of $c$ [11, Corollary 4.5].

Following [11], we write $\operatorname{aexc}(w)$ for the number of
antiexceedances (as per Definition 1.4) in the permutation $w$ and we write
$\operatorname{Aexc}(w)$ for the set of indices that are antiexceedances. Let
$\operatorname{cyc_{>1}}(w)\in\mathbb{N}$ denote the number of non-singleton
cycles in a permutation $w\in\mathfrak{S}_{n}$. In this notation, we have the
following result from [11]. An illustration of this result is in Figure 1,
where the antiexceedances are the vertices marked in red.

######  Lemma 2.2 ([11, Theorem 5.2]).

The following properties relating antiexceedances and $\operatorname{Pop_{T}}$
hold:

  1. (a)

The element $c^{-1}$ has $n-1$ antiexceedances.

  2. (b)

Every element of $\mathfrak{S}_{n}$ other than $c^{-1}$ has at most $n-2$
antiexceedances.

  3. (c)

For every $w\in\mathfrak{S}_{n}$, we have
$\operatorname{aexc}(\operatorname{Pop_{T}}(w))=\operatorname{aexc}(w)-\operatorname{cyc_{>1}}(\pi_{T}(w))$.

Since the only element of $\mathfrak{S}_{n}$ without any cycles of length
greater than 1 is $e$, for any $w\in\mathfrak{S}_{n}\backslash\\{e\\}$ we have
that
$\operatorname{aexc}(\operatorname{Pop_{T}}(w))\leq\operatorname{aexc}(w)-1$.
In order for $w$ to take $n-2$ iterations to reach $e$, by [11, Theorem 5.1]
we must first have that $w\neq c^{-1}$. Then, by Lemma 2.2(b) and the earlier
observation in this paragraph, it follows that $w$ must have exactly $n-2$
antiexceedances and $\pi_{T}(w)$ needs to consist of exactly one cycle with
length greater than 1. Recall that such elements $w\in A_{n}$ are
$A$-splittable (Definition 1.5). An example of an $A$-splittable permutation
is the $w$ illustrated in Figure 1. We have seen that for an element
$w\in\mathfrak{S}_{n}$ to have a $\operatorname{Pop_{T}}$ forward orbit of
length $n-1$, $w$ has to be splittable. In fact, we will prove that this
splittable condition is sufficient. We recall Theorem 1.5.

See 1.5

Combining Theorem 1.5 with [11, Theorem 5.1], we prove [11, Conjecture 5.5].

######  Corollary 2.3 ([11, Conjecture 5.5]).

In type $A_{n-1}$, the number of permutations that require exactly $n-2$ or
$n-1$ iterations of $\operatorname{Pop_{T}}$ to reach the identity is
$2^{n}-\binom{n}{2}$.

The proof of Theorem 1.5 is split into two parts. In the first, we will prove
the claim that $A$-splittable permutations are precisely the elements with
$\operatorname{Pop_{T}}$ forward orbit of length $n-1$. In the second, we will
enumerate the $A$-splittable permutations.

One may be tempted to claim that if $\operatorname{cyc_{>1}}(\pi_{T}(w))=1$,
then $\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}(w)))=1$. Such a
claim, if true, would immediately give Theorem 1.5 upon iteration. Alas, this
is too naïve a hope. For instance, one can check that $w=(1\enspace 4\enspace
5\enspace 8\enspace 7\enspace 6\enspace 9\enspace 3\enspace 2)$ is a
counterexample to the aforementioned claim; we have that
$\pi_{T}(w)=(1\enspace 2\enspace 3\enspace 4\enspace 5\enspace 6\enspace
7\enspace 8\enspace 9)$ and so $\operatorname{cyc_{>1}}(\pi_{T}(w))=1$, while
$\operatorname{Pop_{T}}(w)=(1\enspace 3)(2\enspace 4)(6\enspace 8)(7\enspace
9)(5)$ and $\pi_{T}(\operatorname{Pop_{T}}(w))=(1\enspace 2\enspace 3\enspace
4)(6\enspace 7\enspace 8\enspace 9)(5)$ and so
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}(w)))=2$. A pictorial
illustration of this phenomenon is in Figure 2. This suggests that we need to
account for the structure inherent in $w$ from it being $A$-splittable and
therefore having $n-2$ antiexceedances. For instance, in the earlier example
it can be checked that $w$ is not $A$-splittable and also does not lie in the
orbit of a $A$-splittable permutation. The latter can for instance be checked
by computing that there does not exist $u$ with
$\operatorname{cyc_{>1}}(\pi_{T}(u))=1$ such that
$\operatorname{Pop_{T}}(u)=w$.

123456789123456789123456789 Figure 2. The permutation $w=(1\enspace 4\enspace
5\enspace 8\enspace 7\enspace 6\enspace 9\enspace 3\enspace
2)\in\mathfrak{S}_{9}$ (left) which clearly has non-crossing projection
$(1\enspace 2\enspace 3\enspace 4\enspace 5\enspace 6\enspace 7\enspace
8\enspace 9)$, its image under $\operatorname{Pop_{T}}$ given by
$\operatorname{Pop_{T}}(w)=(1\enspace 3)(2\enspace 4)(6\enspace 8)(7\enspace
9)(5)$ (middle) and $\pi_{T}(\operatorname{Pop_{T}}(w))=(1\enspace 2\enspace
3\enspace 4)(6\enspace 7\enspace 8\enspace 9)(5)$ (right)

Before we proceed, let us make the following observation about $A$-splittable
$w$. Firstly, $w$ has at most two cycles. If $w$ has two cycles, then it is of
the form

$(n\enspace c_{1}\enspace\cdots\enspace c_{\ell})(d_{1}\enspace
d_{2}\enspace\cdots\enspace d_{n-\ell-1})$

where $n>c_{1}>\cdots>c_{\ell}$, $d_{1}>c_{\ell}$ and
$d_{1}>d_{2}>\cdots>d_{n-\ell-1}$. This is because when $w$ has two cycles
then the largest element of each of the cycles is not an antiexceedance, and
so every other element has to be an antiexceedance. In particular, once we
decide the two sets of elements that lie in each cycle, then each of the
elements must be arranged in a decreasing order on each cycle. If $w$ has
exactly one cycle with every element being an antiexceedance except for $j$
and $n$, then $w$ is of the form

$(n\enspace n-1\enspace\cdots\enspace j+1\enspace c_{1}\enspace\cdots\enspace
c_{\ell}\enspace j\enspace d_{1}\enspace\cdots\enspace d_{n-j-\ell-1})$

where $n>j>c_{1}>c_{2}>\cdots>c_{\ell}$ and
$d_{1}>d_{2}>\cdots>d_{n-j-\ell-1}$. This is because besides $n$ and $j$,
every other element must be arranged in a decreasing order on the cycle.

1234567812345678 Figure 3. Examples of permutations in $\mathfrak{S}_{8}$ with
7 antiexceedances; the permutation on the left is of the form with two cycles
while that on the right has one cycle.

The following claim allows us to extract properties of antiexceedances of the
permutations in $\operatorname{Pop_{T}}$ orbits of $A$-splittable $w$.

######  Lemma 2.4.

Let $w\in\mathfrak{S}_{n}$ be $A$-splittable. Suppose
$\operatorname{cyc_{>1}}(\operatorname{Pop_{T}}^{j}(w))=1$ for all $j<i$. If
neither $\alpha$ nor $\beta$ are antiexceedances in
$\operatorname{Pop_{T}}^{i}(w)$, and $\gamma>\max\\{\alpha,\beta\\}$, then
$\gamma$ not an antiexceedance in $\operatorname{Pop_{T}}^{i}(w)$.

It will eventually turn out that the hypothesis in Lemma 2.4 that
$\operatorname{cyc_{>1}}(\operatorname{Pop_{T}}^{j}(w))=1$ for all $j<i$ is
unnecessary, but a priori we do not know that $A$-splittable permutations
satisfy $\operatorname{cyc_{>1}}(\operatorname{Pop_{T}}^{k}(w))=1$ for all
$k$.

###### Proof.

We will use the following fact extracted from [11, Theorem 5.2]:
$r\in\operatorname{Aexc}(u)\setminus\operatorname{Aexc}(\operatorname{Pop_{T}}(u))$
if and only if $u^{-1}(r)$ is the largest entry in a non-singleton cycle of
$\pi_{T}(u)$. Let $t_{k}$ be the largest element in the non-singleton cycle of
$\operatorname{Pop_{T}}^{k}(w)$.

Suppose $w$ consists of two cycles. If $\alpha$ and $\beta$ are in the same
cycle, without loss of generality $\alpha<\beta$, so
$w^{-1}(\alpha)<\alpha<\gamma<w^{-1}(\gamma)$. Note that since
$w_{k}^{-1}(x)=v_{k}(v_{k-1}(\cdots v_{1}(w^{-1}(x))\cdots))$ and each $v_{k}$
results in a clockwise movement of the indices, we get a decreasing sequence
$t_{i}-w_{i}(x)$ until it reaches 0 at which point $x$ ceases to be an
antiexceedance. Since $w^{-1}(\gamma)>w^{-1}(\alpha)$, it follows that the
indices $j_{\alpha},j_{\gamma}$ for which $w_{i}^{-1}(j_{\gamma})=t_{k}$ for
some $k<i$ satisfy the property that $j_{\gamma}<j_{\alpha}$. In particular,
$\gamma\in\operatorname{Aexc}(\operatorname{Pop_{T}}^{j_{\gamma}}(w))\setminus\operatorname{Aexc}(\operatorname{Pop_{T}}^{j_{\gamma+1}}(w))\subset\operatorname{Aexc}(\operatorname{Pop_{T}}^{j_{\alpha}}(w))\setminus\operatorname{Aexc}(\operatorname{Pop_{T}}^{j_{\alpha+1}}(w))$
which is equivalent to the desired conclusion. If $\alpha$ and $\beta$ are not
in the same cycle, let $\mathscr{C}$ be the cycle in $w$ containing $\gamma$,
then note that one of $\alpha$ or $\beta$, without loss of generality assume
it is $\alpha$, is situated counterclockwise along $\mathscr{C}$ from
$\gamma>\max\\{\alpha,\beta\\}$. This implies that
$w^{-1}(\alpha)<w^{-1}(\gamma)$ and we can conclude with the same argument as
earlier.

Suppose $w$ consists of one cycle, and the two elements that are _not_
antiexceedances are given by $j$ and $n$. As before, it suffices to prove that
$w^{-1}(\gamma)>\min\\{w^{-1}(\alpha),w^{-1}(\gamma)\\}$. First, note that if
$\gamma>j$ then we get the desired conclusion. If $\gamma<j$, we first
consider the case that $\alpha=d_{j}$ and $\beta=d_{k}$ for some indices $j$
and $k$. without loss of generality $j<k$. Then
$w^{-1}(\alpha)<\beta<\gamma<w^{-1}(\gamma)$, as desired. The case that
$\alpha=c_{j}$ and $\beta=c_{k}$ is similar. Lastly, suppose $\alpha=c_{j}$
and $\beta=d_{k}$ for some indices $j,k$. If $\gamma=c_{m}$ for some $m<j$
then $w^{-1}(\gamma)>w^{-1}(\alpha)$; similarly, if $\gamma=d_{q}$ for some
$q<k$ then $w^{-1}(\gamma)>w^{-1}(\beta)$. ∎

###### Proof of first part of Theorem 1.5.

We have already established the “only if” part of the claim earlier. It
suffices to check the “if” direction.

We induct on $i$ to show that if $w\in\mathfrak{S}_{n}$ is a $A$-splittable
permutation then
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(w)))=1$. The base
case $i=0$ is true by assumption. Next, we handle the inductive step. Suppose
the largest element in the non-singleton cycle of
$\pi_{T}(\operatorname{Pop_{T}}^{i}(w))$ is $t$ and the smallest element is
$\tilde{t}$. For simplicity of notation, write
$\operatorname{Pop_{T}}^{i}(w)=w_{i}$ and
$\pi_{T}(\operatorname{Pop_{T}}^{i}(w))=v_{i}$.

Now, we must prove that
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i+1}(w)))=1$.
Equivalently, we need to prove that for any $r>s$ with
$r,s\in\\{x:w_{i+1}(x)\neq x\\}$ and $s\neq v_{i+1}(r)$ (that is, $r,s$ are
not fixed points under $w_{i+1}$ and $s$ does not immediately succeed $r$ in
$v_{i+1}$) one of the following conditions holds:

  1. (1)

There exist $a\in[s+1,r-1]$ and $b\in[r+1,n]\cup[1,s-1]$ such that either
$w_{i+1}(a)=b$ or $w_{i+1}(b)=a$.

$r$$s$$a$$b$$r$$s$$a$$b$ Figure 4. Illustration of condition (1).

  2. (2)

There exist $e_{1}\in[r+1,s-1]$ and $f_{1}\in[s+1,n]\cup[1,r-1]$ such that
either $w_{i+1}(e_{1})=r$ and $w_{i+1}(r)=f_{1}$ or $w_{i+1}(f_{i})=r$ and
$w_{i+1}(r)=e_{1}$.

$r$$s$$f_{1}$$e_{1}$$r$$s$$f_{1}$$e_{1}$ Figure 5. Illustration of condition
(2).

  3. (3)

There exist $e_{1}\in[r+1,s-1]$ and $f_{1}\in[s+1,n]\cup[1,r-1]$ such that
either $w_{i+1}(e_{1})=s$ and $w_{i+1}(s)=f_{1}$ or $w_{i+1}(f_{i})=s$ and
$w_{i+1}(s)=e_{1}$.

$r$$s$$f_{1}$$e_{1}$$r$$s$$f_{1}$$e_{1}$ Figure 6. Illustration of condition
(3).

  4. (4)

We have $w_{i+1}(r)=s$,
$\\{w_{i+1}^{-1}(r),w_{i+1}(s)\\}\cap[r+1,s-1]\neq\emptyset$ and
$\\{w_{i+1}^{-1}(r),w_{i+1}(s)\\}\cap\\{[s+1,n]\cup[1,r-1]\\}$.

$r$$s$$w_{i+1}(s)$$w_{i+1}^{-1}(r)$$r$$s$$w_{i+1}^{-1}(r)$$w_{i+1}(s)$ Figure
7. Illustration of condition (4).

  5. (5)

We have $w_{i+1}(s)=r$,
$\\{w_{i+1}^{-1}(s),w_{i+1}(r)\\}\cap[r+1,s-1]\neq\emptyset$ and
$\\{w_{i+1}^{-1}(s),w_{i+1}(r)\\}\cap\\{[s+1,n]\cup[1,r-1]\\}$.

$r$$s$$w_{i+1}^{-1}(s)$$w_{i+1}(r)$$r$$s$$w_{i+1}(r)$$w_{i+1}^{-1}(s)$ Figure
8. Illustration of condition (5).

Since $\\{x:w_{i+1}(x)\neq x\\}\subset\\{x:w_{i}(x)\neq x\\}$, note that
coupled with the induction hypothesis we know that for any $r,s$ satisfying
the aformentioned properties, one of the above five conditions hold when we
condition the permutation $w_{i}$ in lieu of $w_{i+1}$. In particular, we will
show that after operating with the $\operatorname{Pop_{T}}$ operator, we
preserve the property that one of the above five conditions continues to hold.

Before we prove that claim, we first make a reduction. Note that we may
without loss of generality assume that $w_{i}(r)\in[r+1,s]$ because if
$w_{i}(r)\in[s+1,n]\cup[1,r-1]$, then since $v_{i}(r)\in[r+1,s-1]$, it follows
that we have $w_{i+1}(v_{i}(r))=w_{i}(r)$ satisfies condition (1) above. In
particular, this in turn implies that we may without loss of generality assume
that $w_{i}(r)$ is not an antiexceedance in $w_{i}$.

$r$$s$$w_{i}(r)$$v_{i}(r)$ Figure 9. Illustration of why if
$w_{i}(r)\in[s+1,n]\cup[1,r-1]$, then condition (1) is satisfied. The black
edge is part of the diagram for $w_{i}$ and the blue edge is part of the
diagram for $w_{i+1}$.

An identical argument shows that we may suppose without loss of generality
that $w_{i}(s)\in[s+1,n]\cup[1,r]$.

Now, we split into cases.

  1. (I)

Condition (1) above is satisfied for $w_{i}$ and there exists $a\in[r+1,s-1]$
and $b\in[s+1,n]\cup[1,r-1]$ such that $w_{i+1}(b)=a$. Note that if $b\neq
v_{i}^{-1}(r)$, then
$w_{i+1}^{-1}(b)=v_{i}(w_{i}^{-1}(b))=v_{i}(a)\in[s+1,n]\cup[1,r-1]$, and
consequently condition (1) would continue to hold for $w_{i+1}$. It remains to
handle the case that $b=v_{i}^{-1}(r)$.

Suppose for the sake of contradiction that $w_{i+1}$ does not satisfy one of
the five conditions.

First, consider the situation of $v_{i}^{-1}(r)<r$. Then, because
$w_{i}(v_{i}^{-1}(r))\in[r+1,s]$, it is not an antiexceedance in $w_{i}$. Now,
our reduction above gave us that $w_{i}(r)$ is not an antiexceedance in
$w_{i}$.

We claim that $w_{i}^{-1}(t)\not\in[1,r-1]$. To see why this is the case,
observe that because $\operatorname{cyc_{>1}}(\pi_{T}(v_{j}))=1$ for all
$j\leq i$, it follows that if $x,y,z$ are not fixed points of $w_{i}$ (and
consequently not fixed points of $w_{j}$ for any $j\leq i$) then if
$w_{i}^{-1}(x),w_{i}^{-1}(y),w_{i}^{-1}(z)$ appear in this order clockwise on
the circle then $w_{j}^{-1}(x),w_{j}^{-1}(y),w_{j}^{-1}(z)$ appear in this
order clockwise for all $j\leq i$. If $w_{i}^{-1}(t)\in[1,r-1]$, then in
particular we have that $w_{i}^{-1}(t),v_{i}^{-1}(r),r$ appear clockwise in
this order. In particular, there exists some $k$ such that
$w_{k}^{-1}(t)>t,w_{k}^{-1}(w_{i}(v_{i}^{-1}(r))),w_{k}^{-1}(w_{i}(r))$. In
$w_{k}$, $t$ is an antiexceedance while $v_{i}^{-1}(r),r$ are not
antiexceedances. This is a contradiction to Lemma 2.4.

Let $\mathcal{N}$ be the set of numbers clockwise from $v_{i}^{-1}(s)$ to $t$
lying in $v_{i}$ that are not antiexceedances in $w_{i}$. By Lemma 2.4, all
numbers in $\mathcal{N}$ are not antiexceedances in $w_{i}$. Using an
identical argument as the previous paragraph, we can show that any
$q\in\mathcal{N}$ satisfies $w_{i}^{-1}(q)\not\in[1,r-1]$.

Let $\mathcal{Z}$ denote the set of elements situated clockwise from
$\tilde{t}$ to $r$. We claim that there exists an element $z\in\mathcal{Z}$
such that $w_{i}^{-1}(z)\in[s,n]$. This would then provide a contradiction to
the previous paragraph. To show the claim, first note that if
$w_{i}^{-1}(z)\in[r+1,s-1]$ then by the previous paragraph it follows that
$w_{i}^{-1}(z)<v_{i}^{-1}(s)$ and in particular $w_{i+1}^{-1}(z)\in[r+1,s-1]$
as well which would then allow us to satisfy condition (1). Consequently, it
suffices to rule out the possibility that $w_{i}^{-1}(z)\in[1,s-1]$ for all
such elements $z\in\mathcal{Z}$. Note that $w_{i}^{-1}(z)\neq v_{i}^{-1}(s)$.
Consequently, there are only $|\mathcal{Z}|-1$ possibilities for the values of
$w_{i}^{-1}(z)$, which is a contradiction. Refer to Figure 10 for a depiction
of this claim.

$r$$s$$v_{i}^{-1}(r)$$w_{i}(v_{i}^{-1}(r))$$w_{i}(r)$$t$$\tilde{t}$$z$$\tilde{t}$$s$$t$$w_{i}(t)$$w_{i}(\tilde{t})$$v_{i}^{-1}(s)$
Figure 10. Illustrations for case (I). The figure on the left is a depiction
of the situation when $v_{i}^{-1}(r)<r$. On the right, the figure shows the
situation when $r=\tilde{t}$. Here the blue edges should be thought of as part
of the diagram for $w_{i+1}$. The red nodes are not antiexceedances.

Next, we handle the case where $v_{i}^{-1}(r)>r$. This case can only occur if
$r=\tilde{t}$ and $v_{i}^{-1}(r)=t$. Note by our earlier reduction we have
that $w_{i}(\tilde{t})\geq w_{i+1}^{-1}(w_{i}(\tilde{t}))$ and since
$w_{i+1}(r)=w_{i}(t)>r$, it follows that $w_{i}(t)$ and $w_{i}(\tilde{t})$ are
both not antiexceedances in $w_{i+1}$. By Lemma 2.4, we have that $s$ and
$v_{i}(s)$ are both not antiexceedances in $w_{i+1}$ as well. If
$w_{i+1}^{-1}(v_{i}(s))\in[\tilde{t},s-1]$ then we satisfy condition (1).
Otherwise, we necessarily have $w_{i+1}^{-1}(v_{i}(s))=s$. But we also know
that $w_{i+1}^{s}<s$, and consequently we satisfy condition (3), a
contradiction as desired.

  2. (II)

Condition (1) above is satisfied for $w_{i}$ and there exists $a\in[r+1,s-1]$
and $b\in[s+1,n]\cup[1,r-1]$ such that $w_{i+1}(a)=b$. We may assume that
$w_{i}(v_{i}^{-1}(r))\not\in[r+1,s-1]$ as otherwise we may reduce to case (I).
Analogously as above, if $a\neq v_{i}^{-1}(s)$ then we get that condition (1)
is satisfied for $w_{i+1}$. Consequently, henceforth we will assume that
$a=v_{i}^{-1}(s)$.

Suppose for the sake of contradiction that $w_{i+1}$ does not satisfy one of
the five conditions.

If $w_{i}^{-1}(v_{i}^{-1}(s))>v_{i}^{-1}(s)$ then it follows that
$w_{i}^{-1}(v_{i}^{-1}(s))\in[s+1,n]\cup[1,v_{i}^{-1}(r))$. Here we have
$w_{i}^{-1}(v_{i}^{-1}(s))\neq s$ because $s$ is not a fixed point in
$w_{i+1}$ and $w_{i}^{-1}(v_{i}^{-1}(s))\neq v_{i}^{-1}(r)$ because we are not
in case (I). In particular, $w_{i+1}^{-1}(v_{i}^{-1}(s))\in[s+1,n]\cup[1,r-1]$
and so condition (1) is satisfied for $w_{i+1}$, which is a contradiction.
Now, we have that $v_{i}^{-1}(s)\in[r+1,s-1]$ is not an antiexceedance in
$w_{i}$ and so in particular $v_{i}^{-2}(s)\in[r+1,s-1]$. Similarly, since
$v_{i}^{-2}(s)\neq v_{i}^{-1}(r)$ we must have that
$v_{i}^{-2}(s)\in[r+1,s-1]$ and it is not an antiexceedance in $w_{i}$ either.
By Lemma 2.4 we have that $s$ is not an antiexceedance in $w_{i}$ as well. We
can show that $w_{i}^{-1}(s)\not\in[1,r-1]$ by a similar argument as in case
(I) by considering the relative clockwise positions of
$w_{i}^{-1}(s),w_{i}^{-1}(v_{i}^{-1}(s)),w_{i}^{-1}(v_{i}^{-2}(s))$.
Consequently, $w_{i}^{-1}(s)\in[r+1,s-1]$ and in particular
$w_{i+1}(s)\in[s+1,n]\cup[1,r-1]$ while $w_{i+1}^{-1}(s)\in[r+1,s-1]$ so that
condition (3) is satisfied for $w_{i+1}$, which is a contradiction.

$r$$s$$v_{i}^{-2}(s)$$v_{i}^{-1}(s)$ Figure 11. An illustration of case (II).
Here the red nodes are not antiexceedances. The blue edges should be thought
of as part of $w_{i+1}$.

  3. (III)

Condition (2) above is satisfied for $w_{i}$. Because of the reduction we made
before we split into cases, in this case we necessarily have that
$w_{i}^{-1}(r)\in[s+1,n]\cup[1,r-1]$ and $w_{i}(r)\in[r+1,s-1]$. Suppose for
the sake of contradiction that $w_{i+1}$ does not satisfy one of the five
conditions. We may assume that we are not in either of cases (I) or (II). That
is, we may assume that $w_{i}(v_{i}^{-1}(r))\in[s+1,n]\cup[1,r]$ and

$w_{i}(v_{i}^{-1}(s))\in[r,s-1].$ (1)

Note that since by assumption of condition (2), $w_{i}^{-1}(r)\neq
v_{i}^{-1}(s)$ so that $w_{i+1}(s)\in[r+1,s-1]$. Now we split further into
cases. First, if $w_{i}^{-1}(s)\in[s+1,n]\cup[1,v_{i}^{-1}(r))$, then we
satisfy condition (2), a contradiction. If $w_{i}^{-1}(s)=v_{i}^{-1}(r)$ so
that $w_{i+1}(r)=s$ then (1) tells us that condition (4) is satisfied, a
contradiction. Otherwise, $w_{i}^{-1}(s)<s$ and both $w_{i}(r)$ and $s$ are
not antiexceedances in $w_{i}$ and so it follows from Lemma 2.4 that
$v_{i}(s)$ is also not an antiexceedance in $w_{i}$. As in case (I), we may
argue that $w_{i}^{-1}(v_{i}(s))\not\in[1,r-1]$ by considering the relative
clockwise positions of $w_{i}^{-1}(v_{i}(s)),r,w_{i}^{-1}(v_{i}^{-1}(s))$.
Consequently, $w_{i}^{-1}(v_{i}(s))\in[r+1,s]$.

Suppose $w_{i}^{-1}(v_{i}(s))\neq s$. By assumption since we are not in case
(II), it follows that $w_{i}^{-1}(v_{i}(s))\neq v_{i}^{-1}(s)$ so that
$w_{i+1}(v_{i}(s))\in[1,s-1]$ and so condition (1) is satisfied, which is a
contradiction.

It remains to handle the case where $w_{i}^{-1}(v_{i}(s))=s$. Now, consider
the same argument as above for $v_{i}^{2}(s)$. Similarly, we show that if
$w_{i}^{-1}(v_{i}^{2}(s))\neq v_{i}(s)$, then $w_{i+1}$ satisfies one of the
five conditions. Iteratively applying this argument it follows that for all
elements $z$ in $v_{i}$ clockwise from $v_{i}(s)$ to $t$, we have that
$v_{i+1}(z)=z$. In particular, since
$w_{i}^{-1}(r),w_{i}^{-1}(v_{i}^{-1}(r))\in\\{t\\}\cup[1,r-1]$, this implies
that $w_{i+1}^{-1}(r),w_{i+1}^{-1}(v_{i}^{-1}(r))\in[\tilde{t},v_{i}^{-1}(r))$
are both not antiexceedances in $w_{i+1}$. By Lemma 2.4, this implies that
$v_{i}(r)$ is not an antiexceedance in $w_{i+1}$ as well, and in particular
because we are not in case (I), we have that $w_{i+1}^{-1}(v_{i}(r))<r$, which
means $w_{i+1}$ satisfies condition (1), a contradiction.

$r$$s$$w_{i}^{-1}(s)$$v_{i}(s)$ Figure 12. An illustration for case (III). The
nodes labelled red are not antiexceedances.

  4. (IV)

Condition (3) is satisfied for $w_{i}$. This case is very similar to case
(III). Because of the reduction that we made before we split into cases, in
this case we necessarily have that $w_{i}^{-1}(s)\in[r+1,s-1]$ and
$w_{i}(s)\in[s+1,n]\cup[1,r-1]$. Suppose for the sake of contradiction that
$w_{i+1}$ does not satisfy one of the five conditions. We may assume that we
are not in either of case (I) so that $w_{i}^{-1}(v_{i}^{-1}(s))\neq
v_{i}^{-1}(r)$ and in particular $w_{i}^{-1}(v_{i}^{-1}(s))\in[r+1,s-1]$. That
is, $v_{i}^{-1}(s)$ is not an antiexceedance in $w_{i}$. We may also assume
that we are not in case (II) so that $w_{i}^{-1}(v_{i}(s))\neq v_{i}^{-1}(r)$.
Furthermore, we may also assume that $w_{i}^{-1}(r)\in[s+1,n]\cup[1,r-1]$.
This is because $w_{i+1}(r)=w_{i}(v_{i}^{-1}(r))\in[s+1,n]\cup[1,r-1]$ and if
$w_{i}^{-1}(r)\in[r+1,s-1]$ then $w_{i+1}$ would satisfy condition (2) if
$w_{i}^{-1}(r)\in[s-1]$ and would satisfy condition (4) if $w_{i}^{-1}(r)=s$
since $w_{i}^{-1}(v_{i}^{-1}(s))\in[r+1,s-1]$.

Since $s$ is also by assumption not an antiexceedance in $w_{i}$, it follows
by Lemma 2.4 that $v_{i}(s)$ is not an antiexceedance in $w_{i}$ either. By a
similar argument as in case (I), we can show that
$w_{i}^{-1}(v_{i}(s))\not\in[1,r-1]$ by considering the relative clockwise
positions of $w_{i}^{-1}(v_{i}(s)),w_{i}^{-1}(s),w_{i}^{-1}(v_{i}^{-1}(s))$.

If $w_{i}^{-1}(v_{i}(s))<v_{i}^{-1}(s)$, then we get that $w_{i+1}$ satisfies
condition (2), a contradiction. Otherwise, we have that
$w_{i}^{-1}(v_{i}(s))=s$ so that $w_{i+1}(v_{i}(s))=v_{i}(s)$.

Now, consider the same argument for $v_{i}^{2}(s)$. Similarly, we show that if
$w_{i}^{-1}(v_{i}^{2}(s))\neq v_{i}(s)$ then $w_{i+1}$ satisfies one of the
five conditions. Iteratively applying this argument it follows that for all
elements $z$ in $v_{i}$ clockwise from $v_{i}(s)$ to $t$, we have that
$v_{i+1}(z)=z$. In particular, since
$w_{i}^{-1}(r),w_{i}^{-1}(v_{i}^{-1}(r))\in\\{t\\}\cup[1,r-1]$, this implies
that $w_{i+1}^{-1}(r),w_{i+1}^{-1}(v_{i}^{-1}(r))\in[\tilde{t},v_{i}^{-1}(r))$
are both not antiexceedances in $w_{i+1}$. By Lemma 2.4, this implies that
$v_{i}(r)$ is not an antiexceedance in $w_{i+1}$ as well, and in particular
because we are not in case (I), we have that $w_{i+1}^{-1}(v_{i}(r))<r$, which
means $w_{i+1}$ satisfies condition (1), a contradiction.

  5. (V)

Condition (4) is satisfied for $w_{i}$. Because of the reduction we made
before splitting into cases, it follows that we necessarily have that
$w_{i}^{-1}(r)\in[r+1,s-1]$ and $w_{i}(s)\in[s+1,n]\cup[1,r-1]$. We may assume
that we are not in cases (I) or (II) so that
$w_{i}^{-1}(v_{i}^{-1}(r))\in[s+1,n]\cup[1,r-1]$ and
$w_{i}^{-1}(v_{i}^{-1}(s))\in[r,s-1]$. If $w_{i}(r)\neq v_{i}^{-1}(s)$, then
$w_{i+1}^{-1}(r)\in[r+1,s-1]$ and
$w_{i+1}(r)=w_{i}^{-1}(v_{i}^{-1}(r))\in[s+1,n]\cup[1,r-1]$ so that $w_{i+1}$
satisfies condition (1).

If $w_{i}(r)=v_{i}^{-1}(s)$, then $w_{i+1}^{-1}(s)=v_{i}(r)\in[r+1,s-1]$,
$w_{i+1}(s)=r$ and
$w_{i+1}^{-1}(r)=w_{i}^{-1}(v_{i}^{-1}(r))\in[s+1,n]\cup[1,r-1]$ so that
$w_{i+1}$ satisfies condition (5).

$r$$s$$r$$s$$v_{i}(r)$$v_{i}^{-1}(s)$ Figure 13. An illustration for case
(VI). The black edges are part of the diagram for $w_{i}$ while the blue edges
are part of the diagam for $w_{i+1}$. On the left, $w_{i}(r)\neq
v_{i}^{-1}(s)$ and on the right we have the situation where
$w_{i}(r)=v_{i}^{-1}(s)$.

  6. (VI)

Condition (5) is satisfied for $w_{i}$. Because of the reduction we made
before splitting into cases, it follows that we necessarily have that
$w_{i}(r)\in[r+1,s-1]$ and $w_{i}^{-1}(s)\in[s+1,n]\cup[1,r-1]$. We may assume
that we are not in case (II) so that
$w_{i}^{-1}(v_{i}^{-1}(r))\in[s,n]\cup[1,r-1]$ and
$w_{i}^{-1}(v_{i}^{-1}(s))\in[r+1,s-1]$.

If $w_{i}^{-1}(s)\neq v_{i}^{-1}(r)$, then $w_{i+1}(s)\in[s+1,n]\cup[1,r-1]$
while $w_{i+1}(s)=w_{i}^{-1}(v_{i}^{-1}(s))\in[r+1,s-1]$ so that $w_{i+1}$
satisfies condition (2).

If $w_{i}^{-1}(s)=v_{i}^{-1}(r)$, then $w_{i+1}(r)=s$,
$w_{i+1}^{-1}(r)=v_{i}(s)\in[s+1,n]\cup[1,r-1]$ while
$w_{i+1}(s)=w_{i}^{-1}(v_{i}^{-1}(s))\in[r+1,s-1]$ so that $w_{i+1}$ satisfies
condition (4).

$r$$s$$r$$s$$v_{i}^{-1}(r)$$v_{i}(s)$ Figure 14. An illustration for case
(VI). The black edges are part of the diagram for $w_{i}$ while the blue edges
are part of the diagam for $w_{i+1}$. On the left, $w_{i}^{-1}(s)\neq
v_{i}^{-1}(r)$ and on the right we have the situation where
$w_{i}^{-1}(s)=v_{i}^{-1}(r)$.

∎

To count the number of $A$-splittable permutations, we make a psychological
shift to work with _ascents_ instead.

######  Definition 2.5.

An _ascent_ of a permutation $w\in\mathfrak{S}_{n}$ is an element $i\in[n]$
such that $w(i)<w(i+1)$.

The following result is folklore, but since the proof is short we include it
for completeness.

######  Lemma 2.6.

The number of permutations $w\in\mathfrak{S}_{n}$ with exactly $n-2$ ascents
is given by $2^{n}-n-1$.

###### Proof.

For simplicity of notation in the proof, note that by reversing the
permutation it suffices to show that the number of permutations with exactly
one ascent is given by $2^{n}-n-1$.

Let $f(n)$ be the number of permutations with exactly one ascent. We will
prove this lemma via induction, with base case $n=1$ vacuously true. For the
inductive step, observe that it suffices to prove the recurrence
$f(n)=f(n-1)+2^{n-1}-1$. This recurrence follows by studying where $n$ lies
when considering the single-line notation of the permutation $w$. If $n$ is
the first element in the single-line notation, then it follows that the
remaining $n-1$ elements need to have an ascent, and there are $f(n-1)$ such
permutations. Otherwise, if $n$ is not the first element then the element
before $n$ forms an ascent and there cannot be any other ascents. In other
words, we can split $\\{1,\ldots,n-1\\}=A\sqcup B$ into two sets: $A$ contains
elements occurring before $n$, and $B$ contains elements occurring after $n$.
Within $A$ and $B$, the elements occur in decreasing order. Furthermore,
$A\neq\emptyset$. There are $2^{n-1}-1$ ways to make such a partition: pick
which of $A$ and $B$ each of the $n-1$ elements lie in, but we need to remove
one of the possibilities where $A=\emptyset$. ∎

######  Lemma 2.7.

The _Foata bijection_ provides a mapping between the permutations
$w\in\mathfrak{S}_{n}$ with exactly $n-2$ antiexceedances and the number of
permutations $w^{\prime}\in\mathfrak{S}_{n}$ with exactly $n-2$ ascents.

We omit the proof of this lemma since it is well-known. The bijection
transfers antiexceedances to ascents.

Combining the two previous lemmas, we have the following classical result.

######  Corollary 2.8.

The number of permutations $w\in\mathfrak{S}_{n}$ with exactly $n-2$
antiexceedances is given by $2^{n}-n-1$.

###### Proof of second part of Theorem 1.5.

By Corollary 2.8, there are $2^{n}-n-1$ permutations with exactly $n-2$
antiexceedances. Of these $2^{n}-n-1$ permutations $w$ we need to count the
subset of them such that $\operatorname{cyc_{>1}}(\pi_{T}(w))=1$. If
$\pi_{T}(w)$ has more than one cycle and has exactly $n-2$ antiexceedances,
then it necessarily has exactly two cycles. In particular, there exists some
indices $i,j$ with $i\leq j$ such that $(i\enspace i+1\enspace\cdots\enspace
j$) form one cycle in $\pi_{T}(w)$ while $(j+1\enspace\cdots\enspace n\enspace
1\enspace\cdots\enspace i-1)$ forms the other. Note however that when $i=j$,
we have that $\operatorname{cyc_{>1}}(\pi_{T}(w))=1$ and such $w$ are actually
$A$-splittable. In total, the number of permutations $w$ such that
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$ is given by
$2^{n}-n-1-\binom{n}{2}+n=2^{n}-\binom{n}{2}-1$, where the $-\binom{n}{2}$
comes from choosing the indices $i,j$ and the $+n$ comes from when $i=j$. ∎

##  3\. Type B

The _hyperoctahedral group_ $B_{n}$ is the group of permutations $w$ of
$\pm[n]$ such that $w(\overline{i})=\overline{w(i)}$. In this section, we
replace negative signs with bars $\overline{\bullet}$ for ease of notation. We
fix the Coxeter element
$c=(\bar{1}\enspace\bar{2}\enspace\cdots\enspace\bar{n}\enspace 1\enspace
2\enspace\cdots\enspace n)$ of $B_{n}$.

The argument in this case is similar to that in type A. It is of interest
whether we can prove the result for type B via the operation of folding (as
described for instance in [11, Section 4.3]) while using the result for type A
as a black-box. Here we content ourselves with modifying the argument in the
previous section appropriately.

In fact, the combinatorial model for $B_{n}$ can be vaguely thought of as the
combinatorial model for $A_{2n}$ “with $180^{\circ}$ rotation symmetry”. More
precisely, let us briefly expound upon the combinatorial model for
$NC(B_{n},c)$. Label $2n$ equidistant points on a circle with the numbers
$\overline{1},\overline{2},\ldots,\overline{n},1,2,\ldots,n$ in clockwise
order.

######  Definition 3.1.

A set partition $\pi$ of $\pm[n]$ is a _type- $B_{n}$ noncrossing set
partition_ if the resulting diagram from drawing the convex hull of each block
is invariant under $180^{\circ}$ rotation and the convex hulls of different
blocks do not intersect each other.

As in the case for type $A$ Coxeter groups, for a given type-$B_{n}$
noncrossing set partition, we may form an element of $NC(B_{n},c)$ through the
conversion of each block to a cycle by ordering the elements of the block
cyclically in clockwise order around the circle. The product of these cycles
is a noncrossing partition in $NC(B_{n},c)$ and every noncrossing partition in
$NC(B_{n},c)$ arises uniquely in this way. Similarly to the case of type $A$
Coxeter groups, the partial order on $NC(B_{n},c)$ corresponds to the reverse
refinement order on type-$B_{n}$ noncrossing set partitions. The noncrossing
projection of $w\in B_{n}$ is similarly the smallest noncrossing partition
$v\in NC(B_{n},c)$ such that every cycle in $w$ is contained in a cycle in $v$
(as sets).

1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$
Figure 15. The permutation $w:=(2\enspace 3\enspace
4)(\bar{2}\enspace\bar{3}\enspace\bar{4})(6\enspace\bar{6})(1\enspace\bar{5}\enspace\bar{1}\enspace
5)\in B_{6}$ (left), its non-crossing projection $\pi_{T}(w)=(2\enspace
3\enspace 4)(\bar{2}\enspace\bar{3}\enspace\bar{4})(1\enspace 5\enspace
6\enspace\bar{1}\enspace\bar{5}\enspace\bar{6})$ (middle), and its image under
$\operatorname{Pop_{T}}$ given by $\operatorname{Pop_{T}}(w)=(1\enspace
6)(\bar{1}\enspace\bar{6})(5\enspace\bar{5})(2)(3)(4)(\bar{2})(\bar{3})(\bar{4})$
(right)

Define a total order on $\pm[n]$ by

$\overline{1}\prec\overline{2}\prec\cdots\prec\overline{n}\prec 1\prec
2\prec\cdots\prec n.$

In this setting, we have a similar notion of antiexceedance as in Definition
1.6, paralleling that in $A_{n}$, where we replace $<$ with $\prec$.

We have an equivalent of Lemma 2.2 in the setting of $B_{n}$. An illustration
of this result is in Figure 15, where the antiexceedances are the vertices
marked in red.

######  Lemma 3.2 ([11, Theorem 5.6]).

The following properties relating antiexceedances and $\operatorname{Pop_{T}}$
hold:

  1. (a)

The element $c^{-1}$ has $2n-1$ antiexceedances.

  2. (b)

Every element of $B_{n}$ other than $c^{-1}$ has at most $2n-2$
antiexceedances.

  3. (c)

For every $w\in B_{n}$, we have
$\operatorname{aexc}(\operatorname{Pop_{T}}(w))=\operatorname{aexc}(w)-\operatorname{cyc_{>1}}(\pi_{T}(w))$.

In the setting of $B_{n}$, recall Definition 1.7 that an element $w\in B_{n}$
is _$B$ -splittable_ if it contains exactly $2n-2$ antiexceedances and
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$. We recall Theorem 1.7.

See 1.7

The proof of the first part of Theorem 1.7 is analogous to that for type $A$.
This is because the only condition that we need to verify is that when $w\in
B_{n}$ is $B$-splittable then
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(w)))=1$ for all
$i\geq 0$. We can run the exact same proof as that for the first part of
Theorem 1.5 where we can reindex and consider $w\in B_{n}$ as a permutation of
$[2n]$ and apply Theorem 1.5 on $[2n]$. However, because of the
$180^{\circ}$-rotation symmetry of elements in $B_{n}$, we need to be slightly
more careful when we count the number of $B$-splittable elements.

Combining Theorem 1.7 with [11, Theorem 5.1], we prove [11, Conjecture 5.8].

######  Corollary 3.3 ([11, Conjecture 5.8]).

The number of elements of $B_{n}$ that require exactly $2n-2$ or $2n-1$
iterations of $\operatorname{Pop_{T}}$ to reach the identity is $2^{n}-n$.

###### Proof of second part of Theorem 1.7.

First, note that if $w\in B_{n}$ is $B$-splittable and has more than one cycle
then it contains exactly two cycles. Next, observe that in order for
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$, if $w$ has two cycles, then for each
of the cycles $\mathscr{C}$ there exists an index $i$ such that
$i,\overline{i}\in\mathscr{C}$. This is simply because otherwise
$\mathscr{C}_{1}$ would consist of $1,2,\ldots,n$ and $\mathscr{C}_{2}$ would
consist of $\overline{1},\overline{2},\ldots,\overline{n}$ and it is evident
that for any such element $w$, we have that
$\operatorname{cyc_{>1}}(\pi_{T}(w))=2$. Consequently, for each cycle
$\mathscr{C}$ in $w\in B_{n}$, there exists $\overline{i}\in\mathscr{C}$ such
that $w^{-1}(\overline{i})=j$ for some $j\in[n]$. By definition of $B_{n}$, we
also necessarily have that $w(\overline{j})=i$. As such, the two elements that
are not antiexceedances are precisely given by $w(\overline{j}_{1})=i_{1}$ and
$w(\overline{j}_{2})=i_{2}$, where we have one such antiexceedance in each of
the two cycles. Every other element of $w$ is therefore an antiexccedance.
Observe further that $\min\\{\overline{j}_{1},\overline{j}_{2}\\}=1$.

The previous paragraph allows us to count $B$-splittable elements as follows.
Note that every element of $w\in B_{n}$ can be written in a “single-line
notation” where we only keep track of $w(i)$ for
$i\in\\{\overline{n},\overline{n-1},\ldots,\overline{1}\\}$, which in turn
specifies $w(i)$ since $w(i)=\overline{w(\overline{i})}$. For instance,
$1\enspace 4\enspace\overline{3}\enspace 5\enspace\overline{2}$ corresponds to
the element $w\in B_{5}$ such that $w(\overline{1})=1$, $w(\overline{2})=4$,
$w(\overline{3})=\overline{3}$, $w(\overline{4})=5$,
$w(\overline{5})=\overline{2}$, $w(1)=\overline{1}$, $w(2)=\overline{4}$,
$w(3)=3$, $w(4)=\overline{5}$, $w(5)=2$. We can map every element of $B_{n}$
into an element of $\mathfrak{S}_{n}$ via this single-line notation as
follows: first remove the bar $\overline{\bullet}$ on any element of $w$ in
the single-line notation that has a bar and then consider the resulting
permutation as a single-line permutation representation of an element of
$\mathfrak{S}_{n}$. Continuing with the example from earlier, $1\enspace
4\enspace\overline{3}\enspace 5\enspace\overline{2}\in B_{5}$ maps to
$1\enspace 4\enspace 3\enspace 5\enspace 2\in\mathfrak{S}_{5}$. By our
observations in the previous paragraph, after this map we get a permutation of
$\mathfrak{S}_{n}$ with at most two elements that are not antiexceedances.

If the output of our map is $w^{\prime}\in\mathfrak{S}_{n}$ with exactly one
element that is not an antiexceedance, then it is necessarily $(n\enspace
n-1\enspace\cdots\enspace 1)$ by Lemma 2.2. In particular, the element $w\in
B_{n}$ we started off with would necessarily be of the form
$n\enspace\overline{1}\enspace\overline{2}\enspace\cdots\enspace\overline{i-1}\enspace
i\enspace\overline{i+1}\enspace\cdots\enspace\overline{n-1}$ in single-line
notation by the observations we made in the first paragraph of the proof. But
then $\operatorname{cyc_{>1}}(\pi_{T}(w))=2$ because $w$ is made up of two
cycles given by
$(\overline{1}\enspace\overline{2}\enspace\cdots\enspace\overline{i}\enspace
i+1\enspace i+2\enspace\cdots\enspace n)$ and $(1\enspace
2\enspace\cdots\enspace
i\enspace\overline{i+1}\enspace\cdots\enspace\overline{n})$. In other words,
if we started with $w\in B_{n}$ being $B$-splittable then this case is not
possible.

In the other case, we obtain $w^{\prime}\in\mathfrak{S}_{n}$ with exactly two
elements that are not antiexceedances, and we claim that we can uniquely
recover the element $w\in B_{n}$ that we started with and that
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$. Consequently, the number of
$B$-splittable elements in $B_{n}$ is exactly given by $2^{n}-n-1$. To prove
the claim, suppose $w^{\prime}$ is such that $w^{\prime}(i)=x_{i}$ and that
$x_{j}>j$ for $j\neq 1$. The observation in the first paragraph of the proof
implies that $w(\overline{1})=x_{1}$ and $w(\overline{i})=\overline{x_{i}}$
for $i\neq j$ while $w(\overline{j})=x_{j}$. Note that if $w$ is made up of
two cycles, then as sets the two cycles are
$\\{x_{1},x_{2},\ldots,x_{\ell},\overline{x_{1}},\overline{x_{2}},\ldots,\overline{x_{\ell}}\\}$
and
$\\{y_{1},y_{2},\ldots,y_{n-\ell},\overline{y_{1}},\overline{y_{2}},\ldots,\overline{y_{n-\ell}}\\}$
which then easily implies the desired conclusion of
$\operatorname{cyc_{>1}}(\pi_{T}(w))=1$. ∎

##  4\. Type D

The type $D_{n}$ case is rather subtle, because the combinatorial model we
work with of the non-crossing partition lattice (based on [4]) is more
complex. We begin with a quick recap on this combinatorial model of $D_{n}$ as
permutations on $\pm[n]$. The Coxeter group $D_{n}$ is the group of
permutations $w\colon\pm[n]\to\pm[n]$ such that
$w(\overline{i})=\overline{w(i)}$ (where $\overline{\bullet}$ replaces the
negative sign, for simplicity of notation) for all $i\in\pm[n]$ and
$\left|\\{i\in[n]:w(i)<0\\}\right|$ is even. The corresponding set $T$ of
reflections in $D_{n}$ is generated by elements of the form $(i\enspace
j)(\overline{i}\enspace\overline{j})$ for some $i,j\in\pm[n]$ with $i\neq j$.
In this section, we fix the Coxeter element
$c=(\overline{1}\enspace\overline{2}\enspace\cdots\enspace\overline{n-1}\enspace
1\enspace 2\enspace\cdots\enspace n-1)(\overline{n}\enspace n)$. For a cycle
$\mathcal{C}=(c_{1}\enspace c_{2}\enspace\cdots\enspace c_{r})$, we will
denote $\overline{\mathcal{C}}$ to be the cycle obtained by negating every
element of $\mathcal{C}$; that is, we define
$\overline{\mathcal{C}}=(\overline{c_{1}}\enspace\overline{c_{2}}\enspace\cdots\enspace\overline{c_{r}})$.

######  Definition 4.1.

A cycle $\mathcal{C}$ is _balanced_ if $\mathcal{C}=\overline{\mathcal{C}}$.

An easy observation is that any element of $D_{n}$ has an even number of
balanced cycles.

In [4], Athanasiadis and Reiner give an explicit bijection between type
$D_{n}$ noncrossing set partitions and $\mathrm{NC}(D_{n},c)$. In the
remainder of this section, we abuse notation and freely interchange between
noncrossing set partitions and their corresponding permutations.

We give a brief description of the noncrossing partitions in type $D$ alá
Athanasiadis and Reiner. Label $2n-2$ equidistant points on a circle with the
numbers $\overline{1},\overline{2},\ldots,\overline{n-1},1,2\ldots,n-1$ in
clockwise order. Next place an additional point at the center of the circle
and label it with $n$ and $\overline{n}$.

######  Definition 4.2.

A set partition $\pi$ of $\pm[n]$ is a _type- $D_{n}$ noncrossing set
partition_ if:

  1. (1)

For every block $B$ of $\pi$, $\overline{B}=\\{\overline{i}:i\in B\\}$ is also
a block of $\pi$.

  2. (2)

Different blocks of $\pi$ have disjoint interiors of their respective convex
hulls.

  3. (3)

The set $\\{n,\overline{n}\\}$ is not a block of $\pi$.

######  Definition 4.3.

A _zero block_ of a set partition $\pi$ of $\pm[n]$ is a block $B$ of $\pi$
such that $B=\overline{B}$.

Observe that if $\pi$ is a type-$D$ noncrossing set partition, then $\pi$ has
at most one zero block and when it does contain a zero block then the zero
block properly contains $\\{n,\overline{n}\\}$.

Now, given $\pi$ which is a type-$D$ noncrossing set partition, we describe
how to recover the corresponding non-crossing partition in $NC(D_{n},c)$,
following [4]. For each block $B$ of $\pi$ which is not zero block, form a
cycle by reading the elements of $B$ in clockwise order around the boundary of
the convex hull of $B$. If $\pi$ has a zero block $Z$, then form a cycle by
reading the elements of $Z\setminus\\{n,\overline{n}\\}$ in clockwise order
around the boundary of the convex hull of $Z$, and also form the cycle
$\\{n,\overline{n}\\}$.

The following lemma from [4] is helpful for figuring out the cycle structure
of noncrossing projections of elements.

######  Lemma 4.4 ([4]).

Let $w\in D_{n}$, and consider $i,j\in\pm[n]$ with
$i\not\in\\{j,\overline{j}\\}$. We have $(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}w$ if and only if $i$ and $j$ are
in the same cycle of $w$, or $i$ and $j$ are in different balanced cycles of
$w$.

A consequence of this lemma is the following.

######  Lemma 4.5 ([11, Lemma 6.4]).

Let $u\in D_{n}$ and $v=\pi_{T}(u)$. Consider distinct $i,j\in\pm[n-1]$. If
$i$ and $j$ are in the same cycle of $u$, then they are in the same cycle of
$v$.

We will often utilize the above lemma in the following rephrased form.

######  Lemma 4.6 (Rephrased Lemma 4.5).

Let $u\in D_{n}$ and $v=\pi_{T}(u)$. Then for every cycle $\mathcal{C}\in u$,
there exists a cycle $\mathcal{C}^{\prime}\in v$ such that
$\mathcal{C}\cap\pm[n-1]\subset\mathcal{C}^{\prime}$ where the containment
here is as sets.

We will also need the following characterization of covering relations in this
non-crossing partition lattice for $D_{n}$.

######  Lemma 4.7 ([4, Section 3]).

We have that $u$ covers $v$ in the non-crossing partition lattice for $D_{n}$
if and only if $v$ can be obtained from $u$ via the following operations:

  * (i)

splitting the zero block of $u$ into the zero block of $v$ and also a pair of
nonzero blocks,

  * (ii)

splitting a pair of nonzero blocks of $u$ into two such pairs for $v$, or

  * (iii)

splitting the zero block of $u$ into one pair of nonzero blocks for $v$.

Recall that there are two types of non-crossing set partitions, where either
the non-crossing set partition contains a zero block, or it does not. We will
call the non-crossing set partitions that contain a zero block _zeroed_. As
before, we will define an analogue of splittable elements in this setting. To
do so, we need to introduce an additional piece of notation. For a permutation
$w\in D_{n}$, we say that $\operatorname{sgn}(w(i))=1$ if $w(i)\in[n]$ and
$\operatorname{sgn}(w(i))=-1$ if $w(i)\in-[n]$.

1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$$7$$-7$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$$7$$-7$
Figure 16. The noncrossing set partition on the left is _zeroed_ , while the
one on the right is not.

In this section, our goal is to enumerate and characterize elements of $D_{n}$
with $\operatorname{Pop_{T}}$ forward orbits of length $2n-2$. Before we
proceed, we begin by discussing several properties of elements of $D_{n}$ with
length $2n-2$ forward orbits.

######  Lemma 4.8 ([11, Lemma 6.5]).

Suppose $j\in\pm[n-1]$ is such that $w^{-1}(j)\not\in\\{\overline{n},n\\}$.
Then $(\operatorname{Pop_{T}}^{2n-4}(w))^{-1}(j)$ is either $j$ or the
predecessor of $j$.

######  Corollary 4.9.

Suppose $w\in D_{n}$ is such that
$\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$. Let $m=w(n)$. If
$m\not\in\\{n,\overline{n}\\}$, then $\operatorname{Pop_{T}}^{2n-4}(w)(m)\neq
m$.

###### Proof.

If $m\not\in\\{n,\overline{n}\\}$, then we may apply Lemma 4.8 that
$\operatorname{Pop_{T}}^{2n-4}(w)(n)=e$, which contradicts the assumed forward
orbit length of $w$ under $\operatorname{Pop_{T}}$. ∎

The first step is to show that we may restrict our attention to zeroed
elements.

######  Lemma 4.10.

Let $w\in D_{n}$ be such that $\pi_{T}(w)$ is not zeroed. Then
$\left|O_{\operatorname{Pop_{T}}}(w)\right|\leq 2n-3$.

In the proof of the lemma, we will need the following result from [11].

######  Lemma 4.11 ([11, Lemma 6.3]).

Suppose $v\in NC(D_{n},c)$ and $k\in\pm[n-1]$ is such that $v(n)=k$. Let $Y$
be the set consisting of the next $n-1$ numbers after $k$ in clockwise order
around the circle. Then none of the elements of $Y$ lie in the same cycle as
$k$ in $v$.

###### Proof of Lemma 4.10.

Suppose for the sake of contradiction that $w\in D_{n}$ is such that
$\pi_{T}(w)$ is not zeroed but
$\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$. For $k\geq 0$, let
$u_{k}=\operatorname{Pop_{T}}^{k}(w)$ and $v_{k}=\pi_{T}(u_{k})$. Let
$m=w(n)$. First, we claim that since $\pi_{T}(w)$ is not zeroed,
$m\not\in\\{n,\overline{n}\\}$. If $m=n$, we have that $v_{k}(n)=n$ for all
$k\geq 0$. This means that the action of $\operatorname{Pop_{T}}$ is only on
$w|_{n-1}$, and we may effectively think of $w|_{n-1}$ as lying in $B_{n-1}$;
given a noncrossing partition of $D_{n}$ that fixes $n$ and $\overline{n}$, we
may uniquely map it to an induced noncrossing partition of $B_{n-1}$ by
restricting the partition to $\pm[n-1]$. This means that the set of
noncrossing partitions of $D_{n}$ that fix $n$ and $\overline{n}$ can be
mapped to a subset of the noncrossing partitions of $B_{n-1}$. This in turn
implies that the number of iterations of $\operatorname{Pop_{T}}$ needed for
$w$ to reach $e$ is at most the number of iterations of
$\operatorname{Pop_{T}}(\bullet,\widetilde{c})$ for $w|_{n-1}$ to reach $e$
where
$\widetilde{c}=(\overline{1}\enspace\overline{2}\enspace\cdots\enspace\overline{n-1}\enspace
1\enspace 2\enspace\cdots\enspace n-1)$. Now, $w|_{n-1}\neq\widetilde{c}$
because $\widetilde{c}$ is a balanced cycle and if $w|_{n-1}=\widetilde{c}$,
then $w$ would not have an even number balanced cycles, a contradiction to
$w\in D_{n}$. But by [11, Theorem 5.1], since $w|_{n-1}\neq\widetilde{c}$ and
$\pi_{T}(w)$ is not zeroed, we have that the maximum possible length of the
forward orbit of $w|_{n-1}$ is $2(n-1)-1=2n-3$, a contradiction.

If $m=\overline{n}$, then we also have that $w(\overline{n})=n$ so that
$(n\enspace\overline{n})$ is a balanced cycle in $w$. Since $w\in D_{n}$,
there must exist another balanced cycle $\mathcal{C}$. Suppose
$v\in\mathcal{C}$. By Lemma 4.4, it follows that $(v\enspace
n)(\overline{v}\enspace\overline{n})\leq_{T}w\leq_{T}\pi_{T}(w)$. Since
$\pi_{T}(w)$ is not zeroed, it follows that $n$ and $\overline{n}$ are not in
the same cycle and therefore $n$ and $v$ must be in the same cycle of
$\pi_{T}(w)$ by applying Lemma 4.4. Since $\mathcal{C}$ is balanced,
$\overline{v}\in\mathcal{C}$ as well. By considering
$(v\enspace\overline{n})(\overline{v}\enspace n)\leq_{T}\pi_{T}(w)$, the same
argument gives that $n$ and $\overline{v}$ must lie in the same cycle in
$\pi_{T}(w)$ as well. However, this would then be a contradiction to Lemma
4.11. As such, we have shown that $m\not\in\\{n,\overline{n}\\}$.

Observe that if $u_{t}(j)=j$ for some $t$ then for all $s\geq t$ we have that
$u_{s}(j)=j$ as well, since $(j)$ will be in a singleton cycle in $v_{s}$ for
all $s\geq t$. Consequently, by Corollary 4.9, to get a contradiction it
suffices to prove that there exists some $s\leq 2n-4$ such that
$u_{s}(w)(m)=m$. In fact, we will prove something stronger; we will show that
there exists some $s\leq n-1$ such that $u_{s}(w)(m)=m$.

To that end, we introduce some notation from [11]. Define a total order
$\prec_{j}$ that is defined by reading the numbers clockwise around the circle
so that the last number read is $j$. Let $\mathcal{C}_{i}$ be the cycle in
$v_{i}$ containing $j$.

Since $\pi_{T}(w)$ is not zeroed, by Lemma 4.7 it follows that $v_{i}$ is not
zeroed for all $i\geq 1$. Since there are no balanced cycles in $v_{i}$, by
Lemma 4.4 if $\alpha$ and $\beta$ are in the same cycle of $u_{i}$, then they
must lie in the same cycle of $v_{i}$. Since $u_{i+1}^{-1}=v_{i}u_{i}^{-1}$
and $u_{k}^{-1}(m)$ and $m$ are in the same cycle of $u_{k}$, it follows that
$u_{k+1}^{-1}(m)$ and $m$ are in the same cycle of $v_{k+1}$ and in particular
that $u_{k+1}^{-1}(m)$ is the element after $u_{k}^{-1}(m)$ in the clockwise
order on $\mathcal{C}$. Putting this together for $k\geq 1$ where we observe
that since $m\in\pm[n-1]$, we get that

$u_{1}^{-1}(m)\prec_{m}u_{2}^{-1}(m)\prec_{m}\cdots\prec_{m}m$ (2)

By Lemma 4.11, we have that $\overline{m}\prec_{m}u_{1}^{-1}(m)$.
Consequently, the sequence in (2) is of length at most $n-1$, and so there
exists some $s\leq n-1$ such that $u_{s}(w)(m)=m$, as desired. ∎

Next, for a zeroed element $w\in D_{n}$, we associate with it a permutation in
$B_{n-1}$. We will fix the Coxeter element
$c=(\bar{1}\enspace\bar{2}\enspace\cdots\enspace\bar{n-1}\enspace 1\enspace
2\enspace\cdots\enspace n-1)$ in $B_{n-1}$. Let $a=w(n)$ and $b=w^{-1}(n)$. We
will define $w|_{n-1}\in B_{n-1}$ by suitably defining
$w^{-1}(a),w^{-1}(\bar{a})$ and $w(b),w(\bar{b})$ so that $w|_{n-1}$ has the
same convex hull of its cycles as that of $w$. Let $w_{1}\in D_{n}$ be defined
by

$w_{1}(x)=\begin{cases}w(x)&\text{if }x\not\in\\{b,\bar{b}\\},\\\ a&\text{if
}x=b,\\\ \bar{a}&\text{if }x=\bar{b}.\end{cases}$

Let $w_{2}\in D_{n}$ be defined by

$w_{2}(x)=\begin{cases}w(x)&\text{if }x\not\in\\{b,\bar{b}\\},\\\
\bar{a}&\text{if }x=b,\\\ a&\text{if }x=\bar{b}.\end{cases}$

Suppose the elements of the cycles $\mathcal{C}_{1},\ldots,\mathcal{C}_{k}\in
w$ make up the zero block of $\pi_{T}(w)$. Observe that if
$\mathcal{C}_{i}\cap\\{n,\bar{n}\\}=\emptyset$, then $\mathcal{C}_{i}\in
w_{1},w_{2}$ and if $\mathcal{C}_{i}\cap\\{n,\bar{n}\\}\neq\emptyset$ then
there exists some $i\in\\{1,2\\}$ and a cycle $\mathcal{C}\in w_{i}$ such that
$\mathcal{C}_{i}\subset\mathcal{C}$. Suppose some cycle
$\mathcal{C}_{i}\cap\\{n,\bar{n}\\}\neq\emptyset$ and the interior of the
convex hulls of $\mathcal{C}_{i}$ and $\mathcal{C}_{j}$ is nonempty. Then for
the corresponding $w_{i}$, the interior of the convex hulls of $\mathcal{C}$
and $\mathcal{C}_{j}$ is nonempty. It consequently follows that
$\pi_{T}(w_{i})$ is zeroed and its zero block contains the same elements as
that of $\pi_{T}(w)$. It is clear that the nonzero blocks of $\pi_{T}(w_{i})$
and $\pi_{T}(w)$ necessarily coincide. The observation that one of $w_{1}$ or
$w_{2}$ has the same convex hull as $w$ allows us to make the following
definition.

######  Definition 4.12.

Given a zeroed permutation $w\in D_{n}$, define $w_{1}$ and $w_{2}$ as above.
Define the _$n-1$ -projection_ of $w$, written as $w|_{n-1}\in B_{n-1}$, to be
either of $w_{1}$ or $w_{2}$ satisfying $\pi_{T}^{B}(w_{i})=\pi_{T}^{D}(w)$.
If both $w_{1}$ and $w_{2}$ have the desired property, choose the $w_{i}$ such
that $w_{i}^{-1}(w(n))=w^{-1}(n)$. Here the superscripts of the noncrossing
projection indicates whether we are working with the set-up of $B_{n-1}$ or
$D_{n}$.

1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$$7$$-7$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$ Figure 17.
On the left is a diagram representing either the permutation
$w=(1\enspace\bar{6})(2\enspace 3\enspace 4\enspace 5\enspace
7)(\bar{1}\enspace
6)(\bar{2}\enspace\bar{3}\enspace\bar{4}\enspace\bar{5}\enspace\bar{7})\in
D_{7}$ or $w^{\prime}=(1\enspace\bar{6})(2\enspace 3\enspace 4\enspace
5\enspace\bar{7})(\bar{1}\enspace
6)(\bar{2}\enspace\bar{3}\enspace\bar{4}\enspace\bar{5}\enspace 7)$. On the
right, we have
$w|_{6}=w^{\prime}|_{6}=(1\enspace\overline{6})(\overline{1}\enspace
6)(2\enspace 3\enspace 4\enspace
5\enspace\overline{2}\enspace\overline{3}\enspace\overline{4}\enspace\overline{5})$
which should be thought of as an element of $B_{6}$.

With this definition in place, we can define pre-$D$-splittable elements, that
parallel the definition of splitable elements in the context of type A and
type B Coxeter groups.

######  Definition 4.13.

An element $w\in D_{n}$ is _pre- $D$-splittable_ if $\pi_{T}(w)=c$, and either
$w=c^{-1}$ or $w|_{n-1}$ contains exactly $2n-4$ antiexceedances.

It turns out in the setting of type D Coxeter groups, however, that an
additional condition is needed in order for $w$ to have maximum
$\operatorname{Pop_{T}}$ orbit of length $2n-2$. Define a total order $\prec$
on $\pm[n-1]$ by $\overline{1}\prec\cdots\prec\overline{n-1}\prec
1\prec\cdots\prec n-1$. Define $\prec_{j}$ to be the order obtained by doing a
cyclic shift on $\prec$ such that the maximum element of $\prec_{j}$ is $j$.

######  Definition 4.14.

An element $w\in D_{n}$ is _$D$ -splittable_ if it is pre-$D$-splittable and
there exists $x$ such that $x\prec_{w(n)}w^{-1}(n)$.

With this notation in place, we can answer a question posed in [11, Section
6], about the number of elements $w\in D_{n}$ with
$|O_{\operatorname{Pop_{T}}}(w)|=2n-2$. Note that the Coxeter number of
$D_{n}$ is $2n-2$, so that we are enumerating elements with maximum forward
orbit length. This is in contrast with the setting of type A and type B
Coxeter groups, where [11, Theorem 5.1] shows that there exists a unique
element with maximum forward orbit length. Of note is that the value put forth
in [11, Conjecture 6.6] is incorrect; for instance there are 7 elements in
$D_{4}$ with forward orbit length 6 as opposed to the conjectured value of 1
element as predicted by [11, Conjecture 6.6].

We recall Theorem 1.7.

See 1.7

Next, we show that if $w\in D_{n}$ is such that $\pi_{T}(w)$ is zeroed but
$\pi_{T}(w)\neq c$ or $w|_{n-1}$ does not contain $2n-4$ antiexceedances then
$w$ cannot satisfy $\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$. A
reduction that we make in this proof is to relate
$\operatorname{Pop_{T}}(\bullet,c)$ on $D_{n}$ to
$\operatorname{Pop_{T}}(\bullet,\widetilde{c})$ on $B_{n}$ where
$\widetilde{c}=(\overline{1}\enspace\overline{2}\enspace\cdots\enspace\overline{n-1}\enspace
1\enspace 2\enspace\cdots\enspace n-1)$ so as to utilize our results from the
previous section. To that end, we first establish an auxiliary result roughly
relating the cycle structure of $\pi_{T}(\operatorname{Pop_{T}}^{D}(w),c)$ and
$\pi_{T}(\operatorname{Pop_{T}}^{B}(w|_{n-1}),\widetilde{c})$ for elements
$w\in D_{n}$ such that $\pi_{T}(w)$ is zeroed, where the superscripts are
indicative of the setting in which we should think of $\operatorname{Pop_{T}}$
as acting. To more succinctly state the result, we introduce one more piece of
notation.

######  Definition 4.15.

Suppose $w|_{n-1}$ is obtained from $w\in D_{n}$. Let $t=w(n)$. The _$n$
-extension_ of $\operatorname{Pop_{T}}^{B}(w|_{n-1})$ denoted
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})$ is defined to be the
permutation where
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(j)=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(j)$
for all $j\in\pm[n]$ such that $j\not\in\\{t,\overline{t},n,\overline{n}\\}$,
while
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(t)=\overline{n}$,
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(\overline{t})=n$,
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(n)=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(\overline{t})$
and
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(\overline{n})=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(t)$.

######  Lemma 4.16.

For any $w\in D_{n}$ such that $\pi_{T}(w)$ is zeroed and $w(n)\in\pm[n-1]$,
$\operatorname{Pop_{T}}(w)=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})$.

###### Proof.

Suppose
$\pi_{T}(B)=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}(n\enspace\overline{n})$.
First, we prove that
$\pi_{T}^{B}(w|_{n-1})=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}$. Suppose
otherwise for the sake of contradiction so that
$\pi_{T}(w|_{n-1})=\mathcal{C}_{1}\cdots\mathcal{C}_{k}$ where $k\geq 2$, such
that there exists at least an index $r$ with
$\mathscr{C}_{r}\neq\mathcal{C}_{r}$. By Corollary 4.6, we necessarily have
that for every $i\in[k]$, there exists a corresponding index $q_{i}$ such that
$\mathcal{C}_{i}\subset\mathscr{C}_{q_{i}}$ where the inclusion is as sets.
Let

$w=(c_{11}\enspace c_{12}\cdots c_{1\ell_{1}})\cdots(c_{j1}\enspace
c_{j2}\cdots c_{jt_{1}}\enspace n\enspace c_{js_{1}}\cdots
c_{j\ell_{j}})\cdots(c_{k1}\enspace c_{k2}\cdots
c_{jt_{2}}\enspace\overline{n}\enspace c_{js_{2}}\cdots
c_{k\ell_{k}})\cdots(c_{m1}\enspace c_{m2}\cdots c_{m\ell_{m}}).$

Because by definition $w|_{n-1}$ contains a balanced cycle

$(c_{j1}\enspace\cdots\enspace c_{jt_{1}}\enspace
c_{js_{2}}\enspace\cdots\enspace c_{k\ell_{k}}c_{k1}\enspace\cdots\enspace
c_{jt_{2}}c_{js_{1}}\enspace\cdots\enspace
c_{j\ell_{j}})\enspace\cdots\enspace(c_{k1}\enspace
c_{k2}\enspace\cdots\enspace c_{jt_{2}}\enspace c_{js_{2}}\enspace
c_{k\ell_{k}}),$

it follows that $\pi_{T}^{B}(w|_{n-1})$ contains a balanced cycle as well
which corresponds to the part of the partition containing the convex hull of
this cycle. without loss of generality this balanced cycle is
$\mathcal{C}_{1}$. Then we have that $\mathcal{C}_{2},\ldots,\mathcal{C}_{k}$
are disjoint from $\mathcal{C}_{1}$.

Now, any cycle $\mathcal{C}$ of $w$ not containing $n,\overline{n}$ is also a
cycle in $w|_{n-1}$. Next, we observe that if the convex hull of $\mathcal{C}$
in $w$ intersects the convex hull of $(c_{j1}\enspace
c_{j2}\enspace\cdots\enspace c_{jt_{1}}\enspace n\enspace
c_{js_{1}}\enspace\cdots\enspace c_{j\ell_{j}})(c_{k1}\enspace
c_{k2}\enspace\cdots\enspace c_{jt_{2}}\enspace\overline{n}\enspace
c_{js_{2}}\enspace\cdots\enspace c_{k\ell_{k}})$, then the convex hull of
$\mathcal{C}$ in $w|_{n-1}$ would also intersect the convex hull of

$(c_{j1}\enspace\cdots\enspace c_{jt_{1}}\enspace
c_{js_{2}}\enspace\cdots\enspace c_{k\ell_{k}}c_{k1}\enspace\cdots\enspace
c_{jt_{2}}c_{js_{1}}\enspace\cdots
c_{j\ell_{j}})\enspace\cdots\enspace(c_{k1}\enspace
c_{k2}\enspace\cdots\enspace c_{jt_{2}}\enspace c_{js_{2}}\enspace
c_{k\ell_{k}}).$

Recall that $D_{n}$ reflections are given by $(i\enspace
j)(\overline{i}\enspace\overline{j})$. In particular, we claim that if
$(i\enspace j)(\overline{i}\enspace\overline{j})\leq_{T}w$ for some
$i,j\in\pm[n-1]$ and $i\not\in\\{j,\overline{j}\\}$, then $(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}\mathcal{C}_{1}\mathcal{C}_{2}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$.
To see this, first make the observations that every cycle in $w|_{n-1}$ is
contained (as a set) in a cycle $\mathcal{C}_{i}$ and also that if
$\mathcal{C}$ is a balanced cycle in $w|_{n-1}$ such that
$\mathcal{C}\subset\mathcal{C}_{j}$ (here containment is as sets) then
$\mathcal{C}_{j}$ is a balanced cycle as well, where $\mathcal{C}_{j}$ is the
unique balanced cycle in $\pi_{T}^{B}(w|_{n-1})$. For $(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}w$ by Lemma 4.4, there are two
possibilities: if $i$ and $j$ lie in the same cycle, then they are lie in the
same cycle for some $\mathcal{C}_{j}$ by the earlier observation and so
$(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}\mathcal{C}_{1}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$;
if $i$ and $j$ lie in disjoint balanced cycles, then by the earlier
observation they lie in the unique balanced cycle $\mathcal{C}_{b}$ of
$\pi_{T}^{B}(w\bigr{|}_{n-1})$ so that $(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}\mathcal{C}_{1}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$
as well.

At this stage, the only $D_{n}$ reflections $(i\enspace
j)(\overline{i}\enspace\overline{j})\leq_{T}w$ that we have yet to account for
are those where $i\in\\{n,\overline{n}\\}$. There are two cases:

  * •

$n$ and $\overline{n}$ lie in the same cycle. Then the possibilities for
$\\{i,j\\}$ are of the form $\\{n,t\\}$ or $\\{\overline{n},t\\}$ where $t$ is
an element from a balanced cycle. By the earlier observation, $t$ continues to
lie in a balanced cycle $\mathcal{C}_{b}$, so that $(n\enspace
t)(\overline{n}\enspace\overline{t})\leq_{T}\mathcal{C}_{1}\mathcal{C}_{2}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$.

  * •

$n$ and $\overline{n}$ lie in disjoint cycles. Then the only possibilities for
$\\{i,j\\}$ are of the form $\\{n,c_{jx}\\}$ and $\\{\overline{n},c_{ky}\\}$
for appropriate indices $x,y$. It is clear that $(n\enspace
c_{jx})(\overline{n}\enspace\overline{c_{jx}})\leq_{T}\mathcal{C}_{1}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$.

Lastly,
$\mathcal{C}_{1}\mathcal{C}_{2}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$
is a non-crossing partition of $D_{n}$, since
$\mathcal{C}_{1}\mathcal{C}_{2}\cdots\mathcal{C}_{k}$ is a non-crossing
partition of $B_{n}$. This means that
$\pi_{T}(w)\leq_{T}\mathcal{C}_{1}\mathcal{C}_{2}\cdots\mathcal{C}_{k}(n\enspace\overline{n})$,
which is a contradiction by Lemma 4.7.

What remains is a computation. Let $t=w(n)$. Because
$\pi_{T}^{B}(w|_{n-1})=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}$ and
$\pi_{T}(w)=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}(n\enspace\overline{n})$,
it follows that
$\operatorname{Pop_{T}}(w)^{-1}(j)=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(j)$
for $j\not\in\\{n,\overline{n},t,\overline{t}\\}$. Now,
$\operatorname{Pop_{T}}(w)^{-1}(t)=(\pi_{T}(w))^{-1}(n)=\overline{n}=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(n)$
and similarly
$\operatorname{Pop_{T}}(w)^{-1}(\overline{t})=n=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(n)$.
Furthermore, without loss of generality $w^{-1}(n)\in\mathscr{C}_{1}$. Then
$\operatorname{Pop_{T}}(w)^{-1}(n)=\mathscr{C}_{1}(w^{-1}(n))=\mathscr{C}_{1}(w|_{n-1}^{-1}(t))=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(t)$
and analogously
$\operatorname{Pop_{T}}(w)^{-1}(\overline{n})=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(\overline{t})$.
∎

The first step of the proof above shows that if
$\pi_{T}(B)=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}(n\enspace\overline{n})$,
then $\pi_{T}^{B}(w|_{n-1})=\mathscr{C}_{1}\cdots\mathscr{C}_{\ell}$. It may
be tempting to claim that the converse is also true. In this dream scenario,
analyzing the behavior of $w$ under the operation of $\operatorname{Pop_{T}}$
would very neatly reduce to that of understanding the operation of $w|_{n-1}$
under $\operatorname{Pop_{T}}^{B}$, and we already know how to do the latter
because of Section 3. However, such a claim is unfortunately false and even
$\pi_{T}^{B}(w|_{n-1})=\widetilde{c}$ is insufficient to guarantee that
$\pi_{T}(B)$ is zeroed. For instance, consider the permutation $w=63512\in
D_{6}$ (where we are writing the permutation on $\pm[n]$ in one-line
notation). Then $w|_{5}=\overline{1}35\overline{4}2\in B_{5}$ is such that
$\pi_{T}^{B}(w|_{5})=2345\overline{1}=\widetilde{c}_{5}$ while
$\pi_{T}(w)=234561\neq c_{6}$. This shows that the behavior of
$\operatorname{Pop_{T}}^{D}$ is more subtle that we might naïvely expect.

1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$7$-7$8$-8$$9$$-9$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$7$-7$8$-8$1$-1$2$-2$3$-3$4$-4$5$-5$6$-6$7$-7$8$-8$$9$$-9$
Figure 18. An illustration of a _double-cysted_ permutation. Here, on the left
we have  $w=(1\enspace 2\enspace 8)(3\enspace 6\enspace 7)(4\enspace 9\enspace
5)(\overline{4}\enspace\overline{5}\enspace\overline{9})(\overline{1}\enspace\overline{2}\enspace\overline{8})(\overline{3}\enspace\overline{6}\enspace\overline{7})$
and in the middle we have  $w|_{8}=(1\enspace 2\enspace 8)(3\enspace 6\enspace
7)(4\enspace
5\enspace\overline{4}\enspace\overline{5})(\overline{1}\enspace\overline{2}\enspace\overline{8})(\overline{3}\enspace\overline{6}\enspace\overline{7}).$
On the right is $\pi_{T}(w)=(1\enspace 2\enspace 3\enspace 4\enspace 5\enspace
6\enspace 7\enspace 8\enspace
9)(\overline{1}\enspace\overline{2}\enspace\overline{3}\enspace\overline{4}\enspace\overline{5}\enspace\overline{6}\enspace\overline{7}\enspace\overline{8}\enspace\overline{9})$
which consists of two cycles.

######  Definition 4.17.

Suppose $w|_{n-1}$ is obtained from $w\in D_{n}$ and let $t=w(n)$. The
_modified $n$-extension_ of $\operatorname{Pop_{T}}^{B}(w|_{n-1})$ denoted
$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})$ is defined to be the
permutation satisfying

  * •

$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(j)=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(j)$
for all $j\in\pm[n]$ such that $j\not\in\\{t,\overline{t},n,\overline{n}\\}$,

  * •

$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(t)=n$,

  * •

$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(\overline{t})=\overline{n}$,

  * •

$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(n)=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(\overline{t})$,
and

  * •

$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})^{-1}(\overline{n})=\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(t)$.

Recall the definition of $w_{1}$ and $w_{2}$ from before. Observe that if
$\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})=w_{i}$, then
$\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1})=w_{3-i}$. In particular,
if $\pi_{T}(w)$ is zeroed and
$\pi_{T}(\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1}))\neq\pi_{T}(w)$,
then $\pi_{T}(\prescript{n}{m}{\operatorname{Pop_{T}}}(w|_{n-1}))=\pi_{T}(w)$.

This shows that there are only the following two possibilities if $w\in D_{n}$
and $\pi_{T}(w)$ is zeroed is such that
$\operatorname{Pop_{T}}^{B}(w|_{n-1})\neq\operatorname{Pop_{T}}(w)|_{n-1}$.

  1. (1)

$\pi_{T}(\operatorname{Pop_{T}}(w))$ is not zeroed. Lemma 4.7 then implies
that the zero block of $\pi_{T}(w)$ is split into two cycles in
$\pi_{T}(\operatorname{Pop_{T}}(w))$. Call the corresponding $w$ _double-
cysted_.

  2. (2)

$\pi_{T}(\operatorname{Pop_{T}}(w))$ is zeroed and
$\operatorname{Pop_{T}}^{2}(B)=\prescript{n}{m}{(}\operatorname{Pop_{T}}^{B}(w|_{n-1}))$.
Call such an element $w$ _pierced_.

1$-1$2$-2$3$-3$4$-4$1$-1$2$-2$3$-3$4$-4$$5$$-5$ Figure 19. On the left, we
have $w|_{4}=(1\enspace 4\enspace\overline{1}\enspace\overline{4})(2\enspace
3\enspace\overline{2}\enspace\overline{3})$. The $5$-extension of $w|_{4}$ is
given by $(1\enspace 4\enspace\overline{1}\enspace\overline{4})(2\enspace
3\enspace 5)(\overline{2}\enspace\overline{3}\enspace\overline{5})$.

######  Definition 4.18.

$w\in D_{n}$ is _bad_ if either $w$ is double-cysted or pierced.

######  Corollary 4.19.

If $w\in D_{n}$ is such that $\pi_{T}(w)$ is zeroed and such that
$\operatorname{Pop_{T}}^{i}(w)$ is not bad for $1\leq i\leq t$. We have the
following alternative characterization of $\operatorname{Pop_{T}}^{i}(w)$ for
$1\leq i\leq t$.

  * •

If $i$ is odd, then
$\operatorname{Pop_{T}}^{i}(w)=\prescript{n}{}{\operatorname{Pop_{T}}}((\operatorname{Pop_{T}}^{B})^{i-1}(w|_{n-1}))$.

  * •

If $i$ is even, then
$\operatorname{Pop_{T}}^{i}(w)=\prescript{n}{m}{\operatorname{Pop_{T}}}((\operatorname{Pop_{T}}^{B})^{i-1}(w|_{n-1}))$.

Next, we examine bad elements in greater detail. First, we will study double-
cysted elements.

######  Claim 4.20.

Suppose $w$ is double-cysted, so
$\mathcal{C}_{1}\mathcal{C}_{2}\subset\pi_{T}(\operatorname{Pop_{T}}(w))$ for
some (non-balanced) cycles $\mathcal{C}_{1}\ni n$ and
$\mathcal{C}_{2}=\overline{\mathcal{C}_{1}}\ni\bar{n}$. By re-indexing
$\bar{i}$ as $i$ in each of $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ as
necessary, we can consider $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ as elements
of $A_{n}$. Then
$\min\\{\operatorname{aexc}^{A}(\mathcal{C}_{1}),\operatorname{aexc}^{A}(\mathcal{C}_{2})\\}\leq\operatorname{aexc}^{B}(\operatorname{Pop_{T}}(w|_{n-1}))$.

###### Proof.

Let $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ after re-indexing be
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, respectively. Note that by re-
indexing it is possible that we create “new” antiexceedances of the form
$\mathcal{D}_{j}^{-1}(u)=v$ where $v>u$ but $\mathcal{C}_{j}^{-1}(u)=\bar{v}$.
without loss of generality $j=1$. Then note that $\mathcal{D}_{2}^{-1}(v)=u$
while $\mathcal{C}_{2}^{-1}(\bar{v})=u$ so an antiexceedance in
$\mathcal{C}_{2}$ is “destroyed” when we pass to $\mathcal{D}_{2}$ as a result
of re-indexing. Consequently, we have that
$\operatorname{aexc}^{B}(\operatorname{Pop_{T}}(\operatorname{Pop_{T}}^{B}(w|_{n-1})))\geq\max\\{(\operatorname{aexc}(\mathcal{C}_{1})-1)+(\operatorname{aexc}(\mathcal{C}_{2}-1),1\\}$.
Here, the $-1$ in $\operatorname{aexc}(\mathcal{C}_{1})-1$ accounts for the
additional antiexceedance from $\mathcal{C}_{1}^{-1}(n)$ that is not present
in $w|_{n-1}$. In particular, if
$\max\\{\operatorname{aexc}(\mathcal{C}_{1}),\operatorname{aexc}(\mathcal{C}_{2})\\}-1\geq
1$ then
$\operatorname{aexc}(\operatorname{Pop_{T}}(\operatorname{Pop_{T}}^{B}(w|_{n-1})))\geq\min\\{\operatorname{aexc}(\mathcal{C}_{1}),\operatorname{aexc}(\mathcal{C}_{2})\\}$.
Otherwise, we have that

$\operatorname{aexc}(\mathcal{C}_{1})=\operatorname{aexc}(\mathcal{C}_{2})=\operatorname{aexc}(\operatorname{Pop_{T}}(\operatorname{Pop_{T}}^{B}(w|_{n-1})))=1.$

∎

As a consequence of the above claim and Lemma 2.2, we have the following
useful consequence.

######  Corollary 4.21.

Suppose $w$ is double-cysted, then
$\left|O_{\operatorname{Pop_{T}}(w)}\right|\leq\operatorname{aexc}(\operatorname{Pop_{T}}^{B}(w|_{n-1}))$.

###### Proof.

Recall by Lemma 4.16 that
$\operatorname{Pop_{T}}(w)=\prescript{n}{}{\operatorname{Pop_{T}}}(w|_{n-1})$.
In particular, any cycle $\mathcal{C}^{\prime}\in w$ with
$\mathcal{C}^{\prime}\cap\\{n,\bar{n}\\}=\emptyset$ satisfies
$\mathcal{C}^{\prime}\in\operatorname{Pop_{T}}^{B}(w|_{n-1})$ as well. In
particular, write
$\pi_{T}(w|_{n-1})=\mathcal{C}\mathcal{C}_{1}\cdots\mathcal{C}_{j}$. Note that
$\sum_{i=1}^{j}\operatorname{aexc}{\mathcal{C}_{i}}\leq\operatorname{aexc}(\operatorname{Pop_{T}}^{B}(w|_{n-1}))$,
and so Lemma 3.2 implies that
$\max_{j}\left\\{\left|O_{\operatorname{Pop_{T}}^{B}}(\mathcal{C}_{j})\right|\right\\}\leq\operatorname{aexc}(\operatorname{Pop_{T}}^{B}(w|_{n-1}))$.

By Lemma 4.7, note that for $j\geq 1$ we have
$\pi_{T}(\operatorname{Pop_{T}}^{j}(w))$ further refines each of
$\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{C}_{1},\ldots\mathcal{C}_{j}$. That
is, the dynamic of $\operatorname{Pop_{T}}$ can be thought of acting
independently on each of the cycles of $w$. Making the identification of
$\bar{i}$ with $i$ as described in Claim 4.20 when necessary, it follows from
the previous paragraph as well as the result of Claim 4.20 that

$\left|O_{\operatorname{Pop_{T}}}(w)\right|=\max_{j}\left\\{\left|O_{\operatorname{Pop_{T}}^{A}}(\mathcal{D}_{1})\right|,\left|O_{\operatorname{Pop_{T}}^{A}}(\mathcal{D}_{2})\right|,\left|O_{\operatorname{Pop_{T}}^{B}}(\mathcal{C}_{j})\right|\right\\}\leq\operatorname{aexc}(w|_{n-1}).$

∎

Next, we make an observation about the uniqueness of pierced permutations in
the $\operatorname{Pop_{T}}$ orbit.

######  Lemma 4.22.

Suppose $w\in D_{n}$ is such that $w$ is pierced. Then there does not exist
$i\geq 1$ such that $\operatorname{Pop_{T}}^{i}(w)$ is pierced as well.

In the proof of the lemma we will repeatedly make use of the notion of _cycle
disconnected_.

######  Definition 4.23.

Given $w\in D_{n}$, we say that cycles $\mathcal{C}_{1},\mathcal{C}_{2}$ are
_cycle disconnected_ (in $w$) if there do not exist cycles
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ such that the convex hulls of
$\mathcal{D}_{1}$ and $\mathcal{C}_{1}$ have nonempty intersection in their
interiors, the convex hulls of $\mathcal{D}_{k}$ and $\mathcal{C}_{2}$ have
nonempty intersection in their interiors and for $1\leq i\leq k-1$ the convex
hulls of $\mathcal{D}_{i}$ and $\mathcal{D}_{i+1}$ have nonempty intersection
in their interiors.

Conversely, if there exist such cycles
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ we say that $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are _cycle connected_.

Observe that for $w\in D_{n}$ and cycles $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ that are cycle disconnected in $w$, we necessarily have that
the elements of $\mathcal{C}_{1}$ and the elements of $\mathcal{C}_{2}$ lie in
distinct cycles in $\pi_{T}(w)$. Conversely, if $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are cycle connected then their elements lie in the same
cycle in $\pi_{T}(w)$.

###### Proof.

Suppose otherwise for the sake of contradiction, and suppose $i$ is the
smallest such counterexample. Firstly, note that if there exists $j\geq 1$
such that $\operatorname{Pop_{T}}^{j}(w)$ is double-cysted, then
$\pi_{T}(\operatorname{Pop_{T}}^{k}(w))$ cannot be zeroed for $k\geq j$ by
Lemma 4.7. In particular, $\operatorname{Pop_{T}}^{k}(w)$ cannot be pierced
either. Consequently, we may assume for $1\leq k\leq i$ that
$\operatorname{Pop_{T}}^{k}(w)$ is not bad.

Let $w(n)=a$. Suppose $\operatorname{Pop_{T}}^{B}(w|_{n-1})^{-1}(a)=b$. Define
$u\in B_{n-1}$ as follows:

$u(x)=\begin{cases}\operatorname{Pop_{T}}^{B}(w|_{n-1})(x)&\text{if }x\neq
b,\bar{b},\\\ \bar{a}&\text{if }x=b,\\\ a&\text{if }x=\bar{b}.\end{cases}$

Then the fact that $w$ is pierced is equivalent to
$\operatorname{Pop_{T}}(w)|_{n-1}=u$. In particular, we have that
$\operatorname{Pop_{T}}^{2}(w)=\prescript{n}{}{\operatorname{Pop_{T}}}(\operatorname{Pop_{T}}(w)|_{n-1})=\prescript{n}{}{\operatorname{Pop_{T}}}(u)$.
By the previous paragraph and Corollary 4.19, the behavior of
$\operatorname{Pop_{T}}^{k}(w)$ for $1\leq k\leq i$ depends only on
$(\operatorname{Pop_{T}}^{B})^{k}(u)$.

Furthermore, since $w$ is pierced, it follows that there exists a cycle
$\mathcal{C}$ that is cycle disconnected from the cycle $\mathcal{B}_{1}$ in
$\operatorname{Pop_{T}}^{B}(w|_{n-1})$ that contains $a$, but cycle connected
from the cycle $\mathcal{B}_{2}$ in $u$ that contains $a$.

Let $\mathcal{C}_{1}$ be the cycle in $\operatorname{Pop_{T}}^{i+1}(w)$ which
contains $a$. Let $\mathcal{C}_{2}$ be the cycle in
$(\operatorname{Pop_{T}}^{B})^{i+1}(u)$ which contains $a$, and let
$b^{\prime}=(\operatorname{Pop_{T}}^{B})^{i+1}(u)^{-1}(a)$. Note that the
cycles in $\operatorname{Pop_{T}}^{i+1}(w)$ and
$(\operatorname{Pop_{T}}^{B})^{i+1}(u)$ that do not contain any of
$\\{a,\bar{a}\\}$ overlap. In particular, in order for
$\operatorname{Pop_{T}}^{i}(w)$ to be pierced, there must be cycles
$\mathcal{D}\in\operatorname{Pop_{T}}^{i+1}(w),(\operatorname{Pop_{T}}^{B})^{i+1}(u)$
such $\mathcal{D}$ and $\mathcal{C}_{1}$ are cycle connected in
$\operatorname{Pop_{T}}^{i+1}(w)$, while $\mathcal{D}$ and $\mathcal{C}_{2}$
are cycle disconnected in $(\operatorname{Pop_{T}}^{B})^{i+1}(u)$.

We split into two cases based on the clockwise orientation of
$a,\bar{b},\bar{a},b$. First, suppose we are in the situation where in
clockwise order on the circle we have $\bar{a},b,a,\bar{b}$. Note that we may
choose $\mathcal{C}$ such that it only contains elements that either lie
clockwise between $\bar{a}$ and $b$, or lie clockwise between $a$ and
$\bar{b}$. We claim that $\mathcal{C}$ cannot contain an element $c$ such that
$c$ is clockwise between $\bar{a}$ and $b$ and $d=\mathcal{C}(c)$ lies
clockwise between $a$ and $\bar{b}$, which would then contradict the previous
observation on $\mathcal{C}$. This is because if we let
$\widetilde{\mathcal{C}}$ be the cycle in $\operatorname{Pop_{T}}^{i+1}(w)$
that contains $d$, then $d$ would also be situated clockwise between $a$ and
$\bar{b^{\prime}}$, while $\widetilde{\mathcal{C}}^{-1}(d)$ is situated
clockwise between $\bar{a}$ and $b^{\prime}$. In particular, the convex hull
of $\widetilde{\mathcal{C}}$ has nonempty interior intersection with the
convex hull of $\mathcal{C}_{2}$, and $\widetilde{\mathcal{C}}$ would also
have nonempty interior intersection with the convex hull of $\mathcal{D}$, so
that $\mathcal{D}$ and $\mathcal{C}_{2}$ are cycle connected in
$(\operatorname{Pop_{T}}^{B})^{i+1}(u)$, a contradiction.

Next, suppose in clockwise order on the circle we have $a,b,\bar{a},\bar{b}$.
Similar to before, note that we may pick $\mathcal{C}$ to contain an element
$c$ that is situated clockwise between $b$ and $\bar{a}$ such that
$\mathcal{C}(c)=d$ is situated clockwise between $\bar{b}$ and $a$. We may
also choose $\mathcal{D}$ such that it contains an element $c^{\prime}$ that
is situated clockwise between $\bar{a}$ and $\bar{b^{\prime}}$ such that
$d^{\prime}=\mathcal{D}(c^{\prime})$ is situated clockwise between $a$ and
$b$. Let $\mathcal{C}^{\prime}$ be the cycle in $w$ that contains
$d^{\prime}$. Note that if $\mathcal{C}^{\prime}$ only consists of elements
that are either clockwise between $\bar{a}$ and $\bar{b}$ or clockwise between
$a$ and $b$ we would obtain our desired contradiction because $\mathcal{C}$,
$\mathcal{C}^{\prime}$ and the $\mathcal{B}_{1}$ shows that $\mathcal{C}$ and
$\mathcal{B}_{1}$ are cycle connected.

Otherwise, suppose $d^{\prime}$ lies clockwise between $a$ and $b$ while
$(\mathcal{C}^{\prime})^{-1}(d^{\prime})=f^{\prime}$ lies clockwise between
$b$ and $\bar{a}$. In this case, observe that the convex hulls of
$\mathcal{C}^{\prime}$ and $\mathcal{B}_{1}$ have non-empty intersections in
their interior, and the same conclusion also holds for
$\overline{\mathcal{C}^{\prime}}$ and $\mathcal{B}_{1}$. As such, in order for
$\mathcal{C}$ to be cycle disconnected from $\mathcal{B}_{1}$, it follows that
$\mathcal{C}$ can only contain elements that are situated clockwise between
$f^{\prime}$ and $\bar{a}$ or elements that are clockwise between
$\bar{f^{\prime}}$ and $a$ on the circle. Suppose $\mathcal{C}$ contains $g$,
which lies clockwise between $f^{\prime}$ and $\bar{a}$ such that
$\mathcal{C}^{-1}(g)$ lies clockwise between $\bar{f^{\prime}}$ and $a$. Let
$\widetilde{\mathcal{C}}$ be the cycle in $\operatorname{Pop_{T}}^{i+1}(w)$
that contains $g$. Note that the convex hulls of $\widetilde{\mathcal{C}}$ and
$\mathcal{C}_{2}$ have non-empty intersection in their interiors, and the
convex hulls of $\widetilde{\mathcal{C}}$ and $\mathcal{D}$ have non-empty
intersection in their interiors. It follows that $\mathcal{D}$ and
$\mathcal{C}_{2}$ are cycle connected, which is a contradiction.

Lastly, consider the case where both $d^{\prime}$ and
$(\mathcal{C}^{\prime})^{-1}(d^{\prime})=f^{\prime}$ lie clockwise between $b$
and $\bar{a}$. Note that in order for $\mathcal{C}^{\prime}$ to be cycle
connected to $\mathcal{B}_{2}$, there has to be a cycle $\mathcal{B}\in u$
which contains an element $\tilde{a}$ that lies clockwise between $d^{\prime}$
and $f^{\prime}$ such that $\mathcal{B}^{-1}(\widetilde{a})=\tilde{b}$ lies
clockwise between $\bar{a}$ and $b$. Let $\mathcal{B}^{\prime}$ be the cycle
in $\operatorname{Pop_{T}}^{i}(w)$ that contains $\tilde{a}$. Then
$\mathcal{D}$, $\mathcal{B}^{\prime}$ and $\mathcal{C}_{2}$ shows that
$\mathcal{D}$ and $\mathcal{C}_{2}$ are cycle connected in
$(\operatorname{Pop_{T}}^{B})^{i+1}(u)$, which is a contradiction. ∎

The above observations allow us to reduce to the case of $w$ being
pre-$D$-splittable.

######  Lemma 4.24.

If $\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$, then $w$ is
pre-$D$-splittable.

###### Proof.

Suppose $w$ is such that $\left|O_{\operatorname{Pop_{T}}}(w)\right|=2n-2$. By
Lemma 4.10, it follows that $w$ is zeroed. Suppose for the sake of
contradiction that $w$ is not pre-$D$-splittable. Then it follows that
$\operatorname{aexc}(w|_{n-1})\leq 2n-5$. If there does not exist $i$ such
that $\operatorname{Pop_{T}}^{i}(w)$ is bad, then by Corollary 4.19, it
follows that
$\left|O_{\operatorname{Pop_{T}}}(w)\right|=\left|O_{\operatorname{Pop_{T}}^{B}}(w|_{n-1})\right|\leq
2n-5+1=2n-4$, which is a contradiction. The remaining situations to handle are
when there is some $i$ such that $\operatorname{Pop_{T}}^{i}(w)$ is bad.

First, suppose there exists $j$ such that $\operatorname{Pop_{T}}^{j}(w)$ is
pierced. Lemma 4.22 implies that $j$ is unique. By Lemma 3.2 as well as the
arguments before this lemma, we have that

$\left|O_{\operatorname{Pop_{T}}^{B}}(\operatorname{Pop_{T}}^{j+1}(w)|_{n-1})\right|\leq\operatorname{aexc}(\operatorname{Pop_{T}}^{j+1}(w)|_{n-1})\leq
2n-5-j.$

Finally, suppose there exists $i$ such that $\operatorname{Pop_{T}}^{i}(w)$ is
double-cysted. By Corollary 4.21, since
$\operatorname{Pop_{T}}^{i}(w)|_{n-1}=(\operatorname{Pop_{T}}^{B})^{i}(w|_{n-1})$,
we have that the number of additional iterations of $\operatorname{Pop_{T}}$
needed for $\operatorname{Pop_{T}}^{i}(w)$ to reach $e$ does not exceed the
number of additional iterations of $\operatorname{Pop_{T}}^{B}$ needed for
$(\operatorname{Pop_{T}}^{B})^{i}(w|_{n-1})$.

Combining the above, it follows that
$\left|O_{\operatorname{Pop_{T}}}(w)\right|\leq\left|O_{\operatorname{Pop_{T}}^{B}}(w|_{n-1})\right|+1\leq
2n-5+2=2n-3$, a contradiction. ∎

Before we can finish up the proof of Theorem 1.7, we will need a simple
observation about permutations in $B_{n}$.

######  Claim 4.25.

Suppose $w\in B_{n}$ is such that
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(w)))\leq 1$ for
all $i\geq 0$. Suppose also that $(x)(\overline{x})\in w$. Define $v\in B_{n}$
by

$v(y)=\begin{cases}w(y)&\text{if }y\not\in\\{x,\overline{x}\\},\\\
\overline{x}&\text{if }y=x,\\\ x&\text{if }y=\overline{x}.\end{cases}$

Then
$\left|O_{\operatorname{Pop_{T}}}(v)\right|=\left|O_{\operatorname{Pop_{T}}}(w)\right|+1$.

###### Proof.

Define a total order $\prec$ on $\pm[n-1]$ by
$\overline{1}\prec\cdots\prec\overline{n-1}\prec 1\prec\cdots\prec n-1$.
Define $\prec_{j}$ to be the order obtained by doing a cyclic shift on $\prec$
such that the maximum element of $\prec_{j}$ is $j$.

Note that $\operatorname{aexc}{v}=\operatorname{aexc}(w)+1$. By Lemma 3.2, it
suffices to show that
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(v)))\leq 1$ for
all $i\geq 0$ as well. To that end, let
$\mathcal{A}=\\{y:y\prec_{x}\bar{y}\\}$ note that the convex hull of
$\\{y,\operatorname{Pop_{T}}^{i}(v))(y):y\in\mathcal{A}\\}\cup\\{x,\operatorname{Pop_{T}}^{i}(v))(x)\\}\setminus\\{\bar{x}\\}$
coincides with that of
$\\{y,\operatorname{Pop_{T}}^{i}(w)(y):y\in\mathcal{A}\\}$. As such,
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(v)))\leq 1$
follows from
$\operatorname{cyc_{>1}}(\pi_{T}(\operatorname{Pop_{T}}^{i}(w)))\leq 1$. ∎

###### Proof of Theorem 1.7.

First, let us establish that in order for $w\in D_{n}$ to satisfy
$|O_{\operatorname{Pop_{T}}}(w)|=2n-2$, $w$ must be $D$-splittable. Lemma 4.24
already shows that $w$ must be pre-$D$-splittable. Our work in Section 3 shows
that
$\operatorname{cyc_{>1}}(\pi_{T}((\operatorname{Pop_{T}}^{B})^{k}(w|_{n-1})))=1$
for all $i\geq 0$. Let $x=w(n)$. Note that since
$\operatorname{cyc_{>1}}(\pi_{T}((\operatorname{Pop_{T}}^{B})^{k}(w|_{n-1})))=1$,
the only possibility for $\operatorname{Pop_{T}}^{j}(w)$ to be pierced is if
$(x\enspace\bar{x})\in\operatorname{Pop_{T}}^{j+1}(w)|_{n-1}$ but
$(x)(x\enspace\bar{x})(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})$. Let this
property of $w$ be ($\dagger$).

Suppose $w$ is pre-$D$-splittable but not $D$-splittable. Then the smallest
index such that

$(x\enspace\bar{x})\in(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})$

is $j=2n-4$. But $(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})=e$. This shows
that there does not exist $i$ such that $\operatorname{Pop_{T}}^{i}(w)$ is
pierced. Corollary 4.19 and Claim 4.20 combined show that
$|O_{\operatorname{Pop_{T}}}(w)|=2n-3$, a contradiction.

It follows that to complete the proof of theorem it remains to show that
$D$-splittable permutations indeed have $\operatorname{Pop_{T}}$ forward orbit
of length $2n-2$ and to also enumerate the number of such pre-$D$-splittable
permutations.

Define a total order $\prec$ on $\pm[n-1]$ by
$\overline{1}\prec\cdots\prec\overline{n-1}\prec 1\prec\cdots\prec n-1$. As
before, define $\prec_{j}$ to be the order obtained by doing a cyclic shift on
$\prec$ such that the maximum element of $\prec_{j}$ is $j$.

First, we observe some properties of pre-$D$-splittable permutations. Suppose
$w\in D_{n}$ is pre-$D$-splittable, and let $w(n)=i$. For simplicity of
notation, suppose $i>0$; the analysis for when $i<0$ is analogous. First, it
is easy to see that $w|_{n-1}^{-1}(i)\prec_{i}\overline{i+1}$. Note that an
alternate description of permutations $v\in B_{n-1}$ with $2n-4$
antiexceedances is that it is made up of two cycles whose elements are
arranged in counterclockwise order on the circle of elements $\pm[n-1]$. In
particular, it follows that $\\{x:x\prec_{i}w|_{n-1}^{-1}(i)\\}$ lie in the
same cycle. When $w|_{n-1}^{-1}(i)\prec_{i}\overline{i+1}$, it can be checked
that the cycle in $w|_{n-1}$ containing $w|_{n-1}^{-1}(i)$ cannot have the
property that the elements are counterclockwise on the circle, which would
contradict $w|_{n-1}$ containing $2n-4$ antiexceedances. We also claim that
$w|_{n-1}^{-1}(i)\neq\overline{i-1}$. This is because the unique permutation
$u$ that has $2n-4$ antiexceedances satisfying $u^{-1}(i)=i-1$ is

$(i\enspace i+1\enspace\cdots\enspace
n-1\enspace\bar{1}\enspace\bar{2}\enspace\cdots\enspace\overline{i-1})(\overline{i}\enspace\overline{i+1}\enspace\cdots\enspace\overline{n-1}\enspace
1\enspace 2\enspace\cdots i-1)$

and $\operatorname{cyc_{>1}}(\pi_{T}(u))>1$.

Now, we enumerate the number of $D$-splittable permutations. Note that since
$i=w(n)\in\pm[n-1]$, there are a total of $2(n-1)$ possible choices for
$w(n)$. By symmetry, we assume that $i>0$. Observe that by definition of the
$(n-1)$-projection, any $D$-splittable permutation has the property of
$w|_{n-1}^{-1}(i)=w^{-1}(i)$. Suppose $w^{-1}(i)=j$ where
$j\prec_{i}\bar{i-2}$. The elements $\\{x:i\prec_{j}x\\}$ all lie in a cycle.
The remaining choices we have to make is to label each of the elements of
$\\{y:j-1\prec_{\overline{i}}y\\}$ with either $C_{1}$ or $C_{2}$ (indicating
which cycle the element lies in). Summing over all possible choices of $j$,
there are $2^{n-4}+2^{n-5}+\cdots+2=2^{n-3}-2$ way to do the labelling. Note
that $j=\bar{i}$ gives rise to one more such permutation, for a total of
$2^{n-3}-1$ possible permutations. Accounting for the $2(n-1)$ choices for
$i$, as well as $c^{-1}$, in total the number of $D$-splittable elements is
given by $2(n-1)\cdot(2^{n-3}+1)+1=(n-1)\cdot(2^{n-2}+2)+1$, as desired.

It remains to prove that pre-$D$-splittable permutations $w$ actually have
$\operatorname{Pop_{T}}$ forward orbits of length $2n-2$. It is clear that
$\left|O_{\operatorname{Pop_{T}}}(c^{-1})\right|=2n-2$, so it remains to
handle the case when $w\neq c^{-1}$. Our task is two-fold: first, we will show
that for all $i\geq 1$, $\operatorname{Pop_{T}}^{i}(w)$ is zeroed. This would
in particular imply that there does not exist $i$ such that
$\operatorname{Pop_{T}}^{i}(w)$ is double-cysted. Then, we show that there
exists an index $j$ such that $\operatorname{Pop_{T}}^{j}(w)$ is pierced. Let
$x=w(n)$. Equivalently, the property ($\dagger$) implies that it suffices to
show that for some $j\leq 2n-5$ that
$(x)(x\enspace\bar{x})(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})$. Once we
have established both of these, the desired conclusion follows from Claim
4.20, Lemma 4.22 and Claim 4.25 that
$\left|O_{\operatorname{Pop_{T}}}(c^{-1})\right|=(2n-3)+1=2n-2$.

Now, let us show that for all $i\geq 1$, $\operatorname{Pop_{T}}^{i}(w)$ is
zeroed. Observe that any $D$-splittable permutation $w$ has the property that
$\left|\\{y:y\prec_{x}w^{-1}(x)\\}\right|\leq n-1$ for $x\in\pm[n-1]$. In
particular, for $1\leq j\leq n-1$ and $x\in\pm[n-1]$,
$\operatorname{Pop_{T}}^{j}(w)(x)\neq x$. Suppose $i$ is the smallest index
such that $\operatorname{Pop_{T}}^{i}(w)$ is not zeroed. Then there exists
some $z\in[n-1]$ such that for all $x\in\pm[n-1]$ with $x\prec_{z}\bar{z}$, we
have that
$\operatorname{Pop_{T}}^{i}(w)(x),\operatorname{Pop_{T}}^{i}(w)^{-1}(x)\prec_{z}\bar{z}$
as well. Let $z^{\prime}\prec_{z}\bar{z}$ be the smallest index such that
$\operatorname{Pop_{T}}^{i}(w)(z^{\prime})\neq z^{\prime}$. Then
$\operatorname{Pop_{T}}^{i}(w)(z^{\prime})\prec_{z}\bar{z}$ implies that
$i<n-1$. This in turn implies that there exists $y$ such that
$y\prec_{\overline{z-1}}w^{-1}(\overline{z-1})=:a$. Let $b$ be the element
that is clockwise along the circle from $a$. Then because of the structure of
$D$-splittable permutations, either $w^{-1}(y)=a$ or $w^{-1}(y)=b$. In either
case, $\operatorname{Pop_{T}}^{j}(w)^{-1}(y)\prec_{z}\bar{z}$. This shows that
the convex hull of $\\{\operatorname{Pop_{T}}^{j}(w)(x):x\prec_{z}\bar{z}\\}$
has non-empty intersection with $\\{x:\bar{z}\prec_{z}x\\}$, which implies
that $\operatorname{Pop_{T}}^{i}(w)$ is zeroed, as desired.

Finally, we show that there exists an index $j\leq 2n-5$ such that
$(x)(x\enspace\bar{x})\in(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})$. Note
that
$w^{-1}(x)\prec_{x}(\operatorname{Pop_{T}}^{B})(w)^{-1}(x)\prec_{x}(\operatorname{Pop_{T}}^{B})(w)^{-2}(x)\prec_{x}\cdots$.
Since there are at most $2n-5$ elements $y$ such that $w^{-1}(x)\prec_{x}y$,
it follows that for some $j\leq 2n-5$, we have
$x=(\operatorname{Pop_{T}}^{B})^{j+1}(w|_{n-1})^{-1}(x)$, which is the desired
conclusion. ∎

##  5\. Conclusion and further work

For a finite Coxeter group $(W,S)$ with Coxeter number $h$, fixed Coxeter
element $c$, and set of all reflections $T$, the length of the longest orbit
of $\operatorname{Pop_{T}}(\cdot,c)$ is $h$ (see for instance [11, Theorem 5.1
and Theorem 6.1]). In the previous sections, we have given a classification
and enumeration of the forward orbits with close to maximal length. While we
now have a complete understanding of the elements in type $A$ and type $B$
Coxeter groups with forward orbit of length $h-1$, where $h$ is the Coxeter
number of the group under consideration, we only understand elements with
maximum forward orbit length for type $D$ Coxeter groups. We related the
problem of classifying elements with forward orbits of length $2n-3$ in
$D_{n}$ to the question of classifying elements with forward orbits of length
$2n-2$ and $2n-3$ in $B_{n-1}$. It seems reasonable to expect that in order to
understand forward orbits of length $2n-4$ in $D_{n}$, it would be beneficial
to understand forward orbits of length at most $2n-4$ in $B_{n-1}$.

It is natural, therefore, to ask a similar enumeration and classification
question for orbits of other lengths.

######  Question 5.1.

Let $W$ be a Coxeter group of type $A$ or $B$. Let $h$ be the Coxeter number
of $W$ and let $\alpha$ be an integer in the interval $[2,h-2]$. What is the
number of forward orbits of $\operatorname{Pop_{T}}$ with length $\alpha$?

######  Question 5.2.

Let $W$ be a Coxeter group of type $D$. Let $\alpha$ be an integer in the
interval $[2,2n-4]$. What is the number of forward orbits of
$\operatorname{Pop_{T}}$ with length $\alpha$?

Another potential direction is inspired by [9, 10]. In order to state this
question, we need to introduce a piece of notation. We say that $w\in W$ is
_$t$ -pop-stack-sortable_ if $\operatorname{Pop_{S}}^{t}(w)=e$. In [9],
Claesson and Gomundsson proved that for every fixed $t\geq 0$, the generating
function that counts $t$-pop-stack-sortable permutations in symmetric groups
is rational. Defant [10] generalized this result to hyperoctahedral groups
$B_{n}$. It is natural to ask a similar question in the context of $t$-pop-
tsack-torsable permutations, defined analogously. We say that $w\in W$ is _$t$
-pop-tsack-torsable_ if $\operatorname{Pop_{T}}^{t}(w)=e$.

Note, however, that the situation is slightly more subtle in the context of
$\operatorname{Pop_{T}}$ as compared to that of $\operatorname{Pop_{S}}$. In
particular, it is false in general that the generating function which counts
$t$-pop-tsack-torsable permutations is rational. For the sake of simplicity,
to illustrate this point, we restrict to the context of $W=\mathfrak{S}_{n}$.
By construction, the elements of $\mathfrak{S}_{n}$ that are $1$-pop-tsack-
torsable are exactly the non-crossing partitions of $\mathfrak{S}_{n}$, and
these are counted by the Catalan numbers. It follows, therefore, that the
generating function that counts 1-pop-tsack-torsable permutations in
$\mathfrak{S}_{n}$ is not rational.

Theorem 1.5, for instance, shows that the generating function that counts
$(n-1)$-pop-tsack-torsable permutations in $\mathfrak{S}_{n}$ is rational.
This observation motivates the following question.

######  Question 5.3.

Let $W$ be a Coxeter group of type $A,B$, or $D$. What is the range of values
of $t$ such that the generating function counting $t$-pop-tsack-torsable is
rational? More precisely, what is the range of values of $t$ such that

$\sum_{n\geq 1}\left|\operatorname{Pop_{T}}^{-(n-t)}(e)\right|z^{n}$

is rational?

##  6\. Acknowledgements

This work was done at the University of Minnesota Duluth with support from
Jane Street Capital, the NSA (grant number H98230-22-1-0015), and
Massachusetts Institute of Technology. We would like to thank Joe Gallian for
organizing the REU and for his constant support and helpful suggestions. We
are also immensely grateful to Colin Defant for proposing this problem and for
his invaluable help in editing this paper. We would also like to thank Yelena
Mandelshtam for her helpful comments on a draft version of this paper. Last
but not least, we would like to express our appreciation towards Amanda
Burcroff, Colin Defant and Noah Kravitz for advising this program.

## References

  * [1] Drew Armstrong, _Generalized noncrossing partitions and combinatorics of Coxeter groups_ , Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR 2561274
  * [2] A. Asinowski, C. Banderier, S. Billey, B. Hackl, and S. Linusson, _Pop-stack sorting and its image: permutations with overlapping runs_ , Acta Math. Univ. Comenian. (N.S.) 88 (2019), no. 3, 395–402. MR 4012843
  * [3] Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, _Flip-sort and combinatorial aspects of pop-stack sorting_ , Discrete Math. Theor. Comput. Sci. 22 (2021), no. 2, Paper No. 4, 39. MR 4252323
  * [4] Christos A Athanasiadis and Victor Reiner, _Noncrossing partitions for the group $D_{n}$_, SIAM Journal on Discrete Mathematics 18 (2004), no. 2, 397–417.
  * [5] David Bessis, _The dual braid monoid_ , Ann. Sci. École Norm. Sup. (4) 36 (2003), no. 5, 647–683. MR 2032983
  * [6] Miklós Bóna, _A survey of stack-sorting disciplines_ , Electron. J. Combin. 9 (2002/03), no. 2, Article 1, 16, Permutation patterns (Otago, 2003).
  * [7] Thomas Brady and Colum Watt, _Non-crossing partition lattices in finite real reflection groups_ , Trans. Amer. Math. Soc. 360 (2008), no. 4, 1983–2005. MR 2366971
  * [8] Lapo Cioni and Luca Ferrari, _Preimages under the Queuesort algorithm_ , Discrete Math. 344 (2021), no. 11, Paper No. 112561, 14. MR 4298162
  * [9] Anders Claesson and Bjarki Ágúst Gueth mundsson, _Enumerating permutations sortable by $k$ passes through a pop-stack_, Adv. in Appl. Math. 108 (2019), 79–96. MR 3940979
  * [10] Colin Defant, _Pop-stack-sorting for coxeter groups_ , To appear in Comb. Theory.
  * [11] Colin Defant and Nathan Williams, _Coxeter pop-tsack torsing_ , Algebr. Comb. 5 (2022), no. 3, 559–581. MR 4456869
  * [12] Murray Elder and Yoong Kuan Goh, _$k$ -pop stack sortable permutations and 2-avoidance_, Electron. J. Combin. 28 (2021), no. 1, Paper No. 1.54, 15. MR 4245287
  * [13] Donald E. Knuth, _The art of computer programming. Volume 3_ , Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973, Sorting and searching. MR 0445948
  * [14] Peter Ungar, _$2N$ noncollinear points determine at least $2N$ directions_, J. Combin. Theory Ser. A 33 (1982), no. 3, 343–347. MR 676751