# A tiling property for actions of amenable groups along Tempelman Følner
sequences

Jonathan Boretsky  and  Jenna Zomback

###### Abstract.

We show that a certain tiling property (which directly implies the pointwise
ergodic theorem) holds for pmp actions of amenable groups along increasing
Tempelman Følner sequences, thus providing a short and combinatorial proof of
the corresponding pointwise ergodic theorem.

The first author conducted research through the summer research USRA program
at McGill University under the supervision of Marcin Sabok supported by NSERC
Discovery Grant RGPIN 2015-03738.

##  1\. Introduction

For a group $\Gamma$ acting on a probability space $X$ and a sequence
$(F_{n})$ of finite subsets of $\Gamma$, the pointwise ergodic property for
$\Gamma$ along $(F_{n})$ says that the action of $\Gamma$ is ergodic if and
only if for every $L^{1}$ function $f$ on $X$, the integral (the global
average) of $f$ over $X$ is equal to the limit of the averages of $f$ over
$F_{n}\cdot x$ (the pointwise average) for almost every $x\in X$. The
classical ergodic theorem, due to G. D. Birkhoff in 1931 [Bir], says that
probability measure preserving (pmp) actions of $\mathbb{Z}$ along the
sequence $[0,n)$ have the pointwise ergodic property. In 2001, E.
Lindenstrauss proved that actions of amenable groups along tempered Følner
sequences have the pointwise ergodic property [Lin].

A. Tserunyan in [Tse] gives a short, combinatorial proof of the classical
pointwise ergodic theorem (for $\mathbb{Z}$) by reducing it to showing that
the following tiling property holds for pmp actions of $\Gamma=\mathbb{Z}$
along the intervals $F_{n}=[0,n)$:

######  Definition 1 (Tiling Property).

We say that a pmp action of a countable group $\Gamma$ on a standard
probability space $(X,\mu)$ has the tiling property along a sequence $(F_{n})$
of finite subsets of $\Gamma$ if for any pointwise increasing sequence of
measurable functions $\ell_{n}:X\to\mathbb{N}$, $n\in\mathbb{N}$, and
$\epsilon>0$, there are arbitrarily large finite subsets $T\subseteq\Gamma$
such that for a set of points $x$ of measure at least $(1-\epsilon)$, $T\cdot
x$ can be covered up to $\epsilon$ fraction by disjoint sets of the form
$F_{\ell_{i}(y)}\cdot y$ (where $T\cdot x$ and $F_{\ell_{i}(y)}\cdot y$ are
treated as multisets if the action of $\Gamma$ is not free).

It is also implicit in [Tse] that the tiling property implies the pointwise
ergodic theorem for any pmp group action (see Section 3 for a proof). This
implication distills out the analytic part from the proofs of pointwise
ergodic theorems, reducing them to combinatorial (finitary) tiling problems.
Another proof of the ergodic theorem for $\mathbb{Z}$ revolving around the
same idea was given in [Keane-Petersen:ergodic_thm].

In this paper, we prove that the tiling property holds for pmp actions of
amenable groups along increasing Tempelman Følner sequences $(F_{n})$ by
finding Vitali covers with Følner tiles on multiple scales. As a consequence,
we prove the corresponding pointwise ergodic theorem:

######  Theorem 2 (Pointwise ergodic).

Fix a pmp action of an amenable group $\Gamma$ on a standard probability space
$(X,\mu)$ and an increasing Tempelman Følner sequence $(F_{n})$. Then the
action of $\Gamma$ on $X$ is ergodic if and only if for every $f\in
L^{1}(X,\mu)$,

$\lim_{n}A_{f}[F_{n}\cdot x]=\int_{X}f(x)d\mu(x)\text{ a.e.}$

where $A_{f}[F_{n}\cdot
x]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{|F_{n}|}\sum_{\gamma\in
F_{n}}f(\gamma\cdot x)$.

Although this is less general than Lindenstrauss’s theorem, our proof is
shorter and offers the advantage that the methods used are more elementary and
finitary.

Many people have shown this result for increasing Tempelman Følner sequences.
The shortest proof of Theorem 2 that the authors are aware of is given in
[OW], which uses a Vitali covering lemma along with basic functional analysis:
a function $f\in L^{1}(X,\mu)$ is approximated by functions for which the
ergodic theorem holds trivially, and the error is controlled by applying the
Vitali covering lemma. Other proofs include [Eme] and [Tem], which also use a
Vitali covering lemma along with analysis. However, none of these proofs yield
the tiling property described above, and hence they do not take advantage of
the abstract implication of the corresponding pointwise ergodic theorem.

### A word on the proof of the tiling property

Compared to [Tse], the tiling property is much harder to establish for general
increasing Tempelman Følner sequences. For example, tiling $\mathbb{Z}^{d}$
with boxes of different given sizes for each center is harder than tiling
$\mathbb{Z}$ with intervals. The key idea in mitigating this difficulty is to
iterate the Vitali covering lemma to find covers on multiple scales. We
essentially zoom very far out, cover some constant fraction of the space with
large sets (this fraction comes from the Tempelman condition and is
independent of how far we’ve zoomed out), and then zoom in on the spots we
miss, and fill those in as best we can with smaller sets, and so on and so
forth. Since we cover a constant fraction on each scale, if we zoom out far
enough at the beginning, once we zoom all the way back in, we will have
covered nearly the whole space.

### Organization

In Section 2, we provide the necessary definitions and notation that will be
used throughout the paper. In Section 3, we give an explicit proof, due to
Tserunyan, that Definition 1 implies the pointwise ergodic property for any
pmp group action. In Section 4, we establish the tiling property for pmp
actions of amenable groups along increasing Tempelman Følner sequences, which
then directly implies the corresponding pointwise ergodic property.

######  Acknowledgements.

The authors would like to thank their advisors, Marcin Sabok and Anush
Tserunyan, for their guidance, suggestions, and support. Many thanks as well
to Benjamin Weiss for pointing out the proof of Theorem 2 given in [OW], and
to Alexander Kechris for useful suggestions.

##  2\. Definitions and notation

Let $(X,\mu)$ be a standard probability space, and a function
$f:X\rightarrow\mathbb{R}$. For a finite set $A\subseteq X$, define the
average of $f$ over $A$,
$A_{f}[A]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{|A|}\sum_{x\in
A}f(x)$. For a finite equivalence relation $F$ on $X$, define
$A_{f}[F](x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=A_{f}[[x]_{F}]$.
Given a group $\Gamma$ and a finite set $R$, define the $R$-boundary of a set
$S$, denoted $\partial_{R}S$, to be the set of points $s$ for which $Rs\cap
S\neq\emptyset$ and $R_{s}\cap S^{c}\neq\emptyset$.

A sequence $(F_{n})_{n\in\mathbb{N}}$ of finite subsets of $\Gamma$ is a
Følner sequence if $\Gamma=\bigcup_{n}F_{n}$ and
$\lim_{n}\frac{|\partial_{R}F_{n}|}{|F_{n}|}=0$ for all finite sets $R$. A
group $\Gamma$ is called amenable if it admits a Følner sequence. For this
paper, we will assume that our Følner sequences are increasing.

Given a Følner sequence $(F_{n})$, we say $(F_{n})$ is tempered if there is
some natural number $C$ such that for all $n$,

$\left|\bigcup_{k<n}F_{k}^{-1}F_{n}\right|\leq C|F_{n}|$

and Tempelman if there is $C$ such that for all $n$,

$\left|\bigcup_{k\leq n}F_{k}^{-1}F_{n}\right|\leq C|F_{n}|$

in the latter case, we’ll call the smallest such $C$ the Tempelman constant of
$(F_{n})$. Note that any Tempelman Følner sequence is tempered.

Every amenable group has a tempered Følner sequence (in fact, every Følner
sequence has a tempered subsequence). In [Lin]*Example 4.2, an example is
given of an amenable group without a Tempelman Følner sequence. However,
[Hoc]*Theorem 3.4 gives a sufficient condition for the existence of a
Tempelman Følner sequence:

######  Theorem 3 (Hochman 2007).

If for a countable, abelian, amenable group $G$, we have

$r(G)=\sup\\{n\in\mathbb{N}:G\text{ contains a subgroup isomorphic to
}\mathbb{Z}^{n}\\}<\infty$

then $G$ possesses at least one Tempelman Følner sequence.

##  3\. The tiling property implies the pointwise ergodic theorem

The following result is implicitly stated in [Tse] and was explained by
Tserunyan to the second author.

######  Theorem 4 (Tserunyan).

Assume $\Gamma$ has the tiling property along a sequence of finite subsets
$(F_{n})$. Then for any pmp action of $\Gamma$ on a standard probability space
$(X,\mu)$, the action of $\Gamma$ on $X$ is ergodic if and only if for every
$f\in L^{1}(X,\mu)$,

$\lim_{n}A_{f}[F_{n}\cdot x]=\int_{X}f(x)d\mu(x)\text{ a.e.}$

where $A_{f}[F_{n}\cdot
x]\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{|F_{n}|}\sum_{\gamma\in
F_{n}}f(\gamma\cdot x)$.

###### Proof.

By replacing $f$ with $f-\int f$, we may assume without loss of generality
that $\int f=0$. We will show that
${f}^{*}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\limsup_{n\to\infty}A_{f}[F_{n}\cdot
x]\leq 0$ a.e., and an analogous argument shows
${f}_{*}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\liminf_{n\to\infty}A_{f}[F_{n}\cdot
x]\geq 0$ a.e.

Since ${f}^{*}$ is $T$-invariant, ergodicity implies that it is some constant
$C$ almost everywhere. Assume by way of contradiction that $C>c>0$. Define
$\ell_{i}:X\to\mathbb{N}$ by $x\mapsto$ the $i^{\text{th}}$ $n\in\mathbb{N}$
such that $A_{f}[F_{n}x]>c$ (equivalently, $A_{f-c}[F_{n}x]>0$).

Fix $\delta>0$ small enough so that for any measurable $Y\subseteq X$,
$\mu(Y)<\delta$ implies $\int_{Y}(f-c)\,d\mu>-\frac{c}{3}$, and let
$M\in\mathbb{N}$ be large enough so that the set
$Y\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=f^{-1}(-M,\infty)$
has measure at least $1-\delta$.

The tiling property applied to the function $\ell_{i}$ with
$\varepsilon\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{1}{2(M+c)}\frac{c}{3}$
gives a finite $T\subseteq\Gamma$ such that $\mu(Z)\geq 1-\varepsilon$, where
$Z$ is the set of all $x\in X$ such that at least $1-\varepsilon$ fraction of
$T\cdot x$ is partitioned into sets of the form $\ell_{i}(y)\cdot y$.

######  Claim.

For each $x\in Z$, $A_{\mathbb{1}_{Y}(f-c)}[T\cdot x]\geq-(M+c)\varepsilon$.

######  Proof of Claim 1.

By the definition of $Z$, on a subset $B\subseteq T\cdot x$ that occupies at
least $1-\varepsilon$ fraction of $T\cdot x$, the average of $f-c$ is
positive, and hence that of
$\mathbb{1}_{Y}(f-c)\mathord{\downharpoonright_{B}}$ is non-negative. On the
remaining set $T\cdot x\setminus B$, the function $\mathbb{1}_{Y}(f-c)$ is at
least $-(M+c)$, by the definition of $Y$. Thus, the average of
$\mathbb{1}_{Y}(f-c)$ on the entire $T\cdot x$ is at least
$-(M+c)\varepsilon$.

Now we compute using this claim and the invariance of $\mu$:

$\displaystyle\int_{Y}(f-c)\,d\mu$
$\displaystyle=\int_{X}A_{\mathbb{1}_{Y}(f-c)}[T\cdot x]\,d\mu(x)$
$\displaystyle=\int_{Z}A_{\mathbb{1}_{Y}(f-c)}[T\cdot
x]\,d\mu(x)+\int_{X\setminus Z}A_{\mathbb{1}_{Y}(f-c)}[T\cdot x]\,d\mu(x)$
$\displaystyle\geq-(M+c)\varepsilon-(M+c)\varepsilon=-2(M+c)\varepsilon=-\frac{c}{3}.$

This gives a contradiction:

$\displaystyle 0=\int_{X}f\,d\mu$ $\displaystyle=c+\int_{X}(f-c)\,d\mu$
$\displaystyle=c+\int_{Y}(f-c)\,d\mu+\int_{X\setminus Y}(f-c)\,d\mu$
$\displaystyle>c-\frac{c}{3}-\frac{c}{3}>0.\qed$

##  4\. The tiling property for increasing Tempelman Følner sequences

In this section, we prove the following:

######  Lemma 5.

The tiling property holds for pmp actions of amenable groups along increasing
Tempelman Følner sequences.

As a corollary, by Theorem 4, we obtain Theorem 2. In order to prove this
lemma, we need a Vitali covering lemma. For the rest of this section, fix an
amenable group $\Gamma$ and Tempelman Følner sequence $F_{i}$ with Tempelman
constant $C$, standard probability space $(X,\mu)$ on which $\Gamma$ acts in a
pmp way, and $\epsilon>0$.

######  Lemma 6 (Vitali covering).

Given a function $l:X\rightarrow N$ and a finite subset $S\subseteq X$, there
exists a set $K$, which is a disjoint union of sets of the form $F_{l(x)}x$,
$x\in S$, such that $|K|\geq\frac{1}{C}|S\cup K|$.

###### Proof.

Put $=S=\\{x_{1},...,x_{n}\\}$, $D_{0}=K_{0}=\emptyset$. We will inductively
define increasing sets $K_{i}$ and $D_{i}$ for $i\leq n$ until $S\setminus
D_{i}=\emptyset$. Assume $S\setminus D_{i}\neq\emptyset$. Let $t=\max_{x\in
S\setminus{D_{i}}}l(x)$, and let $j$ be least such that $x_{j}\in S\setminus
D_{i}$ and $l(x_{j})=t$. Put
$K_{i+1}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=K_{i}\cup
F_{t}x_{j}$ and
$D_{i+1}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D_{i}\cup
F_{t}^{-1}F_{T}\cdot x_{j}$. Iterate this (up to $n$ times) until $S\setminus
D_{m}=\emptyset$ for some $m\leq n$. Put
$K\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=K_{m}$ and
$D\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=D_{m}$.

We claim that the selected $F_{T}\cdot x_{j}$ are actually pairwise disjoint.
If not, suppose that at the $(i+1)^{\text{th}}$ step there is some $y\in
F_{T}\cdot x_{j}\cap K_{i}$. Then $x_{j}\in F_{t}^{-1}y$. But since $y\in
K_{i}$, there is some $t^{\prime}\geq t$ and $j^{\prime}$ such that $y\in
F_{t^{\prime}}x_{j^{\prime}}$. Hence $x_{j}\in
F_{t}^{-1}F_{t^{\prime}}x_{j^{\prime}}\subseteq
F_{t^{\prime}}^{-1}F_{t^{\prime}}x_{j^{\prime}}\subseteq D_{i}$, contradicting
our choice of $x_{j}$.

So at each step, we add exactly $|F_{t}|$ elements to $K$ and at most
$C|F_{t}|$ elements to $D$. Hence, $|K|\geq\frac{1}{C}|D|\geq\frac{1}{C}|S\cup
K|$ since $S\cup K\subseteq D$. ∎

Now we may begin proving Lemma 5. The idea is to break our space into large
finite sets. We will tile each of these finite sets with Følner shapes of
various sizes, using progressively smaller Følner shapes to fill in whatever
holes remain after placing the larger Følner shapes.

###### Proof of _Lemma 5_.

First, fix $r\in\mathbb{N}$ large enough so that
$\left(\frac{C-1}{C}\right)^{r}<\frac{\epsilon}{2}$. We will ultimately pick
$r$ many “good” sizes of tiles for a large fraction of the points in $X$. Fix
$r$ many functions $G_{i}:[0,1]\rightarrow\mathbb{R}$ such that
$G_{1}(x)\geq\frac{2}{C}(x)$ and for $i>1$,
$G_{i}(x)\geq\frac{C-1}{C}G_{i-1}(x)+(i+1)(x)$ where each $G_{i}$ is
continuous and $G_{i}(0)=0$. For example,
$G_{i}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\left(\frac{C-1}{C}\right)^{i}x+\sum_{k=1}^{i+1}kx$
is such a collection of functions. Fix $\alpha$ small enough so that
$\beta\leq\alpha\implies G_{r}(\beta)<\frac{\epsilon}{2}$. Put
$\eta\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\min(\alpha,\epsilon)$.

For each $p\in\mathbb{N}$, let
$C_{n}^{(p)}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{x\in
X:(\exists i\in\mathbb{N})\;l_{i}(x)\in[p,n]\\}$. Since the $l_{i}$ are
strictly increasing in $x$ for all $x$, $\bigcup_{n}C_{n}^{(p)}=X$. Hence,
there is some large enough $p^{*}$ such that
$\mu(C_{p^{*}}^{(p)})>1-\frac{\eta^{2}}{r}$. This means that for any $r$-many
values $p_{j}$ ($0\leq j<r$),

$\mu(\\{x\in X:(\forall j<r)\;(\exists
i\in\mathbb{N})\;l_{i}(x)\in[p_{j},p_{j}^{*}]\\})>1-\eta^{2}.$

We define two sequences of natural numbers of length $r$ as follows. Let
$L_{0}$ be large enough so that $\frac{|\partial_{F_{r}}F_{n}|}{|F_{n}|}<\eta$
for all $n>L_{0}$. For $i<r$, define
$R_{i}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=L_{i}^{*}$, and
$L_{i+1}>R_{i}$ large enough so that

$\frac{|\partial_{F_{R_{i}}}F_{n}|}{|F_{n}|}<\frac{\eta}{|F_{R_{i}}|}$

for all $n\geq L_{i+1}$. Put
$\delta\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\frac{\eta}{|F_{R_{r-1}}|}$.
We will think of the $[L_{j},R_{j}]$ as ranges of allowable sizes for out
tiles. Finally, Let $T\subseteq\Gamma$ satisfy
$\frac{|\partial_{F_{R_{r-1}}}T|}{|T|}<\delta$.

Define parial functions
$p_{i}(x)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=l_{j}(x)$
where $j$ is smallest such that $l_{j}(x)\in[L_{i},R_{i}]$ if such a $j$
exists. Set
$P\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\left\\{x\in
X:\;(\forall i<r)\;x\in\text{dom}(p_{i})\right\\}$. Hence,
$\mu(P)>1-\eta^{2}$, so $\mu(\left\\{x\in X:A_{\mathbb{1}_{P}}[T\cdot
x]<1-\eta\right\\})\leq\eta$, because otherwise, setting
$B\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\left\\{x\in
X:A_{\mathbb{1}_{P}}[T\cdot x]<1-\eta\right\\}$,

$\displaystyle 1-\eta^{2}<\mu(P)$
$\displaystyle=\int_{X}\mathbb{1}_{P}(x)d\mu(x)$ $\displaystyle[\text{by the
invariance of }\mu]$ $\displaystyle=\int_{X}\frac{1}{|T|}\sum_{\gamma\in
T}\mathbb{1}_{P}(\gamma\cdot x)d\mu(x)$
$\displaystyle=\int_{X}A_{\mathbb{1}_{P}}[T\cdot x]\;d\mu(x)$
$\displaystyle=\int_{X\setminus B}A_{\mathbb{1}_{P}}[T\cdot
x]\;d\mu(x)+\int_{B}A_{\mathbb{1}_{P}}[T\cdot x]\;d\mu(x)$
$\displaystyle\leq\mu(X\setminus B)+\mu(B)(1-\eta)$
$\displaystyle<1-\eta+\eta(1-\eta)=1-\eta^{2}$

Hence, at least $1-\eta$ fraction of points $x\in X$ have $1-\eta$ fraction of
points of $T\cdot x$ lying in $P$. Since $\eta\leq\epsilon$, it now suffices
to show that for a point $x$ such that at least $1-\eta$ fraction of $T\cdot
x$ is contained in $P$, we can tile $T\cdot x$ up to $\epsilon$ fraction with
tiles of the form $F_{l_{i}(x)}x$.

We claim that in $k$ steps, $1\leq k\leq r$, we can tile $T\cdot x$ up to
$\left(\frac{C-1}{C}\right)^{k}+G_{k}(\eta)$ fraction. As discussed earlier,
we will start by tiling with our largest Følner shapes, i.e.
$l_{i}(x)\in[L_{r},R_{r}]$, and in each step we will move down a size.

In step $k$, apply Lemma 6 with $l=p_{r-k}$ and

$S_{k}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\\{x\in T\cdot
x\cap\text{dom}(p_{r-k}):F_{R_{r-k}}x\text{ is contained in the set of
uncovered points in }T\\}$

so that the constructed set of tiles $K_{k}$ is contained in the set of
uncovered points in $T$.

See Fig. 1 for a sketch of the tiling process for $\mathbb{Z}^{2}$. In the
first picture, we place the tiles from $K_{1}$, and in the second picture we
remove strips along the boundaries of $T\cdot x$ as well as $K_{1}$. We also
mark the points $y$ and $z$ for which $p_{r-2}$ is not defined. Applying Lemma
6 to $S_{2}$ (the remaining points), we place smaller tiles, seen in a lighter
color in the third picture.

Figure 1. Identifying the set $S_{2}$ and placing the set of tiles $K_{2}$
when $\Gamma=\mathbb{Z}^{2}$

Now, $S_{k}$ is almost all of the uncovered points in $T$ except possibly:

  1. (1)

A small strip along the boundary of $T$, of size
$|\partial_{F_{R_{r-k}}}T||F_{R_{r-k}}|<\eta|T|$ since
$\frac{|\partial_{F_{R_{r-k}}}T|}{|T|}<\frac{\eta}{|F_{R_{r-}k}|}$.

  2. (2)

The set of points on which $p_{r-k}$ is not defined, which has fewer than
$\eta|T|$ points.

  3. (3)

A small strip along the boundary of the covered points from each of the
previous $k-1$ steps. Fix $j<k$, and consider the set $K_{j}$ of covered
points from the $j^{\text{th}}$ step. We might miss a strip of size
$|\partial_{F_{R_{r-k}}}K_{j}||F_{R_{r-k}}|$. Note that since the boundary of
$K_{j}$ consists of Følner shapes of sizes in $[L_{r-j},R_{r-j}]$, we have
$\frac{|\partial_{F_{R_{r-k}}}K_{j}|}{|K_{j}|}\leq\frac{|\partial_{F_{R_{r-j}}}F_{R_{r-j}}|}{|F_{R_{r-j}}|}$,
so

$\displaystyle|\partial_{F_{R_{r-k}}}K_{j}||F_{R_{r-k}}|$
$\displaystyle\leq\frac{|\partial_{F_{R_{r-j}}}F_{R_{r-j}}|}{|F_{R_{r-j}}|}|K_{j}||F_{R_{r-k}}|$
$\displaystyle\leq\frac{\eta}{|F_{R_{r-j-1}}|}|K_{j}||F_{R_{r-k}}|$
$\displaystyle\leq\eta|T|,$

where the penultimate inequality comes from our choice of $L_{r-j}$ to be
large enough that $n\geq L_{r-j}$ implies
$\frac{|\partial_{F_{R_{r-j}}}F_{n}|}{|F_{n}|}<\frac{\eta}{|F_{R_{r-j-1}}|}$,
and the final inequality comes from $K_{j}\subseteq T$ and the fact that
$r-k\leq r-j-1$ for any $j<k$.

In total, $S_{k}$ is missing at most $(k+1)\eta|T|$ uncovered points from $T$.
If $k=1$, we have that $K_{1}$ covers at least $\frac{1}{C}$ fraction of
$S_{1}\cup K_{1}$, and $|S_{1}\cup K_{1}|\geq(1-2\eta)|T|$. So $K_{1}$ covers
at least $\frac{1}{C}(1-2\eta)|T|$, and we are left with
$\frac{C-1+2\eta}{C}|T|$, so we cover all but $\frac{C-1}{C}+G_{1}(\eta)$
fraction of $|T|$.

If $k\geq 2$, assume $\bigcup_{i<k}K_{i}$ covers all but
$\left(\frac{C-1}{C}\right)^{k-1}+G_{k-1}(\eta)$ fraction of $T$. Notice that

$|S_{k}\cup
K_{k}|\leq\left(\left(\frac{C-1}{C}\right)^{k-1}+G_{k-1}(\eta)\right)|T|,$

since both $S_{k}$ and $K_{k}$ are contained in the set of uncovered points of
$T$. Since $K_{k}$ covers at least $\frac{1}{C}$ fraction of $|S_{k}\cup
K_{k}|$, at most $\frac{C-1}{C}$ fraction of $|S_{k}\cup K_{k}|$ is left
uncovered. So $\bigcup_{i\leq k}K_{k}$ covers all of $T$ but at most

$\displaystyle(k+1)\eta|T|+\frac{C-1}{C}|S_{k}\cup K_{k}|$
$\displaystyle\leq\left((k+1)\eta+\left(\frac{C-1}{C}\right)^{k}+\frac{C-1}{C}G_{k-1}(\eta)\right)|T|$
$\displaystyle\leq\left(\left(\frac{C-1}{C}\right)^{k}+G_{k}(\eta)\right)|T|$

many points. This concludes the proof of our claim. Iterate this algorithm $r$
times so that we have covered all but
$\left(\frac{C-1}{C}\right)^{r}+G_{r}(\eta)$ fraction of $T$. Since, by
hypothesis, both
$\left(\frac{C-1}{C}\right)^{r},G_{r}(\eta)<\frac{\epsilon}{2}$, this
concludes the proof. ∎

## References