An Introduction to Fourier Analysis Part III

T. W. Körner July 24, 2012

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. 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 and might even part with a small reward to the first finder of particular errors. This document is written in L^{A}TEX2e and should be accessible in tex, dvi, ps and pdf form from my home page

http://www.dpmms.cam.ac.uk/~twk/ together with a list of corrections.
   My e-mail address is twk@dpmms.cam.ac.uk.

Contents

1 Some notes of explanation 2 2 Fourier series on the circle 2 3 A Theorem of Kahane and Katznelson 9 4 Many Dimensions 10 5 Some simple geometry of numbers 15 6 A brief look at Fourier transforms 18 7 Infinite products 21 8 Fourier analysis on finite Abelian groups 27 9 The Euler-Dirichlet formula 30 10 Analytic continuation of the Dirichlet functions 32 11 L(1, χ) is not zero 34

12 Chebychev and the distribution of primes 36

13 The prime number theorem 37

14 The Fourier transform and Heisenberg’s inequality 41

15 The Poisson formula 44

16 References and further reading 47

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 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.

Because of the strong number theoretic bias of this course, I will not have the time to devote to the Fourier transform that, ideally, I would have wished. The reader must be aware that she is seeing only a limited number of aspects of Fourier analysis. Although I intend to reach the end of Section 13, I am not sure that I will I have time for the final two sections.

The exercises do not form part of the course. I hope that those who attempt them will find them reasonably easy, instructive and helpful both in understanding the course and helping the reader towards ‘mathematical maturity’ — but I may well be wrong.

2 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.

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

We shall see (Lemma 10) 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 1 Let a_{1}, a_{2}, … be a sequence of complex numbers.

(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 → ∞.

In what follows we define

f ∗ g(t) = \frac{1}{2π} ∫_{𝕋} f(t − s)g(s) ds

(for appropriate f and g).

Lemma 2 If f is integrable we have

S_{n}(f) = f ∗ D_{n}
σ_{n}(f) = f ∗ K_{n}.

where

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

K_{n}(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 (i) \frac{1}{2π} ∫_{𝕋} 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

\frac{1}{2π} ∫_{𝕋} |D_{n}(t)| dt ≥ A log n

for n ≥ 1.

Lemma 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 4 show why Fejér sums work so well. Theorem 5 (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 6 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

\frac{1}{2π} ∫_{𝕋} |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 7 Suppose that L_{n} : 𝕋 → ℝ is continuous but that

sup_{n} \frac{1}{2π} ∫_{𝕋} |L_{n}(t)| dt = ∞.

Show that we can find a sequence of continuous functions g_{n} : 𝕋 → ℝ with |g_{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(0) − L_{n(j)} ∗ g_{k}(0)| ≤ 1. for 1 ≤ j ≤ k.

(b) 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 25.)

Theorem 5 has several very useful consequences.

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

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

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

Lemma 11 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 14).

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

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

Theorem 13 (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 14 (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 13 and 14 uses easy measure theory.)

Exercise 15 If you use Lebesgue integration, state and prove Theorems 13 and 14 for (L^{2}(𝕋), ∥ ∥_{2}).

If you use Riemann integration, extend and prove Theorems 13 and 14 for all Riemann integrable function.

Note the following complement to the Riemann-Lebesgue lemma.

Lemma 16 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 17 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 18 Suppose that a_{n} ∈ ℂ and there exists an A with |a_{n}| ≤ A|n|^{−1} for all n ≥ 1. Write

s_{n} = ∑_{r=0}^{n} a_{r}.

Show that, if

\frac{s_{0} + s_{1} + ⋯ + s_{n}}{n + 1} → s

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

Exercise 19 (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 20 If f : 𝕋 → ℂ is continuously differentiable, then

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

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

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

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

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

⟨x⟩ = x − [x].

Theorem 22 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 8 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.)

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

Theorem 23 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 the requirement of smoothness can be dropped.)

3 A Theorem of Kahane and Katznelson

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

Definition 24 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}| < ϵ.

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 25 (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 26 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 26 which contains the key idea. This is given in the next lemma.

Lemma 27 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.

4 Many Dimensions

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

f̂(n) = \frac{1}{(2π)^{m}} ∫_{𝕋} … ∫_{𝕋} 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 34 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. If you are using Lebesgue integration work with L^{∞} rather than L^{1} functions.)

Lemma 28 If we define K̃_{n} : 𝕋^{m} → ℝ by

K̃_{n}(t_{1}, t_{2}, …, t_{m}) = ∏_{j=1}^{m} K_{n}(t_{j}),

then we have the following results.

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

(ii) If η > 0, then

\frac{1}{(2π)^{m}} ∫_{|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 29 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 30 (Density of trigonometric polynomials) The trigonometric polynomials are uniformly dense in the continuous functions on 𝕋^{m}.

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

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

Lemma 33 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 34 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 35 (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 36 Prove the results from Lemma 28 to Theorem 35

Exercise 37 The extension of Lemma 17 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)

as n → ∞ (ii) (This generalises Lemma 21.) Suppose that f is a twice differentiable

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 22).

Theorem 38 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 39 (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 40 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 41 Given any K > 0 we can find a trigonometric polynomial P such that

(i) \frac{1}{2π} ∫_{𝕋} |P (t)| dt ≤ 1,

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

In our discussion of Kronecker’s theorem (Theorem 39) 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 42 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 43 (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 such that

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

for each 1 ≤ j ≤ M.

Our construction requires some preliminary results.

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

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

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

then there exist p, q ∈ ℤ \ {0} such that pq_{j} = qp_{j} for 1 ≤ j ≤ M.

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

(a) There exists a 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 46 (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 47 If M and x_{1}, x_{2}, …, x_{M} in 𝕋 are as in Lemma 46 (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 46 (ii) and 47 are more or less chosen at random and are not ‘best possible’.

A simple argument using Lemma 47 now gives Lemma 41 and we are done.

Exercise 48 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 → ∞.

5 Some simple geometry of numbers

We need the following extension of Theorem 35.

Lemma 49 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 35) 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 typically painful.

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

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

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

Theorem 51 (Minkowski) Let Γ be an open symmetric convex set in ℝ^{m} with volume V. If V > 2^{m}, 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 (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.

Lemma 52 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 51) it suffices to prove an essentially equivalent result.

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

We need the following simple but crucial result.

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

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

Lemma 55 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}} |∫_{[−π,π]^{m}} 𝕀_{Γ}(x)e^{ik.x} dx|^{2} = (2π)^{m}V.  ⋆

where 𝕀_{Γ} is the characteristic function of Γ.

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 56 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 + dm| ≤ (1 + ϵ)l^{−1}.

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

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

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

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

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

Here is another simple consequence.

Lemma 59 (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_{j} − n_{j}| ≤ l^{−1}

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

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

Theorem 60 (Legendre) Every positive integer is the sum of at most 4 squares.

Lemma 61 We cannot reduce 4 in the statement of Legendre’s theorem (Theorem 60).

We need an observation of Euler.

Lemma 62 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 63 In the lectures we will use quaternions to prove Lemma 62. Prove the equality by direct verification.

Lemma 64 Legendre’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 65 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 66 (Minkowski for general lattices) We work 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 67 Every odd prime is the sum of at most four squares.

We begin with a simple lemma.

Lemma 68 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 69 Let p, u and v be as in Lemma 68. If

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

then Λ 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 67 and with it Theorem 60.

Exercise 70 (i) Recall that if p is a prime, then the multiplicative group (ℤ_{p} \ {0}, ×) is cyclic. (This is the subject of Exercise 111.) 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.)

6 A brief look at Fourier transforms

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

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

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

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

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

Example 72 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 73 (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 74 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 75 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 section 14 (if we reach it) 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 76 We say that f is piecewise continuous if, for each R > 0, f is 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 77 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 5 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 5 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 75 (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.

7 Infinite products

Our object in the next few lectures will be to prove the following remarkable theorem of Dirichlet on primes in arithmetic progression.

Theorem 78 (Dirichlet) If a and d are strictly positive coprime integers, then there are infinitely many primes of the form a + nd with n a positive integer.

(Obviously the result must fail if a and d are not coprime.)

There exist a variety of proofs of special cases when d has particular values but, so far as I know, Dirichlet’s proof of his theorem remains, essentially, the only approachable one. In particular there is no known reasonable^{3} elementary (in the technical sense of not using analysis) proof.

Dirichlet’s method starts from an observation of Euler.

Lemma 79 If s is real with s > 1, then

∏_{\begin{matrix}p prime \\ p≤N \end{matrix}} (1 − \frac{1}{p^{s}} )^{−1} → ∑_{n=1}^{∞} \frac{1}{n^{s}}

as s → 1+.

Using this result, we get a new proof of the existence of an infinity of primes.

Theorem 80 (Euclid) There exist an infinity of primes.

This suggests that it may be worth investigating infinite products a bit more.

Definition 81 Let a_{j} ∈ ℂ. If ∏_{n=1}^{N}(1 + a_{n}) tends to a limit L as N → ∞, we say that the infinite product ∏_{n=1}^{∞}(1 + a_{n}) converges to a value L and write

∏_{n=1}^{∞}(1 + a_{n}) = L.

If the infinite product ∏_{n=1}^{∞}(1+|a_{n}|) converges, then we say that ∏_{n=1}^{∞}(1+a_{n}) is absolutely convergent.

The next result was removed from the first year of the Tripos a couple of years before I took it.

Lemma 82 Let a_{j} ∈ ℂ.

(i) ∏_{n=1}^{∞}(1 + a_{n}) is absolutely convergent if and only if ∑_{n=1}^{∞} a_{n} is.

(ii) If ∏_{n=1}^{∞}(1 + a_{n}) is absolutely convergent and 1 + a_{n} ≠ 0 for each n, then the infinite product converges and

∏_{n=1}^{∞}(1 + a_{n}) ≠ 0.

3In the sense that most reasonable people would call reasonable. Selberg produced a (technically) elementary proof which may be found in his collected works.

Exercise 83 Find a_{j} ∈ ℂ such that ∏_{n=1}^{∞}(1+a_{n}) is not absolutely convergent but is convergent to a non-zero value.

We shall only make use of absolute convergent infinite products.

Exercise 84 If ∏_{n=1}^{∞}(1 + a_{n}) is absolutely convergent and σ : ℕ → ℕ is a bijection (that is, σ is a permutation of ℕ) show that ∏_{n=1}^{∞}(1 + a_{σ(n)}) is absolutely convergent and

∏_{n=1}^{∞}(1 + a_{σ(n)}) = ∏_{n=1}^{∞}(1 + a_{n})

Whilst this is a useful result to know, we shall make no essential use of it. When we write ∑_{p prime} or ∏_{p prime} we mean the primes p to be taken in order of increasing size.

Using Lemma 82 we obtain the following strengthening of Euclid’s theorem.

Theorem 85 (Euler) ∑_{p prime} \frac{1}{p} = ∞.

Since we wish to consider infinite products of functions it is obvious that we shall need an analogue of the Weierstrass M-test for products, obvious what that analogue should be and obvious how to prove it.

Lemma 86 Suppose U is an open subset of ℂ and that we have a sequence of functions g_{n} : U → ℂ and a sequence of positive real numbers M_{n} such that M_{n} ≥ |g_{n}(z)| for all z ∈ U. If ∑_{n=1}^{∞} M_{n} converges, then ∏_{n=1}^{N}(1+g_{n}(z)) converges uniformly on U.

Later we shall need to consider ∑ n^{−s} with s complex. To avoid ambiguity, we shall take n^{−s} = exp(−s log n) where log n is the real logarithm of n.

Lemma 87 If ℜs > 1 we have

∏_{p prime}(1 − p^{−s})^{−1} = ∑_{n=1}^{∞} n^{−s}

both sides being absolutely convergent for each s and uniformly convergent for ℜs > 1 + ϵ for each fixed ϵ > 0.

We now detour briefly from the main argument to show how infinite products can be used to answer a very natural question. ‘Can we always find an analytic function with specified zeros?’ (We count multiple zeros multiply in the usual way.) Naturally we need to take account of the following fact.

Lemma 88 If z_{1}, z_{2}, … are distinct zeros of an analytic function which is not identically zero, then z_{n} → ∞ as n → ∞.

A little thought suggests the path we ought to take, though we may not see how to reach it. A way to reach the path is provided by the Weierstrass primary function E(z, m).

Definition 89 If m is a strictly positive integer

E(z, m) = (1 − z)e^{z+z^{2}/2+z^{3}/3+···+z^{m}/m}.

Lemma 90 The function E( , m) : ℂ → ℂ is analytic with a unique zero at 1. Given ϵ > 0 we can find an M such that

|1 − E(z, m)| ≤ ϵ

for all m ≥ M and |z| ≤ 1/2.

Theorem 91 (Weierstrass) If k is a positive integer and z_{1}, z_{2}, … is a sequence of non-zero complex numbers with z_{n} → ∞, then we can choose n(j) → ∞ so that

F (z) = z^{k} ∏_{j=1}^{∞} E(z/z_{j}, n(j))

is a well defined analytic function with a zero of order k at 0, and zeros at the z_{j} (multiple zeros counted multiply) and no others.

Lemma 92 If f_{1} and f_{2} are analytic functions on ℂ with the same zeros (multiple zeros counted multiply), then there exists an analytic function g such that

f_{1}(z) = e^{g(z)}f_{2}(z).

Lemma 93 If z_{1}, z_{2}, … and w_{1}, w_{2}, … are sequences of complex numbers with z_{j}, w_{j} → ∞ as j → ∞ and z_{j} ≠ w_{k} for all j, k, then there exists a meromorphic function with zeros at the z_{j} and poles at the w_{k} (observing the usual multiplicity conventions).

Exercise 94 (i) Show that we can find an A such that

|1 − E(z, m)| ≤ A|z|^{m+1}

for |z| ≤ 1/2.

(ii) If k is a positive integer and z_{1}, z_{2}, … is a sequence of non-zero complex numbers with z_{n} → ∞, then

F (z) = z^{k} ∏_{j=1}^{∞} E(z/z_{j}, j)

is a well defined analytic function with a zero of order k at 0, and zeros at the z_{j} (multiple zeros counted multiply) and no others.

Exercise 95 (It may be helpful to attack parts of this question non-rigorously first and then tighten up the argument second.)

(i) If C_{N} is the contour consisting of the square with vertices

±(N + 1/2) ± (N + 1/2)i

described anti-clockwise, show that there is a constant K such that

| cot πz| ≤ K

for all z ∈ C_{N} and all integers N ≥ 1.

(ii) By integrating an appropriate function round the contour C_{N}, or otherwise, show that, if w ∉ ℤ,

∑_{n=−N}^{n=N} \frac{1}{w − n} → π cot πw.

(iii) Is it true that, if w ∉ ℤ,

∑_{n=−M}^{n=N} \frac{1}{w − n} → π cot πw,

as M, N → ∞? Give reasons.

(iv) Show that

P (z) = z ∏_{n=1}^{∞} (1 − \frac{z^{2}}{n^{2}} )

is a well defined analytic function and that there exists an analytic function g such that

sin πz = e^{g(z)}P (z).

(v) Find a simple expression for P′(z)/P (z). [Hint: If p(z) = ∏_{j=1}^{N}(z − α_{j}), what is p′(z)/p(z)?]

Find a related expression for \frac{d}{dz} sin πz/ sin πz.

(vi) Show that

sin πz = πz ∏_{n=1}^{∞} (1 − \frac{z^{2}}{n^{2}} ) .

(vii) Find a similar expression for cos πz. (These results are due to Euler.)

Exercise 96 (This makes use of some of the techniques of the previous exercise.) (i) Show that the infinite product

g(z) = ∏_{n=1}^{∞} e^{z/n} (1 − \frac{z}{n})

exists and is analytic on the whole complex plane.

(ii) Show that

g′(z) = g(z) ∑_{n=1}^{∞} (\frac{1}{z − n} + \frac{1}{n}) .

Explain why ∑_{n=1}^{∞}(\frac{1}{z−n} + \frac{1}{n}) is indeed a well defined analytic function on ℂ \ ℤ.

(iii) By using (ii), or otherwise, show that

g(z + 1) = −Azg(z)  (∗)

for some constant A.

(iv) By considering a particular value of z, or otherwise, show that A is real and positive and

∑_{n=1}^{N} \frac{1}{n} − log N → log A

as N → ∞. Deduce the existence of Euler’s constant

γ = lim_{N→∞} (∑_{n=1}^{N} n^{−1} − log N)

and rewrite (∗) as

g(z + 1) = −e^{γ}zg(z).

(v) Find a simple expression for zg(z)g(−z). Use (∗) to show that sin πz is periodic.

8 Fourier analysis on finite Abelian groups

One of Dirichlet’s main ideas is a clever extension of Fourier analysis from its classical frame. 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 97 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 98 (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.

Definition 99 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 100 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.

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

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 |G| 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 101 Verify the statements just made.

Lemma 102 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 103 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 104 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 105 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 106 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 107 If G is a finite Abelian group and f ∈ C(G), then

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

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

Exercise 108 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

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

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

We have now done all that that is required to understand Dirichlet’s motivation. However, it seems worthwhile to make a slight detour to put ‘computational’ bones on this section by exhibiting the structure of G and Ĝ.

Lemma 109 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 110 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 111 Let p be a prime. Use Lemma 110 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 112 With the hypotheses and notation of Lemma 110, 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 113 If G is a finite Abelian group, we can find n(1), n(2), … n(m) with n(j + 1) dividing n(j) such that G is isomorphic to

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

Lemma 114 If we have two sequences n(1), n(2), … n(m) with n(j + 1) dividing n(j) and n′(1), n′(2), … n′(m′) with n′(j + 1) dividing 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 115 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). Fortunately such matters are of no importance for the present course.

9 The Euler-Dirichlet formula

Dirichlet was interested in a particular group. If d is a positive integer consider ℤ/(d) the set of equivalence classes

[m] = {r : r ≡ m mod d}

under the usual multiplication modulo d. We set

G_{d} = {[m] : m and d coprime}

and write ϕ(d) for the order of G_{d} (ϕ is called Euler’s totient function).

Lemma 116 The set G_{d} forms a finite Abelian group under standard multiplication.

The results of the previous section show that, if [a] ∈ G_{d} and we define δ_{a} : G_{d} → ℂ by

δ_{a}([a]) = 1
δ_{a}([m]) = 0 if [m] ≠ [a],

then

δ_{a} = ϕ(d)^{−1} ∑_{χ∈G_{d}} χ([a])^{∗}χ.

We now take up the proof of Dirichlet’s theorem in earnest. We shall operate under the standing assumption that a and d are positive coprime integers and our object is to show that the sequence

a, a + d, a + 2d, …, a + nd, …

contains infinitely many primes. Following Euler’s proof that there exist infinitely many primes we shall seek to prove this by showing that

∑_{p prime p=a+nd for some n} \frac{1}{p} = ∞.

Henceforward, at least in the number theory part of the course p will be a prime, ∑_{p} will mean the sum over all primes and so on.

In order to simplify our notation it will also be convenient to modify the definition of a character. From now on, we say that χ is a character if χ is a map from ℕ to ℂ such that there exists a character (in the old sense) χ̃ ∈ Ĝ_{d} with

χ(m) = χ̃([m]) if m and d are coprime
χ(m) = 0  otherwise.

We write ∑_{χ} to mean the sum over all characters and take χ_{0} to be the character with χ_{0}([m]) = 1 whenever m and d are coprime.

Lemma 117 (i) If χ is a character, then χ(m_{1}m_{2}) = χ(m_{1})χ(m_{2}) for all m_{1}, m_{2} ≥ 0.

(ii) If χ ≠ χ_{0}, then ∑_{m=k+1}^{k+d} χ(m) = 0.

(iii) If δ_{a}(m) = ϕ(d)^{−1} ∑_{χ} χ(a)^{∗}χ(m) then δ_{a}(m) = 1 when m = a + nd and δ_{a}(m) = 0 otherwise.

(iv) ∑_{p=a+nd} p^{−s} = ϕ(d)^{−1} ∑_{χ} χ(a)^{∗} ∑_{p} χ(p)p^{−s}.

Lemma 118 The sum ∑_{p=a+nd} p^{−1} diverges if ∑_{p} χ(p)p^{−s} remains bounded as s tends to 1 through real values of s > 1 for all χ ≠ χ_{0}.

We now prove a new version of Euler’s formula.

Theorem 119 (Euler-Dirichlet formula) With the notation of this section,

∏_{p}(1 − χ(p)p^{−s})^{−1} = ∑_{n=1}^{∞} χ(n)n^{−s},

both sides being absolutely convergent for ℜs > 1.

To link ∏_{p}(1−χ(p)p^{−s})^{−1} with ∑_{p} χ(p)p^{−s} we use logarithms. (If you go back to our discussion of infinite products, you will see that this is not unexpected.) However, we must, as usual, be careful when choosing our logarithm function. For the rest of the argument, log will be the function on

ℂ \ {x : x real and x ≤ 0}

defined by log(re^{iθ}) = log r + iθ [r > 0, −π < θ < π].

Lemma 120 (i) If |z| ≤ 1/2 , then | log(1 − z) + z| ≤ |z|^{2}.

(ii) If ϵ > 0, then ∑_{p} log(1−χ(p)p^{−s}) and ∑_{p} χ(p)p^{−s} converge uniformly in ℜs ≥ 1 + ϵ, whilst

|∑_{p} log(1 − χ(p)p^{−s}) + ∑_{p} χ(p)p^{−s}| ≤ ∑_{n=1}^{∞} n^{−2}.

We have thus shown that if ∑_{p} log(1 − χ(p)p^{−s}) remains bounded as s → 1+ , then ∑_{p} χ(p)p^{−s} does. Unfortunately it is not possible to equate ∑_{p} log(1 − χ(p)p^{−s}) with log(∏_{p}(1 − χ(p)p^{−s})^{−1}).

However, we can refresh our spirits by proving Dirichlet’s theorem in some special cases.

Example 121 There are an infinity of primes of the form 3n + 1 and 3n + 2.equate ∑_{p} log(1 − χ(p)p^{−s}) with log(∏_{p}(1 − χ(p)p^{−s})^{−1}).

Exercise 122 Use the same techniques to show that there are an infinity of primes of the form 4n + 1 and 4n + 3.

10 Analytic continuation of the Dirichlet functions

Dirichlet completed his argument without having to consider ∑_{n=1}^{∞} χ(n)n^{−s} for anything other than real s with s > 1. However, as we have already seen, ∑_{n=1}^{∞} χ(n)n^{−s} = L(s, χ) is defined and well behaved in ℜs > 1. Riemann showed that it is advantageous to extend the definition of analytic functions like L(s, χ) to larger domains.

There are many ways of obtaining such analytic continuations. Here is one.

Lemma 123 If f : ℝ → ℂ is bounded on ℝ and locally integrable^{5}, then

F (s) = ∫_{1}^{∞} f(x)x^{−s} dx

is a well defined analytic function on the set of s with ℜs > 1.equate ∑_{p} log(1− χ(p)p^{−s}) with log(∏_{p}(1 − χ(p)p^{−s})^{−1}).

5Riemann or Lebesgue at the reader’s choice

Lemma 124 (i) If χ ≠ χ_{0} and S(x) = ∑_{1≤m≤x} χ(m), then S : ℝ → ℂ is bounded and locally integrable. We have

∑_{n=1}^{N} χ(n)n^{−s} → s ∫_{1}^{∞} S(x)x^{−s−1} dx

as N → ∞ for all s with ℜs > 1.

(ii) If S_{0}(x) = 0 for x ≤ 0 and S_{0}(x) = ∑_{1≤m≤x} χ_{0}(m), then, writing

T_{0}(x) = S_{0}(x) − d^{−1}ϕ(d)x,

we see that T_{0} : ℝ → ℝ is bounded and locally integrable. We have

∑_{n=1}^{N} χ(n)n^{−s} → s ∫_{1}^{∞} T_{0}(x)x^{−s−1} dx + \frac{ϕ(d)s}{d(s − 1)}

as N → ∞ for all s with ℜs > 1.

Lemma 125 (i) If χ ≠ χ_{0}, there exists an function L(s, χ) analytic on {s ∈ ℂ : ℜs > 0} such that ∑_{n=1}^{∞} χ(n)n^{−s} converges to L(s, χ) on {s ∈ ℂ : ℜs > 1}.

(ii) There exists a meromorphic function L(s, χ_{0}) analytic on {s ∈ ℂ : ℜs > 0} except for a simple pole, residue ϕ(d)/d at 1 such that ∑_{n=1}^{∞} χ_{0}(n)n^{−s} converges to L(s, χ) for ℜs > 1.

Exercise 126 (i) Explain carefully why L( , χ_{0}) is defined uniquely by the conditions given.

(ii) Show that ∑_{n=1}^{∞} χ_{0}(n)n^{−s} diverges for s real and 1 ≥ s > 0.

We now take up from where we left off at the end of the previous section.

Lemma 127 (i) If ℜs > 1, then exp(− ∑_{p} log(1 − χ(p)p^{−s}) = L(s, χ). (ii) If ℜs > 1, then L(s, χ) ≠ 0. (iii) There exists a function Log L(s, χ) analytic on {s : ℜs > 1} such

that exp(Log L(s, χ)) = L(s, χ) for all s with ℜs > 1.

(iv) If χ ≠ χ_{0} and L(1, χ) ≠ 0, then Log L(s, χ)) tends to a finite limit as s → 1 through real values with s > 1.

(v) There is a fixed integer M_{χ} such that

Log L(s, χ) + ∑_{p} log(1 − χ(p)p^{−s}) = 2πM_{χ}

for all ℜs > 1.

(vi) If χ ≠ χ_{0} and L(1, χ) ≠ 0, then ∑_{p} χ(p)p^{−s} remains bounded as s → 1 through real values with s > 1.

We mark our progress with a theorem.

Theorem 128 If L(1, χ) ≠ 0 for all χ ≠ χ_{0} then there are an infinity of primes of the form a + nd.

Since it is easy to find the characters χ in any given case and since it is then easy to compute ∑_{n=1}^{N} χ(n)n^{−1} and to estimate the error ∑_{n=N+1}^{∞} χ(n)n^{−1} to sufficient accuracy to prove that L(1, χ) = ∑_{n=1}^{∞} χ(n)n^{−1} ≠ 0, it now becomes possible to prove Dirichlet’s theorem for any particular coprime a and d.

Exercise 129 Choose a and d and carry out the program just suggested.

However, we still need to show that the theorem holds in all cases.

11 L(1, χ) is not zero

Our first steps are easy.

Lemma 130 (i) If s is real and s > 1, then

∏_{χ} L(s, χ) = exp(− ∑_{p} ∑_{χ} log(1 − χ(p)p^{−s}).

(ii) If s is real and s > 1, then ∏_{χ} L(s, χ) is real and ∏_{χ} L(s, χ) ≥ 1. (iii) ∏_{χ} L(s, χ) ↛ 0 as s → 1.

Lemma 131 (i) There can be at most one character χ with L(1, χ) = 0. (ii) If a character χ takes non-real values then L(1, χ) ≠ 0.

We have thus reduced the proof of Dirichlet’s theorem to showing that if χ is a character with χ ≠ χ_{0} which only takes the values 1, −1 and 0, then L(1, χ) ≠ 0. There are several approaches to this problem, but none are short and transparent. We use a proof of de la Vallée Poussin which is quite short, but not, I think, transparent.

Lemma 132 Suppose that the character χ ≠ χ_{0} and only takes the values 1, −1 and 0. Set

ψ(s) = \frac{L(s, χ)L(s, χ_{0})}{L(2s, χ_{0})}.

(i) The function ψ is well defined and meromorphic for ℜs > \frac{1}{2}. It is analytic except, possibly, for a simple pole at 1.

(ii) If L(1, χ) = 0, then 1 is a removable singularity and ψ is analytic everywhere on \{s : ℜs > \frac{1}{2}\}.

(iii) We have ψ(s) → 0 as s → \frac{1}{2} through real values of s with s ≥ \frac{1}{2}.

Lemma 133 We adopt the hypotheses and notation of Lemma 132. If ℜs > 1, then the following is true.

(i) ψ(s) = ∏_{χ(p)=1} \frac{1 + p^{−s}}{1 − p^{−s}} .

(ii) We can find subsets Q_{1} and Q_{2} of ℤ such that

∏_{χ(p)=1}(1 + p^{−s}) = ∑_{n∈Q_{1}} n^{−s}
∏_{χ(p)=1}(1 − p^{−s})^{−1} = ∑_{n∈Q_{2}} n^{−s}.

(iii) There is a sequence of real positive numbers a_{n} with a_{1} = 1 such that

ψ(s) = ∑_{n=1}^{∞} a_{n}n^{−s}.

Lemma 134 We adopt the hypotheses and notation of Lemmas 132 and 133. (i) If ℜs > 1, then

ψ^{(m)}(s) = ∑_{n=1}^{∞} a_{n}(− log n)^{m}n^{−s}.

(ii) If ℜs > 1, then (−1)^{m}ψ^{(m)}(s) > 0.

(iii) If ψ has no pole at 1, then, if ℜs_{0} > 1 and |s − s_{0}| < ℜs_{0} − 1/2, we have

ψ(s) = ∑_{m=0}^{∞} \frac{ψ^{(m)}(s_{0})}{m!}(s − s_{0})^{m}.

(iv) If ψ has no pole at 1, then ψ(s) ↛ 0 as s → \frac{1}{2} through real values of s with s ≥ \frac{1}{2}.

We have proved the result we set out to obtain.

Lemma 135 If a character χ ≠ χ_{0} only takes real values then L(1, χ) ≠ 0.

Theorem 136 If χ ≠ χ_{0}, then L(1, χ) ≠ 0.

We have thus proved Theorem 78. If a and d are strictly positive coprime integers, then there are infinitely many primes of the form a + nd with n a positive integer.

12 Chebychev and the distribution of primes

On the strength of numerical evidence, Gauss was led to conjecture that the number π(n) of primes less than n was approximately n/ log n. The theorem which confirms this conjecture is known as the prime number theorem. The first real progress in this direction was due to Chebychev^{6}. We give his results, not out of historical piety, but because we shall make use of them in our proof of the prime number theorem. (Note the obvious conventions that n is an integer with n ≥ 1, ∏_{n<p≤2n} means the product over all primes p with n < p ≤ 2n and so on. It is sometimes useful to exclude small values of n.)

Lemma 137 (i) 2^{n} < \binom{2n}{n} < 2^{2n}.

(ii) \binom{2n}{n} divides ∏_{p<2n} p^{[(log 2n)/(log p)]} and ∏_{n<p≤2n} p divides \binom{2n}{n}.

(iii) We have π(2n) > (log 2)n/(log 2n).

(iv) There exists a constant A > 0 such that π(n) ≥ An(log n)^{−1}.

(v) There exists a constant B′ such that ∑_{p≤n} log p ≤ B′n.

(vi)There exists a constant B such that π(n) ≤ Bn(log n)^{−1}.

We restate the main conclusions of Lemma 137.

Theorem 138 (Chebychev) There exist constants A and B with 0 < A ≤ B such that

An(log n)^{−1} ≤ π(n) ≤ Bn(log n)^{−1}.

Riemann’s approach to the prime number theorem involves considering θ(n) = ∑_{p≤n} log p rather than π(n).

Lemma 139 Let Q be a set of positive integers and write α(n) = ∑_{q∈Q,q≤n} 1 and β(n) = ∑_{q∈Q,q≤n} log q.

(i) There exist constants A and B with 0 < A ≤ B such that

An(log n)^{−1} ≤ α(n) ≤ Bn(log n)^{−1}.

if and only if there exist constants A′ and B′ with 0 < A ≤ B such that

A′n ≤ β(n) ≤ B′n.

(ii) We have n^{−1}(log n)α(n) → 1 as n → ∞ if and only if n^{−1}β(n) → 1 as n → ∞.

Lemma 140 If n^{−1}θ(n) → 1 as n → ∞, then n^{−1}(log n)π(n) → 1 as n → ∞.

6His preferred transliteration seems to have been Tchebycheff, but he has been overruled.

13 The prime number theorem

We start by recalling various facts about the Laplace transform.

Definition 141 If a is a real number, let us write E_{a} for the collection of piecewise continuous functions F : ℝ → ℂ such that F (t) = 0 for all t < 0 and F (t)e^{−at} → 0 as t → ∞. If F ∈ E_{a}, we define the Laplace transform of F by

(LF)(z) = ∫_{−∞}^{∞} F (t) exp(−zt) dt

for ℜz > a.

Lemma 142 If F ∈ E_{a}, then (LF)(z) is well defined.

Lemma 143 (i) If F ∈ E_{a}, then (LF)(z) analytic on {z ∈ ℂ : ℜz > a}.

(ii) We define the Heaviside function H by writing H(t) = 0 for t < 0 and H(t) = 1 for t ≥ 0. If a ∈ ℝ and b ≥ 0 set H_{a,b}(t) = H(t − b)e^{at}. Then H_{a,b} ∈ E_{a} and LH_{a,b}(z) can be extended to a meromorphic function on ℂ with a simple pole at a.

Exercise 144 (Uses Exercise 77.) Let F, G ∈ E_{a} for some a ∈ ℝ.

(i) Suppose that there exists a b > a such that (LF)(z) = (LG)(z) for all z with ℜz = b. Show that F = G.

(ii) Suppose that there exist distinct z_{n} ∈ ℂ with ℜz_{n} > a [n ≥ 0] such that z_{n} → z_{0} and (LF)(z_{n}) = (LG)(z_{n}) [n ≥ 0]. Show that F = G.

Engineers are convinced that the converse to Lemma 143 (i) holds in the sense that if F ∈ E_{a} has a Laplace transform f which can be extended to a function f̃ analytic on {z ∈ ℂ : ℜz > b} [a, b real, a ≥ b], then F ∈ E_{b}. Unfortunately, this is not true, but it represents a good heuristic principle to bear in mind in what follows. Number theorists use the Mellin transform

MF (z) = ∫_{0}^{∞} F (t)t^{z−1} dt

in preference to the Laplace transform but the two transforms are simply related.

Exercise 145 Give the relation explicitly.

Riemann considered the two functions

Φ(s) = ∑_{p} p^{−s} log p

and the Riemann zeta function

ζ(s) = ∑_{n=1}^{∞} n^{−s}.

Both of these functions are defined for ℜs > 1 but Riemann saw that they could be extended to analytic functions over a larger domain.

The next lemma is essentially a repeat of Lemmas 124 (ii) and 125 (ii).

Lemma 146 (i) Let S_{0}(x) = 0 for x ≤ 0 and S_{0}(x) = ∑_{1≤m≤x} 1. If

T_{0}(x) = S_{0}(x) − x,

then T_{0} is bounded and locally integrable. We have

∑_{n=1}^{N} n^{−s} → s ∫_{1}^{∞} T_{0}(x)x^{−s−1} dx + \frac{s}{s − 1}

as N → ∞ for all s with ℜs > 1.

(ii) There exists a meromorphic function ζ analytic on {s ∈ ℂ : ℜs > 0} except for a simple pole, residue 1 at 1 such that ∑_{n=1}^{∞} n^{−s} converges to ζ(s) for ℜs > 1.

(iii) If ℜs > 1, then

∑_{p≤N} \frac{log p}{p^{s}} → s ∫_{1}^{∞} θ(x)x^{−s−1} dx

as N → ∞.

The use of s rather than z goes back to Riemann. Riemann showed that ζ can be extended to a meromorphic function over ℂ, but we shall not need this.

How does this help us study Φ?

Lemma 147 (i) We have ∏_{p<N}(1−p^{−s})^{−1} → ζ(s) uniformly for ℜs > 1+δ whenever δ > 0.

(ii) We have

\frac{ζ′(s)}{ζ(s)} = − ∑_{p} \frac{log p}{p^{s} − 1}

for all ℜs > 1.

(iii) We have

Φ(s) = −\frac{ζ′(s)}{ζ(s)} − ∑_{p} \frac{log p}{(p^{s} − 1)p^{s}}

for all ℜs > 1.

(iv) The function Φ can be analytically extended to a meromorphic function on \{s : ℜs > \frac{1}{2}\}. It has a simple pole at 1 with residue 1 and simple poles at the zeros of ζ but nowhere else.

The next exercise is long and will not be used later but is, I think, instructive.

Exercise 148 (i) Show by grouping in pairs that ∑_{n=1}^{∞}(−1)^{n−1}n^{−s} converges to an analytic function g(s) in the region {s : ℜs > 0}.

(ii) Find A and B such that g(s) = Aζ(s)+B2^{−s}ζ(s) for all ℜs > 1. Why does this give another proof that ζ can be extended to an analytic function on {s : ℜs > 0}?

(iii) Show that g(1/2) ≠ 0 and deduce that ζ(1/2) ≠ 0.

(iv) By imitating the arguments of Lemma 147, show that we we can find an analytic function G defined on {s : ℜs > 1/3} such that

Φ(s) = −\frac{ζ′(s)}{ζ(s)} − Φ(2s) − G(s).

Deduce that Φ can be extended to a meromorphic function on {s : ℜs > 1/3}. (v) Show, using (iii), that Φ has a pole at 1/2. (vi) Show that the assumption that | ∑_{p<N} log p−N| ≤ AN^{1/2−ϵ} for some

ϵ > 0 and A > 0 and all large enough N leads to the conclusion that Φ can be analytically extended from {s : ℜs > 1} to an everywhere analytic function on {s : ℜs > 1/2 − ϵ}.

(vii) Deduce that if ϵ > 0 and A > 0

| ∑_{p<N} log p − N| ≥ AN^{1/2−ϵ} for infinitely many values of N.

It is well known that Riemann conjectured that ζ has no zeros in {s : ℜs > 1/2} and that his conjecture is the most famous open problem in mathematics. The best we can do is to follow Hadamard and de la Vallée Poussin and show that ζ has no zero on {s : ℜs = 1}. Our proof makes use of the slightly unconventional convention that if h and g are analytic in a neighbourhood of w, g(w) ≠ 0 and h(z) = (z − w)^{k}g(z), then h has a zero of order k at w. (The mild unconventionality arises when k = 0.)

Lemma 149 Suppose that ζ has a zero of order μ at 1 + iα and a zero of order ν at 1 + 2iα with α real and α > 0. Then the following results hold.

(i) ζ has a zero of order μ at 1 − iα and a zero of order ν at 1 − 2iα.

(ii) As ϵ → 0 through real positive values of ϵ

ϵΦ(1 + ϵ ± iα) → −μ
ϵΦ(1 + ϵ ± 2iα) → −ν
ϵΦ(1 + ϵ) → 1.

(iii) If s = 1 + ϵ with ϵ real and positive, then

0 ≤ ∑_{p} p^{−s} log p(e^{(iα log p)/2} + e^{−(iα log p)/2})^{4}

= Φ(s + 2iα) + Φ(s − 2iα) + 4(Φ(s + iα) + Φ(s − iα)) + 6Φ(s).

(iv) We have 0 ≤ −2ν − 8μ + 6.

Theorem 150 If ℜs = 1, then ζ(s) ≠ 0.

We note the following trivial consequence.

Lemma 151 If we write

T (s) = \frac{ζ′(s)}{ζ(s)} − (s − 1)^{−1},

then given any R > 0 we can find a δ(R) such that T has no poles in

{z : ℜz ≥ 1 − δ(R), |ℑz| ≤ R}.

We shall show that the results we have obtained on the behaviour of ζ suffice to show that

∫_{1}^{X} \frac{θ(x) − x}{x^{2}} dx

tends to a finite limit as X → ∞. The next lemma shows that this is sufficient to give the prime number theorem.

Lemma 152 Suppose that β : [1, ∞) → ℝ is an increasing (so integrable) function.

(i) If λ > 1, y > 1 and y^{−1}β(y) > λ, then

∫_{y}^{λy} \frac{β(x) − x}{x^{2}} dx ≥ A(λ)

where A(λ) is a strictly positive number depending only on λ.

(ii) If

∫_{1}^{X} \frac{β(x) − x}{x^{2}} dx

tends to limit as X → ∞, then x^{−1}β(x) → 1 as x → ∞.

We need a couple of further preliminaries. First we note a simple consequence of the Chebychev estimates (Theorem 138).

Lemma 153 There exists a constant 1 > K > 0 such that

\frac{|θ(x) − x|}{x} ≤ K

for all x sufficiently large.

Our second step is to translate our results into the language of Laplace transforms. (It is just a matter of taste whether to work with Laplace transforms or Mellin transforms.)

Lemma 154 Let f(t) = θ(e^{t})e^{−t} −1 for t ≥ 0 and f(t) = 0 otherwise. Then

Lf(z) = ∫_{−∞}^{∞} f(t)e^{−tz} dt

is well defined and

Lf(z) = \frac{Φ(z + 1)}{z + 1} − \frac{1}{z}

for all ℜz > 0.

The statement ∫_{1}^{∞}(θ(x) − x)/x^{2} dx convergent is equivalent to the statement that ∫_{−∞}^{∞} f(t) dt converges.

We have reduced the proof of the prime number theorem to the proof of the following lemma.

Lemma 155 Suppose Ω is an open set with Ω ⊇ {z : ℜz ≥ 0}, F : Ω → ℂ is an analytic function and f : [0, ∞] → ℝ is bounded locally integrable function such that

F (z) = Lf(z) = ∫_{0}^{∞} f(t)e^{−tz} dt

for ℜz > 0. Then ∫_{0}^{∞} f(t) dt converges.

This lemma and its use to prove the prime number theorem are due to D. Newman. (A version will be found in [1].)

14 The Fourier transform and Heisenberg’s inequality

In this section we return to the Fourier transform on ℝ. We follow a slightly different path to that mapped out in Section 6. I shall state results using Lebesgue measure but students using Riemann integration will find appropriate modifications as exercises.

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

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

Exercise 157 If I prove Lemma 156 I shall do so by setting up a differential equation. Obtain Lemma 156 by complex variable techniques.

We use the following neat formula.

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

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

Exercise 159 (For those using Riemann integration. You will need to refer back to the exercises in Section 6.) Suppose that f and g are continuous and 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 158 we obtain a nice pointwise inversion result.

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

Exercise 161 (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 162 Suppose that f satisfies the conditions of Theorem 160 (if you use Lebesgue integration) or Exercise 161 (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−)).

Lemma 163 (Parseval’s equality) If f and f̂ are continuous and integrable and ˆ f̂(t) = 2πf(−t) for all t then

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

(A less ad hoc version of Parseval’s equality is given in Exercise 164 (v).)

Exercise 164 (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 158 show that

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

for all f ∈ S.

(iii) 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.)

(iv) 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.

(v) 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.

(vi) (Parseval’s equality) Show that, if we work in L^{2}

∫_{ℝ} Gf(λ)(Gg)^{∗}(λ) dλ = ∫_{ℝ} f(t)g(t)^{∗} dt.

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 165 (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 166 Write down explicit conditions for Theorem 165.

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

15 The Poisson formula

The following remarkable observation is called Poisson’s formula.

Theorem 167 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 168 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 167.

Exercise 169 (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} = ∑_{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 170 Suppose f satisfies the conditions of Lemma 168. 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 171 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 172 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 173 (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 172 is best possible.

Lemma 174 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 175 In Lemma 174 show that we can take f ∈ S where S is the class discussed in Exercise 164.

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

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

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

16 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 [4] and Katznelson [6] would be my first choice for introductions and this course draws on both. If you wish to think about applications, the obvious text is that of Dym and McKean [3]. 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 [10] 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 [5] is splendid light reading.

There is an excellent treatment of Dirichlet’s theorem and much more in Davenport’s Multiplicative Number Theory [2]. [The changes between the first and second editions are substantial but do not affect that part which deals with material in this course.] If you wish to know more about the Riemann zeta-function you can start with [9].

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

References

[1] J. Bak and D. J. Newman Complex Analysis Springer, New York, 1982.

[2] H. Davenport Multiplicative Number Theory (2nd Edition), Springer, New York, 1980.

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

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

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

[6] Y. Katznelson An Introduction to Harmonic Analysis Wiley, 1963. [There is a CUP reprint]

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

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

[9] S. J. Patterson An Introduction to the Theory of the Riemann zetafunction CUP, 1988.

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