swap with $h_{2}$ and $h_{3}$ and so on until $h_{b+1}$. If $h_{1}$ is not a
monomial, this means that all of $h_{2},h_{3},\ldots,h_{b+1}$ are monomials.
If $h_{1}$ is a monomial $x^{p}$, this means none of
$h_{2},h_{3},\ldots,h_{b+1}$ are monomials of the same degree $p$. In
particular, whatever $h_{1}$ becomes after all these swaps cannot be the same
shape as any of the things that $h_{2},h_{3},\ldots,h_{b+1}$ become after
these swaps (recall Definition 2.155 for the notion of “becoming”) . However,
if $b+1>N$, this list $h_{2},h_{3},\ldots,h_{b+1}$ contains a full $N$-period
of $t_{b}t_{b-1}\ldots t_{1}\star h$, so $h_{1}$ has to have the same shape as
one of them!

So we now know that $v_{r}$ does not touch the factors
$h_{k},\ldots,h_{N+2},h_{N+1}$. Thus, these are also the factors of
$v_{r}\star h$ which has $N$-periodic nomodata. Because $N$ is a proper
divisor of $k$ it is at most $k/2$. Thus, $v_{r}$ leaves fixed at least half
of the factors and, in particular, leaves fixed the whole left-most period.

Exactly the same reasoning applies to $v_{\ell}$. Let $g:=t_{k}\star f$, so
that $v_{\ell}\star g=h$. If $a<k-N$, then $g_{k}$ swaps across at least $N$
factors of $g$ which then become the leftmost $N$ factors
$h_{k},h_{k-1},\ldots,h_{k-N+1}$ of $h$, which are then untouched by $v_{r}$
and become the leftmost period of $v_{r}\star h$ which has $N$-periodic
nomodata. Whatever $g_{k}$ has become after all these swaps has to have
something like the shape of one of these factors
$h_{k},h_{k-1},\ldots,h_{k-N+1}$ that this very $g_{k}$ swapped across, giving
the same contradiction. ∎

With the next proposition we extend the reduction of Proposition 2.90 arguing
that we may drop $v_{r}$. The idea here is that $v_{r}$ acts on the rightmost
$N$-period, and we can instead undo its action on all other $N$-periods. Since
these periods have the same nomodata, and nomodata completely determine
whether Ritt swaps are defined, this action will necessarily be defined.

######  Proposition 2.92.

Let $f$ be a long decomposition and $N$ a proper divisor of $k$. Suppose that
$g:=v_{r}v_{\ell}t_{k}\star f$ has $N$-periodic nomodata for some
$v_{\ell}=t_{a}t_{a+1}\cdots t_{k-1}$ and $v_{r}=t_{b}t_{b-1}\ldots t_{1}$.
Then $w_{\ell}t_{k}u\star f$ has $N$-periodic nomodata for some left-to-right
transit $w_{\ell}=t_{a^{\prime}}t_{a^{\prime}+1}\cdots t_{k-1}$ and some
$u\in\operatorname{Sym}_{k}$.

###### Proof.

From Proposition 2.91, we know that $b\leq N-1$, so that $v_{r}$ acts on the
rightmost $N$-period. For $j=1,2,3,\ldots,k/N$, let $u_{j}$ be the word that
acts like $v_{r}^{-1}$ on the $j^{\text{th}}$ $N$-period. Formally, expressing
$v_{r}$ as a word in $t_{i}$’s, $u_{j}$ is obtained from $v_{r}^{-1}$ by
adding $(j-1)N$ to the index of each Ritt swap $t_{i}$ in the word. So,
$u_{1}=v_{r}^{-1}$. Since $v_{r}^{-1}\star g$ is defined, and $g$ has
$N$-periodic nomodata, $u_{j}\star g$ is also defined for each $j$. Since
these $u_{j}$ act on disjoint parts of $g$, the composition $u_{k/N}\ldots
u_{2}u_{1}\star g$ is also defined. Since $u_{k/n}\ldots u_{2}u_{1}$ does the
same thing to each $N$-period, the new decomposition

$u_{k/N}\ldots u_{2}u_{1}\star g=u_{k/N}\ldots
u_{2}u_{1}v_{r}v_{\ell}t_{k}\star f=u_{k/N}\ldots u_{2}v_{\ell}t_{k}\star f$

also has $N$-periodic nomodata. For $j=2,3,\ldots,k/N-1$, the $u_{j}$ act on
the “middle” $N$-periods – not the first nor the last – so they commute with
$v_{\ell}$ and with $t_{k}$. Thus, we see that

$u_{k/N}\ldots u_{2}v_{\ell}t_{k}\star
f=(u_{k/N}v_{\ell})t_{k}(u_{k/N-1}\ldots u_{2})\star f$

has $N$-periodic nomodata. Finally, putting $u_{k/N}v_{\ell}$ into first
canonical form $w_{\ell}u_{0}$ for some $u_{0}\in\langle t_{k-N},\ldots
t_{k-2}\rangle$, acting on all but the leftmost of the factors of the leftmost
$N$-period, and and left-to-right transit
$w_{\ell}=t_{a^{\prime}}t_{a^{\prime}+1}\cdots t_{k-1}$. Again, $u_{0}$
commutes with $t_{k}$. So we get

$(u_{k/N}v_{\ell})t_{k}(u_{k/N-1}\ldots u_{2})\star
f=w_{\ell}u_{0}t_{k}(u_{k/N-1}\ldots u_{2})\star
f=w_{\ell}t_{k}(u_{0}u_{k/N-1}\ldots u_{2})\star f$

to have $N$-periodic nomodata. Setting $u:=u_{0}u_{k/N-1}\ldots u_{2}$
completes the proof. ∎

Next, we drop $v_{\ell}$ from Proposition 2.90 in the same way.

######  Proposition 2.93.

Fix a long decomposition $f$ and a proper divisor $N$ of $k$. Suppose that
$g:=v_{\ell}t_{k}\star f$ has $N$-periodic nomodata for some
$v_{\ell}=t_{a}t_{a+1}\ldots t_{k-1}$. Then $t_{k}u\star f$ has $N$-periodic
nomodata for some word $u\in\operatorname{Sym}_{k}$.

###### Proof.

In Proposition 2.91 we proved that $a\geq k/N+1$. We now improve this to
$a>k/N+1$. Suppose towards contradiction that $a=k/N+1$. Then the rightmost
factor $g_{k/N+1}$ of the leftmost $N$-period in $g=v_{\ell}t_{k}\star f$
comes from $f_{1}$: first, $t_{k}$ moves $f_{1}$ to the $k^{\text{th}}$ spot,
and then $v_{\ell}$ moves it right to the end of the period. Since $g$ has
$N$-periodic nomodata, this $g_{k/N+1}$ has the same combinatorial shape as
the rightmost factor $g_{1}$, which came from $f_{k}$. So, something that came
from $f_{1}$ and something that came from $f_{k}$ now have the same
combinatorial shape, but this contradicts the fact that $f_{1}$ and $f_{k}$
Ritt-swapped when $t_{k}$ acted on $f$.

As in the proof of the Proposition 2.92, for $j=1,2,\ldots,k/N$, let $u_{j}$
act on the $j^{\text{th}}$ $N$-period the same way that $v_{\ell}^{-1}$ acts
on the leftmost $N$-period. So $u_{j}$ is obtained from $v_{\ell}^{-1}$ by
adding $jN$ to (equivalently, subtracting $N(k/N-j)$ from) the index of each
Ritt swap $t_{i}$ occurring in some presentation of $v_{\ell}^{-1}$. As
before, $u_{1}u_{2}\cdots u_{k/N}\star g$ is defined and has $N$-periodic
nomodata. Thus we conclude that

$u_{1}u_{2}\cdots u_{k/N}\star g=u_{1}u_{2}\cdots u_{k/N}v_{\ell}t_{k}\star
f=u_{1}u_{2}\cdots u_{k/N-1}t_{k}\star f$

is $N$-periodic. As before, $u_{j}$ with $j=2,3,\ldots,k/N-1$ commute with
$t_{k}$. We also know that $v_{\ell}$ does not involve $t_{k/N+1}$, so $u_{1}$
does not involve $t_{1}$ implying that $u_{1}$ also commutes with $t_{k}$.
Thus,

$u_{1}u_{2}\cdots u_{k/N-1}t_{k}\star f=t_{k}(u_{1}u_{2}\cdots u_{k/N-1})\star
f$

has $N$-periodic nomodata. Setting $u:=u_{1}u_{2}\cdots u_{k/N-1}$ completes
the proof. ∎

Finally, we get drop $t_{k}$ in the same way.

######  Proposition 2.94.

Fix a long decomposition $f$ and a proper divisor $N$ of $k$. Suppose that
$g:=t_{k}\star f$ has $N$-periodic nomodata. Then $u\star f$ has $N$-periodic
nomodata for some $u\in\operatorname{Sym}_{k}$.

###### Proof.

Instead of $t_{k}$ swapping across the boundary of the $k$-period to achieve
periodicity, swap across all the boundaries of $N$-periods that are not
boundaries of the $k$-periods. That is, let

$u:=t_{N}t_{2N}\ldots t_{(k-N)}\text{ .}$

∎

The proof of Theorem 2.86 is now complete.

######  Corollary 2.95.

Let $f$ be a clean $\mathsf{C}$-free long decomposition. Let $e$ be the echo
of $w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$. Then there exists
some $u\in\operatorname{Sym}_{k}$ for which $u\star f$ is defined and has
$e$-periodic nomodata.

###### Proof.

Theorem 2.85 provides some $v\in\operatorname{ASym}_{k}$ for which $v\star f$
is defined and has $e$-periodic nomodata. Theorem 2.86 allows us to replace
$v\in\operatorname{ASym}_{k}$ by $u\in\operatorname{Sym}_{k}$. ∎

Let us record the reduction of the proof of Theorem 1.3 for clean
$\mathsf{C}$-free long decompositions to the special case of $e$-periodic
nomodata.

######  Proposition 2.96.

Let $f$ be a clean $\mathsf{C}$-free long decomposition of a polynomial $P$,
let $\mathcal{C}$ be the $(P,P^{\tau})$ skew-invariant curve encoded by
$w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$, and let $e$ be the
echo of $w\star f=f^{\tau}$.

There exists another clean $\mathsf{C}$-free long decomposition $g$ of the
polynomial $P$ and another $w^{\prime}\in\operatorname{ST}_{k}$ with
$w^{\prime}\star g=g^{\tau}$ encoding the same curve $\mathcal{C}$ with the
additional property that the nomodata of $g$ is $e$-periodic.

###### Proof.

Corollary 2.95 provides the new decomposition $g:=u\star f$ of the same
polynomial $P$ with $e$-periodic nomodata, for some
$u\in\operatorname{Sym}_{k}$.

Replacing $f$ by $u^{-1}\star g$ in the Mahler equation $\phi^{N}w\star
f=f^{\tau}$ encoding the skew-invariant curve $\mathcal{C}$ yields

$\phi^{N}wu^{-1}\star g=u^{-1}\star g^{\tau}$

and then

$u\phi^{N}wu^{-1}\star g=g^{\tau}$

and

$\phi^{N}w^{\prime}\star g=g^{\tau}$

where $w^{\prime}=\widehat{u}wu^{-1}$ where $\widehat{u}$ is defined by
$u\phi^{N}=\phi^{N}\widehat{u}$. Since $u\in\operatorname{Sym}_{k}$, the curve
it encodes is the diagonal. Thus, all these equations encode the same curve
$\mathcal{C}$, with the same echo $e$. ∎

In the remainder of this section we complete the proof of Theorem 1.3 for
polynomials admitting long decompositions with sufficiently periodic nomodata.

######  Lemma 2.97.

Let $f$ be a clean $\mathsf{C}$-free long decomposition of a polynomial $P$,
let $\mathcal{C}$ be the $(P,P^{\tau})$ skew-invariant curve encoded by
$\phi^{N}w\star f=f^{\tau}$ for some $w\in\operatorname{ASym}_{k}$, and let
$e$ be the echo of $w\star f=f^{\tau}$. Fix a nonmonomial listing function
$\alpha$ for $f$. If $f$ has $e$-periodic nomodata, then the trace of $w$ on
$(f,\alpha)$ is trivial.

###### Proof.

Since $f$ and $f^{\tau}$ admit identical nomodata and $w\star f$ is defined,
so is $w\star f^{\tau}$. It follows from Corollary 2.76 that there is a
multiple $r$ of $e$ such that $w\star(f,\alpha)=(f^{\tau},\beta)$ where
$\beta(j)=\alpha(j+r)$ for all $j$. Because $\alpha$ is $e$-periodic,
$\beta=\alpha$. Because the in- and out-degrees of the corresponding factors
of $f$ and $f^{\tau}$ are the same, we see that
$0=\operatorname{trace}_{w,f,\alpha}$. ∎

######  Lemma 2.98.

If $w\in\operatorname{ST}^{+}_{k}$ satisfies $w\star f=f^{\tau}$ for some
clean $\mathsf{C}$-free long decomposition $f$ of some non-exceptional
polynomial, then $w\in\operatorname{ST}_{k}$.

###### Proof.

By Remark 2.34, we may write $w=u\varepsilon$ where
$u\in\operatorname{ST}_{k}$ and
$\varepsilon=\prod_{p\in\mathcal{P}}\epsilon_{p}^{m_{p}}$ is a product of
powers of $\epsilon_{p}$ for various $p$. We may choose words $\widehat{u}$
and $\widehat{\varepsilon}$ representing $u$ and $\varepsilon$, respectively,
for which the such $\widehat{u}\widehat{\varepsilon}$ is reduced. Since
$w\star f$ is defined, so is $\widehat{u}\widehat{\varepsilon}\star f$. If
$m_{p}>0$ (respecitvely, $m_{p}<0$) for some $p$, then $\epsilon_{p}\star f$
(resp., $\epsilon_{p}^{-1}\star f$) is defined. Thus, in particular, the
monomial $x^{p}$ does not occur in $f$.

Fix a nonmonomial listing function $\alpha$ for $f$. Recall that $\alpha$ is
also a nomonomial listing function for $f^{\tau}$ and for
$\varepsilon^{-1}\star f^{\tau}$. Note that because $x^{p}$ does not appear in
$f$, the $\operatorname{trace}_{u,f,\alpha}(j,p)=0$ for all $j$. Rewrite the
equation $\varepsilon u\star f=f^{\tau}$ as $u\star f=\varepsilon^{-1}\star
f^{\tau}$ and compare the $p$-part of the nomodata for the two sides of the
equation. On the left, there is some $r$ for which

$\operatorname{in}_{u\star(f,\alpha)}(j,p)=\operatorname{in}_{f,\alpha}(j+r,p)+\operatorname{trace}_{u,f,\alpha}(j,p)=\operatorname{in}_{f,\alpha}(j+r,p)$

(see Lemma 2.67 and Remarks 2.61 and 2.62). On the right,
$\operatorname{in}_{f^{\tau},\alpha}=\operatorname{in}_{f,\alpha}$, while
$\operatorname{in}_{\varepsilon^{-1}\star
f^{\tau},\alpha}(j,p)=\operatorname{in}_{f^{\tau},\alpha}(j,p)+m_{p}$. If
$m_{p}\neq 0$, this gives a contradiction since
$\operatorname{in}_{f,\alpha}(j,p)$ is bounded. ∎

We conclude this section by proving Theorem 1.3 for clean $\mathsf{C}$-free
long decompositions.

######  Proposition 2.99.

Theorem 1.3 holds in the case that the polynomial $P$ admits a clean
$\mathsf{C}$-free long decomposition $f$.

###### Proof.

Let $\mathcal{C}$ be a $(P,P^{\tau})$-skew invariant curve encoded by
$f^{\tau}=w\star f$ for some long decomposition $f$ of $P$ and
$w\in\operatorname{ST}^{+}_{k}$. Fix a parameterization $(A(t),B(t))$ of
$\mathcal{C}$ by polynomials with no common nonlinear initial compositional
factors. Recall from Definition 2.56 that $n_{f}$ (respectively, $n_{A}$ and
$n_{B}$) is the number of nonmonomials appearing in one $k$-period of $f$
(respectively, in a decomposition of $A$ or $B$) and the echo is
$e=\gcd(n_{f},(n_{B}-n_{A}))$. Fix $\alpha$ a nonmonomial listing function for
$f$.

By Lemma 2.98, $w\in\operatorname{ST}_{k}$. Write $w=\phi^{N}w^{\prime}$ for
some $N\in\mathbb{Z}$ and $w^{\prime}\in\operatorname{ASym}_{k}$. By
Proposition 2.96, we may assume that $f$ has $e$-periodic nomodata. By Lemma
2.97, $\operatorname{trace}_{w^{\prime},f,\alpha}$ is identically zero. Then
Lemma 2.71 shows that $w^{\prime}$ may be expressed as
$w^{\prime}=u_{n_{f}}\cdots u_{2}u_{1}$ , a commuting product of $u_{j}$’s,
where each $u_{j}$ is a product of puddleswaps in the $j^{\text{th}}$ puddle.
In particular, the part of the curve encoded by $w^{\prime}$ consists of
monomials. Thus, $n_{A}=0$ and $n_{B}$ is the number of non-monomials among
$f_{N},\ldots f_{2},f_{1}$.

As noted in Remark 2.46, it suffices to show that $w=u\phi^{N}v$ for some
$u,v\in\operatorname{Sym}_{k}$.

If $t_{k}$ is not a puddle-swap, it does not occur in $w^{\prime}$ so that we
may take $u=\operatorname{id}$ and $v=w^{\prime}$.

From now on, at the cost of replacing $\alpha$, we may take $u_{1}$ to act on
the puddle containing $f_{k}$ and $f_{k+1}$.

If $n_{f}$ does not divide $(n_{B}-n_{A})$, then $\phi^{N}$ moves the puddle
containing $f_{k}$ and $f_{k+1}$ to another puddle. Thus,
$\phi^{N}w^{\prime}=\widehat{u_{1}}\phi^{N}u_{n_{f}}\ldots u_{2}$ with both
$u_{n_{f}}\cdots u_{2}$ and $\widehat{u_{1}}$ in $\operatorname{Sym}_{k}$.

Otherwise, if $n_{f}$ does divide $(n_{B}-n_{A})$, then the puddle containing
$f_{k}$ and $f_{k+1}$ in $f$ corresponds to the “same” puddle containing
$f_{k}^{\tau}$ and $f_{k+1}^{\tau}$ in $f^{\tau}$ via $\phi^{N}w^{\prime}\star
f=f^{\tau}$. In particular, $u_{1}$ must be empty, so again we may take
$u=\operatorname{id}$ and $v=w^{\prime}\in\operatorname{Sym}_{k}$. ∎

###  2.3. Clusterings

In this section, we adapt the technology of _clusterings_ from [8] to long
decompositions to identify more sophisticated combinatorial invariants, beyond
wall sets and nomodata. This allows us to identify several ways for walls to
appear in decompositions all of whose compositional factors are swappable (see
Propositions 2.112 and 2.153 and Lemma 2.158). The same technology
characterizes and then handles the last remaining case of decompositions with
type $\mathsf{C}$ factors but without walls (see Proposition 2.172). The key
difference from [8] is that the boundary between the $k^{\text{th}}$ and
$(k+1)^{\text{st}}$ entries is now treated just like all the others.

####  2.3.1. Preclusterings

The following definition is closely related to [8, Definitions 4.2 and 6.10].

######  Definition 2.100.

A _preclustering_ $A$ of a $k$-long decomposition$f$ is a $k$-periodic subset
of $\mathbb{Z}$ such that for any integers $b>a$ in $A$ with no elements of
$A$ between them,

$f_{[b,a)}:=(f_{b},f_{b-1},\ldots,f_{a+1})$

is a cluster in the sense of [8, Definition 4.2]. That is, either one of the
two following conditions holds.

  * •

There are linear polynomials $E$ and $B$ so that $B\circ f_{b}\circ\cdots\circ
f_{a+1}\circ E=C_{n}$ is a Chebyshev polynomial of degree $n$ not a power of
two.In this case, $f_{[b,a)}$ is called a _$\mathsf{C}$ -cluster_.

  * •

There are linear polynomials $E$ and $B$ so that $B\circ f_{b}\circ\cdots\circ
f_{a+1}\circ E=h_{b}\circ\cdots\circ h_{a+1}$ where each $h_{i}$ is a monomial
or a Ritt polynomial which is not type $\mathsf{C}$ for all $i\in(a,b]$. In
this case, $f_{[b,a)}$ is called a _$\mathsf{C}$ -free cluster_.

Such $f_{[b,a)}$ is a _cluster of $(f,A)$_.
The empty set is a preclustering of $f$ if $f_{[b,a)}$ is a cluster for any
integers $b\geq a+k$.

######  Remark 2.101.

Let us translate parts (1), (2), and (3) of [8, Remark 4.5] to this context.

  1. (1)

If some factor of $f$ is unswappable, $f$ has no preclusterings.

  2. (2)

If all factors of a $k$-long decomposition$f$ are swappable, then $\mathbb{Z}$
is a preclustering of $f$.

  3. (3)

Linearly-equivalent long decompositions have the same preclusterings.

Let us expand the less trivial [8, Remark 4.5(4)]. It concerns the requirement
that the degree of a $\mathsf{C}$-cluster must not be a power of $2$. Because
of it, we cannot drop the hypothesis that $a,b\in A$ from the definition of
“preclustering”. This is also the reason for $b\geq a+k$ instead of $b>a$ in
the definition of empty preclustering.

With the following remark we record how a piece of a cluster may fail to be a
cluster itself.

######  Remark 2.102.

A piece of a cluster is usually a cluster: if $d\geq c>b\geq a$ and
$f_{[d,a)}$ is a cluster, then $f_{[c,b)}$ is a cluster unless $f_{[d,a)}$ is
a $\mathsf{C}$-cluster, and all factors of $f_{[c,b)}$ are quadratic, and
$f_{[c,b)}$ has at least two factors. Here are some useful ways to avoid the
exception.

  1. (1)

Any piece of a $\mathsf{C}$-free cluster is a $\mathsf{C}$-free cluster.

  2. (2)

Any piece of a $\mathsf{C}$-cluster is one of the following:

     * •

contains an odd-degree factor and is a $\mathsf{C}$-cluster;

     * •

contains exactly one factor, which is quadratic; and is a $\mathsf{C}$-free
cluster;

     * •

contains multiple quadratic factors and no odd-degree factors; and is not a
cluster.

  3. (3)

Removing a _quadratic_ factor from a cluster is harmless: if $f_{[b,a)}$ is a
cluster and $f_{a+1}$ (respectively, $f_{b}$) is quadratic, then $f_{[b,a+1)}$
(respectively, $f_{[b-1,a)}$) is a cluster of the same kind, $\mathsf{C}$ or
$\mathsf{C}$-free.

  4. (4)

A piece of a $\mathsf{C}$-cluster that contains a big-enough cluster is itself
a $\mathsf{C}$-cluster. That is, if $b^{\prime\prime}\geq b\geq
b^{\prime}>a^{\prime}\geq a\geq a^{\prime\prime}$, and
$f_{[b^{\prime\prime},a^{\prime\prime})}$ is a $\mathsf{C}$-cluster, and
$f_{[b^{\prime},a^{\prime})}$ is a cluster, but is not a single quadratic,
then $f_{[b,a)}$ is also a $\mathsf{C}$-cluster.

  5. (5)

In (4), the inner cluster $f_{[b^{\prime},a^{\prime})}$ being big enough is
equivalent to it being a $\mathsf{C}$-cluster.

Suppose that $A$ is a preclustering of $f$ and $B\supset A$ is also
$k$-periodic. This $B$ is also a preclustering of the same $f$ if and only if
for every $\mathsf{C}$-cluster of $(A,f)$, the degrees of its pieces in
$(B,f)$ are either $2$ or not powers of $2$.

With the next remark we correlate our notion of preclustering on long
decompositions with the corresponding version in [8] for decompositions.

######  Remark 2.103.

The first two observations are related to parts of [8, Lemma 6.11] and the
third is related to [8, Lemma 6.14].

  1. (1)

If $A$ is a preclustering of $f$, and $0\in A$, then $A\cap\\{0,1,\ldots k\\}$
is a preclustering of $(f_{k},\ldots f_{1})$ in the sense of [8, Definition
4.2]. The assumption $0\in A$ is not cosmetic, because of Remark 2.102.

  2. (2)

More generally, for any $a\in A$, the tuple $A\cap\\{a,a+1,\ldots a+k\\}$ is a
preclustering of the decomposition $(f_{a+k},\ldots f_{a+1})$, in the sense of
[8, Definition 4.2].

  3. (3)

If the empty set is a preclustering of $f$, then the polynomial
$f_{k}\circ\cdots\circ f_{1}$ is linearly related to a (possibly decomposable)
Ritt polynomial in the sense of [8, Definition 2.41]. In Proposition 2.120
below, we almost drop “linearly related” from that statement.

The next definition is very close to [8, Definition 4.3] and to the cleanup in
[8, Lemma 6.11(6)]. When at least one of the clusters is a $\mathsf{C}$
cluster, this literally translates the old definition into the new notation
because a linear factor which is both a translation and a scaling is identity.
When all clusters are $\mathsf{C}$-free, we no longer have a canonical place
to put scalings.

######  Definition 2.104.

Fix a preclustering $A$ of a $k$-long decomposition$f$.

A _precleanup_ of $(A,f)$ is a pair $(h,L)$, where $h$ is a $k$-long
decomposition, $L$ is a $k$-skew periodic sequence of linear polynomials-
linear, and the following hold.

  1. (1)

The $k$-long decomposition$L\circ h$ is linearly equivalent to $f$.

  2. (2)

For $i\notin A$, the linear $L_{i}$ is identity.

  3. (3)

If $f_{[b,a)}$ is a $\mathsf{C}$-cluster of $(A,f)$, and $b\geq i>a$, then
$h_{i}$ is a Chebyshev polynomial;

  4. (4)

If $f_{[b,a)}$ is a $\mathsf{C}$-free cluster of $(A,f)$, and $b\geq i>a$,
then $h_{i}$ is a monic Ritt polynomial;

The precleanup is a _cleanup_ if, furthermore,

  1. (5a)

if there is a $\mathsf{C}$-cluster, whenever $f_{[b,a)}$ is a
$\mathsf{C}$-free cluster, $L_{a}$ is a translation, and

  2. (5b)

whenever $f_{[b,a)}$ is a $\mathsf{C}$-free cluster and $h_{a+1}\circ L_{a}$
is also a Ritt polynomial, $L_{a}$ is a scaling.

All these notions – preclusterings, precleanups, and cleanups – are invariant
under linear-equivalence. In particular, if $(h,L)$ is a (pre)cleanup of the
preclustering $A$ for _some_ $f$, then is is also a (pre)cleanup of the same
preclustering $A$ of the long decomposition $L\circ h$. We now work towards
existence and something like uniqueness of precleanups of a fixed
preclustering.

######  Lemma 2.105.

Every non-empty preclustering admits a precleanup.

###### Proof.

Take the ordered sequence $a_{r}>a_{r-1}>\ldots>a_{1}>a_{0}=a_{r}-k$ of
consecutive elements of $A$ in one period, including both endponits of the
period. For each $j=0,1,\ldots,r-1$, unwrap the definition of
“$f_{[a_{j+1},a_{j})}$ is a cluster” to get $h_{i}$ for $a_{0}<i\leq a_{r}$,
and linear $B_{j}$ and $E_{j}$. Let $L_{a_{j}}:=E_{j}\circ B_{j-1}$ for $j>0$,
and $L_{a_{0}}:=E_{0}\circ\sigma^{-1}(B_{k})$. For all other $i$ with
$a_{0}<i<a_{r}$, define $L_{i}$ to be identity. These $k$-tuples $\vec{h}$ and
$\vec{L}$ extend uniquely to a $k$-long decomposition$h$ and a $k$-skew
periodic sequence of linear polynomials-linear$L$, and the pair $(h,L)$ is a
precleanup of $f$. ∎

####  2.3.2. $\mathsf{C}$-free decompositions

As long as odd-degree Chebyshev polynomials do not enter the picture, the
preclusterings suffice for the Mahler problem. We now work towards Proposition
2.112 which shows that in this situation we may either reduce to an analysis
of walls (and thus Proposition 2.52) or to an analysis of in-out-degrees (and
thus Proposition 2.99).

######  Definition 2.106.

A long decomposition $f$ is _$\mathsf{C}$ -free_ if all factors $f_{i}$ are
swappable and $\mathsf{C}$-free.

As noted Remark 2.101, $\mathbb{Z}$ is a preclustering of any
$\mathsf{C}$-free long decomposition. The following is an easy special case of
Proposition 2.119 below.

######  Lemma 2.107.

The preclustering $\mathbb{Z}$ of a $\mathsf{C}$-free long decomposition
admits a cleanup.

###### Proof.

Start with a precleanup $(h,L)$ of $(\mathbb{Z},f)$ obtained in Lemma 2.105.

To satisfy requirement (5b) from the definition of cleanup, just absorb the
translation part of $L_{a}$ into the Ritt polynomial $h_{a+1}$ whenever
possible.

Because a $\mathsf{C}$-free long decomposition has no $\mathsf{C}$-clusters,
the remaining requirement (5a) is vacuously satisfied. ∎

######  Lemma 2.108.

Suppose that $(g,M)$ and $(h,L)$ are both cleanups of the same preclustering
$\mathbb{Z}$ of the same $\mathsf{C}$-free long decomposition. Then for each
$i$, $M_{i}$ is a scaling if and only if $L_{i}$ is a scaling.

###### Proof.

Here, we pay the price of lining up the indices of linear factors with the
indices of Ritt swaps, but not with the indices of the factors they naturally
go with. First, replace the long decomposition $L\circ h$ (respectively,
$M\circ g$) by the one whose factors are $h_{i}\circ L_{i-1}$ (respectively,
$g_{i}\circ M_{i-1}$). Each new one is linearly equivalent to the
corresponding old one, via $L$ and $M$, respectively. Thus, if the old ones
were linearly related, then so are the new ones. Let $N$ witness the linear
equivalence of the new ones.

We first show that all $N_{i}$ are scalings. From the definition of linearly
equivalence,

$h_{i}\circ L_{i-1}=N_{i+1}^{-1}\circ g_{i}\circ M_{i-1}\circ N_{i}\text{ .}$

Since $g_{i}$ and $h_{i}$ are $\mathsf{C}$-free Ritt polynomials,
$N_{i+1}^{-1}$ must be a scaling by [8, Theorem 3.15].

If $M_{i-1}$ is a scaling, the right-hand side of the displayed equation is a
(not necessarily monic) Ritt polynomial. Condition (5b) in the definition of
cleanup then forces $L_{i-1}$ to also be a scaling. ∎

The “clean $\mathsf{C}$-free long decompositions” of Section 2.2 are precisely
those $\mathsf{C}$-free long decompositions that admit a cleanup where all
linear factors are scalings. We now work towards showing that every other
$\mathsf{C}$-free long decomposition has a wall.

A $\mathsf{C}$-free long decomposition $f$ has a _prewall at $i$_ if $L_{i}$
is not a scaling in some/every cleanup $(h,L)$ of $(\mathbb{Z},f)$.

This terminology is only used in the next three lemmas, where we show that a
prewall is in fact a wall.

######  Lemma 2.109.

If a $\mathsf{C}$-free long decomposition $f$ has a prewall at $i$, then
$t_{i}\star f$ is not defined.

###### Proof.

Suppose toward contradiction that $(h,L)$ is a cleanup of the clustering
$\mathbb{Z}$ of $f$, $t_{i}\star(L\circ h)$ is defined, and $L_{i}$ is not a
scaling. Then there must be linear polynomial $A$, $B$, and $E$ for which
$(A\circ h_{i+1}\circ L_{i}\circ B^{-1},B\circ h_{i}\circ E)$ is one side of a
basic Ritt identity. Since both $h_{i}$ and $B\circ h_{i}\circ E$ are
$\mathsf{C}$-free Ritt polynomials, $B$ is a scaling by [8, Theorem 3.15].
Since both $h_{i+1}$ and $A\circ h_{i+1}\circ L_{i}\circ B^{-1}$ are
$\mathsf{C}$-free Ritt polynomials $A$ is a scaling by [8, Theorem 3.15]. So
now $h_{i+1}\circ L_{i}$ is a non-monic Ritt polynomial, and by definition of
“cleanup”, $L_{i}$ must be a scaling. ∎

######  Lemma 2.110.

Suppose that $t_{i}\star f$ is defined for a $\mathsf{C}$-free long
decomposition $f$. Then $t_{i}\star f$ has a prewall at $j$ if and only if $f$
does.

###### Proof.

Lemma 2.109 shows that neither $f$ nor $t_{i}\star f$ has a prewall at $i$.
All cleanups in this proof are for the preclustering $\mathbb{Z}$.

We first show that $f$ admits a cleanup $(h,L)$ with
$L_{i}=\operatorname{id}$. By Lemma 2.109, $L_{i}$ is a scaling in any
cleanup. Replacing $L_{i}(x)=:\lambda x$ by identity, $h_{i+1}$ by
$\lambda\ast h_{i+1}$, and $L_{i+1}(x)$ by
$L_{i+1}(\lambda^{-\deg(h_{i+1})}x)$ produces the desired cleanup.

Since $t_{i}\star f$ is defined, there are linear polynomials $A$, $B$, and
$E$ for which $(A\circ h_{i+1}\circ B^{-1},B\circ h_{i}\circ E)$ is one side
of a basic Ritt identity. By [8, Lemma 3.37], there are Ritt polynomials
$g_{i+1}$ and $g_{i}$ for which $(h_{i+1}\circ h_{i}=g_{i+1}\circ g_{i})$ is a
basic Ritt identity.

We finally show that setting $g_{\ell}:=h_{\ell}$ for all other indices $\ell$
produces a cleanup $(g,L)$ of $t_{i}\star f$, which obviously has prewalls in
exactly the same places as $(h,L)$. The only part of the definition of
“cleanup” that does not obviously hold is part (5b) at $(i-1)$: could it be
that $L_{i-1}$ is not a scaling, but $g_{i}\circ L_{i-1}$ is a Ritt
polynomial? We noted in [8, Remark 3.33] that this is not possible. ∎

######  Lemma 2.111.

If a $\mathsf{C}$-free long decomposition $f$ has a prewall at $i$, then
$\epsilon_{p}\star f$ and $\epsilon_{p}^{-1}\star f$ are not defined for any
$p$.

###### Proof.

The hypothesis on $\widetilde{f}$ in the definition of the action
$\epsilon_{p}^{\pm 1}\star f$ (Definition 2.19) produces a cleanup of $f$ with
only scaling linear factors. Hence, for $\epsilon_{p}^{\pm}\star f$ to be
defined, $f$ can have no prewalls. ∎

######  Proposition 2.112.

Every $\mathsf{C}$-free long decomposition $f$ either has a wall, or admits a
cleanup $(h,L)$ where all $L_{i}$ are scalings.

###### Proof.

Since $f$ is $\mathsf{C}$-free, each $f_{i}$ is of the form $A_{i}\circ
h_{i}\circ B_{i}$ where $h_{i}$ is a monic $\mathsf{C}$-free Ritt polynomial
and $A_{i}$ and $B_{i}$ are linear. Let $L_{i}:=B_{i+1}\circ A_{i}$. Then
$(h,L)$ is a precleanup of the preclustering $\mathbb{Z}$ of $f$. To satisfy
requirement (5b) of the definition of cleanup, just absorb the translation
part of $L_{i}$ into the Ritt polynomial $h_{i+1}$ whenever possible,
obtaining a cleanup $(g,M)$ of $f$.

If all $M_{i}$ are scalings, we are done. Otherwise, some $M_{i}$ is not a
scaling, and Lemmas 2.109, 2.110, and 2.111 show that $f$ has a wall at $i$. ∎

This completes the proof of Theorem 1.3 for polynomials admitting
$\mathsf{C}$-free long decompositions: the two cases identified in Proposition
2.112 are handled by Propositions 2.52 and 2.99.

####  2.3.3. Clustering with type $\mathsf{C}$

In this subsection, we analyze the relations between different cleanups of the
same long decomposition with a $\mathsf{C}$ cluster since we already have a
complete solution to the Mahler problem for $\mathsf{C}$ free long
decompositions and the assumption that we have a $\mathsf{C}$ cluster permits
us to to match our present definition of cleanup and what appears in [8].

We first work with different cleanups of the same preclustering and then
analyze the effect of removing unnecessary boundaries.

The operation on cleanups in the following definition is the main way to
obtain one cleanup from another.

######  Definition 2.113.

Given a $k$-long decomposition$f$, its _degree sequence_ $\deg(f)$ is the
$k$-periodic $\mathbb{Z}$-indexed sequence $(\deg(f_{i}))_{i\in\mathbb{Z}}$.

By a _$k\textsf{-scalar}$_ we mean a $k$-skew-periodic $\mathbb{Z}$-indexed
sequence $\lambda=(\lambda_{i})_{i\in\mathbb{Z}}$.

For a $k$-long decomposition$f$ and a $k\textsf{-scalar}$ $\lambda$ we define
$\lambda\ast f$ to be the $k$-long decompositionwhose $i^{\text{th}}$
component is

$(\lambda\ast f)_{i}:=\lambda_{i}^{-\deg f_{i}}f_{i}(\lambda_{i}x)\text{ .}$

For a $k$-periodic $\mathbb{Z}$-indexed sequence $d=(d_{i})_{i\in\mathbb{Z}}$
of positive integers and a $k\textsf{-scalar}$ $\lambda$, we define the
_residue of $\lambda$ at $d$_ to be the $k\textsf{-scalar}$ $\mu$ whose
$i^{\text{th}}$ component is given by

$\mu_{i}:=\lambda_{i+1}^{-1}\lambda_{i}^{d_{i}}\text{ .}$

######  Remark 2.114.

An easy computation verifies that for any $k$-skew periodic sequence of linear
polynomials-linear$L$, $k\textsf{-scalar}$ $\lambda$, and $k$-long
decomposition$f$ with degree sequence $d=\deg(f)$,

$(\lambda\ast(h\circ L))=(\lambda\ast h)\circ(\lambda\ast L)$

and

$(\lambda\ast(L\circ h))=(\lambda^{d}\ast L)\circ(\lambda\ast h)\text{ .}$

######  Remark 2.115.

If $\mu$ is the residue of the $k\textsf{-scalar}$ $\lambda$ at the degree
sequence $d=\deg(f)$ of the $k$-long decomposition$f$, then
$\mu\cdot(\lambda\ast f)$ is linearly equivalent to $f$ via the $k$-skew
periodic sequence of linear polynomials-linear$L$ of scalings by $\lambda$
(_i.e._ , $L_{i}(x)=\lambda_{i}x$).

######  Remark 2.116.

We may use these operations to get new (pre)cleanups of the same $f$. Indeed,

  * •

for a translation $L_{i}$, the resulting $\lambda_{i}\ast L_{i}$ is also a
translation;

  * •

for a monic Ritt polynomial $h_{i}$, the resulting $\lambda_{i}\ast h_{i}$ is
also a monic Ritt polynomial; and

  * •

for a Chebyshev polynomial $h_{i}$, the resulting $\lambda_{i}\ast h_{i}$ is
the same Chebyshev polynomial if and only if $\lambda_{i}=\pm 1$.

Our next Lemma 2.117 on the relation between $(h,L)$ and $\lambda\ast(h,L)$
produces a cleanup from a precleanup. Corollary 2.118 then shows how this
operation could connect two cleanups. Proposition 2.122 proves that any
cleanup can be obtained (almost) from any other by this operation.

######  Lemma 2.117.

Suppose that $(h,L)$ is a precleanup of a preclustering $A$ of $f:=L\circ h$.
We assume that $(f,A)$ has a $\mathsf{C}$ cluster.

Fix a $k\textsf{-scalar}$ $\lambda$ and let $\mu$ be the residue of $\lambda$
at the degree sequence $d$ of $h$.
Let $\lambda^{d}$ be the $k\textsf{-scalar}$ defined by
$(\lambda^{d})_{i}:=\lambda_{i}^{d_{i}}$; let $g:=\lambda\ast h$; and let
$M:=\mu\cdot(\lambda^{d}\ast L)$.

Then $(g,M)$ is also a precleanup of $f$ if and only if $\mu_{i}=1$ for
$i\not\in A$ and $\lambda_{i}=\pm 1$ for $i$ inside $\mathsf{C}$ clusters
(that is, when $f_{[b,a)}$ is a $\mathsf{C}$ cluster of $(f,A)$, and $b\geq
i>a$).

When $(A,f)$ has a $\mathsf{C}$ cluster, then condition (5a) in the definition
of cleanup is satisfied by $(g,M)$ if and only if $L_{a}(x)=\mu_{a}^{-1}x+C$
whenever $f_{[b,a)}$ is a $\mathsf{C}$-free cluster of $(f,A)$.
In particular, $\mu_{a}=1$ for all such $a$ if both $(h,L)$ and $(g,M)$
satisfy (5a).

Condition (5b) is satisfied by $(h,L)$ if and only if that condition is
satisfied by $(g,M)$.

###### Proof.

Let us work through the definition of a precleanup of $(L\circ h)$.

  1. (1)

Unwrapping definitions, we get

$M\circ g=\mu\cdot(\lambda^{d}\ast L)\circ(\lambda\ast
h)=\mu\cdot\lambda\ast(L\circ h),$

which is linearly equivalent to $(L\circ h)$ by Remark 2.115.

  2. (2)

For $i\notin A$, we know that $L_{i}$ is identity, and we need
$M_{i}=\mu_{i}\cdot(\lambda_{i}^{d_{i}})\ast L_{i}$ to be identity. Since
$\mu_{i}\cdot(\alpha\ast\operatorname{id})=\mu_{i}\cdot\operatorname{id}$ for
any $\alpha$, we must have $\mu_{i}=1$.

  3. (3)

For $i$ inside $\mathsf{C}$-clusters, we know that $h_{i}$ is a Chebyshev
polynomial, and we need $g_{i}:=\lambda_{i}\ast h_{i}$ to be a Chebyshev
polynomial. This forces $\lambda_{i}=\pm 1$.

  4. (4)

For $i$ inside $\mathsf{C}$-free clusters, we get no extra requirements since
$\alpha\ast P$ is a monic Ritt polynomial whenever $P$ is.

We up the stakes asking for $(g,M)$ to be a cleanup, without requiring $(h,L)$
to be one.

  1. (5a)

When $a$ is the right boundary of a $\mathsf{C}$-free cluster, we need
$M_{a}=\mu_{a}\cdot(\lambda_{a}\ast L_{a})$ to be a translation. If
$L_{a}(x)=Bx+C$, then $(\lambda_{a}\ast L_{a})(x)=Bx+C^{\prime}$, so we need
$\mu_{a}=B^{-1}$. If $(h,L)$ also satisfies (5a) so that $L_{a}$ is a
translation, this forces $\mu_{a}=1$.

  2. (5b)

Still at the right boundary $a$ of a $\mathsf{C}$-free cluster, suppose that
$g_{a+1}\circ M_{a}$ is a Ritt polynomial. Unwrapping the defintions of $g$
and $M$ gives

$g_{a+1}\circ M_{a}=(\lambda_{a+1}\ast
h_{a+1})\circ\mu_{a}\cdot(\lambda_{a}^{d_{a}}\ast L_{a})$ $g_{a+1}\circ
M_{a}=(\cdot\lambda_{a+1}^{-d_{a+1}})\circ
h_{a+1}\circ(\cdot\lambda_{a+1})\circ(\cdot\mu_{a})\circ(\cdot\lambda_{a}^{-d_{a}})\circ
L_{a}\circ(\cdot\lambda_{a}^{d_{a}})$

By definition of residue, the whole middle scaling by
$(\lambda_{a+1}\mu_{a}\lambda_{a}^{-d_{a}})$ is identity, so

$(g_{a+1}\circ M_{a})(x)=\lambda_{a+1}^{-d_{a+1}}\cdot(h_{a+1}\circ
L_{a})(\lambda_{a}^{d_{a}}x).$

Now $h_{a+1}\circ L_{a}$ is linearly-related via scalings to the Ritt
polynomial $g_{a+1}\circ M_{a}$, so $h_{a+1}\circ L_{a}$ is itself a Ritt
polynomial.

On the other hand, in order to have
$M_{a}=\mu_{a}\cdot(\lambda_{a}^{d_{a}}\ast L_{a})$ be a scaling, we need
$L_{a}$ to be a scaling. So, if $(h,L)$ is a cleanup, and $(g,M)$ satisfies
(5a), then $(g,M)$ automatically satisfies (5b). And if $(h,L)$ satisfies (5a)
but not (5b), and $(g,M)$ satisfies (5a), then $(g,M)$ cannot satisfy (5b).

∎

The following corollary is a precise version of [8, Remark 4.9]. When all
clusters are $\mathsf{C}$-free, Corollary 2.118 does not apply. This non-
uniqueness is the price of working with skew-linear-equivalence rather than
linear equivalence (in the sense of [8, Definitions 2.39 and 2.58]). This
issue comes up informally in the proof of [8, Lemma 6.11(6)].

######  Corollary 2.118.

With the setup in Lemma 2.117, suppose further that both $(h,L)$ and $(g,M)$
are cleanups of $(A,f)$. Then, $\lambda_{i}=\pm 1$ for all $i$, and
$\mu_{i}=1$ unless $f_{[j,i)}$ is a $\mathsf{C}$ cluster of $(A,f)$ for some
$j\in A$.

###### Proof.

Suppose toward contradiction that $\lambda_{j+1}\neq\pm 1$. From condition (3)
of the definition of preclustering, it follows that $f_{j+1}$ is in a
$\mathsf{C}$-free cluster of $(A,f)$. Take the largest $b\in A$ with $b<j$
such that $f_{[b,a)}$ is a $\mathsf{C}$-cluster of $(A,f)$ for some $a\in A$.
Now, for every $i=b,b+1,\ldots j$, either $i\notin A$ or $i\in A$ is the right
boundary of a $\mathsf{C}$-free cluster; either way, $\mu_{i}=1$ for all these
$i$. To show that $\lambda_{i}=\pm 1$ for $i=b,b+1,\ldots j+1$, induct on
$i-b$. The base case $i=b$ follows from condition (3) because $f_{b}$ is
inside a $\mathsf{C}$-cluster. For the induction step, assume that
$\lambda_{i}=\pm 1$; recall that
$\lambda_{i+1}=\lambda_{i}^{d_{i}}\mu_{i}^{-1}$ by definition of “residue”;
and that we have already showen that $\mu_{i}=1$ for $i=b,b+1,\ldots j$. So,
$\lambda_{i+1}=(\pm 1)^{d_{i}}(1)^{-1}=\pm 1$. The last induction step we can
carry out is from $j$ to $j+1$, obtaining the desired contradiction. ∎

######  Proposition 2.119.

Every non-empty preclustering admits a cleanup.

The following proof translates the explanation from [8, Remark 4.4] and the
details from the proofs of [8, Lemmas 4.6, 4.8, and 6.11(6)] to our new
setting with long decompositions.

###### Proof.

Fix a non-empty preclustering $A$ of a $k$-long decomposition$f$. Start with a
precleanup $(h,L)$ of $(A,f)$ obtained in Lemma 2.105. To satisfy requirement
(5b) from the definition of cleanup, just absorb the translation part of
$L_{a}$ into the Ritt polynomial $h_{a+1}$ whenever possible.

Because the remaining requirement (5a) is relevant only when $(A,f)$ has a
$\mathsf{C}$-cluster, for the rest of this proof, we now assume that it does.
We will show how to use Lemma 2.117 to satisfy this requirement.

Here are all the conditions on $\mu$ and $\lambda$ that we need.

  * •

For $i\not\in A$, we need $\mu_{i}=1$.

  * •

For $i$ inside $\mathsf{C}$-clusters, we also need $\lambda_{i}=\pm 1$.

  * •

When $a$ is the right boundary of a $\mathsf{C}$-free cluster and
$L_{a}(x)=Bx+C$, we need $\mu_{a}=B^{-1}$.

For each $\mathsf{C}$-cluster $f_{[b,a)}$, we have very tight requirements on
$\lambda_{i}$ for $a<i\leq b$, but no requirements on $\mu_{a}$. So we can let
$\mu_{a}$ absorb the unwanted scalings coming from $\lambda_{a}$, set all
those tightly controlled $\lambda_{i}:=1$, and restart the process at $b$.
This is where the “non-empty” assumption is used.

∎

Empty preclusterings are important as clusterings of long decompositions of
certain polynomials. However, these polynomials do not require the clustering
analysis for the solution of our Mahler problem. The following proposition
shows such polynomials are either subject to Proposition 2.112 or essentially
Chebyshev polynomials and thus exceptional.

######  Proposition 2.120.

If the empty set is a preclustering of $f$, then one of the following
alternatives holds.

  * •

$f$ is linearly equivalent to a $k$-long decompositionall of whose factors are
Ritt polynomials or

  * •

$f$ is linearly equivalent to a $k$-long decompositionall of whose factors are
plus or minus Chebyshev polynomials.

###### Proof.

If the empty set is a preclustering of $f$, then so is $A:=k\mathbb{Z}$.
Applying Proposition 2.119 to it produces $h$ and $L$ with no non-trivial
linear factors except for $L_{kn}$. Since the empty set is a preclustering of
$f$, the concatenation of two periods is also a cluster. For a
$\mathsf{C}$-free cluster, [8, Lemma 4.13] shows that $L_{0}$ is a scaling,
and we are done. For a $\mathsf{C}$-cluster, [8, Lemma 4.14] shows that
$L_{0}$ is identity or the scaling by $-1$. ∎

######  Remark 2.121.

According to Proposition 2.120 if $(\varnothing,f)$ has a $\mathsf{C}$
cluster, then $f$ is a long decomposition of an exceptional polynomial.

######  Proposition 2.122.

Suppose that two pairs of sequences, $(h,L)$ and $(g,M)$, are both cleanups of
the same non-empty preclustering $A$ of the same $k$-long decomposition$f$. As
is standard in this subsection, we assume that $(A,f)$ has a $\mathsf{C}$
cluster. Then $(h,L)$ may be obtained from $(g,M)$ by first forming
$\lambda\ast(g,M)$ for some $k\textsf{-scalar}$ $\lambda$ and then inserting
translations to the right of type $\mathsf{A}$ Ritt polynomials in
$\lambda\ast(g,M)$.

More precisely, there is a $k\textsf{-scalar}$ $\lambda$ such that $(h,L)$
comes from $(\widetilde{g},\widetilde{M}):=\lambda\ast(g,M)$ in the following
way. For each $a\in A$ where $\widetilde{g}_{a+1}$ is a type A Ritt polynomial
(see Definition 3.8 in [8]) and $\widetilde{M}_{a}$ is not a scaling, there is
a translation $T_{a}$ such that $h_{a+1}=\widetilde{g}_{a+1}\circ T_{a}$ and
$L_{a}=T_{a}^{-1}\widetilde{M}_{a}$. Since both $\widetilde{g}_{a+1}$ and
$h_{a+1}$ are Ritt polynomials, there are only finitely many such translations
for each fixed $a$.

Furthermore, $\lambda$ satisfies the conclusion of Corollary 2.118:
$\lambda_{i}=\pm 1$ for all $i$ and $\mu_{i}=1$ inside clusters of $A$ and to
the right of $\mathsf{C}$-free clusters. Here, $\mu$ is the residue of
$\lambda$ at the degree sequence $h$.

###### Proof.

Since $f$ only appears in these definitions up to linear-equivalence, we may
assume that $f=L\circ h$. Fix $b,a\in A$ such that $f_{[b,a)}$ is a
$\mathsf{C}$ cluster of $(A,f)$.

Since $(g,M)$ is also a cleanup of $L\circ h$, some $k$-skew periodic sequence
of linear polynomials-linear$N$ witnesses that $M\circ g$ is linearly
equivalent to $L\circ h$, and then

$(L_{a+k}\circ h_{a+k},L_{a+k-1}\circ h_{a+k-1},\ldots,L_{a+2}\circ
h_{a+2},L_{a+1}\circ h_{a+1})$

and

$(N_{a+k+1}^{-1}\circ M_{a+k}\circ g_{a+k},M_{a+k-1}\circ
g_{a+k-1},\ldots,M_{a+2}\circ g_{a+2},M_{a+1}\circ g_{a+1}\circ N_{a+1})$

are linearly equivalent in the sense of [8, Definition 2.49], and we have two
almost-cleanups of them, again in the sense of [8, Definition 4.3]:

$(h_{a+k},\ldots h_{a+1};L_{a+k},\ldots,L_{a+1},\operatorname{id}))$

and

$(g_{a+k},\ldots g_{a+1};(N_{a+k+1}^{-1}\circ
M_{a+k}),M_{a+k-1},\ldots,M_{a+2},M_{a+1},N_{a+1}).$

Since $f_{[b,a)}$ is a $\mathsf{C}$ cluster, there are no further requirements
on the linear factors at $k$ and at $0$ in [8, Definition 4.3], so these are
actual cleanups in the sense of [8, Definition 4.3]. By [8, Lemma 4.10], these
can only differ by scalings of $\pm 1$ and by translations to the right of
$\mathsf{C}$-free clusters. In particular, since $N_{a+1}$ is not to the right
of a $\mathsf{C}$-free cluster, it must be a scaling by $\pm 1$; and so
$N_{a+k+1}=\sigma(N_{a+1})$ is also a scaling by $\pm 1$. So, the original
long cleanups $(h,L)$ and $(g,M)$ can only differ by scalings of $\pm 1$ and
by translations to the right of $\mathsf{C}$-free clusters, as required. ∎

We now move on to comparing cleanups of different preclusterings. Lemma 2.123
builds on Remark 2.102 tracking what happens to cleanups when a preclustering
is refined to have more, smaller clusters per period. The following two lemmas
are partial converses of Lemma 2.123, used to recognize when a given
preclustering is a refinement of another. Lemma 2.124 is essentially [8, Lemma
4.13] about fusing two adjacent $\mathsf{C}$-free clusters. Lemma 2.125 is a
better version of [8, Lemma 4.14] made possible by our Corollary 2.118 which
is a better version of [8, Remark 4.9].

######  Lemma 2.123.

Suppose that $(h,L)$ is a precleanup of a preclustering $A$ of a $k$-long
decomposition$f$, and $B\supset A$ is also a preclustering of the same $f$.
Then $(h,L)$ is _not_ a precleanup of $(B,f)$ if and only if

  * $({\dagger})$

there are some $b\geq i>a$ for which $f_{[b,a)}$ is a $\mathsf{C}$ cluster of
$(A,f)$, and $f_{i}$ is quadratic, and both $i$ and $(i-1)$ are in $B$.

If $(h,L)$ is a cleanup of $(A,f)$ and $({\dagger})$ does not hold, then
$(h,L)$ is also a cleanup of $(B,f)$.

###### Proof.

Part (1) of the definition cleanup only depends on $h$, $L$, and $f$, not on
$B$. Part (2) of that definition is strictly easier to satisfy for a bigger
$B$. For parts (3) and (4), it is necessary and sufficient to have each factor
$f_{i}$ in the same type of cluster in $(A,f)$ and $(B,f)$. By part (2) of
Remark 2.102, this fails if and only if $B$ rips a single quadratic factor off
a $\mathsf{C}$ cluster of $A$, which is exactly the situation that
$({\dagger})$ describes more precisely. Parts (5a) and (5b) of the definition
of cleanup are again strictly easier: without $({\dagger})$, every “cluster
boundary of $(B,f)$ to the right of a $\mathsf{C}$-free cluster” is also a
“cluster boundary of $(A,f)$ to the right of a $\mathsf{C}$-free cluster.” ∎

######  Lemma 2.124.

Suppose that $(h,L)$ is a cleanup of a non-empty preclustering $A$ of
$f:=L\circ h$ with a $\mathsf{C}$ cluster. Suppose that $c>b>a$ are
consecutive elements of $A$; that $f_{[c,b)}$ and $f_{[b,a)}$ are
$\mathsf{C}$-free clusters; and that their concatenation $f_{[c,a)}$ is also a
cluster. Then $L_{b}$ is identity, and
$B:=A\smallsetminus\\{b+kn:n\in\mathbb{Z}\\}$ is also a preclustering of
$L\circ h$, and $(h,L)$ is also a cleanup of $(B,L\circ h)$.

###### Proof.

To show that $L_{b}$ is identity, we apply [8, Lemma 4.13] to a suitable
finite chunk of these infinite objects. One period is not a long enough chunk,
as it might not contain all three of $a$, $b$, and $c$. Since $A$ is
$k$-periodic, $b\leq a+k$ and $c\leq b+k$, so $c\leq a+2k$, so two periods is
enough.

Let $A^{\prime}:=\\{x-a:x\in A\mbox{ and }a\leq x\leq a+2k\\}$. Now
$((h_{a+2k},\ldots,h_{a+1}),(L_{a+2k},\ldots,L_{a}))$ is a cleanup in the
sense of [8, Definition 4.3] of the preclustering, again in the sense of [8],
$A^{\prime}$ of the decomposition $(f_{a+2k},\ldots,f_{a+1})$.

Applying [8, Lemma 4.13] from to these shows that $L_{b}$ is identity. Since
$A$ is $k$-periodic, it follows that $L_{b+kn}$ are all identity. The rest of
the lemma now follows easily. Note that $B$ is non-empty because $(A,f)$ has
both a $\mathsf{C}$ cluster and a $\mathsf{C}$-free cluster. Writing out the
definition verifies that it is a preclustering. ∎

######  Lemma 2.125.

Suppose that $(h,L)$ is a cleanup of a non-empty preclustering $A$ of
$f:=L\circ h$. Suppose that $c>b>a$ are consecutive elements of $A$; that
$f_{[c,b)}$ and $f_{[b,a)}$ are $\mathsf{C}$ clusters; and that their
concatenation $f_{[c,a)}$ is also a cluster.

Then $L_{b}(x)=\pm x$ and $B:=A\smallsetminus\\{b+kn:n\in\mathbb{Z}\\}$ is
also a preclustering of $L\circ h$. Now $(h,L)$ is also a cleanup of $(B,f)$
if and only if $L_{b}$ is identity.

In any case, any cleanup of $(B,f)$ is also a cleanup of $(A,f)$; and one can
be obtained from $(h,L)$ via Lemma 2.117 as long as $(B,f)$ admits any
cleanups.

###### Proof.

Exactly as in the proof of the last lemma, we apply [8, Lemma 4.14] to two
periods of $(A,f)$ to see that $L_{b}(x)=\pm x$.

Case 1: Suppose that $B$ is empty.

If $L_{b}$ is identity, we have that all $h_{i}$ are Chebyshevs with at least
one of odd degree, and all $L_{i}$ identity, so for any $e\geq d+k$, we have
$f_{[e,d)}=h_{[e,d)}$ is a Chebyshev polynomial whose degree is not a power of
two. So $B$ is a preclustering and $(h,L)$ is a cleanup of it.

If $L_{b}$ is not identity and some $f_{i}$ has degree 2, let $d>b$ be the
least such $i$. Let $\lambda_{i}:=-1$ for $i\equiv b,b+1,\ldots d\pmod{k}$ and
$\lambda_{i}=1$ for other $i$. Use this $\lambda$ to get a cleanup $(g,M)$ of
$(A,f)$ via Lemma 2.117, with $M_{b}$ identity, so all $M_{i}$ identity.
Again, $B$ is a preclustering and $(g,M)$ is a cleanup of it.

If $L_{b}$ is not identity and all $f_{i}$ have odd degree, it is easy to see
that $f_{[e,d)}$ is linearly related to an odd-degree Chebyshev polynomial for
any $e>d$, so $B$ is a preclustering, but it is the exception in Proposition
2.120 admitting no cleanup.

Case 2: Suppose that $B$ is not empty.

If $L_{b}$ is identity, writing out definitions verifies that $B$ is a
preclustering and $(h,L)$ is a cleanup of it.

Otherwise, Lemma 2.117 with an appropriate $k\textsf{-scalar}$ $\lambda$ will
produce another cleanup $(g,M)$ of $(A,f)$ with $M_{b}$ identity, reducing to
the previous sentence.

More precisely, let $d$ be the degree sequence of $h$ and define $\lambda$ by
starting with $\lambda_{b}=-1$, proceeding inductively with
$\lambda_{i+1}=\lambda_{i}^{d_{i}}$ until $\lambda_{a+k}$ is defined, and
filling the rest of the period with $\lambda_{i}=1$. This makes sense because
$b<a+k$ because $B$ is non-empty. The residue of this $\lambda$ at the degree
sequence of $h$ is $-1$ at $b+nk$ and $\pm 1$ at $a+k+nk$ and $1$ everywhere
else. The first assures that $M_{b}$ is identity, and the second is ok because
$a+nk$ are right boundaries of $\mathsf{C}$ clusters. ∎

####  2.3.4. Gates and clusterings

Cluster boundaries give rise to the combinatorial invariants we use to solve
the Mahler problem for polynomials all of whose factors are swappable but not
all of whose factors are $\mathsf{C}$-free. However, cluster boundaries of a
preclustering are very far from an invariant, as we can introduce extra
boundaries almost at will. In this subsection, we show that a preclustering
with a minimal number of clusters, called a _clustering_ , is almost an
invariant of the long decompositions.

In Lemma 2.143 we show that two such clusterings only differ by assigning what
we call “wandering quadratic” factors (see Definition 2.157) to different
clusters. With that result, the boundary set (Definition 2.135) becomes the
desired combinatorial invariant (Theorem 2.145).

The intuitive definition of clustering in terms of the minimal number of
clusters turns out to be equivalent to two more useful but less intuitive
definitions, one in terms of the linear factors in a cleanup and the other in
terms of two particular ways to reduce the number of clusters. We take the
first one as our definition (Definition 2.128), and obtain the second (Lemma
2.131) as a consequence. In Lemmas 2.133 and 2.134, we describe the only way
to obtain one clustering from another by moving a wandering quadratic; we then
define the combinatorial invariant (Definition 2.135) that we use in our
proofs. The rest of the section consists of the tedious verification that it
is indeed invariant: that any two clusterings come from each other via the
operations described in Lemmas 2.133 and 2.134.

Much of the technical work of this section is closely related to [8, Section
4], but the overall approach is substantially improved. With long
decompositions, we avoid the artificial cluster boundary at $k$ that
unnecessarily complicated [8]. With Definition 2.135, we explicitly identify
the combinatorial invariant that remained implicit in [8].

######  Definition 2.126.

Fix a cleanup $(h,L)$ of a non-empty preclustering $A$ of $f$, and fix
consecutive elements $c>b>a$ of $A$. For the duration of this definition,

  * -

the _left cluster_ is $f_{[c,b)}$; and

  * -

the _right cluster_ is $f_{[b,a)}$; and

  * -

the _linear factor $L$_ is $L_{b}$.

We define “$(h,L,A)$ has a  gate at $b$” exactly as in [8, Definition 4.15],
where the blank  is one of “left-to-right”, “right-to-left”, “one-way”, or
“two-way”.

More formally,
$((h_{c},\ldots,h_{a+1}),(\operatorname{id},L_{c-1},\ldots,L_{a}))$ is a
cleanup in the sense of [8, Definition 4.2] of the preclustering
$(c-a,b-a,a-a)$ in the sense of [8] of the decomposition $(h_{c}\circ
L_{c-1},\ldots,h_{a+1}\circ L_{a})$. Whenever this has a left-to-right
(respectively, right-to-left, one-way, two-way) gate at $1$ in the sense of
[8, Definition 4.15], we now say that $(h,L,A)$ has a left-to-right
(respectively, right-to-left, one-way, two-way) gate at $b$.

The next lemma justifies the terminology “$(A,f)$ has a gate at $b$”, explains
the purpose of gates, and notes that two-way gates are superfluous.

######  Lemma 2.127.

Two cleanups of the same preclustering of the same decomposition have the same
kinds of gates in the same places. (Compare with [8, Lemma 4.17(1)].)

The concatenation of a cluster $f_{[b,a)}$ of $(A,f)$ and an adjacent
quadratic factor $f_{a}$ (respectively, $f_{b+1}$) is a cluster if and only if
$(A,f)$ has a right-to-left gate at $a$ (respectively, left-to-right gate at
$b$). The clusters $f_{[b,a)}$ and $f_{[b,a-1)}$ (respectively, $f_{[b,a)}$
and $f_{[b+1,a)}$) are of the same kind, $\mathsf{C}$ or $\mathsf{C}$-free.
(Compare with [8, Remark 4.20].)

If $c>b>a$ are consecutive elements of $A$ and $(A,f)$ has a two-way gate at
$b$, then the two clusters $f_{[c,b)}$ and $f_{[b,a)}$ are of the same kind
(both $\mathsf{C}$ or both $\mathsf{C}$-free), and their concatenation
$f_{[c,a)}$ is also a cluster. (Compare with [8, Lemma 4.16].)

###### Proof.

The first statement follows immediately from comparing [8, Remark 3.14] with
Proposition 2.122 here. The second and third statements are immediate
consequences of [8, Remark 3.14]. ∎

Beware that when the preclustering has only one cluster per period, the
concatenations in the last lemma are not contained in one period, and so are
not clusters of any nonempty preclustering of $f$.

With the following definition we introduce the notion a fake gate. Morally,
these identify cluster boundaries which can be removed. Parts (2) and (3)
below are closely related to the fake wandering quadratics from [8, Definition
4.19].

######  Definition 2.128.

Fix a non-empty preclustering $A$ of $f$, and fix consecutive elements $c>b>a$
of $A$. The gate of $(A,f)$ at $b$ is _fake_ if one of the following holds:

  1. (1)

The gate is two-way.

  2. (2)

The gate is left-to-right, $c=b+1$, and $f_{b+1}$ is quadratic.

  3. (3)

The gate is right-to-left, $b=a+1$, and $f_{a+1}$ is quadratic.

  4. (4)

The gate is left-to-right, $c=b+2$, both $f_{b+2}$ and $f_{b+1}$ are
quadratic, and $(A,f)$ has a right-to-left gate at $c$.

  5. (5)

The gate is right-to-left, $b=a+2$, both $f_{a+2}$ and $f_{a+1}$ are quadratic
and $(A,f)$ has a left-to-right gate at $a$.

A _clustering_ is a preclustering with no fake gates.

Fakeness of gates is defined entirely in terms of the degrees of the factors
$f_{i}$ and gates. The degrees of factors are a property of the $k$-long
decompositionalone, independent of the preclustering $A$ and cleanup. The
gates are a property of the $k$-long decompositionand the preclustering, still
independent of cleanup, by the first part of Lemma 2.127. So the fakeness of
gates again only depends on $f$ and $A$ and does not depend on the choice of
cleanup; and so being a clustering is a property of $(A,f)$, independent of
cleanup.

######  Lemma 2.129.

If a preclustering $A$ of $f$ has a fake gate, then $f$ admits another
preclustering $B$ with fewer cluster boundaries per period, that is,
with $|B\cap\\{1,2,\ldots,k\\}|<|A\cap\\{1,2,\ldots,k\\}|$.

###### Proof.

Suppose $c>b>a$ are consecutive elements of $A$ and $(A,f)$ has a fake gate at
$b$.

For (1), by the last part of Lemma 2.127 and one of Lemmas 2.124 or 2.125,
$B:=A\smallsetminus\\{b+nk:n\in\mathbb{Z}\\}$ is another preclustering of $f$.

For (2) and (3), by the second part of Lemma 2.127, the same $B$ obviously
works as long as it is not empty. If $B$ is empty, then $k=1$ and
$A=\mathbb{Z}$ and all factors of $f$ are quadratic. Then all clusters of
$(A,f)$ are $\mathsf{C}$-free, so a gate between two of them must be a two-way
gate, so $f$ is linearly equivalent to $h$ where every $h_{i}(x)=u_{i}x^{2}$
for some scalar $u_{i}$. The empty set is obviously a preclustering of $h$,
and so also of $f$.

For (4), consider

$B:=(A\smallsetminus[\\{b+nk:n\in\mathbb{Z}\\}\cup\\{c+nk:n\in\mathbb{Z}\\}])\cup\\{b+1+nk:n\in\mathbb{Z}\\}.$

By the second part of Lemma 2.127, this $B$ is another preclustering of $f$.
As long as $b$ and $c=b+2$ are not the same modulo $k$, this $B$ has fewer
cluster boundaries per period than $A$: two were removed and one added back.
Otherwise, $k=2$ and each cluster of $(A,f)$ consists of two quadriatic
factors, so all clusters of $(A,f)$ are $\mathsf{C}$-free clusters, so the
gate at $b$ must be a two-way gate, and just as for (2) and (3) above, the
empty set is a preclustering of $f$.

The proof for (5) is identical to the one for (4). ∎

The next Corollary is the analogue of [8, Lemma 6.11(4)].

######  Corollary 2.130.

If all factors of a $k$-long decomposition$f$ are swappable, then $f$ admits a
clustering.

###### Proof.

Start with the preclustering $\mathbb{Z}$ of $f$ from Remark 2.101, and induct
on the number of cluster boundaries per period, using Lemma 2.129 to decrease
it as long as there are fake gates. ∎

We can now complete what we started with Lemmas 2.124 and 2.125.

######  Lemma 2.131.

The concatenation of two adjacent clusters of a clustering is never a cluster.

More precisely, fix consecutive elements $c>b>a$ of a preclustering $A$ of
$f$, and suppose that the concatenation $f_{[c,a)}$ of the two adjacent
clusters $f_{[c,b)}$ and $f_{[b,a)}$ is itself a cluster. Then $A$ has a gate
at $b$, and this gate satisfies one of Conditions (1), (2), or (3) in
Definition 2.128 of “fake gates”.

###### Proof.

If the clusters $f_{[c,b)}$ and $f_{[b,a)}$ are of the same kind ($\mathsf{C}$
or $\mathsf{C}$-free), then Lemmas 2.124 and 2.125 show that $A$ has a two-way
gate at $b$.

Consider now the case that these clusters are of different kinds. Since one of
$f_{[c,b)}$ and $f_{[b,a)}$ is a $\mathsf{C}$ cluster, one of the factors
$f_{i}$ is an odd-degree Chebyshev polynomial, so the whole $f_{[c,a)}$ must
be a $\mathsf{C}$ cluster. By Remark 2.102, the other cluster must consist of
a single quadratic factor. The second part of Lemma 2.127 now verifies
condition (2) or (3) in the definition of “fake gates”. ∎

We can now connect our clusterings with those in [8]. The following looks much
like Remark 2.103, except that “pre” is gone from “preclusterings”.

######  Remark 2.132.

These observations are again related to parts of [8, Lemma 6.11].

  1. (1)

If $A$ is a clustering of $f$, and $0\in A$, then $A\cap\\{0,1,\ldots k\\}$ is
a clustering of $(f_{k},\ldots f_{1})$ in the sense of [8, Definition 4.26].
Lemma 2.131 verifies the first part of the definition; and [8, Remark 4.27]
connects the second part of the definition to parts (4) and (5) in our
definition of “fake gates”.

  2. (2)

More generally, for any $a\in A$, the tuple $A\cap\\{a,a+1,\ldots a+k\\}$ is a
clustering of the decomposition $(f_{a+k},\ldots f_{a+1})$, in the sense of
[8, Definition 4.26].

  3. (3)

Converses of these may fail: the cluster boundary at $0$ and $k$ required in
[8, Definition 4.26] may not be right for the long decomposition.

So far in this section we have identified two ways of getting a new
preclustering from an old one: fusing two clusters (in each period) and
removing the boundary between them from $A$; and moving a quadratic factor
from one cluster to the next, through a gate in the correct direction. The
next two results examine this second operation. Each time, we have to
separately consider the special case of one cluster boundary per period. Empty
preclusterings are irrelevant to this story. The extreme case $k=1$ is also
irrelevant to this story.

The next two results characterize the essential non-uniqueness of clusterings:
a quadratic factor can cross through a gate from one cluster to another. The
rest of this section is devoted to showing that this is all that can happen,
and that this can only happen once at any particular gate.

######  Lemma 2.133.

Fix a non-empty preclustering $A$ of $f$ and consecutive elements $c>b>a$ of
$A$.

Part 1. Suppose that $b+1\notin A$, and $(A,f)$ has a one-way left-to-right
gate at $b$, and $f_{b+1}$ is quadratic. Let $\alpha:A\rightarrow\mathbb{Z}$
be defined by

$\alpha(i):=\begin{cases}i+1&\mbox{if }i\equiv b\pmod{k}\\\ i&\mbox{otherwise.
}\end{cases}$

Then $B:=\operatorname{range}(\alpha)$ is another preclustering of $f$.

Furthermore, for all adjacent $d>e$ in $A$, the cluster $f_{[d,e)}$ of $(A,f)$
and the cluster $f_{[\alpha(d),\alpha(e))}$ of $(B,f)$ are of the same kind
($\mathsf{C}$ or $\mathsf{C}$-free).

Further yet, for all $e\in A$ with $e\not\equiv b\pmod{k}$, the gate of
$(A,f)$ at $e$ and the gate of $(B,f)$ at $\alpha(e)$ are of the same kind
(none, one-way left-to-right, one-way right-to-left, or two-way).

Finally, the direction of the moved gate is changed: $B$ has a one-way right-
to-left gate at $b+1=\alpha(b)$.

Part 2. The reverse is also true: If $b-1\notin A$, and $(A,f)$ has a one-way
right-to-left gate at $b$, and $f_{b}$ is quadratic; then
$\alpha:A\rightarrow\mathbb{Z}$ defined by

$\alpha(i):=\begin{cases}i-1&\mbox{if }i\equiv b\pmod{k}\\\ i&\mbox{otherwise
}\end{cases}$

produces another preclustering $B:=\operatorname{range}(\alpha)$ of $f$.

Again, the direction of the moved gate is changed: $B$ has a one-way left-to-
right gate at $b-1=\alpha(b)$.

Again, all other gates, and all cluster types are unchanged, exactly as in the
two “furthermore”s in Part 1.

Our proof of this lemma is rather long, but routine.

###### Proof.

We prove Part 1; the proof of Part 2 is identical and left to the reader.

Since $b+1\notin A$, this $\alpha$ respects order and $k$-periodicity. Since
$b\in A$ and $b+1\notin A$ and $A$ is $k$-periodic, it follows that $k\neq 1$.
Setting

$C:=A\smallsetminus(b+k\mathbb{Z})$

we get

$A=C\cup(b+k\mathbb{Z})\mbox{ and }B=C\cup(b+1+k\mathbb{Z}).$

To show that $B$ is a preclustering and that $\alpha$ respects cluster types,
we only need to consider alleged clusters of $B$ with the new boundary $b+1$.

Case 1. If $A$ has more than one cluster boundary per period, these new
clusters are $f_{[c,b+1)}$ and $f_{[b+1,a)}$, corresponding to the clusters
$f_{[c,b)}$ and $f_{[b,a)}$ of $A$. Since $c\in A$ and $b+1\notin A$, we know
that $c\neq b+1$, so $f_{[c,b+1)}$ is not empty. By the second statement in
Lemma 2.127, $f_{[b+1,a)}$ is a cluster. Now $f_{[c,b+1)}$ is the result of
removing the _quadratic_ factor $f_{b+1}$ from the cluster $f_{[c,b)}$, so by
part (3) of Remark 2.102 it is a cluster, of the same kind as $f_{[c,b)}$. By
the same part (3) of Remark 2.102, the cluster $f_{[b,a)}$ is of the same kind
as $f_{[b+1,a)}$.

Case 2. If $A$ has one cluster boundary per period, $A=b+k\mathbb{Z}$ and
$a=b-k$ and $B=b+1+k\mathbb{Z}$. By the second statement in Lemma 2.127,
$f_{[b+1,a)}$ is a cluster; by part (3) of Remark 2.102 applied at its left
end $b$, it is of the same kind as $f_{[b,a)}$. By part (3) of Remark 2.102
applied at the right end $a$ of $f_{[b+1,a)}$, we get that $f_{[b+1,a+1)}$ is
a cluster of the same kind as $f_{[b+1,a)}$. So $f_{[b+1,a+1)}$, the only
alleged cluster per period of $B$, is indeed a cluster, of the same kind as
$f_{[b,a)}$, the only cluster per period of $A$.

It remains to show that $\alpha$ respects the gates as described. We fix a
cleanup $(h,L)$ of $(A,f)$ and build a cleanup $(g,M)$ of $(B,f)$ with

$g_{i}=h_{i}\text{ for }i\not\equiv b\pmod{k}\text{ and }M_{i}=L_{i}\text{ for
}i,i+1\not\equiv b\pmod{k}\text{ .}$

We verify that the new gate at $(b+1)$ is one-way right-to-left as we build
the cleanup. The types of all other gates remain the same: the linear factors
$M_{i}=L_{i}$ in the cleanups are the same, and we already showed that the
types of clusters are the same.

To lighten notation, we talk about adjusting $L_{b+1}$ and $L_{b}$ and
$h_{b+1}$; corresponding entries in other periods are correspondingly
adjusted. Since $k\neq 1$, the linear $L_{b+1}$ and $L_{b}$ are not
corresponding factors from different periods, and can be adjusted
independently. Since $b+1\notin A$, the old linear factor $L_{b+1}$ is
identity. Since $b\notin B$, the new linear factor $M_{b}$ must be identity.

Case 1. If both $f_{[c,b)}$ and $f_{[b,a)}$ are $\mathsf{C}$-free clusters,
the gate at $b$ cannot be one-way, so the hypotheses of this Lemma cannot be
satisfied.

Case 2. If both $f_{[c,b)}$ and $f_{[b,a)}$ are $\mathsf{C}$ clusters, then
$h_{b+1}(x)=x^{2}-2$ and $L_{b}(x)=\lambda^{-1}x$. We can keep $h_{b+1}$, but
need a new linear $M_{b+1}$ such that $M_{b+1}\circ h_{b+1}=h_{b+1}\circ
L_{b}$. This is exactly the defining property of $M_{b+1}=A_{\lambda}$ from
[8, Remark 3.14] So get $M$ from $L$ by replacing $L_{b+1}=\operatorname{id}$
by $M_{b+1}=A_{\lambda}$, and replacing $L_{b}(x)=\lambda^{-1}x$ by
$M_{b}=\operatorname{id}$; and propagating through $k$-periodicity. Now
$(h,M)$ is a cleanup of $(B,f)$ with a right-to-left gate at $b+1$, as wanted.
If this gate is two-way, $M_{b+1}=A_{\lambda}$ must also be a scaling, forcing
$\lambda=\pm 1$, forcing the original gate of $(A,f)$ at $b$ to be two-way,
which we assumed it is not.

Case 3. Suppose that $f_{[c,b)}$ is a $\mathsf{C}$-free cluster, so
$h_{b+1}(x)=x^{2}$, and $f_{[b,a)}$ is a $\mathsf{C}$ cluster. For $(A,f)$ to
have a left-to-right gate at $b$, we must have $L_{b}=\operatorname{id}$. For
the new cleanup, we need $g_{b+1}(x)=x^{2}-2$. Let the new linear factor
$M_{b+1}(x):=x+2$. Clearly, $M_{b+1}\circ g_{b+1}=h_{b+1}\circ L_{b}$. Now
$(g,M)$, obtained from $(h,L)$ by replacing $h_{b+1}$ by $g_{b+1}$ and
$L_{b+1}$ by $M_{b+1}$, is a cleanup of $(B,f)$. It has a right-to-left gate
at $b+1$ as long as $h_{b+2}\circ M_{b+1}\circ(-2)$ is a Ritt polynomial;
which it is, since $M_{b+1}\circ(-2)=\operatorname{id}$ and $h_{b+2}$ is the
rightmost of the non-empty $\mathsf{C}$-free cluster $f_{[c,b+1)}$ of $(B,f)$.
Since this gate is between clusters of different kinds, it must be one-way by
the third part of Lemma 2.127.

Case 4. Suppose that $f_{[c,b)}$ is a $\mathsf{C}$ cluster, so
$h_{b+1}(x)=x^{2}-2$, and $f_{[b,a)}$ is a $\mathsf{C}$-free cluster. For
$(A,f)$ to have a left-to-right gate at $b$, we must have
$L_{b}(x)=\lambda^{-1}x$. For the new cleanup, we need $g_{b+1}(x)=x^{2}$ and
a new linear $M_{b+1}$ such that $M_{b+1}\circ g_{b+1}=h_{b+1}\circ L_{b}$,
which is exactly the defining property of $M_{b+1}=B_{\lambda}$. Now $(g,M)$,
obtained from $(h,L)$ by replacing $h_{b+1}$ by $g_{b+1}$ and
$L_{b+1}=\operatorname{id}$ by $M_{b+1}$ and $L_{b}$ by
$M_{b}=\operatorname{id}$, is a cleanup of $(B,f)$, with a right-to-left gate
at $b+1$, as desired. Again, since this gate is between clusters of different
kinds, it must be one-way by the third part of Lemma 2.127. ∎

We now verify that when a clustering is fed to Lemma 2.133, a clustering is
produced.

######  Lemma 2.134.

(Compare with [8, Lemma 4.32])
Fix a non-empty clustering $A$ of $f$ and consecutive elements $c>b>a$ of $A$.
Suppose that $(A,f)$ has a one-way left-to-right (respectively, right-to-left)
gate at $b\in A$ and that $f_{b+1}$ (resp., $f_{b}$) is quadratic. Let

$B:=(A\smallsetminus b+k\mathbb{Z})\cup b+1+k\mathbb{Z}$ $\text{
(respectively, }B:=(A\smallsetminus\
b+k\mathbb{Z})\cup\\{b-1+nk:n\in\mathbb{Z}\\}\text{ ).}$

Then $B$ is also a clustering of $f$.

###### Proof.

Again, we leave the “respectively” part to the reader.

Since $A$ is a clustering, the gate at $b$ must fail parts (2) and (3) of
Definition 2.128 of “fake gate”, so $b+1$ is not in $A$. Now all hypotheses of
Lemma 2.133 are satisfied, so we get its conclusions: $B$ is another
preclustering of $f$, with the same number of clusters per period as $A$, and
with a one-way right-to-left gate at $b+1$. Corresponding clusters of $B$ and
$A$ are of the same kind, $\mathsf{C}$ or $\mathsf{C}$-free; and all the
“other” cluster boundaries have gates in the same direction(s). As in that
lemma, let

$C:=A\smallsetminus b+k\mathbb{Z}\text{ to get }A=C\cup b+k\mathbb{Z}\text{
and }B=C\cup b+1+k\mathbb{Z}\text{ .}$

Let us verify that $B$ has no fake gates.

  1. (1)

Since $A$ is a clustering, it has no two-way gates. The new gate of $B$ at
$b+1$ is one way, and all other gates of $B$ are in the same direction(s) as
the corresponding gates of $A$. So $B$ also has no two-way gates.

  2. (2)

Where could $B$ have a left-to-right gate at $d$ with a quadratic $f_{d+1}$
and a cluster boundary at $d+1$? If $d,d+1\in C$, then this contradicts $A$
being a clustering. Since $B$ has a one-way gate in the other direction at
$b+1$, we cannot have $d\equiv b+1\pmod{k}$. So $d+1\equiv b+1\pmod{k}$;
without loss of generality, $d+1=b+1$. But then $b=d$ is a cluster boundary of
$B$, a contradiction.

  3. (3)

Where could $B$ have a right-to-left gate at $d$ with a quadratic $f_{d}$ and
a cluster boundary at $d-1$? Again, $d,d-1\in C$ contradicts $A$ being a
clustering. Again, $(d-1,d)\equiv(b,b+1)\pmod{k}$ contradicts $b\notin B$. So
we must have $d-1\equiv b+1\pmod{k}$.

Then $d\equiv b+2\pmod{k}$ is in $B$; since $k\neq 1$, this means that $b+2\in
C$, and $A$ also has a right-to-left gate at $b+2\equiv d\pmod{k}$. Together
with $A$’s original left-to-right gate at $b$ and quadratics $f_{b+1}$ and
$f_{d}=f_{b+2}$, this makes $A$’s gates at $b$ and $b+2$ fake by parts (4) and
(5) of Definition 2.128.

  4. (4,5)

Finally, where could $(B,f)$ have quadratic factors $f_{d}$ and $f_{d+1}$ with
a right-to-left gate at $d+2$ and a left-to-right gate at $d$? Again,
$d,d+2\in C$ immediately contradicts $A$ being a clustering. Again, since $B$
has a one-way right-to-left gate at $b+1$, we cannot have $d\equiv
b+1\pmod{k}$. So we must have $d+2\equiv b+1\pmod{k}$. Now $d\equiv
b-1\pmod{k}$ is in $C$, so $A$ also has a left-to-right gate at $d\equiv
b-1\pmod{k}$. However, $b\equiv d+1\pmod{k}$ is also a cluster boundary of
$A$, and $f_{d+1}$ is a quadratic, making the $A$’s gate at $d$ fake by part
(2) of Definition 2.128; contradicting $A$ being a clustering.

∎

We introduce the boundary set, a slight variant of a clustering, replacing
each ambiguous boundary, at $b$ or $b+1$, with the half-integer
$b+\frac{1}{2}$ lying between the two options for the boundary.

######  Definition 2.135.

For a clustering $A$ of a $k$-long decomposition$f$, the _boundary set_ is the
subset $B$ of $\frac{1}{2}\mathbb{Z}$ such that, for any integer $i$,

  1. (1)

$i-\frac{1}{2}\in B$ if and only if the factor $f_{i}$ is quadratic, and Lemma
2.133 applies:
either $i\in A$ and $(A,f)$ has a right-to-left gate at $i$;
or $i-1\in A$ and $(A,f)$ has a left-to-right gate at $i$.

  2. (2)

$i\in B$ if and only if $i\in A$ and Lemma 2.133 does not apply.

A _boundary list_ $\alpha$ of a $k$-long decomposition$f$ is an increasing
bijection from $\mathbb{Z}$ to a boundary set $B\subset\frac{1}{2}\mathbb{Z}$
of some clustering $(A,f)$.

######  Remark 2.136.

When a new clustering is obtained from another one by moving a quadratic
factor from one cluster to another as in Lemma 2.133, the original clustering
and the new one have the same boundary set. We will show with Theorem 2.145
that this only way to produce new clusterings from old so that ultimately the
boundary set is an invariant of the long decomposition independent of a choice
of clustering.

######  Remark 2.137.

The boundary list will help us to keep track of how the gates move as
$\operatorname{ST}_{k}$ acts on long decompositions. Annoyingly, this
introduces a new non-uniqueness: the starting point $\alpha(0)$.

To prove our Theorem 2.145 that the boundary set is an invariant of a long
decomposition we require several technical lemmas describing how clusters may
overlap. These results are analogous to the work in [8, Lemmas 4.23, 4.24, and
4.25].

The next lemma says that is a cluster can bite off a factor from an adjacent
cluster, either the two clusters can fuse (so this cannot happen in a
clustering), or Lemma 2.133 applies.

######  Lemma 2.138.

Fix consecutive elements $c>b>a$ of a preclustering $A$ of a $k$-long
decomposition$f$. Suppose that the concatenation $f_{[b+1,a)}$ of this cluster
$f_{[b,a)}$ with an adjacent factor $f_{b+1}$ is a cluster. Then exactly one
of the following holds

  1. (1)

$(A,f)$ has a two-way gate at $b$;

  2. (2)

$c=b+1$ and $f_{b+1}$ is quadratic;

  3. (3)

$b+1\notin A$ and $f_{b+1}$ is quadratic and $(A,f)$ has a one-way left-to-
right gate at $b$.

The same is true on the other side: if $f_{[b,a-1)}$ is a cluster, $(A,f)$ has
a two-way gate at $a$; or $f_{a}$ is a quadratic and a single cluster; or
$f_{a}$ is quadratic and $a-1\not\in A$ and $(A,f)$ has a right-to-left gate
at $a$.

###### Proof.

Again, we only prove one side. Case 1. If $f_{b+1}$ is not quadratic, then the
two clusters $f_{[c,b)}$ and $f_{[b,a)}$ are of the same kind, $\mathsf{C}$ or
$\mathsf{C}$-free.

Case 1.1. If $f_{[c,b)}$ is a $\mathsf{C}$-free cluster, then (by Lemma 2.123)
$A^{\prime}:=A\cup(b+1+k\mathbb{Z})$ is also a preclustering of $f$, and any
cleanup of $(A,f)$ is also a cleanup of $(A^{\prime},f)$. Now Lemma 2.124
applies to the concatenation $f_{[b+1,a)}$ of the clusters $f_{[b+1,b)}$ and
$f_{[b,a)}$ of $(A^{\prime},f)$. So $(A^{\prime},f)$ has a two-way gate at
$b$, and so $(A,f)$ has a two-way gate at $b$.

Case 1.2. If $f_{[c,b)}$ is a $\mathsf{C}$ cluster, and $(L,h)$ is a cleanup
of $(A,f)$, then all $h_{i}$ with $c\geq i>a$ are Chebyshev polynomials. In
order to have linear $M$ and $N$ for which

$(M\circ h_{c},h_{c-1},\ldots,h_{b+1},L_{b}\circ h_{b}\circ N)$

is linearly equivalent to

$(h_{c},h_{c-1},\ldots,h_{b+1},\circ h_{b})\text{, }$

we must have $L_{b}(x)=\pm x$, since Chebyshev polynomials are not otherwise
linearly related to themselves (see [8, Section 3] for details of this well-
known fact). So again, $(A,f)$ has a two-way gate at $b$.

Case 2. If $f_{b+1}$ is quadratic, by the second part of Lemma 2.127, $(A,f)$
has a left-to-right gate at $b$. If this gate is two-way, we get conclusion
(1) of the lemma. If $b+1\in A$, we get conclusion (2) in the lemma. If
neither of these holds, we get conclusion (3) of the lemma. ∎

It follows that a cluster cannot bite off more than one factor from an
adjacent cluster, unless the two clusters fuse. In particular, this cannot
happen in a clustering.

######  Lemma 2.139.

Fix consecutive elements $c>b>a$ of a preclustering $A$ of a $k$-long
decomposition$f$, and suppose that $c\geq b+2$. Suppose that the concatenation
$f_{[b+2,a)}$ of this cluster $f_{[b,a)}$ with two adjacent factors $f_{b+2}$
and $f_{b+1}$ is a cluster. Then the whole $f_{[c,a)}$ is a cluster.
Furthermore, $(A,f)$ has a two-way gate at $b$, or $f_{[c,b)}$ is a
$\mathsf{C}$ cluster and $b=a+1$ and $f_{b}$ is quadratic.

The same is true on the other side: if $b-2\geq a$ and $f_{[b,a-2)}$ is a
cluster, and $d<a$ is the next element of $A$, then the concatenation
$f_{[b,d)}$ of two clusters is a cluster; and $(A,f)$ has a two-way gate at
$b$, unless $f_{[a,d)}$ is a $\mathsf{C}$ cluster, and $b=a+1$ and $f_{b}$ is
quadratic.

###### Proof.

Case 1. If $f_{[b+1,a)}$ is also a cluster, then Lemma 2.138 applies, and
conclusion (2) cannot hold, and conclusion (1) is what we want. Suppose toward
contradiction that conclusion (3) holds. Now Lemma 2.133 applies, providing us
with a new preclustering $B$ of $f$, with a cluster boundary at $(b+1)$
instead of $b$, with a one-way gate the wrong way at that gate. Since
$f_{[b+2,a)}$ is a cluster, Lemma 2.138 also applies to this new preclustering
$B$. But conclusion (1) needs a two-way gate where we have a one-way gate;
and, by the second part of Lemma 2.127, conclusions (2) and (3) need a one-way
gate in the other direction at $(b+1)$.

Case 2. If $f_{[b+1,a)}$ is not a cluster, then Remark 2.102 applies, since
$f_{[b+1,a)}$ is contained in the cluster $f_{[b+2,a)}$, and contains the
cluster $f_{[b,a)}$. This means that $f_{[b+2,a)}$ must be a $\mathsf{C}$
cluster, and all factors of $f_{[b+1,a)}$ must be quadratic, and $f_{[b,a)}$
must be a $\mathsf{C}$-free cluster consisting of a single quadratic factor.

So we have: $b=a+1$, and $f_{b}$ and $f_{b+1}$ are quadratic, and $f_{b+2}$ is
linearly related to an odd-degree Chebyshev polynomial. In particular,
$f_{[c,b)}$ is a $\mathsf{C}$ cluster. Fix a cleanup $(h,L)$ of $(A,f)$. Then
$h_{b+2}$ is an odd-degree Chebyshev polynomial, $h_{b+1}(x)=x^{2}-2$ is the
Chebyshev polynomial of degree 2, and $h_{b}(x)=x^{2}$. We are interested in
the linear factor $L_{b}$. For $f_{[b+2,a)}$ to be a cluster, we must have
linear $M$ and $N$ with

$(M\circ h_{b+2},x^{2}-2,L_{b}\circ x^{2}\circ N)$

is linearly equivalent to

$(h_{b+2},x^{2}-2,x^{2}-2).$

By [8, Remark 3.14] about the linear relations between $x^{2}$ and $x^{2}-2$,
this exactly corresponds to the definition of “$(A,f)$ has a right-to-left
gate at $b$”. Now the second part of Lemma 2.127 shows that the concatenation
of the cluster $f{[c,b)}$ and the adjacent quadratic factor $f_{b}$ is a
cluster. Since the whole cluster $f_{[b,a)}$ consists of this one factor, we
have shown that $f_{[c,a)}$ is a cluster. ∎

With the next lemma we show that two overlapping $\mathsf{C}$-clusters for
which the intersection contains all the odd degree factors fuse into a single
$\mathsf{C}$-cluster. This result provides some necessary details for the
proof of [8, Lemma 4.25].

######  Lemma 2.140.

Fix a $k$-long decomposition$f$ and integers $d>c>b>a$. Suppose that
$f_{[d,b)}$ and $f_{[c,a)}$ are both $\mathsf{C}$ clusters, and all factors of
both $f_{[d,c)}$ and $f_{[b,a)}$ are quadratic. Then the whole $f_{[d,a)}$ is
a $\mathsf{C}$ cluster.

###### Proof.

We first replace $k$ by a sufficiently big multiple to ensure that $k\gg d-a$.

The proof proceeds by induction on $(b-a)$. In the base case $b-a=0$, the
desired cluster $f_{[d,a)}$ in the conclusion is one of the clusters
$f_{[d,b)}$ in the hypothesis.

We consider three preclusterings $A$, $B$, and $D$ of $f$. All clusters of
$A$, $B$, and $D$ consist of one factor each, except for $f_{[c,a)}$ for $A$,
$f_{[c,b)}$ for $B$, and $f_{[d,b)}$ for $D$.

We build two cleanups $(h,L)$ and $(g,M)$ of $(B,f)$.

To build $(h,L)$, we start with a cleanup $(\hat{h},\hat{L})$ of $(A,f)$. So,
$\hat{h}_{i}$ are Chebyshev polynomials when $c\geq i>a$; and
$\hat{L}_{i}=\operatorname{id}$ when $c>i>a$. Let $h_{i}(x):=x^{2}$ and
$L_{i}(x):=x-2$ for $i$ with $b\geq i>a$; and let $h_{i}=\hat{h}_{i}$ and
$L_{i}=\hat{L}_{i}$ for other (modulo $k$) $i$.

Similarly, to build $(g,M)$, start with a cleanup $(\hat{g},\hat{M})$ of
$(D,f)$ and take $M_{i}(x)=x-2$ and $g_{i}(x)=x^{2}$ for $i$ where $d\geq
i>c$, as in the previous case. Because we do not know anything about the
factor $f_{d+1}$, it may be necessary to further adjust $g_{d+1}$ and $M_{d}$
to satisfy part (5b) of the definition of “cleanup”.

We know $(h,L)$ has a one-way right-to-left gate at $b$. By part (1) of Lemma
2.127, it follows that so does $(g,M)$. Since $M_{b}=\hat{M}_{b}$, it also
follows that the cleanup $(\hat{g},\hat{M})$ of the preclustering $D$ of $f$
has a one-way right-to-left gate at $b$. By part (2) of Lemma 2.127, we know
that $f_{[d,b-1)}$ is a cluster. The induction step is now complete. ∎

We come now to the main technical lemma explaining exactly under what
conditions two clusters may overlap. We will use this result repeatedly to
compare clusterings of the same $k$-long decompositionand then employ it later
to understand the action of Ritt swaps.

######  Lemma 2.141.

Fix a $k$-long decomposition$f$ and integers $d>c>b>a$. Suppose that
$f_{[d,b)}$ and $f_{[c,a)}$ are both clusters. Then either the whole
$f_{[d,a)}$ is a cluster; or $c=b+1$ and $f_{b+1}$ is quadratic and at least
one of $f_{[d,b)}$ and $f_{[c,a)}$ is a $\mathsf{C}$ cluster.

###### Proof.

The three small pieces $f_{[d,c)}$ and $f_{[c,b)}$ and $f_{[b,a)}$, are almost
always clusters themselves. We first deal with this general case, and then use
Remark 2.102 to analyze situations where some of the pieces are not clusters.

Case 1. All three $f_{[d,c)}$ and $f_{[c,b)}$ and $f_{[b,a)}$ are clusters.

To apply our previous Lemmas 2.138 and 2.139, we need a preclustering $A$ of
$f$ for which these $d>c>b>a$ are consecutive elements of $A$. We can always
do this, possibly at the expense of replacing $k$ by a suitably big multiple:
the conclusion of this lemma is completely local, so this is not a problem.

Now Lemma 2.131 applies at each of the two boundaries $c$ and $b$. If both
gates are two-way, the whole $f_{[d,a)}$ is a cluster. If the outer clusters
are single quadratics that join the middle cluster via one-way gates, they can
both join, again making the whole $f_{[d,a)}$ a cluster. The only other option
is that the middle cluster is the single quadratic, and at least one of the
gates is one-way. Since there are no one-way gates between $\mathsf{C}$-free
clusters, at least one of the clusters must be a $\mathsf{C}$ cluster.

Case 2. If the middle piece $f_{[c,b)}$ is not a cluster, then both
$f_{[d,b)}$ and $f_{[c,a)}$ are $\mathsf{C}$ clusters and the overlap
$f_{[c,b)}$ consists of quadratic factors, so the outer pieces $f_{[d,c)}$ and
$f_{[b,a)}$ still have odd-degree factors, and so they are clusters. In fact,
$f_{[d,i)}$ and $f_{[i,a)}$ are clusters for any $i$ with $c\geq i\geq b$,
since they are contained in a cluster and contain an odd-degree factor. If
$c=b+1$, we are done. Otherwise, we can use Lemma 2.139, as soon as we have a
preclustering $A$ of $f$ for which these $d>b>a$ are consecutive elements. As
in Case 1, we can always find such $A$. We now have two adjacent clusters
$f_{[d,b)}$ and $f_{[b,a)}$, and the $f_{[b+2,a)}$ is also a cluster. Since we
know that $f_{[b,a)}$ contains an odd-degree factor, the whole $f_{[d,a)}$
must be a cluster by Lemma 2.139.

Case 3. If one of the outer pieces, $f_{[d,c)}$ or $f_{[b,a)}$, is not a
cluster, it means that the corresponding big cluster, $f_{[d,b)}$ or
$f_{[c,a)}$, respectively, is a $\mathsf{C}$ cluster whose odd-degree factors
are inside the middle piece $f_{[c,b)}$. Then both $f_{[d,b)}$ and $f_{[c,a)}$
are $\mathsf{C}$ clusters.

If $f_{[b,a)}$ is a cluster, we can apply the reasoning in Case 2 again:
$f_{[d,b)}$ and $f_{[b,a)}$ are adjacent clusters, and $f_{[i,a)}$ is a
cluster for any $i$ with $b\geq i\geq a$. Applying Lemmas 2.138 and 2.139
again, and noting that the middle piece $f_{[c,b)}$ is not a single quadratic,
we get that the whole $f_{[d,a)}$ must be a cluster. The same reasoning
applies if $f_{[d,c)}$ is a cluster.

The last remaining possibility that both $f_{[d,c)}$ and $f_{[b,a)}$ consist
of nothing but quadratics is handled by Lemma 2.140.

∎

The following (surprisingly useful) technical lemma shows that a one-quadratic
cluster of a clustering cannot be contained in a $\mathsf{C}$ cluster.

######  Lemma 2.142.

If

  * •

$A$ is a preclustering of a $k$-long decomposition$f$; and

  * •

$a,a-1\in A$ and $f_{a}$ is quadratic; and

  * •

$f_{[e,d)}$ is a $\mathsf{C}$ cluster for some $e,d$ with $e\geq a$ and
$a-1\geq d$;

then $A$ is not a clustering.

###### Proof.

Let $z$ be the index of an odd-degree factor $f_{z}$ in the $\mathsf{C}$
cluster $f_{[e,d)}$, closest to $a$ on the left or to $a-1$ on the right. We
write out the details of the first case; the second is identical. Let $y>x$ be
the boundaries of the cluster $f_{[y,x)}$ of $(A,f)$ that contains the factor
$f_{z}$. So now

$y\geq z>x\geq a\text{ and }e\geq z\text{ and }a-1\geq d;\text{ implying that
}x-1\geq d\text{ .}$

Since we assumed that $f_{z}$ is the closest odd-degree factor, all $f_{i}$
with $x\geq i\geq a$ are quadratic. Remark 2.102 then forces every such $i$ to
be a cluster boundary of $A$.

We will show that the concatenation $f_{[y,x-1)}$ of adjacent clusters
$f_{[y,x)}$ and $f_{[x,x-1)}$ of $(A,f)$ is itself a cluster, contradicting
Lemma 2.131. Since $f_{[y,x-1)}$ contains the odd-degree factor $f_{z}$, by
Remark 2.102 it suffices to show that $f_{[y,x-1)}$ is contained in a cluster.

If $e\geq y$, then $f_{[y,x-1)}$ is contained in $f_{[e,d)}$. If $y>e$, then
the clusters $f_{[y,x)}$ and $f_{[e,d)}$ overlap, and the overlap includes the
odd-degree factor $f_{z}$. So by Lemma 2.141, the whole $f_{[y,d)}$ is a
cluster, again containing $f_{[y,x-1)}$. ∎

We now return to proving Theorem 2.145 that the boundary set of a $k$-long
decomposition(see Definition 2.135) is unique. It is easy to see that whenever
the empty set is a preclustering of $f$, it is the unique clustering of $f$.
So, we compare two a priori unrelated non-empty clusterings $A$ and $D$ of the
same $k$-long decomposition$f$.

The first Lemma 2.143 in this series deals with one mismatched cluster
boundary. Options (2) and (3) in its conclusion do not produce a mismatch of
boundary sets; option (1) is sorted out in the following Lemma 2.144.

######  Lemma 2.143.

Suppose that $A$ and $D$ are non-empty clusterings of the same $k$-long
decomposition$f$ and $b\in A\smallsetminus D$. Then one of the following is
true.

  1. (1)

Both $f_{b}$ and $f_{b+1}$ are quadratic; and $b+1$ and $b-1$ are both in $D$.

  2. (2)

$A$ has a one-way left-to-right gate at $b$, and $f_{b+1}$ is quadratic,
and $b+1\in D$, and Lemma 2.134 gives another clustering

$B=(A\smallsetminus b+k\mathbb{Z})\cup b+1+k\mathbb{Z}$

of $f$ which shares the cluster boundary $b+1$ with $D$.

  3. (3)

$A$ has a one-way right-to-left gate at $b$, and $f_{b}$ is quadratic, $b-1\in
D$, so Lemma 2.134 gives another clustering $B=(A\smallsetminus
b+k\mathbb{Z})\cup b-1+k\mathbb{Z}$ of $f$ which shares the cluster boundary
$b-1$ with $D$.

###### Proof.

Fix consecutive elements $c>b>a$ of $A$.
Since $b\notin D$, there are consecutive elements $e>d$ of $D$ with $e>b>d$.
Comparing $e$ to $c$ and $d$ to $a$ breaks this proof into four cases. In each
case, we get a contradiction (via Remark 2.102, Lemma 2.142, Lemma 2.141, and
Lemma 2.131) or one of the desired conclusions (via Lemma 2.127 and Lemma
2.134).

Case 1. If $e\geq c$ and $a\geq d$, then the concatenation $f_{[c,a)}$ of two
clusters of $(A,f)$ is contained in the cluster $f_{[e,d)}$ of $(D,f)$. By
Lemma 2.131, this concatenation $f_{[c,a)}$ cannot be a cluster itself. Remark
2.102 then shows that $c=b+1=a+2$, and $f_{b}$ and $f_{b+1}$ are quadratic,
and $f_{[e,d)}$ is a $\mathsf{C}$ cluster, and Lemma 2.142 provides the
contradiction.

Case 2. If $e\geq c$ and $b>d>a$, then Lemma 2.141 applies to the clusters
$f_{[e,d)}$ and $f_{[b,a)}$.

If the whole $f_{[e,a)}$ is a cluster, then $f_{[c,a)}$ is contained in a
cluster, and contains the cluster $f_{[b,a)}$ with at least two factors:
$b>d>a$ implies that $b\geq a+2$. Remark 2.102 then shows that $f_{[c,a)}$ is
a cluster, contradicting Lemma 2.131.

Thus $b=d+1$ and $f_{b}$ is quadratic. We want to show that the concatenation
$f_{[c,b-1)}$ of the cluster $f_{[c,b)}$ of $(A,f)$ and the adjacent quadratic
$f_{b}$ is a cluster. This $f_{[c,b-1)}$ is contained in the cluster
$f_{[e,d)}=f_{[e,b-1)}$, and contains the cluster $f_{[c,b)}$. Remark 2.102
gives what we want, unless $c=b+1$ and $f_{c}$ is quadratic and $f_{[e,d)}$ is
a $\mathsf{C}$ cluster. In that case, Lemma 2.142 provides the contradiction.

Case 3. The situation where $c>e$ but $a\geq d$ works exactly like Case 2.

Case 4. Finally, suppose that $c>e>b>d>a$. Lemma 2.141 now applies to
$f_{[e,d)}$ with $f_{[b,a)}$, and to $f_{[c,b)}$ with $f_{[e,d)}$. Each of
these two instances of Lemma 2.141 produces one of two conclusions, breaking
this case into four subcases.

Subcase 4.1. Suppose that both concatenations $f_{[e,a)}$ and $f_{[c,d)}$ are
clusters. Their overlap $f_{[e,d)}$ contains at least two factors, so another
application of Lemma 2.141 shows that the whole $f_{[c,a)}$ is a cluster,
contradicting Lemma 2.131.

Subcase 4.2. Suppose that $b=d+1$ and $f_{b}$ is quadratic, but the overlap
$f_{[e,b)}$ of $f_{[c,b)}$ with $f_{[e,d)}$ is not a single quadratic and
$f_{[c,d)}$ is a cluster. Since the concatenation $f_{[c,d)}$ of the cluster
$f_{[c,b)}$ and the adjacent quadratic $f_{b}$ is a cluster, Lemma 2.127 shows
that $(A,f)$ has a right-to-left gate at $b$. As in Case 2 above, Lemma 2.134
now gives us another clustering $B=(A\smallsetminus b+k\mathbb{Z})\cup
b-1+k\mathbb{Z}$ of $f$ which shares the cluster boundary $d=b-1$ with $D$.

Subcase 4.3. The reasoning is exactly the same for the symmetric situation
where $e=b+1$ and $f_{b+1}$ is a quadratic, but the overlap $f_{[b,d)}$ of
$f_{[e,d)}$ and $f_{[b,a)}$ is not a single quadratic.

Subcase 4.4. Finally, we arrive at the first option in the conclusion of this
lemma: $f_{b}$ and $f_{b+1}$ are both quadratic, and $e=b+1$ and $d=b-1$. ∎

The last lemma was the induction step for the proof of Theorem 2.145, and the
next lemma is the base case, sorting out option (1) in the conclusion of the
last lemma.

######  Lemma 2.144.

Fix two clusterings $A$ and $D$ of the same $k$-long decomposition$f$. Suppose
that for every $b\in A\smallsetminus D$, both $f_{b}$ and $f_{b+1}$ are
quadratic; and $b+1$ and $b-1$ are both in $D$. Suppose symmetrically that for
every $b\in D\smallsetminus A$, both $f_{b}$ and $f_{b+1}$ are quadratic; and
$b+1$ and $b-1$ are both in $A$. Then $A=D$.

###### Proof.

Fix cleanups $(g,M)$ of $(A,f)$, and $(h,L)$ of $(D,f)$.

Observe first that for every $b\in A\smallsetminus D$, the cluster
$f_{[b+1,b-1)}$ of $D$ broken by $b$ is a $\mathsf{C}$-free cluster, since it
has degree $4$. By Lemma 2.123, this means that $A\cup D$ is another
preclustering of $f$, and $(g,M)$ is a cleanup of it. Symmetrically, $(h,L)$
is also a cleanup of $(A\cup D,f)$.

For any $d\in D\smallsetminus A$, the cleanup $(g,M)$ of $(A,f)$ must have
$M_{d}=\operatorname{id}$. So the cleanup $(g,M)$ of $(A\cup D,f)$ has a two-
way gate at such $d$. So every cleanup of $(A\cup D,f)$, including $(h,L)$,
has a two-way gate at such $d$. So $L_{d}=\operatorname{id}$. So the cleanup
$(h,L)$ of $(D,f)$ has a two-way gate at $d$. But this fake gate of $(D,f)$
contradicts the definition of “clustering”.

The same contradiction arises symmetrically from any $b\in A\smallsetminus D$.
∎

We come now to our Theorem 2.145 showing that the boundary set is an invariant
of a long decomposition, as are the types of clusters and the gates appearing
in a clustering. We prove the theorem by showing that any two clusterings may
be converted one to the other through a finite sequence of applications of
Lemma 2.134.

######  Theorem 2.145.

Any two non-empty clusterings $A$ and $D$ of the same $k$-long
decomposition$f$ give rise to the same boundary set $B$ for $f$.

Corresponding clusters of $(A,f)$ and $(D,f)$ are of the same kind
($\mathsf{C}$ or $\mathsf{C}$-free).

For each $b\in A\cap D\supseteq B\cap\mathbb{Z}$, the gates of $(A,f)$ at $b$
and $(D,f)$ at $b$ are of the same kind (none, one-way left-to-right, one-way
right-to-left).

For each half-integer $b-\frac{1}{2}\in B$ with $b\in A$ and $b-1\in D$ or
vice versa, $A$ and $D$ have one-way gates in opposite direction at this
cluster boundary.

###### Proof.

We build a finite sequence $(A_{i},D_{i})$ for $i=0,1,2,\ldots,n$ of pairs of
clusterings of $f$ such that $A_{0}=A$ and $D_{0}=D$ and $A_{n}=D_{n}$; and
for each $i$, either $A_{i+1}$ is obtained from $A_{i}$ via Lemma 2.134 and
$D_{i+1}=D_{i}$; or vice versa. All the conclusions of this theorem follow
from the corresponding conclusions of Lemma 2.133. For example, at each step,
$A_{i}$ and $A_{i+1}$ will give rise to the same the boundary set; and $D_{i}$
and $D_{i+1}$ will also give rise to the same the boundary set. Thus,
$A=A_{0}$ will have the same boundary set as $A_{n}=D_{n}$ which has the same
boundary set as $D=D_{0}$.

To build the sequence, we induct on

$|(A_{i}\bigtriangleup D_{i})\cap\\{1,2,\ldots,k\\}|\text{, }$

the number of cluster boundary disputes between $D_{i}$ and $A_{i}$, in one
period.

When this number is zero, $A_{i}=D_{i}$ and we are done.

Otherwise, if some $b\in A_{i}\smallsetminus D_{i}$ satisfies condition (2) or
(3) in Lemma 2.143 with $A=A_{i}$ and $D=D_{i}$, that lemma provides
$B=:A_{i+1}$ that has one fewer disputes with $D_{i+1}:=D_{i}$.

Otherwise, if some $b\in D_{i}\smallsetminus A_{i}$ satisfies condition (2) or
(3) in Lemma 2.143 with $A=D_{i}$ and $D=A_{i}$, that lemma provides
$B=:D_{i+1}$ that has one fewer disputes with $A_{i+1}:=A_{i}$.

Finally, the case that every $b\in A_{i}\bigtriangleup D_{i}$ satisfies
condition (1) in Lemma 2.143, is ruled out by Lemma 2.144. ∎

The point of this theorem is that now the number of clusters per period and
the kinds ($\mathsf{C}$ or $\mathsf{C}$-free) of corresponding clusters are
properties of the $k$-long decompositionalone, independent of the clustering.
The existence of one-way gates between corresponding clusters is also a
property of the $k$-long decomposition; and if we distinguish three kinds of
such gates instead of two, separating out the gates occupied by quadratic that
correspond to half-integers in the boundary set, the kinds of one-way gates
are also a property of the $k$-long decomposition, independent of the
clustering.

####  2.3.5. Clusterings and the action of $\operatorname{ST}_{k}$

In this subsection we focus on the interaction between the action of
$\operatorname{ST}_{k}$ and clusterings. Our key result will be that while
clusterings themselves are not invariant under this partial group action, the
number of clusters, the kind (i.e. type $\mathsf{C}$ or $\mathsf{C}$-free),
and the presence or absence (but not the direction) of one-way gates between
the are all invariant under the action of $\operatorname{ASym}_{k}$.

We now collect some easy results from [8] about the interactions between the
partial functions $t_{i}\star$ and clusters, explaining how they fit with our
new context of long decompositions.

######  Proposition 2.146.

(Compare with [8, Remark 4.5(5), Proposition 4.11, Lemma 4.17(2), and Lemma
4.31]) Suppose that $t_{i}\star[f]=[g]$. That is, $t_{i}\star[f]$ is defined
and $[f]$ and $[g]$ are Ritt-swap-related at $i$.

  1. (1)

Then $(f_{i+1},f_{i})$ is a cluster.

  2. (2)

Moreover, $f$ admits a clustering $A$ with $i\notin A$.

  3. (3)

Any (pre)clustering $A$ of $f$ with $i\notin A$ is also a (pre)clustering of
$g$, with the same gates in the same places.

###### Proof.

The first statement is an immediate consequence of the definitions.

For the second statement, fix a clustering $A$ of $f$. If $i\notin A$, we are
done; so suppose that $i\in A$, and let $b>i>a$ be consecutive elements of
$A$. Since tautological Ritt swaps are not allowed, at least one of $f_{i+1}$
and $f_{i}$ is not quadratic; without loss of generality, suppose that $f_{i}$
is not quadratic. Then by Lemma 2.141, $f_{[i+1,a)}$ is a cluster. By Lemma
2.127, it follows that $f_{i+1}$ is quadratic and $A$ has a left-to-right gate
at $i$. By Lemma 2.134, $B:=(A\smallsetminus i+k\mathbb{Z})\cup
i+1+k\mathbb{Z}$ is another clustering of $f$, and $i\notin B$.

To prove (3), we start by showing that a preclustering $A$ of $f$ with
$i\notin A$ is also a preclustering of $t_{i}\star[f]$. Fix a cleanup $(h,L)$
of $(A,f)$. Since $i\notin A$, $f_{i}$ and $f_{i+1}$ are in the same cluster.

If this is a $\mathsf{C}$ cluster, then $h_{i}$ and $h_{i+1}$ are Chebyshev
polynomials and $h_{i}\circ h_{i+1}=h_{i+1}\circ h_{i}$ is a basic Ritt swap.
Let

$\tilde{h}_{i}:=h_{i+1}\text{ and }\tilde{h}_{i+1}:=h_{i}\text{ and
}\tilde{h}_{j}:=h_{j}\text{ for }j\not\equiv i,i+1\pmod{k}\text{ .}$

It is straightforward to verify that $(\tilde{h},L)$ is a cleanup of
$\tilde{g}:=L\circ\tilde{h}$. This $\tilde{g}$ is clearly Ritt-swap-related to
$f$ at $i$, so it is linearly equivalent to $g$. Thus, $(\tilde{h},L)$ is also
a cleanup of $g$, and $A$ is also a preclustering of $g$. This argument works
exactly the same way when both $h_{i}$ and $h_{i+1}$ are monomials inside a
$\mathsf{C}$-free cluster.

In general, inside a $\mathsf{C}$-free cluster we need [8, Lemma 3.37] to
conclude that there are polynomials $\tilde{h}_{i}$ and $\tilde{h}_{i+1}$ such
that $h_{i}\circ h_{i+1}=\tilde{h}_{i+1}\circ\tilde{h}_{i}$ is a basic Ritt
swap. It is now slightly less trivial to verify that $(\tilde{h},L)$ is also a
cleanup of $g$: if $(i-1)\in A$ and $\tilde{h}_{i}$ is not a monomial, one
might worry about condition [5b] in the definition of cleanup. This is
actually not an issue because the Ritt swap forces $\tilde{h}_{i}$ to have
non-trivial in-degree (see Definition 2.57. Thus, $\tilde{h}_{i}$ cannot be a
type $\mathsf{A}$ Ritt polynomial; so $\tilde{h}_{i}$ and $\tilde{h}_{i}\circ
L_{i-1}$ cannot both be Ritt polynomials for a non-trivial translation
$L_{i-1}$.

Since the types of clusters and the linear factors did not change, the two
cleanups have the same gates in the same places. Thus, one is a clustering if
and only if the other is.

∎

The next two lemmas are used in the proof of Theorem 2.149, an analogue of [8,
Theorem 2.52], that the action of the generators $t_{i}$ of
$\operatorname{ASym}_{k}$ on linear equivalence classes of $k$-long
decompositionssatisfy the braid relations.

######  Lemma 2.147.

(Compare with [8, Lemma 4.38]) If $t_{i}\star[f]$ and $t_{i+1}\star[f]$ are
both defined, then $(f_{i+2},f_{i+1},f_{i})$ is a cluster or $f_{i+1}$ is
quadratic.

###### Proof.

By Proposition 2.146, $(f_{i+1},f_{i})$ and $(f_{i+2},f_{i+1})$ are both
clusters. Lemma 2.141 with $d=i+2$ and $c=i+1$ and $b=i$ and $a=i-1$ finishes
the proof. ∎

######  Lemma 2.148.

(Compare with [8, Lemma 4.39]) If one of
$t_{i}\star(t_{i+1}\star(t_{i}\star[f]))$ or
$t_{i+1}\star(t_{i}\star(t_{i+1}\star[f]))$ is defined, then
$(f_{i+2},f_{i+1},f_{i})$ is a cluster.

###### Proof.

Suppose that $t_{i}\star(t_{i+1}\star(t_{i}\star[f]))$ is defined; the other
case is completely analogous. Let $g$ be a representative of $t_{i}\star[f]$,
and let $h$ be a representative of $t_{i+1}\star(t_{i}\star[f])$. Since
$t_{i+1}\star[g]=[h]$ and tautological Ritt swaps are not permitted, at most
one of $g_{i+1}$ and $h_{i+1}$ can be quadratic. Lemma 2.147 applies to both
$g$ and $h$, so at least one of $(g_{i+2},g_{i+1},g_{i})$ and
$(h_{i+2},h_{i+1},h_{i})$ is a cluster. So

$A:=(\mathbb{Z}\smallsetminus i+k\mathbb{Z})\cup i+1+k\mathbb{Z}$

is a preclustering of $g$ or $h$. Therefore, by Proposition 2.146 applied once
or twice, $A$ is also a preclustering of $f$, and, in particular,
$(f_{i+2},f_{i+1},f_{i})$ is a cluster. ∎

This next theorem is the key step in proving Corollary 2.36 that our partial
action of the generators of $\operatorname{ASym}_{k}$ on $\mathscr{D}_{k}$ is
actionable, thus giving a partial group action of $\operatorname{ASym}_{k}$
itself on $\mathscr{D}_{k}$.

######  Theorem 2.149.

Suppose that $k\geq 3$ and $f$ is a $k$-long decompositionand $i$ is an
integer. Then

$t_{i}\star(t_{i+1}\star(t_{i}\star[f]))=t_{i+1}\star(t_{i}\star(t_{i+1}\star[f]))\text{
.}$

That is, they are equal when defined, and one is defined if and only if the
other is.

###### Proof.

By Lemma 2.148, $(f_{i+2},f_{i+1},f_{i})$ is a cluster, so

$A:=(\mathbb{Z}\smallsetminus i+k\mathbb{Z})\cup i+1+k\mathbb{Z}$

is a preclustering of $f$. Let $(h,L)$ be a cleanup of $(f,A)$.

The rest of the proof is almost a repeat of the proof of Proposition 2.146.

If this is happening inside a $\mathsf{C}$ cluster, all three of $h_{i+2}$,
$h_{i+1}$, and $h_{i}$ are Chebyshev polynomials, which commute with each
other. Setting

$\tilde{h}_{i}:=h_{i+2}\text{ and }\tilde{h}_{i+2}:=h_{i}\text{ and
}\tilde{h}_{j}:=h_{j}\text{ for }j\not\equiv i,i+2\pmod{k}$

gives a cleanup $(\tilde{h},L)$ of both
$t_{i}\star(t_{i+1}\star(t_{i}\star[f]))$ and
$t_{i+1}\star(t_{i}\star(t_{i+1}\star[f]))$. This argument works exactly the
same way when all three of $h_{i}$, $h_{i+1}$, and $h_{i+2}$ are monomials
inside a $\mathsf{C}$-free cluster.

Since each of the three factors $h_{i}$, $h_{i+1}$, and $h_{i+2}$ swaps with
each of the others in evaluating either
$t_{i}\star(t_{i+1}\star(t_{i}\star[f]))$ or
$t_{i+1}\star(t_{i}\star(t_{i+1}\star[f]))$, at most one of them can be non-
monomial. Applying [8, Lemma 3.37] repeatedly, as in the proof of Proposition
2.146, finishes this proof. ∎

Another consequence of Proposition 2.146 is an analogue of Theorem 2.145: the
number of clusters per period, the kind of clusters, and the presence of gates
at cluster boundaries are invariant under the partial action of
$\operatorname{ASym}_{k}$. The exact location of the gate changes if and only
if the direction of the gate changes. Action by powers of $\phi$ shifts the
whole picture.

######  Proposition 2.150.

Fix $f\in\mathscr{D}_{k}$ and $w\in\operatorname{ASym}_{k}$ with $w\star f=:g$
defined. Then there are boundary lists $\alpha$ and $\beta$ for $f$ and $g$,
respectively, such that for all $j$,

  1. (1)

$\\{\alpha(j),\beta(j)\\}\subseteq\\{i+1,i+\frac{1}{2},i\\}$ for some $i$;

  2. (2)

the $j^{\text{th}}$ clusters of $f$ and $g$ are of the same kind, $\mathsf{C}$
or $\mathsf{C}$-free;

  3. (3)

$f$ has a gate at $\alpha(j)$ if and only if $g$ has a gate at $\beta(j)$;

  4. (4)

if $\alpha(j)=i+1$ and $\beta(j)=i$, then $f$ has a right-to-left gate at
$\alpha(j)$ and $g$ has a right-to-left gate at $\beta(j)$; and vice versa.

If $h=\phi^{n}\star f$ for some $n\in\mathbb{Z}$, there are boundary lists
$\alpha$ and $\beta$ for $f$ and $h$, respectively, such that
$\beta(j)=\alpha(j+n)$ for all $j$; and corresponding clusters and cluster
boundaries are exactly the same.

###### Proof.

To prove the first part, we apply Theorem 2.145 and Proposition 2.146, and
induct on the length of a word in the generators representing $w$. The way the
direction of gates changes in Theorem 2.145 and Proposition 2.146 prevents the
cluster boundaries from drifting by more than $1$.

The second part about $\phi^{n}\star f$ is immediate. ∎

######  Definition 2.151.

With the setup in Proposition 2.150, we say that _the cluster boundary
$\beta(j)$ comes from the cluster boundary $\alpha(j)$ via $w\star f$._ When
$f$ and $w$ are clear from context, we simply say that $\alpha(j)$ _becomes_
$\beta(j)$, or that $\alpha(j)$ and $\beta(j)$ are _corresponding boundaries_.

######  Remark 2.152.

It is possible for the same $i$ to be a cluster boundary of both $f$ and
$g=w\star f$, but not correspond to itself: if $f$ has a one-factor cluster
$f_{i}$ with gates in the same direction on both sides, after a quadratic
passes through these gates, both boundaries $\alpha(j)=i$ and
$\alpha(j+1)=i+1$ move one step to, say, $\beta(j)=i+1$ and $\beta(j+1)=i+2$;
but $\alpha(j+1)=i+1$ and $\beta(j)=i+1$ are not corresponding boundaries!

######  Proposition 2.153.

In a clustering, a cluster boundary without a gate is a wall.

###### Proof.

Proposition 2.150 shows that if $f$ has a cluster boundary at $i$ with no
gate, then for every $w\in\operatorname{ASym}_{k}$, if defined, $w\star f$ has
a cluster boundary at $i$ with no gate. By Lemma 2.127, $t_{i}\star(w\star f)$
is never defined.

To finish verifying that $f$ has a wall at $i$, we must show that
$\epsilon_{p}\star f$ and $\epsilon^{-1}_{p}\star f$ are not defined (see
Definition 2.19).

Suppose toward contradiction that $\epsilon_{p}\star f$ (respectively,
$\epsilon^{-1}_{p}\star f$) is defined, so, up to linear equivalence, we may
assume that each $f_{i}$ is a Ritt polynomial with in-degree (respectively,
out-degree) at least $p$.

If none of the $f_{i}$ are type $\mathsf{C}$, this gives a cleanup of the
empty (pre)clustering of $f$. In particular, $f$ has no cluster boundaries.

Otherwise, $p$ must be $2$, because type $\mathsf{C}$ Ritt polynomials do not
have other in-degrees or out-degrees. To build a cleanup for $f$, we must
convert those $f_{i}$ which are type $\mathsf{C}$ into actual Chebyshev
polynomials. The linear factors used for this are exactly the ones giving one-
way gates at cluster boundaries. For more details see [8, Remark 3.14 and
Theorem 3.15]. ∎

It follows from Propositions 2.52 and 2.153 that Theorem 1.3 holds when there
is gateless cluster boundary.

######  Corollary 2.154.

Theorem 1.3 hold for any polynomial $P$ whose long decomposition has a cluster
boundary with no gate.

####  2.3.6. Wandering quadratics

We have already shown that if a long decomposition has no walls, then every
cluster boundary has a one-way gate. In this subsection we will show that each
of these one-way gates is “owned by” a unique “wandering quadratic”. This
precise characterization will give us enough control to prove Theorem 1.3 in
the absence of walls.

We now return to a more detailed analysis of the interaction of the action of
$\operatorname{ASym}_{k}$ with boundaries and gates. We begin by keeping track
of corresponding factors of $f$ and $w\star f$ the same way that Definition
2.151 keeps track of corresponding gates.

######  Definition 2.155.

Suppose that $w\star f=g$ for some $k$-long decompositions$f$ and $g$ and some
$w\in\operatorname{ASym}_{k}$. We say that _a factor $g_{b}$ comes from the
factor $f_{a}$ via $w\star f=g$_ if the permutation $\pi(w)$ of Remark 2.33
takes the integer $a$ to $b$. Alternatively, we say that the factor $f_{a}$
_becomes_ $g_{b}$ via $w\star f$, or that $f_{a}$ and $g_{b}$ are
_corresponding factors_.

A computationally useful equivalent to Definition 2.155 may be given
inductively.

######  Remark 2.156.

For $k$-long decompositions$f$ and $g=t_{i}\star f$, a factor $g_{b}$ comes
from the factor $f_{a}$ via $t_{i}\star f$ if $b=a\notin\\{i,i+1\\}$ or
$\\{a,b\\}=\\{i,i+1\\}$.

For an element $w\in\operatorname{ASym}_{k}$ for which $w\star f=g$, a factor
$g_{b}$ come from the factor $f_{a}$ via $w\star f=g$ if there are

  * •

a sequences $\left(w_{i}\right)_{i=1}^{n}$ of generators,
$\\{t_{j}~{}:~{}1\leq j\leq k\\}$,

  * •

a sequence of $k$-long decompositions$\left(H(i)\right)_{i=0}^{n}$, and

  * •

a sequence of factors $\left(h(i)\right)_{i=0}^{n}$

so that

  * •

$w=w_{n}\cdots w_{2}w_{1}$,

  * •

$H(0)=f$,

  * •

$H(m+1)=w_{m+1}\star H(m)$,

  * •

$h(0)=f_{a}$,

  * •

$h(m+1)$ is the factor of $H(m+1)$ which comes from $h(m)$ via $w_{m+1}\star
H(m)=H(m+1)$, and

  * •

$h(n)=g_{b}$.

With the next definition we introduce wandering and loitering quadratics, the
key notions of this section. The word “wandering quadratic” is used in [8] for
a related, though quite different, notion.

######  Definition 2.157.

Fix a $k$-long decomposition$f$ with a non-empty clustering, and let $B$ be
the boundary set of $f$. A quadratic factor $f_{a}$ is a _loitering quadratic
of $f$_ if $a-\frac{1}{2}\in B$.

A quadratic factor $f_{a}$ is a _wandering quadratic of $f$_ if $f_{a}$
becomes a loitering quadratic $g_{b}$ via $w\star f=g$ for some
$w\in\operatorname{ASym}_{k}$.

Let $b^{\prime}$ be the boundary of $f$ corresponding to the boundary
$b-\frac{1}{2}$ of $g$ via $w\star f$ in the sense of Definition 2.151. We say
that the wandering quadratic $f_{a}$ _owns_ the gate that $f$ has at
$b^{\prime}$.

######  Lemma 2.158.

Let $f$ be a long decomposition with at least one quadratic factor and at
least one type-$\mathsf{C}$ factor. If some some clustering of $f$ has an
unowned gate at $a$, then $f$ has a wall at $a$.

###### Proof.

Since $f$ has a quadratic factor, $\epsilon^{\pm 1}_{2}\star f$ is not
defined. Likewise, because $f$ has a type-$\mathsf{C}$ factor,
$\epsilon_{p}^{\pm 1}\star f$ is not defined for odd $p$. Because $f$ has a
cluster boundary with an unowned gate at $a$, $t_{a}\star f$ is not defined.
(See the first paragraph of the proof of Proposition 2.153 for more details.)
That is, $f$ has a wall at $a$. ∎

######  Remark 2.159.

When $f_{a}$ is a loitering quadratic of $f$, that cluster boundary of $f$ is
ambiguous: some clusterings of $f$ have a one-way gate at $a$ and others at
$(a-1)$, so this quadratic could join either of the two clusters.

We shall soon vindicate the last notion by showing that each gate is owned by
at most one wandering quadratic.

######  Lemma 2.160.

Fix a $k$-long decomposition$f$ and a word $w$ in the affine permutation group
such that $w\star f=g$ is defined. Suppose that $g_{a}$ is a loitering
quadratic of $g$, and that it comes from $f_{b}$ via $w\star f$. Then $f_{i}$
is not quadratic for any $i$ between $a$ and $b$, including $a$.

The intuitive idea of the proof is quite simple: one quadratic is near a gate,
and the other is further. As the far quadratic moves to the gate, it will bump
into the near quadratic and stop (since tautological Ritt swaps are not
allowed). The only possible exception would be when the near quadratic crosses
the gate and stops being between the gate and the far quadratic. However, in
that case, when the far quadratic arrives at the gate, the gate will be one-
way the wrong way and the quadratic will not be able to enter the gate.

###### Proof.

What we need to show that if $b>a$, $f_{i}$ is not quadratic for $i=b-1,\ldots
a+1,a$; and if $b<a$, $f_{i}$ is not quadratic for $i=b+1,\ldots a-1,a$. The
proofs of these two statements are identical; we prove the first.

Toward contradiction, let $(f,w,b>c\geq a)$ be a counterexample with $w$
expressed as a product of generators $w=w_{r}\ldots w_{1}$ with the least
possible $r$. That is, $f_{b}$ and $f_{c}$ are quadratic, and the loitering
quadratic $g_{a}$ of $g$ comes from $f_{b}$ via $w\star f$.

For $s=0,1,\ldots r$, let $B(s)$ and $C(s)$ be the places where $f_{b}$ and
$f_{c}$ land via $w_{s}\ldots w_{1}\star f$. So $B(0)=b$ and $C(0)=c$ and
$B(r)=a$. Two quadratic factors cannot Ritt-swap with each other and
$B(0)>C(0)$, so $B(s)>C(s)$ for all $s$. In particular, $a=B(r)>C(r)$ while
$C(0)=c\geq a$. Thus, $C(s)=a$ for some $s<r$.

Let $f^{\prime}:=w_{s}\ldots w_{1}\star f$, let $w^{\prime}:=w_{r}\ldots
w_{s+1}$, and let $b^{\prime}:=B(s)$. Now $w^{\prime}\star f^{\prime}=w\star
f=g$ and the loitering quadratic $g_{a}$ of $g$ comes from
$f^{\prime}_{b^{\prime}}$ via $w^{\prime}\star f^{\prime}$; and
$b^{\prime}=B(s)>C(s)=a$. So $(f^{\prime},w^{\prime},a,b^{\prime})$ is another
counterexample. So the presentation of $w^{\prime}$ in this counterexample
cannot be shorter than that of $w$, so we must have $s=0$ and $w^{\prime}=w$
and $c=a$. Thus, we have

$b=B(0)>C(0)=a=B(r)>C(r)\text{ .}$

######  Claim 2.160.1.

The factors $f_{d}$ are not quadratic for any $d=b-1,\ldots a+1$.

_Proof of Claim:_ Suppose not, and let $D(s)$ be the place where $f_{d}$ lands
via $w_{s}\ldots w_{1}\star f$. So $D(0)=d$, so $B(0)>D(0)>C(0)=a=B(r)>D(r)$.
Thus, for some $s\neq 0,r$, we have $B(s)>D(s)=a$. Again, let
$f^{\prime}:=w_{s}\ldots w_{1}\star f$, let $w^{\prime}:=w_{r}\ldots w_{s+1}$,
and let $b^{\prime}:=B(s)$. As before, $(f^{\prime},w^{\prime},b^{\prime},a)$
is another counterexample. But since $s\neq 0$, the presentation of
$w^{\prime}$ is strictly shorter than that of $w$, which is a contradiction.
$\maltese$

######  Claim 2.160.2.

For all $s>0$, we have $a>C(s)$; for all $s<r$, we have $B(s)>a$.

_Proof of Claim:_ Since $a>C(r)$, if $C(s)\geq a$ for some $s>0$, then
$C(s^{\prime})=a$ for some $s^{\prime}$ with $s<s^{\prime}<r$. Again,
$f^{\prime}:=w_{s^{\prime}}\ldots w_{1}\star f$ and $w^{\prime}:=w_{r}\ldots
w_{s^{\prime}+1}$ and $b^{\prime}:=B(s^{\prime})$ give a counterexample, with
$w^{\prime}$ having a shorter presentation than that of $w$, a contradiction.

Similarly, if $a\geq B(s)$ for some $s<r$, then $a=B(s^{\prime})$ for some
$s^{\prime}<s$ because $B(0)>a$. Now $(f,u,b,a)$ is another counterexample,
with $u=w_{s^{\prime}}\ldots w_{1}$ having a strictly shorter presentation
than that of $w$, which is a contradiction. $\maltese$

Claim 2.160.2 implies that $w_{1}=t_{a-1}$ and $w_{r}=t_{a}$.

######  Claim 2.160.3.

For all $s\neq 0,r$, the factor of $h_{a}$ of $h:=w_{s}\ldots w_{1}\star f$ is
not quadratic.

_Proof of Claim:_ From Claim 2.160.2, we have $B(s)>a>C(s)$. Let $f_{d}$ be
the factor of $f$ that becomes $h_{a}$ via $w_{s}\ldots w_{1}\star f$. Then
$B(0)>d>C(0)$, contradicting Claim 2.160.1. $\maltese$

######  Claim 2.160.4.

For all $s$ with $0<s<r$, the $k$-long decomposition$h:=w_{s}\ldots w_{1}\star
f=w_{s+1}\ldots w_{r}\star g$ admits a clustering with a left-to-right gate at
$(a-1)$.

_Proof of Claim:_ We induct backwards on $s$, from $r-1$ to $1$. For the base
case $s=r-1$, we are looking at $t_{a}\star g$ and $g_{a}$ is a loitering
quadratic of $g$. There is a clustering of $g$ with a cluster boundary at
$(a-1)$ and a left-to-right gate at that boundary. For that clustering,
$t_{a}\star g$ is an intra-cluster swap that does not change the locations and
directions of gates.

For the inductive step, we are looking at $w_{s}\star h$ for $h=w_{s+1}\ldots
w_{r}\star g$. By the inductive hypothesis, some clustering of $h$ has a
cluster boundary at $(a-1)$ and a left-to-right gate at that boundary. By
Claim 2.160.3, $h_{a}$ is not quadratic; so every clustering of $h$ has a
cluster boundary at $(a-1)$ and a left-to-right gate at that boundary. By
Proposition 2.146, this means that $t_{a-1}\star h$ is not defined, so
$w_{s}=t_{i}$ for some $i\neq a$. By the same Proposition 2.146, it follows
that $w_{s}\star h$ also admits a clustering with a left-to-right gate at
$(a-1)$.

Claim 2.160.4 is now proved. $\maltese$

So for $s=1$ we have that $h=t_{a-1}\star f$ has a left-to-right gate at
$(a-1)$ and no quadratic at $a$. But then $t_{a-1}\star h$ is not defined,
contradicting $t_{a-1}\star h=f$.

∎

######  Corollary 2.161.

Each gate is owned by at most one wandering quadratic.

###### Proof.

Suppose that quadratic factors $f_{a}$ and $f_{b}$ of $f$ both own the gate at
$c$. So there is some $u\in\operatorname{ASym}_{k}$ and a gate at $a^{\prime}$
of $g:=u\star f$ corresponding to the gate of $f$ at $c$ such that
$g_{a^{\prime}}$ comes from $f_{a}$ via $u\star f$. Similarly, there is some
$v\in\operatorname{ASym}_{k}$ and a gate at $b^{\prime\prime}$ of $h:=v\star
f$ corresponding to the gate of $f$ at $c$ such that $h_{b^{\prime\prime}}$
comes from $f_{a}$ via $v\star f$.

Now for $w:=vu^{-1}$ we have $w\star g=h$ and the gate of $h$ at
$b^{\prime\prime}$ corresponds to the gate of $g$ at $a^{\prime}$ via $w\star
g$. Both gates are occupied, so Proposition 2.150 tells us that
$a^{\prime}=b^{\prime\prime}$.

Let $b^{\prime}$ be the index for which $g_{b^{\prime}}$ comes from $f_{b}$
via $u\star f$. Now $h_{b^{\prime\prime}}$ comes from $g_{b^{\prime}}$ via
$w\star g$, but $g_{b^{\prime\prime}}=g_{a^{\prime}}$ is quadratic. This
contradicts Lemma 2.160 unless $a^{\prime}=b^{\prime}$; in which case $a=b$,
and the two owners of the same gate turn out to be the same person as wanted.
∎

######  Corollary 2.162.

If a wandering quadratic $f_{a}$ owns the gate at $b$, then $|b-a|\leq k$.

###### Proof.

If $b>a+k$, the factor $f_{a+k}$, which is quadratic because of the
$k$-periodicity of $f$, contradicts Lemma 2.160. ∎

We next show that a wandering quadratic can always move to a gate it owns as
directly as possible, that is, via a single transit in the sense of Definition
2.38.

######  Lemma 2.163.

Suppose that a wandering quadratic $f_{a}$ of a long decomposition $f$ owns
the gate at $b$. Then there is a transit $u$ with $g_{b}$ a loitering
quadratic coming from $f_{a}$ via $u\star f=g$.

###### Proof.

We work out the case where $a<b$; the case where $a>b$ is identical; and the
empty word $u$ works for the case $a=b$.

Let $w$ be a reduced word witnessing that $f_{a}$ owns the gate at $b$,
shortest among such words. That is, $w\star f=h$ is defined and $h_{b}$ is a
loitering quadratic of $h$ that comes from $f_{a}$ via $w\star f$; and
whenever the same happens for some other $w^{\prime}$ and $h^{\prime}$ (with
the same $b$!), $w^{\prime}$ is no shorter than $w$.

We first show that $t_{b}$ does not occur in $w$. Suppose toward contradiction
that $w=vt_{b}w^{\prime}$ for some words $v$ and $w^{\prime}$ with
$w^{\prime}$ not containing $t_{b}$. Let $h^{\prime}:=w^{\prime}\star f$. Now
$t_{b}\star h^{\prime}$ is defined, so $h^{\prime}_{b}$ must be a quadratic.
Since only one quadratic owns this gate at $b$, $h^{\prime}_{b}$ corresponds
to $f_{a}$ via $w^{\prime}\star f=h^{\prime}$ contradicting minimality of the
length of $w$.

The subgroup of $\operatorname{ASym}_{k}$ generated by $\\{t_{i}~{}:~{}i\neq
b\\}$ is an isomorphic copy of $\operatorname{Sym}_{k}$. Thus, we may present
$w$ in second canonical form with respect to $b>a+1>a>b-k$ (see Remark 2.39)
as $w=usw_{3}w_{2}w_{1}$ where

  * •

$w_{1}$ is a reduced word in $t_{i}$ with $b-k<i<a-1$, permuting factors in
the “right chunk” $f_{(a,b-k)}$;

  * •

$w_{2}$ is empty: it permutes factors in the one-factor middle chunk;

  * •

$w_{3}$ is a reduced word in $t_{i}$ with $a<i<b$, permuting factors in the
“left chunk” $f_{[b,a)}$;

  * •

$s=t_{(c,a]}$ is the transit moving the wandering quadratic as we want; and

  * •

$u$ is the rest of the word $v$ in the second canonical form, moving factors
from the right chunk leftward.

Since $u$ does not move the wandering quadratic, $s$ must get it all the way
to the gate at $b$ where it ends up in $w\star f$; so we have $c=b$. Now
$sw_{3}w_{2}w_{1}$ already moves the wandering quadratic $f_{a}$ to the gate
at $b$. Thus, by the minimality of the length of $w$, the word $u$ is empty.
So now we have $w=sw_{3}w_{1}$. Since $sw_{3}$ and $w_{1}$ act on disjoint
chunks of factors, they commute. So, $w=w_{1}sw_{3}$. By the minimality of the
length of $w$, the word $w_{1}$ is empty and $w=sw_{3}$. Using Lemma 2.43, we
get $w=\widehat{w_{3}}s$, which, by the minimality of the length of $w$, gives
$w=s$ as wanted. ∎

We get the following immediate corollary.

######  Corollary 2.164.

If a wandering quadratic $f_{a}$ owns the gate at $b$, then all gates of $f$
between $a$ and $b$ are are in the direction from $a$ to $b$.

######  Lemma 2.165.

Fix a reduced word $u$ and long decompositions $f$ and $g$ with $u\star f=g$.
If both $f_{b}$ and $g_{b}$ are loitering quadratics, then $h_{b}$ is a
loitering quadratic whenever $u=u_{2}u_{1}$ as words, and $h=u_{1}\star f$.

###### Proof.

We induct on the length of $u$. The base cases where the length of $u$ is $0$
or $1$ are trivial. Assuming that the length of $u$ is at least $2$, we may
write $u=t_{y}vt_{x}$ for some $x,y\in\mathbb{Z}$ and some, possibly empty,
word $v$.

Suppose that $u$ is the shortest counterexample; then it is a counterexample
in the strongest sense possible:

  * $(\spadesuit)$

for every way of writing $u$ as $u_{2}u_{1}$ with non-empty $u_{1}$ and
$u_{2}$, the $b$th factor of $u_{1}\star f$ is not a loitering quadratic.

Otherwise, one of $u_{2}$ and $u_{1}$ is a shorter counterexample. In
particular, $t_{x}$ must move the loitering quadratic $f_{b}$. We work out the
case where $x=b$; the other case where $x=b-1$ is symmetric.

######  Claim 2.165.1.

For any words $v_{1}$, $v_{2}$ with $v=v_{2}v_{1}$, the long decomposition
$v_{1}t_{x}\star f$ has a one-way, left-to-right, unoccupied gate at $(b-1)$.

_Proof of Claim:_ If the gate of $v_{1}t_{x}\star f$ corresponding to the gate
of $f$ at $b$ is occupied, we contradict $(\spadesuit)$. Before the gate can
move or change direction, it must have been occupied. $\maltese$

So $vt_{x}\star f$ has a one-way, left-to-right, unoccupied gate at $(b-1)$;
but $u\star f=t_{y}\star(vt_{x}\star f)$ has a loitering quadratic at $b$. It
follows that $y=b$, and $u=t_{b}vt_{b}$, and

  * $(\clubsuit)$

the $(b+1)^{\text{st}}$ factor of $vt_{b}\star f$ is a wandering quadratic.

The Claim also implies that $t_{b-1}\star(v_{1}t_{x}\star f)$ is not defined
for any such $v_{1}$, and so $t_{b-1}$ does not occur in $v$.

Thus, $v$ lies in a copy of $\operatorname{Sym}_{k}$, so we may replace $v$ by
its first canonical form $v=s_{0}s_{Q}w$ where $w$ is a word in $t_{i}$ with
$i\neq b-1,b,b+1$, permuting the factors in the big chunk on the left that
consists of all the factors except the $b^{\text{th}}$ and the
$(b+1)^{\text{st}}$; and $s_{Q}$ is a right-to-left transit move the wandering
quadratic from its starting $(b+1)^{\text{st}}$ spot; and $s_{0}$ is a right-
to-left transit moving the $b^{\text{th}}$ factor of $t_{b}\star f$ left. But
we know from $(\clubsuit)$ that the quadratic ends up back in the
$(b+1)^{\text{st}}$ spot! So, there are only two possibilities for $s_{0}$ and
$s_{Q}$.

Case 1: If $s_{Q}$ is empty, then $s_{0}$ must also be empty. Since $w$
commutes with $t_{b}$, we now have

$u=t_{b}vt_{b}\simeq t_{b}s_{0}s_{Q}wt_{b}=t_{b}wt_{b}\simeq wt_{b}t_{b}$

where $\simeq$ means “reducible of each other” so same length. This
contradicts $u$ being reduced.

Case 2: If $s_{Q}$ is non-empty, it still can only move the wandering
quadratic one step, so $s_{Q}=t_{b+1}$. Now $s_{0}$ must move its factor past
the quadratic, so at least two steps: $s_{0}=s_{1}t_{b+1}t_{b}$. So now

$u=t_{b}vt_{b}\simeq
t_{b}s_{0}s_{Q}wt_{b}=t_{b}(s_{1}t_{b+1}t_{b})t_{b+1}wt_{b}\simeq
t_{b}s_{1}\mathbf{t_{b}t_{b+1}t_{b}}wt_{b}\simeq
t_{b}s_{1}t_{b}t_{b+1}\mathbf{wt_{b}t_{b}}$

again, contradicting $u$ being reduced. (In the displayed equations, the two
boldface expressions come from the braid relation $t_{b+1}t_{b}t_{b+1}\simeq
t_{b}t_{b+1}t_{b}$ and the commutation of $w$ with $t_{b}$.)

In both cases, we have obtained the desired contradiction. ∎

From Lemma 2.165 we immediately obtain the following useful corollary.

######  Corollary 2.166.

Fix a reduced word $u$ and long decompositions $f$ and $g$ with $u\star f=g$.
If both $f_{b}$ and $g_{b}$ are loitering quadratics, then $t_{b}$ and
$t_{b-1}$ do not occur in $u$.

######  Definition 2.167.

A long decomposition f is _lazy_ is all wandering quadratics of $f$ are
loitering.

######  Lemma 2.168.

If $g$ and $u\star g$ are both lazy and the same gates are occupied by
wandering quadratics in both, then $u=u_{r}\ldots u_{1}$ where $u_{i}$
permutes factors in the $i^{\text{th}}$ cluster (with respect to some listing
of the clusters) and does not move any wandering quadratic in that cluster.

###### Proof.

Fix a reduced presentation $w$ of $u$. By Corollary 2.166, whenever $g$ has an
occupied gate at $b$, neither $t_{b}$ nor $t_{b-1}$ occur in $w$. Furthermore,
by Lemma 2.165 and Corollary 2.166, whenever $g$ has an unoccupied gate at
$a$, the gate remains unoccupied, so $t_{a}$ does not occur in $w$.
Intracluster swaps in different clusters commute with each other, and so they
can be collected as described. ∎

######  Proposition 2.169.

Let $f$ be a lazy long decomposition with $r$ clusters and $p$ wandering
quadratics per period, and suppose that $w\star f$ is also lazy, for some
$w\in\operatorname{ASym}_{k}$. Then $w\star f$ may be expressed as

$w\star f=s_{p}\ldots s_{2}s_{1}u_{r}\ldots u_{2}u_{1}\star f$

where

  * •

$u_{j}$ permutes factors in the $j$th cluster (with respect to some listing of
the clusters) and

  * •

$s_{i}$ is a transit that moves the $i$th wandering quadratic (again with
respect to some listing of the wandering quadratics) from one gate to another.

###### Proof.

We are actually going to obtain a slightly different form $u_{r}\ldots
u_{2}u_{1}s_{p}\ldots s_{2}s_{1}$ where transits happen first and intracluster
swaps happen second. The stated result follows from Lemma 2.43, or by applying
the proved result to $w^{-1}$.

We induct on the number of loitering quadratics of $f$ moved to a different
gate by $w\star f$. The base case where none are moved is Lemma 2.168, with
all $s_{j}$ empty.

Now suppose that a wandering quadratic $f_{a}$ of $f$ is moved to $g_{b}$ via
$w\star f=g$. Applying Lemma 2.163 produces a transit $s$, a word
$w^{\prime}:=ws^{-1}$, and a decomposition $f^{\prime}:=s\star f$ with the
factor $f^{\prime}_{b}$ being a loitering quadratic of $f^{\prime}$, and all
other loitering quadratics of $f$ unmoved.

Now $w^{\prime}\star f^{\prime}=g$, both $f^{\prime}$ and $g$ are lazy, and
one more loitering quadratic stays put in $w^{\prime}\star f^{\prime}=g$ as
compared to $w\star f=g$. Thus, by inductive hypothesis, we may express
$w^{\prime}$ as desired; and then $w=sw^{\prime}$ is also of the requisite
form.

∎

######  Proposition 2.170.

For a long decomposition $f$ with $r$ clusters and $p$ wandering quadratics
per period, and for any $w\in\operatorname{ASym}_{k}$, $w\star f$ may be
expressed as

$w\star f=v_{in}s_{p}\ldots s_{2}s_{1}u_{r}\ldots u_{2}u_{1}v_{out}\star f$

where

  * •

$v_{out}$ moves all wandering quadratics to a nearest owned gate, via
transits, so that $v_{out}\star f$ is lazy,

  * •

$u_{j}$ permutes factors in the $j$th cluster (with respect to some listing of
the clusters),

  * •

$s_{i}$ is a transit that moves the $i$th wandering quadratic (again with
respect to some listing of the wandering quadratics) from one gate to another,
and

  * •

$v_{in}$ moves some wandering quadratics from a gate into clusters, via
transits.

###### Proof.

Lemma 2.163 gives the transits making up $v_{in}$ and $v_{out}$. Apply
Proposition 2.169 to the long decomposition $v_{out}\star f$ and
$v_{in}^{-1}wv_{out}^{-1}\in\operatorname{ASym}_{k}$ to obtain the $u_{j}$’s
and $s_{i}$’s. ∎

######  Remark 2.171.

  1. (1)

$s_{j}$ and $u_{j}$ can be done in any order. See Lemma 2.43.

  2. (2)

All intermediate decompositions between $s_{p}\ldots s_{2}s_{1}u_{r}\ldots
u_{2}u_{1}v_{out}\star f$ and $v_{out}\star f$ are lazy.

  3. (3)

In constructing the transits in $v_{out}$ and $v_{in}$, if a particular
wandering quadratic $f_{i}$ owns the gates at both sides of the cluster it is
in, we are free to choose to move this $f_{i}$ to either one of those gates.

We proceed to complete the proof of Theorem 1.3 under the hypothesis that a
long decomposition of the polynomial $P$ admits a non-empty clustering. With
the results we have already proven, this reduces to proving Theorem 1.3 under
much stronger hypotheses on such a clustering.

######  Proposition 2.172.

Let $f$ be a long decomposition admitting a non-empty clustering with at least
one $\mathsf{C}$ cluster and only one-way gates all of which are owned by some
wandering quadratic. If for some $\gamma\in\operatorname{ST}^{+}_{k}$, we have
$\gamma\star f=f^{\tau}$, then there are $\alpha$ and $\beta$ in
$\operatorname{Sym}_{k}$ such that $\beta\phi^{N}\alpha\star f=f^{\tau}$
encodes the same skew-invariant curve. Thus, that curve is a skew-twist.

###### Proof.

Since we have at least on type $\mathsf{C}$ factor, $\epsilon_{p}^{\pm 1}\star
f$ is not defined for any odd $p$. Since gates are owns, $f$ must have at
least one quadratic factor; so, $\epsilon_{2}^{\pm 1}\star f$ is also
undefined. Thus, $\gamma\in\operatorname{ST}_{k}$ and may be expressed as
$\gamma=\phi^{N}w$ for some $N\in\mathbb{Z}$ and
$w\in\operatorname{ASym}_{k}$. We now have $\phi^{N}w\star f=f^{\tau}$

The following claim identifies the two cases we will consider.

######  Claim 2.172.1.

One of the following holds

  * $\clubsuit$

Applying Proposition 2.170 to $w\star f$, we may take
$v_{out}\in\operatorname{Sym}_{k}$.

  * $\spadesuit$

The long decomposition $f$ does not have a cluster boundary at $k$ and
$f_{k+1}$ and $f_{k}$ are not loitering quadratics. The cluster $C_{bad}$ of
$f$ containing $f_{k+1}$ and $f_{k}$ also contains a wandering quadratic
$f_{a}$ which owns exactly one of the gates on the sides of this cluster. If
$f_{a}$ owns the gate on the left of this cluster, $k\geq a$; and if $f_{a}$
owns the gate on the right of this cluster, $a\geq k+1$.

_Proof of Claim:_ The only reason that $\clubsuit$ would fail is that
$v_{out}$ contains $t_{k}$. This cannot happen if either $f_{k+1}$ or $f_{k}$
is a loitering quadratic of $f$, because such a loitering quadratic is not
moved by $v_{out}$.

Consider the situation were the transit $s$ in $v_{out}$ containing $t_{k}$ is
left-to-right; the other one is analogous. At some stage, this transit $s$
takes the wandering quadratic from the $(k+1)^{\text{st}}$ position to the
$k^{\text{th}}$ one. If $f$ had a cluster boundary at $k$, the wandering
quadratic would already be loitering when it is in the $(k+1)^{\text{st}}$