# Non-Classifiability of Kolmogorov Diffeomorphisms up to Isomorphism

Marlies Gerber1 and  Philipp Kunde2

###### Abstract.

We consider the problem of classifying Kolmogorov automorphisms (or
$K$-automorphisms for brevity) up to isomorphism. Within the collection of
measure-preserving transformations, Bernoulli shifts have the ultimate mixing
property, and $K$-automorphisms have the next-strongest mixing properties of
any widely considered family of transformations. J. Feldman observed that
unlike Bernoulli shifts, the family of $K$-automorphisms cannot be classified
up to isomorphism by a complete numerical Borel invariant. This left open the
possibility of classifying $K$-automorphisms with a more complex type of Borel
invariant. We show that this is impossible, by proving that the isomorphism
equivalence relation restricted to $K$-automorphisms, considered as a subset
of the Cartesian product of the set of $K$-automorphisms with itself, is a
complete analytic set, and hence not Borel. Moreover, we prove this remains
true if we restrict consideration to $K$-automorphisms that are also
$C^{\infty}$ diffeomorphisms. This shows in a concrete way that the problem of
classifying $K$-automorphisms up to isomorphism is intractible.

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

2 Jagiellonian University in Krakow, Faculty of Mathematics and Computer
Science, 30-348 Krakow, Poland. The research of P.K. is part of the project
No. 2021/43/P/ST1/02885 co-funded by the National Science Centre and the
European Union’s Horizon 2020 research and innovation programme under the
Marie Sklodowska-Curie grant agreement no. 945339.

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

##  1\. Introduction

A classical question in ergodic theory, posed by J. von Neumann in 1932
[Ne32], is the isomorphism problem: classify measure-preserving
transformations up to isomorphism. We let $\operatorname{Aut}(\mu)$ denote the
set of all invertible measure-preserving transformations on a fixed standard
non-atomic probability space, $(\Omega,\mathcal{B},\,\mu).$ Two elements
$S,T\in\operatorname{Aut}(\mu)$ are said to be _isomorphic_ if there exists
$\varphi\in\operatorname{Aut}(\mu)$ such that $S\circ\varphi$ and
$\varphi\circ T$ agree $\mu$-almost everywhere. Two great successes in the
classification of measure-preserving transformations are the Halmos-von
Neumann classification of ergodic elements of $\operatorname{Aut}(\mu)$ 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].
However, the isomorphism problem remains unsolved for general ergodic measure-
preserving transformations.

In more recent years, focus has shifted to the study of the logical complexity
of the isomorphism problem, and a series of _anti-classification_ results have
appeared. These results demonstrate the complexity of the problem of
classification up to isomorphism, or other equivalence relations, and give
some limitations on what (if any) type of classification is potentially
achievable. (See [Fopp] for a discussion of a hierarchy of potential
classifications.)

To describe some of the anti-classification results, we endow
$\operatorname{Aut}(\mu)$ with the weak topology. (Recall that $T_{n}\to T$ in
the weak topology if and only if we have $\mu(T_{n}(A)\Delta T(A))\to 0$ for
every $A\in\mathcal{B}.)$ This topology is compatible with a complete
separable metric and hence makes $\operatorname{Aut}(\mu)$ into a Polish
space. Let $\mathcal{E}$, $\mathcal{WM}$, $\mathcal{M}$, and $\mathcal{K}$
denote, respectively, the sets of ergodic, weakly mixing, mixing, and
Kolmogorov automorphisms (or $K$-automorphisms for brevity) in
$\operatorname{Aut}(\mu)$. The sets $\mathcal{E}$ and $\mathcal{WM}$ form
(dense) $G_{\delta}$-sets in $\operatorname{Aut}(\mu).$ Thus the induced
topologies on $\mathcal{E}$ and $\mathcal{WM}$ are Polish as well. Moreover,
the sets $\mathcal{M}$ and $\mathcal{K}$ are Borel [Fo00, Proposition 43] and
dense in $\operatorname{Aut}(\mu)$ (denseness can be seen from [Ha44]), but
these sets are meager in the sense of category [Ro48].

The strongest type of classification that is feasible for a Borel family of
automorphisms in $\operatorname{Aut}(\mu)$ is a Borel function from the family
to the real numbers which is a complete invariant, that is, two automorphisms
$S$ and $T$ in the family are isomorphic if and only if the values of the
function are the same at $S$ and $T$. For example, [Or70] shows that metric
entropy is a complete isomorphism invariant for Bernoulli shifts. In contrast,
J. Feldman [Fe74] proved that there is no Borel function from the
$K$-automorphisms to the real numbers that is a complete isomorphism
invariant.

A somewhat weaker type of classification is a Borel way of associating
complete algebraic invariants to a given Borel subset of
$\operatorname{Aut}(\mu)$, such as the Halmos-von Neumann classification.
However, G. Hjorth [Hj01] showed that there is no Borel way of associating
algebraic invariants to $\mathcal{E}$ that completely determines isomorphism.
Moreover, Foreman and B. Weiss [FW04] proved that there is no generic class
(that is, a dense $G_{\delta}$-set) within $\operatorname{Aut}(\mu)$ for which
there is a Borel way of associating a complete algebraic invariant.

Both of these types of classification, by a Borel function that is a complete
invariant or by a Borel way of associating complete algebraic invariants for a
particular family $\mathcal{F}$ in $\operatorname{Aut}(\mu),$ imply that the
isomorphism relation $\mathcal{R}$, when viewed as a subset of the Cartesian
product $\operatorname{Aut}(\mu)\times\operatorname{Aut}(\mu)$, is such that
$\mathcal{R}\cap(\mathcal{F}\times\mathcal{F})$ is Borel. Therefore if
$\mathcal{R}\cap(\mathcal{F}\times\mathcal{F})$ is not Borel, the types of
classification discussed above are not possible for $\mathcal{F}.$ Hjorth
[Hj01] proved that the isomorphism relation $\mathcal{R}$ on
$\operatorname{Aut}(\mu)$ is not a Borel set and is, in fact, a complete
analytic set, which is a maximally complex analytic set. However, his proof
used non-ergodic transformations in an essential way. In the case of the
family $\mathcal{E}$ of ergodic automorphisms, Foreman, D. Rudolph, and Weiss
[FRW11] proved that $\mathcal{R}\cap(\mathcal{E}\times\mathcal{E})$ is a
complete analytic set, and hence not Borel. The results in [Hj01] and [FRW11]
are among the strongest types of anti-classification results, because they
show that even the weakest types of classification, as described in [Fopp],
are not possible. Showing that an equivalence relation on a family in
$\mathcal{F}$ is not Borel can be interpreted as saying that there is no
general method of determining—in a countable number of steps, using countable
amounts of information—whether or not two transformations in the family are
equivalent. This demonstrates in a concrete way that the classification
problem is intractible.

In the search for classification or anti-classification results, we place
increasingly stringent conditions on the family of transformations under
consideration. Bernoulli shifts, which can be viewed as the most random type
of transformations, have the strongest type of classification, a complete
Borel invariant. But what about classes of transformations which satisfy a
randomness assumption that is stronger than ergodicity but weaker than
Bernoulliness, such as weakly mixing transformations, mixing transformations,
and $K$-automorphisms?

In 1958, A. Kolmogorov defined what are now called $K$-automorphisms in terms
of a 0-1 law [Ko58]. V. Rokhlin and Ya. Sinai [RS61] proved that an
automorphism is $K$ if and only if it has completely positive (metric)
entropy, that is, the entropy is positive with respect to every non-trivial
partition. $K$-automorphisms have the strongest mixing properties of any
widely considered family of transformations. Until Ornstein constructed a
counterexample [Or73], it was unknown whether all $K$-automorphisms were, in
fact, Bernoulli. Soon afterwards, Ornstein and P. Shields constructed a family
of non-Bernoulli $K$-automorphisms indexed by sequences of zeros and ones,
such that two automorphisms in this family are isomorphic if and only if the
corresponding sequences agree except possibly at finitely many terms [OS73].
This led Feldman to the previously mentioned result that there is no complete
numerical Borel isomorphism invariant for $K$-automorphisms.

This left open the following questions that appear in Foreman’s surveys [Fo00]
and [Fopp] regarding the complexity of the isomorphism equivalence relation on
$K$-automorphisms: Is the isomorphism equivalence relation restricted to the
$K$-automorphisms

  * •

reducible to $E_{0}$ (the minimal level of complexity possible given Feldman’s
result)?

  * •

reducible to $=^{+}$(the level of complexity of the Halmos-von Neumann type of
classification)?

  * •

a Borel equivalence relation?

(The last of these questions was also posed by Newberger and is stated as
Question 1.16 in [Bpp].) We prove that for the isomorphism equivalence
relation $\mathcal{R},$ the set
$\mathcal{R}\cap(\mathcal{K}\times\mathcal{K})$ is a complete analytic set,
and therefore not Borel, thereby providing a negative answer to all three of
the above questions.

The work of [FRW11] provides not only anti-classification results, but also
new methods of construction of ergodic automorphisms. The automorphisms are
constructed using certain concatenations of blocks of symbols (which can also
be interpreted in terms of cutting and stacking) together with equivalence
relations on these blocks. In [FRW11] there are some random choices in the
constructions, while in [GKpp], we obtained anti-classification results with a
method based on [FRW11], but we replaced the random choices by a deterministic
method using Feldman patterns. In sections 4–6 below, we utilize the
transformations from [GKpp] to construct a certain family of skew products
that are known to be $K$-automorphisms by the results of I. Meilijson [Me74].
This leads to our anti-classification results for $\mathcal{K}.$

Our anti-classification results also hold when the isomorphism relation is
replaced by Kakutani equivalence. Two ergodic automorphisms are said to be
_Kakutani equivalent_ if they are isomorphic to measurable cross-sections of
the same ergodic flow. Another equivalent definition is that
$T,S\in\mathcal{E}$ are Kakutani equivalent if there exist two sets $A,B$ of
positive measure such that the first return map $T_{A}$ of $T$ to $A$ with the
induced measure $\mu_{A}=\mu/\mu(A)$ on $A$ is isomorphic to the analogously
defined first return map $S_{B}$ of $S$ to $B.$ Since the Kakutani equivalence
relation is weaker than isomorphism, one might expect classification to be
simpler. However, in [GKpp] we showed that the Kakutani equivalence relation
on ergodic automorphisms is also a complete analytic set. In the current
paper, we show that this remains true for $K$-automorphisms as well. The
methods in [GKpp] for proving non-classifiability of ergodic automorphisms _up
to Kakutani equivalence_ are also useful in the current paper, even for
obtaining non-classifiability of $K$-automorphisms _up to isomorphism_.

The classification problem (with respect to isomorphism or Kakutani
equivalence) can also be restricted to the class $\text{Diff}^{\infty}(M,\mu)$
of smooth diffeomorphisms of a compact manifold $M$ that preserve a smooth
measure $\mu.$ But even with this restriction, Foreman and Weiss [FW22] proved
that the isomorphism relation on smooth ergodic diffeomorphisms is a complete
analytic set in
$\text{Diff}^{\infty}(M,\mu)\times\text{Diff}^{\infty}(M,\mu)$, and therefore
not Borel if $M$ is the torus, disk, or annulus. For the case of the torus, S.
Banerjee and P. Kunde [BK22] generalized this result to the real-analytic
setting. In [GKpp] we obtained the analogous results for Kakutani equivalence
both in the smooth and the real-analytic settings. In Section 7, we show that
anti-classification results for $K$-automorphisms for both isomorphism and
Kakutani equivalence also hold in the smooth setting. The extension to the
real-analytic setting is still an open problem.

Our anti-classification results for $K$-automorphisms in the smooth setting
hold on the five-dimensional torus, and we use a construction due to Katok
[Ka80] of $C^{\infty}$ diffeomorphisms that are $K$ but not loosely Bernoulli,
and therefore not Bernoulli. Another family of $C^{\infty}$ diffeomorphisms
that are $K$ but not loosely Bernoulli is due to Rudolph [Ru88]. Rudolph’s
examples are, in fact, real-analytic five-dimensional analogs of the
$T$,$T^{-1}$ transformation, which S. Kalikow proved is not loosely Bernoulli
[Kal82]. More recently, A. Kanigowski, F. Rodriguez Hertz, and K. Vinhage
[KRV18] gave an example of a $C^{\infty}$ diffeomorphism in dimension $4$ that
is $K$ and loosely Bernoulli, but not Bernoulli. (It is an open problem
whether there exist $C^{\infty}$ diffeomorphisms that are $K$ but not
Bernoulli in dimension $3$.)

T. Austin [Aupp] introduced a new isomorphism invariant called scenery entropy
that distinguishes between some of the known non-Bernoulli $K$-automorphisms,
including certain smooth examples. As stated in [Aupp], conditionally on an
invariance principle for certain local times, this leads to a continuum of
pairwise non-isomorphic smooth non-Bernoulli $K$-automorphisms (of the same
measure entropy) on a fixed compact manifold. However, as far as we know, this
invariance principle has not yet been established. In Section 7.4, which can
be read independently of Sections 2–6, we indicate another construction of a
continuum of $C^{\infty}$ diffeomorphisms of the five-dimensional torus of the
same measure entropy that are $K$ and pairwise non-Kakutani equivalent (and
therefore non-isomorphic). We include this explicit construction because it
utilizes some of the ideas in Sections 7.1–7.3, but is much simpler. It is not
known if there exists an uncountable family of pairwise non-isomorphic smooth
$K$-automorphisms of the same entropy on a four-dimensional manifold. In
particular, it is an open question if the type of construction in [KRV18],
varying the skewing function, would lead to such a family.

Since $K$-automorphisms are mixing, we obtain anti-classification results for
mixing automorphisms as a corollary. However, the results for
$K$-automorphisms do not cover the collections of mixing or weakly mixing
automorphisms in the zero entropy case. In an earlier work [Kupp2], the second
author has shown that the isomorphism relation, as well as the Kakutani
equivalence relation, on zero entropy smooth weakly mixing transformations of
the torus, disk, or annulus is a complete analytic set. Moreover, he also
obtained this result for zero entropy real-analytic weakly mixing
diffeomorphisms of the 2-torus. The methods used in [Kupp2] are very different
from those in the current paper, and they utilize the “twisted” version of the
Anosov-Katok construction [AK70]. The earlier work of Foreman and Weiss [FW22]
in the smooth setting uses the “untwisted” version of the Anosov-Katok method,
and the transformations produced are ergodic, but not weakly mixing. For the
collection $\mathcal{ZM}$ of zero entropy mixing automorphisms, it is an open
question whether the isomorphism equivalence relation (or the Kakutani
equivalence relation) restricted to $\mathcal{ZM}$ is a Borel subset of
$\mathcal{ZM}\times\mathcal{ZM}.$

Other anti-classification results were recently obtained in the context of
topological conjugacy of diffeomorphisms. Two diffeomorphisms $f$ and $g$ of a
manifold $M$ are said to be topologically conjugate if there exists a
homeomorphism $h$ of $M$ such that $f\circ h=h\circ g$. Foreman and A.
Gorodetski [FGpp] showed that for a closed manifold of any dimension the
topological conjugacy equivalence relation, considered as a subset of the
Cartesian product of the set of $C^{\infty}$ diffeomorphisms with itself, is
not Borel. In the case of $C^{\infty}$ diffeomorphisms of the circle with
Liouvillean rotation numbers, Kunde considered the equivalence relation of
topological conjugacy with the additional requirement that the conjugating map
$h$ be a $C^{r}$ diffeomorphism. He proved that for each $r$, $1\leq
r\leq\infty,$ there is no complete numerical Borel invariant [Kupp].

##  2\. Statement of Results and Outline of Proofs

###  2.1. Results for $K$-automorphisms

Let $(\Omega,\mathcal{B},\mu)$ be a standard non-atomic probability space, and
let $\mathcal{E}$, $\mathcal{H}$, and $\mathcal{K}$ denote the set of all
measure-preserving automorphisms of $\Omega$ that are, respectively, ergodic,
ergodic with positive entropy, and $K$.

To prove our anti-classification results we follow the general strategy from
[FRW11]. An important tool is the concept of a reduction.

######  Definition 1.

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 2.

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$.

######  Definition 3.

An analytic subset $A$ of a Polish space $X$ is called _complete analytic_ if
every analytic set can be continuously reduced to A.

If $A$ is continuously reducible to an analytic set $B$ and $A$ is a complete
analytic set, then so is $B$. There are analytic sets that are not Borel (see,
for example, [Ke95, section 14]). This implies that a complete analytic set is
not Borel.

In the Polish space $\mathcal{T}rees$ (to be defined in Section 3.1), the
subset consisting of trees with an infinite branch is an example of a complete
analytic set [Ke95, section 27].

The map $\Phi$ in Theorem A below provides a continuous reduction from the set
of trees with an infinite branch to
$\left\\{T\in\mathcal{K}\mathrel{}\middle|\mathrel{}T\text{\ is isomorphic to\
}T^{-1}\right\\}$.

######  Theorem A.

There is a continuous map $\Phi:\mathcal{T}rees\to\mathcal{K}$ such that for
$\mathcal{T}\in\mathcal{T}rees$ with $V=\Phi(\mathcal{T})$, the following
conditions hold:

  1. (a)

If $\mathcal{T}$ has an infinite branch, then $V$ and $V^{-1}$ are isomorphic
(and therefore Kakutani equivalent);

  2. (b)

If $\mathcal{T}$ does not have an infinite branch, then $V$and $V^{-1}$ are
not Kakutani equivalent (and therefore not isomorphic).

To obtain our anti-classification result in Corollary A, we define the
continuous embedding
$i:\operatorname{Aut}(\mu)\to\operatorname{Aut}(\mu)\times\operatorname{Aut}(\mu)$
by $i(T)=(T,T^{-1})$, and note that $i\circ\Phi$ is a continuous reduction
from the set of trees with an infinite branch to
$\left\\{(S,T)\in\mathcal{K}\times\mathcal{K}\mathrel{}\middle|\mathrel{}S\text{\
is isomorphic to\ }T\right\\}$. This, together with the observation in
Subsection 3.2 that the isomorphism and Kakutani equivalence relations
considered as subsets of $\mathcal{E}\times\mathcal{E}$ are analytic sets,
yields Corollary A.

######  Corollary A.

The set $\\{(S,T)\in\mathcal{K}\times\mathcal{K}:S$ and $T$ are isomorphic} is
a complete analytic subset of $\mathcal{K}\times\mathcal{K}$ and hence not a
Borel set. The same is true for “isomorphic” replaced by “Kakutani
equivalent”.

To prove Theorem A, we start with the following more explicit Theorem B.

######  Theorem B.

Part 1.  There is a continuous map $\Upsilon:\mathcal{T}rees\to\mathcal{H}$
such that for $\mathcal{T}\in\mathcal{T}rees$ with $U=\Upsilon(\mathcal{T})$,
the following conditions hold:

  1. (a)

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

  2. (b)

If $\mathcal{T}$ does not have an infinite branch, then $U$ and $U^{-1}$ are
not Kakutani equivalent (and therefore not isomorphic).

Part 2. The map $\Upsilon$ in Part 1 can be chosen so that there is also a set
$A\in\mathcal{B}$ of positive measure such that for
$\mathcal{T}\in\mathcal{T}rees$ with $U=\Upsilon(\mathcal{T})$ we have:

  1. (c)

The induced map $U_{A}$ is a $K$-automorphism;

  2. (d)

If $\mathcal{T}$ has an infinite branch, then there exists $\phi\in$
Aut$(\mu)$ such that $\phi\circ U=U^{-1}\circ\phi$ and $\phi(A)=A$.
Consequently, $U_{A}$ is isomorphic to $(U_{A})^{-1}.$

Part 1 of Theorem B with $\mathcal{H\,}$ replaced by $\mathcal{E}$ is in
[GKpp]. If, in addition, “Kakutani equivalent” is replaced by “isomorphic” the
result was proved by M. Foreman, D. Rudolph, and B. Weiss in [FRW11], and
their methods, combined with techniques from Kakutani equivalence theory (see,
for example, [ORW82]), were used in [GKpp].

###### Proof of Theorem A.

Theorem A follows from Theorem B by taking $V=U_{A}$ equipped with the
normalized induced measure $\mu_{A}$. For part (b) of Theorem A, observe that
$V$ and $V^{-1}$ are not Kakutani equivalent if $U$ and $U^{-1}$ are not
Kakutani equivalent. ∎

For $\mathcal{T}\in\mathcal{T}rees$, the transformation
$U=\Upsilon(\mathcal{T})$ in Theorem B is defined as
$U=\Psi(\mathcal{T})\times\mathbb{B}$, where $\Psi(\mathcal{T})$ is the
transformation constructed in sections 7–8 of [GKpp] and $\mathbb{B}$ is the
$(1/2,1/2)$-Bernoulli shift. The definition of $\Psi(\mathcal{T})$ is reviewed
in Section 5 below.

###### Proof of Part 1 (a) of Theorem B.

According to [GKpp, section 5], $\Psi(\mathcal{T})$ is isomorphic to
$\Psi(\mathcal{T})^{-1}$ if $\mathcal{T}$ has an infinite branch. Part (a)
follows immediately. ∎

Part 2 of Theorem B is based on [Me74] and is proved in Section 4. The main
new idea in the automorphism case of the present work occurs in the proof of
Part 1 (b) in Section 6.2.

###  2.2. Results for smooth $K$-diffeomorphisms

If $M$ is a finite-dimensional compact $C^{\infty}$ manifold and $\mu$ is a
standard measure on $M$ determined by a smooth volume element, we let
$\text{Diff}^{\infty}(M,\mu)$ denote the $\mu$-preserving $C^{\infty}$
diffeomorphisms on $M$. Equipped with the $C^{\infty}$ topology,
$\text{Diff}^{\infty}(M,\mu)$ is a Polish space. We can also view each element
of $\text{Diff}^{\infty}(M,\mu)$ as an element of $\operatorname{Aut}(\mu)$,
and with this interpretation, it follows from [Bj09] that
$\text{Diff}^{\infty}(M,\mu)$ is a Borel subset of $\operatorname{Aut}(\mu)$.

In Section 7 we obtain anti-classification results for $K$-automorphisms that
are also $C^{\infty}$ diffeomorphisms preserving a smooth measure. Our work
utilizes A. Katok’s construction of smooth non-Bernoulli $K$-automorphisms
[Ka80].

Let $\mathbb{T}^{n}$ denote the $n$-dimensional torus, that is, the Cartesian
product of $n$ copies of $S^{1}=\mathbb{R}/\mathbb{Z},$ and let $\lambda_{n}$
denote Lebesgue measure on $\mathbb{T}^{n}.$

We will prove the following smooth version of Theorem A.

######  Theorem C.

There is a continuous map

$\displaystyle\Phi:\mathcal{T}rees$
$\displaystyle\to\left(\mathcal{K}\cap\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})\right)\times\left(\mathcal{K}\cap\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})\right)$
$\displaystyle\mathcal{T}$
$\displaystyle\mapsto\left(\Phi_{1}(\mathcal{T}),\Phi_{2}(\mathcal{T})\right)$

such that

  1. (a)

If $\mathcal{T}$ has an infinite branch, then $\Phi_{1}(\mathcal{T})$ and
$\Phi_{2}(\mathcal{T})$ are isomorphic (and therefore Kakutani equivalent);

  2. (b)

If $\mathcal{T}$ does not have an infinite branch, then
$\Phi_{1}(\mathcal{T})$ and $\Phi_{2}(\mathcal{T})$ are not Kakutani
equivalent (and therefore not isomorphic).

As in the case of $K$-automorphisms, this immediately gives the following
anti-classification result.

######  Corollary C.

The set

$\left\\{(S,T)\in\left(\mathcal{K}\cap\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})\right)\times\left(\mathcal{K}\cap\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})\right)\mathrel{}\middle|\mathrel{}\text{$S$
and $T$ are isomorphic}\right\\}$

is a complete analytic subset of
$\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})\times\text{Diff}^{\,\infty}(\mathbb{T}^{5},\lambda_{5})$
with respect to the $C^{\infty}$ topology and hence not a Borel set. The same
is true for “isomorphic” replaced by “Kakutani equivalent”.

Since the weak topology on $\text{Diff}^{\infty}(\mathbb{T}^{5},\lambda_{5})$
is coarser than the $C^{\infty}$ topology,
$\left\\{(S,T)\in\left(\mathcal{K}\cap\text{Diff}^{\infty}(\mathbb{T}^{5},\lambda_{5})\right)\times\left(\mathcal{K}\cap\text{Diff}^{\infty}(\mathbb{T}^{5},\lambda_{5})\right)\mathrel{}\middle|\mathrel{}\text{$S$
and $T$ are isomorphic}\right\\}$ is also a complete analytic subset of
$\text{Diff}^{\infty}(\mathbb{T}^{5},\lambda_{5})\times\text{Diff}^{\infty}(\mathbb{T}^{5},\lambda_{5})$
in the weak topology.

##  3\. Preliminary material

###  3.1. The space of trees

As we mentioned in Section 2.1, the collection of trees within
$\mathcal{T}\kern-1.42262ptrees$ that have an infinite branch is an example of
a complete analytic set, and it is fundamental to our construction. We now
define trees, the space $\mathcal{T}\kern-1.42262ptrees$, and infinite
branches of trees.

Let $\mathbb{N}$ be the nonnegative integers, and let
$\mathbb{N}^{<\mathbb{N}}$ denote the collection of finite sequences in
$\mathbb{N}$. By convention, the empty sequence $\emptyset$ is in
$\mathbb{N}^{<\mathbb{N}}$.

######  Definition 4.

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_{m}\right)$ with $m\leq n$ is an initial
segment of $\tau$, then $\sigma\in\mathcal{T}$. Each tree $\mathcal{T}$
contains $\emptyset$, which is regarded as an initial segment of all
$\tau\in\mathcal{T}$.

######  Definition 5.

A function $f:\\{0,\dots,n-1\\}\to(\tau_{1},\dots,\tau_{n})\in\mathcal{T}$ is
called a _branch_ of $\mathcal{T}$ of length $n$. The collection
$\mathcal{T}\kern-1.42262ptrees$ consists of those trees that contain branches
of arbitrarily long length. An _infinite branch_ through $\mathcal{T}$ is a
function $f:\mathbb{N}\to\mathbb{N}$ such that for all $n\in\mathbb{N}$ we
have $\left(f(0),\dots,f(n-1)\right)\in\mathcal{T}$. If a tree has an infinite
branch, it is called _ill-founded_. If it does not have an infinite branch, it
is called _well-founded_.

To describe a topology on the collection of trees, let
$\left\\{\sigma_{n}:n\in\mathbb{N}\right\\}$ be an enumeration of
$\mathbb{N}^{<\mathbb{N}}$ with the property that every initial segment of
$\sigma_{n}$ is some $\sigma_{m}$ for $m\leq 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\\}$. Such
$\chi_{S}$ can be viewed as 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. In this topology the collection of trees is a closed (hence
compact) subset of $\left\\{0,1\right\\}^{\mathbb{N}^{<\mathbb{N}}}$.
Moreover, the collection $\mathcal{T}\kern-1.42262ptrees$ is a dense
$\mathcal{G}_{\delta}$ subset. Hence, $\mathcal{T}\kern-1.42262ptrees$ is a
Polish space.

Since the topology on the space of trees was introduced via basic open sets,
we can characterize continuous maps defined on
$\mathcal{T}\kern-1.42262ptrees$ as follows.

######  Fact 6.

Let $Y$ be a topological space. Then a map
$f:\mathcal{T}\kern-1.42262ptrees\to Y$ is continuous if and only if for every
open set $O\subseteq Y$ and every
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ with $f(\mathcal{T})\in O$
there exists $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$.

During our constructions the following maps will prove useful.

######  Definition 7.

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 the length $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.2. Isomorphism and Kakutani Equivalence.

In order to obtain Corollary A from Theorem A, we need to explain why the
isomorphism and Kakutani equivalence relations are analytic subsets of
$\mathcal{E}\times\mathcal{E}$. For $S,T\in\mathcal{E}$, we write $S\cong T$
if $S$ and $T$ are isomorphic, and $S\sim T$ if $S$ and $T$ are Kakutani
equivalent. Then $\\{(S,T)\in\mathcal{E}\times\mathcal{E}:S\cong
T\\}=\\{(S,\phi S\phi^{-1}):S\in\mathcal{E},\phi\in\text{Aut}(\mu)\\}$. Thus
$\\{(S,T)\in\mathcal{E}\times\mathcal{E}:S\cong T\\}$ is the image of
$\mathcal{E}\times\text{Aut}(\mu)$ under the continuous map
$(S,\phi)\mapsto(S,\phi S\phi^{-1})$, and is therefore analytic.

To show that the Kakutani equivalence relation is an analytic subset of
$\mathcal{E}\times\mathcal{E},$ we define, for every Borel set $A\subset[0,1]$
of positive measure, the invertible measure-preserving map
$f^{A}:(A,\mu_{A})\to([0,1],\mu)$ by $f^{A}(x)=\mu(A)^{-1}\mu(A\cap[0,x]).$ As
in the introduction, $\mu_{A}=\mu/\mu(A)$ on $A$, and for $T\in\mathcal{E}$,
$T_{A}$ denotes the first return map of $T$ to $A$. The Borel sets
$\mathcal{B}$ form a Polish space under the metric $d(A,B)=\mu(A\Delta B)$,
and $\\{A\in\mathcal{B}:\mu(A)>0\\}$ is an open subset of $\mathcal{B}.$ Note
that for $A,B\in\mathcal{B}$ with $\mu(A)>0,\mu(B)>0,$ two automorphisms
$T,S\in\mathcal{E}$ are such that $T_{A}$ is isomorphic to $S_{B}$ if and only
if $f^{A}T_{A}(f^{A})^{-1}\cong f^{B}S_{B}(f^{B})^{-1}$, which is true if and
only if there exists $\phi\in$ Aut$(\mu)$ such that

(3.1) $\phi f^{A}T_{A}(f^{A})^{-1}=f^{B}S_{B}(f^{B})^{-1}\phi.$

Let $\mathcal{A}=\\{(T,S,A,B,\phi):T,S\in\mathcal{E},A,B\in\mathcal{B}\text{\
with\ }\mu(A)>0,\mu(B)>0,\phi\in\text{Aut}(\mu)\text{\ such that equation
(\ref{eq:Kak}) holds}\\}.$ Then $\mathcal{A}$ is a Borel subset of
$\mathcal{E}\times\mathcal{E}\times\mathcal{B}\times\mathcal{B}\times$
Aut$(\mu)$ and the projection of $\mathcal{A}$ to the first two coordinates is
$\\{(T,S)\in\mathcal{E}\times\mathcal{E}:T\sim S\\},$ which is therefore
analytic.

###  3.3. The $\overline{f}$ distance

In this subsection, we present some preliminaries regarding a notion of
distance between sequences of symbols introduced by Feldman [Fe76]. This
distance, now called $\overline{f}$, is important in the study of Kakutani
equivalence, and it plays a role analogous to the Hamming metric
$\overline{d}$ in Ornstein’s isomorphism theory.

######  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.$ Then

(3.2) $\begin{array}[]{ll}\overline{f}(a_{1}a_{2}\dots a_{n},b_{1}b_{2}\dots
b_{m})=\hfill\\\ {\displaystyle
1-\frac{2\max\\{|\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}$.

######  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 next result from [GKpp, Lemma 14] 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 9 (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}.$

The following facts from [GKpp] will prove useful for our $\overline{f}$
estimates as well.

######  Fact 10.

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

(3.3) $\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

(3.4) $\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 (3.4) holds.

######  Fact 11.

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

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

######  Fact 12.

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

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

Even though the $\overline{f}$ distance does not satisfy the triangle
inequality for strings of different lengths, Facts 11 and 12 give us an
approximative version of it.

######  Fact 13.

If $x,y,z$ are strings of symbols with $\overline{f}(x,z)<\frac{1}{2}$ and
$\overline{f}(y,z)<\frac{1}{2}$, then

$\displaystyle\overline{f}(x,y)$
$\displaystyle\leq\frac{|x|+|z|}{|x|+|y|}\overline{f}(x,z)+\frac{|z|+|y|}{|x|+|y|}\overline{f}(z,y)$
$\displaystyle\leq\overline{f}(x,z)+\overline{f}(z,y)+8\cdot\overline{f}(x,z)\cdot\overline{f}(z,y).$

###  3.4. Feldman patterns

To construct the symbolic systems in [GKpp], the $n$-words in the construction
sequence are built using specific patterns of blocks. These patterns are
called _Feldman patterns_ since they originate from Feldman’s first example of
an ergodic zero-entropy transformation that is not loosely Bernoulli [Fe76].
They are useful in our construction, because different Feldman patterns cannot
be matched well in $\overline{f}$ even after a finite coding.

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 $B_{r}$ is built with
$N^{2(M+1-r)}$ many so-called _cycles_ : Each cycle winds through all the $N$
building blocks. We refer to $B_{r}$ as the $(T,N,M)$-Feldman pattern of type
$r$.

We will use the following statement from [GKpp, Proposition 41] on the
$\overline{f}$-distance between different $(T,N,M)$-Feldman patterns.

######  Lemma 14.

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 $\overline{B}$ of at least $TN^{2M+2}L$ consecutive symbols from
$B_{j}$ and $B_{k}$, respectively, we have

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

##  4\. Construction of the map $\Upsilon:\mathcal{T}rees\to\mathcal{H}$

For $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees,$ we let
$T=\Psi(\mathcal{T})$ be as in [GKpp]. This automorphism is defined as a left
shift on certain bi-infinite strings of symbols in an alphabet $\Sigma.$ These
strings are concatenations of words in a construction sequence
$\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$, as we recall in Section 5 below. The
map $T$ can also be viewed as an automorphism of $[0,1]$ obtained from cutting
and stacking subintervals of $[0,1]$, where the columns in the $n$th tower all
have the same height and the same width, and there is a one-to-one
correspondence between columns in the $n$th tower and words in
$\mathcal{W}_{n}.$ The levels of a column are labeled with symbols in $\Sigma$
that match the symbols in the corresponding word in $\mathcal{W}_{n}.$ This
defines a partition $\mathcal{P}_{\Sigma}$ of $[0,1]$ that is a generating
partition for $T.$

All of the transformations $U=\Upsilon(\mathcal{T})$ in Theorem B are on the
Lebesgue space $[0,1]\times\\{0,1\\}^{\mathbb{Z}}$ with the product of
Lebesgue measure $\mu$ on $[0,1]$ and $(1/2,1/2)$-Bernoulli measure on
$\\{0,1\\}^{\mathbb{Z}}$.

The cutting and stacking construction for realizing $T=\Psi(\mathcal{T})$ on
$[0,1]$ is done in [GKpp] in such a way that
$\Psi:\mathcal{T}\kern-1.42262ptrees\to\operatorname{Aut}([0,1],\mu)$ is
continuous. The automorphism $U=\Upsilon(\mathcal{T})$ is the direct product
of $\Psi(\mathcal{T})$ and a $(1/2,1/2)$-Bernoulli shift $\mathbb{B}$. We take
the set $A$ in Part 2 of Theorem B to be

(4.1)
$A=[0,1]\times\left\\{(\upsilon_{i})_{i\in\mathbb{Z}}\in\\{0,1\\}^{\mathbb{Z}}\mathrel{}\middle|\mathrel{}\upsilon_{0}=0\right\\}.$

###### Proof of Part 2 (c) of Theorem B.

The return time to $A$ is a geometrically distributed random variable, and
according to Lemma 1 of [OS77], this implies that $U_{A}$ is isomorphic to a
skew product to which Meilijson’s Theorem [Me74] applies. Therefore $U_{A}$ is
a $K$-automorphism. Actually the hypotheses in [Me74] are not satisfied, but,
as was observed in [OS77], the proof in [Me74] can be generalized to cover the
case at hand. In fact, the first proposition in [Ge97], which is essentially
contained in [Me74] and [Ho88], implies exactly what we need. ∎

###### Proof of Part 2 (d) of Theorem B.

Suppose that $\mathcal{T}$ has an infinite branch. From [GKpp, section 5] we
know that $T=\Psi(\mathcal{T})$ and $T^{-1}=\Psi(\mathcal{T})^{-1}$ are
isomorphic. Then by taking the product of this isomorphism and the identity on
the $\\{0,1\\}^{\mathbb{Z}}$ factor, we obtain an isomorphism $\phi$ between
$U=\Upsilon(\mathcal{T})$ and $U^{-1}=\Upsilon(\mathcal{T})^{-1}$ such that
$\phi(A)=A$, where $A$ is as in (4.1). ∎

##  5\. Review of Construction of map
$\Psi:\mathcal{T}\kern-1.42262ptrees\to\mathcal{E}$

The proof of the anti-classification results in [GKpp] is based on the
construction of a continuous 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.

In this section we collect important properties of the construction of $\Psi$
in sections 7–8 of [GKpp].

The transformation $T=\Psi(\mathcal{T})$ can be obtained from a cutting and
stacking construction on $[0,1]$ (as mentioned in Section 4) or from a
construction of a symbolic left shift $(\mathbb{K},\operatorname{sh})$ that we
will abbreviate by $\mathbb{K}$. When taking the second approach, for each
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$, the symbolic system is built
using a construction sequence
$\left\\{\mathcal{W}_{n}\left(\mathcal{T}\right)\mathrel{}\middle|\mathrel{}\sigma_{n}\in\mathcal{T}\right\\}$
in a basic alphabet $\Sigma$ of cardinality $2^{12}$, where for each
$n\in\mathbb{N}$ with $\sigma_{n}\in\mathcal{T}$ the set
$\mathcal{W}_{n}=\mathcal{W}_{n}(\mathcal{T})$ of allowed $n$-words depends
only on $\mathcal{T}\cap\left\\{\sigma_{m}:m\leq n\right\\}$. Then

$\begin{split}\mathbb{K}=\left\\{(\sigma_{j})_{j\in\mathbb{Z}}\in\Sigma^{\mathbb{Z}}\mathrel{}\middle|\mathrel{}\forall
n\in\mathbb{Z}^{+},(\sigma_{j})_{j\in\mathbb{Z}}\text{ is a bi-infinite
concatenation of $n$-words}\right\\}.\end{split}$

The inverse $T^{-1}$ could be viewed as a right shift on $\mathbb{K}$. Instead
we will always regard it as a left shift on $\operatorname{rev}(\mathbb{K})$.
Here, we write $\operatorname{rev}(w)$ for the reverse string of a finite or
infinite string $w$. In particular, if $x$ is in $\mathbb{K}$ we define
$\operatorname{rev}(x)$ by setting $\operatorname{rev}(x)(k)=x(-k)$. Then for
a collection $W$ of words, $\operatorname{rev}(W)$ is the collection of
reverses of words in $W$ and
$\left\\{\operatorname{rev}\left(\mathcal{W}_{n}\left(\mathcal{T}\right)\right)\mathrel{}\middle|\mathrel{}\sigma_{n}\in\mathcal{T}\right\\}$
is a construction sequence for $\operatorname{rev}(\mathbb{K})$.

The structure of the tree $\mathcal{T}\subset\mathbb{N}^{\mathbb{N}}$ is also
used to build a sequence of groups $G_{s}(\mathcal{T})$ as follows. Here, the
index $s$ indicates _level_ $s$ of $\mathcal{T}$, which consists of those
elements of $\mathcal{T}$ of length $s$. We define $G_{0}(\mathcal{T})$ to be
the trivial group and assign to each level $s>0$ a so-called _group of
involutions_

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

Each $(\mathbb{Z}_{2})_{\tau}$ is a copy of $\mathbb{Z}_{2}$, and we let
$g_{\tau}$ denote its generator. We have a well-defined notion of _parity_ for
elements in such a group of involutions: an element is called _even_ if it can
be written as the sum of an even number of generators. Otherwise, it is called
_odd_.

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 $g_{\tau}$ to $g_{\sigma}$ where $\sigma$ is the initial segment of
$\tau$ with $lh(\sigma)=s$. The map $\rho_{t,0}$ is the trivial homomorphism
$\rho_{t,0}:G_{t}(\mathcal{T})\to G_{0}(\mathcal{T})=\\{0\\}$. A tree
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ has an infinite branch if and
only if there is an infinite sequence
$\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$.

During the construction one uses the following finite approximations: For
every $n\in\mathbb{N}$ 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\\{\left(\mathbb{Z}_{2}\right)_{\tau}\mathrel{}\middle|\mathrel{}\tau\in\mathcal{T}\cap\left\\{\sigma_{m}:m\leq
n\right\\},\,lh(\tau)=s\right\\}.$

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.

In the following, we simplify notation by reindexing
$\left\\{\mathcal{W}_{n}\left(\mathcal{T}\right)\mathrel{}\middle|\mathrel{}\sigma_{n}\in\mathcal{T}\right\\}$
and
$\left\\{G_{s}^{n}\left(\mathcal{T}\right)\mathrel{}\middle|\mathrel{}\sigma_{n}\in\mathcal{T}\right\\}$
as $\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$ and
$\\{G^{n}_{s}\\}_{n\in\mathbb{N}}$, respectively. To describe their
construction, let $\left(\epsilon_{n}\right)_{n\in\mathbb{N}}$ be a decreasing
sequence of positive numbers such that

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

During the course of construction one also defines a fast growing sequence of
positive integers $\left(e(n)\right)_{n\in\mathbb{N}}$ and an increasing
sequence of prime numbers $(\mathfrak{p}_{n})_{n\in\mathbb{N}}$ (see equations
(8.5) and (8.7) in [GKpp]).

We now collect important properties of the construction sequence
$\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$. We start by setting
$\mathcal{W}_{0}=\Sigma$.

  1. (E1)

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

  2. (E2)

There are $f_{n},k_{n}\in\mathbb{Z}^{+}$ such that every word in
$\mathcal{W}_{n+1}$ is built by concatenating $k_{n}$ words in
$\mathcal{W}_{n}$ and such that every word in $\mathcal{W}_{n}$ occurs in each
word of $\mathcal{W}_{n+1}$ exactly $f_{n}$ times. The number $f_{n}$ is a
product of $\mathfrak{p}_{n}^{2}$ and powers of $2$. Clearly, we have
$k_{n}=f_{n}|\mathcal{W}_{n}|$.

  3. (E3)

If $w=w_{1}\dots w_{k_{n}}\in\mathcal{W}_{n+1}$ and
$w^{\prime}=w_{1}^{\prime}\dots w_{k_{n}}^{\prime}\in\mathcal{W}_{n+1}$, where
$w_{i},w_{i}^{\prime}\in\mathcal{W}_{n}$, then for any
$k\geq\lfloor\frac{k_{n}}{2}\rfloor$ and $1\leq i\leq k_{n}-k$, we have
$w_{i+1}\dots w_{i+k}\neq w_{1}^{\prime}\dots w_{k}^{\prime}$.

######  Remark.

In particular, these specifications say that
$\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$ is a uniquely readable and strongly
uniform construction sequence as defined in [FW19a, section 3.3]. Hence, the
corresponding symbolic system $\mathbb{K}$ has a unique non-atomic ergodic
shift-invariant measure by [FW19a, Lemma 11].

For each $s\leq s(n)$, there is an equivalence relation $\mathcal{Q}_{s}^{n}$
on $\mathcal{W}_{n}$ satisfying the following specifications. 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.

  1. (Q4)

Suppose that $n=M(s)$ for some $s\in\mathbb{Z}^{+}$. 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, where each $w_{n,i}$ is a
concatenation of $(n-1)$-words. 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}$.

  2. (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)}$.111Given an equivalence relation $\mathcal{Q}$ on a
set $X$ 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}$ with respect to
$\mathcal{Q}$ for all $i=0,\dots,n-1$.

  3. (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.222Given two equivalence relations $\mathcal{Q}$ and $\mathcal{R}$ on
a set $X$ we say that $\mathcal{R}$ _refines_ $\mathcal{Q}$ if considered as
sets of ordered pairs we have $\mathcal{R}\subseteq\mathcal{Q}$.

Each equivalence relation $\mathcal{Q}_{s}^{n}$ will induce an equivalence
relation on $\operatorname{rev}(\mathcal{W}_{n})$, which we will also call
$\mathcal{Q}_{s}^{n}$, as follows:
$\operatorname{rev}(w),\operatorname{rev}(w^{\prime})\in\operatorname{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}$.

######  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.

In [FRW11, section 5] and [GKpp, section 4.2.2] the equivalence relations
$\mathcal{Q}_{s}$ are used to define a canonical sequence of factors
$\mathbb{K}_{s}$ and $\operatorname{rev}(\mathbb{K}_{s})$ with factor maps
$\pi_{s}:\mathbb{K}\to\mathbb{K}_{s}$ and
$\pi_{s^{\prime},s}:\mathbb{K}_{s^{\prime}}\to\mathbb{K}_{s}$ for all
$s^{\prime}>s$.

We now list specifications on actions by the groups of involutions
$G^{n}_{s}$.

  1. (A7)

$G_{s}^{n}$ acts freely on $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ and the
$G_{s}^{n}$ action is subordinate333Suppose $\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}}$. 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}$.

  2. (A8)

Suppose $n>M(s)$. We view $G_{s}^{n}=G_{s}^{n-1}\oplus H$. Then the action of
$G_{s}^{n-1}$ on $\mathcal{W}_{n-1}/\mathcal{Q}_{s}^{n-1}$ is extended to an
action on $\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ by the skew diagonal
action.444If $G$ is a group of involutions with a collection of canonical
generators that acts on $X$, then the canonical _skew diagonal action_ of $G$
on $X^{n}$ is defined by  $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}$ In particular,
$\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ is closed under the skew diagonal action
by $G_{s}^{n-1}$.

######  Remark 15.

Let $s\in\mathbb{Z}^{+}$ and $g\in G_{s}^{m}$ for some $m\geq M(s)$. Suppose
that $g$ has odd parity. Since $g$ acts on
$\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ by the skew-diagonal action by (A8), it
induces for all $n>m$ a map
$\eta_{g}:\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}\to\operatorname{rev}(\mathcal{W}_{n})/\mathcal{Q}^{n}_{s}$
by the diagonal action. Then $g$ yields a shift-equivariant isomorphism
$\mathbb{K}_{s}\to\operatorname{rev}(\mathbb{K}_{s})$ that we denote by
$\eta_{g}$ as well (see [GKpp, Lemma 37]).

In case that $\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ has an infinite
branch, then there is an infinite sequence
$\left(g_{s}\right)_{s\in\mathbb{Z}^{+}}$ of canonical generators $g_{s}\in
G_{s}\left(\mathcal{T}\right)$ with $\rho_{t,s}\left(g_{t}\right)=g_{s}$ for
$t>s>0$. Hereby we obtain a coherent sequence of isomorphisms $\eta_{g_{s}}$
between $\mathbb{K}_{s}$ and $\operatorname{rev}(\mathbb{K}_{s})$ satisfying
$\pi_{s+1,s}\circ\eta_{g_{s+1}}=\eta_{g_{s}}\circ\pi_{s+1,s}$ for every
$s\in\mathbb{N}$ by (A7). This yields an isomorphism between $\mathbb{K}$ and
$\operatorname{rev}(\mathbb{K})\cong\mathbb{K}^{-1}$ (see [GKpp, section 5]
for details).

To exclude Kakutani equivalence between $\mathbb{K}$ and
$\operatorname{rev}(\mathbb{K})$ for
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ without an infinite branch,
$n$-words are constructed by substituting Feldman patterns of $s$-equivalence
classes of $(n-1)$-words into Feldman patterns of $(s-1)$-equivalence classes
of $(n-1)$-words. In this iteration of substitution steps one determines
parameters $T_{s},M_{s}$ recursively and proceeds as follows:

  1. (1)

We divide the $2^{4e(n-1)}$ many $s$-classes contained in any
$[A]_{s-1}\in\mathcal{W}_{n-1}/\mathcal{Q}^{n-1}_{s-1}$ into $2^{t_{s}}$
tuples of the form
$\left([A_{1}]_{s},[A_{2}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ such that each
tuple intersects each $\ker(\rho_{s,s-1}^{(n-1)})$ orbit exactly once and the
tuples are images of each other under the action by
$\ker(\rho_{s,s-1}^{(n-1)})$. Here, $N_{s+1}=2^{4e(n-1)-t_{s}}$ with
$t_{s}\in\mathbb{N}$ such that

$2^{t_{s}}=|\ker(\rho_{s,s-1}^{(n-1)})|.$

We note that for $i\neq j$ the $G^{n-1}_{s}$ orbit of $[A_{i}]_{s}$ does not
intersect the $G^{n-1}_{s}$ orbit of $[A_{j}]_{s}$.

  2. (2)

We choose a set $\Gamma_{s-1}\subset\mathcal{W}_{n}/\mathcal{Q}^{n}_{s-1}$
that intersects each orbit of the skew-diagonal action by the group
$\operatorname{im}(\rho_{s,s-1}^{(n-1)})$ exactly once.

  3. (3)

We construct a collection of $M_{s+1}$ different
$\left(T_{s+1},N_{s+1},M_{s+1}\right)$-Feldman patterns, where the tuple of
building blocks is to be determined in step (6).

  4. (4)

By the induction assumption of the substitution step, each
$[w]_{s-1}\in\Gamma_{s-1}$ can be decomposed into a concatenation of different
$(T_{s},N_{s},M_{s})$-Feldman patterns.

  5. (5)

Let $K_{s}\in\mathbb{Z}^{+}$ such that
$K_{s}|\ker(\rho_{s,s-1}^{(n-1)})|=2^{4e(n)}$. For each
$[w]_{s-1}\in\Gamma_{s-1}$ we choose $K_{s}$ many different concatenations of
$\left(T_{s+1},N_{s+1},M_{s+1}\right)$-Feldman patterns. We enumerate these
choices by $\left\\{1,\dots,K_{s}\right\\}$.

  6. (6)

Let $[w]_{s-1}\in\Gamma_{s-1}$ and $j\in\left\\{1,\dots,K_{s}\right\\}$. We
decompose $[w]_{s-1}$ into repetitions $[A]^{T_{s}}_{s-1}$ of single classes.
For the $i$-th such repetition we substitute the $i$-th Feldman pattern
occurring in $j$ using one of the subordinate building tuples from step (1).
In fact, the actual tuple is chosen by cycling through the possible ones. Let
$\Omega^{\prime}_{s}$ be the collection of such strings obtained for all
$[w]_{s-1}\in\Gamma_{s-1}$ and $j\in\\{1,\dots,K_{s}\\}$.

  7. (7)

Then we let
$\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}=G^{n-1}_{s}\Omega^{\prime}_{s}$. In
particular, $\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ is closed under the skew-
diagonal action by $G^{n-1}_{s}$ and each
$[w]_{s-1}\in\mathcal{W}_{n}/\mathcal{Q}^{n}_{s-1}$ contains $2^{4e(n)}$ many
$\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ classes by the choice of $K_{s}$ in step
(5).

  8. (8)

By (6) and (7), each element in $\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ is a
concatenation of different $(T_{s+1},N_{s+1},M_{s+1})$-Feldman patterns, the
so-called $s$-Feldman patterns. We will call the sequence of $s$-pattern types
that appear in an element of $\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ its
$s$-pattern structure. We note that a particular type of
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern can occur in different elements
$[w]_{s}$, $[w^{\prime}]_{s}\in\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ only if
$[w]_{s}=g[w^{\prime}]_{s}$ for some nontrivial $g\in G^{n-1}_{s}$. In this
case the building tuples of that particular type of
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern are disjoint from each other by
step (1).

By this construction in [GKpp, sections 7-8] we obtain the following statement
on $\overline{f}$-distances.

######  Lemma 16 ([GKpp], Proposition 56).

For every $s\in\mathbb{Z}^{+}$ there is $0<\alpha_{s}<\frac{1}{8}$ such that
for every $n\geq M(s)$ we have

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

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

The sequence $(\alpha_{s})_{s\in\mathbb{N}}$ is decreasing. Here, the numbers
$R_{n}$ are determined inductively [GKpp, eq. (8.6)]. Even though
$R_{n}\to\infty$, strings of length $h_{n}/R_{n}$ are long enough to contain
many Feldman patterns of equivalence classes of $(n-1)$-words.

Lemma 16 also allows us to show in the following lemma that a substantial
string of consecutive symbols from an $s$-pattern with the building tuple
traversed in reverse order, is $\overline{f}$-apart from any string in
$\mathbb{K}$. We use this statement in the proof of Lemma 19, where we adapt
methods from [ORW82, chapter 13] to exclude the existence of good
$\overline{f}$-codes between Feldman patterns of different types.

######  Lemma 17.

Suppose that the $(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern of type $r$
appears with building blocks
$\left([A_{1}]_{s},[A_{2}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ in some
$[w]_{s}\in\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$. Let $F$ be a finite string of
symbols in $\Sigma$ of length $|F|\geq
2^{e(n-1)}T_{s+1}N^{2M_{s+1}+2}_{s+1}h_{n-1}$ such that $F$ is part of the
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern of type $r$ with building blocks
$\left([A_{N_{s+1}}]_{s},\dots,[A_{1}]_{s}\right)$ (that is, the building
tuple is traversed in opposite order). Then

(5.3) $\overline{f}(F,D)>\frac{\alpha_{s}}{2}$

for any finite string $D$ in $\mathbb{K}$.

###### Proof.

Assume that there is a string $D$ in $\mathbb{K}$ with
$\overline{f}(F,D)\leq\frac{\alpha_{s}}{2}$ and let $\pi$ be a best possible
match between $F$ and $D$. Then

(5.4)
$1-3\frac{\alpha_{s}}{2}<\frac{1-\frac{\alpha_{s}}{2}}{1+\frac{\alpha_{s}}{2}}\leq\frac{|D|}{|F|}\leq\frac{1+\frac{\alpha_{s}}{2}}{1-\frac{\alpha_{s}}{2}}<1+3\frac{\alpha_{s}}{2}$

by Fact 12. In particular, $D$ has to lie within at most three $s$-patterns
and we decompose $D$ into $D=D_{1}D_{2}D_{3}$, where the substrings $D_{i}$
belong to different $(T_{s+1},N_{s+1},M_{s+1})$-patterns. Furthermore, for
$i=1,2,3,$ let $F_{i}$ denote the substring of $F$ matched to $D_{i}$ under
$\pi$. (Some of the substrings $D_{i},F_{i}$ could be empty.)

If $\overline{f}(F_{i},D_{i})>\frac{\alpha_{s}}{2}$, then we stop examining
this case.

Otherwise, we have
$\frac{1}{2}<1-3\frac{\alpha_{s}}{2}<\frac{|D_{i}|}{|F_{i}|}<1+3\frac{\alpha_{s}}{2}<2$
by the same estimate as in (5.4). If
$|D_{i}|<2T_{s+1}N^{2M_{s+1}+2}_{s+1}h_{n-1}$, then we ignore the strings
$D_{i}$ and $F_{i}$ in the following considerations. This might increase the
$\overline{f}$-distance by at most $8/2^{e(n-1)}$ by Fact 10. If $|D_{i}|\geq
2T_{s+1}N^{2M_{s+1}+2}_{s+1}h_{n-1}$, then $|F_{i}|\geq
T_{s+1}N^{2M_{s+1}+2}_{s+1}h_{n-1}$. In case that the
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern types of $D_{i}$ and $F_{i}$ are
different from each other, these lengths allow the application of Lemma 14 and
we obtain

$\overline{f}(F_{i},D_{i})>\alpha_{s}-\frac{4}{2^{2e(n-1)-0.5t_{s}}}-\frac{1}{R_{n-1}}.$

In the next step, we investigate the case that the
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern types of $D_{i}$ and $F_{i}$ agree
with each other, that is, the type is $r$. We recall from step (8) in the
substitution process that in the construction of
$\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}$ the only other occurrences of that
Feldman pattern of type $r$ come with other tuples of building blocks that are
disjoint from $\left([A_{1}]_{s},[A_{2}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$.
In both possible scenarios (either disjoint tuples of building blocks or the
building blocks are traversed in opposite directions), we can apply the symbol
by block replacement lemma in Lemma 9 and obtain

$\overline{f}(F_{i},D_{i})>\alpha_{s}\cdot\left(1-\frac{1}{2^{4e(n-1)-t_{s}}}\right)-\frac{1}{R_{n-1}}.$

Altogether, we conclude (5.3) by Fact 11. ∎

The repetitions of $s$-classes in $s$-Feldman patterns and the choices of
building tuples in step (6) guarantee the following statement on uniformity of
occurrences of substitution instances (see [GKpp, Lemma 46] and [GKpp, Remark
52]).

######  Remark 18.

Let $w\in\mathcal{W}_{n}$ and $[P_{n-1}]_{s}$ be a
$\left(T_{s+1},N_{s+1},M_{s+1}\right)$-Feldman pattern in $[w]_{s}$ with
building blocks from the tuple
$\left([A_{1}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ in
$\mathcal{W}_{n-1}/\mathcal{Q}_{s}^{n-1}$. Then for every $i=1,\dots,N_{s+1}$
each $a_{i,j}\in\mathcal{W}_{n-1}$ with $[a_{i,j}]_{s}=[A_{i}]_{s}$ is
substituted the same number of times into each occurrence of
$[A_{i}]_{s}^{T_{s+1}\cdot 2^{t_{s+1}}}$ in $[P_{n-1}]_{s}$ within $w$.

We end our review of the constructions in [GKpp] with the observation that at
each stage we can choose the number of concatenations of different Feldman-
patterns arbitrarily large. This allows us to produce sufficiently many
substitution instances of each $n$-word to guarantee requirement (R9) below.

##  6\. Completion of Proofs of Theorems A and B

###  6.1. Shift space description of the process

As described in Section 5, the transformation $T$ was constructed as a
symbolic system $\mathbb{K}$ using a construction sequence
$\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$. Given this construction sequence,
the transformation $U=T\times\mathbb{B}=\Upsilon(\mathcal{T})$ is isomorphic
to the left shift, $\operatorname{sh}$, on a sequence space that we now
describe. Let

$\begin{array}[]{ccl}\mathbb{S}&=&\\{(\sigma_{j},\upsilon_{j})_{j\in\mathbb{Z}}\in(\Sigma\times\\{0,1\\})^{\mathbb{Z}}\,:\text{
for\ every\ }n\in\mathbb{Z}^{+},(\sigma_{j})_{j\in\mathbb{Z}}\text{ is a bi-
infinite }\\\ &&\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ concatenation of $n$-words from
$\mathcal{W}_{n}$}\\},\end{array}$

with the topology induced from the product topology on
$(\Sigma\times\\{0,1\\})^{\mathbb{Z}}$. We abbreviate
$(\mathbb{S},\operatorname{sh})$ by $\mathbb{S}$. Define for each
$n\in\mathbb{N}$ the set

$\mathcal{V}_{n}=\left\\{(w,\upsilon)\mathrel{}\middle|\mathrel{}w\in\mathcal{W}_{n}\text{
and }\upsilon\in\\{0,1\\}^{h_{n}}\right\\}.$

Since the construction sequence $\\{\mathcal{W}_{n}\\}_{n\in\mathbb{N}}$ is
uniquely readable and strongly uniform, the symbolic system $\mathbb{K}$ has a
unique non-atomic shift-invariant measure $\nu^{\prime}$. By putting

$\nu\left(\langle(w,\upsilon)\rangle\right)=\frac{\nu^{\prime}(\langle
w\rangle)}{2^{h_{n}}}$

for each cylinder set $\langle(w,\upsilon)\rangle$ with
$(w,\upsilon)\in\mathcal{V}_{n}$, we define a $\operatorname{sh}$-invariant
measure $\nu$ on the Borel subsets of $\mathbb{S}$ which is the same as the
product of $\nu^{\prime}$ and the $(1/2,1/2)$-Bernoulli measure.

We will often refer to the sequences $\upsilon\in\\{0,1\\}^{h_{n}}$ as
_shadings_ of $n$-words. That is, for the pair
$(w,\upsilon)\in\mathcal{V}_{n}$ we regard the $w_{j}$ entry in $w$ as
_shaded_ if $\upsilon_{j}=1$ and _unshaded_ if $\upsilon_{j}=0$.

As mentioned at the end of Section 5 we can concatenate sufficiently many
Feldman patterns to produce a large number $f_{n}$ of occurrences of each
$n$-word $w_{i}$ in each $(n+1)$-word $w$. Then the law of large numbers
allows us to obtain the following “almost uniformity” of shadings of $w_{i}$
within shadings of $w$.

  1. (R9)

For $w\in\mathcal{W}_{n+1}$ a proportion of at least $\frac{999}{1000}$ of the
shadings $\upsilon\in\\{0,1\\}^{h_{n+1}}$ are such that for all
$w_{i}\in\mathcal{W}_{n}$ and $\upsilon_{j}\in\\{0,1\\}^{h_{n}}$ the number
$R_{i,j}$ of times the shading $\upsilon_{j}$ appears with $w_{i}$ satisfies

(6.1)
$\left\lvert\frac{R_{i,j}}{f_{n}}-\frac{1}{2^{h_{n}}}\right\rvert<\frac{1}{2\cdot
2^{h_{n}}}.$

###  6.2. Proof of Non-Kakutani Equivalence

Since $\mathbb{S}\cong\Upsilon(\mathcal{T})$ has positive entropy, any
Kakutani equivalence between $\mathbb{S}$ and
$\mathbb{S}^{-1}\cong\operatorname{rev}(\mathbb{S})$ would have to be an even
equivalence.555Two transformations $S:(X,\mu)\to(X,\mu)$ and
$T:(Y,\nu)\to(Y,\nu)$ are said to be _evenly equivalent_ if there are subsets
$A\subseteq X$ and $B\subseteq Y$ of equal measure $\mu(A)=\nu(B)>0$ such that
$S_{A}$ and $T_{B}$ are isomorphic to each other. Thus, to prove part (b) in
Theorem B it remains to show that under the assumption that the tree
$\mathcal{T}\in\mathcal{T}\kern-1.42262ptrees$ does not have an infinite
branch, $\mathbb{S}$ is not evenly equivalent to
$\operatorname{rev}(\mathbb{S})$. A generalization of Proposition 3.2 in
[ORW82, p. 92] given in [GKpp, section 9.2] guarantees the existence of a
consistent sequence of well-approximating finite codes in $\overline{f}$
between two evenly equivalent transformations (see properties (C1) and (C2)
below for details). To exclude the existence of such a sequence of finite
codes from $\mathbb{S}$ to $\operatorname{rev}(\mathbb{S})$ in case
$\mathcal{T}$ does not have an infinite branch, we use the method of [ORW82,
chapter 13] and properties of the construction from [GKpp]. This generalizes
section 9.3 of [GKpp].

Here, a _code_ of length $2K+1$ is a function
$\phi:(\Sigma\times\\{0,1\\})^{\mathbb{Z}\cap[-K,K]}\to\Sigma\times\\{0,1\\}$.
Given such a code $\phi$ of length $2K+1$ the _stationary code_ $\bar{\phi}$
on $(\Sigma\times\\{0,1\\})^{\mathbb{Z}}$ determined by $\phi$ is defined as
$\bar{\phi}(s)$ for any $s\in(\Sigma\times\\{0,1\\})^{\mathbb{Z}}$, where for
any $l\in\mathbb{Z}$,

$\bar{\phi}(s)(l)=\phi\left(s\upharpoonright[l-K,l+K]\right).$

In this setting, $\bar{\phi}(s)\upharpoonright[-N,N]$ denotes the string of
symbols

$\bar{\phi}(s)(-N)\,\bar{\phi}(s)(-N+1)\,\dots\,\bar{\phi}(s)(N-1)\,\bar{\phi}(s)(N)$

in $(\Sigma\times\\{0,1\\})^{2N+1}$.

######  Remark.

There is an ambiguity in applying a code $\phi$ of length $2K+1$ to blocks of
the form $s\upharpoonright[a,b]$: It does not make sense to apply it to the
initial string $s\upharpoonright[a,a+K-1]$ or the end string
$s\upharpoonright[b-K+1,b]$. However, if $b-a$ is large with respect to the
code length $2K+1$, we can fill in $\phi(s)\upharpoonright[a,a+K-1]$ and
$\phi(s)\upharpoonright[b-K+1,b]$ arbitrarily and it makes a negligible
difference to the $\overline{f}$ distance. We refer to the general phenomenon
of ambiguity or disagreement at the beginning and end of strings as _end
effects_. Strings are always chosen long enough such that end effects can be
neglected in our $\overline{f}$ estimates.

We show in Lemma 20 that a well-approximating finite code $\phi$ can be
identified with an element of the group action. A key step in the proof is
Lemma 19. Here, we show for substantial substrings $E$ and $\overline{E}$ of
$s$-Feldman patterns $P$ and $\overline{P}$ of different types that there is a
one-to-one correspondence between shadings $\upsilon\in\\{0,1\\}^{|E|}$ such
that
$\overline{f}\left(\phi(E,\upsilon),(\overline{E},\overline{\upsilon})\right)$
is small and shadings $\upsilon^{\prime}\in\\{0,1\\}^{|E|}$ such that
$\phi(E,\upsilon^{\prime})$ is $\overline{f}$-apart from any substring in
$\operatorname{rev}(\mathbb{S})$. This says that the code cannot work well on
at least half of the shadings. To show the existence of such a shading
$\upsilon^{\prime}$ we decompose $\overline{E}$ into complete cycles
$\overline{C}_{k}$ of its $s$-Feldman pattern $\overline{P}$ and look at the
string $C_{k}$ with its associated shading $\upsilon_{k}$ whose image under
the code $\phi$ is matched to such a cycle $\overline{C}_{k}$ under a best
possible $\overline{f}$-match. We then build a reshuffling
$\upsilon^{\prime}_{k}$ of the shading $\upsilon_{k}$ such that
$\phi(C_{k},\upsilon^{\prime}_{k})$ is $\overline{f}$-close to a cycle where
the $s$-classes of words are traversed in the opposite direction. Such a
string is $\overline{f}$-apart from any string in
$\operatorname{rev}(\mathbb{S})$ by Lemma 17. To build such a reshuffling it
is crucial that all substitution instances of the $s$-classes in the complete
cycle occur the same number of times by Remark 18. We visualize the building
of reshufflings in Figures 6.1 and 6.2.

######  Lemma 19.

Let $E$ and $\overline{E}$ be strings of symbols in $\Sigma$ that are
substitution instances of $s$-Feldman patterns $P$ and $\overline{P}$ of
$\mathcal{Q}_{s}^{n-1}$ equivalence classes, respectively, where $n-1\geq
M(s)$. Assume $P$ and $\overline{P}$ are different types of $s$-Feldman
patterns, and $E$ and $\overline{E}$ both have length at least
$\frac{|P|}{2^{2e(n-1)}}$. Suppose $\phi$ is a code of length $K$, where
$h_{n-1}$ is large compared to $K$. Then there is a one-to-one map from
shadings $\upsilon$ in $\\{0,1\\}^{|E|}$ such that

$\overline{f}\left(\phi(E,\upsilon),(\overline{E},\overline{\upsilon})\right)<\frac{\alpha^{2}_{s}}{2000}$

for _some_ $\overline{\upsilon}\in\\{0,1\\}^{|\overline{E}|}$ to shadings
$\upsilon^{\prime}\in\\{0,1\\}^{|E|}$ such that

$\overline{f}\left(\phi(E,\upsilon^{\prime}),(\overline{D},\overline{u})\right)>\frac{\alpha_{s}}{20}$

for _all_ strings $(\overline{D},\overline{u})$ in
$\operatorname{rev}(\mathbb{S})$.

###### Proof.

Recall from the construction in [GKpp] that the $s$-Feldman patterns are
$(T_{s+1},N_{s+1},M_{s+1})$-Feldman patterns with $N_{s+1}=2^{4e(n-1)-t_{s}}$.
Accordingly the length of $s$-patterns is
$|P|=T_{s+1}N^{2M_{s+1}+3}_{s+1}h_{n-1}$ and the maximum cycle length is
$T_{s+1}N^{2M_{s+1}+1}_{s+1}h_{n-1}$. In particular, there are at least
$2^{4e(n-1)}$ complete cycles of $P$ and $\overline{P}$ in $E$ and
$\overline{E}$, respectively. We delete partial cycles of $\overline{P}$ which
might increase the $\overline{f}$ distance by at most $\frac{2}{2^{4e(n-1)}}$.

We denote the tuple of building blocks for $[P]_{s}$ by
$\left([A_{1}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ and the tuple of building
blocks for $[\overline{P}]_{s}$ by
$\left([\overline{A}_{1}]_{s},\dots,[\overline{A}_{N_{s+1}}]_{s}\right)$.
Moreover, let $r$ and $\overline{r}$ denote the types of $s$-Feldman pattern
of $P$ and $\overline{P}$, respectively. We look at cycles $\overline{C}_{k}$
in $\overline{P}$. Then we decompose such a cycle $\overline{C}_{k}$ into the
substitution instances $\overline{C}_{k,i}$ of maximum consecutive repetitions
$[\overline{A}_{i}]^{T_{s+1}N^{2\overline{r}}_{s+1}}_{s}$ of the same
$s$-class. Let $C_{k}$ and $C_{k,i}$ denote the strings in $P$ matched under a
best possible $\overline{f}$-match to $\overline{C}_{k}$ and
$\overline{C}_{k,i}$, respectively. For a proportion of at least
$1-\frac{\alpha_{s}}{10}$ of the indices in $E$ we have that they lie in some
$C_{k,i}$ satisfying

(6.2)
$1-3\frac{\alpha_{s}}{80}<\frac{1-\frac{\alpha_{s}}{80}}{1+\frac{\alpha_{s}}{80}}\leq\frac{|C_{k,i}|}{|\overline{C}_{k,i}|}\leq\frac{1+\frac{\alpha_{s}}{80}}{1-\frac{\alpha_{s}}{80}}<1+3\frac{\alpha_{s}}{80}$

by Fact 12. We ignore those indices that lie in or are matched to some
$C_{k,i}$ violating inequality (6.2). This might increase the
$\overline{f}$-distance by at most $\frac{\alpha_{s}}{4}$. Now we distinguish
between the two possible cases $r<\overline{r}$ and $r>\overline{r}$.

  * •

In the first instance, let $r<\overline{r}$, that is, the cycle length
$T_{s+1}N^{2r+1}_{s+1}h_{n-1}$ in $P$ is smaller than the length
$|\overline{C}_{k,i}|=T_{s+1}N^{2\overline{r}}_{s+1}h_{n-1}$ of maximum
repetition of the same $s$-class in $\overline{P}$. Since
$|C_{k,i}|>(1-3\frac{\alpha_{s}}{80})\cdot|\overline{C}_{k,i}|$ by (6.2),
there are at least
$\lfloor(1-3\frac{\alpha_{s}}{80})N^{2(\overline{r}-r)-1}_{s+1}-2\rfloor$
complete cycles in each $C_{k,i}$. We reduce each $C_{k,i}$ to this repetition
of $\lfloor(1-3\frac{\alpha_{s}}{80})N^{2(\overline{r}-r)-1}_{s+1}-2\rfloor$
many cycles and delete the other symbols. By (6.2) this might increase the
$\overline{f}$ distance by at most
$\frac{12\alpha_{s}}{80}+\frac{5}{N_{s+1}}$. By Remark 18 each $C_{k,i}$ now
contains each substitution instance of each
$\left([A_{1}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ the same number of times.
Furthermore, let $\upsilon_{k,i}$ denote the shading of $C_{k,i}$. Since every
$C_{k,i}$ contains each substitution instance of each
$\left([A_{1}]_{s},\dots,[A_{N_{s+1}}]_{s}\right)$ the same number of times,
there is a reshuffling $\upsilon^{\prime}_{k,i}$ of the shading
$\upsilon_{k,N_{s+1}-i}$ such that each substitution instance on
$(C_{k,i},\upsilon^{\prime}_{k,i})$ is paired with the same shadings as on
$(C_{k,N_{s+1}-i},\upsilon_{k,N_{s+1}-i})$. In fact, we build this reshuffling
as follows: if $\nu\in\\{0,1\\}^{h_{n-1}}$ is the $\ell$-th shading occurring
with a substitution instance $w\in\mathcal{W}_{n-1}$ in
$(C_{k,N_{s+1}-i},\upsilon_{k,N_{s+1}-i})$, then in $\upsilon^{\prime}_{k,i}$
we take $\nu$ to be the shading associated with the $\ell$-th occurrence of
that substitution instance $w$ in $C_{k,i}$. In particular, the images
$\phi(C_{k,i},\upsilon^{\prime}_{k,i})$ and
$\phi\left(C_{k,N_{s+1}-i},\upsilon_{k,N_{s+1}-i}\right)$ are close to each
other in $\overline{f}$.

Figure 6.1. Illustration of the reshuffling procedure in case of Feldman
pattern types $r<\overline{r}$.

  * •

We now turn to the case $r>\overline{r}$, that is, the length
$T_{s+1}N^{2r}_{s+1}h_{n-1}$ of maximum repetitions of the same $s$-class in
$P$ is larger than the cycle length $T_{s+1}N^{2\overline{r}+1}_{s+1}h_{n-1}$
in $\overline{P}$. For a proportion of at most $1/N_{s+1}$, the strings
$C_{k}$ overlap substitution instance of two different $s$-classes. We ignore
those. Otherwise, for some $m\in\\{1,\dots,N_{s+1}\\}$ each $C_{k,i}$,
$i=1,\dots,N_{s+1}$, contains a repetition of at least
$\lfloor(1-3\frac{\alpha_{s}}{80})N_{s+1}-2\rfloor$ many
$[A_{m}]^{T_{s+1}N^{2\overline{r}-1}_{s+1}}_{s}$. This string contains each
substitution instance of $[A_{m}]_{s}$ the same number of times. We reduce
$C_{k,i}$ to this string and delete the other symbols. By (6.2) this might
increase the $\overline{f}$ distance by at most
$\frac{12\alpha_{s}}{80}+\frac{5}{N_{s+1}}$. Since every $C_{k,i}$ contains
each substitution instance of $[A_{m}]_{s}$ the same number of times, we can
build a reshuffling $\upsilon^{\prime}_{k,i}$ of the shading
$\upsilon_{k,N_{s+1}-i}$ as in the other case such that each substitution
instance on $(C_{k,i},\upsilon^{\prime}_{k,i})$ is paired with the same
shadings as on $(C_{k,N_{s+1}-i},\upsilon_{k,N_{s+1}-i})$. As in the other
case, the images $\phi\left(C_{k,i},\upsilon^{\prime}_{k,i}\right)$ and
$\phi(C_{k,N_{s+1}-i},\upsilon_{k,N_{s+1}-i})$ are close to each other in
$\overline{f}$.

Figure 6.2. Illustration of the reshuffling procedure in case of Feldman
pattern types $r>\overline{r}$.

In both cases $r<\overline{r}$ and $r>\overline{r}$, we obtain, for each
string $C_{k,1}\dots C_{k,N_{s+1}}$, a new shading such that the image under
the code $\phi$ is $\overline{f}$-close to a cycle of the $s$-pattern
$\overline{P}$ traversed in the opposite direction. Thus, we obtain a new
shading $\upsilon^{\prime}\in\\{0,1\\}^{|E|}$ such that

$\overline{f}\left(\phi(E,\upsilon^{\prime}),(\overline{F},\overline{\upsilon})\right)<\frac{\alpha^{2}_{s}}{2000}+\frac{2}{2^{4e(n-1)}}+\frac{\alpha_{s}}{4}+\frac{12\alpha_{s}}{80}+\frac{7}{N_{s+1}}<\frac{17\alpha_{s}}{40},$

where $\overline{F}$ is a string of length at least $|P|/2^{2e(n-1)+1}$ such
that $\overline{F}$ is part of a $(T_{s+1},N_{s+1},M_{s+1})$-Feldman pattern
of type $\overline{r}$ with the tuple of building blocks
$\left([\overline{A}_{N_{s+1}}]_{s},[\overline{A}_{N_{s+1}-1}]_{s},\dots,[\overline{A}_{1}]_{s}\right)$
in opposite order. Since such a string $\overline{F}$ is at least
$\frac{\alpha_{s}}{2}$-apart in $\overline{f}$ from every string in
$\operatorname{rev}(\mathbb{K})$ by Lemma 17, we conclude the proof of Lemma
19 with the aid of Fact 13. ∎

We are now ready to prove the observation similar to [GKpp, Lemma 74] that a
well-approximating finite code can be identified with an element of the group
action, where we recall the notation $\eta_{g}$ from Remark 15.

######  Lemma 20.

Let $s\in\mathbb{N}$, $0<\theta<\frac{1}{6}$,
$0<\delta<\frac{\alpha^{3}_{s}}{4\cdot 10^{4}}$,
$0<\varepsilon<\frac{\alpha_{s}}{200}\delta$, and $\phi$ be a finite code from
$\mathbb{S}$ to $\operatorname{rev}(\mathbb{S})$. For $n$ sufficiently large
(depending only on the code length, $s$, $\delta$, and $\varepsilon$), for
every $w\in\mathcal{W}_{n}$ such that for a proportion of at least $1-\theta$
of the shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$ of $w$ there is a
string $(\overline{A},\overline{\upsilon})$ in
$\operatorname{rev}(\mathbb{S})$ with
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$,
the following condition holds for at least a proportion $1-2\theta$ of the
shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$ of $w$: For every string
$(\overline{A},\overline{\upsilon})$ in $\operatorname{rev}(\mathbb{S})$ with
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$
there must be exactly one $\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$
with $|\overline{A}\cap\overline{w}|\geq(1-\delta)h_{n}$ and $\overline{w}$
must be of the form $\left[\overline{w}\right]_{s}=\eta_{g}\left[w\right]_{s}$
for a unique $g=g(w,\upsilon)$ $\in G_{s}$, which is necessarily of odd
parity.

_Outline of Proof:_ If
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$,
then it follows from a straightforward estimate on the length of strings in
(6.3) that there can be at most one
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$|\overline{A}\cap\overline{w}|\geq(1-\delta)|\overline{w}|$. The harder part
is to show that there is exactly one such word
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ and that it has to be of
the form $\left[\overline{w}\right]_{s}=\eta_{g}\left[w\right]_{s}$ for a
unique $g\in G_{s}$, that is, the $s$-pattern structure of $w$ and
$\overline{w}$ has to be the same. This will follow from an application of
Lemma 19 saying that for substantial substrings $E$ and $\overline{E}$ of
$s$-Feldman patterns of different types there is a one-to-one map from
shadings $\upsilon\in\\{0,1\\}^{|E|}$ such that
$\overline{f}\left(\phi(E,\upsilon),(\overline{E},\tilde{\upsilon})\right)$ is
small to shadings $\upsilon^{\prime}\in\\{0,1\\}^{|E|}$ such that
$\phi(E,\upsilon^{\prime})$ is $\overline{f}$-apart from any substring in
$\operatorname{rev}(\mathbb{S})$. Thus, the code cannot work well on at least
half of the shadings if $w$ and $\overline{w}$ have a different $s$-pattern
structure.

We now turn to the detailed proof.

###### Proof.

Our initial requirement on the size of $n$ is that $h_{n-1}$ be much larger
than the length of the code, so that end effects are negligible for
$(n-1)$-words. Let $\upsilon\in\\{0,1\\}^{h_{n}}$ be a shading of $w$ such
that there is a string $(\overline{A},\overline{\upsilon})$ in
$\operatorname{rev}(\mathbb{S})$ with
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$.
By Fact 12 we know from
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$
that

(6.3)
$1-3\varepsilon\leq\frac{1-\varepsilon}{1+\varepsilon}\leq\frac{|\overline{A}|}{h_{n}}\leq\frac{1+\varepsilon}{1-\varepsilon}\leq
1+3\varepsilon.$

Hence, there can be at most one
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$|\overline{A}\cap\overline{w}|\geq(1-\delta)|\overline{w}|$.

######  Claim 21.

Suppose that there is no such
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$. Then there exists
another shading $\upsilon^{\prime}\in\\{0,1\\}^{h_{n}}$ such that
$\overline{f}\left(\phi(w,\upsilon^{\prime}),(\overline{D},\overline{u})\right)>2\varepsilon$
for all strings $(\overline{D},\overline{u})$ in
$\operatorname{rev}(\mathbb{S})$.

In fact, there will be an one-to-one map from shadings
$\upsilon\in\\{0,1\\}^{h_{n}}$ satisfying

$\begin{split}\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon\
&\text{ for a string $(\overline{A},\overline{\upsilon})$ in
$\operatorname{rev}(\mathbb{S})$, where there is }\\\ &\text{ no
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$|\overline{A}\cap\overline{w}|\geq(1-\delta)|\overline{w}|$,}\end{split}$

to shadings $\upsilon^{\prime}\in\\{0,1\\}^{h_{n}}$ such that

$\overline{f}\left(\phi(w,\upsilon^{\prime}),(\overline{D},\overline{u})\right)>2\varepsilon\
\text{ for all strings $(\overline{D},\overline{u})$ in
$\operatorname{rev}(\mathbb{S})$.}$

We prove Claim 21 below. It implies that for a proportion of at least
$1-2\theta$ of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$, for
any string $(\overline{A},\overline{\upsilon})$ in
$\operatorname{rev}(\mathbb{S})$ with
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$,
there must be exactly one $\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$
with $|\overline{A}\cap\overline{w}|\geq(1-\delta)h_{n}$. By the same method
of proof, one also obtains that $w$ and $\overline{w}$ need to have the same
$s$-pattern structure. By the construction in [GKpp], this only happens if
their equivalence classes $\left[w\right]_{s}$ and
$\left[\overline{w}\right]_{s}$ lie on the same orbit of the group action by
$G_{s}^{n}$ (recall from step (5) that substitution instances not lying on the
same $G_{s}^{n}$ orbit were constructed as a different concatenation of
different Feldman patterns). We have seen in Remark 15 that an element $g\in
G_{s}^{n}$ of odd parity induces
$\eta_{g}:\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}\to\operatorname{rev}(\mathcal{W}_{n})/\mathcal{Q}^{n}_{s}$
that preserves the order of $s$-Feldman patterns, while an element $g\in
G_{s}^{n}$ of even parity would induce a map
$\mathcal{W}_{n}/\mathcal{Q}^{n}_{s}\to\operatorname{rev}(\mathcal{W}_{n})/\mathcal{Q}^{n}_{s}$
that reverses the order of $s$-Feldman patterns. By Lemma 16 and the freeness
of the group action according to specification (A7) we conclude that there is
a unique $g\in G_{s}$, which has to be of odd parity, with
$\left[\overline{w}\right]_{s}=\eta_{g}\left[w\right]_{s}$. This yields Lemma
20.

###### Proof of Claim 21.

By assumption, there is no
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$|\overline{A}\cap\overline{w}|\geq(1-\delta)|\overline{w}|$. Since we know
$|\overline{A}|\geq(1-3\varepsilon)|\overline{w}|$, there have to be two words
$\overline{w}_{1},\overline{w}_{2}\in\operatorname{rev}(\mathcal{W}_{n})$ such
that $\overline{A}$ is a substring of $\overline{w}_{1}\overline{w}_{2}$ and

(6.4)
$|\overline{A}\cap\overline{w}_{j}|\geq\left(\delta-3\varepsilon\right)\cdot|\overline{w}_{j}|>\frac{180}{\alpha_{s}}\varepsilon
h_{n}\text{ for }j=1,2.$

Then the beginning of $\phi(w,\upsilon)$ is matched with a string in
$\operatorname{rev}(\mathbb{S})$ associated with the end of
$\overline{w}_{1}$, while the end of $\phi(w,\upsilon)$ is matched with a
string in $\operatorname{rev}(\mathbb{S})$ associated with the beginning of
$\overline{w}_{2}$. There are two possible cases: Either at least one of
$\overline{w}_{1},\overline{w}_{2}$ has a different $s$-pattern structure from
that of $w$, or $\overline{w}_{1}$ and $\overline{w}_{2}$ have the same
$s$-pattern structure as $w$. Here we point out that the Feldman pattern types
in the $s$-pattern structure of the beginning and end of $w$ are different
from each other by construction. (Recall from step (5) that substitution
instances were constructed as a concatenation of different Feldman patterns.)

To investigate both cases we denote by $\overline{A}_{j}$ the part of
$\overline{A}$ corresponding to $\overline{w}_{j}$, $j=1,2$. Let $\pi$ be a
best possible match in $\overline{f}$ between $\phi(w,\upsilon)$ and
$(\overline{A},\overline{\upsilon})$. Then we denote the parts in
$\phi(w,\upsilon)$ corresponding to
$(\overline{A}_{j},\overline{\upsilon}_{j})$ under $\pi$ by
$\phi(A_{j},\upsilon_{j})$. Since $\pi$ is a map on the indices, we can also
view it as a map between $\phi(A_{j},\upsilon_{j})$ and
$(\overline{A}_{j},\overline{\upsilon}_{j})$.

We note that
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$
requires
$\overline{f}\left(\phi(A_{j},\upsilon_{j}),(\overline{A}_{j},\overline{\upsilon}_{j})\right)<\frac{\alpha_{s}}{60}$
for both $j\in\\{1,2\\}$ because otherwise

$\displaystyle\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)$
$\displaystyle=$
$\displaystyle\frac{|A_{1}|+|\overline{A}_{1}|}{|w|+|\overline{A}|}\cdot\overline{f}\left(\phi(A_{1},\upsilon_{1}),(\overline{A}_{1},\overline{\upsilon}_{1})\right)+\frac{|A_{2}|+|\overline{A}_{2}|}{|w|+|\overline{A}|}\cdot\overline{f}\left(\phi(A_{2},\upsilon_{2}),(\overline{A}_{2},\overline{\upsilon}_{2})\right)$
$\displaystyle\geq$ $\displaystyle\frac{\frac{180}{\alpha_{s}}\varepsilon
h_{n}}{h_{n}+(1+3\varepsilon)h_{n}}\cdot\frac{\alpha_{s}}{60}>\varepsilon$

by Fact 11 and our length estimate on $\overline{A}_{j}$ in (6.4). Then Fact
12 and inequality (6.4) yield

(6.5)
$|A_{j}|\geq\frac{1-\frac{\alpha_{s}}{60}}{1+\frac{\alpha_{s}}{60}}\cdot|\overline{A}_{j}|>(1-3\frac{\alpha_{s}}{60})\cdot\frac{180}{\alpha_{s}}\varepsilon
h_{n}>\frac{160}{\alpha_{s}}\varepsilon h_{n}$

for both $j\in\\{1,2\\}$.

In order to have
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\varepsilon$,
we need to have
$\overline{f}\left(\phi(A_{j},\upsilon_{j}),(\overline{A}_{j},\overline{\upsilon}_{j})\right)<\varepsilon$
for at least one $j\in\\{1,2\\}$.

######  Claim 22.

There is a one-to-one map from shadings $\upsilon_{j}\in\\{0,1\\}^{|A_{j}|}$
such that

(6.6)
$\overline{f}\left(\phi(A_{j},\upsilon_{j}),(\overline{A}_{j},\overline{\upsilon}_{j})\right)<\varepsilon$

to shadings $\upsilon^{\prime}_{j}\in\\{0,1\\}^{|A_{j}|}$ such that

$\overline{f}\left(\phi(A_{j},\upsilon^{\prime}_{j}),(\overline{D}_{j},\overline{u}_{j})\right)>\frac{\alpha_{s}}{30}$

for all strings $(\overline{D}_{j},\overline{u}_{j})$ in $rev(\mathbb{S})$.

We prove Claim 22 below. Suppose that $(\overline{D},\overline{u})$ is any
string in $\operatorname{rev}(\mathbb{S})$ with length
$|\overline{D}|<(1+6\varepsilon)h_{n}<1.5h_{n}$ (otherwise, we have
$\overline{f}\left(\phi(w,\upsilon^{\prime}),(\overline{D},\overline{u})\right)>2\varepsilon$
by Fact 12). For every shading $\upsilon$ of $w$, we write
$\upsilon=(\upsilon_{1},\upsilon_{2})$, where $\upsilon_{j}$ is the shading of
$w_{j}$. If equation (6.6) holds with $j=1$, define
$\upsilon^{\prime}=(\upsilon_{1}^{\prime},\upsilon_{2})$; otherwise define
$\upsilon^{\prime}=(\upsilon_{1},\upsilon_{2}^{\prime}).$ We combine the
result from Claim 22 with the estimate on $|A_{j}|$ from (6.5) to conclude
using Fact 11 that the shading $\upsilon^{\prime}\in\\{0,1\\}^{h_{n}}$ is such
that

(6.7)
$\overline{f}\left(\phi(w,\upsilon^{\prime}),(\overline{D},\overline{u})\right)\geq\frac{|A_{j}|+|\overline{D}_{j}|}{|w|+|\overline{D}|}\cdot\frac{\alpha_{s}}{30}>\frac{2}{5}\cdot\frac{160}{\alpha_{s}}\varepsilon\cdot\frac{\alpha_{s}}{30}>2\varepsilon.$

Clearly the map $\upsilon\mapsto\upsilon^{\prime}$ is one-to-one in each of
these two cases separately. If there were
$\upsilon=(\upsilon_{1},\upsilon_{2})$ such that equation (6.6) holds for
$j=1$ and $\tilde{\upsilon}=(\tilde{\upsilon}_{1},\tilde{\upsilon}_{2})$ such
that (6.6) does not hold for $j=1$, then it is not possible to have
$\upsilon_{2}={\tilde{\upsilon}}_{2}^{\prime}$ since
$v_{2}=\tilde{v}_{2}^{\prime}$ would imply
$\overline{f}\left(\phi(w,\upsilon),(\overline{A},\overline{\upsilon}\right)>2\varepsilon,$
by the estimate in (6.7), which contradicts the assumption that
$\overline{f}(\phi(w,\upsilon),(\overline{A},\overline{\upsilon}))<\varepsilon.$
Therefore the map $\upsilon\mapsto\upsilon^{\prime}$ is one-to-one. This
finishes the proof of Claim 21. ∎

###### Proof of Claim 22.

Since
$\overline{f}\left(\phi(A_{j},\upsilon_{j}),(\overline{A}_{j},\overline{\upsilon}_{j})\right)<\varepsilon$,
we have $|A_{j}|\geq\frac{160}{\alpha_{s}}\varepsilon h_{n}$ by (6.5). Hence,
for sufficiently large $n$ the strings $A_{j}$ and $\overline{A}_{j}$ are
longer than $h_{n}/2^{e(n-1)}$. In particular, there are at least
$2^{6e(n-1)}$ complete $s$-Feldman patterns (out of building blocks in
$\mathcal{W}_{n-1}/\mathcal{Q}_{s}^{n-1}$) in $A_{j}$ and $\overline{A}_{j}$.
Moreover, all of them have the same length. (If we are in Case 2,
$s(n)=s(n-1)+1$, of the construction in [GKpp, section 8.2] we ignore the
strings coming from $\mathcal{W}^{\dagger\dagger}$, which might increase the
$\overline{f}$ distance by at most $\frac{2}{\mathfrak{p}_{n}}$ according to
the length portion of strings from $\mathcal{W}^{\dagger\dagger}$ in words of
$\mathcal{W}_{n}$ and Fact 10.) We complete partial $s$-patterns at the
beginning and end of $A_{j}$ and $\overline{A}_{j}$, which might increase the
$\overline{f}$ distance by at most $\frac{2}{2^{6e(n-1)}}$ according to Fact
10 as well. The augmented strings obtained in this way are denoted by
$A_{j,aug}$ and $\overline{A}_{j,aug}$, respectively, and we decompose them
into the $s$-Feldman patterns:

$\displaystyle A_{j,aug}=P_{j,n-1,1}\dots P_{j,n-1,m}$
$\displaystyle\overline{A}_{j,aug}=\overline{P}_{j,n-1,1}\dots\overline{P}_{j,n-1,\overline{m}}.$

In the next step, we write $A_{j,aug}$ and $\overline{A}_{j,aug}$ as

$\displaystyle A_{j,aug}=E_{j,1}\dots E_{j,t}$
$\displaystyle\overline{A}_{j,aug}=\overline{E}_{j,1}\dots\overline{E}_{j,t},$

where $E_{j,i}$ and $\overline{E}_{j,i}$ are maximal substrings such that
$E_{j,i}\subseteq P_{j,n-1,\ell(i)}$ and
$\overline{E}_{j,i}\subseteq\overline{P}_{j,n-1,\overline{\ell}(i)}$
correspond to each other under $\pi$. In particular, we have $t\geq
2^{6e(n-1)}$.

If $A_{j}$ and $\overline{A}_{j}$ lie in $w$ and $\overline{w}_{j}$ with the
same $s$-pattern structure, then
$|A_{j^{\prime}}|>\frac{160}{\alpha_{s}}\varepsilon h_{n}$ for $j^{\prime}\neq
j$ from (6.5) and
$\overline{f}\left(\phi(A_{j},\upsilon_{j}),(\overline{A}_{j},\overline{\upsilon}_{j})\right)<\varepsilon$
together imply that the Feldman pattern types of $P_{j,n-1,\ell(i)}$ and
$\overline{P}_{j,n-1,\overline{\ell}(i)}$ cannot be the same.

If the $s$-pattern structures of $w$ and $\overline{w}_{j}$ are different from
each other, then we have at most one pair of $E_{j,i}$ and
$\overline{E}_{j,i}$ where the type of Feldman pattern coincides. We delete
this possible pair. This might increase the $\overline{f}$ distance by at most
$\frac{2}{2^{6e(n-1)}}$ according to Fact 10 because we have $t\geq
2^{6e(n-1)}$.

Thus, in the following we can assume that all pairs $E_{j,i}$ and
$\overline{E}_{j,i}$ lie in Feldman patterns of different type.

After completing the partial $s$-patterns and deleting at most one pair of
$E_{j,i}$ and $\overline{E}_{j,i}$, we still have
$\overline{f}\left(\phi(A_{j,aug},\upsilon_{j,aug}),(\overline{A}_{j,aug},\overline{\upsilon}_{j,aug})\right)<2\varepsilon<\frac{\alpha^{4}_{s}}{4\cdot
10^{6}}$ if $n$ is sufficiently large. Hence, a proportion of at least
$1-\frac{\alpha^{2}_{s}}{100}$ of the indices have to lie in pairs $E_{j,i}$
and $\overline{E}_{j,i}$ with
$\overline{f}\left(\phi(E_{j,i},\upsilon_{j,i}),(\overline{E}_{j,i},\overline{\upsilon}_{j,i})\right)<\frac{\alpha^{2}_{s}}{2000}$.

If
$\overline{f}\left(\phi(E_{j,i},\upsilon_{j,i}),(\overline{E}_{j,i},\overline{\upsilon}_{j,i})\right)<\frac{\alpha^{2}_{s}}{2000}$,
then we have

(6.8)
$1-\frac{1}{2^{4}}<\frac{1-\frac{1}{2^{5}}}{1+\frac{1}{2^{5}}}\leq\frac{|E_{j,i}|}{|\overline{E}_{j,i}|}\leq\frac{1+\frac{1}{2^{5}}}{1-\frac{1}{2^{5}}}<1+\frac{1}{2^{3}}$

by Fact 12. Since a string well-matched with $P_{j,n-1,\ell}$ has to lie
within at most three consecutive patterns in $\overline{A}_{j,aug}$, in each
$P_{j,n-1,\ell}$ there are at most two segments $E_{j,i}$ with
$|E_{j,i}|<\frac{|P_{j,n-1,\ell}|}{2^{2e(n-1)}}$. For their corresponding
segments we also get
$|\overline{E}_{j,i}|<\frac{|P_{j,n-1,\ell}|}{2^{2e(n-1)-1}}$ by the estimate
in (6.8). By the same reasons, there are at most two segments
$\overline{E}_{j,i}$ with
$|\overline{E}_{j,i}|<\frac{|P_{j,n-1,\ell}|}{2^{2e(n-1)}}$ in each
$\overline{P}_{j,n-1,\ell}$ and we can also bound the lengths of their
corresponding strings. Altogether, the proportion of symbols in those
situations is at most $\frac{1}{2^{2e(n-1)-4}}$ and we ignore them in the
following consideration.

Hence, we consider the case that both $|E_{j,i}|$ and $|\overline{E}_{j,i}|$
are at least $\frac{|P_{j,n-1,\ell}|}{2^{2e(n-1)}}$. This allows us to apply
Lemma 19. Combining it with the previous estimates, we conclude the existence
of a $\upsilon^{\prime}_{j}\in\\{0,1\\}^{|A_{j}|}$ such that

$\overline{f}\left(\phi(A_{j},\upsilon^{\prime}_{j}),(\overline{D}_{j},\overline{u}_{j})\right)>\frac{\alpha_{s}}{20}-\frac{2}{\mathfrak{p}_{n}}-\frac{4}{2^{e(n-1)}}-2\frac{\alpha^{2}_{s}}{100}>\frac{\alpha_{s}}{30}$

for all strings $(\overline{D}_{j},\overline{u}_{j})$ in $rev(\mathbb{S})$.
This finishes the proof of Claim 22. ∎

Altogether, we completed the proof of Lemma 20.

∎

Assume $\mathbb{S}$ and $\operatorname{rev}(\mathbb{S})$ are evenly
equivalent. From [GKpp, Corollary 71] applied to $\mathbb{S}$ there exists a
sequence of finite codes $\left(\phi_{\ell}\right)_{\ell\in\mathbb{N}}$ from
$\mathbb{S}$ to $\operatorname{rev}(\mathbb{S})$ such that for every
$0<\gamma<\frac{1}{2}$ there exists $N=N(\gamma)\in\mathbb{Z}^{+}$ such that
for $N\geq N(\gamma)$ and $k\in\mathbb{Z}^{+}$ and all sufficiently large $n$
(how large depends on $N$,$\gamma$, and $k$) there is a collection
$\mathcal{V}_{n}^{\prime}\subset\mathcal{V}_{n}$ that includes at least
$1-\gamma$ of the strings in $\mathcal{V}_{n}$ and the following condition
holds: For $(w,\upsilon)\in\mathcal{V}_{n}^{\prime}$ there exists
$(\overline{A},\overline{\upsilon})$ that occurs with positive frequency in
the $\operatorname{rev}(\mathbb{S})$ process and we have

$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{A},\overline{\upsilon})\right)<\gamma,$

and

$\overline{f}\left(\phi_{N}(w,\upsilon),\phi_{N+k}(w,\upsilon)\right)<\gamma.$

We apply it with $\gamma=\gamma_{s}=\frac{\alpha^{8}_{s}}{4\cdot 10^{24}}$ for
$s\in\mathbb{Z}^{+}$ to obtain $N(s)\in\mathbb{Z}^{+}$ such that for every
$N\geq N(s)$ and $k\in\mathbb{Z}^{+}$ there is $n(s,N,k)\in\mathbb{Z}^{+}$
sufficiently large so that for all $n\geq n(s,N,k)$ the hypothesis of Lemma 20
with $\theta=\sqrt{\gamma_{s}}$,
$\delta=\delta_{s}=\frac{\alpha^{6}_{s}}{10^{22}}$, $\varepsilon=\gamma_{s}$,
and $\phi=\phi_{N}$ holds, and there exists a collection
$\mathcal{W}^{\prime}_{n}$ of $n$-words (that includes at least
$1-\sqrt{\gamma_{s}}$ of the $n$-words) satisfying the following properties:

  1. (C1)

For $w\in\mathcal{W}^{\prime}_{n}$ we have for a proportion of at least
$1-\sqrt{\gamma_{s}}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$ that there exists
$z=z(w,\upsilon)\in\operatorname{rev}(\mathbb{S})$ such that
$z\upharpoonright[0,h_{n}-1]$ occurs with positive frequency in
$\operatorname{rev}(\mathbb{S})$ and

$\overline{f}\left(\phi_{N}(w,\upsilon),z\upharpoonright[0,h_{n}-1]\right)<\frac{\alpha^{8}_{s}}{4\cdot
10^{24}}.$

  2. (C2)

For $w\in\mathcal{W}^{\prime}_{n}$ we have for a proportion of at least
$1-\sqrt{\gamma_{s}}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$ that

$\overline{f}\left(\phi_{N}(w,\upsilon),\phi_{N+k}(w,\upsilon)\right)<\frac{\alpha^{8}_{s}}{4\cdot
10^{24}}.$

Then we can prove the following analogue of [GKpp, Lemma 75].

######  Lemma 23.

Suppose that $\mathbb{S}$ and $\operatorname{rev}(\mathbb{S})$ are evenly
equivalent and let $s\in\mathbb{N}$. There is a unique $g_{s}\in G_{s}$ such
that for every $N\geq N(s)$ and sufficiently large $n\in\mathbb{N}$ we have
for every $w\in\mathcal{W}_{n}^{\prime}$ that for a proportion of at least
$\frac{99}{100}$ of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$
there is $\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and some
shading sequence $\overline{\upsilon}\in\\{0,1\\}^{h_{n}}$ such that

(6.9)
$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<\frac{\alpha_{s}}{4},$

where $\left(\phi_{\ell}\right)_{\ell\in\mathbb{N}}$ is a sequence of finite
codes as described above and $\mathcal{W}_{n}^{\prime}$ is the associated
collection of $n$-words satisfying properties (C1) and (C2).

Moreover, $g_{s}\in G_{s}$ is of odd parity and the sequence
$(g_{s})_{s\in\mathbb{N}}$ satisfies $g_{s}=\rho_{s+1,s}(g_{s+1})$ for all
$s\in\mathbb{N}$.

_Outline of Proof:_ An application of Lemma 20 will imply that for every
$w\in\mathcal{W}_{n+1}^{\prime}$ there is a large proportion of shadings such
that (6.9) holds for $\overline{w}\in\operatorname{rev}(\mathcal{W}_{n+1})$
with $\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ for some
$g_{s}\in G_{s}$. The hard part is to show that actually the same group
element of $G_{s}$ works for all words in $\mathcal{W}_{n+1}^{\prime}$. This
is the content of Claim 24. Its proof bases upon the observation that a good
$\overline{f}$ match between $\phi_{N}(w,\upsilon)$ and
$(\overline{w},\overline{\upsilon})$ has to respect the $s$-pattern structure
in $w$, that is, if $w=P_{1}\dots P_{r}$ is the decomposition into
$s$-patterns and $\overline{w}=\overline{P}_{1}\dots\overline{P}_{r}$ is the
corresponding decomposition under a best possible $\overline{f}$-match between
$\phi_{N}(w,\upsilon)$ and $(\overline{w},\overline{\upsilon})$, then most of
the $[\overline{P}_{i}]_{s}$ have to lie in $\eta_{g_{s}}[P_{i}]_{s}$. Since
the classes within the building tuple of $P_{i}$ have disjoint $G_{s}$ orbits
by steps (1) and (8) of the construction in Section 5, we can show that for a
large proportion of shaded $n$-words $(w_{j},\upsilon_{j})$ there has to be
$\overline{w}_{j}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}_{j}\right]_{s}=\eta_{g_{s}}\left[w_{j}\right]_{s}$ such
that
$\overline{f}\left(\phi_{N}(w_{j},\upsilon_{j}),(\overline{w}_{j},\overline{\upsilon}_{j})\right)$
is small for some shading sequence
$\overline{\upsilon}_{j}\in\\{0,1\\}^{h_{n}}$. Using assumption (R9) this
implies that for a large proportion of $n$-words $w_{j}$ we have for a large
proportions of shadings $\upsilon_{j}$ that there is
$\overline{w}_{j}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}_{j}\right]_{s}=\eta_{g_{s}}\left[w_{j}\right]_{s}$ such
that
$\overline{f}\left(\phi_{N}(w_{j},\upsilon_{j}),(\overline{w}_{j},\overline{\upsilon}_{j})\right)$
is small. This will allow us to conclude that the same group element of
$G_{s}$ works for all words in $\mathcal{W}_{n+1}^{\prime}$.

Afterwards we show that the same group element $g_{s}\in G_{s}$ works for all
$\phi_{N}$ with $N\geq N(s)$. Here, we use that images under $\phi_{N}$ and
$\phi_{N+k}$ are $\overline{f}$-close to each other, while the properties from
the construction in [GKpp] yield that distinct $s$-classes have $\overline{f}$
distance at least $\alpha_{s}$ by Lemma 16 and that the action by $G_{s}$ is
free by specification (A7).

In a final step we combine these properties with specification (A7) (the
$G_{s+1}^{n}$ action is subordinate to the $G_{s}^{n}$ action) to show that
the sequence $(g_{s})_{s\in\mathbb{N}}$ must satisfy
$g_{s}=\rho_{s+1,s}(g_{s+1})$ for all $s\in\mathbb{N}$.

###### Proof.

In the first part of the proof we fix $N\geq N(s)$. For $n\geq n(s,N,1)$ we
see from property (C1) that for any $w\in\mathcal{W}^{\prime}_{n}$ there is a
proportion of at least $1-\sqrt{\gamma_{s}}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$ such that there exists
$z\in\operatorname{rev}(\mathbb{S})$ with

$\overline{f}\left(\phi_{N}(w,\upsilon),z\upharpoonright[0,h_{n}-1]\right)<\gamma_{s}=\frac{\alpha^{8}_{s}}{4\cdot
10^{24}}<\frac{\alpha_{s}}{200}\cdot\delta_{s}.$

We denote $(\overline{A},\hat{\upsilon})\coloneqq z\upharpoonright[0,h_{n}-1]$
in $\operatorname{rev}(\mathbb{S})$. By Lemma 20 we obtain for a proportion of
at least $1-2\sqrt{\gamma_{s}}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$ that there is exactly one
$\overline{w}=\overline{w}(w,\upsilon)\in\operatorname{rev}(\mathcal{W}_{n})$
with $|\overline{A}\cap\overline{w}|\geq(1-\delta_{s})|\overline{w}|$ and
$\overline{w}$ must be of the form
$\left[\overline{w}\right]_{s}=\eta_{g}\left[w\right]_{s}$ for a unique
$g=g(w,\upsilon)\in G_{s}$, which is of odd parity. Thus, we conclude that
there is some shading sequence
$\overline{\upsilon}=\overline{\upsilon}(w,\upsilon)\in\\{0,1\\}^{h_{n}}$ such
that

(6.10)
$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<\gamma_{s}+\delta_{s}<10^{-20}\alpha_{s}^{6}.$

We now show that one group element of $G_{s}$ works for $\phi_{N}$ and all
words in $\mathcal{W}^{\prime}_{n+1}$.

######  Claim 24.

There is a unique $g_{s}\in G_{s}$ such that for every
$w\in\mathcal{W}^{\prime}_{n+1}$ we have for a proportion of at least
$\frac{99}{100}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n+1}}$ that there is
$\overline{w}=\overline{w}(w,\upsilon)\in\operatorname{rev}(\mathcal{W}_{n+1})$
with $\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and some
shading sequence
$\overline{\upsilon}=\overline{\upsilon}(w,\upsilon)\in\\{0,1\\}^{h_{n+1}}$
such that

$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<\frac{\alpha_{s}}{4}.$

In order to prove Claim 24, we repeat the argument from (6.10) for a word
$w\in\mathcal{W}^{\prime}_{n+1}$ which is a concatenation of $n$-words by
construction. Hence, for a proportion of at least $1-2\sqrt{\gamma_{s}}$ of
possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n+1}},$

(6.11) $\begin{split}&\text{there is a unique $g_{s}=g_{s}(w,\upsilon)\in
G_{s}$ and some
$\overline{w}=\overline{w}(w,\upsilon)\in\operatorname{rev}(\mathcal{W}_{n+1})$}\\\
&\text{with $\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and
some shading sequence
$\overline{\upsilon}=\overline{\upsilon}(w,\upsilon)\in\\{0,1\\}^{h_{n+1}}$
}\\\ &\text{such that
$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<10^{-20}\alpha_{s}^{6}$.}\end{split}$

######  Claim 25.

For every $w\in\mathcal{W}^{\prime}_{n+1}$ there is a collection
$\mathcal{S}=\mathcal{S}(w)\subseteq\\{0,1\\}^{h_{n+1}}$ with
$|\mathcal{S}|\geq\frac{99}{100}2^{h_{n+1}}$ such that for each
$\upsilon\in\mathcal{S}$ we have for the $g_{s}=g_{s}(w,\upsilon)\in G_{s}$
from (6.11) that for a proportion of at least $\frac{8}{10}$ of $n$-blocks
$\tilde{w}\in\mathcal{W}_{n}$ and for a proportion of at least $\frac{8}{10}$
of all shading sequences $\tilde{\upsilon}\in\\{0,1\\}^{h_{n}}$ there is
$\hat{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\hat{w}\right]_{s}=\eta_{g_{s}}\left[\tilde{w}\right]_{s}$ and
$\overline{f}\left(\phi_{N}(\tilde{w},\tilde{\upsilon}),(\hat{w},\hat{\upsilon})\right)<\frac{\alpha_{s}}{4}$
for some shading sequence $\hat{\upsilon}\in\\{0,1\\}^{h_{n}}$.

###### Proof of Claim 25.

Combining the requirement (6.11) with property (R9), there is a collection
$\mathcal{S}^{\prime}\subset\\{0,1\\}^{h_{n+1}}$ with
$|\mathcal{S}^{\prime}|>\frac{499}{500}2^{h_{n+1}}$ of shading sequences
$\upsilon$ satisfying (6.1) and that there is a unique
$g_{s}=g_{s}(w,\upsilon)\in G_{s}$ and
$\overline{w}=\overline{w}(w,\upsilon)\in\operatorname{rev}(\mathcal{W}_{n+1})$
with $\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and some
shading sequence
$\overline{\upsilon}=\overline{\upsilon}(w,\upsilon)\in\\{0,1\\}^{h_{n+1}}$
such that
$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<10^{-20}\alpha_{s}^{6}$.

We decompose $w$ into its $s$-Feldman patterns: $w=P_{1}\dots P_{r}$. For each
$\upsilon\in\mathcal{S}^{\prime}$ we also decompose
$(w,\upsilon)=(P_{1},\upsilon_{1})\dots(P_{r},\upsilon_{r})$ with
$\upsilon_{i}\in\\{0,1\\}^{|P_{i}|}$.

Consider those $(P_{i},\upsilon_{i})$ for which there exists a substring
$(\tilde{P}_{i},\tilde{\upsilon}_{i})$ of length at least
$\frac{\alpha^{4}_{s}}{10^{12}}|P_{i}|$ and a $(\hat{P},\hat{\upsilon})$,
where $\hat{P}$ is a substring of some element of $G_{s}[w]_{s}$ and of
different pattern type from $P_{i}$, with
$\overline{f}\left(\phi_{N}(\tilde{P}_{i},\tilde{\upsilon}_{i}),(\hat{P},\hat{\upsilon})\right)<\frac{\alpha^{2}_{s}}{2000}$.
For such $(P_{i},\upsilon_{i})$ let $\upsilon^{\prime}_{i}$ be the reshuffling
from Lemma 19 according to the first pattern type that occurs in such a
$\hat{P}$. For the other $i$’s, let $\upsilon^{\prime}_{i}=\upsilon_{i}$. Let
$\upsilon^{\prime}=\upsilon^{\prime}_{1}\ldots\upsilon^{\prime}_{r}$. This map
$\upsilon\mapsto\upsilon^{\prime}$ is one-to-one. If
$\upsilon^{\prime}_{i}\neq\upsilon_{i}$ for at least $\frac{1}{500}$ of the
$i$’s, then $\upsilon^{\prime}\notin\mathcal{S}^{\prime}$. So there is a
collection $\mathcal{S}\subset\mathcal{S}^{\prime}$ with
$|\mathcal{S}|>\frac{498}{500}2^{h_{n+1}}$ for which
$\upsilon^{\prime}_{i}=\upsilon_{i}$ for all but $\frac{1}{500}$ of the $i$’s.

Let $\upsilon\in\mathcal{S}$ and
$(\overline{w},\overline{\upsilon})=(\overline{P}_{1},\overline{\upsilon}_{1})\dots(\overline{P}_{r},\overline{\upsilon}_{r})$
with $\overline{\upsilon}_{i}\in\\{0,1\\}^{|\overline{P}_{i}|}$ be the
decomposition corresponding to
$(w,\upsilon)=(P_{1},\upsilon_{1})\dots(P_{r},\upsilon_{r})$ under a best
possible $\overline{f}$-match between $\phi_{N}(w,\upsilon)$ and
$(\overline{w},\overline{\upsilon})$. According to Fact 11 the proportion of
such substrings $(P_{i},\upsilon_{i})$ with

(6.12)
$\overline{f}\left(\phi_{N}(P_{i},\upsilon_{i}),(\overline{P}_{i},\overline{\upsilon}_{i})\right)<10^{-17}\alpha_{s}^{6}$

is at least $\frac{499}{500}$. Thus, for a proportion of at least
$\frac{249}{250}$ of $i$’s we have that (6.12) holds and
$\upsilon^{\prime}_{i}=\upsilon_{i}$.

Choose $i$ such that (6.12) holds and $\upsilon^{\prime}_{i}=\upsilon_{i}$.
After applying $\phi_{N}$ to any substring of $(P_{i},\upsilon_{i})$ of length
at least $\frac{\alpha^{4}_{s}}{10^{12}}|P_{i}|$ the $\overline{f}$ distance
to a corresponding part of $(\overline{P}_{i},\overline{\upsilon}_{i})$ must
be less than $\frac{\alpha^{2}_{s}}{2000}$. Since
$\upsilon_{i}=\upsilon^{\prime}_{i}$ there exists a substring
$(\tilde{P}_{i},\tilde{\upsilon}_{i})$ of $(P_{i},\upsilon_{i})$ such that
$|\tilde{P}_{i}|>(1-\frac{\alpha^{4}_{s}}{10^{12}})|P_{i}|$ and
$\phi_{N}(\tilde{P}_{i},\tilde{\upsilon}_{i})$ is matched to a string
$(\hat{P}_{i},\hat{\upsilon}_{i})$ in
$(\overline{P}_{i},\overline{\upsilon}_{i})$, where $\hat{P}_{i}$ is of the
same pattern type as $P_{i}$, that is, $[\hat{P}_{i}]_{s}$ must lie in
$\eta_{g_{s}}[P_{i}]_{s}$ for $g_{s}=g_{s}(w,\upsilon)$. For each of those
$(P_{i},\upsilon_{i})$ we have

(6.13)
$\overline{f}\left(\phi_{N}(P_{i},\upsilon_{i}),(\hat{P}_{i},\hat{\upsilon}_{i})\right)<\frac{\alpha^{4}_{s}}{10^{11}}.$

We deduce from (6.13) that for a proportion of at least $\frac{998}{1000}$ of
the shaded $n$-blocks $(w_{i,l},\upsilon_{i,l})$ occurring as substitution
instances in $(P_{i},\upsilon_{i})$ we have

$\overline{f}\left(\phi_{N}(w_{i,l},\upsilon_{i,l}),(\hat{A}_{i,l},\hat{\upsilon}_{i,l})\right)<\frac{\alpha^{4}_{s}}{2\cdot
10^{7}}$

for a string $(\hat{A}_{i,l},\hat{\upsilon}_{i,l})$ in
$(\hat{P}_{i},\hat{\upsilon}_{i})$.

Overall, for a proportion of at least $\frac{124}{125}$ of the shaded
$n$-blocks $(w_{i,l},\upsilon_{i,l})$ occurring as substitution instances in
$(w,\upsilon)$ we have
$\overline{f}\left(\phi_{N}(w_{i,l},\upsilon_{i,l}),(\hat{A}_{i,l},\hat{\upsilon}_{i,l})\right)<\frac{\alpha^{4}_{s}}{2\cdot
10^{7}}$ for a string $(\hat{A}_{i,l},\hat{\upsilon}_{i,l})$ in
$(\hat{P}_{i},\hat{\upsilon}_{i})$. Since $\upsilon\in\mathcal{S}$ we obtain
from (6.1) that for a proportion of at least $\frac{8}{10}$ of $n$-blocks
$w_{i,l}\in\mathcal{W}_{n}$ we have for a proportion of at least
$\frac{9}{10}$ of all shading sequences $\upsilon_{i,l}\in\\{0,1\\}^{h_{n}}$
that

$\overline{f}\left(\phi_{N}(w_{i,l},\upsilon_{i,l}),(\hat{A}_{i,l},\hat{\upsilon}_{i,l})\right)<\frac{\alpha^{4}_{s}}{2\cdot
10^{7}}=\frac{\alpha_{s}}{200}\cdot\frac{\alpha^{3}_{s}}{10^{5}}$

for a string $(\hat{A}_{i,l},\hat{\upsilon}_{i,l})$ in
$(\hat{P}_{i},\hat{\upsilon}_{i})$. Then Lemma 20 implies that for these
$n$-blocks $w_{i,l}$ for a proportion of at least $\frac{8}{10}$ of all
shading sequences $\upsilon_{i,l}\in\\{0,1\\}^{h_{n}}$ there is exactly one
$\overline{w}_{i,l}\in rev(\mathcal{W}_{n})$ with
$|\hat{A}_{i,l}\cap\overline{w}_{i,l}|\geq(1-\frac{\alpha^{3}_{s}}{10^{5}})h_{n}$
and $\overline{w}_{i,l}$ must be of the form
$\left[\overline{w}_{i,l}\right]_{s}=\eta_{h_{i,l}}\left[w_{i,l}\right]_{s}$
for a unique $h_{i,l}\in G_{s}$, which is of odd parity. As in (6.10), we also
get

$\overline{f}\left(\phi_{N}(w_{i,l},\upsilon_{i,l}),(\overline{w}_{i,l},\overline{\upsilon}_{i,l})\right)<\frac{\alpha^{4}_{s}}{2\cdot
10^{7}}+\frac{\alpha^{3}_{s}}{10^{5}}<\frac{\alpha_{s}}{4}$

for some shading sequence $\overline{\upsilon}_{i,l}\in\\{0,1\\}^{h_{n}}$.
Since $[\hat{P}_{i}]_{s}$ is contained in $\eta_{g_{s}}([P_{i}]_{s})$ and the
$s$-equivalence classes within the building tuple of $P_{i}$ have disjoint
$G_{s}$ orbits by step (1) of the construction in Section 5, we obtain that
the $h_{i,l}$ are equal to $g_{s}$. Thus, for $g_{s}=g_{s}(w,\upsilon)$ and
for a proportion of at least $\frac{8}{10}$ of $n$-blocks
$\tilde{w}\in\mathcal{W}_{n}$ we have for a proportion of at least
$\frac{8}{10}$ of all shading sequences $\tilde{\upsilon}\in\\{0,1\\}^{h_{n}}$
that there is $\hat{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\hat{w}\right]_{s}=\eta_{g_{s}}\left[\tilde{w}\right]_{s}$ and
$\overline{f}\left(\phi_{N}(\tilde{w},\tilde{\upsilon}),(\hat{w},\hat{\upsilon})\right)<\frac{\alpha_{s}}{4}$
for some shading sequence $\hat{\upsilon}\in\\{0,1\\}^{h_{n}}$. ∎

###### Proof of Claim 24.

Suppose now that there are words $w,w^{\prime}\in\mathcal{W}^{\prime}_{n+1}$
and shadings $\upsilon\in\mathcal{S}(w)$,
$\upsilon^{\prime}\in\mathcal{S}(w^{\prime})$ such that the statement of Claim
25 holds for elements
$g_{s}(w,\upsilon),g_{s}(w^{\prime},\upsilon^{\prime})\in G_{s}$ with
$g_{s}(w,\upsilon)\neq g_{s}(w^{\prime},\upsilon^{\prime})$. Then for a
proportion of at least $\frac{6}{10}$ of all $n$-words
$\tilde{w}\in\mathcal{W}_{n}$ and a proportion of at least $\frac{6}{10}$ of
all shading sequences $\tilde{\upsilon}\in\\{0,1\\}^{h_{n}}$ the conclusion of
Claim 25 holds simultaneously for $g_{s}(w,\upsilon)$ and
$g_{s}(w^{\prime},\upsilon^{\prime})$. In particular, there exist
$\tilde{w}\in\mathcal{W}_{n}$, $\tilde{\upsilon}\in\\{0,1\\}^{h_{n}}$,
$\hat{w},\hat{w}^{\prime}\in\operatorname{rev}(\mathcal{W}_{n})$,
$\hat{\upsilon},\hat{\upsilon}^{\prime}\in\\{0,1\\}^{h_{n}}$ with
$[\hat{w}]_{s}=\eta_{g_{s}(w,\upsilon)}[\tilde{w}]_{s}$,
$[\hat{w}^{\prime}]_{s}=\eta_{g_{s}(w^{\prime},\upsilon^{\prime})}[\tilde{w}]_{s}$,
$\overline{f}\left(\phi_{N}(\tilde{w},\tilde{\upsilon}),(\hat{w},\hat{\upsilon})\right)<\frac{\alpha_{s}}{4}$,
and
$\overline{f}\left(\phi_{N}(\tilde{w},\tilde{\upsilon}),(\hat{w}^{\prime},\hat{\upsilon}^{\prime})\right)<\frac{\alpha_{s}}{4}$.
By the triangle inequality this implies

$\overline{f}\left((\hat{w},\hat{\upsilon}),(\hat{w}^{\prime},\hat{\upsilon}^{\prime})\right)<\frac{\alpha_{s}}{2}$

and therefore $\overline{f}(\hat{w},\hat{w}^{\prime})<\frac{\alpha_{s}}{2}$.
This contradicts
$\left[\hat{w}\right]_{s}=\eta_{g_{s}(w,\upsilon)}\left[\tilde{w}\right]_{s}\neq\eta_{g_{s}(w^{\prime},\upsilon^{\prime})}\left[\tilde{w}\right]_{s}=\left[\hat{w}^{\prime}\right]_{s}$
and Lemma 16. Hence, there is a unique group element $g_{s}\in G_{s}$ working
for all $(n+1)$-words $w$ in $\mathcal{W}^{\prime}_{n+1}$ and all shadings in
$\mathcal{S}(w)$. ∎

In the next step in the proof of Lemma 23, we check that the same group
element $g_{s}\in G_{s}$ works for all $\phi_{N}$, $N\geq N(s)$. Let
$k\in\mathbb{Z}^{+}$. For $n\geq n(s,N,k),$ property (C2) guarantees that for
every $w\in\mathcal{W}^{\prime}_{n},$ for a proportion of at least
$1-\sqrt{\gamma_{s}}$ of possible shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$, we have
$\overline{f}\left(\phi_{N}(w,\upsilon),\phi_{N+k}(w,\upsilon)\right)<\alpha^{4}_{s}$.
On the one hand, let $g_{s}$ be the element in $G_{s}$ such that for every
$w\in\mathcal{W}^{\prime}_{n},$ for a proportion of at least $\frac{99}{100}$
of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$, there exist
$\overline{w}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and some
shading sequence $\overline{\upsilon}\in\\{0,1\\}^{h_{n}}$ such that
$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w},\overline{\upsilon})\right)<\frac{\alpha_{s}}{4}$.
On the other hand, let $h\in G_{s}$ such that for every
$w\in\mathcal{W}^{\prime}_{n},$ for a proportion of at least $\frac{99}{100}$
of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$, there exist
$\overline{w}^{\prime}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}^{\prime}\right]_{s}=\eta_{h}\left[w\right]_{s}$ and some
shading sequence $\overline{\upsilon}^{\prime}\in\\{0,1\\}^{h_{n}}$ such that
$\overline{f}\left(\phi_{N+k}(w,\upsilon),(\overline{w}^{\prime},\overline{\upsilon}^{\prime})\right)<\frac{\alpha_{s}}{4}$.
Assume $g_{s}\neq h$. Then
$\left[\overline{w}^{\prime}\right]_{s}=\eta_{h}[w]_{s}\neq\eta_{g_{s}}\left[w\right]_{s}=\left[\overline{w}\right]_{s}$.
However, for a proportion of at least $\frac{97}{100}$ of shading sequences
$\upsilon\in\\{0,1\\}^{h_{n}}$, we have

$\displaystyle\overline{f}\left((\overline{w},\overline{\upsilon}),(\overline{w}^{\prime},\overline{\upsilon}^{\prime})\right)$
$\displaystyle\leq$
$\displaystyle\overline{f}\left((\overline{w},\overline{\upsilon}),\phi_{N}(w,\upsilon)\right)+\overline{f}\left(\phi_{N}(w,\upsilon),\phi_{N+k}(w,\upsilon)\right)+\overline{f}\left(\phi_{N+k}(w,\upsilon),(\overline{w}^{\prime},\overline{\upsilon}^{\prime})\right)$
$\displaystyle<$
$\displaystyle\frac{\alpha_{s}}{4}+\alpha^{4}_{s}+\frac{\alpha_{s}}{4}<\alpha_{s}.$

This contradicts Lemma 16. Thus, we conclude that $g_{s}\in G_{s}$ works for
all $\phi_{N}$ with $N\geq N(s)$.

Suppose that for some $s\in\mathbb{N}$, we have
$g_{s}^{\prime}\coloneqq\rho_{s+1,s}(g_{s+1})\neq g_{s}$. Let $N\geq N(s+1)$.
Let $n$ be sufficiently large such that $g^{\prime}_{s}\in G^{n}_{s}$ and
Claim 24 holds. Let $w\in\mathcal{W}^{\prime}_{n}$. Then
$\eta_{g_{s}^{\prime}}\left[w\right]_{s}\neq\eta_{g_{s}}\left[w\right]_{s},$
and by applying Claim 24, we obtain for a proportion of at least
$\frac{99}{100}$ of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$,
the existence of $\overline{w}_{1}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}_{1}\right]_{s}=\eta_{g_{s}}\left[w\right]_{s}$ and some
shading sequence $\overline{\upsilon}_{1}\in\\{0,1\\}^{h_{n}}$ such that

$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w}_{1},\overline{\upsilon}_{1})\right)<\frac{\alpha_{s}}{4}.$

Similarly, Claim 24 yields for a proportion of at least $\frac{99}{100}$ of
possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$, the existence of
$\overline{w}_{2}\in\operatorname{rev}(\mathcal{W}_{n})$ with
$\left[\overline{w}_{2}\right]_{s+1}=\eta_{g_{s+1}}\left[w\right]_{s+1}$ and
some shading sequence $\overline{\upsilon}_{2}\in\\{0,1\\}^{h_{n}}$ such that

$\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w}_{2},\overline{\upsilon}_{2})\right)<\frac{\alpha_{s+1}}{4}.$

Since the $G_{s+1}^{n}$ action is subordinate to the $G_{s}^{n}$ action on
$\mathcal{W}_{n}/\mathcal{Q}_{s}^{n}$ by specification (A7), we see that
$\left[\overline{w}_{2}\right]_{s+1}=\eta_{g_{s+1}}\left[w\right]_{s+1}$ lies
in $\eta_{g_{s}^{\prime}}\left[w\right]_{s}$. Hence,
$\left[\overline{w}_{2}\right]_{s}=\eta_{g_{s}^{\prime}}\left[w\right]_{s}\neq\eta_{g_{s}}\left[w\right]_{s}=\left[\overline{w}_{1}\right]_{s}$,
which implies
$\overline{f}\left((\overline{w}_{1},\overline{\upsilon}_{1}),(\overline{w}_{2},\overline{\upsilon}_{2})\right)>\alpha_{s}$
by Lemma 16. On the other hand, for a proportion of at least $\frac{98}{100}$
of possible shading sequences $\upsilon\in\\{0,1\\}^{h_{n}}$, we have

$\displaystyle\overline{f}\left((\overline{w}_{1},\overline{\upsilon}_{1}),(\overline{w}_{2},\overline{\upsilon}_{2})\right)$
$\displaystyle\leq$
$\displaystyle\overline{f}\left((\overline{w}_{1},\overline{\upsilon}_{1}),\phi_{N}(w,\upsilon)\right)+\overline{f}\left(\phi_{N}(w,\upsilon),(\overline{w}_{2},\overline{\upsilon}_{2})\right)$
$\displaystyle<$
$\displaystyle\frac{\alpha_{s}}{4}+\frac{\alpha_{s+1}}{4}<\frac{\alpha_{s}}{2}.$

This contradiction shows that $(g_{s})_{s\in\mathbb{N}}$ must satisfy
$g_{s}=\rho_{s+1,s}(g_{s+1})$ for all $s$. ∎

###### Proof of Part 1 (b) in Theorem B.

If the positive entropy systems $\mathbb{S}=\Upsilon(\mathcal{T})$ and
$\mathbb{S}^{-1}\cong\operatorname{rev}(\mathbb{S})$ are Kakutani equivalent,
then they have to be evenly equivalent. Then the conclusion of Lemma 23
implies that the tree $\mathcal{T}$ has an infinite branch. ∎

##  7\. Proof of Theorem C

###  7.1. Construction of $K$-diffeomorphisms $\Phi_{i}(\mathcal{T})$

As in Section 2.2, $\mathbb{T}^{n}=(\mathbb{R}/\mathbb{Z})^{n}$ and
$\lambda_{n}$ denotes Lebesgue measure on $\mathbb{T}^{n}$. To build the
$K$-diffeomorphisms $\Phi_{i}(\mathcal{T})\in$
Diff${}^{\infty}(\mathbb{T}^{5},\lambda_{5}),$ $i=1,2$ in Theorem 27, we
follow an approach in [Ka80]. We start with a $C^{\infty}$ Anosov
diffeomorphism $g$ of $\mathbb{T}^{2}$ that preserves $\lambda_{2}$. Note that
$g$ is ergodic by [An67] and therefore topologically transitive. We can choose
a $C^{\infty}$ function $\varphi:\mathbb{T}^{2}\mapsto\mathbb{R}^{+}$ with
$||\mathrm{d}\varphi||$ close to 0 so that there exists a closed orbit
$x,gx,\dots,g^{n-1}x,$ for $g$ such that

(7.1) $\sum_{j=0}^{n-1}\varphi(g^{j}(x))\neq n\int_{\mathbb{T}^{2}}\varphi\
\mathrm{d}\lambda_{2}.$

This condition implies that the cohomology equation

$\psi(gx)-\psi(x)=\varphi(x)-\int_{\mathbb{T}^{2}}\varphi\
\mathrm{d}\lambda_{2}$

has no continuous solution $\psi$, that is, $\varphi$ is not cohomologous to a
constant. In order for the Bernoulli shift $\mathbb{B}$ in Proposition 28
below to be the $(1/2,1/2)$ Bernoulli shift, we also require $\varphi$ to be
chosen so that

(7.2)
$\int_{\mathbb{T}^{2}}\varphi\,\mathrm{d}\lambda_{2}=\frac{h_{\lambda_{2}}(g)}{\log
2},$

where $h_{\lambda_{2}}(g)$ denotes the entropy of $g$ with respect to
$\lambda_{2}.$ As we shall see below, the required bound on
$||\mathrm{d}\varphi||$ depends only on $g$. Therefore, once $g$ is chosen, we
let $\varphi$ be a small $C^{1}$ perturbation of the constant function on the
right side of (7.2) that achieves (7.1) by making a small change in a
neighborhood of $x$ not including $gx,\dots,g^{n-1}x$, while maintaining the
value of the integral in (7.2).

If $F^{s}:\mathcal{T}rees\to$ Diff${}^{\infty}(\mathbb{T}^{2},\lambda_{2})$ is
as in [GKpp, section 10], and $T=F^{s}(\mathcal{T})$ for some
$\mathcal{T}\in\mathcal{T}rees,$ let $S^{t},$ $t\in\mathbb{R},$ be the special
flow over $T$ with roof function identically equal to $1$. As usual, $(y,1)$
is identified with $(Ty,0).$ That is, $S^{t}$ is defined on
$(\mathbb{T}^{2}\times[0,1])/((y,1)\sim(Ty,0)).$ Let $T_{g,\varphi}$ be the
skew product defined by $T_{g,\varphi}(x,(y,t))=(gx,S^{\varphi(x)}(y,t))$, for
$x,y\in\mathbb{T}^{2},$ $0\leq t\leq 1,$ with $(x,y,1)$ identified with
$(x,Ty,0)$. Then $T_{g,\varphi}$ preserves $\lambda_{5}$, and according to
[Ka80], $T_{g,\varphi}$ is a $K$-automorphism. However, the identification on
$\mathbb{T}^{2}\times\mathbb{T}^{2}\times[0,1]$ is $(x,Ty,0)\sim(x,y,1)$,
which depends on $T.$

To change $T_{g,\varphi}$ to a $K$-automorphism $\widetilde{T}_{g,\varphi}$
that is a diffeomorphism of $\mathbb{T}^{5}$ with the usual identification, we
will apply Proposition 26.

######  Proposition 26.

For each $\mathcal{T}\in\mathcal{T}rees$, the map
$T=F^{s}(\mathcal{T})\in\text{Diff}^{\,\infty}(\mathbb{T}^{2},\lambda_{2})$
constructed in [GKpp, section 10] is $C^{\infty}$ isotopic to the identity
through diffeomorphisms that preserve $\lambda_{2}$. Moreover, the map taking
$\mathcal{T}\in\mathcal{T}rees$ to the isotopy from Id to
$T=F^{s}(\mathcal{T})$ can be chosen to be a continuous function from
$\mathcal{T}rees$ to $C^{\infty}(\mathbb{T}^{2}\times[0,1],\mathbb{T}^{2}).$

###### Proof.

In the application of the Anosov-Katok method that is used in [GKpp, section
10], we may construct each $T$ in the image of $F^{s}$ to be as close as we
like in the $C^{\infty}$ topology to a fixed rotation
$R_{\alpha_{0}}(y_{1},y_{2})=(y_{1}+\alpha_{0},y_{2})$ of the first coordinate
in $\mathbb{T}^{2}$ (compare with [FW19a, Remark 39]). By [Hi76, Chapter 2,
Theorem 1.7] any $C^{\infty}$ map that is sufficiently close in the $C^{1}$
topology to a given $C^{\infty}$ diffeomorphism is itself a diffeomorphism.
Therefore we may assume that for each $u\in[0,1]$ and each $T$ in the image of
$F^{s}$ the map $uT+(1-u)R_{\alpha_{0}}$ is a diffeomorphism. Let
$\beta:[0,1]\to[0,1]$ be a monotone increasing $C^{\infty}$ function such that
$\beta(t)=p$ in a neighborhood of $p$ for $p=0,1/2$, and $1$. The requirement
that $\beta=1/2$ in a neighborhood of $1/2$ is needed to make the isotopy
$J_{t}$ below be $C^{\infty}$. The requirement that $\beta(t)=p$ in
neighborhoods of $p$ for $p=0,1$ is used later in our construction to make a
smooth identification between $\mathbb{T}^{2}\times\\{0\\}$ and
$\mathbb{T}^{2}\times\\{1\\}$. Let $J_{t}:\mathbb{T}^{2}\to\mathbb{T}^{2}$ for
$0\leq t\leq 1$ be the $C^{\infty}$ isotopy from Id to $T$ given by
$J_{t}=R_{2\beta(t)\alpha_{0}}$, for $0\leq t\leq 1/2$;
$(2-2\beta(t))R_{\alpha_{0}}+2(\beta(t)-1/2)T$, for $1/2<t\leq 1.$

Each map $J_{t}$ is a diffeomorphism of $\mathbb{T}^{2}$, but it need not
preserve $\lambda_{2}$ for those values of $t$ that are in $(1/2,1)$ where
$\beta(t)\neq 1/2,1.$ We will compose $J_{t}$ with another diffeomorphism
$L_{t}:\mathbb{T}^{2}\to\mathbb{T}^{2}$ such that $L_{t}$ is the identity for
$t$ in neighborhoods of $0$ and $1$, and $(L_{t}\circ
J_{t})_{*}\lambda_{2}=\lambda_{2}.$ This step is done using Moser’s Theorem
[Mo65], but we will show how to construct $L_{t}$ explicitly in terms of
Fourier series in order to demonstrate the $C^{\infty}$ dependence of $L_{t}$
on $t$ along with the continuous dependence of $L_{t}\circ J_{t}$ in
C${}^{\infty}(\mathbb{T}^{2}\times[0,1],\mathbb{T}^{2})$ on $\mathcal{T}$.

We follow Moser’s argument as presented in [KH95, Theorem 5.1.27]. Fix
$t\in[0,1]$ and use coordinates $y=(y_{1},y_{2})$ on $\mathbb{T}^{2}$. Let
$\Omega_{0}$ and $\Omega_{1}$ be the two-forms representing
$(J_{t})_{*}\lambda_{2}$ and $\lambda_{2}$, respectively. Let
$\Omega^{\prime}:=\Omega_{1}-\Omega_{0}.$ Since
$\int_{\mathbb{T}^{2}}\Omega^{\prime}=0$, $\Omega^{\prime}=$ d$\Theta$ for
some one-form $\Theta$. (This follows from the fact that the top deRham
cohomology group is $\mathbb{R}.)$ To find such a one-form $\Theta$, we write

$\Omega^{\prime}=f(y_{1},y_{2})\ \mathrm{d}y_{1}\land\mathrm{d}y_{2}.$

Since $f$ is a real-valued $C^{\infty}$ function with $\int_{\mathbb{T}^{2}}f\
\mathrm{d}\lambda_{2}=0,$ we have

$f(y_{1},y_{2})=\sum_{(n,m)\in(\mathbb{Z}\times\mathbb{Z})\setminus\\{(0,0)\\}}a_{(n,m)}\mathrm{exp}(i(ny_{1}+my_{2})),$

where $\overline{a}_{-(n,m)}=a_{(n,m)}$ and the Fourier coefficients
$a_{(n,m)}$ decay faster than any polynomial rate, that is,
$|a_{(n,m)}|\cdot||(n,m)||^{k}\to 0$ as $||(n,m)||\to\infty$ for every
positive integer $k$ (see [Fo92, Theorem 2.6]). Let
$\Theta=p(y_{1},y_{2})\mathrm{d}y_{1}+q(y_{1},y_{2})\mathrm{d}y_{2}.$ We need

(7.3) $\frac{\partial q}{\partial y_{1}}-\frac{\partial p}{\partial
y_{2}}=f(y_{1},y_{2}).$

We choose

$p(y_{1},y_{2})=p(y_{2})=-\mathrm{Re}\Big{[}\sum_{m\in\mathbb{Z},m\neq
0}\frac{a_{(0,m)}}{im}\mathrm{exp}(imy_{2})\Big{]},$

and

$q(y_{1},y_{2})=\mathrm{Re}\Big{[}\sum_{n,m\in\mathbb{Z},n\neq
0}\frac{a_{(n,m)}}{in}\mathrm{exp}(i(ny_{1}+my_{2}))\Big{]}.$

Then the Fourier coefficients of $p$ and $q$ also decay faster than any
polynomial rate, and therefore $p$ and $q$ are $C^{\infty}$ functions. Clearly
(7.3) is satisfied.

The rest of the Moser construction proceeds as in [KH95]. With the explicit
choice of $\Theta$ given above, the map $L_{t}$ with
$(L_{t})_{*}(J_{t})_{*}\lambda_{2}=\lambda_{2}$ that is obtained depends
continuously in the $C^{\infty}$ topology on $t\in[0,1]$. Moreover, because
$T=F^{s}(\mathcal{T})$ depends continuously in the $C^{\infty}$ topology on
$\mathcal{T}$, so does the isotopy $I_{t}:=L_{t}\circ J_{t}.$ ∎

Let $I:\mathbb{T}^{2}\times[0,1]\to\mathbb{T}^{2}$ be the isotopy constructed
in the proof of Proposition 26. Then $I_{u}(y)=I(y,u)$ satisfies $I_{u}=$Id
for $u$ in a neighborhood of $0$, $I_{u}=T$ for $u$ in a neighborhood of 1,
and $I_{u}\in$ Diff${}^{\infty}(\mathbb{T}^{2},\lambda_{2})$, for $0\leq u\leq
1.$ Let $\widetilde{S}^{t}$ be the $C^{\infty}$ flow on
$\mathbb{T}^{3}=(\mathbb{T}^{2}\times[0,1])/((y,1)\sim(y,0)),$ defined by
$\widetilde{S}^{t}(z,u)=(I_{u+t}(I_{u}^{-1}(z)),u+t),$ for nonnegative $u$ and
$t$ with $u+t\leq 1.$ For $u+t=1,$
$\widetilde{S}(z,u)=(T(I_{u}^{-1}(z)),1)\sim(T(I_{u}^{-1}(z)),0).$ Define

$\displaystyle\psi:(\mathbb{T}^{2}\times[0,1])/((Ty,0)\sim(y,1))\to\mathbb{T}^{3}=(\mathbb{T}^{2}\times[0,1])/((y,0)\sim(y,1))$
by $\displaystyle\psi(y,u)=(I_{u}(y),u),\text{\ for\ \ }y\in\mathbb{T}^{2},\
0\leq u\leq 1.$

Since $\psi(y,1)=(T(y),1)\sim(T(y),0)=\psi(T(y),0),$ $\psi$ is well-defined.
Moreover, $\psi$ preserves $\lambda_{3},$ because each $I_{u}$ preserves
$\lambda_{2}.$ For nonnegative $u$ and $t$ with $u+t\leq 1$, we have

$\psi(S^{t}(y,u))=\psi(y,u+t)=(I_{u+t}(y),u+t),$

and