Vitali covering lemma

In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian mathematician Giuseppe Vitali.^[1] The theorem states that it is possible to cover, up to a Lebesgue-negligible set, a given subset E  of R^d by a disjoint family extracted from a Vitali covering of E.

Vitali covering lemma

On the top: a collection of balls; the green balls are on the disjoint subcollection. On the bottom: the subcollection with three times the radius covers all the balls.

Statement of the lemma

• Finite version: Let $B_{1}, \ldots, B_{n}$ be any finite collection of balls contained in d-dimensional Euclidean space R^d (or, more generally, in an arbitrary metric space). Then there exists a subcollection $B_{j_{1}}, B_{j_{2}}, \dots, B_{j_{m}}$ of these balls which are disjoint and satisfy

$B_{1}\cup B_{2}\cup\ldots \cup B_{n}\subseteq 3B_{j_{1}}\cup 3B_{j_{2}}\cup\ldots \cup 3B_{j_{m}}$

where $3B_{j_{k}}$ denotes the ball with the same center as $B_{j_{k}}$ but with three times the radius.

• Infinite version: Let $\{B_{j}:j\in J\}$ be an arbitrary collection of balls in R^d (or, more generally, in a metric space) such that

$\sup \, \{ \mathrm{rad}(B_j) : j \in J \} <\infty$

where $\mathrm{rad}(B_j)$ denotes the radius of the ball B_j. Then there exists a countable subcollection

$\{B_j:j\in J'\}, \quad J'\subset J$

of balls from the original collection which are disjoint and satisfy

$\bigcup_{j\in J} B_{j}\subseteq \bigcup_{j\in J'} 5\,B_{j}.$

Comments.

• The balls can have the form B = {y : d(y, c) < r} (an open ball with center c and radius r) or B = {y : d(y, c) ≤ r}. Then 3 B (or 5 B) denotes the ball of the same form, with 3 r (or 5 r) replacing r. Notice that the definition of balls requires r > 0.
• In the infinite version, the collection of balls can be countable or uncountable.
• 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.

Proof

Finite version

With no loss of generality, we assume that the collection of balls is not empty; that is, n > 0. Let $B_{j_1}$ be the ball of largest radius. Inductively, assume that $B_{j_1},\dots,B_{j_k}$ have been chosen. If there is some ball in $B_1,\dots,B_n$ that is disjoint from $B_{j_1}\cup B_{j_2}\cup\cdots\cup B_{j_k}$, let $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 $X:=\bigcup_{k=1}^m 3\,B_{j_k}$. It remains to show that $B_i\subset X$ for every $i=1,2,\dots,n$. This is clear if $i\in\{j_1,\dots,j_m\}$. Otherwise, there necessarily is some $k\in\{1,\dots,m\}$ such that B_i intersects $B_{j_k}$ and the radius of $B_{j_k}$ is at least as large as that of B_i. The triangle inequality then easily implies that $B_i\subset 3\,B_{j_k}\subset X$, as needed. This completes the proof of the finite version.

Infinite version

Let F denote the collection of all balls B_j, j ∈ J, that are given in the statement of the covering lemma. The following result provides a certain disjoint subcollection G of F. If this subcollection G is described as $\{ B_j, j \in J'\}$, the property of G, stated below, readily proves that

$\bigcup_{j\in J} B_j \subseteq \bigcup_{j \in J'} 5\,B_{j}.$

Precise form of the covering lemma. Let  F be a collection of (nondegenerate) balls in a metric space, with bounded radii. There exists a disjoint subcollection  G of  F with the following property:

every ball B in  F intersects a ball C in  G such that B ⊂ 5 C.

(Degenerate balls only contain the center; they are excluded from this discussion.)
Let R  be the supremum of the radii of balls in F. Consider the partition of F into subcollections F_n, n ≥ 0, consisting of 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₀. Assuming that G₀,...,G_n have been selected, let

$\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 \ldots \cup \mathbf{G}_n \},$

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

$\mathbf{G} := \bigcup_{n=0}^\infty \mathbf{G}_n$

of F satisfies the requirements: G is a disjoint collection, and every ball B ∈ F intersects a ball C ∈ G such that B ⊂ 5 C.
Indeed, let 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  has radius > 2⁻ⁿ⁻¹R. Since the radius of B  is ≤ 2⁻ⁿR, it is less than twice that of C  and the conclusion B ⊂ 5 C  follows from the triangle inequality as in the finite version.^[2]

Remarks

• 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.
• In the most general case of an arbitrary metric space, the selection of a maximal disjoint subcollection requires a form of Zorn's lemma.
• 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]

Applications and method of use

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, $\lambda_d$, of a set E ⊂ R^d, which we know is contained in the union of a certain collection of balls $\{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 $\{B_{j}:j\in J'\}$ which is disjoint and such that $\bigcup_{j\in J'}5 B_j\supset \bigcup_{j\in J} B_j\supset E$. Therefore,

$\lambda_d(E)\leq \lambda_d \Bigl( \bigcup_{j\in J}B_{j} \Bigr) \leq \lambda_d \Bigl( \bigcup_{j\in J'}5B_{j} \Bigr)\leq \sum_{j\in J'} \lambda_d(5 B_{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

$\sum_{j\in J'} \lambda_d(5B_{j}) = 5^d \sum_{j\in J'} \lambda_d(B_{j})$

and thus

$\lambda_d(E) \leq 5^{d} \sum_{j\in J'}\lambda_d(B_{j}).$

Vitali covering theorem

In the covering theorem, the aim is to cover, up to  a "negligible set", a given set E ⊆ R^d by a disjoint subcollection extracted from a Vitali covering for E : a Vitali class or Vitali covering $\mathcal{V}$ for E  is a collection of sets such that, for every x ∈ E  and δ > 0, there is a set U  in the collection $\mathcal{V}$ such that x ∈ U  and the diameter of U  is non-zero and less than δ.

In the classical setting of Vitali,^[1] the negligible set is a Lebesgue negligible set, but measures other than the Lebesgue measure, and spaces other than R^d have also been considered, as is shown in the relevant section below.

The following observation is useful: if $\mathcal{V}$ is a Vitali covering for E  and if E  is contained in an open set Ω ⊆ R^d, then the subcollection of sets U  in $\mathcal{V}$ that are contained in Ω  is also a Vitali covering for E.

Vitali's covering theorem for the Lebesgue measure

The next covering theorem for the Lebesgue measure λ_d is due to Lebesgue (1910). A collection $\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

$\mathrm{diam}(V)^d \le C \, \lambda_d(V)$

for every set V  in the collection $\mathcal{V}$.
The family of cubes is an example of regular family $\mathcal{V}$, as is the family $\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 $\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 $\{U_{j}\}\subseteq \mathcal{V}$ such that

$\lambda_d \Bigl( E \setminus \bigcup_{j}U_{j} \Bigr) = 0.$

The original result of Vitali (1908) is a special case of this theorem, in which d = 1 and $\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]

Vitali's covering theorem for the Hausdorff measure

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 $\mathcal{V}$ a Vitali class of closed sets for E. Then there exists a (finite or countably infinite) disjoint subcollection $\{U_{j}\}\subseteq \mathcal{V}$ such that either

$H^{s} \left( E\backslash \bigcup_{j}U_{j} \right)=0 \ \mbox{ or }\sum_{j} \mathrm{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

$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 $\{U_{j}\}$ is regular and contained in a measurable region B  with finite Lebesgue measure, then

$\sum_j \mathrm{diam}(U_j)^d \le C \sum_j \lambda_d(U_j) \le 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.

From the covering lemma to the covering theorem

The covering lemma can be used as intermediate step in the proof of the following basic form of the Vitali covering theorem. Actually, a little more is needed, namely the precised form of the covering lemma obtained in the "proof of the infinite version".

Theorem. For every subset E of  R^d and every Vitali cover of E by a collection  F of closed balls, there exists a disjoint subcollection  G which covers E up to a Lebesgue-negligible set.

Without loss of generality, one can assume that all balls in F are nondegenerate and have radius ≤ 1. By the precised form of the covering lemma, there exists a disjoint subcollection 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 G  denote the subcollection of those balls in G that meet B(r). Consider the partition of G  into sets G_n, n ≥ 0, consisting of balls that have radius in (2⁻ⁿ⁻¹, 2⁻ⁿ]. Any ball B  in F that meets B(r) is contained in B(r+2). It follows from the disjointness property of G that

$\sum \{ \lambda_d(C) : C \in G \} = \sum_{n=0}^\infty \Bigl(\sum \{ \lambda_d(C) : C \in G_n \} \Bigr) \le \lambda_d(B(r+2)) < +\infty.$

This implies that G_n is a finite set for every n. Given ε > 0, we may select N  such that

$\sum \{ \lambda_d(C) : C \in G_n, \, n > N \} < \varepsilon.$

Let z ∈ Z  be fixed. By definition of Z, this point z does not belong to the closed set K  equal to the (finite) union of balls in G_k, k ≤ N. 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  meets C  and is included in 5 C  for some ball C ∈ G. One sees that C ∈ G  because C  intersects B(r), but C  does not belong to any family G_k, k ≤ N, since B  meets C  but is disjoint from K. This proves that every point z ∈ Z  is contained in the union of 5 C, when C  varies in G_n, n > N, hence

$Z \subset U_N := \bigcup \, \{ 5 \, C : C \in G_n, \, n > N \}$

and

$\lambda_d(U_N) \le \sum \{ \lambda_d(5 \, C) : C \in G_n, \, n > N \} = 5^d \sum \{ \lambda_d(C) : C \in G_n, \, n > N \} < 5^d \varepsilon.$

Since ε > 0 is arbitrary, this shows that Z  is negligible.^[7]

Infinite-dimensional spaces

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]

See also

• Besicovitch covering theorem

Notes

1. (Vitali 1908).
2. The proof given is based on (Evans & Gariepy 1992, section 1.5.1)
3. See the "From the covering lemma to the covering theorem" section of this entry.
4. See (Evans & Gariepy 1992).
5. Vitali (1908) allowed a negligible error.
6. (Falconer 1986).
7. The proof given is based on (Natanson 1955), with some notation taken from (Evans & Gariepy 1992).
8. (Preiss 1979).
9. (Tišer 2003).

References

• Evans, Lawrence C.; Gariepy, Ronald F. (1992), Measure Theory and Fine Properties of Functions, Studies in Advanced Mathematics, Boca Raton, FL: CRC Press, pp. viii+268, ISBN 0-8493-7157-0, MR 1158660, Zbl 0804.28001.
• Falconer, Kenneth J. (1986), The geometry of fractal sets, Cambridge Tracts in Mathematics 85, Cambridge: Cambridge University Press, pp. xiv+162, ISBN 0-521-25694-1, MR 867284, Zbl 0587.28004.
• Hazewinkel, Michiel, ed. (2001), "Vitali theorem", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Lebesgue, Henri (1910), "Sur l'intégration des fonctions discontinues", Annales scientifiques de l'Ecole Normale Supérieure 27: 361–450, JFM 41.0457.01
• Natanson, I. P (1955), Theory of functions of a real variable, New York: Frederick Ungar Publishing Co., p. 277, MR 0067952, Zbl 0064.29102.
• Preiss, David (1979), "Gaussian measures and covering theorems", Commentatione Mathematicae Universitatis Carolinae 20 (1): 95–99, ISSN 0010-2628, MR 526149, Zbl 0386.28015.
• Stein, Elias M.; Shakarchi, Rami (2005). Real analysis. Measure theory, integration, and Hilbert spaces. Princeton Lectures in Analysis, III. Princeton, NJ: Princeton University Press. pp. xx+402. ISBN 0-691-11386-6. MR 2129625. Zbl 1081.28001..
• Tišer, Jaroslav (2003), "Vitali covering theorem in Hilbert space", Transactions of the American Mathematical Society 355 (8): 3277–3289 (electronic), doi:10.1090/S0002-9947-03-03296-3, MR 1974687, Zbl 1042.28014
• Vitali, Giuseppe (1908) [17 December 1907], "Sui gruppi di punti e sulle funzioni di variabili reali", Atti dell'Accademia delle Scienze di Torino (in Italian) 43: 75–92, JFM 39.0101.05. (Title translation) "On groups of points and functions of real variables" is the paper containing the first proof of Vitali covering theorem.