## Tag Archives: covering lemma

### Covering Theorems of the Besicovitch Type

Given a set $E\subset \mathbb{R}^n$, we say $E$ has a Besicovitch covering $\mathcal{F}$ if $\forall\,x\in E$, there exists a cube(or a ball) $Q\in \mathcal{F}$, such that $x$ is the center of $B$.  In other word, we also say $\mathcal{F}$ covers $E$ in the sense of Besicovitch.

We will assume the element in $\mathcal{F}$ is cube $Q(x,\rho)$, which is the cube center at $x$ of edge-length $\rho$. When the covering consists of balls, the theorem still holds up to minor changes.

Thm 1(Besicovitch covering lemma)  Suppose $E\subset \mathbb{R}^n$ is a bounded set, $E$ has a Besicovitch covering $\mathcal{F}$. Then one can extract a sequence of cubes(balls) $\{Q(x_i,\,\rho_i)\}$(possibly finite or countable) such that

1). $E$ is covered by $\bigcup\limits_{i=1}^{\infty}Q(x_i,\rho_i)$.

2). Each point $x$ of $E$ is contained in at most $\theta(n)$ (a number only depends on the dimension $n$) cubes, i.e.  $1\leq\sum_i \chi_i(x)\leq \theta(n)$, where $\chi_i(x)$ is the characteristic function of $Q(x_i,\rho_i)$.

3). The sequence of $\{Q(x_i,\rho_i)\}$ can be classified in $\xi(n)$ families of cubes. That is there exists $\xi(n)$ subcollections of  $\displaystyle\{Q(x_i,\rho_i)\}$, namely $\mathcal{G}_1$,  $\mathcal{G}_2$,  $\cdots$,  $\mathcal{G}_{\xi(n)}$,  such that $\mathcal{G}_k$ consists of disjoint balls and  $\displaystyle\bigcup\limits_{i=1}^\infty Q(x_i,\rho_i)=\bigcup\limits_{j=1}^{\xi(n)}\mathcal{G}_j$.
In order to prove this theorem, let’s see a simpler version first. The idea of proving this theorem is embraced in the following simpler version.
Thm 2 Let $\{Q(0,\rho_k):k=1,2,\cdots\}$ be a decreasinf sequence of cubes centered at the origin of $\mathbb{R}^n$. Assume $E$ is a bounded set of $\mathbb{R}^n$, and $\forall\, x\in E$ we take a positive integer $k(x)$ and denote $Q(x)=Q(x,\rho_{k(x)})$. Then there exists a sequence $\{x_k\}\subset E$(possibly finte) such that:
1). $E$ is covered by $\displaystyle\bigcup\limits_{k=1}^{\infty}Q(x_k)$.

2). $1\leq\sum_k \chi_k(x)\leq 2^n$, where $\chi_k(x)$ is the characteristic function of $Q(x_k)$.

3). The sequence of $\{Q(x_k)\}$ can be classified in $4^n+1$ families of cubes. Each family consists of disjoint cubes.
$\mathbf{Proof:}$ Choose $\displaystyle x_1$ such that $Q(x_1)$ has the largest edge-length among all $Q(x)$, $x\in E$.
If $E-Q(x_1)=\emptyset$, we are done. Otherwise choose $\displaystyle x_2\in E-Q(x_1)$ such that $\displaystyle Q(x_2)$ has the largest edge-length.
Suppose we have choose $\displaystyle x_1,x_2,\cdots,x_m$.
If $\displaystyle E-\bigcup\limits_{i=1}^{m}Q(x_k)=\emptyset$, stop this process and we get a finite sequence of cubes. Otherwise choose $\displaystyle x_{m+1}\in E-\bigcup\limits_{i=1}^{m}Q(x_k)$ such that $\displaystyle Q(x_{m+1})$ has the largest edge-length. Now we can get a sequence of cubes $\{Q(x_k)\}$(possibly finite), which satisfies the following properties:

Satisfies the following properties:

$(i)$ $\forall\, i\neq j$, $x_j\not\in Q(x_i)$.
$(ii)$ $\forall\, i\neq j$, $\displaystyle \frac 12 Q(x_i)\cap \frac 12 Q(x_j)=\emptyset$. Here $\displaystyle \frac 12 Q(x)=Q(x,\frac 12\rho)$. Since $E$ is bounded, we can assume all these cubes are contained in a sufficently large cube. So if the sequence is infinite, we must have $\lim\limits_{k\to\infty}\rho(x_k)=0$.

Let’s consider the conclusion 1). If the sequence is finite, then $\exists\, m$ such that $\displaystyle E-\bigcup\limits_{k=1}^m Q(x_k)=\emptyset$, which means $E$ is covered by these cubes. If the sequence is infinite and $\exists\, x\in E-\bigcup\limits_{k=1}^\infty Q(x_k)$, then there exists $m$ such that $\rho(x_k)<\rho(x)$. This contradicts our principle of choosing points.
Consider conclusion 2). Take $\forall\, x\in E$, WLOG assume $x$ is the origin. There are $2^n$ hyper-quadrants in $\mathbb{R}^n$. At each hyper-quadrant, we can only have one cube centered at this hyper-quadrant and cover the origin at the same time. Otherwise the two cubes may contain one’s center which violates the property $(i)$.

Consider conclusion 3).
Claim: For every $k>0$, at most $4^n$ cubes in $\displaystyle \{Q(x_i):1\leq i\leq k-1\}$ intersect $Q(x_k)$.
pf: If a cube $Q(x_i), 1\leq i\leq k-1$ intersect $Q(x_k)$, then since $\rho(x_i)\geq \rho(x_k)$, $Q(x_i)$ must contain a vertex of $Q(x_k)$. Note that $Q(x_k)$ has at most $2^n$ vertices and each vertex is covered by at most $2^n$ cubes. We know that at most $4^n$ cubes in $\displaystyle \{Q(x_i):1\leq i\leq k-1\}$ intersect $Q(x_k)$.

Construct $\xi(n)=4^n+1$ subfamilies of cubes, namely $\mathcal{G}_1, \mathcal{G}_2,\cdots ,\mathcal{G}_{\xi(n)}$, by the following procedure: Firstly, allocate $Q(x_i)$ into $\mathcal{G}_i$, for $1\leq i\leq \xi(n)$. Consider $Q(x_k)$ when $k>\xi(n)$. If every $\mathcal{G}_i$ contains a cube intersect $Q(x_k)$, then this will contradict our previous claim. So at least there is one $\mathcal{G}_j$ contains balls all disjoint from $Q(x_k)$. We allocate $Q(x_k)$ into the one with the smallest index. Proceed this process inductively.
$\text{Q.E.D.}\hfill \square$

For the proof of theorem 1, we don’t have a decreasing family of cubes. So we have to adjust the principle of chosing points. At the same time $\theta(n)$ and $\xi(n)$ will be different from theorem 2.

$\mathbf{\text{Proof of Thm 1:}}$ Define $\rho(Q)$ be the edge-length of a cube $Q$. Let $a_0=\{\rho(Q):Q\in \mathcal{F}\}$.

If $a_0=\infty$, since $E$ is bounded, we can find a sufficiently large ball to cover $E$. Otherwise choose $Q_1=Q(x_1,\rho_1)$ such that $\rho_1>\frac 12 a_0$.

Suppose we have chosen $Q_1,Q_2,\cdots,Q_m$.

Let $\displaystyle a_m=\sup\{\rho():\text{the center of }Q\text{ lies in } E-\bigcup\limits_{i=1}^{m}Q_i\}$

choose one cube $Q_{m+1}=Q(x_m,\rho_{m+1})$ such that $\rho_{m+1}>\frac 12 a_m$ and $\displaystyle x_{m+1}\in E-\bigcup\limits_{i=1}^{m}Q_i$. Proceed this process inductively, then we can get a sequence of cubes $\{Q_i\}$ satisfy the following properties:

$(i)$ $\forall\, i>j$, $x_i\not\in Q_j$, $\rho_i>\frac 12 \rho_j$

$(ii)$ $\forall\, i\neq j$, $\frac 13 Q_i\cap\frac 13 Q_j=\emptyset$. Here $\frac 13 Q(x,\rho)=Q(x, \frac 13 \rho)$. For the same reason, $\displaystyle \lim\limits_{i\to\infty}\rho_i=0$.

Conclusion 1) holds for the same reason.

Consider conclusion 2). For simplicity, we only consider $n=2$, other dimension is the same. Choose $x\in E$, WLOG, assume $x$ is the origin. Let’s focus on the first quadrant.

Claim: There are at most 4 cubes in this sequence which can center at the first quadrant and cover the origin at the same time.

Pf: Let $A=\{Q\in\{Q_k\} : Q \text{ center the first quadrant and cover the origin}\}$, we can find the one with smallest index(namely the first one to choose) in $A$. WLOG, suppose it is $Q_1=Q_1(x_1,\rho_1)$. Consider four cubes in the first quadrant, let $\rho=\frac 12\rho_1$

$\displaystyle S_0=[0,\rho]\times[0,\rho], S_1=[\rho,2\rho]\times [0,\rho]$

$\displaystyle S_2=[\rho,2\rho]\times[\rho,2\rho], S_3=[0,\rho]\times[\rho,2\rho]$.

Then no cube in $A$ can center outside $S_0\cup S_1\cup S_2\cup S_3$. Otherwise that cube will have an edge-length bigger than $2\rho=\rho_1$.

Then no cube in $A$ can center at $S_0$, because $S_0\subset Q_1$. And there are at most one can center at $S_1, S_2,S_3$ respectively. In total $A$ contains no more than four cubes.

Since there are four quadrants in the plane, each one can have at most 4 cubes cover the origin, so origin can be covered by at most 16 cubes. In other dimensional case, $\theta(n)=2^n$.

Consider conclusion 3). Since $(i)$, we know that if $i>j$ and $Q_i\cap Q_j\neq \emptyset$, $Q_i$ must contain a vertex of $Q_j$ or a middle point of an edge of $Q_j$. There are $2^n+n2^{n-1}=\text{the number of edge of cube in }\mathbb{R}^n$ of them. So as proved before, we can find $\xi(n)$.
$\text{Q.E.D.}\hfill \square$

Special case: $n=1$

When the dimension is $n=1$, we can get the best constants $\theta=2$ and $\xi=2$. The proof is following:
$\mathbf{Proof:}$ Firstly we can find a sequence of intervals $\{I_i\}$(possibly finite) such that covers $E$ and their overlapping number is dominated by some constant $\theta=\theta(1)$.

Consider $I_1$, if $\displaystyle E\subset \bigcup\limits_{i=1}^{\infty}I_i-I_1$, then let $I'_1=\emptyset$, otherwise let $I'_1=I_1$.
Then consider $I_2$, if $\displaystyle E\subset I'_1\cup(\bigcup\limits_{i=2}^{\infty}I_i)-I_2$, set $I'_2=\emptyset$, otherwise let $I'_2=I_2$.
For $I_k$, if $\displaystyle E\subset (\bigcup\limits_{i=1}^{k-1}I'_i)\cup(\bigcup\limits_{i=k}^{\infty}I_i)-I_k$, set $I'_k=\emptyset$, otherwise let $I'_k=I_k$.

Proceed this procedure inductively. Finally we can get a new sequence $\{I'_i\}$.
Then  $\displaystyle E\subset \bigcup\limits_{i=1}^{\infty}I'_i$, because every point in $E$ is covered by finitely many intervals.

Suppoese there are $x\in E$ is covered by there intervals, for instance $I'_i$, $I'_j$, $I'_k$, which are all not emptysets. Then there must have an interval is covered by the other two one, say $I'_i$ is covered by $I'_j$ and $I'_k$.

Case 1: $i<\min\{j,k\}$, then $I'_i$ must be $\emptyset$ during the process.

Case 2: $j or $k, then $I'_i$ should also be $\emptyset$.

Case 3: $\max\{j,k\}. Since $I'_j$ and $I'_k$ are nonempty and cover $I'_i$, then $I'_i$ should also be $\emptyset$ at step $i$.

Contradiction. So $x\in E$ is covered by at most two intervals. So $\theta=2$.

For $\xi$, construct $\mathcal{G}_1$ and $\mathcal{G}_2$ by filling with intervals $I'_i\neq\emptyset$.

WLOG, assume $\displaystyle \{I'_i\}_{i=1}^\infty$ are all nonempty. Allocate $I'_1$ in to $\mathcal{G}_1$.

If $I'_2$ disjoint from $I'_1$ then allocate it in $\mathcal {G}_1$, otherwise in $\mathcal{G}_2$.

Suppose we have put $I'_{k-1}$, consider $I'_k$. If there are two intervals from $\mathcal{G}_1$ and $\mathcal{G}_2$ respectivly, say $I'_i$ and $I'_j$, such that $I'_k$ intersects them both. Then $I'_i$ and $I'_j$ must disjoint from each other, otherwise the overlapping number is at least 3. This contradicts our selection of $\{I'_i\}$. So $I'_i$ and $I'_j$ should be in the same $\mathcal{G}_i$. But this contradicts to the fact that these two intervals are from different $\mathcal{G}_i$. This means we can find an $\mathcal{G}_i, i=1\text{ or }2$ such that all the intervals in it are disjoint from $I'_k$. Then allocate $I'_k$ to this $\mathcal{G}_i$. Proceed this procedure inductively.

$\text{Q.E.D.}\hfill \square$

$\mathbf{Reference:}$

1. Miguel De Guzman, differentiation of integrals in R^n

2. Emmanuele DiBenedetto. Real analysis.