CHOPPING BIG TREES INTO LITTLE TREES

TERENCE TAO

Abstract. We give an argument (used in the literature on the Kato problem, and elsewhere) which (in the language of time-frequency analysis) allows one to decompose a tree of large size into the union of trees of small size. (This argument arose after discussions with Steve Hoffman, Loukas Grafakos, Alex Iosevich, and Xiaochun Li).

1. Introduction

Let n ≥ 1. The family of dyadic cubes Q in R^{n} are of course not disjoint, but can be made disjoint by lifting them to higher dimensions in a number of canonical ways. One way is to introduce the region [Q], which is basically the set [Q] := Q × [l(Q)/2, l(Q)] living in the space-scale space R^{n} × R. This set is traditional viewpoint for such objects as Carleson measures, harmonic extensions to the upper half-space, and similar objects. Another is to introduce the Haar tile

P (Q) := Q × ([−2/l(Q), 2/l(Q)]^{n}\[−1/l(Q), 1/l(Q)]^{n})

in phase space R^{n} × R^{n}. This is the viewpoint for time-frequency analysis. Our preference is toward the latter viewpoint, but in an attempt to avoid confusion, we shall adopt neither viewpoint explicitly, and work entirely with the dyadic cubes in R^{n}.

We define a tree T with top Q_{T} to be a collection T of dyadic cubes contained in Q_{T}, such that Q_{T} ∈ Q which has the convexity property that whenever Q_{1} ⊂ Q_{2} ⊂ Q_{3} and Q_{1}, Q_{3} ∈ T, that Q_{2} is also in T.

Suppose that to each cube Q we associate a non-negative quantity μ(Q). (One can think of this as a measure applied to [Q] or P (Q)). Henceforth this μ is fixed.

If T is a tree, we define the size of the tree by

size(T) := \frac{1}{|Q_{T} |} ∑_{Q∈T} μ(Q),

and the maximal size of the tree by

size_{∗}(T) := sup_{T′⊂T} size(T′).

This latter quantity is basically the Carleson measure norm of μ restricted to T. Suppose we have a tree T_{0} with a large size, let’s say

size_{∗}(T_{0}) ≤ C_{0}.

Let 0 < δ ≤ C_{0} be a small number. An obvious question to ask is whether one can decompose the large tree T_{0} into small trees, each of which has size less than or equal to δ. This is clearly impossible, as the example of a singleton tree T_{0} with large size demonstrates. However, one can do the next best thing:

1991 Mathematics Subject Classification. 42B15, 35L05.

Theorem 1.1. With the above assumptions, we have the disjoint partition

T_{0} := ⋃_{T ∈T} T ∪ P

where the trees T in T satisfy

size_{∗}(T) ≤ δ

and we have the tree counting estimate

∑_{T ∈T} |Q_{T} | + ∑_{Q∈P} |Q| ≤ C_{C_{0},δ}(1 − exp(−K_{C_{0},δ}size(T_{0})))|Q_{T_{0}}|.  (1)

In particular, we have

∑_{T ∈T} |Q_{T} | + ∑_{Q∈P} |Q| ≲ |Q_{T_{0}}|

where the implicit constant depends on C_{0} and δ.

The proof will be based on the following useful heuristic: Whenever uniformity breaks down, apply an induction hypothesis [or iterate]. This philosophy underlies the powerful technique of induction on scales, and similar methods (such as the two ends and bilinear reductions on the Kakeya problem, or of Bellman function techniques, or of good lambda inequalities, etc., etc.). Of course, there still remains the difficult problem of how to select the induction hypothesis correctly (for instance, I only found (1) after much trial and error). Proof Fix C_{0}, δ. We shall choose K = K_{C_{0},δ} sufficiently large, and then C_{C_{0},δ} sufficiently large depending on K; these assumptions shall be implicit in what follows. We may assume that the tree T_{0} is finite.

We induct on the cardinality of T_{0}. The claim is trivial when T_{0} is a singleton. Now suppose inductively that T_{0} is not a singleton, and the claim is already proven for all subtrees of T_{0}.

Let T_{fluctuate} denote all the subtrees T of T_{0} such that

|size(T) − size(T_{0})| ≥ δ/C_{n}

where C_{n} is a large constant (depending only on n) to be chosen later. Let T_{max} denote all the trees in T_{fluctuate} which are maximal with respect to set inclusion.

The idea is to apply the induction hypothesis to the trees in T_{max}, and show that everything else is either of small size or small width.

Observe that the tops {Q_{T} : T ∈ T_{max}} are necessarily disjoint (we always ignore sets of measure zero). In particular we have

∑_{T ∈T_{max}:Q_{T} ⊂Q_{0}} |Q_{T} | ≤ |Q_{0}|  (2)

for all Q_{0} ⊆ Q_{T_{0}}.

For each T ∈ T_{max}, we apply the induction hypothesis and decompose

T = ⋃_{T′∈T(T)} T′ ∪ P(T)

where T(T) is a collection of subtrees of T such that

size_{∗}(T′) ≤ δ for all T′ ∈ T(T)

and P(T) is a collection of dyadic cubes such that

∑_{T′∈T(T)} |Q_{T′}| + ∑_{Q∈P(T)} |Q| ≤ C_{C_{0},δ}(1 − exp(−Ksize(T)))|Q_{T} |.  (3)

Eventually we shall sum this estimate in T in order to obtain (1).

Let

P_{outer} := T_{0}\ ⋃_{T ∈T_{max}} T

denote all the dyadic cubes which are not contained in any of the trees in T_{max} (and hence not in any of the trees in T_{fluctuate}. This set contains Q_{T_{0}} and is thus non-empty. Define P_{buffer} to be the minimal elements of P_{outer} with respect to set inclusion, thus

∑_{Q∈P_{buffer}:Q⊂Q_{0}} |Q| = |Q_{0}|  (4)

for all Q_{0} ∈ P_{outer}. Eventually we shall place P_{buffer} in the set P.

Define the outer tree T_{outer} with top Q_{T_{0}} by

T_{outer} := P_{outer}\P_{buffer}.

We claim that

size_{∗}(T_{outer}) ≤ δ.

In other words, we claim

∑_{Q∈T_{outer};Q⊆Q_{0}} μ(Q) ≤ δ|Q_{0}|  (5)

for all dyadic cubes Q_{0}.

Fix Q_{0}. We may of course assume Q_{0} ⊆ Q_{T_{0}} and Q_{0} ⊂ P_{outer}. We may rewrite the left-hand side of (5) by

∑_{Q∈T_{0};Q⊆Q_{0}} μ(Q) − ∑_{Q′∈P_{buffer}:Q′⊂Q_{0}} ∑_{Q∈T_{0}:Q⊆Q′} μ(Q).

By definition of P_{outer}, we have

∑_{Q∈T_{0};Q⊆Q_{0}} μ(Q) = size(T_{0})|Q_{0}| + O(δ|Q_{0}|/C_{n})

and

∑_{Q∈T_{0}:Q⊆Q′} μ(Q) = size(T_{0})|Q′| + O(δ|Q′|/C_{n}).

The claim then follows from (5), if C_{n} is sufficiently large.

We now define

T := {T_{outer}} ∪ ⋃_{T ∈T_{max}} T(T)

and

P := P_{buffer} ∪ ⋃_{T ∈T_{max}} P(T).

All the desired properties have already obtained or are easily verified, with the exception of (1). Adding everything together, we see that the left-hand side of (1) is less than or equal to

C_{n}|Q_{T_{0}}| + ∑_{T ∈T_{max}} C_{C_{0},δ}(1 − exp(−Ksize(T)))|Q_{T} |.  (6)

The trees in T_{max} divide into two types, the heavy trees

T_{heavy} := {T ∈ T_{max} : size(T) > size(T_{0}) + δ/C_{n}}

and the light trees

T_{light} := {T ∈ T_{max} : size(T) < size(T_{0}) − δ/C_{n}}.

Thus (6) is less than or equal to

C_{n}|Q_{T_{0}}| + C_{C_{0},δ}(1 − exp(−Ksize(T)) exp(Kδ/C_{n})) ∑_{T ∈T_{light}} |Q_{T} | + C_{C_{0},δ}(1 − exp(−Ksize_{∗}(T_{0}))) ∑_{T ∈T_{heavy}} |Q_{T} |.

(7)

Define the quantity 0 ≤ θ ≤ 1 by

θ := \frac{1}{|Q_{T_{0}}|} ∑_{T ∈T_{heavy}} |Q_{T} |.

By the definition of T_{heavy}, we thus have

size(T_{0})|Q_{T_{0}}| ≥ ∑_{Q∈T_{0}} μ(Q) ≥ ∑_{T ∈T_{heavy}} ∑_{Q∈T} μ(Q) ≥ (size(T_{0}) + δ/C_{n})θ|Q_{T_{0}}|;

we thus have

1 − θ ≳ δ/C_{0}.  (8)

Also, we have

∑_{T ∈T_{light}} |Q_{T} | ≤ (1 − θ)|Q_{T_{0}}|.

We can thus bound (7) by

C_{C_{0},δ}|Q_{T_{0}}|(1−(exp(−Ksize(T_{0})) exp(Kδ/C_{n})−exp(−Ksize_{∗}(T_{0})))(1−θ)−exp(−KC_{0})+\frac{C_{n}}{C_{C_{0},δ}}).

Thus to imply (1) it suffices to show the bounds

(exp(−Ksize(T_{0})) exp(Kδ/C_{n}) − exp(−KC_{0}))(1 − θ) ≥ exp(−Ksize(T_{0}))

and

\frac{C_{n}}{C_{C_{0},δ}} ≤ exp(−KC_{0}).

But this follows from (8) by choosing K large enough depending on C_{0}, δ and then C_{C_{0},δ} large enough depending on K, C_{0}, δ.

An immediate corollary is the following. Suppose μ′(Q) is another set of nonnegative numbers (with attendant notions of size′ and size′_{∗}) such that we have

size′(T) ≲ 1 whenever size_{∗}(T) ≤ δ

for some small 0 < δ ≪ 1, as well as the “weak boundedness property”

μ′(Q) ≲ |Q| for all Q.

Then we have

size′_{∗}(T) ≲ 1 whenever size_{∗}(T) ≲ 1,

with the implicit constant depending on δ.

References

[1] P. Auscher, S. Hofmann, J. Lewis, P. Tchamitchian, Extrapolation of Carleson measures and the analyticity of Kato’s square root operators, preprint.

[2] S. Hofmann, J. Lewis, The Dirichlet problem for parabolic operators with singular drift terms, preprint.

[3] J. Lewis, M. Murray, The method of layer potentials for the heat equation in time-varying domains, Memoirs of the Amer. Math. Soc. 545 (1995)

Department of Mathematics, UCLA, Los Angeles, CA 90024

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