Countable abelian group actions and hyperfinite equivalence relations

Abstract

An equivalence relation E on a standard Borel space is hyperfinite if E is the increasing union of countably many Borel equivalence relations $E_n$ where all $E_n$-equivalence classs are finite. In this article we establish the following theorem: if a countable abelian group acts on a standard Borel space in a Borel manner then the orbit equivalence relation is hyperfinite. The proof uses constructions and analysis of Borel marker sets and regions in the space $2^{{\mathbb {Z}}^{<\omega }}.$ This technique is also applied to a problem of finding Borel chromatic numbers for invariant Borel subspaces of $2^{{\mathbb {Z}}^n}$.

This paper is a contribution to the study of countable Borel equivalence relations on Polish spaces. A topological space X is Polish if it is separable and completely metrizable. An equivalence relation E on X is Borel if E is a Borel subset of $X\times X$; it is countable if each E-equivalence class is countable. By a well known theorem of Feldman and Moore [5] any countable Borel equivalence relation E on a Polish space X is the orbit equivalence relation of a Borel action of a countable group G.

Among all countable Borel equivalence relations the class of hyperfinite equivalence relations is best understood. An equivalence relation E is hyperfinite if $E=\bigcup _n E_n$ where $E_n\subseteq E_{n+1}$ and each $E_n$ is a Borel equivalence relation with all equivalence classes finite. A canonical example of a hyperfinite equivalence relation is the relation $E_0$ defined on the Cantor space $2^{\omega }$ as follows:

$$\begin{aligned} xE_0y\iff \exists m\ \forall n\ge m\ (x(n)=y(n)). \end{aligned}$$

It is also well known (c.f. [4]) that any hyperfinite equivalence relation is the orbit equivalence relation of a Borel action of ${\mathbb {Z}}.$ In fact, any Borel ${\mathbb {Z}}$-action gives rise to a hyperfinite equivalence relation. Other characterizations of hyperfinite equivalence relations and complete abstract classifications of hyperfinite equivalence relations can also be found in [4].

However, the following has been an outstanding open problem since 1980s: For which countable groups G do we have that any Borel G-action gives rise to only hyperfinite equivalence relations? Based on results in the measure theory context [3, 10] Weiss [12] asked if this is true for any amenable group. He also proved it for ${\mathbb {Z}}^n.$ A more general result by Jackson et al. [8] shows this for any finitely generated group with polynomial growth (by a famous theorem of Gromov this is exactly the class of finitely generated groups that are nilpotent-by-finite).

The main theorem of this paper is to prove that a Borel action of any countable abelian group gives rise to a hyperfinite equivalence relation. To achieve this it suffices to show the hyperfiniteness of a specific orbit equivalence relation, that is, the shift action of ${\mathbb {Z}}^{<\omega }$ on the space of its subsets $2^{{\mathbb {Z}}^{<\omega }}.$ Much of the effort is to reprove Weiss’ result that the shift action of ${\mathbb {Z}}^n$ on $2^{{\mathbb {Z}}^n}$ gives rise to a hyperfinite equivalence relation. In the new proof a theory of Borel marker sets and regular Borel marker regions is developed. This allows us to prove stronger results such as that there is a continuous (even computable) reduction from the shift action of ${\mathbb {Z}}^n$ into $E_0.$ We also present another application of this theory to a problem on Borel chromatic numbers.

1 Preliminaries

In this first section we recall some general definitions and fix the notation to be used throughout the paper. More ad hoc definitions and notation will be introduced in later sections.

If E is an equivalence relation on the Polish space X,  and F an equivalence relation on the Polish space Y,  then we say E is Borel reducible to F,  written $E \le _B F,$ if there is a Borel function $f :X \rightarrow Y$ such that

$$\begin{aligned} \forall x, y \in X\ (xEy \leftrightarrow f(x) F f(y)). \end{aligned}$$

The function f is called a Borel reduction from E to F,  and we also say that f Borel reduces E to F. Any Borel reduction from E to F induces an injection from the quotient space X / E into Y / F. We say E is Borel embeddable into F,  written $E \sqsubseteq _B F,$ if there is a one-to-one Borel function $f :X \rightarrow Y$ which reduces E to F. In this case we call f a Borel embedding of E into F. The notion of Borel reduction is fundamental in the theory of definable equivalence relations. Sometimes the reduction function f can be continuous or even computable (or recursive). In these cases we will speak of continuous (resp. computable) reductions and continuous (resp. computable) embeddings.

A particular case of interest is when the equivalence relation is generated by a Polish group action. Let G be a Polish group, X a Polish space and $a: G\times X\rightarrow X$ a continuous action of G on X. In this context X is called a Polish G -space. We use the abbreviation $g\cdot x$ to denote a(g, x) if there is no danger of confusion.

The action is free if for any $g\in G$ with $g\ne 1_G$ and any $x\in X,$ $g\cdot x\ne x.$ For any Polish G-space X the free part of the action is the subset of X defined by

$$\begin{aligned} F_G(X)=\{ x\in X:\forall g\in G\,(g\ne 1_G\rightarrow g\cdot x\ne x)\}. \end{aligned}$$

In general $F_G(X)$ is an invariant ${\varvec{\Pi }}^1_1$ subset of X. In case G is countable (and the action is continuous) $F_G(X)$ is an invariant $G_\delta$ subset of X,  and therefore $F_G(X)$ naturally becomes a Polish G-space.

If X is a Polish G-space, the orbit equivalence relation, denoted by $E^X_G,$ is defined as follows: for $x, y\in X,$

$$\begin{aligned} x E^X_G y\iff \exists g\in G\,(g\cdot x=y). \end{aligned}$$

In case the action is free, $E^X_G$ is a Borel equivalence relation (as a subset of $X\times X$). Alternatively, if G is countable (and the action is continuous), the orbit equivalence relation $E^X_G$ is $F_\sigma .$ If Y is a subset of X,  then we denote the equivalence relation $E^X_G\upharpoonright (Y\times Y)$ simply by $E^X_G\upharpoonright Y.$

If X is a Polish G-space and $x\in X,$ we denote the orbit or the equivalence class of x by

$$\begin{aligned}{}[x]_G=\{ g\cdot x:g\in G\}. \end{aligned}$$

In general, if E is an equivalence relation on X and $x\in X,$ we let $[x]_E$ denote the E-equivalence class of x:

$$\begin{aligned}{}[x]_E=\{ y\in X:yEx\}. \end{aligned}$$

In case there is no danger of confusion we will omit all the subscripts.

Throughout the paper we will consider only countable groups G,  which are Polish groups with the discrete topology. In fact, we will mostly consider a specific Polish G-space. Let $2^G$ denote the power set of G,  or equivalently the product space $\prod _{g\in G}\{0,1\}$ with the product topology, where $2=\{0,1\}$ is equipped with the discrete topology. $2^G$ is a Polish space. If $D\subseteq G$ is a finite subset then a function $s:D\rightarrow 2$ determines a basic (cl)open set

$$\begin{aligned} N_s=\{ x\in 2^G:\forall g\in D\, (x(g)=s(g))\}. \end{aligned}$$

For $x\in N_s$ we also write $s\subseteq x.$ We also denote the set

$$\begin{aligned} \{ s: D\rightarrow 2:D\subseteq G \hbox { finite}\} \end{aligned}$$

by $2^{<G}.$ For $s, t\in 2^{<G},$ we say that s and t are incompatible if there is $g\in \mathrm{dom}(s)\cap \mathrm{dom}(t)$ with $s(g)\ne t(g)$; otherwise s and t are said to be compatible. We write $s\subseteq t$ and say that t extends s if s and t are compatible and $\mathrm{dom}(s)\subseteq \mathrm{dom}(t).$

Consider the natural shift action of G on $2^G$: for $A\subseteq G$ and $g\in G,$

$$\begin{aligned} g\cdot A=\{gh:h\in A\}. \end{aligned}$$

This action is continuous. For convenience we will denote the orbit equivalence relation $E^{2^G}_G$ simply by E(G). We also denote by F(G) the free part of this action as well as the equivalence relation $E(G)\upharpoonright F(G).$

We will also work with the natural shift action of G on $2^{<G}$: if $g\in G$ and $s:D\rightarrow 2$ where $D\subseteq G$ is finite, then $g\cdot s:g\cdot D\rightarrow 2$ and for $h\in g\cdot D,$

$$\begin{aligned} (g\cdot s)(h)= s(g^{-1}h). \end{aligned}$$

Most of the time we work with groups $G=\mathbb {Z}^n$ for some positive integer n. They will be expressed as additive groups as usual. When n is fixed we denote by $e_1, e_2,\ldots , e_n$ the group elements

$$\begin{aligned} e_1&= (1,0,\ldots , 0),\\ e_2&= (0,1,\ldots ,0),\\&\qquad \cdots \cdots \\ e_n&= (0,0,\ldots , 1). \end{aligned}$$

We will refer to them as the generators of $\mathbb {Z}^n.$ Any $g\in \mathbb {Z}^n$ can be uniquely expressed as $(g_1,g_2,\ldots , g_n)$ or $g_1e_1+g_2e_2+\cdots +g_ne_n$ for $g_1,g_2,\ldots , g_n\in \mathbb {Z}.$ We define a norm on $\mathbb {Z}^n$ by

$$\begin{aligned} \Vert g\Vert =\Vert (g_1,g_2,\ldots , g_n)\Vert =\max \{|g_1|, |g_2|, \ldots , |g_n|\}. \end{aligned}$$

The norm induces a distance function on $\mathbb {Z}^n$: for $g,h\in \mathbb {Z}^n,$

$$\begin{aligned} \rho (g,h)=\Vert g-h\Vert . \end{aligned}$$

When $G=\mathbb {Z}^n$ acts on $X=F(G)=F(\mathbb {Z}^n)$ the above distance function induces further a distance function on X as follows:

$$\begin{aligned} \rho _X(x,y)={\left\{ \begin{array}{ll} \Vert g\Vert , &{} \hbox {if}\;g\cdot x=y,\\ \infty , &{}\hbox {if}\;(x,y)\not \in E(G). \end{array}\right. } \end{aligned}$$

Note that this is well defined since the action is free. When there is no danger of confusion we will drop the subscript X in denoting $\rho _X.$ When $M\subseteq X$ and $x\in X,$ we also define, as usual,

$$\begin{aligned} \rho (x,M)=\inf \{ \rho (x,y):y\in M\}. \end{aligned}$$

In addition, if $S_1, S_2\subseteq X,$ we also let

$$\begin{aligned} \rho (S_1, S_2)=\inf \{\rho (x,y):x\in S_1,\ y\in S_2\}. \end{aligned}$$

This distance function is not to be confused with the genuine metric d on $2^{\mathbb {Z}^n}$ defined by

$$\begin{aligned} d(x,y)=\left\{ \begin{array}{l@{\quad }l} 0,&{}\hbox { if}\;x=y, \\ 2^{-\min \{ \Vert g\Vert :x(g)\ne y(g)\}}, &{}\hbox { otherwise}.\end{array}\right. \end{aligned}$$

Note that d is in fact an ultrametric, i.e.,

$$\begin{aligned} d(x,y)\le \max \{ d(x,z),d(y,z)\} \end{aligned}$$

for any $x,y,z\in 2^{\mathbb {Z}^n}.$

The set of natural numbers (nonnegative integers) will be denoted as $\omega .$ We also use the interval notation: if $a, b\in \mathbb {Z}$ and $a<b,$ then [a, b] denotes the set $\{c\in \mathbb {Z}:a\le c\le b\}.$

Throughout the paper we also fix a linear order $<_n$ on $\mathbb {Z}^n$ so that $\Vert g\Vert <\Vert h\Vert$ implies $g<_n h.$ For instance, elements of $\mathbb {Z}$ can be enumerated according to $<_1$ as

$$\begin{aligned} 0, -1, 1, -2, 2, \ldots , -k, k, \ldots . \end{aligned}$$

The equivalence relation $E_0$ on $2^\omega$ defined previously is the prototypical hyperfinite equivalence relation. All of the proofs of hyperfiniteness in this paper will proceed by showing that the equivalence relation E reduces to (or embeds into) $E_0.$ In this regard we note the simple fact that it does not matter if we use $E_0=E_0(2^\omega )$ on $2^\omega$ or the variation $E_0(\omega ^\omega )$ on $\omega ^\omega ,$ defined as the eventual equality relation on sequences of natural numbers. We state this in the following proposition.

Proposition 1.1

There is a continuous (in fact computable or recursive) embedding from $E_0(\omega ^\omega )$ to $E_0(2^\omega ).$

Proof

Let $\pi :\omega \rightarrow \omega \times \omega$ be a computable bijection between $\omega$ and $\omega \times \omega .$ Let $\pi (n)=(\pi _0(n), \pi _1(n)).$ For every $k \in \omega ,$ let $((k)_0, (k)_1, \ldots )$ be the base-2 expansion of k,  that is, $k= \sum _i (k)_i \cdot 2^i$ (so for large enough i,  $(k)_i=0$). Define $f :\omega ^\omega \rightarrow 2^\omega$ by: $f(x)(n)= (x(\pi _0(n)))_{\pi _1(n)}.$ f is easily an embedding, and is computable. $\square$

2 Clopen marker sets

Throughout this section we fix a positive integer n.

Lemma 2.1

(Basic clopen marker lemma) Let d be a positive integer. Then there is a relatively clopen set $S\subseteq F(\mathbb {Z}^n)$ such that

(i):

if $x,y\in S$ are distinct, then $\rho (x,y)>d$;

(ii):

for any $x\in F(\mathbb {Z}^n),$ $\rho (x,S)\le d.$

Proof

Let $s_0,s_1,\ldots$ enumerate all elements s of $2^{<\mathbb {Z}^n}$ such that $g\cdot N_s\cap N_s=\emptyset$ for all $g\in \mathbb {Z}^n$ with $0<\Vert g\Vert \le d.$ Define a sequence of sets $S_i$ by induction on i. For $i=0$ let $S_0=N_{s_0}.$ For $i>0$ let

$$\begin{aligned} S_i= S_{i-1}\cup \left( N_{s_i}- \bigcup _{\Vert g\Vert \le d} g\cdot S_{i-1}\,\right) . \end{aligned}$$

Finally let $S=\bigcup _i S_i\cap F(\mathbb {Z}^n).$

By induction on i we show that if $x,y\in S_i$ are distinct, then $\rho (x,y)>d.$ If $i=0$ and $x,y\in S_0$ then $x,y\in N_{s_0}.$ Suppose $\rho (x,y)\le d.$ In particular there is $g\in \mathbb {Z}^n$ with $g\cdot x=y$ and $\Vert g\Vert \le d.$ This implies that $g\cdot N_{s_0}\cap N_{s_0}\ne \emptyset ,$ contradicting our choice of $s_0.$ Thus we have $\rho (x,y)>d.$ Now suppose $i>0$ and $x,y\in S_i.$ A similar argument as above shows that x and y cannot be both in $N_{s_i}.$ By induction we may also assume that x and y are not both in $S_{i-1}.$ Thus without loss of generality we may assume that $x\in S_{i-1}-N_{s_i}$ and $y\in N_{s_i}-S_{i-1}.$ Assume $\rho (x,y)\le d.$ In particular there is $g\in \mathbb {Z}^n$ with $g\cdot x=y$ and $\Vert g\Vert \le d.$ It follows that $y\in \bigcup _{\Vert g\Vert \le d} g\cdot S_{i-1},$ contradicting $y\in S_i.$ Thus again we have $\rho (x,y)>d.$

To verify clause (ii) note that for any $x\in F(\mathbb {Z}^n)$ there is $s_i$ with $x\in N_{s_i}.$ In fact, if no such $s_i$ exists then there is $g\in \mathbb {Z}^n$ with $0<\Vert g\Vert \le d$ such that $g\cdot N_s\cap N_s\ne \emptyset$ for all $s\subseteq x.$ The continuity of the action then implies that $g\cdot x=x,$ contradicting the assumption that the action is free. Now let $x\in F(\mathbb {Z}^n)$ and let i be the smallest such that $x\in N_{s_i}.$ If $x\in S_i$ then $x\in S$ and $\rho (x,S)=0,$ therefore we are done. Otherwise, assume $x\not \in S_i.$ By the definition of $S_i$ it follows that $x\in \bigcup _{\Vert g\Vert \le d} g\cdot S_{i-1}.$ This is to say that there are $g\in \mathbb {Z}^n$ with $\Vert g\Vert \le d$ and $y\in S_{i-1}$ such that $g\cdot y=x,$ and thus $\rho (x,S)\le \rho (x,y)\le d.$

Finally we check that S is clopen in $F(\mathbb {Z}^n).$ By induction on i it is easy to see that each $S_i$ is clopen. Thus it follows immediately from the definition that S is open in $F(\mathbb {Z}^n).$ The argument in the preceding paragraph gives that if $x\in F(\mathbb {Z}^n)-S$ then $x\in \bigcup _{0<\Vert g\Vert \le d} g\cdot S.$ Conversely if $x\in \bigcup _{0<\Vert g\Vert \le d} g\cdot S$ then by (i) we have that $s\not \in S.$ Thus $x\in F(\mathbb {Z}^n)-S$ iff $x\in \bigcup _{0<\Vert g\Vert \le d} g\cdot S.$ Since S is open and the action is continuous, this shows that $F(\mathbb {Z}^n)-S$ is open. $\square$

Remark 2.1

• (1) In the above proof the set $S'=\bigcup _i S_i$ is in fact an open set in $2^{\mathbb {Z}^n}$ satisfying both clauses (i) and (ii). A closer scrutiny shows that $S'$ is $\Sigma ^0_1$ and S is $\Delta ^0_1$ in $F(\mathbb {Z}^n).$ In [2] it was already shown that there is a continuous reduction from $E(\mathbb {Z})$ to $E_0$ on $2^\omega .$ Enhanced by these computability considerations one can show that there is a computable reduction from $E(\mathbb {Z})$ to $E_0.$ Later in Sect. 9 we generalize this to $E(\mathbb {Z}^n)$ for all finite $n\ge 1.$

• (2) Clause (ii) implies that S is in fact a complete section for the action of $\mathbb {Z}^n$ on $F(\mathbb {Z}^n),$ that is, S meets every equivalence class (i.e., for any $x\in F(\mathbb {Z}^n),$ $S\cap [x]\ne \emptyset$). Elements of S are customarily called markers or marker points. The set S itself is called a marker set.

• (3) In the remainder of this article we will refer to the properties (i) and (ii) as basic marker properties. The integer d will be referred to as a marker distance and the set S the basic marker set for the marker distance d.

Marker arguments started from Slaman–Steel’s proof of hyperfiniteness of $E(\mathbb {Z})$ in [11]. In this proof an infinite descending and vanishing sequence of Borel marker sets was constructed and then used to show that $E(\mathbb {Z})$ is an increasing union of finite Borel equivalence relations. In our context if $F(\mathbb {Z})$ admits a sequence

$$\begin{aligned} S_0\supseteq S_1\supseteq \cdots \supseteq S_k\supseteq \cdots \end{aligned}$$

of descending clopen marker sets so that $\bigcap _k S_k=\emptyset ,$ then the Slaman–Steel argument would give another continuous reduction from $F(\mathbb {Z})$ to $E_0$ (different from the one constructed in [2]). Thus it is a natural question whether such a sequence of clopen marker sets exists.

We first note that basic clopen marker sets can always be thinned down by specifying a sufficiently larger marker distance.

Lemma 2.2

Let d be a positive integer and $S_0$ be a basic clopen marker set in $F(\mathbb {Z}^n)$ for the marker distance d. Let $D>2d$ be a positive integer. Then there is a clopen set $S_1\subseteq S_0$ such that

• (i) if $x,y\in S_1$ are distinct, then $\rho (x,y)>D-2d$;

• (ii) for any $x\in F(\mathbb {Z}^n),$ $\rho (x,S_1)\le D+d.$

Proof

Let $S'$ be a basic clopen marker set for the marker distance D. Let $<$ be a linear order of the (finite) set $B=\{ g\in \mathbb {Z}^n:\Vert g\Vert \le d\}.$ Then for $x\in S_0$ let $x\in S_1$ iff there is $g\in B$ such that $g\cdot x\in S'$ and that for all $h\in B$ with $h<g,$ $h^{-1}g\cdot x\not \in S_0.$ It is clear from the definition and the continuity of the action that $S_1$ is clopen. It is useful to note that for each $z\in S'$ there is exactly one $x\in S_1$ with $\rho (x,z)\le d.$ In fact, by the basic marker properties of $S_0,$ for each $z\in S'$ there is at least one $x\in S_0$ with $\rho (x,z)\le d,$ and thus the set

$$\begin{aligned} \{ g\in B:g^{-1}\cdot z\in S_0\} \end{aligned}$$

is nonempty. Let g be the $<$-least element of this set and let $x=g^{-1}\cdot z.$ Then for all $h\in B$ with $h<g,$ $h^{-1}g\cdot x=h^{-1}\cdot z\not \in S_0.$ Therefore x is the unique element of $S_1$ with $\rho (x,z)\le d.$ Conversely, for any $x\in S_1$ there is also exactly one $z\in S'$ with $\rho (x,z)\le d,$ by a similar proof.

Now the conditions (i) and (ii) are easy to check. Let $x,y\in S_1$ be distinct and let $u,v\in S'$ be such that $\rho (x,u),\rho (y,v)\le d.$ Then by the basic marker properties of $S',$ $\rho (u,v)>D.$ Thus $\rho (x,y)\ge \rho (u,v)-\rho (x,u)-\rho (y,v)>D-2d.$ On the other hand, let $x\in F(\mathbb {Z}^n)$ and $z\in S'$ be such that $\rho (x,z)\le D.$ Let $y\in S_1$ be such that $\rho (y,z)\le d.$ Then $\rho (x,S_1)\le \rho (x,y)\le \rho (x,z)+\rho (y,z)\le D+d.$ $\square$

Note that we cannot guarantee that $S_1$ has the exact basic marker properties for any distance. However, when $D\gg d,$ the terms $D-2d$ and $D+d$ are both fairly close to D. For practical purposes these approximate marker properties are good enough for our arguments. For notational convenience we will use the following terminology. Let d be a positive integer and $0<\epsilon <1$ be a real number. A marker set $S\subseteq F(\mathbb {Z}^n)$ is said to satisfy the $(d,\epsilon )$-marker properties if

• (i) if $x,y\in S$ are distinct, then $\rho (x,y)>(1-\epsilon )d$;

• (ii) for any $x\in F(\mathbb {Z}^n),$ $\rho (x,S)\le (1+\epsilon )d.$

This will allow us to iterate the argument in the above proof and generate an infinite descending sequence of clopen marker sets with arbitrarily prescribed approximate marker properties.

Lemma 2.3

Let d be a positive integer, $0<\epsilon <1$ a real number and $S_0$ a clopen marker set in $F(\mathbb {Z}^n)$ satisfying the $(d,\epsilon )$-marker properties. Let $0<\delta <1$ be a real number. Then there is a positive integer D and a clopen set $S_1\subseteq S_0$ satisfying the $(D,\delta )$-marker properties.

Proof

It is easy to see if we choose D so that $\delta D>2d(1+\epsilon )$ and $S'$ to be a basic clopen marker set for the marker distance D,  then the proof of the preceding lemma gives the desired $S_1\subseteq S_0$ with appropriate approximate marker properties. $\square$

In this lemma it is obvious that $S_1$ will be a proper subset of $S_0$ if D is sufficiently large. Better yet, we can guarantee that $S_1$ is sparse in $S_0$ (on each equivalence class under an appropriately defined density notion). By iterating the lemma we can thus create an infinite descending sequence of clopen marker sets each of which is sparse in the previous set. If S is the intersection of all these clopen marker sets then for each $x\in F(\mathbb {Z}^n)$ either $S\cap [x]=\emptyset$ or $S\cap [x]$ is a singleton. We have thus proved the following fact.

Proposition 2.4

There exists an infinite descending sequence of clopen complete sections of $F(\mathbb {Z}^n)$

$$\begin{aligned} S_0\supseteq S_1\supseteq \cdots \supseteq S_k\supseteq \cdots \end{aligned}$$

such that for each $x\in F(\mathbb {Z}^n),$ $|\bigcap _kS_k\cap [x]|\le 1.$

Note that $\bigcap _kS_k\cap [x]=\emptyset$ must hold for some $x\in F(\mathbb {Z}^n),$ since the equivalence relation $F(\mathbb {Z}^n)$ is non-smooth. The following theorem shows that $\bigcap _kS_k\cap [x]=\emptyset$ cannot hold for every $x\in F(\mathbb {Z}^n),$ in other words, $\bigcap _kS_k\cap [x]\ne \emptyset$ must also hold for some $x\in F(\mathbb {Z}^n).$ This gives a negative answer to the question following Remark 2.1, and hence a continuous reduction from $F(\mathbb {Z})$ to $E_0$ has to come from an argument different than Slaman–Steel’s.

Theorem 2.5

(c.f. [6]) Let $S_0\supseteq S_1\supseteq \cdots \supseteq S_k\supseteq \cdots$ be an infinite descending sequence of closed complete sections of $F(\mathbb {Z}^n).$ Then $\bigcap _kS_k\ne \emptyset .$

The theorem is a special case of the main theorem proved in [6] as the authors’ joint work with B. Seward, which we state below.

Theorem 2.6

(Gao et al. [6]) Let G be a countable group and let $S_0\supseteq S_1\supseteq \cdots \supseteq S_k\supseteq \cdots$ be an infinite descending sequence of closed complete sections of F(G). Then $\bigcap _kS_k\ne \emptyset .$

A more direct proof of Theorem 2.5 can be found in the recent [7], Section 3.3.

The following two propositions rule out the existence of marker sets which are “too regular”. The proof essentially uses the fact that the ${\mathbb {Z}}^n$-action on $F({\mathbb {Z}}^n)$ is strongly mixing and therefore the action of any subgroup is ergodic.

Proposition 2.7

There is no Borel marker set $M\subseteq F(\mathbb {Z})$ such that for any $x\in F(\mathbb {Z})$ there is some $d>1$ such that for all $y,z\in [x]\cap M,$ $\rho (y,z)$ is a multiple of d.

Proof

Let $\mu$ be the product measure on $2^\mathbb {Z}.$ Then $\mu$ is a $\mathbb {Z}$-invariant, non-atomic, ergodic, Borel probability measure. Its restriction to $F(\mathbb {Z}),$ which we still denote by $\mu ,$ continues to be such a measure on $F(\mathbb {Z}).$ Now assume M is a Borel marker set with the stated property. Then for each $x\in F(\mathbb {Z})$ let $d_x>1$ be the largest integer such that $\rho (y,z)$ is a multiple of $d_x$ for all $y,z\in M\cap [x].$ For each integer $d>1$ let $X_d=\{x\in F(\mathbb {Z}):d_x=d\}$. Also let $X_1=\{x\in F(\mathbb {Z}):|[x]\cap M|=1\}.$ Then $\{X_d:d\ge 1\}$ form a countable partition of M into $\mathbb {Z}$-invariant Borel subsets. Since $M\cap X_1$ is a Borel transversal on $X_1,$ $\mu (X_1)=0.$ By ergodicity there is some $d>1$ such that $\mu (X_d)=1.$

Let $M_d=(d\mathbb {Z})\cdot (M\cap X_d).$ Then $M_d$ is a Borel complete section of $F(\mathbb {Z})\!\upharpoonright \! X_d$ so that for any $x\in M_d$ and $y\in [x],$ $y\in M_d$ iff $\rho (x,y)$ is a multiple of d. It follows that $X_d=M_d\cup 1 \cdot M_d\cup \cdots \cup (d-1)\cdot M_d.$

Now consider the action of $d\mathbb {Z}$ on $X_d.$ Then $\mu \upharpoonright X_d$ is $d\mathbb {Z}$-invariant, non-atomic, and ergodic. Moreover, the sets $M_d,\ldots , (d-1)\cdot M_d$ are $d\mathbb {Z}$-invariant Borel subsets with the same $\mu$-measure. This is a contradiction since on the one hand each of them should have measure 1 / d,  and on the other hand each should have measure either 0 or 1. $\square$

The following generalization can be established by a similar proof.

Proposition 2.8

There is no Borel marker set $M\subseteq F(\mathbb {Z}^n)$ such that for any $x\in M$ there is a proper subgroup G of $\mathbb {Z}^n$ such that $[x]\cap M\subseteq G\cdot x.$

In contrast to this we note that it is possible to construct marker sets with a moderately regular pattern. This is made precise by the following result. The proof of the following lemma also provides a preview of a technique, called big-marker-little-marker argument, which will be important in later constructions.

Lemma 2.9

For any integer $d>0$ there is a clopen marker set $M_d\subseteq F(\mathbb {Z})$ such that

• (i) for all $z\in F(\mathbb {Z})$ there is $x\in M_d$ with $\rho (x,z)\le d,$ and

• (ii) for all $x,y \in M_d,$ if $\rho (x,y)<2d+1$ then $\rho (x,y)\in \{d+1,d+2\}.$

Proof

Let $D=(d+1)^2$ and $M_D$ be the clopen marker set obtained from applying the Basic Clopen Marker Lemma. For each $i\in [D+1, 2D+1]$ let

$$\begin{aligned} M_{D,i}=\{ x\in M_D:i\cdot x\in M_D\}. \end{aligned}$$

Then $\{ M_{D,i}\, |\, i\in [D+1, 2D+1]\}$ form a partition of $M_D$ into clopen sets. Now for each $i\in [D+1,2D+1]$ let

$$\begin{aligned} i=q_i(d+1)+r_i,\quad \hbox {where}\;q_i, r_i\in \omega \quad \hbox {and}\quad 0\le r_i<d+1. \end{aligned}$$

Here $q_i\ge d$ since $i>D=(d+1)^2.$ Thus one can write

$$\begin{aligned} i=(q_i-r_i)(d+1)+r_i(d+2)=a_i(d+1)+b_i(d+2) \end{aligned}$$

for some integer $a_i, b_i\ge 0.$ Let

$$\begin{aligned} G_i=\{ k(d+1)\,|\, k\le a_i\}\cup \{ a_i(d+1)+k'(d+2)\,|\, k'<b_i\}. \end{aligned}$$

Define

$$\begin{aligned} M_{d,i}=M_{D,i}\cup G_i\cdot M_{D,i}, \end{aligned}$$

and $M_d=\bigcup _i M_{d,i}.$ Then it is easy to check that $M_d$ is as required. $\square$

A generalization of this is the main theorem of the next section.

3 Regular marker regions

Recall that in general a marker set is a Borel complete section of $F(\mathbb {Z}^n).$ In the preceding section we studied the existence of marker sets for $F(\mathbb {Z}^n)$ with various additional properties. The main new property considered is the clopenness. Marker sets constructed in earlier research have been successfully applied to show hyperfiniteness of equivalence relations. Slaman and Steel [11] constructed Borel marker sets for arbitrary countable Borel equivalence relations and used the marker sets for $F(\mathbb {Z})$ to show that $E(\mathbb {Z})$ is hyperfinite. Later several proofs of hyperfiniteness of $E(\mathbb {Z}^n)$ for $n>1$ were found, but all of them are based on constructions of Borel marker sets for $F(\mathbb {Z}^n).$ In all of these proofs, an important technique is to decompose the equivalence classes into finite marker regions. We recall two examples below, but first we make a notational point to be used throughout. When we represent an equivalence class $[x] \in F(\mathbb {Z}^n)$ pictorially, we arrange the elements of [x] in a $\mathbb {Z}^n$ grid according to the group action. For example, for $n=2,$ the element $(1,0)\cdot x$ is the point immediately to the right of x and $(0,1)\cdot x$ is the point immediately above x. We cannot, in a Borel manner, pick a point $x_0\in [x]$ to serve as an “origin” for this representation, but we can nevertheless represent [x] (or subsets of [x],  etc.) in this manner.

Example 3.1

Let $M\subseteq F(\mathbb {Z})$ be a Borel marker set. For each $x\in F(\mathbb {Z})$ define

$$\begin{aligned} l_M(x)\simeq \left\{ \begin{array}{ll} (-n)\cdot x, &{}\quad \hbox {if}\;n\in \omega \;\hbox {is the least such that}\, (-n)\cdot x\in M, \\ \hbox {undefined}, &{}\quad \hbox {if no such}\;n\;\hbox {exists}. \end{array}\right. \end{aligned}$$

Then define a subequivalence relation $R_M$ of $F(\mathbb {Z})$ by

$$\begin{aligned} xR_M y \iff [x]=[y]\quad \text {and}\quad l_M(x)\simeq l_M(y). \end{aligned}$$

(Recall that if f and g are partial functions, then $f(x)\simeq g(x)$ if both f(x) and g(x) are defined and $f(x)=g(x),$ or both f(x) and g(x) are undefined.) It can be easily seen that for each $x\in F(\mathbb {Z}),$ the $R_M$-equivalence class of x is of the form $I\cdot x$ for an interval I in $\mathbb {Z}$ (which is possibly infinite). For this reason we say that $R_M$ gives a partition of all $F(\mathbb {Z})$-equivalence classes into marker intervals (see Fig. 1).

Fig. 1

Marker intervals with marker points highlighted

Conversely, suppose R is a Borel subequivalence relation of $F(\mathbb {Z})$ so that for every $x\in F(\mathbb {Z}),$ $[x]_R\ne [x]$ and $[x]_R=I\cdot x$ for some interval I in $\mathbb {Z}.$ Then by taking all the left end points of the intervals I we recover a marker set $M_R.$ It is also easy to see that the above procedures are inverses of each other, i.e., $R_{M_R}=R$ and $M_{R_M}=M.$

Example 3.2

Let $M\subseteq F(\mathbb {Z}^n)$ be a Borel marker set. For each $x\in F(\mathbb {Z}^n)$ define $c_M(x)=g\cdot x,$ where g is the $<_n$-least element of $\mathbb {Z}^n$ such that $g\cdot x\in M.$ Note that since M is a complete section of $F(\mathbb {Z}^n),$ $c_M$ is always defined. Then we can again define a subequivalence relation $R_M$ of $F(\mathbb {Z}^n)$ by

$$\begin{aligned} xR_M y\iff c_M(x)=c_M(y). \end{aligned}$$

When $n=1,$ each of the $R_M$-equivalence classes is still a marker interval; however they are different from the ones constructed in the preceding example (see Fig. 2). When $n>1,$ the $R_M$-equivalence classes are called Dirichlet regions.

Fig. 2

An alternative construction of marker intervals

The terminology comes from a geometric construction in $\mathbb {R}^n,$ which we describe informally below. For this discussion, we use the standard Euclidean metric on $\mathbb {R}^n$ and $\mathbb {Z}^n$ (although we could use the sup norm we fixed earlier; the description is a little cleaner if we use the standard metric). Fix $x\in F(\mathbb {Z}^n).$ Write $M\cap [x]=J\cdot x$ for $J\subseteq \mathbb {Z}^n.$ Regard J as a subset of $\mathbb {R}^n.$ For each pair of distinct elements (p, q) of J find the perpendicular bisector (in the usual metric of $\mathbb {R}^n$) of the line segment pq,  which is a hyperplane in $\mathbb {R}^n.$ Then the Dirichlet regions in $\mathbb {R}^n$ (see Fig. 3) are polygonal regions with segments of these perpendicular bisectors as boundaries. They are characterized by the property that each region $J_0$ contains a unique element $p_0$ of J in its interior so that $J_0$ consists of points whose distance to $p_0$ is smaller than its distance to any other points in J.

Fig. 3

Two-dimensional Dirichlet regions

In particular let $J_0$ be the region containing the origin. Then $(J_0\cap \mathbb {Z}^n)\cdot x$ is the Dirichlet region of x given by $R_M.$ We remark that the construction is invariant. The precise meaning of this invariance is that, if we instead fix $x'=g\cdot x$ with $g\ne 0,$ then the Dirichlet regions constructed in $\mathbb {R}^n$ for $x'$ are the result of applying a shift by $g^{-1}$ to the Dirichlet regions constructed in $\mathbb {R}^n$ for x. Thus by following the construction for x we will be able to recover the Dirichlet region for $x'.$ We also remark that the discussion in this paragraph only gives the main idea of the construction. The details are incomplete, because we did not address what to do if a lattice point in $\mathbb {R}^n$ falls exactly on the boundary of a region. In this case the lattice point will be regarded as being contained in only one of the Dirichlet regions, and the conflict (among all the Dirichlet regions having this element on the boundary) is resolved according to the linear order $<_n.$ We omit the precise details for now. We note that the arguments in this paper will not use Dirichlet regions, but regions which are “rectangles”. We discuss the meaning of this below.

These examples illustrate how the geometries of $\mathbb {R}^n$ come into play in the study of hyperfiniteness of countable equivalence relations. In order to explore this connection more easily we fix some terminology to be used for the rest of the paper. In general by marker regions we mean the R-equivalence classes for some Borel subequivalence relation R of $F(\mathbb {Z}^n).$ Now fix an $x_0\in F(\mathbb {Z}^n).$ From the obvious correspondence $[x_0]=\mathbb {Z}^n\cdot x_0$ the $F(\mathbb {Z}^n)$-equivalence class $[x_0]$ can be given a geometric structure identical to that of $\mathbb {Z}^n.$ Moreover, for any $x\in [x_0],$ there is a unique $J\subseteq \mathbb {Z}^n$ so that $[x]_R=J\cdot x_0,$ and thus the marker region of x,  $[x]_R,$ also inherits a geometric structure identical to that of J in $\mathbb {Z}^n.$ If $x_1\in [x_0],$ say $x_1=g\cdot x_0,$ then from $[x_0]=\mathbb {Z}^n\cdot x_1$ and $[x]_R=J'\cdot x_1$ we get another copy of $\mathbb {Z}^n$ and a subset $J'$ representing the corresponding geometric structures of $[x_0]$ and the marker region of x. However, since $J=gJ'$ the said geometric structures are identical up to a shift.

Very often the marker regions we consider come from a marker set M of $F(\mathbb {Z}^n).$ For this reason the Borel subequivalence relation is often denoted $R_M.$ As in the example of Dirichlet regions it is often the case that $R_M$ comes from a geometric construction on the background geometric structure of $\mathbb {R}^n.$ And we will employ the usual terminology of solid geometry when we describe these geometric constructions in $\mathbb {R}^n.$ For example, the Dirichlet regions are referred to as polygonal regions. Also, we say a marker region is a rectangle (or a square, or a cube, etc.) if it is such in $\mathbb {Z}^n,$ or more generally it comes from such in $\mathbb {R}^n$ in the sense of our description of this paragraph and the preceding one.

Our main objective of this section is to construct marker regions with regular geometric shapes. Our main theorem below will be a construction of rectangular marker regions. Moreover, we also restrict the choices for edge lengths of the rectangles as much as we can. By doing all this we obtain marker regions with a regular geometry. This turns out to be crucial in further constructions in hyperfiniteness proofs.

Theorem 3.1

Let $d>0$ be an integer. Then there is a subequivalence relation $R^n_d$ of $F(\mathbb {Z}^n)$ such that $R^n_d$ is relatively clopen and the $R^n_d$-marker regions are n-dimensional rectangles with edge lengths either d or $d+1$.

Remark 3.3

When we say that $R^n_d$ is (relatively) clopen, we actually mean that $\{ (x,g) \in F(\mathbb {Z}^n) \times \mathbb {Z}^n :g \cdot x\, R^n_d x\}$ is a clopen subset of $F(\mathbb {Z}^n) \times \mathbb {Z}^n.$ Equivalently, for every $g \in \mathbb {Z}^n,$ the set $\{ x \in F(\mathbb {Z}^n) :g \cdot x\, R^n_d x\}$ is a clopen subset of $F(\mathbb {Z}^n).$ We will use this terminology throughout.

The proof of the theorem uses the big-marker-little-marker method. We will present the proof in several steps. As a first step we show that, in order to obtain the almost cubical marker regions of edge lengths approximately d,  it is enough to create marker regions which are n-dimensional rectangles each of which has edge lengths much bigger than d. The basic idea of the proof of the following lemma is similar to that of Lemma 2.9.

Lemma 3.2

Let $d>0$ and $D>d^2$ be integers. Let $R_D$ be a subequivalence relation of $F(\mathbb {Z}^n)$ so that the $R_D$-marker regions are n-dimensional rectangles with edge lengths greater than D. Then there is a subequivalence relation $R_d\subseteq R_D$ so that every $R_D$-marker region is partitioned into $R_d$-marker regions, which are n-dimensional rectangles with edge lengths either d or $d+1.$ Moreover, if $R_D$ is clopen and there is $\Delta >D$ so that each $R_D$-marker region has edge lengths $\le \Delta ,$ then $R_d$ can also be clopen.

Proof

As we have seen in the proof of Lemma 2.9, every integer $l>d^2$ can be written as $ad+b(d+1)$ with $a, b\ge 0.$ It follows that an n-dimensional rectangle, for instance $[0,l_1]\times \cdots \times [0,l_n]$ with $l_1,\ldots ,l_n>d^2,$ can be tiled by n-dimensional rectangles with edge lengths either d or $d+1.$ This tiling corresponds to a finite equivalence relation $R_{l_1,\ldots ,l_n}$ on the finite set $[0,l_1]\times \cdots \times [0,l_n].$

Now for each $x\in F(\mathbb {Z}^n)$ let

$$\begin{aligned} \vec {l}(x)=(l_1(x),\ldots ,l_n(x)) \end{aligned}$$

where for each $1\le i\le n,$

$$\begin{aligned} l_i(x)=|\{ a\in \mathbb {Z}:(ae_i\cdot x)R_D x\}|. \end{aligned}$$

Since the $R_D$ marker regions are rectangles, the function $\vec {l}(x)$ measures the lengths of the sides the region containing x. It is clear that for any $xR_Dy,$ $\vec {l}(x)=\vec {l}(y).$ Similarly we can also measure the relative position of each element in its marker region. For each $x\in F(\mathbb {Z}^n)$ define

$$\begin{aligned} \vec {p}(x)=(p_1(x),\ldots ,p_n(x)) \end{aligned}$$

where for each $1\le i\le n,$

$$\begin{aligned} p_i(x)=-\inf \{ a\in \mathbb {Z}:(ae_i\cdot x)R_D x\}. \end{aligned}$$

Finally we define $R_d$ by

$$\begin{aligned} xR_dy\iff xR_Dy\quad \hbox {and}\quad \vec {p}(x)R_{\vec {l}(x)}\vec {p}(y). \end{aligned}$$

It follows immediately that the $R_d$-marker regions are n-dimensional rectangles of edge lengths d or $d+1.$

Now suppose $R_D$ is clopen and $\Delta >D$ is such that each $R_D$-marker region has edge lengths $\le \Delta .$ Then the values of $\vec {l}(x)$ and $\vec {p}(x)$ are all bounded by $\Delta .$ This implies that $R_d$ as we defined above is clopen. $\square$

The essence of the above proof is a finitary algorithm being applied uniformly and invariantly to all equivalence classes. This illustrates a general method we will use again and again. Very often we will focus on the description of the finitary algorithm and not explicitly state the formal definitions.

The rectangular marker regions we need in the condition of the above lemma will come from polyhedra with faces perpendicular to the coordinate axes. Let us define precisely the meaning of these terms as we will be using them throughout. By a rectangular polyhedron we mean a finite union of rectangles in $\mathbb {Z}^n.$ This is equivalent to saying it is a bounded set which is a finite boolean combination of rectangles. By a face F of a rectangular polyhedron P we mean a set $F \subseteq P$ such that for some $1 \le i \le n$ we have that F is a maximal subset of P satisfying the following:

• (i) for any $x,y\in F$ and $g\cdot x=y,$ the ith coordinate of g is zero, and

• (ii) either $e_i\cdot F\cap P=\emptyset$ or $-e_i\cdot F\cap P=\emptyset .$

We call such an F a face of R perpendicular to $e_i,$ or simply an i -face. A simple example is shown in Fig. 4a. Note that a polyhedral region R may have many faces perpendicular to $e_i.$ Also, the i-faces need not be “connected” subsets of P in the sense that for $x,y \in F$ there is a sequence

$$\begin{aligned} g_1,\ldots , g_m\in \{\pm e_1,\ldots , \pm e_{i-1},\pm e_{i+1},\ldots , \pm e_n\} \end{aligned}$$

such that $y=(g_1+\cdots +g_m) \cdot x$ and $(g_1+\cdots +g_l)\cdot x\in F$ for all $1\le l\le m.$ For P a rectangle, this definition of face is the usual one, but for P a rectangular polyhedron this definition is perhaps not completely standard (the more customary notion would add the requirement that F be connected in the sense mentioned above). The current definition, however, is the most useful for our purposes. Fig. 4b illustrates the current definition of face.

Fig. 4

Examples of faces. a A polyhedral face F perpendicular to $e_i.$ b One face or two faces? Under our definition, $F_1$ and $F_2$ are part of the same face

Two faces are parallel if they are perpendicular to the same $e_i,$ that is, if they are both i-faces for some $1\le i\le n.$ We also define the notion of perpendicular distance between two parallel faces as follows. If $F_1$ and $F_2$ are both i-faces, then their perpendicular distance is the absolute value of the unique integer $a_i$ whenever there are $a_j\in \mathbb {Z}$ for all $1\le j\le n$ with

$$\begin{aligned} (a_1e_1+\cdots +a_ie_i+\cdots +a_ne_n)\cdot F_1\cap F_2\ne \emptyset . \end{aligned}$$

Note that the perpendicular distance between two parallel faces $F_1$ and $F_2$ is no more than $\rho (F_1,F_2),$ but it is possible for $\rho (F_1,F_2)$ to be large while their perpendicular distance remains small, or even zero.

Lemma 3.3

Let $D>0$ be an integer. Let $R_0$ be a subequivalence relation of $F(\mathbb {Z}^n)$ so that the $R_0$-marker regions are n-dimensional polyhedra with faces perpendicular to the coordinate axes. Suppose that for each $R_0$-marker region every pair of parallel faces have a perpendicular distance greater than D. Then there is a subequivalence relation $R_1\subseteq R_0$ so that every $R_0$-marker region is partitioned into $R_1$-marker regions, which are n-dimensional rectangles with edge lengths greater than D. Moreover, if $R_0$ is clopen and there is $\Delta >D$ so that each $R_0$-marker region is contained in an n-dimensional cube of edge lengths $\Delta ,$ then $R_1$ can also be clopen.

Proof

It is enough to describe a finitary algorithm to decompose each n-dimensional polyhedron with the described property into n-dimensional rectangles with edge lengths greater than D. Let P be a finite polyhedral region in $\mathbb {Z}^n$ with each of its faces perpendicular to some coordinate axis. Note that the faces of P are finite subsets of P definable from P.

Let $F_1,\ldots , F_k$ be all the faces of P. For each $1\le j\le k,$ the face $F_j$ partitions P into at most two parts as follows. Suppose $e_i$ is perpendicular to $F_j$ and without loss of generality assume $-e_i\cdot F_j\cap P=\emptyset .$ By our assumption on the perpendicular distances of parallel faces, for every $0\le c\le D,$ $ce_i\cdot F_j\subseteq P.$ We define $F_j^+\subseteq P$ to be the set of all $x\in P$ such that for any $y\in F_j,$ letting g be the unique element of $\mathbb {Z}^n$ with $g\cdot y=x,$ the ith coordinate of g is non-negative. Let also $F_j^-=P-F_j^+.$ $F_j^-$ could be empty.

Finally define a subequivalence relation $R_P$ on P by

$$\begin{aligned} xR_Py\iff \forall 1\le j\le k \,\left( x\in F_j^+\leftrightarrow y\in F_j^+\right) . \end{aligned}$$

Then the equivalence classes of $R_P$ are rectangles whose faces are parts of linear expansions of the faces of P. These rectangles have edge lengths greater than D exactly because the parallel faces of P have perpendicular distances greater than D. This construction is illustrated in Fig. 5. $\square$

Fig. 5

A partition of a polyhedron into rectangular regions

To finish the proof of the theorem we only need to create polyhedral marker regions with the above mentioned property. To achieve this we start with a basic clopen marker set M for a marker distance $\Delta$ much bigger than D. Consider the equivalence relation $R_M$ defined by

$$\begin{aligned} x R_M y\iff \forall z\in M\,(\rho (x,z)\le \Delta \leftrightarrow \rho (y,z)\le \Delta ). \end{aligned}$$

The basic marker properties of M imply that $R_M$ is in fact clopen. Note that the $R_M$-marker regions are already polyhedra with faces perpendicular to coordinate axes; this follows from the choice of the distance function $\rho$ on $F(\mathbb {Z}^n).$ Therefore we only need to modify these marker regions so that the perpendicular distance between parallel faces is larger than D. There are two potential difficulties. First, we need to see that there is no geometric obstacle to implement this idea, that is, we should be able to do this on any given $F(\mathbb {Z}^n)$ equivalence class. Second and more seriously, we need to be able to perform the modifications in an invariant Borel manner. To address these issues we employ again the big-marker-little-marker method.

Proof of Theorem 3.1

Let $\Delta _2\gg \Delta _1\gg D>d^2.$ Let $M_1$ be a clopen marker set given by Lemma 2.1 for the marker distance $\Delta _1$ and $M_2\subseteq M_1$ be given by Lemma 2.2 for the marker distance $\Delta _2.$ Let $g_1,\ldots , g_k$ enumerate all elements $g\in \mathbb {Z}^n$ with $\Vert g\Vert \le \Delta _2+\Delta _1.$ Then $F(\mathbb {Z}^n)=\bigcup _{1\le i\le k} g_i\cdot M_2.$ We define a sequence $A_0,A_1,\ldots , A_k$ of subsets of $M_1$ as follows:

$$\begin{aligned} A_0&= M_2, \\ A_i&= M_1\cap (g_i\cdot M_2)-\bigcup _{j<i} A_j,\quad \hbox {for}\;1<i\le k. \end{aligned}$$

Then $A_0, A_1,\ldots , A_k$ is a partition of $M_1$ into disjoint clopen sets with the property that, for any $0\le i\le k$ and $x\ne y\in A_i,$ $\rho (x,y)>\Delta _2-2 \Delta _1.$

We now define $R_{M_1}$ as promised

$$\begin{aligned} x R_{M_1}y \iff \forall z\in M_1\,(\rho (x,z)\le \Delta _1\leftrightarrow \rho (y,z)\le \Delta _1). \end{aligned}$$

In order to describe the modifications we will perform on the $R_{M_1}$-marker regions we will use the following auxiliary notation. Let $J_1=\{ g\in \mathbb {Z}^n:\Vert g\Vert \le \Delta _1\}.$ For each $x\in M_1$ let $R_x=J_1\cdot x.$ Then $R_x$ is the cubic region with center x and edge length $2\Delta _1.$ When there is no danger of confusion, we will slightly abuse the terminology of marker regions and refer to each $R_x$ also as a marker region. With this notation $R_{M_1}$ can be equivalently expressed as

$$\begin{aligned} xR_{M_1}y\iff \forall z\in M_1\,(x\in R_z\leftrightarrow y\in R_z). \end{aligned}$$

In this sense we also say that $R_{M_1}$ is generated by the collection $\{ R_x\,|\, x\in M_1\}$ of (possibly overlapping) marker regions. To create marker regions with the desired property we will adjust the collection of cubes $\{R_x\,|\, x\in M_1\}$ to a collection of rectangles $\{R'_x\,|\, x\in M_1\}$ so that

• (i) $R_x\subseteq R'_x$ for each $x\in M_1,$

• (ii) the corresponding faces of $R_x$ and $R'_x$ have a perpendicular distance no more than $\frac{1}{10}\Delta _1,$ and

• (iii) for each face $F_1$ of $R'_x$ and any parallel face $F_2$ of $R'_y$ with $\rho (x,y)\le 3\Delta _1,$ the perpendicular distance between $F_1$ and $F_2$ is at least D.

The subequivalence relation generated by the collection $\{ R'_x\,|\, x\in M_1\}$ clearly satisfies the condition of the preceding lemma.

We define the collection $\{R'_x\,|\, x\in M_1\}$ by giving an inductive definition of $\{R'_x\,|\, x\in A_i\}$ for $0\le i\le k.$ For $x\in A_0,$ let $R_x=R'_x.$ Consider $i>0$ and assume that for all $j<i$ and $x\in A_j,$ $R'_x$ has been defined to satisfy (i)-(iii). Now let $x\in A_i.$ Let $R'_{y_1},\ldots , R'_{y_m}$ enumerate all surrounding rectangles with $y_1,\ldots ,y_m\in \bigcup _{j<i} A_j$ and $\rho (x,y_l)\le 3\Delta _1$ for $1\le l\le m.$ Note that there is a fixed upper bound N for the number m which depends only on n. For example, a volume argument shows that $N\le \left( \frac{(8 \Delta _1)^n}{\Delta _1^n}\right) =8^n.$

It follows that, for each face F of $R_x,$ there are at most 2N many faces of $R'_{y_1},\ldots ,R'_{y_m}$ which are parallel to F. Moreover these faces are the only ones that might have a perpendicular distance $\le$ D from the adjusted face $F'$ of $R'_x$ corresponding to F. Therefore, as long as $\frac{1}{10}\Delta _1>2N(2D),$ the face F can be shifted away from the center x to a suitable $F'$ so that (ii) and (iii) are satisfied for $F'.$ To define $R'_x$ we need only adjust each of its 2n faces in turn. It is clear that (i) holds with this construction. Note that if $x\ne y\in A_i,$ then

$$\begin{aligned} \rho (x,y)>\Delta _2-2 \Delta _1 \gg \Delta _1, \end{aligned}$$

thus the constructions of $R'_x$ and $R'_y$ do not affect each other. It follows that the resulting regions $\{R'_x\,|\, x\in M_1\}$ satisfy properties (i)–(iii). By the preceding lemmas the proof of the theorem is complete. $\square$

Note that Theorem 3.1 is a generalization of Lemma 2.9. In view of the contrast between Lemma 2.9 and Proposition 2.8, there are also limitations on how regular the higher dimensional marker regions can be. For instance, in the case $n=2$ Theorem 3.1 guarantees the existence of Borel tilings of $F(\mathbb {Z}^2)$ by four kinds of almost square tiles, with dimensions $d\times d,$ $d\times (d+1),$ $(d+1)\times d$ and $(d+1)\times (d+1),$ respectively. Proposition 2.8 implies immediately that there is no Borel tiling with only one kind of these tiles used. A more tedious argument shows that there is no Borel tiling which uses only tiles of dimension $d\times d$ and $d\times (d+1).$ Similar arguments also rule out the combinations $\{d\times d, (d+1)\times d\},$ $\{d\times (d+1), (d+1)\times (d+1)\}$ and $\{ (d+1)\times d, (d+1)\times (d+1)\}.$ The other cases are not clear. In particular it is not clear whether there are Borel tilings which use just two or three kinds of the above tiles. We conjecture that the number 4 is optimal.

We make some comments on the role marker regions are going to play in our proof of hyperfiniteness. Since marker regions correspond to finite Borel equivalence relations, a natural attempt to prove hyperfiniteness is to create a sequence of such finite subequivalence relations so that they form an increasing sequence

$$\begin{aligned} R_0\subseteq R_1\subseteq \cdots \subseteq R_k\subseteq \cdots \end{aligned}$$

In terms of the geometry of marker regions when we require $R_k\subseteq R_{k+1}$ it is equivalent to requiring that the $R_{k+1}$-marker regions be unions of $R_k$-marker regions. In this case we say that the marker regions (of different levels) cohere with each other. If increasing levels of coherent marker regions can be produced, then the union of these equivalence relations is hyperfinite. Thus the question is whether the union is the entire equivalence relation $F(\mathbb {Z}^n).$

In Weiss’ proof of the hyperfiniteness of $F(\mathbb {Z}^n),$ increasing levels of coherent regions were used. These were obtained by modifying the Dirichlet regions so as to get coherence. Using the clopen marker of Lemma 2.1, this construction produces an increasing sequence of (relatively) clopen marker regions for $F(\mathbb {Z}^n).$ The union $E_n$ of the corresponding finite subequivalence relations is a hyperfinite subequivalence relation of $F(\mathbb {Z}^n).$ However, $E_n$ is not equal to $F(\mathbb {Z}^n),$ but rather has finite index in it (but this suffices to show the hyperfiniteness of $F(\mathbb {Z}^n)$). Moreover, the index of $E_n$ in $F(\mathbb {Z}^n)$ grows exponentially with n. Thus, an application of this method to study $F(\mathbb {Z}^{<\omega })$ would only produce a hyperfinite subequivalence relation of $F(\mathbb {Z}^{<\omega })$ with infinite index. This does not seem to be progress since it is easy to prove abstractly that any aperiodic countable Borel equivalence relation contains a hyperfinite subequivalence relation.

One can ask, then, whether there is any chance for this method to succeed. Specifically, can we create increasing finite equivalence relations

$$\begin{aligned} R_0\subseteq R_1\subseteq \cdots \subseteq R_k\subseteq \cdots \end{aligned}$$

with each $R_i$ relatively clopen in $F(\mathbb {Z}^n)$ such that $\bigcup _k R_k=F(\mathbb {Z}^n)$? The following theorem gives a negative answer in a somewhat stronger sense. Let R be a subequivalence relation (not necessarily finite) of $F(\mathbb {Z}^n).$ We say that R is nondegenerate if for all $x\in F(\mathbb {Z}^n)$ there are $y,z\in [x]$ with $(y,z)\not \in R,$ that is to say, there are at least two R-marker regions in each $F(\mathbb {Z}^n)$-equivalence class.

Theorem 3.4

There is no increasing sequence of nondegenerate, relatively open subequivalence relations of $F(\mathbb {Z}^n)$

$$\begin{aligned} R_0\subseteq R_1\subseteq \cdots \subseteq R_k\subseteq \cdots \end{aligned}$$

such that $\bigcup _k R_k=F(\mathbb {Z}^n).$

Proof

Assume there were such a sequence. For each $k\in \omega$ let $U_k$ be an open subset of $F(\mathbb {Z}^n)^2$ so that $R_k=U_k\cap F(\mathbb {Z}^n).$ Define the set $C_k$ of boundary points of marker regions for $R_k$ by

$$\begin{aligned} x\in C_k\iff x\in F(\mathbb {Z}^n)\quad \hbox {and}\quad \exists g\in \mathbb {Z}^n\, (\Vert g\Vert =1\quad \hbox {and}\quad (g\cdot x,x)\not \in R_k). \end{aligned}$$

Since $R_k$ is nondegenerate, $C_k$ is a complete section of $F(\mathbb {Z}^n).$ Also, since $(g\cdot x,x)\in F(\mathbb {Z}^n)$ we have that

$$\begin{aligned} x\in C_k\iff x\in F(\mathbb {Z}^n)\quad \hbox {and}\quad \exists g\in \mathbb {Z}^n (\Vert g\Vert =1 \quad \hbox {and}\quad (g\cdot x,x)\not \in U_k). \end{aligned}$$

Note that there are only finitely many $g\in \mathbb {Z}^n$ with $\Vert g\Vert =1,$ hence it follows that $C_k$ is a relatively closed subset of $F(\mathbb {Z}^n).$ Now it is clear since the $R_k$ are increasing that

$$\begin{aligned} C_0\supseteq C_1\supseteq \cdots \supseteq C_k\supseteq \cdots \end{aligned}$$

Thus by Theorem 2.5 $\bigcap _k C_k\ne \emptyset .$ Let $x\in \bigcap _k C_k.$ There is $g\in \mathbb {Z}^n$ with $\Vert g\Vert =1$ so that for infinitely many k,  $(g\cdot x,x)\not \in R_k.$ This contradicts $\bigcup _k R_k=F(\mathbb {Z}^n).$ $\square$

This shows that the marker regions have to be used in a more sophisticated way than to serve directly as witnesses for hyperfiniteness. That is, we must go in a different direction from using clopen markers to produce coherent marker regions. Indeed, one of the main ideas of the current proof will be to use the clopen marker sets to produce marker regions which are as “anti-coherent” as possible. This will be made precise in Sect. 5 where we will construct orthogonal marker regions, which will be one of our main technical tools. Our strategy will be to construct the anti-coherent marker regions $R_k$ and then produce an embedding $\pi :F \rightarrow E_0$ (here F could be $F(\mathbb {Z}^n)$ or $F(\mathbb {Z}^{<\omega })$) where $\pi (x)$ will code the sequence of marker regions that x belongs to. For this to work, we will need that the boundaries of the $R_k$ regions leave finite sets (that is, for each finite set $A \subseteq [x],$ for $x \in F,$ we have that for large enough k that A misses the boundary of all $R_k$ regions). It will be the anti-coherence of the marker regions which guarantees this property.

We mention one more negative result concerning attempts to witness hyperfiniteness by marker regions. The next theorem says that, even using non-coherent marker regions, hyperfiniteness cannot be witnessed by marker regions which are too geometrically regular (for example, nearly cubical rectangular regions as constructed in Theorem 3.1).

Theorem 3.5

There does not exist a sequence of Borel subequivalence relations $R_k$ of $F(\mathbb {Z}^2)$ such that $F_2= \bigcup _k R_k$ where on each $F(\mathbb {Z}^2)$ class each $R_k$ induces a partition into “bounded geometry” polygons, and such that for all $x,y \in F(\mathbb {Z}^2),$ $x F_2 y$ iff $\exists n \ \forall k \ge n\ x R_k y.$ By “bounded geometry polygons” we mean: there are numbers $a_k < b_k$ with $\lim _{k \rightarrow \infty } a_k = \infty$ such that each edge of a polygon in $R_k$ has length between $a_k$ and $b_k.$

The proof of Theorem 3.5 is a measure or probability argument which we omit. The theorem shows that the marker regions $R_k$ must become increasingly “fractal-like” as k gets larger. Indeed, the marker regions we eventually produce will have this fractal-like property.

4 An application of regular marker regions

In this section we present an application of regular marker regions to a Borel coloring problem. General Borel coloring problems were studied by Kechris et al. [9] and Ben Miller. The specific question we deal with below was communicated to us by Miller. Case $n=2$ of Theorem 4.2 was joint work with Miller, again by a different proof.

We use the following notation. Let C be a set and X be an invariant subset of $2^{\mathbb {Z}^n}.$ A function $c:X\rightarrow C$ is a coloring of X if for all $x\in X$ and $1\le i\le n,$ $c(e_i\cdot x)\ne c(x)$ unless $e_i\cdot x=x.$ In this case we also say that c is a |C|-coloring of X. If X is an invariant Borel subset of $2^{\mathbb {Z}^n},$ we define the Borel chromatic number for X,  denoted by $\chi _B(X),$ to be the smallest integer $k>1$ such that there exists a Borel k-coloring of X.

Kechris et al. [9] have shown that $\chi _B(2^\mathbb {Z})=3$ and that for all $n>1$ and any invariant Borel $X\subseteq 2^{\mathbb {Z}^n}$ on which the action of $\mathbb {Z}^n$ is non-smooth, $3\le \chi _B(X)\le 2n+1.$ We show below that for all $n>1$ we have $\chi _B(F(\mathbb {Z}^n))\le 4.$ Concerning the non-free part, the authors and independently R. Muchnik (we thank A. S. Kechris for communicating this to us) have shown the following.

Theorem 4.1

$\chi _B(2^{\mathbb {Z}^n})=2n+1$ for each $n>1.$

We will present the proof of Theorem 4.1 elsewhere, and give here the proof of the 4-colorability of the free part $F(\mathbb {Z}^n)$ in the following strong form.

Theorem 4.2

For each $n>1$ there is a continuous 4-coloring of $F(\mathbb {Z}^n).$

Proof

Fix an integer d which is a multiple of 10 so that $d> 10 \cdot 2^{n+1}.$ Let $R=R^n_d$ be the clopen subequivalence relation of $F(\mathbb {Z}^n)$ given by Theorem 3.1. We need to work with the geometry of R-marker regions.

To begin with, we define a new distance function on $F(\mathbb {Z}^n).$ First note that the following defines a norm on $\mathbb {Z}^n$: for $g=(g_1,\ldots , g_n),$

$$\begin{aligned} \Vert g\Vert _\nu =|g_1|+\cdots +|g_n|. \end{aligned}$$

This norm induces a distance function $\nu$ on $F(\mathbb {Z}^n),$ which we call the New York distance: for $x,y\in F(\mathbb {Z}^n),$

$$\begin{aligned} \nu (x,y)=\left\{ \begin{array}{ll} \Vert g\Vert _\nu , &{}\quad \hbox {if}\;g\cdot x=y, \\ \infty , &{}\quad \hbox {if}\;(x,y)\not \in F(\mathbb {Z}^n). \end{array}\right. \end{aligned}$$

Two elements x and y are of New York distance 1 exactly when there is some $1\le i\le n$ such that $e_i\cdot x=y$ or $e_i\cdot y=x$ (in which case $-e_i\cdot x=y$). A 4-coloring of $F(\mathbb {Z}^n)$ is a function $c:F(\mathbb {Z}^n)\rightarrow \{0,1,2,3\}$ such that $c(x)\ne c(y)$ whenever $\nu (x,y)=1.$

Consider the sets

$$\begin{aligned} B_1&=\{x\in F(\mathbb {Z}^n):\exists 1\le i\le n\, (e_i\cdot x, x)\not \in R \hbox { or } (-e_i\cdot x, x)\not \in R\},\\ B_2&=\{ x\in F(\mathbb {Z}^n):\exists 1\le i\le n\, (2e_i\cdot x, x)\not \in R \hbox { or } (-2e_i\cdot x, x)\not \in R\}. \end{aligned}$$

The set $B_1$ consists of the boundary points of all the R-marker regions, and $B_2$ consists of all points of $B_1$ as well as points of New York distance 1 to those in $B_1.$ Both $B_1$ and $B_2$ are clopen subsets of $F(\mathbb {Z}^n).$

Define

$$\begin{aligned} C_0= \{ x\in F(\mathbb {Z}^n):\forall 1\le i\le n, (e_i\cdot x,x)\not \in R\}. \end{aligned}$$

Then $C_0$ is a transversal for R and it consists of exactly one extremal point of each R-marker region. Furthermore, let

$$\begin{aligned} C_2=\{ x\in B_2:\nu (x,x_0) \hbox { is even, where}\, x_0\in C_0 \ \hbox {and}\ x_0R x\}, \end{aligned}$$

and

$$\begin{aligned} C_1=C_2\cap B_1. \end{aligned}$$

Note that $C_0\subseteq C_1\subseteq C_2.$

Finally, define $A_1=B_1-C_1.$ Note that all sets defined so far are clopen.

Next define a binary relation E by

$$\begin{aligned} xEy\iff \nu (x,y)=1\quad \hbox {and}\quad (x,y\in A_1 \hbox { or } x,y\in C_1). \end{aligned}$$

Let $\sim$ be the transitive closure of E. Then $\sim$ is an equivalence relation. The following fact will be crucial for our further construction.

Claim 1

Each $\sim$-equivalence class has no more than $2^{n^2}$ many elements.

Proof of Claim 1

First note that if xEy then $(x,y)\not \in R.$ To see this, assume xRy and let $x_0$ be the unique element in $C_0$ with $x_0R x$; since $\nu (x,y)=1,$ then $\nu (x,x_0)$ differs from $\nu (y, x_0)$ by 1,  and thus x and y cannot both be in $A_1$ or $C_1,$ contradicting xEy. Thus if xEy,  the R-marker regions containing x and y are different. Moreover, if xEy and letting $R_x$ and $R_y$ be the R-marker regions containing x and y respectively, then there is a face $F_1$ of $R_x$ containing x and a face $F_2$ of $R_y$ containing y so that $F_1$ and $F_2$ are parallel. In fact, if $\sigma \cdot x=y,$ then both $F_1$ and $F_2$ are perpendicular to the vector $\sigma$. The four possible cases for a fixed vector $\sigma$ in dimension $n=2$ are demonstrated in Fig. 6.

Fig. 6

E-neighboring points and perpendicular faces

Next we show that if $x\sim y$ and $g\cdot x=y$ with $g=(g_1,\ldots , g_n)\in \mathbb {Z}^n,$ then for all $1\le i\le n,$ $|g_i|<2^n.$ Toward a contradiction suppose there is a chain

$$\begin{aligned} x=x_0\, E\, x_1\, E\, \cdots \, E\, x_k=y \end{aligned}$$

with $|g^j_\ell |\ge 2^n$ for some $j \le k,$ $1 \le \ell \le n,$ where $g^j=(g^j_1,\ldots , g^j_n)\in \mathbb {Z}^n$ is such that $g^j\cdot x=x_j.$ By taking k minimal, we may assume that $|g^j_\ell |\le 2^n$ for all $j, \ell .$ Fix i so that $|g^k_i|\ge 2^n$ (so actually $|g^k_i|=2^n$). It follows that there are distinct

$$\begin{aligned} j_0, j_1, \ldots , j_{2^n-1}<k \end{aligned}$$

such that for each $l<2^n,$ $g^{j_l}_i=l$ and $g^{j_l+1}_i=l+1.$ It follows that for each $l<2^n$ there are faces $F_l$ and $F'_l$ such that $F_l$ contains $x_{j_l},$ $F'_l$ contains $x_{j_l+1},$ and both $F_l$ and $F'_l$ are perpendicular to $e_i.$ Also, every point in $F_l$ is of the form $h\cdot x$ with $h_i=l,$ and every point in $F'_l$ is of the form $h\cdot x$ with $h_i=l+1.$ This implies that there are at least $2^n+1$ faces from various R-marker regions each of which is perpendicular to $e_i,$ and all of these $2^n+1$ faces have a point that is within $\rho _X$ distance $2^n<\frac{d}{10}$ of the point x. This, however, contradicts the following fact. $\square$

Fact 1

Let R be a rectangular partition of $\mathbb {Z}^n$ with each rectangle having edge lengths in $\{ d, d+1\}.$ Then for any $x \in \mathbb {Z}^n,$ the ball

$$\begin{aligned} B_\rho \left( x, \frac{d}{10}\right) =\left\{ y\in \mathbb {Z}^n:\rho (x,y)\le \frac{d}{10}\right\} \end{aligned}$$

of radius $\frac{d}{10}$ about x can intersect at most $2^n$ many parallel faces of rectangles in R.

Proof

Without loss of generality we may assume x is the origin. Suppose that $B =B_\rho (\vec {0}, \frac{d}{10})$ intersects more that $2^n$ many faces of rectangles, and all of these faces are parallel to a given face $\mathcal {F}.$ Clearly each rectangle in the partition R can have at most one face parallel to $\mathcal {F}$ which intersects S. Thus, we have more than $2^n$ rectangles $R_1, \ldots , R_{2^n+1},$ each of which has a face parallel to $\mathcal {F}$ which intersects B. Let $c_1, \ldots , c_{2^n+1}$ be the centers of these rectangles. Since there are only $2^n$ “quadrants” about the origin in $\mathbb {Z}^n,$ there must be two of these rectangles, say $R_1$ and $R_2,$ such that their centers $c_1$ and $c_2$ lie in the same quadrant about $\vec {0}.$ Without loss of generality, say $c_1$ and $c_2$ both have non-negative values in their coordinate representations. Say $c_1=(a_1, a_2, \ldots , a_n),$ $c_2=(a'_1, a'_2, \ldots , a'_n).$ Then, $0 \le a_i \le \frac{d}{10} + \frac{d}{2}= \frac{3}{5}d$ for all i. It follows that $(\frac{3}{10}d, \frac{3}{10}d, \ldots , \frac{3}{10}d)\in R_1.$ Similarly, $(\frac{3}{10}d,\frac{3}{10}d,\ldots ,\frac{3}{10}d)\in R_2,$ which contradicts the fact that $R_1$ and $R_2$ are disjoint. $\square$

Now it follows immediately from the above fact that for any $x\in B_1,$ the $\sim$-equivalence class of x is confined to a cubical region with all edges of length $2^n.$ Thus there are at most $(2^n)^n=2^{n^2}$ many points in each $\sim$-equivalence class. This completes the proof of the claim. $\square$

For any finite $S\subseteq \mathbb {Z}^n,$ let $\pi _S$ be the lexicographically least element of S. Note that for any finite $S\subseteq \mathbb {Z}^n$ and $g\in \mathbb {Z}^n,$ $\pi _{gS}=g\pi _S.$ It follows that for any finite subset of an $F(\mathbb {Z}^n)$-class, in general of the form $S\cdot x$ for a finite $S\subseteq \mathbb {Z}^n,$ the lexicographically least element $\pi _S\cdot x,$ is well defined (that is, it does not depend on the choice of x). Given each subset S of $[0,d]^n$ in $\mathbb {Z}^n$ we fix a 2-coloring $c_S$ of S into $\{0,1\}$ so that $c(\pi _S)=0.$

We are finally ready to define a continuous 4-coloring c of $F(\mathbb {Z}^n).$ Let $x\in F(\mathbb {Z}^n).$ If $x\in C_2-C_1,$ then let $c(x)=0.$ Since distinct points in $C_2-C_1$ have $\nu$ distance $>1,$ the function c defined so far is a coloring of $C_2-C_1.$ Next for $x\in C_1,$ let $x_0$ be the lexicographically least element of $[x]_\sim$ and let $[x]_\sim =S\cdot x_0.$ By the proof of the above claim, $S\subseteq [0,2^n-1]^n\subseteq [0,d]^n.$ We define $c:[x]_\sim =S\cdot x_0\rightarrow \{0,1\}$ so that

$$\begin{aligned} c(g\cdot x_0)=c_S(g). \end{aligned}$$

At this point note that if $x_1\in C_1$ and $x_2\in C_2-C_1$ then $\nu (x_1,x_2)>1.$ Thus the function c defined so far is a coloring on $C_2.$

Continuing the definition, for $x\in A_1,$ we also consider $[x]_\sim$ and let $x_0$ be its lexicographically least element and $S\subseteq \mathbb {Z}^n$ so that $[x]_\sim =S\cdot x_0.$ We define $c:[x]_\sim =S\cdot x_0\rightarrow \{2,3\}$ so that

$$\begin{aligned} c(g\cdot x_0)=c_S(g)+2. \end{aligned}$$

It is obvious that the function c defined so far is a coloring of $C_2\cup A_1.$

Now we claim that if $x\not \in C_2\cup A_1$ and $\nu (x,y)=1,$ then $y\not \in A_1.$ To see this, let $y\in A_1$ and let $\nu (x,y)=1.$ Let $y_0\in C_0$ be the unique point with $y_0Ry.$ Then $\nu (y,y_0)$ is odd. If $(x,y)\not \in R,$ then $x\in B_1=C_1\cup A_1\subseteq C_2\cup A_1.$ If xRy,  then $x\in B_2$ and, since $\nu (x,y)=1,$ we have that $\nu (x,y_0)$ is even. This implies that $x\in C_2.$ We have thus shown the claim.

Finally for $x\not \in C_2\cup A_1$ we let $D_x=[x]_R-(C_2\cup A_1).$ Let $x_0$ be the lexicographically least element of $D_x$ and let $D_x=S\cdot x_0.$ Define $c:D_x=S\cdot x_0\rightarrow \{2,3\}$ so that

$$\begin{aligned} c(g\cdot x_0)=c_S(g)+2. \end{aligned}$$

By the above claim, if $x_1\in D_x,$ $y_1\not \in D_x$ and $\nu (x_1,y_1)=1,$ then it must be that $y_1\in C_2$; thus $c(y_1)\in \{0,1\}$ and therefore $c(y_1)\ne c(x_1).$ This shows that c is a coloring of all of $F(\mathbb {Z}^n).$

To see that c is a continuous coloring just note that for each color $\kappa \in \{0,1,2,3\},$ $c^{-1}(\kappa )$ is clopen in $F(\mathbb {Z}^n).$ This completes the proof of Theorem 4.2. $\square$

An interesting question which remains open is whether $F(\mathbb {Z}^n)$ admits a continuous (or just Borel) 3-coloring. Investigation of this problem suggests that the answer is closely related to whether we may improve our regular marker regions so that they exhibit further regularity properties. In particular, we are interested in the following intuitive question: can we create regular marker regions so that not only each of them is a rectangle but also they almost line up with each other? The precise question for $n=2$ is as follows.

Question 4.1

Let $d>0$ be an integer. Is there a Borel subequivalence relation $R_d$ of $F(\mathbb {Z}^2)$ such that

• (a) each $R_d$-marker region is a rectangle with edge lengths either d or $d+1,$ and

• (b) if $R_1$ and $R_2$ are two adjacent $R_d$-marker regions and $F_1$ and $F_2$ are parallel edges of $R_1$ and $R_2$ respectively, then the perpendicular distance between $F_1$ and $F_2$ is either 0,  1,  d or $d+1$?

5 Orthogonal marker regions

In Sect. 3 we constructed regular marker regions for $F(\mathbb {Z}^n).$ Recall that for each $d>0$ we constructed clopen subequivalence relation $R^n_d$ of $F(\mathbb {Z}^n)$ such that on each equivalence class of $F(\mathbb {Z}^n),$ the $R^n_d$ classes are n-dimensional rectangles with each edge length either d or $d+1.$ We refer to $R^n_d$ as a rectangular partition of $F(\mathbb {Z}^n).$ For such a partition $R^n_d,$ we show how to construct an orthogonal partition $\tilde{R}^n_d.$ This will also be a clopen subequivalence relation of $F(\mathbb {Z}^n)$ with rectangular regions, and moreover will be orthogonal to $R^n_d.$ By this we mean that every face of a rectangle in $\tilde{R}^n_d$ will be fairly far away from any parallel face of a nearby rectangle in $R^n_d.$ The precise statement is in Lemma 5.1.

We adopt a running convention throughout Sects. 5 and 6. In the statements of all results involving the quantity d,  we always assume d is sufficiently large so that all expressions involving d have value at least 1. For example, in the statement of Lemma 5.1 it should be assumed that d is greater than $9000^n 16^{n^2}.$ This avoids certain trivialities associated with small values of d.

Now we state our basic lemma on orthogonal marker regions. We will not directly use this lemma in the proof of our main result (in Sect. 6), but rather a technical strengthening of it which we give immediately afterward. Nevertheless, this lemma shows in a simpler setting the ideas involved. We note that the values of the various constants appearing in the lemma are not critical.

Lemma 5.1

Let $R^n_d$ be a clopen rectangular partition of $F(\mathbb {Z}^n),$ with each rectangle having edge lengths in $\{ d, d+1\}.$ Then there is a clopen subequivalence relation $\tilde{R}^n_d$ of $F(\mathbb {Z}^n)$ satisfying:

• (1) Each $\tilde{R}^n_d$ class is a rectangular region with edge lengths between 9 d and 12 d.

• (2) Every face of a region $R_1 \in \tilde{R}^n_d$ is at least $\frac{1}{9000^n 16^{n^2}} d$ from any parallel face of a region $R_2 \in R^n_d.$

Proof

Let $s=C d,$ where $C=110 \cdot 4 \cdot 8 \cdot 16^n.$ We first let $M \subseteq F(\mathbb {Z}^n)$ be a clopen marker set for distance $\frac{s}{2}.$ We may assume as in the proof of Theorem 3.1 that $M =A_0 \cup A_1 \cup \cdots \cup A_k,$ and for any $x, y \in A_i,$ $\rho (x,y) \gg s.$ We let $\mathcal {R}$ be the collection of cubes with edge length s which are centered about the points of M. As in the proof of Theorem 3.1, we proceed in k steps to adjust these cubes, at step i adjusting the faces of the cubes with centers in $A_i.$ We do this adjustment in two steps. At the end of both steps, we will have moved each face outward by no more than $\frac{s}{4}.$

Figure 7 shows an initial arrangement of the rectangles before adjustment. In the figure each dot represents a point $x\in M,$ each solid square represents a ball $B_\rho (x,\frac{s}{2})=\{y\in F(\mathbb {Z}^2):\rho (x,y)\le \frac{s}{2}\},$ which is a cube centered about $x\in M$ with edge length s,  and each dashed square represents a ball $B_\rho (x,\frac{s}{4}).$ Since M has marker distance $\frac{s}{2},$ the balls $B_\rho (x,\frac{s}{4})$ are disjoint for distinct $x\in M.$

Fig. 7

Before adjustment, the balls $B_\rho (x,\frac{s}{2}),$ $x\in M,$ could have parallel faces that are close

In the first step of the adjustment, we move each face $\mathcal {F}$ of a cube R with center $x\in A_i$ outward by no more than $\frac{s}{8}$ to avoid each parallel face $\mathcal {F}'$ of any previously adjusted $\mathcal {R}$ cubes with $0<\rho (\mathcal {F}, \mathcal {F}')\le 2s.$ This adjustment is illustrated in Fig. 8. Note that there are possibly multiple such faces $\mathcal {F}'.$

Fig. 8

The first step of the adjustment

Suppose $\mathcal {F}'$ is a parallel face of a previously adjusted $\mathcal {R}$ cube $R'$ with center marker point $x'\in M.$ We note that $R'$ must lie entirely inside the ball of radius $\frac{s}{2}+2s+\frac{3}{2}s=4s$ centered at x,  that is, $R'\subseteq B_\rho (x,4s).$ Note also that the volume of $B_\rho (x,4s)$ is $(8 s)^n.$

Consider all previously adjusted regions with a parallel face $\mathcal {F}'$ such that $\rho (\mathcal {F},\mathcal {F}')\le 2s.$ Each of them contains a smaller ball $B_\rho (x',\frac{s}{4})$ with volume $(\frac{s}{2})^n.$ These smaller balls are disjoint as we noted before, and they remain unchanged throughout the adjustment (see Fig. 9). It follows that there are at most $16^n$ such smaller balls within the ball $B_\rho (x,4s).$ Thus there are at most $16^n$ previously adjusted cubes that we have to consider. Each of such previously adjusted cubes has at most two faces parallel to $\mathcal {F},$ but only one of them can have a perpendicular distance within $\frac{s}{8}$ to the face $\mathcal {F}.$ Therefore the total number of faces $\mathcal {F}'$ we have to avoid is at most $16^n.$ So, by moving the face $\mathcal {F}$ of R no more than $\frac{s}{8},$ we can ensure that its perpendicular distance to all parallel faces of previously adjusted cubes is at least $\frac{s}{2 \cdot 8 \cdot 16^n}.$

Fig. 9

The balls $B_\rho (x,\frac{s}{4}),$ $x\in M,$ remain unchanged and disjoint throughout the adjustment

In the second step of the adjustment, we move each of these faces outward by no more than $\frac{s}{4 \cdot 8 \cdot 16^n}< \frac{s}{8}.$ This will keep their perpendicular distances from the previously adjusted faces considered in the first step at least $\frac{s}{4 \cdot 8 \cdot 16^n}=110 d.$ The objective now is to avoid all of the parallel faces of rectangles in $R^n_d$ within $\frac{7}{4}s+ 10d$ of the adjusted face.

This adjustment is shown in Fig. 10. In the figure, $R^*$ represents a $\mathcal {R}$ cube after the first step of adjustment and after the second step of adjustment for some of its faces. Its edge lengths are now between s and $\frac{3}{2}s.$ $\mathcal {F}^*$ represents a face of $R^*$ under consideration.

Fig. 10

In the second step of the adjustment, the face ${\mathcal {F}}^*$ will be adjusted further by no more than s / 8 to avoid parallel faces from $R^n_d$ cubes in a large region

Suppose N is an $R^n_d$ region with a face F such that $\rho (F,\mathcal {F}^*)\le \frac{7}{4}s+10d$ (not shown in Fig. 10). In Fig. 10 a dashed rectangle represents a region that N must intersect if F satisfies the above inequality and F is to be within parallel distance d of the face obtained by moving $\mathcal {F}^*$ outward by no more that $\frac{s}{4 \cdot 8 \cdot 16^n}$ (note that if the parallel distance from F to the adjusted $\mathcal {F}^*$ is $\ge d,$ then the conclusion of the lemma automatically holds). It follows that N must lie entirely in another rectangular region whose side lengths are bounded as follows: in the direction of the movement, the side length is at most

$$\begin{aligned} \frac{s}{4\cdot 8 \cdot 16^n}+2(d+1) < \frac{s}{4 \cdot 8 \cdot 16^n} +3d; \end{aligned}$$

in the other directions the side length is at most

$$\begin{aligned} \frac{3}{2}s+2\left( \frac{7}{4}s+ 10d+(d+1)\right) <5s+23 d. \end{aligned}$$

Thus the volume of this rectangular region is at most

$$\begin{aligned} \left( \frac{s}{4\cdot 8\cdot 16^n}+3d\right) (5s+23d)^{n-1}. \end{aligned}$$

Note that each $R^n_d$ region has volume at least $d^n.$ Therefore the number of $R^n_d$ regions that can be present in this rectangular region is at most

$$\begin{aligned} \frac{\left( \frac{s}{4\cdot 8\cdot 16^n}+3d\right) (5s+23d)^{n-1}}{d^n}. \end{aligned}$$

Since each $R^n_d$ region contains at most two faces parallel to $\mathcal {F}^*,$ the total number of parallel faces from the $R^n_d$ regions inside this rectangular region is at most

$$\begin{aligned} 2 \cdot \frac{ \left( \frac{s}{4 \cdot 8 \cdot 16^n} +3d\right) (5s+ 23 d)^{n-1} }{d^n}. \end{aligned}$$

(E1)

This number is bounded above by

$$\begin{aligned} 2 \cdot \frac{\frac{s}{2 \cdot 8 \cdot 16^n}\cdot (6s)^{n-1} }{d^n} = \frac{1}{48} \left( \frac{3}{8}\right) ^n C^n \le 9000^n 16^{n^2}. \end{aligned}$$

So, by moving $\mathcal {F}^*$ outward by no more than $\frac{s}{4\cdot 8 \cdot 16^n}$ we may avoid all of these faces by at at least

$$\begin{aligned} \frac{s}{4 \cdot 8 \cdot 16^n} \cdot 9000^{-n} \cdot 16^{-n^2} \ge \frac{1}{9000^n 16^{n^2}} d. \end{aligned}$$

We have finished the description of two steps of adjustment to cubes in $\mathcal {R}.$ Recall that the adjustment is applied to all $\mathcal {R}$ cubes in k stages. At the end of this adjustment we obtain a collection $\tilde{\mathcal {R}}$ of (possibly overlapping) rectangular regions. This is a situation we have encountered in the proof of Theorem 3.1. As in that proof we will apply Lemma 3.3 (depicted by Fig. 5) to obtain a clopen subequivalence relation $\tilde{R}$ of $F(\mathbb {Z}^n).$

To be more specific, the $\tilde{R}$ regions are obtained by extending the faces of the $\tilde{\mathcal {R}}$ regions throughout any $\tilde{\mathcal {R}}$ regions they intersect. Consider a particular $\tilde{\mathcal {R}}$ region. Suppose $\tilde{F}_1$ and $\tilde{F}_2$ are parallel faces of $\tilde{\mathcal {R}}$ regions which both intersect the current region. Then $\tilde{F}_1$ and $\tilde{F}_2$ must lie within $\frac{3}{2}s$ of each other. Say $\tilde{F}_1$ and $\tilde{F}_2$ came from regions that were adjusted at stages $i_1<i_2,$ respectively. Then at stage $i_2$ the face $F_2$ corrresponding to $\tilde{F}_2$ before the adjustment was at distance at most $\frac{3}{2}s+ \frac{s}{4} <2s$ from $\tilde{F}_1.$ Thus, at stage $i_2$ we made the adjustment so that the perpendicular distance of $\tilde{F}_2$ and $\tilde{F}_1$ is at least $\frac{s}{4\cdot 8 \cdot 16^n}.$ So, when we apply Lemma 3.3 and extend $\tilde{F}_1$ and $\tilde{F}_2$ throughout the current region, the extended faces will still have a perpendicular distance at least $\frac{s}{4\cdot 8 \cdot 16^n}=110d$ from each other. It follows that each rectangular region obtained by applying Lemma 3.3 will have edge lengths at least 110 d. Similarly, the extension of $\tilde{F}_2$ came from a face $F^*_2$ that was present at the end of the first step of adjustment. So, the extension of $\tilde{F}_2$ can lie at most $\frac{s}{4}+\frac{3}{2}s=\frac{7}{4}s$ from $F^*_2.$ So, a parallel face of an $R^n_d$ region that can have a perpendicular distance $\le d+1$ to the extension of $\tilde{F}_2$ must be within $\frac{7}{4}s+2d$ of $F^*_2.$ In the second step of the adjustment, we guaranteed that these extended faces will be at least $\frac{1}{9000^n 16^{n^2}} d$ from a parallel face of $R^n_d.$

To summarize, we have defined a clopen subequivalence relation $\tilde{R}$ of $F(\mathbb {Z}^n)$ such that on each $F(\mathbb {Z}^n)$ class, $\tilde{R}$ induces a partition into rectangular regions each having edge lengths between 110 d and $\frac{3s}{2}.$ Furthermore, each face of one of these rectangles are at least $9000^{-n} 16^{-n^2} d$ from any parallel face of a rectangle in $R^n_d.$

Finally, we subdivide each of these rectangular regions into smaller rectangular regions as follows. Divide each edge into intervals of size between $9\frac{1}{2} d$ and $11 \frac{1}{2} d$ (use the fact that any positive integer $\ge 110$ can be written as a positive integral linear combination of 10 and 11). Consider one of the corresponding faces (that is, perpendicular to the edge and passing through one of the endpoints of these intervals). We move it by no more than $\frac{d}{2}$ to avoid the parallel faces of rectangles in $R^n_d$ within 10d. There are at most

$$\begin{aligned} 2 \cdot \frac{\left( \frac{3s}{2}+20 d\right) ^{n-1} \left( \frac{d}{2}+20 d\right) }{d^n} \le 2^n\cdot 21 \cdot C^{n-1} \end{aligned}$$

faces to avoid, so we may avoid them by at least

$$\begin{aligned} \frac{ \left( \frac{d}{2}\right) }{ 2^n \cdot 21 \cdot C^{n-1}} \ge \frac{1}{9000^{n} 16^{n^2}} d. \end{aligned}$$

The resulting rectangular regions have edge lengths between 9d and 12 d. Each face of one of these regions is at least $\frac{1}{9000^n 16^{n^2}} d$ from a parallel face of a rectangle in $R^n_d$ which is within 10 d of the face. Thus, we have satisfied the requirements of the lemma. $\square$

The next lemma is the technical strengthening of Lemma 5.1 that we actually need. The main difference is that we now avoid finitely many rectangular subequivalence relations instead of just one. The reader should think of the bound b which appears in the statement as a fairly small integer (its precise role will become clearer in the next section).

Lemma 5.2

Let $R_1,\ldots , R_k$ be a sequence of clopen subequivalence relations of $F(\mathbb {Z}^n)$ satisfying the following:

• (1) On each $F(\mathbb {Z}^n)$ class, each $R_i$ induces a partition into polyhedral regions R which are unions of rectangles r such that each edge length of one of the r rectangles is between d and 12 d.

• (2) In any ball B of radius $100{,}000\cdot 16^n d$ in some $F(\mathbb {Z}^n)$ equivalence class, there are at most b integers i such that one of the $R_i$ regions has a face $\mathcal {F}$ which intersects B.

Then there is a clopen subequivalence relation $\tilde{R}^n_d \subseteq F(\mathbb {Z}^n)$ satisfying:

• (1) Each $\tilde{R}^n_d$ class is a rectangular region with edge lengths between 9 d and 12 d.

• (2) Every face of an $\tilde{R}^n_d$ region R is at least $\frac{1}{9000^n 16^{n^2} b} d$ from any parallel face of an $R_i$ region $R'$ (for any i).

Proof

The proof is similar to that of Lemma 5.1. The only difference is that in step two of the adjustments, we must avoid all the parallel faces of not just the one family $R^n_d,$ but of all the families $R_1,\ldots , R_k.$ However our hypothesis gives that for each rectangle of size

$$\begin{aligned} ({5s} +23d) \times \cdots \times ({5s} +23d) \times \left( \frac{s}{4 \cdot 8 \cdot 16^n} +3d\right) , \end{aligned}$$

which lies in a sphere of radius $<$ 100,000 $\cdot 16^n d,$ there are at most b many i such that some face of a region in $R_i$ intersects this rectangle. So, there are at most

$$\begin{aligned} (2b) \cdot \left[ \frac{\left( {5s}+ 23 d\right) ^{n-1} \cdot \left( \frac{s}{4 \cdot 8 \cdot 16^n}+3 d\right) }{d^n} \right] \le 9000^n 16^{n^2} b \end{aligned}$$

many faces to avoid. Thus we may avoid them by at least

$$\begin{aligned} \frac{s}{4 \cdot 8 \cdot 16^n} \cdot 9000^{-n} \cdot 16^{-n^2} \cdot \frac{1}{b} \ge \frac{1}{9000^n 16^{n^2} b} d. \end{aligned}$$

$\square$

We remark that in hypothesis (1) of Lemma 5.2 we use d and 12 d rather than d and $d+1$ so that formally Lemma 5.2 is a strengthening of Lemma 5.1.

6 Hyperfiniteness of $F(\mathbb {Z}^{<\omega })$

In this section we show that the free part $F(\mathbb {Z}^{< \omega })$ of $2^{\mathbb {Z}^{< \omega }}$ with the usual action of $\mathbb {Z}^{< \omega }$ is hyperfinite. For notational clarity we let F denote the set $F(\mathbb {Z}^{<\omega })$ and $F_\omega$ denote the orbit equivalence relation on F from the action of $\mathbb {Z}^{<\omega }.$ Each subgroup $\mathbb {Z}^n$ also acts on F and induces a subequivalence relation which we denote by $F_n.$ So, $F_1 \subseteq F_2 \subseteq \ldots$ form an increasing sequence, and $F_\omega = \bigcup _n F_n.$ Of course, all the $\mathbb {Z}^n$ act freely on F as well.

To show $F_\omega$ is hyperfinite, we will construct finite subequivalence relations $R_i$ and use their structure to define a reduction from $F_\omega$ to $E_0.$ Actually, the $R_i$ we build will be relatively clopen subequivalence relations. Recall this means that $\{ (x,g) \in F \times \mathbb {Z}^{< \omega } :g\cdot x\, R_i x\}$ is relatively clopen in $F \times \mathbb {Z}^{< \omega }$ (which is equivalent to saying that for each $g \in \mathbb {Z}^{< \omega },$ $\{ x \in F :g \cdot x\, R_i x\}$ is relatively clopen in F). Then we will be able to obtain a continuous embedding of $F_\omega$ into $E_0(\omega ^\omega ).$ The rough strategy for building the $R_i$ is as follows. We start with a sufficiently fast growing sequence of marker distances $d_1 \ll d_2 \ll \ldots .$ For each i,  let $R^i_{i} \subseteq F_i$ be a clopen subequivalence relation of $F_i$ given by Theorem 3.1 for marker distance $d_i.$ In $i-1$ steps we will then successively modify the rectangles induced by $R^i_i$ to regions giving $R^i_{i-1}, \ldots , R^i_1.$ Each $R^i_j$ will be a clopen subequivalence relation of $F_\omega ,$ such that on each $F_j$ class each region induced by $R^i_j$ will be a finite union of rectangles with edge lengths on the order of $d_j.$ Furthermore, the rectangles contributing to the boundary of the region will be “orthogonal” to the regions induced by $R^j_j,$ $R^{j+1}_j, \ldots , R^{i-1}_j$ (that is, we will maintain a certain distance between nearby parallel faces). The adjusted regions defining $R^i_1$ will witness the hyperfiniteness of $F_\omega .$ Figure 11 illustrates the order of construction of the subequivalence relations $R^i_j.$

Fig. 11

The inductive construction of $R^i_j$

As we successively adjust the regions in the definitions going from $R^i_i$ to $R^i_1,$ the boundaries of the regions will become increasingly “fractal like.” That is, successive adjustments will be done on increasingly small scales.

We note two points about our final regions corresponding to $R^i_1.$ First, they will not cohere. That is, we will not have that $R^i_1 \subseteq R^{i+1}_1.$ Indeed, since all the $R^i_1$ will be clopen, coherence is impossible to achieve by Theorem 3.4. Second, according to Theorem 3.5 it is in some sense necessary that the boundaries of the $R^i_1$ regions become increasingly fractal. So, for example, even for the finite-dimensional relation $F_n$ on $F(\mathbb {Z}^n),$ the original rectangular subequivalence relations $R^n_d$ of Theorem 3.1 can never by themselves witness the hyperfiniteness of $F_n.$

We now turn to the construction of $R^i_j.$ The next lemma will provide the argument for passing from $R^i_{j+1}$ to $R^i_j.$

Lemma 6.1

Let $j<i.$ Let $d_{j+1},$ $d_j$ be positive integers with $d_{j+1} \gg d_j$ (the exact condition necessary is specified below). Suppose $R^i_{j+1}$ is a clopen subequivalence relation of $F_i \subseteq F_\omega .$ Assume that the restriction of $R^i_{j+1}$ to each $F_{j+1}$ class induces a partition into polyhedral regions each of which is a union of rectangles with edge lengths between $d_{j+1}$ and $12 d_{j+1}.$ Suppose clopen equivalence relations $R^j_j,$ $R^{j+1}_j, \ldots ,$ $R^{i-1}_j$ and $R^{j+1}_{j+1},\ldots , R^{i-1}_{j+1}$ have been defined and satisfy:

• (1) $R^j_j\subseteq F_j$; $R^k_j\subseteq F_k$ and $R^k_{j+1} \subseteq F_k$ for all $j < k \le i-1.$

• (2) $R^j_j$ induces a partition of each $F_j$ class into rectangular regions with edge lengths in $\{ d_j, d_j+1\}.$

• (3) For $j < k \le i-1,$ the restriction of $R^k_j$ to each $F_j$ class gives a partition into polyhedral regions R each of which is a union of rectangles with edge lengths between $9 d_j$ and $12 d_j.$

• (4) On each $F_j$ class, for each region R induced by the restriction of $R^k_j,$ there is a region $R'$ induced by the restriction of $R^k_{j+1}$ such that each face of R is within $12 d_j$ of a face of $R'$.

• (5) In any ball B of radius $100{,}000 \cdot 16^j d_j$ contained in an $F_j$ class, there are at most $j+1$ many k with $j < k \le i-1$ such that some region induced by the restriction of $R^k_j$ has a face intersecting B.

• (6) For any $j < k_1 < k_2 \le i-1,$ and regions $R_1,$ $R_2$ contained in an $F_{j}$ class induced by the restrictions of $R^{k_1}_{j},$ $R^{k_2}_{j}$ respectively, if $\mathcal {F}_1,$ $\mathcal {F}_2$ are parallel faces of $R_1,$ $R_2,$ then $\rho (\mathcal {F}_1,\mathcal {F}_2) > \frac{1}{9000^{j} 16^{{j}^2} ({j}+1)} d_{j}.$

• (7) For any $j < k_1 < k_2 \le i,$ and regions $R_1,$ $R_2$ contained in an $F_{j+1}$ class induced by the restrictions of $R^{k_1}_{j+1},$ $R^{k_2}_{j+1}$ respectively, if $\mathcal {F}_1,$ $\mathcal {F}_2$ are parallel faces of $R_1,$ $R_2,$ then $\rho (\mathcal {F}_1,\mathcal {F}_2) > \frac{1}{9000^{j+1} 16^{(j+1)^2} (j+2)} d_{j+1}.$

Then there is a clopen subequivalence relation $R^i_j \subseteq F_i$ satisfying the following:

• (1) On each $F_j$ class, $R^i_j$ induces a partition into polyhedral regions R each of which is a union of rectangles with edge lengths between $9 d_j$ and $12 d_j.$

• (2) On each $F_j$ class, for each region R induced by $R^i_j,$ there is a region $R'$ induced by $R^i_{j+1}$ restricted to the $F_j$ class such that each face of R is within $12 d_j$ of a face of $R'.$

• (3) Condition (5) continues to hold, where now $j<k \le i.$

• (4) Condition (6) continues to hold, where now $j<k \le i.$

Proof

Let $R^i_{j+1}$ and the $R^j_j,$ $R^{j+1}_j, \ldots , R^{i-1}_j$ be given satisfying the above hypotheses. By assumption, the restriction of $R^i_{j+1}$ to each $F_{j+1}$ class induces a partition into polyhedral regions each of which is a union of rectangles with edge lengths between $d_{j+1}$ and $12 d_{j+1}.$ When we further restrict $R^i_{j+1}$ to each $F_j$ class, note that we still obtain a partition into polyhedral regions each of which is a union of rectangles with edge lengths between $d_{j+1}$ and $12 d_{j+1},$ because a cross section of a rectangular region is still a rectangular region whose edge lengths are a subset of the original edge lengths.

We apply Lemma 5.2 as follows. Let the d of Lemma 5.2 be the current $d_j.$ Let the $R_1,\ldots , R_k$ of that lemma be the current $R^{j+1}_j, \ldots , R^{i-1}_j.$ Hypothesis (1) of Lemma 5.2 follows from the current hypothesis (3). Hypothesis (2) of Lemma 5.2 follows from the current hypothesis (5), with $j+1$ as the b of that lemma. Let $\tilde{R}$ be the clopen subequivalence relation of $F_j$ given by Lemma 5.2 (i.e., the $\tilde{R}^n_d$ of that lemma). Then each $\tilde{R}$ class is a rectangular region with edge lengths between $9d_j$ and $12d_j,$ and every face of an $\tilde{R}$ region is at least $\frac{1}{9000^j16^{j^2}(j+1)}d_j$ from any parallel face of any $R^k_j$ region with $j<k<i.$

For each $\tilde{R}$ class A let c(A) be the center point of this rectangular region (uniquely defined in some reasonable manner if A has even edge lengths). We define $R^i_j$ by, for all $x, y\in F,$

$$\begin{aligned} x R^i_j y \iff c([x]_{\tilde{R}}) R^i_{j+1} c([y]_{\tilde{R}}). \end{aligned}$$

Thus, each $R^i_{j}$ class is a union of $\tilde{R}$ classes (which are rectangular regions), and is obtained from an $R^i_{j+1}$ class by adding or subtracting certain $\tilde{R}$ rectangular regions, which must be near the boundary of the $R^i_{j+1}$ region.

Figure 12 illustrates the definition of $R^i_j.$ In Fig. 12a the small regions are $\tilde{R}$ rectangles with edge lengths between $d_j$ and $12 d_j.$ Their centers are represented by the black dots. The solid line represents a face of an $R^i_{j+1}$ region. Since such faces have edge lengths at least $d_{j+1},$ with $d_{j+1}\gg d_j,$ they typically look like straight lines at the scale of this picture. Figure 12b shows the boundary of $R^i_j$ regions with the above definition. The boundary becomes “fractalized” because of the addition and subtraction of $\tilde{R}$ regions to the original $R^i_{j+1}$ region.

Fig. 12

The definition of $R^i_j.$ a The boundary of $R^i_{j+1}$ regions. b The boundary of $R^i_j$ regions

Conclusion (1) of the current lemma follows from the fact that each of the $\tilde{R}$ region is a rectangle with edge lengths between $9 d_j$ and $12 d_j.$

Conclusion (2) is immediate from the definition of the $R^i_j$ and the fact that each $\tilde{R}$ class is a rectangle with edge lengths $\le 12 d_j.$

That (6) continues to hold follows immediately from conclusion (2) of Lemma 5.2.

Finally we come to the key point; that condition (5) continues to hold. Toward a contradiction assume not, and let B be a ball in an $F_j$ class of radius 100,000 $\cdot 16^j d_j.$ Suppose $j < k_1< \cdots < k_{j+2} \le i$ are such that for each $l=1,\ldots , j+2,$ there is an $R^{k_l}_j$ region with a face intersecting B. By our hypothesis (4), each of these faces is within $12 d_j$ of a face of a region induced by $R^{k_l}_{j+1}$ restricted to the current $F_j$ class. Let $\mathcal {A}$ be the collection of these $R^{k_l}_{j+1}$ regions restricted to the $F_j$ class.

Now consider the $F_{j+1}$ class containing the current $F_j$ class. Each $A\in \mathcal {A}$ is a cross section of an $R^{k_l}_{j+1}$ region $A'.$ Moreover, every face of an $A\in \mathcal {A}$ is a cross section of a face of $A'.$ Thus we obtain $j+2$ faces of various $R^{k_l}_{j+1}$ regions each of which has a face with a cross section intersecting B. Since we are in $(j+1)$-dimensional space now, at least two of these $j+2$ faces must be parallel. Thus, we have $k_1,$ $k_2$ with $j<k_1\ne k_2\le i,$ a face $\mathcal {F}_1$ of a region induced by the restriction of $R^{k_1}_{j+1}$ on this $F_{j+1}$ class, and a face $\mathcal {F}_2$ of a region induced by the restriction of $R^{k_2}_{j+1}$ on the same $F_{j+1}$ class, so that $\mathcal {F}_1$ and $\mathcal {F}_2$ are parallel and $\rho (\mathcal {F}_1,\mathcal {F}_2)\le 200,000\cdot 16^j d_j + 24 d_j.$ However, by our hypothesis (7) we also have

$$\begin{aligned} \rho (\mathcal {F}_1,\mathcal {F}_2)>\frac{1}{9000^{j+1} 16^{(j+1)^2} (j+2)} d_{j+1} > 200,000 \cdot 16^j d_j + 24 d_j \end{aligned}$$

since $d_{j+1} \gg d_j.$ This contradiction shows that (5) continues to hold and completes the proof of the lemma. $\square$

We are now in a position to prove the main result of this section, that the shift equivalence relation $F_\omega$ on $F=F(\mathbb {Z}^{< \omega })$ is hyperfinite. In fact, we prove this in a strong form, namely the reduction to $E_0$ we are seeking can be continuous and injective. Recall from Proposition 1.1 that the two forms of $E_0,$ $E_0(\omega ^\omega )$ and $E_0(2^\omega ),$ are continuously embeddable into each other. Thus we may use whichever one is most convenient.

Theorem 6.2

There is a continuous embedding from $F_\omega$ into $E_0.$

Proof

Fix a sufficiently fast growing sequence of natural numbers

$$\begin{aligned} 1 \ll d_1 \ll d_2 \ll \cdots \end{aligned}$$

For each i,  let $R^i_i$ be the clopen subequivalence relation of $F_i \subseteq F_\omega$ from Theorem 3.1 inducing a rectangular partition of the $F_i$ classes with edge lengths in $\{ d_i,d_i+1\}.$ Inductively on i we define the clopen subequivalence relations $R^i_i,$ $R^i_{i-1}, \ldots , R^i_1.$ The relation $R^i_i$ has already been defined, and we assume that $R^i_{j+1}$ and all the $R^k_l$ for $1 \le l \le k <i$ have been defined. In particular, all of the relations $R^j_j,$ $R^{j+1}_j, \ldots ,$ $R^{i-1}_j$ have been defined. Moreover, if $i>j+1,$ all the $R^{j+1}_{j+1},\ldots , R^{i-1}_{j+1}$ have also been defined. We assume inductively that $R^i_{j+1}$ and the subequivalence relations $R^j_j,\ldots ,R^{i-1}_j$ and $R^{j+1}_{j+1},\ldots , R^{i-1}_{j+1}$ satisfy the hypotheses of Lemma 6.1. We then get $R^i_j$ from Lemma 6.1. From Lemma 6.1, we are able to define $R^i_j$ so that the resulting sequences of subequivalence relations continue to satisfy these hypotheses.

So, we may assume the clopen subequivalence relations $R^i_j$ are defined for all $i \ge 1$ and all $1 \le j \le i,$ and they satisfy the hypotheses of Lemma 6.1. We show that if $x, y \in F(\mathbb {Z}^{< \omega })$ and $x F_\omega y,$ then for all large enough i we have $x R^i_1 y.$

Fix $k_0$ such that $x F_{k_0} y.$ Toward a contradiction assume that the set

$$\begin{aligned} I=\{i\ge 1:\lnot (x R^i_1y)\} \end{aligned}$$

is infinite. Let $x_0=x, x_1,\ldots , x_N=y$ be a sequence such that $\rho (x_l,x_{l+1})=1$ and $\rho (x,x_l)\le \rho (x,y).$ For each $i\in I$ there is $0\le l<N$ such that $x_l$ is a boundary point for the $R^i_1$ region containing x,  that is, $x_lR^i_1x$ and $\lnot (x_lR^i_1x_{l+1}).$ Thus there is a fixed l such that the set

$$\begin{aligned} J=\{i\in I:x_l\, \hbox {is a boundary point of the} \,R^i_1\, \hbox {region containing}\, x\} \end{aligned}$$

is infinite. Let z denote this fixed $x_l.$ Fix $k > k_0,$ and consider $k+1$ many elements of J which are greater than k,  say $i_1< \ldots < i_{k+1}.$ Consider the $F_k$ class containing z. Applying conclusion (2) of Lemma 6.1 iteratively, we get that for each of these $i_m$ there is a point $u_m$ on a boundary face $\mathcal {F}_m$ of a region induced by the restriction of $R^{i_m}_k$ so that

$$\begin{aligned} \rho (z,u_m)\le 12(d_1 + d_2+ \cdots + d_{k-1}). \end{aligned}$$

This implies that any two of these faces are within $24(d_1+d_2+\cdots +d_{k-1})$ of each other. Each of the $\mathcal {F}_m$ is a $(k-1)$-dimensional hyperplane in k-dimensional space. Since there are $k+1$ many of them, at least two of them must be parallel. However, conclusion (4) of Lemma 6.1 implies that any two such parallel faces must be at least

$$\begin{aligned} \frac{1}{9000^k 16^{k^2} (k+1)} d_k > 24(d_1 + d_2+ \cdots + d_{k-1}) \end{aligned}$$

apart, using here $d_k \gg d_{k-1}.$ This contradiction shows that $x R^i_1 y$ for all large enough i.

Finally, we define our embedding $\pi$ from $F_\omega$ to $E_0(\omega ^\omega ).$ For $x \in F$ we let $\pi (x)= (\pi _1(x), \pi _2(x), \ldots ),$ where $\pi _i(x) \in \omega$ is an integer code for the $R^i_1$ class containing x defined as follows. Let $c_i=c_i(x)$ be the “center point” of the $R^i_1$ class containing x. By this we mean the center of the rectangular $R^i_i$ class “closest” to the $R^i_1$ class of x; for instance, it can be defined as the unique $R^i_i$ class within Hausdorff distance $12d_1+\cdots + 12 d_{i-1}$ to the $R^i_1$ class containing x. Fix bijections

$$\begin{aligned} \kappa :P=\bigcup \{ 2^S:S\subseteq \mathbb {Z}^{<\omega }\, \hbox {is finite} \} \rightarrow \omega \end{aligned}$$

and

$$\begin{aligned} \tau :\omega \times \omega \rightarrow \omega . \end{aligned}$$

Let

$$\begin{aligned} N_i=N_i(x)=\kappa \left( c_i\upharpoonright \{ g \in \mathbb {Z}^i \wedge ||g|| \le 20d_i\}\right) . \end{aligned}$$

Here we regard $\mathbb {Z}^i \subseteq \mathbb {Z}^{< \omega }$ in the natural way. Let also

$$\begin{aligned} h_i=h_i(x)= \hbox {the unique element}\, h_i\in \mathbb {Z}^i\, \hbox {such that} \,h_i \cdot c_{i-1}=c_i, \end{aligned}$$

where $c_0=c_0(x)=x.$ Let $\pi _i(x)=\tau (N_i(x), h_i(x)).$ This finishes the definition of $\pi _i$ as well as of $\pi .$ We have $\pi$ is continuous since all of the $R^i_1$ regions are clopen.

If $x, y \in F$ and $x F_\omega y,$ then for large enough i we have $x R^i_1 y,$ and so $c_i(x)=c_i(y).$ It follows that $\pi (x) E_0 \pi (y).$ On the other hand, from the $E_0$ class of $\pi (x)$ we may recover the $F_\omega$ class of x using the $h_i$ and the fact that $N_i(x)$ codes

$$\begin{aligned} c_i(x)\upharpoonright \{ g \in \mathbb {Z}^i \wedge ||g|| \le 20d_i\}, \end{aligned}$$

while the distance between $c_{i-1}(x)$ and $c_i(x)$ is at most $13 d_i.$ Likewise, $\pi$ is one-to-one since from $\pi (x)$ we can in a similar manner reconstruct x. Note in particular that in the reconstruction of x we need to use the fact that $c_0(x)=x$ and that $\pi _1(x)$ encodes $h_1(x).$ We have thus proved that $\pi$ is an embedding from $F_\omega$ into $E_0.$ $\square$

7 The non-free part

So far in this paper we have considered the free part F of $X=2^{\mathbb {Z}^ {< \omega }}$ with the shift action of $\mathbb {Z}^ {< \omega }.$ As in Sect. 6 we continue to denote the resulting orbit equivalence relation $F_\omega .$ We showed that $F_\omega$ is hyperfinite. In fact, we showed this in a strong way, namely there is a continuous embedding from $F_\omega$ into $E_0.$ In this section we show that the orbit equivalence relation on the entire space X is hyperfinite.

Throughout this section let $E_\omega$ denote the equivalence relation on X generated by the shift action of $\mathbb {Z}^{< \omega }.$ For each n,  viewing $\mathbb {Z}^n$ as a subgroup of $\mathbb {Z}^{< \omega }$ in the natural way, we obtain also an action of $\mathbb {Z}^n$ on X. Let $E_n$ be the subequivalence relation of $E_\omega$ generated by this action of $\mathbb {Z}^n.$ Then $E_\omega = \bigcup _n E_n.$ We will actually show that there is a continuous embedding from $E_n$ into $E_0.$ However, we do not know if there is a continuous embedding from $E_\omega$ into $E_0.$

Our study of the non-free part is set up as follows. For $x \in X,$ let

$$\begin{aligned} G_x=\{ g \in \mathbb {Z}^{< \omega } :g \cdot x=x\} \end{aligned}$$

be the stabilizer of x. The map $x \mapsto G_x$ is a Borel map from X to $\mathcal {P}(\mathbb {Z}^{< \omega })$ (which is essentially $\omega ^\omega$). For a subgroup H of $\mathbb {Z}^{< \omega },$ let

$$\begin{aligned} X_H= \{ x \in X :G_x=H\}. \end{aligned}$$

Then $X_H$ is an invariant Borel subset of X. Let $E_H$ denote the equivalence relation $E_\omega$ restricted to $X_H.$ We will define our reduction from $E_\omega$ to $E_0$ by defining it on each $X_H$ separately. More precisely, we will define a Borel map

$$\begin{aligned} (x,H) \mapsto \pi (x, H) \in \omega ^\omega \end{aligned}$$

with domain the Borel subset of $X \times \mathcal {P}(\mathbb {Z}^{< \omega })$ consisting of those (x, H) for which $G_x=H.$ For each H,  this map restricted to $X_H$ (more precisely $X_H \times \{ H\}$) will be a reduction of $(X_H,E_H)$ to $E_0.$ This will suffice as we can then easily modify $\pi$ to $\pi '$ which codes H into the output as well as $\pi (x,H).$ Then $\pi '$ will be a reduction of $(X,E_\omega )$ to $E_0.$ Since x determines H,  we will usually write $\pi (x)$ instead of $\pi (x,H).$ In the argument below we will in fact fix the subgroup H and just define $\pi$ on $X_H.$ The reader can check that the map we define is actually Borel as a function of both arguments x and H. The fact that the map $x \mapsto G_x$ is only Borel (and not continuous), however, is what prevents us from getting a continuous reduction.

7.1 Preliminaries about the space $X_H$

We let

$$\begin{aligned} e_1=(1,0,0, \ldots ), e_2=(0,1,0, \ldots ), \ldots , e_n, \ldots \end{aligned}$$

be the standard set of generators for the group $\mathbb {Z}^{< \omega }.$ Every element $g \in \mathbb {Z}^{< \omega }$ can be written uniquely in the form $g=a_1e_1+ \cdots + a_k e_k=(a_1, \ldots , a_k, 0,0, \ldots ),$ where $a_k\ne 0.$ We say that $k=\text {supp}(g)$ is the support of g (and if $g=(0,0,\ldots )$ we say that $\text {supp}(g)=\emptyset$). We view $\mathbb {Z}^n$ as the subgroup of $\mathbb {Z}^{< \omega }$ generated by $e_1, \ldots , e_n.$ We let $\vec {0}$ denote the identity element $(0,0,\ldots )$ of $\mathbb {Z}^{< \omega }.$ For $g=a_1 e_1+\cdots + a_k e_k \in \mathbb {Z}^{< \omega }$ and $n\ge 1,$ let $\pi _n(g)=a_n$ for $n\le k$ and $\pi _n(g)=0$ for $n>k.$

Definition 7.1

Let H be a subgroup of $\mathbb {Z}^{< \omega }.$ We say that $B=\{ h_1, h_2, \ldots \}$ is a normal basis for H if the following are satisfied:

• (1) $H=\langle h_1, h_2, \ldots \rangle .$

• (2) $\text {supp}(h_1)< \text {supp}(h_2)< \cdots$

• (3) For every i,  if $k=\text {supp}(h_i),$ then $\pi _k(h_i)>0.$

• (4) For every n,  $H \cap \mathbb {Z}^n=\langle h_i :\text {supp}(h_i) \le n \rangle .$

We have the following standard algebraic fact. For the sake of completeness we include a proof.

Lemma 7.2

Every subgroup H of $\mathbb {Z}^{< \omega }$ has a normal basis.

Proof

Let $h_1, h_2, \ldots$ enumerate the non-$\vec {0}$ elements of the sequence $h'_1,$ $h'_2, \ldots ,$ where $h'_n$ is defined as follows. If $H \cap \mathbb {Z}^n=H \cap \mathbb {Z}^{n-1},$ let $h'_n=\vec {0}.$ Otherwise, let $I_n=\{ \pi _n(h) :h \in H \cap \mathbb {Z}^n \}.$ $I_n$ is an ideal in $\mathbb {Z},$ and so is principal. Let $h'_n \in H$ be such that $I_n=\langle \pi _n(h'_n) \rangle$ and $\pi _n(h'_n)>0.$ It is straightforward to check that $H \cap \mathbb {Z}^n=\langle h'_1, \ldots , h'_n\rangle ,$ and the result follows. $\square$

It is clear from the above proof that one may choose a normal basis in a Borel manner from H.

Henceforth we fix an arbitrary subgroup H of $\mathbb {Z}^{< \omega }$ and a normal basis $B=\{ h_1, h_2, \ldots \}$ for H.

Definition 7.3

We say n is an essential dimension if $H \cap \mathbb {Z}^n = H \cap \mathbb {Z}^{n-1}.$ Otherwise we say n is an inessential dimension.

So, n is an inessential dimension precisely when we have $n=\text {supp}(h_i)$ for some i (necessarily $i \le n$). Moreover, if n is an inessential dimension then there is a unique $i\le n$ such that $n=\text {supp}(h_i).$

Definition 7.4

For each n,  we define

$$\begin{aligned} s(n)=\left\{ \begin{array}{ll} \infty , &{}\quad \hbox {if}\;n \,\hbox {is an essential dimension}, \\ \pi _n(h_i), &{}\quad \hbox {otherwise if}\; n=\text {supp}(h_i)\, \hbox {for some} \ i\ge 1. \end{array}\right. \end{aligned}$$

We call s(n) the size of the nth dimension.

Thus, the values of s(n) are finite for the inessential dimensions. The following fact records the significance of the size function.

Lemma 7.5

For every $g \in \mathbb {Z}^{< \omega },$ there is a unique $g' \in \mathbb {Z}^{< \omega }$ such that $g-g' \in H$ and such that for all inessential dimensions n,  $0 \le \pi _n(g') < s(n).$

Proof

We first show the existence of such a $g'.$ Let $n_0$ be the largest inessential $n \le \text {supp}(g)$ such that $\pi _n(g)<0$ or $\pi _n(g)\ge s(n).$ Fix $i\ge 1$ so that $\text {supp}(h_i)=n_0.$ From the definition of s(n) there is an integer a with $0 \le \pi _{n_0}(g-ah_i) < s(n_0).$ Also, $\pi _n(g-ah_i)=\pi _n(g)$ for $n >n_0.$ By induction on $n_0,$ there is an $h \in H$ such that $g'=(g-ah_i)-h$ satisfies $0 \le \pi _n(g') <s(n)$ for all inessential n. So, $g= g'+(ah_i+h)$ with $ah_i+h \in H,$ and we are done.

To see the uniqueness, suppose $g''$ also satisfied the requirements, and $g'' \ne g'.$ Note that $g''-g' \in H.$ Let $n_1$ denote the largest n such that $\pi _n(g'')-\pi _n(g') \ne 0.$ Since $g''-g' \in H,$ we must have that $n_1$ is inessential. However, note also $0 < | \pi _{n_1}(g'')-\pi _{n_1}(g')| < s(n_1).$ Without loss of generality we may assume $0 < \pi _{n_1}(g'')-\pi _{n_1}(g') < s(n_1).$ This, however, violates the definition of $s(n_1)$ since $g''-g' \in H$ and $s(n_1)$ is the minimal value of $|\pi _{n_1}(h)|$ for $h \in H$ with $\text {supp}(h) \le n_1.$ $\square$

In view of Lemma 7.5, we can make the following definition.

Definition 7.6

We say that $g \in \mathbb {Z}^{< \omega }$ is in standard form if for all inessential dimensions n we have $0 \le \pi _n(g) <s(n).$ Denote the set of all $g\in \mathbb {Z}^{< \omega }$ in standard form by $\Sigma .$ For each $g\in \mathbb {Z}^{< \omega }$ let $\sigma (g)$ denote the unique $g'\in \Sigma$ such that $g-g'\in H.$

In general, if g and h are in standard form, then $-g$ and $g+h$ are not necessarily in standard form. We need an estimate for the norm of $\sigma (-g)-(-g)$ and that of $\sigma (g+h)-(g+h).$ Recall that for $g=a_1 e_1+\cdots + a_k e_k \in \mathbb {Z}^{< \omega },$ the norm of g is defined as $\Vert g\Vert = \max \{ | a_i| :i \le k\}.$ We will use the following quantity throughout the rest of the section.

Definition 7.7

For each inessential dimension k,  define $c_k=\Vert h_i\Vert$ where $\text {supp}(h_i)=k.$ For each $n\ge 1$ let $D_n$ be the set of all inessential dimensions $k\le n.$ Let $s=\max \{ s(k) :k \in D_n \}.$ Define

$$\begin{aligned} \beta (n)= \prod _{k \in D_n} \left( c_k+2s \right) . \end{aligned}$$

Lemma 7.8

Let $g, h\in \Sigma \cap \mathbb {Z}^n.$ Then

• (a) $\Vert \sigma (-g)+g\Vert \le \beta (n),$ and

• (b) $\Vert \sigma (g+h)-g-h\Vert \le \beta (n).$

Proof

(a) Suppose $g=a_1e_1+ \cdots + a_ne_n\in \Sigma .$ Let $k_1 < k_2 < \ldots <k_m$ enumerate the inessential dimensions $\le n.$ We have $\text {supp}(h_j)=k_j$ for all $1\le j\le m.$ Since g is in standard form, we have $0\le a_{k_j}=\pi _{k_j}(g)\le s(k_j)=\pi _{k_j}(h_{j})$ for all $1\le j\le m.$ Let $s=\max \{ s(k_j):1\le j\le m\}.$

Now $-g=(-a_1)e_1+ \cdots +( -a_n)e_n.$ Since $\sigma (-g)+g\in H\cap \mathbb {Z}^n,$ there is a unique sequence $\alpha _1,\ldots ,\alpha _m$ of integers such that

$$\begin{aligned} \sigma (-g)+g=\alpha _1h_1+\alpha _2h_2+\cdots +\alpha _m h_m. \end{aligned}$$

This gives

$$\begin{aligned} \sigma (-g)=\alpha _1h_1+\alpha _2h_2+\cdots +\alpha _m h_m+(-a_1)e_1+\cdots +(-a_n)e_n. \end{aligned}$$

Consider the projection $\pi _{k_m}.$ Since $\sigma (-g)$ is in standard form, we have $0\le \pi _{k_m}(\sigma (-g))< s(k_m).$ This gives $0\le \alpha _ms(k_m)-a_{k_m}< s(k_m).$ However, $0\le a_{k_m}< s(k_m).$ So $0\le \alpha _m\le 1.$

Next we consider the projection $\pi _{k_{m-1}}.$ Note that

$$\begin{aligned} |\alpha _m\pi _{k_{m-1}}(h_m)-a_{k_{m-1}}|\le c_{k_m}+s. \end{aligned}$$

The expression appearing in between the absolute value signs is the coefficient of $\sigma (-g)$ at the coordinate $e_{k_{m-1}}$ before $\alpha _{m-1}h_{m-1}$ is taken into account. It follows that $|\alpha _{m-1}|\le c_{k_m}+s.$

In a similar fashion, we next consider the projection $\pi _{k_{m-2}}.$ Note that

$$\begin{aligned}&|\alpha _{m-1}\pi _{k_{m-2}}(h_{m-1})+\alpha _m\pi _{k_{m-2}}(h_m)-a_{k_{m-2}}| \\&\quad \le (c_{k_m}+s)c_{k_{m-1}}+c_{k_m}+s \\&\quad \le (c_{k_m}+s)(c_{k_{m-1}}+s). \end{aligned}$$

The expression appearing in between the absolute value signs above is the coefficient of $\sigma (-g)$ at the coordinate $e_{k_{m-2}}$ before $\alpha _{m-2}h_{m-2}$ is taken into account. From this we get that $|\alpha _{m-2}|\le (c_{k_m}+s)(c_{k_{m-1}}+s).$ Continuing in this fashion, we get that

$$\begin{aligned} |\alpha _j|\le \prod _{j+1\le l\le m}(c_{k_l}+s) \end{aligned}$$

for all $1\le j\le m$ and

$$\begin{aligned} \Vert \alpha _1h_1+\cdots +\alpha _mh_m\Vert \le |\alpha _1|c_{k_1}+\cdots +|\alpha _m|c_{k_m}\le \prod _{1\le j\le m}(c_{k_j}+s)<\beta (n). \end{aligned}$$

(b) Suppose $g=a_1e_2+\cdots +a_ne_n\in \Sigma$ and $h=b_1e_1+\cdots +b_ne_n\in \Sigma .$ Again let $k_1<k_2<\cdots <k_m$ enumerate the inessential dimensions $\le n.$ Let

$$\begin{aligned} s=\max \{s(k_j):1\le j\le m\}. \end{aligned}$$

Let $\alpha _1,\ldots ,\alpha _m$ be such that

$$\begin{aligned} \sigma (g+h)=\alpha _1h_1+\cdots +\alpha _mh_m+(a_1+b_1)e_1+\cdots +(a_n+b_n)e_n. \end{aligned}$$

Consider successively $\pi _{k_m}, \pi _{k_{m-1}},\ldots , \pi _{k_1}$ as in the proof of (a). First we obtain

$$\begin{aligned} 0\le \alpha _ms(k_m)+a_{k_m}+b_{k_m}<s(k_m), \end{aligned}$$

which implies $|\alpha _m|\le 1.$ Then we have

$$\begin{aligned} |\alpha _m\pi _{k_{m-1}}(h_m)+a_{k_{m-1}}+b_{k_{m-1}}|\le c_{k_m}+2s, \end{aligned}$$

which implies $|\alpha _{m-1}|\le c_{k_m}+2s.$ In general, we have

$$\begin{aligned} |\alpha _j|\le \prod _{j+1\le l\le m} (c_{k_l}+2s) \end{aligned}$$

for all $1\le j\le m,$ and so

$$\begin{aligned} \Vert \alpha _1h_1\!+\!\cdots \!+\!\alpha _mh_m\Vert \!\le \! |\alpha _1|c_{k_1}+\cdots +|\alpha _m|c_{k_m}\le \prod _{1\le j\le m}(c_{k_j}+2s)=\beta (n). \end{aligned}$$

$\square$

Note that Lemma 7.5 implies that $\Sigma$ is a set of coset representatives for H in $\mathbb {Z}^{< \omega }.$ For $x \in X_H,$ we have $[x]_E= \{ g \cdot x :g \in \Sigma \}.$ If $g, h\in \Sigma$ and $g\ne h,$ then $g\cdot x\ne h\cdot x.$ So, for a fixed x we can identify $[x]_E$ with the set of $g \in \mathbb {Z}^{< \omega }$ in standard form. Note that this identification is not invariant, but depends on x.

Below we define a notion of distance on $X_H,$ although it will not correspond to a true metric.

Definition 7.9

For $x, y \in X_H$ with $x E_n y,$ let $\rho ^n_x(y)=\Vert g\Vert ,$ where $g \in \mathbb {Z}^n$ is the unique element in standard form such that $g \cdot x =y.$

Thus, $\rho ^n_x(y)$ is the “distance” from x to y as seen in the local (i.e., centered about x) rectangular coordinate system about x. This does not give a true metric since $\rho ^n_x(y) \ne \rho ^n_y(x)$ in general. However, in some sense these functions are close to a metric. We make this precise in the following lemma.

Lemma 7.10

For any $x, y \in X_H$ with $x E_n y$ we have $| \rho ^n_x(y)-\rho ^n_y(x)| \le \beta (n).$

Proof

Let $g \in \Sigma \cap \mathbb {Z}^n$ be such that $g \cdot x =y.$ Then $\Vert g \Vert =\rho ^n_x(y).$ We also have $\sigma (-g)\cdot y=(-g)\cdot y=x$ and $\Vert \sigma (-g)\Vert =\rho ^n_y(x).$ Thus

$$\begin{aligned} |\rho ^n_x(y)-\rho ^n_y(x)|=\left| \Vert g\Vert -\Vert \sigma (-g)\Vert \right| \le \Vert \sigma (-g)+g\Vert \le \beta (n) \end{aligned}$$

by Lemma 7.8(a). $\square$

With this notion of distance, we can now extend our basic marker result to the space $X_H.$

Lemma 7.11

Fix n and a marker distance $d \gg \beta (n).$ Then there is a relatively clopen set $M^n_d \subseteq X_H$ satisfying the following:

• (i) For every $x, y \in M^n_d$ with $x E_n y$ we have $\rho ^n_x(y) \ge d- \beta (n).$

• (ii) For every $y \in X_H,$ there is an $x \in M^n_d$ such that $\rho ^n_x(y) \le d.$

Proof

The proof is similar to that of Lemma 2.1. Let $s_0, s_1, \ldots$ enumerate the elements s of $2^{< \mathbb {Z}^n}$ satisfying:

• (1) The basic neighborhood $N_s \cap X_H$ of $X_H$ is nonempty.

• (2) For every $\vec {0} \ne g \in \mathbb {Z}^{< \omega }$ in standard form with $\Vert g \Vert \le d +\beta (n),$ $g \cdot N_s \cap N_s = \emptyset .$

As in the proof of Lemma 2.1 we define by induction on i a sequence of clopen sets $S_i \subseteq X_H.$ Let $S_0= N_{s_0} \cap X_H.$ Note that if $x, y \in N_{s_i} \cap X_H$ and $x \ne y,$ then $\rho ^n_x(y), \rho ^n_y(x) > d+\beta (n).$ In particular, (i) holds for the set $S_0.$ For $i>0$ we define

$$\begin{aligned} S_i= S_{i-1}\cup \left( N_{s_i}- \bigcup \{ g \cdot S_{i-1} :\Vert g \Vert \le d \text { and { g} is in standard form}\} \right) . \end{aligned}$$

Let $M^n_d= \bigcup _i S_i.$ If $x \ne y$ are both in $S_{i-1},$ then $\rho ^n_x(y),$ $\rho ^n_y(x) > d$ by induction. If $x \ne y$ are both in $N_{s_i},$ then $\rho ^n_x(y),$ $\rho ^n_y(x) \ge d+\beta (n).$ Finally, suppose $x \in S_{i-1}$ and $y \in N_{s_i}- \bigcup \{ g \cdot S_{i-1} :\Vert g \Vert \le d \hbox { and}\,g\ \hbox {is in standard form}\}.$ Then $\rho ^n_x(y) > d.$ From Lemma 7.10 we also have $\rho ^n_y(x) > d-\beta (n).$ It follows that (i) holds for $M^n_d.$

To see (ii), let $y \in X_H.$ Let i be the least such that $y \in N_{s_i}.$ This exists since for every $\vec {0} \ne g \in \mathbb {Z}^{< \omega }$ in standard form, $g \cdot y \ne y,$ and so for some neighborhood N of y,  $g \cdot N \cap N = \emptyset .$ If (ii) failed for y,  then

$$\begin{aligned} y \notin \bigcup \{ g \cdot S_{i-1} :\Vert g \Vert \le d \hbox { and} \ g \ \hbox {is in standard form}\}. \end{aligned}$$

It follows from the definition of $S_i$ that $y \in S_i \subseteq M^n_d,$ which contradicts the failure of (ii). $\square$

7.2 Marker regions in $X_H$

As in the case of the free part, we consider marker regions in $X_H$ that are rectangular and almost rectangular. These notions are defined below. In this section we will use the vector notion $\vec {a}$ to denote a sequence $\{a_i\}$ for the essential dimensions $i\le n$ for some fixed n. We use the following conventions about vectors:

• (1) $\vec {a}<\vec {b}$ if for $a_i<b_i$ for all essential dimensions $i\le n$; similarly for $\le , >, \ge ,$ etc. between vectors;

• (2) $\vec {a}+\vec {b}$ denotes the sequence $\{a_i+b_i\}$; similarly for $-.$

• (3) $|\vec {a}|$ denotes the sequence $\{|a_i|\}.$

• (4) If k is a number then $k\vec {a}$ denotes the sequence $\{ka_i\}.$

• (5) If k is a number then $\vec {a}>k$ means $a_i>k$ for all essential dimensions $i\le n$; similarly for $\le , >, \ge ,$ etc.

• (6) If k is a number then $\vec {a}+k$ denotes the sequence $\{a_i+k\}$; similarly for $-.$

Definition 7.12

Given $n\ge 1$ and integers $a_i<b_i$ for the essential dimensions $i\le n,$ let

$$\begin{aligned} \begin{array}{rcl} \Sigma (\vec {a},\vec {b})\!&{}=&{}\!\{ g \in \Sigma \cap \mathbb {Z}^n : \hbox {for all essential dimensions}\, i\!\le \! n,a_i \le \pi _i(g) \le b_i\} \\ &{}=&{}\{ g\in \mathbb {Z}^n: \hbox {for all essential dimensions}\, i\le n, a_i \le \pi _i(g) \le b_i\\ &{}&{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \wedge \ \hbox {for all inessential dimensions} \,i\le n,0\le \pi _i(g) \le s(i)\} \end{array} \end{aligned}$$

A rectangle in an $E_n$ equivalence class of $X_H$ is a set of the form $\Sigma (\vec {a},\vec {b})\cdot x$ for some x and $\vec {a}<\vec {b}.$ We denote it by $R(x;\vec {a},\vec {b}).$

In view of the reference point x,  we also say that $R(x;\vec {a},\vec {b})$ is a rectangle in the x-coordinate system. We refer to $\vec {b}-\vec {a}$ as the edge lengths of the rectangle $R(x;\vec {a},\vec {b}).$ These are explicitly defined only for the essential dimensions; for an inessential dimension $i\le n,$ the implicit edge length is s(i).

Definition 7.13

We say that $R(x;\vec {a},\vec {b})$ is centered about the point x if $\vec {a}=-\vec {b}.$ In this case we say x is the center of the rectangle $R(x;\vec {a},\vec {b}).$

In general, if $yE_nx$ but $y\ne x,$ then a rectangle R in the x-coordinate system may no longer be a rectangle in the y-coordinate system. However, by Lemma 7.10 R will be close to a rectangle in the y-coordinate system with $\beta (n)$ as a bound for the error. In other words, R will still be an almost rectangle (the precise definition and statement follow). In particular, if the edge lengths of R are large compared with $\beta (n),$ then in the y-coordinate system, R will still be almost a rectangle of the same edge lengths. This will be a key point behind the arguments in the rest of this section.

We now make the notion of an almost rectangle precise.

Definition 7.14

Let $\ell$ be a positive integer. By an $\ell$-almost rectangle in an $E_n$ equivalence class of $X_H$ we mean a set R such that there is $x \in X_H$ and $\vec {a}<\vec {b}$ with

$$\begin{aligned} R(x;\vec {a}+\ell , \vec {b}-\ell ) \subseteq R\subseteq R(x;\vec {a}-\ell ,\vec {b}+\ell ). \end{aligned}$$

In this case we say that R is an $\ell$ -almost rectangle in the x -coordinate system with edge lengths $\vec {b}-\vec {a}$ (again specified only for the essential dimensions). Note that the edge lengths of an almost rectangle are not well defined.

Lemma 7.15

Let R be a rectangle in an $E_n$ equivalence class $[x]_{E_n}$ of $X_H.$ Let $y E_n x.$ Then R is a $\beta (n)$-almost rectangle in the y-coordinate system.

Proof

Without loss of generality assume $R=R(x;\vec {a},\vec {b})=\Sigma (\vec {a},\vec {b})\cdot x.$ Let $h\in \Sigma \cap \mathbb {Z}^n$ be such that $h \cdot y =x.$ Then

$$\begin{aligned} R=(\Sigma (\vec {a},\vec {b})+h)\cdot y=\{\sigma (g+h):g\in \Sigma (\vec {a},\vec {b})\}\cdot y. \end{aligned}$$

For each essential dimension $i\le n,$ let $a'_i=a_i+\pi _i(h)$ and $b'_i=b_i+\pi _i(h).$ Then we claim that

$$\begin{aligned} R(y;\vec {a}'+\beta (n),\vec {b}'-\beta (n))\subseteq R\subseteq R(y;\vec {a}'-\beta (n), \vec {b}'+\beta (n)). \end{aligned}$$

(E2)

To show this it suffices to verify that

$$\begin{aligned} \Sigma (\vec {a}'+\beta (n),\vec {b}'-\beta (n))\subseteq & {} \{\sigma (g+h):g\in \Sigma (\vec {a},\vec {b})\}\\\subseteq & {} \Sigma (\vec {a}'-\beta (n),\vec {b}'+\beta (n)). \end{aligned}$$

Let $g\in \Sigma (\vec {a},\vec {b}).$ By Lemma 7.8(b) we have $\Vert \sigma (g+h)-g-h\Vert \le \beta (n).$ It follows that for any essential dimension $i\le n,$

$$\begin{aligned} \pi _i(g)+\pi _i(h)-\beta (n)\le \pi _i(\sigma (g+h))\le \pi _i(g)+\pi _i(h)+\beta (n). \end{aligned}$$

From this the second inclusion follows.

To prove the first inclusion, let $g\in \Sigma (\vec {a}'+\beta (n),\vec {b}'-\beta (n)).$ Then for all essential dimensions $i\le n,$

$$\begin{aligned} a_i+\pi _i(h)+\beta (n)\le \pi _i(g)\le b_i+\pi _i(h)-\beta (n), \end{aligned}$$

and thus

$$\begin{aligned} a_i+\beta (n)\le \pi _i(g-h)\le b_i-\beta (n). \end{aligned}$$

Again by Lemma 7.8(b) we have $\Vert \sigma (g-h)-g+h\Vert \le \beta (n).$ It follows that

$$\begin{aligned} a_i\le \pi _i(g-h)-\beta (n)\le \pi _i(\sigma (g-h))\le \pi _i(g-h)+\beta (n)\le b_i. \end{aligned}$$

This shows that $\sigma (g-h)\in \Sigma (\vec {a},\vec {b}).$ The inclusion follows upon noting that $g=\sigma (\sigma (g-h)+h)$ since $g\in \Sigma .$ $\square$

We next consider center points for almost rectangles. Intuitively, such center points are not unique but they should be close to each other. Our next definition and lemma make this precise.

Definition 7.16

Let $\ell$ be a positive integer and R be an $\ell$-almost rectangle in some $E_n$ equivalence class. By an $\ell$ -almost center for R we mean a point x such that there is $\vec {b}>0$ with

$$\begin{aligned} R(x;-\vec {b}+\ell ,\vec {b}-\ell )\subseteq R\subseteq R(x;-\vec {b}-\ell ,\vec {b}+\ell ). \end{aligned}$$

In this case we say that R is an $\ell$-almost rectangle centered about x.

In the degenerate case that $b_i<\ell$ for some i,  any point x with

$$\begin{aligned} R\subseteq R(x; -\vec {b}-\ell ,\vec {b}+\ell ) \end{aligned}$$

is an $\ell$-almost center for R. In particular, an $\ell$-almost center need not be contained in R. Of course, when the edge lengths of the $\ell$-almost rectangle R are sufficiently large, then the situation is nondegerate, and every $\ell$-almost center for R is necessarily contained in R.

Lemma 7.17

Let R be an $\ell$-almost rectangle in an $E_n$ equivalence class. Let x be an $\ell$-almost center for R.

• (a) If $yE_nx,$ then y is an $(\ell +\rho ^n_y(x)+\beta (n))$-almost center for R.

• (b) If y is also an $\ell$-almost center, then $\rho ^n_y(x)\le 2\ell +\beta (n).$

Proof

Assume $R(x;-\vec {b}+\ell ,\vec {b}-\ell )\subseteq R\subseteq R(x;-\vec {b}-\ell ,\vec {b}+\ell ).$ Let $h\in \Sigma \cap \mathbb {Z}^n$ be such that $h\cdot y=x.$ Then $\rho ^n_y(x)=\Vert h\Vert .$ Similar to the proof of Lemma 7.15, if we define $c_i=\pi _i(h)$ for all essential dimensions $i\le n,$ then by the Eq. (E2) in that proof, we have

$$\begin{aligned} R(y;-\vec {b}+\vec {c}+\ell +\beta (n),\vec {b}+\vec {c} -\ell -\beta (n))\subseteq R(x;-\vec {b}+\ell ,\vec {b}-\ell )\subseteq R \end{aligned}$$

and

$$\begin{aligned} R\subseteq R(x;-\vec {b}-\ell ,\vec {b}+\ell )\subseteq R(y;-\vec {b}+\vec {c}-\ell -\beta (n),\vec {b}+\vec {c}+\ell +\beta (n)). \end{aligned}$$

It follows that

$$\begin{aligned}&R(y;-\vec {b}+|\vec {c}|+\ell +\beta (n), \vec {b}-|\vec {c}|-\ell -\beta (n))\\&\quad \subseteq R\subseteq R(y; -\vec {b}-|\vec {c}|-\ell -\beta (n),\vec {b}+|\vec {c}|+\ell +\beta (n)). \end{aligned}$$

Since $|c_i|\le \rho ^n_y(x),$ we get that y is an $(\ell +\rho ^n_y(x)+\beta (n))$-almost center for R. This proves (a).

For (b), assume y is an $\ell$-almost center for R. Thus for some $\vec {d}>0$ we have

$$\begin{aligned} R(y;-\vec {d}+\ell , \vec {d}-\ell )\subseteq R\subseteq R(y;-\vec {d}-\ell ,\vec {d}+\ell ). \end{aligned}$$

It follows that

$$\begin{aligned} R(y; -\vec {d}+\ell ,\vec {d}-\ell )\subseteq R(y;-\vec {b}+\vec {c}-\ell -\beta (n),\vec {b}+\vec {c}+\ell +\beta (n)) \end{aligned}$$

and

$$\begin{aligned} R(y;-\vec {b}+\vec {c}+\ell +\beta (n),\vec {b}+\vec {c}-\ell -\beta (n))\subseteq R(y;-\vec {d}-\ell ,\vec {d}+\ell ). \end{aligned}$$

These in turn imply that for all essential dimensions $i\le n,$

$$\begin{aligned}&-d_i+\ell \ge -b_i+\pi _i(h)-\ell -\beta (n), \\&d_i-\ell \le b_i+\pi _i(h)+\ell +\beta (n), \\&-b_i+\pi _i(h)+\ell +\beta (n)\ge -d_i-\ell , \\&b_i+\pi _i(h)-\ell -\beta (n)\le d_i+\ell . \end{aligned}$$

These imply

$$\begin{aligned} b_i+|\pi _i(h)|-2\ell -\beta (n)\le d_i\le b_i-|\pi _i(h)|+2\ell +\beta (n), \end{aligned}$$

and so $|\pi _i(h)|\le 2\ell +\beta (n).$ $\square$

It is not clear whether every $\ell$-almost rectangle must have an $\ell$-almost center. But we have the following fact.

Lemma 7.18

Let R be an $\ell$-almost rectangle in an $E_n$ equivalence class. Then R has an $(\ell +\beta (n)+1)$-almost center.

Proof

Assume $R=R(x;\vec {a},\vec {b}).$ Let $c_i$ be the integer part of $\frac{1}{2}(a_i+b_i)$ for all essential dimensions $i\le n.$ Let $h\in \Sigma$ be such that $\pi _i(h)=c_i$ for all essential dimensions $i\le n$ and $\pi _i(h)=0$ for all inessential dimensions $i\le n.$ Let $y=h\cdot x.$ Then $(-h)\cdot y=x$ and $-h\in \Sigma .$ By the Eq. (E2) in the proof of Lemma 7.15 we have

$$\begin{aligned}&R(y; \vec {a}-\vec {c}+\ell +\beta (n), \vec {b}-\vec {c}-\ell -\beta (n))\\&\quad \subseteq R\subseteq R(y;\vec {a}-\vec {c}-\ell -\beta (n),\vec {b}-\vec {c}+\ell +\beta (n)). \end{aligned}$$

Since $\vec {c}-\vec {a}\le \vec {b}-\vec {c}\le \vec {c}-\vec {a}+1,$ we get that y is an $(\ell +\beta (n)+1)$-almost center for R. $\square$

In practice, the almost rectangles we construct will come from actual rectangles and will have almost centers with possibly a slightly different parameter $\ell .$ By Lemma 7.17(b), the set of $\ell$-almost centers for an $\ell$-almost rectangle R is finite. This will allow us to define a finitary algorithm (which we will not specify) to identify a “lexicographically least” $\ell$-almost center of R,  which we denote by $c_n(R).$ As we noted above, if R has sufficiently large edge lengths then $c_n(R)\in R.$ As usual it follows that the function $c_n$ is continuous in the sense that for each finite set $\{g_1,\ldots ,g_m\}\subseteq \Sigma \cap \mathbb {Z}^n,$ the map $x \mapsto c_n(\{ g_1\cdot x,\ldots ,g_m\cdot x\})$ from $X_H$ to $X_H$ is continuous.

For further discussions on the construction of regular marker regions in $X_H,$ we are going to use the following notion of distance between two sets.

Definition 7.19

Given two sets A and B in an $E_n$ equivalence class of $X_H,$ we define the Hausdorff distance between A and B by

$$\begin{aligned} \rho ^n(A,B)=\max \left\{ \sup _{x\in A}\inf _{y\in B}\rho ^n_x(y), \sup _{y \in B} \inf _{x \in A} \rho ^n_y(x)\right\} . \end{aligned}$$

The definition is motivated by the observation that, if R is an $\ell$-almost rectangle in the x-coordinate system, then there is a rectangle $R'$ in the x-coordinate system such that $\rho ^n(R, R')\le \ell .$

We now make more remarks on the almost rectangles we will construct. In practice, the almost rectangles we use will be regions whose boundaries are faces of actual rectangles. In fact, the almost rectangles themselves will not be actual rectangles because the different faces will come from rectangles having different centers. If $x\ne y$ are two such centers, a “flat face” of a rectangle in the x-coordinate system will not be flat in the y-coordinate system.

More specifically, for each essential dimension $i \le n$ of a rectangle $R(x;\vec {a},\vec {b}),$ there are two i-faces of R,  that is, the points of R of the form $\{ g \cdot x\,:\,\pi _i(g)=a_i\}$ and $\{ g\cdot x:\pi _i(g)=b_i\}.$ Note that these faces are defined with x as a necessary parameter. From the proof of Lemma 7.15 we have that if R is a rectangle in the x-coordinate system and $\mathcal {F}$ is an i-face of R (with respect to x), and $y E_n x,$ then $\mathcal {F}$ is within Hausdorff distance $\beta (n)$ of an i-face of a rectangle $R'$ in the y-coordinate system.

Before closing this subsection we define a notion of simultaneous almost rectangles for all dimensions and prove a strengthening of Lemma 7.15 for this notion. The following definition and lemma will be important for our hyperfiniteness proof. In stating the definition we deviate slightly from the conventions we adopted earlier for the notion of vectors. Henceforth $\vec {\beta }$ denotes the sequence $\{\beta (m)\}$ for all $m\le n.$ We also refer to various other vectors of different lengths. We will define them explicitly when there is a danger of confusion.

Definition 7.20

A region R in an $E_n$ equivalence class $[x]_{E_n}$ is said to be a $\vec {\beta }$ -almost rectangle in $E_n$ if for every $m \le n,$ and every $y E_n x,$ $R \cap [y]_{E_m}$ is a $\beta (m)$-almost rectangle in $E_m.$

Lemma 7.21

Let R be a rectangle in an $E_n$-class $[x]_{E_n}.$ Let $y E_n x.$ Then R is a $\vec {\beta }$-almost rectangle in $E_n$ in the y-coordinate system.

Proof

Let $R=\Sigma (\vec {a},\vec {b})\cdot x$ for $\vec {a}<\vec {b}.$ Let $m\le n.$ Let $a'_i=a_i$ and $b'_i=b_i$ for $i\le m.$ Let $h\in \Sigma \cap \mathbb {Z}^n$ be such that $h \cdot y =x.$ Let

$$\begin{aligned} h_l=\pi _1(h)e_1+\cdots +\pi _m(h)e_m \end{aligned}$$

and

$$\begin{aligned} h_r=h-h_l=\pi _{m+1}(h)e_{m+1}+\cdots +\pi _n(h)e_n. \end{aligned}$$

Then both $h_l$ and $h_r$ are still in standard form. Now for $g\in \Sigma (\vec {a},\vec {b})$ we have

$$\begin{aligned} g\cdot x\in R\cap [y]_{E_m}&\iff g\in \Sigma (\vec {a},\vec {b})\wedge g\cdot x\in [y]_{E_m} \\&\iff g\in \Sigma (\vec {a},\vec {b})\wedge \exists g'\in \mathbb {Z}^m\ (g\cdot x=g'\cdot y)\\&\iff g\in \Sigma (\vec {a},\vec {b})\wedge \exists g'\in \mathbb {Z}^m\ (g+h=g') \\&\iff g\in \Sigma (\vec {a},\vec {b})\wedge \exists g'\in \mathbb {Z}^m\ (g+h_r=g'). \end{aligned}$$

Note that if $g'\in \mathbb {Z}^m$ and $g'=g+h_r,$ then $g'\in \Sigma (\vec {a}',\vec {b}').$ Thus $R \cap [y]_{E_m}$ is of the form:

$$\begin{aligned} \{(g'-h_r)\cdot x:g'\in \Sigma (\vec {a}',\vec {b}')\} \end{aligned}$$

and also of the form

$$\begin{aligned} \{ (g'+h_l) \cdot y \,:\, g'\in \Sigma (\vec {a}',\vec {b}')\}. \end{aligned}$$

Since both $g'$ and $h_l$ are in standard form, the proof of Lemma 7.15 shows that this is a $\beta (m)$-almost rectangle in the y-coordinate system. $\square$

7.3 Hyperfiniteness of $E_H$

Our proof of the hyperfiniteness of $E_H$ will follow closely the outline of proofs in the free part.

We next generalize our rectangular marker region lemma to the non-free case.

Lemma 7.22

Fix n,  and let $d \gg \beta (n).$ Then there is a relatively clopen partition $\mathcal {R}$ of $X_H$ such that each $R \in \mathcal {R}$ is a $\vec {\beta }$-almost rectangle in $E_n$ with edge lengths d.

Proof

The proof is similar to that of Theorem 3.1. Fix $\Delta _2 \gg \Delta _1 \gg D > d^2.$ Let $M_1=M^n_{D_1} \subseteq X_H$ be the clopen marker set from Lemma 7.11 for distance $\Delta _1.$ Let $N \subseteq X_H$ be a relatively clopen marker set for distance $\Delta _2.$ For each $x \in N,$ let $g_x \in \Sigma \cap \mathbb {Z}^n$ be lexicographically least such that $g_x \cdot x \in M_1.$ By Lemma 7.10, $\Vert g_x\Vert \le \Delta _1+ \beta (n).$ Let $M_2= \{ g_x \cdot x :x \in N \} \subseteq M_1.$ Then $M_2$ is also relatively clopen.

If $x \ne y$ are both in $M_2,$ we claim that $\rho ^n_x(y) \ge \Delta _2-(2\Delta _1+6\beta (n)).$ To see this, let $g_1\in \Sigma$ and $x' \in N$ with $g_1 \cdot x'=x$ and $\Vert g_1\Vert \le \Delta _1+\beta (n),$ let $g_2\in \Sigma$ with $g_2 \cdot x=y$ and $\Vert g_2\Vert =\rho ^n_x(y),$ and finally let $g_3\in \Sigma$ and $y' \in N$ with $g_3 \cdot y'=y$ and $\Vert g_3\Vert \le \Delta _1+\beta (n).$ Then $\sigma (-g_3) \cdot y=y'$ and $\Vert \sigma (-g_3)\Vert \le \Delta _1+2\beta (n)$ by Lemma 7.8(a). Let $g=g_1+g_2+\sigma (-g_3).$ Then $g \cdot x'=y'$ and $\Vert g\Vert \le \rho ^n_x(y)+2 \Delta _1+3\beta (n).$ Since g is a sum of three elements in standard form, Lemma 7.8(b) gives $\Vert \sigma (g)\Vert \le \Vert g\Vert + 2\beta (n).$ So, $\rho ^n_{x'}(y') =\Vert \sigma (g)\Vert \le \rho ^n_x(y)+ 2 \Delta _1+5\beta (n).$ Since $\rho ^n_{x'}(y') \ge \Delta _2 -\beta (n),$ this shows $\rho ^n_x(y) \ge \Delta _2-(2 \Delta _1+ 6\beta (n)) \gg \Delta _1.$

A similar argument shows that for every $y \in X_H,$ there is an $x \in M_2$ such that $\rho ^n_x(y) \le \Delta _2+\Delta _1+ 3 \beta (n).$ Let $g_1, \ldots , g_k$ enumerate the elements $g\in \Sigma \cap \mathbb {Z}^n$ with $\Vert g\Vert \le \Delta _2+ \Delta _1+3 \beta (n).$ We define the sequence $A_0, A_1, \ldots , A_k$ of relatively clopen subsets of $X_H$ as follows. Let $A_0=M_2.$ For $i>0$ let $A_i= M_1 \cap ( g_i \cdot M_2) - \bigcup _{\iota <i} A_\iota .$ So, $M_1$ is the disjoint union of the $A_i,$ and for every i and every $x \ne y$ in $A_i$ we have $\rho ^n_x(y) \ge \Delta _2-(2 \Delta _1+6\beta (n)).$

For each $x \in M_1,$ let $R_x \subseteq [x]_{E_n}$ be the rectangle centered about x with edge lengths $4 \Delta _1.$ Thus, $X_H= \bigcup _{x \in M_1} R_x.$ In $k+1$ steps we adjust the rectangles $R_x$ for x in $A_0, \ldots , A_k$ respectively to rectangular regions $R'_x.$ We will move each face of a rectangle $R_x$ at each step by no more than $\frac{1}{10} \Delta _1.$ At each step, as we define $R'_x$ we also describe a partition of $R'_x$ into smaller almost rectangular regions.

To begin, for $x \in A_0$ let $R'_x=R_x.$ Suppose the adjusted rectangles $R'_x$ have been defined for $x \in A_j,$ $j<i.$ Consider $x \in A_i.$ We move each face of $R_x$ to avoid parallel faces of nearby $R'_y$ for $y \in \bigcup _{\iota <i} A_\iota .$ To be precise, consider an e-face $\mathcal {F}$ of $R_x,$ where $e\le n$ is an essential dimension. A face of $R'_y$ is parallel to $\mathcal {F}$ if it is an e-face of $R'_y.$ Without loss of generality, assume that

$$\begin{aligned} \mathcal {F}&= \{ g \cdot x :\pi _e(g) = 2 \Delta _1 \wedge \ |\pi _j(g)| \le 2 \Delta _1\, \hbox {for all essential dimensions}\\&\qquad j \ne e \ \wedge \ 0 \le \pi _j(g) <s(j)\quad \hbox {for all inessential dimensions} j\}. \end{aligned}$$

(The case where $\pi _e(g)=-2 \Delta _1$ is similar.) We define an integer a with $|a| \le \frac{1}{10} \Delta _1,$ and shift the face to

$$\begin{aligned} \mathcal {F}'&= \{ g \cdot x :\pi _e(g) = 2 \Delta _1+a \wedge \ |\pi _j(g)| \le 2 \Delta _1\, \hbox {for all essential dimensions}\\&\qquad j \ne e \ \wedge \ 0 \le \pi _j(g) <s(j)\, \hbox {for all inessential dimensions}\, j\}. \end{aligned}$$

Shifting these faces will define the new rectangle $R'_x.$ We wish to find a so that the shifted face $\mathcal {F}'$ will satisfy:

$$\begin{aligned}&\hbox {for any parallel face}\, \mathcal {G}\, \hbox {of a rectangle}\, R'_y\, \hbox {for} \,y\in \bigcup _{\iota <i} A_\iota , \\&\hbox {and any}\, u \in \mathcal {F}', v \in \mathcal {G}, \rho ^n_u(v) \ge 2D+\beta (n). \end{aligned}$$

(*)

There is clearly a bound $N=N(n)$ depending only on n,  for the number of $y \in \bigcup _{\iota <i} A_\iota$ with $\rho ^n_x(y) \le 6 \Delta _1.$ In fact a volume argument in the x-coordinate system shows this number to be bounded by

$$\begin{aligned} \frac{(13 \Delta _1)^m}{(\Delta _1/2 -\beta (n))^m } \le 52^m \le 52^n, \end{aligned}$$

where m is the number of essential dimensions $\le n.$ In fact, let $D_n$ be the set of all inessential dimensions $j\le n.$ For any distinct $y,z\in M_1,$

$$\begin{aligned} \rho ^n_y(z)\ge \Delta _1-\beta (n)>\Delta _1-2\beta (n). \end{aligned}$$

Thus the rectangles centered about y with edge lengths $\frac{1}{2}(\Delta _1-2\beta (n))$ are pairwise disjoint for distinct $y\in M_1$ if $\Delta _1>4\beta (n),$ which follows from the assumption that $\Delta _1\gg \beta (n),$ and there are at most $(\frac{1}{2}\Delta _1-\beta (n))^m\cdot \prod _{j\in D_n}s(j)$ many elements in any one of these rectangles. However, if $\rho ^n_x(y)\le 6\Delta _1,$ then the rectangle centered about y with edge lengths $\frac{1}{2}\Delta _1-\beta (n)$ is entirely contained in the rectangle centered about x with edge lengths

$$\begin{aligned} 2\cdot \left( 6\Delta _1+(\frac{1}{2}\Delta _1-\beta (n))+\beta (n)\right) = 13\Delta _1, \end{aligned}$$

and the latter rectangle has $(13\Delta _1)^m\cdot \prod _{j\in D_n}s(j)$ many elements. The estimate now follows from again $\Delta _1\ge 4\beta (n).$

Note that if $R'_y$ is a previously adjusted rectangle having a face $\mathcal {G}$ parallel to $\mathcal {F}$ and such that there are $u \in \mathcal {F},$ $v \in \mathcal {G}$ with $\rho ^n_u(v) \le \Delta _1,$ then

$$\begin{aligned} \rho ^n_x(y) \le (5\frac{1}{10}) \Delta _1+ 3 \beta (n) < 6 \Delta _1. \end{aligned}$$

Thus, there are at most 2N faces $\mathcal {G}$ to avoid. In the x-coordinate system, each of these faces consists of points whose eth coordinates vary by at most $\beta (n),$ by Lemma 7.8(b). The interval of possible values for a has size $\frac{2}{10} \Delta _1,$ and there are at most 2N many intervals of size $2\beta (n)$ to avoid. We may find an a in the interval of possible values which avoids all of the smaller intervals by at least $\epsilon$ as long as $\frac{2\Delta _1}{10}>2N(2\beta (n)+2\epsilon ).$ Given that $\Delta _1$ is sufficiently large compared to $\beta (n),$ we may assume that $\frac{2\Delta _1}{10} > 2N(4D+4\beta (n))$ (with $\epsilon =2D+\beta (n)$), and it follows that $(*)$ holds. This completes the definition of the $R'_x$ for $x \in A_i.$

Finally, we partition each new adjusted rectangle $R'_x.$ For each essential dimension $e \le n,$ let $\mathcal {G}^e_0, \ldots , \mathcal {G}^e_{L_e}$ enumerate the e-faces of the $R'_y,$ $y \in \bigcup _{\iota <i} A_\iota ,$ which intersect $R'_x.$ Each of these faces $\mathcal {G}^e_l$ is a rectangular face in the y-coordinate system for some y with $y E_n x.$ That is, $\mathcal {G}^e_l \subseteq \mathcal {H}^e_l= \{ g \cdot y :\pi _e(g)=c_l\}$ for some $c_l.$ The faces $\{ \mathcal {H}^e_l \}$ partition $R'_x$ into smaller regions, each of which is a $\vec {\beta }$-almost rectangle in $E_n$ with edge lengths at least 2D. Note that a finite intersection of $\vec {\beta }$-almost rectangles is a $\vec {\beta }$-almost rectangle. From this observation it follows that all of the regions produced are $\vec {\beta }$-almost rectangles. The set $S=R'_x- \bigcup _{\iota <i} \bigcup _{y \in A_\iota } R'_y$ is a union of a set of such $\vec {\beta }$-almost rectangular regions.

At the end of step k,  we have partitioned each $E_n$ class into $\vec {\beta }$-almost rectangular regions, each having edge lengths of at least $2D-2\beta (n).$ That is, for any u,  v on parallel faces of the almost rectangular subregion, $\rho ^n_x(y) \ge 2D-2\beta (n).$ Finally, since $2D-2\beta (n)> D > d^2,$ it is straightforward to divide each such $\vec {\beta }$-almost rectangular region T into $\vec {\beta }$-almost rectangular subregions with edge lengths almost d,  that is, for u, v on parallel faces we have $d-\beta (n)-1 \le \rho ^n_x(y) \le d+\beta (n)+1$ Namely, work in the x-coordinate system. For each essential dimension $i \le n,$ let $[a_i, b_i]$ be an interval in $\mathbb {Z}$ approximating within $\beta (n)$ the values of $\pi _i(g)$ for the set of g such that $g \cdot x \in T.$ Divide each such interval into subintervals each of length d or $d+1.$ This defines the partition of T into $\vec {\beta }$-almost rectangles of edge length d. $\square$

We next give the analog of Lemma 5.1 in the non-free case.

Lemma 7.23

Fix n and $d \gg \beta (n).$ Suppose $R^n_d$ is a clopen partition of $(X_H, E_n)$ into $\vec {\beta }$-almost rectangular regions of edge length d. Then there is a clopen subequivalence relation $\tilde{R}^n_d$ on $(X_H,E_n)$ satisfying:

• (1) Each $\tilde{R}^n_d$ class is a $\vec {\beta }$-almost rectangle with edge lengths between 9d and 12 d.

• (2) If $\mathcal {F}_1$ is a face of a $\tilde{R}^n_d$ region $R_1,$ and $\mathcal {F}_2$ a parallel face of a $R^n_d$ region $R_2,$ then for any $u \in \mathcal {F}_1,$ $v \in \mathcal {F}_2,$ $\rho ^n_u(v) > \frac{1}{9000^n 16^{n^2}} d.$

Proof

As in Lemma 5.1, let $s=Cd$ where $C=110 \cdot 4 \cdot 8 \cdot 16^n.$ As in Lemma 7.22, there is a clopen set $M=M_0 \cup M_1 \cup \cdots \cup M_k$ such that the set $\mathcal {R}$ of rectangles of edge lengths s centered at the points of M covers $X_H,$ and for each l,  and any $x \ne y$ in $M_l,$ $\rho ^n_x(y) \gg s.$ As in the proof of Lemma 5.1, we proceed in k steps. At step l we adjust the rectangles with centers in $M_l.$ As in that proof we do each adjustment in two steps. The set we are adjusting is a rectangle $R_x$ in the x-coordinate system about the center point x. For each essential dimension $i\le n,$ we adjust each of the two i-faces of $R_x.$ The precise notion of “face” and “adjustment” is as in the proof of Lemma 7.22. As in Lemma 5.1, in the first step we adjust by no more than $\frac{s}{8},$ and in the second step by no more than $\frac{s}{4 \cdot 8 \cdot 16^n} < \frac{s}{8}.$ The various faces to be avoided are now no longer true faces as seen in the x-coordinate system, but within $\beta (n)$ of a face of a rectangle in the x-coordinate system. The key point is that as long as d is sufficiently large compared to $\beta (n),$ then the inequalities in the proof of Lemma 5.1 continue to hold.

Consider, for example the second step of the adjustment. Each of the surrounding almost rectangles to be avoided can be approximated within $\beta (n)$ by a rectangle with edge lengths d (for the essential dimensions). Say there are $m \le n$ essential dimensions $i \le n.$ Then the estimate (E1) from Lemma 5.1 is modified by replacing occurrences of d in the numerator by $d+\beta (n),$ and in the denominator by $d-\beta (n).$ So, we have:

$$\begin{aligned} 2 \cdot \frac{\left( \frac{s}{4 \cdot 8 \cdot 16^n}+ 3(d+\beta (n))\right) \cdot (5s+ 23 (d+\beta (n)))^{m-1} }{(d-\beta (n))^m} \end{aligned}$$

as the upper bound, which is still less than $9000^n \cdot 16^{n^2}$ if d is sufficiently large compared to $\beta (n).$ As in the proof of Lemma 7.22, we can avoid parallel faces from these almost rectangles by $\epsilon$ as long as

$$\begin{aligned} \frac{s}{4 \cdot 8 \cdot 16^n} \ge 9000^{n} \cdot 16^{n^2}\cdot (2\beta (n)+2\epsilon ). \end{aligned}$$

With $\epsilon =\frac{1}{9000^n \cdot 16^{n^2}} d,$ this requires

$$\begin{aligned} 110d\ge 2\cdot 9000^n\cdot 16^{n^2}\cdot \beta (n)+2d, \end{aligned}$$

which follows from our assumption that $d\gg \beta (n).$ The rest of the proof is similar to the argument for Lemma 5.1. $\square$

In an exactly similar fashion we also have the following analog of Lemma 5.2.

Lemma 7.24

Fix n and $d \gg \beta (n).$ Let $R_1,\ldots , R_k$ be a sequence of clopen subequivalence relations of $(X_H, E_n)$ satisfying the following:

• (1) On each $E_n$ class, each $R_i$ induces a partition into regions R which are unions of $\vec {\beta }$-almost rectangles r such that each edge length of one of the r rectangles is between d and 12 d.

• (2) In any ball $B=\{ y \in [x]_{E_j} :\rho ^j_x(y)\le 10,000\cdot 16^j d_j\}$ of radius $100{,}000 \cdot 16^n d$ in some $E_n$ equivalence class, there are at most b integers i such that one of the $R_i$ regions has a face $\mathcal {F}$ which intersects B.

Then there is a clopen subequivalence relation $\tilde{R}^n_d \subseteq E_n$ satisfying:

• (1) Each $\tilde{R}^n_d$ class is a $\vec {\beta }$-almost rectangular region with edge lengths between 9 d and 12 d.

• (2) If $\mathcal {F}$ is a face of an $\tilde{R}^n_d$ region R,  and $\mathcal {F}'$ is a parallel face of an $R_i$ region $R'$ (for any i), then for any $u \in \mathcal {F},$ $v \in \mathcal {F}',$ $\rho ^n_u(v) > \frac{1}{9000^n 16^{n^2}b} d.$

To prove that $E_H$ is hyperfinite, we inductively define finite subequivalence relations $R_i$ in a similar fashion as for the free part. We need the analog of Lemma 6.1 which we now state. In this lemma all equivalence relations are subequivalence relations of $(X_H,E_i).$

Lemma 7.25

Let $j<i.$ Let $d_{j+1},$ $d_j$ be positive integers with $d_{j+1} \gg d_j,$ $d_j \gg \beta (j),$ and $d_{j+1} \gg \beta (j+1).$ Suppose $R^i_{j+1}$ is a clopen subequivalence relation of $E_i.$ Assume that the restriction of $R^i_{j+1}$ to each $E_{j+1}$ class induces a partition into regions each of which is a union of $\vec {\beta }$-almost rectangles with edge lengths between $d_{j+1}$ and $12 d_{j+1}.$ Suppose the clopen subequivalence relations $R^j_j,$ $R^{j+1}_j, \ldots ,$ $R^{i-1}_j$ and $R^{j+1}_{j+1},\ldots ,R^{i-1}_{j+1}$ of $E_\omega$ have been defined and satisfy:

• (1) $R^j_j \subseteq E_j$; $R^k_j \subseteq E_k$ and $R^k_{j+1} \subseteq E_k$ for all $j < k \le i-1.$

• (2) $R^j_j$ induces a partition of each $E_j$ class into $\vec {\beta }$-almost rectangular regions with edge lengths $d_j.$

• (3) For $j < k \le i-1,$ the restriction of $R^k_j$ to each $E_j$ class gives a partition into regions R each of which is a union of $\vec {\beta }$-almost rectangles with edge lengths between $9 d_j$ and $12 d_j.$

• (4) On each $E_j$ class, for each region R induced by the restriction of $R^k_j,$ there is a region $R'$ induced by the restriction of $R^k_{j+1}$ such that the Hausdorff distance between R and $R'$ is at most $12d_j.$

• (5) In any ball $B=\{ y \in [x]_{E_j} :\rho ^j_x(y)\le 10,000\cdot 16^j d_j\}$ of radius $100{,}000 \cdot 16^j d_j$ contained in an $E_j$ class, and for each essential dimension $e \le j$ there are at most $j+1$ many k with $j < k \le i-1$ such that some region induced by the restriction of $R^k_j$ has an e-face intersecting B.

• (6) For any $j < k_1 < k_2 \le i-1,$ and regions $R_1,$ $R_2$ in an $E_j$ class induced by restrictions of $R^{k_1}_j,$ $R^{k_2}_j$ respectively, if $\mathcal {F}_1,$ $\mathcal {F}_2$ are parallel faces of $R_1,$ $R_2,$ then for any $u \in \mathcal {F}_1,$ $v \in \mathcal {F}_2,$ $\rho ^j_u(v) > \frac{1}{9000^j 16^{j^2} (j+1)} d_j.$

• (7) For any $j <k_1<k_2 \le i$ and regions $R_1,$ $R_2$ in an $E_{j+1}$ class induced by the restrictions of $R^{k_1}_{j+1},$ $R^{k_2}_{j+1}$ respectively, if $\mathcal {F}_1,$ $\mathcal {F}_2$ are parallel faces of $R_1,$ $R_2,$ then for any $u \in \mathcal {F}_1,$ $v \in \mathcal {F}_2,$ $\rho ^{j+1}_u(v) > \frac{1}{9000^{j+1} 16^{(j+1)^2} (j+2)} d_{j+1}.$

Then there is a clopen subequivalence relation $R^i_j \subseteq E_i$ satisfying the following:

• (1) On each $E_j$ class, $R^i_j$ induces a partition into regions R each of which is a union of $\vec {\beta }$-almost rectangles with edge lengths between $9 d_j$ and $12 d_j.$

• (2) On each $E_j$ class, for each region R induced by the restriction of $R^i_j,$ there is a region $R'$ induced by the restriction of $R^i_{j+1}$ such that the Hausdorff distance between R and $R'$ is at most $12 d_j.$

• (3) Condition (5) continues to hold, where now $j<k \le i.$

• (4) Condition (6) continues to hold, where now $j<k \le i.$

Proof

The proof is almost identical to that of Lemma 6.1. We first apply Lemma 7.24 to produce the partition into $\vec {\beta }$-almost rectangular regions $\tilde{R}$ of edge lengths $d_j.$ The $R_1, \ldots , R_k$ of that lemma are the restrictions to $E_j$ of the current $R^j_j, \ldots R^{i-1}_j.$ The hypotheses of Lemma 7.24 are guaranteed by assumption (5) above together with $d_j \gg \beta (j).$ Our assumption is that the restriction of $R^i_{j+1}$ to each $E_{j+1}$ class induces a partition into regions each of which is a union of $\vec {\beta }$-almost rectangles of edge lengths at least $d_{j+1} \gg d_j.$ When we further restrict each $R^i_{j+1}$ region to each $E_j$ class, we still have regions which are finite unions of $\vec {\beta }$-almost rectangles of edge lengths between $d_{j+1}$ and $12 d_{j+1}.$ This follows from the definition of a $\vec {\beta }$-almost rectangle. In particular, these restricted regions are unions of $\beta (j)$-almost rectangles (this is the main point; when restricted to $E_j$ the error is bounded by $\beta (j),$ rather than $\beta (j+1)$).

We next use $R^i_{j+1}$ and $\tilde{R}$ to define $R^i_j.$ As in Lemma 6.1, let $\mathcal {A}$ denote the collection of j-dimensional $\vec {\beta }$-almost rectangles of edge length $d_j$ induced by $\tilde{R}.$ In particular, each of these regions is a $\beta (j)$-almost rectangle. By Lemma 7.18 each $\beta (j)$-almost rectangle $R \in \mathcal {A}$ has a $(2\beta (j)+1)$-almost center $c_j(R).$ Since $d_j\gg \beta (j)$ we still have $c_j(R) \in R.$ We define $x R^i_j y$ iff $x \in R_1 \in \mathcal {A},$ $y \in R_2 \in \mathcal {A},$ and $c_j(R_1) R^i_{j+1} c_j(R_2).$ Clearly each $R^i_j$ class is a union of $\vec {\beta }$-almost rectangles of edge lengths $d_j.$

For any $R\in \mathcal {A}$ and $x\in R,$ we have

$$\begin{aligned} \rho ^j_{c_j(x)}(x)\le 6d_j+2\beta (j)+1<6d_j+3\beta (j) \end{aligned}$$

and, by Lemma 7.10, $\rho ^j_x(c_j(x))\le 6d_j+4\beta (j).$ Thus any point in an $R^i_j$ region is within $6 d_j+4\beta (j)$ of an $R^i_{j+1}$ region. Moreover, we claim that every point on the boundary of an $R^i_{j}$ region is within $18 d_j + 16\beta (j)$ of a point on the boundary of an $R^i_{j+1}$ region. To see this, let x be a boundary point of an $R^i_j$ region, let $R\in \mathcal {A}$ with $x\in R,$ and $u=c_j(R).$ Since x is a boundary point, there is $\Vert g\Vert =1$ such that $y=g\cdot x$ is not contained in the $R^i_j$ region containing x. In particular $y\not \in R.$ Let $R'\in \mathcal {A}$ with $y\in R'$ and let $v=c_j(R').$ Note that either g or $-g$ is in standard form. Then by Lemma 7.8(b), we have

$$\begin{aligned} \rho ^j_u(v)&\le \rho ^j_u(x)+\rho ^j_x(y)+\rho ^j_y(v)+2\beta (j) \\&\le (6d_j+3\beta (j))+(1+\beta (j))+(6d_j+4\beta (j))+2\beta (j) \\&\le 12d_j+11\beta (j). \end{aligned}$$

Since $\lnot (uR^i_{j+1}v),$ there is a boundary point w in the $R^i_{j+1}$ region containing u with $\rho ^j_u(w)\le 12d_j+11\beta (j).$ Therefore

$$\begin{aligned} \rho ^j_x(w)&\le \rho ^j_x(u)+\rho ^j_u(w)+\beta (j) \\&\le (6d_j+4\beta (j))+(12d_j+11\beta (j))+\beta (j)\\&=18d_j+16\beta (j), \end{aligned}$$

as we claimed.

In view of these estimates, the inequalities used in the proof of Lemma 6.1 continue to hold if $d_{j+1} \gg d_j \gg \beta (j).$ The rest of the proof is thus completed as in Lemma 6.1. $\square$

We now state our main result for the non-free part.

Theorem 7.26

Let H be a subgroup of $\mathbb {Z}^{< \omega }$ and $X_H=\{ x \in X :G_x=H \},$ where $G_x= \{ g \in \mathbb {Z}^{< \omega }:g \cdot x=x\}.$ Let $E_H$ be the equivalence relation on $X_H$ from the shift action of $\mathbb {Z}^{< \omega }.$ Then there is a continuous embedding from $(X_H, E_H)$ into $E_0.$

Proof

The proof is similar to that of Theorem 6.2. We start with a sufficiently fast growing sequence $1 \ll d_1 \ll d_2 \ll \cdots ,$ where $d_i \gg \beta (i)$ for all i. For each i,  let $R^i_i$ be the clopen subequivalence relation of $E_i$ whose classes are $\vec {\beta }$-almost rectangles given by Lemma 7.22. We define inductively the sequence $R^i_i,$ $R^i_{i-1}, \ldots , R^i_1.$ Assume $R^i_{j+1}$ has been defined as have all the $R^k_j$ for $j \le k <i.$ Assume also that each $R^i_{j+1}$ region restricted to each $E_{j+1}$ class is a union of $\vec {\beta }$-almost rectangles of edge lengths between $d_{j+1}$ and $12 d_{j+1},$ and that the hypotheses of Lemma 7.25 are satisfied. Lemma 7.25 then gives $R^i_j$ and maintains the hypotheses. Thus, we define all the $R^i_j.$

Suppose x E y,  and fix $k_0$ so that $x E_{k_0} y.$ Let $\eta = \rho ^{k_0}_x(y).$ Suppose

$$\begin{aligned} I=\{i\ge k_0:\lnot x R^i_1 y\} \end{aligned}$$

is infinite. For each $i\in I,$ the $R^i_1$ region containing x must have a boundary point in the ball in $E_{k_0}$ of radius $\eta$ about x (in the x-coordinate system), so we may assume that some fixed point z lies on all their boundaries. From the estimates we made in the proof of Lemma 7.25, the point z is within

$$\begin{aligned} (18 d_1 +16 \beta (1))+ (18 d_2 + 16 \beta (2)) +\cdots + (18 d_{k_0-1}+16\beta (k_0-1))+2\beta (k_0) \end{aligned}$$

of a point on a boundary face of an approximating rectangle in $R^i_{k_0}$ for each $i\in I.$ Since $\beta (i) \ll d_i$ and $d_{k_0-1} \ll d_{k_0},$ we still contradict conclusion (4) of Lemma 7.25 as before.

Thus a continuous embedding from $E_H$ into $E_0(\omega ^\omega )$ can be defined by encoding the $R^i_1$ regions by integers, in a similar fashion as we did in the proof of Theorem 6.2. This completes the proof of Theorem 7.26. $\square$

8 Actions of countable abelian groups

In this section we summarize the results obtained in the previous two sections and deduce some corollaries. First we have the following basic theorem, which is a straightforward consequence of Theorem 7.26.

Theorem 8.1

Let E be the orbit equivalence relation induced by the shift action of ${\mathbb {Z}}^{<\omega }$ on $2^{{\mathbb {Z}}^{<\omega }}.$ Then E is hyperfinite.

This has the following immediate corollary.

Corollary 8.2

Let G be a countable abelian group acting in a Borel manner on a standard Borel space and let E be the induced orbit equivalence relation. Then E is hyperfinite.

Proof

Since every countable abelian group is a homomorphic image of ${\mathbb {Z}}^{<\omega },$ any action of G is also an action of ${\mathbb {Z}}^{<\omega }.$ By a result of Becker–Kechris ([1, Theorem 3.5.3]), the shift action of ${\mathbb {Z}}^{<\omega }$ on $2^{\mathbb {Z}^{< \omega }}$ is universal among all Borel actions of ${\mathbb {Z}}^{<\omega }.$ For the reader unfamiliar with this result, a complete proof is contained in the proof of Theorem 8.5 below. $\square$

This (partially) answers a question of Weiss (c.f. [4]) and also gives a positive answer to the following question of Kechris. Consider the equivalence relation $\sim _P$ on the set ${\mathbb {R}}_+$ of positive real numbers defined by

$$\begin{aligned} x\sim _P y\iff x/y\in {\mathbb {Q}}. \end{aligned}$$

This is known as the commensurability equivalence relation or the Pythagorean equivalence relation. Kechris asked if it is hyperfinite. Since the equivalence relation is induced by the product action of the multiplicative group of the positive rational numbers, we have the affirmative answer.

Corollary 8.3

The commensurability equivalence relation $\sim _P$ is hyperfinite.

In contrast, recall that the Vitali equivalence relation $\sim _V$ on ${\mathbb {R}}$ is defined by

$$\begin{aligned} x\sim _V y\iff x-y\in {\mathbb {Q}}. \end{aligned}$$

It is much easier and straightforward to see that $\sim _V$ is hyperfinite. A token of its simplicity is that the usual reduction used to show that $\sim _V\le _B E_0$ is a Baire class 1 function and in fact continuous on the set ${\mathbb {R}}-{\mathbb {Q}}$ of irrationals.

In the rest of this section we give some further corollaries of our main theorem. First note that the proof of the main theorem also shows the following slight variation.

Theorem 8.4

Let $2\le k\le \omega .$ Let E be the orbit equivalence relation induced by the shift action of ${\mathbb {Z}}^{<\omega }$ on $X=k^{{\mathbb {Z}}^{<\omega }}.$ Then E is hyperfinite.

Moreover, letting H be a subgroup of ${\mathbb {Z}}^{<\omega }$ and $X_H=\{x\in X:G_x=H\},$ then there is a continuous embedding of $E\upharpoonright X_H$ into $E_0.$

Next we consider continuous free actions of countable abelian groups. In the special case where the underlying space is 0-dimensional we always have continuous embeddings into $E_0.$

Theorem 8.5

Let G be a countable abelian group acting continuously and freely on a 0-dimensional Polish space X. Let E be the induced orbit equivalence relation. Then there is a continuous embedding of E into $E_0.$

Proof

This follows from the techniques used in [4], specifically those used in the proofs of Propositions 1.2, 1.4 and 1.6 of [4], which we recall below. First, fixing a countable clopen base $\{U_i\}$ for the topology of X,  we can define a reduction $f_0:X\rightarrow (2^{\omega })^G$ by

$$\begin{aligned} f_0(x)(g)(i)=1 \iff g^{-1}\cdot x\in U_i. \end{aligned}$$

$f_0$ is indeed an injective continuous G-map, i.e., $g\cdot f_0(x)=f_0(g\cdot x).$ It follows then that the image of $f_0$ is an invariant Borel subset of the free part of $(2^{\omega })^G.$ Next, via any bijection between ${\omega }$ and ${\mathbb {Z}}-\{0\}$ we identify the latter space with $(2^{{\mathbb {Z}}-\{0\}})^G.$ Then $f_0$ is essentially a continuous reduction from X to $(2^{{\mathbb {Z}}-\{0\}})^G.$ In the third step define a further reduction $f_1:(2^{{\mathbb {Z}}-\{0\}})^G\rightarrow 3^{G\times {\mathbb {Z}}}$ by

$$\begin{aligned} f_1(p)(g,n)=\left\{ \begin{array}{ll} p(g)(n), &{}\quad \hbox {if}\;n\ne 0,\\ 2, &{}\quad \hbox {if}\;n=0. \end{array}\right. \end{aligned}$$

Then $f_1$ is still injective and continuous, and sends the free part of $(2^{{\mathbb {Z}}-\{0\}})^G$ into the free part of $3^{G\times {\mathbb {Z}}}$ (by the proof of [4, Proposition 1.6]). In the fourth step we fix an onto homomorphism $\pi :{\mathbb {Z}}^{<\omega }\rightarrow G\times {\mathbb {Z}}$ and note that the trivial reduction $f_2:3^{G\times {\mathbb {Z}}}\rightarrow 3^{{\mathbb {Z}}^{<\omega }}$ defined by

$$\begin{aligned} f_2(p)(g)=p(\pi (g)) \end{aligned}$$

is injective and continuous and sends the free part of $3^{G\times {\mathbb {Z}}}$ into $X_H,$ where $H=\ker (\pi ).$ Now by Theorem 8.4 the last equivalence relation is continuously embeddable into $E_0.$ $\square$

The 0-dimensionality condition on X is of course necessary. In case X is connected every continuous function from X into $2^{\omega }$ is constant. Regarding the commensurability equivalence relation we have the following corollary.

Corollary 8.6

There is a Baire class 1 reduction from $\sim _P$ into $E_0,$ which is continuous on the set of positive irrational numbers.

Proof

Repeat the above proof verbatim assuming $\{U_i\}$ to be the usual countable open base for ${\mathbb {R}}_+,$ i.e., each $U_i$ is an open interval with rational endpoints. Then $f_0$ is Baire class 1 and is continuous on the set of positive irrational numbers. The proof then gives a Baire class 1 reduction of $\sim _P$ to $E_0,$ which is continuous on the irrational part. $\square$

In general, without assuming that the underlying space is 0-dimensional the following theorem is all we know.

Theorem 8.7

Let G be a countable abelian group acting continuously on a Polish space X. Let E be the induced orbit equivalence relation. Let $E_\omega ^*$ be the orbit equivalence relation induced by the shift action of ${\mathbb {Z}}^{<\omega }$ on ${\mathbb {R}}^{{\mathbb {Z}}^{<\omega }}.$ Then there is a continuous embedding of E into $E_\omega ^*.$

Proof

This is again achieved by composing several reductions. First we define a reduction $f_0^*:X\rightarrow X^G$ by

$$\begin{aligned} f_0^*(x)(g)=g^{-1}\cdot x. \end{aligned}$$

Then $f_0^*$ is injective and continuous, and it is a reduction of the orbit equivalence relation on X to that on $X^G.$ Next we note that any Polish space is homeomorphic to a $G_\delta$ subset of $[0,1]^{\omega }.$ Thus by identifying X with its homeomorphic copy in $[0,1]^{\omega }$ we may regard $f_0^*$ to be a reduction from X to $([0,1]^{\omega })^G.$ Now the reduction functions $f_1$ and $f_2$ in the preceding proof can be similarly redefined to get reductions $f_1^*:([0,1]^{\omega })^G\rightarrow {\mathbb {R}}^{G\times {\mathbb {Z}}}$ and $f_2^*:{\mathbb {R}}^{G\times {\mathbb {Z}}}\rightarrow {\mathbb {R}}^{{\mathbb {Z}}^{<\omega }}.$ The composition $f_2^*\circ f_1^*\circ f_0^*$ is a continuous embedding of E into $E_\omega ^*.$ $\square$

9 Continuous embeddings into $E_0$

In this section we show that there is a continuous, in fact computable (or recursive), embedding from the shift equivalence relation on $2^{\mathbb {Z}^n}$ into $E_0.$ For simplicity we use the following notation in this section. Let $n\ge 1$ be fixed. Let $X=2^{\mathbb {Z}^n}$ and let $\pi$ be the shift map on X. Let E denote the shift equivalence relation on X,  and F the shift equivalence relation on F(X),  where F(X) denotes the free part of X. Later in this section we will make use of the proofs given in Sect. 7. However, there will be no confusion since we do not work with $2^{\mathbb {Z}^{< \omega }}$ in this section, and the results we use from Sect. 7 are all about the shift action of $\mathbb {Z}^n.$ We state the main theorem of this section below.

Theorem 9.1

For each $n \ge 1,$ there is a computable one-to-one $f :2^{\mathbb {Z}^n} \rightarrow 2^\omega$ such that for all x,  $y \in 2^{\mathbb {Z}^n}$ we have x E y iff $f(x) E_0 f(y).$

The proof of Theorem 9.1 will use the ideas of Theorem 7.26 along with those of [2] where it was shown that there is a continuous embedding from $2^\mathbb {Z}$ into $E_0.$ The rest of this section is devoted to the proof of Theorem 9.1. We fix the dimension n for the remainder of the section.

Suppose that $H=\langle h_1, \ldots , h_p\rangle$ is a subgroup of $\mathbb {Z}^n,$ with $h_1, \ldots , h_p$ a normal basis for H (see Definition 7.1). Let $\tilde{X}_H= \{ x \in X :\forall h \in H\ h \cdot x=x\}.$ In particular, $X=\tilde{X}_{H_0},$ where $H_0=\{ \vec {0}\}$ is the identity subgroup of $\mathbb {Z}^n.$ Recall that $X_H$ denotes the set of $x \in X$ such that $G_x=H,$ where $G_x=\{ g \in \mathbb {Z}^n :g \cdot x=x\}.$ Thus, $X_H \subseteq \tilde{X}_H.$ Note that $X_H$ is the “free part” of $\tilde{X}_H,$ that is, the part of $\tilde{X}_H$ whose stabilizer group is exactly equal to H. We write $F_H$ for $E \upharpoonright X_H$ and $E_H$ for $E\upharpoonright \tilde{X}_H.$ Clearly $\tilde{X}_H$ is closed in X and $X_H$ is a $G_\delta$ in $\tilde{X}_H.$ It is also obvious that if $\dim (H)=n$ then $X_H$ is finite. We note the following fact which will be used substantially in the rest of the section.

Lemma 9.2

If $\dim (H)<n$ then $X_H$ is dense in $\tilde{X}_H.$

Proof

Let $x\in \tilde{X}_H$ and $F\subseteq \mathbb {Z}^n$ be finite. We need to find $y\in X_H$ such that $y\upharpoonright F=x\upharpoonright F.$ Let K be the quotient group $\mathbb {Z}^n/H$ and $\mathfrak {q}$ be the natural homomorphism from $\mathbb {Z}^n$ to K. Since $\dim (H)<n,$ K is infinite. Since $x\in \tilde{X}_H,$ we have that for all $g\in \mathbb {Z}^n$ and $h\in H,$ $x(g)=(h^{-1}\cdot x)(g)=x(g+h).$ Thus if we let $x^*:K\rightarrow \{0,1\}$ be given by $x^*(\mathfrak {q}(g))=x(g)$ for all $g\in \mathbb {Z}^n,$ then $x^*$ is well defined.

We claim that there is a $y^*:K\rightarrow \{0,1\}$ such that $y^*\upharpoonright \mathfrak {q}(F)=x^*\upharpoonright \mathfrak {q}(F)$ and for all non-identity $q\in K,$ $q\cdot y^*\ne y^*.$ In other words, $y^*$ is in the free part of $2^K$ and $y^*$ extends $x^*\upharpoonright \mathfrak {q}(F).$ This follows immediately from the density of the free part of $2^K$ because K is infinite. We give a quick argument to keep our exposition self-contained. Let $q_1,\ldots , q_k,\ldots$ enumerate all non-identity elements of K. Let $F^*_0=\mathfrak {q}(F).$ Inductively we define finite sets $F^*_{k+1}\supseteq F^*_k$ and $y^*\upharpoonright F^*_{k+1}$ so that $q_k\in F^*_{k+1}$ and so that there is $q\in F^*_{k+1}$ with $q_k+q\in F^*_{k+1}$ and $y^*(q)\ne y^*(q+q_k).$ Suppose $F^*_k$ and $y\upharpoonright F^*_k$ have been defined. Since $F^*_k$ is finite and K is infinite, there must be some $q\not \in F^*_k.$ We just make sure $q, q+q_k\in F^*_{k+1}$ and $y^*(q)\ne y^*(q+q_k).$ This finishes the construction of $y^*$ and proves the claim.

Now define $y:\mathbb {Z}^n\rightarrow \{0,1\}$ by letting $y(g)=y^*(\mathfrak {q}(g))$ for all $g\in \mathbb {Z}^n.$ Then it is easy to verify that $y\upharpoonright F=x\upharpoonright F.$ Clearly $h\cdot y=y$ for all $h\in H.$ To see that $y\in X_H,$ assume toward a contradiction that $g\in \mathbb {Z}^n-H$ is such that $g^{-1}\cdot y=y.$ Then $\mathfrak {q}(g)$ is not the identity in K,  but $y^*(q+\mathfrak {q}(g))=y^*(q)$ for all $q\in K.$ This means $\mathfrak {q}(g)^{-1}\cdot y^*=y^*,$ a contradiction. $\square$

Relatively open subsets of $X_H$ can be extended to $\tilde{X}_H$ systematically as follows. Fix a standard countable base $\{ V_i\}$ for the topology on X. Then $\{V_i\cap \tilde{X}_H\}$ is a base for the topology of $\tilde{X}_H$ and $\{V_i\cap X_H\}$ is a base for the topology of $X_H.$ We regard both of them as the standard bases. Now for any sequence $(i_m)_{m\in \omega },$ if $A=\bigcup _{m\in \omega } (V_{i_m}\cap X_H)$ is an open subset of $X_H,$ we let $\tilde{A}=\bigcup _{m\in \omega }(V_{i_m}\cap \tilde{X}_H).$ Then $\tilde{A}$ is an open subset of $\tilde{X}_H$ such that $\tilde{A} \cap X_H=A.$ Note that $\tilde{A}$ is not canonically determined from the set A. Rather, it depends on the sequence $(i_m).$ For notational simplicity we will just write $\tilde{A},$ assuming implicitly a neighborhood sequence $(i_m)$ has been specified. This notation will also be used for subsets of $X_H \times X_H,$ etc., unless specified otherwise.

We also need a refinement of the above notion. Recall that a set $A \subseteq X_H$ is relatively $\Sigma ^0_1$ if there is a computable total function $f :\omega \rightarrow \omega$ such that

$$\begin{aligned} A= \bigcup _{m\in \omega } (V_{f(m)}\cap X_H). \end{aligned}$$

In this case we also let $\tilde{A}=\bigcup _{m\in \omega } (V_{f(m)} \cap \tilde{X}_H).$ Again, it is understood that this depends on the enumerating function f,  and we have implicitly chosen one. We call $\tilde{A}$ the $\Sigma ^0_1$ extension of A to $\tilde{X}_H.$

We will fix computable bijections between $\omega$ and various relevant sets such as $\mathbb {Z},$ $\mathbb {Z}^n,$ $\omega ^{<\omega },$ etc. For each of the relevant sets N,  the computable bijective function from N onto $\omega$ will be denoted by $\#(\cdot )$ and referred to as the coding function. For instance, if $(k_0,\ldots ,k_l)\in \omega ^{<\omega }$ is a sequence, then $\#(k_0,\ldots ,k_l)\in \omega$ is the code for the sequence. The inverse of a coding function is called a decoding function. For instance, the decoding function from $\omega$ to $\mathbb {Z}^n$ gives a computable enumeration of all group elements in $\mathbb {Z}^n,$ and we use the notation $k\mapsto g_k$ for it. Via the coding and decoding functions we will be able to speak of computable functions between any two relevant sets.

The coding function $\#:\mathbb {Z}^n\rightarrow \omega$ will also induce a one-one correspondence between $X=2^{\mathbb {Z}^n}$ and $2^\omega .$ This allows us to refer to a lexicographic order for elements of X.

We note the following fact about the computability of a normal basis.

Lemma 9.3

There is a computable total function $t:\omega ^{<\omega }\rightarrow \omega ^{<\omega }$ such that for any sequence $(k_0,\ldots , k_l)\in \omega ^{<\omega },$ if $(m_0,\ldots , m_q)=t(k_0,\ldots , k_l),$ then $g_{m_0},\ldots , g_{m_q}$ is a normal basis for $\langle g_{k_0},\ldots , g_{k_l}\rangle .$

Proof

As in Sect. 7 for each $1\le i\le n$ we use $\mathbb {Z}^i$ to denote the subset $\mathbb {Z}^i\times \{0\}^{n-i}$ of $\mathbb {Z}^n.$ Given $g_{k_0},\ldots , g_{k_l}$ let $H=\langle g_{k_0},\ldots , g_{k_l}\rangle .$ By a Gaussian elimination algorithm, one can find $g_{k'_1},\ldots , g_{k'_n}$ such that for any $1\le i\le n,$ $\langle g_{k'_1},\ldots , g_{k'_i}\rangle =H\cap \mathbb {Z}^i.$ Then the proof of Lemma 7.2 gives an algorithm that can be applied to the non-zero elements of $g_{k'_1},\ldots , g_{k'_n}$ to obtain a normal basis $g_{m_0},\ldots , g_{m_q}.$ $\square$

Let $\mathcal {B}$ be the set of all normal bases for subgroups of $\mathbb {Z}^n.$ It is easily seen from Definition 7.1 that $\mathcal {B}$ is a computable subset of $(\mathbb {Z}^n)^{<\omega }.$

For each subgroup H with normal basis $B=(h_1,\ldots ,h_p)\in \mathcal {B}$ we shall define a computable embedding $\pi ^H$ from $E_H$ into $E_0.$ In fact, $\pi ^H$ will be a total computable function from X to $2^\omega$ such that $\pi ^H\!\upharpoonright \! \tilde{X}_H$ is an embedding from $E_H$ into $E_0.$ To do this, we define a total computable function from $\mathcal {B}\times \omega \times \omega ^\omega$ to $\omega .$ We denote the value of the function at (B, k, x) by $\pi ^B_k(x).$ If $H=\langle B\rangle ,$ we will also write $\pi ^H_k(x),$ with the understanding that a normal basis is fixed. We think of $\pi ^H_k(x)$ as the stage k output of $\pi ^H(x).$ That is, we will have that $\pi ^H(x)=(\pi ^H_0(x), \pi ^H_1(x),\ldots )$ is the sequence of the stage k outputs. We will have that $\pi ^{H_0},$ with $H_0=\{\vec {0}\},$ is then the desired embedding for Theorem 9.1.

We shall define $\pi ^H_k(x)$ by a reverse induction on H. That is, we will define $\pi ^H_k(x)$ assuming $\pi ^{H'}_k(x)$ is defined for all subgroups $H'$ with $H' \gneq H.$ This is clearly a legitimate definition as there is no infinite strictly increasing sequence of subgroups of $\mathbb {Z}^n.$

Consider first the case $\dim (H)=n,$ so H has a normal basis $B=(h_1,\ldots ,h_n).$ In this case $\mathbb {Z}^n/H$ is finite, and a finite set of representatives for all cosets of H in $\mathbb {Z}^n$ is computable from B (for instance, the set of all elements in $\mathbb {Z}^n$ in standard form with respect to H in the sense of Sect. 7 is such a set). Letting $F_0$ be such a finite set of coset representatives, any $x\in \tilde{X}_H$ is determined by $x\upharpoonright F_0.$ It follows that each $E_H$ class is finite, and in fact contains no more than $k_0=2^{|F_0|}$ many elements. Let $F_1=F_0+[-k_0,k_0]^n.$ Then, given any $x,y\in \tilde{X}_H,$ it is decidable whether $y\in [x]_{E_H}$ using information only about $x\upharpoonright F_1$ and $y\upharpoonright F_1.$ Let $k_1$ be large enough so that $F_1\subseteq \{g_0, g_1,\ldots , g_{k_1}\}$ and let $F_2=\{g_0,g_1,\ldots , g_{k_1}\}.$ Then, given any $x,y\in \tilde{X}_H,$ the lexicographic order between x and y is decidable using information only about $x\upharpoonright F_2$ and $y\upharpoonright F_2.$ Combining these procedures, we may compute from any $x\in \tilde{X}_H$ the lexicographically least element of $[x]_{E_H}$ with information only about $x\upharpoonright F_2.$ Such an algorithm can be applied to any element of X,  and we obtain $\sigma ^B:X\rightarrow X,$ a total computable function uniformly in B,  with the property that for all $x \in \tilde{X}_H,$ $\sigma ^B(x)$ is the lexicographically least member of $[x]_E=[x]_{E_H}.$ $\sigma ^B \upharpoonright \tilde{X}_H$ is a reduction from $E_H$ to the equality relation on X. There is easily a computable function $\tau$ from X to $2^\omega$ which embeds $(X, =)$ into $(2^\omega , E_0).$ Finally, let $\gamma ^B :X\rightarrow \omega ^\omega$ be a computable function defined uniformly in B such that for $x \in \tilde{X}_H,$ $\gamma ^B(x)(0)$ codes the least $\gamma \in G$ such that $\gamma \cdot x= \sigma ^B(x),$ and $\gamma ^B(x)(k)=0$ for $k>0.$ Let $\pi ^H_k(x)=\#(\tau (\sigma ^B(x))(k), \gamma ^B(x)(k)).$ It is easy to check that $\pi ^H\upharpoonright \tilde{X}_H$ is an embedding from $E_H$ into $E_0(\omega ^\omega ).$

Next we handle the inductive step. Assume henceforth that $\dim (H)=p<n$ and that $B=(h_1,\ldots ,h_p)$ is a normal basis for H. Assume we have defined $\pi ^{B'}_k(x)$ for $x \in X,$ $k\in \omega ,$ and $B'\in \mathcal {B}$ with $\langle B'\rangle \supsetneq H.$ We proceed to define $\pi ^B_k(x).$

To begin, fix a sufficiently fast growing sequence $d^B_1 \ll d^B_2 \ll \cdots$ of marker distances. We may assume that the map $(B,i) \mapsto d^B_i$ is computable. We will use the terminology from Sect. 7. In particular, let $b^B$ denote the value of $\beta (n)$ from Definition 7.7 with respect to H. Here, of course, n is fixed, so $b^B$ is just a single number. A $\vec {b}^B$-almost rectangle will be as in Definition 7.20, using now the constant function $\beta (k)=b^B$ for all $1\le k\le n.$ We may assume that $d^B_1$ is sufficiently large compared to $b^B.$ We now repeat the proofs of Lemmas 7.22, 7.23, and 7.24 in this context, that is, for n fixed. To fix notation, we summarize the main steps of these proofs. All of the constructions below are done uniformly in the normal basis $B=(h_1, \ldots , h_p)$ for H. To ease the notation, however, we sometimes suppress mentioning this dependence on B.

For each i,  let $R^i_i=R^{i,B}_i$ be the subequivalence relation of $F_H$ obtained from Lemma 7.22 for edge length $d_i=d^B_i.$ Each $R^i_i$ class is a b-almost rectangle with edge lengths $d_i.$ Let $C_i =C^B_i\subseteq X_H$ denote the set of centers of these b-almost rectangular regions. Recall that a center of such a b-almost rectangular region is the lexicographically least element of the set of all of its $(2b+1)$-almost centers. The proofs of Lemmas 7.11, 7.22 and 7.18 show that $C_i$ is relatively clopen in $X_H.$ In fact, the $C_i$ are uniformly $\Delta ^0_1$ in B and i. That is, there are $\Sigma ^0_1$ relations $A_1, A_2 \subseteq \mathcal {B}\times X\times \omega$ such that for all $B \in \mathcal {B}$ and $x \in X_H$ we have $x \in C^B_i\leftrightarrow A_1(B,x,i) \leftrightarrow \lnot A_2(B,x,i) .$ To see this, note that the $d^B_i$ and the sequences $s_n=s^B_n$ (defined for each i) as in the proof of Lemma 7.11 are all given by computable functions. The rest of the proof of Theorem 3.1 (and Lemma 7.22) involves effective operations on these sets. So, there is a computable f such that for all B and i we have that $C^B_i=\bigcup _k (V_{f(B,i,k)}\cap X_H).$ We let ${\tilde{C}}^B_i=\bigcup _k (V_{f(B,i,k)} \cap \tilde{X}_H)$ be the $\Sigma ^0_1$ extension of $C^B_i$ to $\tilde{X}_H.$

The proof of Theorem 3.1 (and so also Lemma 7.22) then shows that the relations $R^{i,B}_i$ are, uniformly in B and i,  $\Delta ^0_1$ on $X_H.$ It follows that there are $\Sigma ^0_1$ relations $A_3,$ $A_4 \subseteq \mathcal {B}\times X\times \mathbb {Z}^n \times \omega$ such that for $B\in \mathcal {B},$ $x \in X_H,$ $g \in \mathbb {Z}^n,$ and $i \in \omega$ we have

$$\begin{aligned} R^{i,B}_i(x,g \cdot x) \leftrightarrow A_3(B,x,g,i) \leftrightarrow \lnot A_4(B,x,g,i). \end{aligned}$$

Note that for all B,  the sets $A^B_3$ and $A^B_4$ (the sections of $A_3,$ $A_4$ at B) are actually disjoint on $\tilde{X}_H \times \mathbb {Z}^n \times \omega .$ This is because, if $(x,g,i) \in A^B_3 \cap A^B_4$ with $x \in \tilde{X}_H,$ then by the density of $X_H$ in $\tilde{X}_H$ shown by Lemma 9.2, there would be an $x' \in X_H$ with $(x',g,i) \in A^B_3 \cap A^B_4.$ Let ${\tilde{R}}^{i,B}_i$ be the $\Sigma ^0_1$ extension of $A^B_3$ to $\tilde{X}_H.$

As in the proof of Lemma 7.25 and Theorem 7.26 (which in turn are modifications of the proof of Theorem 6.2), we proceed in $i-1$ steps to modify the subequivalence relations $R^i_i$ to relations $R^i_{i-1},$ $R^i_{i-2}, \ldots , R^i_1,$ all of which are subequivalence relations of $F_H.$ Thus, the $R^i_j$ are subequivalence relations of $F_H$ and satisfy the following:

• (1) On each $F_H$ class, $R^i_j$ induces a partition into regions R each of which is a union of b-almost rectangles with edge lengths between $9 d_j$ and $12 d_j.$

• (2) For each region R induced by $R^i_j,$ there is a region $R'$ induced by $R^i_{j+1}$ such that the Hausdorff distance between R and $R'$ is at most $12 d_j.$

• (3) For any $j < k_1 \ne k_2 \le i-1,$ and $R_1,$ $R_2$ regions induced by $R^{k_1}_j,$ $R^{k_2}_j$ respectively, if $\mathcal {F}_1,$ $\mathcal {F}_2$ are parallel boundary faces of $R_1,$ $R_2,$ then $\rho (\mathcal {F}_1,\mathcal {F}_2) > \frac{1}{9000^j 16^{j^2} (j+1)} d_j.$

The proof of Lemma 7.25 is effective, and thus the $R^i_1=R^{i,B}_1$ are, uniformly in B and i,  $\Delta ^0_1$ on $X_H.$ So, there are $\Sigma ^0_1$ relations $A_5,$ $A_6 \subseteq \mathcal {B}\times X \times \mathbb {Z}^n \times \omega$ such that for all $B \in \mathcal {B},$ $x \in X_H,$ $g \in \mathbb {Z}^n,$ and $i \in \omega ,$

$$\begin{aligned} x R^{i,B}_1 g \cdot x\leftrightarrow A_5(B,x,g,i) \leftrightarrow A_6(B,x,g,i). \end{aligned}$$

In Lemma 9.5 below we show that each $R^{i,B}_1$ class contains exactly one point of $C^B_i.$ The proof of Theorem 7.26 shows that for each B the $R^{i,B}_1$ give a continuous embedding of $F_H$ into $E_0,$ and by our remarks this embedding is actually computable on $X_H.$ Our embedding $\pi ^H,$ however, will be defined on the entire X and, more importantly, must be a reduction on the “non-free” part of $\tilde{X}_H$ as well.

Let $\tilde{A}_5$ and $\tilde{A}_6$ denote the respective $\Sigma ^0_1$ extensions of $A_5$ and $A_6$ to $\mathcal {B}\times \tilde{X}_H \times \mathbb {Z}^n \times \omega .$ Let ${\tilde{R}}^{i,B}_1$ be the extension of $R^{i,B}_1$ to $\tilde{X}_H \times \tilde{X}_H$ defined as follows.

$$\begin{aligned} x \tilde{R}^{i,B}_1 y\leftrightarrow \exists z&\in \tilde{X}_H\ \exists g_1, g_2 \in \mathbb {Z}^n\ ( z \in \tilde{C}^B_i \wedge \Vert g_1\Vert , \Vert g_2\Vert < 20 d^B_i\\&\wedge g_1 \cdot z =x \wedge g_2 \cdot z =y \wedge \tilde{A}_5(B,z,g_1,i) \wedge \tilde{A}_5(B,z,g_2,i) ). \end{aligned}$$

It is straightforward to check that $\tilde{R}^{i,B}_1\cap (X_H\times X_H)=R^{i,B}_1$ and that $\tilde{R}^{i,B}_1$ is $\Sigma ^0_1$ in the sense that $\{ (x,g):x \tilde{R}^{i,B}_1 g\cdot x \}$ is $\Sigma ^0_1$ on $\tilde{X}_H \times \mathbb {Z}^n.$ Also, ${\tilde{R}}^{i,B}_1$ is a symmetric, transitive relation on $\tilde{X}_H$ (but not necessarily reflexive). We give a proof of the transitivity below.

Lemma 9.4

$\tilde{R}^{i,B}_1$ is a transitive relation on $\tilde{X}_H\times \tilde{X}_H.$

Proof

Suppose $x {\tilde{R}}^{i,B}_1 y$ and $y {\tilde{R}}^{i,B}_1 w.$ Let $z_1,$ $g_1,$ $g_2$ witness $x {\tilde{R}}^{i,B}_1 y,$ and $z_2,$ $g_3,$ $g_4$ witness $y{\tilde{R}}^{i,B}_1 w.$ We first claim that $z_1=z_2.$ Otherwise by the density of $X_H$ in $\tilde{X}_H,$ there would be $z'_1, z'_2, y'\in X_H$ with $z'_1 \ne z'_2,$ $z'_1, z'_2 \in C^B_i$ and $R^{i,B}_1(z'_1, y'),$ $R^{i,B}_1(z'_2,y').$ Since $R^{i,B}_1$ is an equivalence relation, we have $z'_1 R^{i,B}_1 z'_2,$ a contradiction as $z'_1$ and $z'_2$ are distinct points of $C^B_i.$

With $z_1=z_2,$ we now have $z_1,$ $g_1,$ $g_4$ witness that $x {\tilde{R}}^{i,B}_1 w.$ $\square$

It follows from the above lemma that, if $x\in \tilde{X}_H,$ then on each $E_H$ class $[x]_{E_H},$ each $\tilde{R}^{i,B}_1$ gives a partition of a subset of $[x]_{E_H}.$ We next note that for every $B\in \mathcal {B}$ and $i\in \omega ,$ if $x \in \tilde{X}_H$ is in the domain of ${\tilde{R}}^{i,B}_1$ then there is a unique point of ${\tilde{C}}^B_i$ in the ${\tilde{R}}^{i,B}_1$ equivalence class of x. This follows from a density argument similar to the one in the above proof, provided that the corresponding uniqueness statement in $X_H$ holds. The uniqueness in $X_H$ in turn follows from our construction of the $R^i_1$ regions in Lemma 7.25. Since this argument was not presented in Sect. 7 (it was not needed there), we give the proof below.

Lemma 9.5

For every $B \in \mathcal {B}$ and $i \in \omega ,$ there is a unique point in $C^B_i$ in each $R^{i,B}_1$ equivalence class. Also, if $x \in \tilde{X}_H$ is in the domain of ${\tilde{R}}^{i,B}_1$ then there is a unique point of ${\tilde{C}}^B_i$ in the ${\tilde{R}}^{i,B}_1$ equivalence class of x.

Proof

For each B,  i and almost rectangular region R in $R^{i,B}_i,$ since $d^B_i \gg b^B,$ it follows easily that there is a unique point c(R) of $C^B_i$ in R. For $B \in \mathcal {B},$ $x \in X_H,$ and $i \in \omega$ there is a unique $R^{i,B}_i$ class $R \subseteq [x]_E$ such that the $R^{i,B}_1$ class $R'$ of x satisfies

$$\begin{aligned} \rho ^B(R, R') \le 12 (d^B_1+ \cdots + d^B_{i-1}) \end{aligned}$$

(here $\rho ^B$ denotes the Hausdorff distance as defined using the basis B,  see Definition 7.19). The fact that R exists follows by repeated application of (2). To see uniqueness, suppose R and S were two such regions for $R'.$ Then

$$\begin{aligned} \rho ^B(R,S) \le 24 (d^B_1+ \cdots + d^B_{i-1}) < d^B_i -b^B. \end{aligned}$$

This is a contradiction as $\rho ^B(c(R),s) \ge d^B_i - b^B$ for any $s \in S.$ For $x \in X_H,$ let $c^B_i(x)=c(R)$ where R is the unique $R^{i,B}_i$ class in $[x]_{E}$ such that

$$\begin{aligned} \rho (R, [x]_{R^{i,B}_1}) \le 12 (d_1+ \cdots + d_{i-1}). \end{aligned}$$

Then $c^B_i(x) \in C^B_i$ and $c^B_i(x)$ is in the unique R as above. We must have $c^B_i(x) \in R'= [x]_{R^{i,B}_1}$ as otherwise there is a district $R^{i,B}_i$ class $S \ne R$ such that

$$\begin{aligned} \rho ^B(c^b_i(x),S) \le 12 (d^B_1+ \cdots + d^B_{i-1}) < d^B_i-b^B, \end{aligned}$$

and this is not the case. The same argument shows that there cannot be two distinct $R^{i,B}_i$ classes R and S such that c(R) and c(S) both lie in $R'.$

Suppose now that $x \in \tilde{X}_H$ is in the domain of ${\tilde{R}}^{i,B}_1.$ From the definition of ${\tilde{R}}^{i,B}_1$ it is immediate that that there is a $z \in {\tilde{C}}^B_i$ with $z {\tilde{R}}^{i,B}_1 x$ (take $g_1=0$ in the definition of ${\tilde{R}}^{i,B}_1$). Suppose $z_1,z_2 \in {\tilde{C}}^B_i$ were two such points. The density of $X_H$ in $\tilde{X}_H$ would then give points $z'_1,$ $z'_2,$ $x'$ in $X_H$ with $z'_1\ne z'_2,$ $z_1,z_2 \in C^B_i,$ and $z'_1 R^{i,B}_1 x',$ $z'_2 R^{i,B}_1 x'.$ This contradicts the previous paragraph. $\square$

For each $x \in X$ and $m \ge 1,$ let $N_m(x)$ denote the basic open set in $\tilde{X}_H$:

$$\begin{aligned} N_m(x)=\{ y \in \tilde{X}_H :\forall g \in \mathbb {Z}^n\ ( \Vert g\Vert \le m \rightarrow y(g)=x(g))\}. \end{aligned}$$

If $x \in \tilde{X}_H,$ then $N_m(x)\ne \emptyset .$ We may identify $N_m(x)$ with $x \upharpoonright \{ g :\Vert g\Vert \le m \}.$

The following definition will be important for our construction. For $\Sigma ^0_1$ sets ${\tilde{C}}^B_i,$ $\tilde{A}_5,$ and $\tilde{A}_6$ defined above, we define $\Delta ^0_1$ approximations for them in the usual manner. That is, if f is a computable function such that ${\tilde{C}}^B_i=\bigcup _k (V_{f(B,i,k)}\cap \tilde{X}_H )$ we set ${\tilde{C}}^{m,B}_i= \bigcup _{k \le m} (V_{f(B,i,k)}\cap \tilde{X}_H).$ We likewise define $\tilde{A}^m_5$ and $\tilde{A}^m_6.$

Definition 9.6

For $B\in \mathcal {B},$ $i,m \in \omega ,$ and $x \in \tilde{X}_H,$ we say x is i -determined by depth m (with respect to B) if there is a $g \in \mathbb {Z}^n$ with $\Vert g\Vert < 20 d^B_i$ such that $z \doteq g^{-1} \cdot x$ satisfies the following:

• (1) $N_m(z) \subseteq \tilde{C}_i^{m,B}$

• (2) $\{ B \}\times N_m(z) \times \{ g\} \times \{ i\} \subseteq \tilde{A}_5^m.$

• (3) For every $h \in \mathbb {Z}^n$ with $\Vert h\Vert < 20 d^B_i$ we have $\{ B \} \times N_m(z) \times \{ h\} \times \{ i\} \subseteq \tilde{A}_5^m$ or $\{ B \} \times N_m(z) \times \{ h\} \times \{ i\} \subseteq \tilde{A}_6^m.$

Roughly speaking, this says that, by the mth stage of the computation, it is already determined that the neighborhood of depth m about z must be contained in $\tilde{C}^B_i,$ $x=g \cdot z$ must be ${\tilde{R}}^{i,B}_1$ equivalent to z,  and also for all $\Vert h\Vert <20 d^B_i$ whether or not $h \cdot z$ is ${\tilde{R}}^{i,B}_1$ equivalent to z has been decided. In other words, this neighborhood which is determined by the mth stage of the computation completely determines the points which are ${\tilde{R}}^{i,B}_1$ equivalent to z.

We denote $D(B,x,i,m)\leftrightarrow x$ is i-determined by depth m relative to B. This is a $\Delta ^0_1$ relation on $\mathcal {B}\times \tilde{X}_H\times \omega \times \omega .$

Note that if $x \in X_H,$ then for each i there is a large enough m so that x is i-determined by depth m (relative to B which generates H). On the other hand, if $x \in \tilde{X}_H- X_H,$ then for any given i there may or may not be an m such that x is i-determined by depth m. If x is i-determined by depth m,  we clearly have that x is in the domain of ${\tilde{R}}^{i,B}_1.$ Finally, note that for any $B \in \mathcal {B},$ $x, y \in \tilde{X}_H$ and $i, m \in \omega ,$ if x is i-determined by depth m and $x {\tilde{R}}^{i,B}_1 y,$ then y is also i-determined by depth m. To see this, let g and $z=g^{-1}\cdot x$ witness that x is i-determined by depth m,  and let $z',$ $g_1,$ $g_2$ witness that $x {\tilde{R}}^{i,B}_1 y$ (so $z'=g_1^{-1}\cdot x$). Since $z,z' \in {\tilde{C}}^B_i$ and $z {\tilde{R}}^{i,B}_1 x,$ $z' {\tilde{R}}^{i,B}_1 x,$ it follows that $z=z'.$ We have therefore $z {\tilde{R}}^{i,B}_1 y$ and also from (3) of Definition 9.6 it follows that $\{ B \} \times N_m(z) \times \{ g_2\} \times \{ i\} \subseteq \tilde{A}_5^m$ or $\{ B \} \times N_m(z) \times \{ g_2\} \times \{ i\} \subseteq \tilde{A}_6^m.$ Since $z {\tilde{R}}^{i,B}_1 y$ we must have the first alternative. This verifies (2) of Definition 9.6 for y being i-determined by stage m,  and (1), (3) for y follow from $z=z'.$

We now proceed to the definition of $\pi ^H_k(x).$ The output $\pi ^H_k(x)$ will be effectively computable from x,  k,  and the $\Delta ^0_1$ relation D(B, x, i, m). This will give that $\pi ^H$ is computable.

For $B \in \mathcal {B},$ $x \in \tilde{X}_H,$ and $i, m \ge 1,$ if x is i-determined by depth m,  we let $x^m_i$ be the unique point in $\tilde{C}^B_i$ with $x {\tilde{R}}^{i,B}_1 x^m_i.$ Note that this point, if it exists, does not depend on m. That is, if $x^m_i$ is defined then so is $x^p_i$ for all $p \ge m$ and $x^p_i=x^m_i.$ If x is not i-determined by depth m,  then we leave $x^m_i$ undefined.

Definition 9.7

For $x \in \tilde{X}_H$ and $k \in \omega ,$ let $i_k(x)$ be the largest $i \le k$ such that x is i-determined by depth k,  if such an i exists. If no such i exists set $i_k(x)=0$ (these notions are defined relative to B,  which we suppress in the notation).

We say x is active at stage k if $i_k(x)> i_{k-1}(x),$ and otherwise say x is passive at stage k.

Fix now $B \in \mathcal {B},$ $x \in \tilde{X}_H$ and assume $\pi ^H_1(x), \ldots , \pi ^H_{k-1}(x)$ have been defined. To define $\pi ^H_k(x)$ we consider two cases according to whether x is active or passive at stage k. The idea is that when x is active at stage k we “guess” that x is the “free” part $X_H$ and define $\pi ^H_k(x)$ accordingly. When x is passive at stage k,  we “guess” that x is in the “non-free” part $\tilde{X}_H-X_H$ and define $\pi ^H_k(x)$ accordingly. The key points are that if $x \in \tilde{X}_H-X_H$ then we will eventually guess correctly, while if $x \in X_H$ then we guess correctly infinitely often.

Case I: x is active at stage k.

In this case $i_k(x)> i_{k-1}(x).$ By definition, x is $i_k(x)$-determined by depth k. Let $z_k(x)$ be the unique point of $\tilde{C}_{i_k(x)}$ such that $x \tilde{R}_{i_k(x)} z_k.$ Similarly define $z_{k-1}(x).$ If $z_{k-1}(x)$ is defined (that is, $i_{k-1}(x)>0$), let $a_k(x) \in \mathbb {Z}^n$ be the least a in standard form with

$$\begin{aligned} a \cdot z_{k-1}(x) \upharpoonright \{ g :\Vert g \Vert \le 20 d^B_{i_k}\}= z_k(x) \upharpoonright \{ g :\Vert g \Vert \le 20 d^B_{i_k}\}. \end{aligned}$$

If $z_{k-1}(x)$ is not defined, set $a_k(x)$ to be the least a in standard form such that

$$\begin{aligned} a \cdot x \upharpoonright \{ g :\Vert g \Vert \le 20 d^B_{i_k}\}=z_k(x) \upharpoonright \{ g :\Vert g \Vert \le 20 d^B_{i_k}\}. \end{aligned}$$

An easy density argument shows that $\Vert a_k(x) \Vert \le d^B_{k-1}+d^B_k+2b^B < 2 d^B_k.$ Let

$$\begin{aligned} N_k(x)=N_{20 d^B_{i_k}}(z_k(x))= z_k(x) \upharpoonright \{ g :\Vert g\Vert \le 20 d^B_{i_k} \}. \end{aligned}$$

We let $\pi ^H_k(x)=\#(a_k(x), N_k(x)),$ that is, $\pi ^H_k(x)$ is an integer coding $(a_k(x),N_k(x)).$

Case II x is passive at stage k.

Let $z_k(x)$ be as in the previous case, with the provision that if $i_k(x)=0$ then set $z_k(x)=x.$ Let $u_k(x)$ be the least element u of $\mathbb {Z}^n-H$ such that

$$\begin{aligned} (u\cdot z_k(x))(g)=z_k(x)(g) \end{aligned}$$

for all $g \in \mathbb {Z}^n$ with $\Vert g\Vert ,\Vert u+g\Vert <20 k.$ It is easy to see that there is always such a u using the fact that $\mathbb {Z}^n-H$ is infinite. Let $H_k(x)=\langle H, u_k(x)\rangle$ with normal basis $B_k(x)=t(B,u_k(x)),$ where t is as defined in Lemma 9.3. Let $\pi ^{H}_k(x)$ code $B_k(x)$ and $\pi ^{H_k(x)}_k(z_k(x)),$ where $\pi ^{H_k(x)}_k$ is the stage k output for the map $\pi ^{H_k(x)},$ which is defined by induction since $H_k(x)\supsetneq H.$ Finally, if $k-1$ was an active stage or if the value of $u_{k-1}(x)$ is different from $u_k(x)$ then we code also $\pi ^{H_k(x)}_0(z_k(x)),\ldots , \pi ^{H_k(x)}_{k-1}(z_k(x))$ into $\pi ^{H}_k(x).$

This completes the definition of $\pi ^{H}_k(x)$ and so of the map $\pi ^H.$ The definition above, and our comments along the way, show that the map $(B,k,x) \mapsto \pi ^H_k(x)$ is computable; the only other point to observe is that the recursion occuring in Case II (defining $\pi ^H_k(x)$ in terms of $\pi ^{H_k(x)}_k(x)$) is legitimate as there is no infinite strictly increasing chain of subgroups of $\mathbb {Z}^n.$ It remains to show that $\pi ^H$ is a reduction of $E_H$ to $E_0(\omega ^\omega ),$ and that $\pi ^H$ is one-to-one on $\tilde{X}_H.$

Lemma 9.8

Suppose x,  y are in $\tilde{X}_H$ and $x E_H y.$ If $x \in X_H$ (and so also $y \in X_H$) then for infinitely many k we have that x and y are active at stage k,  and for large enough k,  x is active at stage k iff y is active at stage k. Furthermore, for large enough active k we have $z_k(x)=z_k(y).$ If $x \in \tilde{X}_H-X_H$ (and so also $y \in \tilde{X}_H-X_H$) then for all large enough k we have that x and y are passive at stage k.

Proof

Suppose first that $x \in X_H.$ Then for all i there is an m such that x is i-determined by depth m. For $k \ge m$ we have $i_k(x) \ge i,$ and so the $i_k(x)\rightarrow \infty$ as $k\rightarrow \infty .$ Thus, there are infinitely many k such that x is active at stage k. Since the $\tilde{R}^{i,B}_1$ witness hyperfiniteness on $X_H,$ there is an $i'$ such that for all $i \ge i',$ $x \tilde{R}^{i,B}_1 y.$ For such i and any m it follows that x is i-determined by depth m iff y is i-determined by depth m. From this and the fact that the $i_k(x)\rightarrow \infty$ it follows that for all large enough k,  $i_k(x)=i_k(y).$ Hence, for large enough k we have that x is active at stage k iff y is active at stage k. For these large k (i.e., with $i_k(x) \ge i'$) we also have that $z_k(x)=z_k(y)$ since $x \tilde{R}^{i_k,B}_1 y.$

Suppose now that x,  $y \in \tilde{X}_H-X_H.$ Thus there is an $u \in \mathbb {Z}^n-H$ such that $u \cdot x=x$ (and also $u \cdot y =y$). Since $u \notin H,$ there is an $u' \in u+H$ with $u'$ in standard form (with respect to B), and $u' \ne \vec {0}.$ From the marker construction of Lemma 7.11 it follows that for any i with $d^B_i > \Vert u'\Vert$ that $\tilde{C}^B_i \cap [x]_E=\emptyset .$ In particular, for any such i,  x and y will never be i-determined by depth m (for any m). Say this happens for all $i \ge i'.$ Let $k_0$ be large enough so that for any $i <i',$ if x or y is i-determined by depth m,  for some m,  then x or y is i-determined by depth $k_0.$ Thus, for all $k \ge k_0$ the values of $i_k(x)$ and $i_k(y)$ are stabilized, that is, x and y are passive at stage k. $\square$

Lemma 9.9

$\pi ^H$ is a reduction from $E_H$ to $E_0(\omega ^\omega ).$

Proof

Suppose first that x,  $y \in X_H$ and x E y. From Lemma 9.8 there are infinitely many k such that x and y are both active at stage k,  and $z_k(x)=z_k(y).$ In Case I, the output consists of $a_k$ together with $N_k.$ Note that $N_k$ depends only on $z_k.$ Thus, $N_k(x)=N_k(y).$ Since $a_k$ only depends on $z_{k-1}$ and $z_k,$ we have $a_k(x)=a_k(y).$ Thus, $\pi ^H_k(x)=\pi ^H_k(y)$ for large enough active k. In case II, the values of $H_k=\langle H, u_k\rangle$ and $\pi ^{H_k}_k(z_k)$ being output also depend only on $z_k,$ and so will be the same for x and y.

Next suppose that x,  $y \in \tilde{X}_H-X_H$ and $x E_H y.$ From Lemma 9.8, for large enough k both x and y will be passive at stage k. So we are in Case II in the definition of $\pi ^H_k$ for both x and y. It follows that for large enough k the values of $u_k$ and thus $H_k$ will be the same for both x and y,  and both will be eventually constant. By induction $\pi ^{H_k(x)}_k(x)=\pi ^{H_k(y)}_k (y)$ for large enough k. So, $\pi ^H_k(x)=\pi ^H_k(y)$ for large enough k.

For the converse, suppose next that x,  $y \in \tilde{X}_H$ and $\pi ^H(x) E_0 \pi ^H(y).$ First note that either x,  y are both in $X_H$ or both in $\tilde{X}_H-X_H.$ This follows from Lemma 9.8 and the fact that we can distinguish the outputs in the active versus the passive cases. So, assume first that x,  $y \in X_H.$ By considering the output values $\pi ^H_k(x)$ for the infinitely many k where x is active, we see that the $E_0$ class of $\pi ^H(x)$ determines a tail of a sequence $(a_k(x), N_k(x))$ as in Case I. Since $\Vert a_k(x)\Vert < 2 d_{i_k},$ and the definition of $N_k(x)$ involves all g with $\Vert g\Vert < 20 d_{i_k},$ it follows that from the $E_0$ class of $\pi ^H(x)$ we can reconstruct the $E_H$ class of x. Suppose next that x,  $y \in \tilde{X}_H-X_H.$ From Lemma 9.8 both $z(x)=\lim _k z_k(x)$ and $z(y)=\lim _k z_k(y)$ exist. Of course, $z(x) E_H x$ and $z(y) E_H y.$ The outputs $\pi ^H_k(x)$ are eventually of the form $(B'(x), \pi ^{H'(x)}_k(z(x))),$ where $H'(x)=\langle H, u(x) \rangle ,$ u(x) is the least element u of $\mathbb {Z}^n-H$ such that $u \cdot x=x,$ and $B'(x)$ is the normal basis for $H'(x).$ Likewise for $\pi ^H_k(y).$ Since $\pi ^H(x) E_0 \pi ^H(y),$ we have $B'(x)=B'(y)$ and therefore $u(x)=u(y).$ Let $B'=B(x)=B(y)$ and $H'=H'(x)=H'(y)$ be the common values. It follows that $\pi ^{H'}(z(x)) E_0 \pi ^{H'}(z(y)).$ If $\dim (H')<n,$ then by induction it follows that $z(x) E_{H'} z(y).$ Since $E_{H'}\subseteq E_H,$ we have $xE_Hy.$ If $\dim (H')=n,$ then the $E_0$ class of $\pi ^{H'}(x)$ determines the $E_0$ class of $\tau \circ \sigma ^{B'}(x),$ where $\tau ,$ $h^{B'}$ are as defined in the $p=n$ case. From the properties of $\tau ,$ this determines $\sigma ^{B'}(x),$ which is the lexicographically least element of the finitely many elements of $[x]_E.$ So, $\pi ^H(y)$ determines also this same element, and it follows that $[x]_E=[y]_E.$ $\square$

Lemma 9.10

$\pi ^H$ is one-to-one from $\tilde{X}_H$ to $\omega ^\omega .$

Proof

Suppose that $x,y\in \tilde{X}_H$ and $\pi ^H(x)=\pi ^H(y).$ From Lemma 9.9 we know that $x E_H y.$ Suppose first that x,  $y \in X_H.$ Consider the sequence $k_0<k_1<\cdots$ of k which are active for x (and hence also y,  since this determined from the output $\pi ^H(x)=\pi ^H(y)$). For each $k_q,$ the output $\pi ^H_{k_q}(x)$ encodes the unique $a_k(x)$ in standard form (relative to H) such that $a_k(x) \cdot z_{k_{q-1}}(x)=z_{k_q}(x).$ Thus, the sequence of $z_{k_q}(x)$ is determined from the output $\pi ^H(x).$ From this it follows as in Lemma 9.9 that x is also determined from $\pi ^H(x),$ and so $x=y.$

Suppose next that x,  $y \in \tilde{X}_H-X_H.$ Let z(x),  z(y) again denote the limiting values of the $z_k(x)$ and $z_k(y)$ as in Lemma 9.9. The value of $z_k(x)$ only changes for active k,  and the output $\pi ^H_k(x)$ records the change, that is, an $a_k(x)$ such that $a_k(x) \cdot z_{k-1}(x)=z_k(x).$ Also, the output $\pi ^H(x)$ determines an $a' \in \mathbb {Z}^n$ such that $a' \cdot x= z_{k_0}(x),$ where $k_0$ is least so that $i_{k_0}>0.$ So, $\pi ^H(x)$ determines an element g such that $g \cdot x=z(x).$ Since $\pi ^H(x)=\pi ^H(y),$ we also have $g \cdot y= z(y).$ Let $u \in \mathbb {Z}^n$ be the least element of $\mathbb {Z}^n-H$ such that $u \cdot x=x.$ Since $xE_Hy$ we have $u \cdot y=y$ as well. Let $H'=\langle H,u\rangle .$ Let $\bar{k}$ be the least stage such that for all $k \ge \bar{k},$ x is k is passive at stage k and $a_k=u.$ Then $\pi ^H_k(x)$ encodes not only $\pi ^{H'}_{\bar{k}}(z(x))$ but also $\pi ^{H'}_0(z(x)),\ldots , \pi ^{H'}_{\bar{k}-1}(z(x))$ as well. Thus, the output $\pi ^H(x)$ determines completely $\pi ^{H'}(z(x)).$ If $\dim (H')<n,$ then by induction z(x) is determined from $\pi ^{H'}(z(x)),$ and thus $x= g^{-1} \cdot z(x)$ is determined as well. If $\dim (H')=n,$ then we use the earlier observation that $\pi ^{H'}$ is one-to-one in this base case of our induction. $\square$

We have thus completed the proof of Theorem 9.1.

10 Open problems and further remarks

In this final section we summarize the problems left open by this article for future research. First of all the main result of this paper is a small step toward the solutions of the following hierarchy of fascinating open questions in the field.

Problem 10.1

(The Increasing Union Problem) Let $E=\bigcup _n E_n$ where each $E_n$ is a hyperfinite equivalence relation and $E_n\subseteq E_{n+1}.$ Is E hyperfinite?

Problem 10.2

(Weiss) Is every amenable equivalence relation hyperfinite? In particular, is every orbit equivalence relation induced by an action of a countable amenable group hyperfinite?

The following is a less ambitious problem along the line. However, a positive solution would already surpass all known results to date.

Problem 10.3

Is every orbit equivalence relation of a countable nilpotent group action hyperfinite?

We do not know if the method used in this article will continue to play a role in these problems. Nevertheless, some of our results seem to be applicable in a more general context. For instance the basic marker lemmas are all adaptable to the case of general countable groups.

Another problem on which we made some initial progress in this article but is still open is the computation of the Borel chromatic numbers.

Problem 10.4

What is the Borel chromatic number of

$$\begin{aligned} X_H=\{ x\in 2^{{\mathbb {Z}}^{n}}:G_x =H\}, \end{aligned}$$

where $G_x=\{ g \in \mathbb {Z}^{n} :g \cdot x=x\},$ for H a subgroup of ${\mathbb {Z}}^n,$ $n\ge 2$?

This question has not been completely answered even for the free part (corresponding to the trivial G). Our Theorem 4.2 showed that 4 colors suffice but it is not clear if it is optimal. Recycling an old piece of terminology we pose the following question.

Problem 10.5

(The Borel Four-Color Problem) Is there a Borel 3-coloring of $F({\mathbb {Z}}^n)$ for $n\ge 2$?

We also conjecture that the answer is uniform for all $n\ge 2.$ Closely related to this problem is the intuitive question of how regular we can make the Borel marker regions. We already formulated a precise question as Question 4.1. Here we pose a general vague question.

Problem 10.6

Do there exist Borel marker regions for $F({\mathbb {Z}}^n)$ which are almost cubes and are almost lined up?

Finally we reiterate that in contrast to our results in the preceding section we do not know if $E_\omega$ (the shift equivalence relation on $2^{\mathbb {Z}^{<\omega }}$) continuously embeds into $E_0.$ In view of the proof of Theorem 8.5 this is equivalent to the following problem.

Problem 10.7

Let G be a countable abelian group acting continuously on a 0-dimensional Polish space X. Is $E^X_H$ continuously reducible to $E_0$?