Vitali's covering lemma is a useful result in

analysis, specifically when one is addressing questions about

density. Suppose we are working in R

^{n}, n-

dimensional

Euclidean space, under

Lebesgue measure where we denote by |S| the

measure of a

subset S of R

^{n}. It's probably best to think of |S| as the volume of S. We have the following result:

**Vitali's Covering Lemma.** If U is an open set in R^{n} and c is a constant such that c < |U|, then there exist disjoint open balls B_{1}, ..., B_{N} contained in U such that

Σ_{1≤j≤N}|B_j| > 3^{-n}c.

This is one of those situations where the ideas in the proof end up being more useful than the result itself.

*Proof of Vitali's Covering Lemma.* Since we are considering R^{n} under the Lebesgue measure, we can get approximate |U| as well as we would like to by taking the measure of larger and larger compact (closed and bounded) subsets of U. Thus there is a compact subset K of U such that |K| > c. Since U is open, for every point x in U there is an open ball around x, say B_{x}, contained within U. Let C := {B_{x} : x ∈ U}. Now C forms an open cover of K and since K is compact, it has a finite subcover given, say, by the balls B_{x1}, ..., B_{xm} for some positive integer m. Let us take all these balls and put them in the set S. We now perform the following process:

1. If S is not empty, there is a ball of maximum radius in S. We shall take this ball and call it B_{j} where j-1 is the number of times we have already performed the process; if S is empty, stop.

2. Remove all the balls in S that intersect B_{j}.

So at step j, we are greedily picking a ball B_{j} of maximum radius in S out of those balls in S that do not intersect any of the previous balls B_{1}, ..., B_{j-1}. Since there were only finitely many balls in S when we started the above process, this algorithm must terminate and we end up with some collection of balls B_{1}, ..., B_{N}. Now, suppose B is some ball that was deleted from S at the j^{th} step. Then B had radius at most that of B_{j} and since B ∩ B_{j} ≠ ∅, we get that B is contained in the ball centered at the center of B_{j} of three times the radius of B_{j}, which we shall denote by 3B_{j}. Since S was a subcover for K before we started messing with it, we have that the balls 3B_{1}, ..., 3B_{N} also provide a cover for K.

Notice moreover that, by the nature of our algorithm, the balls B_{1}, ..., B_{N} are disjoint.

Now, since the balls 3B_{j} cover K, their union has measure at least that of K. As a result

Σ_{1≤j≤N}|3B_{j}| ≥ |K| > c.

But |3B_{j}| = 3^{n}|B_{j}| since that's how volume works. Therefore,

Σ_{1≤j≤N}3^{n}|B_{j}| > c,

and dividing by 3^{n} gives

Σ_{1≤j≤N}|B_{j}| > 3^{-n}c. QED.