1 Introduction
This paper is a contribution to the study of countable Borel equivalence relations. We consider Borel actions of countable groups on Polish spaces and study the orbit equivalence relations which they generate. Properties such as hyperfiniteness, treeability, chromatic numbers, matchings, etc. have received much interest both in ergodic theory and descriptive set theory. Typically, investigations into these properties begin with the construction of Borel complete sections possessing special properties. In this paper we introduce new methods based on forcing techniques for studying Borel complete sections. We use forcing constructions to prove the existence of certain regularity phenomena in complete sections. This of course prevents the existence of complete sections with certain features. These results generally fail if one is allowed to restrict to a comeager or co-null set, and thus go beyond what is provable using those ideals. We note that recent work of Thomas [Reference Thomas17] and Marks [Reference Marks12] explore the use of Martin’s ultrafilter and its generalizations as a largeness notion (see also [Reference Marks11] for other recent uses of determinacy in the study of Borel equivalence relations).
Since the results of this paper were obtained, Seward and Tucker-Drob showed a universality result for free actions of countable groups (Theorem 2.1). The referee observed that this result could be used to give alternate proofs of our results. In some cases this is just a cosmetic change to the forcing arguments, but in other cases a quite different action of the group must be considered and the alternate proof using the Seward and Tucker-Drob result seems like a genuinely different argument. For this reason we have, with the referee’s permission, often given this alternate argument in addition to, or instead of, the forcing argument.
Recall that a set S is a complete section for an equivalence relation E if S meets every E-class. A classic result on complete sections is the Slaman–Steel lemma which states that every aperiodic countable Borel equivalence relation E admits a decreasing sequence of Borel complete sections
$S_{n}$
with empty intersection (this result is stated explicitly as Lemma 6.7 of [Reference Kechris and Miller9], where they attribute it to Slaman-Steel; the proof is implicit in Lemma 1 of [Reference Slaman and Steel16]). This result played an important role in their proof that every equivalence relation generated by a Borel action of
$\mathbb {Z}$
is hyperfinite. A long-standing open problem asks if every equivalence relation generated by a Borel action of a countable amenable group must be hyperfinite, and progress on this problem is in some ways connected to strengthening the Slaman–Steel lemma. In particular, constructing sequences of complete sections (“marker sets”) with certain geometric properties is central to the proofs of [Reference Gao and Jackson4, Reference Schneider and Seward14] that every equivalence relation generated by the Borel action of an abelian, or even locally nilpotent, group is hyperfinite. In particular, the constructions in [Reference Gao and Jackson4, Reference Schneider and Seward14] build complete sections
$B_{n}$
(facial boundaries) which are sequentially orthogonal, or repel one another, so that the sequence
$S_{n} = \bigcup _{i> n} B_{i}$
is decreasing and vanishes. Thus, the question of what kinds of marker sets various equivalence relations can admit is an important one.
Our first theorem unveils a curious property which limits how quickly a sequence of complete sections can vanish. In fact, this theorem says that if a sequence of complete sections vanishes, then it must do so arbitrarily slowly.
Theorem 1.1. Let
$\Gamma $
be a countable group, X a compact Polish space, and
$\Gamma \curvearrowright X$
a continuous action giving rise to the orbit equivalence relation E. Let
$(S_{n})_{n \in \mathbb {N}}$
be a sequence of Borel complete sections of E. If
$(A_{n})_{n \in \mathbb {N}}$
is any sequence of finite subsets of
$\Gamma $
such that every finite subset of
$\Gamma $
is contained in some
$A_{n}$
, then there is an
$x \in X$
such that for infinitely many n we have
$A_{n}\cdot x \cap S_{n} \neq \varnothing $
.
We remark that the above result is easily seen to be inherited from subspaces, so one can instead simply require that X contain a compact invariant subset. In particular, by results in [Reference Gao, Jackson and Seward7, Reference Gao, Jackson and Seward8] the above result holds when
$X = F(2^{\Gamma })$
, where
$F(2^{\Gamma })$
is the set of points in
$2^{\Gamma }$
having trivial stabilizer.
This theorem was motivated by a similar result for the case when each
$S_{n}$
is clopen, the proof of which is a straightforward topological argument without forcing. We will define a forcing notion, called orbit forcing, that will allow us to give a proof of Theorem 1.1 that is essentially a generalization of the topological proof.
We remark that, after learning of the above theorem, Conley and Marks obtained another interesting result on the behavior of distances to sequences of complete sections [Reference Conley and Marks1].
The orbit forcing can be used to obtain more results, the following being an example.
Theorem 1.2. If
$B \subseteq F(2^{\Gamma })$
is a Borel complete section then B meets some orbit recurrently, i.e., there is
$x\in F(2^{\Gamma })$
and finite
$T\subseteq \Gamma $
such that for any
$y\in [x]$
,
$T\cdot y\cap B\neq \varnothing $
.
Again, if B is assumed to be clopen then the result follows from the fact that minimal elements form a dense set in
$F(2^{\Gamma })$
[Reference Gao, Jackson and Seward8, Theorem 5.3.6]. We find that the most direct way to obtain this “Borel result” is to mimic the topological proof but use forcing.
The above result can be strengthened in various ways. For example, in the case of
$\Gamma = \mathbb {Z}^{d}$
we can require that the recurrences occur at odd distances (distance here refers to the taxi-cab metric induced by the
$\ell _{1}$
norm
$\| (g_{1},\dots ,g_{d})\|=|g_{1}|+\cdots +|g_{d}|$
).
Theorem 1.3. Let
$d\geq 1$
. If
$B \subseteq F(2^{\mathbb {Z}^{d}})$
is a Borel complete section then B meets some orbit recurrently with odd distances, i.e., there is
$x\in F(2^{\mathbb {Z}^{d}})$
and finite
$T\subseteq \{ g \in \mathbb {Z}^{d} \colon \| g\| \text { is odd }\}$
such that for any
$y\in [x]$
,
$T\cdot y\cap B\neq \varnothing $
.
It is worth noting that Theorem 1.3, and in fact all of the forcing results in this paper, can be proved using the orbit forcing method. However, we believe that forcing arguments in general may provide a new path for studying countable Borel equivalence relations. Thus, in order to demonstrate the flexibility of forcing arguments in this setting, we define and use other forcing notions beyond the orbit forcing. We choose to prove the above theorem by using a notion of an odd minimal
$2$
-coloring forcing.
Another forcing notion we introduce is that of a grid periodicity forcing. Using this forcing, we obtain the following result which reveals a surprising amount of regularity in complete sections.
Theorem 1.4. Let
$d\geq 1$
. If
$B \subseteq F(2^{\mathbb {Z}^{d}})$
is a Borel complete section then there is an
$x\in F(2^{\mathbb {Z}^{d}})$
and a lattice
$L\subseteq \mathbb {Z}^{d}$
such that
$L\cdot x\subseteq B$
.
If
$B \subseteq F(2^{\mathbb {Z}^{d}})$
is a Borel set but not a complete section, then there is x with
$\mathbb {Z}^{d} \cdot x \cap B = \varnothing $
. Thus we have the following immediate corollary.
Corollary 1.5. Let
$d\geq 1$
. If
$B \subseteq F(2^{\mathbb {Z}^{d}})$
is Borel then there is an
$x\in F(2^{\mathbb {Z}^{d}})$
and a lattice
$L\subseteq \mathbb {Z}^{d}$
such that either
$L\cdot x\subseteq B$
or
$L\cdot x\cap B=\varnothing $
.
Marks [Reference Marks11] has proved a similar result for free groups using Borel determinacy. Also, after discussing Theorem 1.4 with him, he generalized Theorem 1.4 to all countable residually finite groups [Reference Marks13]. His proof also uses forcing, though it uses none of the forcing notions we introduce here. This again suggests that the flexibility in choosing a forcing notion may be important for future applications to Borel equivalence relations.
The above results can be viewed as ruling out certain Borel complete sections (marker sets) with strong regularity properties. Alternatively, they can be viewed as saying that Borel marker sets must, on some equivalence classes, exhibit regular structure. In general, regular marker sets and structures are desirable in hyperfiniteness proofs or Borel combinatorial results (e.g., in the study of Borel chromatic numbers). The negative results stated below unveil a fine line between what is possible and what is not possible.
In [Reference Gao and Jackson4], the first two authors proved that all equivalence relations generated by Borel actions of countable abelian groups are hyperfinite (this has since been extended to locally nilpotent groups [Reference Schneider and Seward14]). For the finite equivalence relations they construct, the shapes of the classes at a sufficiently large scale look like rectangles. However, at finer and finer scales the shapes appear to be increasingly fractal-like. We use forcing to prove a claim made in [Reference Gao and Jackson4] stating that this fractal-like behavior is necessary. This fact indicates that hyperfiniteness results of this type have a necessary degree of complexity. The theorem below is stated for rectangles but the proof works for any reasonable polygon.
Theorem 1.6. There does not exist a sequence
$\mathcal {R}_{n}$
of Borel finite subequivalence relations on
$F(2^{\mathbb {Z}^{2}})$
satisfying all the following:
-
(1) (regular shape) For each n, each marker region R of
$\mathcal {R}_{n}$
is a rectangle. -
(2) (bounded size) For each n, there is an upper bound
$w(n)$
on the size of the edge lengths of the marker regions R in
$\mathcal {R}_{n}$
. -
(3) (increasing size) Letting
$v(n)$
denote the smallest edge length of a marker region R of
$\mathcal {R}_{n}$
, we have
$\lim _{n} v(n)=+\infty $
. -
(4) (vanishing boundary) For each
$x \in F(2^{\mathbb {Z}^{2}})$
we have that
$\lim _{n} \rho (x, \partial \mathcal {R}_{n})=+\infty $
.
Our last two negative results touch upon the theory of Borel chromatic numbers. It is not difficult to show that
$F(2^{\mathbb {Z}^{2}})$
has Borel chromatic number strictly greater than
$2$
. By using the odd minimal
$2$
-coloring forcing, we show that in fact there cannot exist any Borel chromatic coloring of
$F(2^{\mathbb {Z}^{2}})$
which uses two colors on arbitrarily large regions.
Theorem 1.7. There does not exist a Borel chromatic coloring
$f \colon F(2^{\mathbb {Z}^{2}}) \to \{0,1,\dots ,k\}$
such that for all
$x \in F(2^{\mathbb {Z}^{2}})$
there are arbitrarily large rectangles R in
$\mathbb {Z}^{2}$
such that
$f(R\cdot x)$
consists of only two elements of
$\{0,1,\dots , k\}$
.
A useful structure for the study of Borel graphs and chromatic numbers is the notion of toast or “barrier” as named in [Reference Conley and Miller2]. For example, in [Reference Conley and Miller2] Conley and Miller used barriers to prove that for a large class of Borel graphs G, the Baire-measurable and
$\mu $
-measurable chromatic numbers of G are at most twice the standard chromatic number of G minus one. In a similar fashion, the existence of a toast structure on
$F(2^{\mathbb {Z}^{2}})$
would easily imply the existence of a Borel chromatic
$3$
-coloring. As a consequence of Theorem 1.1, we deduce that there is no toast structure which is layered.
Corollary 1.8. There is no Borel layered toast on
$F(2^{\mathbb {Z}^{d}})$
, i.e., there is no sequence of finite subequivalence relations
$\{T_{n}\}$
of
$E_{\mathbb {Z}^{d}}$
on some subsets
$\operatorname{dom}(T_{n})\subseteq F(2^{\mathbb {Z}^{d}})$
such that
-
(0)
$\bigcup _{n} \operatorname{dom}(T_{n})= F(2^{\mathbb {Z}^{d}})$
. -
(1) For each
$T_{n}$
-equivalence class C, and each
$T_{m}$
-equivalence class
$C^{\prime }$
where
$m>n$
, if
$C \cap C^{\prime } \neq \varnothing $
then
$C \subseteq C^{\prime }$
. -
(2) For each
$T_{n}$
-equivalence class C there is a
$T_{n+1}$
-equivalence class
$C^{\prime }$
such that
$C \subseteq C^{\prime }\setminus \partial C^{\prime }$
.
We mention that unlayered toast (defined in Section 4) does exist and thus
$F(2^{\mathbb {Z}^{2}})$
does have Borel chromatic number
$3$
. This result will appear in [Reference Gao, Jackson, Krohne and Seward6].
2 Preliminaries
In this section we present some preliminaries that will be used throughout the rest of the paper. Other undefined notions can be found in [Reference Gao3, Reference Kechris10].
2.1 Countable Borel equivalence relations and group actions
In this paper we will be concerned mainly with countable Borel equivalence relations. Let X be a Polish space and E an equivalence relation on X. E is Borel if it is a Borel subset of
$X\times X$
. E is countable if each E-equivalence class is countable. For
$x\in X$
, we let
$[x]_{E}$
denote the E-equivalence class of x, i.e.,
$$ \begin{align*} [x]_{E}=\{ y\in X \colon x \mathbin{E} y\}. \end{align*} $$
When there is no ambiguity we will omit the subscript and only write
$[x]$
.
Countable Borel equivalence relations typically arise from orbit equivalence relations of countable group actions. If
$\Gamma $
is a countable discrete group and
$\Gamma \curvearrowright X$
is a Borel action of
$\Gamma $
on a Polish space X, then the orbit equivalence relation
$E^{X}_{\Gamma }$
defined by
$$ \begin{align*} E^{X}_{\Gamma}=\{(x, y)\in X\times X:\exists g\in \Gamma\, (g\cdot x=y)\} \end{align*} $$
is obviously a countable Borel equivalence relation. Conversely, by a well-known theorem of Feldman–Moore, every countable Borel equivalence relation is of the form
$E^{X}_{\Gamma }$
for some Borel action
$\Gamma \curvearrowright X$
of a countable group
$\Gamma $
. For this reason, whenever we speak of a countable Borel equivalence relation E we assume that there has been fixed a Borel action of a countable group
$\Gamma \curvearrowright X$
so that
$E=E^{X}_{\Gamma }$
. For any
$x\in X$
, note that
$[x]=\Gamma \cdot x$
; we also refer to
$[x]$
as the orbit of x.
If
$\Gamma \curvearrowright X$
and
$\Gamma \curvearrowright Y$
are two actions of
$\Gamma $
on Polish spaces X and Y, respectively, a
$\Gamma $
-map, or an equivariant map, from X to Y is a map
$\varphi \colon X\to Y$
such that for all
$g\in \Gamma $
and
$x\in X$
,
$$ \begin{align*} \varphi(g\cdot x)=g\cdot \varphi(x). \end{align*} $$
If in addition
$\varphi $
is injective, it will be called a
$\Gamma $
-embedding or an equivariant embedding.
For a countable group
$\Gamma $
, the Bernoulli(left)shift of
$\Gamma $
is the action
$\Gamma \curvearrowright 2^{\Gamma }$
defined by
$$ \begin{align*} (g\cdot x)(h)=x(g^{-1}h), \end{align*} $$
for
$x\in 2^{\Gamma }$
and
$g, h\in \Gamma $
. The shift action is continuous and enjoys certain universality properties. Consider the action
$\Gamma \curvearrowright 2^{\Gamma \times \omega }$
is defined by
$$ \begin{align*} (g\cdot x)(h, n)=x(g^{-1}h, n), \end{align*} $$
for
$x\in 2^{\Gamma \times \omega }$
,
$g, h\in \Gamma $
, and
$n\in \omega $
. A theorem of Becker–Kechris states that this latter action is a universal Borel
$\Gamma $
-action. That is, for any Borel action
$\Gamma \curvearrowright X$
of
$\Gamma $
on a Polish space X, there is a Borel
$\Gamma $
-embedding from X into
$2^{\Gamma \times \omega }$
. In view of this, any
$\Gamma $
-action on a Polish space X is Borel isomorphic to the action of
$\Gamma $
restricted to an invariant Borel subset of
$2^{\Gamma \times \omega }$
. In [Reference Seward and Tucker-Drob15] Seward and Tucker-Drob showed the following (the free part
$F(2^{\Gamma })$
of the shift action is defined below).
Theorem 2.1 [Reference Seward and Tucker-Drob15, Theorem 1.1].
Suppose
$\Gamma $
is a countable group and
$\Gamma \curvearrowright X$
a free Borel action on a Polish space X. Then there is an equivariant Borel map
$\varphi \colon X \to F(2^{\Gamma })$
from the action
$\Gamma \curvearrowright X$
to the action of
$\Gamma $
on
$F(2^{\Gamma })$
.
A particularly important action for this paper is the shift action of
$\Gamma =\mathbb {Z}^{d}$
on
$X=2^{\mathbb {Z}^{d}}$
. In this case we write
$E_{\mathbb {Z}^{d}}$
for the orbit equivalence relation
$E^{X}_{\Gamma }$
. We will frequently restrict the action to the free part
$F(2^{\mathbb {Z}^{d}})$
, and we will also write
$F(2^{\mathbb {Z}^{d}})$
for the restriction of the orbit equivalence relation to the free part (which is also a Polish space).
2.2 Aperiodicity, hyperaperiodicity, and minimality
Let
$\Gamma $
be a countable group, X a Polish space, and
$\Gamma \curvearrowright X$
a Borel action. An element
$x\in X$
is aperiodic if for any nonidentity
$g\in \Gamma $
,
$g\cdot x\neq x$
. The set of all aperiodic elements of X is called the free part of X, and is denoted as
$F(X)$
. When
$F(X)=X$
we say that the action is free. The free part
$F(2^{\Gamma })$
of the shift action is a Polish space.
An element
$x\in X$
is hyperaperiodic if the closure of its orbit is contained in the free part of X, i.e.,
$\overline {[x]}\subseteq F(X)$
. We have the following characterization.
Lemma 2.2 [Reference Gao, Jackson and Seward7].
A point
$x \in 2^{\Gamma }$
is hyperaperiodic if and only if for all
$e_{\Gamma } \neq s \in \Gamma $
, there is a finite
$T\subseteq \Gamma $
such that
$$ \begin{align*}\forall g \in \Gamma \ \exists t \in T \quad x(g s t) \neq x(g t).\end{align*} $$
Hyperaperiodic points are also called
$2$
-colorings. Unfortunately, in this paper we will also consider graph colorings in the usual sense that adjacent vertices have different colors. If k many colors are used, we will refer to such colorings as graph k-colorings or chromatic k-colorings.
The action
$\Gamma \curvearrowright X$
is minimal if every orbit is dense, i.e.,
$\overline {[x]}=X$
for every
$x\in X$
. In general, we call an element
$x\in X$
minimal if the induced action of
$\Gamma $
on
$\overline {[x]}$
is minimal. When X is a compact Polish space and the action is continuous, an application of Zorn’s lemma shows that there always exist minimal elements. In fact, when X is compact Polish (or even compact with a well-ordered base) we can prove this in
$\mathsf {ZF}$
(i.e., we don’t need any form of
$\mathsf {AC}$
to prove this).
Fact 2.3 (
$\mathsf {ZF}$
).
Let X be a compact
$T_{2}$
topological space with a well-ordered base
$\{ U_{\eta }\}_{\eta <\lambda }$
. Let
$\Gamma $
be a group and
$(g,x)\mapsto g \cdot x \in X$
a continuous action of
$\Gamma $
on X. Then there is an
$x \in X$
which is minimal.
If the action of
$\Gamma $
is only Borel, then the same conclusion holds if X is compact and Polish [Reference Gao, Jackson and Seward8, Lemma 2.4.4].
Proof Let
$K_{0}=X$
. We define by transfinite recursion on the ordinals a sequence of non-empty compact sets
$K_{\alpha }\subseteq X$
which are decreasing, in that if
$\alpha <\beta $
then
$K_{\beta } \subseteq K_{\alpha }$
, and also invariant, in that if
$x \in K_{\alpha }$
then
$[x]=\{ g\cdot x \colon g \in \Gamma \} \subseteq K_{\alpha }$
. For
$\alpha $
limit we set
$K_{\alpha } =\bigcap _{\beta <\alpha } K_{\beta }$
. For the successor case, suppose
$K_{\alpha }$
is defined, and is non-empty, compact, and invariant. If
$K_{\alpha }$
is minimal, we are done. Otherwise there is a least
$\eta <\lambda $
such that
$U_{\eta } \cap K_{\alpha }\neq \emptyset $
and
$K_{\alpha }- \text {sat}(U_{\eta })\neq \emptyset $
(here
$\text {sat}(U)=\{ y \colon \exists x \in U \exists g \in \Gamma \ y=g\cdot x\}$
is the saturation of U under the equivalence relation on X generated by
$\Gamma $
). This exists since we are assuming there is a non-empty, compact (hence closed), invariant
$K\subsetneq K_{\alpha }$
. Let
$K_{\alpha +1}=K_{\alpha }- \text {sat}(U_{\eta })$
. Since the action of
$\Gamma $
is continuous,
$\text {sat}(U_{\eta })$
is open, so
$K_{\alpha +1}$
is non-empty and compact. It is also invariant (the difference of two invariant sets), and properly contained in
$K_{\alpha }$
. As the sets
$K_{\alpha }$
are decreasing, the sequence must terminate in some
$K_{\alpha }$
which is minimal.
Corollary 2.4 (
$\mathsf {ZF}$
).
A continuous action of a Polish group
$\Gamma $
on a compact Polish space X has a minimal element.
In the case of
$2^{\Gamma }$
, minimality is captured by the following combinatorial condition, which is well known and follows from a simple compactness argument. We will use the following fact repeatedly.
Lemma 2.5 (cf., e.g., [Reference Gao, Jackson and Seward8]).
A point
$x \in 2^{\Gamma }$
is minimal if and only if for every finite
$A \subseteq \Gamma $
there is a finite
$T \subseteq \Gamma $
such that
$$ \begin{align*}\forall g \in \Gamma \ \exists t \in T \ \forall a \in A \quad x(g t a) = x(a).\end{align*} $$
It was proved in [Reference Gao, Jackson and Seward8] that minimal
$2$
-colorings exist on every countable group
$\Gamma $
.
2.3 Borel complete sections, Borel graphs, and geometry on orbits
For a Polish space X with a countable Borel equivalence relation E, a complete section S is a subset of X that meets every orbit of X, i.e., for any
$x\in X$
,
$S\cap [x]\neq \varnothing $
. Complete sections are frequently built to posses properties of geometric significance and for this reason are informally called marker sets.
A countable equivalence relation on a standard Borel space X is called hyperfinite if there is an increasing sequence of Borel equivalence relations
$$ \begin{align*} R_{0}\subseteq R_{1}\subseteq R_{2}\subseteq \cdots \end{align*} $$
on X with all
$R_{n}$
-equivalence classes finite, such that
$E=\bigcup _{n} R_{n}$
.
We mostly focus our attention on complete sections of the free part
$F(2^{\Gamma })$
of Bernoulli shifts
$\Gamma \curvearrowright 2^{\Gamma }$
. The following useful consequence of Theorem 2.1 allows us to sometimes draw useful conclusions by considering other
$\Gamma $
-actions.
Fact 2.6. Suppose P is a collection of sequences of subsets of
$\Gamma $
. Then the following are equivalent:
-
(1) For every sequence
$B_{n}$
of Borel complete sections of the shift action of
$\Gamma $
on
$F(2^{\Gamma })$
, there exists an
$x \in F(2^{\Gamma })$
so that the sequence
$n \in \mathbb {N} \mapsto \{\gamma \in \Gamma : \gamma \cdot x \in B_{n}\}$
is in P. -
(2) There exists a free Borel action
$\Gamma \curvearrowright X$
of
$\Gamma $
on a Polish space X such that for every sequence
$B_{n}^{\prime }$
of Borel complete sections of this action, there exists an
$x \in X$
so that the sequence
$n \in \mathbb {N} \mapsto \{\gamma \in \Gamma : \gamma \cdot x \in B_{n}^{\prime }\}$
is in P.
Proof We show (2) implies (1). By Theorem 2.1 there is a
$\Gamma $
-equivariant Borel map
$\phi \colon X \rightarrow F(2^{\Gamma })$
. If
$(B_{n})_{n \in \mathbb {N}}$
is a sequence of Borel complete sections for
$F(2^{\Gamma })$
, then
$B_{n}^{\prime } = \phi ^{-1}(B_{n})$
is a sequence of Borel complete sections for X. By (2), there is
$x \in X$
so that the sequence
$n \mapsto \{\gamma \in \Gamma \colon \gamma \cdot x \in B_{n}^{\prime }\}$
is in P. Hence,
$\phi (x) \in F(2^{\Gamma })$
and the sequence
$n \mapsto \{\gamma \in \Gamma \colon \gamma \cdot \phi (x) \in B_{n}\} = \{\gamma \in \Gamma \colon \gamma \cdot x \in B_{n}^{\prime }\}$
is in P.
The following notions and terminology are tools to study the geometric structures. Fix
$d\geq 1$
. For an element
$g=(g_{1},\dots , g_{d})\in {\mathbb Z}^{d}$
, let
$$ \begin{align*} \|g\|=\sum_{i=1}^{d} |g_{i}|. \end{align*} $$
The metric induced by this norm is often called the taxi-cab metric. If
$x, y\in F(2^{{\mathbb Z}^{d}})$
are in the same orbit, then there is a unique
$g_{x,y}\in {\mathbb Z}^{d}$
with
$g_{x,y}\cdot x=y$
, and we define
$\rho (x,y)=\|g_{x,y}\|$
. If
$y\not \in [x]$
, we just let
$\rho (x,y)=+\infty $
. This
$\rho $
is thus a distance function that is a metric on each orbit. For
$A\subseteq F(2^{{\mathbb Z}^{d}})$
we also define
$\rho (x,A)=\min \{\rho (x,y): y\in A\}$
. If A is a complete section, then
$\rho (x,A)<+\infty $
for any x.
In general, for any finitely generated group
$\Gamma $
with a finite symmetric generating set S (meaning
$\gamma ^{-1}\in S$
for every
$\gamma \in S$
), a number of standard objects can be associated with the space
$2^{\Gamma }$
. First, there is the Cayley graph
$C_{S}(\Gamma )=(\Gamma , D)$
with
$\Gamma $
as the vertex set and with the edge relation D defined by
$$ \begin{align*} (g,h)\in D\iff \exists \gamma\in S\ ( g=\gamma h). \end{align*} $$
The Cayley graph induces a Borel graph
$C_{S}(2^{\Gamma })=(2^{\Gamma }, \tilde {D})$
on
$2^{\Gamma }$
, where the edge relation
$\tilde {D}$
is defined as
$$ \begin{align*} (x,y)\in \tilde{D}\iff \exists \gamma\in S\ (x=\gamma\cdot y). \end{align*} $$
The geodesics in
$C_{S}(2^{\Gamma })$
give a distance function
$\rho _{\Gamma }$
, i.e.,
$\rho _{\Gamma }(x,y)$
is the length of the shortest path from x to y in
$C_{S}(2^{\Gamma })$
. Note that the distance function
$\rho $
defined above for
$2^{\mathbb {Z}^{d}}$
is an example of the more general
$\rho _{\Gamma }$
, with S being the set of standard generators for
$2^{\mathbb {Z}^{d}}$
.
If
$A\subseteq 2^{\Gamma }$
, the boundary of A, denoted
$\partial A$
, is the set
$$ \begin{align*} \partial A=\{ x\in A: \exists \gamma\in S\ \gamma\cdot x\not\in A\}. \end{align*} $$
3 Orbit forcing
We start with a very general forcing construction in which one generically builds an element in a Polish space with a countable Borel equivalence relation.
Definition 3.1. Let E be a countable Borel equivalence relation on a Polish space X, and let
$x \in X$
. The orbit forcing
$\mathbb {P}_{x}=\mathbb {P}_{x}^{E}$
is defined by
$$ \begin{align*} \mathbb{P}_{x}=\{U \subseteq X: U\mbox{ is open and } U \cap [x]_{E} \neq \varnothing\} \end{align*} $$
with its elements ordered by inclusion, that is,
$U \leq U^{\prime }$
iff
$U \subseteq U^{\prime }$
.
Since
$U \cap \overline {[x]}\neq \varnothing $
iff
$U \cap [x] \neq \varnothing $
, we can view the sets
$U\cap \overline {[x]}$
as the objects in the forcing notion, in which case the forcing notion
$\mathbb {P}_{x}$
can simply be viewed as ordinary Cohen forcing on the closed subspace
$Y=\overline {[x]}$
of X. Thus, as with usual Cohen forcing, we can regard forcing arguments using
$\mathbb {P}_{x}$
as category arguments on the space
$\overline {[x]}$
. Nevertheless, we will see that the forcing proofs can be more intuitive than category arguments.
We employ throughout the usual metamathematical convention/abuse that we avoid talking about countable transitive models M and pretend that we can force over V (we can replace V in the arguments by such an M).
As remarked in the previous section, we can view the countable Borel equivalence relation E as coming from a Borel action of a countable group
$\Gamma $
, and view the space X as a certain invariant Borel subset of
$2^{\Gamma \times \omega }$
. Now if G is
$\mathbb {P}_{x}$
-generic over V, the space
$X^{V[G]}$
continues to be a standard Borel space and
$E^{V[G]}$
continues to be a countable Borel equivalence relation. Moreover, the generic G can be identified with an element
$x_{G}\in X^{V[G]}$
. With a slight abuse of terminology we will refer to
$x_{G}$
as a generic element of X for the orbit forcing
$\mathbb {P}_{x}$
. Note that we always have that
$x_{G} \in \overline {[x]}_{E}$
, where both the orbit and the closure are computed in
$V[G]$
.
As a first application of the orbit-forcing we present a general result, Theorem 3.4, about sequences of complete sections in equivalence relations generated by continuous actions of countable groups on compact spaces. This includes the case of Bernoulli shift actions on
$2^{\Gamma }$
and
$F(2^{\Gamma })$
since there exist compact invariant sets
$X \subseteq F(2^{\Gamma })$
[Reference Gao, Jackson and Seward7, Reference Gao, Jackson and Seward8]. First we recall a well-known definition and fact.
Definition 3.2. Consider a Borel action of a countable group
$\Gamma $
on a Polish space X. A point
$x \in X$
is recurrent if for every open set
$U \subseteq X$
with
$U\cap [x]\neq \varnothing $
, there is a finite
$T \subseteq \Gamma $
so that for all
$y\in [x]$
there is
$t \in T$
with
$t \cdot y \in U$
.
Lemma 3.3. Let
$\Gamma $
be a countable group, X a compact Polish space, and
$\Gamma \curvearrowright X$
a continuous, minimal action. Then every
$x \in X$
is recurrent.
Proof Fix a point
$x \in X$
and a non-empty open set U with
$U \cap [x]\neq \emptyset $
. Enumerate
$\Gamma $
as
$\gamma _{1}, \gamma _{2}, \ldots $
and set
$T_{n} = \{\gamma _{i} : 1 \leq i \leq n\}$
. Towards a contradiction, suppose that for every n there is
$x_{n} \in [x]$
with
$T_{n} \cdot x_{n} \cap U = \varnothing $
. Since X is compact, there is an accumulation point y of the sequence
$x_{n}$
. Now for any
$i \in \mathbb {N}$
we have
$\gamma _{i} \cdot x_{n} \not \in U$
for every
$n \geq i$
. Since
$\Gamma $
acts continuously and U is open, it follows that
$\gamma _{i} \cdot y \not \in U$
. Thus the orbit of y does not meet U and hence is not dense, a contradiction to the minimality of the action.
Theorem 3.4. Let
$\Gamma $
be a countable group, X a compact Polish space, and
$\Gamma \curvearrowright X$
a continuous action giving rise to the orbit equivalence relation E. Let
$(A_{n})_{n \in \mathbb {N}}$
be a sequence of finite subsets of
$\Gamma $
such that every finite subset of
$\Gamma $
is contained in some
$A_{n}$
. Let
$(S_{n})_{n \in \mathbb {N}}$
be a sequence of Borel complete sections of E. Then there is an
$x \in X$
such that for infinitely many n we have
$A_{n}\cdot x \cap S_{n} \neq \varnothing $
.
Proof Since X is compact, we may fix an
$x \in X$
which is minimal. Let
$\mathbb {P}=\mathbb {P}_{x}$
be the corresponding orbit forcing. Let
$p =U\cap \overline {[x]} \in \mathbb {P}$
and fix
$N\in \mathbb {N}$
. By minimality of x, there is a finite
$T \subseteq \Gamma $
such that for all
$z \in \overline {[x]}$
there is a
$t \in T$
with
$t \cdot z \in U$
. Let
$n> N$
be such that
$T^{-1}\subseteq A_{n}$
. Let G be generic for
$\mathbb {P}$
with corresponding real
$x_{G}$
. The statements that
$\forall z \in \overline {[x]}\ (S_{n} \cap [z] \neq \varnothing )$
and
$\forall z\in \overline {[x]}\ (T\cdot z\cap U\neq \varnothing )$
are
$\boldsymbol {\Pi }^{1}_{1}$
and so by absoluteness continue to be true in
$V[G]$
. Since
$x_{G} \in \overline {[x]}$
, there is a
$y \in [x_{G}]\cap S_{n}$
. So there is a
$t \in T$
with
$t\cdot y \in U$
, and
$t^{-1} \cdot (t \cdot y)\in S_{n}$
. Since
$t\cdot y$
is also generic, there is a
$q \leq p$
such that
$q \Vdash A_{n} \cdot \dot {x} \in S_{n}$
. This shows
$1 \Vdash \exists ^{\infty } n\ (A_{n} \cdot \dot {x} \cap S_{n} \neq \varnothing )$
. Thus there are infinitely many n such that
$A_{n} \cdot x_{G} \cap S_{n}\neq \varnothing $
, and by absoluteness there is a
$z\in V\cap \overline {[x]}$
such that
$A_{n} \cdot z \cap S_{n} \neq \varnothing $
for infinitely many n.
We have the following immediate corollary concerning complete sections in
$F(2^{\mathbb {Z}^{d}})$
.
Corollary 3.5. Let
$f \colon \mathbb {N} \to \mathbb {N}$
be such that
$\lim \sup _{n} f(n)=+\infty $
. Let
$\{ S_{n}\}$
be a sequence of Borel complete sections of
$F(2^{\mathbb {Z}^{d}})$
. Then there is an
$x \in F(2^{\mathbb {Z}^{d}})$
such that for infinitely many n we have
$\rho (x,S_{n})<f(n)$
.
Proof Let x be any 2-coloring (or hyperaperiodic element) in
$2^{\mathbb {Z}^{d}}$
. Then
$X=\overline {[x]}$
is a compact invariant subspace of
$F(2^{\mathbb {Z}^{d}})$
. Apply Theorem 3.4 to X with
$A_{n}=\{ \gamma \in \mathbb {Z}^{d}: \|\gamma \|<f(n)\}$
.
Remark 3.6. (1) The proof of Theorem 3.4 still works if each
$S_{n}$
is just assumed to be absolutely
$\boldsymbol {\Delta }^{1}_{2}$
, instead of Borel. By this we mean there are
$\boldsymbol {\Sigma }^{1}_{2}$
statements
$\varphi $
and
$\psi $
which define
$S_{n}$
, and
$X-S_{n}$
and such that
$\varphi $
,
$\psi $
continue to define complimentary sets in all forcing extension
$V[G]$
of V.
(2) The proof of Theorem 3.4 shows that we may weaken the hypothesis of Corollary 3.5 that the
$S_{n}$
are complete sections to the statement that for each
$x \in F(2^{\mathbb {Z}^{d}})$
and for each n there is an
$m \geq n$
such that
$S_{m} \cap [x] \neq \varnothing $
. However, we need to assume now that
$\liminf _{n} f(n)=+\infty $
.
As we mentioned above, a forcing argument using
$\mathbb {P}_{x}$
is essentially the same as a category argument on the subspace
$\overline {[x]}$
of the Polish space X. In Theorem 3.7 we will illustrate this by using this alternate approach.
As a consequence of the methods of Theorem 3.4 we are able to obtain some results on the existence of recurrent points.
Theorem 3.7. Let
$\Gamma $
be a countable group, X a compact Polish space,
$\Gamma \curvearrowright X$
a continuous action, Y a Polish space, and
$\Gamma \curvearrowright Y$
a Borel action. Let
$\varphi \colon X \to Y$
be a Borel equivariant map. Then there is an
$x \in X$
such that
$\varphi (x)$
is a recurrent point of Y.
Proof By replacing X with an invariant subspace and using Corollary 2.4 we may assume that
$\Gamma \curvearrowright X$
is minimal. Fix a countable base
$\mathcal {V}$
for Y. For each
$V \in \mathcal {V}$
the preimage
$\varphi ^{-1}(V)$
is Borel and hence there is a (possibly empty) open set
$U_{V} \subseteq X$
with
$U_{V} \triangle \varphi ^{-1}(V)$
meager. By the Baire category theorem,
$X^{\prime } = X \setminus \bigcup _{\gamma \in \Gamma } \bigcup _{V \in \mathcal {V}} \gamma \cdot (U_{V} \triangle \varphi ^{-1}(V))$
is non-empty. Fix any
$x \in X^{\prime }$
. We claim that
$\varphi (x)$
is recurrent. Consider an open set
$W \subseteq Y$
with
$W \cap [\varphi (x)] \neq \varnothing $
. Then there is
$V \in \mathcal {V}$
with
$V \subseteq W$
and
$V \cap [\varphi (x)] \neq \varnothing $
. So
$\varphi ^{-1}(V) \cap [x] \neq \varnothing $
and our choice of x implies
$U_{V} \cap [x] \neq \varnothing $
. By Lemma 3.3 x is recurrent, so there is a finite set
$T \subseteq \Gamma $
with
$T \cdot y \cap U_{V} \neq \varnothing $
for all
$y \in [x]$
. The definition of
$X^{\prime }$
then gives
$T \cdot y \cap \varphi ^{-1}(V) \neq \varnothing $
for all
$y \in [x]$
. We conclude that
$T \cdot y \cap W \neq \varnothing $
for all
$y \in [\varphi (x)]$
. Thus
$\varphi (x)$
is recurrent.
Corollary 3.8. For any countable group
$\Gamma $
, any Borel action
$\Gamma \curvearrowright Y$
of
$\Gamma $
on a Polish space Y, and any Borel equivariant map
$\varphi \colon F(2^{\Gamma }) \to Y$
, there is an
$x \in F(2^{\Gamma })$
such that
$\varphi (x)$
is recurrent.
Proof By [Reference Gao, Jackson and Seward7, Reference Gao, Jackson and Seward8], there is an invariant compact set
$X \subseteq F(2^{\Gamma })$
. Now apply Theorem 3.7 to X.
Corollary 3.9. Let
$\tau $
be a Polish topology on
$F(2^{\Gamma })$
having the same Borel sets as the standard topology. Then there is a
$\tau $
-recurrent point.
Corollary 3.10. If
$B \subseteq F(2^{\Gamma })$
is a Borel complete section then B meets some orbit recurrently, i.e., there is
$x\in F(2^{\Gamma })$
and finite
$T\subseteq \Gamma $
such that for any
$y\in [x]$
,
$T\cdot y\cap B\neq \varnothing $
.
Proof Let
$\tau $
be a Polish topology on
$F(2^{\Gamma })$
with
$B\in \tau $
and having the same Borel sets as the standard topology (cf. [Reference Gao3, Section 4.2]). Apply Corollary 3.9.
In Theorem 7.4 we will strengthen Corollary 3.10 in the case
$\Gamma =\mathbb {Z}^{d}$
by showing that on some orbit B must contain a lattice.
4 Borel layered toast
In this short section we present another application of Corollary 3.5 on the non-existence of certain types of strong marker structure on
$F(2^{\mathbb {Z}^{d}})$
. The name “toast” for the type of structure defined below was coined by Miller. We will define two versions of this notion, the general or “unlayered” toast structure, and the more restrictive notion of “layered” toast. These are both strong types of marker structures to impose on the orbits of
$F(2^{\mathbb {Z}^{d}})$
. We can consider both the Borel as well as the clopen versions of these notions, which leads to four separate questions concerning the existence of these structures. It turns out that a Borel unlayered toast structure does exist, but the answers are no for all the other existence questions. We present the proof for the nonexistence of Borel layered toast here; the other results are presented in [Reference Gao, Jackson, Krohne and Seward5, Reference Gao, Jackson, Krohne and Seward6].
We note that the notion of toast arose naturally through its connections with interesting problems in Borel combinatorics. For example, in [Reference Gao, Jackson, Krohne and Seward6] we use Borel unlayered toasts to construct a Borel chromatic
$3$
-coloring of
$F(2^{\mathbb {Z}^{d}})$
(and thus showing that
$F(2^{Z^{d}})$
has Borel chromatic number 3). In this construction, the regions between the toast layers (that is, the points in a
$T_{n}$
class minus
$\bigcup _{m<n} \operatorname{dom}(T_{m})$
) are chromatically
$2$
-colored. Theorem 6.9 later in this paper will put strong restrictions on chromatically
$2$
-colored regions of Borel colorings in
$F(2^{\mathbb {Z}^{2}})$
. Toast structures have been constructed modulo meager sets and modulo
$\mu $
-null sets by Conley and Miller and used to bound the Baire-measurable and
$\mu $
-measurable chromatic numbers of many Borel graphs [Reference Conley and Miller2].
First we make precise the notion of a toast marker structure.
Definition 4.1. Let
$\{T_{n}\}$
be a sequence of subequivalence relations of
$E_{\mathbb {Z}^{d}}$
on some subsets
$\operatorname{dom}(T_{n})\subseteq F(2^{\mathbb {Z}^{d}})$
with each
$T_{n}$
-equivalence class finite. Assume
$\bigcup _{n} \operatorname{dom}(T_{n})= F(2^{\mathbb {Z}^{d}})$
. We say
$\{ T_{n}\}$
is a (unlayered)toast if:
-
(1) For each
$T_{n}$
-equivalence class C, and each
$T_{m}$
-equivalence class
$C^{\prime }$
where
$m>n$
, if
$C \cap C^{\prime } \neq \varnothing $
then
$C \subseteq C^{\prime }$
. -
(2) For each
$T_{n}$
-equivalence class C there is
$m>n$
and a
$T_{m}$
-equivalence class
$C^{\prime }$
such that
$C \subseteq C^{\prime }\setminus \partial C^{\prime }$
.
We say
$\{ T_{n}\}$
is a layered toast if, instead of (2) above, we have
-
(2′ ) For each
$T_{n}$
-equivalence class C there is a
$T_{n+1}$
-equivalence class
$C^{\prime }$
such that
$C \subseteq C^{\prime }\setminus \partial C^{\prime }$
.
Figure 1 illustrates the definitions of layered and unlayered toast.
(a) Layered toast. (b) Unlayered toast.
Theorem 4.2. There is no Borel layered toast on
$F(2^{\mathbb {Z}^{d}})$
.
Proof Suppose
$\{T_{n}\}$
were a sequence of Borel subequivalence relations of
$E_{\mathbb {Z}^{d}}$
on some subsets
$\operatorname{dom}(T_{n})\subseteq F(2^{\mathbb {Z}^{d}})$
forming a layered toast structure on
$F(2^{\mathbb {Z}^{d}})$
. For each n let
$\partial T_{n}$
be the union of all boundaries of the
$T_{n}$
-equivalence classes. For
$x \in F(2^{\mathbb {Z}^{d}})$
, let
$f_{x} \colon \mathbb {N} \to \mathbb {N}$
be defined by
$f_{x}(n)=\rho (x, \partial T_{n})$
if
$x \in \operatorname{dom}(T_{n})$
and
$f_{x}(n)=0$
otherwise. This is well-defined as each
$T_{n}$
-equivalence class is finite. Since
$\{T_{n}\}$
is a layered toast, by (
$2^{\prime }$
) we have
$\operatorname{dom}(T_{n})\subseteq \operatorname{dom}(T_{n+1})$
for all n. For
$x \in F(2^{\mathbb {Z}^{d}})$
, let
$n_{0}$
be large enough so that
$x \in \operatorname{dom}(T_{n_{0}})$
. We claim that for
$n \geq n_{0}$
that
$f_{x}(n)<f_{x}(n+1)$
. To see this, let
$n \geq n_{0}$
, and let
$a=f_{x}(n)$
. Let
$g \in \mathbb {Z}^{n}$
with
$\| g \| \leq a$
. It follows easily from the definitions of a and
$\partial T_{n}$
that
$g \cdot x$
is
$T_{n}$
-equivalent to x (if we choose a path p from
$\vec {0}$
to g of length a, then by an easy induction along the path we have that
$g^{\prime } \cdot x$
is
$T_{n}$
-equivalent to x for all
$g^{\prime }$
in p). So, from property (
$2^{\prime }$
) we have that
$g \cdot x \notin \partial T_{n+1}$
. Thus,
$\rho (x,\partial T_{n+1})>a$
. So, for all
$x \in F(2^{\mathbb {Z}^{d}})$
and all sufficiently large n (which may depend on x) we have
$f_{x}(n)<f_{x}(n+1)$
.
If we let
$f\colon \mathbb {N} \to \mathbb {N}$
be the function
$f(n)=\sqrt {n}$
, then for all
$x \in F(2^{\mathbb {Z}^{n}})$
we have that for all but finitely many
$n \in \mathbb {N}$
that
$\rho (x, \partial T_{n})> f(n)$
. This violates Corollary 3.5.
5 Bounded geometry of marker regions
In this section we prove a nonexistence theorem for marker regions in
$F(2^{\mathbb {Z}^{2}})$
that are of regular shape. A version of this theorem was stated without proof as Theorem 3.5 of [Reference Gao and Jackson4].
Before stating the theorem we make some comments about its significance. Suppose E is a finite subequivalence relation of
$F(2^{\mathbb {Z}^{n}})$
. Since the action is free and
$\mathbb {Z}^{n}$
is abelian, it makes sense to speak of the shape of an E-equivalence class
$[x]_{E}$
. This is the equivalence class (under translation by elements of
$\mathbb {Z}^{d}$
) of the finite set
$A \subseteq \mathbb {Z}^{n}$
given by
$A=\{ g \in \mathbb {Z}^{n} \colon g \cdot x\, E\, x\}$
). We also call the E-equivalence classes marker regions.
In the proof [Reference Gao and Jackson4] of the hyperfiniteness of abelian group actions, the essential ingredient is the construction of orthogonal marker regions for
$F(2^{\mathbb {Z}^{<\omega }})$
. Given a sequence
$d_{1} < d_{2} <\cdots $
of distance scales, a sequence of finite subequivalence relations
$E_{n}$
with marker regions
$\mathcal {R}_{n}$
was constructed which witnessed the hyperfiniteness of
$F(2^{\mathbb {Z}^{<\omega }})$
in the sense that if
$x E\, y$
then for large enough n we have
$x E_{n}\, y$
. Equivalently, for any
$x \in F(2^{\mathbb {Z}^{<\omega }})$
, the distance
$\varphi _{x}(n)=\rho (x,\partial \mathcal {R}_{n})$
from x to the boundary of its region in
$\mathcal {R}_{n}$
goes to infinity. A key aspect of the construction is that the marker regions
$R\in \mathcal {R}_{n}$
become increasingly fractal-like as n increases. At scale
$d_{n}$
each
$R\in \mathcal {R}_{n}$
is roughly a rectangle, but at the smaller scales
$d_{i}$
the region R has increasingly irregular boundary.
It is natural to ask if the fractal-like nature of the construction is necessary. Theorem 5.1 says that it is. We state the result for rectangles for simplicity, but the argument also applies to polyhedra with a bounded number of sides.
Theorem 5.1. There does not exist a sequence
$\mathcal {R}_{n}$
of Borel finite subequivalence relations on
$F(2^{\mathbb {Z}^{2}})$
satisfying all the following:
-
(1) (regular shape) For each n, each marker region R of
$\mathcal {R}_{n}$
is a rectangle. -
(2) (bounded size) For each n, there is an upper bound
$w(n)$
on the size of the edge lengths of the marker regions R in
$\mathcal {R}_{n}$
. -
(3) (increasing size) Letting
$v(n)$
denote the smallest edge length of a marker region R of
$\mathcal {R}_{n}$
, we have
$\lim _{n} v(n)=+\infty $
. -
(4) (vanishing boundary) For each
$x \in F(2^{\mathbb {Z}^{2}})$
we have that
$\lim _{n} \rho (x, \partial \mathcal {R}_{n})=+\infty $
.
Proof We sketch a simple Cohen forcing/category proof of the result. Let
$\mathbb {P}$
be Cohen forcing to add an element of
$2^{\mathbb {Z}^{2}}$
, so conditions p are finite functions from
$\mathbb {Z}^{2}$
to
$\{ 0,1\}$
, and are ordered by extension. Let
$p \in \mathbb {P}$
and fix
$n_{0} \in \mathbb {N}$
. By extending p we may assume
$\operatorname{dom}(p)$
is a rectangle centered at
$(0,0)$
, say with maximum side length
$\| p\|$
. Suppose
$q \leq p$
is constructed as shown in Figure 2, where we stagger the vertical offsets of the rectangles (which are copies of p) by
$1$
as we move to the adjacent column to the right. Note that if q is any condition constructed in this manner and L is a horizontal line segment of points in
$\mathbb {Z}^{2} \cap \operatorname{dom}(q)$
with length greater than
$2\| p\|^{2}$
, and L is not within
$\| p\|$
of the boundary of
$\operatorname{dom}(q)$
, then for one of the copies
$p^{\prime }$
of p in q we will have that
$p^{\prime }$
is centered at a point of L.
The construction of the condition q.
Let
$n>n_{0}$
be large enough so that
$v(n)> 2\| p\|^{2}$
. Extend p to a condition q by the above staggering pattern so that q has dimensions greater than
$3w(n)$
. If
$x_{G}$
is a generic extending q, then for some
$R\in \mathcal {R}_{n}\cap [x_{G}]$
we will have that one of the horizontal boundary segments of R will have length
$\geq v(n)$
and will be contained in q (and not within
$\| p \|$
of the boundary of
$\operatorname{dom}(q)$
). Thus, one of the copies
$p^{\prime }$
of p in q is centered on
$\partial R$
. Since the shift of a generic is also generic, there is an
$r \leq q$
with
$r \Vdash \exists n> n_{0}\ (\dot {x}_{G} \in \partial \mathcal {R}_{n})$
. This shows that for infinitely many n we have
$\dot {x}_{G} \in \partial \mathcal {R}_{n}$
which contradicts (3).
We now present an alternate proof due to the referee of Theorem 5.1 using Fact 2.6.
Alternate proof of Theorem 5.1.
We will make use of Fact 2.6. Let
$$ \begin{align*} X = \varprojlim \mathbb{Z}^{2} / (3^{n} \mathbb{Z} \times 2^{n} \mathbb{Z}) = \{f \in \prod_{n} \mathbb{Z}^{2} / (3^{n} \mathbb{Z} \times 2^{n} \mathbb{Z}) \colon \forall n \ \varphi_{n}(f(n+1)) = f(n)\},\end{align*} $$
where
$\varphi _{n} \colon \mathbb {Z}^{2} / (3^{n+1} \mathbb {Z} \times 2^{n+1} \mathbb {Z}) \rightarrow \mathbb {Z}^{2} / (3^{n} \mathbb {Z} \times 2^{n} \mathbb {Z})$
is the canonical homomorphism. Consider the action of
$\mathbb {Z}^{2}$
on X defined by the rule
$((a, b) \cdot f)(i) = f(i) + [(a, a+b)]$
. Since
$3^{n}$
and
$2^{n}$
are relatively prime, by the Chinese remainder theorem, for every
$[(i, j)] \in \mathbb {Z}^{2} / (3^{n} \mathbb {Z} \times 2^{n} \mathbb {Z})$
there is
$k \in \mathbb {N}$
with
$[(k,k)] = [(i,j)]$
. Hence, for every non-empty basic open set U, there is a finite
$S \subseteq \mathbb {Z}$
such that
$\bigcup _{k \in S} (k, 0) \cdot U = X$
.
Suppose a sequence
$\mathcal {R}_{n}$
of finite Borel subequivalence relations satisfies conditions (1)–(3). We claim that for comeager many x, there are infinitely many n such that
$x \in \partial \mathcal {R}_{n}$
(hence condition (4) must fail). By the Baire category theorem, it suffices to show that for every
$N \in \mathbb {N}$
the set of x with
$x \in \partial \mathcal {R}_{n}$
for some
$n \geq N$
is comeager.
Fix N and fix a non-empty basic open set U. As above, fix a finite set
$S \subseteq \mathbb {Z}$
with
$\bigcup _{k \in S} (k, 0) \cdot U = X$
. By (3) we can fix
$n \geq N$
with
$v(n) \geq \sup _{k \in S} |k|$
. Set
$B = \{x \in X \colon \forall k \in S \ (-k,0) \cdot x \in \partial \mathcal {R}_{n}\}$
. Since
$v(n) \geq \sup _{k \in S} |k|$
, B meets the boundary of every
$\mathcal {R}_{n}$
-class. So B is a complete section and therefore must be non-meager as
$X = \bigcup _{\gamma \in \mathbb {Z}^{2}} \gamma \cdot B$
. In particular, B is non-meager in
$\bigcup _{k \in S} (k,0) \cdot U = X$
and therefore
$\bigcup _{k \in S} (-k,0) \cdot B$
is non-meager in U. Of course,
$\bigcup _{k \in S} (-k,0) \cdot B \subseteq \partial \mathcal {R}_{n}$
by definition of B, so
$\partial \mathcal {R}_{n}$
is non-meager in U. It follows that the set of x with
$x \in \partial \mathcal {R}_{n}$
for some
$n \geq N$
is non-meager in every non-empty basic open set, and is therefore comeager.
The alternate proof given above has the advantage that it did not need the bounded size (assumption (2)) condition. It is also possible to give a forcing proof which shows this stronger result. Briefly, construct
$x \in F(2^{\mathbb {Z}^{2}})$
which is x-minimal. By this we mean that if a pattern
$p\in 2^{[-n,n]^{2}}$
appears in x, then there is a
$k_{p}\in \mathbb {N}$
such that for any
$y \in [x]$
there is a
$k \leq k_{p}$
such that
$(k,0)\cdot y$
is in the neighborhood
$N_{p}$
determined by p. This can be done, for example, by letting x be the limit of
$x_{n}$
, where
$x_{n}$
is defined on a domain
$[a_{n},b_{n}]\times \mathbb {Z}$
and has a vertical period
$p_{n}$
, and letting
$x_{n+1}$
be obtained from
$x_{n}$
by placing adjacent copies of
$x_{n}$
, with all possible vertical shifts
$\leq p_{n}$
, and then changing the values on the right-most vertical line to have period
$p_{n+1}>p_{n}$
and such that the nth non-zero shift
$s_{n} \in \mathbb {Z}^{2}-\{ (0,0)\}$
will not be a period. If
$\mathbb {P}_{x}$
is the orbit-forcing corresponding to x, then an argument similar to that above shows that
. It is not immediately clear if (2) can be eliminated for the more general statement about polygons.
6 Minimal 2-coloring forcing on
$F(2^{\mathbb {Z}^{d}})$
We introduce a forcing
$\mathbb {P}_{mt}$
which we call the minimal two-coloring forcing and a variant
$\mathbb {P}_{omt}$
, the odd minimal two-coloring forcing, and use them to obtain several results.
$\mathbb {P}_{mt}$
is a natural forcing to generically add an
$x_{G}$
which is a minimal
$2$
-coloring. While this forcing can be defined for any countable group, we describe it here just for the group
$\mathbb {Z}^{d}$
, and in fact take
$d=2$
as the general case is entirely similar.
Definition 6.1. The minimal
$2$
-coloring forcing
$\mathbb {P}_{mt}$
on
$\mathbb {Z}^{2}$
consists of conditions
$$ \begin{align*} \mathfrak{p}=(p,n,t_{1},\dots, t_{n},T_{1},\dots, T_{n}, m, f_{1},\dots, f_{m}, F_{1},\dots, F_{m}), \end{align*} $$
where
$m,n \in \mathbb {N}$
,
$p\in 2^{<\mathbb {Z}^{2}}$
with
$\operatorname{dom}(p)=[a, b]\times [c,d]$
for some
$a, b,c,d\in \mathbb {Z}$
,
$t_{1},\dots , t_{n}\in \mathbb {Z}^{2}-\{(0,0)\}$
,
$f_{1},\dots , f_{m}\in 2^{<\mathbb {Z}^{2}}$
, and
$T_{1},\dots , T_{n}$
,
$F_{1},\dots , F_{m}$
are finite subsets of
$\mathbb {Z}^{2}$
such that the following conditions are satisfied:
-
(a) (2-coloring property) For any
$1\leq i\leq n$
and
$g\in \operatorname{dom}(p)$
there is
$\tau \in T_{i}$
such that
$g+\tau , g+t_{i}+\tau \in \operatorname{dom}(p)$
and
$p(g+\tau )\neq p(g+t_{i}+\tau )$
. -
(b1) (minimality) For any
$1\leq j\leq m$
and
$g\in \operatorname{dom}(p)$
there is
$\sigma \in F_{j}$
such that
$g+\sigma +\operatorname{dom}(f_{j})\subseteq \operatorname{dom}(p)$
and for all
$u\in \operatorname{dom}(f_{j})$
,
$p(g+\sigma +u)=f_{j}(u)$
. -
(b2) (minimality with flips) For any
$1\leq j\leq m$
and
$g\in \operatorname{dom}(p)$
there is
$\sigma \in F_{j}$
such that
$g+\sigma +\operatorname{dom}(f_{j})\subseteq \operatorname{dom}(p)$
and for all
$u\in \operatorname{dom}(f_{j})$
,
$p(g+\sigma +u)=1-f_{j}(u)$
.
We let
$n(\mathfrak {p}), \vec {t}(\mathfrak {p})$
, etc. denote the components of
$\mathfrak {p}$
.
If
$\mathfrak {p},\mathfrak {q}\in \mathbb {P}_{mt}$
, we define
$\mathfrak {q}\leq \mathfrak {p}$
iff
$q\supseteq p$
,
$n(\mathfrak {q})\geq n(\mathfrak {p})$
,
$m(\mathfrak {q})\geq m(\mathfrak {p})$
,
$t_{i}(\mathfrak {q})=t_{i}(\mathfrak {p})$
and
$T_{i}(\mathfrak {q})=T_{i}(\mathfrak {p})$
for all
$1\leq i\leq n(\mathfrak {p})$
, and
$f_{j}(\mathfrak {q})=f_{j}(\mathfrak {p})$
and
$F_{j}(\mathfrak {q})=F_{j}(\mathfrak {p})$
for all
$1\leq j\leq m(\mathfrak {p})$
.
Properties (a) and (b1) will ensure the generic
$x_{G}$
is respectively a
$2$
-coloring and minimal, while (b2) will aid in the arguments. We now prove a few simple lemmas which show that
$\mathbb {P}_{mt}$
does indeed add a minimal
$2$
-coloring in
$2^{\mathbb {Z}^{2}}$
. As the proofs of the lemmas are straightforward, we give sketches, leaving some details to the reader.
Lemma 6.2. For any
$g\in \mathbb {Z}^{2}$
, the set
$D_{g}=\{\mathfrak {q}\in \mathbb {P}_{mt} \colon g\in \operatorname{dom}(q)\}$
is dense in
$\mathbb {P}_{mt}$
.
Proof Let
$\mathfrak {p}\in \mathbb {P}_{mt}$
and
$g\in \mathbb {Z}^{2}$
. We need to find
$\mathfrak {q}\leq \mathfrak {p}$
with
$g\in \operatorname{dom}(q)$
. Let q be obtained by tiling a large rectangle in
$\mathbb {Z}^{2}$
containing g with copies of p. Let
$n(\mathfrak {q})=n(\mathfrak {p})$
and likewise for the other components. It is easy to check that (a), (b1), and (b2) are still satisfied by
$\mathfrak {q}$
.
If
$p \in 2^{<\mathbb {Z}^{2}}$
, we let
$\bar {p} \in 2^{<\mathbb {Z}^{2}}$
be defined by
$\operatorname{dom}(\bar {p})=\operatorname{dom}(p)$
and
$\bar {p}(g)=1-p(g)$
for
$g \in \operatorname{dom}(p)$
. We call
$\bar {p}$
the “flip”of p.
Lemma 6.3. For any
$t\in \mathbb {Z}^{2}-\{(0,0)\}$
the set
$$ \begin{align*}E_{t}=\{\mathfrak{q}\in\mathbb{P}_{mt}\colon \exists 1\leq i\leq n(\mathfrak{q})\ t_{i}(\mathfrak{q})=t\}\end{align*} $$
is dense in
$\mathbb {P}_{mt}$
.
Proof Let
$t=(t_{1},t_{2})\in \mathbb {Z}^{2}-\{(0,0)\}$
and
$\mathfrak {p}\in \mathbb {P}_{mt}$
. We construct
$\mathfrak {q}\leq \mathfrak {p}$
with
$t=t_{i}(\mathfrak {q})$
for some
$1\leq i\leq n(\mathfrak {q})$
. Let
$q \in 2^{\mathbb {Z}^{2}}$
be obtained by tiling a large rectangular region with copies of p, say using a
$(2a+1) \times (2a+1)$
array of copies of p, except for the center copy where we use instead
$\bar {p}$
. We assume
$a> \max \{ t_{1},t_{2}\}$
. We let
$n(\mathfrak {q})=n(\mathfrak {p})+1$
,
$t_{n(\mathfrak {q})}=t$
, and
$T_{n(\mathfrak {q})}=[-w,w]\times [-w,w]$
where w is the maximum side length of q, and the other components of
$\mathfrak {q}$
and
$\mathfrak {p}$
are equal. For any
$g \in \operatorname{dom}(q)$
there is a
$\tau \in T_{n(\mathfrak {q})}$
such that
$g+\tau $
is in the center copy of
$\bar {p}$
, and
$g+t+\tau $
is not in the center copy. If
$q(g+\tau ) \neq q(g+t+\tau )$
then we are done, and otherwise there is a
$\tau ^{\prime }$
so that
$g+\tau ^{\prime }$
is in a copy of p adjacent to the center copy, in the same relative position, and such that neither
$g+\tau ^{\prime }$
nor
$g+t+\tau ^{\prime }$
are in the center copy. We then have
$q(g+\tau ^{\prime })=1-q(g+\tau )=1-q(g+t+\tau )= 1-q(g+t+\tau ^{\prime })$
, since
$g+t+\tau $
and
$g+t+\tau ^{\prime }$
are in the same relative positions in copies of p (and not the center copy). This shows (a) for
$\mathfrak {q}$
, and (b1) and (b2) are easy.
Lemma 6.4. For any finite set
$A\subseteq \mathbb {Z}^{2}$
, the set
$$ \begin{align*}D_{A}=\{\mathfrak{q}\in\mathbb{P}_{mt} \colon \exists 1\leq j\leq m(\mathfrak{q})\ A\subseteq {\operatorname{dom}} (f_{j}(\mathfrak{q}))\}\end{align*} $$
is dense in
$\mathbb {P}_{mt}$
.
Proof Let
$\mathfrak {p}\in \mathbb {P}$
and
$A\subseteq \mathbb {Z}^{2}$
be finite. From Lemma 6.2 we may assume that
$A\subseteq \operatorname{dom}(p)$
. Let q consist of p together with a copy of
$\bar {p}$
immediately to the right. Let
$m(\mathfrak {q})=m(\mathfrak {p})+1$
,
$F_{m(\mathfrak {q})}=[-w,w]\times [-w,w]$
where w is the maximum dimension of q, and
$f_{m(\mathfrak {q})} =p\restriction A$
. Then (b1) trivially holds for
$m(\mathfrak {q})$
and (b2) holds since the right copy is
$\bar {p}$
.
In fact, the above proof gives the following lemma.
Lemma 6.5. For any
$\mathfrak {p}\in \mathbb {P}_{mt}$
, the set
$$ \begin{align*} D_{p}=\{\mathfrak{q}\in\mathbb{P}_{mt}\colon \exists 1\leq j\leq m(\mathfrak{q})\ p\subseteq f_{j}(\mathfrak{q})\} \end{align*} $$
is dense below
$\mathfrak {p}$
in
$\mathbb {P}_{mt}$
.
Proof As in the previous proof, define q to be a tiling with one copy of p and a copy of
$\bar {p}$
to the right.
Putting these lemmas together we have the following.
Lemma 6.6. If
$x_{G}$
is generic for
$\mathbb {P}_{mt}$
, then
$x_{G}$
is a minimal
$2$
-coloring.
Proof Lemma 6.2 gives that
$x_{G} \in 2^{\mathbb {Z}^{2}}$
. Lemma 6.3 gives that
$x_{G}$
is a
$2$
-coloring. To see that
$x_{G}$
is minimal, let
$A \subseteq \mathbb {Z}^{2}$
be finite, and let
$f=x_{G}\restriction A$
. Let
$\mathfrak {p} \in G$
be such that
$\operatorname{dom}(p) \supseteq A$
. From Lemma 6.5 there is a
$\mathfrak {q} \in G$
with
$f \subseteq f_{j}$
for some
$1 \leq j \leq m(\mathfrak {q})$
. We then have that
$F_{j}(\mathfrak {q})$
witnesses the minimality condition for A, that is, for all
$g \in \mathbb {Z}^{2}$
there is a
$t \in F_{j}(\mathfrak {q})$
such that
$x_{G}(g+t +u)=f(u)$
for all
$u\in \operatorname{dom}(f)=A$
.
Using Lemma 6.6 and the proof of Theorem 3.4 we can get a direct proof of Corollary 3.5 which is self-contained and does not rely on the a priori construction of a minimal
$2$
-coloring.
We next define the variation
$\mathbb {P}_{omt}$
.
Definition 6.7. The odd minimal
$2$
-coloring forcing
$\mathbb {P}_{omt}$
is defined exactly as
$\mathbb {P}_{mt}$
in Definition 6.1 except that we add the requirement that if
$\operatorname{dom}(p)=[a,b]\times [c,d]$
then both
$b-a+1$
and
$d-c+1$
are odd. That is, the rectangle representing the domain of p must have odd numbers of vertices on each of the sides.
The following result intuitively states that any Borel complete section in
$F(2^{\mathbb {Z}^{2}})$
has an odd recurrence on some orbit.
Theorem 6.8. Let
$O=\{ g\in \mathbb {Z}^{2}\colon \|g\| \text { is odd}\}$
. If
$B \subseteq F(2^{\mathbb {Z}^{2}})$
is a Borel complete section then there is
$x\in F(2^{\mathbb {Z}^{2}})$
and finite
$T\subseteq O$
such that for any
$y\in [x]$
,
$T\cdot y\cap B\neq \varnothing $
.
Proof Let
$x_{G}$
be a generic real for
$\mathbb {P}_{omt}$
. Since
$B^{V[G]}$
continues to be a Borel complete section, there is
$g_{0}\in \mathbb {Z}^{2}$
such that
$g_{0}\cdot x_{G}\in B$
. Since
$g_{0}\cdot x_{G}$
is also generic, we may assume
$g_{0}=(0,0)$
, that is,
$x_{G} \in B$
. Let
$\mathfrak {p}\in G$
with
$\mathfrak {p}\Vdash \dot {x}_{G} \in B$
. Note that for any
$\mathfrak {q} \leq \mathfrak {p}$
there is an
$\mathfrak {r} \leq \mathfrak {q}$
such that r contains two disjoint copies of p at an odd distance apart. We can, in fact, get r by placing three copies of q next to each other, since
$\operatorname{dom}(q)$
is a rectangle with an odd number of vertices on each side. This implies that there is a
$\mathfrak {q}\in G$
with
$\mathfrak {q}\leq \mathfrak {p}$
and such that q contains two disjoint copies of p an odd distance apart. Since
$x_{G}$
is minimal, there is
$N\in \mathbb {N}$
such that for all
$g\in \mathbb {Z}^{2}$
there is a
$\tau \in \mathbb {Z}^{2}$
with
$\|\tau \|\leq N$
such that
$\tau \cdot (g\cdot x_{G})\in U_{q}$
, where
$U_{q}$
is the basic open set in
$2^{\mathbb {Z}^{2}}$
determined by q. We may assume N is greater than the maximum dimension of
$\operatorname{dom}(q)$
. Fix any
$y\in [x_{G}]$
. Fix
$\tau $
with
$\|\tau \|\leq N$
such that
$\tau \cdot y\in U_{q}$
. In particular
$\tau \cdot y\in U_{p}$
. Let
$h\in O$
be such that
$\|h\|\leq N$
and
$h\cdot (\tau \cdot y)\in U_{p}$
. Since
$\tau \cdot y$
and
$h\cdot (\tau \cdot y)$
are also generic, they are both in B. One of
$\| \tau \|$
,
$\| h +\tau \|$
is odd so we are done, letting T be all elements of O of norm
$\leq 2N$
.
Alternate proof of Theorem 6.8.
We will make use of Fact 2.6. Consider the canonical action of
$\mathbb {Z}^{2}$
on the inverse limit
$$ \begin{align*}X = \varprojlim \mathbb{Z}^{2} / (3^{n} \mathbb{Z})^{2} = \left\{f \in \prod_{n} \mathbb{Z}^{2} / (3^{n} \mathbb{Z})^{2} : \forall n \ \varphi_{n}(f(n+1)) = f(n)\right\},\end{align*} $$
where
$\varphi _{n} : \mathbb {Z}^{2} / (3^{n+1} \mathbb {Z})^{2} \rightarrow \mathbb {Z}^{2} / (3^{n} \mathbb {Z})^{2}$
is the canonical homomorphism. It is easy to see that X is compact and that the action is free, continuous, and minimal. Now fix a Borel complete section B. We must have that B is non-meager as otherwise
$X = \bigcup _{\gamma \in \mathbb {Z}^{2}} \gamma \cdot B$
would be meager. Consequently, there is a non-empty basic open set U such that B is comeager in U.
Since U is basic open, there is a finite partial function p with domain
$k \in \mathbb {N}$
such that
$U = \{f \in X : f \supseteq p\}$
. Hence,
$\bigcup _{\gamma \in T^{\prime }} \gamma \cdot U = X$
where
$$ \begin{align*}T^{\prime} = \{(n, m) \in \mathbb{Z}^{2} : 0 \leq n, m < 3^{k}\}.\end{align*} $$
Now fixing
$g = (3^{k}, 0)$
we have that
$g \cdot U = U$
and thus
$(\gamma + g) \cdot U = \gamma \cdot U$
for all
$\gamma \in \mathbb {Z}^{2}$
. Now setting
$$ \begin{align*}T = \{\gamma \in T^{\prime} : \|\gamma\| \text{ is odd}\} \cup \{\gamma + g : \gamma \in T^{\prime} \text{ and } \|\gamma\| \text{ is even}\},\end{align*} $$
we have that every element of T has odd length and
$\bigcup _{\gamma \in T} \gamma \cdot U = X$
. Now fix a point x in the comeager set
$X \setminus \bigcup _{\gamma \in \mathbb {Z}^{2}} \gamma \cdot (U \setminus B)$
. For any
$y \in [x]$
we have
$y \in X = \bigcup _{\gamma \in T} \gamma \cdot U$
and hence there is
$\gamma \in T$
with
$\gamma ^{-1} \cdot y \in U$
. Moreover, our choice of x implies that
$\gamma ^{-1} \cdot y \not \in U \setminus B$
. Hence
$\gamma ^{-1} \cdot y \in B$
as desired.
The next theorem is about Borel chromatic k-colorings of
$F(2^{\mathbb {Z}^{2}})$
. It says that there does not exists a Borel chromatic k-coloring f of
$F(2^{\mathbb {Z}^{2}})$
such that on every orbit there are arbitrarily large regions on which f induces a chromatic
$2$
-coloring.
Theorem 6.9. Suppose
$f \colon F(2^{\mathbb {Z}^{2}}) \to \{0,1,\dots ,k-1\}$
is a Borel function. Then there is an
$x \in F(2^{\mathbb {Z}^{2}})$
and an
$M \in \mathbb {N}$
such that if the map
$t \mapsto f(t \cdot x)$
is a chromatic
$2$
-coloring on
$[a,b]\times [c,d]$
, then
$\min \{ b-a, d-c\} \leq M$
.
Proof This follows easily by considering a generic
$x_{G}$
for
$\mathbb {P}_{omt}$
as in the proof of Theorem 6.8. Alternatively, we give the following proof using Fact 2.6.
Consider the natural action of
$\mathbb {Z}^{2}$
on the inverse limit
$X = \varprojlim \mathbb {Z}^{2} / (3^{n} \mathbb {Z})^{2}$
. Suppose
$f : X \rightarrow \{0, 1, \ldots , k-1\}$
is a Borel function. As
$X = \bigcup _{i=0}^{k-1} f^{-1}(i)$
, we can fix i so that
$B = f^{-1}(i)$
is non-meager. Let U be a non-empty basic open set such that B is comeager in U. Since U is basic open, there is
$n \in \mathbb {N}$
such that
$\gamma \cdot U = U$
for all
$\gamma \in (3^{n} \mathbb {Z})^{2}$
. By the Baire category theorem the set
$B^{\prime } = \bigcap _{\gamma \in (3^{n} \mathbb {Z})^{2}} \gamma \cdot B$
is comeager in U. Fix any
$x \in B^{\prime }$
and note that
$f(\gamma \cdot x) = i$
for all
$\gamma \in (3^{n} \mathbb {Z})^{2}$
. Set
$M = 2 \cdot 3^{n}$
and consider a rectangle
$[a, b] \times [c, d]$
with
$b-a, d-c> M$
. Then there is
$\gamma \in (3^{n} \mathbb {Z})^{2}$
with
$\gamma , \gamma + (3^{n},0) \in [a,b] \times [c,d]$
and hence
$f(\gamma \cdot x) = i = f((\gamma + (3^{n},0)) \cdot x)$
. Of course, since
$(3^{n}, 0)$
has odd length, any chromatic
$2$
-coloring of
$[a,b] \times [c,d]$
would have to assign them different colors. Therefore the restriction of f to
$\{g \cdot x \colon g \in [a,b] \times [c,d]\}$
cannot be a chromatic
$2$
-coloring.
7 Grid periodicity forcing
We introduce another variation of the minimal
$2$
-coloring forcing which will show that Borel complete sections in
$F(2^{\mathbb {Z}^{d}})$
must have orbits on which highly regular structure is exhibited. We will take
$d=2$
for the following arguments for simplicity, though the arguments in the general case are only notationally more complicated.
Definition 7.1. Let n be a positive integer. The grid periodicity forcing
$\mathbb {P}_{gp}(n)$
is defined as follows. A condition
$p \in \mathbb {P}_{gp}(n)$
is a function
$p\colon R\setminus \{ u\} \to \{ 0,1\}$
where
$R=[a,b]\times [c,d]$
is a rectangle in
$\mathbb {Z}^{2}$
with
$w=b-a+1$
,
$h=d-c+1$
both powers of n, and
$u\in R$
. We write
$R(p)$
,
$w(p)$
,
$h(p)$
,
$u(p)$
for the corresponding objects and parameters.
We define
$q \leq p$
iff
$R(q)$
is obtained by a rectangular tiling by copies of
$R(p)$
and if
$c \in R(q)$
is in the copy
$R(p)+t$
and
$c-t\neq u(p)$
, then
$q(c)=p(c-t)$
. Also,
$u(q)$
must be equal to one of the copied translates of
$u(p)$
.
Figure 3 illustrates the extension relation for
$\mathbb {P}_{gp}$
.
The extension relation in the grid periodicity forcing
$\mathbb {P}_{gp}$
.
Lemma 7.2. Let
$x_{G}$
be generic for
$\mathbb {P}_{gp}$
. Then
$x_{G}$
is a minimal
$2$
-coloring.
Proof (sketch)
To see
$x_{G}$
is a
$2$
-coloring, fix
$s \in \mathbb {Z}^{2}\setminus \{ (0,0)\}$
. The set
$$ \begin{align*} D_{s}=\{ p\in\mathbb{P}_{gp}\colon \exists g\in\operatorname{dom}(p)\ (g+s\in \operatorname{dom}(p)\text{ and } p(g)\neq p(g+s))\} \end{align*} $$
is easily dense in
$\mathbb {P}_{gp}$
. Let
$p \in D_{s}\cap G$
, and say
$R(p)$
has dimensions
$w\times h$
. Let
$g_{0}\in \operatorname{dom}(p)$
be such that
$g_{0}+s\in \operatorname{dom}(p)$
and
$p(g_{0})\neq p(g_{0}+s)$
. Note that
$x_{G}$
is periodic with period
$(w,h)$
except for the points of the form
$u(p)+(aw,bh)$
. From this it follows that the
$2$
-coloring property for s is witnessed for
$x_{G}$
by the set
$T=[-N,N]\times [-N,N]$
where
$N=\max \{ w,h\}$
.
The proof that
$x_{G}$
is minimal is a similar easy argument.
Since
$x_{G}$
is a minimal
$2$
-coloring, we certainly have that
$x_{G}$
is not periodic, that is,
$x_{G} \in F(2^{\mathbb {Z}^{2}})$
. However,
$x_{G}$
satisfies some weak form of periodicity as the next lemma shows.
Lemma 7.3. Let
$x_{G}$
be a generic real for
$\mathbb {P}_{gp}(n)$
.
-
(i) For any vertical or horizontal line
$\ell $
in
$\mathbb {Z}^{2}$
,
$x_{G} \restriction \ell $
is periodic with period a power of n. -
(ii) For any finite
$A \subseteq \mathbb {Z}^{2}$
, there is a lattice
$L = (w \mathbb {Z}) \times (h \mathbb {Z})$
, with both w and h powers of n, and there is
$u \in \mathbb {Z}^{2} \setminus (A + L)$
such that
$x_{G}$
is constant on
$k + L$
whenever
$k + L \neq u + L$
.
Proof (ii) Given A and
$p\in \mathbb {P}_{gp}$
, there is a
$q \leq p$
with
$A \subseteq R(q) \setminus \{u(q)\}$
. Let
$q \in G$
be such a condition, and let
$w,h$
be the dimensions of
$R(q)$
. Let
$L=L(q)$
be the lattice
$w\mathbb {Z} \times h \mathbb {Z}$
. By the
$(w,h)$
periodicity of
$x_{G}$
off of
$u(q)+L$
, this L and
$u=u(q)$
work.
(i) Given any vertical or horizontal line
$\ell $
in
$\mathbb {Z}^{2}$
, the set of
$p\in \mathbb {P}_{gp}$
with
$\ell \cap (u(p) + L(p))=\varnothing $
is dense. This implies that
$x_{G} \restriction \ell $
has a period
$n^{k}$
for some k.
As an application of grid periodicity forcing we now have the following structure theorem for Borel complete sections of
$F(2^{\mathbb {Z}^{2}})$
.
Theorem 7.4. Let
$B \subseteq F(2^{\mathbb {Z}^{2}})$
be a Borel complete section. Then there is an
$x \in F(2^{\mathbb {Z}^{2}})$
and a lattice
$L= k+\{ (iw,jh) \colon (i,j) \in \mathbb {Z}^{2}\}$
such that
$L\cdot x \subseteq B$
.
Proof Let
$x_{G}$
be a generic real for
$\mathbb {P}_{gp}$
. We claim that
$B \cap [x_{G}]$
contains a lattice as required. Since
$B \cap [x_{G}]\neq \varnothing $
, we may fix
$k \in \mathbb {Z}^{2}$
and
$q \in G$
such that
$q \Vdash (k \cdot {\dot {x}}_{G} \in B)$
. For any
$(i,j)\in \mathbb {Z}^{2}$
, let
$\pi _{i,j}$
be the translation defined by
$\pi _{i,j}(g)=g+(iw(q),jh(q))$
. Then
$\pi _{i,j}$
induces an automorphism of
$\mathbb {P}_{gp}$
and
$$ \begin{align*}\pi_{i,j}(q) \Vdash (\pi_{i,j}(k) \cdot {\dot{x}}_{G} \in B).\end{align*} $$
Note that
$\pi _{i,j}(k)\cdot {\dot {x}}_{G}= (k+(iw(p),jh(p)))\cdot {\dot {x}}_{G}$
. It suffices therefore to show that G contains the condition
$\pi _{i,j}(q)$
. By density, there is a
$p\leq q$
in G with
$R(p) \supseteq R(q) \cup R(\pi _{i,j}(q))$
. It is clear, however, from the definition of the extension relation that
$p\leq \pi _{i,j}(q)$
. Thus,
$\pi _{i,j}(q)\in G$
as well.
Alternate proof of Theorem 7.4.
We will make use of Fact 2.6. Consider the natural action of
$\mathbb {Z}^{2}$
on the inverse limit
$X = \varprojlim \mathbb {Z}^{2} / (3^{n} \mathbb {Z})^{2}$
. Fix a Borel complete section B. As
$\bigcup _{\gamma \in \mathbb {Z}^{2}} \gamma \cdot B = X$
, we must have that B is non-meager. So B is comeager in some non-empty basic open set U. Since U is basic open, there is
$k \in \mathbb {N}$
with
$\gamma \cdot U = U$
for all
$\gamma \in (3^{k} \mathbb {Z})^{2}$
. Hence, setting
$L = (3^{k} \mathbb {Z})^{2}$
, we have that there are comeager many
$x \in U$
with
$L \cdot x \subseteq B$
.
We mention that while Marks was visiting the authors, he used forcing methods to generalize the above theorem to all countable residually finite groups
$\Gamma $
[Reference Marks13].
The proof of Theorem 7.4 also gives the following variation of Theorem 7.4.
Theorem 7.5. Let
$f \colon F(2^{\mathbb {Z}^{2}}) \to \mathbb {N}$
be Borel. Then there is an
$x \in F(2^{\mathbb {Z}^{2}})$
and a lattice
$L \subseteq \mathbb {Z}^{2}$
such that the map
$s \mapsto f(s \cdot x)$
is constant on L.
Considering the characteristic function of the Borel set B gives:
Corollary 7.6. If
$B \subseteq F(2^{\mathbb {Z}^{2}})$
is Borel, then there is an
$x \in F(2^{\mathbb {Z}^{2}})$
such that either
$\{ s \colon s\cdot x \in B\}$
or
$\{ s \colon s\cdot x \in 2^{\mathbb {Z}^{2}}\setminus B\}$
contains a lattice L in
$\mathbb {Z}^{2}$
.
Acknowledgement
We thank the referee for showing us the alternate proofs using Theorem 2.1 and allowing us to include them here. Research of SG and SJ was supported in part by NSF grants DMS-1201290 and DMS-1800323. Research of EK was supported in part by NSF RTG grant DMS-0943870. BS was supported in part by NSF Graduate Student Research Fellowship DGE 0718128 and NSF RTG grant 1045119.
