Vitali covering lemma

Theorem (Finite Covering Lemma). Let ${\displaystyle B_{1},\dots ,B_{n}}$ be any finite collection of balls contained in an arbitrary metric space. Then there exists a subcollection ${\displaystyle B_{j_{1}},B_{j_{2}},\dots ,B_{j_{m}}}$ of these balls which are disjoint and satisfy

$${\displaystyle B_{1}\cup B_{2}\cup \dots \cup B_{n}\subseteq 3B_{j_{1}}\cup 3B_{j_{2}}\cup \dots \cup 3B_{j_{m}}.}$$

Proof: Without loss of generality, we assume that the collection of balls is not empty; that is, n > 0. Let ${\displaystyle B_{j_{1}}}$ be the ball of largest radius. Inductively, assume that ${\displaystyle B_{j_{1}},\dots ,B_{j_{k}}}$ have been chosen. If there is some ball in ${\displaystyle B_{1},\dots ,B_{n}}$ that is disjoint from ${\displaystyle B_{j_{1}}\cup B_{j_{2}}\cup \dots \cup B_{j_{k}}}$, let ${\displaystyle B_{j_{k+1}}}$ be such ball with maximal radius (breaking ties arbitrarily), otherwise, we set m := k and terminate the inductive definition.

Now set ${\textstyle X:=\bigcup _{k=1}^{m}3\,B_{j_{k}}}$. It remains to show that ${\displaystyle B_{i}\subset X}$ for every ${\displaystyle i=1,2,\dots ,n}$. This is clear if ${\displaystyle i\in \{j_{1},\dots ,j_{m}\}}$. Otherwise, there necessarily is some ${\displaystyle k\in \{1,\dots ,m\}}$ such that ${\displaystyle B_{i}}$ intersects ${\displaystyle B_{j_{k}}}$ and the radius of ${\displaystyle B_{j_{k}}}$ is at least as large as that of ${\displaystyle B_{i}}$. The triangle inequality then easily implies that ${\displaystyle B_{i}\subset 3\,B_{j_{k}}\subset X}$, as needed. This completes the proof of the finite version.

Theorem (Infinite Covering Lemma). Let ${\displaystyle \mathbf {F} }$ be an arbitrary collection of balls in a separable metric space such that

$${\displaystyle R:=\sup \,\{\mathrm {rad} (B):B\in \mathbf {F} \}<\infty }$$

where ${\displaystyle \mathrm {rad} (B)}$ denotes the radius of the ball B. Then there exists a countable sub-collection ${\displaystyle \mathbf {G} \subset \mathbf {F} }$ such that the balls of ${\displaystyle \mathbf {G} }$ are pairwise disjoint, and satisfy

$${\displaystyle \bigcup _{B\in \mathbf {F} }B\subseteq \bigcup _{C\in \mathbf {G} }5\,C.}$$

And moreover, each ${\displaystyle B\in \mathbf {F} }$ intersects some ${\displaystyle C\in \mathbf {G} }$ with ${\displaystyle B\subset 5C}$.

Proof: Consider the partition of F into subcollections F_n, n ≥ 0, defined by

${\displaystyle \mathbf {F} _{n}=\{B\in \mathbf {F} :2^{-n-1}R<{\text{rad}}(B)\leq 2^{-n}R\}.}$

That is, ${\textstyle \mathbf {F} _{n}}$ consists of the balls B whose radius is in (2⁻ⁿ⁻¹R, 2⁻ⁿR]. A sequence G_n, with G_n ⊂ F_n, is defined inductively as follows. First, set H₀ = F₀ and let G₀ be a maximal disjoint subcollection of H₀ (such a subcollection exists by Zorn's lemma). Assuming that G₀,...,G_n have been selected, let

${\displaystyle \mathbf {H} _{n+1}=\{B\in \mathbf {F} _{n+1}:\ B\cap C=\emptyset ,\ \ \forall C\in \mathbf {G} _{0}\cup \mathbf {G} _{1}\cup \dots \cup \mathbf {G} _{n}\},}$

and let G_n+1 be a maximal disjoint subcollection of H_n+1. The subcollection

${\displaystyle \mathbf {G}$ :=\bigcup _{n=0}^{\infty }\mathbf {G} _{n}}

of F satisfies the requirements of the theorem: G is a disjoint collection, and is thus countable since the given metric space is separable. Moreover, every ball B ∈ F intersects a ball C ∈ G such that B ⊂ 5 C.
Indeed, if we are given some ${\displaystyle B\in \mathbf {F} }$, there must be some n be such that B belongs to F_n. Either B does not belong to H_n, which implies n > 0 and means that B intersects a ball from the union of G₀, ..., G_n−1, or B ∈ H_n and by maximality of G_n, B intersects a ball in G_n. In any case, B intersects a ball C that belongs to the union of G₀, ..., G_n. Such a ball C must have a radius larger than 2⁻ⁿ⁻¹R. Since the radius of B is less than or equal to 2⁻ⁿR, we can conclude by the triangle inequality that B ⊂ 5 C, as claimed. From this ${\displaystyle \bigcup _{B\in \mathbf {F} }B\subseteq \bigcup _{C\in \mathbf {G} }5\,C}$ immediately follows, completing the proof.[2]

Remarks

• In the infinite version, the initial collection of balls can be countable or uncountable. In a separable metric space, any pairwise disjoint collection of balls must be countable. In a non-separable space, the same argument shows a pairwise disjoint subfamily exists, but that family need not be countable.
• The result may fail if the radii are not bounded: consider the family of all balls centered at 0 in R^d; any disjoint subfamily consists of only one ball B, and 5 B does not contain all the balls in this family.
• The constant 5 is not optimal. If the scale c⁻ⁿ, c > 1, is used instead of 2⁻ⁿ for defining F_n, the final value is 1 + 2c instead of 5. Any constant larger than 3 gives a correct statement of the lemma, but not 3.
• Using a finer analysis, when the original collection F is a Vitali covering of a subset E of R^d, one shows that the subcollection G, defined in the above proof, covers E up to a Lebesgue-negligible set.[3]

An application of the Vitali lemma is in proving the Hardy–Littlewood maximal inequality. As in this proof, the Vitali lemma is frequently used when we are, for instance, considering the d-dimensional Lebesgue measure, ${\displaystyle \lambda _{d}}$, of a set E ⊂ R^d, which we know is contained in the union of a certain collection of balls ${\displaystyle \{B_{j}:j\in J\}}$, each of which has a measure we can more easily compute, or has a special property one would like to exploit. Hence, if we compute the measure of this union, we will have an upper bound on the measure of E. However, it is difficult to compute the measure of the union of all these balls if they overlap. By the Vitali lemma, we may choose a subcollection ${\displaystyle \left\{B_{j}:j\in J'\right\}}$ which is disjoint and such that ${\textstyle \bigcup _{j\in J'}5B_{j}\supset \bigcup _{j\in J}B_{j}\supset E}$. Therefore,

${\displaystyle \lambda _{d}(E)\leq \lambda _{d}{\biggl (}\bigcup _{j\in J}B_{j}{\biggr )}\leq \lambda _{d}{\biggl (}\bigcup _{j\in J'}5B_{j}{\biggr )}\leq \sum _{j\in J'}\lambda _{d}(5B_{j}).}$

Now, since increasing the radius of a d-dimensional ball by a factor of five increases its volume by a factor of 5^d, we know that

${\displaystyle \sum _{j\in J'}\lambda _{d}(5B_{j})=5^{d}\sum _{j\in J'}\lambda _{d}(B_{j})}$

and thus

${\displaystyle \lambda _{d}(E)\leq 5^{d}\sum _{j\in J'}\lambda _{d}(B_{j}).}$

The next covering theorem for the Lebesgue measure λ_d is due to Lebesgue (1910). A collection ${\displaystyle {\mathcal {V}}}$ of measurable subsets of R^d is a regular family (in the sense of Lebesgue) if there exists a constant C such that

${\displaystyle \operatorname {diam} (V)^{d}\leq C\,\lambda _{d}(V)}$

for every set V in the collection ${\displaystyle {\mathcal {V}}}$.
The family of cubes is an example of regular family ${\displaystyle {\mathcal {V}}}$, as is the family ${\displaystyle {\mathcal {V}}(m)}$ of rectangles in R² such that the ratio of sides stays between m⁻¹ and m, for some fixed m ≥ 1. If an arbitrary norm is given on R^d, the family of balls for the metric associated to the norm is another example. To the contrary, the family of all rectangles in R² is not regular.

Theorem —  Let E ⊆ R^d be a measurable set with finite Lebesgue measure, and let ${\displaystyle {\mathcal {V}}}$ be a regular family of closed subsets of R^d that is a Vitali covering for E. Then there exists a finite or countably infinite disjoint subcollection ${\displaystyle \{U_{j}\}\subseteq {\mathcal {V}}}$ such that

$${\displaystyle \lambda _{d}{\biggl (}E\setminus \bigcup _{j}U_{j}{\biggr )}=0.}$$

The original result of Vitali (1908) is a special case of this theorem, in which d = 1 and ${\displaystyle {\mathcal {V}}}$ is a collection of intervals that is a Vitali covering for a measurable subset E of the real line having finite measure.
The theorem above remains true without assuming that E has finite measure. This is obtained by applying the covering result in the finite measure case, for every integer n ≥ 0, to the portion of E contained in the open annulus Ω_n of points x such that n < |x| < n+1.[4]

A somewhat related covering theorem is the Besicovitch covering theorem. To each point a of a subset A ⊆ R^d, a Euclidean ball B(a, r_a) with center a and positive radius r_a is assigned. Then, as in the Vitali theorem, a subcollection of these balls is selected in order to cover A in a specific way. The main differences with the Vitali covering theorem are that on one hand, the disjointness requirement of Vitali is relaxed to the fact that the number N_x of the selected balls containing an arbitrary point x ∈ R^d is bounded by a constant B_d depending only upon the dimension d; on the other hand, the selected balls do cover the set A of all the given centers.[5]

One may have a similar objective when considering Hausdorff measure instead of Lebesgue measure. The following theorem applies in that case.[6]

Theorem —  Let H^s denote s-dimensional Hausdorff measure, let E ⊆ R^d be an H^s-measurable set and ${\displaystyle {\mathcal {V}}}$ a Vitali class of closed sets for E. Then there exists a (finite or countably infinite) disjoint subcollection ${\displaystyle \{U_{j}\}\subseteq {\mathcal {V}}}$ such that either

$${\displaystyle H^{s}\left(E\setminus \bigcup _{j}U_{j}\right)=0}$$

or

$${\displaystyle \sum _{j}\operatorname {diam} (U_{j})^{s}=\infty .}$$

Furthermore, if E has finite s-dimensional Hausdorff measure, then for any ε > 0, we may choose this subcollection {U_j} such that

${\displaystyle H^{s}(E)\leq \sum _{j}\mathrm {diam} (U_{j})^{s}+\varepsilon .}$

This theorem implies the result of Lebesgue given above. Indeed, when s = d, the Hausdorff measure H^s on R^d coincides with a multiple of the d-dimensional Lebesgue measure. If a disjoint collection ${\displaystyle \{U_{j}\}}$ is regular and contained in a measurable region B with finite Lebesgue measure, then

${\displaystyle \sum _{j}\operatorname {diam} (U_{j})^{d}\leq C\sum _{j}\lambda _{d}(U_{j})\leq C\,\lambda _{d}(B)<+\infty }$

which excludes the second possibility in the first assertion of the previous theorem. It follows that E is covered, up to a Lebesgue-negligible set, by the selected disjoint subcollection.

The covering lemma can be used as intermediate step in the proof of the following basic form of the Vitali covering theorem.

Proof: Without loss of generality, one can assume that all balls in F are nondegenerate and have radius less than or equal to 1. By the infinite form of the covering lemma, there exists a countable disjoint subcollection ${\displaystyle \mathbf {G} }$ of F such that every ball B ∈ F intersects a ball C ∈ G for which B ⊂ 5 C. Let r > 0 be given, and let Z denote the set of points z ∈ E that are not contained in any ball from G and belong to the open ball B(r) of radius r, centered at 0. It is enough to show that Z is Lebesgue-negligible, for every given r.

Let ${\displaystyle \mathbf {G} _{r}=\{C_{n}\}_{n}}$ denote the subcollection of those balls in G that meet B(r). Note that ${\displaystyle \mathbf {G} _{r}}$ may be finite or countably infinite. Let z ∈ Z be fixed. For each N, z does not belong to the closed set ${\displaystyle K=\bigcup _{n\leq N}C_{n}}$ by the definition of Z. But by the Vitali cover property, one can find a ball B ∈ F containing z, contained in B(r), and disjoint from K. By the property of G, the ball B intersects some ball ${\displaystyle C_{i}\in \mathbf {G} }$ and is contained in ${\displaystyle 5C_{i}}$. But because K and B are disjoint, we must have i > N. So ${\displaystyle z\in 5C_{i}}$ for some i > N, and therefore

${\displaystyle Z\subset \bigcup _{n>N}5C_{n}.}$

This gives for every N the inequality

${\displaystyle \lambda _{d}(Z)\leq \sum _{n>N}\lambda _{d}(5C_{n})=5^{d}\sum _{n>N}\lambda _{d}(C_{n}).}$

But since the balls of ${\displaystyle \mathbf {G} _{r}}$ are contained in B(r+2), and these balls are disjoint we see

${\displaystyle \sum _{n}\lambda _{d}(C_{n})<\infty .}$

Therefore, the term on the right side of the above inequality converges to 0 as N goes to infinity, which shows that Z is negligible as needed.[7]

The Vitali covering theorem is not valid in infinite-dimensional settings. The first result in this direction was given by David Preiss in 1979:[8] there exists a Gaussian measure γ on an (infinite-dimensional) separable Hilbert space H so that the Vitali covering theorem fails for (H, Borel(H), γ). This result was strengthened in 2003 by Jaroslav Tišer: the Vitali covering theorem in fact fails for every infinite-dimensional Gaussian measure on any (infinite-dimensional) separable Hilbert space.[9]