RANDOM MARTINGALES AND LOCALIZATION OF MAXIMAL INEQUALITIES

ASSAF NAOR AND TERENCE TAO

Abstract. Let (X, d, μ) be a metric measure space. For ∅ ≠ R ⊆ (0, ∞) consider the Hardy-Littlewood maximal operator

M_{R}f(x) =^{def} sup_{r∈R} \frac{1}{μ(B(x, r))} ∫_{B(x,r)} |f| dμ.

We show that if there is an n > 1 such that one has the “microdoubling condition” μ (B (x, (1 + \frac{1}{n}) r)) ≲ μ (B(x, r)) for all x ∈ X and r > 0, then the weak (1, 1) norm of M_{R} has the following localization property:

∥M_{R}∥_{L_{1}(X)→L_{1,∞}(X)} ≍ sup_{r>0} ∥M_{R∩[r,nr]}∥_{L_{1}(X)→L_{1,∞}(X)} .

An immediate consequence is that if (X, d, μ) is Ahlfors-David n-regular then the weak (1, 1) norm of M_{R} is ≲ n log n, generalizing a result of Stein and Strömberg [47]. We show that this bound is sharp, by constructing a metric measure space (X, d, μ) that is Ahlfors-David n-regular, for which the weak (1, 1) norm of M_{(0,∞)} is ≳ n log n. The localization property of M_{R} is proved by assigning to each f ∈ L_{1}(X) a distribution over random martingales for which the associated (random) Doob maximal inequality controls the weak (1, 1) inequality for M_{R}.

Contents

1. Introduction 2 1.1. Microdoubling and the localization theorem 4 1.2. Weak (1, 1) norm bounds 5 1.3. Ultrametric approximations: deterministic and random 7 1.4. Lower bounds 8 1.5.1. Adding more hypotheses 9 1.6. The example of the infinite tree 10 2. Doob-type maximal inequalities 11 3. Localization of maximal inequalities 13 4. An argument of E. Lindenstrauss 19 5. The infinite tree 24 6. Sharpness 27 6.1. A preliminary construction 27 6.3. The doubling example 30 6.4. The Ahlfors-David regular example 34 References 39

1. Introduction

A metric measure space (X, d, μ) is a separable metric space (X, d), equipped with a Radon measure μ. We assume throughout the non-degeneracy property 0 < μ(B(x, r)) < ∞ for all r > 0, where B(x, r) =^{def} {y ∈ X : d(x, y) ⩽ r}. For any locally integrable f : X → ℂ, we can then define the Hardy-Littlewood maximal function

Mf(x) =^{def} sup_{r>0} \frac{1}{μ(B(x, r))} ∫_{B(x,r)} |f| dμ,

which is easily verified to be measurable.

We shall study the weak (1, 1) operator norm of M, defined as usual to be the least quantity 0 ⩽ ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩽ ∞ for which one has the distributional inequality

∥Mf∥_{L_{1,∞}(X)} ⩽ ∥M∥_{L_{1}(X)→L_{1,∞}(X)} · ∥f∥_{L_{1}(X)}  (1)

for all f ∈ L_{1}(X). Here L_{p}(X) (p ⩾ 1) denotes the usual Lebesgue space corresponding to the measure μ, and L_{p,∞}(X) is the weak L_{p} norm,

∥f∥_{L_{p,∞}(X)} =^{def} sup_{λ>0} λ · μ(|f| > λ)^{1/p}.

Analogously to (1), the strong (p, p) operator norm of M is defined as usual to be the least quantity 0 ⩽ ∥M∥_{L_{p}(X)→L_{p}(X)} ⩽ ∞ for which

∥Mf∥_{L_{p}(X)} ⩽ ∥M∥_{L_{p}(X)→L_{p}(X)} · ∥f∥_{L_{p}(X)}  (2)

for all f ∈ L_{p}(X).

In most cases of interest it is probably impossible to compute ∥M∥_{L_{1}(X)→L_{1,∞}(X)} exactly; notable exceptions to this statement are ultrametric spaces, where the weak (1, 1) norm of M equals 1 (we will return to the class of ultrametric spaces presently), and the real line ℝ, equipped with the usual metric and Lebesgue measure, where it was shown by Melas [34] that the weak (1, 1) norm of M equals \frac{11+\sqrt{61}}{12} (the case of the strong (p, p) norm of M, p > 1, when X = ℝ, remains open, but we refer to [20, 25] for some partial results).

In view of these difficulties, it seems more reasonable to ask for estimates on the asymptotic behavior of the various operator norms of maximal functions. Quite remarkably, despite the wide applicability of maximal inequalities, and significant effort by many researchers, even in the simple case when X is the n-dimensional Hilbert space ℓ_{2}^{n} and μ is Lebesgue measure, it is unknown whether or not the weak (1, 1) norm of M is bounded independently of the dimension n.

A classical application of the Vitali covering theorem (see for example [17, 46, 21, 27]) shows that for any n-dimensional normed space X, the weak (1, 1) and strong (p, p) norms of M grow at most exponentially in n. This was greatly improved by Stein and Strömberg [47] to ∥M∥_{L_{1}(X)→L_{1,∞}(X)} = O(n log n) for a general n-dimensional normed space, and to the slightly better bound ∥M∥_{L_{1}(ℓ_{2}^{n})→L_{1,∞}(ℓ_{2}^{n})} = O(n) for n-dimensional Hilbert space. Until recently, there was no known example of a sequence of n-dimensional normed spaces X_{n} for which ∥M∥_{L_{1}(X_{n})→L_{1,∞}(X_{n})} tends to ∞ with n. A recent breakthrough of Aldaz [1] showed that when X_{n} = ℓ_{∞}^{n}, i.e., ℝ^{n} equipped with the ℓ_{∞} norm (whose unit ball is an axis parallel cube), ∥M∥_{L_{1}(X_{n})→L_{1,∞}(X_{n})} must tend to ∞ with n; the best known lower bound [3] on ∥M∥_{L_{1}(ℓ_{∞}^{n})→L_{1,∞}(ℓ_{∞}^{n})} is (log n)^{1−o(1)}. The best known upper estimate for ∥M∥_{L_{1}(X)→L_{1,∞}(X)} when X = ℓ_{∞}^{n} remains the Stein-Strömberg O(n log n) bound.

As partial evidence that when X is the n-dimensional Euclidean space ℓ_{2}^{n}, the weak (1, 1) norm ∥M∥_{L_{1}(X)→L_{1,∞}(X)} might be bounded, we can take Stein’s theorem [45] (see also the appendix of [47]) which asserts that in the Euclidean case, for p > 1 we have ∥M∥_{L_{p}(X)→L_{p}(X)} ⩽ C(p), where C(p) < ∞ depends on p but not on n. For general ndimensional normed spaces, Stein and Strömberg [47] obtained the bound ∥M∥_{L_{p}(X)→L_{p}(X)} ⩽ c(p)n, while Bourgain [8, 9] and Carbery [13] proved that for any n-dimensional normed space, ∥M∥_{L_{p}(X)→L_{p}(X)} ⩽ C(p) < ∞ provided p > \frac{3}{2}. It is unknown whether or not there is some 1 < p < \frac{3}{2} for which there exist n-dimensional normed spaces X_{n} such that ∥M∥_{L_{p}(X_{n})→L_{p}(X_{n})} is unbounded. This is unknown even for the case of cube averages X_{n} = ℓ_{∞}^{n}. It was shown by Bourgain [10] that ∥M∥_{L_{p}(X)→L_{p}(X)} ⩽ C(p, q) for all p > 1 when X = ℓ_{q}^{n} and q is an even integer, and this was extended by Müller to X = ℓ_{q}^{n} for all 1 ⩽ q < ∞.

A dimension independent bound on ∥M∥_{L_{1}(ℓ_{2}^{n})→L_{1,∞}(ℓ_{2}^{n})} would mean that the classical Euclidean Hardy-Littlewood maximal inequality is in essence an infinite dimensional phenomenon. This statement is not quite true, since there is no “Lebesgue measure” on infinite dimensional Hilbert space, but nevertheless, even Stein’s dimension independent bound on ∥M∥_{L_{p}(ℓ_{2}^{n})→L_{p}(ℓ_{2}^{n})}, p > 1, has interesting infinite dimensional consequences—see for examples Tišer’s work [53] on differentiation of integrals with respect to certain Gaussian measures on Hilbert space (provided that the integrand is in L_{p} for some p > 1). Moreover, improved bounds on ∥M∥_{L_{1}(X)→L_{1,∞}(X)} are clearly of interest since they would yield improved quantitative estimates in the many known applications of the Hardy-Littlewood maximal inequality. As an example, such bounds are relevant for quantitative variants of Rademacher’s differentiation theorem for Lipschitz functions, which are used in results on the bi-Lipschitz distortion of discrete nets (see [11, 15]).

Bounds on ∥M∥_{L_{1}(X)→L_{1,∞}(X)} and ∥M∥_{L_{p}(X)→L_{p}(X)} have been also intensively investigated for metric measure spaces other than finite dimensional normed spaces. Strong (p, p) bounds for free groups (with counting measure) have been established by Nevo and Stein in [40]. In Section 5 we prove the corresponding weak (1, 1) inequality, which is nevertheless not sufficient for the purpose of ergodic theoretical applications as in [40]; see Conjecture 1 below for more information^{1}. In the case of the Heisenberg group ℍ^{2n+1}, equipped with either the Carnot-Carathéodory metric or the Koranyi norm (and the underlying measure being the Haar measure), dimension independent strong (p, p) bounds have been obtained by Zienkiewicz [56], and a weak (1, 1) bound of O(n) was obtained by Li [30]. It is unclear if these bounds generalize to other nilpotent Lie groups (though perhaps similar methods could apply to certain two step nilpotent Lie groups, by replacing the use of [41] in [56] with the results of [38, 23]).

The main result of the present paper implies a general bound for the weak (1, 1) norm of the Hardy-Littlewood maximal function on Ahlfors-David n-regular spaces; a class of metric measure spaces that contains the examples described above as special cases (except for the case of the free group, which is dealt with separately in Section 5). Specifically, assume that the metric measure space (X, d, μ) satisfies the growth bounds

1After presenting our work we learned from Michael Cowling that the weak (1, 1) inequality for the free group can be also deduced from the work of Rochberg and Taibleson [42]. Our combinatorial proof in Section 5 is different from the proof in [42], though it is similar to the proof in an unpublished manuscript of Cowling, Meda and Setti, which adapts arguments of Strömberg [48] in the case of the hyperbolic space.

We thank Michael Cowling and Lewis Bowen for showing us the Cowling-Meda-Setti manuscript.

∀x ∈ X ∀r > 0, r^{n} ⩽ μ (B(x, r)) ⩽ Cr^{n},  (3)

where n ⩾ 2, and C is independent of x, r. Under this assumption, we show that

∥M∥_{L_{1}(X)→L_{1,∞}(X)} = O(n log n),  (4)

where the implied constant depends only on C. At the same time, we construct for all n ⩾ 2 an Abelian group G_{n}, equipped with a translation invariant metric d_{n} and a translation invariant measure μ_{n}, that satisfies (3) with C = 81 ^{2}, yet

∥M∥_{L_{1}(G_{n})→L_{1,∞}(G_{n})} ≳ n log n.  (5)

We can also ensure that for all p > 1 we have

∥M∥_{L_{p}(G_{n})→L_{p}(G_{n})} ≲_{p} 1.  (6)

Here, and in what follows, we use X ≲ Y, Y ≳ X to denote the estimate X ⩽ CY for some absolute constant C; if we need C to depend on parameters, we indicate this by subscripts, thus X ≲_{p} Y means that X ⩽ C_{p}Y for some C_{p} depending only on p. We shall also use the notation X ≍ Y for X ≲ Y ∧ Y ≲ X.

Note that the bound (4) contains the Stein-Strömberg result for n-dimensional normed spaces. It also applies to, say, any translation invariant length metric on nilpotent Lie groups^{3}. However, it falls shy (by a logarithmic factor) of the two O(n) results quoted above: for the Euclidean space ℓ_{2}^{n}, and the Heisenberg group ℍ^{2n+1}. Our lower bound (5) suggests that in order to improve upon the O(n log n) bound of Stein and Strömberg, one must genuinely use the underlying geometry of the normed vector space and not just the metric properties, or the L_{p} theory. For instance, to obtain the bound of O(n) in the case of the Euclidean metric in [47], it was necessary to exploit the relationship between averaging on balls and the heat semigroup, in order that the Hopf-Dunford-Schwartz maximal inequality can be used. A similar strategy was used for the Heisenberg group in [30]. This type of relationship does not appear to be available for general norms on ℝ^{n}.

The results presented above are simple corollaries of a general localization phenomenon for maximal inequalities, which we shall now describe. In fact, for the bound (4) to hold true, we need to assume a condition which is less restrictive than the Ahlfors-David regularity condition (3); in particular it need not hold for all radii r, and it thus also applies to discrete groups of polynomial growth, equipped with the word metric and the counting measure. All of these issues are explained in the following subsection.

1.1. Microdoubling and the localization theorem. Let (X, d, μ) be a metric measure space. For R ⊆ (0, ∞) we consider the maximal operator corresponding to radii in R, which is defined by

M_{R}f(x) =^{def} sup_{r∈R} \frac{1}{μ(B(x, r))} ∫_{B(x,r)} |f| dμ.  (7)

Thus, using our previous notation, M = M_{(0,∞)}.

2One can modify the argument to make C arbitrarily close to 1, but we will not do so here as it requires more artificial constructions.

3It seems likely however that the original Stein-Strömberg argument can be extended to this setting.

We shall say that (X, d, μ) is n-microdoubling with constant K if for all x ∈ X and all r > 0 we have

μ (B (x, (1 + \frac{1}{n}) r)) ⩽ KB(x, r).  (8)

The case n = 1 in (8) is the classical K-doubling condition

∀x ∈ X ∀r > 0, μ (B (x, 2r)) ⩽ KB(x, r).  (9)

Note that (8) follows from the Ahlfors-David n-regularity condition (3), with K = eC. The microdoubling property appeared in various guises in the literature; for example, it follows from a lemma of Colding and Minicozzi [18] (see also Proposition 6.12 in [14]) that if (X, d, μ) is a K-doubling length space, then it is also n-microdoubling with constant O(1), where n = e^{K^{O(1)}}. We note in passing that this exponential dependence on K is necessary, as exhibited by the interval X = [1, N], with the metric inherited from ℝ, and the measure whose density is φ(x) = \frac{1}{x}; the doubling constant for this length space is of order log N, but it can only be n-microdoubling with n a power of N.

Our main result is the following localization theorem for maximal inequalities on microdoubling spaces. It deals, for any 1 ⩽ p < ∞, with the weak (p, p) norm of M_{R}, defined as the optimal number ∥M_{R}∥_{L_{p}(X)→L_{p,∞}(X)} for which the distributional inequality

μ (M_{R}f > λ) ⩽ \frac{∥M_{R}∥_{L_{p}(X)→L_{p,∞}(X)}^{p}}{λ^{p}} ∥f∥_{L_{p}(X)}^{p}

holds for all f ∈ L_{p}(X) and λ > 0.

Theorem 1.1 (Localisation). Fix n ⩾ 1 and K ⩾ 5. Let (X, d, μ) be a metric measure space satisfying the microdoubling condition (8). Fix ∅ ≠ R ⊆ (0, ∞) and p ⩾ 1. Then we have

∥M_{R}∥_{L_{p}(X)→L_{p,∞}(X)} ≲ K + (1 + \frac{log log K}{1 + log n})^{1/p} sup_{r>0} ∥M_{R∩[r,nr]}∥_{L_{p}(X)→L_{p,∞}(X)} .  (10)

Remark 1.1. In the converse direction, one trivially has

∥M_{R}∥_{L_{p}(X)→L_{p,∞}(X)} ⩾ sup_{r>0} ∥M_{R∩[r,nr]}∥_{L_{p}(X)→L_{p,∞}(X)} .

Note that the term \frac{log log K}{1+log n} in (10) is always at most log log K. Thus when K is independent of n, up to constants, in order to establish a weak (p, p) maximal inequality for spaces obeying (8), it suffices to do so for scales localized to an interval [r, nr]. In many cases (e.g. finite-dimensional normed vector spaces) we can also rescale to r = 1.

1.2. Weak (1, 1) norm bounds. To deduce some corollaries of Theorem 1.1, fix an integer m ∈ ℕ, and note that for all f ∈ L_{p}(X) and r, λ > 0 we have,

μ (M_{R∩[r,nr]}f > λ) = μ ( max_{0⩽j⩽m−1} M_{R∩[rn^{j/m},rn^{(j+1)/m}]}f > λ)

⩽ ∑_{j=0}^{m−1} μ (M_{R∩[rn^{j/m},rn^{(j+1)/m}]}f > λ) ⩽ m max_{0⩽j⩽m−1} μ (M_{R∩[rn^{j/m},rn^{(j+1)/m}]}f > λ) .

Thus, under the assumptions of Theorem 1.1 (and specializing to p = 1), we have for every m ∈ ℕ,

∥M_{R}∥_{L_{1}(X)→L_{1,∞}(X)} ≲ K + m (1 + \frac{log log K}{1 + log n}) sup_{r>0} ∥M_{R∩[r,n^{1/m}r]}∥_{L_{1}(X)→L_{1,∞}(X)} . (11)

Note that for m ⩾ 2n log n we have n^{1/m} ⩽ 1 + \frac{1}{n}, and hence for all r > 0,

M_{R∩[r,n^{1/m}r]}f ⩽ \frac{1}{μ(B (x, r))} ∫_{B(x,(1+ \frac{1}{n})r)} |f|dμ ⩽^{(8)} KA_{1+ \frac{1}{n}} f,  (12)

where A_{r} is the averaging operator:

A_{r}f(x) =^{def} \frac{1}{μ(B(x, r))} ∫_{B(x,r)} |f| dμ.  (13)

Under some mild uniformity assumption on μ, the strong (1, 1) norm of A_{r} is bounded for all r > 0. For example, if μ(B(x, r)) does not depend on x (as is the case for invariant metrics and measures on groups), then a simple application of Fubini’s theorem shows that ∥A_{r}∥_{L_{1}(X)→L_{1}(X)} ⩽ 1. In fact, if we knew that μ(B(x, r)) ⩽ Kμ(B(y, r)) for all x ∈ X and y ∈ B(x, r) (which is a trivial consequence of the Ahlfors-David regularity condition (3)), then we would have by the same reasoning ∥A_{r}∥_{L_{1}(X)→L_{1}(X)} ⩽ K. An elegant way to combine this uniformity condition with the microdoubling condition (8), is to impose the following condition, which we call strong n-microdoubling with constant K:

∀x ∈ X ∀r > 0 ∀y ∈ B(x, r), μ (B (y, (1 + \frac{1}{n}) r)) ⩽ KB(x, r).  (14)

Thus, by a combination of (11) and (12), we see that if (X, d, μ) satisfies (14), then ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ≲_{K} n log n. Similarly, if R ∩ [r, n^{1/m}r] contains at most one point for all r > 0, then ∥M_{R}∥_{L_{1}(X)→L_{1,∞}(X)} ≲_{K} m. This happens in particular if

R = 2^{ℤ} = {2^{k} : k ∈ ℤ} ,

and m ≍ log n, proving the following corollary:

Corollary 1.2. Fix n ⩾ 1 and K ⩾ 5. Let (X, d, μ) be a metric measure space satisfying the strong n-microdoubling condition (14). Then

∥M∥_{L_{1}(X)→L_{1,∞}(X)} ≲_{K} n log n,  (15)
∥M_{2^{ℤ}}∥_{L_{1}(X)→L_{1,∞}(X)} ≲_{K} log n.  (16)

The lacunary maximal function M_{2^{ℤ}} was previously studied for n-dimensional normed spaces by Bourgain in [9], where he proved that its strong (p, p) norm is bounded by a dimension independent constant C_{p} < ∞ (recall that for the non-lacunary maximal function this is only known for p > \frac{3}{2}). The logarithmic upper bound (16) on the weak (1, 1) norm of the lacunary maximal function when X is an n-dimensional normed space was proved by Menárguez and Soria in [35].

In section 4 we present a different approach to the proof of Corollary 1.2, following an argument of E. Lindenstrauss [31]. While it gives slightly weaker results, and does not yield the localization theorem, this approach is of independent interest. Moreover, Lindenstrauss’ approach is based on a beautiful randomization of the Vitali covering argument, and as such complements our approach to Theorem 1.1, which is based on a random partitioning method that originated in theoretical computer science and combinatorics (an overview of our technique is contained in Section 1.3). The maximal functions considered in [31] arose when taking averages over Følner sequences of an amenable group action on a measure space, and were thus not directly connected to the metric questions that are studied in the present paper. Nevertheless we consider the arguments in Section 4 to be essentially the same as those in [31]. We thank Raanan Schul for pointing out how the maximal inequality of E. Lindenstrauss implies the Hardy-Littlewood maximal inequality under strong microdoubling.

1.3. Ultrametric approximations: deterministic and random. Doob’s classical maximal inequality for martingales (see Section 2) is perhaps the simplest and most versatile maximal inequality for which the weak (1, 1) norm is known exactly (and is equal to 1). Our proof of Theorem 1.1 relates the weak (1, 1) inequality for M to the maximal inequality for martingales, by allowing the martingale itself to be a random object. We show that while the weak (1, 1) inequality is not itself a martingale inequality, it is possible to associate to each f ∈ L_{1}(X) a distribution over random martingales. These random martingales stochastically approximate Mf, in the sense that we can write down a variant of Doob’s inequality for each of them, which, under the microdoubling assumption, in expectation yields theorem 1.1. The details are presented in Section 3.

An alternative interpretation of Doob’s maximal inequality is that if (X, d, μ) is a metric measure space, and if in addition d is an ultrametric, i.e., d(x, y) ⩽ max{d(x, z), d(z, y)} for all x, y, z ∈ X, then ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩽ 1. Indeed, restrict for simplicity to the case of a finite ultrametric, in which case we obtain an induced hierarchical family of partitions of X into balls, where each ball at a given “level” is the union of balls of smaller radii at the next “level”. This picture immediately shows that by considering the averages of f on smaller and smaller balls, in the ultrametric case we can reduce the weak (1, 1) inequality for Mf to Doob’s maximal inequality.

Of course, not every metric is an ultrametric, or even close to an ultrametric. Nevertheless, over the previous two decades, researchers in combinatorics and computer science developed methods to associate to a general metric space (X, d) a distribution over random ultrametrics ρ on X, which dominate d and sufficiently approximate it in various senses (depending on the application at hand). Such methods are often also called “random partitioning methods”, in reference to the hierarchical (tree) structure of ultrametrics. This approach originated in the pioneering works of Linial and Saks [32] and Alon, Karp, Peleg and West [2], and has been substantially developed and refined by Bartal [4, 5]. Important contributions of Calinescu, Karloff and Rabani [12] and Fakcharoenphol, Rao and Talwar [22] resulted in a sharp form of “Bartal’s random tree method”, and our work builds on these ideas. In [36, 37] such random ultrametrics were used in order to prove maximal-type inequalities of a very different nature (motivated by embedding problems, as ultrametrics are isometric to subsets of Hilbert space [29]); these results also served as some inspiration for our work.

One should mention here that the idea of relating metrics to ultrametric models is, of course, standard. Hierarchical partitioning schemes are ubiquitous in analysis and geometry (see the discussion of Calderón-Zygmund decompositions in [45], or, say, Christ’s cube construction in [16]). Proving maximal inequalities by considering certain Hierarchical partitions is extremely natural; a striking example of this type is Talagrand’s majorizing measure theorem [49], which deals with sharp maximal inequalities for Gaussian processes via a construction of special ultrametrics (the ultrametric approach is explicit in [49], and has an alternative later description [50] via the so called “generic chaining”; see also [26]). Explicit uses of random coverings and partitions in the context of purely analytic problems occurred in E. Lindenstrauss’ aforementioned randomization of the Vitali covering argument for the purpose of pointwise theorems for amenable groups [31], and in the work of Nazarov, Treil and Volberg [39] on T (b) theorems on non-homogeneous spaces. See also [28] for applications to extensions of Lipschitz functions.

1.4. Lower bounds. A standard application of the Vitali covering argument (see e.g. [46] or [52]) yields the inequality

∥M̃f∥_{L_{1,∞}(X)} ⩽ ∥f∥_{L_{1}(X)},  (17)

where M̃f is the modified Hardy-Littlewood maximal operator

Mf(x) =^{def} sup_{r>0} \frac{1}{μ(B(x, r, r))} ∫_{B(x,r)} |f| dμ,

and B(x, r) ⊆ B(x, r, r) ⊆ B(x, 2r) is the enlarged ball

B(x, r, r) =^{def} ⋃_{y∈B(x,r)} B(y, r) = {z ∈ X : d(x, y), d(y, z) ⩽ r for some y ∈ X}.

In particular, if we have the doubling condition (9), then

∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩽ K.  (18)

The factor 2 in (9) cannot be replaced by any smaller number while still retaining linear behavior in terms of K of the weak (1, 1) operator norm; see [43].

In the absence of any further assumptions on the metric measure space, the bound (18) is close to sharp:

Proposition 1.5 (The star counterexample). Fix K ⩾ 1. Then there exists a metric measure space obeying (9) with

∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩾ ⌊K⌋ − 1.

Proof. Without loss of generality we may take K to be an integer. Let X be the “star” graph formed by connecting one “hub” vertex v_{0} to (K − 1)^{2} other “spoke” vertices v_{1}, …, v_{(K−1)^{2}}, with the usual graph metric (thus d(v_{0}, v_{i}) = 1 and d(v_{i}, v_{j}) = 2 for all distinct i, j ∈ {1, …, (K − 1)^{2}}). Let μ be the measure which assigns the mass K − 1 to v_{0} and mass 1 to all other vertices; one easily verifies that (9) holds. Let f ∈ L_{1}(X) be the function which equals 1 on v_{0} and vanishes elsewhere. Then one easily verifies that ∥f∥_{L_{1}(X)} = K − 1, that μ(X) = K(K − 1), and that Mf(x) ⩾ \frac{K−1}{K} for all x ∈ X, and the claim follows. □

Remark 1.2. One can achieve a similar effect in a high-dimensional Euclidean space ℝ^{n}. If we let X = {0, e_{1}, …, e_{n}} be the origin and standard basis with the usual Euclidean metric and counting measure, then (9) holds with K =^{def} n + 1, while if we let f be the indicator function of 0, then Mf(x) ⩾ \frac{1}{2} for all x ∈ X, and so ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩾ \frac{n+1}{2} = \frac{K}{2} . A more sophisticated version of this example was observed in [44]: if we take X to be the origin 0, together with a maximal 1.01-separated (say) subset of the sphere S^{d−1}, then (9) holds for K = |X| ⩾ C^{n} for some absolute constant C > 1, but ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩾ \frac{K}{2} by the same argument as before. In particular this shows that the Hardy-Littlewood weak (1, 1) operator norm (as well as the L_{p} operator norm for any fixed 1 < p < ∞) for measures in ℝ^{n} can grow exponentially in the dimension n. In the converse direction, a well-known application of the Besicovitch covering lemma [6, 7] shows that ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ⩽ C^{n} for some absolute constant C whenever X is a subset of ℝ^{n} with the Euclidean metric, and μ is an arbitrary Radon measure. In particular, as observed in [44], this shows that the constants in the Besicovitch covering lemma must grow exponentially in the dimension (see also [24]).

1.5.1. Adding more hypotheses. Despite the example in Proposition 1.5, we know due to Corollary 1.2 that in many cases the bound (18) can be significantly improved. In particular, a more meaningful variant of Proposition 1.5 would be if we also impose the natural uniformity condition that μ(B(x, r)) is independent of x ∈ X. As discussed in Section 1.2, this immediately implies that the averaging operators A_{r} given in (13) are now contractions on L_{1}(X). Thus in order for the weak (1, 1) operator norm to be large, one needs to have contributions to the set {Mf > λ} from several scales r, rather than just a single scale as in Proposition 1.5.

Another hypothesis that one can add, in order to make a potential counter-example more meaningful, is that the maximal operator M is already of strong-type (p, p) for all 1 < p ⩽ ∞, as we know to be the case for X = ℓ_{2}^{n}, due to Stein’s theorem [45]. Finally, we can make the task of bounding the maximal operator easier by replacing M with the lacunary maximal operator M_{2^{ℤ}}.

Our first main construction shows that even with all of these additional hypotheses and simplifications, we still cannot improve significantly upon (18).

Theorem 1.3 (Doubling example). Let K ⩾ 1. Then there exists a metric measure space (X, d, μ) with X an Abelian group and d, μ translation-invariant, such that the doubling condition (9) holds, and ∥M∥_{L_{p}(X)→L_{p}(X)} ≲_{p} 1 holds for all 1 < p ⩽ ∞ (with the implied constant independent of K), but such that

∥M_{2^{ℤ}}∥_{L_{1}(X)→L_{1,∞}(X)} ⩾ \frac{K}{48}.  (19)

We prove this theorem in Section 6.3. The basic idea is to first build a maximal operator not arising from a metric measure space which is of strong type (p, p) but not of weak type (1, 1), and then take an appropriate “tensor product” of this operator with a martingale type operator to obtain a new operator which is essentially a lacunary maximal operator associated to a metric measure space. The constant 48 in (19) can of course be improved, but we will not seek to optimize it here.

As stated earlier, we also construct an example of a metric measure space that shows that Corollary 1.2 is sharp even under the stronger Ahlfors-David regularity condition (3).

Theorem 1.4 (Ahlfors-David regular example). Assume that n ⩾ 2. Then there exists an Abelian group G, with invariant measure μ and an invariant metric d, obeying the Ahlfors-David n-regularity condition (3) with K = 81, such that

∥M∥_{L_{1}(G)→L_{1,∞}(G)} ≳ n log n,  (20)

and

∥M_{2^{ℤ}}∥_{L_{1}(G)→L_{1,∞}(G)} ≳ log n.  (21)

Furthermore we have

∥M∥_{L_{p}(G)→L_{p}(G)} ≲_{p} 1  (22)

for all 1 < p ⩽ ∞.

1.6. The example of the infinite tree. The above examples seem to indicate that the weak (1, 1) behavior of the Hardy-Littlewood maximal function can deteriorate substantially when the doubling constant is large, even when assuming good L_{p} bounds, as well as uniformity assumptions on the measure of balls. Nevertheless, there are some interesting examples of metric measure spaces with very poor (or non-existent) doubling properties, for which one still has a weak (1, 1) bound. We give just one example of this phenomenon, namely the infinite regular tree.

Theorem 1.5 (Hardy-Littlewood inequality for the infinite tree). Fix an integer k ⩾ 2, and let T be the infinite rooted k-ary tree, with the usual graph metric d and counting measure μ. Then we have

∥M∥_{L_{1}(T)→L_{1,∞}(T)} ≲ 1

(Thus the implied constant is independent of the degree k.)

We prove this theorem in Section 5. We remark that the L_{p} boundedness of this maximal function for p > 1 was essentially established by Nevo and Stein in [40]. The argument here proceeds very differently from the usual covering type arguments, which are totally unavailable here due to the utter lack of doubling for this tree. Instead, we use a more combinatorial argument taking advantage of the “expander” or “non-amenability” properties of this tree, which roughly asserts that any given finite subset of the tree must have large boundaries at every distance scale.

When k is odd, T is almost^{4} identifiable with the free group on \frac{k+1}{2} generators. The above theorem then suggests that a maximal ergodic theorem in L_{1} should be available for ergodic actions of free groups on measure-preserving systems (the analogous L_{p} maximal theorems for p > 1 being established in [40]). However, the non-amenability of the free group prevents one from applying standard arguments to transfer Theorem 1.5 to this setting (indeed, our proof of Theorem 1.5 will rely heavily on this non-amenability). Thus the following conjecture remains open:

Conjecture 1. Let F be a finitely generated free group, and let w ↦ T_{w} be an ergodic action of F on a probability space (X, ℬ, μ). Then

∥sup_{n⩾1} \frac{1}{|B(id, n)|} ∑_{w∈B(id,n)} |T_{w}f|∥_{L_{1,∞}(X)} ≲ ∥f∥_{L_{1}(X)}

for all f ∈ L_{1}(X), where B(id, n) is the collection of words in F of length less than n.

We remark that by applying the pointwise convergence theorems in [40] and a standard density argument, Conjecture 1 would imply the pointwise convergence result

lim_{n→∞} \frac{1}{|B(id, n)|} ∑_{w∈B(id,n)} T_{w}f(x) = ∫_{X} f dμ

for all f ∈ L_{1}(X) and almost every x ∈ X. This result is currently known for f ∈ L_{p}(X) for p > 1, due to [40].

4More precisely, one needs to enlarge the tree at the root to have k + 1 descendants instead of k. But one can easily check that this change only affects the weak (1, 1) norm of the maximal function by a constant at worst.

Acknowledgements. We thank Raanan Schul for pointing out that the Lindenstrauss maximal inequality implies the Hardy-Littlewood maximal inequality under strong microdoubling, and Zubin Guatam for explaining the proof of the Lindenstrauss maximal inequality. A. N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation. T. T. was supported by a grant from the MacArthur foundation, by NSF grant DMS-0649473, and by the NSF Waterman award.

2. Doob-type maximal inequalities

Let (X, d, μ) be a metric measure space with μ(X) < ∞ (more generally, the arguments below extend to the σ-finite case). If ℱ is a σ-algebra of measurable sets in X, we let L_{p}(ℱ) denote the space of L_{p}(X) functions which are ℱ -measurable. The orthogonal projection from L_{2}(X) to the closed subspace L_{2}(ℱ) will be denoted f ↦ 𝔼(f|ℱ), and as is well known it extends to a contraction on L_{p}(X) for all 1 ⩽ p ⩽ ∞. The following important inequality of Doob is classical (see [19, 21]).

Proposition 2.1 (Doob’s maximal inequality). Let ℱ_{0} ⊆ ℱ_{1} ⊆ ℱ_{2} ⊆ ⋯ be an increasing sequence of σ-algebras. Then we have

f ∈ L_{1}(X) ⟹ ∥sup_{k⩾0} |𝔼(f|ℱ_{k})|∥ _{L_{1,∞}(X)} ⩽ ∥f∥_{L_{1}(X)},

and for 1 < p ⩽ ∞,

f ∈ L_{p}(X) ⟹ ∥sup_{k⩾0} |𝔼(f|ℱ_{k})|∥ _{L_{p}(X)} ⩽ \frac{p}{p − 1}∥f∥_{L_{p}(X)}.

We now establish a variant of this inequality, in which the expectations 𝔼(f|ℱ_{k}) are replaced by more general sublinear operators.

Theorem 2.1 (Modified Doob’s inequality). Let ℱ_{0} ⊆ ℱ_{1} ⊆ ℱ_{2} ⊆ ⋯ be an increasing sequence of σ-algebras and fix 1 ⩽ p < ∞. For each k ∈ ℕ let M_{k} be a sublinear operator^{5} defined on L_{p}(X) + L_{∞}(X) such that we have the bounds

f ∈ L_{p}(X) ⟹ ∥M_{k}f∥_{L_{p,∞}(X)} ⩽ A∥f∥_{L_{p}(X)},  (23)

and

f ∈ L_{∞}(X) ⟹ ∥M_{k}f∥_{L_{∞}(X)} ⩽ B ∥𝔼 (|f||ℱ_{k}) ∥_{L_{∞}(X)} .  (24)

Suppose also that we have the localization property

f ∈ L_{p}(X) + L_{∞}(X) ∧ E_{k} ∈ ℱ_{k} ⟹ 1_{E_{k}}M_{k+1}f = M_{k+1} (1_{E_{k}}f) .  (25)

Then we have

∥sup_{k⩾0} |M_{k}f|∥_{L_{p,∞}(X)} ⩽ ((2A)^{p} + (2B)^{p})^{1/p} ∥f∥_{L_{p}(X)}

for all f ∈ L_{p}(X).

Remark 2.1. Observe that the properties (24), (25) (with B = 1) are satisfied by the projection operator M_{k+1}f =^{def} 𝔼(f|ℱ) whenever ℱ_{k} ⊆ ℱ ⊆ ℱ_{k+1}. Thus (24), (25) can be viewed together as a kind of assertion that M_{k+1} lies “between” ℱ_{k} and ℱ_{k+1} in some sense.

5By this we mean that |M_{k}(f + g)| ⩽ |M_{k}(f)| + |M_{k}(g)| and |M_{k}(cf)| = |c| · |M_{k}f| for all functions f, g in the domain of M_{k} and all constants c ∈ ℝ.

Proof. By monotone convergence we may restrict the supremum over k ⩾ 0 to a finite range, say 0 ⩽ k ⩽ K for some finite K ∈ ℕ. We can then assume without loss of generality that ℱ_{k} is the trivial algebra {∅, X} for all k < 0. By homogeneity it suffices to show that

f ∈ L_{p}(X) ⟹ μ ( sup_{0⩽k⩽K} |M_{k}f| > 1) ⩽ ((2A)^{p} + (2B)^{p}) ∫_{X} |f|^{p} dμ.  (26)

Fix f ∈ L_{p}(X) and note that Doob’s maximal inequality implies that

μ ( sup_{0⩽k⩽K} 𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} ) ⩽ μ ( sup_{0⩽k⩽K} 𝔼 (|f|^{p}|ℱ_{k}) ⩾ \frac{1}{(2B)^{p}} ) ⩽ (2B)^{p} ∫_{X} |f|^{p} dμ.

Thus in order to prove (26) it will suffice to show that

μ (\{ sup_{0⩽k⩽K} |M_{k}f| > 1\} \ \{ sup_{0⩽k⩽K} 𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} \}) ⩽ (2A)^{p} ∫_{X} |f|^{p} dμ.  (27)

Consider the inclusion

\{ sup_{0⩽k⩽K} |M_{k}f| > 1\} \ \{ sup_{0⩽k⩽K} 𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} \}

⊆ ⋃_{k=0}^{K} \{|M_{k}f| > 1 ∧ sup_{0⩽j<k} 𝔼 (|f||ℱ_{j}) < \frac{1}{2B} \} . (28)

Therefore, if we introduce the sets

A_{k} =^{def} X \ ⋃_{0⩽j<k} \{𝔼 (|f||ℱ_{j}) ⩾ \frac{1}{2B} \} ,

and

Ω_{k} =^{def} \{𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} \} ∩ A_{k}.

Then A_{k} ∈ ℱ_{k−1}, the sets Ω_{k} are disjoint, and using (25) we see that (28) implies the inclusion

\{ sup_{0⩽k⩽K} |M_{k}f| > 1\} \ \{ sup_{0⩽k⩽K} 𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} \} ⊆ ⋃_{k=0}^{K} \{|1_{A_{k}}M_{k}f| > 1\}

= ⋃_{k=0}^{K} {|M_{k}(1_{A_{k}}f)| > 1} . (29)

On the other hand, from (24) we have

∥M_{k}(f1_{A_{k}\Ω_{k}})∥_{L_{∞}(X)} ⩽ B ∥𝔼 (|f|1_{A_{k}\Ω_{k}} |ℱ_{k}) ∥_{L_{∞}(X)} = B ∥𝔼 (|f||ℱ_{k}) 1_{A_{k}\Ω_{k}} ∥_{L_{∞}(X)}

⩽ B · \frac{1}{2B} = \frac{1}{2}.

Hence by the sublinearity of M_{k} we have the following inclusion (up to sets of measure zero):

\{|M_{k}(f1_{A_{k}})| > 1\} ⊆ \{|M_{k}(f1_{Ω_{k}})| > \frac{1}{2}\} .  (30)

Combining (29) with (30) and the assumption (23), we obtain

μ (\{ sup_{0⩽k⩽K} |M_{k}f| > 1\} \ \{ sup_{0⩽k⩽K} 𝔼 (|f||ℱ_{k}) ⩾ \frac{1}{2B} \}) ⩽ ∑_{k=0}^{K} μ (|M_{k}(f1_{Ω_{k}})| > \frac{1}{2})

⩽ ∑_{k=0}^{K}(2A)^{p} ∫_{Ω_{k}} |f|^{p} dμ = (2A)^{p} ∫_{⋃_{k=0}^{K} Ω_{k}} |f|^{p}dμ ⩽ (2A)^{p} ∫_{X} |f|^{p} dμ.

This is precisely the estimate (27), as desired. □

3. Localization of maximal inequalities

Let (X, d, μ) be a bounded metric measure space. Given a partition 𝒫 of X and x ∈ X, we denote by 𝒫(x) the unique element of 𝒫 containing X. We shall say that a sequence {𝒫_{k}}_{k=0}^{∞} of partitions of X is a partition tree if the following conditions hold true:

• 𝒫_{0} is the trivial partition {X}.

• For every x ∈ X and k ∈ {0} ∪ ℕ we have

diam(𝒫_{k}(x)) ⩽ \frac{diam(X)}{2^{k}}.  (31)

• For every k ∈ {0} ∪ ℕ the partition 𝒫_{k+1} is a refinement of the partition 𝒫_{k}, i.e.,

for every x ∈ X we have 𝒫_{k+1}(x) ⊆ 𝒫_{k}(x). For β > 0, a probability distribution Pr over partition trees {𝒫_{k}}_{k=0}^{∞} is said to be β-padded if for every x ∈ X and every k ∈ ℕ,

Pr [B (x, \frac{β diam(X)}{2^{k}}) ⊆ 𝒫_{k}(x)] ⩾ \frac{1}{2}.  (32)

Note that (32) has the following simple consequence, which we will use later: for every measurable set Ω ⊆ X denote

Ω_{β}^{pad(k)} =^{def} \{x ∈ Ω : B (x, \frac{β diam(X)}{2^{k}}) ⊆ 𝒫_{k}(x)\} .  (33)

Thus Ω_{β}^{pad(k)} is a random subset of Ω. By Fubini’s theorem we have:

𝔼 [μ (Ω_{β}^{pad(k)})] = ∫_{Ω} Pr [B (x, \frac{β diam(X)}{2^{k}}) ⊆ 𝒫_{k}(x)] dμ(x) ⩾^{(32)} \frac{μ(Ω)}{2}.  (34)

Remark 3.1. In the definitions above we implicitly made the assumptions that certain events are measurable in the appropriate measure spaces. Namely, for (32) we need the event \{B (x, \frac{β diam(X)}{2^{k}}) ⊆ 𝒫_{k}(x)\} to be Pr-measurable for every x ∈ X and k ∈ \{0\} ∪ ℕ,

and for (34) we need the event \{(x, \{𝒫_{k}\}_{k=0}^{∞}) : x ∈ Ω ∧ B (x, \frac{β diam(X)}{2^{k}}) ⊆ 𝒫_{k}(x)\} to be measurable with respect to μ × Pr for all k ∈ {0} ∪ ℕ. These assumptions will be trivially satisfied in the concrete constructions below.

Remark 3.2. In the above definitions we made some arbitrary choices: the factor \frac{1}{2^{k}} in (31) can be taken to be some other factor r_{k} > 0, and the \frac{1}{2} lower bound on the probability in (32) can be taken to be some other probability p_{k}. Since we will not use these additional degrees of freedom here, we chose not to mention them for the sake of simplifying notation. But, the arguments below can be easily carried out in greater generality, which might be useful for future applications of these notions.

The following lemma deals with the existence of padded random partition trees on microdoubling metric measure spaces. The argument is similar to the proof of Theorem 3.17 in [28], which is based on ideas from the theoretical computer science literature [12, 22]. The last part of the argument is in the spirit of the proof of the main padding inequality in [37].

Lemma 3.1. Fix n ⩾ 1 and K ⩾ 5. Let (X, d, μ) be a separable bounded metric measure space which satisfies (8). Then X admits a \frac{1}{16n log K} -padded probability distribution over partition trees.

Remark 3.3. Let (X, d) is a separable complete and bounded metric space which is doubling with constant λ, i.e., every ball in X can be covered by at most λ balls of half the radius. It is a classical fact, due to Vol′berg and Konyagin [54] in the case of compact spaces, and Luukkainen and Saksman [33] in the case of general complete spaces (see also [55] and chapter 13 in [27]), that X admits a non-degenerate measure μ which is doubling with constant λ^{2} (the power 2 can be replaced here by any power bigger than 1). Thus the conclusion of Lemma 3.1 holds in this case with n = 1 and K = λ^{2}.

Proof of Lemma 3.1. By rescaling the metric we may assume without loss of generality that diam(X) = 1. Since X is bounded, μ(X) < ∞, and we may therefore normalize μ to be a probability measure. Let x_{1}, x_{2}, x_{3}, … be points chosen uniformly and independently at random from X according to the measure μ, i.e., (x_{1}, x_{2}, …) is distributed according to the probability measure μ^{⊗ℵ_{0}}. For each k let r_{k} be a random variable that is distributed uniformly on the interval [2^{−k−2}, 2^{−k−1}]. We assume that r_{1}, r_{2}, … are independent. Let Pr denote the joint distribution of (x_{1}, x_{2}, …), (r_{1}, r_{2}, …).

For every k ∈ ℕ define a random variable j_{k} : X → ℕ ∪ {∞} by

j_{k}(x) =^{def} inf {j ∈ ℕ ∪ {∞} : d(x, x_{j}) ⩽ r_{k}} .

Note that j_{k}(x) is almost surely finite for every x ∈ X, since each x_{j} has positive probability of falling into B(x, r_{k}) ⊇ B (x, 2^{−k−2}) (see the argument in [28] for more details). Since X is separable, it follows that the event ⋃_{x∈X} ⋃_{k=1}^{∞}{j_{k}(x) < ∞} has probability 1. From now on we will condition on this event.

For every k ∈ ℕ and ℓ_{1}, …, ℓ_{k} ∈ ℕ define

P (ℓ_{1}, …, ℓ_{k}) =^{def} {x ∈ X : j_{1}(x) = ℓ_{1}, …, j_{k}(x) = ℓ_{k}} .

Then 𝒫_{k} =^{def} {P (ℓ_{1}, …, ℓ_{k}) : ℓ_{1}, …, ℓ_{k} ∈ ℕ} is a partition of X. By definition

P (ℓ_{1}, …, ℓ_{k}) ⊆ B(x_{ℓ_{k}}, r_{k}) ⊆ B (x_{ℓ_{k}}, 2^{−k−1}) ,

and for all k ∈ ℕ,

P (ℓ_{1}, …, ℓ_{k}, ℓ_{k+1}) ⊆ P (ℓ_{1}, …, ℓ_{k}).

Therefore 𝒫_{k+1} is a refinement of 𝒫_{k} and diam(𝒫_{k}(x)) ⩽ 2^{−k} for all x ∈ X.

Denote

β = \frac{1}{16n log K} .  (35)

Since K ⩾ 5, we have β < \frac{1}{25}. Fix k ∈ ℕ and x ∈ X and observe that

Pr [B (x, \frac{β}{2^{k}} ) ⊆ 𝒫_{k}(x)] = Pr [⋂_{ℓ=1}^{k} \{∀y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) = j_{ℓ}(y)\}]

⩾ 1 − ∑_{ℓ=1}^{k} Pr [∃y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) ≠ j_{ℓ}(y)] . (36)

Fix ℓ ∈ {1, …, k}. Observe the following inclusion:

\{∃y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) ≠ j_{ℓ}(y)\}

⊆ ⋃_{i=1}^{∞} ⋂_{j=1}^{i−1} \{r_{ℓ} − \frac{β}{2^{k}} < d(x_{i}, x) ⩽ r_{ℓ} + \frac{β}{2^{k}} ∧ d(x_{j}, x) > r_{ℓ} + \frac{β}{2^{k}} \} . (37)

To prove (37), assume that the event on the left hand side of (37) occurs, i.e., that there is some y ∈ B (x, \frac{β}{2^{k}} ) for which j_{ℓ}(x) ≠ j_{ℓ}(y). Let i ∈ ℕ be the first index such that d(x_{i}, x) ⩽ r_{ℓ} + \frac{β}{2^{k}}. In order to prove that the event in the right hand side of (37) occurs, it suffices to show that the event ⋂_{j=1}^{i−1} \{r_{ℓ} − \frac{β}{2^{k}} < d(x_{i}, x) ⩽ r_{ℓ} + \frac{β}{2^{k}} ∧ d(x_{j}, x) > r_{ℓ} + \frac{β}{2^{k}} \} occurs, which, by the minimality of i, is equivalent to showing that d(x_{i}, x) > r_{ℓ} − \frac{β}{2^{k}}. So, assume for the sake of contradiction that d(x_{i}, x) ⩽ r_{ℓ} − \frac{β}{2^{k}}. This implies in particular that j_{ℓ}(x) = i, and moreover, since y ∈ B (x, \frac{β}{2^{k}} ), we have d(x_{i}, y) ⩽ r_{ℓ}, implying that j_{ℓ}(y) ⩽ i. But, d (x, x_{j_{ℓ}(y)}) ⩽ d (y, x_{j_{ℓ}(y)}) + d(x, y) ⩽ r_{ℓ} + \frac{β}{2^{k}}, and the minimality of i implies that j_{ℓ}(y) ⩾ i. Thus j_{ℓ}(y) = i = j_{ℓ}(x), contradicting our assumption on y.

Now, (37) implies that

Pr [∃y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) ≠ j_{ℓ}(y)]
⩽ 2^{ℓ+2} ∫_{2^{−ℓ−2}}^{e^{−ℓ−1}} (μ (B (x, r + \frac{β}{2^{k}} )) − μ (B (x, r − \frac{β}{2^{k}} )))

· (∑_{i=1}^{∞} (1 − μ (B (x, r + \frac{β}{2^{k}} )))^{i−1}) dr

= 1 − 2^{ℓ+2} ∫_{\frac{1}{4} e^{−ℓb}}^{\frac{1}{2} e^{−ℓb}} \frac{μ (B (x, r − \frac{β}{2^{k}} ))}{μ (B (x, r + \frac{β}{2^{k}} ))}dr.  (38)

Denote h(t) =^{def} log μ (B(x, s)). Then by Jensen’s inequality we see that

2^{ℓ+2} ∫_{2^{−ℓ−2}}^{2^{−ℓ−1}} \frac{μ (B (x, r − \frac{β}{2^{k}} ))}{μ (B (x, r − \frac{β}{2^{k}} ))}dr = 2^{ℓ+2} ∫_{2^{−ℓ−2}}^{2^{−ℓ−1}} e^{h(r− \frac{β}{2^{k}})−h(r+ \frac{β}{2^{k}})}dr

⩾ exp (2^{ℓ+2} ∫_{2^{−ℓ−2}}^{2^{−ℓ−1}} [h (r − \frac{β}{2^{k}} ) − h (r + \frac{β}{2^{k}} )] dr) . (39)

The expression in the exponent in (39) can be estimated as follows:

∫_{2^{−ℓ−2}}^{2^{−ℓ−1}} [h (r − \frac{β}{2^{k}} ) − h (r + \frac{β}{2^{k}} )] dr = ∫_{2^{−ℓ−2}−β2^{−k}}^{2^{−ℓ−2}+β2^{−k}} h (s) ds − ∫_{2^{−ℓ−1}−β2^{−k}}^{2^{−ℓ−1}+β2^{−k}} h (s) ds

⩾ β2^{−k+1} [h (2^{−ℓ−2} − βe^{−k}) − h (2^{−ℓ−1} + β2^{−k})] . (40)

By recalling the definition of h, a combination of (38), (39), (40) yields the bound,

Pr [∃y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) ≠ j_{ℓ}(y)] ⩾ 1 − (\frac{μ (B (x, 2^{−ℓ−2} − β2^{−k}))}{μ (B (x, 2^{−ℓ−1} + β2^{−k}))})^{β2^{−(k−ℓ)+3}} . (41)

Note that since ℓ ⩽ k and β ⩽ \frac{1}{25} we know that 2^{−ℓ−1} + β2^{−k} ⩽ (1 + \frac{1}{n})^{n+1} (2^{−ℓ−2} − β2^{−k}). Hence, combining the assumption (8) with (41), we see that

Pr [∃y ∈ B (x, \frac{β}{2^{k}} ) , j_{ℓ}(x) ≠ j_{ℓ}(y)] ⩽ 1 − K^{−(n+1)β2^{−(k−ℓ)+3}}

⩽ (n + 1)β2^{−(k−ℓ)+3} log K ⩽^{(35)} 2^{−(k−ℓ)}. (42)

Plugging (42) into (36) we see that

Pr [B (x, \frac{1}{16n log K} · 2^{−k}) ⊆ 𝒫_{k}(x)] = Pr [B (x, \frac{β}{2^{k}} ) ⊆ 𝒫_{k}(x)] ⩾ 1 − ∑_{ℓ=1}^{k} 2^{−(k−ℓ)} ⩾ \frac{1}{2}.

This is precisely the statement that the partition tree \{𝒫_{k}\}_{k=0}^{∞} is \frac{1}{16n log K} -padded. □

The connection between the existence of padded random partition trees and the Hardy-Littlewood maximal inequality is established in the proof of Theorem 1.1.

Proof of Theorem 1.1. By a standard monotone convergence argument we may assume that R is bounded, say R ⊆ [0, D] for some D > 1. Fix f ∈ L_{p}(X). By homogeneity it suffices to show that

μ (M_{R}f > 1) ≲ C^{p} ((1 + \frac{log log K}{1 + log n}) Q^{p} + K^{p}) ∫_{X} |f|^{p}dμ,

where C > 0 is a universal constant and

Q =^{def} sup_{r>0} ∥M_{R∩[r,nr]}∥_{L_{p}(X)→L_{p,∞}(X)} .  (43)

By monotone convergence we may assume that f (and hence also M_{R}f) has bounded support. We would like to apply Theorem 2.1, but unfortunately there are no obvious candidates for ℱ_{k} with which we have either (24) or (25). Nevertheless, we shall be able to proceed by replacing M_{R} with a slightly modified variant.

Let E be the support of f and denote

E′ =^{def} {x ∈ X : d(x, E) ⩽ D},

and

E′′ =^{def} {x ∈ X : d(x, E) ⩽ 2D}.

Then E ⊆ E′ ⊆ E′′ and diam(E′′) ⩽ 4D + diam(E) < ∞. Moreover the support of M_{R}f is contained in E′. It will therefore suffice to prove that

∥M_{R}∥_{L_{p}(E′)→L_{p,∞}(E′′)} ≲ (1 + \frac{log log K}{1 + log n}) Q + K.

By rescaling the metric we may assume that diam(E′′) = 1. Once this is achieved we may also assume that R ⊆ (0, 1], since the operator M_{R∩(1,∞)}, viewed as an operator on L_{p}(E′), is pointwise bounded by the averaging operator on E′.

Using Lemma 3.1, let {𝒫_{k}} _{k=0}^{∞} be a random partition tree on E′′ which is β-padded, where

β = \frac{1}{16n log K} .

Let m be the largest integer such that 2^{−m} ⩽ β. Denote for k ⩾ 0 and i ∈ {1, 2, 3},

R_{k}^{i} =^{def} R ∩ [2^{−(3k+i)m}, 2^{−(3k−1+i)m}] and R^{i} =^{def} ⋃_{k∈ℕ∪{0}} R_{k}^{i}.

Thus R = R^{1} ∪ R^{2} ∪ R^{3}, which implies that

μ (M_{R}f > 1) = μ (max {M_{R^{1}}f, M_{R^{2}}f, M_{R^{3}}f} > 1) ⩽ μ (M_{R^{1}}f > 1) + μ (M_{R^{2}}f > 1) + μ (M_{R^{3}}f > 1) . (44)

Fix i ∈ {1, 2, 3} and k ∈ ℕ ∪ {0}, and define

E_{k}^{i} =^{def} {x ∈ E′ : M_{R_{k}^{i}}f(x) > 1} \ ⋃_{j=0}^{k−1} {x ∈ E′ : M_{R_{j}^{i}}f(x) > 1} .

Then the sets E_{k}^{i} are disjoint and

μ (M_{R^{i}}f > 1) = μ ( sup_{k∈ℕ∪{0}} M_{R_{k}^{i}}f > 1) = ∑_{k=0}^{∞} μ (E_{k}^{i}) .  (45)

Recalling (33), we denote

Ẽ_{k}^{i} =^{def} (E_{k}^{i})_{β}^{pad((3(k−1)+i+1)m)} = \{x ∈ E_{k}^{i} : B (x, \frac{β}{2^{(3(k−1)+i+1)m}} ) ⊆ 𝒫_{(3(k−1)+i+1)m}(x)\} .

Then by (34) we know that

𝔼 [μ \binom{}{E_{k}^{i}}] ⩾ \frac{μ (E_{k}^{i})}{2}.  (46)

Plugging (46) into (45) we see that

μ (M_{R^{i}}f > 1) ⩽ 2𝔼 [∑_{k=0}^{∞} μ \binom{}{E_{k}^{i}}] = 2𝔼 [μ ( sup_{k∈ℕ∪\{0\}} M̃_{R_{k}^{i}}f > 1)] ,  (47)

where M̃_{R_{k}^{i}} is the sublinear operator

M̃_{R_{k}^{i}}g =^{def} 1Ẽ_{k}^{i}M_{R_{k}^{i}}g.

Write r = 2^{−(3k+i)m} and let v ≍ 1 + \frac{log log K}{1+log n} be an integer such that 2^{m/v} ⩽ n. By the definition of Q, for every g ∈ L_{p}(E′) and t > 0 we have

μ (M̃_{R_{k}^{i}}g > t) ⩽ μ (M_{R_{k}^{i}}g > t) = μ (M_{R∩[r,2^{m}r]}g > t)

⩽ ∑_{u=0}^{v−1} μ (M_{R∩[r2^{\frac{um}{v}} ,nr2^{\frac{um}{v}}]}g > t) ⩽ vQ^{p} \frac{∥g∥_{L_{p}(E′)}^{p}}{t^{p}} .

Thus,

g ∈ L_{p}(E′) ⟹ ∥M̃_{R_{k}^{i}}g∥_{L_{p,∞}(E′)} ⩽ v^{1/p}Q∥g∥_{L_{p}(E′)}.  (48)

For every k ∈ ℕ ∪ {0} we let ℱ_{k} =^{def} σ(𝒫_{k}) be the σ-algebra generated by the partition 𝒫_{k}. Then ℱ_{0} ⊆ ℱ_{1} ⊆ ℱ_{2} ⊆ · · ·. We claim that for every k ∈ ℕ ∪ {0}, if F ∈ ℱ_{(3k+i+1)m} then

1_{F} M̃_{R_{k+1}^{i}}(g) = M̃_{R_{k+1}^{i}}(1_{F} g).  (49)

By the definition of M̃_{R_{k}^{i}}, in order to prove (49) we have to show that for almost every x ∈ E′ we have

1_{F} (x) · 1Ẽ_{k+1}^{i}(x) · M_{R_{k+1}^{i}}(g)(x) = 1Ẽ_{k+1}^{i}(x) · M_{R_{k+1}^{i}}(1_{F} g)(x).  (50)

It is non-trivial to check (50) only when x ∈ Ẽ_{k+1}^{i}, in which case we are guaranteed that B (x, β2^{−(3k+i+1)m}) ⊆ 𝒫_{(3k+i+1)m}(x). But since F ∈ ℱ_{(3k+i+1)m}, we know that P_{(3k+i+1)m}(x) is either disjoint from F or contained in F. If P_{(3k+i+1)m}(x) ⊆ F, then for every r ∈ R_{k+1}^{i},

B(x, r) ⊆ B (x, 2^{−(3k+i+2)m}) ⊆ B (x, β2^{−(3k+i+1)m}) ⊆ 𝒫_{(3k+i+1)m}(x) ⊆ F,  (51)

where we used the fact that r ⩽ 2^{−(3(k+1)−1+i)m} and 2^{−m} ⩽ β. The inclusion (51) implies that both sides of the equation (50) are equal to M_{R_{k+1}^{i}}(g)(x). On the other hand, if P_{(3k+i+1)m}(x) is disjoint from F, then B(x, r) is disjoint from F for all r ∈ R_{k+1}^{i}, implying that both sides of the equation (50) vanish. This concludes the proof of (49).

Fix g ∈ L_{∞}(E′), and extend g to a function on X whose value is 0 outside E′. Assume that

∥𝔼 (|g||ℱ_{(3k+i+1)m}) ∥_{L_{∞}(E′)} = 1.

This implies that for all F ∈ ℱ_{(3k+i+1)m} we have

∫_{F} |g|dμ = ∫_{F ∩E′} |g|dμ ⩽ μ (F ∩ E′) ⩽ μ(F).  (52)

Fix r ∈ R_{k}^{i} and x ∈ E′. Denote

F =^{def} ⋃ {C ∈ 𝒫_{(3k+i+1)m} : C ∩ B(x, r) ≠ ∅} ∈ ℱ_{(3k+i+1)m}.

Note that B(x, r) ⊆ E′′, which implies that

F ⊇ B(x, r).  (53)

Moreover,

F ⊆ B (x, r + sup_{C∈𝒫_{(3k+i+1)m}} diam(C)) ⊆ B (x, r + 2^{−(3k+i+1)m}) ⊆ B (x, (1 + 2^{−m}) r) , (54)

where in the last inclusion in (54) we used the fact that r ∈ R_{k}^{i} implies that r ⩾ 2^{−(3k+i)m}. Hence,

\frac{1}{μ(B(x, r))} ∫_{B(x,r)} |g|dμ ⩽^{(53)} \frac{1}{μ(B(x, r))} ∫_{F} |g|dμ ⩽^{(52)} \frac{μ(F)}{μ(B(x, r))}

⩽^{(54)} \frac{μ (B (x, (1 + 2^{−m}) r))}{μ(B(x, r))} ⩽ \frac{μ (B (x, (1 + \frac{1}{n}) r))}{μ(B(x, r))} ⩽^{(8)} K, (55)

We are now in position to apply Theorem 2.1 to the increasing sequence of σ-algebras {ℱ_{(3k+i+1)m}} _{k=0}^{∞} and the sublinear operators {M_{R_{k}^{i}}}_{k=0}^{∞}, with A = v^{1/p}Q, due to (48), and B = K, due to (55):

μ ( sup_{k∈ℕ∪{0}} M̃_{R_{k}^{i}}f > 1) ⩽ (2^{p}vQ^{p} + 2^{p}K^{p}) ∫_{X} |f|^{p}dμ

≲ (2^{p} (1 + \frac{log log K}{1 + log n}) Q^{p} + 2^{p}K^{p}) ∫_{X} |f|^{p}dμ.

Using (47) and (44), we therefore deduce that

[μ (M_{R}f > 1)]^{1/p} ≲ ((1 + \frac{log log K}{1 + log n})^{1/p} Q + K) ∥f∥_{L_{p}(X)},

as required. □

4. An argument of E. Lindenstrauss

We now present an alternative approach to Corollary 1.2, following an argument of E. Lindenstrauss [31]. Let us first make some definitions. We fix a metric measure space (X, d, μ). Given any two radii r, r′ > 0 and a center x ∈ X, we define the enlarged ball B(x, r, r′) by

B(x, r, r′) =^{def} ⋃_{y∈B(x,r)} B(y, r′) = {z ∈ X : d(x, y) ⩽ r ∧ d(y, z) ⩽ r′ for some y ∈ X}.

Thus, for instance,

B(x, r) ⊆ B(x, r, r′) ⊆ B(x, r + r′).  (56)

In analogy to [31], we say that a finite sequence of radii 0 < r_{1} < r_{2} < ⋯ < r_{k} is tempered with constant K ⩾ 1 if we have the bound

∀ j ∈ {1, …, k} ∀x ∈ X ∀y ∈ B(x, r_{j}),

μ (B(x, r_{j}) ⋃ (⋃_{i=1}^{j−1} B (x, r_{j}, r_{i}))) ⩽ Kμ (B (y, r_{j})) . (57)

Theorem 4.1 (Lindenstrauss maximal inequality). Let (X, d, μ) be a metric measure space, and let 0 < r_{1} < r_{2} < … < r_{k} be a sequence of radii which is tempered with constant K. Then we have the weak (1, 1) maximal inequality

μ (x ∈ X : max_{1⩽j⩽k} \frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} |f| dμ > λ) ⩽ \frac{2e}{e − 1} \frac{K}{λ} ∥f∥_{L_{1}(X)}

for all f ∈ L_{1}(X) and λ > 0.

Proof of Corollary 1.2 assuming Theorem 4.1. Assume that (X, d, μ) obeys the strong microdoubling condition (14). It is immediate to check that any sequence 0 < r_{1} < r_{2} < … < r_{k} obeying the lacunarity condition r_{j} ⩾ nr_{j−1} will be tempered with constant K, and hence by Theorem 4.1,

μ (x ∈ X : max_{1⩽j⩽k} \frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} |f| dμ > λ) ⩽ \frac{2e}{e − 1} \frac{K}{λ} ∥f∥_{L_{1}(X)}.

If instead we have the lacunarity condition r_{j} ⩾ 2r_{j−1}, then we can sparsify this sequence into O(log n) subsequences obeying the prior lacunarity condition, and hence, by subadditivity,

μ (x ∈ X : max_{1⩽j⩽k} \frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} |f| dμ > λ) ≲ \frac{K log n}{λ}∥f∥_{L_{1}(X)}.

From monotone convergence we then conclude (16). Similarly, any sequence obeying the lacunarity condition r_{j} ⩾ (1 + \frac{1}{n})r_{j−1} can be sparsified into O(n log n) sequences which have a lacunarity ratio of n. By monotone convergence this implies that

μ (x ∈ X : sup_{r∈(1+ \frac{1}{n})^{ℤ}} \frac{1}{B(x, r)} ∫_{B(x,r)} |f| dμ > λ) ≲ \frac{Kn log n}{λ}∥f∥_{L_{1}(X)},

where (1 + \frac{1}{n})^{ℤ} denotes the integer powers of 1 + \frac{1}{n}. Now note from (14) that every ball is contained in a ball whose radius is an integer power of 1 + \frac{1}{n}, and whose measure is at most K times larger. Thus

Mf(x) ⩽ K sup_{r∈(1+ \frac{1}{n})^{ℤ}} \frac{1}{B(x, r)} ∫_{B(x,r)} |f| dμ,

and (15) follows. □

Proof of Theorem 4.1. As in [31], this is achieved by a randomized variant of the Vitali covering argument. We may take f to be non-negative, and normalize λ = 1. For each j ∈ {1, …, k}, let E_{j} be a compact subset of X on which we have

x ∈ E_{j} ⟹ \frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} f dμ > 1.  (58)

By inner regularity it will suffice to show that

μ (⋃_{j=1}^{k} E_{j}) ⩽ \frac{2e}{e − 1}K ∫_{X} f dμ.  (59)

We establish (59) by induction on k. The case k = 0 is vacuously true, so suppose k ⩾ 1 and the claim has already been proven for k −1 (i.e, that (59) holds true for all non-negative f ∈ L_{1}(X) and all sets {E_{j}}_{j=1}^{k−1} satisfying (58)).

By compactness, we see that there exists an ε > 0 such that

x ∈ E_{k} ⟹ μ(B(x, r_{k})) > ε.

We then define the extended ball

B^{∗}(x) =^{def} B(x, r_{k}) ⋃ (⋃_{j=1}^{k−1} B(x, r_{k}, r_{j})) .

Thus, since the sequence of radii {r_{j}}_{j=1}^{k} is tempered, for all y ∈ B(x, r_{k}),

ε < μ (B^{∗}(y)) ⩽ Kμ(B(x, r_{k})).  (60)

If we then define the intensity function

p(x) =^{def} inf_{y∈B(x,r_{k})} \frac{1}{μ(B^{∗}(y))},

then p is a measurable function on E_{k} which is bounded both above and below:

\frac{1}{Kμ ((B(x, r_{k}))} ⩽ p(x) < \frac{1}{ε}.  (61)

We now introduce a Poisson process Σ on E_{k} with intensity p(x). Thus Σ is a random subset^{6} of E_{k} which will be almost surely finite, and more precisely, for any non-negative measurable weight w : E_{k} → ℝ_{+}, the quantity ∑_{x∈Σ} w(x) is a Poisson random variable with expectation

α_{w} =^{def} 𝔼 [∑_{x∈Σ} w(x)] = ∫_{E_{k}} wp dμ,  (62)

i.e., for any integer k ⩾ 0

Pr (∑_{x∈Σ} w(x) = k) = \frac{e^{−α_{w}}α_{w}^{k}}{k!} .  (63)

Now we define the random sets

E′ =^{def} ⋃_{x∈Σ} B^{∗}(x) and F =^{def} ⋃_{x∈Σ} B(x, r_{k}).

Then,

μ (⋃_{j=1}^{k} E_{j}) ⩽ μ(E_{k}) + μ(E′) + μ (⋃_{j=1}^{k−1} E_{j} \ E′) .  (64)

6If E_{k} contains atoms, then Σ may contain multiplicity, thus it is really a multiset rather than a set in this case. One way to create Σ is to let N be a Poisson random variable with expectation P =^{def} ∫_{E_{k}} pdμ and then let Σ = {x_{1}, …, x_{N}} where x_{1}, …, x_{N} are iid elements of E chosen using the probability distribution pdμ/P.

Let us investigate the third term in (64). Fix j ∈ {1, …, k − 1}. If x ∈ E_{j} \ E′, then

\frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} f dμ > 1.

But, since x ∉ E′ it follows from our definitions that B(x, r_{j}) is disjoint from F. Thus we have

\frac{1}{B(x, r_{j})} ∫_{B(x,r_{j})} f1_{X\F} dμ > 1.

We can therefore apply the induction hypothesis to the sets {E_{j} \ E′}_{j=1}^{k−1} and the function f1_{X\F}, and conclude that

μ (⋃_{j=1}^{k−1} E_{j} \ E′) ⩽ \frac{2e}{e − 1}K ∫_{X\F} f dμ.

It follows from (64) that it suffices to show that

μ(E_{k}) + 𝔼 [μ(E′)] ⩽ 𝔼 [μ(E_{k}) + μ(E′)] ⩽ \frac{2e}{e − 1}K𝔼 [∫_{F} f dμ] .  (65)

Now, applying (62) and (63) with w =^{def} 1/p, we have

μ(E_{k}) = 𝔼 [∑_{x∈Σ} \frac{1}{p(x)}] ,

while from definition of E′ we have

μ(E′) ⩽ ∑_{x∈Σ} μ (B^{∗}(x)) = ∑_{x∈Σ} \frac{1}{p(x)}.

Thus, in order to prove (65) it suffices to show that

𝔼 [∑_{x∈Σ} \frac{1}{p(x)}] ⩽ \frac{e}{e − 1}K𝔼 [∫_{F} f dμ] .  (66)

From (58) we know that for all x ∈ Σ,

\frac{1}{p(x)} < \frac{1}{p(x)μ(B(x, r_{k}))} ∫_{X} 1_{B(x,r_{k})}f dμ,

and hence

𝔼 [∑_{x∈Σ} \frac{1}{p(x)}] ⩽ ∫_{X} (𝔼 [∑_{x∈Σ} \frac{1}{p(x)μ(B(x, r_{k}))}1_{B(x,r_{k})}]) f dμ.  (67)

Fix y ∈ X. From (62) with w(x) = \frac{1_{B(x,r_{k})}(y)}{p(x)μ(B(x,r_{k}))}, we see that

𝔼 [∑_{x∈Σ} \frac{1}{p(x)μ(B(x, r_{k}))}1_{B(x,r_{k})}(y)] = ∫_{E_{k}∩B(y,r_{k})} \frac{1}{μ(B(x, r_{k}))} dμ(x).  (68)

By substituting (68) into (67), we see that in order to prove (66) it will suffice to prove the pointwise estimate

∫_{E_{k}∩B(y,r_{k})} \frac{1}{μ(B(x, r_{k}))} dμ(x) ⩽ \frac{eK}{e − 1}𝔼 [1_{F} (y)] ,  (69)

for all y ∈ X.

Now observe that the definition of F implies that 1_{F} (y) = 1 if and only if |Σ∩B(y, r_{k})| ⩾ 1. But, recall from (62) (using w(x) = 1_{B(y,r_{k})}(x)) that |Σ ∩ B(y, r_{k})| is a Poisson random variable with expectation

α(y) =^{def} ∫_{E_{k}} 1_{B(y,r_{k})}p dμ = ∫_{E_{k}∩B(y,r_{k})} p(x) dμ(x),  (70)

and thus

𝔼 [1_{F} (y)] = 1 − e^{−α(y)}.  (71)

A combination of (61) and (70) yields the bound

∫_{E_{k}∩B(y,r_{k})} \frac{1}{μ(B(x, r_{k}))} dμ(x) ⩽ Kα(y).  (72)

The definition of p(x) implies that if y ∈ B(x, r_{k}) then p(x) ⩽ \frac{1}{μ(B^{∗}(y))} ⩽ \frac{1}{μ(B(y,r_{k}))}, since B^{∗}(y) ⊇ B(x, r_{k}). In combination with (70), we deduce that α(y) ⩽ 1. But, the function α ↦ \frac{1−e^{−α}}{α} is decreasing on [0, ∞), and therefore 1 − e^{−α(y)} ⩾ (1 − e^{−1})α(y). This, in combination with (71) and (72), implies (69), and completes the proof of Theorem 4.1. □

As observed in [31], the above argument allows us to extract a good maximal inequality for sufficiently sparse subsequences of radii if the situation is sufficiently “amenable”. In our current context, the analogue for amenability is in fact subexponential growth:

Corollary 4.2. Let (X, d, μ) be a metric measure space such that μ(B(x, r)) is independent of x ∈ X for all r > 0. Suppose also that we have the sub-exponential growth condition

lim_{r→∞} \frac{log μ(B(x, r))}{r} = 0  (73)

for any x ∈ X (note that our assumption implies that the choice of x is in fact irrelevant). Then there exists a sequence of radii 0 < r_{1} < r_{2} < … tending to infinity such that we have the maximal inequality

f ∈ L_{1}(X) ⟹ ∥sup_{k⩾1} A_{r_{k}}|f|∥_{L_{1,∞}(X)} ⩽ 4∥f∥_{L_{1}(X)},

where the averaging operators A_{r} are given by A_{r}g =^{def} \frac{1}{B(x,r)} ∫_{B(x,r)} |g| dμ.

Proof. We construct the radii recursively as follows. We set r_{1} =^{def} 1. If r_{1}, …, r_{k} have already been chosen, we choose r_{k+1} > max {r_{k}, k} so that

log μ (B (x, r_{k+1} + r_{k})) ⩽ μ (B (x, r_{k+1})) + 0.001

for any x ∈ X. Such a radius must exist, since otherwise one would easily contradict (73). The sequence of radii is tempered with constant K = e^{0.001}, and the claim follows since \frac{2K}{1−e^{−1}} < 4. □

5. The infinite tree

Fix k ⩾ 2 and let T be the infinite rooted k-ary tree with the usual graph metric and the counting measure μ. In this section we prove Theorem 1.5. The first (standard) step is to replace the Hardy-Littlewood maximal function with the spherical maximal function

M^{∘}f(x) =^{def} sup_{r⩾0} \frac{1}{|S(x, r)|} ∑_{y∈S(x,r)} |f(y)|,

where S(x, r) is the sphere

S(x, r) =^{def} {y ∈ T : d(x, y) = r}.

Since every ball can be written as the disjoint union of spheres, we have the pointwise estimate

Mf(x) ⩽ M^{∘}f(x),

and so it suffices to show that

μ (x ∈ T : M^{∘}f(x) ⩾ λ) ≲ \frac{1}{λ}∥f∥_{L_{1}(T)},  (74)

for all f ∈ L_{1}(T) and λ > 0.

Our arguments rely on the following expander-type estimate. We use |E| = μ(E) to denote the cardinality of a finite set E ⊆ T.

Lemma 5.1. Let E, F be finite subsets of T and let r ⩾ 0 be an integer. Then

|{(x, y) ∈ E × F : d(x, y) = r}| ⩽ 2|E|^{1/2}|F |^{1/2}k^{r/2}.

This bound should be compared against the “trivial” bounds of |E|k^{r} and |F |k^{r}. It is superior when |E|/|F | lies between k^{r} and k^{−r}. By setting E and F equal to concentric spheres one can verify that the bound is essentially sharp in this case.

Proof. Let us subdivide T = ⋃_{j=0}^{∞} T_{j}, where T_{j} is the generation of the tree at depth j (thus

for instance |T_{j}| = k^{j}). We then define E_{j} =^{def} E ∩ T_{j} and F_{j} =^{def} F ∩ T_{j}. Observe that in order for an element in E_{j} and an element in F_{i} to have distance exactly r, we must have i = j + r − 2m for some m ∈ {0, …, r}. Thus we can write

|\{(x, y) ∈ E × F : d(x, y) = r\}| = ∑_{m=0}^{r} ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i=j+r−2m \end{matrix}} |\{(x, y) ∈ E_{j} × F_{i} : d(x, y) = r\}| . (75)

Fix m ∈ {0, …, r} and i, j ∈ ℕ ∪ {0} such that i = j + r − 2m. Observe that if x ∈ T_{j} and y ∈ T_{i} are at distance r in T, then the m^{th} parent of x equals the (r − m)^{th} parent of y. From this we conclude that for each x ∈ T_{j} there are at most k^{r−m} elements of y ∈ T_{i} with d(x, y) = r, and conversely for each y ∈ T_{i} there are at most k^{m} elements of x ∈ T_{j} with d(x, y) = r. Thus

|{(x, y) ∈ E_{j} × F_{i} : d(x, y) = r}| ⩽ min {k^{r−m}|E_{j}|, k^{m}|F_{i}|} .  (76)

A combination of (75) and (76) implies that our task is therefore to show that

∑_{m=0}^{r} ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i=j+r−2m \end{matrix}} min \{k^{r−m}|E_{j}|, k^{m}|F_{i}|\} ⩽ 2|E|^{1/2}|F |^{1/2}k^{r/2}.  (77)

If we write c_{j} =^{def} \frac{|E_{j}|}{k^{j}} and d_{j} =^{def} \frac{|F_{j}|}{k^{j}} for j ⩾ 0 and c_{j} =^{def} d_{j} =^{def} 0 for j < 0 then we have

∑_{j=0}^{∞} k^{j}c_{j} = |E| and ∑_{j=0}^{∞} k^{j}d_{j} = |F |,  (78)

and we have

∑_{m=0}^{r} ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i=j+r−2m \end{matrix}} min \{k^{r−m}|E_{j}|, k^{m}|F_{i}|\} = ∑_{m=0}^{r} ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i=j+r−2m \end{matrix}} k^{(i+j+r)/2} min \{c_{j}, d_{i}\}

⩽ k^{r/2} ∑_{i,j=0}^{∞} k^{(i+j)/2} min {c_{j}, d_{i}} . (79)

A combination of (78) and (79) shows that in order to prove (77) it will suffice to show that

∑_{i,j=0}^{∞} k^{(i+j)/2} min {c_{j}, d_{i}} ⩽ 2 (∑_{j⩾0} k^{j}c_{j})^{1/2} (∑_{i⩾0} k^{i}d_{i})^{1/2} .

To prove this inequality, let α be a real parameter to be chosen later, and estimate

∑_{i,j=0}^{∞} k^{(i+j)/2} min \{c_{j}, d_{i}\} ⩽ ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i<j+α \end{matrix}} k^{(i+j)/2}c_{j} + ∑_{\begin{matrix}i,j∈ℕ∪\{0\} \\ i⩾j+α \end{matrix}} k^{(i+j)/2}d_{i} ⩽ ∑_{j=0}^{∞} k^{j+ \frac{α}{2}} c_{j} + ∑_{i=0}^{∞} k^{i− \frac{α}{2}} d_{i}.

Optimising in α we obtain the required result. □

For each r ⩾ 0, let A_{r}^{∘} denote the spherical averaging operator

A_{r}^{∘}f(x) =^{def} \frac{1}{μ(S(x, r))} ∑_{y∈S(x,r)} |f(y)|.

Thus M^{∘}f(x) = sup_{r⩾0} A_{r}^{∘}f(x). We can use Lemma 5.1 to obtain a distributional estimate on A_{r}^{∘}.

Lemma 5.2. Let f ∈ L_{1}(T), r > 0 and λ > 0. Then

μ (A_{r}^{∘}f ⩾ λ) ≲ ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽2k^{r} \end{matrix}} \sqrt{\frac{2^{n}}{k^{r}}} · 2^{n}μ (|f| ⩾ 2^{n−1}λ) .

Proof. We may take f to be non-negative. By dividing f by λ we may normalize λ = 1. We bound

f ⩽ \frac{1}{2} + ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} 2^{n}1_{E_{n}} + f1_{\{f⩾ \frac{1}{2} k^{r}\}},  (80)

where E_{n} is the sublevel set

E_{n} =^{def} {2^{n−1} ⩽ f < 2^{n}} .  (81)

Hence

A_{r}^{∘}f ⩽ \frac{1}{2} + ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} 2^{n}A_{r}^{∘} (1_{E_{n}}) + A_{r}^{∘} (f1_{\{f⩾ \frac{1}{2} k^{r}\}}) .  (82)

Since μ(S(x, r)) ⩽ k^{r} we see that

μ (A_{r}^{∘} (f1_{\{f⩾ \frac{1}{2} k^{r}\}}) ≠ 0) ⩽ k^{r}μ (f ⩾ \frac{1}{2}k^{r}) .  (83)

Thus we have

μ (A_{r}^{∘}f ⩾ 1) ⩽^{(82)∧(83)} μ ( ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} 2^{n}A_{r}^{∘} (1_{E_{n}}) ⩾ \frac{1}{2}) + k^{r}μ (f ⩾ \frac{1}{2}k^{r}) .

Note that if

∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} 2^{n}A_{r}^{∘} (1_{E_{n}}) ⩾ \frac{1}{2}

then we necessarily have for some n ∈ ℕ such that 1 ⩽ 2^{n} ⩽ k^{r},

A_{r}^{∘} (1_{E_{n}}) ⩾ \frac{1}{2^{n+4}} (\frac{2^{n}}{k^{r}} )^{1/4} .

Indeed, otherwise we have

\frac{1}{2} ⩽ ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} 2^{n}A_{r}^{∘} (1_{E_{n}}) ⩽ \frac{1}{16} ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} (\frac{2^{n}}{k^{r}} )^{1/4} ⩽ \frac{2^{1/4}k^{r/4} − 1}{16k^{r/4} (2^{1/4} − 1)} < \frac{1}{2},

which is a contraction. Thus

μ (A_{r}^{∘}f ⩾ 1) ⩽ ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽k^{r} \end{matrix}} μ(F_{n}) + k^{r}μ (f ⩾ \frac{1}{2}k^{r}) ,  (84)

where

F_{n} =^{def} \{A_{r}^{∘} (1_{E_{n}}) ⩾ \frac{1}{2^{n+4}} (\frac{2^{n}}{k^{r}} )^{1/4}\} .

Note that F_{n} is finite and observe that

\frac{1}{k^{r}} |\{(x, y) ∈ E_{n} × F_{n} : d(x, y) = r\}| = ∑_{y∈F_{n}} A_{r}^{∘} (1_{E_{n}}) (y) ⩾ \frac{μ(F_{n})}{2^{n+4}} (\frac{2^{n}}{k^{r}} )^{1/4} .

Applying Lemma 5.1 we conclude that

\frac{μ(F_{n})}{2^{n+4}} (\frac{2^{n}}{k^{r}} )^{1/4} ⩽ 2\sqrt{\frac{μ(E_{n})μ(F_{n})}{k^{r}}}.

Hence

μ(F_{n}) ⩽ 2^{10}\sqrt{\frac{2^{n}}{k^{r}}} · 2^{n}μ(E_{n}).

Plugging this estimate into (84), we obtain the required result. □

Proof of Theorem 1.5. Now we prove (74). Since M^{∘}f = sup_{r⩾0} A_{r}^{∘}f, Lemma 5.2 implies that

μ (M^{∘}f ⩾ λ) ⩽ ∑_{r=0}^{∞} μ (A_{r}^{∘}f ⩾ λ) ≲ ∑_{r=0}^{∞} ∑_{\begin{matrix}n∈ℕ∪\{0\} \\ 1⩽2^{n}⩽2k^{r} \end{matrix}} \sqrt{\frac{2^{n}}{k^{r}}} · 2^{n}μ (|f| ⩾ 2^{n−1}λ)

= ∑_{x∈T} ∑_{n=0}^{∞} ( ∑_{\begin{matrix}r∈ℕ∪\{0\} \\ k^{r}⩾2^{n−1} \end{matrix}} \frac{1}{k^{r/2}} ) 2^{3n/2}1_{\{|f(x)|⩾2^{n−1}λ\}} ≲ ∑_{x∈T} ∑_{n=0}^{∞} 2^{n}1_{\{|f(x)|⩾2^{n−1}λ\}} ≲ ∑_{x∈T} \frac{1}{λ}|f(x)|,

which is (74), as desired. The proof of Theorem 1.5 is complete. □

6. Sharpness

The purpose of this section is to prove Theorem 1.3 and Theorem 1.4.

6.1. A preliminary construction. Before we exhibit the full examples, we first need a preliminary example of a maximal operator associated to a finite Abelian group (but not to a metric) which has bad weak (1, 1) behavior.

Proposition 6.2 (Preliminary example). Let q be a power of an odd prime, and let 𝔽_{q} be the finite field with q elements. If q is sufficiently large then there exists a vector space X_{q} over 𝔽_{q} with counting measure μ and dimension m = dim(X_{q}) ⩽ \sqrt{q}, and disjoint sets {E_{z} ⊆ X_{q}}_{z∈𝔽_{q}} which are symmetric around the origin (i.e. x ∈ E_{z} if and only if −x ∈ E_{z}) with measure

z ∈ F_{q} ⟹ \frac{1}{2q} μ(X_{q}) < μ(E_{z}) < \frac{2}{q}μ(X_{q}),  (85)

and such that the maximal function

M_{q}f(x) =^{def} max_{z∈𝔽_{q}} \frac{1}{μ(E_{z})} ∫_{E_{z}} |f(x + y)|dμ(y)

obeys the bounds

∥M_{q}f∥_{L_{p}(X_{q})} ≲ (\frac{p}{p − 1})^{2} ∥f∥_{L_{p}(X_{q})}  (86)

for all 1 < p ⩽ ∞, but such that

∥M_{q}∥_{L_{1}(X_{q})→L_{1,∞}(X_{q})} > \frac{q}{2}.  (87)

Furthermore, there exists a one-dimensional subspace W_{−m+1} in X_{q} with the property that for all z ∈ 𝔽_{q}

μ(W_{−m+1} + E_{z}) ⩾ \frac{1}{4}μ(X_{q}),  (88)

where W_{−m+1} + E_{z} is the Minkowski sum of W_{−m+1} and E_{z}.

Remark 6.1. The dimension bound dim(X_{q}) ⩽ \sqrt{q} is not necessary for Theorem 1.3, but will be useful for proving Theorem 1.4. Conversely, the property (88) is used for Theorem 1.3 but not for Theorem 1.4. Even though our choice of notation for W_{−m+1} seems somewhat cumbersome at this juncture, it will become convenient when we apply Proposition 6.2 in Section 6.3.

Proof of Proposition 6.2. Let m be the largest integer less than \sqrt{q}. We set X_{q} =^{def} 𝔽_{q}^{m} to be the m-dimensional vector space over 𝔽_{q}, with counting measure μ. On this space we consider the non-degenerate quadratic form^{7} Q : X_{q} → 𝔽_{q} by

Q(x_{1}, …, x_{m}) =^{def} x_{1}^{2} + … + x_{m}^{2}.

Define for z ∈ 𝔽_{q}

E_{z} =^{def} {x ∈ 𝔽_{q}^{m} : Q(x) = z} = Q^{−1}(z).

Clearly E_{z} is symmetric around the origin.

Let 𝔽_{q}^{∗} denote the dual of the additive group of 𝔽_{q}. Fix a non-trivial character χ ∈ 𝔽_{q}^{∗}\{1}. Then a standard Gauss sum argument (see Lemma 4.14 in [51]) shows that since q is odd,

|∑_{x∈𝔽_{q}} χ (yx^{2})| = \sqrt{q}  (89)

for every y ∈ 𝔽_{q} \ {0}.

For every x = (x_{1}, …, x_{m}), x′ = (x′_{1}, …, x′_{m}) ∈ X_{q} write ⟨x, x′⟩ =^{def} ∑_{j=1}^{m} x_{j}x′_{j} ∈ 𝔽_{q}. Then

for every η ∈ X_{q} and y ∈ 𝔽_{q} \ {0} we have (using the fact that q is odd),

|∫_{X_{q}} χ (yQ(x) + ⟨η, x⟩) dμ(x)| = ∏_{j=1}^{m} | ∑_{x_{j}∈𝔽_{q}} χ (yx_{j}^{2} + η_{j}x_{j})|

= ∏_{j=1}^{m} | ∑_{x_{j}∈𝔽_{q}} χ (y (x_{j} + \frac{η_{j}}{2y} )^{2})| =^{(89)} q^{m/2} = \frac{μ(X_{q})}{q^{m/2}}. (90)

Consider the elementary identity

1_{E_{z}}(x) = \frac{1}{q} ∑_{y∈𝔽_{q}} χ(−yz)χ (yQ(x)) .  (91)

For every η ∈ X_{q} and z ∈ 𝔽_{q} write

ˆ1_{E_{z}}(η) =^{def} \frac{1}{μ(X_{q})} ∫_{X_{q}} 1_{E_{z}}(x)χ (⟨η, x⟩) dμ(x).

7One could also use here a random symmetric function from F_{q}^{m} to F_{q} if desired; the key features of Q that we shall need are that it is even, and its Fourier coefficients are all small.

Then

|\frac{μ (E_{z})}{μ(X_{q})} − \frac{1}{q}| = |ˆ1_{E_{z}}(0) − \frac{1}{q}| ⩽^{(91)} \frac{1}{qμ(X_{q})} ∑_{y∈𝔽_{q}\\{0\}} |∫_{X_{q}} χ (yQ(x) + ⟨η, x⟩ − yz) dμ(x)|

⩽^{(90)} \frac{1}{q^{m/2}} ⩽ \frac{\sqrt{q}}{q^{\sqrt[\frac{1}{2}]{q}}} ⩽ \frac{1}{2q} , (92)

provided that q is large enough. This proves (85). Moreover, for every η ∈ X_{q} \ {0},

|ˆ1_{E_{z}}(η)| ⩽^{(91)} \frac{1}{qμ(X_{q})} ∑_{y∈𝔽_{q}\\{0\}} |∫_{X_{q}} χ (yQ(x) + ⟨η, x⟩) dμ(x)| ⩽^{(90)} \frac{1}{q^{m/2}} ⩽ \frac{\sqrt{q}}{q^{\sqrt[\frac{1}{2}]{q}}} .  (93)

Consider the averaging operator

A_{z}f(x) =^{def} \frac{1}{μ(E_{z})} ∫_{E_{z}} f(x + y)dμ(y).

Inequalities (92) and (93), combined with Parseval’s identity, imply the L_{2} bound

∥f − A_{z}f∥_{L_{2}(X_{q})} ⩽ \frac{μ(X_{q})}{μ(E_{z})} · max_{η∈X_{q}\\{0\}} |ˆ1_{E_{z}}(η)| · ∥f∥_{L_{2}(X_{q})} ⩽ \frac{2∥f∥_{L_{2}(X_{q})}}{q^{\frac{m}{2} −1}} .  (94)

On the other hand, since A_{z} is a contraction in L_{1}, we have

∥f − A_{z}f∥_{L_{1}(X_{q})} ⩽ 2∥f∥_{L_{1}(X_{q})}.  (95)

Interpolating between (94) and (95) (see [57]) we get that for every 1 ⩽ p ⩽ 2,

∥f − A_{z}f∥_{L_{p}(X_{q})} ⩽ 2^{\frac{2}{p} −1} · (\frac{2}{q^{\frac{m}{2} −1}} )^{2− \frac{2}{p}} ∥f∥_{L_{p}(X_{q})} = 2 (q^{1− \frac{m}{2}} )^{2− \frac{2}{p}} ∥f∥_{L_{p}(X_{q})}.  (96)

Hence

∥max_{z∈𝔽_{q}} ||f| − A_{z} (|f|) |∥_{L_{p}(X_{q})} ⩽ (∑_{z∈𝔽_{q}} ∥||f| − A_{z} (|f|) |∥_{L_{p}(X_{q})}^{p})^{1/p}

⩽^{(96)} 2q^{1/p} (q^{1− \frac{m}{2}} )^{2− \frac{2}{p}} ∥f∥_{L_{p}(X_{q})}.

Thus

∥M_{q}f∥_{L_{p}(X_{q})} ⩽ (1 + 2q^{1/p} (q^{1− \frac{m}{2}} )^{2− \frac{2}{p}} ) ∥f∥_{L_{p}(X_{q})}

⩽ (1 + 2q^{1/p} (q^{\frac{3}{2} − \frac{\sqrt{q}}{2}} )^{2− \frac{2}{p}} ) ∥f∥_{L_{p}(X_{q})} ≲ \frac{∥f∥_{L_{p}(X_{q})}}{(p − 1)^{2}} . (97)

The last step in (97) can be proved as follows: for q ⩾ 36, the term 1 + 2q^{1/p} (q^{\frac{3}{2} − \frac{\sqrt{q}}{2}} )^{2− \frac{2}{p}} is ≲ 1 + q^{1−ε− \frac{ε\sqrt{q}}{2}} , where we write \frac{1}{p} = 1 − ε. Now consider the cases ε ⩾ \frac{2}{\sqrt{q}} and ε < \frac{2}{\sqrt{q}} separately. The bound (97) proves (86) when 1 ⩽ p ⩽ 2. The case p > 2 follows from a similar interpolation argument, using trivial bound ∥M_{q}f∥_{L_{∞}(X_{q})} ⩽ ∥f∥_{L_{∞}(X_{q})}.

To prove (87), let f =^{def} 1_{{0}} be the indicator function of the origin 0. Then ∥f∥_{L_{1}(X)} = 1. Since the sets \{E_{z}\}_{z∈𝔽_{q}} cover X_{q}, we see from (85) that M_{q}f(x) > \frac{q}{2μ(X_{q})} for all x ∈ X_{q}, and (87) follows (setting λ slightly larger than \frac{q}{2μ(X_{q})}).

Finally, let W_{−m+1} be the span of the first basis vector e_{1} ∈ X_{q} = 𝔽_{q}^{m}. Let S denote

the set of squares in 𝔽_{q}, i.e. S =^{def} \{x^{2} : x ∈ 𝔽_{q}\}. Since q is odd, |S| = \frac{q+1}{2}. Observe that (x_{1}, …, x_{m}) lies in E_{z} + W_{−m+1} if and only if x_{2}^{2} + … + x_{m}^{2} is in z − S. Arguing as in (92) we deduce that

μ (E_{z} + W_{−m+1}) = ∑_{s∈S} μ ((x_{1}, x_{2}, …, x_{m}) ∈ 𝔽_{q}^{m} : x_{2}^{2} + ⋯ + x_{m}^{2} = z − s)
= ∑_{s∈S} q |{(x_{2}, …, x_{m}) ∈ 𝔽_{q}^{m−1} : x_{2}^{2} + ⋯ + x_{m}^{2} = z − s}|

⩾ ∑_{s∈S} q (\frac{|𝔽_{q}^{m−1}|}{q} − \frac{|𝔽_{q}^{m−1}|}{q^{(m−1)/2}} )

= μ(X_{q}) (\frac{q + 1}{2q} − \frac{q + 1}{2q^{(m−1)/2}} ) .

This establishes the bound (88) for q sufficiently large. □

Remark 6.2. This example once again demonstrates the (well-known) fact that L_{2}-type smoothing estimates, such as those arising from smallness of Fourier coefficients, can imply L_{p} maximal bounds by standard interpolation arguments, but do not necessarily imply weaktype (1, 1) bounds.

6.3. The doubling example. We now prove Theorem 1.3. The claim is trivial for K ⩽ 48, so we will assume K ⩾ 48. By Bertrand’s postulate we may find an odd prime q between K/4 and K/2, which we now fix. We then let 𝔽_{q}, X_{q} and {E_{z}}_{z∈𝔽_{q}} be as in Proposition 6.2. Fix an arbitrary enumeration of the points in 𝔽_{q}, say 𝔽_{q} = {z_{1}, …, z_{q}} and write E_{z_{j}} = E_{j} (this will not create any ambiguity in what follows). It will also be convenient to set E_{0} = {0}. The maximal function M_{q} in Proposition 6.2 is not associated to a metric, let alone one with the doubling property (9), since the sets E_{j} are not nested. However, this can be remedied by extending the space X_{q} in the following fashion.

We let X =^{def} X_{q} × 𝔽_{q}^{q} be the Cartesian product of X_{q} with the vector space 𝔽_{q}^{q}, with counting measure μ. We also let

{0} = V_{0} ⊆ V_{1} ⊆ … ⊆ V_{q} = 𝔽_{q}^{q}

be the standard flag in 𝔽_{q}^{q}, thus V_{j} is the span of {e_{1}, …, e_{j}} for j ∈ {0, …, q}, where e_{1}, …, e_{q} is the standard basis of 𝔽_{q}^{q}. In particular

j ∈ {0, …, q} ⟹ μ(V_{j}) = q^{j}.  (98)

Recall that X_{q} is itself a vector space 𝔽_{q}^{m} over 𝔽_{q}, thus we have another flag

{0} = W_{−m} ⊆ W_{−m+1} ⊆ … ⊆ W_{0} = X_{q},

where

j ∈ \{0, …, m\} ⟹ μ(W_{−j}) = \frac{μ(X_{q})}{q^{j}}.  (99)

We can ensure that W_{−m+1} is the one-dimensional subspace mentioned in Proposition 6.2.

For v ∈ 𝔽_{q} let j(v) denote the minimal j ∈ {0, …, q} such that v ∈ V_{j}. For u ∈ X_{q} and j ∈ {0, …, q}, let ℓ_{j}(u) be the maximal ℓ ∈ {0, …, m} such that u ∈ E_{j} + W_{−ℓ}. Now, for (u, v), (u′, v′) ∈ X define

d((u, v), (u′, v′)) =^{def} 4^{j(v−v′)}1_{{v≠v′}} + 2^{−ℓ_{j(v−v′)}(u−u′)}1_{{u≠u′}}.  (100)

We claim that d is a translation invariant metric on X. The translation invariance and non-degeneracy of d are immediate from the definition. The symmetry of d follows from the fact that the E_{j} ⊆ X_{q} are symmetric around the origin. It therefore remains to verify that for all x, y ∈ X we have d(x + y, 0) ⩽ d(x, 0) + d(y, 0). Write x = (u, v), y = (u′, v′), j = j(v), j′ = j(v′), ℓ = ℓ_{j}(u), ℓ′ = ℓ_{j′}(u′). Without loss of generality j ⩾ j′. Then v ∈ V_{j} and v′ ∈ V_{j′} ⊆ V_{j}. So, v + v′ ∈ V_{j}, i.e., j(v + v′) ⩽ j. Denoting ℓ′′ = ℓ_{j(v+v′)}(u + u′), we see that it suffices to prove the inequality

4^{j}1_{{v+v′≠0}} + 2^{−ℓ′′}1_{{u+u′≠0}} ⩽ 4^{j}1_{{v≠0}} + 2^{−ℓ}1_{{u≠0}} + 4^{j′}1_{{v′≠0}} + 2^{−ℓ′}1_{{u′≠0}}  (101)

If j′ ⩾ 1 then v, v′ ≠ 0, and (101) holds since 4^{j′} ⩾ 4 ⩾ 2^{−ℓ′′}. On the other hand, if j′ = 0 (equivalently v′ = 0) then by definition u′ ∈ W_{−ℓ′}. Since u ∈ E_{j} + W_{−ℓ}, it follows that u + u′ ∈ E_{j} + W_{−ℓ} + W_{−ℓ′} = E_{j(v+v′)} + W_{− min{ℓ,ℓ′}}. Thus ℓ′′ ⩾ min{ℓ, ℓ′}, and (101) follows from the trivial inequality 2^{− min{ℓ,ℓ′}}1_{{u+u′≠0}} ⩽ 2^{−ℓ}1_{{u≠0}} + 2^{−ℓ′}1_{{u′≠0}}.

The balls in the metric d take the following form:

r ⩾ 4^{q} + 1 ⟹ B(0, r) = X,  (102)
∃j ∈ {1, …, q − 1}, 4^{j} + 1 ⩽ r < 4^{j+1} ⟹ B(0, r) = X_{q} × V_{j},  (103)
∃j ∈ {1, …, q − 1}, 4^{j} ⩽ r < 4^{j} + 2^{−m+1} ⟹ B(0, r) = (E_{j} × V_{j}) ∪ (X_{q} × V_{j−1}) , (104)

∃(j, ℓ) ∈ {1, …, q − 1} × {1, …, m − 1}, 4^{j} + 2^{−ℓ} ⩽ r < 4^{j} + 2^{−ℓ+1} ⟹ B(0, r) = ((E_{j} + W_{−ℓ}) × V_{j}) ∪ (X_{q} × V_{j−1}) , (105)

1 ⩽ r < 4 ⟹ B(0, r) = X_{q} × {0},  (106)
∃ℓ ∈ {1, …, m}, 2^{−ℓ} ⩽ r < 2^{−ℓ+1} ⟹ B(0, r) = W_{−j} × {0}.  (107)

We shall first of all prove that (X, d, μ) is doubling with constant 2q ⩽ K. For r ⩾ 4 take j ∈ {1, 2, …} such that 4^{j} ⩽ r < 4^{j+1}. If, in addition, 4^{j} + 1 ⩽ r < 4^{j+1} then since 2r < 4^{j+2}, it follows from (103), (104), (105) that B(x, 2r) ⊆ X_{q} × V_{j+1}, implying that

μ (B(0, 2r)) ⩽ μ (X_{q} × V_{j+1}) = q^{j+1}μ (X_{q}) ⩽ q · μ (X_{q} × V_{j}) =^{(103)} q · μ (B(0, r)) . (108)

On the other hand, if 4^{j} ⩽ r < 4^{j} + 1 then 4^{j} + 1 ⩽ 2r < 4^{j+1}. Note that (104), (105) imply that

E_{j} × V_{j} ⊆ B (0, r) ,  (109)

and therefore

μ (B(0, 2r)) =^{(103)} μ (X_{q} × V_{j}) = q^{j}μ(X_{q}) ⩽^{(85)} 2q^{j+1}μ (E_{j}) = 2qμ (E_{j} × V_{j}) ⩽^{(109)} 2qμ (B (x, r)) .

Similarly, using (106), (107), also for 0 < r < 4 we have μ (B(0, 2r)) ⩽ qμ (B(0, r)). Thus (X, d, μ) is doubling with constant 2q, as claimed.

Now, from (87) we can find f_{q} : X_{q} → ℝ_{+} with norm ∥f_{q}∥_{L_{1}(X_{q})} = 1 and λ > 0 such that

μ(M_{q}f_{q} > λ) > \frac{q}{2λ}.  (110)

We extend this function f_{q} to a function f : X → ℝ_{+} defined by f(x, y) =^{def} f_{q}(x) for x ∈ X_{q} and y ∈ 𝔽_{q}^{q}. Thus

∥f∥_{L_{1}(X)} = |𝔽_{q}^{q}| · ∥f_{q}∥_{L_{1}(X_{q})} = q^{q}.  (111)

We shall next compute M_{2^{ℤ}}f(x, y) for (x, y) ∈ X_{q} × 𝔽_{q}^{q} = X. Actually, for very minor technical reasons we need to consider the slight variant

M_{2^{ℤ}}^{ε}f(x, y) = sup_{r∈2^{ℤ}} \frac{1}{μ(B((x, y), (1 + ε)r))} ∫_{B((x,y),(1+ε)r)} |f(x, y)| dμ(x, y)  (112)

for some small ε > 0, but this clearly will not make a difference since we can rescale the metric by 1 + ε.

Observe that for any 1 ⩽ j ⩽ q we have

M_{2^{ℤ}}^{ε}f(x, y) ⩾ \frac{1}{μ (B(0, (1 + ε)4^{j}))} ∑_{(x′,y′)∈B(0,(1+ε)4^{j})} f_{q}(x + x′).

Note that if 0 < ε < 4^{−q} · 2^{−m+1} then it follows from (104) that

μ (B(0, (1 + ε)4^{j})) ⩽ μ(E_{j} × V_{j}) + μ(X_{q} × V_{j−1}) ⩽^{(85)} \frac{2}{q}μ(X_{q})q^{j} + μ(X_{q})q^{j−1} = 3q^{j−1}μ(X_{q}).

Using the inclusion B(0, (1+ε)4^{j}) ⊇ E_{j} ×V_{j}, which trivially follows from (104), we conclude that

M_{2^{ℤ}}^{ε}f(x, y) ⩾ \frac{1}{3q^{j−1}μ(X_{q})} ∑_{x′∈E_{j}} ∑_{y′∈V_{j}} f_{q}(x + x′).

Hence, in combination with (98) and (85), we get the bound

M_{2^{ℤ}}^{ε}f(x, y) ⩾ \frac{1}{6μ(E_{j})} ∑_{x′∈E_{j}} f_{q}(x + x′).

Taking the supremum over all j we conclude the pointwise estimate

M_{2^{ℤ}}^{ε}f(x, y) ⩾ \frac{1}{6}M_{q}f_{q}(x).

In particular we have

μ (M_{2^{ℤ}}^{ε}f > \frac{1}{6}λ) ⩾ |𝔽_{q}^{q}|μ (M_{q}f_{q} > λ) > q^{q} · \frac{q}{2λ}.

Recalling (111) we thus see that

∥M_{2^{ℤ}}^{ε}∥_{L_{1}(X)→L_{1,∞}(X)} ⩾ \frac{1}{12}q ⩾ \frac{K}{48},

yielding (19).

The only remaining task is to establish the L_{p} bounds ∥M∥_{L_{p}(X)→L_{p}(X)} ≲_{p} 1, for p > 1. To do this let’s examine what equations (102)–(107) say about the measures of the balls B(0, r) appearing in the definition of the maximal function M. For r < 4, the balls all take the form W_{−j} × {0} for some −m ⩽ −j ⩽ 0. For 4^{j} ⩽ r < 4^{j} + 2^{−m+1} for some 1 ⩽ j ⩽ q, the ball B(0, r) is equal to the union of the two sets E_{j} × V_{j} and X_{q} × V_{j−1}, which have the same measure up to a universal factor thanks to (85), (98). For 4^{j} + 2^{−m+1} ⩽ r < 4^{j+1}, we see that the ball B(0, r) lies between (E_{j} + W_{−m+1}) × V_{j} and X_{q} × V_{j}, and so thanks to (88) has measure comparable to X_{q} × V_{q}. Putting all this together, we obtain the pointwise bound

Mg(x, y) ≲ max_{−m⩽−j⩽0} \frac{1}{μ(W_{−j})} ∑_{x′∈x+W_{−j}} |g(x′, y)| + max_{0⩽j⩽q} \frac{1}{μ(X_{q})μ(V_{j})} ∑_{x′∈X_{q}} ∑_{y′∈y+V_{j}} |g(x′, y′)|

+ max_{0⩽j⩽q} \frac{1}{μ(E_{j})μ(V_{j})} ∑_{x′∈x+E_{j}} ∑_{y′∈y+V_{j}} |g(x′, y′)| (113)

for all functions g : X → ℝ.

If we let ℬ_{−j}, for −m ⩽ −j ⩽ 0, be the σ-algebra on X generated by the cosets of W_{−j} × {0}, we have

max_{−m⩽−j⩽0} \frac{1}{μ(W_{−j})} ∑_{x′∈x+W_{−j}} |g(x′, y)| = max_{−m⩽−j⩽0} 𝔼 [|g||ℬ_{−j}] (x, y),  (114)

where 𝔼 [|g||ℬ_{−j}] denotes the conditional expectation of |g| with respect to the σ-algebra ℬ_{−j}. Applying Doob’s maximal inequality (Proposition 2.1), we thus see that this expression is bounded on L_{p}, i.e.,

(∫_{X} | sup_{−m⩽−j⩽0} \frac{1}{μ(W_{−j})} ∑_{x′∈x+W_{−j}} |g(x′, y)||^{p} dμ(x, y))^{1/p} ⩽ \frac{p}{p − 1}∥g∥_{L_{p}(X)}.  (115)

A similar argument disposes of the second term in (113), i.e.,

(∫_{X} |max_{0⩽j⩽q} \frac{1}{μ(X_{q})μ(V_{j})} ∑_{x′∈X_{q}} ∑_{y′∈y+V_{j}} |g(x′, y′)||^{p} dμ(x, y))^{1/p} ⩽ \frac{p}{p − 1}∥g∥_{L_{p}(X)}. (116)

By combining (115) and (116) with (113), we see that it suffices to establish the bound

(∫_{X} |max_{0⩽j⩽q} \frac{1}{μ(E_{j})μ(V_{j})} ∑_{x′∈x+E_{j}} ∑_{y′∈y+V_{j}} |g(x′, y′)||^{p} dμ(x, y))^{1/p} ≲ (\frac{p}{p − 1})^{3} ∥g∥_{L_{p}(X)}. (117)

We can bound the left-hand side of (117) by

(∫_{X} |max_{0⩽j⩽q} \frac{1}{μ(V_{j})} ∑_{y′∈y+V_{j}} G(x, y′)|^{p} dμ(x, y))^{1/p} ,

where

G(x, y′) =^{def} max_{0⩽j⩽q} \frac{1}{μ(E_{j})} ∑_{x′∈x+E_{j}} |g(x′, y′)|.

Applying Doob’s maximal inequality again, we thus reduce to showing that

∥G∥_{L_{p}(X)} ≲ (\frac{p}{p − 1})^{2} ∥g∥_{L_{p}(X)}.

But this follows from (86) (and Fubini’s theorem). The proof of Theorem 1.3 is complete. □

6.4. The Ahlfors-David regular example. Now we prove Theorem 1.4. Once again we may take n to be large, as the claim is easy for bounded n (e.g., one could take the usual Hardy-Littlewood maximal function on ℝ^{n}).

The heart of our construction is the following lemma:

Lemma 6.1. There exists a finite Abelian group X, equipped with counting measure μ and an invariant metric d_{X}, with the following properties:

(1) The are integers a < b such that for all x, y ∈ X we have d_{X}(x, y) ∈ {0} ∪ {3^{j/n}}_{j=a}^{b}.

(2) For all r ∈ [3^{a/n}, 3^{b/n}] and all x ∈ X we have

3^{−a}r^{n} ⩽ μ(B(x, r)) ⩽ 3^{−a+3}r^{n}.  (118)

(3) ∥M∥_{L_{1}(X)→L_{1,∞}(X)} ≳ n log n.

(4) ∥M_{2^{ℤ}}∥_{L_{1}(X)→L_{1,∞}(X)} ≳ log n.

(5) For all 1 < p ⩽ ∞ we have ∥M∥_{L_{p}(X)→L_{p}(X)} ≲_{p} 1.

Proof of Theorem 1.4 assuming Lemma 6.1. In what follows 𝔽_{3} denotes the field of size 3. Let Y be the subspace of 𝔽_{3}^{ℵ_{0}} consisting of all finitely supported vectors, equipped with the counting measure ν. For (y_{1}, y_{2}, …) ∈ Y let j(y) denote the largest j ∈ ℕ such that y_{j} ≠ 0. If y = 0 we set j(y) = −∞. For y, y′ ∈ Y define

ρ_{Y} (y, y′) =^{def} 3^{b/n} · 3^{j(y−y′)/n}.

Then ρ_{Y} is an invariant ultrametric on Y, satisfying ρ_{Y} (y, y′) ∈ {0} ∪ {3^{(b+j)/n}}_{j=1}^{∞} for all y, y′ ∈ Y. Let Y_{j} ⊆ Y denote the set of vectors whose support is contained in the first j coordinates. Thus Y_{j} is a subspace of Y and Y_{j} = B_{ρ_{Y}} (0, 3^{(b+j)/n}). Since ν(Y_{j}) = 3^{j}, it follows that for all r ⩾ 3^{b/n} and y ∈ Y we have

3^{−b−1}r^{n} ⩽ ν (B_{ρ_{Y}} (y, r)) ⩽ 3^{−b}r^{n}.  (119)

Next, we let Z denote the set 𝔽_{3}^{ℵ_{0}}, and let τ denote the countable product of the normalized counting measure on 𝔽_{3}. Thus τ is an invariant probability measure on Z. For k ∈ ℕ let Z_{k} be the subspace of Z consisting of (z_{1}, z_{2}, …) ∈ Z with z_{1} = z_{2} = … = z_{k} = 0 (we shall also use the convention Z_{0} = Z). Thus τ(Z_{k}) = 3^{−k}. For z ∈ Z let k(z) denote the largest integer k ⩾ 0 such that z ∈ Z_{k} (with the convention k(0) = ∞). For z, z′ ∈ Z define

ρ_{Z}(z, z′) =^{def} 3^{(a−1)/n} · 3^{−k(z−z′)/n}.

Then ρ_{Z} is an invariant ultrametric on Z, satisfying ρ_{Z}(z, z′) ∈ {0} ∪ {3^{(a−j)/n}}_{j=1}^{∞} for all z, z′ ∈ Y. It follows from the definitions that for all k ⩾ 0 we have B_{ρ_{Z}} (0, 3^{(a−k−1)/n}) = Z_{k}. Let σ be the invariant measure on Z given by σ = 3^{a−1}τ. Thus for all r ⩽ 3^{a/n} we have,

\frac{1}{3}r^{n} ⩽ σ (B_{ρ_{Z}}(y, r)) ⩽ 3r^{n}.  (120)

We shall now let G be the Abelian group Z ×X ×Y, equipped with the ℓ_{∞} product metric d_{G} ((z, x, y), (z′, x′, y′)) = max {ρ_{Z}(z, z′), d(x, x′), ρ_{Y} (y, y′)} . We shall also equip G with the product measure μ_{G} = σ × μ × ν.

The balls in G are given by B_{d_{G}}(0, r) = B_{ρ_{Z}}(0, r) × B_{d_{X}}(0, r) × B_{ρ_{Y}} (0, r). If r ⩾ 3^{b/n} then B_{d_{X}}(0, r) = X, and thus by (118) we have μ (B_{d_{X}}(0, r)) ∈ [3^{b−a}, 3^{b−a+3}]. Similarly, for r ⩾ 3^{b/n} we have B_{ρ_{Z}}(0, r) = Z, and thus σ (B_{ρ_{Z}}(0, r)) = 3^{a−1}. It therefore follows from (119) that

r ⩾ 3^{b/n} ⟹ μ_{G} (B_{d_{G}}(0, r)) ∈ [\frac{1}{9}r^{n}, 9r^{n}] .  (121)

If 3^{a/n} ⩽ r < 3^{b/n}, then B_{ρ_{Y}} (0, r) = {0}, and hence ν (B_{ρ_{Y}} (0, r)) = 1. As before, we also have in this case σ (B_{ρ_{Z}}(0, r)) = 3^{a−1}, and by (118), μ (B_{d_{X}}(0, r)) ∈ [3^{−a}r^{n}, 3^{−a+3}r^{n}]. Thus,

3^{a/n} ⩽ r < 3^{b/n} ⟹ μ_{G} (B_{d_{G}}(0, r)) ∈ [\frac{1}{3}r^{n}, 9r^{n}] .  (122)

Finally, for r < 3^{a/n} we have B_{ρ_{Y}} (0, r) = {0} and B_{d_{X}}(0, r) = {0} and so ν (B_{ρ_{Y}} (0, r)) = μ (B_{d_{X}}(0, r)) = 1. In combination with (120), we see that

r < 3^{a/n} ⟹ μ_{G} (B_{d_{G}}(0, r)) ∈ [\frac{1}{3}r^{n}, 3r^{n}] .  (123)

Inequalities (121), (122), (123) show that the metric measure space (G, d_{G}, μ_{G}) is Ahlfors-David n-regular.

It remains to prove the estimates (20), (21), (22). By assertion (3) of Lemma 6.1 we can find f : X → ℝ_{+} with ∥f∥_{L_{1}(X)} = 1, and λ > 0, such that

μ (Mf > λ) ≳ \frac{n log n}{λ}.  (124)

Define a function g : G → ℝ_{+} by g(z, x, y) = f(x)1_{{y=0}}. Then ∥g∥_{L_{1}(G)} = σ(Z) = 3^{a−1}. Moreover, we have the pointwise estimate

Mg(x, y, z) ⩾ sup_{3^{a/n}⩽r⩽3^{b/n}} \frac{∫_{B_{ρ_{Z}} (0,r)×B_{d_{X}} (0,r)×B_{ρ_{Y}} (0,r)} f(x + x′)1_{\{z+z′=0\}}dμ_{G}(z′, x′, y′)}{μ_{G} (B_{ρ_{Z}}(0, r) × B_{d_{X}}(0, r) × B_{ρ_{Y}} (0, r))}

= (Mf(x)) 1_{{z=0}},

where we used the fact that B_{ρ_{Y}} (0, r) = {0} for r ⩽ 3^{b/n}. Thus by Fubini’s theorem,

μ_{G} (Mg > λ) ⩾ σ(Z)μ (Mf > λ) ≳^{(124)} 3^{a−1} \frac{n log n}{λ} = \frac{n log n}{λ}∥g∥_{L_{1}(G)}.

This proves (20); the proof of (21) is identical. To prove (22) take an non-negative h ∈ L_{p}(G), and observe the pointwise bound

Mh(z, x, y) ⩽ sup_{r<3^{a/n}} \frac{∫_{B_{ρ_{Z}} (0,r)} h(z + z′, x, y)dσ(z′)}{σ (B_{ρ_{Z}}(0, r))}  (125)

+ sup_{3^{a/n}⩽r⩽3^{b/n}} \frac{∫_{Z×B_{d_{X}} (0,r)} h(z′, x + x′, y)dσ(z′)dμ(x′)}{2^{a−1}μ (B_{d_{X}}(0, r))}  (126)

+ sup_{r>3^{b/n}} \frac{∫_{Z×X×B_{ρ_{Y}} (0,r)} h(z′, x′, y + y′)dσ(z′)dμ(x′)dν(y′)}{2^{a−1} · 3^{b−a}ν (B_{ρ_{Y}} (0, r))}, (127)

where in the denominator of (127) we used the fact that μ(x) ⩾ 3^{b−a}.

Since ρ_{Z} is an ultrametric, Doob’s maximal inequality implies that for all x ∈ X and y ∈ Y we have,

∫_{Z} ( sup_{r<3^{a/n}} \frac{∫_{B_{ρ_{Z}} (0,r)} h(z + z′, x, y)dσ(z′)}{σ (B_{ρ_{Z}}(0, r))})^{p} dσ(z) ≲_{p} ∫_{Z} h(z, x, y)^{p}dσ(z).

Thus, by Fubini’s theorem, the L_{p}(G) norm of the term in (125) is ≲_{p} ∥h∥_{L_{p}(G)}. A similar argument shows that the L_{p}(G) norm of the term in (127) is ≲_{p} ∥h∥_{L_{p}(G)}. Finally, using assertion (5) of Lemma 6.1, we get the same bound for the term in (126), proving (22). □

Proof of Lemma 6.1. Let q = 3^{k} be a power of three between \frac{1}{3}n log n and \frac{1}{9}n log n. We invoke Proposition 6.2 to create a vector space X_{q} = 𝔽_{q}^{m} over a finite field 𝔽_{q} with counting measure μ, together with sets E_{1}, …, E_{q} obeying the properties stated in Proposition 6.2; in particular

m ≲ \sqrt{n log n}.  (128)

Note that 𝔽_{q} can itself be viewed as a vector space over the field 𝔽_{3} of three elements, and thus X_{q} is a vector space over 𝔽_{3} of dimension

M =^{def} mk = m log_{3} q ≲ n^{1/2}(log n)^{3/2}.  (129)

As in Section 6.3, the idea is to take a Cartesian product of X_{q} with another vector space, and try to create balls which resemble the product of a set E_{j} with a subspace. Some care is however required in order to make the construction compatible with both the constraint (8) and the triangle inequality.

Analogously to the arguments in Section 6.3, we shall need a flag

{0} = W_{−M} ⊆ W_{−M+1} ⊆ … ⊆ W_{0} = X_{q}

of vector spaces over 𝔽_{3} in X_{q}, so that μ(W_{−j}) = 3^{−j}μ(X_{q}) for all −M ⩽ −j ⩽ 0. (We will not use (88) or the space W_{−m+1} in Proposition 6.2, so there is no collision of notation here.)

Our space shall be X =^{def} X_{q} × 𝔽_{3}^{q}, with counting measure μ. We shall need a flag

{0} = V_{0} ⊆ V_{1} ⊆ … ⊆ V_{q} = 𝔽_{3}^{q}

in 𝔽_{3}^{q}, with μ(V_{j}) = 3^{j}.

For every integer −M ⩽ j ⩽ q, we define the set B_{j} ⊆ X = X_{q} × 𝔽_{3}^{q} as follows:

• If −M ⩽ j ⩽ 0, we set B_{j} =^{def} W_{j} × {0}.

• If 1 ⩽ j ⩽ q, we set

B_{j} =^{def} (X_{q} × V_{j}) ⋃ ( ⋃_{ℓ=1}^{min{j+k,q}}(E_{ℓ} × V_{ℓ})) .  (130)

The B_{j} are symmetric and nested, with

{0} = B_{−M} ⊆ B_{−M+1} ⊆ … ⊆ B_{q} = X.  (131)

We define a function d : X × X → ℝ_{+} by setting d(x, x) = 0 for all x ∈ X, and

d(x, y) =^{def} min {3^{j/n} : x − y ∈ B_{j}} ,  (132)

for all distinct x, y ∈ X. Thus d takes values in {0} ∪ {3^{j/n} : −M + 1 ⩽ j ⩽ q}. The first assertion of Lemma 6.1 therefore holds with a = −M + 1 and b = q.

Claim 6.2. d is a translation-invariant metric on X.

Proof. The translation-invariance, non-degeneracy, and symmetry properties of d are obvious (symmetry follows from the symmetry of E_{j}). The only non-trivial task is to verify the triangle inequality. By construction, it will suffice to show that x + x′ ∈ B_{j′′−1} whenever x ∈ B_{j}, x′ ∈ B_{j′}, and −M < j, j′, j′′ ⩽ q are such that

3^{j′′/n} > 3^{j/n} + 3^{j′/n}.  (133)

By symmetry we may assume that j ⩽ j′. It follows from (133) that provided n is large enough,

3^{j′′/n} > 3^{j′/n} (1 + 3^{−(M+q−1)/n}) ⩾ 3^{j′/n} (1 + 3^{− \frac{1}{2} log n}) ⩾ 3^{(j′+k)/n},  (134)

where we used the fact that q ⩽ \frac{1}{3}n log n, while M ≲ n^{1/2}(log n)^{3/2} and k = log_{3} q ≲ log n.

It follows from (134) that

j′′ > j′ + k.  (135)

If j′ ⩽ 0, then we have B_{j} +B_{j′} = B_{j′}, so x+x′ ∈ B_{j′} ⊆ B_{j′′−k} ⊆ B_{j′′−1}, as required. Assume therefore that j′ ⩾ 1. Then B_{j} ⊆ B_{j′} ⊆ X_{q} ×V_{min{j′+k,q}}, and hence x+x′ ∈ X_{q} ×V_{min{j′+k,q}}. On the other hand, we will have X_{q} × V_{min{j′+k,q}} ⊆ B_{j′′−1} as soon as min{j′ + k, q} < j′′. Since j′′ ⩽ q, it follows from (135) that j′ + k < q. Hence, using (135) once more, we see that min{j′ + k, q} = j′ + k < j′′, as required. □

Claim 6.3. For all r ∈ [3^{−(M−1)/n}, 3^{q/n}] and all x ∈ X, we have

\frac{1}{3}r^{n} ⩽ \frac{μ(B(x, r))}{μ(X_{q})} ⩽ 4r^{n}.

Proof. By translation invariance we may assume that x = 0. Let j be the integer such that 3^{j/n} ⩽ r < 3^{(j+1)/n}. Then B(0, r) = B_{j}. If j ⩽ 0 then B_{j} = W_{j} × {0}, and hence

\frac{μ(B(x, r))}{μ(X_{q})} = \frac{μ(B_{j})}{μ(X_{q})} = 3^{j} ∈ [\frac{1}{3}r^{n}, r^{n}] .  (136)

If j ⩾ 1 the it follows from (130) that B_{j} ⊇ X_{q} × V_{j}, and hence

\frac{μ(B(0, r))}{μ(X_{q})} = \frac{μ(B_{j})}{μ(X_{q})} ⩾ μ(V_{j}) = 3^{j} ⩾ \frac{1}{3}r^{n}.  (137)

At the same time, it follows from (130) that

\frac{μ(B(0, r))}{μ(X_{q})} = \frac{μ(B_{j})}{μ(X_{q})} ⩽ 3^{j} + ∑_{ℓ=1}^{min\{j+k,q\}} \frac{μ(E_{ℓ})}{μ(X_{q})}μ(V_{ℓ}) ⩽^{(85)} 3^{j} + \frac{2}{q} ∑_{ℓ=1}^{min\{j+k,q\}} 3^{j}

⩽ 3^{j} + \frac{3}{q} · 3^{min\{j+k,q\}} = 3^{j} + \frac{3}{3^{k}} · 3^{min\{j+k,q\}} = 4 · 3^{j} ⩽ 4r^{n}, (138)

as required. □

Claim 6.3 implies the second assertion of Lemma 6.1, since μ(X_{q}) = 3^{M} = 3^{−a+1}.

We shall now prove the third assertion of Lemma 6.1. Since the balls B(x, r) in X take the form x + B_{j} for some j, we have

Mf(x) = max_{−M⩽j⩽q} \frac{1}{μ(B_{j})} ∑_{y∈B_{j}} |f(x + y)|.

¿From (87) we can find f_{q} : X_{q} → ℝ_{+} with ∥f_{q}∥_{L_{1}(X_{q})} = 1, and λ > 0, such that

μ (M_{q}f_{q} > λ) > \frac{q}{2λ}.  (139)

We extend this function f_{q} to a function f : X → ℝ_{+} defined by f(x, y) =^{def} f_{q}(x) for x ∈ X_{q} and y ∈ 𝔽_{3}^{q}. Thus,

∥f∥_{L_{1}(X)} = 3^{q}.  (140)

Observe that for 1 ⩽ j ⩽ q − k we have,

μ(B_{j}) ⩽^{(138)} 4μ(X_{q})3^{j} ⩽^{(85)} 8qμ(E_{j+k})μ(V_{j}) = 8μ(E_{j+k})μ(V_{j+k}).

Hence, for all (x, x′) ∈ X we have,

Mf(x, x′) ⩾ max_{1⩽j⩽q−k} \frac{1}{8μ(V_{j+k})μ(E_{j+k})} ∑_{(y,y′)∈B_{j}} |f_{q}(x + y)|.

Since B_{j} contains E_{j+k} × V_{j+k} for 1 ⩽ j ⩽ q − k, we conclude that

Mf(x, x′) ⩾ max_{k+1⩽ℓ⩽q} \frac{1}{8μ(E_{ℓ})} ∑_{y∈E_{ℓ}} |f_{q}(x + y)|

⩾ \frac{1}{8} (max_{1⩽j⩽q} \frac{1}{μ(E_{j})} ∑_{y∈E_{j}} |f_{q}(x + y)| − ∑_{j=1}^{k} \frac{1}{μ(E_{j})} ∑_{y∈E_{j}} |f_{q}(x + y)|) . (141)

Denote g : X → ℝ by g(x, x′) = ∑_{j=1}^{k} \frac{1}{μ(E_{j})} ∑_{y∈E_{j}} |f_{q}(x + y)|. Then

∥g∥_{L_{1}(X)} ⩽ k3^{q}∥f_{q}∥_{L_{1}(X_{q})} =^{(140)} ∥f∥_{L_{1}(X)} log_{3} q.  (142)

It follows from (141) that we have the pointwise bound M_{q}f_{q}(x) ⩽ 8Mf(x, x′) + g(x, x′). Thus,

\frac{q∥f∥_{L_{1}(X)}}{2λ} ⩽^{(139)∧(140)} μ ((x, x′) ∈ X : M_{q}f_{q}(x) > λ)
⩽  μ (8Mf + g > λ)
⩽  μ (Mf > \frac{λ}{16}) + μ (g > \frac{λ}{2})
⩽  μ (Mf > \frac{λ}{16}) + \frac{2∥g∥_{L_{1}(X)}}{λ}
⩽^{(142)} μ (Mf > \frac{λ}{16}) + \frac{2 log_{3} q∥f∥_{L_{1}(X)}}{λ} .

Hence,

∥M∥_{L_{1}(X)→L_{1,∞}(X)} ≳ q ≳ n log n,  (143)

which gives the third assertion of Lemma 6.1.

A similar argument (requiring a closer inspection of the details of Proposition 6.2) can be used to give the fourth assertion of Lemma 6.1; alternatively, one can use (143) and the pigeonhole principle to show that a dilated version M_{r·2^{ℤ}} of the lacunary maximal function has weak (1, 1) norm ≳ log n for some r > 0, and then rescale the metric. We omit the details.

It remains to verify the L_{p} bound in assertion (5) of Lemma 6.1, i.e., to show for all f ∈ L_{p}(X) we have

∥ max_{−M⩽j⩽q} \frac{1}{μ(B_{j})} ∑_{y∈B_{j}} |f(x + y)|∥_{L_{p}(X)} ≲_{p} ∥f∥_{L_{p}(X)}.

The contribution of the case −M ⩽ j ⩽ 0 can be handled by Doob’s maximal inequality as in Section 6.3, so we need only consider the case 1 ⩽ j ⩽ q. Using (138) and the definition of B_{j}, we soon verify the pointwise estimate

max_{1⩽j⩽q} \frac{1}{μ(B_{j})} ∑_{y∈B_{j}} |f(x + y)| ≲ max_{1⩽i⩽q} \frac{1}{μ(X_{q} × V_{i})} ∑_{y∈X_{q}×V_{i}} |f(x + y)|

+ max_{1⩽i⩽q} \frac{1}{μ(E_{i} × V_{i})} ∑_{y∈E_{i}×V_{i}} |f(x + y)|. (144)

Indeed, denote

h(x) = max_{1⩽i⩽q} \frac{1}{μ(X_{q} × V_{i})} ∑_{y∈X_{q}×V_{i}} |f(x + y)| + max_{1⩽i⩽q} \frac{1}{μ(E_{i} × V_{i})} ∑_{y∈E_{i}×V_{i}} |f(x + y)|.

Then for all 1 ⩽ j ⩽ q,

\frac{1}{μ(B_{j})} ∑_{y∈B_{j}} |f(x + y)| ≲^{(130)} \frac{∑_{y∈X_{q}×V_{j}} |f(x + y)| + ∑_{ℓ=1}^{min\{j+k,q\}} ∑_{y∈E_{ℓ}×V_{ℓ}} |f(x + y)|}{μ(B_{j})}

⩽^{(137)} \frac{h(x)μ (X_{q} × V_{j}) + ∑_{ℓ=1}^{min\{j+k,q\}} h(x)μ (E_{ℓ} × V_{ℓ})}{3^{j}μ(X_{q})} ⩽^{(138)} 4h(x),

proving (144).

The fact that the first term in the right-hand side of (144) is bounded in L_{p}(X) again follows from Doob’s maximal inequality, while the L_{p}(X) boundedness of the second term in the right-hand side of (144) follows from (86), Doob’s maximal inequality and a Fubini argument, as in Section 6.3. The proof of Theorem 1.4 is now complete. □

References

[1] J. M. Aldaz. The weak type (1, 1) bounds for the maximal function associated to cubes grow to infinity with the dimension. Preprint. Available at http://arxiv.org/abs/0805.1565, 2008.

[2] N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78–100, 1995.

[3] G. Aubrun. Maximal inequality for high-dimensional cubes. Confluentes Mathematici, 1:169–179, 2009.

[4] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pages 184–193. IEEE Comput. Soc. Press, Los Alamitos, CA, 1996.

[5] Y. Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas, TX), pages 161–168. ACM, New York, 1999.

[6] A. S. Besicovitch. A general form of the covering principle and relative differentiation of additive functions. Proc. Cambridge Philos. Soc., 41:103–110, 1945.

[7] A. S. Besicovitch. A general form of the covering principle and relative differentiation of additive functions. II. Proc. Cambridge Philos. Soc., 42:1–10, 1946.

[8] J. Bourgain. On high-dimensional maximal functions associated to convex bodies. Amer. J. Math., 108(6):1467–1476, 1986.

[9] J. Bourgain. On the L^{p}-bounds for maximal functions associated to convex bodies in R^{n}. Israel J. Math., 54(3):257–265, 1986.

[10] J. Bourgain. On dimension free maximal inequalities for convex symmetric bodies in R^{n}. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 168–176. Springer, Berlin, 1987.

[11] J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987.

[12] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358–372 (electronic), 2004/05.

[13] A. Carbery. An almost-orthogonality principle with applications to maximal functions associated to convex bodies. Bull. Amer. Math. Soc. (N.S.), 14(2):269–273, 1986.

[14] J. Cheeger. Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal., 9(3):428–517, 1999.

[15] J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisenberg group to L_{1}. Preprint. Available at http://arxiv.org/abs/0910.2026, 2009.

[16] M. Christ. A T (b) theorem with remarks on analytic capacity and the Cauchy integral. Colloq. Math., 60/61(2):601–628, 1990.

[17] R. R. Coifman and G. Weiss. Analyse harmonique non-commutative sur certains espaces homogènes. Lecture Notes in Mathematics, Vol. 242. Springer-Verlag, Berlin, 1971. Étude de certaines intégrales singulières.

[18] T. H. Colding and W. P. Minicozzi, II. Liouville theorems for harmonic sections and applications. Comm. Pure Appl. Math., 51(2):113–138, 1998.

[19] J. L. Doob. Stochastic processes. Wiley Classics Library. John Wiley & Sons Inc., New York, 1990. Reprint of the 1953 original, A Wiley-Interscience Publication.

[20] R. Dror, S. Ganguli, and R. S. Strichartz. A search for best constants in the Hardy-Littlewood maximal theorem. J. Fourier Anal. Appl., 2(5):473–486, 1996.

[21] R. Durrett. Probability: theory and examples. Duxbury Press, Belmont, CA, second edition, 1996.

[22] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004.

[23] V. Fischer. The spherical maximal function on the free two-step nilpotent Lie group. Math. Scand., 99(1):99–118, 2006.

[24] Z. Füredi and P. A. Loeb. On the best constant for the Besicovitch covering theorem. Proc. Amer. Math. Soc., 121(4):1063–1073, 1994.

[25] L. Grafakos, S. Montgomery-Smith, and O. Motrunich. A sharp estimate for the Hardy-Littlewood maximal function. Studia Math., 134(1):57–67, 1999.

[26] O. Guédon and A. Zvavitch. Supremum of a process in terms of trees. In Geometric aspects of functional analysis, volume 1807 of Lecture Notes in Math., pages 136–147. Springer, Berlin, 2003.

[27] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[28] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[29] A. J. Lemin. Isometric embedding of ultrametric (non-Archimedean) spaces in Hilbert space and Lebesgue space. In p-adic functional analysis (Ioannina, 2000), volume 222 of Lecture Notes in Pure and Appl. Math., pages 203–218. Dekker, New York, 2001.

[30] H.-Q. Li. Fonctions maximales centrées de Hardy-Littlewood sur les groupes de Heisenberg. Studia Math., 191(1):89–100, 2009.

[31] E. Lindenstrauss. Pointwise theorems for amenable groups. Invent. Math., 146(2):259–295, 2001.

[32] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993.

[33] J. Luukkainen and E. Saksman. Every complete doubling metric space carries a doubling measure. Proc. Amer. Math. Soc., 126(2):531–534, 1998.

[34] A. D. Melas. The best constant for the centered Hardy-Littlewood maximal inequality. Ann. of Math. (2), 157(2):647–688, 2003.

[35] M. T. Menárguez and F. Soria. On the maximal operator associated to a convex body in R^{n}. Collect. Math., 43(3):243–251 (1993), 1992.

[36] M. Mendel and A. Naor. Maximum gradient embeddings and monotone clustering. To appear in Combinatorica. Preprint available at http://arxiv.org/abs/cs.DS/0606109, 2006.

[37] M. Mendel and A. Naor. Ramsey partitions and proximity data structures. J. Eur. Math. Soc., 9(2):253– 275, 2007.

[38] D. Müller and A. Seeger. Singular spherical maximal operators on a class of two step nilpotent Lie groups. Israel J. Math., 141:315–340, 2004.

[39] F. Nazarov, S. Treil, and A. Volberg. The T b-theorem on non-homogeneous spaces. Acta Math., 190(2):151–239, 2003.

[40] A. Nevo and E. M. Stein. A generalization of Birkhoff’s pointwise ergodic theorem. Acta Math., 173(1):135–154, 1994.

[41] A. Nevo and S. Thangavelu. Pointwise ergodic theorems for radial averages on the Heisenberg group. Adv. Math., 127(2):307–334, 1997.

[42] R. Rochberg and M. Taibleson. Factorization of the Green’s operator and weak-type estimates for a random walk on a tree. Publ. Mat., 35(1):187–207, 1991. Conference on Mathematical Analysis (El Escorial, 1989).

[43] Y. Sawano. Sharp estimates of the modified Hardy-Littlewood maximal operator on the nonhomogeneous space via covering lemmas. Hokkaido Math. J., 34(2):435–458, 2005.

[44] R. Shvidkoy. A dimension-dependent maximal inequality. Proc. Edinb. Math. Soc. (2), 45(3):547–548, 2002.

[45] E. M. Stein. The development of square functions in the work of A. Zygmund. Bull. Amer. Math. Soc. (N.S.), 7(2):359–376, 1982.

[46] E. M. Stein. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.

[47] E. M. Stein and J.-O. Strömberg. Behavior of maximal functions in R^{n} for large n. Ark. Mat., 21(2):259– 269, 1983.

[48] J.-O. Strömberg. Weak type L^{1} estimates for maximal functions on noncompact symmetric spaces. Ann. of Math. (2), 114(1):115–126, 1981.

[49] M. Talagrand. Regularity of Gaussian processes. Acta Math., 159(1-2):99–149, 1987.

[50] M. Talagrand. The generic chaining. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes.

[51] T. Tao and V. Vu. Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006.

[52] Y. Terasawa. Outer measures and weak type (1, 1) estimates of Hardy-Littlewood maximal operators. J. Inequal. Appl., pages Art. ID 15063, 13, 2006.

[53] J. Tišer. Differentiation theorem for Gaussian measures on Hilbert space. Trans. Amer. Math. Soc., 308(2):655–666, 1988.

[54] A. L. Vol′berg and S. V. Konyagin. On measures with the doubling condition. Izv. Akad. Nauk SSSR Ser. Mat., 51(3):666–675, 1987.

[55] J.-M. Wu. Hausdorff dimension and doubling measures on metric spaces. Proc. Amer. Math. Soc., 126(5):1453–1459, 1998.

[56] J. Zienkiewicz. Estimates for the Hardy-Littlewood maximal function on the Heisenberg group. Colloq. Math., 103(2):199–205, 2005.

[57] A. Zygmund. Trigonometric series. Volumes I and II combined. With a foreword by Robert Fefferman. 3rd ed. Cambridge Mathematical Library. Cambridge: Cambridge University Press. xiii, 2002.