Topics in Fourier Analysis Part III, Autumn 2005

T. W. Körner May 23, 2006

Small print This is just a first draft for the course. The content of the course will be what I say, not what these notes say. (I may change my mind on the contents of the last part of the course.) Experience shows that skeleton notes (at least when I write them) are very error prone, so use these notes with care. I should very much appreciate being told of any corrections or possible improvements. My e-mail address is twk@dpmms. These notes are written in L^{A}TEX 2ε and should be available in tex, ps, pdf and dvi format from my home page

http://www.dpmms.cam.ac.uk/˜ twk/

Contents

1 Some notes of explanation 2 2 Radars and suchlike 2 3 Fourier series on the circle 4 4 A Theorem of Kahane and Katznelson 10 5 Many Dimensions 12 6 Some simple geometry of numbers 16 7 A preliminary look at Fourier transforms 20 8 The Fourier transform and Heisenberg’s inequality 24 9 The Poisson formula 27 10 Fourier analysis on finite Abelian groups 30 11 Poisson and finite Abelian groups 33

12 The fast Fourier transform and some applications 35

13 The Radon transform 36

14 References and further reading 38

1 Some notes of explanation

Since the birth of the Lebesgue integral it has been clear that it is a much more powerful tool for studying Fourier analysis than the Riemann integral. However I shall try to make the course accessible to (and examinable for) those who have not done measure theory (though they may have to take the statement of certain results on trust). If either those who know Lebesgue integration or those who do not feel that this leads to any problems, they should raise them with me.

2 Radars and suchlike

This first section may also appear most opaque. However, it touches on themes which will reappear throughout the course and, in particular, in Section 8 when we discuss Heisenberg’s inequality.

We work in the (x, y) plane. Consider an array of 2N + 1 radio transmitters broadcasting at frequency ω. Let the kth transmitter be at (0, kl) [k = −N, −N + 1, …, 0, 1, …, N]. It is reasonable to take the signal at (x, y) due to the kth transmitter to be

A_{k}r_{k}^{−2} exp(i(ωt − λ^{−1}r_{k} − ϕ_{k}))

where λ is the wavelength (thus ωλ = c the speed of light) and r_{k}^{2} = x^{2} + (y − kl)^{2}. The total signal at (x, y) is

S(x, y, t) = ∑_{k=−N}^{N} A_{k}r_{k}^{−2} exp(i(ωt − λ^{−1}r_{k} − ϕ_{k})).

Lemma 2.1 If x = R cos θ, y = R sin θ where R is very large then, to a very good approximation,

S(R cos θ, R sin θ, t) = R^{−2} exp(i(ωt − λR)Q(u)

where

Q(u) = ∑_{k=−N}^{N} A_{k} exp(i(ku − ϕ_{k})),

and u = λ^{−1}l sin θ.

In the discussion that follows we use the notation of Lemma 2.1 and the discussion that preceded it. We set

P (u) = ∑_{k=−N}^{N} A_{k} exp(iku),

that is P = Q with ϕ_{k} = 0 for all k. Since we could take the A_{k} to be complex, there was no real increase in generality in allowing ϕ_{k} ≠ 0, but I wished to make the following points.

Lemma 2.2 (i) Given θ_{0} we can find ϕ_{k} such that

Q(u) = P (u − u_{0}).

(ii) S(−x, −y, t) = S(x, y, t).

(iii) If l > λπ/2 then there exist 0 < θ_{1} < π/2 such that

S(R cos θ_{1}, R sin θ_{1}, t) = S(0, R, t).

Bearing in mind that the equations governing the reception of signal at (x, y) transmitted from our array are essentially the same as those governing the reception of signal at our array, Lemma 2.2 (i) talks about electronic stearability of radar beams, and Lemma 2.2 (ii) and (iii) deal with ambiguity. It is worth noting that in practice the signal received by a radar corresponds to |Q(u)|.

Let us look at P (u) in two interesting cases.

Lemma 2.3 (i) If A_{k} = (2N + 1)^{−1} then, writing P_{N}(u) = P (u),

P_{N}(u) = \frac{1}{2N + 1} \frac{sin((N + \frac{1}{2})u)}{sin(\frac{1}{2}u)}.

(ii) With the notation of (i)

P_{N}(av/N) → \frac{sin av}{2av}

as N → ∞.

Lemma 2.3 is usually interpreted as saying that a radar cannot discriminate between two targets if their angular distance is of the order of the size of λ/a where λ is the wave length used and a is the length of the array. It is natural to ask if a cleverer choice of A_{k} might enable us to avoid this problem. We shall see that the choice in Lemma 2.3 may not be the best there is no way of avoiding the λ/a rule.

3 Fourier series on the circle

We work on the circle 𝕋 = ℝ/2πℤ (that is on the interval [0, 2π] with the two ends 0 and 2π identified). If f : 𝕋 → ℂ is integrable^{1}, we write

f̂(n) = \frac{1}{2π} ∫_{𝕋} f(t) exp −int dt.

We shall see (Lemma 3.11) that f is uniquely determined by its Fourier coefficients f̂(n). Indeed it is clear that there is a ‘natural identification’ (where natural is deliberately used in a vague sense)

f(t) ∼ ∑_{r=−∞}^{∞} f̂(r) exp irt.

However we shall also see that, even when f is continuous, ∑_{r=−∞}^{∞} f̂(r) exp irt may fail to converge at some points t.

Fejér discovered that, although

S_{n}(f, t) = ∑_{r=−n}^{n} f̂(r) exp irt

may behave badly as n → ∞, the average

σ_{n}(f, t) = (n + 1)^{−1} ∑_{m=0}^{n} S_{m}(f, t) = ∑_{r=−n}^{n} \frac{n + 1 − |r|}{n + 1}f̂(r) exp irt

behaves much better. (We call σ_{n}(f, t) the Fejér sum. We also write S_{n}(f, t) = S_{n}(f)(t) and σ_{n}(f, t) = σ_{n}(f)(t).)

Exercise 3.1 Let a_{1}, a_{2}, … be a sequence of complex numbers.

1That is Lebesgue integrable or Riemann integrable according to the reader’s background.

(i) Show that, if a_{n} → a then

\frac{a_{1} + a_{2} + ⋯ + a_{n}}{n} → a

as n → ∞.

(ii) By taking an appropriate sequence of 0s and 1s or otherwise find a sequence a_{n} such that a_{n} does not tend to a limit as n → ∞ but (a_{1} + a_{2} + ⋯ + a_{n})/n does.

(iii) By taking an appropriate sequence of 0s and 1s or otherwise find a bounded sequence a_{n} such that (a_{1} + a_{2} + ⋯ + a_{n})/n does not tend to a limit as n → ∞.

Lemma 3.2 If f is integrable, we have

S(f) = f ∗ D_{n},
σ(f) = f ∗ K_{n}

where

D_{n}(f, t) = \frac{sin((n + \frac{1}{2})t)}{sin(\frac{1}{2}t)},

K_{n}(f, t) = \frac{1}{n + 1} (\frac{sin(\frac{n+1}{2}t)}{sin(\frac{1}{2}t)})^{2}

for t ≠ 0.

The key differences between the Dirichlet kernel D_{n} and the Fejér kernel K_{n} are illustrated by the next two lemmas.

Lemma 3.3 (i) ∫_{𝕋} D_{n}(t) dt = 1.

(ii) If t ≠ π then D_{n}(t) does not tend to a limit as n → ∞.

(iii) There is a constant A > 0 such that ∫_{𝕋} |D_{n}(t)| dt ≥ A log n for n ≥ 1.

Lemma 3.4 (i) \frac{1}{2π} ∫_{𝕋} K_{n}(t) dt = 1.

(ii) If η > 0 then K_{n} → 0 uniformly for |t| ≥ η as n → ∞.

(iii) K_{n}(t) ≥ 0 for all t.

The properties set out in Lemma 3.4 show why Fejér sums work so well. It is worth reflecting briefly on how we might use these ideas to shape radar beams in the manner of Section 1. Note however that we do not much improve angular discrimination.

Exercise 3.5 Justify the last sentence. Theorem 3.6 (i) If f : 𝕋 → 𝕋 is integrable and f is continuous at t then

σ_{n}(f, t) → f(t)

as n → ∞.

(ii) If f : 𝕋 → 𝕋 is continuous then

σ_{n}(f) → f

uniformly as n → ∞.

Exercise 3.7 Suppose that L_{n} : 𝕋 → ℝ is continuous (if you know Lebesgue theory you merely need integrable) and

(A) \frac{1}{2π} ∫_{𝕋} L_{n}(t) dt = 1,

(B) If η > 0 then L_{n} → 0 uniformly for |t| ≥ η as n → ∞,

(C) L_{n}(t) ≥ 0 for all t.

(i) Show that if f : 𝕋 → ℝ is integrable and f is continuous at t then

L_{n} ∗ f(t) → f(t)

as n → ∞.

(ii) Show that, if f : 𝕋 → ℂ is continuous, then

L_{n} ∗ f → f

uniformly as n → ∞.

(iii) Show that condition (C) can be replaced by

(C’) There exists a constant A > 0 such that

∫_{𝕋} |L_{n}(t)| dt ≤ A

in parts (i) and (ii). [You need only give the proof in one case and say that the other is ‘similar’.]

Exercise 3.8 Suppose that L_{n} : 𝕋 → ℝ is continuous but that

sup_{n} ∫_{𝕋} |L_{n}(t)| dt = ∞.

Show that we can find a sequence of continuous functions g_{n} : 𝕋 → ℝ with |f_{n}(t)| ≤ 1 for all t, L_{n} ∗ g_{n}(0) ≥ 0 for all n and

sup_{n} L_{n} ∗ g_{n}(0) = ∞.

(i) If you know some functional analysis deduce the existence of a continuous function f such that

sup_{n} L_{n} ∗ f(0) = ∞.

(ii) Even if you can obtain the result of (i) by slick functional analysis there is some point in obtaining the result directly.

(a) Suppose that we have defined positive integers n(1) < n(2) < ⋯ < n(k), a continuous function g_{k} and a real number ϵ(k) with 2^{−k} > ϵ(k) > 0. Show that there is an ϵ(k + 1) with ϵ(k)/2 > ϵ(k + 1) > 0 such that whenever g is a continuous function with ∥g − g_{k}∥_{∞} < 2ϵ(k + 1) we have |L_{n(j)} ∗ g − L_{n(j)} ∗ g_{k}(0)| ≤ 1. for 1 ≤ j ≤ k.

(b) If sup |L_{m}∗g_{k}(0)| = ∞ we have proved our theorem, so we may suppose |L_{m} ∗ g_{k}(0)| ≤ A_{k} for some A_{k} and all m. Continuing with the notation of (a), show that there exists an n(k +1) > n(k) and a continuous function g_{k+1} with ∥g_{k+1} − g_{k}∥_{∞} ≤ ϵ(k + 1) such that |L_{n(k+1)} ∗ g_{k+1}(0)| > 2^{k+1}.

(c) By carrying out the appropriate induction and considering the uniform limit of g_{k} obtain (i).

(iii) Show that there exists a continuous function f such that S_{n}(f, 0) fails to converge as n → ∞. (We shall obtain a stronger result later in Theorem 4.2.)

Theorem 3.6 has several very useful consequences.

Theorem 3.9 (Density of trigonometric polynomials) The trigonometric polynomials are uniformly dense in the continuous functions on 𝕋.

Lemma 3.10 (Riemann-Lebesgue lemma) If f is an integrable function on 𝕋, then f̂(n) → 0 as |n| → ∞.

Theorem 3.11 (Uniqueness) If f and g are integrable functions on 𝕋 with f̂(n) = ĝ(n) for all n, then f = g.

Lemma 3.12 If f is an integrable function on 𝕋 and ∑_{j} |f̂(j)| converges, then f is continuous and f(t) = ∑_{j} f̂(j) exp ijt.

As a preliminary to the next couple of results we need the following temporary lemma (which will be immediately superseded by Theorem 3.15).

Lemma 3.13 (Bessel’s inequality) If f is a continuous function on 𝕋, then

∑_{n=−∞}^{∞} |f̂(n)|^{2} ≤ \frac{1}{2π} ∫_{𝕋} |f(t)|^{2} dt.

Theorem 3.14 (Mean square convergence) If f is a continuous function on 𝕋, then

\frac{1}{2π} ∫_{𝕋} |f(t) − S_{n}(f, t)|^{2} dt → 0

as n → ∞.

Theorem 3.15 (Parseval’s Theorem) If f is a continuous function on 𝕋, then

∑_{n=−∞}^{∞} |f̂(n)|^{2} = \frac{1}{2π} ∫_{𝕋} |f(t)|^{2} dt.

More generally, if f and g are continuous,

∑_{n=−∞}^{∞} f̂(n)ĝ(n)^{∗} = \frac{1}{2π} ∫_{𝕋} f(t)g(t)^{∗} dt.

(The extension to all L^{2} functions of Theorems 3.14 and 3.15 uses easy measure theory.)

Exercise 3.16 If you use Lebesgue integration state and prove Theorems 3.14 and 3.15 for (L^{2}(𝕋), ∥ ∥_{2}).

If you use Riemann integration extend and prove Theorems 3.14 and 3.15 for all Riemann integrable function.

Note the following complement to the Riemann-Lebesgue lemma.

Lemma 3.17 If κ(n) → ∞ as n → ∞, then we can find a continuous function f such that lim sup_{n→∞} κ(n)f̂(n) = ∞.

The proof of the next result is perhaps more interesting than the result itself.

Lemma 3.18 Suppose that f is an integrable function on 𝕋 such that there exists an A with |f̂(n)| ≤ A|n|^{−1} for all n ≠ 0. If f is continuous at t, then S_{n}(f, t) → f(t) as n → ∞.

Exercise 3.19 Suppose that a_{n} ∈ ℂ and there exists an A with

|a_{n+1} − a_{n}| ≤ A|n|^{−1} for all n ≥ 1.

Show that if

\frac{a_{1} + a_{2} + ⋯ + a_{n}}{n} → a

as n → ∞, then a_{n} → a as n → ∞. (Results like this are called Tauberian theorems.)

Exercise 3.20 (i) Suppose that f : [−π, π) → ℝ is increasing and bounded. Write f(π) = lim_{t→0} f(π − t). Show that

∫_{−π}^{π} f(t) exp it dt = ∫_{0}^{π}(f(t) − f(t − π)) exp it dt

and deduce that |f̂(1)| ≤ (f(π) − f(−π))/2 ≤ (f(π) − f(−π)).

(ii) Under the assumptions of (i) show that

|f̂(n)| ≤ (f(π) − f(−π))/|n|

for all n ≠ 0.

(iii) (Dirichlet’s theorem) Suppose that g = f_{1}−f_{2} where f_{k} : [−π, π) → ℝ is increasing and bounded [k = 1, 2]. (It can be shown that functions g of this form are the so called functions of bounded variation.) Show that, if g is continuous at t, then S_{n}(g, t) → f(t) as n → ∞.

Most readers will already be aware of the next fact.

Lemma 3.21 If f : 𝕋 → ℂ is continuously differentiable, then

(f′)ˆ (n) = inf̂(n).

This means that Lemma 3.18 applies, but we can do better.

Lemma 3.22 If f : 𝕋 → ℂ is continuously differentiable, then

∑_{n=−∞}^{∞} |f̂(n)| < ∞.

Here is a beautiful application due to Weyl of Theorem 3.9. If x is real let us write ⟨x⟩ for the fractional part of x, that is, let us write

⟨x⟩ = x − [x].

Theorem 3.23 If α is an irrational number and 0 ≤ a ≤ b ≤ 1, then

\frac{card\{1 ≤ n ≤ N | ⟨nα⟩ ∈ [a, b]\}}{N} → b − a

as N → ∞. The result is false if α is rational.

(Of course this result may be deduced from the ergodic theorem and Theorem 3.9 itself can be deduced from the Stone-Weierstrass theorem but the techniques used can be extended in directions not covered by the more general theorems.)

Exercise 3.24 (i) Suppose that

τ = \frac{1 + \sqrt{5}}{2}and σ = \frac{1 − \sqrt{5}}{2}.

Show that, if u_{n} = τ^{n} + σ^{n}, then u_{0}, u_{1} ∈ ℤ and

u_{n+1} = u_{n} + u_{n−1}

for all n. Conclude that u_{n} ∈ ℤ for all ℤ. Explain why σ^{n} → 0 as n → ∞ and conclude that, in general,

\frac{card\{1 ≤ n ≤ N | ⟨τ^{n}⟩ ∈ [a, b]\}}{N} ↛ b − a

as N → ∞.

(ii) (This just an aside unrelated to the course.) Use the ideas of (i) to show that, if F_{n} is the nth Fibonacci number^{2}, then F_{n} is the nearest integer to

\frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n}

for all n ≥ 0.

Hurwitz used Parseval’s theorem in a neat proof of the isoperimetric inequality.

Theorem 3.25 Among all smooth closed non-self-intersecting curves of given length the one which encloses greatest area is the circle.

(Reasonably simple arguments show that requirement of smoothness can be dropped.)

4 A Theorem of Kahane and Katznelson

We need to recall (or learn) the following definition.

Definition 4.1 A subset E of 𝕋 has (Lebesgue) measure zero if, given ϵ > 0 we can find intervals I_{j} of length |I_{j}| such that ⋃_{j=1}^{∞} I_{j} ⊇ E but ∑_{j=1}^{∞} |I_{j}| < ϵ.

2Recall F_{0} = 0, F_{1} = 1, F_{n+1} = F_{n} + F_{n−1}.

There is a deep and difficult theorem of Carleson which tells us that if f : 𝕋 → ℂ is continuous (or even L^{2}), then the set

E = {t ∈ 𝕋 | S_{n}(f, t) ↛ f(t) as n → ∞}

has measure 0. (We shall neither prove nor make use of this result which is included for information only.) Kahane and Katznelson proved a converse which though much easier to prove is still remarkable. Theorem 4.2 (Kahane and Katznelson) Given any subset E of 𝕋 with measure zero we can find a continuous function f such that

lim sup_{n→∞} |S_{n}(f, t)| → ∞

for all t ∈ E.

The theorem follows relatively simply from its ‘finite version’.

Lemma 4.3 Given any K > 0 we can find a δ(K) > 0 such that if J_{1}, J_{2}, … J_{N} is any finite collection of intervals with ∑_{r=1}^{N} |J_{r}| < δ(K) we can find a trigonometric polynomial P such that ∥P ∥_{∞} ≤ 1 but

sup_{n} |S_{n}(P, t)| ≥ K

for all t ∈ ⋃_{r=1}^{N} J_{r}.

It is the proof of Lemma 4.3 which contains the key idea. This is given in the next lemma.

Lemma 4.4 Let us define log z on ℂ \ {x ∈ ℝ | x ≤ 0} so that log x is real when x is real and positive. Suppose that 1 > δ > 0 and that θ_{1}, θ_{2}, …, θ_{N} ∈ ℝ. If we set

ϕ(z) = log (N^{−1} ∑_{n=1}^{N} \frac{1 + δ}{1 + δ − ze^{−iθ_{n}}} )

then ϕ is a well defined analytic function on {z | |z| < 1 + δ/2} such that (i) |ℑϕ(z)| < π for all |z| < 1 + δ/2, (ii) ϕ(0) = 0, (iii) |ℜϕ(e^{iθ})| ≥ log(δ^{−1}/4N) for all |θ − θ_{n}| ≤ δ/2 and 1 ≤ n ≤ N.

5 Many Dimensions

The extension of these ideas to higher dimensions can be either trivial or very hard. If f : 𝕋^{m} → ℂ, we define

f̂(n) = ∫_{𝕋} … ∫_{𝕋} f(t) exp(−in.t) dt_{1} … dt_{m}.

Very little is known about the convergence of

∑_{u^{2}+v^{2}≤N} f̂(u, v) exp(i(ux + vy))

as N → ∞, even when f is continuous. (Of course, under stronger conditions, such as those in Exercise 5.7 below the matter becomes much easier.)

However the treatment of the sums of type

∑_{|u|,|v|≤N} f̂(u, v) exp(i(ux + vy))

is a straightforward. The following results are part of the course but will be left as exercises. (Of course, if you have trouble with them you can ask the lecturer to do them.)

Lemma 5.1 If we define K̃ : 𝕋^{m} → ℝ by K̃(t_{1}, t_{2}, …, t_{m}) = ∏_{j=1}^{m} K(t_{j}) then we have the following results.

(i) \frac{1}{(2π)^{m}} ∫_{𝕋^{m}} K̃_{n}(t) dt = 1.

(ii) If η > 0, then ∫_{|t|≥η} K̃_{n}(t) dt → 0 as n → ∞.

(iii) K̃_{n}(t) ≥ 0 for all t.

(iv) K̃_{n} is a (multidimensional) trigonometric polynomial.

Lemma 5.2 If f : 𝕋^{m} → ℂ is integrable and P : 𝕋^{m} → ℂ is a trigonometric polynomial, then

P ∗ f(x) = \frac{1}{(2π)^{m}} ∫_{𝕋^{m}} P (x − t)f(t) dt

is a trigonometric polynomial in x.

Theorem 5.3 (Density of trigonometric polynomials) The trigonometric polynomials are uniformly dense in the continuous functions on 𝕋^{m}.

Lemma 5.4 (Riemann-Lebesgue lemma) If f is an integrable function on 𝕋^{m}, then f̂(n) → 0 as |n| → ∞.

Theorem 5.5 (Uniqueness) If f and g are integrable functions on 𝕋^{m} with f̂(n) = ĝ(n) for all n, then f = g.

Lemma 5.6 If f is an integrable function on 𝕋 and ∑_{j} |f̂(j)| converges then f is continuous and f(t) = ∑_{j} f̂(j) exp ij.t.

Exercise 5.7 Suppose that f : 𝕋^{m} → ℂ is integrable and ∑_{(u,v)∈ℤ^{2}} |f̂(u, v)| < ∞. Show that

∑_{u^{2}+v^{2}≤N} f̂(u, v) exp(i(ux + vy)) → f(x, y)

uniformly as N → ∞.

Theorem 5.8 (Parseval’s Theorem) If f is a continuous function on 𝕋^{m}, then

∑_{n∈ℤ^{m}} |f̂(n)|^{2} = \frac{1}{(2π)^{m}} ∫_{𝕋^{m}} |f(t)|^{2} dt.

More generally, if f and g are continuous,

∑_{n∈ℤ^{m}} f̂(n)ĝ(n)^{∗} = \frac{1}{(2π)^{m}} ∫_{𝕋^{m}} f(t)g(t)^{∗} dt.

Exercise 5.9 Prove the results from Lemma 5.1 to Theorem 5.8

Exercise 5.10 The extension of Lemma 3.18 to many dimensions is not required for the course but makes a nice exercise. The proof follows the one dimensional proof but is not quite word for word.

(i) Suppose that f is a bounded integrable function on 𝕋^{2} such that there exists an A with |f̂(u, v)| ≤ A(u^{2} + v^{2})^{−1} for all (u, v) ≠ (0, 0). Show that, if f is continuous at (s, t),, then

∑_{|u|,|v|≤n} f̂(u, v) exp(i(us + vt)) → f(s, t)

(ii) (This generalises Lemma 3.22.) Suppose that f is an twice differen-

tiable function on 𝕋^{2} with \frac{∂^{2}f(x, y)}{∂x∂y} continuous. Show that ∑_{(u,v)∈ℤ^{2}} |f̂(u, v)| < ∞.

(iii) State the correct generalisations of parts (i) and (ii) to higher dimensions.

We immediately obtain a striking generalisation of Weyl’s theorem (Theorem 3.23).

Theorem 5.11 Suppose that α_{1}, α_{2}, …, α_{M} are real numbers. A necessary and sufficient condition that

\frac{card\{1 ≤ n ≤ N | (⟨nα_{1}⟩, ⟨nα_{2}⟩, …, ⟨nα_{M}⟩ ∈ ∏_{j=1}^{M}[a_{j}, b_{j}]\}}{N} → ∏_{j=1}^{M}(b_{j} − a_{j})

as N → ∞ whenever 0 ≤ a_{j} ≤ b_{j} ≤ 1 is that

∑_{j=1}^{M} n_{j}α_{j} ∉ ℤ for integer n_{j} not all zero.  ⋆

If α_{1}, α_{2}, …, α_{M} satisfy ⋆ we say that they are independent. The multidimensional version of Weyl’s theorem has an important corollary.

Theorem 5.12 (Kronecker’s theorem) Suppose that α_{1}, α_{2}, …, α_{M} are independent real numbers. Then given real numbers β_{1}, β_{2}, …, β_{M} and ϵ > 0 we can find integers N, m_{1}, m_{2}, …, m_{M} such that

|Nα_{j} − β_{j} − m_{j}| < ϵ

for each 1 ≤ j ≤ M.

The result is false if α_{1}, α_{2}, …, α_{M} are not independent.

We use this to obtain a theorem of Kolmogorov.

Theorem 5.13 There exists a Lebesgue integrable (that is an L^{1}) function f : 𝕋 → ℂ such that

lim sup_{N→∞} |S_{n}(f, t)| = ∞

for all t ∈ 𝕋.

Although this result is genuinely one of Lebesgue integration it can be obtained by simple (Lebesgue measure) arguments from a result not involving Lebesgue integration.

Lemma 5.14 Given any K > 0 we can find a trigonometric polynomial P such that

(i) ∫_{𝕋} |P (t)| dt ≤ 1,

(ii) max_{n≥0} |S_{n}(P, t)| ≥ K for all t ∈ 𝕋.

In our discussion of Kronecker’s theorem (Theorem 5.12) we worked modulo 1. In what follows it is easier to work modulo 2π. The readier will readily check that the definition and theorem that follow give the appropriate restatement of Kronecker’s theorem.

Definition 5.15 We work in 𝕋. If α_{1}, α_{2}, …, α_{M} satisfy

∑_{j=1}^{M} n_{j}α_{j} ≠ 0 for integer n_{j} not all zero.  ⋆

we say that they are independent.

Theorem 5.16 (Kronecker’s theorem (alternative statement)) Suppose that α_{1}, α_{2}, …, α_{M} are independent points in 𝕋. Then given complex numbers λ_{1}, λ_{2}, …, λ_{M} with |λ_{j}| = 1 [j = 1, 2, …, M] and ϵ > 0 we can find an integer N N such that

| exp(iNα_{j}) − λ_{j}| < ϵ

for each 1 ≤ j ≤ M.

Our construction requires some preliminary results.

Lemma 5.17 If x_{1}, x_{2}, …, x_{M} are independent points in 𝕋 and t ∈ 𝕋 and

∑_{j=1}^{M} n_{j}(x_{j} − t) = 0 for integer n_{j} not all zero

∑_{j=1}^{M} m_{j}(x_{j} − t) = 0 for integer m_{j} not all zero

then there exist P, Q ∈ {n : n ∈ ℤ, n ≠ 0} such that P n_{j} = Qm_{j} for 1 ≤ j ≤ M.

Lemma 5.18 If x_{1}, x_{2}, …, x_{M} are independent points in 𝕋 and t ∈ 𝕋, then one of the following must hold:-

(a) There exists an i ≠ 1 such that the points x_{j} − t with j ≠ i are independent.

(b) x_{1} − t is a rational multiple of 2π and the points x_{j} − t with j ≠ 1 are independent.

Lemma 5.19 (i) If I is an open interval in 𝕋 and x_{1}, x_{2}, …, x_{m} are independent we can find x_{m+1} ∈ I such that x_{1}, x_{2}, …, x_{m+1} are independent.

(ii) Given an integer M ≥ 1, we can find independent points x_{1}, x_{2}, …, x_{M} in 𝕋 such that

|x_{j} − 2πj/M| ≤ 10^{−3}M^{−1}

Lemma 5.20 If M and x_{1}, x_{2}, …, x_{M} in 𝕋 are as in Lemma 5.19 (ii), then setting

μ = M^{−1} ∑_{j=1}^{M} δ_{x_{j}}

we have the following two results.

(i) max_{n≥0} |S_{n}(μ, t)| ≥ 100^{−1} log M for each t ∈ 𝕋,

(ii) There exists an N such that max_{N≥n≥0} |S_{n}(μ, t)| ≥ 200^{−1} log M for each t ∈ 𝕋.

Remark 1 If you wish you may treat S_{n}(μ, t) as a purely formal object. However, it is better for later work to think what it actually is. Remark 2 Factors like 10^{−3} and 100^{−1} in Lemmas 5.19 (ii) and 5.20 are more or less chosen at random and are not ‘best possible’.

A simple argument using Lemma 5.20 now gives Lemma 5.14 and we are done.

Exercise 5.21 (i) Show, by considering Fejér sums or otherwise, that we cannot find a continuous function f such that S_{n}(f, t) → ∞ uniformly as n → ∞.

(ii) (Requires measure theory and a little bit more thought.) Show that we cannot find an integrable (i.e. L^{1}) function f such that S_{n}(f, t) → ∞ for almost all t as n → ∞.

6 Some simple geometry of numbers

We need the following extension of Theorem 5.8.

Lemma 6.1 If A is a well behaved set and f is the characteristic function of A (that is f(x) = 1 if x ∈ A, f(x) = 0 otherwise), then

∑_{n∈ℤ^{m}} |f̂(n)|^{2} = \frac{1}{(2π)^{m}} ∫_{𝕋^{m}} |f(t)|^{2} dt.

If you know Lebesgue measure, then this is obvious (for bounded measurable sets, say) since a simple density argument shows that Parseval’s Theorem (Theorem 5.8) holds for every f ∈ L^{1}∩L^{2}. If we restrict ourselves to Riemann integration, it is obvious what sort of approximation argument we should use but the technical details are a typically painful.

Exercise 6.2 EITHER (i) Give the detailed proof of Lemma 6.1 in terms of Lebesgue measure.

OR (ii) Give the detailed proof of Lemma 6.1 in terms of Riemann integration in the special case when A is a sphere.

We use Parseval’s Theorem (in the form of Lemma 6.1) to give Siegel’s proof of Minkowski’s theorem.

Theorem 6.3 (Minkowski) Let Γ be an open symmetric convex set in ℝ^{m} with volume V. If V > 2^{n}, then Γ ∩ ℤ^{m} contains at least two points.

The reader will recall that Γ is convex if

x, y ∈ Γ and 0 ≤ λ ≤ 1 ⇒ λx + (1 − λ)y ∈ Γ

and that Γ is symmetric if

x ∈ Γ ⇒ −x ∈ Γ.

It is not entirely obvious obvious (though it is true) that every open convex set has a (possibly infinite) volume in the sense of Riemann. Readers who wish to use Riemann integration may add the words ‘well behaved’ to the statement of Minkowski’s theorem.

Before beginning the proof we observe that Minkowski’s result is best possible.

Lemma 6.4 If V ≤ 2^{m} there exists an open symmetric convex set Γ in ℝ^{m} with volume V such that Γ ∩ ℤ^{m} = {0}.

To prove Minkowski’s theorem (Theorem 6.3) it suffices to prove an essentially equivalent result.

Theorem 6.5 Let Γ be a bounded open symmetric convex set in ℝ^{m} with volume V. If V > 2^{n}(2π)^{n}, then Γ ∩ (2πℤ)^{m} contains at least two points.

We need the following simple result.

Lemma 6.6 If Γ is symmetric convex set and x, x − 2y ∈ Γ, then y ∈ Γ.

By applying Parseval’s theorem to f(x) = ∑_{k∈ℤ^{m}} ϕ(2x − 2πk) we obtain the following results.

Lemma 6.7 Let Γ be a bounded open symmetric convex set in ℝ^{m} with volume V such that Γ ∩ (2πℤ)^{m} only contains 0. Then

2^{−m} ∑_{k∈ℤ)^{m}} |∫ ϕ(x)e^{ik.x} dx|^{2} = (2π)^{m}V.  ⋆

Minkowski’s theorem follows at once by considering the term with k = 0 in equation ⋆.

Here is a simple application of Minkowski’s theorem.

Lemma 6.8 Suppose that a, b, c, d are real numbers with ad−bc = 1. Given l > 0 and ϵ > 0 we can find integers m and n such that

|an + bm| ≤ (1 + ϵ)l, |cn + bm| ≤ (1 + ϵ)l^{−1}.

Taking c = x, a = 1, b = 0, d = 1 and thinking carefully we obtain in quick succession.

Lemma 6.9 If x is real there exist n and m integers with m ≠ 0 such that

|x − \frac{n}{m}| ≤ \frac{1}{m^{2}} .

Lemma 6.10 If x is real there exist infinitely many pairs of integers n and m with m ≠ 0 such that

|x − \frac{n}{m}| ≤ \frac{1}{m^{2}} .

Here is another simple consequence.

Lemma 6.11 (Quantitative version of Dirichlet’s theorem) If x ∈ ℝ^{m}, then given l > 0 and ϵ > 0 we can find n, n_{1}, n_{2}, …, n_{m} ∈ ℤ such that

|nx − n_{j}| ≤ l^{−1}

for 1 ≤ j ≤ m and |n| ≤ l^{m}.

We conclude our collection of consequences with Lagrange’s four squares theorem.

Theorem 6.12 (Lagrange) Every positive integer is the sum of at most 4 squares.

Lemma 6.13 We can not reduce 4 in the statement of Lagrange’s theorem (Theorem 6.12).

We need an observation of Euler.

Lemma 6.14 If x_{0}, x_{1}, x_{2}, x_{3}, y_{0}, y_{1}, y_{2}, y_{3} are real, then

(x_{0}^{2}+x_{1}^{2} + x_{2}^{2} + x_{3}^{2})(y_{0}^{2} + y_{1}^{2} + y_{2}^{2} + y_{3}^{2})
=(x_{0}y_{0} − x_{1}y_{1} − x_{2}y_{2} − x_{3}y_{3})^{2} + (x_{0}y_{1} + x_{1}y_{0} + x_{2}y_{3} − x_{3}y_{2})^{2}+
(x_{0}y_{2} − x_{1}y_{3} + x_{2}y_{0} + x_{3}y_{1})^{2} + (x_{0}y_{3} + x_{1}y_{2} − x_{2}y_{1} + x_{3}y_{1})^{2}.

Exercise 6.15 In the lectures we will use quaternions to prove Lemma 6.14. Prove the equality by direct verification.

Exercise 6.16 Use complex numbers to prove that, if x_{0}, x_{1}, y_{0}, y_{1}, are real, then

(x_{0}^{2} + x_{1}^{2})(y_{0}^{2} + y_{1}^{2}) = (x_{0}y_{0} − x_{1}y_{1})^{2} + (x_{0}y_{1} − x_{1}y_{0})^{2}.

Lemma 6.17 Lagrange’s four square theorem will follow if we can show that every odd prime is the sum of at most four squares.

We shall also need the volume of a 4 dimensional sphere. A simple argument gives the volume of a unit sphere in any dimension.

Lemma 6.18 Let V_{n} be the (n-dimensional) volume of an n dimensional unit sphere.

(i) If f : [0, ∞) → ℝ is a continuous function with t^{n+2}f(t) → 0 as t → ∞, then

∫_{ℝ^{n}} f(∥x∥) dV (x) = V_{n} ∫_{0}^{∞} f(t)nt^{n−1} dt.

(ii) V_{2k} = \frac{π^{k}}{k!} , V_{2k+1} = \frac{k!2^{2k+1}π^{k}}{(2k + 1)!} .

Finally we need the apparently more general version of Minkowski’s theorem obtained by applying a linear map.

Theorem 6.19 (Minkowski for general latices) We work in in ℝ^{m}. Let Λ be a lattice with fundamental region of volume L and let Γ be an open symmetric convex set with volume V. If V > 2^{m}L, then Γ ∩ Λ contains at least two points.

We now turn to the proof of the fundamental lemma.

Lemma 6.20 Every odd prime is the sum of at most four squares.

We begin with a simple lemma.

Lemma 6.21 Let p be an odd prime.

(i) If we work in ℤ_{p}, then the set {u^{2} : u ∈ ℤ_{p}} has at least (p + 1)/2 elements.

(ii) We can find integers u and v such that u^{2} + v^{2} ≡ −1 mod p.

We now introduce a lattice.

Lemma 6.22 Let p, u and v be as in Lemma 6.21. If

Λ = {(n, m, a, b) ∈ ℤ^{4} : nu + mv ≡ a, mu − nv ≡ b mod p}

the Λ is a lattice with fundamental region of volume p^{2}.

If (n, m, a, b) ∈ Λ, then n^{2} + m^{2} + a^{2} + b^{2} ≡ 0 mod p.

We can now prove Lemma 6.20 and with it Theorem 6.12.

Exercise 6.23 (i) Recall that if p is a prime, then the multiplicative group (ℤ_{p} \ {0}, ×) is cyclic. (This is the subject of Exercise 10.15.) Deduce that if p = 4k + 1, then there is an element u in (ℤ_{p} \ {0}, ×) of order 4. Show that u^{2} = −1.

(ii) If p and u are as in (i) show that

Λ = {(n, m) ∈ ℤ^{2} : m ≡ n mod p}

is a lattice and deduce that there exist n, m with n^{2} + m^{2} = p. (This is a result of Fermat. Every prime congruent to 1 modulo 4 is the sum of two squares.)

(iii) Show that any odd number which is the sum of two squares must be congruent to 1 modulo 4.

7 A preliminary look at Fourier transforms

If f : ℝ → ℂ is integrable on each finite interval [a, b] (in the Riemann or Lebesgue sense) and ∫_{−∞}^{∞} |f(x)| dx < ∞ we^{3} shall say that f is appropriate. (This is non-standard notation.) If f is appropriate define

f̂(λ) = ∫_{−∞}^{∞} f(t) exp(−iλt) dt.

3The majority of my auditors who know Lebesgue integration will prefer the formulations ‘f ∈ L^{1}(ℝ)’ or ‘f measurable and ∫_{−∞}^{∞} |f(x)| dx < ∞’.

Lemma 7.1 If f is appropriate, f̂: ℝ → ℂ is continuous. and bounded.

Our first problem is that even when f is appropriate f̂ need not be.

Example 7.2 If f is the indicator function of [a, b] (that is, f(x) = 1 if x ∈ [a, b], f(x) = 0 otherwise), then

∫_{−∞}^{∞} |f̂(λ)| dλ = ∞.

This turns out not to matter very much but should be borne in mind.

When we try to imitate our treatment of Fourier series we find that we need to interchange the order of integration of two infinite integrals. If we use Lebesgue integration we can use a very powerful theorem.

Theorem 7.3 (Fubini’s theorem) If f : ℝ^{2} → ℂ is measurable and either of the two integrals

∫_{−∞}^{∞} ∫_{−∞}^{∞} |f(x, y)| dx dy and ∫_{−∞}^{∞} ∫_{−∞}^{∞} |f(x, y)| dy dx

exists and is finite, then they both do and the integrals

∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dx dy and ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dy dx.

exist and are finite and equal.

If we use Riemann integration, then we have a slogan.

Pretheorem 7.4 If f : ℝ^{2} → ℂ is well behaved and either of the two integrals

∫_{−∞}^{∞} ∫_{−∞}^{∞} |f(x, y)| dx dy and ∫_{−∞}^{∞} ∫_{−∞}^{∞} |f(x, y)| dy dx

is finite, then they both are and

∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dx dy and ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dy dx.

In every case that we need the pretheorem can be turned into a theorem but the proofs become more and more tedious as we weaken the conditions on f.

Exercise 7.5 In this exercise we use Riemann integration and derive a simple Fubini type theorem.

(i) If I and J are intervals on ℝ (so I could have the form [a, b], [a, b), (a, b) or (a, b)) and we write 𝕀_{I×J}(x, y) = 1 if (x, y) ∈ I × J, 𝕀_{I×J}(x, y) = 0, otherwise show that

∫_{−∞}^{∞} ∫_{−∞}^{∞} 𝕀_{I×J}(x, y) dx dy = ∫_{−∞}^{∞} ∫_{−∞}^{∞} 𝕀_{I×J}(x, y) dy dx.

(ii) Suppose that I_{r} and J_{r} are intervals on ℝ and that λ_{r} ∈ ℂ [1 ≤ r ≤ n]. If f = ∑_{r=1}^{n} 𝕀_{I_{r}×J_{r}} show that

∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dx dy = ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dy dx.

(iii) Suppose that f : ℝ^{2} → ℂ is continuous and that I and J are intervals on ℝ. If g(x, y) = 𝕀_{I×J}(x, y)f(x, y) show using (ii) that

∫_{−∞}^{∞} ∫_{−∞}^{∞} g(x, y) dx dy = ∫_{−∞}^{∞} ∫_{−∞}^{∞} g(x, y) dy dx.

(iv) Suppose that f : ℝ^{2} → ℂ is continuous and that there exists a real constant A such that

|f(x, y)| ≤ A(1 + x^{2})^{−1}(1 + y^{2})^{−1}.  ⋆

Show, using (ii), that

∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dx dy = ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(x, y) dy dx.

Conditions like ⋆ imposing some rate of decrease at infinity play an important role in Fourier analysis.

In the next section we shall adopt a slightly more sophisticated approach to the Fourier transform than that given in the next exercise but the results are sufficient for many purposes and the exercise gives an interesting review of earlier work. We shall need the following definition.

Definition 7.6 We say that f is piecewise continuous if, for each R > 0, f continuous at all but finitely many points of (−R, R) and

f(t) = lim_{h→0+} f(t − h)

for all t.

(Different authors use different definitions. They are all the same ‘in spirit’ but not ‘in logic’.)

Exercise 7.7 If f is appropriate and R > 0 we define

σ_{R}(f, t) = \frac{1}{2π} ∫_{−R}^{R} (1 − \frac{|λ|}{R}) f̂(λ) exp(iλt) dλ.

(It will become clear that this is the analogue of the Fejér sum.)

(i) (For users of the Lebesgue integral) By adapting the proof of Theorem 3.6 show that if f ∈ L^{1} and f is continuous at t then

σ_{R}(f, t) → f(t)

as R → ∞. Is the result necessarily true if f is not continuous at t? Give reasons.

(i’) (For users of the Riemann integral) By adapting the proof of Theorem 3.6 show that if f is continuous and there there exists a real constant A such that

|f(x)| ≤ A(1 + x^{2})^{−1}

for all x, show that

σ_{R}(f, t) → f(t)

for all t.

Without going into detail convince yourself that the result continues to hold if we replace the condition ‘f continuous’ by the condition ‘f piecewise continuous’ and the conclusion by

σ_{R}(f, t) → f(t)

at all t where f is continuous. (All we need is a slight extension of Exercise 7.5 (iv).)

(ii) (For users of the Lebesgue integral) Suppose that f and g are piecewise continuous L^{1} functions. Show that, if f̂(λ) = ĝ(λ) for all λ, then f(t) = g(t) for all t.

(ii’) (For users of the Riemann integral) Suppose f and g are piecewise continuous and there there exists a real constant A such that

|f(x)|, |g(x)| ≤ A(1 + x^{2})^{−1}

for all x. Show that, if f̂(λ) = ĝ(λ) for all λ, then f(t) = g(t) for all t.

8 The Fourier transform and Heisenberg’s inequality

In this section we starting by looking at some of the ideas of the previous section from a slightly different angle. I shall state results using Lebesgue measure but students using Riemann integration will find appropriate modifications as exercises.

Here are a few standard results on Fourier transforms.

Lemma 8.1 (i) If f ∈ L^{1}(ℝ) and we write f_{a}(x) = f(x − a), then

f̂_{a}(λ) = e^{iλa}f̂(λ).

(ii) If f is differentiable, f′ is continuous, f, f′ ∈ L^{1}(ℝ) and f(t) → 0 as |t| → ∞, then

iλf̂′(λ) = f̂(λ).

(iii) If f, g ∈ L^{1}(ℝ) and we write

f ∗ g(x) = ∫_{−∞}^{∞} f(x − y)g(y) dy

then f ∗ g ∈ L^{1}(ℝ) and

{ \atop f ∗ g}(λ) = f̂(λ)ĝ(λ).

Exercise 8.2 Prove similar results for the Riemann integral. (Feel free to use strong hypotheses.)

We pay particular attention to the Gaussian (or heat, or error) kernel E(x) = (2π)^{−1/2} exp(−x^{2}/2).

Lemma 8.3 Ê(λ) = (2π)^{1/2}E(λ)

Exercise 8.4 If I prove Lemma 8.3, I shall do so by setting up a differential equation. Obtain Lemma 8.3 by complex variable techniques.

We use the following neat formula.

Lemma 8.5 If f, g ∈ L^{1}(ℝ) then the products f̂× g, f × ĝ ∈ L^{1}(ℝ) and

∫_{∞}^{∞} f̂(x)g(x) dx = ∫_{∞}^{∞} f(λ)ĝ(λ) dλ.

Exercise 8.6 (For those using Riemann integration. You will need to refer back to the exercises in Section 7.) Suppose f and g are continuous and there there exists a real constant A such that

|f(x)|, |g(x)| ≤ A(1 + x^{2})^{−1}

for all x and

f̂(λ)|, |ĝ(λ)| ≤ A(1 + λ^{2})^{−1}

for all λ. Show that

∫_{∞}^{∞} f̂(x)g(x) dx = ∫_{∞}^{∞} f(λ)ĝ(λ) dλ.

Without going into detail convince yourself that the hypothesis ‘f and g are continuous’ can be replaced by ‘f and g are piecewise continuous’.

By taking f = E_{h} where E_{h}(x) = h^{−1}E(h^{−1}(x)) [h > 0] in Lemma 8.5 we obtain a nice pointwise inversion result.

Theorem 8.7 If f, f̂ ∈ L^{1} and f is continuous at t, then ˆ f̂(t) = 2πf(−t).

Exercise 8.8 (For those using Riemann integration.) Suppose that f is piecewise continuous and there exists a real constant A such that

|f(x)| ≤ A(1 + x^{2})^{−1}

for all x and

|f̂(λ)| ≤ A(1 + λ^{2})^{−1}

for all λ. Show that if f is continuous at t, then ˆ f̂(t) = 2πf(−t).

Exercise 8.9 Suppose that f satisfies the conditions of Theorem 8.7 (if you use Lebesgue integration) or Exercise 8.8 (if you use Riemann integration). If t is a point where f(t+) = lim_{h→0+} f(t + h) and f(t−) = lim_{h→0+} f(t − h) both exist show that

ˆf̂(−t) = π(f(t+) + f(t−)).

Exercise 8.10 Suppose that G, Ĝ ∈ L^{1}(ℝ), G(0) ≠ 0 and ∫_{−∞}^{∞} G(t) dt ≠ 0. Show that if we replace E by G in our arguments we still obtain

∫_{−∞}^{∞} f̂(λ) dt = Af(0)

for all f satisfying appropriate conditions and some constant A.

We can now prove a version of Parseval’s formula for Fourier transforms.

Theorem 8.11 If f, g, f̂, ĝ ∈ L^{1}(ℝ) and f and g are continuous, then

\frac{1}{2π} ∫_{−∞}^{∞} f̂(λ)ĝ(λ)^{∗} dλ = ∫_{−∞}^{∞} f(t)g(t)^{∗} dt

and

\frac{1}{2π} ∫_{−∞}^{∞} |f̂(λ)|^{2} dλ = ∫_{−∞}^{∞} |f(t)|^{2} dt.

Exercise 8.12 Prove similar results for the Riemann integral. (Feel free to use strong hypotheses.)

The next exercise contains a more sophisticated version of Parseval’s theorem.

Exercise 8.13 (This requires Lebesgue measure.) The present course is rather old fashioned, not least in the way it thinks of Fourier transforms f̂ in terms of its values f̂(λ) at points λ, rather than an object in its own right. Here is one of several ways in which a more general view gives a more elegant theory.

(i) Let S be the set of infinitely differentiable functions f with

x^{n}f^{(m)}(x) → 0

as |x| → ∞ for all integers n, m ≥ 0. Show that if f ∈ S, then f̂ ∈ S.

(ii) Let 𝕀_{[a,b]}(x) = 1 for x ∈ [a, b], 𝕀_{[a,b]}(x) = 0 otherwise. Show that if E_{h} is defined as above, then

∥𝕀_{[a,b]} − E_{h} ∗ 𝕀_{[a,b]}∥_{2} → 0

as h → 0+. Deduce or prove otherwise that S is L^{2} norm dense in L^{2}. (iii) By taking g = f̂ in Lemma 8.5 show that

∥f̂∥_{2}^{2} = 2π∥f∥_{2}^{2}

for all f ∈ S.

(iv) Deduce that there is a unique continuous mapping F : L^{2} → L^{2} with F(f) = f̂ for all f ∈ S. (Uniqueness is easy but you should take care proving existence.)

(v) Show that F : L^{2} → L^{2} is linear and that

∥F(f)∥_{2}^{2} = 2π∥f∥_{2}^{2}

for all f ∈ L^{2}.

If we define J : L^{2} → L^{2} by (J f)(t) = f(−t) show that F^{2} = 2πJ.

(vi) If we wish to work in L^{2}, it makes sense to use a different normalising factor and call G = (2π)^{−1/2}F the Fourier transform. Show that G^{4} = I and that G : L^{2} → L^{2} is a bijective linear isometry.

We now come to one of the key facts about the Fourier transform (some would say one of the key facts about the world we live in).

Theorem 8.14 (Heisenberg’s inequality) If f is reasonably well behaved, then

\frac{∫_{−∞}^{∞} λ^{2}|f̂(λ)|^{2} dλ}{∫_{−∞}^{∞} |f̂(λ)|^{2} dλ} × \frac{∫_{−∞}^{∞} x^{2}|f(x)|^{2} dx}{∫_{−∞}^{∞} |f(x)|^{2} dx} ≥ \frac{1}{4}.

If equality holds, then f(x) = A exp(−bx^{2}) for some b > 0.

Exercise 8.15 Write down explicit conditions for Theorem 8.14.

The extension of Heisenberg’s inequality to all f ∈ L^{2} is given in Section 2.8 of the beautiful book [1] of Dym and McKean.

9 The Poisson formula

The following remarkable observation is called Poisson’s formula.

Theorem 9.1 Suppose that f : ℝ → ℂ is a continuous function such that ∑_{m=−∞}^{∞} |f̂(m)| converges and ∑_{n=−∞}^{∞} |f(2πn + x)| converges uniformly on [−π, π]. Then

∑_{m=−∞}^{∞} f̂(m) = 2π ∑_{n=−∞}^{∞} f(2πn).

It is possible to adjust the hypotheses on f in Poisson’s formula in various ways though some hypotheses there must be. We shall simply think of f as ‘well behaved’. The following rather simple lemma will suffice for our needs.

Lemma 9.2 If f : ℝ → ℂ is a twice continuously differentiable function such that ∫_{−∞}^{∞} |f(x)| dx, ∫_{−∞}^{∞} |f′(x)| dx and ∫_{−∞}^{∞} |f′′(x)| dx converge whilst f′(x) → 0 and x^{−2}f(x) → 0 as |x| → ∞, then f satisfies the conditions of Theorem 9.1.

Exercise 9.3 (i) By applying Poisson’s formula to the function f defined by f(x) = exp(−t|x|/2π) show that

2(1 − e^{−t})^{−1} = 1 + ∑_{n=−∞}^{∞} 2t(t^{2} + 4π^{2}n^{2})^{−1}.

(ii) By expanding (t^{2}+4πn^{2})^{−1} and (carefully) interchanging sums deduce that

2(1 − e^{−t})^{−1} = 1 + 2t^{−1} + ∑_{m=0}^{∞} c_{m}t^{m}

where c_{2m} = 0 and

c_{2m+1} = a_{2m+1} ∑_{n=1}^{∞} n^{−2m}

for some value of a_{2m+1} to be given explicitly.

(iii) Hence obtain Euler’s formula

∑_{n=1}^{∞} n^{−2m} = (−1)^{m−1}2^{2m−1}b_{2m−1}π^{2m}/(2m − 1)!

for m ≥ 1, where the b_{m} are defined by the formula

(e^{y} − 1)^{−1} = y^{−1} − 2^{−1} + ∑_{n=1}^{∞} b_{n}y^{n}/n!

(The b_{n} are called Bernoulli numbers.)

Exercise 9.4 Suppose f satisfies the conditions of Lemma 9.2. Show that

K ∑_{m=−∞}^{∞} f̂(Km) = 2π ∑_{n=−∞}^{∞} f(2πK^{−1}n)

for all K > 0. What is the corresponding result when K < 0.

By letting K → 0+ deduce that

ˆf̂(0) = 2πf(0).

(There is some interest in just seeing that this is so, but it is more profitable to give a rigorous proof.) Deduce in the usual way that

ˆf̂(t) = 2πf(−t)

for all t.

Poisson’s formula has a particularly interesting consequence.

Lemma 9.5 If g : ℝ → ℂ is twice continuously differentiable and g(t) = 0 for |t| ≥ π, then g is completely determined by the values of ĝ(m) for integer m.

Taking g = f̂ and remembering the inversion formula we obtain the following result.

Pretheorem 9.6 If f : ℝ → ℂ is a well behaved function with f̂(λ) = 0 for |λ| ≥ π then f is determined by its values at integer points.

We call this a pretheorem because we have not specified what ‘well behaved’ should mean.

The simplest approach is via the sinc function

sinc(x) = \frac{1}{2π} ∫_{−π}^{π} exp(ixλ) dλ.

We state the most immediately useful properties of sinc.

Lemma 9.7 (i) sinc(0) = 1, (ii) sinc(n) = 0 if n ∈ ℤ but n ≠ 0.

(We note also that although, strictly speaking, ŝinc(λ) is not defined for us, since ∫_{−∞}^{∞} | sinc(x)| dx = ∞, we are strongly tempted to say that ŝinc(λ) = 1 if |λ| < π and ŝinc(λ) = 0 if |λ| > π.)

We can, at once, prove that Pretheorem 9.6 is best possible.

Lemma 9.8 If ϵ > 0, then we can find an infinitely differentiable non-zero f such that f̂(λ) = 0 for |λ| > π + ϵ but f(n) = 0 for all n ∈ ℤ.

Exercise 9.9 In Lemma 9.8 show that we can take f ∈ S where S is the class discussed in Exercise 8.13.

We can also show how to recover the function of Pretheorem 9.6 from its values at integer points.

Theorem 9.10 Suppose that f : ℝ → ℂ is a continuous function with ∫_{−∞}^{∞} |f(t)| dt < ∞. If f̂(λ) = 0 for |λ| ≥ π then

∑_{n=−N}^{N} f(n) sinc(t − n) → f(t)

as uniformly as N → ∞.

Thus Pretheorem 9.6 holds under very general conditions. We state it in a lightly generalised form. Theorem 9.11 (Shannon’s Theorem) Suppose that f : ℝ → ℂ is a continuous function with ∫_{−∞}^{∞} |f(t)| dt < ∞ and that K > 0. If f̂(λ) = 0 for |λ| ≥ K, then then f is determined by its values at points of the form nπK^{−1} with n ∈ ℤ.

Theorem 9.11 belongs to the same circle of ideas as Heisenberg’s inequality. It is the key to such devices as the CD.

10 Fourier analysis on finite Abelian groups

The methods of Fourier analysis can be extended to the much wider system of locally compact Abelian groups. We shall hint at how this is done by looking at the special case of finite Abelian groups.

Recall that classical Fourier analysis deals with formulae like

f(t) = ∑_{n=−∞}^{∞} f̂(n)e_{n}(t)

where e_{n}(t) = exp(int). The clue to further extension lies in the following observation.

Lemma 10.1 Consider the Abelian group 𝕋 = ℝ/(2πℤ) and the subgroup S = {z : |z| = 1} of (ℂ\{0}, ×). The continuous homomorphisms θ : 𝕋 → S are precisely the functions e_{n} : 𝕋 → S given by e_{n}(t) = exp(int) with n ∈ ℤ.

Exercise 10.2 (i) Find (with proof) all the continuous homomorphisms θ : (ℝ, +) → (S, ×). What is the connection with Fourier transforms?

(ii) (Only for those who know Zorn’s lemma^{4}.) Assuming Zorn’s lemma, show that any linearly independent set in a vector space can be extended to a basis. If we consider ℝ as a vector space over ℚ show that there exists a linear map T : ℝ → ℝ such that T (1) = 1, T (√2) = 0. Deduce the existence of a function T : ℝ → ℝ such that T (x + y) = T (x) + T (y) for all x, y ∈ ℝ which is not continuous (with respect to the usual metric). Show that, if we accept Zorn’s lemma, there exist discontinuous homomorphisms θ : (ℝ, +) → (S, ×).

This suggests the following definition.

4And, particularly, those who only know Zorn’s lemma.

Definition 10.3 If G is a finite Abelian group, we say that a homomorphism χ : G → S is a character. We write Ĝ for the collection of such characters.

In this section we shall accumulate a substantial amount of information about Ĝ by a succession of small steps.

Lemma 10.4 Let G be a finite Abelian group.

(i) If x ∈ G has order m and χ ∈ Ĝ, then χ(x) is an mth root of unity. (ii) Ĝ is a finite Abelian group under pointwise multiplication.

To go further we consider, for each finite Abelian group G, the collection C(G) of functions f : G → ℂ. If G has order |G|, then C(G) is a vector space of dimension N which can be made into a complex inner product space by means of the inner product

⟨f, g⟩ = \frac{1}{|G|} ∑_{x∈G} f(x)g(x)^{∗}.

Exercise 10.5 Verify the statements just made.

Lemma 10.6 Let G be a finite Abelian group. The elements of Ĝ form an orthonormal system in C(G).

Does Ĝ form an orthonormal basis of C(G)? The next lemma tells us how we may hope to resolve this question.

Lemma 10.7 Let G be a finite Abelian group. The elements of Ĝ form an orthonormal basis if and only if given an element x ∈ G which is not the identity we can find a character χ with χ(x) ≠ 1.

The way forward is now clear.

Lemma 10.8 Suppose that H is a subgroup of a finite Abelian group G and that χ ∈ Ĥ. If K is a subgroup of G generated by H and an element a ∈ G, then we can find a χ̃ ∈ K̂ such that χ̃|H = χ.

Lemma 10.9 Let G be a finite Abelian group and x an element of G of order m. Then we can find a χ ∈ Ĝ with χ(x) = exp 2πi/m.

Theorem 10.10 If G is a finite Abelian group then Ĝ has the same number of elements as G and they form an orthonormal basis for C(G).

Lemma 10.11 If G is a finite Abelian group and f ∈ C(G), then

f = ∑_{χ∈Ĝ} f̂(χ)χ

where f̂(χ) = ⟨f, χ⟩.

Exercise 10.12 Suppose that G is a finite Abelian group. Show that, if we define θ_{x} : Ĝ → ℂ by θ_{x}(χ) = χ(x) for χ ∈ Ĝ, x ∈ G, then the map Θ : G → ˆ ĝ given by Θ(x) = θ_{x} is an isomorphism.

If we now identify x with θ_{x} (and, so, G with ˆ Ĝ) show that

|G| ˆf̂(x) = f(x^{−1})

for all f ∈ C(G) and x ∈ G.

We put ‘computational’ bones on this section by exhibiting the structure of G and Ĝ.

Lemma 10.13 Let (G, ×) be an Abelian group.

(i) Suppose that x, y ∈ G have order r and s with r and s coprime. Then xy has order rs.

(ii) If G contains elements of order n and m, then G contains an element of order the least common multiple of n and m.

Lemma 10.14 Let (G, ×) be a finite Abelian group. Then there exists an integer N and an element k such that k has order N and, whenever x ∈ G, we have x^{N} = e.

Exercise 10.15 Let p be a prime. Use Lemma 10.14 together with the fact that a polynomial of degree k can have at most k roots to show that the multiplicative group (ℤ_{p} \ {0}, ×) is cyclic.

Lemma 10.16 With the hypotheses and notation of Lemma 10.14 we can write G = K × H where K is the cyclic group generated by x and H is another subgroup of K.

As usual we write C_{n} for the cyclic group of order n.

Theorem 10.17 If G is a finite Abelian group we can find n(1), n(2), … n(m) with n(j + 1)|n(j) such that G is isomorphic to

C_{n(1)} × C_{n(2)} × … C_{n(m)}.

Lemma 10.18 If we have two sequences n(1), n(2), … n(m) with n(j + 1)|n(j) and n′(1), n′(2), … n′(m′) with n′(j + 1)|n′(j) then

C_{n(1)} × C_{n(2)} × … C_{n(m)} is isomorphic to C_{n′(1)} × C_{n′(2)} × … C_{n′(m′)}

if and only if m = m′ and n(j) = n′(j) for each 1 ≤ j ≤ m.

It is easy to identify Ĝ.

Lemma 10.19 Suppose that

G = C_{n(1)} × C_{n(2)} × … C_{n(m)}

with C_{n(j)} a cyclic group of order n(j) generated by x_{j}. Then the elements of Ĝ have the form χ_{ω_{n(1)}^{r(1)},ω_{n(2)}^{r(2)}}, …_{ω_{n(m)}^{r(m)}} with ω_{n(j)} = exp(2πi/n(j) and

χ_{ω_{n(1)}^{r(1)},ω_{n(2)}^{r(2)}}, … ω_{n(m)}^{r(m)}(x_{1}^{s(1)}x_{2}^{s(2)} … x_{m}^{s(m)}) = ω_{n(1)}^{r(1)s(1)}ω_{n(2)}^{r(2)s(2)} … ω_{n(m)}^{r(m)s(m)}.

My readers will see that Ĝ is isomorphic to G but the more sophisticated algebraists will also see that this is not a natural isomorphism (whereas G and ˆ Ĝ are naturally isomorphic).

11 Poisson and finite Abelian groups

The following neat discussion is taken from the remarkable book of Audrey Terras [8].

Let us look for an analogue of Poisson’s summation formula for finite Abelian groups. We need the following observation.

Lemma 11.1 Let H be a subgroup of the finite Abelian group G. Consider

H^{#} = {χ ∈ Ĝ : χ(h) = 1 for all h ∈ H}.

Then H^{#} is a subgroup of Ĝ and there is a natural identification

H^{#} ≅ (H/G) .

If we look long enough at Poisson’s summation formula

∑_{n∈ℤ}f(n + y) = ∑_{n∈ℤ} f̂(n) exp(2πiny),

we may see a correct analogue for finite Abelian groups.

Theorem 11.2 Let H be a subgroup of the finite Abelian group G and let f ∈ C(G). Then, with the notation of Lemma 11.1,

\frac{1}{|H|} ∑_{h∈H} f(gh) = ∑_{χ∈H^{#}} f̂(χ)χ(g).

(It is easy to get the normalisation wrong here, so it is a good idea to check it by taking f = 1.)

Recall^{5} the following definitions from coding theory.

Definition 11.3 A linear code E is a subspace of the vector space 𝔽_{2}^{n} over the field 𝔽_{2} of two elements.

The dual E′ of E is the set

E′ = {a ∈ 𝔽_{2}^{n} : ∑_{j=1}^{n} a_{j}x_{j} = 0 for all x ∈ 𝔽_{2}^{n}}.

If x ∈ E its Hamming weight W (x) is given by

W (x) = |{j : x_{j} = 1}|.

The weight enumerator polynomial of E is given by

w_{E}(x, y) = ∑_{j=1}^{n} A_{j}x^{n−j}y^{j}

where A_{j} is the number of elements of E of Hamming weight j.

Exercise 11.4 Show directly that E′ is a linear code.

Exercise 11.5 Under the assumptions and with the notation above, show that the following results are true.

(i) w_{C} is a homogeneous polynomial of degree n.

(ii) If C has rank r, then w_{C}(1, 1) = 2^{r}.

(iii) w_{C}(1, 0) = 1.

(iv) w_{C}(0, 1) takes the value 0 or 1.

(v) w_{C}(s, t) = w_{C}(s, t) for all s and t if and only if w_{C}(0, 1) = 1.

Lemma 11.6 A linear code E can be considered as a subgroup of the Abelian group (𝔽_{2}, +). With the notation of Lemma 11.1, its dual is E^{#}.

5‘Recall’ is here used in the mathematical sense ‘I am about to tell you’.

Applying the Poisson formula to E′ we obtain the following result.

Lemma 11.7 If E is a linear code with dual E′ and f ∈ C(E′), then

∑_{a∈E′} f(a) = |E|^{−1} ∑_{χ∈E} f̂(χ).

Applied to the function f(a) = x^{n−W (u)}y^{W (u)} this gives the fundamental MacWilliams identity.

Theorem 11.8 (MacWilliams) If E is a linear code with dual E′, then

w_{E′}(x, y) = |E|^{−1}w_{E}(x − y, x + y).

Exercise 11.9 The repetition code C for 𝔽_{2}^{n} consists of the two elements (0, 0, …, 0) and (1, 1, …, 1). Find the dual and verify the MacWilliams identity.

12 The fast Fourier transform and some applications

If f : ℝ → ℝ is well behaved the natural way to compute f̂(λ) is by means of a sum

N^{−1} ∑_{j=0}^{N−1} f(x_{j}) exp(−iλx_{j})

which requires at least N + 1 multiplications and N − 1 additions. To get a good grasp of f̂ we might require its value at N points which in turn would require about 2N^{2} arithmetical operations.

This made Fourier methods very expensive in computer time but the situation was transformed by the following simple set of observations.

Theorem 12.1 Let G_{N} be the multiplicative group of Nth roots of unity and G_{2N} the group of 2Nth roots of unity. Suppose that, given ω_{N} = exp 2π/N, we can compute all the Fourier coefficients of any F ∈ C(G_{N}) using no more than M multiplications and additions. Then, given ω_{N} = exp 2π/N, we can compute all the Fourier coefficients of any F ∈ C(G_{2N}) using no more than 2M + 8N multiplications and additions.

Theorem 12.2 (Cooley and Tuckey) Let N = 2^{n} and let G_{N} be the multiplicative group of Nth roots of unity. Then, given ω_{N} = exp 2π/N, we can compute all the Fourier coefficients of any f ∈ C(G_{N}) using no more than n2^{n+2} = 4N log_{2} N additions and multiplications.

This method gives us a large number of Fourier transforms very cheaply. A little thought shows that although the method restricts us in some ways these restrictions are worth accepting.

The next result is left as a simple exercise to the reader but forms part of the course.

Theorem 12.3 Let N = 2^{n} and let G_{N} be the multiplicative group of Nth roots of unity. Then, given ω_{N} = exp 2π/N and f̂, we can compute all the values of any f ∈ C(G_{N}) using no more than n2^{n+2} = 4N log_{2} N additions and multiplications.

Here is a pretty application.

Theorem 12.4 Suppose 2^{n} = N ≥ p + q + 1. Then, given ω_{N} = exp 2π/N, we can compute all the coefficients c_{u} of the product ∑_{u=1}^{p+q} c_{u}t^{u} of two polynomials ∑_{r=1}^{p} a_{r}t^{r} and ∑_{s=1}^{q} b_{s}t^{s} in no more than 2^{n}+3n2^{n+2} = N +12N log_{2} N additions and multiplications.

This idea can be made the basis of fast exact multiplication of integers so large that they must be stored in many registers.

13 The Radon transform

In a CAT scanner beams of X-rays are shone through the human skull and we seek to reconstruct the interior of the skull by looking at the shadows cast by the X-rays.

Let us look first at an idealised one-dimensional problem in which a ray is shone along the x-axis in the direction x increasing. If the ray has intensity V (x) and the material has ‘attenuating’ power f(x) at at x it is natural to suppose that, to first order, in δx

V (x + δx) = (1 − f(x))V (x).

First year calculus now gives (assuming reasonable behaviour)

\frac{V (X)}{V (Y)} = exp (− ∫_{X}^{Y} f(x) dx) .

This law has been verified by experiment. Assuming that f(x) = 0 for large x

this means that we can indeed find ∫_{−∞}^{∞} f(x) dx by measuring the attenuation

of a ray of light.

Now consider the two-dimensional problem in which we have a well behaved, but unknown function f : ℝ^{2} → ℝ. In accordance with the previous

paragraph we may suppose that we can find the line integral ∫_{−∞}^{∞} f(x) dx of f

along any given straight line l. Can we reconstruct f from this information? This problem and its higher dimensional analogues is call the ‘tomographic problem’. The reader is warned that the nature of the problem depends on the dimension. The two-dimensional problem corresponds to ‘slice tomography’.

Let us establish some notation. Write u_{θ} for the unit vector making an angle θ with the x-axis and v_{θ} for the unit vector making an angle θ + π/2 with the x-axis. We know the line integrals

(Rf)(r, θ) = ∫_{−∞}^{∞} f(ru_{θ} + tv_{θ}) dt

and we wish to recover f. The function Rf : ℝ × 𝕋 → R is called the Radon transform of f.

Exercise 13.1 (i) Show that

(Rf)(−r, θ) = (Rf)(r, θ + π)

(ii) Find Rf in the two cases

(a) f(x, y) = exp(−(x^{2} + y^{2})/2),

(b) f(x, y) = 1 if |x|, |y| ≤ 1.

The Radon transform has a remarkable connection with the Fourier transform. Write

F_{1}(Rf)(s, θ) = ∫_{−∞}^{∞}(Rf)(r, θ) exp(−irs) ds

so that F_{1}(Rf) is the one-dimensional Fourier transform of Rf with respect to the first transform.

Lemma 13.2 Provided f is well behaved

f̂(su_{θ}) = F_{1}(Rf)(s, θ)

where f̂ is the usual two dimensional Fourier transform.

Thus f is uniquely determined by Rf and f may be obtained from Rf by using one and two-dimensional Fourier transforms.

Exercise 13.3 Recover the f in Exercise 13.1 from their Radon transforms.

14 References and further reading

If the elegance and variety of a subject is to be judged by the elegance and variety of the (best) texts on that subject, Fourier Analysis must surely stand high. On the pure side the books of Helson [2] and Katznelson [4] would be my first choice for introductions and this course draws on both. (There is also a nice book by Krantz [7].) If you wish to think about applications, the obvious text is that of Dym and and McKean [1]. The next two recommendations are irrelevant to Part III but, if you go on to work in any field involving classical analysis, Zygmund’s treatise [9] is a must and, if you would like a first glimpse at wavelets, (unmentioned in this course) Babarah Hubbard’s popularisation The World According to Wavelets [3] is splendid light reading.

In preparing this course I have also used [5] and [6] since I find the author sympathetic.

References

[1] H. Dym and H. P. McKean Fourier Series and Integrals Academic Press, 1972.

[2] H. Helson Harmonic Analysis Adison–Wesley, 1983.

[3] B. Hubbard The World According to Wavelets A. K. Peters, 1996.

[4] Y. Katznelson An Introduction to Harmonic Analysis Wiley, 1963. [Now reprinted by CUP]

[5] T. W. Körner Fourier Analysis CUP, 1988.

[6] T. W. Körner Exercises for Fourier Analysis CUP, 1993.

[7] S. Krantz A Panorama of Harmonic Analysis Carus Monographs, 1999.

[8] A. Terras Fourier analysis on finite groups and applications CUP, 1999.

[9] A. Zygmund Trigonometric Series (2 Volumes) CUP, 1959.