# Skew-invariant curves and the algebraic independence of Mahler functions

Alice Medvedev<EMAIL_ADDRESS>Signal Fox
175 Varick St., 2nd Floor
New York, NY 10014
USA  ,  Khoa D. Nguyen<EMAIL_ADDRESS>University of Calgary. MS 542
2500 University Drive NW
Calgary, AB T2N 4T4
Canada  and  Thomas Scanlon<EMAIL_ADDRESS>University of
California, Berkeley
Department of Mathematics
Evans Hall
Berkeley, CA 94720-3840
USA

###### Abstract.

For $p\in\mathbb{Q}_{+}\smallsetminus\\{1\\}$ a positive rational number
different from one, we say that the Puisseux series
$f\in\mathbb{C}((t))^{\text{alg}}$ is $p$-Mahler of non-exceptional polynomial
type if there is a polynomial $P\in\mathbb{C}(t)^{\text{alg}}[X]$ of degree at
least two which is not conjugate to either a monomial or to plus or minus a
Chebyshev polynomial for which the equation $f(t^{p})=P(f(t))$ holds. We show
that if $p$ and $q$ are multiplicatively independent and $f$ and $g$ are
$p$-Mahler and $q$-Mahler, respectively, of non-exceptional polynomial type,
then $f$ and $g$ are algebraically independent over $\mathbb{C}(t)$. This
theorem is proven as a consequence of a more general theorem that if $f$ is
$p$-Mahler of non-exceptional polynomial type, and $g_{1},\ldots,g_{n}$ each
satisfy some difference equation with respect to the substitution $t\mapsto
t^{q}$, then $f$ is algebraically independent from $g_{1},\ldots,g_{n}$. These
theorems are themselves consequences of a refined classification of skew-
invariant curves for split polynomial dynamical systems on $\mathbb{A}^{2}$.

##  1\. Introduction

Mahler introduced the class of functions which now bear his name in [6] with
the aim of systematically deducing transcendence, and more generally algebraic
independence, of special values of certain transcendental functions satisfying
functional equations. Specifically, for a positive rational number $q$ not
equal to $1$ we say that the formal Puissuex series
$f\in\mathbb{C}((t))^{\text{alg}}$ is $q$-Mahler of polynomial type if there
is a polynomial $Q(X)\in\mathbb{C}(t)^{\text{alg}}[X]$ of degree at least two
for which $f(t^{q})=Q(f(t))$.111Mahler usually considers the case that $q$ is
the reciprocal of a positive integer. The greater generality adds no
complexity to our arguments and permits us to make suitable reductions
throughout the course of our proof. Functions satisfying other functional
equations appear in the literature under the name of Mahler functions.
Notably, often, as in [10], $Q$ is allowed to be a rational function in which
case we might say that $f$ is $q$-Mahler of rational type. In other works
(see, for instance [1, 14]) $q$-Mahler functions are those $f$ for which
$f(t^{q^{j}})$ (for $j\in\mathbb{N}$) are linearly dependent over
$\mathbb{C}(t)$. In this case, we might say that $f$ is $q$-Mahler of linear
type.

We address the problem of determining the possible algebraic relations between
$p$-Mahler and $q$-Mahler functions for multiplicatively independent $p$ and
$q$. Versions of this problem have been studied. For example, Zannier shows in
[15] that a transcendental function cannot be simultaneously $p$-Mahler and
$q$-Mahler of polynomial type when $p$ and $q$ are multiplicatively
independent integers and the polynomials have coefficients in $\mathbb{C}[t]$.
Adamczewski and Bell [1] prove analogous results when “polynomial type” is
replaced by “linear type”. Our main theorem is that if $p$ and $q$ are
multiplicatively independent positive rational numbers and $f$ and $g$ are
$p$-Mahler and $q$-Mahler, respectively, of _non-exceptional_ polynomial type,
then $f$ and $g$ are algebraically independent over $\mathbb{C}(t)$.

To state this theorem precisely we should recall the notion of exceptional
polynomials.

There are three basic kinds of exceptional polynomials: linear polynomials,
monomials, and (scalings of) Chebyshev polynomials. 222 For each positive
integer $N$ there is a unique monic polynomial $C_{N}$ which satisfies the
functional equation $C_{N}(X+\frac{1}{X})=X^{N}+\frac{1}{X^{N}}$. For us, a
Chebyshev polynomial is a polynomial of the form $C_{N}$ for some $N\geq 2$. A
polynomial $P$ is exceptional if it is linear or $P$ is conjugate 333Usually,
for two polynomials $P$ and $Q$ we say that $P$ and $Q$ are conjugate if there
is a linear polynomial $L$ with $P\circ L=L\circ Q$. For the questions treated
in this paper we require the notion of _skew-conjugacy_ relative to a field
automorphism $\sigma$. The polynomials $P$ and $Q$ are skew-conjugate if there
is a linear polynomial $L$ for which $P\circ L=L^{\sigma}\circ Q$ where if
$L(x)=ax+b$, then $L^{\sigma}=\sigma(a)x+\sigma(b)$. If $\sigma$ acts
trivially, then the usual notion of conjugacy agrees with skew-conjugacy. See
Definition 2.4 for details.  to $X^{N}$ or to $\pm C_{N}$ where
$N=\operatorname{deg}(P)$.

Otherwise, $P$ is _non-exceptional_. 444In [8] the non-exceptional polynomials
are called “disintegrated”. For $p\in\mathbb{Q}_{+}\smallsetminus\\{1\\}$ we
say that $f\in\mathbb{C}((t))^{\text{alg}}$ is $p$-Mahler of non-exceptional
polynomial type if there is a non-exceptional polynomial
$P\in\mathbb{C}(t)^{\text{alg}}[X]$ for which the equation $f(t^{p})=P(f(t))$
holds. Our main theorem takes the following form.

######  Theorem 1.1.

Let $p$ and $q$ be two multiplicatively independent positive rational numbers,
$f\in\mathbb{C}((t))^{\text{alg}}$ and $g\in\mathbb{C}((t))^{\text{alg}}$ be
two formal Puisseux series over the complex numbers, and suppose that $f$ and
$g$ are $p$-Mahler and $q$-Mahler, respectively, of non-exceptional polynomial
type. Then $f$ and $g$ are algebraically independent over $\mathbb{C}(t)$.

The hypotheses in Theorem 1.1 are much stronger than we actually require and
the conclusion is much weaker than what prove. Indeed, it suffices to assume
merely that $f$ is $p$-Mahler of non-exceptional polynomial type and that $g$
satisfies some difference equation with respect to the substitution $t\mapsto
t^{q}$. In fact, our proof Theorem 1.1 is algebraic and applies in a much
wider context.

The substitutions $t\mapsto t^{p}$ and $t\mapsto t^{q}$ induce commuting field
automorphisms $\sigma$ and $\tau$ of the fields of algebraic functions
$\mathbb{C}(t)^{\text{alg}}$ and of formal Laurent series. Moreover, the
multiplicative independence of $p$ and $q$ imply that $\sigma$ and $\tau$ are
independent in the sense that if $h$ is a non-constant formal Puisseux series
and $\left(m,n\right)\neq\left(0,0\right)$, then $\sigma^{m}\tau^{n}(h)\neq
h$. To say that $f$ is a $p$-Mahler of non-exceptional polynomial type is
simply to say that there is a non-exceptional polynomial
$P\in\mathbb{C}(t)^{\text{alg}}[X]$ with $\sigma(f)=P(f)$. Abstracting this
situation, we formulate our more general theorem on algebraic independence.

######  Theorem 1.2.

Let $C\subseteq K\subseteq L$ be a tower of algebraically closed fields of
characteristic zero. Suppose that $\sigma$ and $\tau$ are commuting
automorphisms of $L$ which preserve $K$ and have $C$ as their common fixed
field. Suppose moreover that $\sigma$ and $\tau$ are independent in the sense
that if $a\in L\smallsetminus C$ and
$\left(m,n\right)\in\mathbb{Z}^{2}\smallsetminus\\{\left(0,0\right)\\}$, then
$\sigma^{m}\tau^{n}(a)\neq a$.

We make two additional hypotheses about difference equations. First, for any
automorphism $\rho$ in the group generated by $\sigma$ and $\tau$ and any
$c\in C$, there are no nonconstant solutions to the equation $\rho(x)=cx$ in
$L$. Secondly, for $\rho$ and $\mu$ independent automorphisms in the group
generated by $\sigma$ and $\tau$, $M\in\mathbb{Z}_{+}$ a positive integer, and
$a\in L^{\times}$ an element of $L$ satisfying
$\rho(\frac{\mu(a)}{a})=(\frac{\mu(a)}{a})^{M}$, then $a\in K$.

Suppose that $f\in L$ satisfies an equation of the form $\sigma(f)=P(f)$ for
some non-exceptional polynomial $P\in K[X]$ and that $g_{1},\ldots,g_{n}\in L$
each satisfy non-trivial $\tau$-difference equations over $K$. That is, for
some $r\in\mathbb{N}$ there are non-zero polynomials
$Q_{i}(X_{0},X_{1},\ldots,X_{r})\in K[X_{0},\ldots,X_{r}]$ so that
$Q_{i}(g_{i},\tau(g_{i}),\ldots,\tau^{r}(g_{i}))=0$ for $1\leq i\leq n$. Then
$f$ is algebraically independent from $g_{1},\ldots,g_{n}$ over $K$.

Recently, Adamczewski, Dreyfus, Hardouin, and Wibmer [2] proved a similar
algebraic independence statement under the hypothesis that $f$ satisfies a
linear $\sigma$-difference equation.

Our proof of Theorem 1.2 makes use of the full strength of the
characterization of skew-invariant curves from [8]. Most uses of [8] to date
invoke merely the characterization of invariant curves for dynamical systems
of the form $\left(x,y\right)\mapsto\left(P(x),P(y)\right)$ where $P$. For
example, the second author of the present paper obtained in [9] a result on
the algebraic independence of the analytic conjugacies associated to Mahler
functions by using just the characterization of invariant varieties. For
invariant varieties, the relevant description may also be obtained using the
theory of orbifolds as shown by Pakovich [11] and admits a generalization to
the case where $P$ is a rational function [12]. For the application to our
problem on the algebraic independence of Mahler functions, we need a precise
description of the possible skew-invariant curves for maps of the form
$\left(x,y\right)\mapsto\left(P(x),P^{\tau}(y)\right)$ where $P$ is a non-
exceptional polynomial and $\tau:K\to K$ is any field automorphism. The main
theorem of [8] describes these combinatorially and in the present paper we
push that characterization further, showing in the language of [8], that these
skew-invariant curves are given by skew-twists.

Let us give the requisite definitions and state the precise form of our
theorem on skew-invariant curves.

A difference field $(K,\sigma)$ is a field $K$ given together with a
distinguished field automorphism $\sigma:K\to K$. For any object $X$ defined
over $K$, we write $X^{\sigma}$ for the transform of $X$ over $K$. For
example, for a polynomial $P\in K[X]$, $P^{\sigma}$ is the polynomial obtained
by applying $\sigma$ to the coefficients of $P$. Given an algebraic variety
$X$ over $K$ and a regular map $f:X\to X^{\sigma}$, we say that the subvariety
$Y\subseteq X$ is _skew-invariant_ if the restriction of $f$ to $Y$ maps $Y$
to $Y^{\sigma}$.

Given two one-variable polynomials $P,Q\in K[X]$, we say that
$Y\subseteq\mathbb{A}^{2}_{K}$ is a skew-twist curve for $(P,Q)$ if there are
polynomials $\alpha$ and $\beta$ and an integer $n$ so that
$P=\beta\circ\alpha$, $Q=\alpha^{\sigma^{n+1}}\circ\beta^{\sigma^{n}}$, and

  * •

either $n\geq 0$ and $Y$ is defined by $y=\alpha^{\sigma^{n}}\circ
P^{\sigma^{n-1}}\circ\cdots\circ P^{\sigma}\circ P(x)$

  * •

or $n\leq-1$ and $Y$ is defined by $x=\beta^{\sigma^{-1}}\circ
Q^{\sigma^{-n-2}}\circ Q^{\sigma^{-n-3}}\circ\cdots\circ Q(y)$; note that when
$n=-1$, this simply mean $x=\beta^{\sigma^{-1}}(y)$.

With these definitions in place we may state our theorem on skew-invariant
curves.

######  Theorem 1.3.

Let $(K,\sigma)$ be a difference field of characteristic zero and $\tau:K\to
K$ be a field automorphism commuting with $\sigma$. Let $P\in K[X]$ be a non-
exceptional polynomial. Then every skew-invariant curve for $(P,P^{\tau})$ is
either a horizontal or vertical line or a skew-twist curve.

Section 2 comprises the bulk of this paper and is devoted to proving Theorem
1.3. In [8] we worked with a formalism of decompositions and Ritt monoid
actions on these decompositions in order to encode and manipulate skew-
invariant curves. Starting with Subsection 2.1 we modify that formalism by
replacing the decompositions with what we call long decompositions. The monoid
actions are then replaced with partial group actions and once again a
$(P,Q)$-skew-invariant curve will be encoded by an equation of the form
$w\star\vec{P}=\vec{Q}$ where $\vec{P}$ and $\vec{Q}$ are long decompositions
of $P$ and $Q$, respectively. When $Q=P^{\tau}$, then decomposition $\vec{Q}$
may be taken to be $\vec{P}^{\tau}$, and then as far as the “shape” of the
long decompositions are concerned, it would seem that the action by $w$ does
not have any real effect. Theorem 1.3 is a mathematical expression of this
observation.

In practice, we must work to produce enough invariants of these long
decompositions to limit the possibilities for such a $w$. One such invariant
might be what we call a wall, that is, a point in the decomposition at which
swaps are impossible. We prove early on with Corollary 2.53 that Theorem 1.3
holds when a long decomposition of $P$ admits a wall.

In Subsection 2.2 we study the case in which Chebyshev functions do not appear
in a decomposition of $P$. In this case, we will find a semi-invariant way to
break a long decomposition of $P$ into blocks and then to describe the our
partial group actions on the decomposition in terms of certain numerical
functions. Finally, in Subsection 2.3 we expand the theory of clusterings from
[8] to produce sufficiently robust combinatorial invariants in the remaining
cases. We collect all of the steps required for the proof of Theorem 1.3 in
Subsection 2.4. This paper concludes with the proof of Theorems 1.1 and 1.2 in
Section 3.

### Acknowledgements

During the writing of this paper A.M. was partially supported by the NSF grant
DMS-1500976 and the Simons Foundation award 317672, K.N. was partially
supported by NSERC Discovery Grant RGPIN-2018-03770 and CRC tier-2 research
stipend 950-231716, and T.S. was partially supported by NSF grants FRG
DMS-1760413 and DMS-1800492 and a Simons Fellowship in Mathematics.

##  2\. Skew-invariant curves

There are two natural procedures for producing skew-invariant curves for
$\left(P,Q\right)$ where $P$ and $Q$ are univariate polynomials. First, we
have the skew-twists. That is, if we factor $P=\beta\circ\alpha$ and
$Q=\alpha^{\sigma^{n+1}}\circ\beta^{\sigma^{n}}$ for some natural number $n$
and polynomials $\alpha$ and $\beta$, then the curve defined by
$y=\alpha^{\sigma^{n}}\circ P^{\sigma^{n-1}}\circ\cdots\circ P(x)$, which we
call a _skew-twist curve_ is $\left(P,Q\right)$-skew-invariant. Note that here
we allow for $\alpha$ or $\beta$ to be linear and $n=0$, so that this includes
the case that $Q$ is skew-linearly conjugate to $P$. Another natural way to
obtain a skew-invariant curve would be have an identity of the form
$X^{n}\circ P=Q\circ X^{n}$ for some positive integer $n$ in which case the
curve defined $y=x^{n}$, which we call a _monomial curve_ , is
$\left(P,Q\right)$-skew-invariant. Of course, we may swap the roles of $P$ and
$Q$ to obtain skew-invariant curves for $\left(Q,P\right)$. For example, if we
have the identity $P\circ X^{n}=X^{n}\circ Q$, then the curve defined by
$y^{n}=x$ is $\left(P,Q\right)$-skew-invariant. Likewise, we may compose such
skew-invariant curves to obtain new ones. That is, if $C$ is
$\left(P,Q\right)$-skew-invariant and $D$ is $\left(Q,R\right)$-skew-
invariant, then the (possibly reducible) $D\circ C$ is
$\left(P,R\right)$-skew-invariant. The process of iterating these operations
and possibly taking components of the resulting reducible curves gives rise to
all of the skew-invariant curves. However, this fact on its own does not give
a sufficiently clear picture of the class of skew-invariant curves. The
description is complicated, for instance, by the fact that the composite of
two skew-twists need not be a skew-twist itself since a given polynomial may
admit several different presentations as a composite of other polynomials.
Moreover, our two classes of basic skew-invariant curves are not disjoint. If
$P=R\circ X^{n}$ and $Q=X^{n}\circ R$ where $R^{\sigma}=R$, then the
$\left(P,Q\right)$-skew-invariant curve defined by $y=x^{n}$ is a skew-twist
curve and is also a monomial curve.

The skew-invariant curves for pairs $\left(P,Q\right)$ of non-exceptional
polynomials are described in [8, Proposition 6.19] as components of curves
encoded by equations of the form $w\star\vec{f}=\vec{g}$ where $\vec{f}$ is a
decomposition of $f$, $\vec{g}$ is a decomposition of $g$, and $w$ belongs to
the augmented skew-twist monoid. With [8, Theorem 6.26], various results on
canonical forms for such actions are applied to convert the equation
$w\star\vec{f}=\vec{g}$ into a concise geometric form. In this section, which
is dedicated to the proof of Theorem 1.3, we modify the formalism of
decompositions and monoid actions to work with what we call long
decompositions and will then specialize to describe the skew-invariant curves
appearing in Theorem 1.3.

###  2.1. Long decompositions and partial group actions

In this subsection we develop the formalism of long decompositions and partial
group actions. With this work we may prove Theorem 1.3 in two cases: when $P$
is indecomposable (Proposition 2.22) and then when $P$ admits a decomposition
with an unswappable factor (Corollary 2.53).

####  2.1.1. Long decompositions

While we recall some of the definitions and results from [8], the reader is
advised to consult that text for further details. Let us begin by recalling
and introducing our basic definitions.

######  Definition 2.1.

A polynomial $f\in K[X]$ is _indecomposable_ if $\operatorname{deg}(f)\geq 2$
and whenever $f=A\circ B$ with $A,B\in K[X]$, then either $A$ or $B$ is
linear. A _decomposition_ of the polynomial $f$ is a finite sequence
$\left(f_{k},\ldots,f_{1}\right)$ of indecomposable polynomials for which
$f=f_{k}\circ\cdots\circ f_{1}$. A ($k$-)_long decomposition_ of $f$ is a
$k$-skew-periodic $\mathbb{Z}$-indexed sequence
$\left(f_{i}\right)_{i\in\mathbb{Z}}$ of indecomposable polynomials (meaning
that for every $i\in\mathbb{Z}$ we have $f_{i+k}=f_{i}^{\sigma}$) for which
$\left(f_{k},\ldots,f_{1}\right)$ is a decomposition of $f$.

######  Notation 2.2.

Throughout the rest of this section we will fix the number $k$. Generally,
when working with a $k$-long decomposition, we shall write something like
$f=\left(f_{i}\right)_{i\in\mathbb{Z}}$ and may use the notation $\vec{f}$
when we wish to distinguish between sequences and individual polynomials.

######  Remark 2.3.

Every nonlinear polynomial admits a long decomposition. Part of Ritt’s [13]
theorem on polynomial decompositions is that the number $k$ depends only on
the polynomial. Of course, unless the polynomial is indecomposable, the long
decomposition itself is not an invariant, but the rest of Ritt’s theorem
expresses the extent to which it is and how one decomposition may be obtained
from another.

######  Definition 2.4.

A $k$-skew periodic sequence of linear polynomials-linearis a
$\mathbb{Z}$-indexed sequence $L=\left(L_{i}\right)_{i\in\mathbb{Z}}$ of
linear polynomials for which $L_{i+k}=L_{i}^{\sigma}$ holds for all
$i\in\mathbb{Z}$.

The $k$-long decomposition$f$ is _linearly equivalent_ to the $k$-long
decomposition$g$ via the $k$-skew periodic sequence of linear polynomials-
linear$L$ provided that $g_{i}=L_{i+1}^{-1}\circ f_{i}\circ L_{i}$ for all
$i\in\mathbb{Z}$. We write $\mathscr{D}_{k}$ for the set of equivalence
classes of $k$-long decompositions.

######  Remark 2.5.

On one hand, Definition 2.4 describes an operation which takes as input $f$
and $L$ and returns $g$. On the other hand, the relation “$f$ is linearly
equivalent to $g$ via some $k$-skew periodic sequence of linear polynomials-
linear” is an equivalence relation on the set of $k$-long decompositions. This
notion matches the _skew_ -linear equivalence of [8] rather than linear
equivalence. For $f$ a $k$-long decompositionwe write $[f]$ for its
equivalence class relative to linear equivalence.

Ritt’s theorems on polynomial decompositions [13] express the extent to which
a polynomial admits a unique presentation as a composition of indecomposable
polynomials. Loosely speaking, if the polynomial $P$ may be expressed in two
different ways as $P=P_{k}\circ\cdots\circ P_{1}$ and
$P=Q_{\ell}\circ\cdots\circ Q_{1}$ where each $P_{i}$ and $Q_{j}$ is
indecomposable, then $\ell=k$ and the decomposition
$\left(Q_{k},\ldots,Q_{1}\right)$ may be obtained from the decomposition
$\left(P_{k},\ldots,P_{1}\right)$ by transforming these sequences through a
finite number of what in [8] we call _Ritt swaps_. We encode this process of
passing from one decomposition to another via a sequence of Ritt swaps through
a certain partial monoid action and then take this further to encode all skew-
invariant curves through more general partial monoid actions.

Let us recall some of the formalism of Ritt identities and Ritt swaps. For
more details, consult [8, page 102].

######  Definition 2.6.

The following identities are called _basic Ritt identities._

  * •

$x^{p}\circ x^{q}=x^{q}\circ x^{p}$ for distinct prime numbers $p$ and $q$,

  * •

$C_{p}\circ C_{q}=C_{q}\circ C_{p}$ for distinct _odd_ primes $p$ and $q$
where $C_{p}$ is the $p^{\text{th}}$ Chebyshev polynomial, and

  * •

$x^{k}\cdot u(x)^{p}\circ x^{p}=x^{p}\circ x^{k}\cdot u(x^{p})$ (and the
identity with the left and right sides reversed) where $u(0)\neq 0$, $p$ is
prime, and $x^{k}\cdot u(x^{p})$ is indecomposable.

######  Definition 2.7.

Fix a polynomial $u$ with no initial nor terminal, compositional nor
multiplicative monomial factors. The in-degree and out-degree of a Ritt
polynomial $g(x)=x^{k}u(x^{\ell})^{n}$ are

$\operatorname{in-deg}(g):=\ell\mbox{ and }\operatorname{out-deg}(g):=n.$

######  Remark 2.8.

Of course, for any polynomial $h$, $h\circ h=h\circ h$. However, we do not
consider such tautological identities to be basic Ritt identities. It is also
the case that for any prime $p$, $C_{2}\circ C_{p}=C_{p}\circ C_{2}$, but we
do not treat this relation as a basic Ritt identity.

######  Definition 2.9.

The polynomials appearing in basic Ritt identities are called _Ritt
polynomials_. An indecomposable polynomial $P$ is _swappable_ if there are
linear polynomials $A$ and $B$ for which $A\circ P\circ B$ is a Ritt
polynomial. A swappable polynomial $P$ is said to be of type $\mathsf{C}$ if
there are linear polynomials $A$ and $B$ for which $A\circ P\circ B$ is a
Chebyshev polynomial of odd degree. Otherwise, the swappable polynomial $P$ is
said to be _$\mathsf{C}$ -free_.

The distinction between type $\mathsf{C}$ and $\mathsf{C}$-free swappable
polynomials and the choice of defining $C_{2}$ to be $\mathsf{C}$-free will
become clear in our work on clusterings in Subsection 2.3.

######  Remark 2.10.

In [8, Definition 2.41] Ritt polynomials are required to be monic. We do not
impose that condition here. However, when we speak of _monomials_ we always
mean expressions of the form $x^{n}$ for some $n\geq 2$. Another difference
between the definition of Ritt polynomial here and in [8] is that for this
paper we require Ritt polynomials to be indecomposable, but this is not so in
[8].

######  Definition 2.11.

For $i\in\mathbb{Z}$, we consider the symbol $t_{i}$. For $k$-long
decompositions$f$ and $g$. We say that _$g$ is obtained from $f$ by a Ritt
swap at $i$_ and write $t_{i}\star[f]=[g]$ if there are linear polynomials
$L$, $M$, and $N$ such that

$g_{i}=S\circ N^{-1},g_{i+1}=L\circ R,g_{i}=f_{i}\,\,\,\text{ for }j\not\equiv
i,i+1\pmod{k}$

and $(L^{-1}\circ f_{i+1}\circ M)\circ(M^{-1}\circ f_{i}\circ N)=R\circ S$ is
a basic Ritt identity.

######  Definition 2.12.

For $\tilde{f}$ and $\tilde{g}$ two $k$-long decompositions, we say that
$\tilde{g}$ is obtained from $\tilde{f}$ via a Ritt swap in the strict sense
at $i$ if
$\tilde{f}_{i+1}\circ\tilde{f}_{i}=\tilde{g}_{i+1}\circ\tilde{g}_{i}$ is a
basic Ritt identity and $\tilde{f}_{j}=\tilde{g}_{j}$ for $j\not\equiv i\text{
or }i+1\pmod{k}$. In this case, we write $t_{i}\bullet\tilde{f}=\tilde{g}$.

######  Remark 2.13.

For $i\neq k$, our definition of $t_{i}\star[f]=[g]$ is exactly [8, Definition
2.43].

If $t_{i}\bullet\tilde{f}=\tilde{g}$, then taking $L=M=N=\operatorname{id}$
shows that $t_{i}\star[\tilde{f}]=[\tilde{g}]$. For $k\neq 2$, the converse
also holds: if $t_{i}\star[f]=[g]$, then there are long decompositions
$\tilde{f}$ and $\tilde{g}$ such that $t_{i}\bullet\tilde{f}=\tilde{g}$. In
this case, we say that $(L,\tilde{f},\tilde{g},M)$ is a witness of
$t_{i}\star[f]=[g]$ when $f$ and $g$ are linearly equivalent to $\tilde{f}$
and $\tilde{g}$ via $L$ and $M$.

######  Remark 2.14.

It follows from skew-periodicity that if the $k$-long decompositions$f$ and
$g$ are Ritt swap related at $i$, then they are also Ritt swap related at $j$
for any $j\equiv i\pmod{k}$. Thus, it is natural to index the generators
$t_{i}$ by $\mathbb{Z}/k\mathbb{Z}$. So for example, when we write an
expression like $t_{k+1}$ we mean $t_{1}$. To use the order on the indices, we
often choose to work with $\\{t_{i}~{}:~{}a\leq i<a+k\\}$ for some $a$, which
is not necessarily $0$.

######  Remark 2.15.

If the Ritt swap in Definition 2.11 involves an identity of one of the first
two kinds, then it really is a swap in that $f_{i+1}=g_{i}$ and
$f_{i}=g_{i+1}$. However, for an identity of the third kind, a Ritt swap at
$i$ will transform one of $f_{i}$ or $f_{i+1}$ into a different polynomial.

We shall consider two other kinds of operations on $\mathscr{D}_{k}$. The
symbol $\phi$ will be used to encode skew-twist curves.

######  Definition 2.16.

For $f=(f_{i})_{i\in\mathbb{Z}}$ a $k$-long decomposition, we define
$\phi\bullet f:=(f_{i+1})_{i\in\mathbb{Z}}$ and $\phi^{-1}\bullet
f:=(f_{i-1})_{i\in\mathbb{Z}}$. This gives an action the symbol $\phi$ on
$\mathscr{D}_{k}$ defined by $\phi\star[f]=[\phi\bullet f]$ and of $\phi^{-1}$
via $\phi^{-1}\star[f]=[\phi^{-1}\bullet f]$.

######  Remark 2.17.

Unlike the symbols $t_{i}$, for any $x\in\mathscr{D}_{k}$, $\phi\star x$ is
defined. Moreover, $\phi^{-1}\star=(\phi\star)^{-1}$.

######  Remark 2.18.

What we call $\phi^{-1}$ corresponds to the symbol $\beta$ of [8].

Finally, we define partial operations specifically connected to the third kind
of basic Ritt identity. These are used to encode monomial curves.

######  Definition 2.19.

For each prime number $p$ we have symbols $\epsilon_{p}$ and
$\epsilon_{p}^{-1}$. If $\tilde{f}$ and $\tilde{g}$ are $k$-long
decompositionssuch that for all $i\in\mathbb{Z}$,
$\tilde{f}_{i}=x^{r_{i}}u_{i}(x^{p})$ where either $u_{i}(0)\neq 0$ and $\deg
u_{i}>0$ or $p\neq r_{i}$ and $\tilde{g}_{i}=x^{r_{i}}u_{i}(x)^{p}$, then we
write $\epsilon_{p}\bullet\tilde{f}=\tilde{g}$ and $\epsilon_{p}^{-1}\bullet
g=f$. This relation induces a partial action of $\epsilon_{p}$ and of
$\epsilon_{p}^{-1}$ on $\mathscr{D}_{k}$ given by
$\epsilon_{p}\star[\tilde{f}]:=[\epsilon_{p}\bullet\tilde{f}]$ and
$\epsilon_{p}^{-1}\bullet[\tilde{g}]:=[\epsilon_{p}^{-1}\bullet\tilde{g}]$. If
$f$ and $g$ are $k$-long decompositionswith $[f]=[\tilde{f}]$ and
$[g]=[\tilde{g}]$, and $L$ and $M$ are $k$-skew periodic sequences of linear
polynomials-linearso that $\tilde{f}$ is linearly equivalent to $f$ via $L$
and $\tilde{g}$ is linearly equivalent to $g$ via $M$, then we say that
$(L,\tilde{f},\tilde{g},M)$ is a witness to $\epsilon_{p}\star[f]=[g]$. In
this context, $(M^{-1},\tilde{g},\tilde{f},L^{-1})$ is a witness to
$\epsilon_{p}^{-1}\star[g]=[f]$.

######  Remark 2.20.

What we call here $\epsilon_{p}^{-1}$ corresponds to the $\delta_{p}$ of [8].

######  Remark 2.21.

The condition that $\tilde{f}_{i}$ is not a monomial of degree $p$ is included
to disambiguate the monomial curves encoded by identities of the form
$\epsilon_{p}\star[f]=[g]$ and the skew-twist curves encoded by relations of
the form $\phi\star[f]=[g]$.

With this notation in place, we may prove an easy case of Theorem 1.3.

######  Proposition 2.22.

Theorem 1.3 holds when $P$ is indecomposable.

Our proof of Proposition 2.22 passes through several lemmas.

######  Lemma 2.23.

Let $P$ be an indecomposable non-exceptional polynomial and let $\mathcal{C}$
be a skew-invariant curve for $(P,P^{\tau})$. Then there exist non-constant
polynomials $Q,A,B,A_{0},B_{0}$ in $K[X]$ and integers $a,b,c,d$ with $a,b\geq
0$ and $c,d\geq-1$ satisfying the following properties:

  * (i)

$\mathcal{C}$ is parametrized by $(A,B)$, i.e. the map
$\mathbb{A}^{1}\to\mathbb{A}^{2}$ given by $t\mapsto(A(t),B(t))$ is dominant
onto $\mathcal{C}$.

  * (ii)

$A$ and $B$ have no shared nonlinear initial compositional factors.

  * (iii)

$P\circ A=A^{\sigma}\circ Q$ and $P^{\tau}\circ B=B^{\sigma}\circ Q$.

  * (iv)

$A=P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-a}}\circ A_{0}\circ
Q^{\sigma^{c}}\circ\cdots\circ Q$ and $B=P^{\tau\sigma^{-1}}\circ\cdots\circ
P^{\tau\sigma^{-b}}\circ B_{0}\circ Q^{\sigma^{d}}\circ\cdots\circ Q$.

  * (v)

$Q^{\sigma^{c+1}}$ is not an initial compositional factor of $A_{0}$,
$P^{\sigma^{-a-1}}$ is not a terminal compositional factor of $A_{0}$,
$Q^{\sigma^{d+1}}$ is not an initial compositional factor of $B_{0}$, and
$P^{\tau\sigma^{-b-1}}$ is not a terminal compositional factor of $B_{0}$.

  * (vi)

$P^{\sigma^{-a}}\circ A_{0}=A_{0}^{\sigma}\circ Q^{\sigma^{c+1}}$ and
$P^{\tau\sigma^{-b}}\circ B_{0}=B_{0}^{\sigma}\circ Q^{\sigma^{d+1}}$.

  * (vii)

$A=A_{0}^{\sigma^{a}}\circ Q^{\sigma^{a+c}}\circ\cdots
Q=P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-(a+c+1)}}\circ
A_{0}^{\sigma^{-(c+1)}}$ and $B=B_{0}^{\sigma^{b}}\circ
Q^{\sigma^{b+d}}\circ\cdots Q=P^{\tau\sigma^{-1}}\circ\cdots\circ
P^{\tau\sigma^{-(b+d+1)}}\circ B_{0}^{\sigma^{-(d+1)}}$. Consequently,
$A_{0}^{\sigma^{-(c+1)}}$ and $B_{0}^{\sigma^{-(d+1)}}$ do not have a
nontrivial common initial compositional factor and either $(a,c)$ or $(b,d)$
is $(0,-1)$.

###### Proof.

Let $d:=\deg(P)$. If the lemma holds for the given data $(P,\mathcal{C})$ then
it holds for $(L^{\sigma}\circ P\circ L^{-1},(L,L)(C))$ where $L$ is any
linear polynomial. Hence we may assume that $P$ is centered meaning that the
coefficient of $X^{d-1}$ is $0$.

From [8, Corollary 2.35], we know that $\mathcal{C}$ is parametrized by
$(A,B)$ and there exists a polynomial $Q$ such that (iii) holds since
$\mathcal{C}$ is skew-invariant under $(P,P^{\tau})$. By choosing a pair
$(A,B)$ with minimal $\deg(A)+\deg(B)$, we may assume that they do not have a
common nonlinear initial compositional factors.

We now express $A$ and $B$ as in (iv) with maximal $a,b,c,d$ then (v) holds.
Now we establish Property (vi). From (iii) and (iv), we have:

(1) $P\circ P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-a}}\circ A_{0}=P\circ
P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-(a-1)}}\circ A_{0}\circ
Q^{\sigma^{c+1}}.$

When $a=0$, this identity means $P\circ A_{0}=A_{0}\circ Q^{\sigma^{c+1}}$.
From now on, assume $a>0$.

First, assume the case when $P$ does not have the form $P_{1}\circ X^{m}$
where $m>1$. Since $P$ is centered, the only linear polynomial $L$ such that
$P\circ L=P$ is the identity polynomial $L(X)=X$. Consequently, whenever
$P\circ R=P\circ S$ for non-constant polynomials $R,S$ then we have $R=S$.
Applying this observation repeatedly to (1), we have:

$P^{\sigma^{-a}}\circ A_{0}=A_{0}\circ Q^{\sigma^{c+1}}.$

Now suppose that $P=P_{1}(X^{m})$ where $m>1$. Since $P$ is indecomposable, we
must have that $m=d$ is a prime and $P_{1}$ is linear. The polynomial $P\circ
P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-(a-1)}}$ is centered and we write

(2) $P\circ P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-(a-1)}}=P_{2}\circ
X^{\ell}$

where $\ell$ is largest possible. We claim that $\ell=d$. Suppose $\ell>d$ and
we arrive at a contradiction. Since $d$ is a prime, $\ell$ is a power of $d$
and hence $d^{2}\mid\ell$. Identity (2) implies:

$P\circ P^{\sigma^{-1}}\circ\cdots\circ P^{\sigma^{-(a-2)}}\circ
P_{1}^{\sigma^{-a-1}}=P_{2}\circ X^{\ell/d^{2}}\circ X^{d}.$

This implies:

(3) $P^{\sigma^{-(a-2)}}\circ P_{1}^{\sigma^{-a-1}}=P_{3}\circ X^{d}$

for some linear polynomial $P_{3}$. Since $P$ is centered, (3) implies that
$P_{1}$ is a scaling and hence $P(X)=\lambda X^{d}$ for some constant
$\lambda$, which is a contradiction. Therefore, we must have $\ell=d$.
Identity (1) implies:

$P^{\sigma^{-a}}\circ A_{0}=\zeta\cdot(A_{0}\circ Q^{\sigma^{c+1}})$

where $\zeta$ is a $d$-th root of unity. After replacing $A_{0}$ by $\zeta
A_{0}$, we have that $A$ is unchanged (since $a>0$) and $P^{\sigma^{-a}}\circ
A_{0}=A_{0}\circ Q^{\sigma^{c+1}}$. By similar arguments, we can also arrange
for the identity $P^{\tau\sigma^{-b}}\circ B_{0}=B_{0}^{\sigma}\circ
Q^{\sigma^{d+1}}$. Property (vii) follows from (iv) and repeated applications
of (vi). Finally we have either $(a,c)$ or $(b,d)$ is $(0,-1)$ since otherwise
$Q$ would be a common initial factor of $A$ and $B$. ∎

######  Lemma 2.24.

Let $P$ and $\mathcal{C}$ be as in Lemma 2.23. Let $Q,A,B,\ldots$ satisfy the
conclusion of Lemma 2.23. If $A_{0}$ and $B_{0}$ are linear then $\mathcal{C}$
is a skew-invariant curve for $(P,P^{\tau})$.

###### Proof.

From Lemma 2.23, we have:

$A=A_{0}^{\sigma^{a}}\circ Q^{\sigma^{a+c}}\circ\cdots Q,\
B=B_{0}^{\sigma^{b}}\circ Q^{\sigma^{b+d}}\circ\cdots Q,$

and without loss of generality, assume $a=0$ and $c=-1$. Then $A=A_{0}$ is
linear.

After replacing $(B,Q,B_{0})$ by $(B\circ A^{-1},A^{\sigma}\circ Q\circ
A^{-1},B_{0}\circ(A^{-1})^{\sigma^{d+1}})$, we may assume that $A=A_{0}=X$.
Then property (vi) gives that $P=Q$ and $P^{\tau\sigma^{-b}}\circ
B_{0}=B_{0}^{\sigma}\circ Q^{\sigma^{d+1}}=B_{0}^{\sigma}\circ
P^{\sigma^{d+1}}$. Therefore:

$P^{\tau}=B_{0}^{\sigma^{b+1}}\circ
P^{\sigma^{b+d+1}}\circ(B_{0}^{-1})^{\sigma^{b}}=(B_{0}^{\sigma^{-d}}\circ
P)^{\sigma^{b+d+1}}\circ\left((B_{0}^{-1})^{\sigma^{-d}}\right)^{\sigma^{b+d}}.$

Put $\alpha=B_{0}^{\sigma^{-d}}\circ P$, $\beta=(B_{0}^{-1})^{\sigma^{-d}}$,
and $n=b+d$, then we have $P=\beta\circ\alpha$,
$P^{\tau}=\alpha^{\sigma^{n+1}}\circ\beta^{\sigma^{n}}$. and the curve
$\mathcal{C}$ is given by the equation:

$y=B(x)=B_{0}^{\sigma^{b}}\circ Q^{\sigma^{b+d}}\circ\cdots
Q(x)=\alpha^{\sigma^{n}}\circ P^{\sigma^{n-1}}\circ\cdots\circ P(x)$

fitting the definition of a skew-twist curve. ∎

###### Proof of Proposition 2.22 when $P$ is not swappable of type
$\mathsf{C}$.

Let $P$ be an indecomposable non-exceptional polynomial and let $\mathcal{C}$
be a skew-invariant curve for $(P,P^{\tau})$. Let $Q,A,B,\ldots$ be the data
as in the conclusion of Lemma 2.23.

Case 1: $P$ is unswappable. From $P^{\sigma^{-a}}\circ
A_{0}=A_{0}^{\sigma}\circ Q^{\sigma^{c+1}}$ and the fact that $A_{0}^{\sigma}$
does not have $P^{\sigma^{-a}}$ as a terminal compositional factor, we
conclude that $A_{0}$ is linear. Similarly, $B_{0}$ is linear and
$\mathcal{C}$ is a skew-twist curve thanks to Lemma 2.24.

Case 2: $P$ is swappable and not of type $\mathsf{C}$. If both $A_{0}$ and
$B_{0}$ are linear then we are done thanks to Lemma 2.24. It remains to
consider the following 2 cases.

Case 2.1: $A_{0}$ is linear and $N:=\deg(B_{0})\geq 2$. From properties (v)
and (vi) in Lemma 2.23 and [8, Corollary 5.24], there exist linear polynomials
$L_{1}$ and $L_{2}$ such that:

$P^{\tau\sigma^{-b}}=L_{2}^{\sigma}\circ X^{k}U(X)^{N}\circ L_{2}^{-1},$
$B_{0}=L_{2}\circ X^{N}\circ L_{1}^{-1},$
$Q^{\sigma^{d+1}}=L_{1}^{\sigma}\circ X^{k}U(X^{N})\circ L_{1}^{-1},$

where $U(X)$ is a non-constant polynomial such that $U(0)\neq 0$ and
$k\in\mathbb{N}$ with $\gcd(k,N)=1$.

Put $\eta=\tau^{-1}\sigma^{b-a}$ and $\mu=\sigma^{c-d}$ then the above
identities yield:

$P^{\sigma^{-a}}=L_{2}^{\eta\sigma}\circ
X^{k}U^{\eta}(X)^{N}\circ(L_{2}^{\eta})^{-1}\ \text{and}$
$Q^{\sigma^{c+1}}=L_{1}^{\mu\sigma}\circ
X^{k}U^{\mu}(X^{N})\circ(L_{1}^{\mu})^{-1}$

Combining this with the identity $P^{\sigma^{-a}}\circ
A_{0}=A_{0}^{\sigma}\circ Q^{\sigma^{c+1}}$ and the assumption that
$\deg(A_{0})=1$, we have:

(4) $L^{\sigma}\circ X^{k}U^{\eta}(X)^{N}\circ L^{-1}=X^{k}U^{\mu}(X^{N})$

where $L=A_{0}^{-1}\circ(L_{1}^{\mu})^{-1}\circ L_{2}^{\eta}$. Since $P$ is
not type $\mathsf{C}$, identity (4) yields that $L$ is a scaling thanks to [8,
Theorem 3.15]. This implies:

(5) $U(X^{N})=cU^{\eta\mu^{-1}}(X)^{N}$

for some $c\in K^{*}$. It follows immediately that $U(X)$ must be a monomial:
otherwise suppose $X^{r}$ and $X^{s}$ with $r>s$ are the highest degree terms
with a non-zero coefficients in $U$, then the two such terms in $U(X^{N})$ are
$X^{Nr}$ and $X^{Ns}$ while the ones for $U^{\eta\mu^{-1}}(X)^{N}$ are
$X^{Nr}$ and $X^{r(N-1)+s}$, contradicting (5). But when $U$ is a monomial, we
have a contradiction to the assumption that $U(0)\neq 0$. Therefore the case
$\deg(A_{0})=1$ and $\deg(B_{0})\geq 2$ cannot happen. It remains to treat the
following case.

Case 2.2: $M:=\deg(A_{0})\geq 2$ and $N:=\deg(B_{0})\geq 2$. We proceed as in
the above case. By [8, Corollary 5.24], there exist linear polynomials
$\ell_{1},\ell_{2},L_{1},L_{2}$ such that:

(6) $\displaystyle\begin{split}P^{\sigma^{-a}}=\ell_{2}^{\sigma}\circ
X^{k^{\prime}}V(X)^{M}\circ\ell_{2}^{-1}&,\
P^{\tau\sigma^{-b}}=L_{2}^{\sigma}\circ X^{k}U(X)^{N}\circ L_{2}^{-1},\\\
A_{0}=\ell_{2}\circ X^{M}\circ\ell_{1}^{-1}&,\ B_{0}=L_{2}\circ X^{N}\circ
L_{1}^{-1},\\\ Q^{\sigma^{c+1}}=\ell_{1}^{\sigma}\circ
X^{k^{\prime}}V(X^{M})\circ\ell_{1}^{-1}&,\
Q^{\sigma^{d+1}}=L_{1}^{\sigma}\circ X^{k}U(X^{N})\circ
L_{1}^{-1},\end{split}$

where $U(X),V(X)$ are non-constant polynomials such that $U(0)V(0)\neq 0$ and
$k,k^{\prime}\in\mathbb{N}$ with $\gcd(k^{\prime},M)=\gcd(k,N)=1$. As before,
put $\eta=\tau^{-1}\sigma^{b-a}$ and $\mu=\sigma^{c-d}$, we then have:

$P^{\sigma^{-a}}=\ell_{2}^{\sigma}\circ
X^{k^{\prime}}V(X)^{M}\circ\ell_{2}^{-1},\
P^{\sigma^{-a}}=L_{2}^{\eta\sigma}\circ
X^{k}U^{\eta}(X)^{N}\circ(L_{2}^{\eta})^{-1},$
$Q^{\sigma^{c+1}}=\ell_{1}^{\sigma}\circ
X^{k^{\prime}}V(X^{M})\circ\ell_{1}^{-1},\
Q^{\sigma^{c+1}}=L_{1}^{\mu\sigma}\circ
X^{k}U^{\mu}(X^{N})\circ(L_{1}^{\mu})^{-1}.$

This implies:

(7)
$\displaystyle\begin{split}X^{k^{\prime}}V(X)^{M}=(\ell_{2}^{-1})^{\sigma}\circ
L_{2}^{\eta\sigma}\circ
X^{k}U^{\eta}(X)^{N}\circ(L_{2}^{\eta})^{-1}\circ\ell_{2},\\\
X^{k^{\prime}}V(X^{M})=(\ell_{1}^{-1})^{\sigma}\circ L_{1}^{\mu\sigma}\circ
X^{k}U^{\mu}(X^{N})\circ(L_{1}^{\mu})^{-1}\circ\ell_{1}.\end{split}$

The first identity together with the assumption that $P$ is not type
$\mathsf{C}$ imply that $\ell_{2}^{-1}\circ L_{2}^{\eta}$ is a scaling thanks
to [8, Theorem 3.15]. The second identity together with the fact that
$X^{k^{\prime}}V(X^{M})$ and $X^{k}U^{\eta}(X^{N})$ are centered imply that
$\ell_{1}^{-1}\circ L_{1}^{\mu}$ is a scaling. Thanks to these extra
properties, (7) yields the following:

  * •

$k=k^{\prime}$.

  * •

$\operatorname{in-deg}(V)=\operatorname{in-deg}(U)$.

  * •

$M\cdot\operatorname{in-deg}(V)=\operatorname{in-
deg}(X^{k^{\prime}}V(X^{M}))=\operatorname{in-
deg}(X^{k}U^{\mu}(X^{N}))=N\cdot\operatorname{in-deg}(U)$. Therefore $M=N$.

The middle pair of equations in (6) gives:

$B_{0}^{\mu}=L_{2}^{\mu}\circ
X^{N}\circ(L_{1}^{\mu})^{-1}\circ\ell_{1}\circ\ell_{1}^{-1}=L_{3}\circ
X^{N}\circ\ell_{1}^{-1}$

for some linear $L_{3}$ since $(L_{1}^{\mu})^{-1}\circ\ell_{1}$ is a scaling.
This implies that $X^{N}\circ\ell_{1}^{-1}$ is a common initial compositional
factor of $A_{0}$ and $B_{0}^{\mu}$. After applying $\sigma^{-(c+1)}$, we have
that $A_{0}^{\sigma^{-(c+1)}}$ and $B_{0}^{\sigma^{-(d+1)}}$ have a nontrivial
common initial compositional factor, contradicting property (vii) in Lemma
2.23. Therefore the case when $\deg(A_{0})>2$ and $\deg(B_{0})>2$ cannot
happen either. ∎

######  Remark 2.25.

To finish the proof of Proposition 2.22, it remains to consider the case when
$P$ is type $\mathsf{C}$. We express $P=R\circ C_{q}\circ N$ where $R$ and $N$
are linear and $q=\deg(P)$ is an odd prime. Since skew-invariant curves for
one pair of polynomials are transformed into skew-invariant curves for
$\sigma$-linear conjugates of those polynomials, after replacing $P$ by an
appropriate $\sigma$-linear conjugate, we may assume that
$R=\operatorname{id}$. Hence $P=C_{q}\circ N$ with
$N\neq\pm\operatorname{id}$. As in the above proof, we let $Q,A,B,\ldots$ be
the data in the conclusion of Lemma 2.23 then [8, Corollary 5.14] implies that
there exist linear polynomials $L_{1}$ and $L_{2}$ such that:

$P^{\tau\sigma^{-b}}=L_{2}^{\sigma}\circ X^{k}U(X)^{\delta}\circ L_{2}^{-1},$
$B_{0}=L_{2}\circ X^{\delta}\circ L_{1}^{-1},$
$Q^{\sigma^{d+1}}=L_{1}^{\sigma}\circ X^{k}U(X^{\delta})\circ L_{1}^{-1},$

where $\delta=\deg(B_{0})$, $U(X)$ is a non-constant polynomial such that
$U(0)\neq 0$ and $k\in\mathbb{N}$ with $\gcd(k,\delta)=1$. Now since $P$ is
$C_{q}\circ N$, we have that $\delta\leq 2$. Hence $\deg(B_{0})\leq 2$.
Similarly $\deg(A_{0})\leq 2$.

######  Lemma 2.26.

Let $d\geq 3$ be an odd integer. Suppose $L_{1}(x)$, $L_{2}(x)$, and $U(x)$
are polynomials in $K[x]$ such that $\deg(L_{1})=\deg(L_{2})=1$, $U(0)\neq 0$,
and

$L_{1}\circ C_{d}\circ L_{2}=xU(x)^{2}.$

Then one of the following cases holds:

  * (i)

$L_{1}(x)=a(x+2)$ and $L_{2}(x)=bx-2$ for some $a,b\in K^{*}$.

  * (ii)

$L_{1}(x)=a(x-2)$ and $L_{2}(x)=bx+2$ for some $a,b\in K^{*}$.

###### Proof.

Since $0$ is a critical value of $xU(x)^{2}$ while $\pm 2$ are the only
critical values of $C_{d}(x)$, we have that $L_{1}(2)=0$ or $L_{1}(-2)=0$.

First, we consider the case $L_{1}(-2)=0$. From $L_{1}(C_{d}(L_{2}(0)))=0$ and
$L_{1}(-2)=0$, we have $C_{d}(L_{2}(0))=-2$. Henc $L_{2}(0)$ is either $-2$ or
one of the remaining $(d-1)/2$ critical points lying above $-2$. But $0$ is
not a critical point of $xU(x)^{2}$, we must have $L_{2}(0)=-2$. This yields
case (i). The case $L_{1}(2)=0$ is similar and we finish the proof. ∎

######  Lemma 2.27.

Let $d\geq 3$ be an odd integer and let $P_{2}(x)=x^{2}$. Suppose that $N$,
$L$, and $Q$ are polynomials in $K[x]$ such that $\deg(N)=\deg(L)=1$, $L$ is a
translation, and:

(8) $N\circ C_{d}\circ L\circ P_{2}=L^{\sigma}\circ P_{2}\circ Q.$

Then one of the following cases holds:

  * (i)

$L(x)=x-2$, $N(x)=\lambda(x+2)-2$, and $Q(x)=\pm\sqrt{\lambda}C_{q}(x)$ for
some $\lambda\in K^{*}$.

  * (ii)

$L(x)=x+2$, $N(x)=\lambda(x-2)+2$, and $Q(x)=\pm\sqrt{\lambda}C_{q}(x)$ for
some $\lambda\in K^{*}$.

###### Proof.

Write $L(x)=x+\ell$. By Ritt’s theorem, there exist linear polynomials
$\alpha,\beta,\gamma,\delta$ and polynomial $U(x)$ in $K[x]$ such that:

(9) $\displaystyle\alpha\circ N\circ C_{d}\circ\beta^{-1}$
$\displaystyle=xU(x)^{2},$ (10) $\displaystyle\beta\circ L\circ
P_{2}\circ\gamma$ $\displaystyle=x^{2},$ (11) $\displaystyle\alpha\circ
L^{\sigma}\circ P_{2}\circ\delta^{-1}$ $\displaystyle=x^{2},$ (12)
$\displaystyle\delta\circ Q\circ P_{2}\circ\gamma$ $\displaystyle=xU(x^{2})$

By Lemma 2.26 for (9), we have two cases. The first case is that:

(13) $\alpha\circ N=a(x+2)\text{and}\ \beta^{-1}=bx-2\ \text{for some $a,b\in
K^{*}$}.$

Since $P_{2}(x)=x^{2}$ and $L(x)=x+\ell$, from (10), we have:

(14) $\gamma(x)=cx,\ \beta\circ L=\frac{1}{c^{2}}x,\
\beta=\frac{1}{c^{2}}(x-\ell)\ \text{for some $c\in K^{*}$}.$

From (13) and (14), we have:

$\frac{x+2}{b}=\frac{1}{c^{2}}(x-\ell).$

This gives $b=c^{2}$ and $\ell=-2$. We now have $L(x)=x-2$ and the given (8)
becomes:

$N(C_{d}(x^{2}-2))=Q(x)^{2}-2.$

Combining this with the identity $C_{d}(x^{2}\pm 2)=C_{d}(x)^{2}\pm 2$ and
expressing $N(x)=\lambda x+d$, we have:

$\lambda C_{d}(x)^{2}-2\lambda+d=Q(x)^{2}-2.$

This implies $\lambda C_{d}(x)^{2}=Q(x)^{2}$ and $-2\lambda+d=-2$. This yields
case (i).

The remaining case when applying Lemma 2.26 for (9) is that:

(15) $\alpha\circ N=a(x-2)\text{and}\ \beta^{-1}=bx+2\ \text{for some $a,b\in
K^{*}$}.$

This can be settled by similar arguments. ∎

###### Proof of Proposition 2.22.

We apply the reduction and observation in Remark 2.25: $P=C_{q}\circ N$ where
$q$ is an odd prime and $N\neq\pm\operatorname{id}$ is linear, let
$Q,A,B,\ldots$ be the data in the conclusion of Lemma 2.23 and we have
$\deg(A_{0}),\deg(B_{0})\leq 2$. We prove by contradiction that the case
$(\deg(A_{0}),\deg(B_{0}))\neq(1,1)$ cannot happen then Lemma 2.24 finishes
the proof.

Case 1: $\deg(A_{0})=\deg(B_{0})=2$. With $P_{2}(x)=x^{2}$, we can express
$A_{0}=L\circ P_{2}\circ M$ and $B_{0}=L_{1}\circ P_{2}\circ M_{1}$ where
$L,L_{1},M,M_{1}$ are linear and $L$ and $L_{1}$ are translation. Then
property (vi) in Lemma 2.23 together with $P=N\circ C_{q}$ yield:

(16) $\displaystyle N^{\sigma^{-a}}\circ C_{q}\circ L\circ P_{2}$
$\displaystyle=L^{\sigma}\circ P_{2}\circ(M^{\sigma}\circ
Q^{\sigma^{c+1}}\circ M^{-1}),$ (17) $\displaystyle N^{\tau\sigma^{-b}}\circ
C_{q}\circ L_{1}\circ P_{2}$ $\displaystyle=L_{1}^{\sigma}\circ
P_{2}\circ(M_{1}^{\sigma}\circ Q^{\sigma^{d+1}}\circ M_{1}^{-1}).$

We apply Lemma 2.27 to the above pair of equations.

Case 1.1: both data $(N^{\sigma^{-a}},L,M^{\sigma}\circ Q^{\sigma^{c+1}}\circ
M^{-1})$ and $(N^{\tau\sigma^{-b}},L_{1},M_{1}^{\sigma}\circ
Q^{\sigma^{d+1}}\circ M_{1}^{-1})$ satisfy the conclusion in case (i) of Lemma
2.27 or both data satisfy the conclusion in case (ii). This gives
$L=L_{1}=x-2$ or $L=L_{1}=x+2$ and there exist $\alpha,\alpha_{1}\in K^{*}$
such that:

$M^{\sigma}\circ Q^{\sigma^{c+1}}\circ M^{-1}=\alpha C_{q}\ \text{and}\
M_{1}^{\sigma}\circ Q^{\sigma^{d+1}}\circ M_{1}^{-1}=\alpha_{1}C_{q}.$

This implies:

$Q^{\sigma^{c+1}}=(M^{-1})^{\sigma}\circ(\cdot\alpha)\circ C_{q}\circ M\
\text{and}\ Q^{\sigma^{d+1}}=(M_{1}^{-1})^{\sigma}\circ(\cdot\alpha_{1})\circ
C_{q}\circ M_{1}.$

Together with the fact that if $\ell_{1}\circ C_{q}\circ\ell_{2}=C_{q}$ for
some linear polynomials $\ell_{1}$ and $\ell_{2}$ then $\ell_{1}=\ell_{2}=\pm
x$, we have:

$M^{\sigma^{-(c+1)}}=\pm M_{1}^{\sigma^{-(d+1)}}.$

We now have:

$A_{0}^{\sigma^{-(c+1)}}=L\circ P_{2}\circ M^{\sigma^{-(c+1)}}=L_{1}\circ
P_{2}\circ M_{1}^{\sigma^{-(d+1)}}=B_{0}^{\sigma^{-(d+1)}}.$

This contradicts property (vii) in Lemma 2.23.

Case 1.2: between the data $(N^{\sigma^{-a}},L,M^{\sigma}\circ
Q^{\sigma^{c+1}}\circ M^{-1})$ and
$(N^{\tau\sigma^{-b}},L_{1},M_{1}^{\sigma}\circ Q^{\sigma^{d+1}}\circ
M_{1}^{-1})$, one satisfies (i) while the other one satisfies (ii) in Lemma
2.27. Without loss of generality, assume the first data satisfies (i) and the
second satisfies (ii). Hence there exist $\alpha,\beta\in K^{*}$ such that:

$N^{\sigma^{-a}}=\alpha x+2\alpha-2\ \text{and}\ N^{\tau\sigma^{-b}}=\beta
x-2\beta+2.$

This gives $\beta=\alpha^{\tau\sigma^{a-b}}$ and
$-2\beta+2=2\alpha^{\tau\sigma^{a-b}}-2=2\beta-2$. Hence $\beta=1$ and
$N(x)=x$, contradicting the condition that $N\neq\pm\operatorname{id}$.

Case 2: without loss of generality, the remaining case is that $\deg(A_{0})=2$
and $\deg(B_{0})=1$. From property (vi) in Lemma 2.23, we have:

$Q^{\sigma^{d+1}}=(B_{0}^{-1})^{\sigma}\circ P^{\tau\sigma^{-b}}\circ
B_{0}=(B_{0}^{-1})^{\sigma}\circ N^{\tau\sigma^{-b}}\circ C_{q}\circ B_{0}.$

Applying $\sigma^{c-d}$ both sides gives:

(18) $Q^{\sigma^{c+1}}=(B_{0}^{-1})^{\sigma^{c-d+1}}\circ
N^{\tau\sigma^{c-d-b}}\circ C_{q}\circ B_{0}^{\sigma^{c-d}}.$

As in the earlier Case 1, we express $A_{0}=L\circ P_{2}\circ M$ where $M$ is
linear and $L$ is a translation. Then we get

(19) $\displaystyle N^{\sigma^{-a}}\circ C_{q}\circ L\circ P_{2}$
$\displaystyle=L^{\sigma}\circ P_{2}\circ(M^{\sigma}\circ
Q^{\sigma^{c+1}}\circ M^{-1}),$

from property (vi) in Lemma 2.23 as before. Applying Lemma 2.27 to (19), there
exists $\alpha\in K^{*}$ such that:

(20) $M^{\sigma}\circ Q^{\sigma^{c+1}}\circ M^{-1}=\alpha C_{q}.$

Together with (18), we have:

(21) $(M\circ B_{0}^{-1})^{\sigma}\circ N^{\tau\sigma^{c-d-b}}\circ C_{d}\circ
B_{0}\circ M^{-1}=\alpha C_{q}.$

This implies $B_{0}\circ M^{-1}=\pm x$, then $(M\circ B_{0}^{-1})^{\sigma}=\pm
x$, and hence

(22) $N^{\tau\sigma^{c-d-b}}=\pm\alpha x.$

Applying Lemma 2.27 to (19) again, there is $\beta\in K^{*}$ such that
$N^{\sigma^{-a}}=\beta x+2\beta-2$ or $N^{\sigma^{-a}}=\beta x-2\beta+2$. But
in either case, (22) implies that $\beta=1$ and hence $N(x)=x$ contradicting
the condition $N\neq\pm\operatorname{id}$. ∎

####  2.1.2. Partial group actions

We introduce partial actions and rewriting systems to view the result of
sequences of these partial operations on $\mathscr{D}_{k}$ as partial group
actions. From the intended actions of these generators of the groups to get a
(usual) group action, we would have to show that the relations given by a
presentation of the relevant group are respected. However, this is not the
case here. To get these desired partial group actions, asymmetric term-
rewriting systems replace the relations in a presentation.

All of the following definitions are standard, with the exception of the very
simple and natural notion of actionability. A standard reference for rewriting
systems is [3] and for partial group actions is [5]. However, we use somewhat
different notation from these other authors.

######  Definition 2.28.

For a set $X$, let $M_{X}$ be the monoid of partial injective functions on
$X$. That is, elements of $M_{X}$ are injections $m:Y\rightarrow X$ for some
$Y\subseteq X$, and the operation is composition, with maximal possible
domain.

For a set $T$, let $T^{*}$ be the free monoid generated by $T$, also known as
the set of words on $T$. For a function $\alpha:T\rightarrow M_{X}$, let
$\alpha^{*}:T^{*}\rightarrow M_{X}$ be the induced monoid homomorphism.

For a monoid $G$ and a set $X$, a _partial action_ of $G$ on $X$ is a function
$\beta:G\rightarrow M_{X}$ such that for any $a,b\in G$,

$\beta(b)\circ\beta(a)\subseteq\beta(ba).$

Here, the subset relation is in the sense of the graphs of functions. In more
functional notation, $m_{1}\subseteq m_{2}$ means that $m_{1}$ is the
restriction of $m_{2}$ to a possibly smaller set. When $\beta$ is clear, we
write $g\star x$ instead of $\beta(g)(x)$ for $g\in G$ and $x\in X$.

The purpose of a rewriting system $R$ is that whenever $(u,v)\in R$, we are
allowed to replace a substring $u$ in some big string $aub$ by the string $v$
to get $avb$. This is the asymmetric analog of the relations in a group
presentation.

######  Definition 2.29.

(See [3, Definition 2.1.1 and 2.1.2]) A _string rewriting system_ on $T$ is a
subset $R$ of $T^{*}\times T^{*}$. The _reduction relation_
$\overrightarrow{R}$ induced by $R$ is the reflexive transitive closure of the
relation

$\\{(aub,avb)\in T^{*}\times T^{*}):a,b\in T^{*}\text{ and }(u,v)\in R\\}.$

The equivalence relation generated by $\overrightarrow{R}$ is denoted by
$\overline{R}$. It is the monoid congruence generated by $R$. The quotient
monoid and the quotient map are denoted by $G_{R}$ and
$\pi_{R}:T^{*}\rightarrow G_{R}$, respectively.

The string rewriting system $R$ is _confluent_ if whenever
$(v,w)\in\overline{R}$, there is another word $u$ with both
$(v,u)\in\overrightarrow{R}$ and $(w,u)\in\overrightarrow{R}$. That is,
whenever two words are $R$-equivalent, they are $R$-reducible to the same
word.

A word $w\in T^{*}$ is _$\overline{R}$ -reduced_ if it is not
$\overline{R}$-equivalent to any shorter word.

######  Definition 2.30.

Fix sets $X$ and $T$, a function $\alpha:T\rightarrow M_{X}$, and a confluent
rewriting system $R$ on $T$. The pair $(\alpha,R)$ is _actionable_ if
$\alpha^{*}(u)\subseteq\alpha^{*}(v)$ for all $u,v\in T^{*}$ with $(u,v)\in
R$.

The next proposition demonstrates that the technical notion of “actionable”
from Definitions 2.30 exactly corresponds to the idea that an action defined
on generators is really “actionable” in that it may be made into a partial
action.

######  Proposition 2.31.

Fix sets $X$ and $T$, a function $\alpha:T\rightarrow M_{X}$, and a confluent
rewriting system $R$ on $T$. If the pair $(\alpha,R)$ is actionable, then

$\bar{\alpha}(g):=\cup\\{\alpha^{*}(w):w\in T^{*}\text{ and }\pi_{R}(w)=g\\}$

defines a partial action $\star$ of $G_{R}$ on $X$.

In functional notation, this union means that for $g\in G$ and $x,y\in X$,

$g\star x=y\text{ if and only if }\alpha^{*}(w)(x)=y\text{ for some }w\in
T^{*}\text{ with }\pi_{R}(w)=g\text{ .}$

###### Proof.

It is clear that whenever $(R,\alpha)$ is actionable, so is
$(\overrightarrow{R},\alpha)$.

We first show that the union $\bar{\alpha}(g)$ of functions is itself a
function. Suppose that $g\star x=y$ and $g\star x=y^{\prime}$; that is, there
are words $w,w^{\prime}\in T^{*}$ with $\pi_{R}(w)=\pi_{R}(w^{\prime})=g$ and
$\alpha^{*}(w)(x)=y$ and $\alpha^{*}(w^{\prime})(x)=y^{\prime}$. Since
$\pi_{R}(w)=\pi_{R}(w^{\prime})=g$, we must have
$(w,w^{\prime})\in\overline{R}$. Since $R$ is confluent, there is a word $u\in
T^{*}$ with both $(w,u)$ and $(w^{\prime},u)$ in $\overrightarrow{R}$. Since
$(\overrightarrow{R},\alpha)$ is actionable, $(w,u)\in\overrightarrow{R}$ and
$\alpha^{*}(w)(x)=y$ implies that $\alpha^{*}(u)(x)=y$. The same reasoning
with $w^{\prime}$ and $y^{\prime}$ shows that $\alpha^{*}(u)(x)=y^{\prime}$.
So $y=y^{\prime}$ as wanted.

We now show that $\bar{\alpha}$ satisfies the definition of partial action.
Fix $a,b\in G_{R}$ and $x,y,z\in X$, and suppose that $a\star x=y$ and $b\star
y=z$. Then there are words $u,v\in T^{*}$ with $\pi_{R}(u)=a$ and
$\pi_{R}(v)=b$ and $\alpha^{*}(u)(x)=y$ and $\alpha^{*}(v)(y)=z$. Let $w:=vu$
be the concatenation of the two words. Then $\pi_{R}(w)=\pi_{R}(vu)=ba$ and
$\alpha^{*}(w)(x)=z$. So $(ba)\star x=z$. ∎

The generators we are interested in are $\phi$ and its inverse; the
$\epsilon_{p}$ for prime $p$, and their inverses; and the $t_{i}$ for
$i=1,2,\ldots k$.

######  Definition 2.32.

Foe $k\geq 3$, here are the four groups we are interested in and their
rewriting systems.

  * •

$\operatorname{Sym}_{k}$ is generated by
$T_{\operatorname{Sym}_{k}}:=\\{t_{1},t_{2},\ldots t_{k-1}\\}$ and defined by
the rewriting system

$R_{\operatorname{Sym}_{k}}:=\\{(t_{i}t_{i},\operatorname{id})\\}\cup\\{(t_{i}t_{j},t_{j}t_{i}):j\neq
i\pm 1\\}\cup\\{(t_{i}t_{j}t_{i},t_{j}t_{i}t_{j}):j=i\pm 1\\}\text{ .}$

  * •

$\operatorname{ASym}_{k}$ is generated by
$T_{\operatorname{ASym}_{k}}:=\\{t_{1},t_{2},\ldots t_{k-1},t_{k}\\}$ and
defined by the rewriting system

$R_{\operatorname{ASym}_{k}}:=\\{(t_{i}t_{i},\operatorname{id})\\}\cup\\{(t_{i}t_{j},t_{j}t_{i}):j\not\equiv
i\pm 1\pmod{k}\\}$ $\cup\\{(t_{i}t_{j}t_{i},t_{j}t_{i}t_{j}):j\equiv i\pm
1\pmod{k}\\}$

where addition of indices is modulo $k$, so including
$(t_{k}t_{1}t_{k},t_{1}t_{k}t_{1})$ and excluding $(t_{1}t_{k},t_{k}t_{1})$.

  * •

$\operatorname{ST}_{k}$ is generated by
$T_{\operatorname{ST}_{k}}:=T_{\operatorname{ASym}_{k}}\cup\\{\phi,\phi^{-1}\\}$
and defined by the rewriting system

$R_{\operatorname{ST}_{k}}:=R_{\operatorname{ASym}_{k}}\cup\\{(\phi\phi^{-1},\operatorname{id}),(\phi^{-1}\phi,\operatorname{id}),(\operatorname{id},\phi^{-1}\phi),(\operatorname{id},\phi\phi^{-1})\\}\cup$
$\cup\\{(\phi t_{i},t_{i+1}\phi):1\leq i\leq k\\}\cup\\{(t_{i+1}\phi,\phi
t_{i}):1\leq i\leq k\\},$

where addition of indices is again modulo $k$.

  * •

$\operatorname{ST}^{+}_{k}$ is generated by
$T_{\operatorname{ST}^{+}_{k}}:=T_{\operatorname{ST}_{k}}\cup\\{\epsilon_{p},\epsilon_{p}^{-1}:\mbox{
prime }p\\}$ and defined by the rewriting system

$R_{\operatorname{ST}^{+}_{k}}:=R_{\operatorname{ST}_{k}}\cup\\{(\epsilon_{p}\omega,\omega\epsilon_{p}),(\omega\epsilon_{p},\epsilon_{p}\omega)~{}:~{}p\text{
prime },\omega\in T_{\operatorname{ST}^{+}_{k}}\\}$
$\cup\\{(\epsilon_{p}\epsilon_{p}^{-1},\operatorname{id}),(\epsilon_{p}^{-1}\epsilon_{p},\operatorname{id})~{}:~{}p\text{
prime }\\}\text{ .}$

That is, $\epsilon_{p}$ commutes with everything and $\epsilon_{p}^{-1}$ is
its inverse.

When $k=2$, we drop the braid relation $t_{1}t_{2}t_{1}=t_{2}t_{1}t_{2}$. So,
$\operatorname{ASym}_{2}$ is the infinite dihedral group. We do not define
these groups when $k=1$.

######  Remark 2.33.

Interpreting $t_{i}$ as the transposition switching $i$ and $i+1$ in the set
$\\{1,2,\ldots,k\\}$ identifies $\operatorname{Sym}_{k}$ with the usual
symmetric group. For $k\geq 3$, the next group $\operatorname{ASym}_{k}$ is
well-known under many names including “affine symmetric group.” It has several
copies of $\operatorname{Sym}_{k}$ inside it, generated by
$T_{j}:=\\{t_{i}:i\neq j,1\leq i\leq k\\}$ for any fixed $j\leq k$. Even when
$k=2$, the group $\operatorname{ASym}_{k}$ admits a surjective homomorphism to
$\operatorname{Sym}_{k}$ sending $t_{i}$ to the transposition switching $i$
and $i+1$ for $i\neq k$ and sending $t_{k}$ to the one switching $1$ and $k$.
This homomorphism restricts to an isomorphism on each copy of
$\operatorname{Sym}_{k}$ inside $\operatorname{ASym}_{k}$. The kernel of this
homormophism is a copy of $\mathbb{Z}$. In particular,
$\operatorname{ASym}_{k}$ is infinite. It is clear from the rewriting system
that $\operatorname{ST}_{k}$ is the semidirect product of
$\operatorname{ASym}_{k}\unlhd\operatorname{ST}_{k}$ and the infinite cyclic
group generated by $\phi$. It can be useful to think of
$\operatorname{ST}_{k}$ and $\operatorname{ASym}_{k}$ as subgroups of
permutations of $\mathbb{Z}$, where $t_{i}$ is the permutation that switches
$i+rk$ with $i+1+rk$ for all $r\in\mathbb{Z}$ and $\phi$ is the shift by $1$.
We write $\pi:\operatorname{ASym}_{k}\to\operatorname{Sym}(\mathbb{Z})$ for
this group homomorphism.

######  Remark 2.34.

The generating sets of Definition 2.32 form a chain, and the groups are a
chain of groups
$\operatorname{Sym}_{k}<\operatorname{ASym}_{k}<\operatorname{ST}_{k}<\operatorname{ST}^{+}_{k}$.
We have presented $\operatorname{ST}_{k}$ as a semidirect product of
$\mathbb{Z}\cong\langle\phi\rangle$ with $\operatorname{ASym}_{k}$. The action
of conjugation by $\phi$ on $\operatorname{ASym}_{k}$ is given by the
automorphism $\eta:\operatorname{ASym}_{k}\to\operatorname{ASym}_{k}$ induced
by $t_{i}\mapsto t_{i+1}$. Likewise, we have presented
$\operatorname{ST}^{+}_{k}$ as a product of $\operatorname{ST}_{k}$ with
$\bigoplus_{i=0}^{\infty}\mathbb{Z}\cong\langle\epsilon_{p}~{}:~{}p\text{ a
prime }\rangle$. Thus, any element of $\operatorname{ST}^{+}_{k}$ may be
written in the form $\prod_{p}\epsilon^{m_{p}}\phi^{n}w$ where
$m_{p}\in\mathbb{Z}$, all but finitely many of which are zero,
$n\in\mathbb{Z}$, and $w\in\operatorname{ASym}_{k}$.

The first two groups, $\operatorname{Sym}_{k}$ and $\operatorname{ASym}_{k}$
are Coxeter groups (see [4]) with their usual Coxeter rewriting systems. The
first part of each, relations of the form $(t_{i}t_{i},\operatorname{id})$,
shorten the word they act on and are asymmetric; while the rest are symmetric
and do not change the length of the word they act on. Matsumoto’s Theorem
applies to $\operatorname{Sym}_{k}$ and $\operatorname{ASym}_{k}$, with
$R_{\text{cox}}$ consisting of the second and third sets of rewriting rules,
that is, not including the pairs $(t_{i}t_{i},\operatorname{id})$, and
$R_{\text{cox}+}$ being the whole rewriting system.

######  Fact 2.35 (Matsumoto’s Theorem [7]).

Any two $R_{\text{cox}+}$-equivalent, $R_{\text{cox}+}$-reduced words are also
$R_{\text{cox}}$-equivalent; and every word is $R_{\text{cox}+}$-reducible to
an $R_{\text{cox}+}$-reduced one. Since $R_{\text{cox}}$ is symmetric, any two
$R_{\text{cox}}$-equivalent words are $R_{\text{cox}}$-reducible to each
other. In particular, it follows that $R_{\text{cox}+}$ is confluent.

Recall that a word $w\in T^{*}$ is _$\overline{R}$ -reduced_ if it is not
$\overline{R}$-equivalent to any shorter word. The next corollary follows
easily from the hard result, Theorem 2.149 below, analogous to [8, Theorem
2.52] , that the braid relations $(t_{i}t_{i+1}t_{i},t_{i+1}t_{i}t_{i+1})$
hold for Ritt swaps.

######  Corollary 2.36.

Each of the four confluent rewriting systems of Definition 2.32 together with
the actions of its generators defined Definitions 2.11, 2.16, and 2.19 is
actionable, and the partial group action $\bar{\alpha}$ is also given by

$g\star x=y\text{ if and only if }\alpha^{*}(w)(x)=y\text{ for every reduced
}w\in T^{*}\text{ with }\pi_{R}(w)=g.$

###### Proof.

For $k\geq 3$, confluence of the first two rewriting systems
$R_{\operatorname{Sym}_{k}}$ and $R_{\operatorname{ASym}_{k}}$ is a special
case of Matsumoto’s Theorem. Confluence in the case of $k=2$ is triival. By
Remark 2.34, confluence of $R_{\operatorname{ST}_{k}}$ and of
$R_{\operatorname{ST}^{+}_{k}}$ follows.

For $k<3$, braid relations are irrelevant. For $k\geq 3$, Theorem 2.149
verifies the braid relations that

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

for any $i=1,2,\ldots k$ and any long decomposition $f$. That is, they are
equal when defined, and one is defined if and only if the other is. All other
instances of the definition of “actionable” are immediate.

We can replace “some $w\in T^{*}$ with $\pi_{R}(w)=g$” in the functional
version of Proposition 2.31 with “any reduced $w\in T^{*}$ with
$\pi_{R}(w)=g$” because the conclusion of Matsumoto’s theorem is this strong
version of confluence. ∎

######  Remark 2.37.

In [8] we worked with the language of monoid actions rather than partial group
actions and the space on which those monoids acted was the set of equivalence
classes up to skew-linear equivalence of decompositions of length $k$. The
actions of $\operatorname{Sym}_{k}$, $\operatorname{ST}_{k}$, and
$\operatorname{ST}^{+}_{k}$ given here correspond to the actions of the Ritt
Monoid $\operatorname{RM}_{k}$, the skew-twist monoid $\operatorname{ST}_{k}$,
and the augmented skew-twist monoid $\operatorname{ST}^{+}_{k}$ there. Our
$\operatorname{ST}_{k}$ is generated as a monoid by $t_{1}$, …, $t_{k-1}$,
$\phi$, and $\phi^{-1}$ because $t_{k}=\phi t_{1}\phi^{-1}$. The subgroup of
$\operatorname{ST}_{k}$ generated by $t_{1},t_{2},\ldots t_{k-2}$ along with
$\psi:=t_{k-1}\phi$ and $\gamma:=\phi^{-1}t_{k-1}$ would be the analog of the
border guard monoid $\operatorname{BG}_{k}$ from [8]; but the new intermediate
group $\operatorname{ASym}_{k}$ turns out to be much more convenient.

The two canonical forms for words in $\operatorname{Sym}_{k}$ from [8] fit
nicely with Matsumoto’s theorem. We shall use them here, not only with the
standard copy of $\operatorname{Sym}_{k}$ in $\operatorname{ASym}_{k}$, but
also with the other copies of Remark 2.33. The following are intuitive
explanations of analogues of [8, Definitions 5.6, 5.8, and 5.14].

######  Definition 2.38.

For $b+k>a>b$, the word $t_{a-1}t_{a-2}\ldots t_{b}$ in
$T_{\operatorname{Sym}_{k}}^{*}$ is called a _right-to-left transit_. In the
action of $\operatorname{Sym}_{k}$ on long decompositions, this drags the
factor $f_{b}$ left from its original position at $b$ to its new position at
$a$, across all the intermediate factors. A left-to-right transit is defined
symmetrically. A _transit_ is one of the two.

######  Remark 2.39.

A sequence of Ritt swaps in the right-to-left first canonical form is a
sequence of right-to-left transits whose action resembles an insert-sort:
having arranged the factors $f_{k}$ through $f_{i+1}$ in the correct order,
this sequence _inserts_ the next factor $f_{i}$ in the required place among
$f_{k}$ through $f_{i+1}$; and then proceeds to deal with $f_{i-1}$, and so
on, until all factors are arranged as wanted. We define left-to-right first
canonical form analogously.

Sometimes, there is a natural way to break a long decomposition into chunks.
Rooms of Section 2.1.3 and clusters in the technical Section 2.3 are two
examples. Words in second canonical form (with respect to such a
chunkification) first shuffle factors within each chunk as much as necessary
and only then move factors between chunks. This is closely related, but not
identical, to a merge-sort.

Given integers $c_{0}+k=c_{r}>c_{r-1}>\ldots>c_{1}>c_{0}$, a word
$T_{\operatorname{Sym}_{k}}^{*}$ is in _second canonical form with respect to
$\bar{c}$_ if it is of the form $vw_{r}w_{r-1}\ldots w_{1}$ where

  * •

each $w_{j}$ is a word in first canonical form, using only $t_{i}$ with
$c_{i+1}>i>c_{i}$; and

  * •

$v$ is a word in first canonical form that does not change the order of
factors originating within the same chunk.

We restate the key Propositions 5.11 and 5.15 from [8] in the language of
rewriting systems and observe that they are immediate consequences of
Matsumoto’s theorem

######  Proposition 2.40.

Every word in $T_{\operatorname{Sym}_{k}}^{*}$ is
$R_{\operatorname{Sym}_{k}}$-reducible to a word in first canonical form. For
every $\bar{c}$, every word in $T_{\operatorname{Sym}_{k}}^{*}$ is
$R_{\operatorname{Sym}_{k}}$-reducible to a word in second canonical form with
respect to $\bar{c}$.

###### Proof.

This proof is really a template that can likely work for other canonical
forms.

As should be clear, and is proven in detail in [8, Propositions 5.11 and
5.15], every permutation in $\operatorname{Sym}_{k}$ is represented by a word
in $T_{\operatorname{Sym}_{k}}^{*}$ in each of our canonical forms. It is
clear that words in these canonical forms are reduced: to write a permutation
$\sigma$ as a product of adjacent transpositions requires at least one such
transposition for each pair $a<b$ with $\sigma(b)<\sigma(a)$, and these
canonical forms use exactly this many generators. So, for each word $w$ in
$T_{\operatorname{Sym}_{k}}^{*}$, there is a reduced word $v$ in this
canonical form, representing the same permutation as $w$. That is, $v$ and $w$
are $R_{\operatorname{Sym}_{k}}$-equivalent, and $v$ is
$R_{\operatorname{Sym}_{k}}$-reduced; so by Matsumoto’s theorem, $w$ is
$R_{\operatorname{Sym}_{k}}$-reducible to $v$. ∎

######  Remark 2.41.

Words in first or second canonical form are themselves reduced since we have
shown that every word is not only equivalent to, but reducible to such a word.

The following refined version of the second canonical form, needed very soon,
showcases how long decompositions make it easy to talk about a period that is
not $(f_{k},f_{k-1},\ldots f_{1})$. Instead, we focus on the behavior of
$w\star$ on the substring $\left(f_{k+i},f_{k+i-1},\ldots,f_{k+1},f_{k},\ldots
f_{i+1}\right)$ separated into two chunks
$\left(f_{k+i},f_{k+i-1},\ldots,f_{k+1}\right)$ and $\left(f_{k},\ldots
f_{i+1}\right)$.

######  Lemma 2.42.

Fix some $i$ with $0<i<k$. Suppose $w\star f$ is defined for some long
decomposition $f$ and some word $w$ in $\\{t_{j}~{}:~{}j\neq i\\}$. Then there
are words $u_{L}^{+}$, $u_{R}^{+}$, $v$, $u_{L}^{-}$, and $u_{L}^{+}$ so that

  * •

$u_{L}^{+}u_{R}^{+}vu_{L}^{-}u_{R}^{-}\star f=w\star f$,

  * •

$u_{L}^{+}$ and $u_{L}^{-}$ are words in $\\{t_{j}~{}:~{}1\leq j<i\\}$,

  * •

$u_{R}^{+}$ and $u_{R}^{-}$ are words in $\\{t_{j}~{}:~{}i<j<k\\}$,

  * •

for some $m\leq\min\\{i,k-i\\}$, $v\star$ has the effect of swapping the block
$\left(f_{k},\ldots,f_{k-m+1}\right)$ with
$\left(f_{k+m},\ldots,f_{k+1}\right)$. In terms of our generators, $v$ takes
the form $v=v_{k+1-m}\cdots v_{k}$ where where $v_{j}=t_{m+j-1}\cdots t_{j}$.

###### Proof.

Indeed, using the second canonical form of [8, Proposition 5.15], we may find
words $u_{L}^{-}$, $u_{R}^{-}$, and $\hat{w}$ so that

  * •

$\hat{w}u_{L}^{-}u_{R}^{-}\star f=w\star f$,

  * •

$u_{L}^{-}$ is a word in $\\{t_{j}~{}:~{}1\leq j<i\\}$,

  * •

$u_{R}^{-}$ is a word in $\\{t_{j}~{}:~{}i<j<k\\}$, and

  * •

$\hat{w}$ is composed of nonoverlapping right-to-left transits across $k$:
there are numbers $k+i-1\geq\ell_{k}>\ell_{k-1}>\cdots>\ell_{i}\geq i$ so that
we may write $\hat{w}=\hat{w}_{i}\cdots\hat{w}_{k}$ with
$\hat{w}_{j}=t_{\ell_{j}}t_{\ell_{j}-1}\cdots t_{j}$ if $\ell_{j}\geq j$ and
$\hat{w}_{j}$ is empty and $\ell_{j}=j-1$ otherwise.

We now further decompose $\hat{w}$. Let $n:=\min\\{j~{}:~{}k>j\geq
i~{}\&~{}\ell_{j+1}\geq k\\}$.

If no such $n$ exists, then $\hat{w}$ is the empty word, so that we may take
$u_{R}^{+}$, $u_{L}^{+}$, and $v$ to all be the empty word.

Otherwise, let $u_{R}^{+}:=\hat{w}_{n}\cdots\hat{w}_{i}$. From the
construction, $u_{R}^{+}$ is a word in $\\{t_{j}~{}:~{}i<j<k\\}$. If $n=k$,
then $\hat{w}=u_{R}^{+}$ and we finish by taking $v$ and $u_{L}^{+}$ to be the
empty word. So, we may assume that $n<k$. Let $m:=k-n$. Consider the expanded
product

$\displaystyle\hat{w}_{n+1}\cdots\hat{w}_{k}$ $\displaystyle=$
$\displaystyle(t_{\ell_{n+1}}\cdots t_{n+1})\cdots(t_{\ell_{k-1}}\cdots
t_{k-1})(t_{\ell_{k}}\cdots t_{k})$ $\displaystyle=$
$\displaystyle(t_{\ell_{n+1}}\cdots t_{k+1}t_{k}\cdots t_{n+1})\cdots$
$\displaystyle(t_{\ell_{k-1}}\cdots t_{k+m}t_{k-1+m}\cdots
t_{k-1})(t_{\ell_{k}}\cdots t_{k+m+1}t_{k+m}\cdots t_{k})$

The blocks $t_{k-1+m}\cdots t_{k-1}$ and $t_{\ell_{k}}\cdots t_{k+m+1}$
commute. Hence, the word $\hat{w}$ is equivalent to

$(t_{\ell_{n+1}}\cdots t_{k+1}t_{k}\cdots t_{n+1})\cdots(t_{\ell_{k-2}}\cdots
t_{k-1+m}t_{k-2+m}\cdots t_{k-2})[t_{\ell_{k-1}}\cdots$
$t_{k+m}][t_{\ell_{k}}\cdots t_{k+m+1}][t_{k+m-1}\cdots t_{k-1}][t_{k+m}\cdots
t_{k}]$

Continuing in this way, if we set

$u_{L}^{+}:=[t_{\ell_{n+1}}\cdots t_{k+1}][t_{\ell_{n+2}}\cdots
t_{k+2}]\cdots[t_{\ell_{k}}\cdots t_{k+m+1}]\text{ ,}$

then we obtain the requisite decomposition. ∎

The following strong version of the braid relations will be useful in
analyzing wandering quadratics (see for example, the proof of Lemma 2.163).

######  Lemma 2.43.

Fix $b>a>b-k$. Suppose that $s=t_{(b,a]}$ is a transit from $b$ to $a$, and
$w$ is a word in $t_{i}$ for $b>i>a$, and $\widehat{w}$ is obtained from $w$
by replacing every $t_{i}$ by $t_{i-1}$. Then $sw=\widehat{w}s$.

###### Proof.

Apply the left-to-right first canonical form to maybe $(sw)^{-1}$ (see Remark
2.39). ∎

An identity of the form $w\star[\vec{f}]=[\vec{g}]$ with
$w\in\operatorname{ST}^{+}_{k}$ and long decompositions $\vec{f}$ and
$\vec{g}$ of $f$ and $g$, respectively, encodes an $(f,g)$-skew-invariant
curve [8, Definition 6.3]. Moreover, every such $(f,g)$-skew-invariant curve
is encoded by such an identity [8, Proposition 6.19]. Let us explain how this
relates our new formalism from Remark 2.13.

######  Remark 2.44.

When $k\neq 2$, Remark 2.13 permits a more elegant characterization of an
encoded curve.

If $f$ is a $k$-long decompositionand $w=w_{n}\cdots
w_{1}\in\operatorname{ST}^{+}_{k}$ where each $w_{j}$ is a generator not equal
to $t_{k}$, then a _witnessing sequence_ for $w\star[f]$ consists of a
sequence $\left(f^{0},\ldots,f^{n}\right)$ of $k$-long decompositionsand a
sequence $\left(L^{1},\ldots,L^{n}\right)$ of $k$-skew periodic sequences of
linear polynomials-linearso that

  * •

$f=f^{0}$,

  * •

if $w_{j}\neq t_{k}$, then $w_{j}\bullet(\phi\bullet
L^{j})^{-1}f^{j-1}L^{j}=f^{j}$, and

  * •

if $w_{j}=\phi$ or $w_{j}=\phi^{-1}$, then every component of $L^{j}$ is the
polynomial $x$.

We say that $\mathcal{A}$ is a correspondence encoded by this witnessing
sequence if $\mathcal{A}$ is a composition of curves
$\mathcal{B}_{n}\circ\cdots\circ\mathcal{B}_{1}$ where for each $j$

  * •

if $w_{j}=t_{i}$, then $\mathcal{B}_{j}$ is the curve defined by
$L_{1}^{j}(x_{2})=x_{1}$,

  * •

if $w_{j}=\epsilon_{p}$, then $\mathcal{B}_{j}$ is the curve defined by
$x_{2}=(L_{1}^{j})^{-1}(x_{1})^{p}$,

  * •

if $w_{j}=\epsilon_{p}^{-1}$, then $\mathcal{B}_{j}$ is the curve defined by
$x_{1}=(L_{1}^{j})^{-1}(x_{2})^{p}$,

  * •

if $w_{j}=\phi$, then $\mathcal{B}_{j}$ is the curve defined by
$x_{2}=f_{1}^{j}(x_{1})$, and

  * •

if $w_{j}=\phi^{-1}$, then $\mathcal{B}_{j}$ is the curve defined by
$x_{2}=f_{1}^{j+1}(x_{1})$.

######  Remark 2.45.

(See [8, Lemma 2.61(3)]) The correspondence $\mathcal{A}$ encoded by an
identity of the form $w\star[f]=[g]$ is well-defined up to pre- and post-
composition with linear functions corresponding to the choices of
representative of the classes $[f]$ and of $[g]$. Even though $\mathcal{A}$ is
defined in terms of sequences of generators, it is, in fact, well-defined for
elements of the group. The verification of this fact depends on knowing that
Ritt swaps satisfy the braid relations and will be proven with Theorem 2.149.

######  Remark 2.46.

(See [8, Proposition 6.19]) For any pair of non-exceptional polynomials $f$
and $g$, for any $(f,g)$-skew-invariant curve $\mathcal{A}$ and all long
decompositions $\vec{f}$ and $\vec{g}$ of $f$ and $g$, respectively, there is
a word $w\in\operatorname{ST}^{+}_{k}$ so that $\mathcal{A}$ is an irreducible
component of a curve encoded by the identity $w\star[\vec{f}]=[\vec{g}]$.
Recall from Remark 2.34 that we may assume that $w$ has the form
$\prod_{p}\epsilon_{p}^{m_{p}}\phi^{n}u$ where $m_{p}\in\mathbb{Z}$ and all
but finitely many are zero, $n\in\mathbb{Z}$, and
$u\in\operatorname{ASym}_{k}$.

If $\mathcal{A}$ is a skew-twist, then $w$ may be taken to be $\phi^{N}u$ for
some $N\in\mathbb{Z}$ and $u\in\operatorname{Sym}_{k}$. Conversely, any curve
so encoded is a skew-twist.

Indeed, any curve encoded by $v\phi^{N}u\star\vec{f}=\vec{g}$ with
$v,u\in\operatorname{Sym}_{k}$ and $N\in\mathbb{Z}$ is a skew-twist because
$v^{-1}\star\vec{g}$ is another long decomposition of $g$ and $u\star\vec{f}$
is another long decomposition of $f$.

####  2.1.3. Walls

Let us recall that we wish to characterize $(f,f^{\tau})$-skew-invariant
curves where $f$ is a non-exceptional polynomial and $\tau$ is another field
automorphism which commutes with $\sigma$. We know by Remark 2.46 that any
such curve will be a component of a curve encoded by an identity of the form
$w\star[f]=[f^{\tau}]$, where we have written $f$ for a long decomposition of
the polynomial $f$.

Before we take on some of the combinatorial complexity of the theory of
decompositions, let us pause to work out a simple case of Theorem 1.3 where
one of the $t_{i}$’s cannot act.

######  Definition 2.47.

For $f$ a $k$-long decompositionand an integer $i$ we say that $f$ has a wall
at $i$ if

  * •

for all words $w\in\operatorname{ASym}_{k}$, the action $t_{i}w\star f$ is not
defined and

  * •

for every prime number $p$ neither $\epsilon_{p}\star f$ nor
$\epsilon_{p}^{-1}\star f$ is defined.

The easiest way to have a wall in a decomposition is to have an unswappable
factor in the sense of Definition 2.9.

######  Lemma 2.48.

If $f$ is $k$-long decomposition, $i\in\mathbb{Z}$, and $f_{i}$ is
unswappable, then $f$ has walls at $i-1$ and at $i$.

###### Proof.

Let us check that for no $w\in\operatorname{ST}_{k}$ is $t_{i}w\star f$
defined. We do this by showing by induction on the length of a word in the
generators representing $w$ that, if defined, $w\star f$ has an unswappable
factor at $i$. This is trivial for the empty word. By induction, it suffices
to consider the case that $w=t_{j}$ for some $j$. If $j\equiv i$ or
$i-1\pmod{k}$, then $t_{j}\star f$ is not defined because $f_{i}$ is
unswappable. Otherwise, the $i^{\text{th}}$ factor of $t_{j}\star f$ is
$f_{i}$. From this we see that neither $t_{i}w\star f$ nor $t_{i-1}w\star f$
is defined.

For the second part of the definition of a wall, observe that whenever
$\epsilon_{p}^{\pm}\star f$ is defined, then every factor of $f$ must be
swappable (see Definition 2.19), which is not the case for $f_{i}$. ∎

######  Remark 2.49.

In Subsection 2.3, we will work with other classes of $k$-long decomposition’s
with walls.

######  Definition 2.50.

A _wall set_ for a $k$-long decomposition$f$ is a translate ${\mathcal{W}}$ of
$M\mathbb{Z}$ for an integer $M$ dividing $k$ such that $f$ has a wall at $i$
for all $i\in{\mathcal{W}}$.

A _room_ of $({\mathcal{W}},f)$ consists of the $M$ factors of $f$ between
consecutive elements of ${\mathcal{W}}$. For example, if $k=16$ and $M=4$ and
${\mathcal{W}}=3+4\mathbb{Z}$, one room of $({\mathcal{W}},f)$ is
$(f_{7},f_{6},f_{5},f_{4})$.

Two rooms are _different_ if they are different modulo $k$. There are
$\frac{k}{M}$ different rooms. Continuing the above example,
$(f_{23},f_{22},f_{21},f_{20})$ is not a different room from
$(f_{7},f_{6},f_{5},f_{4})$, but $(f_{27},f_{26},f_{25},f_{24})$ is.

######  Proposition 2.51.

If ${\mathcal{W}}$ is a wall set for a $k$-long decomposition$f$ with $R$
rooms and $w\in\operatorname{ASym}_{k}$ with $w\star f$ defined, then $w$ may
be represented as $w_{R}\cdots w_{2}w_{1}$ where each $w_{i}$ acts on factors
in a different $i^{\text{th}}$ room of $({\mathcal{W}},f)$. Moreover,
$\mathcal{W}$ is still a wall set for $w\star f$.

###### Proof.

If ${\mathcal{W}}$ is a wall set for $f$ and the Ritt swap $t_{i}\star f$ is
defined, the two factors swapped are in the same room.

If two Ritt swaps $t_{i}$ and $t_{j}$ act on factors in different rooms, the
indices $i$ and $j$ cannot be adjacent modulo $k$, so the Ritt swaps commute.

To complete the proof, present $w$ as a product of $t_{i}$’s, use commutation
to collect all of the $t_{i}$’s with $i$ in the $j^{\text{th}}$ room in order
to form $w_{j}$.

That $\mathcal{W}$ is a wall set for $w\star f$ follows from the definition of
a wall. ∎

Recall from Remark 2.34 that conjugation by $\phi$ induces the automorphism
$\eta$ of $\operatorname{ASym}_{k}$ given by $t_{i}\mapsto t_{i+1}$.

If $i_{0}+M\mathbb{Z}$ is a wall set of $f$ and $w_{i}$ acts on the $i$th room
of $f$, then $\eta^{jM}(w_{i})$ acts on the $(i+j)^{\text{th}}$ room.

######  Proposition 2.52.

Suppose that $P$ is a polynomial admitting the decomposition
$P=P_{k}\circ\cdots\circ P_{1}$ with associated long decomposition $\vec{P}$
and that $\vec{P}$ has a wall at $i$. Then any $(P,P^{\tau})$-skew invariant
curve is a skew-twist.

###### Proof.

From Remark 2.46 and the fact that no $\epsilon_{p}^{\pm 1}\star\vec{P}$ is
defined, every $(P,P^{\tau})$-skew-invariant curve is encoded by an identity
of the form $\phi^{N}w\star\vec{P}=\vec{P}^{\tau}$ with
$w\in\operatorname{ASym}_{k}$ and $N\in\mathbb{Z}$. In fact, because we
$\vec{P}$ has a wall at $i$, $w$ may be expressed as a reduced word in
$\\{t_{j}~{}:~{}j\not\equiv i\pmod{k}\\}$.

If $i=k$, then curve encoded by this identity is already a skew-twist and we
are done. So, from now on, we take $1\leq i<k$.

We break into two cases depending on whether $k$ divides $N$ or not.

Case $N$ is not divisible by $k$: Write $N=N^{\prime}k+L$ with $0<L<k$. Let
$M:=\gcd(k,L)$, let $R:=\frac{k}{M}$, and set $\mu:=\tau\sigma^{-N^{\prime}}$.
We work instead with the identity $\phi^{L}w\star\vec{P}=\vec{P}^{\mu}$. From
the hypothesis that we have a wall at $i$, it follows that $i+M\mathbb{Z}$ is
a wall set for $\vec{P}$. Without loss of generality, $0<i<M$. By Proposition
2.51 we may express $w$ as a product $w_{R}\cdots w_{1}$ where each $w_{s}$
acts on the $s^{\text{th}}$ room. Setting $\tilde{w}_{R}:=\eta^{L}(w_{R})$,

we have $\phi^{L}w_{R}\cdots
w_{1}\star\vec{P}=\tilde{w}_{R}\phi^{L}w_{R-1}\cdots
w_{1}\star\vec{P}=\vec{P}^{\mu}$. Taking $u$ to be the reverse word of
$\tilde{w}_{R}$, we have $\phi^{L}w_{R-1}\cdots
w_{1}\star\vec{P}=u\vec{P}^{\mu}$ where now $u$, $w_{1}$, …, $w_{R-1}$ are all
words omitting $t_{k}$. Such an equation encodes a skew-twist curve, as
required.

Case $N$ is divisible by $k$: We will show in this case that $w$ may be
expressed without $t_{k}$. Write $N=kN^{\prime}$. Then we have
$\phi^{kN^{\prime}}w\star\vec{P}=\vec{P}^{\tau}$ from which we conclude that
$w\star\vec{P}=\phi^{-kN^{\prime}}\vec{P}^{\tau}=\vec{P}^{\tau\sigma^{-N^{\prime}}}$.
Write $\mu=\tau\sigma^{-N^{\prime}}$, we would then have
$w\star\vec{P}=\vec{P}^{\mu}$.

Let us focus on the behavior of $w\star$ on the substring
$\left(P_{i-1}^{\sigma},\ldots,P_{1}^{\sigma},P_{k},\ldots
P_{i+1},P_{i}\right)$.

By Lemma 2.42, we may find words $u_{L}^{+}$, $u_{R}^{+}$, $v$, $u_{L}^{-}$,
and $u_{L}^{+}$ so that

  * •

$u_{L}^{+}u_{R}^{+}vu_{L}^{-}u_{R}^{-}\star\vec{P}=w\star\vec{P}$,

  * •

$u_{L}^{+}$ and $u_{L}^{-}$ are words in $\\{t_{j}~{}:~{}1\leq j<i\\}$,

  * •

$u_{R}^{+}$ and $u_{R}^{-}$ are words in $\\{t_{j}~{}:~{}i<j<k\\}$,

  * •

for some $m\leq\min\\{i,k-i\\}$, $v\star$ has the effect of swapping the block
$\left(P_{k},\ldots,P_{k-m+1}\right)$ with
$\left(P^{\sigma}_{k+m},\ldots,P_{k+1}^{\sigma}\right)$. In terms of our
generators, $v$ takes the form $v=v_{k+1-m}\cdots v_{k}$ where where
$v_{j}=t_{m+j-1}\cdots t_{j}$.

We will show that $v$ must be trivial so that $w$ may be expressed without
$t_{k}$.

Observe that because $t_{k}$ does not appear in $u_{L}^{+}u_{L}^{-}$, the
result of applying this word to $\vec{P}$ is another long decomposition of
$P$, which we will temporarily call $\vec{Q}$. Unless $v$ is trivial, for the
action $v\star\vec{Q}$ to be defined, it is necessary that (possibly replacing
$\vec{Q}$ by a linearly equivalent long decomposition) either

  * •

the polynomial $Q_{k+m}\circ Q_{k+m-1}\circ\cdots\circ Q_{k-m+1}$ is an odd
degree Chebyshev polynomial and for $k-m<j<k<s\leq k+m$ $\deg(Q_{j})$ and
$\deg(Q_{s})$ are distinct prime numbers or

  * •

the polynomial $Q_{k+m}\circ\cdots\circ Q_{k+1}$ is a monomial of degree prime
to every monomial appearing amongst the set $\\{Q_{j}~{}:~{}k-m<j\leq k\\}$ or

  * •

the polynomial $Q_{k}\circ\cdots\circ Q_{k-m+1}$ is a monomial of degree prime
to every monomial appearing amongst the set $\\{Q_{j}~{}:~{}k<j\leq k+m\\}$.

Each of these possibilities leads to a contradiction. Let now
$\vec{R}:=v\star\vec{Q}$.

In the first case, the degree of the polynomial $R_{k}\circ\cdots\circ R_{i}$
is different from that of the polynomial $Q_{k}\circ\cdots\circ Q_{i}$.
However, $\deg(Q_{k}\circ\cdots\circ Q_{i})=\deg(P_{k}\circ\cdots\circ P_{i})$
and because $\vec{P}^{\mu}=w\star\vec{P}=u_{L}^{+}u_{R}^{+}\star R$ and
$u_{R}^{+}$ being a word in $\\{t_{j}~{}:~{}i<j<k\\}$ does not affect the
resulting polynomial obtained by composing the terms from $i$ to $k$,
$\deg(R_{k}\circ\cdots\circ R_{i})=\deg(P_{k}^{\mu}\circ\cdots\circ
P_{i}^{\mu})=\deg(P_{k}\circ\cdots\circ P_{i})$.

The other two cases are handled similarly noting that the number of instances
of a given monomial appearing in the block from $i$ to $k$ is also invariant.
With this, we end the proof of the proposition in the case that $k$ divides
$N$. Notice that in this case, the plain skew-twist is given by a skew-
compositional power of $P$.

∎

######  Corollary 2.53.

If $P$ is a polynomial having an unswappable compositional factor, then
Theorem 1.3 holds for $P$.

###### Proof.

By Lemma 2.48 any decomposition of $P$ has a wall. By Proposition 2.52 any
$(P,P^{\tau})$-skew-invariant curve is a skew-twist. ∎

###  2.2. in/out degrees

In this section, we focus on the use of the in-degree and out-degree functions
as a way to study compositional identities. A highlight of this section is the
proof of Theorem 1.3 for the case when the polynomial $P$ has a clean
$\mathsf{C}$-free long decomposition $f$.

######  Definition 2.54.

A long decomposition $f$ is a _clean $\mathsf{C}$-free long decomposition_ if
all factors $f_{i}$ are monomials or Ritt polynomials, at least one factor is
not a monomial, and all of factors are $\mathsf{C}$-free. (See Definition
2.9.)

Let us record a easy and useful fact about linear equivalence between clean
$\mathsf{C}$-free long decompositions.

######  Lemma 2.55.

Linear equivalence between two clean $\mathsf{C}$-free long decompositions is
always witnessed by scalings.

###### Proof.

Suppose that $f$ is a clean $\mathsf{C}$-free long decomposition and $L$ is a
$k$-skew periodic sequence of linear polynomials-linearand $g$ is a clean
$\mathsf{C}$-free long decomposition linearly related to $f$ via $L$. By
definition of linear equivalence, we have $g_{i}=L_{i+1}^{-1}\circ f_{i}\circ
L_{i}$ for all $i$. By [8, Theorem 3.15], this forces $L_{i+1}$ to be a
scaling. ∎

As in the other cases of Theorem 1.3, a $(P,P^{\tau})$ skew-invariant curve
$\mathcal{C}$ is encoded by $u\star f=f^{\tau}$ for some
$u\in\operatorname{ST}^{+}_{k}$. To show that $\mathcal{C}$ is a skew-twist
curve, we show in Lemma 2.98 that we may take $u\in\operatorname{ST}_{k}$ so
that $\phi^{N}w\star f=f^{\tau}$ for some $w\in\operatorname{ASym}_{k}$. We
will show that the curve $\mathcal{C}$ is also encoded by
$u_{1}\phi^{N}u_{2}\star f=f^{\tau}$ for some
$u_{1},u_{2}\in\operatorname{Sym}_{k}$.

The key idea of the proof in this case is to associate certain combinatorial
data, which we call _nomodata_ to $f$ and then to find another long
decomposition $g$ of the same polynomial for which this nomodata is $e$\-
periodic for a certain special $e$.

######  Definition 2.56.

Let $f$ be a clean $\mathsf{C}$-free long decomposition, and let
$w\in\operatorname{ST}_{k}$ be such that $w\star f=f^{\tau}$ encodes a curve
$\mathcal{C}$ parametrized by $(A(t),B(t))$ for some polynomials $A$ and $B$.

Let $n_{A}$, $n_{B}$, and $n_{f}$ be the number of non-monomial factors in
$A$, $B$, and one $k$-period of $f$, respectively.

The _echo of $w\star f=f^{\tau}$_ is $e:=\gcd(n_{f},(n_{B}-n_{A}))$.

In Section 2.2.1, we set up and analyze the nomodata that is used throughout
this section. In Section 2.2.2, we find some $v\in\operatorname{ASym}_{k}$ for
which $v\star f$ has $e$-periodic nomodata. Then in Section 2.2.3, we show
that the same can be accomplished with some $u\in\operatorname{Sym}_{k}$. Then
$g:=u\star f$ is the desired other long decomposition of the same polynomial,
with $e$-periodic nomodata. The skew-invariant curve $\mathcal{C}$ is now also
encoded by $\phi^{N}w^{\prime}\star g=g^{\tau}$ for some
$w^{\prime}\in\operatorname{ASym}_{k}$. We observe (Lemma 2.97) that
$w^{\prime}$ cannot change the nomodata of $g$, and it will follow that all it
can do is permute adjacent monomials. The proof ends just like the proof in
the “walls” case, with “puddles” of monomials between non-monomials replacing
the “rooms” between walls.

####  2.2.1. Scaffolding

In this subsection we identify and analyze the combinatorial data of a clean
$\mathsf{C}$-free long decomposition $f$ in full generality, that is, without
assuming that $f$ has anything to do with the Mahler problem.

With the following definition, we recall the definitions of in-degree and out-
degree from Definition 2.7 and then decompose these into their prime
components.

######  Definition 2.57.

Fix a polynomial $u$ with no initial nor terminal, compositional nor
multiplicative monomial factors. Recall that the in-degree and out-degree of a
Ritt polynomial $g(x)=x^{k}u(x^{\ell})^{n}$ are

$\operatorname{in-deg}(g):=\ell\mbox{ and }\operatorname{out-deg}(g):=n.$

We decompose the in- and out-degrees into their prime components by the
formulae

$\operatorname{in-deg}(g)=\prod_{p\in\mathcal{P}}p^{\operatorname{in-
deg}(g,p)}$

and

$\operatorname{out-deg}(g)=\prod_{p\in\mathcal{P}}p^{\operatorname{out-
deg}(g,p)}$

where the products are taken over the set $\mathcal{P}$ all of the prime
numbers.

The condition on $u$ just means that $u$ has a non-zero constant coefficient,
is not a power of another polynomial, and cannot be written as $u(x)=v(x^{p})$
for any polynomial $v$ and any integer $p\geq 2$.

Each non-monomial Ritt polynomial has a unique representation of this form, so
in-degree and out-degree are indeed properties of the polynomial itself.

These integers $k,\ell,n$ are the same for two scaling-related Ritt
polynomials. Thus, by Lemma 2.55 the “in-degree of $f_{i}$” (respectively,
“out-degree of $f_{i}$”) is a property of the linear-equivalence class of a
clean $\mathsf{C}$-free long decomposition $f$.

######  Definition 2.58.

An increasing function $\alpha:\mathbb{Z}\to\mathbb{Z}$ is a _non-monomial
listing function_ for a clean $\mathsf{C}$-free long decomposition $f$ if

  * •

for each $j\in\mathbb{Z}$, $f_{\alpha(j)}$ is _not_ a monomial, and

  * •

for each $i\in\mathbb{Z}$, if $f_{i}$ is not a monomial, then $i$ is in the
range of $\alpha$.

A _nomodata_ for a clean $\mathsf{C}$-free long decomposition $f$ is a
quadruple $(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$
where

  * •

$\alpha$ is a non-monomial listing function for $f$;

  * •

$\operatorname{in}:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{N}$ is
defined by $\operatorname{in}(j,p):=\operatorname{in-deg}(f_{\alpha(j)},p)$;

  * •

$\operatorname{out}:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{N}$ is
defined by $\operatorname{out}(j,p):=\operatorname{out-deg}(f_{\alpha(j)},p)$;
and

  * •

$\operatorname{pud}:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{N}$ is
defined by

$\operatorname{pud}(j,p):=\\#\\{i\in(\alpha(j-1),\alpha(j))~{}:~{}f_{i}=x^{p}\\}.$

######  Remark 2.59.

The last part $\operatorname{pud}$ of the nomodata of $f$ keeps track of the
monomials $f_{i}$ with $\alpha(j-1)<i<\alpha(j)$:

$\prod_{i=\alpha(j-1)+1}^{\alpha(j)-1}\deg(f_{i})=\prod_{p\in\mathcal{P}}p^{\operatorname{pud}(j,p)}.$

We informally say that these monomials are the $j$th puddle, viewing the long
decomposition $f$ as a sequence of alternating non-monomials and puddles.
These puddles may be empty.

######  Remark 2.60.

The components $\operatorname{in}$, $\operatorname{out}$, and
$\operatorname{pud}$ of a nomodata are two-variable functions of $j$, an
integer, and $p$ a prime. Sometimes, we will drop $p$ from the notation
regarding them simply as functions of the variable $j$.

######  Remark 2.61.

If
$(\alpha(j),\operatorname{in}(j,p),\operatorname{out}(j,p),\operatorname{pud}(j,p))$
is a nomodata for $f$, then
$(\alpha(j+m),\operatorname{in}(j+m,p),\operatorname{out}(j+m,p),\operatorname{pud}(j+m,p))$
is another nomodata for the same $f$ for any $m\in\mathbb{Z}$. Conversely, any
two non-monomial listing functions $\alpha$ and $\beta$ for $f$ are related by
a shift: $\beta(j)=\alpha(j+m)$ for some $m\in\mathbb{Z}$. The nomodata for
$f$ is determined by the non-monomial listing function.

If there are exactly $m$ non-monomials in one $k$-period of $f$ (that is,
amongst $f_{1},\ldots,f_{k}$), then $\alpha(j+m)=\alpha(j)+k$ for all $j$; and
the three degree functions are $m$-periodic.

######  Remark 2.62.

If $(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$ is a
nomodata for $h$, then
$(\alpha-N,\operatorname{in},\operatorname{out},\operatorname{pud})$ is a
nomodata for $\phi^{N}\star h$.

######  Remark 2.63.

If $\tau$ is a field automorphism, then $f$ and $f^{\tau}$ obtained from $f$
by applying $\tau$ to all the coefficients of $f$ have the same nomodata.

######  Remark 2.64.

The index $j$ of a non-monomial factor $f_{\alpha(j)}$ is often the more
reliable counter than the index $i$ of the factor $f_{i}$. For example, the
periodicity of nomodata is better stated in terms of $j$.

The key feature of the nomodata is that it completely determines whether
$t_{i}\star f$ is defined and the nomodata of $t_{i}\star f$ can be read off
from the nomodata of $f$. The following trace function keeps track of this.

######  Definition 2.65.

Suppose that
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$ is a
nomodata for a long decomposition $f$, and suppose that $t_{i}\star f$ is
defined. The _trace of $t_{i}$ on $(f,\alpha)$_,
$\operatorname{trace}_{t_{i},f,\alpha}$, is the following function
$\lambda:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{Z}$.

  * •

If $i$ and $i+1$ are not in the range of $\alpha$,
the trace $\lambda$ is the constant function zero.

  * •

If $i=\alpha(j)$ and $f_{i+1}$ is the monomial $x^{p}$,
then $\lambda(x,p)=1$ for $x\equiv j(\mod m)$, and zero for all other inputs.

  * •

If $i+1=\alpha(j)$ and $f_{i}$ is the monomial $x^{p}$,
then $\lambda(x,p)=-1$ for $x\equiv j(\mod m)$, and zero for all other inputs.

If $w$ is a word in $t_{i}$ with $w\star f$ defined, the _trace of $w$ on
$(f,\alpha)$_ is the recursive sum:

$\operatorname{trace}_{ut_{i},f,\alpha}:=\operatorname{trace}_{u,t_{i}\star
f,\beta}+\operatorname{trace}_{t_{i},f,\alpha}\text{, }$

where
$\beta=\alpha+\sum_{p\in\mathcal{P}}\operatorname{trace}_{t_{i},f,\alpha}$.

In general, we write $w\star(f,\alpha)=(g,\beta)$ when $g=w\star f$ and
$\beta=\alpha+\sum_{p\in\mathcal{P}}\operatorname{trace}_{w,f,\alpha}$. This
notation is justified by Lemma 2.67 below.

######  Remark 2.66.

It is easy to see that the trace of $w$ on $(f,\alpha)$ is well-defined for
$w\in\operatorname{ASym}_{k}$, independent of its representation as a product
of generators.

######  Lemma 2.67.

Suppose that
$(\alpha,\operatorname{in}_{f,\alpha},\operatorname{out}_{f,\alpha},\operatorname{pud}_{f,\alpha})$
is a nomodata for a $k$-long decomposition$f$; that
$w\in\operatorname{ASym}_{k}$ with $w\star f$ defined; that
$\lambda=\operatorname{trace}_{w,f,\alpha}$ is the trace of $w$ on
$(f,\alpha)$. Then a nomodata for $g:=w\star f$ can be computed as follows.
The function

$\beta(j):=\alpha(j)+\sum_{p}\lambda(j,p)$

identifies the non-monomials of $g$.

$\operatorname{in}_{g,\beta}(j,p)=\operatorname{in}_{f,\alpha}(j,p)-\lambda(j,p)\text{,
}$
$\operatorname{out}_{g,\beta}(j,p)=\operatorname{out}_{f,\alpha}(j,p)+\lambda(j,p)\text{,
and}$
$\operatorname{pud}_{g,\beta}(j,p)=\operatorname{pud}_{f,\alpha}(j,p)+\lambda(j,p)-\lambda(j-1,p)\text{
.}$

###### Proof.

This easy induction on the length of a word representing $w$ is left to the
reader. ∎

######  Definition 2.68.

The _admissibility conditions_ for an $m$-periodic function
$\lambda:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{Z}$ to be a trace of a
word acting on a $k$-long decomposition$f$ with $m$ non-monomials per
$k$-period and with nomodata $(\alpha,in,out,pud)$ are

  1. (1)

$-\operatorname{out}(j,p)\leq\lambda(j,p)\leq in(j,p)$ for all $j$ and $p$;

  2. (2)

$\operatorname{pud}(j,p)+\lambda(j,p)-\lambda(x-1,p)\geq 0$ for all $j$ and
$p$;

  3. (3)

for each $p$, if $\operatorname{pud}(j,p)=0$ for all $j$, then
$\lambda(j,p)=0$ for all $j$.

The first two admissibility conditions are necessary because the functions
$\operatorname{in}_{f,\alpha}-\lambda$,
$\operatorname{out}_{f,\alpha}+\lambda$, and
$\operatorname{pud}_{f,\alpha}(j,p)+\lambda(j,p)-\lambda(j-1,p)$ are parts of
the nomodata for $w\star(f,\alpha)$, so they must be non-negative. The last is
also clearly necessary: if a monomial $x^{p}$ is not available anywhere in
$f$, actions by $\operatorname{ASym}_{k}$ cannot change the $p$-parts of in-
and out-degrees of non-monomials in $f$. The main result of this subsection is
Theorem 2.74 showing that these admissibility conditions are also sufficient:
given $f$ with nomodata
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$ and a
function $\lambda$ satisfying the admissibility conditions, we shall produce a
word $w$ with $w\star f$ defined and with trace $\lambda$. We will build this
word out of long-swaps, each of which moves its monomial through a puddle and
then swaps it with a non-monomial.

######  Definition 2.69.

If $i$ and $i+1$ are not in the range of $\alpha$, then $t_{i}$ is a _puddle-
swap_ for $(f,\alpha)$. A _long-swap_ for $(f,\alpha)$ is a word of the form

$t_{\alpha(j)}t_{\alpha(j)+1}\ldots t_{i-1}t_{i}\text{ for
}i\leq\alpha(j+1)\text{; or }t_{\alpha(j)-1}t_{\alpha(j)-2}\ldots t_{i}\text{
for }i>\alpha(j-1)\text{ .}$

The first option above is a left-to-right transit (see Definition 2.38) that
brings a monomial through the puddle to the left of $\alpha(j)$, followed by
the Ritt swap of that monomial with the non-monomial $f_{\alpha(j)}$.

If $x^{p}$ is a monomial that swaps with the non-monomial when a long-swap $w$
acts, we call $w$ a _$p$ -long-swap_.

######  Remark 2.70.

  1. (1)

The concepts in Definition 2.69 only depend on the range of $\alpha$. Thus,
they are the same for different nomodata for the same $f$.

  2. (2)

Puddle-swaps in different puddles commute.

  3. (3)

Suppose that $w$ is a word in puddle-swaps for $(f,\alpha)$, and that $f$ has
$r$ puddles per period. Then $w\approx w_{r}\ldots w_{1}$ where each $w_{j}$
is a word in puddle-swaps in the $j$th puddle; and these $w_{j}$ commute with
each other.

  4. (4)

If $w$ is a word in puddle-swaps for $(f,\alpha)$, then
$\operatorname{trace}_{w,f,\alpha}$ is identically zero. Lemma 2.71 provides a
converse.

######  Lemma 2.71.

Suppose that $w$ is a reduced word for which $w\star f$ is defined and
$\operatorname{trace}_{w,f,\alpha}$ is identically zero. Then $w$ is a product
of puddleswaps for $(f,\alpha)$.

###### Proof.

Fix a non-monomial $f_{\alpha(j)}$. If suffices to show that $t_{\alpha(j)}$
and $t_{(\alpha(j)+1)}$ do not occur in $w$.

Let $w_{x}$ be the initial segment of $w$ of length $x$, so
$w_{x}\star(f,\alpha)$ is an intermediate decomposition that occurs as $w\star
f$ is carried out generator by generator. Let $I(x)$ be in-degree of the
$j^{\text{th}}$ non-monomial of $w_{x}\star(f,\alpha)$. If $I(x)$ is constant
in $x$, we are done. Otherwise, there is some prime $p$ for which the $p$-part
of $I$ changes at some points. We work out the case that it increases at some
point; the other case is symmetric. Let $y$ and $z$ be such that the $p$-part
of $I(x)$ attains its maximal value for $y<x<z$ but not at $y$ or $z$; and let
$u:=w_{[z,y]}$ be a middle subword of $w$.

Let us pause and regroup. We now work with $(g,\beta):=w_{y-1}\star(f,\alpha)$
and the word $u$, focusing on the non-monomial factor $g_{\beta(j)}$ and the
monomial $x^{p}$. Since the first thing that happens as $u\star g$ is
evaluated is the $p$-part of the in-degree of $g_{\beta(j)}$ increasing, it
follows that $w_{y}$ (the first letter of $u$) is $t_{\alpha(j)-1}$ and
$g_{\alpha(j)-1}$ is the monomial of degree $p$.

For $x:=y,y+1,\ldots,z$, let $N(x)$ and $M(x)$ be the positions of the
$j^{\text{th}}$ nonmonomial and this particular degree-$p$ monomial in
$u_{x}\star f$, where $u_{x}=w_{[x,y]}$. Because the $p$-part of the the in-
degree of the non-monomial does not change again, for $x=y+1,\ldots,z-1$ we
always have $M(x)>N(x)$, and there are no degree-$p$ monomials between these.
Because at the end, the $p$-part of the the in-degree of the non-monomial
decreases, we must have a degree-$p$ monomial immediately to the left of this
non-monomial at the end, so $M(z-1)=N(z-1)+1$.

Case 1: If this degree-$p$ monomial does not cross any other non-monomials as
$u\star g$ is carried out, then it stays in the $(j+1)^{\text{st}}$ puddle of
all intermediate decompositions. We first rewrite $u$, keeping the same
length, so that it stays at the right edge of that puddle, except to let
through other-degree monomials who cross our non-monomial. We then rewrite
$u$, decreasing its length by $2$, so that this degree-$p$ monomial stays on
the right, rather than on the left, of the non-monomial throughout. The
decrease in length is a contradiction.

Case 2: If this degree-$p$ monomial does cross other non-monomials, it must in
particular cross $g_{\alpha(j+1)}$. Consider the middle subword $v$ of $u$
which begins with this degree-$p$ monomial crossing $g_{\alpha(j+1)}$ right-
to-left and ends with it crossing back. This $v$ is shorter than $u$, and
satisfies the same hypotheses.

∎

######  Lemma 2.72.

Suppose that $\lambda:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{Z}$ looks
like the trace of one Ritt swap in the sense that there is exactly one pair
$(j,p)$ with $\lambda(j,p)=\pm 1$ and $\lambda(j^{\prime},p^{\prime})=0$ for
all other pairs. Suppose that $\lambda$ satisfies the admissibility conditions
for some $(f,\alpha)$. Then there is a long-swap $v$ with trace $\lambda$ on
$(f,\alpha)$.

###### Proof.

We work out the case that $\lambda(j,p)=1$. The other case is handled
symmetrically.

By the second admissibility condition, there is a monomial $x^{p}$ in the
puddle to the left of $f_{\alpha(j)}$, say $x_{p}=f_{i}$ with
$\alpha(j+1)>i>\alpha(j)$, and $i$ is minimal such. The transit
$w=t_{\alpha(j)+1}\cdots t_{i-1}$ is a word in puddle-swaps for $(f,\alpha)$.
By the first admissibility condition, $\operatorname{in-
deg}(f_{\alpha(j)},p)\geq\lambda(j,p)=1$. Thus, $t_{\alpha(j)}w\star f$ is
defined and has trace $\lambda$ on $(f,\alpha)$. ∎

######  Lemma 2.73.

Suppose that $w_{i}\star f$ is defined for $i=1,2$; that $w_{i}$ is a
$p_{i}$-longswap for $f$; and that $p_{1}\neq p_{2}$. Then there is a word
$v_{2}$ such that $v_{2}w_{1}\star f$ is defined, and $v_{2}$ is a
$p_{2}$-longswap for $w_{1}\star f$, and the trace of $v_{2}$ on $w_{1}\star
f$ is the same as the trace of $w_{2}$ on $f$.

###### Proof.

If the factors moved by $w_{1}$ and $w_{2}$ are disjoint, then $w_{1}$ and
$w_{2}$ already commute. Let us consider a case where $w_{1}$ and $w_{2}$
affect the same puddle but the nonmonomials on opposite ends of that puddle.
Here we treat the subcase where $w_{1}$ is right-to-left and $w_{2}$ is left-
to-right. The other subcase is handled similarly. So,
$w_{1}=t_{\alpha(j)-1}\cdots t_{a+1}t_{a}$ and $w_{2}=t_{\alpha(j-1)}\cdots
t_{b-1}t_{b}$ for some $j$, and $\alpha(j)>b+1>a>\alpha(j-1)$. Set
$v_{2}:=t_{\alpha(j-1)}\cdots t_{b-1}$ ; so that $w_{2}=v_{2}t_{b}$.

The other cases where $w_{1}$ and $w_{2}$ affect the same non-monomial are
equally tedious and straightforward. ∎

######  Theorem 2.74.

Fix $(f,\alpha)$ with $m$ non-monomials per period, and suppose that
$\lambda:\mathbb{Z}\times\mathcal{P}\rightarrow\mathbb{Z}$ is an $m$-periodic
function satisfying the admissibility conditions (see Definition 2.68). Then
there is some $w\in\operatorname{ASym}_{k}$ such that $w\star(f,\alpha)$ is
defined, and the trace of $w$ on $(f,\alpha)$ is $\lambda$.

###### Proof.

The third condition in Definition 2.68 implies that $\lambda$ is supported on
finitely many primes $p$: those with $f_{i}=x^{p}$ for some $i$. We first
produce words $w_{p}$ for each such prime $p$, and then put them together, via
Lemma 2.73.

Let $N:=\sum_{j=1}^{m}|\lambda(j,p)|$. This is the total number of monomials
$x^{p}$ that need to cross non-monomials, per period. The word $w_{p}$ that
will be a sequence of $N$ $p$-longswaps. We induct on $N$ to build the word
$w_{p}$, adding a longswap to decrement $N$. More precisely, we shall find a
word $u$ which is a $p$-longswap for $f$, with trace $\mu$ on $(f,\alpha)$,
such that $\lambda-\mu$ has a smaller $N$. The only hard part is finding a
starting point where the monomial $x^{p}$ is available in the appropriate
puddle.

Case 0. If $\lambda(j,p)=0$ for all $j$, then $N=0$ and the induction is over.

Case 1. If for some $j$ we have $\lambda(j,p)\leq 0$ and $\lambda(j-1,p)\geq
0$ and they are not both zero, then
$\operatorname{pud}_{f,\alpha}(j,p)+\lambda(j,p)-\lambda(j-1,p)\geq 0$ gives
$\operatorname{pud}_{f,\alpha}(j,p)\geq-\lambda(j,p)+\lambda(j-1,p)>0$. The
hypothesis of this Case says that the $j^{\text{th}}$ puddle is not supposed
to gain any monomials $x^{p}$ on either side, and is supposed to lose at least
one monomial $x^{p}$ on at least one side; and we just showed that there is at
least one monomial $x^{p}$ in this $j$th puddle. Lemma 2.72 now gives the
desired longswap $u$.

Case 2 [resp. 3]. If $\lambda(j,p)>0$ for all $j$ [resp., $\lambda(j,p)<0$ for
all $j$ ], fix $j$ such that the $j^{\text{th}}$ puddle contains at least one
monomial $x^{p}$; this is possible by the assumption of Step 2. Use Lemma 2.72
to get a longswap $u$ that takes this monomial out of this puddle on the
right, decreasing the positive $\lambda(j+1,p)$ [resp.,on the left, inreasing
the negative $\lambda(j,p)$].

That covers all possible cases, by periodicity: $\lambda$ cannot force us to
only remove monomials $x^{p}$ from every puddle. ∎

####  2.2.2. Building the trace function

We now return to analyzing a clean $\mathsf{C}$-free long decomposition $f$
that fits into the Mahler problem. Our goal for this section, accomplished in
Theorem 2.85 at the end, is to find some $v\in\operatorname{ASym}_{k}$ for
which $v\star f$ is defined and has $e$-periodic nomodata. With Theorem 2.74,
it suffices to find the trace $\lambda$ of such a word, accomplished in
Proposition 2.83 right before the main theorem.

We first need to connect the combinatorics from Section 2.2.1 to the echo $e$.
Suppose that $w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$, that
$\alpha$ is a non-monomial listing function for $f$, and that $\lambda$ is the
trace of $w$ on $(f,\alpha)$. By Lemma 2.67,
$\beta(j):=\alpha(j)+\sum_{p}\lambda(j,p)$ is a nomodata for $f^{\tau}$. Since
$\alpha$ is also a nonmonomial listing function for $f^{\tau}$, we must have
$\beta(j)=\alpha(j+r)$ for some integer $r$. The next lemma identifies this
$r$ explicitly. A proof of Lemma 2.67 could follow this template.

######  Lemma 2.75.

Let $f$ be a clean $\mathsf{C}$-free long decomposition, and let
$w\in\operatorname{ST}^{+}_{k}$ be such that $w\star f=g$ encodes a curve
parametrized by $\\{(A(t),B(t))\\}$ for some polynomials $A$ and $B$. Let
$n_{A}$ and $n_{B}$ be the number of non-monomial factors in $A$ and $B$,
respectively. Let $\alpha$ and $\beta$ be increasing listings of the indices
on non-monomial factors of $f$ and $g$, respectively. Suppose that $\alpha(0)$
and $\beta(0)$ are the least positive indices of non-monomials in the $f$ and
$g$, respectively. If the factor $f^{\tau}_{b}$ corresponds to $f_{\alpha(j)}$
via $w\star f=g$, then $b=\beta(j+(n_{B}-n_{A}))$.

###### Proof.

We argue by induction on the length of a word representing $w$. As is our
wont, we will identify $w$ with this word.

The base case where $w$ is empty is trivial. The induction step where $w$ is a
single generator is verified below. The conclusion is obviously additive,
which concludes the proof. We organize the long case-out in order of
increasing complexity of the argument.

Let us start with the cases where $\beta=\alpha$ works. If $w=\epsilon_{p}$ or
$w=\epsilon_{p}^{-1}$, one of $A$ and $B$ is identity and the other is a
monomial, so $n_{B}-n_{A}=0$. If $w=t_{k}$ and both $f_{k}$ and $f_{k+1}$ are
monomials, both $A$ and $B$ are monomials, so $n_{B}-n_{A}=0$. In both cases,
$\beta:=\alpha$ works for $g$, and $g_{\alpha(j)}$ comes from $f_{\alpha(j)}$
via $w\star f=g$ for every $j$.

We next consider the cases where the non-monomials do move, but do not cross
between $k$ and $k+1$. If $w=t_{i}$ for some $i\neq k$, both $A$ and $B$ are
identity, so $n_{B}-n_{A}=0$. Now $\beta:=\pi\circ\alpha$ is the desired non-
monomial listing function for $g$, where $\pi$ is the permutation of
$\mathbb{Z}$ associated with $t_{i}$, that is, swapping $i+kn$ with $i+1+kn$
for all $n\in\mathbb{Z}$. If $w=\phi$ and $f_{1}$ is a monomial, then $A$ is
identity and $B$ a monomial, so $n_{B}-n_{A}=0$. Now $\beta(j):=\alpha(j)-1$
is a non-monomial listing function for $g$, and $\alpha(0)-1>0$ since
$\alpha(0)\neq 1$ since $f_{1}$ is a monomial. The argument for $\phi^{-1}$
and monomial $f_{k}$ is symmetric.

Finally, we consider the cases when a non-monomial crosses between $k$ and
$k+1$. If $w=\phi$ and $f_{1}$ is not a monomial, then $A$ is identity and $B$
not a monomial, so $n_{B}-n_{A}=1$. Now $\alpha(0)=1$, so while $\alpha(j)-1$
is a non-monomial listing function for $g$, it does not satisfy our extra
requirement; but $\beta(j):=\alpha(j+1)-1$ does. The argument for $\phi^{-1}$
is symmetric. If $w=t_{k}$ and $f_{1}$ is not a monomial, then $A$ is a
monomial and $B$ not a monomial, so $n_{B}-n_{A}=1$. Now $\alpha(0)=1$, and
$g_{1}$ (which comes from $f_{0}$) is a monomial, so $\beta(0)$ must be
greater than $1$. In particular, $g_{\beta(0)}$ does not correspond to
$f_{\alpha(0)}$, but to the next non-monomial to the left of it, namely
$f_{\alpha}(1)$, as wanted. The case where $f_{k}$ rather than $f_{1}$ is not
a monomial is symmetric.

∎

The special case of Lemma 2.75 where $g=f^{\tau}$ is a key step in solving the
Mahler problem.

######  Corollary 2.76.

Let $f$ be a clean $\mathsf{C}$-free long decomposition, and let
$w\in\operatorname{ST}^{+}_{k}$ be such that $w\star f=f^{\tau}$ encodes a
curve parametrized by $(A(t),B(t))$ for some polynomials $A$ and $B$. Let
$n_{A}$ and $n_{B}$ be the number of non-monomial factors in $A$ and $B$,
respectively. Let $\alpha$ be non-monomial listing function for $f$.

If the factor $f^{\tau}_{b}$ corresponds to $f_{\alpha(j)}$ via $w\star
f=f^{\tau}$, then $b=\alpha(j+(n_{B}-n_{A}))$.

######  Proposition 2.77.

Suppose that
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$ is a
nomodata for $f$, that $w\in\operatorname{ASym}_{k}$ has trace
$\mu=\operatorname{trace}_{w,f,\alpha}$, and that $\phi^{N}w\star f=f^{\tau}$
encodes a curve parametrized by $(A(t),B(t))$ for some polynomials $A$ and
$B$. Let $n_{A}$ and $n_{B}$ be the number of non-monomial factors in $A$ and
$B$, respectively. Set $r:=n_{A}-n_{B}$.

Then for all $j$,

$\operatorname{in}(j)-\mu(j)=\operatorname{in}(j+r)$
$\operatorname{out}(j)+\mu(j)=\operatorname{out}(j+r)$
$\operatorname{pud}(j)+\mu(j)-\mu(j-1)=\operatorname{pud}(j+r)\text{ .}$

###### Proof.

Lemma 2.67 gives a nomodata for $(g,\beta):=w\star(f,\alpha)$ as

$\beta(j):=\alpha(j)+\sum_{p}\mu(j,p)\text{, }$
$\operatorname{in}_{g,\beta}=\operatorname{in}_{f,\alpha}-\mu\text{, }$
$\operatorname{out}_{g,\beta}=\operatorname{out}_{f,\alpha}+\mu,$
$\operatorname{pud}_{g,\beta}(j)=\operatorname{pud}_{f,\alpha}(j)+\mu(j)-\mu(j-1)\text{
.}$

By Remark 2.62, a nomodata for $\phi^{N}w\star f$ is given by $\beta-N$ with
the same $\operatorname{in}$, $\operatorname{out}$, and $\operatorname{pud}$.
Since $\phi^{N}w\star f=f^{\tau}$, this is also a nomodata for $f^{\tau}$, and
so it is another nomodata for $f$. By Remark 2.61, we get some $s$ with

$\alpha(j)+\sum_{p}\mu(j,p)-N=\alpha(j+s)$
$\operatorname{in}(j)-\mu(j)=\operatorname{in}(j+s)$
$\operatorname{out}(j)+\mu(j)=\operatorname{out}(j+s)$
$\operatorname{pud}(j)+\mu(j)-\mu(j-1)=\operatorname{pud}(j+s)$

Corollary 2.76 shows that $s=r$. ∎

######  Remark 2.78.

With the setup in Proposition 2.77, it follows that the sum
$\operatorname{in}(j)+\operatorname{out}(j)$ is $r$-periodic:

$\operatorname{in}(j+r)+\operatorname{out}(j+r)=\operatorname{in}(j)-\mu(j)+\operatorname{out}(j)+\mu(j)=\operatorname{in}(j)+\operatorname{out}(j)\text{
.}$

For those primes $p$ whose monomials $x^{p}$ do not appear in $f$, we must
have $\mu(j,p)=0$ for all $j$, so $\operatorname{in}(j,p)$ and
$\operatorname{out}(j,p)$ are also $r$-periodic.

Suppose that $f$ has $n_{f}$ nonmonomials per $k$-period. Anything that is
both $n_{f}$-periodic and $r$-periodic is also $e$-periodic, where $e$ is the
echo $\gcd(n_{f},r)$.

######  Lemma 2.79.

Fix some $f$ with $m$ non-monomials per $k$-period. Suppose that for some
integer $r$, a nomodata
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$ for $f$
satisfies
$\operatorname{in}(j+r)+\operatorname{out}(j+r)=\operatorname{in}(j)+\operatorname{out}(j)$
for all $j$. Suppose that the trace of $u\star(f,\alpha)=:(g,\beta)$ is
$\lambda:=\operatorname{trace}_{u,f,\alpha}$ for some
$u\in\operatorname{ASym}_{k}$. Then the following are equivalent:

  1. (1)

$\operatorname{in}_{g,\beta}(j+r,p)=\operatorname{in}_{g,\beta}(j,p)$ for all
$j$ and prime $p$, that is, $\operatorname{in}_{g,\beta}$ is $r$-periodic in
$j$;

  2. (2)

$\operatorname{out}_{g,\beta}(j+r,p)=\operatorname{out}_{g,\beta}(j,p)$ for
all $j$ and prime $p$, that is, $\operatorname{out}_{g,\beta}$ is $r$-periodic
in $j$;

  3. (3)

for each prime $p$ there are constants $C_{i}(p)$ for $i=1,2,\ldots
d:=\gcd(m,r)$ such that $\lambda(j,p)=\operatorname{in}(j,p)+C_{i}(p)$ for all
$j\equiv i\pmod{d}$.

###### Proof.

Ritt swaps do not change the sum of in- and out-degree, so these sums are
still $r$-periodic. That is,

$\operatorname{in}_{g,\beta}(j+r)+\operatorname{out}_{g,\beta}(j+r)=\operatorname{in}_{g,\beta}(j)+\operatorname{out}_{g,\beta}(j)$

for all $j$. It follows that (1) and (2) are equivalent.

By Lemma 2.67, $\operatorname{in}_{g,\beta}=\operatorname{in}-\lambda$, so (1)
is equivalent to $\operatorname{in}-\lambda$ being $r$-periodic. Since it is
already $m$-periodic, it is $r$-periodic if and only if it is $d$-periodic.
The constants $C_{i}(p)$ in (3) are the values of
$\operatorname{in}(j,p)-\lambda(j,p)$ for $j\in i+d\mathbb{Z}$. ∎

######  Lemma 2.80.

Let $f$ be a clean $\mathsf{C}$-free long decomposition with nomodata
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$. Let $e$ be
the echo of $w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$. Let $p$
be a prime for which the monomial $x^{p}$ does not appear in $f$. Then the
$p$-part of the nomodata for $f$ is $e$-periodic. That is,
$\operatorname{in}(j,p)$, $\operatorname{out}(j,p)$, and
$\operatorname{pud}(j,p)$ are $e$-periodic in $j$.

###### Proof.

By Corollary 2.76, a non-monomial $f_{\alpha(j)}$ corresponds to
$f^{\tau}_{\alpha(j+(n_{B}-n_{A}))}$ via $w\star f=f^{\tau}$. Since $x^{p}$
does not occur in $f$, the $p$-part of the in-degree of this non-monomial does
not change as $w\star f$ is carried out. So
$\operatorname{in}(j,p)=\operatorname{in-
deg}(f_{\alpha(j)},p)=\operatorname{in-
deg}(f^{\tau}_{\alpha(j+(n_{B}-n_{A}))},p)=\operatorname{in-
deg}(f_{\alpha(j+(n_{B}-n_{A}))},p)=\operatorname{in}(j+(n_{B}-n_{A}),p)$.
That is, the function $\operatorname{in}(j,p)$ is $(n_{B}-n_{A})$-periodic in
$j$. Of course, it is also $n_{f}$-periodic in $j$, so it is $e$-periodic. The
exact same argument works for the out-degree. Since $x^{p}$ does not appear in
$f$, we get $\operatorname{pud}(j,p)=0$ for all $j$, and constant functions
are as periodic as it gets.∎

######  Lemma 2.81.

Let $f$ be a clean $\mathsf{C}$-free long decomposition with $m$ non-monomials
per $k$-period and with nomodata
$(\alpha,\operatorname{in},\operatorname{out},\operatorname{pud})$. Let $e$ be
the echo of $w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$. Suppose
that we have numbers $C_{i}(p)$ for $i\in\mathbb{Z}/e\mathbb{Z}$ and $p$ prime
satisfying

$-(\operatorname{out}(j,p)+\operatorname{in}(j,p))\leq C_{i}(p)\leq 0$

and

$C_{i}(p)+\operatorname{in}(j+zr,p)\geq
C_{i-1}(p)+\operatorname{in}(j-1+zr,p)$

for some $r$ and for all primes $p$, all $i$, and all $j\equiv i\pmod{e}$ and
some $z$ which may depend on $j$. Suppose further that for primes $p$ for
which the monomials $x^{p}$ do not appear in $f$, we have
$C_{i}(p)=-\operatorname{in}(j,p)$ for all $i$ and all $j\equiv i\pmod{e}$.

Then $\lambda$ defined by $\lambda(j,p)=\operatorname{in}(j,p)+C_{i}(p)$ (for
$j\equiv i\pmod{e}$) satisfies the admissibility conditions for $(f,\alpha)$
and all of the following functions are $e$-periodic:

$\alpha(j)+\sum_{p}\lambda(j,p),\,\,\,\operatorname{in}-\lambda,\,\,\,\operatorname{out}+\lambda,\,\,\,\operatorname{pud}(j)+\lambda(j)-\lambda(j-1)\text{
.}$

###### Proof.

The only interaction between different primes is the conclusion that
$\alpha(j)+\sum_{p}\lambda(j,p)$ is $e$-periodic. We return to this conclusion
after proving the rest of the lemma separately for each prime.

For primes $p$ for which the monomials $x^{p}$ do not appear in $f$, we get
$\lambda(j,p)=0$ for all $j$, immediately satisfying the admissibility
conditions. The last three functions in the conclusion of this lemma are just
the $p$-parts of the nomodata of $f$, shown to be $e$-periodic in Lemma 2.80.
The third admissibility condition only refers to these primes, so it is now
verified for all primes.

Proposition 2.77 is our main tool for verifying the second admissibility
condition. Let $u\in\operatorname{ASym}_{k}$ be such that $w=\phi^{N}u$ for
some integer $N$ and let $\mu$ be the trace of $u$ on $(f,\alpha)$. Solving
one of the conclusions of Proposition 2.77 for $\mu$ in terms of the function
$\operatorname{in}(j,p)$ and substituting into the last conclusion of
Proposition 2.77 gives

(23)
$[\operatorname{in}(j,p)-\operatorname{in}(j+r,p)]-[\operatorname{in}(j-1,p)-\operatorname{in}(j-1+r,p)]=\operatorname{pud}(j+r,p)-\operatorname{pud}(j,p)\text{
.}$

Iterating Equation 23 $z$-times and adding the telescoping sums, we obtain

(24)
$[\operatorname{in}(j,p)-\operatorname{in}(j+zr,p)]-[\operatorname{in}(j-1,p)-\operatorname{in}(j-1+zr,p)]=\operatorname{pud}(j+zr,p)-\operatorname{pud}(j,p)\text{
.}$

Rearranging gives

(25)
$\operatorname{pud}(j,p)+\operatorname{in}(j,p)-\operatorname{in}(j-1,p)+(\operatorname{in}(j-1+zr,p)-\operatorname{in}(j+zr,p))=\operatorname{pud}(j+zr,p)\geq
0\text{ .}$

When $j\equiv i\pmod{e}$

(26) $C_{i}(p)+\operatorname{in}(j+zr,p)\geq
C_{i-1}(p)+\operatorname{in}(j-1+zr,p)$

is one of our hypotheses for some $z$.

Equivalently,

(27)
$C_{i}(p)-C_{i-1}(p)\geq\operatorname{in}(j-1+zr,p)-\operatorname{in}(j+zr,p)$

Combining Equation 25 which we know for all $z$ and Equation 27 which we know
for some $z$ gives

(28)
$\operatorname{pud}(j,p)+\operatorname{in}(j,p)-\operatorname{in}(j-1,p)+(C_{i}(p)-C_{i-1}(p))\geq
0\text{ .}$

Rearranging Equation 28 and recalling that
$\lambda(j,p)=\operatorname{in}(j,p)+C_{i}(p)$ for $j\equiv i\pmod{e}$
produces

$\operatorname{pud}(j,p)+\lambda(j,p)-\lambda(j-1,p)\geq 0\text{ ,}$

which is precisely the second admissibility condition for $\lambda$.

The first admissibility condition
$-\operatorname{out}(j,p)\leq\lambda(j,p)\leq\operatorname{in}(j,p)$ follows
immediately from the hypothesis that
$-(\operatorname{out}(j,p)+\operatorname{in}(j,p))\leq C_{i}(p)\leq 0$.

Since $\lambda$ satisfies the admissibility conditions for $(f,\alpha)$, by
Theorem 2.74 there exists some $v\in\operatorname{ASym}_{k}$ with trace
$\lambda$ on $(f,\alpha)$. Let $(g,\beta):=v\star(f,\alpha)$. The four
functions in the conclusion of this lemma are then a nomodata for for
$(g,\beta)$.

By Remark 2.78, $(\operatorname{in}+\operatorname{out})$ is $e$-periodic, so
Lemma 2.79 applies, and condition (3) there is satisfied. From the equivalent
conditions (1) and (2) in that lemma, we get that
$\operatorname{in}-\lambda=\operatorname{in}_{g,\beta}$ and
$\operatorname{out}+\lambda=\operatorname{out}_{g,\beta}$ are $e$-periodic in
$j$. With Equation 23, this implies that
$\operatorname{pud}(j)+\lambda(j)-\lambda(j-1)=\operatorname{pud}_{g,\beta}$
is $e$-periodic.

We know that $\operatorname{pud}_{g,\beta}$ is $e$-periodic for all $p$, so
their sum $\sum_{p\in\mathcal{P}}\operatorname{pud}_{g,\beta}$ is
$e$-periodic. This sum is exactly the total number of monomials (of all
degrees) in the $j$th puddle! That is, the function $(\beta(j)-\beta(j-1))$ is
$e$-periodic; and it follows that $\beta$ itself is, too. ∎

######  Lemma 2.82.

Fix positive integers $e$ and $k$ with $k$ being a multiple of $e$. For every
function $\varpi:\mathbb{Z}/k\mathbb{Z}\rightarrow\mathbb{N}$ there is a non-
positive $e$-periodic function
$\zeta:\mathbb{Z}/k\mathbb{Z}\rightarrow\mathbb{Z}$ so that their sum
$\lambda:=\varpi+\zeta$ takes values in $\mathbb{N}$ and satisfies that for
every $j\in\mathbb{Z}/k\mathbb{Z}$ there is some $z\in\mathbb{Z}$ such that

(29) $\lambda(j+ze)\geq\lambda(j+ze-1)$

###### Proof.

The desired Inequality 29 unwraps to

(30) $\varpi(j+ze)+\zeta(j+ze)\geq\varpi(j+ze-1)+\zeta(j+ze-1).$

Since $\zeta$ will be $e$-periodic, Inequality 30 is equivalent to

(31) $\varpi(j+ze)+\zeta(j)\geq\varpi(j+ze-1)+\zeta(j-1)$

Take $s\in\mathbb{Z}/k\mathbb{Z}$ so that $\varpi$ attains its minimal value
at $s$. We construct $\zeta(s-x)$ by recursion on $x=0,1,\ldots e-1$; and then
extend by $e$-periodicity. Throughout this construction we verify that
Inequality 31 holds for $j\equiv s-x\pmod{e}$ and will maintain an additional
property that

($\spadesuit$) $\lambda(s-x+ze)\geq\lambda(s)\text{ for all }z$

We start by setting $\zeta(s):=0$. Condition $\spadesuit$ ‣ 2.2.2 holds in
this case by minimality of $\varpi(s)$. For the recursive step, we are given
$\zeta(s-x)$ and we need to choose $\zeta(s-x-1)$. We set $\zeta(s-x-1):=0$ if

(32) $\varpi(s-x+ze)+\zeta(s-x)\geq\varpi(s-x+ze-1)$

is satisfied for some $z$ for in so doing Inequality 31 holds for this choice
of $\zeta(s-x-1)$. Condition $\spadesuit$ ‣ 2.2.2 is satisfied in this case
because for $j\equiv s-x-1\pmod{e}$, we get

$\lambda(j)=\varpi(j)+\zeta(s-x-1)=\varpi(j)+0=\varpi(j)\geq\varpi(s)=\varpi(s)+0=\lambda(s).$

Otherwise,

$\varpi(s-x+ze)-\varpi(s-x+ze-1)+\zeta(s-x)<0$

for all $z$. In this case, we let $\zeta(s-x-1)$ be the largest (i.e. the
least negative) of all these possible values:

$\zeta(s-x-1):=\max_{z}(\varpi(s-x+ze)-\varpi(s-x+ze-1)+\zeta(s-x)).$

In particular, for some $z$ we have

$\zeta(s-x-1)=\varpi(s-x+ze)-\varpi(s-x+ze-1)+\zeta(s-x)$

so

$\varpi(s-x+ze-1)+\zeta(s-x-1)=\varpi(s-x+ze)+\zeta(s-x).$

In particular, we conclude

$\varpi(s-x+ze)+\zeta(s-x)\geq\varpi(s-x+ze-1)+\zeta(s-x-1)$

which verifies Inequality 31 for this value of $z$.

To obtain Condition $\spadesuit$ ‣ 2.2.2, unwrap the maximum function to see
that

$\zeta(s-x-1)\geq\varpi(s-x+ze)-\varpi(s-x+ze-1)+\zeta(s-x)$

for all $z$. Rearranging and unwrapping the definition of $\lambda$ gives

$\lambda(s-x+ze-1)=\varpi(s-x+ze-1)+\zeta(s-x-1)\geq\varpi(s-x+ze)+\zeta(s-x)=\lambda(s-x+ze)$

for all $z$. By the truth of Condition $\spadesuit$ ‣ 2.2.2 for $s-x$,

$\lambda(s-x+ze)\geq\lambda(s).$

The recursive step and, therefore, the whole recursive construction, is now
complete. To verify the last remaining instance of the desired inequality,
note that

$\lambda(s+1)\geq\lambda(s)$

is an instance of Condition $\spadesuit$ ‣ 2.2.2.

Since $\lambda(s)=\varpi(s)\geq 0$, Condition $\spadesuit$ ‣ 2.2.2 also
implies that $\lambda$ is nonnegative.

∎

######  Proposition 2.83.

Let $f$ be a clean $\mathsf{C}$-free long decomposition with $m$ non-monomials
per $k$-period and with nomodata $(\alpha,in,out,pud)$. Let $e$ be the echo of
$w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$. Then there exists an
$m$-periodic function $\lambda$ satisfying the Admissibility Conditions for
$f$ such that all of the following functions are $e$-periodic:

$\alpha(j)+\sum_{p}\lambda(j,p),\,\,\,\operatorname{in}-\lambda,\,\,\,\operatorname{out}+\lambda,\,\,\,\operatorname{pud}(j)+\lambda(j)-\lambda(j-1).$

###### Proof.

Applying Lemma 2.82 to the function $\varpi(j):=\operatorname{in}(l,p)$ and
set $C_{i}(p):=\zeta(i)$. These values satisfy the hypotheses of Lemma 2.81,
thus completing the proof.

∎

######  Remark 2.84.

The $\lambda$ we obtained in 2.83 using Lemma 2.82 is necessarily non-
negative, but there may be (probably are) other functions satisfying the
conclusion of that proposition. The one we built is an upper bound on
solutions of $-\operatorname{out}(j)\leq\lambda(j)\leq\operatorname{in}(j)$
for all $j$; and for all $j$ there is some $z$ such that
$\lambda(j+zr)\geq\lambda(j-1+zr)$. The same reasoning starting with
$-\operatorname{out}$ and adding positive constants on cosets to obtain the
desired inequality would produce a non-positive solution, which would be a
lower bound on other solutions. The trace of $u\in\operatorname{Sym}_{k}$
obtained in Theorem 2.86 will be one of these other solutions.

The main result of this section is now an immediate consequence of Proposition
2.83 and Theorem 2.74.

######  Theorem 2.85.

Let $f$ be a clean $\mathsf{C}$-free long decomposition with $m$ non-monomials
per $k$-period and with nomodata $(\alpha,in,out,pud)$. Let $e$ be the echo of
$w\star f=f^{\tau}$ for some $w\in\operatorname{ST}_{k}$. Then there exists
some $v\in\operatorname{ASym}_{k}$ for which $v\star f$ is defined and has
$e$-periodic nomodata.

###### Proof.

Applying Proposition 2.83 we obtain a function $\lambda$ satisfying the
Admissibility conditions for $(f,\alpha)$. By Theorem 2.74 there is some
$v\in\operatorname{ASym}_{k}$ for which $v\star f$ is defined and has trace
$\lambda$ on $(f,\alpha)$. The $e$-periodic functions in the conclusion of
Proposition 2.83 are exactly a nomodata for $v\star f$. ∎

####  2.2.3. From $\operatorname{ASym}_{k}$ to $\operatorname{Sym}_{k}$

The main result of this Subsection 2.2.3 is Theorem 2.86 in which Theorem 2.85
is upgraded replacing $\operatorname{ASym}_{k}$ by $\operatorname{Sym}_{k}$.

######  Theorem 2.86.

Let $N$ be an integer dividing $k$, and let $f$ be a clean $\mathsf{C}$-free
long decomposition, and suppose that $v\star f$ has $N$-periodic nomodata for
some $v\in\operatorname{ASym}_{k}$. Then $u\star f$ has $N$-periodic nomodata
for some $u\in\operatorname{Sym}_{k}$.

######  Remark 2.87.

Theorem 2.86 holds trivially when $N=k$. For the remainder of this subsection
we take $N<k$.

We prove Theorem 2.86 through a series of reductions.

######  Proposition 2.88.

Theorem 2.86 follows from the special case where $v=v_{0}t_{k}$ for some
$v_{0}\in\operatorname{Sym}_{k}$.

###### Proof.

We induct on the number $M$ of instances of $t_{k}$ in some presentation of
$v$ as a word in $\\{t_{1},\ldots,t_{k}\\}$. When $M=0$ and there are no
instances of $t_{k}$ in $v$, let $u=v$. For the induction step, take a word
$v=v_{0}t_{k}\widehat{v}$ where $\widehat{v}$ has $M$ instances of $t_{k}$.
Let $g:=\widehat{v}\star f$. Now $v_{0}t_{k}\star g$ has periodic nomodata, so
by the special case, there is some word $\widehat{u}$ with no $t_{k}$’s for
which $\widehat{u}\star g$ has periodic nomodata. But then
$\widehat{u}\widehat{v}\star f=\widehat{u}\star g$ has periodic nomodata. Now
$\widehat{u}\widehat{v}$ has only $M$ instances of $t_{k}$ in it, so by the
induction hypothesis, there is some $u\in\left(t_{1},\ldots,t_{k-1}\right)$
such that $u\star f$ has periodic nomodata. ∎

Let us consider how the expression $v=v_{0}t_{k}$ in Proposition 2.88 acts on
$f$. First, $t_{k}$ swaps the boundary factors and then $v_{0}$ mixes
everything else using Ritt swaps. The next lemma expresses the sense in which
it would have been possible to first perform this kind of mixing before
performing a swap at the boundary. That is, one can arrange all of the factors
in the correct order first, allow $t_{k}$ to swap the boundard factors, and
then bring the newly changed boundary factors into the middle of the
decomposition.

######  Lemma 2.89.

For any $v_{0}\in\operatorname{Sym}_{k}$ there is some $\widehat{v}\in\langle
t_{2},\ldots,t_{k-2}\rangle$ such that
$v_{0}t_{k}=v_{r}v_{\ell}t_{k}\widehat{v}$ where $v_{\ell}$ is a left-to-right
transit $t_{a}t_{a+1}\ldots t_{k-1}$ and $v_{r}$ is a right-to-left transit
$t_{b}t_{b-1}\ldots t_{1}$.

###### Proof.

First, put $v_{0}$ into first canonical (See Remark 2.39):

$v_{0}=v_{r}v^{\prime}$

where $v_{r}$ is as above, and $v^{\prime}\in\langle
t_{2},\ldots,t_{k-1}\rangle$. Then put $v^{\prime}$ into reverse first
canonical form:

$v^{\prime}=v_{\ell}\widehat{v}$

where $v_{\ell}$ and $\widehat{v}$ are as required. So,

$v_{0}t_{k}=v_{r}v_{\ell}\widehat{v}t_{k}\text{ .}$

Since non-adjacent Ritt swaps commute,

$v_{0}t_{k}=v_{r}v_{\ell}t_{k}\widehat{v}\text{, }$

as wanted. ∎

######  Proposition 2.90.

Theorem 2.86 follows from the special case where $v=v_{r}v_{\ell}t_{k}$ where
$v_{\ell}$ is a left-to-right transit $t_{a}t_{a+1}\ldots t_{k-1}$ bringing
the leftmost factor into the middle and $v_{r}$ is a right-to-left transit
$t_{b}t_{b-1}\ldots t_{1}$ bringing the rightmost factor into the middle.

###### Proof.

From the Proposition 2.88, we know it suffices to prove the special case where
$v=v_{0}t_{k}$ and $v_{0}\in\operatorname{Sym}_{k}$. Lemma 2.89 gives us
$v_{r}$ and $v_{\ell}$ as in the statement of this proposition and
$\widehat{v}\in\operatorname{Sym}_{k}$ such that
$v_{0}t_{k}=v_{r}v_{\ell}t_{k}\widehat{v}$ in $\operatorname{ASym}_{k}$. As in
the proof of Proposition 2.88, let $g:=\widehat{v}\star f$. Now
$v_{r}v_{\ell}t_{k}\star g$ has periodic nomodata, so for some
$\widehat{u}\in\operatorname{Sym}_{k}$ we have that $\widehat{u}\star g$ has
periodic nomodata. Thus, $\widehat{u}\widehat{v}\star f$ has periodic
nomodata. That is, $u:=\widehat{u}\widehat{v}$ works. ∎

The next proposition says that the altered boundary factors cannot go very far
into the middle: they must stay within the first/last period of the periodic
nomodata of $v_{r}v_{\ell}t_{k}\star f$.

######  Proposition 2.91.

Fix a long decomposition $f$ and a natural number $N<k$. Suppose that
$v_{r}v_{\ell}t_{k}\star f$ has $N$-periodic nomodata for some
$v_{\ell}=t_{a}t_{a+1}\ldots t_{k-1}$ and $v_{r}=t_{b}t_{b-1}\ldots t_{1}$.
Then $b+1\leq N$ and $a\geq k-N$.

###### Proof.

We first show that $b+1\leq N$. Leting $h:=v_{\ell}t_{k}\star f$, we get that
$t_{b}t_{b-1}\ldots t_{1}\star h$ has $N$-periodic nomodata. In evaluating
$t_{b}t_{b-1}\ldots t_{1}\star h$, the rightmost factor $h_{1}$ of $h$ has to