# Anti-classification results for the Kakutani equivalence relation

Marlies Gerber1 and  Philipp Kunde2

###### Abstract.

We prove that the Kakutani equivalence relation of ergodic invertible measure-
preserving transformations is not a Borel set. This shows in a precise way
that classification up to Kakutani equivalence is impossible. We also obtain
this anti-classification result for ergodic area-preserving smooth
diffeomorphisms on compact surfaces admitting a non-trivial circle action as
well as real-analytic diffeomorphisms on the $2$-torus.

1 Indiana University, Department of Mathematics, Bloomington, IN 47405, USA

2 University of Hamburg, Department of Mathematics, 20146 Hamburg, Germany.
P.K. acknowledges financial support from a DFG Forschungsstipendium under
Grant No. 405305501

\-
2020 Mathematics Subject classification: Primary: 37A20; Secondary: 37A35,
37A05, 37C40, 03E15
Key words:  Kakutani equivalence, anti-classification, complete analytic,
smooth ergodic theory

##  1\. Introduction

A fundamental theme in ergodic theory, going back to J. von Neumann [Ne32], is
the isomorphism problem: classify measure-preserving transformations (MPT’s)
up to isomorphism. By an MPT we mean a measure-preserving automorphism of a
standard non-atomic probability space. We let $\mathcal{X}$ denote the set of
all MPT’s of a fixed standard non-atomic probability space
$(\Omega,\mathcal{M},\mu)$. Two automorphisms $S,T\in\mathcal{X}$ are said to
be _isomorphic_ (written $S\cong T$) if there exists $\varphi\in\mathcal{X}$
such that $S\circ\varphi$ and $\varphi\circ T$ agree $\mu$-almost everywhere.
Since there is a decomposition of each MPT into ergodic components that is
preserved under isomorphism (see, for example, Chapter 5 of [VO16]), we often
consider just the set $\mathcal{E}$ of ergodic elements of $\mathcal{X}.$ Two
great successes in the classification of MPT’s are the Halmos-von Neumann
classification of ergodic MPT’s with pure point spectrum by countable
subgroups of the unit circle [HN42] and D. Ornstein’s classification of
Bernoulli shifts by their metric entropy [Or70]. Nonetheless, the isomorphism
problem remains unsolved for general ergodic MPT’s.

In contrast to the positive results in [HN42] and [Or70], a series of _anti-
classification_ results have appeared, starting with the work of F. Beleznay
and M. Foreman [BF96]. Anti-classification results demonstrate the complexity
of the isomorphism problem. To describe some of this work, we endow
$\mathcal{X}$ with the weak topology. (Recall that $T_{n}\to T$ in the weak
topology if and only if $\mu(T_{n}(A)\triangle T(A))\to 0$ for every
$A\in\mathcal{M}.)$ This topology is compatible with a complete separable
metric and hence makes $\mathcal{X}$ into a Polish space. Since $\mathcal{E}$
is a (dense) $G_{\delta}$ -set in $\mathcal{X}$, the induced topology on
$\mathcal{E}$ is Polish as well. In contrast to the Halmos-von Neumann
classification result, G. Hjorth [Hj01] showed that there is no Borel way of
associating algebraic invariants to ergodic MPT’s that completely determines
isomorphism. Moreover, Foreman and B. Weiss [FW04] proved that there is no
generic class (that is, a dense $G_{\delta}$ -set) of ergodic MPT’s for which
there is a Borel way of associating a complete algebraic invariant. Hjorth
also proved that the isomorphism relation $\mathcal{R}$ is itself not a Borel
set when viewed as a subset of $\mathcal{X}\times\mathcal{X}$. However, his
proof used nonergodic transformations in an essential way. In the case of
ergodic MPT’s, Foreman, D. Rudolph, and Weiss [FRW11] proved that
$\mathcal{R}\cap(\mathcal{E}\times\mathcal{E})$ is not Borel. One way to
interpret an equivalence relation not being a Borel set is to say that there
is no inherently countable technique for determining whether or not two
members of the set are equivalent. (See the survey article by M. Foreman
[Fo18] for more details.) Thus [FRW11] gives a precise formulation of the
unclassifiability of ergodic MPT’s up to isomorphism.

Recently, Foreman and A. Gorodetski [FGpp] obtained anti-classification
results in a different context. They considered topological equivalence of
$C^{\infty}$ diffeomorphisms of a compact manifold $M.$ Two diffeomorphisms
$f$ and $g$ of $M$ are said to be topologically equivalent if there is a
homeomorphism $\varphi$ of $M$ such that $f\circ\varphi=\varphi\circ g.$ In
the case dim$(M)\geq 2,$ Foreman and Gorodetski proved there is no Borel
function from the $C^{\infty}$ diffeomorphisms to the reals that is a complete
invariant for topological equivalence. Moreover, if dim$(M)\geq 5,$ they
proved the analog of the unclassifiability result of [FRW11], that is, the set
of topologically equivalent pairs of diffeomorphisms is not Borel.

When the anti-classification results in [FRW11] became known, immediately the
question arose whether these results are also true if “isomorphism” is
replaced by “Kakutani equivalence”. (See [We14] for some history of this
question.) In this paper we answer this question affirmatively. Our arguments
build on the methods in [FRW11] and also imply the anti-classification result
of [FRW11].

Kakutani equivalence is the best known and most natural equivalence relation
on ergodic MPT’s, besides isomorphism, for which the classification problem
can be considered. (Orbit equivalence is not interesting in the present
context, because according to Dye’s theorem, all ergodic MPT’s are orbit
equivalent.) Two ergodic MPT’s are said to be _Kakutani equivalent_ if they
are isomorphic to measurable cross-sections of the same ergodic flow. Since
the Kakutani equivalence relation is weaker than isomorphism, one might expect
classification to be simpler. In fact, until the work of J. Feldman [Fe76], it
seemed that there might be only three Kakutani equivalence classes: zero
entropy, finite positive entropy, and infinite entropy. However, Feldman found
examples to show that each entropy class (zero, finite positive, and infinite)
contains at least two non-Kakutani equivalent ergodic MPT’s. A. Katok [Ka77],
and Ornstein, Rudolph, and Weiss [ORW82], independently, extended this to
obtain uncountably many non-Kakutani equivalent examples in each entropy
class.

A precursor to the anti-classification results for isomorphism is the
observation by Feldman [Fe74] that there does not exist a Borel function from
$\mathcal{E}$ to the reals such that two transformations are isomorphic if and
only if the Borel function takes the same value at these transformations. His
proof is an easy application of a 0-1 law to the uncountable family of non-
Bernoulli K-automorphisms constructed by Ornstein and P. Shields [OS73]. It is
interesting to note that the uncountable family of automorphisms constructed
in [ORW82] can be substituted for the Ornstein-Shields examples to conclude
that there is no Borel function from $\mathcal{E}$ to the reals whose values
are complete invariants for Kakutani equivalence. The key common feature of
the examples in [OS73] and the examples in [ORW82] is that they are indexed by
sequences of zeros and ones in such a way that two of the examples are
isomorphic (in the case of [OS73]) or Kakutani equivalent (in the case of
[ORW82]) if and only if the two corresponding sequences of zeros and ones
agree except for possibly finitely many terms.

In the context of Kakutani equivalence for flows, M. Ratner [Ra81] introduced
the Kakutani invariant and used this to prove that for distinct integers
$k,\ell>0,$ the product of $k$ copies of the horocycle flow with itself is not
Kakutani equivalent to the product of $\ell$ copies. More recently, A.
Kanigowski, K. Vinhage, and D. Wei [KVW21] obtained an explicit formula for
the Kakutani invariant for unipotent flows acting on compact quotients of
semisimple Lie groups. It is an open question whether the Kakutani invariant
is a complete invariant in the class of unipotent flows.

We also note that the analog of the result in [FW04] fails for Kakutani
equivalence in a trivial way, because the rank one transformations form a
dense $G_{\delta}$-subset of $\mathcal{E},$ and all rank one transformations
are zero entropy loosely Bernoulli, and therefore in the same Kakutani
equivalence class. In case of isomorphism, Foreman, Rudolph and Weiss [FRW11,
section 10] use a theorem of J. King [Ki86] to prove that the collection of
pairs $(S,T)$ of rank one ergodic transformations such that $S$ and $T$ are
isomorphic is a Borel subset of $\mathcal{E}\times\mathcal{E}.$ Nonetheless,
no useful structure theorem to classify rank one transformations up to
isomorphism is known.

We prove that the set $\mathcal{S}$ of pairs $(S,T)$ in
$\mathcal{E}\times\mathcal{E}$ such that $S$ and $T$ are Kakutani equivalent
is not a Borel set. We follow the general scheme in [FRW11], but with some
notable differences. As in [FRW11] we consider the set,
$\text{$\mathcal{T}$}rees,$ which consists of countable rooted trees with
arbitrarily long branches. Then, analogously to the approach in [FRW11], we
construct a continuous function
$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$ such that
$\Psi(\mathcal{T})$ is Kakutani equivalent to $\Psi(\mathcal{T})^{-1}$ if and
only if $\mathcal{T}$ has an infinite branch. According to a classical result
[Ke95], the collection of $\mathcal{T}\kern-1.42262ptrees$ with one or more
infinite branches is a complete analytic subset of
$\mathcal{T}\kern-1.42262ptrees.$ It follows that the set $\mathcal{S}$ of
Kakutani equivalent pairs is a complete analytic set and hence not Borel. In
fact, by an argument similar to that in [FRW11], $\Psi(\mathcal{T})$ is
actually _isomorphic_ to $\Psi(\mathcal{T})^{-1}$ if $\mathcal{T}$ has an
infinite branch. Therefore any equivalence relation on $\mathcal{E}$ that is
weaker than (or equal to) isomorphism and stronger than (or equal to) Kakutani
equivalence is complete analytic. This includes _even_ Kakutani equivalence
(see Definition 64 in Section 9.2), and $\alpha$-equivalence (defined in
[FJR94]). Indeed, we first prove our result for even Kakutani equivalence and
then use the methods of [ORW82] to prove that for any
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees,$ $\Psi(\mathcal{T})$ and
$\Psi(\mathcal{T})^{-1}$ cannot be Kakutani equivalent unless they are evenly
Kakutani equivalent.

Foreman, Rudolph, and Weiss use the elegant method of joinings to prove that
for $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ such that $\mathcal{T}$ has
no infinite branch, the corresponding element of $\mathcal{E}$ is not
isomorphic to its inverse. However, as they announced in [FRW06], they could
also have used a finite coding argument and approximations in the
$\overline{d}$-metric for this proof. We use the finite coding approach and
apply the result in [ORW82] that for evenly equivalent processes $(S,P)$ and
$(T,Q),$ there is a finite code defined on the $(T,Q)$ process such that the
$\overline{f}$-distance between the $(S,P)$ process and the process coded from
$(T,Q)$ is small.

As in [FRW11], each level $s$ of a tree
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ corresponds to an equivalence
relation $\mathcal{Q}_{s}$ on certain finite words, and $\mathcal{Q}_{s+1}$
refines $\mathcal{Q}_{s}.$ One of the main steps in the construction of
$\Psi(\mathcal{T})$ is a procedure for substituting $\mathcal{Q}_{s+1}$
equivalence classes into $\mathcal{Q}_{s}$ equivalence classes. Foreman,
Rudolph, and Weiss use a random substitution method, while we use Feldman
patterns (defined in Section 6) to execute a deterministic substitution.

The classification problem (with respect to isomorphism or Kakutani
equivalence) can also be restricted to the class of smooth ergodic
diffeomorphisms of a compact manifold $M$ that preserve a smooth measure. For
dimensions greater than or equal to three, there are no known obstacles to
realizing an arbitrary ergodic MPT as a diffeomorphism of a compact manifold
except for the requirement, proved by A. Kushnirenko [Ku65], that the ergodic
MPT have finite entropy. Thus it is not clear if the restriction to smooth
ergodic diffeomorphisms changes the classification problem. But even with this
restriction, Foreman and Weiss [FW3] proved that the isomorphism relation is
not Borel. Moreover, S. Banerjee and P. Kunde [BKpp] showed that the
isomorphism relation is still not Borel if “smooth” is replaced by “real
analytic”. We obtain the analogous results for Kakutani equivalence both in
the smooth and the real analytic settings.

To obtain their anti-classification results for smooth diffeomorphisms,
Foreman and Weiss [FW19b] introduced a functor $\mathcal{F}$ from certain
odometer-based systems in [FRW11] to the so-called circular systems, which
they showed in [FW19a] have a smooth realization on $\mathbb{D}^{2}$ and
$\mathbb{T}^{2}$ via the untwisted Anosov-Katok method [AK70], while on
$\mathbb{T}^{2}$ Banerjee and Kunde [Ba17, BKpp] extended these results to the
real analytic case. We also make use of this machinery to obtain smooth and
real analytic models of the images under $\mathcal{F}$ of the odometer-based
systems that we construct using the Feldman patterns. The same argument as in
[FW19b] shows that in our construction $\mathcal{F}(\Psi(\mathcal{T}))$ and
$\mathcal{F}(\Psi(\mathcal{T})^{-1})$ are isomorphic if $\mathcal{T}$ has an
infinite branch. But the more difficult part, showing that
$\mathcal{F}(\Psi(\mathcal{T}))$ and $\mathcal{F}(\Psi(\mathcal{T})^{-1})$ are
_not_ Kakutani equivalent if $\mathcal{T}$ does _not_ have an infinite branch,
requires a different argument from that in [FW19b]. In fact, in [GKpp], we
obtained an example of two _non_ -Kakutani equivalent odometer-based systems
$S$ and $T$ such that $\mathcal{F}(S)$ and $\mathcal{F}(T)$ are Kakutani
equivalent. However, for the systems $\Psi(\mathcal{T})$ that we construct in
the present paper, if $\Psi(\mathcal{T})$ is not Kakutani equivalent to
$\Psi(\mathcal{T})^{-1},$ then $\mathcal{F}(\Psi(\mathcal{T}))$ is not
Kakutani equivalent to $\mathcal{F}(\Psi(\mathcal{T})^{-1})$. Thus, we can
transfer the non-Kakutani equivalence between $\Psi(\mathcal{T})$ and
$\Psi(\mathcal{T})^{-1}$ to non-Kakutani equivalence between
$\mathcal{F}(\Psi(\mathcal{T}))$ and $\mathcal{F}(\Psi(\mathcal{T})^{-1})$ if
$\mathcal{T}$ does not have an infinite branch. This yields smooth and real
analytic anti-classification results for isomorphism (already proved in [FW3]
and [BKpp]), Kakutani equivalence, and every equivalence relation in between
these two.

Classification questions can also be considered in the context of group
actions. For example, E. Gardella and M. Lupini [GLpp] showed that for every
nonamenable countable discrete group $\Gamma$, the relations of isomorphism
and orbit equivalence of free ergodic (or weak mixing) measure preserving
actions of $\Gamma$ on a standard probability space are not Borel. The
analogous question for amenable countable discrete groups and the isomorphism
relation is open.

##  2\. Preliminaries

###  2.1. Some terminology from ergodic theory

We call a separable non-atomic probability space $(\Omega,\mathcal{M},\mu)$ a
_standard measure space_. Since every standard measure space is isomorphic to
the unit interval with Lebesgue measure $\lambda$ on the Borel sets
$\mathcal{B}$, every invertible MPT (also called an _automorphism_) of a
standard measure space is isomorphic to an invertible Lebesgue measure-
preserving transformation on $[0,1]$. As in the introduction, we let
$\mathcal{X}$ denote the group of MPT’s on $[0,1]$ endowed with the weak
topology, where two MPT’s are identified if they are equal on sets of full
measure.

While in this model we fix the measure and look at transformations preserving
that measure, there is also a dual viewpoint of fixing the transformation and
considering the collection of its invariant measures. The transformation that
we use is the left shift $sh:\Sigma^{\mathbb{Z}}\to\Sigma^{\mathbb{Z}},$
defined by

$sh((x_{n})_{n=-\infty}^{\infty})=(x_{n+1})_{n=-\infty}^{\infty}$

on $(\Sigma^{\mathbb{Z}},\mathcal{C})$, where $\Sigma$ is a countable set and
$\mathcal{C}$ is the $\sigma$-algebra of Borel sets in $\Sigma^{\mathbb{Z}}.$
We endow the set of shift-invariant measures with the weak∗ topology. In our
paper, $\Sigma$ is finite and for each shift-invariant measure $\nu$ that we
construct, there is also an explicit cutting-and-stacking procedure that
yields an ergodic Lebesgue measure-preserving automorphism $T$ of $[0,1]$ such
that $\left([0,1],\mathcal{B},\lambda,T\right)$ is isomorphic to
$\left(\Sigma^{\mathbb{Z}},\mathcal{C},\psi(T),sh\right).$ This is a special
case of a more general result of Foreman [Fo10]: there is a Borel bijection
$\psi$ between the aperiodic Lebesgue measure-preserving transformations on
$[0,1]$ and nonatomic shift-invariant measures on $\Sigma^{\mathbb{Z}}$ taking
comeager sets to comeager sets such that
$\left([0,1],\mathcal{B},\lambda,T\right)$ is isomorphic to
$\left(\Sigma^{\mathbb{Z}},\mathcal{C},\psi(T),sh\right).$ In particular, the
choice of model for measure-preserving transformations is not important for
the Borel or analytic distinction.

Another important viewpoint is to assign a process to a MPT. For this purpose,
we recall that a _partition_ $P$ of a standard measure space
$(\Omega,\mathcal{M},\mu)$ is a collection
$P=\left\\{c_{\sigma}\right\\}_{\sigma\in\Sigma}$ of subsets
$c_{\sigma}\in\mathcal{M}$ with $\mu(c_{\sigma}\cap c_{\sigma^{\prime}})=0$
for all $\sigma\neq\sigma^{\prime}$ and
$\mu\left(\bigcup_{\sigma\in\Sigma}c_{\sigma}\right)=1$, where $\Sigma$ is a
finite set of indices. Each $c_{\sigma}$ is called an _atom_ of the partition
$P$. For two partitions $P$ and $Q$ we define the join of $P$ and $Q$ to be
the partition $P\vee Q=\left\\{c\cap d:c\in P,d\in Q\right\\}$, and for a
sequence of partitions $\\{P_{n}\\}_{n=1}^{\infty}$ we let
$\vee_{n=1}^{\infty}P_{n}$ be the smallest $\sigma$-algebra containing
$\cup_{n=1}^{\infty}P_{n}$. We say that a sequence of partitions
$\\{P_{n}\\}_{n=1}^{\infty}$ is a _generating sequence_ if
$\vee_{n=1}^{\infty}P_{n}=\mathcal{M}$. We also have a standard notion of a
_distance between two ordered partitions_ : If $P=\\{c_{i}\\}_{i=1}^{N}$ and
$Q=\\{d_{i}\\}_{i=1}^{N}$ are two ordered partitions with the same number of
atoms, then we define

$d(P,Q)=\sum_{i=1}^{N}\mu(c_{i}\triangle d_{i}),$

where $\triangle$ denotes the symmetric difference.

For an automorphism $T$ of $(\Omega,\mathcal{M},\mu)$ and a partition
$P=\left\\{c_{\sigma}\right\\}_{\sigma\in\Sigma}$ of $\Omega$ we can define
the $(T,P)$-name for almost every $x\in\Omega$ by

$(a_{n})_{n=-\infty}^{\infty}\in\Sigma^{\mathbb{Z}}\text{ with }T^{i}(x)\in
c_{a_{i}}.$

Note that the $(T,P)$-name of $T(x)$ is the left shift of the $(T,P)$-name of
$x$. If the partition $P$ is a _generator_ (that is,
$\left\\{T^{n}P\right\\}_{n=-\infty}^{\infty}$ is a generating sequence), then
$(X,\mu,T)$ is isomorphic to $(\Sigma^{\mathbb{Z}},\nu,sh)$ with the measure
$\nu$ satisfying $\nu\\{(x_{n})_{n=-\infty}^{\infty}:x_{n}=a_{n}\text{\ for\
}n=j,j+1,...,k\\}=\mu(T^{-j}(c_{a_{j}}))\cap
T^{-(j+1)}(c_{a_{j+1}})\cap\cdots\cap T^{-k}(c_{a_{k}})).$ The pair $(T,P)$ is
called a _process_.

Recall that the _Hamming distance_ between two strings of symbols $a_{1}\dots
a_{n}$ and $b_{1}\dots b_{n}$ is defined by $\overline{d}\left(a_{1}\dots
a_{n},b_{1}\dots b_{n}\right)=\frac{1}{n}|\left\\{i:a_{i}\neq
b_{i}\right\\}|$. It can be extended to infinite words $w=\dots
a_{-2}a_{-1}a_{0}a_{1}a_{2}...$ and $w^{\prime}=\dots
b_{-2}b_{-1}b_{0}b_{1}b_{2}\dots$ by
$\overline{d}(w,w^{\prime})=\limsup_{n\to\infty}\overline{d}\left(w_{n},w_{n}^{\prime}\right)$,
where $w_{n}=a_{-n}a_{-n+1}\dots a_{n-1}a_{n}$ and
$w_{n}^{\prime}=b_{-n}b_{-n+1}\dots b_{n}$ are the truncated words.

###  2.2. Symbolic systems

An _alphabet_ is a countable or finite collection of symbols. In the
following, let $\Sigma$ be a finite alphabet endowed with the discrete
topology. Then $\Sigma^{\mathbb{Z}}$ with the product topology is a separable,
totally disconnected and compact space. A usual base of the product topology
is given by the collection of cylinder sets of the form $\left\langle
u\right\rangle_{k}=\left\\{f\in\Sigma^{\mathbb{Z}}:f\upharpoonright[k,k+n)=u\right\\}$
for some $k\in\mathbb{Z}$ and finite sequence
$u=\sigma_{0}\dots\sigma_{n-1}\in\Sigma^{n}$. For $k=0$ we abbreviate this by
$\left\langle u\right\rangle$.

The shift map $sh:\Sigma^{\mathbb{Z}}\to\Sigma^{\mathbb{Z}}$ is a
homeomorphism. If $\mu$ is a shift-invariant Borel measure, then the measure-
preserving dynamical system
$\left(\Sigma^{\mathbb{Z}},\mathcal{B},\mu,sh\right)$ is called a _symbolic
system_. The closed support of $\mu$ is a shift-invariant subset of
$\Sigma^{\mathbb{Z}}$ called a _symbolic shift_ or _sub-shift_.

The symbolic shifts that we use are described by specifying a collection of
words. A word $w$ in $\Sigma$ is a finite sequence of elements of $\Sigma$,
and we denote its length by $|w|$.

######  Definition 1.

A sequence of collections of words $\left(W_{n}\right)_{n\in\mathbb{N}}$,
where $\mathbb{N}=\left\\{0,1,2,\dots\right\\}$, satisfying the following
properties is called a _construction sequence_ :

  1. (1)

for every $n\in\mathbb{N}$ all words in $W_{n}$ have the same length $h_{n}$,

  2. (2)

each $w\in W_{n}$ occurs at least once as a subword of each $w^{\prime}\in
W_{n+1}$,

  3. (3)

there is a summable sequence $\left(\varepsilon_{n}\right)_{n\in\mathbb{N}}$
of positive numbers such that for every $n\in\mathbb{N}$, every word $w\in
W_{n+1}$ can be uniquely parsed into segments $u_{0}w_{1}u_{1}w_{1}\dots
w_{l}u_{l+1}$ such that each $w_{i}\in W_{n}$, each $u_{i}$ (called spacer or
boundary) is a word in $\Sigma$ of finite length and for this parsing

$\frac{\sum_{i=0}^{l+1}|u_{i}|}{h_{n+1}}<\varepsilon_{n+1}.$

We will often call words in $W_{n}$_ $n$-words_ or _$n$ -blocks_, while a
general concatenation of symbols from $\Sigma$ is called a _string_. We also
associate a symbolic shift with a construction sequence: Let $\mathbb{K}$ be
the collection of $x\in\Sigma^{\mathbb{Z}}$ such that every finite contiguous
substring of $x$ occurs inside some $w\in W_{n}$. Then $\mathbb{K}$ is a
closed shift-invariant subset of $\Sigma^{\mathbb{Z}}$ that is compact since
$\Sigma$ is finite.

######  Remark.

The symbolic shifts built from construction sequences can be realized as
transformations built by cutting-and-stacking constructions. Spacers are not
used in our constructions until Section 10.

In order to be able to unambiguously parse elements of $\mathbb{K}$ we will
use construction sequences consisting of uniquely readable words.

######  Definition 2.

Let $\Sigma$ be an alphabet and $W$ be a collection of finite words in
$\Sigma$. Then $W$ is _uniquely readable_ if and only if whenever $u,v,w\in W$
and $uv=pws$ with $p$ and $s$ strings of symbols in $\Sigma$, then either $p$
or $s$ is the empty word.

Moreover, our $(n+1)$-words will be strongly uniform in the $n$-words as
defined below.

######  Definition 3.

We call a construction sequence $\left(W_{n}\right)_{n\in\mathbb{N}}$
_uniform_ if there is a summable sequence $(\varepsilon_{n})_{n\in\mathbb{N}}$
of positive numbers and for each $n\in\mathbb{N}$ a map $d_{n}:W_{n}\to(0,1)$
such that for all words $w^{\prime}\in W_{n+1}$ and $w\in W_{n}$ we have

$\Big{|}\frac{r(w,w^{\prime})}{h_{n+1}/h_{n}}-d_{n}(w)\Big{|}<\frac{\varepsilon_{n+1}}{h_{n}},$

where $r(w,w^{\prime})$ is the number of of occurrences of $w$ in
$w^{\prime}$. Moreover, the construction sequence is called _strongly uniform_
if for each $n\in\mathbb{N}$ there is a constant $c>0$ such that for all words
$w^{\prime}\in W_{n+1}$ and $w\in W_{n}$ we have $r(w,w^{\prime})=c$.

In the following we will identify $\mathbb{K}$ with the symbolic system
$\left(\mathbb{K},sh\right)$. We introduce the following natural set $S$ which
will be of measure one for measures that we consider.

######  Definition 4.

Suppose that $\left(W_{n}\right)_{n\in\mathbb{N}}$ is a construction sequence
for a symbolic system $\mathbb{K}$ with each $W_{n}$ uniquely readable. Let
$S$ be the collection of $x\in\mathbb{K}$ such that there are sequences of
natural numbers $\left(a_{n}\right)_{n\in\mathbb{N}}$,
$\left(b_{n}\right)_{n\in\mathbb{N}}$ going to infinity such that for all
$m\in\mathbb{N}$ there is $n\in\mathbb{N}$ such that
$x\upharpoonright[-a_{m},b_{m})\in W_{n}$.

We note that $S$ is a dense shift-invariant $\mathcal{G}_{\delta}$ subset of
$\mathbb{K}$ and we recall the following properties from [FW19a, Lemma 11] and
[FW19b, Lemma 12].

######  Fact 5.

Fix a construction sequence $\left(W_{n}\right)_{n\in\mathbb{N}}$ for a
symbolic system $\mathbb{K}$ in a finite alphabet $\Sigma$. Then:

  1. (1)

$\mathbb{K}$ is the smallest shift-invariant closed subset of
$\Sigma^{\mathbb{Z}}$ such that for all $n\in\mathbb{N}$ and $w\in W_{n}$,
$\mathbb{K}$ has non-empty intersection with the basic open interval
$\left\langle w\right\rangle\subset\Sigma^{\mathbb{Z}}$.

  2. (2)

Suppose that $\left(W_{n}\right)_{n\in\mathbb{N}}$ is a uniform construction
sequence. Then there is a unique non-atomic shift-invariant measure $\nu$ on
$\mathbb{K}$ concentrating on $S$ and $\nu$ is ergodic.

  3. (3)

If $\nu$ is a shift-invariant measure on $\mathbb{K}$ concentrating on $S$,
then for $\nu$-almost every $s\in S$ there is $N\in\mathbb{N}$ such that for
all $n>N$ there are $a_{n}\leq 0<b_{n}$ such that
$s\upharpoonright[a_{n},b_{n})\in W_{n}$.

Since our symbolic systems
$\mathbb{K}\cong\left(\Sigma^{\mathbb{Z}},\mathcal{B},\nu,sh\right)$ will be
built from a uniquely readable uniform construction sequence, they will
automatically be ergodic. To each symbolic system we will also consider its
inverse $\mathbb{K}^{-1}$ which stands for $\left(\mathbb{K},sh^{-1}\right)$.
Since it will often be convenient to have the shifts going in the same
direction, we also introduce another convention.

######  Definition 6.

If $w$ is a finite or infinite string, we write $rev(w)$ for the reverse
string of $w$. In particular, if $x$ is in $\mathbb{K}$ we define $rev(x)$ by
setting $rev(x)(k)=x(-k)$. Then for $A\subseteq\mathbb{K}$ we define
$rev(A)=\left\\{rev(x):x\in A\right\\}.$

If we explicitly view a finite word $w$ positioned at a location interval
$[a,b)$, then we take $rev(w)$ to be positioned at the same interval $[a,b)$
and we set $rev(w)(k)=w(a+b-(k+1))$. For a collection $W$ of words $rev(W)$ is
the collection of reverses of words in $W$.

Then we introduce the symbolic system $\left(rev(\mathbb{K}),sh\right)$ as the
one built from the construction sequence
$\left(rev(W_{n})\right)_{n\in\mathbb{N}}$. Clearly, the map sending $x$ to
$rev(x)$ is a canonical isomorphism between $\left(\mathbb{K},sh^{-1}\right)$
and $\left(rev(\mathbb{K}),sh\right)$. We often abbreviate the symbolic system
$\left(rev(\mathbb{K}),sh\right)$ as $rev(\mathbb{K})$. If we have a cutting-
and-stacking model of $\left(rev(\mathbb{K}),sh\right)$ where each level
(except the top level) of each column is mapped to the level above it, then
the model for $\left(\mathbb{K},sh^{-1}\right)$ would map each level (except
the bottom level) to the level below it. In analogy with
$\left(rev(\mathbb{K}),sh\right)$, we could instead reverse the order of the
levels in each column and map the levels upward.

###  2.3. Odometer-Based Systems

The systems constructed in the first part of the paper to prove our anti-
classification result for ergodic MPT’s will turn out to be so-called
odometer-based systems. In this subsection we review the definition.

Let $\left(k_{n}\right)_{n\in\mathbb{N}}$ be a sequence of natural numbers
$k_{n}\geq 2$ and

$O=\prod_{n\in\mathbb{N}}\left(\mathbb{Z}/k_{n}\mathbb{Z}\right)$

be the $\left(k_{n}\right)_{n\in\mathbb{N}}$-adic integers. Then $O$ has a
compact abelian group structure and hence carries a Haar measure $\mu$. We
define a transformation $T:O\to O$ to be addition by $1$ in the
$\left(k_{n}\right)_{n\in\mathbb{N}}$-adic integers (that is, the map that
adds one in $\mathbb{Z}/k_{0}\mathbb{Z}$ and carries right). Then $T$ is a
$\mu$-preserving invertible transformation, called an _odometer
transformation_ , which is ergodic and has discrete spectrum.

We now define the collection of symbolic systems that have odometer systems as
their timing mechanism to parse typical elements of the system.

######  Definition 7.

Let $\left(W_{n}\right)_{n\in\mathbb{N}}$ be a uniquely readable construction
sequence with $W_{0}=\Sigma$ and $W_{n+1}\subseteq\left(W_{n}\right)^{k_{n}}$
for every $n\in\mathbb{N}$. The associated symbolic shift will be called an
_odometer-based system_.

Thus, odometer-based systems are those built from construction sequences
$\left(W_{n}\right)_{n\in\mathbb{N}}$ such that the words in $W_{n+1}$ are
concatenations of a fixed number $k_{n}$ of words in $W_{n}$. Hence, the words
in $W_{n}$ have length

$h_{n}=\prod_{i=0}^{n-1}k_{i},$

if $n>0$, and $h_{0}=1$. Moreover, the spacers in part 3 of Definition 1 are
all the empty words (that is, an odometer-based transformation can be built by
a cutting-and-stacking construction using no spacers).

######  Remark.

By [FW4], any finite entropy system that has an odometer factor can be
represented as an odometer-based system

###  2.4. The $\overline{f}$ metric

Feldman [Fe76] introduced a notion of distance, now called $\overline{f}$,
between strings of symbols.

######  Definition 8.

A _match_ between two strings of symbols $a_{1}a_{2}\dots a_{n}$ and
$b_{1}b_{2}\dots b_{m}$ from a given alphabet $\Sigma,$ is a collection
$\mathcal{M}$ of pairs of indices $(i_{s},j_{s})$, $s=1,\dots,r$ such that
$1\leq i_{1}<i_{2}<\cdots<i_{r}\leq n$, $1\leq j_{1}<j_{2}<\cdots<j_{r}\leq m$
and $a_{i_{s}}=b_{j_{s}}$ for $s=1,2,\dots,r.$ A _pairing_ is defined the same
way as a match, except we drop the requirement that $a_{i_{s}}=b_{j_{s}}.$Then

(2.1) $\begin{array}[]{ll}\overline{f}(a_{1}a_{2}\dots a_{n},b_{1}b_{2}\dots
b_{m})=\hfill\\\ {\displaystyle
1-\frac{2\sup\\{|\mathcal{M}|:\mathcal{M}\text{\ is\ a\ match\ between\
}a_{1}a_{2}\cdots a_{n}\text{\ and\ }b_{1}b_{2}\cdots
b_{m}\\}}{n+m}.}\end{array}$

We will refer to $\overline{f}(a_{1}a_{2}\cdots a_{n},b_{1}b_{2}\cdots b_{m})$
as the “$\overline{f}$-distance” between $a_{1}a_{2}\cdots a_{n}$ and
$b_{1}b_{2}\cdots b_{m},$ even though $\overline{f}$ does not satisfy the
triangle inequality unless the strings are all of the same length. A match
$\mathcal{M}$ is called a _best possible match_ if it realizes the supremum in
the definition of $\overline{f}$. The extension of the definition of
$\overline{f}$-distance from finite words to infinite words is analogous to
the extension for $\overline{d}$-distance.

If $x=x_{1}x_{2}\cdots x_{n}$ and $y=y_{1}y_{2}\cdots y_{n}$ are
decompositions of the strings of symbols $x$ and $y$ into substrings such that
in a given match (or pairing) between $x$ and $y$, all matches (or pairings)
are between symbols in $x_{i}$ and $y_{i},$ for $i=1,2,\dots,n,$ then we say
that $x_{i}$ _corresponds_ to $y_{i}$ (and vice versa), under this match (or
pairing). If we are given a match or pairing between $x=x_{1}x_{2}\cdots
x_{n}$ and $y,$ then we can decompose $y$ into $y_{1}y_{2}\cdots y_{n}$ so
that $x_{i}$ corresponds to $y_{i},$ for $i=1,2,\dots,n.$ The choice of
$y_{1},y_{2},\dots,y_{n}$ is not unique, but this does not matter in any of
our arguments.

######  Remark.

In the proof of Lemma 13, we will use certain pairings to give an upper bound
on $|\mathcal{M}|,$ for a best possible match $\mathcal{M}.$

######  Remark.

Alternatively, one can view a match as an injective order-preserving function
$\pi:\mathcal{D}(\pi)\subseteq\left\\{1,\dots,n\right\\}\to\mathcal{R}(\pi)\subseteq\left\\{1,\dots,m\right\\}$
with $a_{i}=b_{\pi(i)}$ for every $i\in\mathcal{D}(\pi)$. Then
$\overline{f}\left(a_{1}\dots a_{n},b_{1}\dots
b_{m}\right)=1-\max\left\\{\frac{2|\mathcal{D}(\pi)|}{n+m}:\pi\text{ is a
match}\right\\}$.

The following simple properties of $\overline{f}$ from [GKpp], that were
already used in [Fe76] and [ORW82], will appear frequently in our arguments.
These properties can be proved easily by considering the _fit_
$1-\bar{f}(a,b)$ between two strings $a$ and $b$.

######  Fact 9.

Suppose $a$ and $b$ are strings of symbols of length $n$ and $m,$
respectively, from an alphabet $\Sigma$. If $\tilde{a}$ and $\tilde{b}$ are
strings of symbols obtained by deleting at most $\lfloor\gamma(n+m)\rfloor$
terms from $a$ and $b$ altogether, where $0<\gamma<1$, then

(2.2) $\overline{f}(a,b)\geq\overline{f}(\tilde{a},\tilde{b})-2\gamma.$

Moreover, if there exists a best possible match between $a$ and $b$ such that
no term that is deleted from $a$ and $b$ to form $\tilde{a}$ and $\tilde{b}$
is matched with a non-deleted term, then

(2.3) $\overline{f}(a,b)\geq\overline{f}(\tilde{a},\tilde{b})-\gamma.$

Likewise, if $\tilde{a}$ and $\tilde{b}$ are obtained by adding at most
$\lfloor\gamma(n+m)\rfloor$ symbols to $a$ and $b$, then (2.3) holds.

######  Fact 10.

If $x=x_{1}x_{2}\cdots x_{n}$ and $y=y_{1}y_{2}\cdots y_{n}$ are
decompositions of the strings of symbols $x$ and $y$ into corresponding
substrings under a best possible $\overline{f}$-match between $x$ and $y,$
that is, one that achieves the minimum in the definition of $\overline{f},$
then

$\overline{f}(x,y)=\sum_{i=1}^{n}\overline{f}(x_{i},y_{i})v_{i},$

where

(2.4) $v_{i}=\frac{|x_{i}|+|y_{i}|}{|x|+|y|}.$

######  Fact 11.

If $x$ and $y$ are strings of symbols such that $\overline{f}(x,y)\leq\gamma,$
for some $0\leq\gamma<1,$ then

(2.5)
$\left(\frac{1-\gamma}{1+\gamma}\right)|x|\leq|y|\leq\left(\frac{1+\gamma}{1-\gamma}\right)|x|.$

We also recall the following elementary fact from [ORW82, Proposition 2.3,
p.85].

######  Fact 12.

Suppose $a$ and $b$ are strings of symbols of length $n$ and $m,$
respectively, from an alphabet $\Sigma$. Let $h$ be a symbol that is not an
element in $\Sigma$. Suppose $\tilde{a}$ and $\tilde{b}$ are strings of
symbols obtained by inserting at most $(\beta-1)n$ symbols $h$ in $a$ and at
most $(\beta-1)m$ symbols $h$ in $b$. Then

$\overline{f}\left(\tilde{a},\tilde{b}\right)\geq\frac{\overline{f}(a,b)}{\beta}.$

The next result provides lower bounds on the $\overline{f}$ distance when
symbols $a_{i}$ and $b_{j}$ are replaced by blocks $A_{a_{i}}$ and
$A_{b_{j}}$.

######  Lemma 13 (Symbol by block replacement).

Suppose that $A_{a_{1}},A_{a_{2}},\dots,A_{a_{n}}$ and
$A_{b_{1}},A_{b_{2}},\cdots,A_{b_{m}}$ are blocks of symbols with each block
of length $L.$ Assume that $\alpha\in(0,1/7),R\geq 2,$ and for all substrings
$C$ and $D$ consisting of consecutive symbols from $A_{a_{i}}$ and
$A_{b_{j}},$ respectively, with $|C|,|D|\geq L/R,$ we have

$\overline{f}(C,D)\geq\alpha\text{, if }a_{i}\neq b_{j}.$

Then

$\overline{f}(A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}},A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}})>\alpha\overline{f}(a_{1}a_{2}\dots a_{n},b_{1}b_{2}\dots
b_{m})-\frac{1}{R}.$

###### Proof.

We may assume $n\leq m.$ Suppose $\mathcal{M}$ is a best possible match
between $A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}}$ and $A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}}.$ Recall that $|\mathcal{M}|$ denotes the number of pairs of symbols
in $A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}}$ and $A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}}$ that are matched by $\mathcal{M}.$ We use the analogous notation
$|\mathcal{N}|$ for a match $\mathcal{N}$ between the strings
$a_{1}a_{2}\cdots a_{n}$ and $b_{1}b_{2}\cdots b_{m}.$

_Claim._ There exists a match $\mathcal{N}$ (not necessarily a best possible
match) between the strings $a_{1}a_{2}\dots a_{n}$ and $b_{1}b_{2}\cdots
b_{m}$ such that

(2.6)
$L(n+m)-2|\mathcal{M}|\geq\alpha\big{\\{}L(n+m)-2L|\mathcal{N}|-\frac{3L(n+m)}{R}\big{\\}}.$

The lemma will follow from this claim, because

$\overline{f}(A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}},A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}})=1-\frac{2|\mathcal{M}|}{L(n+m)}\text{\ and\ }$

$\begin{array}[]{ccc}\frac{\alpha}{L(n+m)}\big{\\{}L(n+m)-2L|\mathcal{N}|-\frac{3L(n+m)}{R}\big{\\}}&\geq&\alpha\overline{f}(a_{1}a_{2}\cdots
a_{n},b_{1}b_{2}\cdots b_{m})-\frac{3\alpha}{R}\\\
&>&\alpha\overline{f}(a_{1}a_{2}\cdots a_{n},b_{1}b_{2}\cdots
b_{m})-\frac{1}{R}.\end{array}$

_Proof of Claim._ We will modify $\mathcal{M}$ in a series of $i$ steps, for
$i=1,2,\dots,n,$ obtaining pairings $\mathcal{M}_{i}$ between
$A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}}$ and $A_{b_{1}}A_{b_{2}}\cdots A_{b_{m}}$
such that $|\mathcal{M}|\leq|\mathcal{M}_{1}|\leq\cdots\leq$
$|\mathcal{M}_{n-1}|\leq|\mathcal{M}_{n}|.$ The positions of the modifications
will move from left to right with each step. We will simultaneously construct
a sequence of matches $\mathcal{N}_{i}$ between $a_{1}a_{2}\dots a_{n}$ and
$b_{1}b_{2}\dots b_{m}$ such that
$\mathcal{N}_{1}\subseteq\mathcal{N}_{2}\subseteq\cdots\subseteq\mathcal{N}_{n}.$
At the end of this construction, we will show that the inequality (2.6) holds
with $\mathcal{N}=\mathcal{N}_{n}$ and $\mathcal{M}$ replaced by
$\mathcal{M}_{n}.$ This implies (2.6) as written.

We let $\mathcal{M}_{0}=\mathcal{M}$ and $\mathcal{N}_{0}=\emptyset$. In the
inductive construction of $\mathcal{M}_{i}$ and $\mathcal{N}_{i}$ (as
described below), at most one pair of matching symbols is added to
$\mathcal{N}_{i-1}$ to form $\mathcal{N}_{i},$ and each time such an addition
occurs, we allow up to $L$ pairs to be in the part of $\mathcal{M}_{i}$ that
is newly specified at stage $i$.

Suppose $1\leq i\leq n,$ and $\mathcal{M}_{i-1}$ and $\mathcal{N}_{i-1}$ have
been constructed. Assume that $A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}}=B_{1}B_{2}\cdots B_{n},$ where $A_{a_{j}}$ corresponds to $B_{j}$
under $\mathcal{M}_{i-1}.$ If $B_{i}$ starts with a symbol in $A_{b_{j_{i}}}$,
we also assume that none of symbols in the matching pairs in
$\mathcal{N}_{i-1}$ come from $a_{i}a_{i+1}\dots a_{n}$ or
$b_{j_{i}}b_{j_{i}+1}\dots b_{m}.$ (Therefore these symbols are still
available to add to $\mathcal{N}_{i-1}$ to form $\mathcal{N}_{i}.)$ We
consider the following four cases (with various subcases).

_Case 1._ $B_{i}$ contains two or more complete $A_{b_{j}}$’s. Then
$|B_{i}|\geq 2|A_{a_{i}}|$ and therefore
$\overline{f}(A_{a_{i}},B_{i})>1/7>\alpha$ by Fact 11. In this case we take
$\mathcal{M}_{i}=\mathcal{M}_{i-1}$ and $\mathcal{N}_{i}=\mathcal{N}_{i-1}.$

_Case 2._ $B_{i}$ consists of one complete $A_{b_{j}}$ plus possibly a final
string $A_{b_{j-1}}^{\text{fin}}$ in $A_{b_{j-1}}$ and possibly an initial
string $A_{b_{j+1}}^{\text{int}}$ in $A_{b_{j+1}}.$ By the induction
hypothesis, $b_{j}$,$b_{j+1},$ and $a_{i}$ are not in any of the pairs in
$\mathcal{N}_{i-1}$, and neither is $b_{j-1}$ if
$A_{b_{j-1}}^{\text{fin}}\neq\emptyset.$
_Case 2(i)_. If $a_{i}=b_{j-1}$ or $a_{i}=b_{j}$, then we add one pair of
equal symbols from these equations to $\mathcal{N}_{i-1}$ to form
$\mathcal{N}_{i}.$ To construct $\mathcal{M}_{i}$ we modify
$\mathcal{M}_{i-1}$ on $A_{a_{i}}$ and $B_{i}$ to create a perfect pairing
between $A_{a_{i}}$ and $A_{b_{j}}$. (That is, each symbol in $A_{a_{i}}$ is
paired with a symbol in $A_{b_{j}}$, even though they might not actually
match.) The symbols in $B_{i}\setminus A_{b_{j}}$ are not paired to anything
by $\mathcal{M}_{i}$ and they are eliminated from consideration for any future
pairings $\mathcal{M_{\ell}}$ for $\ell>i$. Outside of $A_{a_{i}}$ and
$B_{i},$ $\mathcal{M}_{i}$ agrees with $\mathcal{M}_{i-1}.$ Note that
$|\mathcal{M}_{i}|\geq|\mathcal{M}_{i-1}|$ because $\mathcal{M}_{i}$ has the
maximum possible number of pairings between $A_{a_{i}}$ and $B_{i}.$
_Case 2(ii)_. If $a_{i}\neq b_{j-1}$, $a_{i}\neq b_{j},$ and $a_{i}=b_{j+1},$
then we add $a_{i}$ and $b_{j+1}$ to $\mathcal{N}_{i-1}$ to form
$\mathcal{N}_{i}.$ In this subcase and the next one, we let
$A_{a_{i}}^{(0)},A_{a_{i}}^{(1)},$ and $A_{a_{i}}^{(2)}$ be the subdivision of
$A_{a_{i}}$ into the segments corresponding to
$A_{b_{j-1}}^{\text{fin}}$,$A_{b_{j}}$, and $A_{b_{j+1}}^{\text{int}},$
respectively. We construct $\mathcal{M}_{i}$ from $\mathcal{M}_{i-1}$ by
creating a perfect pairing between the extension of $A_{a_{i}}^{(2)}$ to a
total length of $L$ symbols and $A_{b_{j+1}}.$ (In case $i=n,$ we only pair
$A_{a_{n}}^{(2)},$ with no extension). Any pairing in $\mathcal{M}_{i-1}$
involving a symbol in this extension of $A_{a_{i}}^{(2)}$ or in $A_{b_{j+1}}$
that is different from the newly created perfect pairing is not included in
$\mathcal{M}_{i}.$ Otherwise $\mathcal{M}_{i}$ is the same as
$\mathcal{M}_{i-1}.$ On the part that was changed the pairing is as good as it
can be for that number of symbols, and therefore
$|\mathcal{M}_{i}|\geq|\mathcal{M}_{i-1}|$. On the strings $A_{a_{i}}^{(0)}$
and $A_{b_{j-1}}^{\text{fin}}$ the subscripts of the blocks do not match, and
therefore either $\overline{f}(A_{a_{i}}^{(0)},$
$A_{b_{j-1}}^{\text{fin}})\geq\alpha$ by hypothesis or at least one of these
two strings has length less than $L/R.$ In the latter case, if the other
string has length at least $4L/(3R),$ then by Fact 11,
$\overline{f}(A_{a_{i}}^{(0)},$ $A_{b_{j-1}}^{\text{fin}})>1/7>\alpha.$ If one
string has length less than $L/R$ and the other string has length less than
$4L/(3R)$ we refer to this as the “short substring case$"$ and the number of
symbols coming from such cases will be at most $14Ln/(3R)\leq
7L(n+m)/(3R)<3L(n+m)/R.$ (As we will see in the next subcase there could be up
to two pairs of short substrings for each $i\in\\{1,2,\dots n\\}$.) The
strings $A_{a_{i}}^{(1)}$ and $A_{b_{j}}$ are also in blocks whose subscripts
do not match. Since $A_{b_{j}}$ is an entire block, the short substring case
does not apply, and we obtain
$\overline{f}(A_{a_{i}}^{(1)},A_{b_{j}})>\alpha.$ For the next step, $B_{i+1}$
starts with $A_{b_{j+2}}$ and we modify $A_{a_{i+1}}$ to be only the last
$|A_{a_{i}}^{(2)}|$ symbols in the original $A_{a_{i+1}}.$
_Case 2(iii)_. If $a_{i}\neq b_{j-1}$, $a_{i}\neq b_{j},$ and $a_{i}\neq
b_{j+1},$ then we keep $\mathcal{M}_{i}=\mathcal{M}_{i-1}$ and
$\mathcal{N}_{i}=\mathcal{N}_{i-1}.$ For each of the pairs $A_{a_{i}}^{(0)}$
and $A_{b_{j-1}}^{\text{fin}}$,$A_{a_{i}}^{(1)}$ and $A_{b_{j}}$,
$A_{a_{i}}^{(2)}$ and $A_{b_{j+1}}^{\text{int}}$, either we know that the
$\overline{f}$ distance is greater than $\alpha$ or (possibly for the first
and the third pair) we are in the short substring case.
_Case 3._ $B_{i}$ contains a final segment of $A_{b_{j-1}}$ and an initial
segment of $A_{b_{j}}.$
_Case 3(i)_. If $a_{i}=b_{j-1},$ then we add $a_{i}$ and $b_{j-1}$ to
$\mathcal{N}_{i-1}$ to form $\mathcal{N}_{i}$. We replace $\mathcal{M}_{i-1}$
on $A_{a_{i}}$ and $B_{i}$ by a perfect pairing between $A_{a_{i}}$ and $L$
consecutive symbols in the $A_{b_{j-1}}A_{b_{j}}$ string starting with the
first symbol in $B_{i}$. If $B_{i}$ contains fewer than $L$ symbols, then we
continue the pairing beyond the end of $B_{i}.$ (This may eliminate some
previous pairings that were in $\mathcal{M}_{i-1}$ but the net result is still
$|\mathcal{M}_{i}|\geq|\mathcal{M}_{i-1}|.)$ If $B_{i}$ contains more than $L$
symbols, then the remaining $|B_{i}|-L$ symbols stay unpaired in
$\mathcal{M}_{\ell}$ for $\ell\geq i.$
_Case 3(ii)_. If $a_{i}\neq b_{j-1}$ and $a_{i}=b_{j},$ then we add $a_{i}$
and $b_{j}$ to $\mathcal{N}_{i-1}$ to form $\mathcal{N}_{i}.$ We keep
$\mathcal{M}_{i}$ the same as $\mathcal{M}_{i-1}$ up to the symbol prior to
the first one in $A_{a_{i}}$ that is paired with a symbol in $A_{b_{j}}.$ Then
we pair the next $L$ consecutive symbols in $A_{a_{i}}A_{a_{i+1}}$ to
$A_{b_{j}}.$ Otherwise $\mathcal{M}_{i}$ stays the same as
$\mathcal{M}_{i-1}.$
_Case 3(iii)_. If $a_{i}\neq b_{j-1}$ and $a_{i}\neq b_{j},$ then we again
have two pairs of strings, one for the part of $A_{i}$ that corresponds to a
final segment of $A_{b_{j-1}}$ and the other for the part of $A_{i}$ that
corresponds to the initial segment of $A_{b_{j}}.$ Each of these pairs is
$\overline{f}$ distance at least $\alpha$ apart or consists of short
substrings. We let $\mathcal{M}_{i}=\mathcal{M}_{i-1}$ and
$\mathcal{N}_{i}=\mathcal{N}_{i-1}.$
_Case 4._ $B_{i}$ is a substring of a single $A_{b_{j}}.$
_Case 4(i)_. If $a_{i}=b_{j},$ then we add $a_{i}$ and $b_{j}$ to
$\mathcal{N}_{i-1}$ to form $\mathcal{N}_{i}$. If $j\neq m$, we construct
$\mathcal{M}_{i}$ by extending $B_{i}$ to the right for a total of $L$ symbols
and pairing the extended $B_{i}$ exactly with $A_{a_{i}}.$ If $j=m$, we pair
all of $B_{i}$ with a substring in $A_{a_{i}}$. Whatever pairings in
$\mathcal{M}_{i-1}$ are not affected by these changes are included in
$\mathcal{M}_{i}.$
_Case 4(ii)_. If $a_{i}\neq b_{j},$ then
$\overline{f}(A_{a_{i}},B_{j})\geq\alpha,$ and we let
$\mathcal{M}_{i}=\mathcal{M}_{i-1}$ and $\mathcal{N}_{i}=\mathcal{N}_{i-1}.$

In summary, after we apply this procedure for $i=1,2,\dots,n,$ and we remove
from $A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}}$ and $A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}}$ the symbols involved in the (at most $L|\mathcal{N}_{n}|$) pairings
obtained from Cases (2i),(2ii),(3i),(3ii), and (4i) in the formation of
$\mathcal{M}_{i}$ from $\mathcal{M}_{i-1}$, and we remove the pairs of
corresponding strings in the short substring case, we are left with a total of
at least $L(n+m)-2L|\mathcal{N}_{n}|-3L((n+m)/R)$ symbols in pairs of strings
in $A_{a_{1}}A_{a_{2}}\cdots A_{a_{n}}$ and $A_{b_{1}}A_{b_{2}}\cdots
A_{b_{m}}$ that correspond under $\mathcal{M}_{n}.$ On these corresponding
strings the $\mathcal{M}_{n}$ pairing is a subset of the original
$\mathcal{M}$, and the symbols in each pair of these corresponding strings are
contained in some $A_{a_{i}}$ and $A_{b_{j}}$ where $a_{i}\neq b_{j}.$ By
hypothesis, the $\overline{f}$-distance between two such corresponding strings
is at least $\alpha.$ Therefore

$\begin{array}[]{ccc}L(n+m)-2|\mathcal{M}_{0}|&\geq&L(n+m)-2|\mathcal{M}_{n}|\\\
&\geq&\alpha\big{\\{}L(n+m)-2L|\mathcal{N}_{n}|-\frac{3L(n+m)}{R}\big{\\}},\end{array}$

where the second inequality follows from Fact 10. ∎

###  2.5. Some background from descriptive set theory

To state our results precisely we need some concepts explained below. The main
tool is the idea of a reduction. See [Ke95] and [Fo18] for further
information.

######  Definition 14.

Let $X$ and $Y$ be Polish spaces and $A\subseteq X$, $B\subseteq Y$. A
function $f:X\to Y$ _reduces_ $A$ to $B$ if and only if for all $x\in X$:
$x\in A$ if and only if $f(x)\in B$.

Such a function $f$ is called a Borel (respectively, continuous) reduction if
$f$ is a Borel (respectively, continuous) function.

$A$ being reducible to $B$ can be interpreted as saying that $B$ is at least
as complicated as $A$. We note that if $B$ is Borel and $f$ is a Borel
reduction, then $A$ is also Borel. Equivalently, if $f$ is a Borel reduction
of $A$ to $B$ and $A$ is not Borel, then $B$ is not Borel.

######  Definition 15.

If $\mathcal{S}$ is a collection of sets and $B\in\mathcal{S}$, then $B$ is
called _$\mathcal{S}$ -complete_ for Borel (respectively, continuous)
reductions if and only if every $A\in\mathcal{S}$ is Borel (respectively,
continuously) reducible to $B$.

Following the interpretation above $B$ is said to be at least as complicated
as each set in $\mathcal{S}$.

######  Definition 16.

If $X$ is a Polish space and $B\subseteq X$, then $B$ is _analytic_ if and
only if it is the continuous image of a Borel subset of a Polish space.
Equivalently, there is a Polish space $Y$ and a Borel set $C\subseteq X\times
Y$ such that $B$ is the $X$-projection of $C$.

There are analytic sets that are not Borel (see, for example, [Ke95, section
14]). This implies that a complete analytic set is not Borel. The collection
of ill-founded trees, which we describe below, is an example of a complete
analytic set, and it is fundamental to our construction, as well as that in
[FRW11].

To define the ill-founded trees, we first consider the set
$\mathbb{N}^{<\mathbb{N}}$ of finite sequences of natural numbers. For
$\tau\in\mathbb{N}^{<\mathbb{N}},$ let $lh(\tau)$ denote the length of $\tau$.
A _tree_ is a set $\mathcal{T}\subseteq\mathbb{N}^{<\mathbb{N}}$ such that if
$\tau=\left(\tau_{1},\dots,\tau_{n}\right)\in\mathcal{T}$ and
$\sigma=\left(\tau_{1},\dots,\tau_{s}\right)$ with $s\leq n$ is an initial
segment of $\tau$, then $\sigma\in\mathcal{T}$. If $\sigma$ is an initial
segment of $\tau$, then $\sigma$ is a _predecessor_ of $\tau$ and $\tau$ is a
_successor_ of $\sigma$. We define the level $s$ of a tree $\mathcal{T}$ to be
the collection of elements of $\mathcal{T}$ that have length $s$.

A _branch_ through $\mathcal{T}$ is a function $f$ into $\mathcal{T}$ with
domain either some $\\{0,\dots,n-1\\}$ or $\mathbb{N}$ itself such that
$lh(f(s))=s$, and if $s+1$ is in the domain of $f$, then $f(s+1)$ is an
immediate successor of $f(s)$. If a tree has an infinite branch (that is, the
$f$ above can be taken with domain $\mathbb{N}$), it is called _ill-founded_.
If it does not have an infinite branch, it is called _well-founded_.

In the following, let $\left\\{\sigma_{n}:n\in\mathbb{N}\right\\}$ be an
enumeration of $\mathbb{N}^{<\mathbb{N}}$ with the property that every proper
predecessor of $\sigma_{n}$ is some $\sigma_{m}$ for $m<n$. Under this
enumeration subsets $S\subseteq\mathbb{N}^{<\mathbb{N}}$ can be identified
with characteristic functions $\chi_{S}:\mathbb{N}\to\left\\{0,1\right\\}$.
The collection of such $\chi_{S}$ can be viewed as the members of an infinite
product space $\left\\{0,1\right\\}^{\mathbb{N}^{<\mathbb{N}}}$ homeomorphic
to the Cantor space. Here, each function
$a:\left\\{\sigma_{m}:m<n\right\\}\to\left\\{0,1\right\\}$ determines a basic
open set

$\left\langle
a\right\rangle=\left\\{\chi:\chi\upharpoonright\left\\{\sigma_{m}:m<n\right\\}=a\right\\}\subseteq\left\\{0,1\right\\}^{\mathbb{N}^{<\mathbb{N}}}$

and the collection of all such $\left\langle a\right\rangle$ forms a basis for
the topology. The collection of trees is a closed (hence compact) subset of
$\left\\{0,1\right\\}^{\mathbb{N}^{<\mathbb{N}}}$ in this topology. Moreover,
the collection of trees containing arbitrarily long finite sequences is a
dense $\mathcal{G}_{\delta}$ subset. In particular, this collection is a
Polish space. We will denote the space of trees containing arbitrarily long
finite sequences by $\mathcal{T}\kern-1.42262ptrees$.

Since the topology on the space of trees was introduced via basic open sets
giving us a finite amount of information about the trees in it, we can
characterize continuous maps defined on $\mathcal{T}\kern-1.42262ptrees$ as
follows.

######  Fact 17.

Let $Y$ be a topological space. Then a map
$f:\mathcal{T}\kern-1.42262ptrees\to Y$ is continuous if and only if for all
open sets $O\subseteq Y$ and all
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ with $f(\mathcal{T})\in O$
there is $M\in\mathbb{N}$ such that for all
$\mathcal{T}^{\prime}\in\mathcal{T}\kern-1.42262ptrees$ we have:

if $\mathcal{T}\cap\left\\{\sigma_{n}:n\leq
M\right\\}=\mathcal{T}^{\prime}\cap\left\\{\sigma_{n}:n\leq M\right\\}$, then
$f\left(\mathcal{T}^{\prime}\right)\in O$.

As mentioned before, we have the following classical fact (see, for example,
[Ke95, section 27]).

######  Fact 18.

The collection of ill-founded trees is a complete analytic subset of
$\mathcal{T}\kern-1.42262ptrees$.

As described in the next section, we will prove the main results of this paper
by reducing the collection of ill-founded trees to pairs of Kakutani-
equivalent ergodic transformations. Then Fact 18 will show that this set of
Kakutani-equivalent pairs of transformations is also complete analytic.

During our construction the following maps will prove useful.

######  Definition 19.

We define a map $M:\mathcal{T}\kern-1.42262ptrees\to\mathbb{N}^{\mathbb{N}}$
by setting $M\left(\mathcal{T}\right)(s)=n$ if and only if $n$ is the least
number such that $\sigma_{n}\in\mathcal{T}$ and $lh(\sigma_{n})=s$. Dually, we
also define a map $s:\mathcal{T}\kern-1.42262ptrees\to\mathbb{N}^{\mathbb{N}}$
by setting $s\left(\mathcal{T}\right)(n)$ to be the length of the longest
sequence $\sigma_{m}\in\mathcal{T}$ with $m\leq n$.

######  Remark.

When $\mathcal{T}$ is clear from the context we write $M(s)$ and $s(n)$. We
also note that $s(n)\leq n$ and that $M$ as well as $s$ is a continuous
function when we endow $\mathbb{N}$ with the discrete topology and
$\mathbb{N}^{\mathbb{N}}$ with the product topology.

##  3\. Main Results

###  3.1. Statement of results

We are ready to state the main result of this paper.

######  Theorem 20.

The collection

$\left\\{(S,T):S\text{ and }T\text{ are ergodic and Kakutani
equivalent}\right\\}\subseteq\mathcal{E}\times\mathcal{E}$

is a complete analytic set. In particular, it is not Borel.

As we show below, this will follow from the subsequent theorem which is proved
in Section 9.

######  Theorem 21.

There is a continuous one-to-one map

$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$

such that for $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ and
$T=\Psi(\mathcal{T})$:

$\mathcal{T}$ has an infinite branch if and only if $T$ and $T^{-1}$ are
Kakutani equivalent.

Using the notions from descriptive set theory in Section 2.5, Theorem 21 can
also be expressed as follows.

######  Corollary 22.

There is a continuous one-to-one map

$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$

that reduces the collection of ill-founded trees to the collection of ergodic
transformations $T$ such that $T$ and $T^{-1}$ are Kakutani equivalent.

###### Proof of Theorem 20.

The map $i(T)=\left(T,T^{-1}\right)$ is a continuous mapping from
$\mathcal{E}$ to $\mathcal{E}\times\mathcal{E}$ and reduces
$\left\\{T\in\mathcal{E}:T\text{ is Kakutani equivalent to }T^{-1}\right\\}$
to

$\left\\{(S,T)\in\mathcal{E}\times\mathcal{E}:S\text{ and }T\text{ are
Kakutani equivalent}\right\\}.$

Then Theorem 20 follows from Fact 18 and Corollary 22. ∎

To prove Theorem 21 we actually show the following stronger result.

######  Proposition 23.

There is a continuous one-to-one map

$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$

such that for $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ and
$T=\Psi(\mathcal{T})$:

  1. (1)

If $\mathcal{T}$ has an infinite branch, then $T$ and $T^{-1}$ are isomorphic.

  2. (2)

If $T$ and $T^{-1}$ are Kakutani equivalent, then $\mathcal{T}$ has an
infinite branch.

This stronger proposition also implies the anti-classification result for the
isomorphism relation in [FRW11].

######  Corollary.

There is a continuous one-to-one map

$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$

that reduces the collection of ill-founded trees to the collection of ergodic
automorphisms $T$ such that $T$ is isomorphic to $T^{-1}$. Hence, the
collection

$\left\\{(S,T):S\text{ and }T\text{ are ergodic and
isomorphic}\right\\}\subseteq\mathcal{E}\times\mathcal{E}$

is a complete analytic set.

In Section 10 we are able to upgrade these results to the setting of
diffeomorphisms.

######  Theorem 24.

Let $M$ be the disk, annulus or torus with Lebesgue measure $\lambda$. Then
the collection

$\left\\{(S,T):S\text{ and }T\text{ are ergodic diffeomorphisms and Kakutani
equivalent}\right\\}$

in $\text{Diff}^{\,\infty}(M,\lambda)\times\text{Diff}^{\,\infty}(M,\lambda)$
is a complete analytic set and hence not a Borel set with respect to the
$C^{\infty}$ topology.

In case of $M=\mathbb{T}^{2}$ we also obtain the results in the real-analytic
category (see Subsection 10.1 for the definition of the space
$\text{Diff}_{\rho}^{\,\omega}(M,\lambda)$).

######  Theorem 25.

Let $\rho>0$ and $\lambda$ be the Lebesgue measure on $\mathbb{T}^{2}$. Then
the collection

$\left\\{(S,T):S\text{ and }T\text{ are ergodic diffeomorphisms and Kakutani
equivalent}\right\\}$

in
$\text{Diff}_{\rho}^{\,\omega}(M,\lambda)\times\text{Diff}_{\,\rho}^{\,\omega}(M,\lambda)$
is a complete analytic set and hence not a Borel set with respect to the
$\text{Diff}_{\rho}^{\,\omega}$ topology.

###  3.2. Outline of the proof of Proposition 23

To construct the reduction $\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$
we build for every $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ a
transformation $\Psi(\mathcal{T})$ as a symbolic system with a strongly
uniform and uniquely readable construction sequence
$\left(\mathcal{W}_{n}\left(\mathcal{T}\right)\right)_{n\in\mathbb{N}}$ which
implies its ergodicity. This will be done in such a way that
$\mathcal{W}_{n}(\mathcal{T})$ is entirely determined by
$\mathcal{T}\cap\left\\{\sigma_{m}:m\leq n\right\\}$, which, by Fact 17
guarantees continuity of $\Psi$ (see Proposition 20 in [FRW11] for details).
(Alternatively, in the cutting-and-stacking model, the $n$th tower is
determined by $\mathcal{T}\cap\left\\{\sigma_{m}:m\leq n\right\\}$, and this
implies that $\Psi$ is continuous.) Related to the structure of the tree we
also specify equivalence relations $\mathcal{Q}_{s}^{n}(\mathcal{T})$ on the
collections $\mathcal{W}_{n}(\mathcal{T})$ of $n$-words and group actions on
the equivalence classes in
$\mathcal{W}_{n}(\mathcal{T})/\mathcal{Q}_{s}^{n}(\mathcal{T})$ as in [FRW11].
These specifications will allow us to prove in Section 5 that
$\Psi(\mathcal{T})$ and $\Psi(\mathcal{T})^{-1}$ are isomorphic if the tree
$\mathcal{T}$ has an infinite branch.

The harder part is to show that $\Psi(\mathcal{T})$ and
$\Psi(\mathcal{T})^{-1}$ are not Kakutani equivalent if the tree $\mathcal{T}$
does not have an infinite branch. For this purpose, we build the $n$-words in
our construction sequence using specific patterns of blocks (that we call
Feldman patterns) which originate from Feldman’s first example of an ergodic
zero-entropy automorphism that is not loosely Bernoulli [Fe76]. As observed in
[ORW82], different Feldman patterns cannot be matched well in $\overline{f}$
even after a finite coding. We introduce these patterns in detail in Section
6. In our construction of $n$-words we apply them repeatedly by substituting
Feldman patterns of finer equivalence classes into Feldman patterns of coarser
classes. We present such a substitution step in general in Section 7, and then
use it in an iterative way to construct the collection
$\mathcal{W}_{n}(\mathcal{T})$ of $n$-words in Section 8. There we also verify
that $\mathcal{W}_{n}(\mathcal{T})$ satisfies the aforementioned
specifications. Finally, using techniques from [ORW82] based on the structure
of Feldman patterns, we show in Section 9 that $\Psi(\mathcal{T})$ and
$\Psi(\mathcal{T})^{-1}$ cannot be Kakutani equivalent if the tree
$\mathcal{T}$ does not have an infinite branch. In the analysis of possible
finite codes we face the additional challenge that we do not know the precise
words being coded, only their equivalence classes.

We transfer the results to the setting of diffeomorphisms in Section 10 and
give an outline of this proof at the beginning of that section.

##  4\. The Setup

We present a general setup of our construction. It is very similar to the one
in [FRW11, Section 4] with a few minor changes (for example, specification
(Q4) and our specifications on the group actions).

###  4.1. General properties of our construction

For each $n\in\mathbb{N}$ with $\sigma_{n}\in\mathcal{T}$ we construct a set
of words $\mathcal{W}_{n}=\mathcal{W}_{n}(\mathcal{T})$ in the basic alphabet
$\Sigma=\\{1,\dots,2^{12}\\}$ which depend only on
$\mathcal{T}\cap\left\\{\sigma_{m}:m\leq n\right\\}$. To start we set
$\mathcal{W}_{0}=\Sigma$.

  * (E1)

All words in $\mathcal{W}_{n}$ have the same length $h_{n}$ and the
cardinality $|\mathcal{W}_{n}|$ is a power of $2$.

  * (E2)

If $\sigma_{m}$ and $\sigma_{n}$ are consecutive elements of $\mathcal{T}$,
then every word in $\mathcal{W}_{n}$ is built by concatenating words in
$\mathcal{W}_{m}$. There is $f_{m}\in\mathbb{Z}^{+}$ such that every word in
$\mathcal{W}_{m}$ occurs in each word of $\mathcal{W}_{n}$ exactly $f_{m}$
times. The number $f_{m}$ will be a product of $p_{n}^{2}$ and powers of $2$,
where $p_{n}$ is a large prime number chosen when $\sigma_{n}$ is considered.

  * (E3)

If $\sigma_{m}$ and $\sigma_{n}$ are consecutive elements of $\mathcal{T}$,
$w=w_{1}\dots w_{h_{n}/h_{m}}\in\mathcal{W}_{n}$ and
$w^{\prime}=w_{1}^{\prime}\dots w_{h_{n}/h_{m}}^{\prime}\in\mathcal{W}_{n}$,
where $w_{i},w_{i}^{\prime}\in\mathcal{W}_{m}$, then for any
$k\geq\lfloor\frac{h_{n}/h_{m}}{2}\rfloor$ and $1\leq
i\leq\frac{h_{n}}{h_{m}}-k$, we have $w_{i+1}\dots w_{i+k}\neq
w_{1}^{\prime}\dots w_{k}^{\prime}$.

######  Remark 26.

In particular, these specifications say that
$\left\\{\mathcal{W}_{n}:\sigma_{n}\in\mathcal{T}\right\\}$ is a uniquely
readable and strongly uniform construction sequence for an odometer-based
system. Hence, the corresponding symbolic system $\mathbb{K}$ has a unique
non-atomic ergodic shift-invariant measure $\nu$ by Fact 5.

###  4.2. Equivalence relations and canonical factors

Related to the structure of the tree we will specify, for each $s\leq s(n)$,
an equivalence relation $\mathcal{Q}_{s}^{n}$ on our words $\mathcal{W}_{n}$.
We write $Q_{s}^{n}$ for the number of equivalence classes in
$\mathcal{Q}_{s}^{n}$ and enumerate the classes by
$\left\\{c_{j}^{(n,s)}:j=1,\dots,Q_{s}^{n}\right\\}$. In the construction of
the factor $\mathbb{K}_{s}$ described in 4.2.2, we will identify
$\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ with an alphabet denoted by
$\left(\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}\right)^{\ast}$ of $Q_{s}^{n}$
symbols $\left\\{1,\dots,Q_{s}^{n}\right\\}$.

Each equivalence relation $\mathcal{Q}_{s}^{n}$ will induce an equivalence
relation on $rev(\mathcal{W}_{n})$, which we will also call
$\mathcal{Q}_{s}^{n}$, as follows: $rev(w),rev(w^{\prime})\in
rev(\mathcal{W}_{n})$ are equivalent with respect to $\mathcal{Q}_{s}^{n}$ if
and only if $w,w^{\prime}\in\mathcal{W}_{n}$ are equivalent with respect to
$\mathcal{Q}_{s}^{n}$.

To state the specifications on our equivalence relations we recall some
general notions.

######  Definition 27.

Let $X$ be a set and let $\mathcal{Q}$ and $\mathcal{R}$ be equivalence
relations on $X$.

  * •

We write $\mathcal{R}\subseteq\mathcal{Q}$ and say that $\mathcal{R}$
_refines_ $\mathcal{Q}$ if considered as sets of ordered pairs we have
$\mathcal{R}\subseteq\mathcal{Q}$.

  * •

We define the _product equivalence relation_ $\mathcal{Q}^{n}$ on $X^{n}$ by
setting $x_{0}\dots x_{n-1}\sim x_{0}^{\prime}\dots x_{n-1}^{\prime}$ if and
only if $x_{i}\sim x_{i}^{\prime}$ for all $i=0,\dots,n-1$.

Our equivalence relations will satisfy the following specifications. Let
$\left(\epsilon_{n}\right)_{n\in\mathbb{N}}$ be a decreasing sequence of
positive numbers such that

(4.1) $\sum_{n\in\mathbb{N}}\epsilon_{n}<\infty.$

To start, we let $\mathcal{Q}_{0}^{0}$ be the equivalence relation on
$\mathcal{W}_{0}=\Sigma$ which has one equivalence class, that is, any two
elements of $\Sigma$ are equivalent.

  * (Q4)

Suppose that $n=M(s)$. There is a specific number
$J_{s(n),n}\in\mathbb{Z}^{+}$ such that each word in $w_{n}\in\mathcal{W}_{n}$
is a concatenation $w_{n}=w_{n,1}\dots w_{n,J}$ of $J=J_{s(n),n}$ strings of
equal length. Then any two words in the same $\mathcal{Q}_{s}^{n}$ class agree
with each other except possibly on initial or final strings of length at most
$\frac{\epsilon_{n}}{2}\frac{h_{n}}{J_{s(n),n}}$ on the segments $w_{n,i}$ for
$i=1,\dots,J_{s(n),n}$.

  * (Q5)

For $n\geq M(s)+1$ we can consider words in $\mathcal{W}_{n}$ as
concatenations of words from $\mathcal{W}_{M(s)}$ and define
$\mathcal{Q}_{s}^{n}$ as the product equivalence relation of
$\mathcal{Q}_{s}^{M(s)}$.

  * (Q6)

$\mathcal{Q}_{s+1}^{n}$ refines $\mathcal{Q}_{s}^{n}$ and each
$\mathcal{Q}_{s}^{n}$ class contains $2^{4e(n)}$ many $\mathcal{Q}_{s+1}^{n}$
classes.

######  Remark.

By (Q5) we can view $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ as sequences of
elements $\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}$ and similarly for
$rev(\mathcal{W}_{n})/\mathcal{Q}_{s}^{n}$. In particular, it follows that
$\mathcal{Q}_{0}^{n}$ is the equivalence relation on $\mathcal{W}_{n}$ which
has one equivalence class. Moreover, it allows us to regard elements in
$\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ for $n\geq M(s)+1$ as sequences of
symbols in the alphabet
$\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$.

######  Remark.

In case that the exponent is not relevant we will refer to the
$\mathcal{Q}_{s}^{n}$ as $\mathcal{Q}_{s}$. For $u\in\mathcal{W}_{n}$ we write
$[u]_{s}$ for its $\mathcal{Q}_{s}^{n}$ class.

As in [FRW11, section 5] these specifications are sufficient to describe a
canonical tower of factors. For this purpose, we consider the symbolic shift
$\mathbb{K}\subset\Sigma^{\mathbb{Z}}$ with measure $\nu$ corresponding to
$\Psi(\mathcal{T})$ for a fixed
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$.

####  4.2.1. The odometer factor

We start by describing an odometer factor of our transformation which will
turn out to be the Kronecker factor and will determine a natural “timing
mechanism” to detect blocks.

Suppose that $\sigma_{m}$ and $\sigma_{n}$ with $m<n$ are consecutive members
of $\mathcal{T}$ and let $x\in\mathbb{K}$. By unique readability there are
unique $w,w^{\prime}\in\mathcal{W}_{n}$ and
$k\in\left\\{0,\dots,h_{n}-1\right\\}$ such that
$x\upharpoonright[-k,-k+2h_{n}-1]=ww^{\prime}$. We call the interval of
integers $[-k,-k+h_{n}-1]$ the $n$-block of $x$ containing $0$.

If the $m$-block of $x$ containing $0$ is given by
$[-k^{\prime},-k^{\prime}+h_{m}-1]$, then there is a unique $\pi(x,n)$ such
that $k^{\prime}=-k+\pi(x,n)h_{m}$. We can view $\pi(x,n)$ as an element in
$\mathbb{Z}_{h_{n}/h_{m}}$ and we define

$\pi_{0}:\mathbb{K}\to\prod\left\\{\mathbb{Z}_{h_{n}/h_{m}}:\,\sigma_{m}\text{
and }\sigma_{n}\text{ are successive elements of }\mathcal{T}\right\\},$

by $\pi_{0}(x)=(\pi(x,n))_{\sigma_{n}\in\mathcal{T}}.$ Since
$\pi(sh(x),\cdot)$ is obtained from $\pi(x,\cdot)$ by adding
$\bar{1}=(1,0,0,\dots)$ in the odometer
$O_{\mathcal{T}}\coloneqq\prod\left\\{\mathbb{Z}_{h_{n}/h_{m}}:\,\sigma_{m}\text{
and }\sigma_{n}\text{ are successive elements of }\mathcal{T}\right\\}$, we
denote the corresponding odometer transformation by
$\mathcal{O}_{\mathcal{T}}$ and collect the following properties (see [FRW11,
Lemma 22]).

######  Lemma 28.

The map $\pi_{0}$ is a factor map from $\Psi(\mathcal{T})$ to
$\mathcal{O}_{\mathcal{T}}$. If $p>2$ is a prime number, then
$\mathrm{e}^{2\pi\mathrm{i}/p}$ is an eigenvalue of the unitary operator
associated with $\mathcal{O}_{\mathcal{T}}$ if and only if $p=p_{n}$ for some
$n$ with $\sigma_{n}\in\mathcal{T}$.

By the analogous procedure one associates the same odometer transformation
$\mathcal{O}_{\mathcal{T}}$ to $\mathbb{K}^{-1}$ and we let
$\pi_{0}^{\ast}:\mathbb{K}^{-1}\to\prod\mathbb{Z}_{h_{n}/h_{m}}$ be the
analogous map. We note that $\pi_{0}^{\ast}(rev(x))=i(\pi_{0}(x))$ for the
involution $i$ of $\mathcal{O}_{\mathcal{T}}$ given by $i(x)=-x$.

####  4.2.2. The canonical factors

Now we define a canonical sequence of invariant sub-$\sigma$-algebras of the
algebra $\mathcal{B}(\mathbb{K})$ of measurable subsets of $\mathbb{K}$.

We let $\mathbb{K}_{0}$ be the odometer factor $O_{\mathcal{T}}$ introduced
above. For each $s\geq 1$ a typical $x\in\mathbb{K}$ gives a bi-infinite
sequence of the classes
$\left\\{c_{j}^{(M(s),s)}:j=1,\dots,Q_{s}^{M(s)}\right\\}$ in
$\mathcal{Q}_{s}^{M(s)}$ which yields a shift-equivariant map from
$\mathbb{K}$ to $\left\\{1,\dots,Q_{s}^{M(s)}\right\\}^{\mathbb{Z}}$. To be
more precise, we define a map
$\tilde{\pi}_{s}:\mathbb{K}\to\left\\{1,\dots,Q_{s}^{M(s)}\right\\}=\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$
which assigns to a $x\in\mathbb{K}$ the letter $j$ if the word
$w\in\mathcal{W}_{M(s)}$ on the $M(s)$-block of $x$ containing the position
$0$ satisfies $[w]_{s}=c_{j}^{(M(s),s)}$. Hereby, we define a shift-
equivariant map
$\pi_{s}:\mathbb{K}\to\mathbb{K}_{s}\coloneqq\left\\{1,\dots,Q_{s}^{M(s)}\right\\}^{\mathbb{Z}}$
by letting
$\pi_{s}(x)=\left(\tilde{\pi}_{s}(sh^{k}(x))\right)_{k\in\mathbb{Z}}.$ There
is an analogous map from $rev(\mathbb{K})$ to $rev(\mathbb{K}_{s})$ that we
also denote by $\pi_{s}$.

Next, we describe a convenient base for the topology on $\mathbb{K}_{s}$: For
$n\geq M(s)$, $w\in\mathcal{W}_{n}$ and $0\leq k<h_{n}$, we let
$\left\langle[w]_{s},k\right\rangle$ be the collection of
$(x,y)\in\mathbb{K}_{s}$ such that the position $0$ is at the $k$-th place in
the $n$-block $B$ of $x$ containing $0$ and if
$v\in\left\\{1,\dots,Q_{s}^{M(s)}\right\\}^{h_{n}}$ is the word in $x$ at the
block $B$, then $v$ is the sequence of $\mathcal{Q}_{s}^{M(s)}$ classes given
by $[w]_{s}$. Then the collection of those
$\left\langle[w]_{s},k\right\rangle$ for $\sigma_{n}\in\mathcal{T}$,
$w\in\mathcal{W}_{n}$ and $0\leq k<h_{n}$ forms a basis for the topology of
$\mathbb{K}_{s}$ consisting of clopen sets. In particular, for $m=M(s)$ a word
$w\in\mathcal{W}_{m}$ gives a word of length $h_{m}$ in our alphabet
$\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$ that is the
repetition of the same letter. We denote the collection of these words by
$\left(\mathcal{W}_{m}\right)_{s}^{\ast}$. Then for $n>m=M(s)$ with
$\sigma_{n}\in\mathcal{T}$ each word in $\mathcal{W}_{n}$ is a concatenation
of $\frac{h_{n}}{h_{m}}$ words in $\mathcal{W}_{m}$ by specification (E2) and,
thus, determines a sequence of $\frac{h_{n}}{h_{m}}$ many elements of
$\left(\mathcal{W}_{m}\right)_{s}^{\ast}$. We let
$\left(\mathcal{W}_{n}\right)_{s}^{\ast}$ be the collection of words in the
alphabet $\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$
arising this way. Then the sequence
$\left((\mathcal{W}_{n})_{s}^{\ast}\right)_{n\geq M(s)}$ gives a well-defined
odometer-based construction sequence for $\mathbb{K}_{s}$ in the alphabet
$\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$.

We also define the measure $\nu_{s}\coloneqq\pi_{s}^{\ast}\nu$ on
$\mathbb{K}_{s}$. To be more explicit, with the aid of specifications (E2) and
(Q6) we see that
$\nu_{s}(\left\langle[w]_{s},k\right\rangle)=\frac{1}{h_{n}Q_{s}^{n}}$ for any
$w\in\mathcal{W}_{n}$ and $0\leq k<h_{n}$.

Finally, we let $\mathcal{H}_{0}$ be the shift-invariant sub-$\sigma$-algebra
of the $\mathcal{B}(\mathbb{K})$ generated by the collection of
$\pi_{0}^{-1}(B)$, where $B$ is a basic open set in $O_{\mathcal{T}}$, and we
let $\mathcal{H}_{s}$ be the shift-invariant sub-$\sigma$-algebra of the
$\mathcal{B}(\mathbb{K})$ generated by the collection of $\pi_{s}^{-1}(B)$,
where $B$ is a basic open set in $\mathbb{\mathbb{K}}_{s}$. Then
$\mathcal{H}_{s}$ is the sub-$\sigma$-algebra determined by the factor map
$\pi_{s}$.

Since the equivalence relation $\mathcal{Q}_{s+1}^{M(s+1)}$ refines
$\left(\mathcal{Q}_{s}^{M(s)}\right)^{h_{M(s+1)}/h_{M(s)}}$ by specifications
(E2) and (Q6), we have $\mathcal{H}_{s+1}\supseteq\mathcal{H}_{s}$ and a
continuous factor map $\pi_{s+1,s}:\mathbb{K}_{s+1}\to\mathbb{K}_{s}$. To
express this one explicitly, we note that a $\mathbb{Z}$-sequence of
$\mathcal{Q}_{s+1}^{M(s+1)}$ classes determines a sequence of
$\mathcal{Q}_{s}^{M(s)}$ classes, because a $\mathcal{Q}_{s+1}^{M(s+1)}$ class
is contained in a $\mathcal{Q}_{s}^{M(s+1)}$ class which is a
$h_{M(s+1)}/h_{M(s)}$-tuple of $\mathcal{Q}_{s}^{M(s)}$ classes. Analogously
we define a map from $rev(\mathbb{K}_{s+1})$ to $rev(\mathbb{K}_{s})$ that we
also denote by $\pi_{s+1,s}$.

In analogy with [FRW11, Proposition 23] we can prove the following statement
making use of specification (Q4).

######  Lemma 29.

$\mathcal{B}\left(\mathbb{K}\right)$ is the smallest invariant
$\sigma$-algebra that contains $\bigcup_{s}\mathcal{H}_{s}$.

###### Proof.

It suffices to show that for any $m\in\mathbb{N}$ and any
$u\in\mathcal{W}_{m}$ the basic open set $\left\langle
u\right\rangle\subseteq\mathbb{K}$ can be approximated arbitrarily well in
measure by elements of $\bigcup_{s}\mathcal{H}_{s}$. For this purpose, we fix
$\varepsilon>0$ and choose $n>m$ such that $n=M(s)$ for some $s\in\mathbb{N}$
and $\epsilon_{n}+2\frac{h_{m}J_{s(n),n}}{h_{n}}<\varepsilon$. Then we let
$G\subset\mathbb{K}$ be the collection of $x$ such that within the $n$-word
$w_{n}\in\mathcal{W}_{n}$ located at the $n$-block of $x$ containing the
position $0$, $x(0)$ is not among the first or last
$\left(\frac{\epsilon_{n}}{2}+\frac{h_{m}J_{s(n),n}}{h_{n}}\right)\frac{h_{n}}{J_{s(n),n}}=\frac{\epsilon_{n}}{2}\frac{h_{n}}{J_{s(n),n}}+h_{m}$
letters of one of the $J_{s(n),n}$ many segments $w_{n,i}$ in specification
(Q4), that is, $x(0)$ belongs to one of the center segments. By the ergodic
theorem and our assumption on $n$ the measure of $G$ is at least
$1-\varepsilon$.

Now let $x\in G\cap\left\langle u\right\rangle$ and let $w\in\mathcal{W}_{n}$
be located at the $n$-block $B=[-k,-k+h_{n})$ of $x$ containing $0$. If
$c_{j}^{(n,s)}$ is the $\mathcal{Q}_{s}^{M(s)}$ class of $w$, then

$sh^{-k}(x)\in\pi_{s}^{-1}\left(\left\langle
c_{j}^{(n,s)},0\right\rangle\right)\subseteq sh^{-k}\left(\left\langle
u\right\rangle\right)$

by specification (Q4). Hence, $G\cap\left\langle u\right\rangle$ is a union of
shifts of sets of the form $\pi_{s}^{-1}\left(\left\langle
c_{j}^{(n,s)},0\right\rangle\right)$ lying in $\mathcal{H}_{s}$. ∎

As in the proof above, for $n=M(s)$, the set $L_{n}$ of $x$ such that within
the $n$-word $w_{n}\in\mathcal{W}_{n}$ located at the $n$-block of $x$
containing the position $0$ we have that $x(0)$ is among the first or last
$\frac{\epsilon_{n}}{2}\frac{h_{n}}{J_{s(n),n}}$ letters of one of the
$J_{s(n),n}$ many segments $w_{n,i}$ in specification (Q4), has measure
$\epsilon_{n}$. Let $L$ be the collection of $x\in\mathbb{K}$ such that for
all large $s$, if $n=M(s)$ then $x$ does not belong to $L_{n}$, that is,
$x(0)$ is not among the first or last
$\frac{\epsilon_{n}}{2}\frac{h_{n}}{J_{s(n),n}}$ letters of one of the
$J_{s(n),n}$ many segments $w_{n,i}$ within the $n$-word
$w_{n}\in\mathcal{W}_{n}$ located at the $n$-block of $x$ containing the
position $0$. Then $L$ has measure one by equation (4.1) and the Borel-
Cantelli Lemma.

We collect the following properties as in Propositions 24 and 25 of [FRW11].

######  Lemma 30.

  1. (1)

For all $x\neq y$ belonging to $L$, there is an open set
$S\in\bigcup_{s}\mathcal{H}_{s}$ such that $x\in S$ and $y\notin S.$

  2. (2)

For all $s\geq 1$, $\mathcal{H}_{s}$ is a strict subalgebra of
$\mathcal{H}_{s+1}$. Moreover, if
$\left\\{\nu_{x}:x\in\mathbb{K}_{s}\right\\}$ is the disintegration of
$\nu_{s+1}$ over $\nu_{s}$, then for $\nu_{s}$-a.e. $x$ the measure $\nu_{x}$
is nonatomic.

###  4.3. Groups of involutions

To approximate conjugacies we will use groups associated to trees as in
[FRW11]. These groups will be direct sums of
$\mathbb{Z}_{2}=\mathbb{Z}/2\mathbb{Z}$ and are called _groups of
involutions_.

If $G$ is a group of involutions and $B=\left\\{r_{i}:i\in I\right\\}$ is a
distinguished basis (that is, a particular choice of basis for $G$ considered
as a vector space over $\mathbb{Z}_{2}$), then we call the elements $r_{i}\in
B$ _canonical generators_ and we have a well-defined notion of _parity_ for
elements in $G$: an element $g\in G$ is called _even_ if it can be written as
the sum of an even number of elements in $B$. Otherwise, it is called _odd_.
Parity is preserved under homomorphisms sending the canonical generators of
one group to the canonical generators of the other. Moreover, for an inverse
limit system of groups of involutions
$\left\\{G_{s}:s\in\mathbb{Z}^{+}\right\\}$ (where each group has a set of
canonical generators) with parity-preserving homomorphisms
$\rho_{t,s}:G_{t}\to G_{s}$ for $0<s<t$, the elements of the inverse limit
$\underleftarrow{\lim}G_{s}$ have a well-defined parity.

For a tree $\mathcal{T}\subset\mathbb{N}^{\mathbb{N}}$ we assign to each level
$s>0$ a group of involutions $G_{s}\left(\mathcal{T}\right)$ by taking a sum
of copies of $\mathbb{Z}_{2}$ indexed by the nodes of $\mathcal{T}$ at level
$s$. Let

$G_{s}(\mathcal{T})=\sum_{\tau\in\mathcal{T},\,lh(\tau)=s}\left(\mathbb{Z}_{2}\right)_{\tau}.$

Each node of $\mathcal{T}$ at level $s$ corresponds to an element of
$G_{s}(\mathcal{T})$ that is 1 in the copy of $\mathbb{Z}_{2}$ for that node
and $0$ in the other copies of $\mathbb{Z}_{2}$. We also define
$G_{0}(\mathcal{T})$ to be the trivial group. For levels $0<s<t$ of
$\mathcal{T}$ we have a canonical homomorphism
$\rho_{t,s}:G_{t}\left(\mathcal{T}\right)\to G_{s}\left(\mathcal{T}\right)$
that sends a generator $\tau$ of $G_{t}\left(\mathcal{T}\right)$ to the unique
generator $\sigma$ of $G_{s}\left(\mathcal{T}\right)$ that is an initial
segment of $\tau$. The map $\rho_{t,0}$ is the trivial homomorphism
$\rho_{t,0}:G_{t}(\mathcal{T})\to G_{0}(\mathcal{T})=\\{0\\}.$ We denote the
inverse limit of $\left\langle
G_{s}\left(\mathcal{T}\right),\rho_{t,s}:s<t\right\rangle$ by
$G_{\infty}\left(\mathcal{T}\right)$ and we let
$\rho_{s}:G_{\infty}\left(\mathcal{T}\right)\to G_{s}\left(\mathcal{T}\right)$
be the projection map.

Since there is a one-to-one correspondence between the infinite branches of
$\mathcal{T}$ and infinite sequences $\left(g_{s}\right)_{s\in\mathbb{Z}^{+}}$
of generators $g_{s}\in G_{s}\left(\mathcal{T}\right)$ with
$\rho_{t,s}\left(g_{t}\right)=g_{s}$ for $t>s>0$, we obtain the following
characterization.

######  Fact 31.

Let $\mathcal{T}\subset\mathbb{N}^{\mathbb{N}}$ be a tree. Then
$G_{\infty}\left(\mathcal{T}\right)$ has a nonidentity element of odd parity
if and only if $\mathcal{T}$ is ill-founded (that is, $\mathcal{T}$ has an
infinite branch).

In order to make the elements of $G_{\infty}\left(\mathcal{T}\right)$
correspond to conjugacies, we will build symmetries into our construction
using the following finite approximations to
$G_{\infty}\left(\mathcal{T}\right)$. We let
$G_{0}^{n}\left(\mathcal{T}\right)$ be the trivial group and for $s>0$ we let

$G_{s}^{n}\left(\mathcal{T}\right)=\sum\left(\mathbb{Z}_{2}\right)_{\tau}\text{
where the sum is taken over }\tau\in\mathcal{T}\cap\left\\{\sigma_{m}:m\leq
n\right\\},\,lh(\tau)=s.$

When $\mathcal{T}$ is clear from the context, we will frequently write
$G_{s}^{n}$. We also introduce the finite approximations
$\rho_{t,s}^{(n)}:G_{t}^{n}(\mathcal{T})\to G_{s}^{n}(\mathcal{T})$ to the
canonical homomorphisms.

During the course of construction we will consider group actions of
$G_{s}^{n}$ on our quotient spaces $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$.
Here, we will need to control systems of such group actions on the refining
equivalence relations. For that purpose, the following general definitions
will prove useful.

######  Definition 32.

Suppose

  * •

$\mathcal{Q}$ and $\mathcal{R}$ are equivalence relations on a set $X$ with
$\mathcal{R}$ refining $\mathcal{Q}$,

  * •

$G$ and $H$ are groups with $G$ acting on $X/\mathcal{Q}$ and $H$ acting on
$X/\mathcal{R}$,

  * •

$\rho:H\to G$ is a homomorphism.

Then we say that the $H$ action is _subordinate_ to the $G$ action if for all
$x\in X$, whenever $[x]_{\mathcal{R}}\subset[x]_{\mathcal{Q}}$ we have
$h[x]_{\mathcal{R}}\subset\rho(h)[x]_{\mathcal{Q}}$.

######  Definition 33.

If $G$ acts on $X$, then the canonical _diagonal action_ of $G$ on $X^{n}$ is
defined by

$g\left(x_{0}x_{1}\dots x_{n-1}\right)=gx_{0}\,gx_{1}\dots gx_{n-1}\ \text{
for any }g\in G.$

If $G$ is a group of involutions with a collection of canonical generators,
then we define the _skew diagonal action_ on $X^{n}$ by setting

$g\left(x_{0}x_{1}\dots x_{n-1}\right)=\begin{cases}gx_{0}\,gx_{1}\dots
gx_{n-1},&\text{ if $g\in G$ is of even parity,}\\\ gx_{n-1}\,gx_{n-2}\dots
gx_{0},&\text{ if $g\in G$ is of odd parity.}\end{cases}$

######  Remark.

Recalling the notion of a product equivalence relation from Definition 27 we
can identify $X^{n}/\mathcal{Q}^{n}$ with $\left(X/\mathcal{Q}\right)^{n}$ in
an obvious way. Then we can also extend an action of $G$ on $X/\mathcal{Q}$ to
the diagonal or skew diagonal actions on $\left(X/\mathcal{Q}\right)^{n}$ in a
straightforward way.

To extend our group actions we will use the following extension lemma from
[FRW11, Lemma 46].

######  Lemma 34.

Let $X$ be a set and $\mathcal{R}\subseteq\mathcal{Q}$ be equivalence
relations on $X$. Suppose that

  * •

$\rho:H\to G\times\mathbb{Z}_{2}$ is a homomorphism,

  * •

$G\times\mathbb{Z}_{2}$ acts on $X/\mathcal{Q}$,

  * •

$H$ acts on $X/\mathcal{R}$ by a free action subordinate to the
$G\times\mathbb{Z}_{2}$ action on $X/\mathcal{Q}$,

  * •

if $H_{1}=\left\\{h\in H:\rho(h)=(0,i),i\in\left\\{0,1\right\\}\right\\}$,
then every orbit of the $\mathbb{Z}_{2}$ factor of $G\times\mathbb{Z}_{2}$
contains an even number of $H_{1}$ orbits.

Then there is a free action of $H\times\mathbb{Z}_{2}$ on $X/\mathcal{R}$
subordinate to the $G\times\mathbb{Z}_{2}$ action via the map
$\rho^{\prime}(h,i)=\rho(h)+(0,i)$.

We now list specifications on the group actions.

  * (A7)

$G_{s}^{n}$ acts freely on $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ and the
$G_{s}^{n}$ action is subordinate to the $G_{s-1}^{n}$ action on
$\mathcal{W}_{n}/\mathcal{Q}_{s-1}^{n}$ via the canonical homomorphism
$\rho_{s,s-1}^{(n)}:G_{s}^{n}\to G_{s-1}^{n}$.

  * (A8)

Suppose $M(s)<n$, $\sigma_{m}$ and $\sigma_{n}$ are consecutive elements of
$\mathcal{T}$ and we view $G_{s}^{n}=G_{s}^{m}\oplus H$. Then the action of
$G_{s}^{m}$ on $\mathcal{W}_{m}/\mathcal{Q}_{s}^{m}$ is extended to an action
on $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ by the skew diagonal action.

######  Remark 35.

In particular, in the above situation with $M(s)<n$ and
$\sigma_{m},\sigma_{n}$ consecutive elements of $\mathcal{T}$ both
specifications together yield that $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ is
closed under the skew diagonal action by $G_{s}^{m}$. Clearly, this also holds
if we view each element in $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ as a sequence
in the alphabet
$\left(\mathcal{W}_{M(s)}/\mathcal{Q}_{s}^{M(s)}\right)^{\ast}$.

##  5\. Infinite branches give isomorphisms

As in [FRW11] the specifications on our transformations stated in the previous
section suffice to build an isomorphism between $\Psi(\mathcal{T})$ and
$\Psi(\mathcal{T})^{-1}$ in case that the tree $\mathcal{T}$ has an infinite
branch.

######  Lemma 36.

Let $s\in\mathbb{N}$ and $g\in G_{s}^{m}$ for some $m\in\mathbb{N}$. Suppose
that $g$ has odd parity. Then there is a shift-equivariant isomorphism
$\eta_{g}:\mathbb{K}_{s}\to rev(\mathbb{K}_{s})$ canonically associated to $g$
as in (5.1).

Moreover, if $s^{\prime}>s$ and $g^{\prime}\in G_{s^{\prime}}^{n}$ for some
$n\geq m$ with $\rho_{s^{\prime},s}(g^{\prime})=g$, then
$\pi_{s^{\prime},s}\circ\eta_{g^{\prime}}=\eta_{g}\circ\pi_{s^{\prime},s}$.

###### Proof.

We recall from Section 4.2 that
$\left((\mathcal{W}_{m})_{s}^{\ast}\right)_{m\geq M(s)}$ defines a
construction sequence for $\mathbb{K}_{s}$. Similarly,
$\left(rev\left((\mathcal{W}_{m})_{s}^{\ast}\right)\right)_{m\geq M(s)}$ is a
construction sequence for $rev(\mathbb{K}_{s})$. For $n>m$ there is
$K\in\mathbb{N}$ such that we can write any element
$[w]_{s}^{\ast}\in(\mathcal{W}_{n})_{s}^{\ast}$ as
$[w]_{s}^{\ast}=[w_{0}]_{s}^{\ast}[w_{1}]_{s}^{\ast}\dots[w_{K-1}]_{s}^{\ast}$
with $[w_{i}]_{s}^{\ast}\in(\mathcal{W}_{m})_{s}^{\ast}$ for $i=0,\dots,K-1$.
By specification (A8) the group action is given by the skew diagonal action
and, hence, we have

$g\left([w_{0}]_{s}^{\ast}[w_{1}]_{s}^{\ast}\dots[w_{K-1}]_{s}^{\ast}\right)=g[w_{K-1}]_{s}^{\ast}g[w_{K-2}]_{s}^{\ast}\dots
g[w_{0}]_{s}^{\ast}.$

As pointed out in Remark 35, $(\mathcal{W}_{n})_{s}^{\ast}$ is closed under
the skew diagonal action. Thus
$g[w_{K-1}]_{s}^{\ast}g[w_{K-2}]_{s}^{\ast}\dots
g[w_{0}]_{s}^{\ast}\in(\mathcal{W}_{n})_{s}^{\ast}$, which implies
$g[w_{0}]_{s}^{\ast}g[w_{1}]_{s}^{\ast}\dots g[w_{K-1}]_{s}^{\ast}\in
rev\left((\mathcal{W}_{n})_{s}^{\ast}\right)$. Hence the map

(5.1) $[w_{0}]_{s}^{\ast}[w_{1}]_{s}^{\ast}\dots[w_{K-1}]_{s}^{\ast}\mapsto
g[w_{0}]_{s}^{\ast}g[w_{1}]_{s}^{\ast}\dots g[w_{K-1}]_{s}^{\ast}$

is an invertible map from the construction sequence for $\mathbb{K}_{s}$ to
the construction sequence for $rev(\mathbb{K}_{s})$. It can also be
interpreted as a shift-equivariant map from cylinder sets in $\mathbb{K}_{s}$
to cylinder sets located in the same position in $rev(\mathbb{K}_{s})$. This
yields the isomorphism in the first assertion.

The second assertion follows from specification (A7), which says that the
action by $g^{\prime}$ is subordinate to the action by $g$ via the
homomorphism $\rho_{s^{\prime},s}$. ∎

######  Definition 37.

Let $s\in\mathbb{N}$ and $g\in G_{s}^{m}$ for some $m\in\mathbb{N}$. Suppose
that $g$ has odd parity. Then $g$ yields a shift-equivariant isomorphism
$\eta_{g}:\mathbb{K}_{s}\to rev(\mathbb{K}_{s})$ as in Lemma 36. For every
$n\geq m$ it also induces a map $\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}\to
rev(\mathcal{W}_{n})/\mathcal{Q}^{n}_{s}$ that we denote by $\eta_{g}$ as
well.

In the following we call a sequence of isomorphisms $\zeta_{s}$ between
$\mathbb{K}_{s}$ and $rev(\mathbb{K}_{s})$ _coherent_ if
$\pi_{s+1,s}\circ\zeta_{s+1}=\zeta_{s}\circ\pi_{s+1,s}$ for every
$s\in\mathbb{N}$.

######  Lemma 38.

Let $\left(\zeta_{s}\right)_{s\in\mathbb{N}}$ be a coherent sequence of
isomorphisms between $\mathbb{K}_{s}$ and $rev(\mathbb{K}_{s})$. Then there is
an isomorphism $\zeta:\mathbb{K}\to rev(\mathbb{K})$ such that
$\pi_{s}\circ\zeta=\zeta_{s}\circ\pi_{s}$ for every $s\in\mathbb{N}$.

###### Proof.

Since the isomorphisms $\zeta_{s}$ cohere, their inverse limit defines a
measure-preserving isomorphism between the subalgebra of
$\mathcal{B}\left(\mathbb{K}\right)$ generated by $\bigcup_{s}\mathcal{H}_{s}$
and the subalgebra of $\mathcal{B}\left(rev(\mathbb{K})\right)$ generated by
$\bigcup_{s}rev(\mathcal{H}_{s})$. By Lemma 29 this extends uniquely to a
measure-preserving isomorphism $\tilde{\zeta}$ between
$\mathcal{B}\left(\mathbb{K}\right)$ and
$\mathcal{B}\left(rev(\mathbb{K})\right)$. Then by part (1) of Lemma 30 we can
find sets $D\subset\mathbb{K}$, $D^{\prime}\subset rev(\mathbb{K})$ of measure
zero such that $\tilde{\zeta}$ determines a shift-equivariant isomorphism
$\zeta$ between $\mathbb{K}\setminus D$ and $rev(\mathbb{K})\setminus
D^{\prime}$. ∎

Now we are ready to prove the first half of Proposition 23.

###### Proof of part (1) in Proposition 23.

Suppose that $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ has an infinite
branch. Then $G_{\infty}(\mathcal{T})$ has an element $g$ of odd parity
according to Fact 31. By Lemma 36 we obtain a coherent sequence of
isomorphisms $\zeta_{s}\coloneqq\eta_{\rho_{s}(g)}$ between $\mathbb{K}_{s}$
and $rev(\mathbb{K}_{s})$. Hence, Lemma 38 yields an isomorphism between
$\mathbb{K}$ and $rev(\mathbb{K})$. Since $rev(\mathbb{K})$ is isomorphic to
$\mathbb{K}^{-1}$, we conclude that $\mathbb{K}\cong\mathbb{K}^{-1}$. ∎

##  6\. Feldman Patterns

In [Fe76] Feldman constructed the first example of an ergodic zero-entropy
automorphism that is not loosely Bernoulli. The construction is based on the
idea that no pair of the following strings

$\displaystyle abababab$ $\displaystyle aabbaabb$ $\displaystyle aaaabbbb$

can be matched very well. In our construction we will concatenate variants of
his blocks that we call _Feldman patterns_.

We start with an observation that follows along the lines of Lemma 6.5 and
Remark 6.6 in [GKpp], whose proofs were inspired by [Fe76, Theorem 4] and
[ORW82, Proposition 1.1, p.79].

######  Lemma 39.

Suppose $a_{1},a_{2},\dots,a_{N}$ are distinct symbols in an alphabet
$\Sigma.$ Let $M,S,T,j,k\in\mathbb{Z}^{+}$, $S\geq T$, $M\geq j>k$, and

$\displaystyle B_{k}=$ $\displaystyle\left(a_{1}^{TN^{2k}}a_{2}^{TN^{2k}}\dots
a_{N}^{TN^{2k}}\right)^{N^{2(M+1-k)}},$ $\displaystyle
B_{j}=\left(a_{1}^{SN^{2j}}a_{2}^{SN^{2j}}\dots
a_{N}^{SN^{2j}}\right)^{N^{2(M+1-j)}}.$

Suppose $B$ and $\overline{B}$ are strings of consecutive symbols in $B_{j}$
and $B_{k},$ respectively, where $|B|\geq SN^{2M+2}$. Assume that $N\geq 20$.
Then

$\overline{f}(B,\overline{B})>1-\frac{4}{\sqrt{N}}.$

###### Proof.

By removing fewer than $2SN^{2j}$ symbols from the beginning and end of $B,$
we can decompose the remaining part of $B$ into strings
$C_{1},C_{2},\dots,C_{r}$ each of the form $a_{i}^{SN^{2j}}.$ Since
$2SN^{2j}\leq 2\frac{|B|+|\overline{B}|}{N^{2}},$ it follows from Fact 9 that
removing these symbols increases the $\overline{f}$ distance between $B$ and
$\overline{B}$ by less than $\frac{4}{N^{2}}.$ Let
$\overline{C}_{1},\overline{C}_{2},\dots,\overline{C}_{r}$ be the
decomposition of $\overline{B}$ into substrings corresponding to
$C_{1},C_{2},\dots,C_{r}$ under a best possible match between
$C_{1}C_{2}\cdots C_{r}$ and $\overline{B}.$

Let $i\in\\{1,2,\dots,r\\}.$

  1. Case 1.

$|\overline{C}_{i}|<\frac{3}{2\sqrt{N}}|C_{i}|$. Then by Fact 11,
$\overline{f}(C_{i},\overline{C}_{i})>1-\frac{3}{\sqrt{N}}$.

  2. Case 2.

$|\overline{C}_{i}|\geq\frac{3}{2\sqrt{N}}|C_{i}|=\frac{3}{2}SN^{2j-(1/2)}$.
The length of a cycle $a_{1}^{TN^{2k}}a_{2}^{TN^{2k}}\cdots a_{N}^{TN^{2k}}$
in $B_{k}$ is at most $TN^{2j-1}.$ Therefore $\overline{C}_{i}$ contains at
least $\lfloor\frac{3\sqrt{N}}{2}\rfloor-1>\sqrt{N}$ complete cycles. Thus
deleting any partial cycles at the beginning and end of $\overline{C}_{i}$
would increase the $\overline{f}$ distance between $C_{i}$ and
$\overline{C}_{i}$ by less than $\frac{2}{\sqrt{N}}.$ On the rest of
$\overline{C}_{i}$, only $\frac{1}{N}$ of the symbols can match the symbol in
$C_{i}.$ Thus
$\overline{f}(C_{i},\overline{C}_{i})>1-\frac{2}{\sqrt{N}}-\frac{2}{N}>1-\frac{3}{\sqrt{N}}.$

Therefore, by Fact 10, $\overline{f}(C_{1}C_{2}\cdots
C_{r},\overline{C}_{1},\overline{C}_{2}\cdots,\overline{C}_{r})>1-\frac{3}{\sqrt{N}}.$
Hence
$\overline{f}(B,\overline{B})>1-\frac{3}{\sqrt{N}}-\frac{4}{N^{2}}>1-\frac{4}{\sqrt{N}}.$
∎

Let $T,N,M\in\mathbb{Z}^{+}$. A $(T,N,M)$-Feldman pattern in building blocks
$A_{1},\dots,A_{N}$ of equal length $L$ is one of the strings
$B_{1},\dots,B_{M}$ that are defined by

$\displaystyle B_{1}=$ $\displaystyle\left(A_{1}^{TN^{2}}A_{2}^{TN^{2}}\dots
A_{N}^{TN^{2}}\right)^{N^{2M}}$ $\displaystyle B_{2}=$
$\displaystyle\left(A_{1}^{TN^{4}}A_{2}^{TN^{4}}\dots
A_{N}^{TN^{4}}\right)^{N^{2M-2}}$ $\displaystyle\vdots$ $\displaystyle\vdots$
$\displaystyle B_{M}=$ $\displaystyle\left(A_{1}^{TN^{2M}}A_{2}^{TN^{2M}}\dots
A_{N}^{TN^{2M}}\right)^{N^{2}}$

Thus $N$ denotes the number of building blocks, $M$ is the number of
constructed patterns, and $TN^{2}$ gives the minimum number of consecutive
occurrences of a building block. We also note that each building block
$A_{i}$, $1\leq i\leq N$, occurs $TN^{2M+2}$ many times in each pattern. Every
block $B_{j}$, $1\leq j\leq M$, has total length $TN^{2M+3}L$. Moreover, we
notice that $B_{j}$ is built with $N^{2(M+1-j)}$ many so-called _cycles_ :
Each cycle winds through all the $N$ building blocks.

We conclude this analysis with a statement on the $\overline{f}$-distance
between different $(T,N,M)$-Feldman patterns.

######  Proposition 40 (Distance between different Feldman patterns in
$\overline{f}$).

Let $N\geq 20$, $M\geq 2$, and $B_{j}$, $1\leq j\leq M$, be the
$(T,N,M)$-Feldman patterns in the building blocks $A_{1},\dots,A_{N}$ of equal
length $L$. Assume that $\alpha\in\left(0,\frac{1}{7}\right)$, $R\geq 2$, and
$\overline{f}(C,D)>\alpha$, for all substrings $C$ and $D$ consisting of
consecutive symbols from $A_{i_{1}}$ and $A_{i_{2}}$, respectively, where
$i_{1}\neq i_{2}$, with $|C|,|D|\geq\frac{L}{R}$.

Then for all $j,k\in\left\\{1,\dots,M\right\\}$, $j\neq k$, and all sequences
$B$ and $\bar{B}$ of at least $TN^{2M+2}L$ consecutive symbols from $B_{j}$
and $B_{k}$, respectively, we have

(6.1)
$\overline{f}\left(B,\bar{B}\right)\geq\alpha-\frac{4}{\sqrt{N}}-\frac{1}{R}.$

###### Proof.

Using Lemma 13 the statement follows from Lemma 39 with $S=T$. ∎

In our iterative construction process, that we present in Sections 7 and 8, we
substitute Feldman patterns of finer equivalence classes of words into Feldman
patterns of coarser classes. In Section 9 we need estimates on the
$\overline{f}$ distance between such different Feldman patterns of equivalence
classes even under finite coding. Since we do not know the precise words being
coded but just their equivalence classes, the following Coding Lemma will
prove useful, especially in Lemma 62 and Lemma 71.

######  Remark.

The Coding Lemma below can be applied in the case $A=B_{k}$ and $B=B_{j}$,
where $B_{k}$ and $B_{j}$ are as in Lemma 39, with $k\neq j,$ except in the
definition of $B_{j}$, the $a_{i}$’s are replaced by $b_{i}$’s, and we assume
$T=S.$ In case $j>k,$ each $\Lambda_{im}$ in the Coding Lemma is equal to
$N^{2(j-k)-1}$ cycles in $B_{k},$ and the permutations are the identity, while
$\Upsilon_{im}=b_{m}^{TN^{2j}}.$ If $k>j,$ each substring
$\Lambda_{i1}\Lambda_{i2}\cdots\Lambda_{iN}$ of $B_{k}$ actually consists of
repetitions of a single symbol, and we again take
$\Upsilon_{im}=b_{m}^{TN^{2j}}.$ The permutations in the Coding Lemma allow
for the more general situation that occurs in Lemma 45 and Remark 51.

######  Lemma 41 (Coding Lemma).

Let $B_{mj}^{(i)}$, $1\leq i\leq z,$$1\leq m\leq N,1\leq j\leq q,$ and
$A_{ij}$, $1\leq i\leq z$,$1\leq j\leq q$, be blocks of symbols, with each
block of length $L.$ Assume $q\geq N>2^{16}.$ Suppose $R_{1}\geq 2,$
$\alpha\in(0,1/7),$ and for all substrings $C$ and $D$ consisting of
consecutive symbols in $B_{mj}^{(i)}$ and
$B_{m^{\prime}j^{\prime}}^{(i^{\prime})},$ respectively, with $|C|,|D|\geq
L/R_{1},$ we have $\overline{f}(C,D)\geq\alpha$ if $m\neq m^{\prime}.$ For
$1\leq i\leq z$, $1\leq m\leq N,$ let $\Lambda_{im}$ be a permutation of the
strings $A_{i1},A_{i2},\cdots,A_{iq},$ and let
$\Upsilon_{im}=B_{m1}^{(i)}B_{m2}^{(i)}\cdots B_{mq}^{(i)}.$ Let

$A=\Lambda_{11}\Lambda_{12}\dots\Lambda_{1N}\Lambda_{21}\Lambda_{22}\cdots\Lambda_{2N}\cdots\Lambda_{z1}\Lambda_{z2}\cdots\Lambda_{zN}$

and

$B=\Upsilon_{11}\Upsilon_{12}\cdots\Upsilon_{1N}\Upsilon_{21}\Upsilon_{22}\cdots\Upsilon_{2N}\cdots\Upsilon_{z1}\Upsilon_{z2}\cdots\Upsilon_{zN}.$

Suppose $R_{2}\geq 2$ and $\overline{A}$,$\overline{B}$ are strings of
consecutive symbols in $A$,B, respectively, each of length at least
$zqNL/R_{2}.$ Then

$\overline{f}(\overline{A},\overline{B})\geq\alpha\left[\frac{1}{8}-\frac{2}{\sqrt[4]{N}}\right]-\frac{1}{R_{1}}-\frac{4R_{2}}{z}.$

###### Proof.

We begin by considering, instead of strings of symbols $B_{mj}^{(\ell)}$ and
$A_{ij},$ individual symbols, $b_{mj}^{(\ell)},\text{1$\leq\ell\leq
z^{\prime\prime},$ }1\leq m\leq N,\text{1$\leq j\leq q,$}$ such that
$b_{mj}^{(\ell)}\neq b_{m^{\prime}j^{\prime}}^{(\ell^{\prime})}$ for $m\neq
m^{\prime},$ and $a_{ij},$ $1\leq i\leq z^{\prime},$ $1\leq j\leq q.$ Let
$\mathcal{A}_{ij}$ be a permutation of $a_{i1},a_{i2},\dots a_{iq}$ and let
$\mathcal{B}_{m}^{(\ell)}=b_{m1}^{(\ell)}b_{m2}^{(\ell)}\cdots
b_{mq}^{(\ell)}$ for some $1\leq\ell\leq z^{\prime\prime}.$ Let
$R_{3}=\sqrt[4]{N}$ and $R_{4}=\sqrt{N}.$ If a substring
$\overline{\mathcal{A}}_{i,j}$ of $\mathcal{A}_{i,j}$ of length at least
$q/R_{3}$ and a substring $\overline{\mathcal{B}}_{m}^{(\ell)}$ of
$\mathcal{B}_{m}^{(\ell)}$ satisfy
$\overline{f}(\overline{\mathcal{A}}_{i,j},\overline{\mathcal{B}}_{m}^{(\ell)})\leq
1/8,$ then at least 7/9 of the symbols in $\overline{\mathcal{A}}_{ij}$ are
equal to a symbol in
$\\{b_{m1}^{(\ell)},b_{m2}^{(\ell)},\dots,b_{mq}^{(\ell)}\\}.$ Then at least
$7q/(9R_{3})$ symbols among $a_{i1},a_{i2},\dots a_{iq}$ are elements of
$\\{b_{m1}^{(\ell)},b_{m2}^{(\ell)},\dots,b_{mq}^{(\ell)}\\}.$ This can happen
for at most $9R_{3}/7$ values of $m.$ For the other values of $m,$ and all
values of $j$ and $\ell,$
$\overline{f}(\overline{\mathcal{A}}_{ij},\overline{\mathcal{B}}_{m}^{(\ell)})>1/8.$
Now suppose $\mathcal{A}_{i}$ and $\mathcal{B}^{(\ell)}$ are substrings
consisting of consecutive symbols in
$\mathcal{A}_{i1}\mathcal{A}_{i2}\cdots\mathcal{A}_{iN},$ and
$\mathcal{B}_{1}^{(\ell)}\mathcal{B}_{2}^{(\ell)}\cdots\mathcal{B}_{N}^{(\ell)},$
respectively, both of length at least $qN/R_{4}.$ Then there are at least
$(N/R_{4})-2$ complete $\mathcal{A}_{ij}$’s in $\mathcal{A}_{i}$ and at least
$(N/R_{4})-2$ complete $\mathcal{B}_{m}^{(\ell)}$’s in $\mathcal{B}.$ By Fact
9, if we remove the incomplete strings at the beginning and end of
$\mathcal{A}_{i}$ and $\mathcal{B}^{(\ell)}$ we increase the $\overline{f}$
distance by at most $4R_{4}/N.$ We apply Lemma 13 with $\alpha=1/8$ to the
resulting complete strings and then compensate by subtracting $4R_{4}/N.$ Thus

$\overline{f}(\mathcal{A}_{i},\mathcal{B}^{(\ell)})>\frac{1}{8}\left(1-\frac{9R_{3}/7}{(N/R_{4})-2}\right)-\frac{1}{R_{3}}-\frac{4R_{4}}{N}>\frac{1}{8}-\frac{7/6}{\sqrt[4]{N}}-\frac{4}{\sqrt{N}}=:\beta.$

Therefore by Lemma 13,

(6.2)
$\overline{f}(\mathcal{A}_{1}\mathcal{A}_{2}\cdots\mathcal{A}_{z^{\prime}},\mathcal{B}^{(1)}\mathcal{B}^{(2)}\cdots\mathcal{B}^{(z^{\prime\prime})})>\beta-\frac{1}{R_{4}}.$

Suppose $\overline{A}$ and $\overline{B}$ are as in the statement of the
lemma. We will apply Lemma 13 again, now regarding
$\mathcal{A}_{1}\mathcal{A}_{2}\cdots\mathcal{A}_{z^{\prime}}$ and
$\mathcal{B}^{(1)}\mathcal{B}^{(2)}\cdots\mathcal{B}^{(z^{\prime\prime})}$ as
indices on the blocks in $\overline{A}$ and $\overline{B}.$ By removing any
incomplete sequence of blocks at the beginning and end of $\overline{A}$ and
$\overline{B},$ we may assume that $\overline{A}$ consists of complete
sequences $\Lambda_{i1}\Lambda_{i2}\cdots\Lambda_{iN}$ and $\overline{B}$
consists of complete sequences $\Upsilon_{\ell 1}\Upsilon_{\ell
2}\cdots\Upsilon_{\ell N},$ thereby possibly increasing the $\overline{f}$
distance by at most $4R_{2}/z.$ By Lemma 13 and (6.2),
$\overline{f}(\overline{A},\overline{B})>\alpha(\beta-\frac{1}{\sqrt{N}})-\frac{1}{R_{1}}-\frac{4R_{2}}{z}>\alpha(\frac{1}{8}-\frac{2}{\sqrt[4]{N}})-\frac{1}{R_{1}}-\frac{4R_{2}}{z}.$
∎

##  7\. A General Substitution Step

In this section we describe a step in our iteration of substitutions in a very
general framework. The substitution will have the following initial data:

  * •

An alphabet $\Sigma$ and a collection of words $X\subset\Sigma^{\mathfrak{h}}$

  * •

Equivalence relations $\mathcal{P}$ and $\mathcal{R}$ on $X$ with
$\mathcal{R}$ refining $\mathcal{P}$

  * •

Groups of involutions $G$ and $H$ with distinguished generators

  * •

A homomorphism $\rho:H\to G$ that preserves the distinguished generators. We
denote the range of $\rho$ by $G^{\prime}$ and its kernel by $H_{0}$ with
cardinality $|H_{0}|=2^{t}$ for some $t\in\mathbb{N}$.

  * •

A free $G$ action on $X/\mathcal{P}$ and a free $H$ action on $X/\mathcal{R}$
such that the $H$ action is subordinate to the $G$ action via $\rho$. In
particular, for each $k\in\mathbb{Z}^{+}$ the skew diagonal actions of $G$ on
$\left(X/\mathcal{P}\right)^{k}$ and $H$ on $\left(X/\mathcal{R}\right)^{k}$
are defined.

  * •

There are $N$ different equivalence classes in $X/\mathcal{P}$ denoted by
$[A_{i}]_{\mathcal{P}}$, $i=1,\dots,N$, where $N=2^{\nu+N^{\prime}}$ with
$N^{\prime},\nu\in\mathbb{N}$.

  * •

Each equivalence class $[A_{i}]_{\mathcal{P}}$ contains $2^{4e}$ elements of
$X/\mathcal{R}$, where $e\in\mathbb{Z}^{+}$ with $e\geq\max(2,t)$. We
subdivide these $\mathcal{R}$ classes into tuples as follows. Pick an
arbitrary class $[A_{1}]_{\mathcal{P}}$ and take a set
$\left\\{\left[A_{1,1}\right]_{\mathcal{R}},\dots,\left[A_{1,2^{4e-t}}\right]_{\mathcal{R}}\right\\}$
of $\mathcal{R}$ classes in $[A_{1}]_{\mathcal{P}}$ that intersects each orbit
of the $H_{0}$ action exactly once. This yields the first tuple
$\left(\left[A_{1,1}\right]_{\mathcal{R}},\dots,\left[A_{1,2^{4e-t}}\right]_{\mathcal{R}}\right)$.
Then we obtain $2^{t}-1$ further tuples as the images
$\left(h\left[A_{1,1}\right]_{\mathcal{R}},\dots,h\left[A_{1,2^{4e-t}}\right]_{\mathcal{R}}\right)$
for each $h\in H_{0}\setminus\left\\{\text{id}\right\\}$. Hereby, we have
divided the $2^{4e}$ elements of $X/\mathcal{R}$ in $[A_{1}]_{\mathcal{P}}$
into $2^{t}$ many tuples such that each tuple intersects each orbit of the
$H_{0}$ action exactly once and the tuples are images of each other under the
action by $H_{0}$. In the next step, we choose one element $h\in H$ in each of
the $H/H_{0}$ cosets and apply each such $h$ to the tuples in
$[A_{1}]_{\mathcal{P}}$ to obtain tuples in $\rho(h)[A_{1}]_{\mathcal{P}}$. If
there are any $[A_{j}]_{\mathcal{P}}$’s that are not in the $G^{\prime}$ orbit
of $[A_{1}]_{\mathcal{P}}$, then we repeat the procedure for such a
$[A_{j}]_{\mathcal{P}}$, etc. Our procedure guarantees that the choices of
elements in the $H_{0}$ orbits are consistent between different
$[A_{i}]_{\mathcal{P}}$ equivalence classes, so that the action of $H$ sends
tuples to tuples. Let the $2^{t}$ tuples in $\left[A_{i}\right]_{\mathcal{P}}$
be written as

$\left(\left[A_{i,u2^{4e-t}+1}\right]_{\mathcal{R}},\dots,\left[A_{i,(u+1)2^{4e-t}}\right]_{\mathcal{R}}\right),$

where $u\in\\{0,\dots,2^{t}-1\\}.$

  * •

For some $R\geq 2$ and some $\alpha\in\left(0,\frac{1}{8}\right)$ we have

(7.1) $\overline{f}(A,\bar{A})\geq\alpha$

for any substantial substrings $A$ and $\bar{A}$ of at least
$\frac{\mathfrak{h}}{R}$ consecutive symbols in any representatives of two
different $\mathcal{P}$-equivalence classes, that is, representatives of
$\left[A_{i_{1},j_{1}}\right]_{\mathcal{R}}$ and
$\left[A_{i_{2},j_{2}}\right]_{\mathcal{R}}$ for $i_{1}\neq i_{2}$ and any
$j_{1},j_{2}\in\left\\{1,\dots,2^{4e}\right\\}$.

  * •

For some $\beta\in(0,\alpha]$ we have

(7.2) $\overline{f}(A,\bar{A})\geq\beta$

for any substantial substrings $A$ and $\bar{A}$ of at least
$\frac{\mathfrak{h}}{R}$ consecutive symbols in any representatives of two
different $\mathcal{R}$-equivalence classes, that is, representatives of
$\left[A_{i,j_{1}}\right]_{\mathcal{R}}$ and
$\left[A_{i,j_{2}}\right]_{\mathcal{R}}$, respectively, for $j_{1}\neq j_{2}$.

Let $K,T_{2}\in\mathbb{Z}^{+}$ and $\tilde{R}\geq 2$ be given. The number
$\tilde{R}$ will be used in Proposition 43 to quantify substantial $\tilde{R}$
substrings of newly constructed concatenations. Then in Section 8 we specify
the size of $\tilde{R}$ needed for the application of Proposition 43. We also
suppose that there are numbers $M_{1},P,U_{1}\in\mathbb{Z}^{+}$, where
$\nu\cdot(2M_{1}+3)\geq\nu+N^{\prime}$ and $U_{1}$ is a multiple of $2^{t}$
such that

(7.3) $U_{1}\geq 2\tilde{R}^{2}.$

Finally, let $M_{2}\in\mathbb{Z}^{+}$ with

(7.4) $M_{2}\geq K\cdot P\cdot U_{1}\cdot 2^{\nu\cdot(2M_{1}+3)}.$

Hereby, we define the numbers

(7.5) $T_{1}\coloneqq T_{2}\cdot 2^{(4e-t)\cdot(2M_{2}+3)},$ (7.6)
$U_{2}\coloneqq U_{1}\cdot 2^{\nu\cdot(2M_{1}+3)},$

and

(7.7) $k=U_{1}\cdot T_{1}\cdot 2^{\nu\cdot(2M_{1}+3)}.$

Note that $k$ is a multiple of $N$ by our assumption
$\nu\cdot(2M_{1}+3)\geq\nu+N^{\prime}$.

Suppose we have a collection $\Omega\subset\left(X/\mathcal{P}\right)^{k}$ of
cardinality $|\Omega|=P$ that satisfies the following properties:

  * •

$\Omega$ is closed under the skew diagonal action of $G$,

  * •

each $\omega\in\Omega$ is a different concatenation of $U_{1}$ many different
$\left(T_{1},2^{\nu},M_{1}\right)$-Feldman patterns as described in Section 6,
each of which is constructed out of a tuple consisting of $2^{\nu}$ many
$[A_{i}]_{\mathcal{P}}$,

  * •

each $[A_{i}]_{\mathcal{P}}\in X/\mathcal{P}$ occurs exactly $\frac{k}{N}$
times in each $\omega\in\Omega$.

Then we construct a collection $S\subset\left(X/\mathcal{R}\right)^{k}$ of
substitution instances of $\Omega$ as follows.

  1. (1)

We start by choosing a set $\Upsilon\subset\Omega$ that intersects each orbit
of the action by the group $G^{\prime}$ exactly once.

  2. (2)

We construct a collection of $M_{2}$ many different
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns, where the tuple of
building blocks is to be determined in step (6). Note that each such pattern
is constructed as a concatenation of $T_{2}2^{(4e-t)\cdot(2M_{2}+3)}$ many
building blocks in total which motivates the definition of the number $T_{1}$
from above.

  3. (3)

By assumption on $\Omega$ we can subdivide each element $r\in\Upsilon$ as a
concatenation of $U_{1}2^{\nu\cdot(2M_{1}+3)}=U_{2}$ strings of the form
$[A_{i}]_{\mathcal{P}}^{T_{1}}$ and each $i\in\left\\{1,\dots,N\right\\}$
occurs exactly $V\coloneqq\frac{1}{N}U_{2}$ many times in this decomposition.

  4. (4)

For each $r\in\Upsilon$ we choose $K$ different sequences of $U_{2}$
concatenations of different $\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman
patterns in ascending order from our collection in the second step and
enumerate the sequences by $j\in\left\\{1,\dots,K\right\\}$. We require that
each of the constructed patterns appears at most once, that is, we needed to
construct at least $|\Upsilon|\cdot K\cdot U_{2}$ many different patterns in
that step. This explains the condition on the number $M_{2}$ in equation
(7.4).

  5. (5)

We define a sequence $\psi=\left(\psi_{1},\dots,\psi_{V}\right)$ with
$V=\frac{1}{N}U_{1}2^{\nu\cdot(2M_{1}+3)}$, by
$\psi_{v}=u\in\\{0,\dots,2^{t}-1\\}$, where $u\equiv v\>\mod\>2^{t}.$ That is,
the sequence $\psi$ cycles through the symbols in
$\left\\{0,\dots,2^{t}-1\right\\}.$ Since $U_{1}$ was chosen as a multiple of
$2^{t}$ and $\frac{1}{N}2^{\nu\cdot(2M_{1}+3)}\in\mathbb{Z}$ by the assumption
$\nu\cdot(2M_{1}+3)\geq\nu+N^{\prime}$ , each symbol from
$\left\\{0,\dots,2^{t}-1\right\\}$ occurs the same number $\frac{V}{2^{t}}$ of
times in the sequence $\psi$.

  6. (6)

Let $r\in\Upsilon$ and $j\in\left\\{1,\dots,K\right\\}$, and write

$r=\left[A_{i(1)}\right]_{\mathcal{P}}^{T_{1}}\cdots\left[A_{i(\ell)}\right]_{\mathcal{P}}^{T_{1}}\cdots\left[A_{i(U_{2})}\right]_{\mathcal{P}}^{T_{1}},$

where $i(1),\dots,i(U_{2})\in\\{1,\dots,N\\}.$ If $i(\ell)=i_{0}$ and this is
the $m$th occurrence of $i_{0}$ in the sequence $i(1),\dots,i(\ell)$ then we
let $u=\psi_{m}$ and substitute a Feldman pattern built with the tuple

$\left(\left[A_{i_{0},u2^{4e-t}+1}\right]_{\mathcal{R}},\dots,\left[A_{i_{0},(u+1)2^{4e-t}}\right]_{\mathcal{R}}\right)$

into $\left[A_{i_{0}}\right]_{\mathcal{P}}^{T_{1}}.$ The Feldman pattern that
is used is the $\ell$th pattern among the $U_{2}$ patterns previously chosen
for the given $r$ and $j$. We follow this procedure for each
$\ell=1,\dots,U_{2}$ to obtain an element $s\in(X/R)^{k}$. Let $S$ be the
collection of such $s\in(X/R)^{k}$ obtained for all $r\in\Upsilon$ and
$j\in\\{1,\dots,K\\}.$

Using this collection $S\subset\left(X/\mathcal{R}\right)^{k}$ we define

$\Omega^{\prime}=HS.$

Figure 7.1. Visualization of the substitution step.

######  Proposition 42.

This collection $\Omega^{\prime}\subset\left(X/\mathcal{R}\right)^{k}$
satisfies the following properties.

  1. (1)

$\Omega^{\prime}$ is closed under the skew diagonal action by $H$.

  2. (2)

For each element in $\omega\in\Omega$ there are $K\cdot|H_{0}|$ many
substitution instances in $\Omega^{\prime}$.

  3. (3)

Each element of $\Omega^{\prime}$ contains each
$\left[A_{i,j}\right]_{\mathcal{R}}$ the same number of times.

###### Proof.

The first statement follows from the definition of $\Omega^{\prime}$
immediately. For part (2) we recall that $\Upsilon\subset\Omega$ was chosen to
intersect each orbit of the action by the group $G^{\prime}$ exactly once and
that for each element in $\Upsilon$ there are $K$ many substitution instances
in $S$. To see the third part we use that all the $[A_{i}]_{\mathcal{P}}\in
X/\mathcal{P}$ occurred uniformly in each $\omega\in\Omega$. By construction
of the sequence $\psi$ in step (5) each tuple
$\left(\left[A_{i,a+1}\right]_{\mathcal{R}},\dots,\left[A_{i,a+2^{4e-t}}\right]_{\mathcal{R}}\right)$
occurs the same number of times as building blocks for
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns substituted into strings
$[A_{i}]_{\mathcal{P}}^{T_{1}}$. Since Feldman patterns are uniform in their
building blocks, we conclude the third statement. ∎

In the following, we estimate the $\overline{f}$ distance of elements in
$\Omega^{\prime}$ that are equivalent with respect to the $\mathcal{P}$
product equivalence relation but are not $\mathcal{R}$-equivalent. We conclude
that they are still approximately $\beta$ apart from each other in
$\overline{f}$, where $\beta$ is as in (7.2). The $\overline{f}$ distance for
strings of symbols in $\Sigma_{\mathcal{R}}$ will be denoted
$\overline{f}_{\Sigma_{\mathcal{R}}}$. When there is no subscript on the
$\overline{f}$, it is understood that the alphabet is $\Sigma$.

######  Proposition 43.

Let $\omega_{1}^{\prime}$ and $\omega_{2}^{\prime}$ be two different
substitution instances in $\Omega^{\prime}$ of an element $\omega\in\Omega$.
We consider
$\omega_{1}^{\prime},\omega_{2}^{\prime}\in\Omega^{\prime}\subset\left(X/\mathcal{R}\right)^{k}$
as strings of length $k$ in the alphabet
$\Sigma_{\mathcal{R}}\coloneqq\left\\{\left[A_{i,j}\right]_{\mathcal{R}}:1\leq
i\leq N,\,1\leq j\leq 2^{4e}\right\\}$. Then we have

(7.8)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(W^{\prime},\overline{W}^{\prime}\right)>1-\frac{4}{2^{e}}-\frac{1}{\tilde{R}}$

for any substrings $W^{\prime}$ and $\overline{W}^{\prime}$ of at least
$k/\tilde{R}$ consecutive $\Sigma_{\mathcal{R}}$-symbols from
$\omega_{1}^{\prime}$ and $\omega_{2}^{\prime}$, respectively.

Moreover, we have

(7.9)
$\overline{f}\left(V,\overline{V}\right)>\beta-\frac{1}{R}-\frac{4}{2^{e}}-\frac{1}{\tilde{R}}$

for any substrings $V$, $\overline{V}$ of at least $k\mathfrak{h}/\tilde{R}$
consecutive symbols in any representatives $W_{1}$ and $W_{2}$ of
$\omega_{1}^{\prime}$ and $\omega_{2}^{\prime}$, respectively, in the alphabet
$\Sigma$.

###### Proof.

Let $W^{\prime}$ and $\overline{W}^{\prime}$ be any substrings of at least
$k/\tilde{R}$ consecutive $\Sigma_{\mathcal{R}}$-symbols from
$\omega_{1}^{\prime}$ and $\omega_{2}^{\prime}$, respectively. We subdivide
both strings into sequences coming from the
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns and we recall that their
length is $T_{2}2^{(4e-t)\cdot(2M_{2}+3)}=T_{1}$. By adding fewer than
$2T_{1}$ many $\Sigma_{\mathcal{R}}$-symbols to each of $W^{\prime}$ and
$\overline{W}^{\prime}$ we can complete partial patterns at the beginning and
end. Let $W_{aug}^{\prime}$ and $\overline{W}_{aug}^{\prime}$ be the augmented
$W^{\prime}$ and $\overline{W}^{\prime}$ strings obtained in this way. By Fact
9 and condition (7.3) we have

(7.10)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(W^{\prime},\overline{W}^{\prime}\right)>\overline{f}_{\Sigma_{\mathcal{R}}}\left(W_{aug}^{\prime},\overline{W}_{aug}^{\prime}\right)-\frac{2\tilde{R}}{U_{1}2^{v\cdot\left(2M_{1}+3\right)}}>\overline{f}_{\Sigma_{\mathcal{R}}}\left(W_{aug}^{\prime},\overline{W}_{aug}^{\prime}\right)-\frac{1}{\tilde{R}}.$

We write $W_{aug}^{\prime}$ and $\overline{W}_{aug}^{\prime}$ as

$\displaystyle W_{aug}^{\prime}=P_{1}^{(p_{1},a_{1},k_{1})}\dots
P_{s}^{(p_{s},a_{s},k_{s})},\;\;$
$\displaystyle\overline{W}_{aug}^{\prime}=\overline{P}_{1}^{(q_{1},b_{1},l_{1})}\dots\overline{P}_{t}^{(q_{t},b_{t},l_{t})},$

where $P_{i}^{(p_{i},a_{i},k_{i})}$, $1\leq i\leq s$, as well as
$\overline{P}_{j}^{(q_{j},b_{j},l_{j})}$, $1\leq j\leq t$, are complete
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns in the
$\Sigma_{\mathcal{R}}$-alphabet and the superscripts
$p_{i},q_{j}\in\left\\{1,\dots,M_{2}\right\\}$ indicate which pattern
structure is used. Moreover, the other superscripts identify the building
blocks. Here, $a_{i},b_{j}\in\left\\{1,\dots,N\right\\}$ refer to the
$\mathcal{P}$-equivalence class of the building blocks and
$k_{i},l_{j}\in\left\\{1,\dots,2^{4e-t}\right\\}$ refer to the tuple of
$\mathcal{R}$-equivalence classes of building blocks. If we apply Lemma 39
with $S=T=T_{2}$ and $N$ replaced by $2^{4e-t}$, we obtain

(7.11)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(P,\overline{P}\right)\begin{cases}=1,&\text{if
}\left(a_{i},k_{i}\right)\neq\left(b_{j},l_{j}\right)\\\
>1-\frac{4}{2^{2e-0.5t}},&\text{if
}\left(a_{i},k_{i}\right)=\left(b_{j},l_{j}\right)\text{ and }p_{i}\neq
q_{j}\end{cases}$

for any sequences $P$ and $\overline{P}$ of at least
$\frac{T_{1}}{2^{4e-t}}=T_{2}2^{(4e-t)\cdot(2M_{2}+2)}$ consecutive
$\Sigma_{\mathcal{R}}$-symbols in $P_{i}^{(p_{i},a_{i},k_{i})}$ and
$\overline{P}_{j}^{(q_{j},b_{j},l_{j})}$, respectively.

We examine the two possible cases: $\omega_{1}^{\prime}$ and
$\omega_{2}^{\prime}$ have disjoint $H$ orbits (case 1) or
$\omega_{1}^{\prime}=h\omega_{2}^{\prime}$ for some $h\in H_{0}$ (case 2).
From the construction we recall that in the first case all occurring
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns in $\omega_{1}^{\prime}$
and $\omega_{2}^{\prime}$ are different from each other. To investigate the
second case we recall that a tuple of building blocks is mapped to a different
tuple under the action of an element $h\in H_{0}$. Hence, identical Feldman
patterns in $\omega_{1}^{\prime}=h\omega_{2}^{\prime}$ and
$\omega_{2}^{\prime}$ have different tuples of building blocks.

In both cases we consider a best possible $\overline{f}$ match between
$W_{aug}^{\prime}$ and $\overline{W}_{aug}^{\prime}$. To simplify notation we
ignore the superscripts of the occurring
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns. We denote the string in
$\overline{W}_{aug}^{\prime}$ matched with $P_{i}$ by $\tilde{P}_{i}$. If
$|\tilde{P}_{i}|<\frac{T_{1}}{2^{e}}$ or $|\tilde{P}_{i}|>2^{e}T_{1}$, then

(7.12)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(P_{i},\tilde{P}_{i}\right)>1-\frac{2}{2^{e}}.$

Otherwise, we subdivide $\tilde{P}_{i}$ into the strings coming from the
Feldman patterns in $\overline{W}_{aug}^{\prime}$ and we denote the part of
$\tilde{P}_{i}$ belonging to $\overline{P}_{j}$ by $\tilde{P}_{i,j}$. Note
that there are at most $2^{e}+2$ many $j$’s with nonempty $\tilde{P}_{i,j}$
due to $|\tilde{P}_{i}|\leq 2^{e}T_{1}$. In the following we ignore all
$\tilde{P}_{i,j}$ of length $|\tilde{P}_{i,j}|<\frac{T_{1}}{2^{2e}}$. Hereby,
we omit at most $\frac{2T_{1}}{2^{2e}}$ many symbols from $\tilde{P}_{i}$. We
denote the remaining $\tilde{P}_{i}$ string by $\tilde{P}_{i,red}$ and we
obtain from Fact 9 that

(7.13)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(P_{i},\tilde{P}_{i}\right)>\overline{f}_{\Sigma_{\mathcal{R}}}\left(P_{i},\tilde{P}_{i,red}\right)-\frac{2}{2^{2e}}.$

For all the remaining $j$’s with $|\tilde{P}_{i,j}|\geq\frac{T_{1}}{2^{2e}}$
the corresponding string in $P_{i}$ under the matching is called $P_{i,j}$. If
$|P_{i,j}|<\frac{T_{1}}{2^{4e-t}}$, then

$\overline{f}_{\Sigma_{\mathcal{R}}}\left(P_{i,j},\tilde{P}_{i,j}\right)>1-\frac{2|P_{i,j}|}{|\tilde{P}_{i,j}|+|P_{i,j}|}=1-\frac{2}{\frac{|\tilde{P}_{i,j}|}{|P_{i,j}|}+1}>1-\frac{2}{2^{e}}.$

Otherwise, we use the estimates from formula (7.11). This yields

$\overline{f}_{\Sigma_{\mathcal{R}}}\left(P_{i},\tilde{P}_{i}\right)>1-\frac{2}{2^{e}}-\frac{2}{2^{2e}}\geq
1-\frac{3}{2^{e}}$

by equation (7.13). Combining this with equation (7.12), we obtain

(7.14)
$\overline{f}_{\Sigma_{\mathcal{R}}}\left(W_{aug}^{\prime},\overline{W}_{aug}^{\prime}\right)>1-\frac{4}{2^{e}}.$

With the aid of equation (7.10) we finish the proof of (7.8).

Now we turn to the proof of (7.9) in the alphabet $\Sigma$. We treat $V_{aug}$
and $\overline{V}_{aug}$ as concatenations of complete
$\left(T_{2},2^{4e-t},M_{2}\right)$-Feldman patterns by adding fewer than
$2T_{1}h$ many $\Sigma$-symbols to complete partial patterns at the beginning
and end of $V$ and $\overline{V}$. Note that $V_{aug}$ and
$\overline{V}_{aug}$ correspond to some $W_{aug}^{\prime}$ and
$\overline{W}_{aug}^{\prime}$ in the $\Sigma_{\mathcal{R}}$-alphabet of the
same type as above. By Lemma 13, with $\overline{f}\geq 1-\frac{4}{2^{e}}$
coming from equation (7.14), and our assumptions from equations (7.1) and
(7.2), we obtain

$\overline{f}\left(V_{aug},\overline{V}_{aug}\right)>\left(1-\frac{4}{2^{e}}\right)\cdot\beta-\frac{1}{R}>\beta-\frac{1}{R}-\frac{4}{2^{e}}.$

Finally, we conclude (7.9) with the aid of Fact 9 and equation (7.3). ∎

##  8\. The Construction Process

To construct the map $\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$ we
must build a construction sequence
$\left(\mathcal{W}_{n}\left(\mathcal{T}\right)\right)_{n\in\mathbb{N}}$
satisfying our specifications for each
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$. Moreover, this has to be done
in such a way that $\mathcal{W}_{n}\left(\mathcal{T}\right)$ is entirely
determined by $\mathcal{T}\cap\left\\{\sigma_{m}:m\leq n\right\\}$, that is,

(8.1) $\begin{split}&\text{if }\mathcal{T}\cap\left\\{\sigma_{m}:m\leq
n\right\\}=\mathcal{T}^{\prime}\cap\left\\{\sigma_{m}:m\leq n\right\\},\\\
&\text{then for all }m\leq
n:\>\mathcal{W}_{m}\left(\mathcal{T}\right)=\mathcal{W}_{m}(\mathcal{T}^{\prime}),\end{split}$

and we guarantee the continuity of our map
$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$ by Fact 17. Therefore, we
follow [FRW11] to organize our construction: For each $n$ and for each subtree
$\mathcal{S}\subseteq\left\\{\sigma_{m}:m\leq n\right\\}$ and each
$\sigma_{m}\in\mathcal{S}$ we build $\mathcal{W}_{m}\left(\mathcal{S}\right)$.
By induction we want to pass from stage $n-1$ to stage $n$. So, we assume that
we have constructed
$\left(\mathcal{W}_{m}\left(\mathcal{S}\right)\right)_{\sigma_{m}\in\mathcal{S}}$,
$\left(\mathcal{Q}_{m}(\mathcal{S})\right)_{\sigma_{m}\in\mathcal{S}}$, and
the action of $\left(G^{m}_{s}(\mathcal{S})\right)_{\sigma_{m}\in\mathcal{S}}$
for each subtree $\mathcal{S}\subseteq\left\\{\sigma_{m}:m\leq n-1\right\\}$.
In the inductive step, we now have to construct
$\left(\mathcal{W}_{m}\left(\mathcal{S}\right)\right)_{\sigma_{m}\in\mathcal{S}}$
for each subtree $\mathcal{S}\subseteq\left\\{\sigma_{m}:m\leq n\right\\}$.

Obviously, for those subtrees $\mathcal{S}$ with $\sigma_{n}\notin\mathcal{S}$
there is nothing to do. So, we have to work on the finitely many subtrees
$\mathcal{S}$ with $\sigma_{n}\in\mathcal{S}$. We list those in arbitrary
manner as $\left\\{\mathcal{S}_{1},\dots,\mathcal{S}_{E}\right\\}$. Assume
that $\mathcal{T}$ is the $e$-th subtree on this list and that we have
constructed the collections $\mathcal{W}_{n}\left(\mathcal{S}_{i}\right)$ of
$n$-words for all $i\in\left\\{1,\dots,e-1\right\\}$. Let $\mathfrak{P}$ be
the collection of prime numbers occurring in the prime factorization of any of
the lengths of the words that we have constructed so far.111In our
construction of $\mathcal{W}_{n}\left(\mathcal{T}\right)$ we will choose a
prime number $p_{n}$ larger than the maximum of $\mathfrak{P}$. By Lemma 28 we
see that our map $\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$ takes
distinct trees to transformations with nonisomorphic Kronecker factors. Hence,
for $\mathcal{T}\neq\mathcal{T}^{\prime}$ we get that $\Psi(\mathcal{T})$ is
not isomorphic to $\Psi(\mathcal{T}^{\prime})$ or
$\Psi(\mathcal{T}^{\prime})^{-1}$ (compare with [FRW11, Corollary 34]). As in
[FRW11] this is actually not necessary for the proof of the main theorem but
we keep this order of induction to parallel the strategy in [FRW11] and to
allow possible extensions in future work.

We want to construct $\mathcal{W}_{n}\left(\mathcal{T}\right)$,
$\mathcal{Q}_{s}^{n}\left(\mathcal{T}\right)$, and the action of
$G_{s}^{n}\left(\mathcal{T}\right)$, which we abbreviate by $\mathcal{W}_{n}$,
$\mathcal{Q}_{s}^{n}$, and $G_{s}^{n}$, respectively. For that purpose, let
$m$ be the largest number less than $n$ such that $\sigma_{m}\in\mathcal{T}$.
If $m=0$ we have $\mathcal{W}_{0}=\Sigma=\left\\{1,\dots,2^{12}\right\\}$ (see
Remark 54 for comments on this base case) and for $m>0$ our induction
assumption says that we have
$\mathcal{W}_{m}=\mathcal{W}_{m}\left(\mathcal{T}\right)$,
$\mathcal{Q}_{s}^{m}=\mathcal{Q}_{s}^{m}\left(\mathcal{T}\right)$, and
$G_{s}^{m}=G_{s}^{m}\left(\mathcal{T}\right)$ satisfying our specifications.
Furthermore, there are
$\frac{1}{8}>\alpha_{1,m}>\dots>\alpha_{s(m),m}>\beta_{m}>0$ and a positive
integer $R_{m}$ with

(8.2) $R_{m}\geq\frac{9}{\beta_{m}}$

such that the following assumptions on $\overline{f}$ distances hold:

  * •

For every $s\in\left\\{1,\dots,s(m)\right\\}$ we have

(8.3) $\overline{f}\left(W,W^{\prime}\right)>\alpha_{s,m}$

on any substrings $W$ and $W^{\prime}$ of at least $\frac{h_{m}}{R_{m}}$
consecutive symbols in any words $w,w^{\prime}\in\mathcal{W}_{m}$ with
$[w]_{s}\neq[w^{\prime}]_{s}$.

  * •

We have

(8.4) $\overline{f}\left(W,W^{\prime}\right)>\beta_{m}$

on any substrings $W$ and $W^{\prime}$ of at least $\frac{h_{m}}{R_{m}}$
consecutive symbols in any words $w,w^{\prime}\in\mathcal{W}_{m}$ with $w\neq
w^{\prime}$.

We start the construction in stage $n$ by choosing a prime number $p_{n}$
larger than the maximum of $\mathfrak{P}$ and satisfying

(8.5) $p_{n}>\max\left(4R_{m},2^{n},\frac{1}{\epsilon_{n}}\right),$

where we recall the definition of the sequence
$\left(\epsilon_{n}\right)_{n\in\mathbb{N}}$ from (4.1). Then we choose an
integer $R_{n}$ such that

(8.6) $R_{n}\geq\frac{40p_{n}}{\beta_{m}}$

Moreover, we choose the integer $e(n)>e(m)$ sufficiently large such that

(8.7) $2^{e(n)}>\max\left(10R_{n},\max_{s\leq s(n)}|G_{s}^{n}|\right).$

In the two possible cases $s(n)=s(m)$ and $s(n)=s(m)+1$ we now present the
construction of $n$-words out of $m$-words as well as the extension of
$G_{s}^{m}$ actions to $G_{s}^{n}$ actions. In case of $s(n)=s(m)+1$ we also
define the new equivalence relation $\mathcal{Q}_{s(n)}^{n}$.

###  8.1. Case 1: s(n)=s(m)

####  8.1.1. Construction of $\mathcal{W}_{n}$

We apply the substitution step described in Section 7 $s(m)+1$ many times to
construct $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ for $s=0,\dots,s(m)$ and
eventually $\mathcal{W}_{n}$. Adapting to the notation in the general
substitution step we set $X=\mathcal{W}_{m}$ and

$\displaystyle\mathcal{P}_{i}=\mathcal{Q}_{i-1}^{m},$
$\displaystyle\mathcal{R}_{i}=\mathcal{Q}_{i}^{m},$ $\displaystyle
G_{i}=G_{i-1}^{m},$ $\displaystyle H_{i}=G_{i}^{m}$

for the $i$-th application, where $i=1,\dots,s(m)$. In the final $(s(m)+1)$-th
application we let $\mathcal{P}_{s(m)+1}=\mathcal{Q}_{s(m)}^{m}$,
$\mathcal{R}_{s(m)+1}=\left\\{(w,w):w\in\mathcal{W}_{m}\right\\}$, that is,
$X/\mathcal{R}_{s(m)+1}=\mathcal{W}_{m}$, $G_{s(m)+1}=G_{s(m)}^{m}$, and we
let $H_{s(m)+1}$ be the trivial group acting trivially on $\mathcal{W}_{m}$.

To carry out the successive application of the substitution step we always set
$\tilde{R}=R_{n}$ and introduce $t_{i}\in\mathbb{N}$ for $i=1,\dots,s(m)+1$
such that $t_{s(m)+1}=0$ and

$2^{t_{i}}=|ker(\rho_{i,i-1}^{(m)})|\text{ for }i=1,\dots,s(m).$

Here, we recall that $\rho_{i,i-1}^{(m)}:G_{i}^{m}\to G_{i-1}^{m}$ is the
canonical homomorphism defined in Subsection 4.3. Moreover, we define
parameters as follows

$\displaystyle P_{i}=2^{(i-1)\cdot 4e(n)},$ $\displaystyle\text{for
}i=1,\dots,s(m)+1,$ $\displaystyle N_{i}=2^{(i-1)\cdot 4e(m)},$
$\displaystyle\text{for }i=1,\dots,s(m)+1.$

Then we have $N_{i}=|\mathcal{W}_{m}/\mathcal{Q}_{i-1}^{m}|$ and the number
$P_{i}$ will describe $|\mathcal{W}_{n}/\mathcal{Q}_{i-1}^{n}|$. We also set
$K_{s(m)+1}=2^{4e(n)}$, and choose numbers $K_{i}$, $i=1,\dots,s(m)$, such
that $K_{i}\cdot|ker(\rho_{i,i-1}^{(m)})|=2^{4e(n)}$ for $i=1,\dots,s(m)$. We
point out that these numbers are chosen in this way to always obtain exactly
$2^{4e(n)}$ substitution instances of each coarser equivalence class (see part
(2) of Proposition 42) in order to satisfy specification property (Q6).
Moreover, we choose a number $U_{1}=2^{U_{1}^{\prime}}$ with

$\displaystyle U_{1}^{\prime}\geq\max_{i=1,\dots,s(m)}t_{i}$ and
$\displaystyle U_{1}\geq\max\left(2R_{n}^{2},2^{8e(m)}\right).$

In particular, condition (7.3) is satisfied in all construction steps.

By forward recursion we define the parameters $M_{i}$, $i=1,\dots,s(m)+2$, as
well as $U_{i}$, $i=2,\dots,s(m)+1$:

$\displaystyle M_{1}=1,$ $\displaystyle M_{2}=K_{1}P_{1}U_{1},$ $\displaystyle
M_{i}=K_{i-1}P_{i-1}U_{i-1}2^{(4e(m)-t_{i-2})\cdot(2M_{i-1}+3)}$ for $i\geq
3$, $\displaystyle U_{2}=U_{1},$ $\displaystyle
U_{i}=U_{i-1}2^{(4e(m)-t_{i-2})\cdot(2M_{i-1}+3)}$ $\displaystyle\text{ for
$i\geq 3$}.$

Hereby, we define the parameters $T_{i}$, $i=1,\dots,s(m)+2$, by backward
recursion:

$\displaystyle T_{s(m)+2}=p_{n}^{2},$ $\displaystyle T_{i}=T_{i+1}\cdot
2^{(4e(m)-t_{i})\cdot\left(2M_{i+1}+3\right)}$ $\displaystyle\text{ for $i\leq
s(m)+1$}.$

We stress that the definitions of $T_{i}$ and $M_{i}$ are directly linked to
the corresponding conditions in equations (7.4) and (7.5) from the general
substitution step. We also conclude from equation (7.7) that the number $k$ of
concatenations working for all substitutions steps is given by

(8.8) $k=U_{s(m)+1}\cdot T_{s(m)+1}\cdot
2^{(4e(m)-t_{s(m)})\cdot(2M_{s(m)+1}+3)}=U_{s(m)+1}\cdot T_{s(m)}=U_{2}\cdot
T_{1},$

which implies that the length of $n$-words is given by

$h_{n}=U_{s(m)+1}\cdot T_{s(m)+1}\cdot
2^{(4e(m)-t_{s(m)})\cdot(2M_{s(m)+1}+3)}\cdot h_{m}=U_{1}\cdot T_{1}\cdot
h_{m}.$

After determining all these parameters we describe the successive application
of the general substitution step. We start by concatenating $k=U_{1}\cdot
T_{1}$ many times the single element of
$X/\mathcal{P}_{1}=\mathcal{W}_{m}/\mathcal{Q}_{0}^{m}$ which yields
$\Omega_{1}=\mathcal{W}_{n}/\mathcal{Q}_{0}^{n}\subseteq\left(\mathcal{W}_{m}/\mathcal{Q}_{0}^{m}\right)^{k}=\left(X/\mathcal{Q}_{0}\right)^{k}$
of cardinality $|\Omega_{1}|=P_{1}=1$. Note that this element can be
considered as a repetition of $U_{1}$ many
$\left(T_{1},2^{0},1\right)$-Feldman patterns. This viewpoint allows the
application of our first substitution step $i=1$ using the notation from
above. More explicitly, the first substitution step produces a collection
$\Omega_{1}^{\prime}\subset\left(X/\mathcal{R}_{1}\right)^{k}=\left(\mathcal{W}_{m}/\mathcal{Q}_{1}^{m}\right)^{k}$
of $K_{1}\cdot|ker(\rho_{1,0}^{(m)})|=2^{4e(n)}=P_{2}$ substitution instances,
which are concatenations of $U_{2}$ many
$\left(T_{2},2^{4e(m)-t_{1}},M_{2}\right)$-Feldman patterns. On the one hand,
$\Omega_{1}^{\prime}$ will serve as our collection
$\Omega_{2}\subset\left(X/\mathcal{P}_{2}\right)^{k}=\left(\mathcal{W}_{m}/\mathcal{Q}_{1}^{m}\right)^{k}$
for the application of the substitution step $i=2$. On the other hand,
$\Omega_{1}^{\prime}$ will turn out to be our collection of equivalence
classes in $\mathcal{W}_{n}/\mathcal{Q}_{1}^{n}$. Successively, we apply the
substitution step for $i=2,\dots,s(m)+1$.

######  Remark 44.

In correspondence with specification (Q5), $\mathcal{Q}_{s}^{n}$ is defined as
the product equivalence relation on $\mathcal{W}_{n}$ for each
$s=1,\dots,s(m)$. Then we see from the procedure of the substitution step that
for each $w\in\mathcal{W}_{n}$ its class
$[w]_{s}\in\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ is a concatenation of
$U_{s+1}\geq 2^{8e(m)}$ different
$\left(T_{s+1},2^{4e(m)-t_{s}},M_{s+1}\right)$-Feldman patterns (with building
blocks out of $\mathcal{W}_{m}/\mathcal{Q}_{s}^{m}$). We call these the _$s$
-Feldman patterns_ and refer to this sequence of Feldman patterns as the _$s$
-pattern type_ of $w$. Using the same enumeration of
$\left(T_{s+1},2^{4e(m)-t_{s}},M_{s+1}\right)$-Feldman patterns, we also
define the $s$-pattern types for words in $rev(\mathcal{W}_{n})$.

For such a $s$-Feldman pattern $P_{m}$ we make the following observation.

######  Lemma 45.

Let $w\in\mathcal{W}_{n}$ and $[P_{m}]_{s}$ be a
$\left(T_{s+1},2^{4e(m)-t_{s}},M_{s+1}\right)$-Feldman pattern in $[w]_{s}$
with building blocks from the tuple
$\left([A_{1}]_{s},\dots,[A_{2^{4e(m)-t_{s}}}]_{s}\right)$ in
$\mathcal{W}_{m}/\mathcal{Q}_{s}^{m}$. Then for every