Ptolemaics meetings 2 & 3

I’m very far behind in this, I’ve got to admit I’m busier than last year and haven’t coped with it completely yet. Luckily we’re progressing slowly in order to understand better and that gives me the opportunity to merge together the blog posts for meetings 2 & 3.

As I said in the previous post, the goal for now is to understand the proof of {L^2\rightarrow L^{2,\infty}} boundedness of Carleson’s operator (through time freq. analysis). As an introduction to the real thing we’ve started from the simpler case of the Walsh transform, or Walsh series, or Walsh phase plane, whatever you want to call it. It’s easier because all the nasty technicalities disappear but the ideas needed are already in there, that’s why it propaedeutic. We’re following Hytönen’s notes as suggested by Tuomas (you can find them here: http://wiki.helsinki.fi/pages/viewpage.action?pageId=79564963). An alternative is Tao’s lecture notes (lecture 5 in particular) for course Math254A W’ 01 (http://www.math.ucla.edu/~tao/254a.1.01w/) which are quite nice – as all of his stuff. The main differences are in that Hytönen proves every single statement, and he deals with the Walsh series (analogue of the Fourier series) while Tao deals with the Walsh transform (analogue of the Fourier transform). Also, Hytönen then goes on to prove the full euclidean case, while Tao doesn’t.

The Walsh operators are best described as operators on the real line with a different field structure. One works on {\mathbb{Z}_2[[X]]}, i.e. the Laurent series with coefficient in {\mathbb{Z}_2}, which can be identified with the (binary expression of) positive reals by

\displaystyle a_N \cdots a_0 . a_{-1} a_{-2} \cdots \equiv a_N X^N + \ldots a_1 X + a_0 + \frac{a_{-1}}{X} + \frac{a_{-2}}{X^2} + \ldots .

Notice there’s only a finite number of terms with positive degree, and the characteristic of the field is 2. We have some issues with reals that end in an infinite series of {1}, but we can ignore them as their measure is zero. Addition {\oplus} and multiplication {\otimes} are the same as those for Laurent series; in the real representation the operations correspond to those of {\mathbb{R}^{+}} except you never carry a digit. This modification of the field operations has the effect of isolating dyadic intervals somehow. To see why, consider the natural distance

\displaystyle d(x,y) = 2^{\mathrm{deg}(x\oplus y)}

({\oplus} is the same as {\ominus} in char. 2): points like {0.111111111111} and {1} are at a distance of {1} (no matter how many {1}‘s I attach to the end of the first one).

The Pontryagin dual (or characters) of the additive group of {\mathbb{Z}_2[[X]]} is isomorphic to {\mathbb{Z}_2[[X]]} itself, and it can be seen as follows: take {e(x)} to be the square wave of period {1} (taking values {+1,-1}); in other terms, if {a_{-1}(x)=0}, then {e(x)=+1}, while if {a_{-1}(x)=1} then {e(x)=-1}. With this notation {e(x\otimes \xi)} is a character for every {\xi \in \mathbb{Z}_2[[X]]}, as can be easily verified. On the other hand, we can show that these are all the characters. Consider {\phi} a character of {\mathbb{Z}_2[[X]]}, and define

\displaystyle \zeta_k := \phi(X^{k-1}).

These numbers are in {\{+1,-1\}}, because {\mathbb{Z}_2[[X]]} has characteristic 2 and thus the characters are real valued. Moreover, since the characters are continuous functions, it follows that – thanks to our metric {d} – it is {\phi(X^{k})\equiv 1} for {k \ll -1}. Then if you define the element {\xi} such that {\xi_k = 0} whenever {\zeta_{-k} = 1} and {\xi_k=1} whenever {\zeta_{-k}=-1}, the element {\xi} is in {\mathbb{Z}_2[[X]]} and it is such that {\phi(x)=e(x\otimes \xi)} for every {x}. Shortly,

\displaystyle \mathbb{Z}_2[[X]]\cong \widehat{\mathbb{Z}_2[[X]]}.

Now, we’re interested in Walsh series, i.e. only to functions that are periodic of period {1}. In the real case those are functions on the quotient {\mathbb{R}/\mathbb{Z}=\mathbb{T}}, so in this case we consider functions on the quotient

\displaystyle \mathbb{Z}_2[[X]] / \mathbb{Z}_2[X];

equivalently, we’ll consider functions on the elements of the kind {0.a_{-1}a_{-2}\cdots}, extended by periodicity. What’s different in this scenario, w.r.t. the euclidean case, is that the last quotient is also a (closed) subgroup of the big group {\mathbb{Z}_2[[X]]}. In order to determine the characters of this group, which we name {G}, we can appeal to Pontryagin’s theory (since {\mathbb{Z}_2[[X]]} is abelian and locally compact), and we’ll have that

\displaystyle \widehat{G} \cong \widehat{\mathbb{Z}_2[[X]]}/\Lambda\cong \mathbb{Z}_2[[X]]/\Lambda,

where {\Lambda} is the annihilator of {G}. It’s easy to see what {\Lambda} is: it’s isomorphic to {G} itself (through {\xi\mapsto e(\cdot \otimes \xi)}), which implies

\displaystyle \widehat{G}\cong \mathbb{Z}_2 [X].

In other words, the characters of {G} are

\displaystyle e(x\otimes \xi)

where {\xi} is a polynomial (notice how this is in perfect analogy with the euclidean case).

Having sorted this out we proceed on to the Walsh-series. Since we can write any natural number {n} in base {2} as {\sum_i n_i 2^i} with a finite number of {n_i \neq 0}, we have a bijection between {\mathbb{N}} and {\mathbb{Z}_2 [X]}. We identify the two sets under this bijection and write {n} in place of {\xi} with the obvious meaning, so that we can write the {n}-th character as

\displaystyle w_n(x) := e(x\otimes n).

These are known as Walsh functions. It is immediate from this to see that if {n} and {m} have complementary digits up to the leftmost one (i.e. if the {k}-th digit of {n} is {1} then the {k}-th digit of {m} is {0} and viceversa), then {m\oplus n = m+n} and therefore in this case

\displaystyle w_{m+n}(\cdot) = e(\cdot \otimes (m\oplus n)) = w_m(\cdot) w_n (\cdot)

Using the algebraic properties of {e} then

\displaystyle e(x\otimes n) = \prod_{i=0}^{i_0}{e(x\otimes n_i X^i)}=\prod_{i=0}^{i_0}{e(x\otimes X^i)^{n_i}},

accepting the convention that {(-1)^0 = 1}. Now, if we look back at the definition, {e(x\otimes X^i)} is {+1} when {a_{-1-i}(x) = 0} and {-1} otherwise. This means it is just the square wave rescaled by a factor {2^{-i}}, and we can write this in a more usual way by saying that {e(x\otimes X^i)} is {h(2^i x)}, where {h} is the Haar function or square wave of period {1}. Thus, identifying {G} and {\mathbb{T}} set theoretically one can write

\displaystyle w_n(x) = \prod_{i=0}^{i_0}{w_{2^i}(x)^{n_i}}=\prod_{i=0}^{i_0}{h(2^i x)^{n_i}}.

Of course one could say I’ making way too many identifications, but my point was exactly to see all these definitions as a unique one.

Anyway, what are these functions like? From this last equivalent definition it’s immediate to see that {w_n} is constant on dyadic intervals of length {2^{-k(n)}}, where {k(n)} is the smallest integer such that {2^{k(n)}>n}. They assume values {+1} or {-1} and on every dyadic interval of size {2^{-k(n)+1}} they look exactly like {\pm h} (rescaled to fit in there). Thus every {w_n} for {n} less than {2^{k_0+1}} can be obtained by flipping (i.e. inverting the sign of) the values of {w_{2^{k_0}}(x) = h(2^{k_0}x)} on a dyadic interval of length {2^{-k_0}}. This way we obtain {2^{2^{k_0}}} functions though, while we only need {2^{k_0}}. Those additional functions will turn out to be in the linear span of the {w_n}‘s.

It’s best if I show a picture of what they look like (I’ve used Mathematica to plot them): the following are the first 9 Walsh functions

walsh9
As you see, not all the patterns show up. At the following link you can find a further picture of the first 32: http://imgur.com/6hSQIJN

From the Walsh functions, as they are the characters of the group, we can define the Walsh-Fourier transform on {G} as

\displaystyle Wf(n) = \int{f(x) e(x\otimes n)}\,dx = \int{f(x) w_n (x)}\,dx = \left\langle f, w_n \right\rangle,

where {dx} is the (pull-back of) the Lebesgue measure. For {\mathbb{Z}_2[[X]]} the Walsh-Fourier transform is the more general expression

\displaystyle \widehat{f}(\xi) :=\int{f(x) e(x\otimes \xi)}\,dx.

It’s not at all hard to prove that the Walsh functions are orthogonal to each other (I won’t repeat it here since it’s in the notes linked above). As in previous post then we want to consider approximations to functions {f \,:\,G \rightarrow \mathbb{R}} (we consider only real functions since the Walsh functions are real themselves) obtained by projections onto subspaces of the form

\displaystyle W_N f (x) := \sum_{n=0}^{N-1}{\left\langle f, w_n\right\rangle w_n (x)};

these are the Walsh series. We are interested in proving they are a.e. convergent if {f \in L^2(G) \equiv L^2(0,1)}. As seen in the previous post, one can do so by proving the {L^2 \rightarrow L^{2,\infty}} boundedness of the operator

\displaystyle \mathcal{C}f(x) = \sup_{N \in \mathbb{N}}{|W_N f(x)|}.

This is what the notes are about, and the way this is done is by time-frequency analysis on the Walsh plane. I will come to this later.

I would now like to digress a bit in a somewhat fuzzy way about the idea that {\mathbb{Z}_2[[X]]/{\mathbb{Z}_2 [X]}} can be thought of as some sort of limit of the finite subgroups {\mathbb{Z}_2^k} for {k\rightarrow \infty} (I’ve got the feeling that category theory might make the following less fuzzy, but I’m not really into that kind of perversion). The idea is that the Walsh-Fourier transform on the full group is kind of a limit of the discrete Fourier transforms on the subgroups.

First of all we consider the characters of {\mathbb{Z}_2^k}: it’s a finite abelian group and therefore they are isomorphic to the group itself; moreover, they are given by products of characters of {\mathbb{Z}_2}. Call these last characters {\varphi_0} (values {(1\quad 1)}) and {\varphi_1} (values {(1\quad -1)}). Then the characters {\phi} of {\mathbb{Z}_2^k} are

\displaystyle \phi(z_1,\ldots, z_k) = \varphi_{i_1}(z_1)\cdot \ldots \cdot \varphi_{i_k}(z_k),

where {(i_1,\ldots, i_k) \in \mathbb{Z}_2^k} (this is the isomorphism, actually). Since {\mathbb{Z}_2^k} is (isomorphic to) a subgroup of {G} – a closed one indeed, since it’s a finite union of points – we can also use Pontryagin results as before, so that

\displaystyle \widehat{\mathbb{Z}_2^k} = \widehat{G}/\Lambda' \cong G / {\mathbb{Z}_2 [X]_{\mathrm{deg}\geq k}},

where {\Lambda'\cong \mathbb{Z}_2 [X]_{\mathrm{deg}\geq k}} is the annihilator of {\mathbb{Z}_2^k} in {G}, i.e. the polynomials with monomials of degree at least {k}. Thus the characters can also be written as {e(\cdot \otimes n)} for {n<2^k}. Now, these are the Walsh functions up to index {2^k -1}, which are constant on dyadic intervals of length {2^{-k}}, and can thus be specified by a sequence in {\{+1,-1\}^{2^k}}. So, the Walsh functions of index {<2^k}, as sequences, are the characters of {\mathbb{Z}_2^k}. The ordering given by the index is a bit different from the natural order given by the {\phi}‘s above: they are ordered by the correspondence {(i_1,\ldots, i_k) \mapsto 2^k i_1 + \ldots + i_k \equiv (i_1 \cdots i_k)_2 }, e.g. the character {\varphi_0 \varphi_1 \varphi_1} is the character number {011_2 = 3} in base 10. As a member of the Walsh functions its index is 6 though. Let me explain why.

Associate to {(z_1, \ldots, z_k)} the number {z = z_1 2^{-1} + \ldots + z_k 2^{-k}}, and write {n} in base 2 by its digits as {(n_{k-1}\cdots n_1 n_0)_2} (where there can be an arbitrary number of zero digits on the left). Then

\displaystyle w_n (z) = \prod_{i=0}^{k-1}{h(2^i z)^{n_i}}.

By definition of {h} (assume it is right continuous on the jump discontinuities, so that {h(0)=1, h(1/2)=-1}), if {n_i=1} it is {h(2^i z) = h(z_{i+1} /2) = \varphi_1(z_{i+1})}. If instead {n_i=0} then the corresponding factor is just {\varphi_0 (z_{i+1})}. Thus

\displaystyle w_n(z) = \prod_{i=0}^{k-1}{\varphi_{n_i}(z_{i+1})},

which as a character of {\mathbb{Z}_2^k} is associated to index {(n_0 n_1 \cdots n_{k-1})_2} – the number whose digits are the binary digits of {n} in reversed order. Thus the orders of the Walsh functions and the characters differ by a reflection transformation in the binary digits, which we denote as {n \mapsto \overline{n}} (it depends on {k}, be careful). Thinking of {z} as a polynomial in {1/X} this transformation is obtained by multiplying by {X^{k+1}} and then substituting {X} with {1/X}. As an example, the characters of {\mathbb{Z}_2^3} are ordered as follows: {\{w_0, w_4, w_2, w_6, w_1, w_5, w_3, w_7\}}. This is because {\overline{{000}_2} = {000}_2 = 0}, {\overline{{001}_2} = {100}_2 = 4}, {\overline{{010}_2} = {010}_2 = 2}, and so on.

Now consider the functions {f\,:\, \mathbb{Z}_2^k \rightarrow \mathbb{C}}. Denote {w_{\overline{n}}} by {\phi_n}. They can be specified by {2^k} values, and we can define their Fourier transform as

\displaystyle \widehat{f}(n) = \sum_{z\in \mathbb{Z}_2^k}{f(z) \phi_n (z)}.

Since it’s a linear transformation we could also write it in matrix form. For example, in {\mathbb{Z}_2^2} the matrix of the (Walsh-)Fourier transform would be

\displaystyle H_2 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}.

For {\mathbb{Z}_2^3} it would instead be (let me write only {+} and {-} signs for clarity)

\displaystyle H_3 = \begin{pmatrix} + & + & + & + & + & + & + & + \\ + & - & + & - & + & - & + & -\\ + & + & - & - & + & + & - & -\\ + & - & - & + & + & - & - & + \\ + & + & + & + & - & - & - & - \\ + & - & + & - & - & + & - & +\\ + & + & - & - & - & - & + & +\\ + & - & - & + & - & + & + & - \end{pmatrix}.

You might have already spotted what’s going on. These are the Walsh-Hadamard matrices, that are obtained by the recursive formula

\displaystyle H_{k+1} = \begin{pmatrix} H_{k} & H_{k} \\ H_{k} & -H_{k} \\ \end{pmatrix},

starting from

\displaystyle H_1=\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.

Why is this so? if you think of {\mathbb{Z}_2^{k+1}} as {\mathbb{Z}_2\times \mathbb{Z}_2^k } then the characters are

\displaystyle \varphi_{i_0}(z_0)\cdot \varphi_{i_1}(z_1)\cdot \ldots \cdot \varphi_{i_k}(z_k),

and if you write {I = (i_1 \cdots i_k)_2} (binary expression) this is just

\displaystyle \varphi_{i_0}(z_0)\phi_{I}(z_1, \ldots, z_k),

and the matrix entries are thus determined by the values {i_0, z_0}. {i_0 = 0} corresponds to the rows {1} to {2^k} in the {2^{k+1} \times 2^{k+1}} matrix of the Fourier transform on {\mathbb{Z}_2^{k+1}}, and it has no effect because {\varphi_0\equiv 1}, therefore these rows are just two copies of the matrix {H_k}; on the other hand {i_0 = 1} corresponds to the rows {2^k} to {2^{k+1}}, and it changes the sign if {z_0 = 1}, thus these rows are a copy of {H_k} (this corresponds to {z_0=0}) with a copy of {-H_k} on the side (this corresponds to {z_0 = 1}).

Thus we’ve found an iterative way to generate the Walsh functions. If you want to generate all the Walsh function up to index {N = 2^k -1} all you have to do is generate the matrix {H_k} and sort the rows by the correspondence {n\mapsto \overline{n}}. This requires {O(N^2)} space and {O(N^2)} transcription operations.

Getting back on track, consider {k} fixed; we want to see how these discrete transforms are related to the transform on the full group {G}. The transform {H_k} acts on functions from {\mathbb{Z}_2^k} to {\mathbb{R}} (for simplicity), thought of as vectors with entries

\displaystyle (f(0,\ldots,0,0), f(0,\ldots,0,1), \ldots).

Any element {(z_1,\ldots, z_k)} is associated to the integer {z:=(z_1\cdots z_k)_2 < 2^k}. Consider now any function {f\in L^2(G)\equiv L^2(0,1)}. We want to obtain from that {f} another function {\tilde{f}\,:\,\mathbb{Z}_2^k\rightarrow \mathbb{R}}, and we do so by constructing an approximation of {f} which is constant on the dyadic intervals of length {2^{-k}}, i.e.

\displaystyle f^k(x) = \sum_{i=0}^{2^k -1}{f^k_i \chi_{I^k_i}(x)}

for some choice of {f^k_i}, where {I^k_i :=[2^{-k}i,2^{-k}(i+1)[}. The function

\displaystyle \tilde{f}(z_1,\ldots,z_k) := f^k_{z}

will then be our function on {\mathbb{Z}_2^k}. We identify this from now on with an element of {\mathbb{R}^{2^k}}.

The criterion for this choice is that {f^k (x)} be as close as possible to {f(x)} in the {L^2} norm: by optimizing it’s immediate to see that we have to take {f^k_i} to be the average of {f(x)} on the {i}-th interval

\displaystyle f^k_i := 2^k \int_{2^{-k}i}^{2^{-k}(i+1)}{f} = 2^k \left\langle f, \chi_{I^k_i}\right\rangle.

With this particular choice it’s immediate to see that if you take the row {m} of {H_k} then

\displaystyle [m\mbox{-th row of } H_k] \cdot \tilde{f} = 2^k \left\langle f, w_{\overline{m}}\right\rangle

because the Walsh functions are constant on the dyadic intervals {I^k_i}, so that

\displaystyle H_k \tilde{f} = 2^k\begin{bmatrix} \left\langle f, w_{\overline{0}}\right\rangle \\ \left\langle f, w_{\overline{1}}\right\rangle \\ \vdots \\ \end{bmatrix}.

Now this means that

\displaystyle H_k^{T} H_k \tilde{f} = 2^k\sum_{n=0}^{2^k -1}{\left\langle f, w_n\right\rangle} (w_n)^T = 2^k W_{2^k}f

({w_n} are rows of {H_k} and also the values of {w_n(x)} on the dyadic intervals {I^k_i}, as noticed before). Now {H_k} is unitary if rescaled and symmetric, and one can compute exactly

\displaystyle {H_k}^2 = 2^k \mathbb{I},

which in turn implies

\displaystyle \tilde{f} = W_{2^k}f

(as vectors of values on the {I^k_i}‘s). Thus {W_{2^k}} is just replacing {f} on the dyadic intervals {I^k_i} with its own average on them, and in particular if {f(x)} is constant on the {I^k_i}‘s then {W_{2^k} f = f}. The convergence we’re looking for can thus be viewed as “taking this property to the limit”, in an informal sense (we want the limit along any sequence and for generic {L^2(0,1)} functions – which are not very well approximated by these functions constant on dyadic intervals).

I haven’t said anything yet about the time frequency in this model: I will address that in the next post of this series, along with some heuristics behind the proof of the the {L^2\rightarrow L^{2,\infty}} boundedness of the Carleson operator for Walsh series (this is called Billard’s theorem, it was proved in the very same year Carleson proved his result; I don’t know with which techniques though).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s