\documentclass[12pt,a4paper]{article}
\usepackage{amssymb,amsmath,amsxtra}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{convention}[theorem]{Convention}
\newtheorem{pretheorem}[theorem]{Pretheorem}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\card}{\operatorname{card}}
\newcommand{\Int}{\operatorname{Int}}
\newcommand{\Log}{\operatorname{Log}}
\newcommand{\sinc}{\operatorname{sinc}}
\begin{document}
\title{An Introduction to Fourier Analysis\\Part III}
\author{T.~W.~K\"{o}rner}
\maketitle
\begin{footnotesize}
\noindent
{\bf 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 {\bf 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 \LaTeX2e and should be accessible
in tex, dvi, ps and pdf form from my home
page
{\tt http://www.dpmms.cam.ac.uk/\~{}twk/}
together with a list of corrections.

My e-mail address is \verb+twk@dpmms.cam.ac.uk+.
\end{footnotesize}

\tableofcontents
\section{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~\ref{S;prime number}, I am not sure that
I will I have time for the final two sections.

\emph{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.
          
\section{Fourier series on the circle} We work on the circle
${\mathbb T}={\mathbb R}/2\pi{\mathbb Z}$ (that is on
the interval $[0,2\pi]$ with the two ends $0$ and $2\pi$
identified). If $f:{\mathbb T}\rightarrow{\mathbb C}$
is integrable\footnote{That is 
to say Lebesgue integrable
or Riemann integrable according to the reader's
background.} we write
\[\hat{f}(n)=\frac{1}{2\pi}\int_{\mathbb T}f(t)\exp -int\,dt.\]
We shall see (Lemma~\ref{Unique}) that $f$ is uniquely
determined by its Fourier coefficients $\hat{f}(n)$.
Indeed it is clear that there is a `natural identification'
(where natural is deliberately used in a vague sense)
\[f(t)\sim\sum_{r=-\infty}^{\infty}\hat{f}(r)\exp irt.\]
However, we shall also see that, even when $f$ is continuous,
$\sum_{r=-\infty}^{\infty}\hat{f}(r)\exp irt$ may
fail to converge at some points $t$.

Fej\'{e}r discovered that, although
\[S_{n}(f,t)=\sum_{r=-n}^{n}\hat{f}(r)\exp irt\]
may behave badly as $n\rightarrow\infty$, the
average
\[\sigma_{n}(f,t)=(n+1)^{-1}\sum_{m=0}^{n}S_{m}(f,t)
=\sum_{r=-n}^{n}\frac{n+1-|r|}{n+1}\hat{f}(r)\exp irt\]
behaves much better. (We call $\sigma_{n}(f,t)$ the
Fej\'{e}r sum. We also write $S_{n}(f,t)=S_{n}(f)(t)$
and $\sigma_{n}(f,t)=\sigma_{n}(f)(t)$.)

\begin{exercise} Let $a_{1}$, $a_{2}$, \dots be a sequence
of complex numbers. 

(i) Show that, if $a_{n}\rightarrow a$, then
\[\frac{a_{1}+a_{2}+\dots+a_{n}}{n}\rightarrow a\]
as $n\rightarrow\infty$.

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

(iii) By taking an appropriate sequence of $0$s and $1$s
or otherwise find a bounded sequence $a_{n}$ such that
$(a_{1}+a_{2}+\dots+a_{n})/n$ does not tend to a limit
as $n\rightarrow\infty$.
\end{exercise}

In what follows we define
\[f*g(t)=\frac{1}{2\pi}\int_{\mathbb T}f(t-s)g(s)\,ds\]
(for appropriate $f$ and $g$).
\begin{lemma} If $f$ is integrable we have
\begin{align*}
S_{n}(f)&=f*D_{n}\\
\sigma_{n}(f)&=f*K_{n}.
\end{align*}
where
\begin{align*}
D_{n}(t)&=\frac{\sin((n+\tfrac{1}{2})t)}{\sin(\tfrac{1}{2}t)}\\
K_{n}(t)&=\frac{1}{n+1}\left(\frac{\sin(\tfrac{n+1}{2}t)}
{\sin(\tfrac{1}{2}t)}\right)^{2}
\end{align*}
for $t\neq 0$.
\end{lemma}

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

\begin{lemma} (i) 
${\displaystyle \frac{1}{2\pi}\int_{\mathbb T}D_{n}(t)\, dt=1}$.

(ii) If $t\neq \pi$, then $D_{n}(t)$ does not tend to
a limit as $n\rightarrow\infty$.

(iii) There is a constant $A>0$ such that
\[\frac{1}{2\pi}\int_{\mathbb T}|D_{n}(t)|\, dt\geq A\log n\] 
for $n\geq 1$.
\end{lemma}

\begin{lemma}\label{Fejer positive}
(i) $\displaystyle{\frac{1}{2\pi}\int_{\mathbb T}K_{n}(t)\, dt=1}$.

(ii) If $\eta>0$, then $K_{n}\rightarrow 0$ uniformly
for $|t|\geq \eta$
as $n\rightarrow\infty$.

(iii) $K_{n}(t)\geq 0$ for all $t$.
\end{lemma}

The properties set out in Lemma~\ref{Fejer positive}
show why Fej\'{e}r sums work so well.

\begin{theorem}~\label{Fejer convergence} 
(i) If $f:{\mathbb T}\rightarrow{\mathbb C}$
is integrable and $f$ is continuous at $t$, then
\[\sigma_{n}(f,t)\rightarrow f(t)\]
as $n\rightarrow\infty$.

(ii) If $f:{\mathbb T}\rightarrow{\mathbb C}$
is continuous, then
\[\sigma_{n}(f)\rightarrow f\]
uniformly as $n\rightarrow\infty$.
\end{theorem}
\begin{exercise} Suppose that
$L_{n}:{\mathbb T}\rightarrow{\mathbb R}$
is continuous (if you know Lebesgue theory you
merely need integrable) and

(A) ${\displaystyle \frac{1}{2\pi}\int_{\mathbb T}L_{n}(t)\, dt=1}$,

(B) If $\eta>0$, then $L_{n}\rightarrow 0$ uniformly
for $|t|\geq \eta$
as $n\rightarrow\infty$,

(C) $L_{n}(t)\geq 0$ for all $t$.

(i) Show that, if $f:{\mathbb T}\rightarrow{\mathbb C}$
is integrable and $f$ is continuous at $t$, then
\[L_{n}*f(t)\rightarrow f(t)\]
as $n\rightarrow\infty$.

(ii) Show that, if $f:{\mathbb T}\rightarrow{\mathbb C}$
is continuous, then
\[L_{n}*f\rightarrow f\]
uniformly as $n\rightarrow\infty$.

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

(C') There exists a constant $A>0$ such that
\[\frac{1}{2\pi}\int_{\mathbb T}|L_{n}(t)|\, dt\leq A\]
in parts (i) and (ii). [You need only give the proof in
one case and say that the other is `similar'.]
\end{exercise}
\begin{exercise} Suppose that
$L_{n}:{\mathbb T}\rightarrow{\mathbb R}$
is continuous but that
\[\sup_{n}\frac{1}{2\pi}
\int_{\mathbb T}|L_{n}(t)|\, dt=\infty.\]
Show that we can find a sequence of continuous functions
$g_{n}:{\mathbb T}\rightarrow{\mathbb R}$ with
$|g_{n}(t)|\leq 1$ for all $t$, $L_{n}*g_{n}(0)\geq 0$
for all $n$ and 
\[\sup_{n}L_{n}*g_{n}(0)=\infty.\]

(i) If you know some functional analysis deduce the
existence of a continuous function $f$ such that
\[\sup_{n}L_{n}*f(0)=\infty.\]

(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)<\dots<n(k)$, a continuous function
$g_{k}$ and a real number $\epsilon(k)$ with
$2^{-k}>\epsilon(k)>0$.
Show that there is an $\epsilon(k+1)$ with
$\epsilon(k)/2>\epsilon(k+1)>0$ such that
whenever $g$ is a continuous function with
$\|g-g_{k}\|_{\infty}<2\epsilon(k+1)$
we have $|L_{n(j)}*g(0)-L_{n(j)}*g_{k}(0)|\leq 1$.
for $1\leq j\leq 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}\|_{\infty}\leq\epsilon(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\rightarrow\infty$. (We shall obtain a stronger result
later in Theorem~\ref{Kahane and Katznelson}.)
\end{exercise}

Theorem~\ref{Fejer convergence} has several very useful 
consequences.
\begin{theorem}[Density of trigonometric polynomials]%
\label{density} The trigonometric polynomials are
uniformly dense in the continuous functions on ${\mathbb T}$.
\end{theorem}
\begin{lemma}[Riemann-Lebesgue lemma] If $f$ is an
integrable function on ${\mathbb T}$, then
$\hat{f}(n)\rightarrow 0$ as $|n|\rightarrow\infty$.
\end{lemma}
\begin{theorem}[Uniqueness]\label{Unique}
If $f$ and $g$ are
integrable functions on ${\mathbb T}$ with 
$\hat{f}(n)=\hat{g}(n)$ for all $n$, then $f=g$.
\end{theorem}
\begin{lemma} If $f$ is an
integrable function on ${\mathbb T}$ and
$\sum_{j}|\hat{f}(j)|$ converges, then $f$ is continuous
and $f(t)=\sum_{j}\hat{f}(j)\exp ijt$.
\end{lemma}
As a preliminary to the next couple of results we
need the following temporary lemma (which will be immediately
superseded by Theorem~\ref{Parseval}).
\begin{lemma}[Bessel's inequality]
If $f$ is
a continuous function on ${\mathbb T}$, then
\[\sum_{n=-\infty}^{\infty}|\hat{f}(n)|^{2}
\leq\frac{1}{2\pi}\int_{\mathbb T}|f(t)|^{2}\,dt.\]
\end{lemma}
\begin{theorem} [Mean square convergence]%
\label{mean square} If $f$ is
a continuous function on ${\mathbb T}$, then
\[
\frac{1}{2\pi}\int_{\mathbb T}
| f(t)-S_{n}(f,t) |^{2}\,dt\rightarrow 0
\]
as $n\rightarrow\infty$.
\end{theorem}
\begin{theorem} [Parseval's Theorem]\label{Parseval} 
If $f$ is
a continuous function on ${\mathbb T}$, then
\[\sum_{n=-\infty}^{\infty}|\hat{f}(n)|^{2}
=\frac{1}{2\pi}\int_{\mathbb T}|f(t)|^{2}\,dt.\]
More generally, if $f$ and $g$ are continuous
\[\sum_{n=-\infty}^{\infty}\hat{f}(n)\hat{g}(n)^{*}
=\frac{1}{2\pi}\int_{\mathbb T}f(t)g(t)^{*}\,dt.\]
\end{theorem}


(The extension to all $L^{2}$ functions of Theorems~\ref{mean square}
and~\ref{Parseval} uses easy measure
theory.)
\begin{exercise} 
If you use Lebesgue integration, 
state and prove Theorems~\ref{mean square}
and~\ref{Parseval} for $(L^{2}({\mathbb T}),\|\ \|_{2})$.

If you use Riemann integration, extend and prove
Theorems~\ref{mean square} and~\ref{Parseval}
for all Riemann integrable function.
\end{exercise}
Note the following complement to the Riemann-Lebesgue lemma.
\begin{lemma} If 
$\kappa(n)\rightarrow \infty$ as $n\rightarrow\infty$,
then we can find a continuous function $f$
such that $\limsup_{n\rightarrow\infty}\kappa(n)\hat{f}(n)=\infty$.
\end{lemma}

The proof of the next result is perhaps more interesting
than the result itself.
\begin{lemma}\label{pointwise}
Suppose that $f$ is an
integrable function on ${\mathbb T}$ such that there
exists an $A$ with $|\hat{f}(n)|\leq A|n|^{-1}$ for
all $n\neq 0$. If $f$ is continuous at $t$, then
$S_{n}(f,t)\rightarrow f(t)$ as $n\rightarrow\infty$.
\end{lemma}
\begin{exercise} Suppose that $a_{n}\in{\mathbb C}$
and there
exists an $A$ with $|a_{n}|\leq A|n|^{-1}$ for
all $n\geq 1$. Write
\[s_{n}=\sum_{r=0}^{n}a_{r}.\]
Show that, if
\[\frac{s_{0}+s_{1}+\dots+s_{n}}{n+1}\rightarrow s\]
as $n\rightarrow\infty$, then $s_{n}\rightarrow s$
as $n\rightarrow\infty$. (Results like this are
called Tauberian theorems.)

\end{exercise}
\begin{exercise} (i)
Suppose that $f:[-\pi,\pi)\rightarrow{\mathbb R}$
is increasing and bounded. Write $f(\pi)=\lim_{t\rightarrow 0}
f(\pi -t)$.
Show that
\[\int_{-\pi}^{\pi}f(t)\exp it\, dt=
\int_{0}^{\pi}(f(t)-f(t-\pi))\exp it\, dt\]
and deduce that $|\hat{f}(1)|\leq 
(f(\pi)-f(-\pi))/2\leq(f(\pi)-f(-\pi))$.

(ii) Under the assumptions of (i) show that
\[|\hat{f}(n)|\leq (f(\pi)-f(-\pi))/|n|\]
for all $n\neq 0$.

(iii) (Dirichlet's theorem) Suppose that $g=f_{1}-f_{2}$
where $f_{k}:[-\pi,\pi)\rightarrow{\mathbb R}$
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)\rightarrow f(t)$ as $n\rightarrow\infty$. 
\end{exercise}

Most readers will already be aware of the next fact.
\begin{lemma} If $f:{\mathbb T}\rightarrow{\mathbb C}$
is continuously differentiable, then
\[(f')\hat{\ }(n)=in\hat{f}(n).\]
\end{lemma}
This means that Lemma~\ref{pointwise} applies,
but we can do better.
\begin{lemma}\label{once is}
If $f:{\mathbb T}\rightarrow{\mathbb C}$
is continuously differentiable, then
\[\sum_{n=-\infty}^{\infty}|\hat{f}(n)|<\infty.\]
\end{lemma}

Here is a beautiful application due to Weyl
of Theorem~\ref{density}. If $x$ is real,
let us write $\langle x\rangle$ for the fractional part
of $x$, that is, let us write
\[\langle x\rangle=x-[x].\]
\begin{theorem}\label{Weyl} If $\alpha$ is an irrational
number and $0\leq a\leq b\leq 1$, then
\[\frac{\card\{1\leq n\leq N \mid \langle n\alpha\rangle
\in [a,b]\}}{N}
\rightarrow b-a\]
as $N\rightarrow\infty$. The result is false
if $\alpha$ is rational.
\end{theorem}
(Of course this result may be deduced from the ergodic
theorem and Theorem~\ref{density} 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.
\begin{theorem} Among all smooth closed
non-self-intersecting curves of given length, 
the one which encloses greatest area is the circle.
\end{theorem}
(Reasonably simple arguments show that the requirement of smoothness
can be dropped.) 
\section{A Theorem of Kahane and Katznelson}
We need to recall (or learn) the following definition.
\begin{definition} A subset $E$ of ${\mathbb T}$
has (Lebesgue) measure zero if, given $\epsilon>0$,
we can find intervals $I_{j}$ of length $|I_{j}|$
such that $\bigcup_{j=1}^{\infty}I_{j}\supseteq E$
but $\sum_{j=1}^{\infty}|I_{j}|<\epsilon$.
\end{definition}

There is a deep and difficult theorem of Carleson
which tells us that if $f:{\mathbb T}\rightarrow{\mathbb C}$
is continuous (or even $L^{2}$), then the set
\[E=\{t\in {\mathbb T}\mid S_{n}(f,t)\nrightarrow f(t)
\ \text{as $n\rightarrow\infty$}\}\]
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.

\begin{theorem}[Kahane and Katznelson]%
~\label{Kahane and Katznelson} Given
any  subset $E$ of ${\mathbb T}$ with
measure zero, we can find a continuous function $f$
such that
\[\limsup_{n\rightarrow\infty}|S_{n}(f,t)|\rightarrow\infty\]
for all $t\in E$.
\end{theorem}

The theorem follows relatively simply from its
`finite version'.
\begin{lemma}\label{Finite Katznelson}
Given any $K>0$, we can find a $\epsilon(K)>0$
such that if $J_{1}$, $J_{2}$, \dots $J_{N}$ is any
finite collection of intervals with 
$\sum_{r=1}^{N}|J_{r}|<\epsilon(K)$
we can find a trigonometric polynomial $P$
such that $\|P\|_{\infty}\leq 1$ but
\[\sup_{n}|S_{n}(P,t)|\geq K\]
for all $t\in \bigcup_{r=1}^{N}J_{r}$.
\end{lemma}

It is the proof of Lemma~\ref{Finite Katznelson}
which contains the key idea. This is given
in the next lemma.
\begin{lemma} Let us define $\log z$ on
${\mathbb C}\setminus\{x\in{\mathbb R}\,:\, x\leq 0\}$
so that $\log x$ is real when $x$ is real and positive.
Suppose that $1>\delta>0$ and that 
$\theta_{1},\ \theta_{2},\ \dots,\ \theta_{N}\in{\mathbb R}$.
If we set
\[\phi(z)=\log\left(N^{-1}\sum_{n=1}^{N}
\frac{1+\delta}{1+\delta-ze^{-i\theta_{n}}}\right),\]
then $\phi$ is a well defined analytic function
on $\{z\mid |z|<1+\delta/2\}$ such that

(i) $|\Im \phi(z)|<\pi$ for all $|z|<1+\delta/2$,

(ii) $\phi(0)=0$,

(iii) $|\Re \phi(e^{i\theta})|\geq \log(\delta^{-1}/4N)$
for all $|\theta-\theta_{n}|\leq\delta/2$
and $1\leq n\leq N$.
\end{lemma}
\section{Many Dimensions} The extension of these
ideas to higher dimensions can be either trivial
or very hard. If $f:{\mathbb T}^{m}\rightarrow{\mathbb C}$
we define
\[\hat{f}({\mathbf n})=\frac{1}{(2\pi)^{m}}
\int_{\mathbb T}\dots \int_{\mathbb T}
f({\mathbf t})\exp(-i{\mathbf n}.{\mathbf t})
\,dt_{1}\dots dt_{m}.\]
Very little is known about the convergence of
\[\sum_{u^{2}+v^{2}\leq N}\hat{f}(u,v)\exp(i(ux+vy))\]
as $N\rightarrow\infty$ even when $f$ is continuous.
(Of course, under stronger conditions, such as those
in Exercise~\ref{trivial circular} below the matter
becomes much easier.)


However the treatment of the sums of type
\[\sum_{|u|,|v|\leq N}\hat{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^{\infty}$
rather than $L^{1}$ functions.)
\begin{lemma}\label{many start}
If we define $\tilde{K}_{n}:{\mathbb T}^{m}\rightarrow{\mathbb R}$
by 
\[\tilde{K}_{n}(t_{1},t_{2},\dots,t_{m})=\prod_{j=1}^{m}K_{n}(t_{j}),\]
then we have the following results.

(i) ${\displaystyle \frac{1}{(2\pi)^{m}}\int_{{\mathbb T}^{m}}
\tilde{K}_{n}({\mathbf t})\, d{\mathbf t}=1}$.

(ii) If $\eta>0$, then 
\[\frac{1}{(2\pi)^{m}}\int_{|{\mathbf t}|\geq\eta}\tilde{K}_{n}({\mathbf t})
\,d{\mathbf t}\rightarrow 0\] 
as $n\rightarrow\infty$.

(iii) $\tilde{K}_{n}({\mathbf t})\geq 0$ for all ${\mathbf t}$.

(iv) $\tilde{K}_{n}$ is a (multidimensional) trigonometric
polynomial.
\end{lemma}
\begin{lemma}
If $f:{\mathbb T}^{m}\rightarrow{\mathbb C}$ is integrable
and $P:{\mathbb T}^{m}\rightarrow{\mathbb C}$ is a trigonometric
polynomial, then
\[P*f({\mathbf x})=\frac{1}{(2\pi)^{m}}\int_{{\mathbb T}^{m}}
P({\mathbf x}-{\mathbf t})f({\mathbf t})\, d{\mathbf t}\]
is a trigonometric polynomial in ${\mathbf x}$.
\end{lemma}
\begin{theorem}[Density of trigonometric polynomials]%
The trigonometric polynomials are
uniformly dense in the continuous functions on ${\mathbb T}^{m}$.
\end{theorem}
\begin{lemma}[Riemann-Lebesgue lemma] If $f$ is an
integrable function on ${\mathbb T}^{m}$, then
$\hat{f}({\mathbf n})\rightarrow 0$ 
as $|{\mathbf n}|\rightarrow\infty$.
\end{lemma}
\begin{theorem}[Uniqueness] If $f$ and $g$ are
integrable functions on ${\mathbb T}^{m}$ with 
$\hat{f}({\mathbf n})=\hat{g}({\mathbf n})$ 
for all ${\mathbf n}$, then $f=g$.
\end{theorem}
\begin{lemma} If $f$ is an
integrable function on ${\mathbb T}$ and
$\sum_{{\mathbf j}}|\hat{f}({\mathbf j})|$ converges, 
then $f$ is continuous
and $f({\mathbf t})=\sum_{{\mathbf j}}\hat{f}({\mathbf j})
\exp i{\mathbf j}.{\mathbf t}$.
\end{lemma}
\begin{exercise}\label{trivial circular}
Suppose that
$f:{\mathbb T}^{m}\rightarrow{\mathbb C}$
is integrable and 
$\sum_{(u,v)\in{\mathbb Z}^{2}}|\hat{f}(u,v)|<\infty$.
Show that
\[\sum_{u^{2}+v^{2}\leq N}\hat{f}(u,v)\exp(i(ux+vy))
\rightarrow f(x,y)\]
uniformly as $N\rightarrow\infty$.
\end{exercise}
\begin{theorem} [Parseval's Theorem]\label{many end}
If $f$ is
a continuous function on ${\mathbb T}^{m}$, then
\[\sum_{n\in{\mathbb Z}^{m}}|\hat{f}({\mathbf n})|^{2}
=\frac{1}{(2\pi)^{m}}\int_{{\mathbb T}^{m}}
|f({\mathbf t})|^{2}\,d{\mathbf t}.\]
More generally, if $f$ and $g$ are continuous,
\[\sum_{n\in{\mathbb Z}^{m}}
\hat{f}({\mathbf n})\hat{g}({\mathbf n})^{*}
=\frac{1}{(2\pi)^{m}}\int_{{\mathbb T}^{m}}
f({\mathbf t})g({\mathbf t})^{*}\,d{\mathbf t}.\]
\end{theorem}
\begin{exercise}  Prove the results from Lemma~\ref{many start}
to Theorem~\ref{many end}
\end{exercise}
\begin{exercise} The extension of Lemma~\ref{pointwise}
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 ${\mathbb T}^{2}$ such that there
exists an $A$ with $|\hat{f}(u,v)|\leq A(u^{2}+v^{2})^{-1}$ for
all $(u,v)\neq (0,0)$. Show that,
if $f$ is continuous at $(s,t)$, then
\[\sum_{|u|,|v|\leq n}\hat{f}(u,v)\exp(i(us+vt))
\rightarrow f(s,t)\]
as $n\rightarrow\infty$

(ii) (This generalises Lemma~\ref{once is}.) 
Suppose that $f$ is a
twice differentiable function on ${\mathbb T}^{2}$
with 
${\displaystyle \frac{\partial^{2}f(x,y)}{\partial x\partial y}}$
continuous. Show that
$\sum_{(u,v)\in{\mathbb Z}^{2}}|\hat{f}(u,v)|<\infty$.

(iii) State the correct generalisations of parts (i) and
(ii) to higher dimensions. 
\end{exercise}

We immediately obtain a striking generalisation of
Weyl's theorem (Theorem~\ref{Weyl}).
\begin{theorem}\label{Weyl many} Suppose
that $\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
are real numbers. A necessary and sufficient condition
that
\[\frac{\card\{1\leq n\leq N \mid 
(\langle n\alpha_{1}\rangle,\langle n\alpha_{2}\rangle,
\dots,\langle n\alpha_{M}\rangle)
\in \prod_{j=1}^{M}[a_{j},b_{j}]\}}{N}
\rightarrow \prod_{j=1}^{M}(b_{j}-a_{j})\]
as $N\rightarrow\infty$ whenever $0\leq a_{j}\leq b_{j}\leq 1$
is that
\begin{equation*}
\sum_{j=1}^{M} n_{j}\alpha_{j}\notin{\mathbb Z}
\ \text{for integer $n_{j}$ not all zero}. \tag*{$\bigstar$}
\end{equation*}
\end{theorem}
If $\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
satisfy $\bigstar$ we say that they are independent.
The multidimensional version of Weyl's theorem has
an important corollary.
\begin{theorem}{\bf (Kronecker's theorem)}\label{Kronecker's theorem}
Suppose
that $\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
are independent real numbers. Then given real
numbers $\beta_{1}$, $\beta_{2}$, \dots, $\beta_{M}$
and $\epsilon>0$ we can find integers
$N$, $m_{1}$, $m_{2}$, \dots, $m_{M}$ such that
\[|N\alpha_{j}-\beta_{j}-m_{j}|<\epsilon\]
for each $1\leq j\leq M$.

The result is false if
$\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
are not independent.
\end{theorem} 

We use this to obtain a theorem of Kolmogorov.
\begin{theorem} There exists a Lebesgue integrable
(that is an $L^{1}$) function 
$f:{\mathbb T}\rightarrow{\mathbb C}$ such that
\[\limsup_{n\rightarrow\infty}|S_{n}(f,t)|=\infty\]
for all $t\in{\mathbb T}$.
\end{theorem}
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.
\begin{lemma}\label{Polynomial Kolmogorov}
Given any $K>0$ we can find a
trigonometric polynomial $P$ such that

(i) ${\displaystyle \frac{1}{2\pi}\int_{\mathbb T}|P(t)|\, dt\leq 1}$,

(ii) $\max_{n\geq 0}|S_{n}(P,t)|\geq K$
for all $t\in{\mathbb T}$.
\end{lemma}

In our discussion of Kronecker's theorem
(Theorem~\ref{Kronecker's theorem}) we worked
modulo $1$. In what follows it is easier
to work modulo $2\pi$. The readier will readily
check that the definition and theorem that follow
give the appropriate restatement of Kronecker's theorem.
\begin{definition}
We work in ${\mathbb T}$.
If $\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
satisfy 
\begin{equation*}
\sum_{j=1}^{M} n_{j}\alpha_{j}\neq 0
\ \text{for integer $n_{j}$ not all zero}. \tag*{$\bigstar$}
\end{equation*}
we say that they are independent.

\end{definition}
\begin{theorem}{\bf (Kronecker's theorem (alternative statement))}%
\label{alternative Kronecker} Suppose
that $\alpha_{1}$, $\alpha_{2}$, \dots, $\alpha_{M}$
are independent points in ${\mathbb T}$. Then, given complex
numbers $\lambda_{1}$, $\lambda_{2}$, \dots, $\lambda_{M}$
with $|\lambda_{j}|=1$ $[j=1,\ 2,\ \dots,\ M]$
and $\epsilon>0$, we can find an integer $N$
such that
\[|\exp(iN\alpha_{j})-\lambda_{j}|<\epsilon\]
for each $1\leq j\leq M$.
\end{theorem}

Our construction requires some preliminary results.
\begin{lemma} If  $x_{1}$, $x_{2}$, \dots, $x_{M}$
are independent points in ${\mathbb T}$ and $t\in{\mathbb T}$
and
\begin{align*}
\sum_{j=1}^{M} p_{j}(x_{j}-t)&=0
\ \text{for integer $p_{j}$ not all zero}\\
\sum_{j=1}^{M} q_{j}(x_{j}-t)&= 0
\ \text{for integer $q_{j}$ not all zero}
\end{align*}
then there exist 
$p,q\in{\mathbb Z}\setminus\{0\}$
such that
$pq_{j}=qp_{j}$ for $1\leq j\leq M$.
\end{lemma}
\begin{lemma} If  $x_{1}$, $x_{2}$, \dots, $x_{M}$
are independent points in ${\mathbb T}$ and $t\in{\mathbb T}$,
then one of the following must hold:-

(a) There exists a $i\neq 1$ such that
the points $x_{j}-t$ with $j\neq i$ are independent.

(b) $x_{1}-t$ is a rational multiple of $2\pi$
and the points $x_{j}-t$ with $j\neq 1$ are independent.
\end{lemma}
\begin{lemma}\label{Kronecker set up} 
(i) If $I$ is an open interval in ${\mathbb T}$
and $x_{1}$, $x_{2}$, \dots, $x_{m}$ are independent
we can find $x_{m+1}\in I$ such that
$x_{1}$, $x_{2}$, \dots, $x_{m+1}$ are independent.
 
(ii) Given an integer $M\geq 1$ we can find
independent points
$x_{1}$, $x_{2}$, \dots, $x_{M}$ in ${\mathbb T}$
such that
\[|x_{j}-2\pi j/M|\leq 10^{-3}M^{-1}\]
\end{lemma}

\begin{lemma}\label{Finite measure} If $M$ and
$x_{1}$, $x_{2}$, \dots, $x_{M}$ in ${\mathbb T}$
are as in Lemma~\ref{Kronecker set up}~(ii),
then setting
\[\mu=M^{-1}\sum_{j=1}^{M}\delta_{x_{j}}\]
we have the following two results.

(i) $\max_{n\geq 0}|S_{n}(\mu,t)|\geq 100^{-1}\log M$
for each $t\in{\mathbb T}$,

(ii) There exists an $N$ such that
$\max_{N\geq n\geq 0}|S_{n}(\mu,t)|\geq 200^{-1}\log M$
for each $t\in{\mathbb T}$.
\end{lemma}

\noindent\emph{Remark 1} If you wish you may treat 
$S_{n}(\mu,t)$ as a purely formal object. However,
it is better for later work to think what it actually is.

\noindent\emph{Remark 2} Factors like $10^{-3}$ and $100^{-1}$
in Lemmas~\ref{Kronecker set up}~(ii) and~\ref{Finite measure}
are more or less chosen at random and are not `best possible'.

A simple argument using Lemma~\ref{Finite measure} now gives
Lemma~\ref{Polynomial Kolmogorov} and we are done.
\begin{exercise} Show, by considering
Fej\'{e}r sums or otherwise, that we cannot find a continuous
function $f$ such that $S_{n}(f,t)\rightarrow\infty$
uniformly as $n\rightarrow\infty$.
\end{exercise}

\section{Some simple geometry of numbers}
We need the following
extension of Theorem~\ref{many end}.
\begin{lemma}\label{characteristic Parseval}
If $A$ is a well behaved set
and $f$ is the characteristic function
of $A$ (that is $f(x)=1$ if $x\in A$,
$f(x)=0$ otherwise), then
\[\sum_{n\in{\mathbb Z}^{m}}|\hat{f}({\mathbf n})|^{2}
=\frac{1}{(2\pi)^{m}}\int_{{\mathbb T}^{m}}
|f({\mathbf t})|^{2}\,d{\mathbf t}.\]
\end{lemma}
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~\ref{many end})
holds for every $f\in L^{1}\cap 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.
\begin{exercise} EITHER (i) Give the detailed
proof of Lemma~\ref{characteristic Parseval}
in terms of Lebesgue measure.

OR (ii) Give the detailed
proof of Lemma~\ref{characteristic Parseval}
in terms of Riemann integration in the
special case when $A$ is a sphere.
\end{exercise}

We use Parseval's Theorem (in the form of
Lemma~\ref{characteristic Parseval}) to
give Siegel's proof of Minkowski's
theorem.
\begin{theorem}[Minkowski]\label{Minkowski}
Let $\Gamma$ be an open symmetric  convex set
in ${\mathbb R}^{m}$ with volume $V$.
If $V>2^{m}$, then $\Gamma\cap {\mathbb Z}^{m}$
contains at least two points.
\end{theorem}

The reader will recall that $\Gamma$ is convex if
\[{\mathbf x},{\mathbf y}\in \Gamma
\ \text{and}\ 0\leq\lambda\leq 1
\Rightarrow
\lambda{\mathbf x}+(1-\lambda){\mathbf y}\in \Gamma\]
and that $\Gamma$ is symmetric if
\[{\mathbf x}\in \Gamma
\Rightarrow -{\mathbf x}\in \Gamma.\]
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.
\begin{lemma} If $V\leq 2^{m}$ there exists
an open symmetric  convex set $\Gamma$
in ${\mathbb R}^{m}$ with volume $V$
such that $\Gamma\cap {\mathbb Z}^{m}=\{{\mathbf 0}\}$.
\end{lemma}

To prove Minkowski's theorem  (Theorem~\ref{Minkowski})
it suffices to prove an essentially equivalent result.
\begin{theorem}
Let $\Gamma$ be a bounded open symmetric  convex set
in ${\mathbb R}^{m}$ with volume $V$.
If $V>2^{m}(2\pi)^{m}$, then $\Gamma\cap(2\pi {\mathbb Z})^{m}$
contains at least two points.
\end{theorem}
We need the following simple but crucial result.
\begin{lemma} If $\Gamma$ is symmetric  convex set
and ${\mathbf x},{\mathbf x}-2{\mathbf y}\in \Gamma$,
then ${\mathbf y}\in \Gamma$.
\end{lemma}
By applying Parseval's theorem to 
$f({\mathbf x})=\sum_{{\mathbf k}\in {\mathbb Z}^{m}}
{\mathbb I}_{\Gamma/2}({\mathbf x}-2\pi {\mathbf k})$ we
obtain the following results.
\begin{lemma} Let $\Gamma$ be a bounded open symmetric  convex set
in ${\mathbb R}^{m}$ with volume $V$ such that
$\Gamma\cap(2\pi {\mathbb Z})^{m}$ only contains
${\mathbf 0}$. Then
\begin{equation*}
\tag*{$\bigstar$}
2^{-m}\sum_{{\mathbf k}\in {\mathbb Z}^{m}}
\left|
\int_{[-\pi,\pi]^{m}} 
{\mathbb I}_{\Gamma}({\mathbf x})e^{i{\mathbf k}.{\mathbf x}}
\, d{\mathbf x}
\right|^{2}
=(2\pi)^{m}V.
\end{equation*}
where ${\mathbb I}_{\Gamma}$ is the characteristic function
of $\Gamma$.
\end{lemma}
Minkowski's theorem follows at once by considering the
term with ${\mathbf k}={\mathbf 0}$ in equation
$\bigstar$.

Here is a simple application of Minkowski's theorem.
\begin{lemma} Suppose that $a$, $b$, $c$, $d$ are
real numbers with $ad-bc=1$. Given $l>0$ and $\epsilon>0$
we can find integers $m$ and $n$ such that
\[|an+bm|\leq(1+\epsilon) l,\ |cn+dm|\leq (1+\epsilon) l^{-1}.\]
\end{lemma}
Taking $c=x$, $a=1$, $b=0$, $d=-1$ and thinking carefully
we obtain in quick succession.
\begin{lemma} If $x$ is real there exist $n$ and $m$ integers
with $n\neq 0$ such that
\[\left|x-\frac{m}{n}\right|\leq\frac{1}{n^{2}}.\]
\end{lemma}
\begin{lemma} If $x$ is real there exist infinitely
many pairs of integers $n$ and $m$
with $n\neq 0$ such that
\[\left|x-\frac{m}{n}\right|\leq\frac{1}{n^{2}}.\]
\end{lemma}

Here is another simple consequence.
\begin{lemma}{\bf (Quantitative version of Dirichlet's theorem)}
If ${\mathbf x}\in{\mathbb R}^{m}$, then,
given $l>0$ and $\epsilon>0$, 
we can find
$n,\ n_{1},\ n_{2},\ \dots,\ n_{m}\in{\mathbb Z}$ such that
\[|nx_{j}-n_{j}|\leq l^{-1}\] 
for $1\leq j\leq m$ and $|n|\leq l^{m}$.
\end{lemma}

We conclude our collection of consequences with
Legendre's four squares theorem.
\begin{theorem}[Legendre]\label{Legendre} 
Every positive integer
is the sum of at most 4 squares.
\end{theorem}
\begin{lemma} We cannot reduce 4 in the statement
of Legendre's theorem (Theorem~\ref{Legendre}).
\end{lemma}

We need an observation of Euler.
\begin{lemma}\label{Euler Legendre} If $x_{0}$, $x_{1}$,
$x_{2}$, $x_{3}$, $y_{0}$, $y_{1}$,
$y_{2}$, $y_{3}$ are real, then
\begin{align*}
(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}.
\end{align*} 
\end{lemma}
\begin{exercise} In the lectures we will use quaternions
to prove Lemma~\ref{Euler Legendre}. Prove the
equality by direct verification.
\end{exercise}
\begin{lemma} Legendre's four square theorem will follow
if we can show that every odd prime is the sum
of at most four squares.
\end{lemma}

We shall also need the volume of a $4$ dimensional
sphere. A simple argument gives the
volume of a unit sphere in any dimension.
\begin{lemma} Let $V_{n}$ be the ($n$-dimensional)
volume of an $n$ dimensional unit sphere.

(i) If $f:[0,\infty)\rightarrow{\mathbb R}$ is a continuous
function with $t^{n+2}f(t)\rightarrow 0$ as 
$t\rightarrow\infty$, then 
\[\int_{{\mathbb R}^{n}}f(\|{\mathbf x}\|)\,dV({\mathbf x})
=V_{n}\int_{0}^{\infty}f(t)nt^{n-1}\,dt.\]

(ii) $V_{2k}=\dfrac{\pi^{k}}{k!}$,
$V_{2k+1}=\dfrac{k!2^{2k+1}\pi^{k}}{(2k+1)!}$.
\end{lemma}

Finally we need the apparently more general
version of Minkowski's theorem obtained by
applying a linear map.
\begin{theorem}[Minkowski for general lattices]%
\label{Minkowski general} We work
in ${\mathbb R}^{m}$. Let $\Lambda$ 
be a lattice with fundamental region of volume $L$
and let $\Gamma$ be an open symmetric  convex set
with volume $V$.
If $V>2^{m}L$, then $\Gamma\cap\Lambda$
contains at least two points.
\end{theorem}

We now turn to the proof of the fundamental lemma.
\begin{lemma}\label{prime Legendre} Every odd prime is the sum
of at most four squares.
\end{lemma}
We begin with a simple lemma.
\begin{lemma}\label{lattice finder} Let $p$
be an odd prime.

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

(ii) We can find integers $u$ and $v$ such that
$u^{2}+v^{2}\equiv-1 \bmod p$.
\end{lemma}

We now introduce a lattice.
\begin{lemma} Let $p$, $u$ and $v$ be as in 
Lemma~\ref{lattice finder}. If 
\[\Lambda=\{(n,m,a,b)\in{\mathbb Z}^{4}
\, : \,
nu+mv\equiv a,\ mu-nv\equiv b \bmod p\}\]
then $\Lambda$ is a lattice
with fundamental region of volume $p^{2}$.

If $(n,m,a,b)\in\Lambda$, then
$n^{2}+m^{2}+a^{2}+b^{2}\equiv 0 \bmod p$.
\end{lemma}
We can now prove Lemma~\ref{prime Legendre} and with it 
Theorem~\ref{Legendre}. 

\begin{exercise} (i) Recall that if $p$
is a prime, then the
multiplicative group $({\mathbb Z}_{p}\setminus\{0\},\times)$
is cyclic. (This is the subject of Exercise~\ref{cyclic in field}.)
Deduce that if $p=4k+1$, then there is an element $u$ in 
$({\mathbb Z}_{p}\setminus\{0\},\times)$ of order $4$.
Show that $u^{2}=-1$.

(ii) If $p$ and $u$ are as in (i) show that
\[\Lambda=\{(n,m)\in{\mathbb Z}^{2}
\, : \,
m\equiv n \bmod 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.)
\end{exercise}
\section{A brief look at Fourier transforms}\label{brief}
If time permits
we will look at Fourier transforms in sections~\ref{Heisenberg section}
and~\ref{Poisson section}. If $f:{\mathbb R}\rightarrow{\mathbb C}$
is integrable on each finite interval $[a,b]$
(in the Riemann or Lebesgue sense)
and $\int_{-\infty}^{\infty}|f(x)|\,dx<\infty$ 
we\footnote{The majority
of my auditors who know Lebesgue integration will
prefer the formulations `$f\in L^{1}({\mathbb R})$'
or `$f$ measurable and $\int_{-\infty}^{\infty}|f(x)|\,dx<\infty$.}
shall say that $f$ is \emph{appropriate}.
(This is non-standard notation.) 
If $f$ is appropriate define
\[\hat{f}(\lambda)
=\int_{-\infty}^{\infty}f(t)\exp(-i\lambda t)\, dt.\]

\begin{lemma} If $f$ is appropriate, 
$\hat{f}:{\mathbb R}\rightarrow{\mathbb C}$ is continuous
and bounded.
\end{lemma}
Our first problem is that even when $f$ is appropriate
$\hat{f}$ need not be.
\begin{example} If $f$ is the indicator function of
$[a,b]$ (that is, $f(x)=1$ if $x\in [a,b]$, $f(x)=0$
otherwise), then 
\[\int_{-\infty}^{\infty}|\hat{f}(\lambda)|\,d\lambda=\infty.\]
\end{example} 
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.
\begin{theorem}[Fubini's theorem] If 
$f:{\mathbb R}^{2}\rightarrow{\mathbb C}$ is measurable
and either of the two integrals
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}|f(x,y)|\,dx\,dy\ \text{and}
\ \int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}|f(x,y)|\,dy\,dx\]
exists and is finite, then they both do and the integrals 
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dx\,dy\ \text{and}
\ \int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dy\,dx.\]
exist and are finite and equal.
\end{theorem}

If we use Riemann integration, then we have
a slogan.
\begin{pretheorem} If 
$f:{\mathbb R}^{2}\rightarrow{\mathbb C}$ is well behaved
and either of the two integrals
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}|f(x,y)|\,dx\,dy\ \text{and}
\ \int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}|f(x,y)|\,dy\,dx\]
is finite, then they both are and
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dx\,dy\ \text{and}
\ \int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dy\,dx.\]
\end{pretheorem}
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$.

\begin{exercise}\label{Riemann meets Fubini} In this exercise
we use Riemann integration
and derive a simple Fubini type theorem.

(i) If $I$ and $J$ are intervals on ${\mathbb R}$ (so
$I$ could have the form $[a,b]$, $[a,b)$, $(a,b)$
or $(a,b)$) and we write ${\mathbb I}_{I\times J}(x,y)=1$
if $(x,y)\in I\times J$, ${\mathbb I}_{I\times J}(x,y)=0$,
otherwise show that
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}{\mathbb I}_{I\times J}(x,y)\,dx\,dy= 
\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}{\mathbb I}_{I\times J}(x,y)\,dy\,dx.\]

(ii) Suppose that $I_{r}$ 
and $J_{r}$ are intervals on ${\mathbb R}$
and that $\lambda_{r}\in{\mathbb C}$ $[1\leq r\leq n]$.
If $f=\sum_{r=1}^{n}{\mathbb I}_{I_{r}\times J_{r}}$
show that
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dx\,dy=
\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dy\,dx.\]

(iii) Suppose that $f:{\mathbb R}^{2}\rightarrow{\mathbb C}$ is continuous
and that  $I$ and $J$ are intervals on ${\mathbb R}$. If
$g(x,y)={\mathbb I}_{I\times J}(x,y)f(x,y)$ show
using (ii) that
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}g(x,y)\,dx\,dy=
\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}g(x,y)\,dy\,dx.\]

(iv) Suppose that $f:{\mathbb R}^{2}\rightarrow{\mathbb C}$ is continuous
and that there exists a real constant $A$ such that
\begin{equation*}
|f(x,y)|\leq A(1+x^{2})^{-1}(1+y^{2})^{-1}.
\tag*{$\bigstar$}
\end{equation*}
Show, using (ii), that
\[\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dx\,dy=
\int_{-\infty}^{\infty}
\int_{-\infty}^{\infty}f(x,y)\,dy\,dx.\]
\end{exercise}
Conditions like $\bigstar$ imposing some rate of decrease
at infinity play an important role in Fourier
analysis.

In section~\ref{Heisenberg section} (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.
\begin{definition} 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\rightarrow 0+}f(t-h)$ for all $t$.
\end{definition}
(Different authors use different definitions. They
are all the same `in spirit' but not `in logic'.) 
\begin{exercise}\label{Crude uniqueness}
If $f$ is appropriate and $R>0$ we define
\[\sigma_{R}(f,t)=\frac{1}{2\pi}\int_{-R}^{R}
\left(1-\frac{|\lambda|}{R}\right)\hat{f}(\lambda)
\exp(i\lambda t)\,d\lambda.\]
(It will become clear that this is the analogue of
the Fej\'{e}r sum.)

(i) (For users of the Lebesgue integral)
By adapting the proof
of Theorem~\ref{Fejer convergence} show that
if $f\in L^{1}$ and $f$ is continuous at $t$
then
\[\sigma_{R}(f,t)\rightarrow f(t)\]
as $R\rightarrow\infty$. 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~\ref{Fejer convergence} show that
if $f$ is continuous and there
there exists a real constant $A$ such that
\[|f(x)|\leq A(1+x^{2})^{-1}\]
for all $x$, show that
\[\sigma_{R}(f,t)\rightarrow 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
\[\sigma_{R}(f,t)\rightarrow f(t)\]
at all $t$ where $f$ is continuous.
(All we need is a slight extension of 
Exercise~\ref{Riemann meets Fubini}~(iv).)

(ii) (For users of the Lebesgue integral)
Suppose that $f$ and $g$
are piecewise continuous $L^{1}$
functions. Show that, if $\hat{f}(\lambda)=\hat{g}(\lambda)$
for all $\lambda$, 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)|\leq A(1+x^{2})^{-1}\]
for all $x$. Show that, if $\hat{f}(\lambda)=\hat{g}(\lambda)$
for all $\lambda$, then $f(t)=g(t)$ for all $t$.
\end{exercise} 



\section{Infinite products} Our object in the next few
lectures will be to prove the following remarkable
theorem of Dirichlet on primes in arithmetic
progression.
\begin{theorem}[Dirichlet]\label{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.
\end{theorem}
(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\footnote{In the sense that most
reasonable people would call reasonable. Selberg produced
a (technically)  elementary proof which may be found in his
collected works.} elementary
(in the technical sense of not using analysis) 
proof.

Dirichlet's method starts from an observation of Euler.
\begin{lemma}\label{Euler prime start}
If $s$ is real with $s>1$, then
\[\prod_{\substack{\text{$p$ prime}\\p\leq N}}
\left(1-\frac{1}{p^{s}}\right)^{-1}\rightarrow
\sum_{n=1}^{\infty}\frac{1}{n^{s}}\]
as $s\rightarrow 1+$.
\end{lemma}
Using this result, we get a new proof of the existence
of an infinity of primes.
\begin{theorem}[Euclid] There exist an infinity of primes.
\end{theorem}

This suggests that it may be worth investigating 
infinite products a bit more.
\begin{definition} Let $a_{j}\in{\mathbb C}$. If
$\prod_{n=1}^{N}(1+a_{n})$ tends to a limit $L$
as $N\rightarrow\infty$, we say that the 
\emph{infinite product} $\prod_{n=1}^{\infty}(1+a_{n})$
\emph{converges} to a value $L$ and write
\[\prod_{n=1}^{\infty}(1+a_{n})=L.\]
If the infinite product $\prod_{n=1}^{\infty}(1+|a_{n}|)$
converges, then we say that $\prod_{n=1}^{\infty}(1+a_{n})$
is \emph{absolutely convergent}.
\end{definition}
The next result was removed from the first year of
the Tripos a couple of years before I took it.
\begin{lemma}\label{absolute convergence} 
Let $a_{j}\in{\mathbb C}$.

(i) $\prod_{n=1}^{\infty}(1+a_{n})$ is absolutely
convergent if and only if $\sum_{n=1}^{\infty}a_{n}$
is.

(ii) If $\prod_{n=1}^{\infty}(1+a_{n})$ is absolutely
convergent and $1+a_{n}\neq 0$ for each $n$, then
the infinite product converges and
\[\prod_{n=1}^{\infty}(1+a_{n})\neq 0.\]
\end{lemma}
\begin{exercise} Find $a_{j}\in{\mathbb C}$ such that
$\prod_{n=1}^{\infty}(1+a_{n})$ is not absolutely
convergent but is convergent to a non-zero value.
\end{exercise}
We shall only make use of absolute convergent infinite
products.
\begin{exercise} If $\prod_{n=1}^{\infty}(1+a_{n})$ is 
absolutely convergent and 
$\sigma:{\mathbb N}\rightarrow{\mathbb N}$
is a bijection 
(that is, $\sigma$ is a permutation of ${\mathbb N}$)
show that $\prod_{n=1}^{\infty}(1+a_{\sigma(n)})$ is 
absolutely convergent and
\[\prod_{n=1}^{\infty}(1+a_{\sigma(n)})
=\prod_{n=1}^{\infty}(1+a_{n})\]
\end{exercise}
Whilst this is a useful result to know, we shall make no essential
use of it. When we write
$\sum_{\text{$p$ prime}}$ or $\prod_{\text{$p$ prime}}$
we mean the primes $p$ to be taken in order of increasing
size.

Using Lemma~\ref{absolute convergence} we obtain
the following strengthening of Euclid's theorem.
\begin{theorem}[Euler]
${\displaystyle \sum_{\text{$p$ prime}}\frac{1}{p}=\infty.}$
\end{theorem}

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.
\begin{lemma} Suppose $U$ is an open subset of ${\mathbb C}$
and that we have a sequence of functions 
$g_{n}:U\rightarrow{\mathbb C}$ and a sequence of positive
real numbers $M_{n}$ such that $M_{n}\geq |g_{n}(z)|$
for all $z\in U$. If $\sum_{n=1}^{\infty}M_{n}$
converges, then $\prod_{n=1}^{N}(1+g_{n}(z))$ converges
uniformly on $U$.
\end{lemma}
Later we shall need to consider $\sum 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$.
\begin{lemma} If $\Re s>1$ we have
\[\prod_{\text{$p$ prime}}(1-p^{-s})^{-1}=\sum_{n=1}^{\infty}n^{-s}\]
both sides being absolutely convergent for each $s$
and uniformly convergent for $\Re s>1+\epsilon$ for
each fixed $\epsilon>0$.
\end{lemma}

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.
\begin{lemma} If $z_{1}$, $z_{2}$, \dots are distinct zeros
of an analytic function which is not identically
zero, then $z_{n}\rightarrow\infty$ as $n\rightarrow\infty$.
\end{lemma}

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)$.
\begin{definition} If $m$ is a strictly positive integer
\[E(z,m)=(1-z)e^{z+z^{2}/2+z^{3}/3+\dots+z^{m}/m}.\]
\end{definition}
\begin{lemma} The function $E(\ ,m):\mathbb{C}\rightarrow\mathbb{C}$
is analytic with a unique zero at 1. Given $\epsilon>0$
we can find an $M$ such that
\[|1-E(z,m)|\leq \epsilon\]
for all $m\geq M$ and $|z|\leq 1/2$.
\end{lemma}


\begin{theorem}[Weierstrass] If $k$ is a positive integer
and $z_{1},z_{2},\dots$ is a sequence of non-zero complex
numbers with $z_{n}\rightarrow\infty$, then we can choose
$n(j)\rightarrow\infty$ so that
\[F(z)=z^{k}\prod_{j=1}^{\infty}E\big(z/z_{j},n(j)\big)\]
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.
\end{theorem}
\begin{lemma} If $f_{1}$ and $f_{2}$ are analytic functions
on ${\mathbb C}$ 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).\]
\end{lemma}
\begin{lemma} If $z_{1},z_{2},\dots$ and $w_{1},w_{2},\dots$
are sequences of complex numbers with 
$z_{j},w_{j}\rightarrow\infty$ as $j\rightarrow\infty$
and $z_{j}\neq 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).
\end{lemma}
\begin{exercise}
(i) Show that we can find an $A$ such that
\[|1-E(z,m)|\leq A|z|^{m+1}\]
for $|z|\leq 1/2$.

(ii) If $k$ is a positive integer
and $z_{1},z_{2},\dots$ is a sequence of non-zero complex
numbers with $z_{n}\rightarrow\infty$, then
\[F(z)=z^{k}\prod_{j=1}^{\infty}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.
\end{exercise}
\begin{exercise} (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 
\[\pm (N+1/2)\pm (N+1/2)i\] 
described
anti-clockwise, show that there is a constant $K$
such that
\[|\cot \pi z|\leq K\]
for all $z\in C_{N}$ and all integers $N\geq 1$.

(ii) By integrating an appropriate function round the
contour $C_{N}$, or otherwise,
show that, if $w\notin{\mathbb Z}$,
\[\sum_{n=-N}^{n=N}\frac{1}{w-n}\rightarrow  \pi\cot\pi w.\]

(iii) Is it true that, if $w\notin{\mathbb Z}$,
\[\sum_{n=-M}^{n=N}\frac{1}{w-n}\rightarrow  \pi\cot\pi w,\]
as $M,N\rightarrow\infty$? Give reasons.

(iv) Show that
\[P(z)=z\prod_{n=1}^{\infty}\left(1-\frac{z^{2}}{n^{2}}\right)\]
is a well defined analytic function and that there exists
an analytic function $g$ such that
\[\sin\pi z=e^{g(z)}P(z).\]

(v) Find a simple expression for
$P'(z)/P(z)$. 

\noindent[Hint: If $p(z)=\prod_{j=1}^{N}(z-\alpha_{j})$,
what is $p'(z)/p(z)$?]
 
Find a related expression for
$\frac{d\ }{dz}\sin \pi z/\sin \pi z$.

(vi) Show that
\[\sin\pi z=\pi z\prod_{n=1}^{\infty}\left(1-\frac{z^{2}}{n^{2}}\right).\]

(vii) Find a similar expression for $\cos\pi z$. (These
results are due to Euler.)
\end{exercise}
\begin{exercise} (This makes use of some of the
techniques of the previous exercise.) (i) Show that the infinite product
\[g(z)=\prod_{n=1}^{\infty}e^{z/n}\left(1-\frac{z}{n}\right)\]
exists and is analytic on the whole complex plane.

(ii) Show that
\[g'(z)=g(z)
\sum_{n=1}^{\infty}\left(\frac{1}{z-n}+\frac{1}{n}\right).\]
Explain why $\sum_{n=1}^{\infty}(\frac{1}{z-n}+\frac{1}{n})$
is indeed a well defined analytic function on 
${\mathbb C}\setminus{\mathbb Z}$.

(iii) By using (ii), or otherwise, show that
\begin{equation*}
g(z+1)=-Azg(z) \tag*{($*$)}
\end{equation*}
for some constant $A$.

(iv) By considering a particular value of $z$, or otherwise,
show that $A$ is real and positive and
\[\sum_{n=1}^{N}\frac{1}{n}-\log N\rightarrow \log A\]
as $N\rightarrow\infty$.
Deduce the existence of Euler's constant
\[\gamma=\lim_{N\rightarrow\infty}
\left(\sum_{n=1}^{N}n^{-1}-\log N\right)\]
and rewrite $(*)$ as
\begin{equation*}
g(z+1)=-e^{\gamma}zg(z). 
\end{equation*}

(v) Find a simple expression for $zg(z)g(-z)$. Use $(*)$
to show that $\sin \pi z$ is periodic.
\end{exercise}
\section{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)=\sum_{n=-\infty}^{\infty}\hat{f}(n)e_{n}(t)\]
where $e_{n}(t)=\exp(int)$. The clue to further extension
lies in the following observation.
\begin{lemma} Consider the Abelian group 
${\mathbb T}={\mathbb R}/(2\pi{\mathbb Z})$ and the
subgroup $S=\{z:|z|=1\}$ of $({\mathbb C}\setminus\{0\},\times)$.
The continuous homomorphisms 
$\theta:{\mathbb T}\rightarrow S$ are precisely
the functions $e_{n}:{\mathbb T}\rightarrow S$ given
by $e_{n}(t)=\exp(int)$ with $n\in{\mathbb Z}$.
\end{lemma}
\begin{exercise} (i) Find (with proof) all the
continuous homomorphisms 
\[\theta:({\mathbb R},+)\rightarrow (S,\times).\]
What is the connection with Fourier transforms?

(ii) (Only for those who know Zorn's lemma%
\footnote{And, particularly, those who only know Zorn's lemma.}.)
Assuming Zorn's lemma show that any linearly independent
set in a vector space can be extended
to a basis. If we consider ${\mathbb R}$ as a vector
space over ${\mathbb Q}$, show that there exists
a linear map $T:{\mathbb R}\rightarrow{\mathbb R}$ such
that $T(1)=1$, $T(\surd 2)=0$. Deduce the existence
of a function $T:{\mathbb R}\rightarrow{\mathbb R}$
such that $T(x+y)=T(x)+T(y)$ for all $x,y\in {\mathbb R}$
which is not continuous (with respect to the usual metric).
Show that, if we accept Zorn's lemma, there exist
discontinuous homomorphisms
$\theta:({\mathbb R},+)\rightarrow (S,\times)$.
\end{exercise}

This suggests the following definition.
\begin{definition} If $G$ is a finite Abelian group,
we say that a homomorphism $\chi:G\rightarrow S$
is a \emph{character}. We write $\hat{G}$ for the
collection of such characters.
\end{definition}
In this section we shall accumulate a
substantial amount of information about $\hat{G}$
by a succession of small steps.

\begin{lemma} Let $G$ be a finite Abelian group.

(i) If $x\in G$ has order $m$ and $\chi\in\hat{G}$,
then $\chi(x)$ is an $m$th root of unity.

(ii) $\hat{G}$ is a finite Abelian group under
pointwise multiplication. 
\end{lemma}

To go further we consider, for each finite Abelian group
$G$, the collection $C(G)$ of functions $f:G\rightarrow{\mathbb C}$.
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
\[\langle f,g\rangle=\frac{1}{|G|}\sum_{x\in G}f(x)g(x)^{*}.\]
\begin{exercise} Verify the statements just made.
\end{exercise}

\begin{lemma} Let $G$ be a finite Abelian group.
The elements of $\hat{G}$ form an orthonormal
system in  $C(G)$.
\end{lemma}
Does $\hat{G}$ form an orthonormal basis of $C(G)$? The
next lemma tells us how we may hope to resolve this
question.
\begin{lemma} Let $G$ be a finite Abelian group.
The elements of $\hat{G}$  form an orthonormal basis
if and only if, given an element $x\in G$ which is
not the identity, we can find a character $\chi$
with $\chi(x)\neq 1$.
\end{lemma}

The way forward is now clear.
\begin{lemma} 
Suppose that $H$ is a subgroup of a finite Abelian
group  $G$ and that $\chi\in\hat{H}$. If $K$
is a subgroup of $G$ generated by $H$ and an element
$a\in G$, then we can find a $\tilde{\chi}\in\hat{K}$
such that $\tilde{\chi}|H=\chi$.
\end{lemma}
\begin{lemma} Let $G$ be a finite Abelian group
and $x$ an element of $G$ of order $m$. Then
we can find a $\chi\in\hat{G}$ with
$\chi(x)=\exp 2\pi i/m$.
\end{lemma}
\begin{theorem} If $G$ is a finite Abelian group,
then $\hat{G}$ has the same number of elements
as $G$ and they form an orthonormal basis
for $C(G)$.
\end{theorem}
\begin{lemma} If $G$ is a finite Abelian group
and $f\in C(G)$, then
\[f=\sum_{\chi\in\hat{G}}\hat{f}(\chi)\chi\]
where $\hat{f}(\chi)=\langle f,\chi \rangle$.
\end{lemma}
\begin{exercise} Suppose that $G$ is a finite Abelian
group. Show that if we define 
$\theta_{x}:\hat{G}\rightarrow {\mathbb C}$ by
$\theta_{x}(\chi)=\chi(x)$ for $\chi\in \hat{G}$,
$x\in G$, then the map $\Theta:G\rightarrow\Hat{\Hat{G}}$
given by $\Theta(x)=\theta_{x}$ is an isomorphism.

If we now identify $x$ with $\theta_{x}$ (and, so,
$G$ with $\Hat{\Hat{G}}$) show that
\[\Hat{\Hat{f}}(x)=|G|^{-1}f(x^{-1})\]
for all $f\in C(G)$ and $x\in G$.
\end{exercise}     

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 $\hat{G}$.
\begin{lemma} Let $(G,\times)$ be an Abelian group.

(i) Suppose that $x,y\in 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$.
\end{lemma}
\begin{lemma}\label{maximum order}
Let $(G,\times)$ be a finite Abelian group.
Then there exists an integer $N$ and an element $k$
such that $k$ has order $N$ and, whenever $x\in G$,
we have $x^{N}=e$.
\end{lemma}
\begin{exercise}\label{cyclic in field}
Let $p$ be a prime.
Use Lemma~\ref{maximum order}
together with the fact that a polynomial of degree
$k$ can have at most $k$ roots to show that the
multiplicative group $({\mathbb Z}_{p}\setminus\{0\},\times)$
is cyclic.
\end{exercise}
\begin{lemma} With the hypotheses and notation
of Lemma~\ref{maximum order}, we can write $G=K\times H$
where $K$ is the cyclic group generated by $x$
and $H$ is another subgroup of $K$.
\end{lemma}
As usual we write $C_{n}$ for the cyclic group
of order $n$.
\begin{theorem} If $G$ is a finite Abelian group, we can find
$n(1)$, $n(2)$, \dots $n(m)$ with $n(j+1)$ dividing $n(j)$
such that $G$ is isomorphic to 
\[C_{n(1)}\times C_{n(2)}\times \dots C_{n(m)}.\]
\end{theorem}
\begin{lemma} If we have two sequences
$n(1)$, $n(2)$, \dots $n(m)$ with $n(j+1)$ dividing $n(j)$
and
$n'(1)$, $n'(2)$, \dots $n'(m')$ with $n'(j+1)$ dividing $n'(j)$,
then
\[C_{n(1)}\times C_{n(2)}\times \dots C_{n(m)}
\ \text{is isomorphic to}
\ C_{n'(1)}\times C_{n'(2)}\times \dots C_{n'(m')}\]
if and only if $m=m'$ and $n(j)=n'(j)$ for each $1\leq j\leq m$.
\end{lemma}

It is easy to identify $\hat{G}$.
\begin{lemma} Suppose that
\[G=C_{n(1)}\times C_{n(2)}\times \dots C_{n(m)}\]
with $C_{n(j)}$ a cyclic group of order $n(j)$ generated
by $x_{j}$. Then the elements of $\hat{G}$ have the
form 
$\chi_{\omega_{n(1)}^{r(1)},\omega_{n(2)}^{r(2)}},\dots
_{\omega_{n(m)}^{r(m)}}$ with $\omega_{n(j)}=\exp\big(2\pi i/n(j)\big)$
and
\[\chi_{\omega_{n(1)}^{r(1)},\omega_{n(2)}^{r(2)}},\dots
\omega_{n(m)}^{r(m)}(x_{1}^{s(1)}x_{2}^{s(2)}\dots x_{m}^{s(m)})
=\omega_{n(1)}^{r(1)s(1)}\omega_{n(2)}^{r(2)s(2)}\dots
\omega_{n(m)}^{r(m)s(m)}.\]
\end{lemma}
My readers will see that $\hat{G}$ is isomorphic to $G$,
but the more sophisticated algebraists will also
see that this is \emph{not a natural isomorphism}
(whereas $G$ and $\Hat{\Hat{G}}$ are \emph{naturally isomorphic}).
Fortunately such matters are of no importance
for the present course.
\section{The Euler-Dirichlet formula} Dirichlet was interested
in a particular group. If $d$ is a positive integer consider
${\mathbb Z}/(d)$ the set of equivalence classes
\[[m]=\{r:r\equiv m \mod{d}\}\]
under the usual multiplication modulo $d$.
We set
\[G_{d}=\{[m]:\text{$m$ and $d$ coprime}\}\]
and write $\phi(d)$ for the order of $G_{d}$ ($\phi$ is
called Euler's totient function).
\begin{lemma} The set $G_{d}$ forms a finite
Abelian group under
standard multiplication.
\end{lemma}
The results of the previous section show that, if $[a]\in G_{d}$
and we define $\delta_{a}:G_{d}\rightarrow{\mathbb C}$ by
\begin{align*}
\delta_{a}([a])&=1\\
\delta_{a}([m])&=0\qquad \text{if $[m]\neq [a]$},
\end{align*}
then
\[\delta_{a}=\phi(d)^{-1}\sum_{\chi\in G_{d}}\chi([a])^{*}\chi.\]

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,\ \dots, a+nd,\ \dots\]
contains infinitely many primes. Following
Euler's proof that there exist infinitely many primes
we shall seek to prove this by showing that
\[\sum_{\substack{\text{$p$ prime}\\p=a+nd\ \text{for some $n$}}}
\frac{1}{p}=\infty.\]
Henceforward, at least in the number theory part of the 
course $p$ will be a prime,  $\sum_{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 $\chi$ is a character if $\chi$ is a map from
${\mathbb N}$ to ${\mathbb C}$ such that there exists a character
(in the old sense) $\tilde{\chi}\in \hat{G}_{d}$
with
\begin{alignat*}{2}
\chi(m)&=\tilde{\chi}([m])&&\qquad\text{if $m$ and $d$ are coprime}\\
\chi(m)&=0&&\text{otherwise}.
\end{alignat*}
We write $\sum_{\chi}$ to mean the sum over all characters
and take $\chi_{0}$ to be the character with
$\chi_{0}([m])=1$ whenever $m$ and $d$ are coprime.

\begin{lemma} (i) If $\chi$ is a character, then
$\chi(m_{1}m_{2})=\chi(m_{1})\chi(m_{2})$
for all $m_{1},m_{2}\geq 0$.

(ii) If $\chi\neq\chi_{0}$, then
$\sum_{m=k+1}^{k+d}\chi(m)=0$.

(iii) If $\delta_{a}(m)=\phi(d)^{-1}\sum_{\chi}\chi(a)^{*}\chi(m)$
then $\delta_{a}(m)=1$ when $m=a+nd$ and $\delta_{a}(m)=0$
otherwise.

(iv) $\displaystyle{\sum_{p=a+nd}p^{-s}
=\phi(d)^{-1}\sum_{\chi}\chi(a)^{*}\sum_{p}\chi(p)p^{-s}}$.
\end{lemma}
\begin{lemma} The sum $\sum_{p=a+nd}p^{-1}$ diverges if
$\sum_{p}\chi(p)p^{-s}$ remains bounded
as $s$ tends to $1$ through real values of $s>1$
for all $\chi\neq\chi_{0}$.
\end{lemma}

We now prove a new version of Euler's formula.
\begin{theorem}[Euler-Dirichlet formula]
With the notation of this section,
\[\prod_{p}(1-\chi(p)p^{-s})^{-1}=
\sum_{n=1}^{\infty}\chi(n)n^{-s},\]
both sides being absolutely convergent for $\Re s>1$.
\end{theorem}
To link $\prod_{p}(1-\chi(p)p^{-s})^{-1}$
with $\sum_{p}\chi(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
\[{\mathbb C}\setminus\{x:\text{$x$ real and $x\leq 0$}\}\]
defined by $\log (re^{i\theta})=\log r+i\theta$
[$r>0$, $-\pi<\theta<\pi$].
\begin{lemma} (i) If $|z|\leq 1/2$ , then $|\log(1-z)+z|\leq |z|^{2}$.

(ii) If $\epsilon>0$, then $\sum_{p}\log(1-\chi(p)p^{-s})$
and $\sum_{p}\chi(p)p^{-s}$ converge uniformly in 
$\Re s\geq 1+\epsilon$, whilst
\[\left|\sum_{p}\log(1-\chi(p)p^{-s})+\sum_{p}\chi(p)p^{-s}\right|
\leq \sum_{n=1}^{\infty}n^{-2}.\]
\end{lemma}

We have thus shown that if $\sum_{p}\log(1-\chi(p)p^{-s})$
remains bounded as $s\rightarrow 1+$ , then $\sum_{p}\chi(p)p^{-s}$
does. Unfortunately it is not possible to equate 
$\sum_{p}\log(1-\chi(p)p^{-s})$
with $\log(\prod_{p}(1-\chi(p)p^{-s})^{-1})$.

However, we can refresh our spirits by proving Dirichlet's
theorem in some special cases.
\begin{example} There are an infinity of primes 
of the form $3n+1$ and $3n+2$.equate 
$\sum_{p}\log(1-\chi(p)p^{-s})$
with $\log(\prod_{p}(1-\chi(p)p^{-s})^{-1})$.
\end{example}
\begin{exercise} Use the same techniques to show that
there are an infinity of primes 
of the form $4n+1$ and $4n+3$.
\end{exercise} 
\section{Analytic continuation of the Dirichlet functions}
Dirichlet completed his argument without having to consider
$\sum_{n=1}^{\infty}\chi(n)n^{-s}$ for anything other
than real $s$ with $s>1$. However, as we have already seen,
$\sum_{n=1}^{\infty}\chi(n)n^{-s}=L(s,\chi)$ is defined and well
behaved in $\Re s>1$. Riemann showed that it is advantageous
to extend the definition of analytic
functions like $L(s,\chi)$
to larger domains.

There are many ways of obtaining such 
\emph{analytic continuations}. Here is one.
\begin{lemma} If $f:{\mathbb R}\rightarrow{\mathbb C}$
is bounded on ${\mathbb R}$ and 
locally integrable\footnote{Riemann or Lebesgue at
the reader's choice}, then
\[F(s)=\int_{1}^{\infty}f(x)x^{-s}\,dx\]
is a well defined analytic function on the set of $s$ with
$\Re s>1$.equate 
$\sum_{p}\log(1-\chi(p)p^{-s})$
with $\log(\prod_{p}(1-\chi(p)p^{-s})^{-1})$.
\end{lemma}
\begin{lemma}\label{Extend Dirichlet 1} 
(i) If $\chi\neq \chi_{0}$ and 
$S(x)=\sum_{1\leq m\leq x}\chi(m)$, then 
$S:{\mathbb R}\rightarrow{\mathbb C}$ is bounded
and locally integrable. We have
\[\sum_{n=1}^{N}\chi(n)n^{-s}
\rightarrow s\int_{1}^{\infty}S(x)x^{-s-1}\, dx\]
as $N\rightarrow\infty$ for all $s$ with $\Re s>1$.

(ii) If $S_{0}(x)=0$ for $x\leq 0$ and
$S_{0}(x)=\sum_{1\leq m\leq x}\chi_{0}(m)$, then,
writing 
\[T_{0}(x)=S_{0}(x)-d^{-1}\phi(d)x,\]
we see that 
$T_{0}:{\mathbb R}\rightarrow{\mathbb R}$ is bounded
and locally integrable. We have
\[\sum_{n=1}^{N}\chi(n)n^{-s}\rightarrow 
s\int_{1}^{\infty}T_{0}(x)x^{-s-1}\, dx+\frac{\phi(d)s}{d(s-1)}\]
as $N\rightarrow\infty$ for all $s$ with $\Re s>1$.
\end{lemma}
\begin{lemma}\label{Extend Dirichlet 2}
(i) If $\chi\neq\chi_{0}$, there exists an 
function $L(s,\chi)$
analytic on $\{s\in{\mathbb C}:\Re s>0\}$
such that
$\sum_{n=1}^{\infty} \chi(n)n^{-s}$ converges to
$L(s,\chi)$ on
$\{s\in{\mathbb C}:\Re s>1\}$.

(ii) There exists a meromorphic function $L(s,\chi_{0})$
analytic on $\{s\in{\mathbb C}:\Re s>0\}$ except for
a simple pole, residue $\phi(d)/d$ at $1$ such that
$\sum_{n=1}^{\infty} \chi_{0}(n)n^{-s}$ converges to 
$L(s,\chi)$ for $\Re s>1$.
\end{lemma}
\begin{exercise}
(i) Explain carefully why
$L(\ ,\chi_{0})$ is defined uniquely by
the conditions given.

(ii) Show that
$\sum_{n=1}^{\infty} \chi_{0}(n)n^{-s}$ diverges
for $s$ real and $1\geq s >0$.
\end{exercise}

We now take up from where we left off at the end 
of the previous section.
\begin{lemma}  (i) If $\Re s>1$, then
$\exp(-\sum_{p}\log(1-\chi(p)p^{-s})=L(s,\chi)$.

(ii) If $\Re s>1$, then $L(s,\chi)\neq 0$.

(iii) There exists a function $\Log L(s,\chi)$ analytic
on $\{s: \Re s>1\}$ such that $\exp(\Log L(s,\chi))=L(s,\chi)$
for all $s$ with $\Re s>1$.

(iv) If $\chi\neq \chi_{0}$ and
$L(1,\chi)\neq 0$, then $\Log L(s,\chi))$ tends to
a finite limit as $s\rightarrow 1$ through real values with $s>1$.

(v) There is a fixed integer $M_{\chi}$ such that
\[\Log L(s,\chi)+\sum_{p}\log(1-\chi(p)p^{-s})=2\pi M_{\chi}\]
for all $\Re s>1$.

(vi) If $\chi\neq\chi_{0}$ and $L(1,\chi)\neq 0$, then
$\sum_{p}\chi(p)p^{-s}$ remains bounded as 
$s\rightarrow 1$ through real values with $s>1$.
\end{lemma}

We mark our progress with a theorem.
\begin{theorem} If $L(1,\chi)\neq 0$ for all $\chi\neq\chi_{0}$
then there are an infinity of primes of the form
$a+nd$.
\end{theorem}

Since it is easy to find the characters $\chi$ in any given case
and since it is then easy to compute $\sum_{n=1}^{N}\chi(n)n^{-1}$
and to estimate the error $\sum_{n=N+1}^{\infty}\chi(n)n^{-1}$
to sufficient accuracy to prove that
$L(1,\chi)=\sum_{n=1}^{\infty}\chi(n)n^{-1}\neq 0$,
it now becomes possible to prove Dirichlet's theorem
for any particular coprime  $a$ and $d$.
\begin{exercise} Choose $a$ and $d$ and carry out the
program just suggested.
\end{exercise}
However, we still need to show that the  theorem holds
in all cases.
\section{$L(1,\chi)$ is not zero} Our first steps are easy.
\begin{lemma} (i) If $s$ is real and $s>1$, then
\[\prod_{\chi}L(s,\chi)=
\exp(-\sum_{p}\sum_{\chi}\log(1-\chi(p)p^{-s}).\]

(ii) If $s$ is real and $s>1$, then $\prod_{\chi}L(s,\chi)$
is real and $\prod_{\chi}L(s,\chi)\geq 1$.

(iii) $\prod_{\chi}L(s,\chi)\nrightarrow 0$ as
$s\rightarrow 1$.
\end{lemma}
\begin{lemma} (i) There can be at most one character
$\chi$ with $L(1,\chi)=0$.

(ii) If a character $\chi$ takes non-real values
then $L(1,\chi)\neq 0$.
\end{lemma}

We have thus reduced the proof of Dirichlet's theorem
to showing that if  $\chi$ is a character
with $\chi\neq \chi_{0}$ which only
takes the values $1$, $-1$ and $0$, then $L(1,\chi)\neq 0$.
There are several approaches to this problem, but
none are short and transparent. We use a proof
of de la Vall{\'{e}}e Poussin which is quite short,
but not, I think, transparent.
\begin{lemma}\label{Smoke 1} Suppose that the
character $\chi\neq \chi_{0}$ and only
takes the values $1$, $-1$ and $0$. Set
\[\psi(s)=\frac{L(s,\chi)L(s,\chi_{0})}{L(2s,\chi_{0})}.\]

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

(ii) If  $L(1,\chi)=0$, then $1$ is a removable singularity
and $\psi$ is analytic everywhere on $\{s:\Re s>\frac{1}{2}\}$.

(iii) We have $\psi(s)\rightarrow 0$ as $s\rightarrow \frac{1}{2}$
through real values of $s$ with $s\geq \frac{1}{2}$.
\end{lemma}
\begin{lemma}~\label{Smoke 2}
We adopt the hypotheses and notation of
Lemma~\ref{Smoke 1}. If $\Re s>1$, then the following is true.

(i) ${\displaystyle
\psi(s)=\prod_{\chi(p)=1}\frac{1+p^{-s}}{1-p^{-s}}.}$

(ii) We can find subsets $Q_{1}$ and $Q_{2}$ of $\mathbb{Z}$
such that
\begin{align*}
\prod_{\chi(p)=1}(1+p^{-s})&=\sum_{n\in Q_{1}}n^{-s}\\
\prod_{\chi(p)=1}(1-p^{-s})^{-1}&=\sum_{n\in Q_{2}}n^{-s}.
\end{align*}

(iii) There is a sequence of real positive numbers $a_{n}$
with $a_{1}=1$ such that
\[\psi(s)=\sum_{n=1}^{\infty}a_{n}n^{-s}.\]
\end{lemma}
\begin{lemma} We adopt the hypotheses and notation of
Lemmas~\ref{Smoke 1} and~\ref{Smoke 2}.

(i) If $\Re s>1$, then
\[\psi^{(m)}(s)=\sum_{n=1}^{\infty}a_{n}(-\log n)^{m}n^{-s}.\]

(ii) If $\Re s>1$, then $(-1)^{m}\psi^{(m)}(s)>0$.

(iii) If $\psi$ has no pole at $1$, then, if $\Re s_{0}>1$
and $|s-s_{0}|<\Re s_{0}-1/2$, we have
\[\psi(s)=\sum_{m=0}^{\infty}
\frac{\psi^{(m)}(s_{0})}{m!}(s-s_{0})^{m}.\]

(iv) If $\psi$ has no pole at $1$, then
$\psi(s)\nrightarrow 0$ as $s\rightarrow \frac{1}{2}$
through real values of $s$ with $s\geq \frac{1}{2}$.
\end{lemma}

We have proved the result we set out to obtain.
\begin{lemma} If a character $\chi\neq\chi_{0}$ 
only takes real values
then $L(1,\chi)\neq 0$.
\end{lemma}
\begin{theorem} If $\chi\neq\chi_{0}$, then $L(1,\chi)\neq 0$.
\end{theorem}
We have thus proved Theorem~\ref{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.
\section{Chebychev and the distribution of primes}
On the strength of numerical evidence, Gauss was
led to conjecture that the number $\pi(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\footnote{His preferred transliteration
seems to have been Tchebycheff, but he has
been over-ruled.}. 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\geq 1$,
$\prod_{n<p\leq 2n}$ means the product over all primes 
$p$ with $n<p\leq 2n$ and so on. It is sometimes
useful to exclude small values of $n$.)
\begin{lemma}\label{Chebychev lemma} (i) ${\displaystyle
2^{n}<\binom{2n}{n}<2^{2n}}$.

(ii) ${\displaystyle \binom{2n}{n}\ \text{divides}
\ \prod_{p<2n} p^{[(\log 2n)/(\log p)]}}$
and 
${\displaystyle \prod_{n<p\leq 2n} p\ \text{divides}
\ \binom{2n}{n}}$.

(iii) We have $\pi(2n)>(\log 2)n/(\log 2n)$.

(iv)  There exists a constant $A>0$ such that
$\pi(n)\geq An(\log n)^{-1}$.

(v) There exists a constant $B'$ such that
$\sum_{p\leq n} \log p\leq B'n$.

(vi)There exists a constant $B$ such that
$\pi(n)\leq Bn(\log n)^{-1}$.
\end{lemma}
We restate the main conclusions of Lemma~\ref{Chebychev lemma}.
\begin{theorem}[Chebychev]\label{Chebychev theorem} 
There exist constants $A$ and $B$
with $0<A\leq B$ such that
\[An(\log n)^{-1}\leq\pi(n)\leq Bn(\log n)^{-1}.\]
\end{theorem}

Riemann's approach to the prime number theorem involves
considering $\theta(n)=\sum_{p\leq n}\log p$ rather than
$\pi(n)$.
\begin{lemma} Let $Q$ be a set of positive integers
and write $\alpha(n)=\sum_{q\in Q,q\leq n} 1$ 
and $\beta(n)=\sum_{q\in Q,q\leq n} \log q$.

(i) There exist constants $A$ and $B$
with $0<A\leq B$ such that
\[An(\log n)^{-1}\leq\alpha(n)\leq Bn(\log n)^{-1}.\]
if and only if there exist constants $A'$ and $B'$
with $0<A\leq B$ such that
\[A'n\leq\beta(n)\leq B'n.\]

(ii) We have $n^{-1}(\log n)\alpha(n)\rightarrow 1$
as $n\rightarrow\infty$
if and only if $n^{-1}\beta(n)\rightarrow 1$
as $n\rightarrow\infty$.
\end{lemma}
\begin{lemma}\label{logarithm transfer}
If $n^{-1}\theta(n)\rightarrow 1$
as $n\rightarrow\infty$, then
$n^{-1}(\log n)\pi(n)\rightarrow 1$
as $n\rightarrow\infty$.
\end{lemma}
\section{The prime number theorem}\label{S;prime number} 
We start by recalling various
facts about the Laplace transform.
\begin{definition}
If $a$ is a real number,
let us write ${\mathcal E}_{a}$  for the collection
of piecewise continuous
functions $F:{\mathbb R}\rightarrow{\mathbb C}$
such that $F(t)=0$ for all $t<0$ and
$F(t)e^{-at}\rightarrow 0$ as $t\rightarrow\infty$.
If $F\in {\mathcal E}_{a}$, we define the
\emph{Laplace transform} of $F$ by
\[({\mathcal L}F)(z)=\int_{-\infty}^{\infty}F(t)\exp(-zt)\,dt\]
for $\Re z>a$.
\end{definition}
\begin{lemma} If $F\in {\mathcal E}_{a}$, then 
$({\mathcal L}F)(z)$ is well defined.
\end{lemma}


\begin{lemma}\label{Laplace}
(i) If $F\in {\mathcal E}_{a}$, then 
$({\mathcal L}F)(z)$
analytic on $\{z\in{\mathbb C}:\Re z>a\}$.

(ii) We  define the Heaviside function $H$ by
writing $H(t)=0$ for $t<0$ and $H(t)=1$ for $t\geq 0$.
If $a\in {\mathbb R}$ and $b\geq 0$ set
$H_{a,b}(t)=H(t-b)e^{at}$. Then $H_{a,b}\in {\mathcal E}_{a}$
and ${\mathcal L}H_{a,b}(z)$ can be extended
to a meromorphic function on ${\mathbb C}$ with a simple
pole at $a$. 
\end{lemma}
\begin{exercise} (Uses Exercise~\ref{Crude uniqueness}.) 
Let $F,G\in {\mathcal E}_{a}$ for some $a\in{\mathbb R}$.

(i) Suppose that there exists a $b>a$ such
that $({\mathcal L}F)(z)=({\mathcal L}G)(z)$ for
all $z$ with $\Re z=b$. Show that $F=G$.

(ii) Suppose that there exist distinct $z_{n}\in{\mathbb C}$
with $\Re z_{n}>a$ $[n\geq 0]$ such that $z_{n}\rightarrow z_{0}$
and $({\mathcal L}F)(z_{n})=({\mathcal L}G)(z_{n})$
$[n\geq 0]$. Show that $F=G$.
\end{exercise}

Engineers are convinced that the converse to 
Lemma~\ref{Laplace}~(i) holds in the sense that if
$F\in {\mathcal E}_{a}$ has a Laplace transform $f$
which can be extended to a function $\tilde{f}$
analytic on $\{z\in{\mathbb C}:\Re z>b\}$ 
[$a$, $b$ real, $a\geq b$], then $F\in {\mathcal 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
\[{\mathcal M}F(z)=\int_{0}^{\infty}F(t)t^{z-1}\,dt\]
in preference to the Laplace transform but the
two transforms are simply related.
\begin{exercise} Give the relation explicitly.
\end{exercise}

Riemann considered the two functions
\[\Phi(s)=\sum_{p}p^{-s}\log p\]
and the \emph{Riemann zeta function}
\[\zeta(s)=\sum_{n=1}^{\infty}n^{-s}.\]
Both of these functions are defined for $\Re 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~\ref{Extend Dirichlet 1}~(ii)
and~\ref{Extend Dirichlet 2}~(ii).
\begin{lemma} 
(i) Let $S_{0}(x)=0$ for $x\leq 0$ and
$S_{0}(x)=\sum_{1\leq m\leq x}1$. If
\[T_{0}(x)=S_{0}(x)-x,\]
then $T_{0}$ is bounded
and locally integrable. We have
\[\sum_{n=1}^{N}n^{-s}\rightarrow 
s\int_{1}^{\infty}T_{0}(x)x^{-s-1}\, dx+\frac{s}{s-1}\]
as $N\rightarrow\infty$ for all $s$ with $\Re s>1$.

(ii) There exists a meromorphic function $\zeta$
analytic on $\{s\in{\mathbb C}:\Re s>0\}$ except for
a simple pole, residue $1$ at $1$ such that
$\sum_{n=1}^{\infty}n^{-s}$ converges to 
$\zeta(s)$ for $\Re s>1$.

(iii) If $\Re s>1$, then
\[\sum_{p\leq N}\frac{\log p}{p^{s}}
\rightarrow 
s\int_{1}^{\infty}\theta(x)x^{-s-1}\, dx\]
as $N\rightarrow\infty$.
\end{lemma}
The use of $s$ rather than $z$ goes back to Riemann.
Riemann showed that $\zeta$ can be extended to a meromorphic
function over ${\mathbb C},$ but we shall not need this.

How does this help us study $\Phi$?
\begin{lemma}\label{extend half}
(i) We have $\prod_{p<N}(1-p^{-s})^{-1}\rightarrow \zeta(s)$
uniformly for $\Re s>1+\delta$ whenever $\delta>0$.

(ii) We have
\[\frac{\zeta'(s)}{\zeta(s)}=-\sum_{p}\frac{\log p}{p^{s}-1}\]
for all $\Re s>1$.

(iii) We have
\[\Phi(s)=-\frac{\zeta'(s)}{\zeta(s)}-
\sum_{p}\frac{\log p}{(p^{s}-1)p^{s}}\]
for all $\Re s>1$.

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


The next exercise is long and will not be used later but is,
I think, instructive.
\begin{exercise} (i) Show by grouping in pairs
that $\sum_{n=1}^{\infty}(-1)^{n-1}n^{-s}$
converges to an analytic function $g(s)$ in the
region $\{s:\Re s>0\}$.

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

(iii) Show that $g(1/2)\neq 0$ and deduce that $\zeta(1/2)\neq 0$.

(iv) By imitating the arguments of Lemma~\ref{extend half},
show that we we can find an analytic function $G$ defined
on $\{s:\Re s>1/3\}$ such that
\[\Phi(s)=-\frac{\zeta'(s)}{\zeta(s)}-\Phi(2s)-G(s).\]
Deduce that $\Phi$ can be extended to a meromorphic
function on $\{s:\Re s>1/3\}$. 

(v) Show, using (iii), that $\Phi$ has a pole at $1/2$.

(vi) Show that the assumption that 
$|\sum_{p<N}\log p -N|\leq A N^{1/2-\epsilon}$ for
some $\epsilon>0$ and $A>0$ and all large enough $N$
leads to the conclusion that
$\Phi$ can be analytically extended from $\{s:\Re s>1\}$
to an everywhere analytic function
on $\{s:\Re s>1/2-\epsilon\}$.

(vii) Deduce that if $\epsilon>0$ and $A>0$
\[|\sum_{p<N}\log p -N|\geq A N^{1/2-\epsilon}
\ \text{for infinitely many values of $N$.}\]
\end{exercise}

It is well known that Riemann conjectured that $\zeta$
has no zeros in $\{s:\Re 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}e Poussin and show that $\zeta$
has no zero on $\{s:\Re 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)\neq 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$.)
\begin{lemma} Suppose that $\zeta$ has a zero of order
$\mu$ at $1+i\alpha$ 
and a zero of order $\nu$ at $1+2i\alpha$
with $\alpha$ real and $\alpha>0$. Then
the following results hold.

(i) $\zeta$ has a zero of order $\mu$ at $1-i\alpha$
and a zero of order $\nu$ at $1-2i\alpha$.

(ii) As $\epsilon\rightarrow 0$ through
real positive values of $\epsilon$
\begin{align*}
\epsilon\Phi(1+\epsilon \pm i\alpha)&\rightarrow -\mu\\
\epsilon\Phi(1+\epsilon \pm 2i\alpha)&\rightarrow -\nu\\
\epsilon\Phi(1+\epsilon)&\rightarrow 1.
\end{align*}

(iii) If $s=1+\epsilon$ with $\epsilon$ real and positive,
then
\begin{align*}
0&\leq\sum_{p}p^{-s}\log p (e^{(i\alpha\log p)/2}+
e^{-(i\alpha\log p)/2})^{4}\\
&=\Phi(s+2i\alpha)+\Phi(s-2i\alpha)
+4(\Phi(s+i\alpha)+\Phi(s-i\alpha))
+6\Phi(s).
\end{align*}

(iv) We have $0\leq-2\nu-8\mu+6$.
\end{lemma}
\begin{theorem} If $\Re s=1$, then $\zeta(s)\neq 0$.
\end{theorem}
We note the following trivial consequence.
\begin{lemma}
If we write
\[T(s)=\frac{\zeta'(s)}{\zeta(s)}-(s-1)^{-1},\]
then given any $R>0$ we can find a $\delta(R)$
such that $T$ has no poles in
\[\{z:\Re z\geq 1-\delta(R),\ |\Im z|\leq R\}.\]
\end{lemma}

We shall show that the results we have obtained on 
the behaviour of $\zeta$ suffice to show that
\[\int_{1}^{X}\frac{\theta(x)-x}{x^{2}}\,dx\]
tends to a finite limit as $X\rightarrow\infty$.
The next lemma shows that this is sufficient to
give the prime number theorem.
\begin{lemma} Suppose that 
$\beta:[1,\infty)\rightarrow{\mathbb R}$
is an increasing (so integrable) function.

(i) If $\lambda>1$, $y>1$ and $y^{-1}\beta(y)>\lambda$,
then
\[\int_{y}^{\lambda y}\frac{\beta(x)-x}{x^{2}}\,dx
\geq A(\lambda)\]
where $A(\lambda)$ is a strictly positive number
depending only on $\lambda$.

(ii) If 
\[\int_{1}^{X}\frac{\beta(x)-x}{x^{2}}\,dx\]
tends to limit as $X\rightarrow\infty$, then
$x^{-1}\beta(x)\rightarrow 1$ as $x\rightarrow\infty$.
\end{lemma}

We need a couple of further preliminaries.
First we note a simple consequence of the Chebychev
estimates (Theorem~\ref{Chebychev theorem}).
\begin{lemma} There exists a constant $1>K>0$
such that
\[\frac{|\theta(x)-x|}{x}\leq K\]
for all $x$ sufficiently large.
\end{lemma}
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.)
\begin{lemma} Let $f(t)=\theta(e^{t})e^{-t}-1$ for
$t\geq 0$ and $f(t)=0$ otherwise. Then
\[\mathcal{L}f(z)=\int_{-\infty}^{\infty}f(t)e^{-tz}\,dt\]
is well defined and 
\[\mathcal{L}f(z)=\frac{\Phi(z+1)}{z+1}-\frac{1}{z}\]
for all $\Re z>0$.

The statement $\int_{1}^{\infty}(\theta(x)-x)/x^{2}\,dx$
convergent is equivalent to the statement that
$\int_{-\infty}^{\infty}f(t)\,dt$ converges.
\end{lemma}

We have reduced the proof of the prime number theorem
to the proof of the following lemma.
\begin{lemma} Suppose $\Omega$ is an open set
with $\Omega\supseteq \{z:\Re z\geq 0\}$,
$F:\Omega\rightarrow{\mathbb C}$  is an analytic
function and $f:[0,\infty]\rightarrow{\mathbb R}$
is bounded locally integrable function such that
\[F(z)=\mathcal{L}f(z)=\int_{0}^{\infty}f(t)e^{-tz}\,dt\]
for $\Re z>0$. Then $\int_{0}^{\infty}f(t)\,dt$ converges.
\end{lemma}
This lemma and its use to prove the prime number theorem
are due to D.~Newman. (A version will be found in~\cite{Newman}.)
\section{The Fourier transform and Heisenberg's inequality}%
\label{Heisenberg section} In this section we return to the
Fourier transform on ${\mathbb R}$. We follow a slightly
different path to that mapped out in Section~\ref{brief}.
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\pi)^{-1/2}\exp(-x^{2}/2)$.
\begin{lemma}\label{Fourier of Gauss}
$\hat{E}(\lambda)=(2\pi)^{1/2}E(\lambda)$.
\end{lemma}
\begin{exercise} If I prove Lemma~\ref{Fourier of Gauss}
I shall do so by setting up a differential equation.
Obtain Lemma~\ref{Fourier of Gauss}  by complex variable
techniques.
\end{exercise}

We use the following neat formula.
\begin{lemma}\label{neat} If $f,g\in L^{1}({\mathbb R})$
then the products 
$\hat{f}\times g,\ f\times\hat{g}\in L^{1}({\mathbb R})$
and
\[\int_{-\infty}^{\infty}\hat{f}(x)g(x)\,dx
=\int_{-\infty}^{\infty}f(\lambda)\hat{g}(\lambda)
\,d\lambda.\]
\end{lemma}

\begin{exercise} (For those using Riemann integration.
You will need to refer back to the exercises in
Section~\ref{brief}.) Suppose that $f$ and $g$ are continuous 
and
there exists a real constant $A$ such that
\[|f(x)|,|g(x)|\leq A(1+x^{2})^{-1}\]
for all $x$ and
\[|\hat{f}(\lambda)|,|\hat{g}(\lambda)|\leq A(1+\lambda^{2})^{-1}\]
for all $\lambda$. Show that
\[\int_{-\infty}^{\infty}\hat{f}(x)g(x)\,dx
=\int_{-\infty}^{\infty}f(\lambda)\hat{g}(\lambda)\,d\lambda.\]
Without going into detail, convince yourself that
the hypothesis `$f$ and $g$ are continuous'
can be replaced by `$f$ and $g$ are piecewise continuous'.
\end{exercise}

By taking $f=E_{h}$ where 
$E_{h}(x)=h^{-1}E(h^{-1}(x))$ $[h>0]$ in Lemma~\ref{neat}
we obtain a nice pointwise inversion result.
\begin{theorem}\label{Lebesgue point} 
If $f,\hat{f}\in L^{1}$ and $f$ is continuous
at $t$, then $\Hat{\Hat{f}}(t)=2\pi f(-t)$.
\end{theorem} 
\begin{exercise}\label{Riemann point} 
(For those using Riemann integration.)
Suppose that $f$ is piecewise continuous and
there exists a real constant $A$ such that
\[|f(x)|\leq A(1+x^{2})^{-1}\]
for all $x$ and
\[|\hat{f}(\lambda)|\leq A(1+\lambda^{2})^{-1}\]
for all $\lambda$. Show that if $f$ is continuous
at $t$, then $\Hat{\Hat{f}}(t)=2\pi f(-t)$.
\end{exercise}
\begin{exercise} Suppose that $f$ satisfies the conditions
of Theorem~\ref{Lebesgue point} (if you use Lebesgue integration)
or Exercise~\ref{Riemann point} (if you use Riemann integration).
If $t$ is a point where $f(t+)=\lim_{h\rightarrow 0+}f(t+h)$
and $f(t-)=\lim_{h\rightarrow 0+}f(t-h)$ both exist,
show that
\[\Hat{\Hat{f}}(-t)=\pi(f(t+)+f(t-)).\]
\end{exercise}
\begin{lemma} {\bf (Parseval's equality)} 
If
$f$ and $\hat{f}$ are continuous and integrable and 
$\hat{\hat{f}}(t)=2\pi f(-t)$ for all $t$
then
\[\int_{\mathbb R}|f(t)|^{2}\,dt=
\frac{1}{2\pi}\int_{\mathbb R}|\hat{f}(\lambda)|^{2}\,d\lambda.\]
\end{lemma}
(A less ad hoc version of Parseval's equality is
given in Exercise~\ref{Hilbert dual}~(v).)
\begin{exercise}\label{Hilbert dual}
(This requires Lebesgue measure.)
The present course is rather old fashioned, not least
in the way it thinks of Fourier transforms $\hat{f}$
in terms of its values $\hat{f}(\lambda)$ at points $\lambda$,
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)\rightarrow 0\]
as $|x|\rightarrow\infty$ for all integers $n,m\geq 0$.
Show that, if $f\in S$, then $\hat{f}\in S$.

(ii) Let ${\mathbb I}_{[a,b]}(x)=1$ for $x\in [a,b]$,
${\mathbb I}_{[a,b]}(x)=0$ otherwise.
Show that, if $E_{h}$ is defined as above, then
\[\|{\mathbb I}_{[a,b]}-E_{h}*{\mathbb I}_{[a,b]}\|_{2}
\rightarrow 0\]
as $h\rightarrow 0+$.
Deduce, or prove otherwise, that $S$ is $L^{2}$ norm dense
in $L^{2}$.

(iii)  By taking $g=\hat{f}$ in Lemma~\ref{neat} show that
\[\|\hat{f}\|_{2}^{2}=2\pi \|f\|_{2}^{2}\]
for all $f\in S$.

(iii) Deduce that there is a unique continuous mapping 
${\mathcal F}:L^{2}\rightarrow L^{2}$ with ${\mathcal F}(f)=\hat{f}$
for all $f\in S$. (Uniqueness is easy  but you should take care
proving existence.)

(iv) Show that ${\mathcal F}:L^{2}\rightarrow L^{2}$ is linear
and that
\[\|{\mathcal F}(f)\|_{2}^{2}=2\pi \|f\|_{2}^{2}\]
for all $f\in L^{2}$.

If we define ${\mathcal J}:L^{2}\rightarrow L^{2}$ by
$({\mathcal J}f)(t)=f(-t)$ show that 
${\mathcal F}^{2}=2\pi{\mathcal J}$.

(v) If we wish to work in $L^{2}$, it makes sense to use
a different normalising factor and call 
${\mathcal G}=(2\pi)^{-1/2}{\mathcal F}$ the Fourier
transform. Show that ${\mathcal G}^{4}=I$ and that
${\mathcal G}:L^{2}\rightarrow L^{2}$ is a bijective linear
isometry.

(vi) (Parseval's equality) Show that, if we work in $L^{2}$
\[\int_{\mathbb R}
{\mathcal G}f(\lambda)({\mathcal G}g)^{*}(\lambda)
\,d\lambda=\int_{\mathbb R}f(t)g(t)^{*}\,dt.\]
\end{exercise}
 
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).
\begin{theorem}[Heisenberg's inequality]\label{Heisenberg}
If $f$ is reasonably well behaved, then
\[
\frac
{\int_{-\infty}^{\infty}\lambda^{2}|\hat{f}(\lambda)|^{2}\,d\lambda} 
{\int_{-\infty}^{\infty}|\hat{f}(\lambda)|^{2}\,d\lambda}
\times
\frac
{\int_{-\infty}^{\infty}x^{2}|f(x)|^{2}\,dx} 
{\int_{-\infty}^{\infty}|f(x)|^{2}\,dx}
\geq \frac{1}{4}.
\]
If equality holds, then $f(x)=A\exp(-bx^{2})$ for some $b>0$.
\end{theorem}
\begin{exercise} Write down explicit conditions for
Theorem~\ref{Heisenberg}.
\end{exercise}               
The extension of Heisenberg's inequality to all
$f\in L^{2}$ is given in Section~2.8 of the
beautiful book~\cite{Dym} of Dym and McKean.
\section{The Poisson formula}\label{Poisson section} 
The following
remarkable observation is called Poisson's formula.
\begin{theorem}\label{Poisson}
Suppose that 
$f:{\mathbb R}\rightarrow{\mathbb C}$ is a continuous
function such that $\sum_{m=-\infty}^{\infty}|\hat{f}(m)|$
converges and $\sum_{n=-\infty}^{\infty}|f(2\pi n+x)|$
converges uniformly on $[-\pi,\pi]$. Then
\[\sum_{m=-\infty}^{\infty}\hat{f}(m)=
2\pi\sum_{n=-\infty}^{\infty}f(2\pi n).\]
\end{theorem}

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.
\begin{lemma}\label{simple needs}
If $f:{\mathbb R}\rightarrow{\mathbb C}$ 
is a twice continuously differentiable function such 
that $\int_{-\infty}^{\infty}|f(x)|\,dx$,
$\int_{-\infty}^{\infty}|f'(x)|\,dx$
and $\int_{-\infty}^{\infty}|f''(x)|\,dx$ 
converge whilst $f'(x)\rightarrow 0$ 
and $x^{2}f(x)\rightarrow 0$ as $|x|\rightarrow\infty$,
then $f$ satisfies the conditions of Theorem~\ref{Poisson}.
\end{lemma}

\begin{exercise} (i) By applying Poisson's formula to the function
$f$ defined by $f(x)=\exp(-t|x|/2\pi)$, show that
\[2(1-e^{-t})^{-1}
=\sum_{n=-\infty}^{\infty}2t(t^{2}+4\pi^{2}n^{2})^{-1}.\]

(ii) By expanding $(t^{2}+4\pi n^{2})^{-1}$ and
(carefully) interchanging sums, deduce that
\[2(1-e^{-t})^{-1}=1+2t^{-1}+\sum_{m=0}^{\infty}c_{m}t^{m}\]
where $c_{2m}=0$ and
\[c_{2m+1}=a_{2m+1}\sum_{n=1}^{\infty}n^{-2m}\]
for some value of $a_{2m+1}$ to be given explicitly.

(iii) Hence obtain Euler's formula
\[\sum_{n=1}^{\infty}n^{-2m}=
(-1)^{m-1}2^{2m-1}b_{2m-1}\pi^{2m}/(2m-1)!\]
for $m\geq 1$, where the $b_{m}$ are defined by the formula
\[(e^{y}-1)^{-1}=y^{-1}-2^{-1}+\sum_{n=1}^{\infty}b_{n}y^{n}/n!\]
(The $b_{n}$ are called Bernoulli numbers.)
\end{exercise}
\begin{exercise} Suppose $f$ satisfies the conditions of
Lemma~\ref{simple needs}. Show that
\[K\sum_{m=-\infty}^{\infty}\hat{f}(Km)=
2\pi \sum_{n=-\infty}^{\infty}f(2\pi K^{-1}n)\]
for all $K>0$. What is the corresponding result when $K<0$?

By letting $K\rightarrow 0+$, deduce that
\[\Hat{\Hat{f}}(0)=2\pi 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
\[\Hat{\Hat{f}}(t)=2\pi f(-t)\]
for all $t$.
\end{exercise}

Poisson's formula has a particularly interesting consequence.
\begin{lemma} If $g:{\mathbb R}\rightarrow{\mathbb C}$
is twice continuously differentiable and
$g(t)=0$ for $|t|\geq \pi$, then $g$ is completely
determined by the values of $\hat{g}(m)$ for
integer $m$.
\end{lemma}
Taking $g=\hat{f}$ and remembering the inversion formula
we obtain the following result.
\begin{pretheorem}\label{before Shannon}
If $f:{\mathbb R}\rightarrow{\mathbb C}$
is a well behaved function with $\hat{f}(\lambda)=0$
for $|\lambda|\geq\pi$,
then $f$ is determined by its values at integer
points.
\end{pretheorem}
We call this a pretheorem because we have not specified
what `well behaved' should mean. 

The simplest approach is via the \emph{sinc function}
\[\sinc(x)=\frac{1}{2\pi}\int_{-\pi}^{\pi}\exp(ix\lambda)\,d\lambda.\]
We state the most immediately useful properties 
of  $\sinc$.
\begin{lemma}
(i) $\sinc(0)=1$,

(ii) $\sinc(n)=0$ if $n\in{\mathbb Z}$ but $n\neq 0$.
\end{lemma}

(We note also that although, strictly speaking,
$\widehat{\sinc}(\lambda)$ is not defined 
for us, since $\int|\sinc (x)|\,dx=\infty$,
we are strongly tempted to say that
$\widehat{\sinc}(\lambda)=1$ if $|\lambda|<\pi$
and 
$\widehat{\sinc}(\lambda)=0$ if $|\lambda|>\pi$.)

We can, at once, prove that Pretheorem~\ref{before Shannon}
is best possible.
\begin{lemma}\label{Shannon best}
If $\epsilon>0$, then we can find an
infinitely differentiable non-zero $f$ such that
$\hat{f}(\lambda)=0$ for $|\lambda|>\pi+\epsilon$,
but $f(n)=0$ for all $n\in{\mathbb Z}$.
\end{lemma}
\begin{exercise} In Lemma~\ref{Shannon best} show that
we can take $f\in S$ where $S$ is the class discussed in
Exercise~\ref{Hilbert dual}.
\end{exercise}

We can also show how to recover the function of
Pretheorem~\ref{before Shannon} from its values
at integer points.
\begin{theorem}\label{Shannon constructive}
Suppose $f:{\mathbb R}\rightarrow{\mathbb C}$
is a continuous function with 
$\int_{-\infty}^{\infty}|f(t)|\,dt<\infty$.
If $\hat{f}(\lambda)=0$
for $|\lambda|\geq\pi$,
then 
\[\sum_{n=-N}^{N}f(n)\sinc(t-n)\rightarrow f(t)\]
as uniformly as $N\rightarrow\infty$.
\end{theorem}
Thus Pretheorem~\ref{before Shannon} holds under 
very general conditions. We state it in a lightly
generalised form.
\begin{theorem}[Shannon's Theorem]~\label{Shannon}
Suppose that $f:{\mathbb R}\rightarrow{\mathbb C}$
is a continuous function with 
$\int_{-\infty}^{\infty}|f(t)|\,dt<\infty$
and that $K>0$.
If $\hat{f}(\lambda)=0$
for $|\lambda|\geq K$,
then $f$ is determined by its values at points of the form 
$n\pi K^{-1}$ with $n\in{\mathbb Z}$.
\end{theorem}

Theorem~\ref{Shannon} belongs to the same circle of ideas
as Heisenberg's inequality. It is the key to such devices
as the CD.

\section{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~\cite{Helson} and Katznelson~\cite{Katznelson}
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~\cite{Dym}.
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~\cite{Zygmund} is a must
and, if you would like a first glimpse
at wavelets, (unmentioned in this course)
Babarah Hubbard's popularisation 
\emph{The World According to Wavelets}~\cite{Hubbard}
is splendid light reading.
 
  
There is an excellent treatment of Dirichlet's
theorem and much more in Davenport's
\emph{Multiplicative Number Theory}~\cite{Davenport}.
[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~\cite{Patterson}.

In preparing this course I have also used~\cite{Korner1}
and~\cite{Korner2} since I find the author sympathetic.
\begin{thebibliography}{99}
\bibitem{Newman} J.~Bak and D.~J.~Newman
\emph{Complex Analysis}
Springer, New York, 1982.
\bibitem{Davenport} H.~Davenport
\emph{Multiplicative Number Theory}
(2nd Edition), Springer, New York, 1980.
\bibitem{Dym} H.~Dym and H.~P.~McKean
\emph{Fourier Series and Integrals}
Academic Press, 1972.
\bibitem{Helson} H.~Helson
\emph{Harmonic Analysis}
Adison--Wesley, 1983.
\bibitem{Hubbard} B. Hubbard
\emph{The World According to Wavelets}
A.~K.~Peters, 1996. 
\bibitem{Katznelson} Y.~Katznelson
\emph{An Introduction to Harmonic Analysis}
Wiley, 1963. [There is a CUP reprint]
\bibitem{Korner1} T.~W.~K\"{o}rner 
\emph{Fourier Analysis}
CUP, 1988.
\bibitem{Korner2} T.~W.~K\"{o}rner 
\emph{Exercises for Fourier Analysis}
CUP, 1993.
\bibitem{Patterson} S.~J.~Patterson
\emph{An Introduction to the Theory of the Riemann zeta-function}
CUP, 1988.
\bibitem{Zygmund} A.~Zygmund
\emph{Trigonometric Series} (2 Volumes)
CUP, 1959. 
\end{thebibliography}
\end{document}
