LECTURE NOTES 5 FOR 254A

TERENCE TAO

1. Overview

In this set of notes we return to the phase plane. This time, we will study the Walsh model of the phase plane as opposed to the standard Fourier model, the difference being that the underlying group is Z_{2}[[x]] rather than R. This model is less useful for applications (for instance, there is no good notion of a derivative, and hence there are no applications to PDE), however it is a good model for building intuition because it is “cleaner” than the Fourier model. For instance, in the Walsh model it is possible to localize both in space and frequency simultaneously.

To describe the Walsh model, we begin with the half-line R_{+}. Except on a set of measure zero (which we shall always ignore), every point x on R_{+} can be identified with a doubly-infinite set of binary digits

x = … a_{3}a_{2}a_{1}a_{0}.a_{−1}a_{−2}a_{−3} …

where a_{n} ∈ Z_{2} and a_{n} is eventually zero as n → +∞. We use a_{n}(x) to denote the n^{th} binary digit of x. We give this half-line a norm ∥x∥, defined to be the largest power of 2 which is less than or equal to x.

We give R^{+} the field structure of Z_{2}[[x]] (i.e. identifying binary strings with Z_{2}- valued Laurent polynomials ∑_{n} a_{n}x^{n}; this space can also be thought of as ZZ_{2}). By this, we mean that we define addition ⊕ on R^{+} by

a_{n}(x ⊕ y) := a_{n}(x) + a_{n}(y),

and multiplication ⊗ by

a_{n}(x ⊗ y) := ∑_{m∈Z} a_{m}(x)a_{n−m}(y).

These operations are just like ordinary addition and multiplication except one never carries a digit. These operations turn R^{+} into a field^{1} of characteristic two i.e. x ⊕ x = 0. (This means in particular that x ⊖ y = x ⊕ y, which has the pleasant effect that it is impossible to make sign errors.) The field is more “discrete” than R and takes some getting used to (e.g. the interval [0, 1] is closed under addition!). We give R^{+} the usual Lebesgue measure; this is invariant under Walsh translations x ↦ x ⊕ x_{0}, while for Walsh dilations we have

1To see the invertibility of ⊗, first observe that (1 ⊕ x)^{−1} = 1 ⊕ x ⊕ (x ⊗ x) ⊕ … when |x| < 1, and then generalize by scaling.

∫_{R_{+}} f(k ⊗ x) dx = \frac{1}{∥k∥} ∫_{R_{+}} f(x) dx.  (1)

(see Exercises). All integrals will be on R^{+} unless otherwise specified.

Note that R^{+} is a metric space under the metric d(x, y) := ∥x ⊕ y∥. This metric is not quite equivalent to the usual metric |x − y| (for instance, 1 − ε and 1 + ε are a distance 1 apart for any 0 < ε < 1) but is very similar.

On R one uses Schwartz functions or C_{0}^{∞} functions as the test functions to work on. The analogue in the Walsh model are dyadic step functions, defined as finite linear combinations of characteristic functions χ_{I}, where the I are dyadic intervals in R^{+}.

The Fourier analysis of R is fundamentally driven by the plane waves exp(2πixξ). The Walsh analogue of this is the dyadic plane waves e(x ⊗ ξ), where e : R^{+} → {−1, +1} is defined by e(x) := +1 when a_{−1}(x) = 0 and e(x) := −1 when a_{−1}(x) = 1. Thus the graph of e(x) is just a square wave with period 1 - it’s the Walsh analogue of exp(2πix). One minor pleasantness in the Walsh case is that e is always real, thus avoiding the need for complex numbers. Also, note that e() is multiplicative in the sense that e(x ⊕ y) = e(x)e(y). We can then define the Walsh-Fourier transform, defined on dyadic step functions f by

f̂(ξ) := ∫ e(x ⊗ ξ)f(x) dx.

The Walsh-Fourier transform maps dyadic step functions to dyadic step functions, and its own inverse. Note that the function χ_{[0,1]} is its own Walsh-Fourier transform. (We delegate this to the exercises). This function plays the same role in Walsh-Fourier analysis that the Gaussian e^{−πx^{2}} plays in Fourier analysis. Note that unlike the Gaussian, we have perfect localization in both space and frequency simultaneously (which we know to be impossible on R).

By scaling and translating the Walsh Gaussian χ_{[0,1]} we obtain the handy formula

χ̂_{I}(ξ) := |I|χ_{[0,|I|^{−1}]}(ξ)e(x_{I}ξ)  (2)

for all dyadic intervals I, where we use x_{I} to denote an arbitrary element of I.

The Walsh-Fourier transform has basically the same properties as the Fourier transform: translation in space corresponds to modulation by dyadic plane waves on the frequency side, and vice versa; scaling by k in physical space corresponds to scaling by k^{−1} in frequency space; multiplication goes to Walsh convolution and vice versa; and we have the Parseval and Plancherel theorems. The proofs are identical to the corresponding statements in the Fourier case.

Now we look at what frequency projections look like. Specifically, we want to understand the frequency projections π_{ω} for dyadic intervals^{2} ω, defined by

π̂_{ω}f(ξ) := χ_{ω}(ξ)f̂(ξ).

Let’s first understand this for the case ω = [0, 1]. In this case we have

π_{[0,1]}f(x) = f ∗ χ̂_{[0,1]}(x) = f ∗ χ_{[0,1]}(x) = ∫ f(y)χ_{[0,1]}(x ⊕ y) dy.

If x lies in the interval (n, n + 1), we thus have

π_{[0,1]}f(x) = ∫_{n}^{n+1} f(y) dy,

More generally, if k ∈ Z and x lies in the dyadic interval (2^{−k}n, 2^{−k}(n + 1)), then

π_{[0,2^{k}]}f(x) = 2^{k} ∫_{2^{−k}n}^{2^{−k}(n+1)} f(y) dy.

Thus π_{[0,2^{k}]} is an averaging operator at spatial scale 2^{−k}. (Compare this with the Fourier situation). Shifting this by some frequency ξ, we see that

π_{[ξ,ξ⊕2^{k+1}]}f(x) = 2^{k}e(ξ ⊗ x) ∫_{2^{−k}n}^{2^{−k}(n+1)} e(ξ ⊗ y)f(y) dy.

In particular, we have

π_{[2^{k},2^{k+1}]}f(x) = 2^{k}e(2^{k} ⊗ x) ∫_{2^{−k}n}^{2^{−k}(n+1)} e(2^{k} ⊗ y)f(y) dy.

To understand this better, let’s have some notation. For any dyadic interval I, define the parent 2I of this interval to be the unique dyadic interval containing I of twice the length. The interval 2I is thus the union of I and another interval I^{∗}, which we call the conjugate of I. We then have

π_{[2^{k},2^{k+1}]}f(x) = \frac{1}{2}(\frac{1}{|I|} ∫_{I} f − \frac{1}{|I^{∗}|} ∫_{I^{∗}} f),

where I is the unique dyadic interval of length 2^{−k−1} which contains x. This operator is the analogue of the Littlewood-Paley projection P_{k} - note how it captures precisely the mean and averaging properties we were heuristically deducing in the Week 2 notes (averaging at scale 2^{−k−1}, but mean zero at scale 2^{−k}).

Let’s see how the frequency cutoffs π_{ω} interact with spatial cutoffs χ_{I}. From our formula for π_{[0,1]} we see that π_{[0,1]} commutes with χ_{I} whenever the dyadic interval I has length at least 1. More generally (by scaling and modulation) we see that π_{ω} commutes with χ_{I} whenever I × ω has area at least 1. This fact is extremely pleasant, and is not quite present in the Fourier case (any projection in frequency space must cause leakage in physical space, and vice versa, so there is no way physical and Fourier cutoffs can commute). We can thus define phase space projections

π_{I×ω} := π_{ω}χ_{I} = χ_{I}π_{ω}

whenever I × ω respects the Heisenberg uncertainty principle (i.e. has area at least 1). Observe that this really is a projection in that it is self-adjoint and idempotent (as opposed to the Fourier case, in which all smoothed out projections are only projections in a moral sense).

2Conventionally, intervals in physical space are given names like I, while intervals in frequency space are given names like ω.

Consider the projection π_{[0,1]×[0,1]}. From our formula for π_{[0,1]} we see that

π_{[0,1]×[0,1]}f := (∫_{[0,1]} f)χ_{[0,1]},

i.e. π_{[0,1]×[0,1]} is the orthogonal rank 1 projection (in L^{2}(R^{+}) to the line spanned by the dyadic Gaussian χ_{[0,1]}. More generally, if P = I × ω is a Heisenberg tile, i.e. a dyadic rectangle of area exactly 1, then π_{P} is the orthogonal rank 1 projection to the line spanned by the Walsh wave packet (or Walsh function)

ϕ_{P} (x) := |I|^{−1/2}e(ξ_{ω}x)χ_{I}(x).

(In principle, the choice of ξ_{ω} could affect the definition of ϕ_{P}, but one can check that this only affects ϕ_{P} by a sign, which turns out to always be irrelevant). In other words, since we have defined ϕ_{P} to be L^{2}-normalized, we have

π_{P} f = ⟨f, ϕ_{P} ⟩ϕ_{P} .

(This result can be deduced from the P = [0, 1] × [0, 1] case by translation, modulation, and scaling).

Since π_{I×ω} is a rank 1 projection, we see that there is only a one-dimensional family of functions which have spatial support in I and frequency support in ω, namely the constant multiples of ϕ_{P}.

It is instructive to compare some examples of wave packets ϕ_{P}, when P is some integer shift of the unit square [0, 1]^{2}, with their Fourier counterparts, namely the Gaussian translated and modulated by integer amounts. One is made of square waves and the other of sine waves, but otherwise they are very similar.

If P = I ×ω is a tile, we write I_{P} for the spatial interval I and ω_{P} for the frequency interval ω. Tiles have the nice property that given any two tiles which intersect, one of them is wider than the other and the spatial interval of the narrower one is contained in that of the wider one. Conversely, the frequency interval of the wider one is contained in that of the narrower one (so the narrower interval is taller). More succinctly, if we define P < P′ as the statement that P and P′ intersect and that I_{P} ⊂ I_{P′}, then < is a partial order and one has P < P′ or P′ < P if and only if P ∩ P′ ≠ ∅.

Observe from (2) that the Walsh-Fourier transform of a Walsh wave packet is another Walsh wave packet, up to a sign:

ϕ̂_{I×ω} = ±ϕ_{ω×I}.

Thus the Walsh-Fourier transform intertwines π_{I×ω} and π_{ω×I}. As a consequence of this and Plancherel we see that ϕ_{I×ω} and ϕ_{I′×ω′} are orthogonal whenever I and I′ are disjoint, or ω and ω′ are disjoint. In other words,

⟨ϕ_{P} , ϕ_{P′}⟩ = 0 whenever P ∩ P′ = ∅.

In other words, the projections π_{P} and π_{P′} are orthogonal to each other whenever P ∩ P′ = ∅.

This suggests putting together several disjoint tiles (which correspond to rank 1 projections) to create higher rank projections. To make this formal, we first observe from our formulae for π_{P} that

π_{P} f(x) = |I|^{−1}χ_{I}(x)e(ξ_{ω}x) ∫ f(y)χ_{I}(y)e(ξ_{ω}y) dy.

We use Plancherel:

π_{P} f(x) = |I|^{−1}χ_{I}(x)e(ξ_{ω}x) ∫ f̂(ξ)χ̂_{I}(ξ ⊕ ξ_{ω}) dξ.

Now we use (2):

π_{P} f(x) = χ_{I}(x)e(ξ_{ω}x) ∫ f̂(ξ)χ_{ω}(ξ)e((ξ ⊕ ξ_{ω}) ⊗ x_{I}) dξ.

Observe that

(x ⊕ x_{I}) ⊗ (ξ ⊕ xi_{ω}) = 0

for all (x, ξ) ∈ I × ω. We can thus rewrite this formula as

π_{P} f(x) = ∫ χ_{P} (x, ξ)e(x, ξ)f̂(ξ) dξ.

Because of this, it is tempting to define the phase space projection

π_{Ω}f(x) := ∫ χ_{Ω}(x, ξ)e(x, ξ)f̂(ξ) dξ

for arbitrary Ω. It turns out this is only useful for Ω which respect the uncertainty principle, in the sense that they can be written as the union of disjoint tiles. Clearly, for such Ω we have

π_{Ω} = ∑_{P ∈P} π_{P}

whenever P is a collection of disjoint tiles which tile Ω; since each tile has area 1, the cardinality of P must equal the area |Ω| of Ω. From this and orthogonality of the π_{P} we see that π_{Ω} is a rank |Ω| projection. It is also clear that any function of the form π_{Ω} has spatial support in {x : (x, ξ) ∈ Ω for some ξ} and frequency support in {ξ : (x, ξ) ∈ Ω for some x}. (Virtually none of these properties are retained if Ω does not respect the uncertainty principle).

For future reference we shall need

Lemma 1.1. If Ω respects the uncertainty principle, and P is a tile which is strictly contained inside Ω, then Ω − P also respects the uncertainty principle.

Proof By definition, Ω is the union of a disjoint collection of tiles Q_{1}, …, Q_{N}. If one of these Q_{i} were equal to P, we would be done. Otherwise, the idea is to shuffle the Q around until one of them does equal P.

We may throw away all the Q_{j} which don’t intersect P (and shrink Ω accordingly), since they can always be added back later. Now observe it is impossible for one of the Q_{j} to be wider than P and another to be taller than P, otherwise we would contradict disjointness. By symmetry we may thus assume that all the Q_{j} are wider than P.

Let Q_{wide} be a tile Q_{j} with maximal width. Consider the tile Q_{wide}^{∗}, defined as the tile with the same spatial interval as Q_{wide} but the conjugate frequency interval. This tile also intersects P, and thus must encounter some Q_{j}. Q_{j} cannot be taller than Q_{wide}, else it would intersect Q_{wide}, and it cannot be wider, by definition of Q_{wide}. Thus it must be Q_{wide}^{∗}. In other words, Q_{wide} and Q_{wide}^{∗} are both in the collection of Q_{j}. We can then replace Q_{wide} ∪ Q_{wide}^{∗} by the union of two tiles of half the width and twice the height. One of these does not intersect P and can thus be thrown away. Continuing in this way we may remove more and more tiles from the Q_{j} until eventually one of them is equal to P, at which point we are done.

Observe that π_{I×R^{+}} corresponds to the spatial projection χ_{I}. To see this, first see that it is true for any Walsh wave packet on a tile P in I × R^{+} (since one can use P to begin a tiling of I × R^{+}). From this it is clear that it is true for any function on I, and outside I it is clear that the projection vanishes. Similarly π_{R^{+}×ω} equals π_{ω}.

Sometimes it is convenient to pass from the Walsh continuum to a discrete analogue. Suppose that 0 < a < A are integers, and a dyadic step function f is supported on an interval [0, 2^{A}], but is constant on dyadic intervals of length 2^{a}. Thus 2^{a} is the smallest interesting scale and 2^{A} is the largest interesting scale. Then f is a convolution of a function with χ_{[0,2^{a}]}, and so its Fourier support is contained in that of χ_{[0,2^{a}]}, i.e. f̂ is supported on [0, 2^{−a}]. Conversely, f is a product of a function with χ_{[0,2^{A}]}, hence f̂ is a convolution of a function with 2^{A}χ_{[0,2^{−A}]}. Thus f̂ is constant on dyadic intervals of length 2^{−A}. Thus on the frequency side, 2^{−A} is the smallest interesting scale and 2^{−a} is the largest.

We can then discretize physical space to the discrete interval (which is a subgroup of R^{+})

I_{a,A} := 2^{a}Z ∩ [0, 2^{A})

and frequency space to the dual interval I_{−A,−a}, so that phase space is discretized to I_{a,A} × I_{−A,−a}. One can give these intervals normalized counting measure

μ_{a,A}(E) := 2^{−a}#(E)

so that phase space has measure μ_{a,A} ⊗ μ_{−A,−a}. One can then define the Walsh-Fourier transform on these discrete spaces as usual, and one has analogues of all the previous statements.

For instance, when a = −1, A = 0, then functions only have two values, f(0) and f(.1) (here 0.1 is 1/2, not 1/10!), and the Fourier transform only has two values, f̂(0) = (f(0) + f(.1))/2 and f̂(1) = (f(0) − f(.1))/2. Phase space consists of four points, and there are four tiles one can play with.

We won’t use discretized models much in this course, but they are handy for building up intuition.

Let’s return to the phase space projections π_{Ω}, defined for sets Ω which respect the uncertainty principle. Observe that π_{Ω}f and π_{Ω′}f are orthogonal whenever Ω, Ω′ respect the uncertainty principle and are disjoint. In particular we have

∥π_{Ω∪Ω′}f∥_{2}^{2} = ∥π_{Ω}f∥_{2}^{2} + ∥π_{Ω′}f∥_{2}^{2}.  (3)

Also, we clearly have

∥∥π_{Ω}f∥_{2}^{2} ≥ 0.

Thus the quantity ∥∥π_{Ω}f∥_{2}^{2} is behaving like some sort of non-negative measure on the phase plane. It’s almost as if there was some function W (f, f)(x, ξ) on phase space for which

W (f, f)(x, ξ) ≥ 0 for all x, ξ  (4)

and

∥∥π_{Ω}f∥_{2}^{2} = ∫_{Ω} W (f, f) for all Ω which respects the uncertainty principle. (5)

We are writing W (f, f) because the expression is clearly quadratic in f. To make this rigorous, it would be nice if W (f, f) was just a special case of some W (f, g) such that

W (f, g) is linear with respect to f or g.  (6)

Also, by taking Ω = I × R in (5) and letting I shrink to a point we see that

|f(x)|^{2} = ∫ W (f, f)(x, ξ) dξ  (7)

and similarly

|f̂(ξ)|^{2} = ∫ W (f, f)(x, ξ) dx  (8)

thus |f̂|^{2} and |f|^{2} are the marginal distributions of W (f, f). Combining this with (4), we see that

f has physical support in I ⟹ W (f, f) has support in I × R^{+}  (9)

and

f has frequency support in ω ⟹ W (f, f) has support in R^{+} × ω (10)

It would also be nice if translating f in physical space corresponded to translating W (f, f) in the x variable, and similarly for frequency space and the ξ variable, that scaling f by k in physical space in an L^{2}-preserving manner should just replace W (f, f)(x, ξ) by W (f, f)(k^{−1} ⊗ x, k ⊗ ξ). If all these properties held, then W (f, f) would be a realization of the ideal we discussed in the Week 1 notes, namely a phase space portrait of f. W (f, f) would somehow be the probability density of f at (x, ξ), measuring how much of f had a position at x and frequency at ξ. (The functions |f(x)|^{2} and |f(ξ)|^{2} only do this for one of the two variables).

It turns out that such W do not actually exist, but one can find candidates which almost obey all of the above properties.

For instance, the function

W (f, g)(x, ξ) := f(x)g(ξ)

obeys all the properties desired except for the non-negativity property (4). The only one which is remotely tricky is (5). By (3) it suffices to do this when Ω is a tile; by translation, modulation, and scaling we can set the tile to be [0, 1]^{2}. Then we have

∫_{[0,1]^{2}} W (f, f) = ∫_{0}^{1} ∫_{0}^{1} f(x)f̂(ξ) dxdξ = ⟨f, χ_{[0,1]}⟩⟨f̂, χ_{[0,1]}⟩ = | ∫_{[0,1]} f|^{2} = ∥π_{[0,1]^{2}}f∥_{2}^{2}

as desired.

Example: In the discrete model a = −1, A = +1 mentioned earlier, we have W (0, 0) = f(0)(f(0)+f(.1))/2, W (.1, 0) = f(1)(f(0)+f(.1))/2, W (0, 1) = f(0)(f(0)− f(.1))/2, and W (.1, 1) = f(1)(f(0) − f(.1))/2. Note that W is not always positive, but its average on any set which respects the uncertainty principle is positive. This is a good example of things being weird at the quantum level but seemingly okay at the classical level.

There are many other choices of W (f, g) which would work. For instance, any expression of the form

W (f, g)(x, ξ) := ∫ f(x ⊕ (a ⊗ t))g(x ⊕ (b ⊗ t))e(ξ ⊗ t) dt

will work, if a, b are numbers such that a ⊕ b = 1. (Note that a = 0, b = 1 corresponds to the form f(x)g(ξ) used earlier). Bilinear expressions of this type are known as Walsh-Wigner transforms. The Fourier analogue is

W (f, g)(x, ξ) := ∫ f(x + at)g(x − bt)e^{−2πiξt} dt

where a + b = 1; when a = b = 1/2, this is known as the Wigner transform of f and g.

Now let’s see why one cannot find such a W with all the properties required (including (4)). Since W (f, g)(0, 0) is bilinear, it must have the form

W (f, g)(0, 0) = ∫ ∫ f(x)g(y)K(x, y) dxdy

for some kernel K, possibly distributional. From (9) and polarization we see that W (f, g) vanishes whenever f, g are supported on a dyadic interval I not containing the origin. In particular K vanishes on I × I in this case, which implies that K(x, x) = 0 for all x ≠ 0. On the other hand, the positivity condition (4) enforces (morally at least) the condition K(x, y)^{2} ≤ K(x, x)K(y, y) (i.e. every two-by-two minor of K must be non-negative). This implies that K vanishes everywhere except at the origin, which means that W (f, g)(0, 0) = cf(0)g(0) for some constant c. But this is easily seen to disobey (10).

On the other hand, if one gives up the linearity condition (6), then one can grab (4):

Proposition 1.2. Let f be a dyadic step function. Then there exists a non-negative function W (f, f) on the phase plane which obeys (5).

One can also make this function obey all the other properties required (other than linearity), but we shall not try to do so here.

Proof We are looking for a non-negative function W (f, f) such that

⟨W (f, f), χ_{P} ⟩ = ∥π_{P} f∥_{2}^{2}

for all tiles P (the claim (5) then follows by (3)).

Let’s first do some linear programming^{3}. Consider the set Σ ⊂ L^{2}(R^{+}) as the affine span of the functions −χ_{P} /∥π_{P} f∥_{2}^{2}; this has the form v_{0} + V for some vector space V ⊂ L^{2}(R^{+}) and v_{0}inL^{2}(R^{+}). Also, consider the positive cone Γ defined by

Γ := {f ∈ L^{2}(R^{+}) : f(x) ≥ 0 for all x ∈ R^{+}.}

Clearly we must have ⟨W (f, f), F ⟩ = −1 for all F in the affine space Σ. Thus if Σ intersects Γ, no such W (f, f) is possible. On the other hand, if Σ is disjoint from Γ, then by repeating the standard proof of the Hahn-Banach theorem we can find an affine hyperspace containing Σ which is disjoint from Γ. This hyperspace does not go through the origin, and so has the form {F ∈ L^{2} : ⟨W (f, f), F ⟩ = −1} for some W (f, f) ∈ L^{2}. This function obeys the desired properties.

This it remains to show that Σ is disjoint from Γ. Suppose for contradiction that this were not the case, then some non-zero affine combination of −χ_{P} /∥π_{P} f∥_{2}^{2} gives a non-negative function. Since f is a dyadic step function we can discretize, and assume that this convex combination is a finite one. This is the same as saying that we can find a finite collection P_{1}, …, P_{N} of tiles and real numbers a_{1}, …, a_{N} such that ∑_{i=1}^{N} a_{i}χ_{P_{i}} is non-negative, while ∑_{i=1}^{N} a_{i}∥π_{P_{i}}f∥_{2}^{2} is negative. By adding a positive multiple of some χ_{P} we may assume that ∑_{i=1}^{N} a_{i}χ_{P_{i}} is not identically zero and ∑_{i=1}^{N} a_{i}∥π_{P_{i}}f∥_{2}^{2} = 0. Equivalently - separating a_{i} into positive and negative numbers, and discarding any zeroes - we may find tiles P_{1}, …, P_{N}, Q_{1}, …, Q_{M} and positive constants a_{1}, …, a_{N} and b_{1}, …, b_{M} such that we have the pointwise estimate

∑_{i=1}^{N} a_{i}χ_{P_{i}} ≥ ∑_{j=1}^{M} b_{j}χ_{Q_{j}}  (11)

as well as the bound

∑_{i=1}^{N} a_{i}∥π_{P_{i}}f∥_{2}^{2} = − ∑_{i=1}^{M} b_{i}∥π_{Q_{j}}f∥_{2}^{2}.

Integrating (11) we have (since tiles have area 1)

∑_{i=1}^{N} a_{i} > ∑_{j=1}^{M} b_{j}.

3Specifically, we are deriving Farkas’s lemma, which states that the only obstructions to solving a linear programming problem occur when one can derive 0 > 0 from non-negative linear combinations of the constraints.

Since neither side can be zero, we may thus normalize

∑_{i=1}^{N} a_{i} > ∑_{j=1}^{M} b_{j} + 1.

Suppose that of all possible such P_{i}, a_{i}, Q_{j}, b_{j}, we pick an example which minimizes ∑_{j=1}^{M} b_{j}. This means in particular that P_{i} ≠ Q_{j} for all i, j, since one could otherwise decrement a_{i} and b_{j} by the same factor.

More generally, by Lemma 1.1 we can assume that Q_{j} ⊄ P_{i_{1}} ∪ … ∪ P_{i_{k}} for any disjoint tiles P_{i_{1}}, …, P_{i_{k}}. For if this were the case, we could use Lemma 1.1 to find disjoint tiles P′_{1}, …, P′_{k−1}, Q_{j} which cover the same region of phase space as P_{i_{1}}, …, P_{i_{k}}. By transferring an epsilon of the a_{i_{s}} to these new tiles, one can then cancel out some of the Q_{j}, again contradicting minimality.

Let Q_{wide} be a tile Q_{j} which maximizes the length of the spatial interval I_{Q_{j}}. Pick any x in I_{Q_{wide}}, and let ξ vary in ω_{Q_{wide}}. By (11), (x, ξ) must be contained in some P_{i_{ξ}}, which is distinct from Q_{wide}. There are two cases: either there exists a ξ such that P_{i_{ξ}} is taller than Q_{wide}, or that P_{i_{ξ}} is wider than Q_{wide} for all ξ.

Consider the latter case. Then we can cover Q_{wide} by a collection P of the tiles in {P_{1}, …, P_{n}}, each of which are wider than Q_{wide}. By passing to the tiles in P whose frequency intervals are maximal with respect to set inclusion, we may assume that the tiles in P are disjoint. But this contradicts the conclusion of two paragraphs ago.

In the former case, we see that for every x ∈ I_{Q_{wide}} the interval x × ω_{Q_{wide}} is contained in some P_{i}. Now we may repeat the previous argument (but for height instead of width) to again get a contradiction.

2. A Walsh version of Carleson’s theorem

Recall the Fourier inversion formula

f(x) = ∫_{−∞}^{∞} f̂(ξ)e^{−2πixξ} dξ

(where f̂ temporarily denotes the Fourier transform once again). In particular, we have (formally at least)

f(x) = lim_{N→∞} ∫_{−∞}^{N} f̂(ξ)e^{−2πixξ} dξ.

Thus, if we let P_{N} denote the Fourier multiplier corresponding to χ_{(−∞,A]}, we have

f(x) = lim_{N→∞} P_{N}f(x).

If f is Schwartz, then this formula is valid pointwise in x (indeed the convergence is uniform). However, it is not as clear what is going on for rough functions f.

Plancherel’s theorem combined with monotone convergence tells us that P_{N}f converges to f in L^{2} norm, but this does not imply pointwise convergence. A possible difficulty is indicated by Gibbs phenomenon: if f has a jump discontinuity (for instance), then P_{N}f will oscillate around that discontinuity by a sizeable amount, and thus does not converge uniformly (although it still converges pointwise a.e.)

Indeed, examples due to Kolmogorov and others show that if f is merely in L^{1}, then P_{N}f can diverge a.e. On the other hand, in 1966 Lennart Carleson (currently here at UCLA!) proved (in a famously difficult paper):

Theorem 2.1. If f is in L^{2}, then P_{N}f converges a.e. to f as N → ∞.

As is usual in this business, pointwise convergence is obtained by showing a bound on the maximal function

Cf(x) := sup_{N} |P_{N}f(x)|.  (12)

Suppose in particular that one was able to show the weak-type bound

∥Cf∥_{L^{2,∞}} ≲ ∥f∥_{2}.  (13)

Then, for any f in L^{2} and any ε > 0, we could approximate f by a smooth function g and an error of L^{2} norm O(ε). From the above estimate we see that P_{N}(f) will not fluctuate very much from P_{N}(g) outside of a set of small measure. By the usual methods one can then demonstrate pointwise convergence. (In fact this is reversible: if the above weak-type estimate failed, then one could not obtain pointwise convergence. This is known as Stein’s maximal principle, which we will not discuss here).

We will not quite prove Carleson’s theorem here, as it is a little technical. However, we will prove the Walsh analogue of Carleson’s theorem, which already contains all the major ideas of the proof. We redefine P_{N} for N > 0 to be the Walsh multiplier corresponding to [0, N] (acting on functions on R^{+}), and define the Walsh-Carleson operator Cf(x) by (12). We shall show the bound (13) for this operator.

We follow the arguments of Lacey and Thiele in a short paper last year; this was inspired by a brilliant 1973 paper of Fefferman, and also by their earlier work on the bilinear Hilbert transform in 1998. The techniques here have since been applied to a number of very delicate multi-linear operators and maximal operators, and is still an active area of research (especially at UCLA!)

We begin with a couple standard reductions. The first is linearization - we replace the sub-linear operator C by the linear variant

P_{N(x)}f(x),

where N : R^{+} → R^{+} is an arbitrary measurable function. Clearly P_{N(x)}f(x) is dominated by C; conversely, one can choose an N(x) so that P_{N(x)}f(x) is comparable to Cf(x) in magnitude everywhere. Thus it suffices to prove that

∥P_{N(x)}f(x)∥_{L^{2,∞}} ≲ ∥f∥_{2}

for some arbitrary function N, which we now fix. (Of course, N is likely to be extremely rough). For technical reasons we shall assume that N is never a terminating binary.

We fix f to be some dyadic step function, which we normalize to have L^{2} norm 1. We have to show that

|{x : |P_{N(x)}f(x)| ≥ λ}| ≲ λ^{−2}.

It suffices to show that

∫_{E} |P_{N(x)}f(x)| ≲ |E|^{1/2}

for all sets E ⊂ R^{+} of finite measure, since the claim then follows by setting E := {x : |P_{N(x)}f(x)| ≥ λ}. Clearly, it suffices to show that

| ∫_{E} P_{N(x)}f(x)| ≲ |E|^{1/2}

for all E (split E into sets where P_{N(x)}f(x) is positive or negative). We now fix E.

So far we have only taken very cautious, reversible steps. Now let’s do more interesting operations. We would like to understand the projections P_{N} in terms of the Walsh projections of the previous section. If we can decompose the interval [0, N] as the disjoint union of dyadic intervals ω then we would have P_{N} = ∑_{ω} π_{ω}. Of course, there are several ways to do this, but we would like to be as efficient as possible and use as few intervals as we can.

Call an interval ω left-handed if it is the left-half of its parent interval 2ω. Let L denote the collection of left-handed intervals. Observe that [0, N] is the disjoint union of those intervals ω ∈ L for which N ∈ ω^{∗}. (This is the partition obtained by the greedy algorithm, and is the maximal one). Thus

P_{N(x)}f(x) = ∑_{ω∈L} χ_{ω^{∗}}(N(x))π_{ω}f(x).

The projection π_{ω} can be written as π_{R^{+}×ω}, which can be split as ∑_{P:ω_{P} =ω} π_{P}, the sum of all the tile projections of tiles P whose frequency interval is ω. However π_{P} f(x) vanishes unless x ∈ I_{P}. Thus we can write

P_{N(x)}f(x) = ∑_{ω∈L} ∑_{P:ω_{P} =ω} χ_{ω^{∗}}(N(x))χ_{I_{P}} (x)π_{P} f(x).

Call a tile left-handed if its frequency interval is, and call P_{0} the set of left-handed tiles. If P = I × ω is a tile, define the conjugate tile P^{∗} by P^{∗} := I × ω^{∗}. (Thus if P is left-handed, then P^{∗} lies directly atop of P). We thus have

P_{N(x)}f(x) = ∑_{P ∈P_{0}} χ_{P^{∗}}(x, N(x))π_{P} f(x) = ∑_{P ∈P_{0}} χ_{P^{∗}}(x, N(x))⟨f, ϕ_{P} ⟩ϕ_{P} (x).

Thus each tile P can potentially contribute something to P_{N(x)}f(x), but only if the point (x, N(x)) is captured by the conjugate tile P^{∗}. Integrating on E, we thus reduce to showing that

| ∑_{P ∈P_{0}} a_{P} b_{P} | ≲ |E|^{1/2}  (14)

where a_{P}, b_{P} are the numbers

a_{P} := ∫_{E_{P}} ϕ_{P} (x) dx
b_{P} := ⟨f, ϕ_{P} ⟩

and E_{P} is the set

E_{P} := {x ∈ E : (x, N(x)) ∈ P^{∗}} = {x ∈ E ∩ I_{P} : N(x) ∈ ω_{P}^{∗} }.

Notice how we have managed to decouple the function f from the set E and the function N. Initially, f, E, and N were all interacting with each other in a rather non-linear manner. Now, f only interacts with P, while E and N^{∗} only interact with P^{∗}, while P and P^{∗} of course are highly correlated with each other. One can think of this as a kind of “factorization” of the operator.

As we shall see, the relationship between P and P^{∗} will be crucial - and more specifically, the fact that these two tiles are close together, but not identical. A key observation is the following: if P and Q are two distinct left-handed tiles which overlap, then P^{∗} and Q^{∗} will not overlap. Equivalently, if P^{∗} and Q^{∗} overlap, then P and Q cannot. So we have disjointness in one or the other - but to begin with, we don’t know which type of disjointness we have. The strategy will be to somehow separate the two types of disjointness.

To estimate ∑_{P ∈P_{0}} a_{P} b_{P} we must obtain good bounds on the a_{P} and b_{P} separately. However, the problem is that even after we do this there are many, many tiles P (a three-parameter set) to sum, with much overlap (both in the P s and in the P^{∗}s). We will need to sort these tiles into more manageable clumps. In some clumps the P s will be disjoint, while in others the P^{∗}s will be disjoint.

Since f is normalized in L^{2}, and the ϕ_{P} are normalized, we see that |b_{P} | ≤ 1 for all P. Actually, we can do a lot better: from Bessel’s inequality and orthogonality we have

( ∑_{P ∈D} |b_{P} |^{2})^{1/2} ≤ 1  (15)

whenever D is a disjoint collection of tiles in P_{0}. This is the only bound we will use on the b_{P}.

What about the a_{P}? Let’s first consider estimating a single a_{P}. Since ϕ_{P} has size |I_{P} |^{−1/2} and is supported on I_{P}, we have the crude bound

|a_{P} | ≤ |I_{P} |^{−1/2}|E_{P} |.  (16)

Since |E_{P} | ≤ |E|, |I_{P} | we thus have

|a_{P} | ≤ min(|I_{P} |^{−1/2}|E|, |I_{P} |^{1/2}) ≤ |E|^{1/2}.  (17)

Thus we can control a single factor a_{P} b_{P} by O(|E|^{1/2}) easily.

How could we boost this to sums of a_{P} b_{P}? The estimate (15) helps, but is clearly not enough by itself. To build some intuition, let’s first try summing ∑_{P ∈D} a_{P} b_{P}, where D ranges over a collection of disjoint tiles. Expanding this out we have

∑_{P ∈D} ∫_{E_{P}} b_{P} ϕ_{P} .

Since E_{P} is smaller than E, we expect this expression to morally be smaller than

∑_{P ∈D} ∫_{E} b_{P} ϕ_{P} ,

though this is not rigorous because of the possibility of cancellation. Interchanging the sum and integral and applying Cauchy-Schwartz, we bound this by

|E|^{1/2}∥ ∑_{P ∈D} b_{P} ϕ_{P} ∥_{2},

which is OK by Bessel’s inequality and (15). Of course, we have to go back and deal with the E_{P} vs E issue, but morally at least we can cope with this type of sum.

Now suppose we have a sum ∑_{P ∈D} a_{P} b_{P} in which the P are not necessarily disjoint, but their conjugates P^{∗} are. Now we cannot exploit (15) so easily, and we must find other tricks. To simplify matters let us consider a model type of collection D, namely the set

D = {P ∈ P_{0} : P ≤ P_{T} }

where the “top tile” P_{T} is some arbitrary tile. This type of collection is known as a tree (from its shape in the phase plane) and will play an important role in our arguments. (Actually this is an example of a complete tree; in our arguments we shall actually deal with much more “pruned” versions of this object).

To be consistent with (15), let us assume that

|b_{P} | ≲ (\frac{|I_{P} |}{|I_{P_{T}} |})^{1/2}.  (18)

(It turns out that this is not such an unreasonable assumption - we will eventually choose trees so that something like (18) holds for each tree). Thus we can bound

| ∑_{P ∈D} a_{P} b_{P} | ≲ |I_{P_{T}} |^{−1/2} ∑_{P ∈D} |I_{P} |^{1/2}|a_{P} |.

Since ϕ_{P} has size |I_{P} |^{−1/2}, we can bound

|I_{P} |^{1/2}|a_{P} | ≲ |E_{P} |.

Now the key observation is that because the P^{∗} are disjoint, the E_{P} are also disjoint, and are contained in E ∩ I_{P_{T}}. Thus we have

| ∑_{P ∈D} a_{P} b_{P} | ≲ |I_{P_{T}} |^{−1/2}|E ∩ I_{P_{T}} |.

Now we argue as in (17) to obtain

| ∑_{P ∈D} a_{P} b_{P} | ≲ |I_{P_{T}} |^{−1/2}|E|^{1/2}|I_{P_{T}} |^{1/2} = |E|^{1/2}

as desired.

To summarize, we have managed to (morally) handle summations over certain types of tile sets D which are either disjoint, or are conjugate-disjoint. Of course, the entire tile set P has too much self-overlap to fall into either one of these categories. However, it turns out that one can split P into the countable union of “trees”, each of which fall into one or the other of the above categories. At first this doesn’t seem like enough, because one still gets a divergence when summing. However, as we shall see, in this sum, the trees slowly get “lighter” (in the sense that the ratio |E_{P} |/|I_{P} | is no longer 1, but gets smaller and smaller), and less “energetic” (in the sense that estimates like (18) improve), and eventually we will be able to sum things in a geometric series.

Now for the technical stuff. From here onwards all tiles will be assumed to be left-handed.

Definition 2.2. Let P_{T} be a tile. A 1-tree with top P_{T} is a collection T of tiles in P_{0} containing P_{T} such that P ≤ P_{T} for all P ∈ T. A 2-tree with top P_{T} is a collection T of tiles containing P_{T} in P_{0} such that P^{∗} ≤ P_{T}^{∗} for all P ∈ T. We define a tree with top P_{T} to be any collection T of tiles in P_{0} containing P_{T} such that P ≤ P_{T} or P^{∗} ≤ P_{T}^{∗} for all P ∈ T.

Note that in a 1-tree, the conjugate tiles P^{∗} are all disjoint, while in a 2-tree the P tiles are all disjoint. A tree is composed of a 1-tree and 2-tree, thus we have a chance of estimating an individual tree.

Definition 2.3. A collection P of tiles in P_{0} is convex if, whenever P_{1} < P_{2} < P_{3} are tiles in P_{0} such that P_{1}, P_{3} ∈ P, then P_{2} must also be in P.

Convexity is a technical thing needed to make the “we can replace E_{P} by E” step rigorous in the above heuristic argument. Note that P_{0} is trivially convex.

Definition 2.4. For any collection P of tiles in P_{0}, we define the mass mass(P) by

mass(P) := sup_{P ∈P} \frac{|Ẽ_{P} |}{|I_{P} |}

where Ẽ_{P} is a slight enlargement of E_{P}, defined by

Ẽ_{P} := {x ∈ E : (x, N(x)) ∈ P ∪ P^{∗}} = {x ∈ E ∩ I_{P} : N(x) ∈ ω_{P} ∪ ω_{P}^{∗} }.

Clearly we have mass(P) ≤ 1 for any P, however for many of our trees the mass will be much smaller. The mass will control the size of the a_{P}. The corresponding quantity controlling the b_{P} is called the energy:

Definition 2.5. For any collection P of tiles in P_{0}, we define the energy energy(P) by

energy(P) := sup_{T ⊂P}(\frac{1}{|I_{P_{T}} |} ∑_{P ∈T} |b_{P} |^{2})^{1/2},

where T ranges over all 2-trees contained in P.

Since the tiles in a 2-tree are disjoint, we expect to use (15) to get some control on energy(P) (at least, we should be able to control the contribution of the big trees). Since every singleton tile is itself a 2-tree with itself as its top, we obtain the estimate

|b_{P} | ≤ |I_{P} |^{1/2}energy(P)  (19)

which is the analogue of (18).

Clearly, mass and energy are monotone in the sense that adding more tiles to a collection can only serve to increase the mass and energy.

There will be three key lemmas in the proof of (14). The first one shows how to bound the contribution of a single tree.

Lemma 2.6 (Tree estimate). If T is a convex tree, then

| ∑_{P ∈T} a_{P} b_{P} | ≲ |I_{P_{T}} |mass(T)energy(T).

To use this lemma we need to split P_{0} up into trees, each of which has a relatively small mass and energy. This is the purpose of the other two lemmas:

Lemma 2.7 (Mass decomposition lemma). Let P be a convex collection of tiles. Then we can partition P = ⋃_{T ∈T} T ∪ P′ where P′ is a convex collection of tiles with

mass(P′) ≤ \frac{1}{2}mass(P),

and T is a collection of convex trees with

∑_{T ∈T} |I_{P_{T}} | ≲ |E|/mass(P).  (20)

Lemma 2.8 (Energy decomposition lemma). Let P be a convex collection of tiles. Then we can partition P = ⋃_{T ∈T} T ∪ P′ where P′ is a convex collection of tiles with

energy(P′) ≤ \frac{1}{2}energy(P),

and T is a collection of convex trees with

∑_{T ∈T} |I_{P_{T}} | ≲ energy(P)^{−2}.  (21)

We will prove these lemmas in the next few sections. For now, let us see how they imply (14). Define the auxiliary quantity width(P) by

width(P) = min(|E|/mass(P), energy(P)^{−2}).

From the mass and energy decomposition lemmas we have

Corollary 2.9. Let P be a convex collection of tiles. Then we can partition P = ⋃_{T ∈T} T ∪ P′ where P′ is a convex collection of tiles with

width(P′) ≥ 2width(P), and T is a collection of convex trees with

∑_{T ∈T} |I_{P_{T}} | ≲ width(P).  (22)

Now we do the following algorithm. Initialize P = P_{0}. If P has zero mass or zero energy then clearly ∑_{P} a_{P} b_{P} vanishes, and we are done. Otherwise, P has some finite width. We apply the above Corollary, and split ∑_{P ∈P} a_{P} b_{P} into

∑_{T ∈T} ∑_{P ∈T} a_{P} b_{P}

and

∑_{P ∈P′} a_{P} b_{P} .

By the tree estimate, the first expression is bounded by

∑_{T ∈T} |I_{P_{T}} |mass(P)energy(P).

Using the bounds

energy(P) ≲ width(P)^{−1/2}; mass(P) ≲ min(1, |E|/width(P)

and (22), we can bound this by

width(P) min(1, |E|/width(P))width(P)^{−1/2}.

This quantity is bounded by |E|^{1/2} but decays geometrically as width(P) gets much larger or much narrower than |E|. To deal with P′, we replace P by P′ and iterate the above algorithm (but now with a width which is at least twice as large). Summing this geometric series we get |E|^{1/2} as desired.

3. Proof of the mass decomposition lemma

Fix P, and call a tile P ∈ P heavy if |Ẽ_{P} | ≥ \frac{1}{2}mass(P)|I_{P} |. We need to eliminate all the heavy tiles from P in order to create P′. The idea is to organize the heavy tiles into trees and use some sort of disjointness of the Ẽ_{P} to obtain (20).

The algorithm is as follows. Initialize T to be empty, and P′ to equal P. If P′ contains no heavy tiles, terminate the algorithm. Otherwise, pick a heavy tile P_{T} in P′ with a maximal width |I_{P_{T}} |. Form the tree {P ∈ P′ : P^{∗} ≤ P_{T}^{∗} or P ≤ P_{T} }. Remove this tree from P′ (adding it to T); note that this does not disturb the convexity of P′. Continue the algorithm until P no longer contains heavy tiles.

Note that since P′ is always convex, so are the trees T. It remains to show (20). First observe that the conjugate tops P_{T}^{∗} of the trees we remove are disjoint; if one P_{T}^{∗} intersects another, then the wider of the trees was selected first, and when that tree was removed from P′, the smaller top should also have been removed at that time, a contradiction. Similarly the tops P_{T} are disjoint. The Ẽ_{P_{T}} are now essentially disjoint subsets of E, and (20) easily follows.

4. Proof of the energy decomposition lemma

This is a similar argument to the mass lemma. Fix P, and call a tree T ∈ P energized if

(\frac{1}{|I_{P_{T}} |} ∑_{P ∈T:P^{∗}≤P_{T}^{∗}} |b_{P} |^{2})^{1/2} ≥ \frac{1}{2}energy(P).

Thus the 2-tree component of an energized tree has a large energy. We shall therefore removed all energized trees from P.

The algorithm is as follows. Initialize T to be empty, and P′ to equal P. If P′ contains no energized trees, terminate the algorithm. Otherwise, pick an energized tree T in P′, which we can assume to be maximal with respect to set inclusion (so in particular it is convex, and removing T from P′ will not disturb convexity). We can also assume that T is as low as possible, or in other words that ξ_{P_{T}}, the midpoint of ω_{P_{T}}, is minimal. (As we shall see, it is important that we remove trees from the bottom before we work our way to the top). We then remove T from P′ and repeat the iteration.

In each individual tree T, we extract out the 2-tree

T′ := {P ∈ T : P^{∗} ≤ P_{T}^{∗}}.

In this tree the tiles P are all disjoint. We in fact have the stronger statement that the tiles in ⋃_{T ∈T} T′ are all disjoint. To see this, suppose for contradiction that we had two trees T_{1}, T_{2} with tiles P_{1}, P_{2} such that P_{1} < P_{2}. Then P_{T_{1}} is higher than P_{T_{2}}, so T_{2} must have been selected first. But since P_{1} < P_{2}, we also have P_{1} < P_{T_{2}}, which implies that P_{1} should have been incorporated into T_{2} (as it was chosen to be maximal), a contradiction.

From disjointness and (15) we have

∑_{T ∈T} ∑_{P ∈T′} |b_{P} |^{2} ≤ 1;

since each tree is energized, (21) follows.

5. Proof of the tree estimate for 1-trees

To prove Lemma 2.6 we shall prove it for 1-trees and 2-trees separately.

Suppose T is a 1-tree. We now use (16) and (19) to estimate ∑_{P} a_{P} b_{P} by ∑_{P} |E_{P} |energy(T), so it suffices to show that

∑_{P} |E_{P} | ≲ mass(T)|I_{P_{T}} |.

To do this we shall split I_{P_{T}} into disjoint intervals J, such that

∑_{P} |E_{P} ∩ J| ≲ mass(T)|J|.

We introduce the intervals J which are not of the form I_{P} for any P ∈ T, but such that 2J is of the form I_{P_{J}} for some P_{J} ∈ T. Clearly these intervals partition I_{P_{T}}. The tiles P which give a non-zero contribution to |E_{P} ∩ J| all obey I_{P} ⊇ J, and since we have a 1-tree, the sets E_{P} ∩ J are all disjoint and live inside Ẽ_{P_{J}}. The claim follows.

6. Proof of the tree estimate for 2-trees

Now suppose T is a 2-tree. Now the P are all disjoint, which suggests repeating the first argument from the heuristic discussion. Again, we rewrite ∑_{P} a_{P} b_{P} as

∑_{P ∈T} ∫_{E_{P}} b_{P} ϕ_{P} .

Now we run into the issue of what to do with the E_{P}. We can rewrite the above as

∫_{E∩I_{P_{T}}} ∑_{P ∈T:N(x)∈ω_{P}^{∗}} b_{P} ϕ_{P} .  (23)

Let us first forget about E by estimating this crudely by

∫_{I_{P_{T}}} | ∑_{P ∈T:N(x)∈ω_{P}^{∗}} b_{P} ϕ_{P} |.  (24)

If we could remove the constraint N(x) ∈ ω_{P}^{∗}, then we could use Cauchy-Schwarz to bound (24) by

|I_{P_{T}} |^{1/2}∥ ∑_{P ∈T} b_{P} ϕ_{P} ∥_{2},

which by the definition of energy is O(|I_{P_{T}} |energy(T)). This doesn’t gain us the mass factor, but we threw that away before and we’ll return to it. So the issue is how to deal with the N(x) ∈ ω_{P}^{∗} constraint. For each x, let W (x) denote the largest dyadic interval containing ω_{P_{T}} which does not contain N(x) (so for instance W (x) = R if N(x) ∈ ω_{P_{T}}). Note that if N(x) ∈ ω_{P}^{∗}, then ω_{P} is disjoint from W (x), while if N(x) ∉ ω_{P}^{∗}, then ω_{P} is contained in W (x). Thus we can write

∑_{P ∈T:N(x)∈ω_{P}^{∗}} b_{P} ϕ_{P} = (1 − π_{W (x)}) ∑_{P ∈T} b_{P} ϕ_{P} .

The operator π_{W (x)} is just Walsh convolution with some function supported on [0, |W (x)|^{−1}] and has magnitude |W (x)|^{−1}, hence π_{W (x)}f is pointwise dominated by the Hardy-Littlewood maximal function of f. Thus we have

| ∑_{P ∈T:N(x)∈ω_{P}^{∗}} b_{P} ϕ_{P} | ≲ M ∑_{P ∈T} b_{P} ϕ_{P} .  (25)

So now we can use Cauchy-Schwarz to bound (24) by

|I_{P_{T}} |^{1/2}∥M( ∑_{P ∈T} b_{P} ϕ_{P})∥_{2},

which is OK by the previous arguments and the Hardy-Littlewood maximal inequality. So we can at least get the right bound but for the mass factor.

To put this mass factor back in it will suffice if we can control (23) by

mass(T) ∫_{I_{P_{T}}} M ∑_{P ∈T} b_{P} ϕ_{P}

since we can then run the previous argument.

We again partition I_{P_{T}} into the intervals J which are of the form I_{P} for any P ∈ T, but such that 2J is not of the form I_{P_{J}} for some P_{J} ∈ T. It thus suffices to show that

| ∫_{E∩J} ∑_{P ∈T:N(x)∈ω_{P}^{∗}} b_{P} ϕ_{P} | ≲ mass(T) ∫_{J} M| ∑_{P ∈T} b_{P} ϕ_{P} |

for each such interval J.

Fix J. The only P which contribute are those such that P ≥ P_{J}. Thus the integrand vanishes unless N(x) ∈ ω_{P_{J}}^{∗}. Applying (25) we can therefore bound the left-hand side by

∫_{E∩J;N(x)∈ω_{P_{J}}^{∗}} M ∑_{P ∈T} b_{P} ϕ_{P} .

The integrand is essentially constant on J, while the set integrated on has measure at most O(mass(T)|J|). The claim follows.

7. Homework for week 6 - due Friday, March 2

• Prove that for any dyadic interval I, the set k ⊗ I is another dyadic interval of side length ∥k∥|I| (ignoring sets of measure zero). As a consequence, prove (1), for dyadic step functions f.

• Show that the function χ_{[0,1]} is its own Walsh-Fourier transform. Conclude from this the Walsh-Fourier transform maps dyadic step functions to dyadic step functions, and its own inverse.

• A dyadic Calderón-Zygmund operator is an operator T defined on (possibly vector-valued) functions on R^{+} by the formula

T f(x) := ∫_{R^{+}} K(x, y)f(y) dy

where T is bounded on L^{2}, and K obeys the bounds

|K(x, y)| ≲ \frac{1}{∥x ⊕ y∥}

and

|K(x, y) − K(x, z)|, |K(y, x) − K(z, x)| ≲ \frac{∥y ⊕ z∥}{∥y ⊕ x∥^{2}}

whenever ∥y ⊕ z∥ < ∥y ⊕ x∥. Prove that if T is a dyadic Calderón-Zygmund operator, then T is weak-type (1, 1), and is bounded on L^{p} for all 1 < p < ∞. (Note: the proof should be a little simpler than the corresponding statement on the field R. This is a general fact in harmonic analysis: the Walsh case is cleaner than the Fourier.)

LECTURE NOTES 5 21

Note that by repeating the arguments from the Week 2 notes, we thus obtain as a consequence the dyadic Littlewood-Paley inequality

∥f∥_{p} ∼ ∥ ∑_{k∈Z}(π_{[2^{k},2^{k+1}]}f|^{2})^{1/2}∥_{p}

for 1 < p < ∞. Note: Thanks to Dmitry Ryabogin for comments and misprints.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

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