Density and covering properties of intervals of R^{n}

Tamás Keleti

February 11, 2001

Abstract

The key result of this paper is the existence of functions ρ_{n}(h) for which whenever H is a (Lebesgue) measurable subset of the ndimensional unit cube I^{n} with measure |H| > h and R is a class of subintervals (n-dimensional axis-parallel rectangles) of I^{n} that covers H, then there exists an interval R ∈ R in which the density of H is greater than ρ_{n}(h); that is, |H∩R| ; |R| > ρ_{n}(h) ( = ( h ; 2n)^{n} ). We show how we can use this result for finding 4 points of a measurable subset of the unit square such that they are the vertices of an axis-parallel rectangle that has quite large intersection with the original set. We introduce and investigate density and covering properties of classes of subsets of R^{n}. As a consequence we get a covering property of the class of intervals of R^{n}: if R is a family of n-dimensional intervals with | ∪ R| < ∞ then there is a finite sequence R_{1}, …, R_{m} ∈ R such that | ∪_{k=1}^{m} R_{k}| ≥ (1 − ε)| ∪ R| and ∥ ∑_{k=1}^{m} χ_{R_{k}}∥_{q} ≤ C(n, q, ε)| ∪ R|^{1/q}.

1 Introduction

While the author was working on a modified problem of A. Carbery, the following question arose:

If a measurable subset of the unit square is covered by axis-parallel rectangles (contained in the unit square) such that its density is small in each rectangle, can we conclude that the set itself must have small measure?

First note that if we allow any (not necessary axis-parallel) rectangles then the answer is negative. Indeed, a closed subset of a Nikodym set (a set in the unit square with measure one such that for each point of the set there is a straight line intersecting the set only in that single point, see e. g. [6]) with measure 1 − ε can be easily covered by rectangles such that the density of the subset is less then ε in each rectangle.

1991 Mathematical Reviews Classification. Primary 28A75; Secondary 42B25.

However, as we shall prove (Theorem 2.1), for axis-parallel rectangles (even in n-dimension) the answer is affirmative. Then we can easily get a similar result for sets not necessarily in the unit cube (Theorem 2.5). Using this property of the intervals (the n-dimensional axis-parallel rectangles) of R^{n} - that we shall call the “minimal density property” or shortly MDP - we can also prove a covering property of the intervals of R^{n} (Theorem 2.6).

In Section 3 we present a result about the modified problem of A. Carbery (asked by I. Gyöngy) that motivated our investigation. Namely, we use the minimal density property of the axis-parallel rectangles to find an (axis-parallel) rectangle with vertices in a given set with large intersection with this set. For this we will also need a result for the original problem of A. Carbery.

In Section 4 we investigate the classes of subsets of R^{n} that have the minimal density property. We investigate how this property relates to some (old and new) covering properties. We show how we can improve some covering properties (the V_{q} property) for classes satisfying the MDP. Thus we can prove a strong covering property of the intervals of R^{n}.

Most of the measure theoretic results can be equivalently formulated as combinatorial ones, in the sense that the measurable sets and the intervals may be assumed to be finite unions of dyadic cubes and the coverings may be assumed to be finite. Nevertheless, the proof of our key result (Theorem 2.1) uses methods of analysis. We investigate a minimal operator analogue to the well known Hardy-Littlewood maximal operator (see e.g. [6] or [7]).

Notation 1.1 We denote by I^{n} the n-dimensional open unit cube; that is, I^{n} = (0, 1)×…×(0, 1). By an interval of R^{n} we mean an n-dimensional axisparallel open rectangle: the Cartesian product of n open (1-dimensional) intervals. We denote by I^{n} the class of intervals of R^{n} and by I_{0}^{n} the class of (n-dimensional) subintervals of I^{n}.

We denote the (Lebesgue) measure and the closure of a set A ⊂ R^{n} by |A| and A, resp. By the density of A in B (with |B| > 0) we mean |A∩B| ; |B|.

2 Intervals of R^{n}

Theorem 2.1 If H is a measurable subset of I^{n} with |H| > h and R is a class of intervals in I^{n} that covers H, then there exists an interval R ∈ R in which the density of H is greater than ( h ; 2n)^{n}; that is,

|H ∩ R| ; |R| > ( h ; 2n)^{n} .

Proof. We prove the statement by induction on n. Let n = 1. Take a finite subclass of R that intersects H in a set of measure greater than h. It is well known that from a finite class of intervals one can always select two subclasses of disjoint intervals such that the union of the selected intervals is the same as the union of the whole class. Then, in our case, at least one of the selected classes of disjoint intervals intersects H in a set of measure greater than h/2. Thus in at least one of these intervals the density of H must be greater than h/2.

Assume that the statement is true for n − 1. Since we can find a closed set H′ ⊂ H with |H′| > h we can assume that H is closed. Then we can cover every point of I^{n} \ H by an interval disjoint to H, thus we can assume that R covers the whole I^{n}.

Let

m(x_{1}, …, x_{n}) = inf {|H ∩ (x_{1} × T)| ; |T | : T ∈ I_{0}^{n−1}, (x_{2}, …, x_{n}) ∈ T } .

Standard arguments show (see e.g. [5]) the measurability of the function m : I^{n} → [0, 1].

Suppose that the density of H is at most b in every R ∈ R. Then we prove that

2b ≥ ∫_{I^{n}} m > 2 ( h ; 2n)^{n} ,

which clearly implies our statement.

• 2b ≥ ∫_{I^{n}} m

Fix x_{2}, …, x_{n} ∈ I. For a t ∈ I let K_{t} × T_{t} (K_{t} ∈ I_{0}^{1}, T_{t} ∈ I_{0}^{n−1}) be an interval in R that covers (t, x_{2}, …, x_{n}). By definition,

m(s, x_{2}, …, x_{n}) ≤ |H ∩ (s × T_{t})| ; |T_{t}| (for any s ∈ I).

Thus, integrating and using that the density of H in K_{t} ×T_{t} is at most b, we get

∫_{K_{t}} m(s, x_{2}, …, x_{n})ds ≤ |K_{t}||H ∩ (K_{t} × T_{t})| ; |K_{t} × T_{t}| ≤ |K_{t}|b.  (1)

The intervals K_{t} (t ∈ I) cover I, so, taking a finite class of intervals K_{t} that covers I except a set of measure at most ε and selecting two subclasses of disjoint intervals with the same union, we get intervals K_{t_{1}}, …, K_{t_{m}} that covers I except a set of measure at most ε such that every point is covered at most twice. From (1) we get

∑_{i=1}^{m} ∫_{K_{t_{i}}} m(s, x_{2}, …, x_{n})ds ≤ ∑_{i=1}^{m} |K_{t_{i}}|b.  (2)

Since the intervals K_{t_{1}}, …, K_{t_{m}} cover I except a set of measure at most ε and 0 ≤ m ≤ 1 we get that the left-hand side of (2) is at least ∫_{I} m(s, x_{2}, …, x_{n})ds − ε. On the other hand, every point is covered at most twice, so the right-hand side is at most 2b. Therefore we have ∫_{I} m(s, x_{2}, …, x_{n})ds ≤ 2b, which, integrated with respect to x_{2}, …, x_{n}, gives the inequality we wanted to prove.

• ∫_{I^{n}} m > 2 ( h ; 2n)^{n}

Let

A = {x ∈ H : m(x) < a} where a = (|H| ; 2n)^{n−1} = ( n−1 ; n|H| ; 2(n − 1))^{n−1}.

Fix x_{1} ∈ I. Let A^{x_{1}} = {(x_{2}, …, x_{n}) : (x_{1}, …, x_{n}) ∈ A}. By definition, any (x_{2}, …, x_{n}) ∈ A^{x_{1}} is covered by a T ∈ I_{0}^{n−1} with

|H ∩ (x_{1} × T)| ; |T | < a.

Since A ⊂ H it implies that A^{x_{1}} is covered by (n − 1-dimensional) intervals in which its density is less than a. By our induction assumption, this implies that |A^{x_{1}}| ≤ n−1 ; n|H|. Thus |A| ≤ n−1 ; n|H|, which implies that |H \ A| ≥ |H|/n. Using this, we get that

∫_{I^{n}} m ≥ ∫_{H\A} m ≥ ∫_{H\A} a = |H \ A|a ≥ |H| ; n (|H| ; 2n)^{n−1} > 2 ( h ; 2n)^{n} ,

which completes the proof.

Remark 2.2 Similar covering properties of intervals of the real line have been studied for very long time. The n = 1 case of Theorem 2.1 also follows from Youngs’ First Covering Lemma ([10], 2. Lemma) from 1910, which says that if each point of a compact subset of the real line is the left-hand end-point of at least one interval then we can find a finite number of these intervals, non-overlapping, such that the measure of the non-covered part of the closed set is smaller than any fixed positive number.

Remark 2.3 The method we used in this proof is similar to the method used in [5] but, instead of Hardy-Littlewood maximal operator, we used the corresponding minimal operator. In fact, in the same way as in the proof of Theorem 2.1, we can also get a (very weak-type) inequality for the minimal operator. Namely, denoting the minimal operator associated to I_{0}^{n} by m_{n} (that is, m_{n}f(x) = inf { 1 ; |R| ∫_{R} |f| : x ∈ R ∈ I_{0}^{n}} for any f ∈ L_{1}(I^{n})), we can

prove that ρ_{n} (∫_{{m_{n}f<b}} f) ≤ b for any f : I^{n} → I measurable function and b > 0. From this we can easily obtain that

∫_{{m_{n}f<b}} |f| ≤ 2n∥f∥_{∞}^{1− 1 ; n} b^{1 ; n}

for any f ∈ L_{∞}(I^{n}) and b > 0.

A similar notion of minimal operator was introduced in [3].

Notation 2.4 We shall call the function ( h ; 2n)^{n} (which appeared in Theorem 2.1) ρ_{n}(h).

Theorem 2.5 Suppose that H is a measurable subset of R^{n} with finite measure, R is a class of intervals of R^{n} that covers H and the density of H in ∪R is greater than h > 0. Then there exists an interval R ∈ R in which the density of H is greater than ρ_{n}(h); that is,

|H ∩ R| ; |R| > ρ_{n}(h) = ( h ; 2n)^{n} .

Proof. We can assume that R is finite since one can select a finite subclass R′ ⊂ R such that the density of H ∩ (∪R′) in ∪R′ is still greater than h.

It is known (see e.g. [6] p. 70) that if G is an open bounded subset of R^{n} and K is a compact set with positive measure then there is a disjoint sequence {K_{k}} of sets homothetic to K contained in G such that |G \ ∪_{k=1}^{∞}K_{k}| = 0.

Applying this for G = I^{n} and K = ∪R, we get the sequence {K_{k}} and homothecies ϕ_{k} : K → K_{k}. Let H_{k} = ϕ_{k}(H), R_{k} = ϕ_{k}(R). Then R^{∗} = ∪_{k=1}^{∞}R_{k} covers H^{∗} = ∪_{k=1}^{∞}H_{k}. Clearly |H^{∗}| = ∑ |H_{k}|, 1 = ∑ |K_{k}| and |H_{k}|/|K_{k}| = |H|/|K|, so |H^{∗}| = |H|/|K| > h.

Applying Theorem 2.1, we can select an R′ ∈ ∪_{k=1}^{∞}R_{k} in which the density of H^{∗} is greater than ρ_{n}(h). If R′ ∈ R_{k} then the density of H in R = ϕ_{k}^{−1}(R′) ∈ R is also greater than ρ_{n}(h).

Theorem 2.6 For each n ∈ N there is a function C_{n} : R^{+} → R^{+} such that for any R ⊂ I^{n} with | ∪ R| < ∞ and ε > 0 there exist R_{1}, …, R_{m} ∈ R for which

(i)  | ∪ R \ ∪_{k=1}^{m}R_{k}| ; | ∪ R| < ε

and

(ii)  ∑_{k=1}^{m} |R_{k}| ; | ∪ R| < C_{n}(ε).

Proof. Let

t = | ∪ R|, R_{δ} = {R ∈ R : |R| > δ} and H^{δ} = ∪R_{δ}.

Then ∪R = ∪_{δ>0}H^{δ}, so we can choose δ > 0 such that | ∪ R \ H^{δ}| < εt/2.

Let H_{1} = H^{δ}. Assume that k ≥ 1 and H_{k} ⊂ H^{δ} is already defined. Let a_{k} = |H_{k}|/(2t).

If a_{k} < ε/4 then let m = k − 1 and the procedure is finished.

Otherwise, applying Theorem 2.5 for the R^{δ} covering of H_{k}, we get R_{k} ∈ R^{δ} with

|R_{k} ∩ H_{k}| ; |R_{k}| > ρ_{n}(a_{k}).

Let H_{k+1} = H_{k} \ R_{k}.

We claim that this procedure finishes after a finite number of steps. Indeed, if a_{k} ≥ ε/4 for every k then

|R_{k} ∩ H_{k}| > ρ_{n}(ε/4)|R_{k}| > ρ_{n}(ε/4)δ,

which is impossible since the sets R_{k} ∩ H_{k} are disjoint subsets of a set with finite measure.

Since H_{m+1} = H^{δ} \∪_{k=1}^{m}R_{k}, a_{m+1} = |H_{m+1}|/(2t) < ε/4 and |∪R\H^{δ}| < εt/2 we get

| ∪ R \ ∪_{k=1}^{m}R_{k}| ; t < ε,

which means that (i) is satisfied.

Let

d_{k} = |R_{k} ∩ H_{k}| ; 2t (k = 1, …, m).

Then d_{k} = a_{k} − a_{k+1} and |R_{k}| ; 2t < d_{k} ; ρ_{n}(a_{k}). Thus

∑_{k=1}^{m} |R_{k}| ; 2t < ∑_{k=1}^{m} d_{k} ; ρ_{n}(a_{k}) = ∑_{k=1}^{m}(a_{k} − a_{k+1}) 1 ; ρ_{n}(a_{k}).

Since ρ_{n}(x) is increasing and a_{k} ≥ ε/4 the right-hand side is a lower estimate of the integral of the function min(1/ρ_{n}(x), 1/ρ_{n}(ε/4)) in the interval [a_{m+1}, a_{1}], so we get

∑_{k=1}^{m} |R_{k}| ; 2t <∫_{a_{m+1}}^{a_{1}} min ( 1 ; ρ_{n}(x), 1 ; ρ_{n}( ε ; 4)) dx < ε/4 ; ρ_{n}( ε ; 4) +∫_{ε/4}^{1/2} 1 ; ρ_{n}(x)dx = C_{n}(ε) ; 2.

Therefore (ii) is also satisfied.

Remark 2.7 Using that ρ_{n}(x) = (x/(2n))^{n}, the proof above gives C_{n}(ε) < n ; 4(n−1)(8n)^{n}(1/ε)^{n−1} for n ≥ 2. For n = 1, using the same argument as in the very first part of the proof of Theorem 2.1, we get C_{1} = 2.

Example 2.8 Let 0 < δ < 1 and let R be the class of axis-parallel unit squares with lower-left vertices on the segment {(x, y) : x + y = 0, −1 ≤ x ≤ 0}. Let H = {(x, y) : 0 ≤ x + y ≤ δ} ∩ ∪R. Then R covers H and we have |H| > δ and | ∪ R| = 3. Thus the density of H in ∪R is greater than δ/3 but its density is δ^{2}/2 = 4.5(δ/3)^{2} in any R ∈ R. Therefore Theorem 2.5 (and consequently Theorem 2.1) cannot be true with ρ′_{2}(h) = 4.5h^{2}, which means that only the constant can be improved in these results (for n = 2). (Slightly modifying this construction, we can also prove that no function greater than h^{2}/2 can be good either.)

One can check that if R_{1}, …, R_{m} ∈ R (where R is the same as above) then | ∪ R \ ∪_{k=1}^{m}R_{k}| > 1/m. Thus, whenever | ∪ R \ ∪_{k=1}^{m}R_{k}|/| ∪ R| < ε, we have m > 1 ; 3ε, hence (∑_{k=1}^{m} |R_{k}|)/| ∪ R| > 1 ; 9ε. Therefore Theorem 2.6 would not be true for C_{2}(ε) ≤ 1 ; 9ε. On the other hand, according to Remark 2.7, Theorem 2.6 holds for C_{2}(ε) = 128 ; ε.

In a similar way (taking n-dimensional axis-parallel cubes with “lowerleft” vertices on a not too small domain of the hyperplane {x_{1}+…+x_{n} = 0}) we can show that, in higher dimensions as well, we have the best possible exponents in the above mentioned results.

3 Application

Recently A. Carbery asked the following question:

For which functions a : [0, 1] → [0, 1] is it true that (*) if H is a measurable subset of I^{2} then one can always find 4 points

of H such that they are the vertices of a (2-dimensional) interval with area at least a(|H|)?

This question led I. Gyöngy to ask the following question:

For which functions f : [0, 1] → [0, 1] is it true that

(**) if H is a measurable subset of I^{2} then one can always find 4 points of H such that they are the vertices of a (2-dimensional) interval R such that |R ∩ H| ≥ f(|H|)?

Clearly it is more difficult to satisfy (**) then (*). However, we shall see that, using Theorem 2.1, it is easy to obtain a function satisfying (**) from a function that satisfies (*).

A. Carbery, M. Christ and J. Wright [1] proved that a(h) = ch^{2}/ log(1/h) (for a suitable c > 0 and h small enough) satisfies (*). For the sake of completeness, we sketch a proof of this result.

Proposition 3.1 If a measurable set H ⊂ I^{2} with measure u does not contain the 4 vertices of any interval with area at least v then we have

u^{2} ≤ 2v log 1 ; v + v^{2}.  (3)

Proof. Since there exists a closed subset of H with measure arbitrarily close to u we can assume that H is closed. Let H_{m} be the union of those closed squares of the regular m×m subdivision of I^{2} that intersect H. Only finitely many H_{m} can contain the 4 vertices of an interval with area at least v since otherwise, taking a subsequence in which all the 4 vertices converge, we would get an interval with area at least v and with vertices belonging to H. Let K_{m} be the set that we get by magnifying H_{m} with ratio m. Thus (for a fixed large m) K_{m} consists of at least m^{2}u (unit) squares and they form no (axis-parallel) rectangle with area at least m^{2}v.

Let k_{i} be the number of squares (of K_{m}) in the i-th row. Let P be the number of the horizontal square pairs; that is,

P = ∑_{i=1}^{m} \binom{k_{i}}{2} ≥ 1 2 \begin{matrix}(∑_{i=1}^{m} k_{i}) & 2 \\ m \end{matrix} − 1 2 ∑_{i=1}^{m} k_{i} ≥ 1 2m^{3}(u^{2} − o(1)).  (4)

The j-th and the j + i-th squares cannot be both in K_{m} in more than m^{2}v/i rows since otherwise K_{m} contains the vertices of a rectangle with area at least m^{2}v. Thus

P ≤ ∑_{i=1}^{m−1} ∑_{j=1}^{m−i} min(m, m^{2}v/i) = ∑_{i=1}^{[mv]}(m − i)m + ∑_{i=[mv]+1}^{m}(m − i)m^{2}v/i
= o(m^{3}) + mv(m − (mv/2))m + m^{3}v log(1/v) − (m − mv)m^{2}v
= m^{3}(v log(1/v) + v^{2}/2 + o(1))  (5)

Combining (4) and (5) and letting m tend to infinity, we get the inequality (3).

Corollary 3.2 The function a(u) = cu^{2}/ log(1/u) (if u ≤ δ < 1 and a(u) = a(δ) if u > δ) satisfies (*), where c > 0 depends on δ (and c → 1/4 as δ → 0).

Example 3.3 Let H_{m} be the union of the diagonal squares of the regular m × m subdivision of the unit square. Then clearly |H_{m}| = 1/m and each axis-parallel rectangle with vertices in H_{m} has area at most 1 ; m^{2} . Thus a function that satisfies (*) cannot be greater than u^{2}. It is unknown weather a(u) = cu^{2} satisfies (*) (for a sufficiently small c > 0).

Proposition 3.4 If the function a satisfies (*) then f(h) = ρ_{2}(h/2)a(h/2) satisfies (**), (where ρ_{2}(h) = h^{2}/16 is the function that appeared in Theorem 2.1 for n = 2).

Proof. Let H be a measurable subset of I^{2} with measure h and let

R = {R : R ∈ I_{0}^{2} : |R| ≥ a (h ; 2) and |R ∩ H| ; |R| < ρ_{2} (h ; 2)} .

Let H′ = H ∩ ∪R.

The class R covers H′ but the density of H is less than ρ_{2}(h/2) in any R ∈ R. Thus, by Theorem 2.1, we must have |H′| ≤ h/2. Hence |H \ H′| ≥ h/2, so, using that the function a satisfies (*), we can find an interval R with vertices in H \ H′ such that |R| ≥ a(h/2). Since R is not in R we get that |R∩H|/|R| ≥ ρ_{2}(h/2). Thus |R∩H| ≥ ρ_{2}(h/2)|R| ≥ ρ_{2}(h/2)a(h/2) = f(h).

Corollary 3.5 The function f(h) = c′h^{4}/ log(1/h) (if h ≤ δ < 1 and f(h) = f(δ) if h > δ) satisfies (**), where c′ depends only on δ.

Proof. It follows from Corollary 3.2 and Proposition 3.4.

Example 3.6 We use a construction of I. Reiman [9]. Let p be a prime number (or a power of a prime) and let a_{1}, …, a_{m} be the points and b_{1}, …, b_{m} be the lines of the (finite) projective plane of order p, where m = p^{2} + p + 1. We take H_{p} to be the union of open squares of the regular m×m subdivision of the unit square as follows: we take the square in the i-th row and j-th column if and only if a_{i} is on b_{j}. Then, using that two lines meet only in one point, we have that whenever 4 points of H_{p} are the vertices of an axisparallel rectangle R then the vertices must be in one row or in one column of the subdivision. On the other hand, each line contains p + 1 points and each point is on p + 1 lines, so we get that h = |H_{p}| = (p + 1)/m > m^{−1/2} and |H ∩ R| ≤ (p + 1)/m^{2} ≤ m^{−3/2} + m^{−2} < h^{3} + h^{4}. Therefore (**) does not hold for the function h^{3} + h^{4} ( ∼ h^{3} ).

Therefore the best exponent (or the infimum of the exponents) for functions satisfying (**) is in the interval [3,4]. This is the best we currently know.

Remark 3.7 All positive results of this section can be easily generalized to n-dimensional spaces: Instead of Proposition 3.1, with a similar counting argument, we can prove by induction that if H ⊂ I^{n}, |H| = u_{n} and H does not contain the 2^{n} vertices of any n-dimensional interval then we have u_{n} ≤

o (vn^{1 ; 2^{n−1}+α} ) (as v_{n} → 0) for any α > 0. Then we get that a_{n}(u) = c_{n}u^{2^{n−1}+α}

satisfies the n-dimensional version of (*) (for proper c_{n} > 0 depending only on n and α).

The proof of Proposition 3.4 clearly works in any dimension, hence the statement holds also in n-dimensions. Thus f_{n}(h) = c′_{n}h^{n+2^{n−1}+α} satisfies the n-dimensional version of (**).

However, it is considerably more difficult to construct examples showing that we cannot have much better results than the above mentioned. The natural n-dimensional generalization of Example 3.3 (e. g. the union of those cubes of the regular m×…×m subdivision of the unit cube for which the sum of the coordinates is divisible by m) shows only that a function satisfying the n-dimensional version of (*) cannot be greater than u^{n}. No natural generalization of Example 3.6 seems to be known.

By standard probabilistic method, it is easy to prove the following combinatorial result:

One can select O(m^{n−n/2^{n−1}}) points of the regular n-dimensional m × … × m lattice such that no 2^{n} of them are the vertices of an n-dimensional interval. Moreover, we can assume that we chose O(m^{n−1−n/2^{n−1}}) points of each n − 1-dimensional m × … × m sublattice.

Then, taking the union of the corresponding open cubes of a regular subdivision of the unit cube, we get a set H with measure O(1/m^{n/2^{n−1}}) such that if the vertices of an n-dimensional interval R are in H then |R| < 1/m and |R∩H| < O(1/m^{1+n/2^{n−1}}). Thus we get O(u^{2^{n−1}/n}) and O(u^{(2^{n−1}/n)+1}) functions that do not satisfy the n-dimensional versions of (*) and (**), respectively; which are still quite far from our positive results.

One possible way to obtain better examples is to show that, as Erdős [4] conjectured, one can also select O(m^{n−1/2^{n−1}}) points of the regular ndimensional m × … × m lattice such that no 2^{n} of them are the vertices of an n-dimensional interval.

Then we would have O(u^{2^{n−1}}) and O(u^{2^{n−1}+1}) functions that do not satisfy the n-dimensional versions of (*) and (**), respectively, which would be quite close to our positive results.

4 The minimal density property

Notation 4.1 We denote the L_{q} norm of a function f : R^{n} → R by ∥f∥_{q}; that is, ∥f∥_{q} = (∫_{R^{n}} |f|^{q})^{1/q}. The characteristic function of a set A ⊂ R^{n} is denoted by χ_{A}.

Definition 4.2 Let B be a class of nonempty open bounded subsets of R^{n} and 1 ≤ q ≤ ∞.

• We say that B has the minimal density property (MDP) if there exists a function ρ : R^{+} → R^{+} such that if H ⊂ R^{n} is measurable with finite measure, R ⊂ B covers H and the density of H in ∪R is d > 0 then one can find an R ∈ R in which the density of H is greater than ρ(d); that is,

|R ∩ H| ; |R| > ρ ( |H| ; | ∪ R|) .

• The class B is said to have the covering property V_{q} (see [2]) if there exist constants C < ∞ and c > 0 such that for any R ⊂ B with | ∪ R| < ∞ we can find R_{1}, …, R_{m} ∈ R such that

(i’) | ∪_{k=1}^{m} R_{k}| ≥ c | ∪ R| and (ii) ∥ ∑_{k=1}^{m} χ_{R_{k}}∥_{q} ≤ C | ∪ R|^{1/q}.

• We say that B has the complete covering property V_{q} (CV_{q}) if there exists a function C : R^{+} → R^{+} such that for any ε > 0 and R ⊂ B with | ∪ R| < ∞ we can find R_{1}, …, R_{m} ∈ R such that

(i) |∪_{k=1}^{m} R_{k}| ≥ (1−ε)|∪R| and (ii) ∥ ∑_{k=1}^{m} χ_{R_{k}}∥_{q} ≤ C(ε)|∪R|^{1/q}.

Remark 4.3 If R is a class of open sets with | ∪ R| < ∞ then for any ε_{1} > 0 there exists a finite subclass R′ ⊂ R such that |∪R′| ≥ (1−ε_{1})|∪R|. (Indeed, since R^{n} is hereditary Lindelöf, there exist R_{1}, R_{2}, … ∈ R such that ∪_{i}R_{i} = ∪R, hence lim_{N→∞} | ∪_{j=1}^{N} R_{j}| = | ∪_{i} R_{i}| = | ∪ R|.)

Therefore, if we want to prove any of the above mentioned properties, we can assume that R is finite.

Remark 4.4 Note that Theorem 2.5 and Theorem 2.6 state that I^{n} (the intervals of R^{n}) has the minimal density property and the CV_{1} property. In the proof of Theorem 2.6 we used only the minimal density property of I^{n}, so we proved that MDP implies CV_{1}.

Remark 4.5 If we also assume that each x ∈ R^{n} is contained in sets R ∈ B with arbitrarily small diameter then clearly B is a Busemann-Feller differentiation basis with B(x) = {R : x ∈ R ∈ B}.

It is a standard argument that the V_{1} property (which is clearly weaker than the CV_{1} property) of a B-F basis B implies that B differentiates the L_{∞} functions, which clearly implies the density property of the basis B. (In fact, as Busemann and Feller proved, differentiating L_{∞} is equivalent to the density property). Therefore the minimal density property implies the density property. On the other hand, as we proved the minimal density property of I^{n}, we have an alternative proof of Saks’ strong maximal theorem. (For these definitions and results see e. g. [6] or [7].)

Theorem 4.6

MDP ⇔ CV_{1}.

That is, for any class B of nonempty open bounded subsets of R^{n} the minimal density property and the CV_{1} property are equivalent.

Proof. According to Remark 4.4, it is enough to prove that CV_{1} ⇒ MDP.

Suppose that R ⊂ B covers the measurable H ⊂ R^{n} such that the density of H is d in ∪R but at most s in any R ∈ R.

Using the CV_{1} property of B for ε = d/2 = |H| ; 2|∪R| we get a sequence R_{1}, …, R_{n} ∈ R such that

(i)  | ∪ R \ ∪_{k=1}^{m}R_{k}| ≤ ε| ∪ R| = |H|/2

and

(ii)  ∑_{k=1}^{m} |R_{k}| ≤ C(d/2)| ∪ R|.

Since H ⊂ ∪R, (i) implies that |H ∩ (∪_{k=1}^{m}R_{k})| ≥ |H|/2. Thus, using that the density of H is at most s in each R_{k}, we get

|H| ; 2 ≤ |H ∩ (∪_{k=1}^{m}R_{k})| ≤ ∑_{k=1}^{m} |H ∩ R_{k}| ≤ s ∑_{k=1}^{m} |R_{k}| ≤ s C(d/2)| ∪ R|.

Therefore

s ≥ d/2 ; C(d/2),

which means that choosing ρ(d) < d ; 2C(d/2) we get the minimal density property of B.

Example 4.7 Let R consist of sets that are the union of an open disc and an open sector with the same centre and twice larger radius.

Then R is clearly a regular B-F base, so it has several standard nice properties (e.g. weak 1-1 property of the maximal operator, density property, it differentiates L_{1} functions).

However R does not have the minimal density property. Indeed, we can cover an annulus by sets of R (with the same centre and radius) such that the density of the annulus is arbitrary small in each set.

Therefore

1. The minimal density property is strictly stronger than the density property.

2. The minimal density property and the CV_{q} properties of a class cannot be proved by using only the standard methods (e.g. properties of the maximal operator).

Remark 4.8 It would be interesting to find a weak sufficient geometrical condition that guarantees the MDP. We could find (see [8]) a quite weak sufficient condition that includes for example the regular convex sets and also the star-shaped sets that contain a ball in their hub with radius at least a fixed constant times the diameter of the set. In fact, we could prove in [8] that this condition implies a Besicovitch type property, which is much stronger than the MDP (or even the CV_{∞} property), which shows that the condition is too strong.

Lemma 4.9 Let B be a class of nonempty bounded open subsets of R^{n} satisfying the minimal density property with the function ρ. Then for any ε > 0 from any sequence R_{1}, R_{2}, … ∈ B with | ∪_{i=1}^{∞} R_{i}| < ∞ one can select a finite subsequence R̃_{1}, …, R̃_{m} with the following properties:

(i)  | ∪_{k=1}^{m} R̃_{k}| ≥ (1 − ε)| ∪_{i=1}^{∞} R_{i}|  and

P_{1}^{ρ(ε)} :  |R̃_{k} \ ∪_{j<k}R̃_{j}| > ρ(ε)|R̃_{k}|  (k = 1, …, m).

Proof. We define the subsequence R̃_{k} by induction. If R̃_{1}, …, R̃_{k−1} is defined then let R̃_{k} be the first element of the sequence (R_{i}) for which the disjoint part property P_{1}^{ρ(ε)} is satisfied for k. If there is no such R_{i} then the procedure is finished and m = k − 1. Thus we get a finite or infinite subsequence (R̃_{k}).

The disjoint part property P_{1}^{ρ(ε)} is clearly satisfied for every k, so we have to prove only (i).

Let

H = ∪_{i=1}^{∞}R_{i} \ ∪_{k}R̃_{k}.

Suppose that x ∈ H. Then there exists an index l_{x} for which x ∈ R_{l_{x}}. Since R_{l_{x}} were not chosen in the subsequence (R̃_{k}) there exists a k_{x} for which

|R_{l_{x}} ∩ H| ≤ |R_{l_{x}} \ ∪_{j<k_{x}} R̃_{j}| ≤ ρ(ε)|R_{l_{x}}|.

Therefore H is covered by R = {R_{l_{x}} : x ∈ H} ⊂ B such that the density of H is at most ρ(ε) in each R ∈ R. Thus, by the minimal density property of B, the density of H in ∪R is less than ε. Therefore

ε > |H| ; | ∪_{x∈H} R_{l_{x}}| ≥ |H| ; | ∪_{i=1}^{∞} R_{i}| = | ∪_{i=1}^{∞} R_{i} \ ∪_{k}R̃_{k}| ; | ∪_{i=1}^{∞} R_{i}|.

Hence | ∪_{k} R̃_{k}| > (1 − ε)| ∪_{i=1}^{∞} R_{i}|, so, taking m large enough in the case when (R̃_{k}) is infinite, we can satisfy (i).

Notation 4.10 Let M_{B} denotes the maximal operator corresponding to B, that is

M_{B}(f)(x) = sup_{x∈R∈B} 1 ; |R| ∫_{R} |f| if x ∈ ∪B

and M_{B}(f)(x) = 0 otherwise.

Theorem 4.11 Let 1 < p ≤ ∞ and 1/p + 1/q = 1. If B has the minimal density property (or the equivalent CV_{1} property) and the maximal operator M_{B} is weak-(p, p) than B has the CV_{q} property as well.

Proof. Let R ⊂ B, | ∪ R| < ∞ and ε > 0. We can assume that R = {R_{1}, R_{2}, …}. Then, applying Lemma 4.9, we get a finite subsequence R̃_{1}, …, R̃_{m} satisfying (i) and P_{1}^{ρ(ε)}.

Therefore we only have to prove that the disjoint part property P_{1}^{ρ(ε)} and the weak type (p, p) property of the maximal operator M_{B} implies that

∥ ∑_{k=1}^{m} χR̃_{k}∥_{q} ≤ C(ε)| ∪ R|^{1/q}.

This is essentially proved in [2] in the proof of Proposition 1. (One should only replace 1/2 by ρ(ε) in that proof).

Corollary 4.12 If B has the MDP (or the equivalent CV_{1}) then

V_{q} ⇔ CV_{q} (1 ≤ q < ∞).

Proof. It is proved in [2] that the V_{q} property of B and the weak type (p, p) property of the maximal operator M_{B} are equivalent (if 1 ; p + 1 ; q = 1), (in fact, we need only the easy V_{q} ⇒ weak-(p, p) part of this result), hence the non-trivial V_{q} ⇒ CV_{q} implication follows from Theorem 4.11.

Corollary 4.13 The class I^{n} has the CV_{q} property for any 1 ≤ q < ∞; that is, for any n ∈ N, 1 ≤ q < ∞ and ε > 0 there exists a constant C(n, q, ε) such that if R is a family of n-dimensional intervals and | ∪ R| < ∞ then there is a finite sequence R_{1}, …, R_{m} ∈ R such that

(i) |∪_{k=1}^{m}R_{k}| ≥ (1−ε)|∪R| and (ii) ∥ ∑_{k=1}^{m} χ_{R_{k}}∥_{q} ≤ C(n, q, ε)|∪R|^{1/q}.

Remark 4.14 Taking a general Orlicz norm ∥.∥_{Φ} we can also define the V_{Φ} and CV_{Φ} properties by replacing in Definition 4.2 (ii) by ∥ ∑_{k=1}^{m} χ_{R_{k}}∥_{Φ} ≤ C∥χ_{∪R}∥_{Φ}. We do not know weather it is always true that if B has the MDP then V_{Φ} ⇔ CV_{Φ}.

Acknowledgment. I would like to thank Professors M. Laczkovich and D. Preiss for helpful discussions.

This research was, in part, supported by OTKA grant F 019468. Part of this research was done while the author was at the Mathematical Institute of the Hungarian Academy of Sciences. This note was completed while the author was visiting the University College London having a Royal Society/NATO Postdoctoral Fellowship award.

References

[1] A. Carbery, M. Christ and J. Wright, Multidimensional van der Corput and sublevel set estimates, preprint.

[2] A. Córdoba, R. Fefferman, A geometric proof for the strong maximal theorem, Ann. of Math. 102 (1975), 95-100.

[3] D. Cruz-Uribe, SFO and C. J. Neugebauer, The structure of the reverse Hölder classes, Trans. Amer. Math. Soc. 347 (1995), 2941-2960.

[4] P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183-190.

[5] M. de Guzmán, An inequality for the Hardy-Littlewood maximal operator with respect to a product of differentiation bases, Studia Math. 49 (1974), 185-194.

[6] M. de Guzmán, Differentiation of Integrals in R^{n}, Springer, Lecture Notes in Mathematics Vol. 481, Berlin, 1975.

[7] M. de Guzmán, Real Variable Methods in Fourier Analysis, North-Holland, Mathematics Studies Vol. 46, Amsterdam, 1981.

[8] T. Keleti, A covering property of some classes of sets in R^{n}, Acta Univ. Carol. Math. Phys. 39 (1998), 111-118.

[9] I. Reiman, Über ein problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hung. 9 (1958), 269-273.

[10] W. H. Young and G. C. Young, On the existence of a differential coefficient, Proc. London Math. Soc., Ser. 2, 9 (1910), 325-335.

Department of Analysis, Eötvös Loránd University, Múzeum krt. 6-8, H-1088 Budapest, Hungary e-mail: elek@cs.elte.hu