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<i<k or k<i<j, then I'_i should also be \emptyset.

Case 3: \max\{j,k\}<i. 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


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

2. Emmanuele DiBenedetto. Real analysis.