ABSTRACT Title of Dissertation: THE UNCERTAINTY PRINCIPLE IN HARMONIC ANALYSIS AND BOURGAIN?S THEOREM. Alexander M. Powell, Doctor of Philosophy, 2003 Dissertation directed by: Professor John J. Benedetto Department of Mathematics We investigate the uncertainty principle in harmonic analysis and how it con- strains the uniform localization properties of orthonormal bases. Our main result generalizes a theorem of Bourgain to construct orthonormal bases which are uni- formly well-localized in time and frequency with respect to certain generalized variances. In a related result, we calculate generalized variances of orthonor- malized Gabor systems. We also answer some interesting cases of a question of H. S. Shapiro on the distribution of time and frequency means and variances for orthonormal bases. THE UNCERTAINTY PRINCIPLE IN HARMONIC ANALYSIS AND BOURGAIN?S THEOREM. by Alexander M. Powell Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2003 Advisory Committee: Professor John J. Benedetto, Chairman/Advisor Professor Dennis M. Healy Professor Raymond L. Johnson Professor C. Robert Warner Professor J. Robert Dorfman ?c Copyright by Alexander M. Powell 2003 DEDICATION To My Parents ii ACKNOWLEDGEMENTS I am deeply grateful to my thesis advisor, John Benedetto. He has taught me a great deal of beautiful and interesting mathematics, and has been a constant source of encouragement. I can not imagine a more generous and supportive thesis advisor. I consider myself ex- tremely lucky to have worked him these past few years. I would also like to thank Wojtek Czaja for ?taking me under his wing? during the past two years. I have learned much from him. Finally, I would like to thank my family for all their love and support. iii TABLE OF CONTENTS 1 Introduction 1 1.1 Qualitative uncertainty principles . . . . . . . . . . . . . . . . . . 3 1.2 The Heisenberg uncertainty principle . . . . . . . . . . . . . . . . 5 1.3 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Frame theoretic background 10 3 Gabor systems 15 3.1 Gabor systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Density and duality . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Linear independence . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 The Zak transform . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.5 The Balian-Low theorem . . . . . . . . . . . . . . . . . . . . . . . 20 3.5.1 Sharpness in the Balian-Low theorem . . . . . . . . . . . . 21 3.6 A (p, q) Balian-Low theorem . . . . . . . . . . . . . . . . . . . . . 21 3.7 Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.8 Battle?s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Bourgain?s Theorem 26 4.1 Preliminary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . 29 iv 4.1.1 Decay rates of inverses of matrices . . . . . . . . . . . . . 29 4.1.2 Bilinear form estimates . . . . . . . . . . . . . . . . . . . . 31 4.1.3 Phase space localization . . . . . . . . . . . . . . . . . . . 32 4.2 Finite, orthonormal, well localized systems . . . . . . . . . . . . . 33 4.3 A (p, q) version of Bourgain?s theorem . . . . . . . . . . . . . . . 43 5 Orthonormalizing Coherent States 53 5.1 Orthonormalizing coherent states . . . . . . . . . . . . . . . . . . 55 5.2 Estimating the {anj,k} . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3 Localization estimates . . . . . . . . . . . . . . . . . . . . . . . . 62 6 Shapiro?s Question 67 6.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.2 Two variances and one mean . . . . . . . . . . . . . . . . . . . . . 70 6.2.1 Prolate spheroidal wavefunctions . . . . . . . . . . . . . . 71 6.2.2 Preliminary lemmas . . . . . . . . . . . . . . . . . . . . . 73 6.2.3 Two variances and one mean: the proof . . . . . . . . . . . 75 6.3 Two means and one variance . . . . . . . . . . . . . . . . . . . . . 76 6.4 Means of Bourgain bases . . . . . . . . . . . . . . . . . . . . . . . 81 Bibliography 83 v Chapter 1 Introduction Given a function f ? L2(R), the Fourier transform of f , denoted f? , is formally defined by ? f?(?) = f(t)e?2?it?dt, where the integral is over R. If one views f as a signal which is a function of time, then f? describes how f is built up from different frequency components. The uncertainty principle (UP) in harmonic analysis is a class of theorems which state that a nontrivial function, f , and its Fourier transform, f? , can not both be simultaneously too well localized. One, of course, needs to be precise about what ?localization? means. Roughly speaking, a function is well localized if it decays to zero quickly at ??, or if it is highly concentrated on a compact set. We shall state some concrete definitions of localization later. Likewise, once a measure of localization is specified, one needs to be precise about what it means to be ?too well? localized. Again, there is a great deal of flexibility, and theorems range from giving highly technical and quantitative statements to more general and qualitive interpretations. Heisenberg?s uncertainty principle in quantum mechanics is the prototype of all uncertainty principles. His uncertainty principle deals with the inability 1 to precisely determine both position and momentum of a particle. While our focus and motivation here will be purely mathematical, Heiseberg?s uncertainty principle will nonetheless play an important role for us. Later on, we shall discuss a relevant mathematical formulation of it as an L2(R) norm inequality. For some historical background on the uncertainty principle and for more information on its physical meaning, [20] and [16] both give a nice mathematical overview. The masterpiece [27] is perhaps the most comprehensive mathematical text on the subject, whereas [20] is possibly the most complete survey article on the topic. Let us begin with an elementary, non-technical example of the uncertainty principle. Given f ? L2(R) and ? > 0, define the dilation, f?(t), by f?(t) = ?f(?t). For fixed f, it is visually clear that f? becomes increasingly more con- ( ) ( ) centrated about the origin as ? ? ?. However, since f? 1 ??(?) = f? , one? ? sees that f?? becomes increasingly more spread out as ? ? ?. This example shows that when one dilates a function to make it more localized, the Fourier transform becomes less localized. While simple, this illustrates the uncertainty principle?s main theme, namely the incompatibility of having both f and f? too sharply localized. The limiting case (as ? ? ?) in the above example gives rise to the Dirac delta measure, ?. Since the distributional support of ? is {0}, ? is about as well localized as possible. On the other hand, the distributional Fourier transform of ? is the constant function ?? ? 1, which is indeed very poorly localized. For this reason, the statement ?? = 1 may be viewed as a manifestation of the uncertainty principle, [5]. 2 1.1 Qualitative uncertainty principles Given a function f, define the support of f to be the closure of the set {t ? R : f(t) 6= 0}, namely, supp(f) = {t ? R : f(t) 6= 0}. In view of our intuitive definition of localization, the notion of support gives a natural way to measure if a function is well localized. In particular, if a func- tion has compact support then it fits our intuitive requirements for being well localized. Using support as our measure of localization, we observe the following ele- mentary uncertainty principle. Suppose f ? L2(R), and that f and f? both have compact support. Then the Paley-Wiener theorem, [33], states that f is the re- striction to R of an entire function. Since an entire function can not vanish on any interval, it follows that no nontrivial f ? L2(R) can have both supp(f) and supp(f?) compact. Benedicks, [10], gave the following extension of this result. Theorem 1.1 (Benedicks). If f ? L2(R) and the sets supp(f) and supp(f?) both have finite Lebesgue measure, then f ? 0. While this is an appealing result which illustrates the uncertainty principle nicely, its hypotheses are very strong and it does not give very precise insight into matters. A more advanced result along these lines is given by Hardy, [25]. Although the result dates back to 1933, there has been a recent upsurge of interest in it, see [24], [29]. Theorem 1.2 (Hardy). Let f ? L2(R) and suppose that |f(t)| ? Ce??at2 2and |f?(?)| ? Ce??b? , 3 for some constant C and constants a, b > 0. Then ab > 1 =? f(t) ? 0 and 2 ab = 1 =? f(t) = ce?a?t , where c ? C is a constant. Hardy?s proof relies critically on complex analysis and the Phragmen-Lindelo?f theorem. Motivated by Hardy?s theorem, Ingham, [31], proved the following version for functions with compact support. Theorem 1.3 (Ingham). Let ?(t) be a positive function which monotonically approaches zero as t ? ?. Suppose f ? L2(R) and that f is zero outside of the interval [?l, l]. Such an f can satisfy f(t) = O(e?|t|?(|t|)), |t| ? ? if and only if ? ? ?(t) dt 1 t is convergent. One direction of the proof of Ingham?s theorem depends on the theory of quasi- analytic functions and the Carleman-Denjoy theorem, [30]. The other direction employs standard constructive methods. In the case where a = b, Hardy?s theorem deals with the symmetric weights e?a?t 2 2 2 and e?a?? . Ingham?s result replaces the e?a?t decay condition on f by the most extreme decay possible, namely that f is compactly supported, and replaces the other decay condition by one weaker than the original. Morgan considers the 4 problem for combinations of weights which lie ?in between? those considered by Hardy and Ingham. While Morgan actually proved several theorems in this direction,[38], the following gives a typical flavor of his results. Theorem 1.4 (Morgan). Suppose  > 0, f ? L2(R) and that 1 + 1 = 1, where p q p > 2. If p f(t) = O(e?|t| ), |t| ? ? and ?|?|q+f?(?) = O(e ), |?| ? ?, then f ? 0. Morgan?s result makes use of the Phragmen-Lindelho?f theorem and saddle point methods. The trio of theorems due to Hardy, Ingham and Morgan, respectively, shows how the uncertainty principle can be meaningfully refined by using different pair- ings of weights to measure localization. It is worth pointing out that although the above results are similar in appearance, they have different methods of proof. Understanding the role which different combinations of weights play in the un- certainty principle will be an important theme for us. The weights t2 and ?2 are especially important, and make their first appearance in the Heisenberg uncer- tainty principle. 1.2 The Heisenberg uncertainty principle The Heisenberg uncertainty principle alluded to earlier may be stated as follows. 5 Theorem 1.5 (Heisenberg Uncertainty Principle). For every f ? L2(R) and any a, b ? R ||(t? a)f || 1L2(R)||(? ? b)f? ||L2(R) ? ||f ||2L2( ). (1.1)4? R 2 Moreover, equality holds in (1.1) if and only if f(t) = Ce2?ibte?c(t?a) for some constants C ? C and c > 0. Rewriting (1.1) we have: (? ) 1 (? ) 1 2 2 |t? a|2|f(t)|2dt |? ? b|2| 1f?(?)|2d? ? ||f ||2 4? L 2(R). (1.2) In this form, we see that Heisenberg?s uncertainty principle measures localization using the t2 and ?2 weights. If a function is well localized in the sense of decaying quickly to zero at ??, then the integral ? |t|2|f(t)|2dt (1.3) will be finite. The relevant type of decay here is not a pointwise decay, but is instead an L2(R) decay. Moreover, the size of (1.3) tells us how spread out f is. For example, the functions f 11(t) = ?[?10,10](t) and f2(t) = 1? 20 2 [?1,1](t) have both been normalized and it is visually clear that the first function is more spread out than the second. This is reflected by the fact that the integral (1.3) is larger for f1 than f2. Thus, the use of the t 2 and ?2 weights to measure localization is both intuitively attractive and also allows one to make more quantitative statements about localization than in the previous section. The utility of the t2 weight in measuring localization motivates the following definition. Definition 1.6. Given f ? L2(R) satisfying ||f ||L2(R) = 1, we define the mean of f by ? ?(f) = t|f(t)|2dt (1.4) 6 and the variance of f by ? ?2(f) = |t? ?(f)|2|f(t)|2dt. (1.5) We shall often find it convenient to work with the square root of the variance (? ) 1 2 ?(f) = |t? ?(f)|2|f(t)|2dt . (1.6) This quantity is usually refered to as the standard deviation or dispersion of f We collect some interesting facts on means and variances in the following lemma. Lemma 1.7. Let f ? L2(R) and suppose ||f ||L2(R) = 1. If (? ) 1 2 I(a) = |t? a|2|f(t)|2dt (1.7) is finite for a single value a = a0 ? R, then it is finite for every a ? R. Moreover, (? ) 1 2 ?(f) = infa?R |t? a|2|f(t)|2dt . In other words, a = ?(f) minimizes I(a). We may rewrite the Heisenberg uncertainty principle in terms of variances. Theorem 1.8. If f ? L2(R) satisfies ||f ||L2(R) = 1 then 1 ?(f)?(f?) ? . (1.8) 4? There is an extensive literature on extensions and generalizations of Heisen- berg?s inequality, for example see [20]. We shall mention one particularly inter- esting example. In the next definition, we use the notation R? = R to denote the dual group of R. We shall do this whenever we wish to emphasize that we are dealing with the frequency domain. For example, if f ? L2(R) then f? ? L2(R?). 7 Definition 1.9. Let u and v be nonnegative Borel measurable functions on R? and R, respectively. If 1 < p, q 0 such that (? )1/q1/s (? s )1/p? ? sup u(?)d? v(t)?p /pdt = K s>0 0 0 then we say (u, v) ? F (p, q). Definition 1.10. Given a nonnegative Borel measurable function v, LPv (R) is the set of all Borel measurable functions f for which (? )1/p ?f?p,v ? |f(t)|pv(t)dt 0 such that ? A||c||l2 ? || cnxn||H ? B||c||l2 (2.4) holds for all finite sequences c = {cn}. We say that a sequence {xn} ? H is a Riesz basis for its span if (2.4) holds. In this case, we do not require {xn} to be complete. For example, any orthonormal sequence is a Riesz basis for its span. The following result shows that Riesz bases and exact frames are actually the same. Theorem 2.8. Let H be a separable Hilbert space. {xn} ? H is an exact frame for H if and only if it is a Riesz basis for H. A portion of the proof is illustrated by the following result. Theorem 2.9. Suppose {x ?n}n=0 ? L2(R) is a Riesz basis for its span. One can not have xN ? span {xj : j 6= N} for any N . Proof. Without loss of generality suppose N = 0, and that x0 ? span {xj : j 6= 0}. Let 0 < A ? B 0. A well known alternative definition of Riesz bases in terms of Grammian matrices appears in [22]. Theorem 2.10. Suppose X = {xn}n?Z is a frame for the separable Hilbert space H. X is a Riesz basis for H if and only if the Grammian matrix Gj,k = ?xj, xk? defines a positive invertible operator on l2(Z). In finite dimensions, Riesz basis are particularly simple. Theorem 2.11. If X = {xn}Nn=1 is a finite, linearly independent subset of a Hilbert space, H, then X is a Riesz basis for its span. Proof. Since X is finite dimensional and linearly independent, it is easily verified that (2.4) holds. 14 Chapter 3 Gabor systems We gave several examples of uncertainty principles in the introduction. The types of results we surveyed all dealt with uncertainty for an individual function and its Fourier transform. For example, the qualitative uncertainty principle, theorem 1.1, implies that a nontrivial function f ? L2(R) and its Fourier transform, f? , can not both have compact support. One of our goals is to understand how the uncertainty principle applies to certain collections of functions, as opposed to how it applies to individual func- tions. For us, the collection of functions under consideration will usually be an orthonormal basis. We want to know what sort of uniform localization, in time and frequency, the elements of an orthonormal basis can have. This chapter will focus on this question for Gabor orthonormal bases, but will also briefly address wavelet orthonormal bases. Gabor systems and wavelet systems are both examples of coherent systems. A system of functions is coherent if it generated by a single function under the action of a group. For example, let f ? L2(R), and define fn(t) = f(t ? n). It is clear that {fn} is a coherent system of functions, generated by the action of Z on f . It is well known, e.g., [12], that this particular system of functions can 15 not form an orthonormal basis, or even a frame, for L2(R). Gabor systems and wavelets are the simplest coherent systems for which one can obtain orthormal bases for L2(R). Although it will be not play a direct role in our work, let us mention that the respective groups associated with Gabor systems and wavelets are the Heisenberg group and affine group. 3.1 Gabor systems Definition 3.1. Given a function f ? L2(R) and constants a, b > 0, the Gabor system, G(f, a, b) = {fm,n}m,n?Z is defined by f (t) = e?2?ibmtm,n f(t? an). Thus, a Gabor system consists of translates and modulates of a fixed function. Gabor systems have been widely studied because they can be used to give effective decompositions of functions. One of the main questions in Gabor analysis is to determine for which functions f and constants a, b the Gabor system, G(f, a, b), is an orthonormal basis, Riesz basis, or frame. The following example is often called the trivial Gabor basis. Example 3.2. Let f(t) = ?[0,1](t). Using standard results on Fourier series it is easy to see that G(f, 1, 1) is an orthonormal basis for L2(R). The following result shows that the localization of a Gabor system is inher- ently uniform with respect to variances. Theorem 3.3. Suppose that f ? L2(R) and that the variances ?(f) and ?(f?) are both finite. Let {fm,n} = G(f, a, b) for some a, b > 0. A direct calculation, [4], shows that ?m,n ? Z, ?(fm,n) = ?(f) 16 and ?m,n ? Z, ?(f?m,n) = ?(f?). This shows that the elements of a Gabor system have uniform localization with respect to time and frequency variances. The following example shows a Gabor frame which has excellent localization in time and frequency. 2 Example 3.4. If g(t) = e??t and ab < 1, then G(g, a, b) is a frame for L2(R). See [22] for further details. Moreover, a direct calculation combined with theorem 3.3 shows that ? 1m,n ? Z, ?(gm,n) = ?(g) = ? 2 ? and ? 1m,n ? Z, ?(g?m,n) = ?(g?) = ? . 2 ? The problem with theorem 3.3 is that the uniform localization need not be a ?good? localization when the Gabor system under consideration is an orthonor- mal basis. This is illustrated by example 3.2, where f(t) = ?[0,1](t) generates an orthonormal basis. Note that ?(f?) = ?, so that all elements of the trivial Gabor basis have uniformly poor localization in frequency. We shall see that this behavior is typical for Gabor orthonormal bases. 3.2 Density and duality The difference between examples 3.2 and 3.4 is actually quite illuminating. In example 3.2, one has a poorly localized orthonormal basis with a = b = 1. In example 3.4, one has a well localized frame but one is required to take a ?denser? set of translates and modulates (i.e., ab < 1). 17 The next theorem is a first step towards explaining the relationship between the value of (a, b) and localization and basis/frame properties of Gabor systems. Theorem 3.5. If G(g, a, b) is a frame for L2(R) then ab ? 1. If G(g, a, b) is a Riesz basis for L2(R) then ab = 1. The following closely related result gives further insight. Theorem 3.6 (Ron-Shen Duality). Let g ? L2(R) and a, b > 0. G(g, a, b) is a frame for L2(R) if and only if G(g, 1 , 1) is a Riesz basis for its closed linear b a span. 3.3 Linear independence An interesting and useful result on Gabor systems is that any finite subset of a Gabor system is linearly independent. The case a = b = 1 was proven in [28] by Heil, Ramanathan, and Topiwala and the general case was shown by Linnell in [36]. Theorem 3.7. Let f ? L2(R) be nontrivial, and a, b > 0. Any finite subset of G(f, a, b) is linearly independent. Heil, Ramanathan, and Topiwala conjectured, in [28], that this result still holds for irregular Gabor systems (i.e., those not defined on a lattice). While they have shown that this conjecture is true for certain interesting cases, the general case is still open. 18 3.4 The Zak transform Definition 3.8. The Zak transform, Zf , of a function f ? L2(R) is formally defined to be ? Zf(t, ?) = f(t? n)e2?in? . n?Z Note that the Zak transform is quasiperiodic, [22]. In other words, it satisfies the two equations Zf(t+ 1, ?) = e2?i?Zf(t, ?), (3.1) and Zf(t, ? + 1) = Zf(t, ?). (3.2) For this reason, Zf is fully determined by its values on Q = [0, 1)2. The next result gives a precise statement on the range and domain of the Zak transform. Theorem 3.9. The Zak transform is a unitary operator from L2(R) to L2(Q). The following result, [9], shows why the Zak transform is especially useful for studying Gabor systems on the Z ? Z lattice. Theorem 3.10. Let g ? L2(R). 1. If Zg 6= 0 a.e. in Q then G(g, 1, 1) is complete in L2(R). 2. If 1/Zg is in L2(Q) then G(g, 1, 1) is complete and minimal in L2(R). A sequence, {xn}, is minimal if ?j, xj ?/ span{xn : n 6= j}. 3. If there exist 0 < A ? B < ? such that A ? |Zg| ? B a.e. in Q then G(g, 1, 1) is a Riesz basis for L2(R). 4. If |Zg| = 1 a.e. in Q then G(g, 1, 1) is an orthonormal basis for L2(R). 19 3.5 The Balian-Low theorem The Balian-Low theorem is the classical uncertainty principle for Gabor systems. It shows that the localization behavior of the trivial Gabor orthonormal basis is typical of all Gabor orthonormal bases. The Balian-Low theorem traces its origins back to [1], [37], but there have been numerous corrections and simplifications of the original proof, e.g., [8], [2]. Theorem 3.11 (Balian-Low). Let g ? L2(R). If the Gabor system G(g, 1, 1) is an orthonormal basis for L2(R) then either ? |t|2|g(t)|2dt = ? or ? |?|2|g?(?)|2d? = ?. This is the simplest version of the Balian-Low theorem. It is actually true in much greater generality. For example, [8], the result still holds if ?orthonormal basis? is replaced by ?Riesz basis?. The theorem above applies to Gabor systems on the lattice Z ? Z and holds in one dimension. Gro?chenig, Han, Heil, and Kutyniok have given extensions to symplectic lattices in higher dimensions, [23]. Benedetto, Czaja, and Maltsev have investigated the Balian-Low theorem for the symplectic form in higher dimensions, [7]. Rewriting the Balian-Low theorem in terms of variances gives Theorem 3.12. Let g ? L2(R). If G(g, 1, 1) is an orthonormal basis for L2(R) then either ?2(g) = ? or ?2(g?) = ?. 20 3.5.1 Sharpness in the Balian-Low theorem The Balian-Low theorem says there are no Gabor orthonormal bases localized with respect to both the t2 and ?2 weights. It is natural to ask to what extent this result is sharp. Namely, by how much can one weaken the t2 and ?2 weights so that the Balian-Low theorem no longer holds? We have proven the following result, [6], which shows that the Balian-Low theorem is essentially sharp. Theorem 3.13 (Benedetto, Czaja, Gadzin?ski, Powell). Let d > 2. There exists a function g ? L2(R) such that G(g, 1, 1) is an orthonormal basis for L2(R) and ? 1 + |t|2 |g(t)|2dt 0 and that 1 + 1 = 1. p q If g ? L2(R) and G(g, 1, 1) is an orthonormal basis for L2(R) then either ? |t|p+|g(t)|2dt = ? 21 or ? |?|q+|g?(?)|2d? = ?. The proof of this makes use of the following results on Gabor systems and modulation space embeddings. Definition 3.15. Given f, g ? L2(R) the short time Fourier transform of f with respect to g is formally defined by ? Sg[f ](t, ?) = f(t)g(x? t)e?2?ix?dx. Definition 3.16. Let g be a fixed Schwartz class function. The modulation space M1,1 is defined to be the set of all measurable functions for which ? ? ||f ||1,1 = |Sgf(x, y)|dxdy 0 and assume 1 + 1 = 1 with 1 < p, q < ?. There p q exists a constant C such that ((? ) )1 (? ) 1 2 2 ?f?1,1 ? C |t|p+|f(t)|2dt + |?|q+ |?(?)|2d? holds for all f ?M1,1. 22 Thus,we see that theorem 3.14 follows from theorems 3.17 and 3.18. As with the standard Balian-Low theorem, we have the following ?sharpness? result. Theorem 3.19 (Benedetto, Czaja, Gadzin?ski, Powell). Let d > 2 and 1 + 1 = 1 with 1 < p, q < ?. There exists a function g ? L2(R) such that p q G(g, 1, 1) is an orthonormal basis for L2(R), and ? 1 + |t|p |g(t)|2dt 2. In view of these two results, it is natural to ask what happens for general (i.e., non-Gabor) orthonormal bases, namely, what sort of ?uniform 26 localization? can a general orthonormal basis for L2(R) have with respect to the weights t2 and ?2. This question was posed by Balian, [1], and answered by Bourgain, [11]. Theorem 4.1 (Bourgain). Let  > 0. There exists an orthonormal basis, {bn}, for L2(R) such that 1 ?(bn) ? ? + , ?n 2 ? and ?(b?n) ? ? 1 + , ?n. 2 ? This result uses variances (see definition 1.5) to measure localization; the uniform boundedness of the variances reflects a type of uniform localization of the basis with respect to the t2 and ?2 weights. To put this in perspective, note that there are ? ? S(R) which gener- ate wavelet orthonormal bases, {?m,n}m,n?Z, for L2(R). Since ? ? S(R), each ?(?m,n) and ?(??m,n) is finite. However we have already seen (fact 3.23) that for any wavelet system these variances are not uniformly bounded, [4]. Theorems 3.11, 3.13, and 4.1 form a trio of results which give insight into the boundaries of uncertainty for the t2 and ?2 weights. In this chapter we shall consider the situation for the weights tp and tq, where 1+ 1 = 1. This investigation p q is motivated by the (p, q) Balian-Low theorem of Feichtinger and Gro?chenig, theorem 3.14, which says that if g ? L2(R) generates a Gabor orthonormal basis then one can not have both ? |t|p+|g(t)|2dt 2. We shall consider what sort of localization a general orthonormal basis can have with respect to the tp and ?q weights. Our main result will generalize theo- rem 4.1. We use the following ?generalized variances? to measure localization. Definition 4.2. Given f ? L2(R) and ? > 0 we define the generalized variance of f by ? ?2?(f) = inf |t? a|?a?R |f(t)|2dt. As with the standard definition of variance, it will often be convenient to work with the square root of the generalized variance (? ) 1 2 ??(f) = infa?R |t? a|?|f(t)|2dt . We refer to this as the generalized standard deviation or dispersion of f . In terms of this definition, our main result is Theorem 4.3. Let 1 < p, q 1, we say A belongs to Qs if the coefficients Am,n satisfy | CAm,n| < (1 + |m? n|)s for some constant C > 0. We say that A belongs to Es if |A ?s|m?n|m,n| < Ce . 29 The next result says that if A is in one of the two decay classes defined above, then A?1 has a similar kind of decay. Theorem 4.5 (Jaffard). Let A : l2(I) ? l2(I) be an invertible matrix, where I = Z,N, or {0, ? ? ? , N ? 1}. Then A ? Q =? A?1s ? Qs and A ? E =? A?1s ? Es? , for some 0 < s? ? s. The case I = {0, 1, 2, ? ? ? , N ? 1} should be interpreted as follows. We quote from [43]: ?View the n ? n matrix An as a finite section of an infinite dimen- sional matrix A. If we increase the dimension of An (and thus consequently the dimension of (An) ?1) we can find uniform constants independent of n such that the corresponding decay properties hold.? Let us next comment on the constants which arise in Jaffard?s theorem. We restrict ourselves to the case I = {0, 1, ? ? ? , N?1}. Suppose that AN are sections of the infinite matrix A and that |AN(j, k)| ? C | ? | , ? j, k ? I1 + j k s holds for all N . Suppose for simplicity that there is a fixed 0 < r < 1 such that AN = IN ?BN with ||BN || ? r < 1 holds for each N . Jaffard?s theorem then says there exists C ? such that ? | CA?1N (j, k)| ? | ? | , ? j, k ? I1 + j k s holds for each N . The constant C ? depends only on r, s, and C. One may see this by examining Jaffard?s proofs, [32]. 30 4.1.2 Bilinear form estimates Next, we state some estimates on bilinear forms. Since the results are simple we include the proofs. Other results of this type appear in [26]. Lemma 4.6. Given ? > 1, there exists a constant C? such that for every {an} ? l2(N), N ? N ?N ?N | ?Nan||am| 2 1 + |j ? | ? C? ? |aj| .k j=0 k=0 j=0 Proof. The idea is to sum along the positively sloped diagonals of the finite grid {(j, k) ? Z2 : 0 ? j, k ? N}. Following this idea and applying Ho?lder?s inequality at the appropriate place yields ?N ?N | N N N?daj||ak| ? ??| |2 |ad+j||aj|= aj + 2 1 + |j ? k|? 1 + d? j=0 k=0 j=0 d=1 j=0 ?N ?N N??d | |2 1= aj + 2 |ad+j||a? j|1 + d j=0 (d=1 )j=0?N ?N ?N ? | |2 | |2 1aj + 2 ak 1 + d? j=0 k=0 d=1 ?N ? C 2? |aj| . j=0 Lemma 4.7. Let ? > 2. There exists C? such that for every {a 2 2m,n} ? l (N ) ? ? (? )N N | Nam,n||aj,k| 2 1 + |m? j|? + |n? | ? C |a | .k ? ? m,n m,n=0 j,k=0 m,n=0 31 Proof. ?N ?N |am,n|| | ?N ?N N??c N??daj,k |am,n||am+c,n+d| 1 + |m? ? 2j|? + |n? k|? 1 + |c|? + |d|? m,n=0 j,k=0 ( ) c=0 d=0 m=0 n=0?? ? ( )N N ? | |2 1 ? a 2m,n ? ? 1 + |c| ? + |d| ? C? |a? m,n| . c Z d Z m,n=0 m,n=0 Consequently, one also has Lemma 4.8. Given ? > 1, there exists a constant C? such that for every {am,k} ? l2(N2) and N ? N ?N ?N ?N | ?Nam,k||aj,k| | ? | ? C 2 ? ? |aj,k| . 1 + j m k=0 m=0 j=0 j,k=0 4.1.3 Phase space localization We begin by recalling the following definition. Definition 4.9. Given f, g ? L2(R) the short time Fourier transform of f with respect to g is formally defined by ? Sg[f ](t, ?) = f(t)g(x? t)e?2?ix?dx. The following lemma is theorem 11.2.5 in [22]. Lemma 4.10. If f, g ? S(R) then Sg[f ] ? S(R2). Lemma 4.11. Suppose ? ? L2(R) and define ? (t) = e?2?ijtj ?(t). If | C??(?)| ? 1 + |?| ,N for some constant C > 0, then |? ?| ? C1?j, ?k , (4.1) 1 + |j ? k|N where C1 is a constant which may depend on N . 32 Proof. Without loss of generality assume n > 0 and note that ? |??0, ?n?| ? |??(?)||??(? ? n)|d? = I1 + I2, where ? I1 = |??(?)||??(? ? n)|d? ???(n/2) C2? | | | ? | d?N??(n/2) (1 + ? )(1 + ? n N)? 2 ? 1 C d? 1 + |(n/2)|N N??(n/2) 1 + |?| ? C1 1 + |n|N and ? I2 = |??(?)||??(? ? n)|d? ??>(n/2) 2 ? C| | | ? | d?(1 + ? N)(1 + ? n N?>(n/2) )? 1 C2? 1 + |(n/2)| | ? | d?N N?>n/2 1 + ? n ? C1 . 1 + |n|N Combining the estimates for I1 and I2, (4.1) follows. 4.2 Finite, orthonormal, well localized systems Lemma 4.12. Assume 1 + 1 = 1 and q ? N. There exists a constant C = p q C(p, q) and a constant K0 > 0 so that for each T ? N and each integer K > K0 there exists a finite orthonormal set S0 = S0(T,K) = {s }T?1n n=0 of cardinality T satisfying supp sn ? [?1, 1] (4.2) 33 and (? ) 1 2 |t|p|sn(t)|2dt ? C (4.3) and (? ) 1 2 |? ? nK|q|s?n(?)|2d? ? C, (4.4) for n = 0, 1, ? ? ? , T ? 1. Proof. Throughout the proof, C will denote various constants which are inde- pendent of T and K. C may depend on (p, q), ?, and N , all of which are fixed throughout the proof. I. Let ? ? S(R) be a function of L2(R) norm one satisfying supp ? ? [?1, 1] (4.5) and | C??(?)| ? | | , (4.6)? N + 1 where N > 4q,N ? N. Now define ? (t) = e2?ijKtj ?(t), j = 0, 1, ? ? ? , T ? 1, where K > K0 are integers and K0 will be defined later. Next, define h0(t) = ?0(t) (4.7) and ?n?1 hn(t) = ?n(t) ? an,j?j(t), 1 ? n ? T ? 1 (4.8) j=0 where the an,j are chosen to make hn orthogonal to {? }n?1j j=0 . This choice of an,j implies that for all 0 ? l ? n? 1 ?n?1 ??n, ?l? = an,j??j, ?l?. j=0 34 Rewriting this in matrix form, we have Ga = g, ? ? ???n?1, ?n?1? ??n?2, ?n?1? ? ? ? ??0, ?n?1?? ? ?? ? ??n?1, ?n?2? ??n?2, ?n?2? ? ? ? ?? ?? 0 , ?n?2?? where G = ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??n?1, ?0? ??n?2, ?0? ? ? ? ??0, ?0? ? ? ? ? ?an,n?1? ???n, ?n?1??? ? ? ?a ? ? ? ? n,n?2?? ? ??? , ? ? ?? n n 2 ?? a = ? and g = ? .?? ? ? ? ? ? ? ? ?? ? ? ? ??? an,0 ??n, ?0? Note that these matrices all depend on n, but we shall usually suppress this for economy of notation. When we wish to emphasize the dependence on n, we shall write G = Gn for example. II. First of all, observe that G is an invertible matrix. To see this, note that the {? }n?1j j=0 are linearly independent by theorem 3.7. Hence, by theorem 2.11 {?j}n?1j=0 is a Riesz basis for its span. Thus, by theorem 2.10, G = Gn is invertible for each n (recall that G depends on n). In particular, the {an}n?1j j=0 are unique. To apply Jaffard?s lemma, we also need to know that the spectrum of G = Gn stays uniformly bounded away from 0 independent of n. Note that the matrix G is a Toeplitz matrix, and by (4.6) has polynomial decay of order N off the main diagonal, in fact, | | ? C ? CG(j, k) . (4.9) 1 +KN |j ? k|N 1 + |j ? k|N For K large enough, the first inequality of (4.9) implies G = Gn is diagonally 35 dominant and has spectrum uniformly bounded away from 0. By our choice of K > K0, this will be the case. III. By the result of Jaffard, G?1 has the same type of decay off its main diagonal as G, namely, |G?1(j, k)| ? C . 1 + |j ? k|N Also, note that the comments after the statement of Jaffard?s theorem ensure that C is independent of K. Therefore, noting that an,n?j is the j-th element of the vector a, ?n?1 ?n?1 |a | ? |G?1(j, l)||g | = |G?1n,n?j l (j, l)||??n, ?n?l?1?| l=0 l=0 ?n?1 ( )( ) ? C C 1 + |j ? l|N 1 +KN |l + 1|N l=0 ?n?1 ( ) ? C C 1 + |j ? l|N KN(l + 1)N l=0 C ?n?1? 1 1 KN (1 + |j ? l|N) |l + 1|N l=0 ? ? C ? 1 1 KN (1 + |(j + 1) ? l|N) |l|N ( l=)1 ? 1 C| | .KN j + 1 N To see the last step, note that ? ??1 1 1 |l| ?N(1 + |j + 1 ? l|N) (1 + | j+1 |N) lN 1?l? j+1 2 l=1 2 combined with a similar estimate for the remaining range of summation gives the desired inequality. By the above, we have | Can,j| = |an,n?(n?j)| ? . (4.10) KN |n? j + 1|N 36 IV. Note that ?n?1 2 ?n?1 n+1 | |2 ? C 1 C 2 ? 1 an,j ? K2N |n? j + 1|2N K2N j2N j=0 j=0 j=2 ? C ? C. K2N Using (4.5), we can estimate the localization of the hn(t). ? |t|p|hn(t)|2dt ? ||h 2n||L2(R) ?n?1 ?n?1 = |??n ? an,j?j, ?n ? an,j?j?| j=0 j=0 ?n?1 ?n?1 ? 1 + 2 |an,j||??n, ?j?| + |an,j||an,k||??j, ?k?| j=0 j,k=0 ( 1?? ) ( ) 1 n 1 2 ?n?1 2 ?n?1 ? 1 + 2 |a |2n,j |? C ? 2j, ?n?| + |an,j||an,k| 1 +KN |j ? k|N j=0 j=0 j,k=0 ( 1 1?n? ) (1 2 ?n? )1 2 2 n?1 ? | |2 C ? 1 + 2 a 2n,j (1 +KN |j ? n| + C |aN 2 n,j|) j=0 j=0 j=0 ? C, where the penultimate inequality used lemma 4.8. Thus, ? |t|p|h 2n(t)| dt ? C, (4.11) where C is independent of n, T,K. 37 V. We now estimate the localization of the h?n(t). Using (4.10) we have (? ) 1 2 |? ? nK|q|h?n(?)|2d? (? ) (? ?? ) 1 1 n 1 2 2 ? |? ? nK|q|??(? ? nK)|2d? + |? ? nK|q| an,j??(? ? jK)|2d? j=0 (? ) 1 n?1 (? ) 1 2 ? 2 ? |?|q|??(?)|2d? + |a | |? ?K(n? j)|q|??(?)|2n,j d? j=0 (? ) 11 2 ?? (? ? )n 1 q 2 ? |?|q|??(?)|2d? + C |an,j| |K(n? j)|(q?l) |?|l|??(?)|2d? j=0 l=0 (? ) 1 ?n?1 ( ? ) 12 2 ? |?|q|??(?)|2d? + C |a ||n? j|q/2 Kqn,j sup0?l?q |?|l|??(?)|2d? j=0 (? ) 1 2 ?n?1 ? |?|q|??(?)|2d? + CKq/2 |an,j||n? j|q/2 j=0 (? ) 1 n?1 2 ? ? |?|q|??(?)|2d? + CKq/2 |an,j||n? j + 1|q/2 j=0 (? ) 1 n?1 2 ? | |q| |2 K q/2 ? ? ??(?) d? + C |n? j + 1|?N |n? j + 1|q/2 KN j=0 (? ) 1 2 ? |?|q|??(?)|2 Cd? + KN?(q/2) ? C. Thus, (? ) 1 2 |? ? nK|q|h?n(?)|2d? ? C, (4.12) where C is independent of n, T,K. VI. It remains to normalize the hn. First note that the norms of the hn are bounded away from 0, since by (4.8) and (4.10) 38 1 = ||?n||L2(R) ? ||hn||L2(R) + ||?n ? hn||L2(R) ?n?1 ? ||hn||L2(R) + |an,j| j=0 ?n?1 ? || || 1 Chn L2(R) + KN |n? j + 1|N j=0 ?? ? || C 1hn||L2(R) + KN jN j=2 ? ||hn|| C L2(R) + . KN Take K large enough so that C < 1N . From this it follows thatK 2 1 ? ||hn||L2(R). (4.13) 2 In view of this and the discussion following (4.9), it is clear how to define the constant K0 in the statement of the theorem. Finally, let sn(t) = hn(t)/||hn||L2(R). By (4.11), (4.12), and (4.13) we see that (4.3) and (4.4) hold. Also, it is clear that (4.5) implies (4.2). Lemma 4.13. Assume 1 + 1 = 1 and q ? N. There exists a constant C and a p q constant K0 such that for every K > K0 and T ? N satisfying T 2/p ? N and T 2/q ? N, there exists a finite orthonormal set, S = S(T,K) = {sm,n}, (0 ? m < T 2/q and 0 ? n < T 2/p) of cardinality T 2, satisfying [ ] 1 supp s 2/p 2/pm,n ? T , 2T K , (4.14) 2 (? ) 1 2 |t?Kn? T (2/p)K|p|s 2m,n(t)| dt ? C, (4.15) 39 and (? ) 1 2 |? ?Km|q|s? (?)|2m,n d? ? C. (4.16) Proof. I. Regarding the hypotheses of the lemma, note that there exist infinitely many T ? N for which T 2/p ? N and T 2/q ? N. To see this, note that q ? N implies a = p ? Q with a, b ? N. Now, for b 2/p every N ? N, we can define TN = Naq ? N, so that TN = N2bq ? N and 2/q T = N2aN ? N. 2/q II. Let S (T q/20 , K) = {s (t)}T ?1m m=0 be the system from the previous lemma. Define s (t) = s (t? nK ? T (2/p)K) for 0 ? m < T 2/qm,n m and 0 ? n < T 2/p. Now, (4.15) and (4.16) hold by the previous lemma. Also, note that by (4.2) [ ] supp sm,n ? nK + T 2/pK ? 1, nK + T 2/pK + 1 , so that all the sm,n are supported in [ ] [ ] T 2/pK ? 1, (T 2/p ? 1)K + T 2/pK + 1 ? 1T 2/p, 2KT 2/p . 2 Lemma 4.14. Let {?m} be as in the proof of lemma 4.12 and let ?m,n(t) = ?m(t? nK ?KT 2/p). Then ??? ?? l?? ?l ? ? C|K(m+ j)| ??m,n(?)??j,k(?)d?? |K(j ?m)|N + |K(k ? n)| ,N for all j,m ? 0 satisfying (j,m) 6= (0, 0). 40 Proof. Throughout the proof, C will denote a constant independent of T,K. Recall that K ? N. So, ??? ? ?? ? ?l?? ?m,n(?)??j,k(?)d?? ??? ?2/p 2/p ? = ?? ?le?2?i(nK+T K)???(? ?mK)e2?i(kK+T K)???(? ? jK)d??? ???? ? ? = ? ?le?2?i(n?k)K???(? ?mK)??(? ? jK)d??? ??? ? = ?? ? (? +mK)le?2?i(n?k)K(?+mK)??(?)??(? ? (j ?m)K)d??? ??? ?? = ?? (? +mK)le?2?i(n?k)K???(?)??(? ? (j ?m)K)d??? ?l ??? ?? ? |C l?d ? dd||mK| ? ? ??(?)??(? ? (j ?m)K)e?2?i(n?k)K?d??? d=0 ?l ? ? = |C ||mK|l?d ?S [?dd ?b ??]((j ?m)K, (n? k)K)? d=0 ?l ? ? ? C|(m+ j + 1)K|l ?S d?b[? ??]((j ?m)K, (n? k)K)? d=0 ? C|(m+ j + 1)K| l 1 + |j ?m| ,NKN + |n? k|NKN where we used lemma 4.11 and the fact that ? ? S(R) in the last inequality. Lemma 4.15. Let S = S(K,T ) be the system from lemma 4.13. Also, assume q ? N. For every f ? span S one has ??? ?? ?? ?l|f?(?)|2d??? ? CK lT (2l)/q||f ||2L2( ) for l = 0, 1, ? ? ? , q. (4.17)R Proof. Throughout the proof, C will denote various constants which are indepen- dent of T,K. Assume f ? span S. Since the ?m,n are linearly independent and span S(T,K), we have (T (?2/q)?1) (T (?2/p)?1) f(t) = dm,n?m,n(t), m=0 n=0 41 for some finite sequence of constants {dm,n}. The disjointness of the supports of ?m,n and ?j,k for n =6 k implies ?? ?? 2 2 2 2 ?T?q ?1 T?p ?1 T?q ?1 T?p ?1 ? ||f ||2 ? ?L2( ) = ?? dR m,ndj,k??m,n, ?j,k??? ?m=0 n=0 j=0 k=0 ? ?? ?? 2 2 2 ??T? q ?1 T?p ?1 T?q ?1 ?? = ?? dm,ndj,n??m,n, ?j,n???? m=0 n=0 j=0 ? ?? ??? ?? ? = ?? | ? d |2m,n + dm,ndj,n??m,n, ?j,n??? m,n m6=j n ? ?? ? |d 2m,n| + |dm,n||dj,n||??m,n, ?j,n?|. m,n m=6 j n That is, ? ?? ||f ||2 ? |d |2L2( ) m,n + |dm,n||dj,n||??m,n, ?j,n?|. (4.18)R m,n m=6 j n I. Using lemma 4.8 ?? ?? |dm,n||dj,n||??m,n, ?j,n?| ? |dm,k|| C dj,k| 6 6 1 +K N |j ?m|N m=j n k m=j ?? ? |dm,n||dj,n| C KN |m? j|N m6=j n ? C ? |d 2 N m,n | . K m,n Therefore, applying the triangle inequality to (4.18) gives: ? ?? |d |2j,k ? ||f ||2L2( ) + |dm,k||dR j,k||??m,k, ?j,k?| j,k m6=j n ? ? ||f ||2 CL2( ) + |d 2R N m,n| .K m,n Take K large enough so that C < 1N . ThusK 2 ? |d 2m,n| ? 2||f ||2L2( ). (4.19)R m,n 42 II. Using lemma 4.14 and (4.19) we have ? ? ???? ? ? ???? ? ?? ? ?l|f?(?)|2d??? = ? d l? m,ndj,k ? ??m,n(?)??j,k(?)d??? m,n j,k T?2/q?1 T?2/q?1 T?2/p?1 T?2/p?1 ??? ?? ? |dm,n||d ? lj,k| ? ? ??m,k(?)??j,k(?)d??? j=0 m=0 k=0 n=0 T?2/q?1 T?2/q?1 T?2/p?1 T?2/p?1 ? | || | |K(j +m+ 1)| l C dm,k dj,k 1 + |K(k ? n)|N + |K(j ?m)|N j=0 m=0 k=0 n=0 ???? ? C(2K)lT (2l)/q |dm,n||dj,k| 1 + |k ? n|N + |j ?m|N ( n j m) k? ? CK lT (2l)/q |d 2m,n| m,n ? CK lT (2l)/q||f ||2L2(R). 4.3 A (p, q) version of Bourgain?s theorem We are now ready to prove our main result, theorem 4.3. The proof follows that of Bourgain, [11] which, in turn, is based on an idea of W. Rudin, [40], for con- structing bounded bases for the Hardy space H2(Cn). Proof of Theorem 4.3. Throughout the proof C will denote various constants which are independent of n, Tn, K, and any indices. Let {fn} ?n?N ? Cc (R) be sequence which is dense in the unit sphere of L2(R). Fix K > max{2,K0}, where K0 is the same as in lemma 4.13. The orthonormal ? basis we construct will be of the form ?n=1Bn where Bn is a finite orthonormal set of C? compactly supported functions. We shall construct the Bn inductively. 43 I. Suppose B1, . . . , Bn?1 are already defined such that Bj is a finite orthonormal set of C? compactly supported functions and the elements of Bj and Bk are mutually orthonormal. Define Fn = fn ? P[B1,...,Bn 1]fn, where P? [B1,...,Bn?1] is the orthonormal projection onto n??1 [B1, . . . , Bn?1] ? span Bn?1. l=1 For the base case of the induction we simply let F1 = f1. Using Fn, we now prepare the way to construct Bn. i. Note that ||F ||2n L2( ) ? 1. (4.20)R To see this, we shall first show Fn ? P[B1,??? ,Bn 1]f? n. ?Fn,P[B1,??? ,Bn 1]fn? = ?f? n ? P[B1,??? ,Bn 1]fn, P? [B1,??? ,Bn 1]f? n? = ?fn ? P[B1,??? ,Bn?1]fn, P[B1,??? ,Bn 1](P? [B1,??? ,Bn 1]fn)?? = ?P[B1,??? ,Bn 1]fn ? P[B1,??? ,Bn 1](P[B1,??? ,Bn 1]fn), P? ? ? [B1,??? ,Bn 1]fn?? = ?0, P[B1,??? ,Bn]fn? = 0. Since ||fn||2L2( = 1 it follows from the definition of F and the orthogonalityR) n proven above that 1 = ||Fn||2L2( ) + ||P 2R [B1,...,Bn?1]fn||L2(R). Thus ||Fn||L2(R) ? 1. ii. Since fn and all elements of the Bj are C ? and compactly supported it follows that Fn is also C ? and compactly supported. Choose Tn > 2 large enough so that [ ] supp Fn ? ? 1 T 2/p 1 , T 2/pn n , (4.21)2 2 44 n??1 supp b ? [?1 1T 2/p 2/pn , Tn ] for all b ? Bj, (4.22)2 2 j=1 and ? |?|l|F?n(?)|2d? ? T 2l/qn , for l = 0, 1, . . . , q. (4.23) Note that we have no difficulties with the case l = 0 in (4.23), since ||F?n||L2(R) ? 1 by Parseval?s theorem and (4.20). II. Let S = S(Tn, K) = {sn : 0 ? j < T (2/p) and 0 ? k < T (2/q)j,k n n } be the system from lemma 4.13. We will switch from the double indexing to T 2 single indexing and enumerate the elements of the system as {sn,l} nl=1. If l1, l2 are the indices for which s nn,l = sl ,l , let1 2 x(s ) = Kl + T (2/p)n,l 1 n K and y(sn,l) = Kl2, so that by lemma 4.13 (? ) 1 2 |t? x(s )|p 2n,j |sn,j(t)| dt ? C (4.24) and (? ) 1 2 |? ? y(s qn,j)| |s?n,j(?)|2d? ? C. (4.25) Note that T (2/p)n K ? x(sn,j) ? 2KT 2/p 2/qn and 0 ? y(sn,j) ? KTn . (4.26) Let 0 < ? < 1 be fixed throughout the proof. Choosing ? carefully (small 4 enough) will allow one to estimate precise values of the constant C in theorem 4.3. We shall not consider this issue during the proof, and shall content ourselves with finding some, possibly large, constant C that works. Define 45 bn,1(t) = ? Fn(t) + ?n,1s1,n(t)Tn bn,2(t) = ? F (t) + ? s T n n,1 n,1 (t) + ?n,2sn,2(t) n .. .. .. b ?n,T 2(t) = Fn(t) + ?n,1sn,1(t) + ? ? ? + ?k,T 2?1sn,T 2?1(t) + ?n,T 2sn T n n n n,T 2(t),n n T 2 where the ?n,j and ?n,j are chosen to ensure that {b nn,j}j=1 is orthonormal. i. The choice of ?n,j and ?n,j implies that | ? | ? ?1 ?n,j for j = 1, 2, ? ? ? , T 2n , (4.27)Tn and | ??n,j| ? for j = 1, 2, ? ? ? , T 2n ? 1. (4.28)T 2n ? To see this, first note that {Fn} S(Tn, K) is an orthogonal set. Therefore, the { }T 2assumption that B nn,j j=1 is orthonormal implies that for l = 1, 2, ? ? ? , T 2n we have ?2 0 = ||Fn||2 2 22 L2( + ?T R) n,1 + ? ? ? + ?n,l?1 + ?n,l?n,l (4.29)n and for l = 1, 2, ? ? ? , T 2n ? 1 ?2 ?2 = 1 ? ||F 2 2 2n,l 2 n||L2T (R) ? ?n,1 ? ? ? ? ? ?n,l?1. (4.30)n ii. Using (4.29) and (4.30) we shall now prove (4.27) and (4.28) by induction. The case j = 1 of (4.27) holds since (4.30) implies, ?2 1 = ||F 2 2 2 n ||L2 + ? .T (R) n,1n Since 2 < Tn and ? < 1 , we may choose 0 < ?n,1 ? 1. So,4 2 |1 ? ?n,1| ? |1 ? ?2n,1| ? ? ? ? . T 2n Tn Using this, the case j = 1 of (4.28) now follows since by (4.29) ?2 0 = ||F 2n|| 2 + ?n,1?n,1 T 2 L (R)n 46 which implies 2 2 |?n,1| ? ? 1 ? 1 | ? ? ? . T 2 ? 2 2n n,1| Tn (1 ? ?/Tn) Tn The last inequality holds because ? < 1 and Tn > 2.4 iii. Next, assume |? ?n,j| ? 2 holds for j < l. We may once again chooseTn 0 < ?n,l ? 1. Since the cardinality of S(Tn, K) is T 2n , 2 ?l?1 2 | ? ? ? ? 2 ?2 ? 1 ?n,l| ? |1 ? ?2 2 2n,l| ? + ? ? + TT 2 n,j T 2 n ? 2 ? ,4 2n T T Tj=1 n n n n and (4.27) follows by induction. For (4.28), assume that |? ?n,j| ? 2 for j < l andTn |1 ? ? ?n,l| ? . Thus,Tn ( 2 ?l? )1 ( )2 |? | ? 1 ? ||F ||2n,l | | n L2( ) + ? 2 n,j ? 1 ? ? 2 ? , ? 2 Rn,l Tn (1 ? ?/T ) T 2 T 2j=1 n n n and (4.28) holds by induction. III. By (4.27) and (4.28), we know that ?n,j is close to zero and ?n,j is close to one. Thus, we expect to have bn,j close to sn,j. In fact, ||bn,j ? sn,j||L2(R) ? ? 3 . (4.31) Tn To see this, note that by (4.27) and (4.28) ||bn,j ? sn,j||L2(R) ? ||bn,j ? ?n,jsn,j||L2(R) + |1 ? ?n,j| ? ||bn,j ? ? ?n,jsn,j||L2(R) + Tn ( ) 1 2 ?j?1 2? = ||F ||2 ?n L2( ) + |? 2n,k| +T 2 Rn Tnk=1 ( ( )) 1 2 2 2 ? ? ? ? ?+ T 2 + ? 3 . T 2 n 4n Tn Tn Tn IV. Let us now prove that (? ) 1 2 ?p(b p 2 p/2 n,j) ? |t? x(sn,j)| |sn,j(t)| dt + CK ?. (4.32) 47 2/p 2/p Using (4.26),(4.31) and the fact that the b 1n,j are supported in [? T2 n , 2Tn K] (since Fn and sn,j are), we have (? ) 1 2 |t? x(sn pj )| |b (t)|2n,j dt (? ) 1 (? ) 1 2 2 ? |t? x(snj )|p|b 2 n p 2n,j ? sn,j(t)| dt + |t? x(sj )| |sn,j(t)| dt (? ) 1 2 ? |2T 2/pK + 2KT 2/p|p/2||b n n p 2n n n,j ? sj ||L2(R) + |t? x(sj )| |sn,j(t)| dt (? ) 1 2 ? CKp/2Tn||bn,j ? s n p 2n,j||L2(R) + |t? x(sj )| |sn,j(t)| dt (? ) 1 2 ? CKp/2? + |t? x(sn pj )| |s (t)|2n,j dt . Thus, by (4.15) and the definition of x(snj ) we have ?p(bn,j) ? C + CK(p/2)?. (4.33) V. Here we show that (? ) 1 2 ?q(b?n,j) ? |? ? y(s? )|q|s? (?)|2n,j n,j d? + C?K(q/2). i. First we show that (? ) 1 | ? |q| ? 2 ? y(s? 2 (q/2)n,j) F?n(?)| d? ? C?K . (4.34) Tn 48 This follows from (4.23) and (4.26) since ? ? ?q |? ? y(s? )|qn,j |F? (?)|2d? ? c |?|k|y(s? q?k 2n k n,j)| |F?n(?)| d? k=0 ?q ? ? C |y(s?n,j)|q?k |?|k|F?n(?)|2d? k=0 ?q ? C |y(s? )|q?kKkT (2k)/qn,j n k=0 ?q ? C |3KT 2/q|q?kKkT (2k)/qn n k=0 ?q ? C(3K)q T (2?(2k)/q)n T (2k)/qn k=0 = CKqT 2n . ii. Next, we show that (? ) 1 ? 2|? ? y(s? q 2 (q/2)n,j)| |b?n,j(?) ? s?n,j(?) ? F?n(?)| d? ? C?K . Tn Let ?(?) = b?n,j(?) ? s? ?n,j(?) ? F?n(?). Note that ? is in the span of S(TT n, K).n Thus, using (4.26), lemma 4.15,(4.28) and that q ? 2N 49 ? ? |? ? y(s?n,j)|q|?(?)|2d? = (? ? y(s?n,j))q|?(?)|2d? ?? ? ???q? ? ? = ? ck(y(s?n,j)) q?k ?k|?(?)|2d??? k=0 ?q ??? ? ? C3q Kq?kT (2?2k/q) ?? ?k|?(?)|2d?? ? n ? k=0 ?q ? C Kq?kT (2?2k/q)KkT 2k/qn n ||?||2L2(R) k=0 ? CKq||?||2L2( )T 2( R n? ) ? CKq |? 2 2n,l| Tn (l ) 2 ? ?CKqT 2n T 2n T 4n ? CKq?2, and the desired estimate follows. Note that this is the only step where we have made use of q ? 2N (as opposed to q ? N). iii. Combining the estimates from i. and ii. we have 50 (? ) 1 2 ?q(b?n,j) ? |? ? y(s?n,j)|q|b (?)|2n,j d? (? ) 1 2 ? |? ? y(s?n,j)|q|s? 2n,j(?)| d? (? ) 1 2 + |? ? y(s?n,j)|q|b? 2n,j(?) ? s?n,j(?)| d? (? ) 1 (? ) 1 2 2 ? |? ? |q| ?y(s?n,j) s?n,j(?)|2d? + |? ? y(s? q 2n,j)| | F?n(?)| ? Tn (? ) 1 2 + | ?? ? y(s?n,j)|q|b?n,j(?) ? s? (?) ? F? (?)|2n,j n d? Tn (? ) 1 2 ? |? ? y(s? )|q|s? 2 (q/2) (q/2)n,j n,j(?)| d? + ?CK + ?CK (? ) 1 2 = |? ? y(s? )|q|s? (?)|2d? + C?K(q/2)n,j n,j . Thus, ? (b? ) ? C + CK(q/2)q n,j ?. (4.35) ? VI. Having shown that all the elements of B = ?j=1 bn,j have the desired local- ization, it only remains to show that B is complete. To see this, note that 51 ||P 2 2[B1,??? ,B ]fk||L2( ) = ||P[B1,??? ,B ]fk||L2( ) + ||P[B ]fk||2k R k 1 R k L2? (R) = ||P 2 2[B1,??? ,B f || 2 + ||P (F + P f )||k 2?1] k L (R) [Bk] k [B1,??? ,Bk?1] k L (R) = 1 ? ||F ||2k L2( ) + ||P[B ]Fk||2R k L2(R) (?Tk)2 = 1 ? ||F ||2 2k L2( + |?FR) k, bk,j?| j=1 ( )2 = 1 ? || ?F ||2 2 2k L2( ) + (Tk) ||Fk||R L2T (R)k = 1 ? ||Fk||2 2L2( ) + ? ||Fk||4R L2(R) ? ?2, To see the final inequality, let h(t) = 1 ? t2 + a2t4 be defined on [0, 1], where 0 < a < 1 is fixed. It is easy to see that h(t) ? a2. Since ||Fn||L2(R) ? 1 and4 ? < 1 , the last step follows. 4 Now, suppose y ? L2(R) satisfies ?y, b? = 0 for all b ? B. If y is not identically zero, then y? = y/||y|| 2L2(R) is in the unit sphere of L (R) and there exists fn suchk that fn ? y? in L2(R) as k ? ?. Thus,k 0 < ? ? ||P[B1,??? ,Bn ]fn ||L2(R) ? ||P[B]fn ||L2(R) ? ||P[B]y?||L2(R) = 0,k k k where the limit is as k ? ?. This contradiction shows that B is complete and hence is an orthonormal basis. 52 Chapter 5 Orthonormalizing Coherent States The proofs of Bourgain?s theorem and our (p, q) generalization are both rather technical. Both proofs start by constructing finite, orthonormal, well-localized systems of functions in L2(R). Since these systems are not complete, one needs to carefully take linear combinations of these finite systems with a dense set of functions to obtain an orthonormal basis. Question 5.1. Why are the proofs of Bourgain?s theorem and our (p, q) general- ization necessarily so complicated? To answer this, let?s begin by taking another look at Bourgain?s theorem. A naive alternate idea for constructing a basis of the type in Bourgain?s theorem is to start with a complete set of functions which already have the desired uniform localization and to orthonormalize them to obtain a basis. 2 For example, it follows from fact 3.3 that if g(t) = 21/4e??t , then the elements of the Gabor system G(g, 1, 1) all satisfy 1 1 ?(gm,n) = ? and ?(g?m,n) = ? . (5.1) 2 ? 2 ? Moreover, G(g, 1, 1) is complete, but is not a Riesz basis for L2(R), or even a frame for L2(R). This follows (e.g., see [19], [22], [9]) from 53 Theorem 5.2. Let g(t) = 21/4e??t 2 . 1. G(g, a, b) is a frame for L2(R), if ab < 1. 2. G(g, a, b) is incomplete in L2(R), if ab > 1. 3. G(g, a, b) complete in L2(R), but not a frame, if ab = 1. Moreover, G(g, a, b) remains complete if any element is removed, but is no longer complete if two elements are removed. Thus, if one orthonormalizes G(g, 1, 1) with respect to some indexing of Z?Z then one obtains a new system, O(g, 1, 1), which is an orthonormal basis for L2(R). Since all the elements of G(g, 1, 1) satisfy (5.1) it is plausible that the elements of the orthonormalized system also have uniformly bounded time and frequency variances. However, it is difficult to estimate the variances here because G(g, 1, 1) is not a Riesz basis. The difficulties arise specifically because it is difficult to estimate the spectra of the Grammian matrices which arise in the Gram-Schmidt orthogonalization process. Theorem 2.10 sheds light on this. On the other hand, if one chooses ab > 1 then it follows from the Ron-Shen duality theorem that G(g, a, b) is a Riesz basis for its span. By theorem 5.2, G(g, a, b) is incomplete. Thus, if one orthonormalizes G(g, a, b), the resulting system O(g, a, b) is not complete. However, since G(g, a, b) is a Riesz basis for its span, we show it is possible to estimate the variances of the elements of O(g, a, b). In summary, ? O(g, 1, 1) is an orthonormal basis for L2(R), but it is difficult to estimate the time and frequency variances of the elements in O(g, 1, 1). ? If ab > 1 then O(g, a, b) is not complete in L2(R), but one can derive variance estimates. 54 This explains why the proof of Bourgain?s theorem proceeds as it does. Since the idea outlined in the first bullet is difficult to carry out, Bourgain?s proof essentially uses the second idea and adds in completeness by cleverly taking linear combinations with a dense sequence. Note that in Bourgain?s theorem, one doesn?t work with the Gaussian, but instead with a compactly supported function. The compact support makes the orthonormalization easier. In this chapter we shall focus on orthonormalizing G(g, 2, 2), where g is the Gaussian. 5.1 Orthonormalizing coherent states Consider the indexing of 2Z ? 2Z which begins (0, 0), (2, 2), (0, 2), (?2, 2), (?2, 0), (?2,?2), (0,?2), (2,?2), (2, 0), (4, 4), (0, 4), (?4, 4), (?4, 0), (?4,?4), (0,?4), ? ? ? and continues to spiral outwards in this manner. Let O(g, 2, 2) be the system which results when G(g, 2, 2) is orthonormalized in the above order. We examine the time and frequency localization of the elements in O(g, 2, 2). To simplify the exposition, we shall only derive estimates for those elements whose index is of the form (n, n), n ? N. Let ?n,n be the function obtained when gn,n is orthogonalized with respect to the previous elements of G(g, 2, 2), indexed as above, namely, ?n?1 ?n?1 ?n,n(t) = gn,n(t) ? anj,kgj,k(t), (5.2) j=?(n?1) k=?(n?1) where the anj,k are chosen to ensure that ?n,n is orthogonal to {gj,k : ?(n? 1) ? j, k ? (n? 1)}. (5.3) 55 We shall frequently suppress the dependence of anj,k on n and simply write aj,k. Note that by theorems 3.7 and 2.11, the aj,k are unique. To normalize the ?n,n, let ?n,n(t) = ?n,n(t)/||?n,n||L2(R). Thus, ?n,n is the element of O(g, 2, 2) with index (n, n). We shall show Theorem 5.3. For every p > 0 there exists a constant Cp such that ?p(?n,n) ? Cp and ?p(??n,n) ? Cp holds for all n ? N. The main part of the proof is devoted to estimating the {anj,k} in (5.2). This is the content of the next section. 5.2 Estimating the {anj,k} To estimate the {anj,k}, we begin by using (5.3) to take inner products in (5.2). This yields ?n?1 ?n?1 ?g nn,n, gp,q? = aj,k?gj,k, gp,q?, (5.4) j=1?n k=1?n for all (p, q) satisfying ?(n?1) ? p, q ? n?1. The following lemma gives explicit values for the inner products in (5.4). 2 Lemma 5.4. Let h(t) = 21/4e??t . Fix a, b > 0 and let G(h, a, b) = {hm,n}m,n?Z. Then h? = h and ||h||L2(R) = 1 (5.5) and ?hm,n, hk,l? ? ? b2(n?l)2 ?? a2(m?k)2= e e e??iab(n+l)(m?k)2 2 . (5.6) 56 Proof. A standard calculation gives (5.5). To see (5.6) we calculate as follows: ? ?h , h ? = h(t? nb)h(t? lb)e?2?iat(m?k)m,n k,l dt ? ? = 2 e??(t?nb) 2 e??(t?lb) 2 e?2?iat(m?k)dt ? ? = 2 e??(t 2?2nbt+n2b2+t2?2lbt+l2b2)e?2?iat(m?k)dt ? ? = 2e??b 2(n2+l2) e?2?(t 2?b(n+l)t)e?2?iat(m?k)dt ? ? 2 = 2e??b 2(n2+l2) 2?( b (n+l))2 ?2?(t2e e ?b(n+l)t+ b (n+l)2)e?2?iat(m?k)2 4 dt ? ???b2(n2+l2? 1 (n+l)2) ?2?(t? b (n+l))2= 2e e )e?2?iat(m?k)2 2 dt [ ] ? 2 = e? b (n?l) 2 e??iab(n+l)(m?k)F e?2?t22 (a(m? k)) ? ? 2 2 1 ? 2 = 2e? b (n?l) e??iab(n+l)(m?k)? e? a (m?k)22 2 2 = e? ? b2(n?l)2 ? a2e (m?k) 2 2 2 e??iab(n+l)(m?k), where F denotes the Fourier transform. 2 Corollary 5.5. Let g(t) = 21/4e??t and let G(g, 2, 2) = {gm,n}m,n?Z. Then ?g , g ?2?(n?l)2 ?2?(m?k)2m,n k,l? = e e . (5.7) Using this corollary, we see that (5.4) is equivalent to Ga = g, (5.8) where ? ? ? ? ?2?(1)2e v ?2?(1) 2 ?? ?? ? e ? ? ?? ? ? ? e?2?(2) 2 v ? e?2?(2) 2 ? g = ?? ?? ? ? with v = ? ? ?? ? ? ? ?? ? ? ? ? ? ? ? ?? 2 e?2?(2n?1) v e?2?(2n?1) 2 57 and ? ? ? ? ?yn?1? ?aj,n?1?? ? ? ?? ?y? n? ? 2? ?? ? a ?j,n?2? a = ? ?with yj = ? ? ?? ? ? ? ? ? ? ?? ? ? ? ?? ? y1?n aj,1?n and ? ? ? B0 B1 B2 ? ? ? B2n?2? ?? ?? B1 B ?? 0 B1 ? ? ? B2n?3 G = ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? B2n?2 ? ? ? B2 B1 B0 where 2 Bj = e ?2?j C and ? ? 1 e?2?(1) 2 e?2?(3) 2 ? ? ? e?2?(2n?2)2 ?? ?? ??2?(1)2 2 2? e 1 e?2?(1) ? ? ? e?2?(2n?3)? ? ? C ?? ? ? . ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2 2 2 e?2?(2n?2) e?2?(2n?3) e?2?(2n?4) ? ? ? 1 Once again, we have suppressed the fact that all these matrices depend on n. We may use the following result to estimate the spectrum of G. It appears, among other places, in [39]. Theorem 5.6 (Gershgorin Theorem). Let A = (ai,j) be a d? d matrix with complex entries. The spectrum of A satisfies ?d ?d ?(A) ? Ri, Ri = {z ? C : |z ? ai,i| ? |ai,j|}. i=1 j=1,j=6 i We now apply the Gershgorin theorem to our matrix G. Note that ?? ( ) ( )2n 1 ?n 2 ? 2 supi | 2 G | = e?2?ji,j ? 2 1 ? e?2?j ? 1 ? r. j=1,j=6 i j=?n j?Z 58 One may verify that 0 < r < 1, and, in fact, numerically one has that r ? .0075. Thus, ?(G) ? [1 ? r, 1 + r] is bounded away from 0. Note that while G depends on n, this spectrum bound is independent of n. Likewise, if we let R = I ? G, then we have ?(R) ? [?r, r]. This allows us to derive the following block-version of Jaffard?s lemma for our matrix G. Although the proof is essentially the same as Jaffard?s,[32], we nonetheless include it for the sake of completeness. Lemma 5.7. There exist C, ? > 0 independent of n, such that |G?1| ? Ce??|j??k?|e??|J?K|j,k , where j = Jn + j ?, k = Kn + k?, and 0 ? J,K, j ?, k? < n. Recall G is an (2n? 1)2 ? (2n? 1)2 matrix. Proof. Throughout the proof C will denote various constants independent of n. Let R = I ?G. We have ?(R) ? [?r, r], where 0 < r < 1 is as above. Therefore, ? ? 1 (2 ? ? n?1)2 2 |Rm(j, k)| ? |Rm(j, l)|2? = ||Rmej||2 ? ||Rm|| ? rm. (5.9) l=1 Here, ? ? ?2 denotes the l2 norm of a vector and ? ? ? denotes the corresponding matrix norm it induces. Also, {ej} is the canonical basis for l2. By the definitions of G and R we have |R(j, k)| ? ce?|J?K|e?|j??k?|. In particular, ? ? ?0 < ? < 1, |R(j, k)| ? ce??|J?K|e??|j ?k |, 59 so that (2?n?1)2 (2?n?1)2 (2?n?1)2 |Rl(j, k)| ? ? ? ? |R(j,m1)| ? ? ? |R(ml?1,ml)||R(ml, k)| m1=1 ml?1=1 ml=1 2?n?1 2?n?1 2?n?1 2?n?1 2?n?1 2?n?1 ? ? ? ? M =1 m? ?1 1=1 Ml?1=1 ml 1=1 Ml=1 m ? l=1? cle?|J?M ? ? 1|e?|j ?m1| ? ? ? e?|Ml?1?Ml|e?|m?l 1?m?l|e??|K?Ml|e??|k??m?l|? 2?n?1 2?n?1 2?n?1 2?n?1 ? ? ? ? M =1 m? =1 M ?1 1 l?1=1 ml?1=1 c?cle?|J?M1|e?|j ??m?1| ? ? ? ? ?e?|Ml?1?Ml|e?|ml 1?ml|e??|K?Ml?1| ??|k?e ?m?? l |?1 ... ? C le??|J?K|e??|j??k?|. Combining this with (5.9) gives that for all m ? N | ? ?Rm(j, k)| ? min{rm, Cme??|J?K|e??|j ?k |}. (5.10) Take M large enough so that ? ? CrM?1 < 1. By (5.10) ( ) 1 ( ) 1 | ? ? MRm(j, k)| ? (rm)M?1Cme??|J?K|e??|j ?k | = ?me??|J?K| ??|j? ?e ?k | M . ? Using G?1 = ?m=0R m and (5.10), we have ?? |G?1(j, j)| ? m 1r = 1 ? r m=0 and ?? |G?1(j, k)| ? 1 ? ? ?? + (? )ne? |j ?k | ?j,k M M e? |J?K|M ( n=1 ) ?1/M? ?e? |j??k?|e? ? |J?K|M M . 1 ? ?1/M This completes the proof. 60 We shall use lemma 5.7 together with (5.8) and the definition of g to estimate the {anj,k}. The following lemma will be useful. Lemma 5.8. There exist constants C and ?, independent of n, such that 2?n?1 e??|n?j?l| 2 e?2?l ? Ce??|n?j| l=1 holds for all n ? N and ?(n? 1) ? j ? n? 1. Proof. 2?n?1 ? ? e??|n?j?l| ?2?l 2 e ? e??|n?j?l|e?2?l2 + e??|n?j?l| 2e?2?l l=1 1?l? 1 |n?j| l> 1 |n?j| 2 2 ? ? ? ? 1 ?|n?j| ?2?l2e e + e? 1?(n?j)2 e??|n?j?l|2 2 1?l? 1 |n?j| l> 1 |n?j| 2 2 ? ? ? 1e? ?|n?j| e?2?l2 1 2+ e? ?(n?j) e??|n?j?l|2 2 l?Z l?Z ? Ce??|n?j|. The second inequality holds because ? ? 1 | ? | ? | ? ? | 11 l n j = n j l > |n? j|. 2 2 Using lemmas 5.7 and 5.8 we may now estimate the coefficants {anj,k}. Lemma 5.9. There exist constants C, ? > 0 such that the coefficants {anj,k} satisfy |an | ? Ce??|n?j|e??|n?k|j,k . Recall that {anj,k} depends on n. The above constants are independent of n. 61 Proof. Using (5.8), we have a = G?1g. Using lemma 5.7 and the definitions of g and a, we have ?? ??(2?n?1)2 ?? |a ?n?j,n?k| ? ?? G?1(jn+ k, l)g ?l? l=1 ??? ??2?n?1 2?n?1 ? = ? G?1 ? 2 2?? (jn+ k, l ?n+ L)e?2?(l ) e?2?L ?? l?=1 L=1 2?n?1 2?n?1 ? ??|j?l?e |e??|k?L| ?e??|l |e??|L| l?=1 L=1 ? Ce??|j|e??|k| for each ?(n? 1) ? j, k ? n? 1. Thus, |an | ? Ce??|n?j|e??|n?k|j,k . 5.3 Localization estimates First, note that by theorem 5.2 the L2(R) norms of the {?n,n}n?N stay uniformly bounded away from 0. Lemma 5.10. There exists ? > 0 such that ||? 2n,n||L2( ) > ?R holds for all n ? N. Proof. We proceed by contradiction. Suppose there exists a subsequence of {? ?n,n}n=0 satisfying lim ||? 2 ?? nm,nm ||L2( ) = 0.R m 62 By (5.2), n?m?1 n?m?1 gnm,nm ? aj,kgj,k ? 0, in L2(R). j=1?nm k=1?nm We may use the translation and modulation invariance of Gabor systems to con- vert this from a statement about the gnm,nm to a statement about g0,0. In partic- ular, we have that for every  > 0 there exists {cj,k} ? C such that ? ??? ? ? ? ?? ? ?? ?? ????g0,0 ? cj,kgj,k???? < . j<0 k<0 L2(R) This implies that g0,0 ? span {gj,k : j, k < 0}. (5.11) Recall that G(g, 2, 2) is a Riesz basis for its span by theorem 5.2 and the Ron-Shen duality theorem. Therefore, (5.11) is a contradiction by theorem 2.9. We need one final lemma before we can prove theorem 5.3. Lemma 5.11. For every M ? N there exists C = CM > 0 such that ??? ?? ?? ??M?? |t? n|M ? g (t)g (t)dt?? ? Ce? (j?l) 2 ? ? j + l2 ?n ?j,k l,m 2 ? holds for all n ? N and all j, k, l,m ? Z. ? ?? (j?k)2 ?2?[t?( l+k 2Proof. Since gj,0(t)gl,0(t) = 2e e )]2 2 , it suffices to examine ? |t? n|p|gm,0(t)|2dt. Using ?M |t? n|M ? K |t|knM?kM k=0 we have ? ?M ? |t? n|pe?2?t2dt ? K nM?l |t|l ?2?t2M e dt ? C MMn . l=0 63 We are now in position to estimate the localization of the {?n,n}. Theorem 5.12. Fix p ? N. There exists a constant Cp such that ? |t? n|p|?n,n(t)|2dt ? Cp and ? |? ? n|p|??n,n(?)|2d? ? Cp hold for all n ? N. Proof. ? ? | ? |p| |2 1t n ?n,n(t) dt = p|| || |t? n| |? (t)| 2dt ? 2 n,n n,n ? L 2(R) ? ?? ?2 ?n?1 n?1 ? 1 = ? ?? ? ? ?p || || |t? n| ?gn,n(t) ? aj,kgj,k(t) ?? dt?? 2n,n L2(R) ? j=?(n?1) k=?(n?1) ? ? 1 (S1 + S2 + S3) , ? where ? ? S1 = |t? n|p|gn,n(t)|2dt = |t|p|g(t)|2dt, ?n?1 ?n?1 ? S2 = a |t? n|pj,k gj,k(t)gn,n(t)dt j=?(n?1) k=?(n?1) ?n?1 ?n?1 ? + a pj,k |t? n| gj,k(t)gn,n(t)dt, j=?(n?1) k=?(n?1) ?n?1 ?n?1 ?n?1 ?n?1 ? S3 = a p j,kal,m |t? n| gj,k(t)gl,m(t)dt. j=?(n?1) k=?(n?1) l=?(n?1) m=?(n?1) It is clear that S1 is uniformly bounded in n. To see that S2 is bounded indepen- 64 dantly of n we use lemmas 5.9 and 5.11 ?n?1 ?n?1 ( )( ? ?p) | | ? ??|n?j| ??|n?k| ?? (j? 2 ? n) ? ? (n+ j)S 2C e e e 2 ?n ? ? 2 2 ? (j=1?n k=1?n? )(n?1 ?n? )1 ?? ??p = 2C e??|n?k| e??|n?j| ? e? (n?j) 2 2 ?n? j? ? ? 2 ? (j=1 n )(k=1?n? )n?1 ?n?1 ? 2C e??|n?k| e???|n?j| (k=1?n )( j=1?n?? ?? ) ? 2C e??|k| e???|j| . k=1 j=1 Likewise, for S3 we have ?n?1 ?n?1 ? ? |S | ? C e??|j?n|e??|k?n|e??|l?n|e??|m?n| ?? (j? ? l)2 ? ? (j + l) ? 3 e 2 ?n 2 ? ? j,k=1?n l,m=1?n 2?n?1 2?n?1 ?? ?? = C e??|j|e??|k|e??|l|e??|m|e? ? (j?l)2 j + l 2 ?? ??2 j(,k=1 l,m=1?? )( ?? ) ? C e??|j|e??|l||j + l| e??|k|e??|m| . j,l=1 k,m=1 Thus, we see that for any p > 0 there is Cp, independent of n, such that ? |t? n|p|?n,n(t)|2dt < Cp, ?n ? N. For the other inequality, note that g?m,n(?) = e ?2?inb(?+am)g?(? + am) = (g?)n,?m = gn,?m. Therefore, the same calculations as above yield the uniform boundedness of ? |? ? n|p|??n,n(?)|2d?. We conclude the section with the following question. 65 2 Question 5.13. Let g(t) = 21/4e??t . If one orthonormalizes G(g, 1, 1) does there exist a constant C such that the resulting system O(g, 1, 1) = {om,n} is an orthonormal basis for L2(R) which satisfies ?(om,n) ? C and ?(o?m,n) ? C for all m,n ? Z? 66 Chapter 6 Shapiro?s Question We have already seen how means and variances convey information about where a function is ?located? in the time-frequency plane. The Balian-Low theorem and Bourgain?s theorem both address the question of whether or not the sequences of time and frequency variances of an orthonormal basis can be bounded. Re- call that Bourgain?s theorem constructs an orthonormal basis, {b 2n}, for L (R) whose variance sequences, {?2(b 2n)} and {? (b?n)}, are both bounded. On the other hand, the Balian-Low theorem shows that no Gabor orthonormal basis can have both of these variance sequences bounded. A better understanding of how orthonormal bases ?cover? the time-frequency plane requires one also examine the mean sequences. In 1991 H. Shapiro posed the following question, [41] Question 6.1 (Shapiro). Given four sequences of real numbers, {an}, {bn}, {cn}, {dn}, does there exist an orthonormal basis {?n} for L2(R) such that ?(?n) = an, ?(??n) = bn, ? 2(?n) = c 2 n, ? (??n) = dn 67 holds for all n? The following theorem will serve as a starting point for our investigation. Theorem 6.2. There does not exist an infinite orthonormal sequence {fn} ? L2(R) such that all four of the mean and variance sequences are bounded. Shapiro, [41], gives an elegant elementary proof of theorem 6.2 which relies on a compactness result of Kolmogorov. The result also follows from the theory of prolate spheroidal wavefunctions, [35]. We shall discuss prolate spheroidal wavefunctions later. Motivated by theorem 6.2, we consider the following question. Question 6.3. If {?n} is an orthonormal basis for L2(R), how many of the sequences {?(?n)}, {?(??n)}, {?2(? 2n)}, {? (??n)} can be bounded? Which combi- nations of these sequences can be bounded? 6.1 Examples Let us consider some examples. Example 6.4 (Wavelet Basis). Let ? ? L2(R) be such that the wavelet system W(?) = {?m,n} is an orthonormal basis for L2(R). A direct calculation, [4], shows that for wavelet systems the three sequences {?(?m,n)}, {?2(? 2m,n)}, {? (??m,n)} are unbounded. Example 6.5 (Gabor basis). Let g be any function such that the corresponding Gabor system G(g, 1, 1) = {gm,n} is an orthonormal basis for L2(R). A direct 68 computation shows that both {?(gm,n)} and {?(g?m,n)} are unbounded sequences. Moreover, by the Balian-Low theorem, at least one of the two variance sequences, {?2(g 2m,n)} and {? (g?m,n)} must be unbounded (in fact constantly equal to ?). Example 6.6 (Hermite basis). Let {hn} be the Hermite functions defined by ( 21/4 ? )k1 k h (t) = ? ? e?t2 d ?2?t2k (e ). k! 2 ? dtk We follow the notation of [20]. The Hermite functions are eigenfunctions of the Fourier transform, form an orthonormal basis for L2(R), and satisfy ? ? ? 2 ? thk(t) = k + 1hk+1(t) + khk?1(t). (6.1) By taking the inner product of (6.1) with hk and using the orthonormality of the Hermite functions, it follows that ?(hk) = 0 for all k. Since each hn is an eigenfunction of the Fourier transform, we also have ?(h?k) = 0. In particular, both mean sequences are bounded. Using (6.1) again, one can show that ?(hk) = ? ?(h? ) = 2k ? k+1 , so that both variance sequences are unbounded. 2 ? Example 6.7 (Bourgain basis). Let  > 0. In [11], Bourgain constructs an ( )2 orthonormal basis, {fn} for L2(R) satisfying ?2(fn) ? 1 +  and ?2(f?n) ?2? ( ) 1 2+  for all n. However, the mean sequences are both unbounded. 2? Example 6.8 (Wilson Basis). Let g ? L2(R) and define the associated Wilson system, {?l,k}l?0,k?Z, by ?0,k(t) = g(t? k), k = 0 ? ?l,k(t) = 2g(t? k/2)cos(2?lt), l 6= 0, k + l even, ? ?l,k(t) = 2g(t? k/2)sin(2?lt), l 6= 0, k + l odd. 69 See [22] for background on Wilson bases. For any g one can verify that {?(?l,m)} and {?2(??l,k)} are unbounded sequences. For examples of Wilson bases with exponential localization in time and frequency see, [15], [14]. We shall prove two theorems which answer question 6.3. The first shows that theorem 6.2 holds for orthonormal bases even if the hypotheses are weakened to allow one of the mean sequences to be unbounded. Namely, there does not exist an orthonormal basis {f 2n} for L (R) with {?(f?n)}, {?2(fn)} and {?2(f?n)} being bounded sequences. Theorem 6.9. There does not exist an orthonormal basis {fn} for L2(R) such that {?2(fn)}, {?2(f?n)} and {?(f?n)} are all bounded sequences. The second result shows that theorem 6.2 does not hold for orthonormal bases if the hypotheses are weakened to allow one of the variance sequences to be unbounded. Namely, there are orthonormal bases {fn} for L2(R) such that {?2(fn)}, {?(fn)} and {?(f?n)} are bounded sequences. Theorem 6.10. There exists a constant C > 0 such that for any  > 0 there exists an othonormal basis, {fn}, for L2(R) satisfying |?(fn)| ? , |?(f?n)| ?  and ?2(fn) ? C for all n. 6.2 Two variances and one mean In this section we shall prove theorem 6.9. We shall first need some background on the prolate spheroidal wavefunctions. 70 6.2.1 Prolate spheroidal wavefunctions Our brief discussion of prolate spheroidal wavefunctions will follow that of [42], [34], [35]. These papers, written by combinations of Landau, Slepian, and Pollak, are the original and authoritative references on prolate spheroidal wavefunctions. Definition 6.11. Given ? > 0, the Paley Wiener space, PW? is defined by PW? = {f ? L2(R) : supp( f? ) ? [??,?]}. Theorem 6.12 (Slepian, Pollak). Given any T > 0 and ? > 0, there exists a sequence {? }? 2n n=0 ? L (R), called the prolate spheroidal wave functions, and a monotone decreasing sequence of positive numbers, {?n}, such that: 1. The ?n are complete and orthonormal in PW?, 2. The ? 2 T Tn are complete and orthogonal in L ([? , ]) with2 2 ? T 2 ?n(t)?m(t)dt = ?n?(m,n), ?T 2 3. ? T 2 sin(?(t? s)) ?n?n(t) = ?n(s)ds. ?T ?(t? s) 2 Definition 6.13. Given constants , ?,? > 0, we define ? ? S = ST,?,,? = {f ? L2(R) : |f(t)|2dt ? 2 and |f?(?)|2d? ? ?2}. |t|?T |?|?? Landau and Pollak showed that Theorem 6.14 (Landau, Pollak). If f ? ST,?,,? with ?f?L2(R) = 1 then [?2T?] ?f ? a 2 2 2n?n?L2( ) ? 12(+ ?) + ? ,R n=0 71 where the coefficants, an = an(f) are defined by ?? Pf = an?n n=0 and P is the projection onto PW?. The next result follows directly from Landau and Pollak?s result. It is well known, but we include a proof for the sake of completeness. Theorem 6.15. Let S = ST,?,,?. Suppose  and ? are small enough. There exists N ? N such that S contains no orthonormal subset containing more than N elements. Proof. Suppose {fl}Nl=1 ? S is orthonormal, where N is some fixed integer. Let {?n}?n=0 be the prolate spheroidal wavefunctions for [?T, T ] ? [?,?] ? R ? R?. So, by Landau and Pollak?s theorem, for each l = 1, . . . , N there exists {a ?n,l}n=0 such that if fl = Pfl + hl, where P is the projection onto PW?, then ?? Pfl = an,l?n, n=0 ?hl?2L2( ) = ?fl ? Pfl?2 2L2( ) = ? ,R R and [?2T?] ?fl ? a 2n,l?n?L2( ) ? 12(+ ?)2 + ?2.R n=0 First, note that ?? [?2T?] ? an,l?n?L2(R) = ?fl ? hl ? an,l?n?L2(R) n=[2T?]+1 n=0 [?2T?] ? ?fl ? an,l?n?L2(R) + ?hl?L2(R) n=0 ? ? 12(+ ?)2 + ?2 + ?. 72 Since hl ? Pfj for all j and l, it follows from orthonormality that 0 = ?fl, fj? = ?hl, hj? ? + ?n=0 an,lan,j for j 6= l. Thus, ?? ? ? ? 1 ? ? 1?[?2T?] ?? ?? 2 ?? 2?? a a ? ? 2? ?n,l n,j? ? |?hl, hj?| + |an,l| |an,j|2?? n=0 ? n=[2T?]+1 n=[2T?]+1 ? ? ?2 + ( 12(+ ?)2 + ?2 + ?)2 for j 6= l. Next, note that we also have ? ? 1 [?2T?] 2 [2T?] [2T?]? |a |2? ? ? n,l = ? an,l?n?L2(R) ? ?fl?L2(R) ? ?fl ? an,l?n?L2(R) n=0 n=0 n=0 ? ? 1 ? 12(+ ?)2 + ?2. Thus, defining vl = (a0,l, a1,l, . . . , a [2T?]+1 [2T?],l) ? R for l = 1, 2, . . . , N , we have ? 1 ? |vl| ? 1 ? 12(+ ?)2 + ?2 (6.2) and (? )2 |?vl, vj?| ? ?2 + 12(+ ?)2 + ?2 + ? for l =6 j. (6.3) If N is too large, (6.2) and (6.3) yield a contradiction. Recall  and ? are assumed to be sufficiently small. 6.2.2 Preliminary lemmas Lemma 6.16. Suppose g ? L2(R), ||g||L2(R) = 1, satisfies |?(gn)| < A, |?(g?n)| < B ,?(gn) < J ,?(g?n) < K. 2 2 Fix  > 0. For any R > max{J , K2 2 } we have  g ? SA+R,B+R,,. 73 2 Proof. Since R > J 2 , ? ? ? |g(t)|2dt ? |g(t)|2dt ? |g(t)|2dt |t|?A+R |t|??|?(g)|+R |t??(g)|?R2 ? 1 |t? ?(g)|2|g(t)|2dt ? J < 2. R R R Likewise, ? 2 | |2 ? Kg?(?) d? < 2. |t|?B+R R Lemma 6.17. Suppose f, g ? L2(R), ||f ||L2(R) = ||g||L2(R) = 1, and that the means and variances ?(f), ?(f?), ?(g), ?(g?),?2(f),?2(f?),?2(g),?2(g?) are all finite. Then, |? ?| ? ?(f) + ?(f?) + ?(g) + ?(g?)f, g 2 . |?(f) ? ?(g)| + |?(f?) ? ?(g?)| Proof. Let S1 = {t : |t? ?(f)| ? 1 |?(f) ? ?(g)|} 2 and S2 = {t : | 1 t? ?(g)| ? |?(f) ? ?(g)|}. 2 So, 74 ? ? ? |?f, g?| ? |f(t)||g(t)|dt ? |f(t)||g(t)|dt+ |f(t)||g(t)|dt ? S1 S2 ? 2| ? | |t? ?(f)||f(t)||g(t)|dt?(f) ?(g) ? 2 + | ? | |t? ?(g)||f(t)||g(t)|dt?(f) ?(g) ? 2?(f) 2?(g)|?(f) ? ?(g)| + |?(f) ? ?(g)| 2 (?(f) + ?(g)) = | .?(f) ? ?(g)| Likewise, |? ?(f?) + ?(g?)f, g?| = |?f? , g??| ? 2 . |?(f?) ? ?(g?)| Now, combining the previous two inequalities gives |? ?| ? ?(f) + ?(f?) + ?(g) + ?(g?)f, g 2 , |?(f) ? ?(g)| + |?(f?) ? ?(g?)| as desired. 6.2.3 Two variances and one mean: the proof We can now prove theorem 6.9. We restate the theorem here. Theorem 6.18. There does not exist an orthonormal basis {gn} for L2(R) such that {?2(gn)}, {?2(g?n)} and {?(g?n)} are all bounded sequences. Proof. We proceed by contradiction. Suppose such a basis, {gn}n?Z, exists and that |?(g?n)| < B, ?(gn) ? K, ?(g?n) ? K 75 holds for each n ? Z. Let In ? R ? R? be the rectangle [n, n + 1] ? [?B,B]. So, { ?(?(gn), ?(g?n))}n?Z is contained in the disjoint union n? In. By lemma 6.16Z and theorem 6.15 ( ? ) ?N such that ?n, card In {(?(gj), ?(g?j))}j ? N. (6.4) Let f(t) = e?2?it?(g?0)g 2?iMt0(t+?(g0)) and fM(t) = e f(t). So, ?fM?L2(R) = 1 and ?(fM) = 0, ?(f?M) = M, ?(fM) < K, ?(f?M) < K. Let Sn = {j : (?(gj), ?(g?j)) ? In}. Thus, by Parseval?s theorem, lemma 6.17, and (6.4) we have ? ??? ?2 |? ?|2 ? ? 2(4K) ? 1 = fM , g ?n ? |0 ? ?(gn)| + |M ? ?(g? ?n n n)| ? 1 = 64K2 (|?(gn)| + |M ? ?(g? )|)2n n ?? 1 = 64K2 ? (|?(gk)| + |M ? ?(g?k)|) 2 n k Sn ?? ? 1128NK2 (| .n| + |M ?B|)2 n=0 Since the right hand side of this inequality approaches 0 as M ? ?, we have a contradiction. 6.3 Two means and one variance We prove theorem 6.10 in this section. Let us restate the theorem here. Theorem 6.19. There exists a constant C > 0 such that for any  > 0 there exists an orthonormal basis, {fn}, for L2(R) satisfying |?(bj)| ? , |?(b?j)| ? , and ?2(bj) ? C for all j. 76 Proof. We begin by defining a system of functions G(T,N), which we shall need for the proof. I. Let g ? S(R) be a function satisfying ? ||g||L2(R) = 1 and g? ? C?c (R) ? supp g? ? [?1/2, 1/2] ? g is real and even ? ?(g) = ?(g?) = 0 and ?(g) ? ? 0 |?(bj)| + |?(b?j)| +N ? |?(bj) ?N | + |?(b?j) ?N | + 3N ? |?(bj) ?N | + 4|?(b?j) ?N | ? 4|?(bj) ?N | + 4|?(b?j) ?N |. Therefore, ? CK2 ?? C0K 2 j?S (1 + |?(bj) ?N | + |?(b? 2j) ?N |) j?S (1 + |?(bj)| + |?(b?j)| +N)21 1 for some constant C0. By (6.12), the left side of this inequality goes to 0 as N ? ?. Combining this with a similar estimate for the sum over S2 shows that the right side of (6.13) goes to 0 as N ? ?. Thus, we have a contradiction. 83 BIBLIOGRAPHY [1] Roger Balian, Un principe d?incertitude fort en the?orie du signal ou en me?canique quantique, C. R. Acad. Sci. Paris Se?r. II Me?c. Phys. Chim. Sci. Univers Sci. Terre 292 (1981), no. 20, 1357?1362. MR 83a:94009 [2] Guy Battle, Heisenberg proof of the Balian-Low theorem, Lett. Math. Phys. 15 (1988), no. 2, 175?177. MR 89i:81057 [3] , Phase space localization theorem for ondelettes, J. Math. Phys. 30 (1989), no. 10, 2195?2196. MR 91a:81140 [4] John J. Benedetto, Frame decompositions, sampling, and uncertainty princi- ple inequalities, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 247?304. MR 94i:94005 [5] , Harmonic analysis and applications, Studies in Advanced Mathe- matics, CRC Press, Boca Raton, FL, 1997. MR 97m:42001 [6] John J. Benedetto, Wojtek Czaja, Przemyslaw Gadzin?ski, and Alexander Powell, The Balian-Low and regularity of Gabor systems, Journal of Geo- metric Analysis. (To appear). 84 [7] John J. Benedetto, Wojtek Czaja, and Andrei Maltsev, The Balian-Low theorem for the symplectic form on R2d, Journal of Mathematical Physics (To appear). [8] John J. Benedetto, Christopher Heil, and David F. Walnut, Differentiation and the Balian-Low theorem, J. Fourier Anal. Appl. 1 (1995), no. 4, 355?402. MR 96f:42002 [9] John J. Benedetto and David F. Walnut, Gabor frames for L2 and related spaces, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 97?162. MR 94i:42040 [10] Michael Benedicks, On Fourier transforms of functions supported on sets of finite Lebesgue measure, J. Math. Anal. Appl. 106 (1985), no. 1, 180?183. MR 86f:43006 [11] J. Bourgain, A remark on the uncertainty principle for Hilbertian basis, J. Funct. Anal. 79 (1988), no. 1, 136?143. MR 89f:81025 [12] Ole Christensen, Baiqiao Deng, and Christopher Heil, Density of Ga- bor frames, Appl. Comput. Harmon. Anal. 7 (1999), no. 3, 292?304. MR 2000j:42043 [13] Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Confer- ence Series in Applied Mathematics, vol. 61, Society for Industrial and Ap- plied Mathematics (SIAM), Philadelphia, PA, 1992. MR 93e:42045 [14] Ingrid Daubechies, Ste?phane Jaffard, and Jean-Lin Journe?, Erratum: ?A simple Wilson orthonormal basis with exponential decay?, SIAM J. Math. Anal. 22 (1991), no. 3, 878. MR 92a:81066b 85 [15] , A simple Wilson orthonormal basis with exponential decay, SIAM J. Math. Anal. 22 (1991), no. 2, 554?573. MR 92a:81066a [16] H. Dym and H. P. McKean, Fourier series and integrals, Academic Press, New York, 1972, Probability and Mathematical Statistics, No. 14. MR 56 #945 [17] Jacek Dziuban?ski and Eugenio Herna?ndez, Band-limited wavelets with subex- ponential decay, Canad. Math. Bull. 41 (1998), no. 4, 398?403. MR 2000a:42052 [18] Hans G. Feichtinger and Karlheinz Gro?chenig, Gabor frames and time- frequency analysis of distributions, J. Funct. Anal. 146 (1997), no. 2, 464? 495. MR 98k:42041 [19] Gerald B. Folland, Harmonic analysis in phase space, Annals of Mathemat- ics Studies, vol. 122, Princeton University Press, Princeton, NJ, 1989. MR 92k:22017 [20] Gerald B. Folland and Alladi Sitaram, The uncertainty principle: a mathe- matical survey, J. Fourier Anal. Appl. 3 (1997), no. 3, 207?238. MR 98f:42006 [21] Karlheinz Gro?chenig, An uncertainty principle related to the Poisson sum- mation formula, Studia Math. 121 (1996), no. 1, 87?104. MR 98a:42007 [22] , Foundations of time-frequency analysis, Applied and Numeri- cal Harmonic Analysis, Birkha?user Boston Inc., Boston, MA, 2001. MR 2002h:42001 86 [23] Karlheinz Gro?chenig, Deguang Han, Christopher Heil, and Gitta Kutyniok, The Balian-Low theorem for symplectic lattices in higher dimensions, Appl. Comput. Harmon. Anal. 13 (2002), no. 2, 169?176. MR 1 942 751 [24] Karlheinz Gro?chenig and Georg Zimmermann, Hardy?s theorem and the short-time Fourier transform of Schwartz functions, J. London Math. Soc. (2) 63 (2001), no. 1, 205?214. MR 2001k:46065 [25] G. H. Hardy, A theorem concerning Fourier transforms, Journal London Math. Soc. 8 (1933), 227?231. [26] G. H. Hardy, J. E. Littlewood, and G. Po?lya, Inequalities, Cambridge Math- ematical Library, Cambridge University Press, Cambridge, 1988, Reprint of the 1952 edition. MR 89d:26016 [27] Victor Havin and Burglind Jo?ricke, The uncertainty principle in harmonic analysis, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 28, Springer-Verlag, Berlin, 1994. MR 96c:42001 [28] Christopher Heil, Jayakumar Ramanathan, and Pankaj Topiwala, Linear in- dependence of time-frequency translates, Proc. Amer. Math. Soc. 124 (1996), no. 9, 2787?2795. MR 96k:42039 [29] J. A. Hogan and J. D. Lakey, Rotations in Fourier uniqueness and localiza- tion criteria, Preprint (2002). [30] Lars Ho?rmander, The analysis of linear partial differential operators. I, sec- ond ed., Springer Study Edition, Springer-Verlag, Berlin, 1990, Distribution theory and Fourier analysis. MR 91m:35001b 87 [31] A. E. Ingham, A note on Fourier transforms, Journal London Math. Soc. 9 (1934), 29?32. [32] S. Jaffard, Proprie?te?s des matrices ?bien localise?es? pre?s de leur diagonale et quelques applications, Ann. Inst. H. Poincare? Anal. Non Line?aire 7 (1990), no. 5, 461?476. MR 93h:47035 [33] Yitzhak Katznelson, An introduction to harmonic analysis, corrected ed., Dover Publications Inc., New York, 1976. MR 54 #10976 [34] H. J. Landau and H. O. Pollak, Prolate spheroidal wave functions, Fourier analysis and uncertainty. II, Bell System Tech. J. 40 (1961), 65?84. MR 25 #4147 [35] , Prolate spheroidal wave functions, Fourier analysis and uncertainty. III. The dimension of the space of essentially time- and band-limited signals., Bell System Tech. J. 41 (1962), 1295?1336. MR 26 #5200 [36] Peter A. Linnell, von Neumann algebras and linear independence of trans- lates, Proc. Amer. Math. Soc. 127 (1999), no. 11, 3269?3277. MR 2000b:46106 [37] F. Low, Complete sets of wave packets, in A Passion for Physics - Essays in Honor of Geoffrey Chew, World Scientific, Singapore, 1985, pp. 17?22. [38] G. W. Morgan, A note on Fourier transforms, Journal London Math. Soc. 9 (1934), 187?192. [39] Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri, Numerical mathemat- ics, Texts in Applied Mathematics, vol. 37, Springer-Verlag, New York, 2000. MR 2000m:65001 88 [40] Walter Rudin, New constructions of functions holomorphic in the unit ball of Cn, CBMS Regional Conference Series in Mathematics, vol. 63, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1986. MR 87f:32013 [41] Harold S. Shapiro, Uncertainty principles for bases in L2(R), unpublished manuscript (1991). [42] D. Slepian and H. O. Pollak, Prolate spheroidal wave functions, Fourier analysis and uncertainty. I, Bell System Tech. J. 40 (1961), 43?63. MR 25 #4146 [43] Thomas Strohmer, Four short stories about Toeplitz matrix calculations, Lin- ear Algebra Appl. 343/344 (2002), 321?344, Special issue on structured and infinite systems of linear equations. MR 2002k:47060 89