DYADIC PIGEONHOLES IN HARMONIC ANALYSIS

TERENCE TAO

Abstract. A manifesto urging greater use of the dyadic pigeonhole principle in harmonic analysis.

1. Introduction

The pigeonhole principle states that if c_{1}, …, c_{k} are non-negative quantities with c_{1} + … + c_{k} ≥ n, then there exists 1 ≤ i ≤ k such that c_{i} ≥ n/k.

This simple principle has many applications to harmonic analysis. For instance, if f and g are functions and if we desire to find a point x such that f(x) ≥ g(x), then it suffices to find a set E of non-zero measure such that

∫_{E} f(x) dx ≥ ∫_{E} g(x).

This is useful because sometimes the integral ∫_{E} f is easier to evaluate than f(x).

Exercise: if E and F are measurable subsets of a compact Lie group G, show that there exists group elements g, g′ ∈ G such that

|g(E) ∩ F | ≤ |E||F |/|G| ≤ |g′(E) ∩ F |

where |E| denotes the Haar measure of G. (This particular fact is very useful in factorization theory, and can be used to bootstrap weak-type (∞, p) results to weak-type (p, p) for operators invariant under the group action. See e.g. [1]). It is possible to replace the ≤ with equality, but this does not appear to be too useful.

However, the pigeonhole principle truly comes into its own when one uses dyadic pigeonholes. The power of this principle can be summarized in the following slogan:

Dyadic Pigeonhole Principle. If epsilons do not matter, then all non-negative functions are effectively simple functions (i.e. constant multiples of characteristic functions).

This allows for a substantial simplification in the analysis of many expressions in harmonic analysis, and especially in the study of maximal functions such as the Kakeya maximal function.

Of course, the notion of epsilons not mattering is a bit fuzzy. Here’s a rigorous formulation. Let A and B be positive quantities which depend on a parameter 0 < ε ≪ 1. We say that A ⪅ B with controlling parameters c_{1}, …, c_{k} > 0 if one has

A ≤ C_{ε} max_{1≤i≤k,±} c_{i}^{±ε}B.

1991 Mathematics Subject Classification. 42B.

If A ⪅ B ⪅ A, then we write A ≈ B. We will usually be quite fuzzy about what the controlling parameter is, as it is usually quite irrelevant (one epsilon is pretty much as good as any other).

Like the Uncertainty Principle (another fundamental tool in harmonic analysis), the Dyadic Pigeonhole Principle has many slightly different rigorous formulations, depending on the application. A typical one is

Lemma 1.1. Let 0 < p < ∞, ε > 0 and let f be a non-negative L^{p} function. Then there exists a simple function cχ_{E} such that we have the pointwise estimate f ≈ c on E and the norm estimate

c|E|^{1/p} ≈ ∥f∥_{p}

with controlling parameter c.

Proof Since

∑_{k∈Z} 2^{kp}|{2^{k−1} ≤ f < 2^{k}}| ≥ C^{−1} ∫ f^{p} = ∑_{k∈Z} C_{ε}^{−1}2^{−ε|k|}∥f∥_{p}^{p}

we see from the pigeonhole principle that there must exist an integer k such that

2^{kp}|{2^{k−1} ≤ f < 2^{k}}| ≥ C_{ε}^{−1}2^{−ε|k|}∥f∥_{p}^{p}.

The claim then follows by setting c = 2^{k} and |E| = {2^{k−1} ≤ f < 2^{k}} (the upper bound on c|E|^{1/p} follows immediately from the pointwise control on f).

One can easily tighten the c^{ε} factor to a logarithmic factor. One can also make |E| the controlling parameter instead of c if one wishes, although this usually does not make a difference. We’ll call c the (L^{p}) effective height of f, E the (L^{p}) effective support, and |E| the (L^{p}) effective base. It is not quite uniquely defined even for fixed p, but it does little harm to pretend that it is.

Thus, up to epsilons, the bulk of the L^{p} norm of a function is contained in a single simple function. Unfortunately, this simple function can depend on p; higher L^{p} norms tend to favour tall narrow simple functions, while lower L^{p} norms favour low broad simple functions. (Otherwise, the p-dependence of an L^{p} norm would be rather trivial, behaving like c|E|^{1/p} for some c and E). However, in practice we only want to control one L^{p} norm at a time, and so the above lemma is quite adequate.

This lemma already goes some way as to why restricted weak-type estimates

|⟨T χ_{E}, χ_{F} ⟩| ≲ |E|^{1/p}|F |^{1/q′}

are so close to strong-type estimates

|⟨T f, g⟩| ≲ ∥f∥_{p}∥g∥_{q′}

Exercise: Prove the restricted weak-type forms of Holder’s inequality, Young’s inequality, and fractional integration. (Since the first two are bilinear estimates, one of course needs the bilinear restricted weak-type formulation

|⟨T (χ_{E}, χ_{F}), χ_{G}⟩| ≲ |E|^{1/p}|F |^{1/q}|G|^{1/r′}

for these two estimates).

The point of the dyadic pigeonhole principle is that we can measure certain useful characteristics of functions as numeric quantities (effective height, effective base, etc.). Of course, one could argue that Lebesgue norms (and more sophisticated norms such as Morrey norms, Sobolev norms, etc.) also achieve this objective, but the quantities obtained from the dyadic pigeonhole principle tend to be more flexible.

The dyadic pigeonhole principle is especially useful for geometric maximal function type questions, such as considering the overlap of tubes. Here’s an example.

Proposition 1.2. [1] Let T_{1}, …, T_{N} be a collection of δ × 1 tubes in R^{n} such that any two intersecting tubes make an angle of ≳ δ. Then

| ⋃_{i=1}^{N} T_{i}| ⪆ \sqrt{N}δ^{n−1}

with controlling parameters δ, N.

Proof The counting function ∑_{i} χ_{T_{i}} has an L^{1} norm of Nδ^{n−1}. Thus, this function has an effective height μ and an effective support E such that μ|E| ≈ Nδ^{n−1} with controlling parameter μ (which can be replaced by N since 1 ≤ μ ≤ N).

We have two lower bounds on | ⋃_{i=1}^{N} T_{i}|. The first is the trivial

| ⋃_{i=1}^{N} T_{i}| ≥ |E|.

The second one is the bound

| ⋃_{i=1}^{N} T_{i}| ⪆ μδ^{n−1}.

This comes from the observation that if the counting function has a height of ⪆ μ at some point x, then there are ≈ μ tubes T_{i} passing through x. Since these tubes are all at an angle ≳ δ with respect to each other, they become essentially disjoint outside of a small ball such as B(x, 1/10), and the claim follows. Taking the geometric mean of the two estimates we get the result.

Once one has proven an estimate using the dyadic pigeonhole principle, one can sometimes go back and redo the argument without losing any epsilons whatsoever. Basically, one has to find non-pigeonhole analogues of pigeonhole arguments (or else break up functions into a dyadic sum of characteristic functions rather than a single characteristic function, and hope for some exponential decay somewhere to allow one to sum up). Algebraic manipulations of effective heights and bases usually become things like Hölder’s inequality (in all its guises) or Cauchy-Schwarz in the non-pigeonhole world. Another approach which works in simple cases is to replace the dyadic decomposition 2^{k−1} ≤ f < 2^{k} with a more elementary decomposition into two pieces, f < 2^{k_{0}} and f ≥ 2^{k_{0}}.

Exercise: Find a proof of the previous proposition which does not lose any epsilons. (Hint: there is an exponential gain available if |E| is very different from μδ^{n−1}. There are many ways to exploit this gain).

2. Tight estimates

As mentioned earlier, there is a problem with the dyadic pigeonhole principle when multiple L^{p} norms are involved because of non-uniformity - there can be more than one effective height and base if we are interested in multiple L^{p} norms. However this problem goes away when we have L^{p} estimates which are tight - where the lower bound we have on one norm is almost matched by an upper bound coming from interpolation between the two other norm estimates. In such cases we have only one effective height and base, and can in fact quantify their magnitude quite exactly. For instance:

Lemma 2.1. [4] Let f be a non-negative function supported on a set of measure ⪅ A, bounded above by ⪅ B, and has the lower L^{1} bound

∥f∥_{1} ⪆ AB.

Then for any 0 < p < ∞, f has an effective height of ≈ B and an effective support of size ≈ A in the sense of the dyadic Pigeonhole Principle.

Note that the lower bound on ∥f∥_{1} is matched by the trivial bound coming from the other two hypotheses on f. Proof Let cχ_{E} be the effective simple function of f for L^{1}. Then we have c|E| ≈ ∥f∥_{1} ⪆ AB, c ⪅ B, and |E| ⪅ A. This forces c ≈ B and |E| ≈ A, which in turn forces ∥f∥_{p} ⪆ BA^{1/p}. The claim then follows by repeating the above argument for L^{p} instead of L^{1}.

Exercise: Suppose that f is a non-negative function such that we have the reverse Hölder inequality

∥f∥_{2} ⪆ ∥f∥_{1}^{1/2}∥f∥_{∞}^{1/2}.

Show that f has only one effective height and base which works for all 1 < p < ∞, and determine these heights in terms of the L^{1} and L^{∞} norms of f. (Actually, they should be obvious from dimensional analysis).

Sometimes one has a lower bound on one quantity and an upper bound on another quantity, but lack a third bound to interpolate against and so the two bounds are not directly comparable. In this case one cannot reduce to a single effective height and support, but can place bounds on such a function. For instance:

Lemma 2.2. [3] Let T be a positivity-preserving linear operator and E, F be sets such that

⟨T χ_{E}, χ_{F} ⟩ = α|F | = β|E|

for some α, β > 0. Then there exists a subset F′ of F with

⟨T χ_{E}, χ_{F′}⟩ ≈ α|F | = β|E|

and

T χ_{E} ⪆ αχ_{F′}.

Similarly, there exists a subset E′ of E with

⟨T χ_{E′}, χ_{F} ⟩ ≈ α|F | = β|E|

and

T^{∗}χ_{F} ⪆ βχ_{E′}.

I’ll be vague about what the controlling parameter is; for this particular lemma, it turns out that one doesn’t actually need one (i.e. we can replace ⪅ by ≲, etc. Proof The function χ_{F} T χ_{E} has an L^{1} norm of α|F |, so we can find an effective simple function cχ_{F′} underneath χ_{F} T χ_{E} such that c|F′| ⪅ α|F |. Clearly F′ ⊂ F, so c ⪆ α, and we are done. The second half of the lemma comes by considering χ_{E}T^{∗}χ_{F} instead of χ_{F} T χ_{E}.

One can complement these lower bounds on T χ_{E} and T^{∗}χ_{F} if one assumes some sort of extremality hypothesis on E and F; this often puts constraints on the effective height and base of quantities such as χ_{F} T χ_{E}.

Exercise: Suppose that E, F maximize the quantity

\frac{⟨T χ_{E}, χ_{F} ⟩}{|E|^{1/p}|F |^{1/q′}}

for some 1 < p, q < ∞ over the range of all possible sets of non-zero finite measure^{1}, and let α, β be as above. Show the pointwise a.e. estimates

T χ_{E} ≳ αχ_{F} , T^{∗}χ_{F} ≳ αχ_{E}

and show that we can find sets E′ ⊂ E, F′ ⊂ F with |E′| ∼ |E|, |F′| ∼ |F |, T χ_{E} ∼ α on F′, and T^{∗}χ_{F} ∼ β on E′.

3. Effective separation

There are more numeric quantities out there than the effective height and base of a function. Given a bounded set E in R^{n}, one can also talk about the effective separation of E. Just as the height measures how high a function generally is, and the base measures the size of the set where the function is large, the effective separation of E measures how far two typical points in E are, or equivalently how large a ball one needs to contain a fair portion of E.

There are a couple ways to define effective separation. A simple one is to define the nuclear cube Q of E to be a cube of minimal side-length such that

|E ∩ Q| ≥ |Q|^{ε}|E|

and to define the effective separation σ to be the side-length of the essential cube Q. Define the nucleus E^{∗} to be E ∩ Q.

Exercise: Show that |E| ⪅ |Q| ⪅ 1, |E^{∗}| ≈ |E|, and

|E^{∗} ∩ q| ≲ (\frac{|q|}{|Q|})^{ε}|E^{∗}|

for all cubes q. All estimates have controlling parameter |E|.

Thus the nucleus E^{∗} contains the bulk of E, and are fairly evenly distributed throughout the nuclear cube Q.

Exercise: If two points x, y are chosen at random from E, show that |x − y| is comparable to the effective separation σ of E with probability ≈ 1.

This particular notion of separation will be exploited in the study of generalized Radon transforms along curves [8]. Here is one of the key lemmas:

Lemma 3.1. Let k ≥ 0 be an integer, and let P be a C^{k} function on [0, 1] with P^{(k)}(x) ≥ 1 for all x ∈ [0, 1]. Let E be a subset of [0, 1] with effective separation σ. Then

∫_{E} |P (x)| dx ⪆ σ^{k}|E|.

Proof We verify this for k = 1, and leave the general case as an exercise (or see [8]). Since P′(x) > 1, the set {x : |P (x)| ≪ σ} is contained in an interval of length ≪ σ. The portion of E^{∗} inside this set has measure at most \frac{1}{2}|E^{∗}| by the above exercise, so the set {x ∈ E^{∗} : |P (x)| ≳ σ} has measure ∼ |E^{∗}| ≈ |E|. The claim follows.

1Of course, such a maximum may not actually be attainable, but one can usually get around this technicality if one discretizes T or finds some other way to force compactness.

The bilinear approach to restriction and Kakeya problems (see e.g. [2], [7], [11]) also captures the concept of an effective angular separation. In [7] parabolic rescaling arguments are used to reduce to the case when the effective angular separation is comparable to 1. Cone multipliers can be treated similarly, using conformal Lorentz transformations instead of parabolic rescaling.

Unfortunately, not all angles are created equal, and in particularly delicate analysis of, say, the geometric intersections of tubes there may be more than one type of effective angular separation to deal with. The x-ray argument of Wolff [10] is an example of this; in addition to the main angular separation σ there is the plate angle w, the elevation angle ϕ, and a secondary angular separation restricted to those tubes passing through a single plate (also called σ). In fact, this paper closely follows the philosophy of assigning a number to every conceivable geometric measurement (angle, multiplicity, planarity, size of support, etc.) in the object under study. Another good use of this philosophy occurs in work on the distance set problem [12].

4. Iteration

We have assigned various numeric quantities (effective height, base, separation) to functions and sets. However, these quantities are not completely robust, in the sense that these quantities can change radically if we remove about half of the function or set. For instance, a set which is the union of a small number separated δ-intervals can have a large effective separation, but if one refines the set to a single δ-interval, then the effective separation can drop to just δ.

However, this difficulty can be mostly alleviated by iterating. For instance, suppose we have a set E_{0} with effective separation σ_{0}. A refinement E_{1} of E_{1} may have a smaller effective separation^{2} σ_{1} which may be much less than 1. However, we may keep going. A refinement E_{2} of E_{1} may have an effective separation of σ_{2}, and so forth, until we reach E_{100} (say), with a separation of σ_{100}.

Suppose each refinement E_{i} has comparable size to the previous set, |E_{i}| ≈ |E_{i−1}|, so that |E_{0}| ≈ |E_{100}|. Since we have |E_{i}| ⪅ σ_{i} ⪅ 1, we thus have

|E_{0}| ⪅ σ_{100} ⪅ σ_{99} ⪅ … ⪅ σ_{0} ⪅ 1.

By the pigeonhole principle again, we must be able to find 0 ≤ i ≤ 99 such that σ_{i+1} and σ_{i} are very close, indeed

|E_{0}|^{1/100}σ_{i} ⪅ σ_{i+1} ⪅ σ_{i}.

Indeed, we can even make a cluster of 10 σ_{i} close to each other:

|E_{0}|^{1/10}σ_{i} ⪅ σ_{i+9} ⪅ σ_{i+8} ⪅ … ⪅ σ_{i}.

Thus one can make geometric quantities such as effective separation fairly stable under refinement if one has the freedom to choose where to start (in this case, from E_{i}). This idea is exploited heavily in recent work on x-ray estimates [10], [5], and is also used for Radon transforms (see [8]; a variant occurs in [3]).

2As defined above, effective separation is not completely monotone, but this can be rectified by a small change in definition. See [8].

References

[1] J. Bourgain, Besicovitch-type maximal operators and applications to Fourier analysis, Geom. and Funct. Anal. 22 (1991), 147–187.

[2] J. Bourgain, Estimates for cone multipliers, Operator Theory: Advances and Applications, 77 (1995), 41–60.

[3] M. Christ, Curvature, combinatorics, and convolution: a case study, preprint.

[4] N. Katz, I. Łaba, T. Tao, An improved bound for the Minkowski dimension of Besicovitch sets in R^{3}, submitted to Annals of Math.

[5] I. Łaba, T. Tao, An x-ray estimate in R^{n}, submitted, Revista Mat. Iber.

[6] T. Tao, Endpoint bilinear restriction theorems for the cone, and some sharp null form estimates, submitted, Math Z.

[7] T. Tao, A. Vargas, L. Vega, A bilinear approach to the restriction and Kakeya conjectures, J. Amer. Math. Soc. 11 (1998), pp. 967–1000.

[8] T. Tao, J. Wright, L^{p} improving properties of averages over curves, submitted.

[9] T. Wolff: An improved bound for Kakeya type maximal functions, Revista Mat. Iberoamericana 11(1995), 651–674.

[10] T. Wolff: A mixed norm estimate for the x-ray transform, Revista Mat. Iberoamericana 14(1998), 561–601.

[11] T. H. Wolff, A sharp bilinear cone restriction estimate, to appear, Annals of Math.

[12] T. H. Wolff, Decay of circular means of Fourier transforms of measures, to appear, IMRN.

Department of Mathematics, UCLA, Los Angeles, CA 90024

  E-mail address: tao@math.ucla.edu