\documentclass[12pt,a4paper]{article}
\usepackage{amsmath,amsxtra,amsthm,amssymb,makeidx,graphics}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheoremstyle{citing}{3pt}{3pt}{\itshape}{0pt}{\bfseries}%
{.}{ }{\thmnote{#3}}\theoremstyle{citing}\newtheorem*{varthm}{}
\DeclareMathOperator{\var}{var}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Int}{Int}
\renewcommand{\emptyset}{\varnothing}
\theoremstyle{remark}
\newtheorem{question}[theorem]{Exercise}
\makeindex
\begin{document}
\title{Topics in Analysis}
\author{T.~W.~K\"{o}rner}
\maketitle
\begin{footnotesize}
{\bf Small print}
This course is not intended as a foundation
for further courses, so the lecturer is allowed substantial 
flexibility. Exam questions will be set on the course as given
(so, if I do not have time to cover everything in these notes,
the topics examined will be those actually lectured)
and will only cover topics in these notes. Unless there
is more time to spare than I expect, I will not talk about
topological spaces but confine myself to ordinary Euclidean
spaces ${\mathbb R}^{n}$, ${\mathbb C}$ and complete
metric spaces.

These notes lay out the results of the course. There is
a separate set of notes giving the associated proofs,
but those notes are intended for home use and not
as a means of following the live lectures. 

I can provide some notes on the exercises
for supervisors by e-mail. The exercises themselves
form sections~\ref{S;sheet one} to~\ref{S;sheet four}
of these notes.

These notes are written in
\LaTeXe\ and should be available
in tex, ps, pdf and dvi format
from my home page
\begin{center}
{\bf http://www.dpmms.cam.ac.uk/\~{}twk/}
\end{center}
\end{footnotesize}
\newpage
\tableofcontents
\newpage
\section{Metric spaces}\label{S;metric} This section is devoted to 
fairly formal preliminaries. Things get more interesting
in the next section and the course gets fully under way
in the third.
Both those students who find the early material worryingly
familiar and those who find it worryingly unfamiliar are asked
to suspend judgement until then.

Most Part~II students will
be familiar with the notion of a metric space.
\begin{definition}\label{D;metric}\index{metric space!definition} 
Suppose that
$X$ is a non-empty set
and $d:X^{2}\rightarrow{\mathbb R}$ is a function
which obeys the following rules.

(i) $d(x,y)\geq 0$ for all $x,\,y\in X$.

(ii) $d(x,y)=0$ if and only if $x=y$.

(iii) $d(x,y)=d(y,x)$ for all $x,\,y\in X$.

(iv) $d(x,y)+d(y,z)\geq d(x,z)$ for all $x,\,y,\,z\in X$.

Then we say that $d$ is a \emph{metric} on $X$ and that $(X,d)$
is a \emph{metric space}.
\end{definition} 

For most of the course we shall be concerned with
metrics which you already know well.

\begin{lemma}\label{L;some metrics}\index{metric space!examples}
(i) Consider ${\mathbb R}^{n}$.
If we take $d$ to be ordinary Euclidean distance
\[d({\mathbf x},{\mathbf y})=\|{\mathbf x}-{\mathbf y}\|=
\left(\sum_{j=1}^{n}|x_{j}-y_{j}|^{2}\right)^{1/2},\]
then $({\mathbb R}^{n},d)$ is a metric space.
We refer to this space as \emph{Euclidean space}.

(ii) Consider ${\mathbb C}$. If we take
$d(z,w)=|z-w|$, then $({\mathbb C},d)$ is a metric space.
\end{lemma}
\begin{proof} Proved in previous courses 
(and set as Exercise~\ref{Q;some metrics}).
\end{proof}

The next definitions work in any metric
space, but you
can concentrate on what they mean for ordinary Euclidean space.
\begin{definition}\index{metric space!convergence}
If $(X,d)$ is a metric space
$x_{n}\in X$, $x\in X$ and $d(x_{n},x)\rightarrow 0$, then
we say that $x_{n}\xrightarrow[d]{}x$ as $n\rightarrow\infty$.
\end{definition}
\begin{definition}\index{balls, open and closed}
If $(X,d)$ is a metric space
$x\in X$ and $r>0$, then we write
\[B(x,r)=\{y\in X\,:\,d(x,y)<r\}\]
and call $B(x,r)$ the \emph{open ball} of radius $r$
with centre $x$.
\end{definition}  
\begin{definition}\label{Def;Open}\index{open set}\index{closed set} 
Let $(X,d)$ be a metric space.

(i) We say that a subset $E$ of $X$ is \emph{closed} if,
whenever $x_{n}\in E$ and $x_{n}\xrightarrow[d]{}x$,
it follows that $x\in E$.

(ii) We say that a subset $U$ of $X$ is \emph{open} if,
whenever $u\in U$, we can find a $\delta>0$ such that
$B(u,\delta)\subseteq U$.
\end{definition}
\begin{exercise}\label{E;Balls}\index{balls, open and closed}
(i) If $x\in X$ and $r>0$,
then $B(x,r)$ is open in the sense of Definition~\ref{Def;Open}.

(ii) If $x\in X$ and $r>0$, then the set
\[\bar{B}(x,r)=\{y\in X\,:\,d(x,y)\leq r\}\]
is closed. (Naturally enough, we call $\bar{B}(x,r)$
a \emph{closed ball}.)

(iii) If $E$ is closed, then $X\setminus E$ is open.

(iv) If $E$ is open then $X\setminus E$ is closed.
\end{exercise}

We recall (without proof) the following important
results from~1A.
\begin{theorem}{\bf[Cauchy criterion]}\label{T;junior Cauchy} 
A sequence
$a_{n}\in{\mathbb R}$ converges if and only if,
given $\epsilon>0$, we can find an $N(\epsilon)$
such that $|a_{n}-a_{m}|<\epsilon$ for all
$n,\,m\geq N(\epsilon)$ 
\end{theorem}

Generalisation
leads us to the following definitions.
\begin{definition}\index{Cauchy!sequence}
If $(X,d)$ is a metric space, then a sequence 
$(a_{n})$ with $a_{n}\in X$ is called a \emph{Cauchy sequence}
if, given $\epsilon>0$, we can find an $N(\epsilon)$
such that $d(a_{n},a_{m})<\epsilon$ for all
$n,\,m\geq N(\epsilon)$.
\end{definition}
\begin{definition}\index{complete metric space}\index{metric space!complete} 
We say that a metric space $(X,d)$ is 
\emph{complete} if every Cauchy sequence converges.
\end{definition}
\begin{exercise}\label{E;convergent Cauchy} 
Show that if $(X,d)$ is a metric space
(complete or not), then every convergent sequence is Cauchy.
\end{exercise}

We note the following very useful remarks.
\begin{lemma}\label{L;fast Cauchy}
Let $(X,d)$ be a metric space. 

(i) If a Cauchy sequence $x_{n}$ in  $(X,d)$ has a convergent 
subsequence with limit $x$, then $x_{n}\rightarrow x$.

(ii) Let $\epsilon_{n}>0$
and $\epsilon_{n}\rightarrow 0$ as $n\rightarrow\infty$.
If $(X,d)$ has the property that, whenever 
$d(x_{n},x_{n+1})<\epsilon_{n}$ for $n\geq 1$,
it follows that the sequence
$x_{n}$ converges, then $(X,d)$ is complete.
\end{lemma}

Lemma~\ref{L;fast Cauchy}~(ii) is most useful when we have
$\sum_{n=1}^{\infty}\epsilon_{n}$ convergent, 
for example if $\epsilon_{n}=2^{-n}$.

The next exercise is simply a matter of disentangling notation.
\begin{exercise}\label{E;closed Cauchy} 
Suppose that $(X,d)$ is a metric space
and $Y$ is a non-empty subset of $X$. 

(i) Show that, if $d_{Y}(a,b)=d(a,b)$ for all $a,\,b\in Y$,
then $(Y,d_{Y})$ is a metric space.

(ii) Show that, if $(X,d)$ is complete and $Y$ is closed in $(X,d)$,
then $(Y,d_{Y})$ is complete.

(iii)  Show that, if $(Y,d_{Y})$ is complete, then
(whether $(X,d)$ is complete or not) $Y$ is closed
in $(X,d)$.
\end{exercise}

We now come to our first real theorem.
\begin{theorem}\label{T;Euclid}\index{Euclidean metric complete} 
The Euclidean space ${\mathbb R}^{n}$
with the usual metric is complete.
\end{theorem}
We shall usually prove such theorems in the case $n=2$
and remark that the general case is similar.

\section{Compact sets in Euclidean Space}
In Part~1A we showed that any bounded sequence had a convergent
subsequence. This result generalises to $n$ dimensions.
\begin{theorem}\label{T;Bolzano}
(Bolzano--Weierstrass theorem).
If $K>0$ and ${\mathbf x}_{r}\in {\mathbb R}^{m}$
satisfies $\|{\mathbf x}_{r}\|\leq K$ for  all $r$, then we can find
an ${\mathbf x}\in {\mathbb R}^{m}$ and $r(k)\rightarrow\infty$
such that ${\mathbf x}_{r(k)}\rightarrow{\mathbf x}$
as $k\rightarrow\infty$. 
\end{theorem}


We now prove a very useful theorem.
\begin{theorem}\label{T;closed bounded} 
(i) If $E$ is closed bounded subset of ${\mathbb R}^{m}$,
then any sequence ${\mathbf x}_{r}\in E$ has a subsequence with a limit
in $E$.

(ii) Conversely, if $E$ is a subset of ${\mathbb R}^{m}$
with the property that 
any sequence ${\mathbf x}_{r}\in E$ has a subsequence with a limit
in $E$, then $E$ is closed and bounded.
\end{theorem}

We shall refer to the property described in (i) as the 
Bolzano--Weierstrass property\index{Bolzano--Weierstrass property}.

If you cannot see how to prove a result in ${\mathbb R}^{m}$
using the Bolzano--Weierstrass property, then the 1A proof
for ${\mathbb R}$ will often provide a hint. 


We often refer to closed bounded subsets of ${\mathbb R}^{m}$
as \emph{compact sets}\index{compact set}. 
(The reader is warned that, in general metric spaces,
`closed and bounded' does not mean the same thing as `compact'
(see, for example, Exercise~\ref{Q;unit ball}). If
we deal with the even more general case of topological spaces we have
to distinguish between compactness and sequential 
compactness\footnote{If you
intend to climb Everest you need your own oxygen supply. If you intend
to climb the Gog Magogs you do not.}. 
We shall only talk about compact sets in ${\mathbb R}^{m}$.)



The reader will be familiar with definitions of the following
type.
\begin{definition}\index{continuous function}
If $(X,d)$ and $(Y,\rho)$ are metric spaces 
and $E\subseteq X$, we
say that a function $f:E\rightarrow Y$ is \emph{continuous} if, given
$\epsilon>0$ and $x\in E$, we can find a $\delta(x,\epsilon)>0$
such that, whenever $z\in E$ and $d(z,x)<\delta(x,\epsilon)$,
we have $\rho(f(z),f(x))<\epsilon$.
\end{definition}
\begin{exercise}\label{E;topological continuity}
Let $(X,d)$ and $(Y,\rho)$ be metric spaces
and let $f:X\rightarrow Y$ be a function.

(i) $f$ is continuous if and only if $f^{-1}(U)$
is open whenever $U$ is.

(ii) $f$ is continuous if and only if $f^{-1}(E)$
is closed whenever $E$ is.
\end{exercise}

Even if the reader has not met the general metric space definition,
she will probably have a good idea of the properties of
continuous functions $f:E\rightarrow{\mathbb R}^{n}$
when $E$ is a subset of ${\mathbb R}^{m}$.

The following idea will be used several times during the course.
\begin{lemma}\label{L;distance closed}\index{d@$d(x,A)$} 
If $(X,d)$ is a metric space
and $A$ is a non-empty closed subset of $X$ let us write
\[d(x,A)=\inf\{d(x,a)\,:\,a\in A\}.\]
Then $d(x,A)=0$ implies $x\in A$. Further
the map $x\mapsto d(x,A)$ is continuous.
\end{lemma}

We now prove that the continuous image of a compact
set is compact.
\begin{theorem}\label{T;Compact image}
If $E$ is a compact subset of ${\mathbb R}^{m}$
and $f:E\rightarrow{\mathbb R}^{n}$ is continuous, then $f(E)$
is a compact subset of ${\mathbb R}^{n}$.
\end{theorem} 

At first sight Theorem~\ref{T;Compact image} seems too abstract to be
useful, but it has an immediate corollary.
\begin{theorem}\label{T;compact bound} 
If $E$ is a non-empty compact subset of ${\mathbb R}^{m}$
and $f:E\rightarrow{\mathbb R}$ is continuous, then there exist
${\mathbf a},\,{\mathbf b}\in E$ such that
\[f({\mathbf a})\geq f({\mathbf x})\geq f({\mathbf b})\]
for all ${\mathbf x}\in E$.
\end{theorem} 

Thus a continuous real valued function on a compact set
is bounded and attains its bounds.
\begin{exercise}\label{E;1A bounds} 
Deduce the theorem in~1A
which states that if $f:[c,d]\rightarrow{\mathbb R}$ is continuous,
then $f$ is bounded and attains its bounds. 
\end{exercise}
Theorem~\ref{T;compact bound} gives a neat proof of the fundamental
theorem of algebra (which, contrary to its name, is a theorem of analysis).
\begin{theorem}{\bf [Fundamental Theorem of Algebra]}%
\label{T;Fundamental Algebra}\index{fundamental theorem of algebra} 
If we work
in the complex numbers, every non-constant polynomial has a root.
\end{theorem}

The reader will probably have seen, but may well have forgotten,
the contents of the next exercise.
\begin{exercise}\label{E;roots}
We work in the complex numbers.
 
(i) Use induction on $n$ to show that,
if $P$ is a polynomial of degree $n$ and $a\in{\mathbb C}$,
then there exists a polynomial $Q$ of degree $n-1$ and an
$r\in{\mathbb C}$ such that
\[P(z)=(z-a)Q(z)+r.\]

(ii) Deduce that, if $P$ is a polynomial of degree $n$ 
with root $a$, then  there exists a polynomial $Q$ of degree $n-1$
such that
\[P(z)=(z-a)Q(z).\]

(iii) Use induction and the fundamental theorem of algebra
to show that every polynomial $P$ of degree $n$ can be written in the form
\[A\prod_{j=1}^{n}(z-a_{j})\]
with $A,\,a_{1},\,a_{2},\,\dots,\,a_{n}\in{\mathbb C}$
and $A\neq 0$.

(iv) Show that, if $P$ is a polynomial of degree at most $n$ which vanishes
at $n+1$ points, then $P$ is the zero polynomial.
\end{exercise}



\section{Laplace's equation}
We need a preliminary definition.
\begin{definition} Let $(X,d)$ be a metric space and $E$
a subset of $X$.

(i) The \emph{interior} of $E$ is the set of all points 
$x$ such that there\index{interior}
exists a $\delta>0$ (depending on $x$) such that
$B(x,\delta)\subseteq E$. We write $\Int E$ for the interior of $E$.

(ii) The \emph{closure}\index{closure}
 of $E$ is the set of points $x$ in $X$ such that we can find
$e_{n}\in E$ with $e_{n}\xrightarrow[d]{}x$.
We write $\Cl E$ for the closure of $E$.

(iii) The \emph{boundary}\index{boundary} 
of $E$ is the set $\partial E=\Cl E\setminus \Int E$. 
\end{definition}
\begin{exercise}\label{E;boundaries}
(i) Show that $\Int E$ is
open. Show also that, if $V$ is open and $V\subseteq E$, then
$V\subseteq \Int E$.

(ii) Show that $\Cl E$ is
closed. Show also that, if $F$ is closed and $F\supseteq E$, then
$F\supseteq \Cl E$.

(Thus $\Int E$ is the largest open set contained in $E$ 
and $\Cl E$ is the smallest closed set containing $E$.)

(iii) Show that $\partial E$ is closed.

(iv) Suppose that we work in ${\mathbb R}^{m}$ with the usual metric.
Show that if $E$ is bounded, then so is $\Cl E$.
\end{exercise}

Recall that, if $\phi$ is a real valued function in ${\mathbb R}^{m}$ with
sufficiently many derivatives, then we write
\[\triangledown^{2}\phi=\sum_{j=1}^{m}
\frac{\partial^{2}\phi}{\partial x_{j}^{2}}.\]
In this section we look at solutions of Laplace's
equation
\[\triangledown^{2}\phi=0.\]
Our first collection of results lead up to a proof of uniqueness.
\begin{lemma}\label{L;up Laplace} Let $\Omega$ be a bounded
open subset of ${\mathbb R}^{m}$.
Suppose $\phi:\Cl \Omega\rightarrow {\mathbb R}$ is continuous
and satisfies
\[\triangledown^{2}\phi>0\]
on $\Omega$. Then $\phi$ cannot attain its maximum on $\Omega$.
\end{lemma}

\begin{theorem}\label{T;down Laplace}  
Let $\Omega$ be a bounded open subset of ${\mathbb R}^{m}$.
Suppose $\phi:\Cl \Omega\rightarrow {\mathbb R}$ is continuous 
on $\Cl \Omega$
and satisfies
\[\triangledown^{2}\phi=0\]
on $\Omega$. Then $\phi$ attains its maximum on $\partial \Omega$.
\end{theorem}

\begin{exercise}\label{E;analytic maximum} 
Let $\Omega$ be a
bounded open subset of ${\mathbb C}$.
Suppose that 
\[f:\Cl \Omega\rightarrow{\mathbb C}\]
is continuous
and $f$ is analytic on $\Omega$. Recall that the real
and imaginary parts of $f$ satisfy Laplace's equation
on $\Int \Omega$. Show that $|f|$ attains its maximum on $\partial \Omega$.

\noindent$[$Hint: Why can we assume that $\Re f(z_{0})=|f(z_{0})|$
at any particular point $z_{0}$?$]$
\end{exercise}

\begin{theorem}\label{T;unique Laplace}%
\index{solution of Laplace's equation!uniqueness}
Let $\Omega$ be a bounded open  subset of ${\mathbb R}^{m}$.
Suppose that the functions 
$\phi,\psi:\Cl \Omega\rightarrow {\mathbb R}$ are continuous
and satisfy
\[\triangledown^{2}\phi=0,\ \triangledown^{2}\psi=0\]
on $\Omega$. Then, if $\phi=\psi$ on $\partial \Omega$,
it follows that $\phi=\psi$ on $\Cl \Omega$.
\end{theorem}

You proved a version of Theorem~\ref{T;unique Laplace}
in Part~1A but only for `nice boundaries' and functions that
behaved `nicely' near the boundary.

You have met the kind of arguments used above when you proved
Rolle's theorem in 1A. Another use of this argument is given
in Exercise~\ref{Q;Schwarz} which provides a nice
revision for this section. 

In Part~1A you assumed that you could always solve Laplace's equation.
The next exercise (which forms  part of the course)
shows that this is not the case.
\begin{exercise}\label{E;no Laplace}%
\index{solution of Laplace's equation!possible non-existence}%
\index{Zaremba's counterexample} 
(i) Let
\[\Omega=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,0<\|{\mathbf x}\|<1\}.\]
Show that $\Omega$ is open,  that
\[Cl \Omega=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|\leq 1\}\]
and
\[\partial\Omega=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|=1\}
\cup\{{\boldsymbol 0}\}.\]

(ii) Suppose that 
$\phi:\Cl \Omega\rightarrow {\mathbb R}$ is continuous,
that $\phi$ is twice differentiable on $\Omega$
and that $\phi$ satisfies
\[\triangledown^{2}\phi=0\]
on $\Omega$ together with  the boundary conditions
\[\phi({\mathbf x})
=\begin{cases}
0&\text{if $\|{\mathbf x}\|=1$},\\
1&\text{if ${\mathbf x}={\boldsymbol 0}$}.
\end{cases}
\]
Use the uniqueness of solutions of Laplace's equation to show that
$\phi$ must be radially symmetric in the sense that
\[\phi({\mathbf x})=f(\|{\mathbf x}\|)\]
for some function $f:[0,1]\rightarrow {\mathbb R}$. 

(iii) Show that
\[\frac{d\ }{dr}\big(rf(r)\big)=0\]
for $0<r<1$ and deduce that $f(r)=A+B\log r$  $[0<r<1]$
for some constants $A$ and $B$.

(iv) Conclude that the function $\phi$ described in (ii)
can not exist. 
\end{exercise}

This result is due to Zaremba, one of the founding fathers
of Polish mathematics. Later Lebesgue produced a three dimensional
example (the Lebesgue thorn) which will be briefly discussed
by the lecturer, but does not form part of the course.
\section{Fixed points} In Part~1A we proved the intermediate
value theorem.
\begin{theorem}\label{T;intermediate} 
If $f:[a,b]\rightarrow{\mathbb R}$ is continuous
function and $f(a)\geq c\geq f(b)$, then we can find
a $y\in [a,b]$ such that $f(y)=c$.
\end{theorem}
We then used it  to the following very pretty
fixed point theorem.
\begin{theorem}\label{T;one fixed}
If $f:[a,b]\rightarrow[a,b]$ is a continuous
function, then we can find
a $w\in [a,b]$ such that $f(w)=w$.
\end{theorem}
Notice that we can reverse the implication
and use Theorem~\ref{T;one fixed} to prove
Theorem~\ref{T;intermediate}. (See Exercise~\ref{E;two Brouwer}.) 

The object of this section is to extend the fixed
point theorem to two dimensions.
\begin{theorem}\label{T;fix disc} Let 
$\bar{D}=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|\leq 1\}$.
If $f:\bar{D}\rightarrow \bar{D}$ is a continuous
function, then we can find
a ${\mathbf w}\in \bar{D}$ such that $f({\mathbf w})={\mathbf w}$.
\end{theorem}
Although we will keep strictly to two dimensions the reader
should note that the result and many of its consequences
hold in $n$ dimensions.

Notice also that the result can be extended to (closed) squares,
triangles and so on.
\begin{lemma}\label{L;fix you} Let 
$\bar{D}=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|\leq 1\}$.
Suppose that $g:\bar{D}\rightarrow A$ is a bijective
function with $g$ and $g^{-1}$ continuous. Then if
$F:A\rightarrow A$ is a continuous
function, we can find
an $a\in A$ such that $F(a)=a$.
\end{lemma}

From now on we shall use extensions of the type
given for Lemma~\ref{L;fix you}
without comment.

The proof of Theorem~\ref{T;fix disc} will take us some time.
It consists in showing that a number of interesting statements
are equivalent. The proof thus consists of lemmas of the form
$A\Rightarrow B$ or$B\Leftrightarrow C$, \ldots. I suggest that the
reader considers each of these implications individually and then
steps back to see how they hang together.


We write
\[D=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|<1\},
\ \bar{D}=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|\leq 1\},
\partial D=\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|=1\}.\]
\begin{theorem}\label{T;Brouwer retracts} 
The following two statements are equivalent.

(i) If $f:{\bar D}\rightarrow {\bar D}$ is continuous, then we can find
a ${\mathbf w}\in {\bar D}$ such that $f({\mathbf w})={\mathbf w}$.
(We say that every continuous function of the closed disc into itself
has a fixed point.)

(ii) There does not exist a continuous function 
$g:{\bar D}\rightarrow\partial D$
with $g({\mathbf x})={\mathbf x}$ for all ${\mathbf x}\in \partial D$.
(We say that there is no \emph{retraction mapping}\index{retraction mapping} 
from ${\bar D}$ to $\partial D$.)
\end{theorem}

Let ${\mathbf a}_{1}$, ${\mathbf a}_{2}$ and ${\mathbf a}_{3}$
be unit vectors making angles of $\pm2\pi/3$ with each other.
We take $T$ to be the closed triangle with vertices
${\mathbf a}_{1}$, ${\mathbf a}_{2}$ and ${\mathbf a}_{3}$
and sides $I$, $J$ and $K$.

(For those who insist on things being spelt out
\[T=\{\lambda_{1}{\mathbf a}_{1}
+\lambda_{2}{\mathbf a}_{2}+\lambda_{3}{\mathbf a}_{3}\,:
\,\lambda_{1}+\lambda_{2}+\lambda_{3}=1,
\ \lambda_{j}\geq 0\}\]
but though such ultra precision has its place,
that place is not this course.)

The next collection of equivalences is easy to prove.
\begin{lemma}\label{L;more retract} 
The following three statements are equivalent.

(i) There is no retraction mapping from $\bar{D}$ to $\partial D$.

(ii) Let
\begin{gather*}
\tilde{I}=\{(\cos\theta,\sin\theta)\,:\,0\leq \theta\leq 2\pi/3\},
\ \tilde{J}=\{(\cos\theta,\sin\theta)\,:\,2\pi/3\leq \theta \leq 4\pi/3\}\\
\text{and}\ \tilde{K}=\{(\cos\theta,\sin\theta)
\,:\,4\pi/3\leq \theta \leq 2\pi\}.
\end{gather*}
Then there does not exist a continuous function 
$\tilde{k}:{\bar D}\rightarrow\partial D$
with 
\[\tilde{k}({\mathbf x})\in \tilde{I}\ \text{for all}\ {\mathbf x}\in \tilde{I},
\ \tilde{k}({\mathbf x})\in \tilde{J}\ \text{for all}\ {\mathbf x}\in \tilde{J},
\ \tilde{k}({\mathbf x})\in \tilde{K}\ \text{for all}\ {\mathbf x}\in \tilde{K}.\] 

(iii) There does not exist a continuous function 
$k:T\rightarrow\partial T$
with 
\[k({\mathbf x})\in I\ \text{for all}\ {\mathbf x}\in I,
\ k({\mathbf x})\in J\ \text{for all}\ {\mathbf x}\in J,
\ k({\mathbf x})\in K\ \text{for all}\ {\mathbf x}\in K.\]
\end{lemma}

We now prove a slightly more difficult equivalence.
\begin{lemma}\label{L;colour me} 
The following two statements are equivalent,

(i) There does not exist a continuous function $h:T\rightarrow\partial T$
with 
\[h({\mathbf x})\in I\ \text{for all}\ {\mathbf x}\in I,
\ h({\mathbf x})\in J\ \text{for all}\ {\mathbf x}\in J,
\ h({\mathbf x})\in K\ \text{for all}\ {\mathbf x}\in K.\]

(ii) If $A$, $B$ and $C$ are closed subsets of $T$ with
$A\supseteq I$, $B\supseteq J$ and $C\supseteq K$
and $A\cup B\cup C=T$,
then $A\cap B\cap C\neq\emptyset$.
\end{lemma}

We shall prove statement~(ii) of Lemma~\ref{L;colour me} 
from which the remaining statements
will then follow. The key step is Sperner's Lemma.
\begin{lemma}\label{L;Sperner}\index{Sperner's lemma} 
Consider a triangle $DEF$
divided up into a triangular grid.
If all the vertices of the grid are coloured red, green or blue
and every vertex on the side $DE$ of the big triangle
(with the exception of $E$) 
are coloured red,
every vertex of $EF$ (with the exception of $F$) green
and every vertex of $FD$ (with the exception of $D$) blue 
then there is a triangle of the grid 
all of whose vertices have different colours.
\end{lemma}


We can now prove the statement~(ii) of Lemma~\ref{L;colour me}
and so of Theorem~\ref{T;fix disc} and all its equivalent forms.

The following pair of exercises 
(set as Exercises~\ref{A1.7} and~\ref{A1.8})
may be helpful in thinking about the
arguments of this section.
\begin{exercise}\label{E;two Brouwer}
The following four statements are equivalent.

(i) If $f:[0,1]\rightarrow [0,1]$ is continuous, then we can find
a $w\in[0,1]$ such that $f(w)=w$.

(ii) There does not exist a continuous function $g:[0,1]\rightarrow\{0,1\}$
with $g(0)=0$ and $g(1)=1$.
(In topology courses we say that $[0,1]$ is connected.)

(iii) If $A$ and $B$ are closed subsets of $[0,1]$ with
$0\in A$, $1\in B$ and $A\cup B=[0,1]$
then $A\cap B\neq\emptyset$.

(iv)  If $h:[0,1]\rightarrow {\mathbb R}$ is continuous
and $h(0)\leq c\leq h(1)$, then we can find
a $y\in[0,1]$ such that $h(y)=c$.
\end{exercise} 
\begin{exercise}\label{E;two Sperner} Suppose that we colour the points $r/n$
red or blue $[r=0,\,1,\,\dots,\,n]$ with $0$ red
and $1$ blue. Show that there are a pair of neighbouring points 
$u/n$, $(u+1)/n$ of different colours. Use this result
to prove statement~(iii) of Exercise~\ref{E;two Brouwer}.
\end{exercise}
Sperner's lemma can be extended to higher dimensions
and once this is done the remainder of our proofs together with
Brouwer's theorem extend with simple changes to
higher dimensions.

Here is an example of the use of Brouwer's theorem.
\begin{exercise}\label{E;reverse Markov} 
Suppose that $A=(a_{ij})$ is a $3\times 3$ matrix such that
$a_{ij}\geq 0$ for all $1\leq i,j\leq 3$ and
$\sum_{i=1}^{3}a_{ij}=1$ for all $1\leq j\leq 3$. Let
\[T=\{{\mathbf x}\in{\mathbb R}^{3}\,:\,x_{j}\geq 0
\ \text{for all $j$ and}\ x_{1}+x_{2}+x_{3}=1\}.\]
By considering the effect of $A$ on $T$, show that $A$ has
an eigenvector lying in $T$ with eigenvalue $1$.
\end{exercise}

If you have not done the~1B Markov chains course 
Exercise~\ref{E;reverse Markov} may appear somewhat artificial.
However, if you have done that course, you will see that is not.
\begin{exercise}\label{E;invriant Markov} 
(Only for those who understand the terms used.
This is not part of the course.) Use the argument
of Exercise~\ref{E;reverse Markov} to show that
every $3$ state Markov chain has an invariant measure.
(Remember that in Markov chains `the $i$'s and $j$'s swap places'.)
What result can you obtain under the assumption that
Brouwer's theorem holds in higher dimensions?
\end{exercise}

Brouwer's theorem is rather deep. Here is a result which can be
proved using it.

\begin{exercise}\label{E;informal intersection}
Show that if $ABCD$ is a square and $\gamma$ 
is a continuous path joining $A$ and $C$ whilst $\tau$  
is a continuous path joining $B$ and $D$, then $\gamma$ and $\tau$
intersect,

\noindent$[$See Exercise~\ref{Q;Brouwer intersection} for a more detailed
statement and a description of the proof.$]$ 
\end{exercise}  
Another interesting result is given as Exercise~\ref{Q;surjection}.
\section{Non-zero sum games} It is said that converting the front 
garden of
a house into a parking place raises the value of a house, but lowers
the value of the other houses in the road. Once everybody has
done the conversion, the value of  each house is lower than before
the process started. 

Let us make a simple model of such a situation
involving just two people with just two choices
to see what we can say about it.

Suppose that Albert has the choice of doing $A_{1}$ 
or $A_{2}$ and Bertha the choice of doing $B_{1}$
or $B_{2}$. If $A_{i}$ and $B_{j}$ occur, then
Albert gets $a_{ij}$ units and Bertha
gets $b_{ij}$ units. If you went to the
1B~course on optimisation you learnt how to deal with
the case when $a_{ij}=-b_{ij}$ (this is called
\emph{zero-sum} case\index{zero-sum game}
since $a_{ij}+b_{ij}=0$ and Albert's loss
is Bertha's gain). Albert and Bertha agree
that Albert will choose $A_{i}$ with probability $p_{i}$
and Bertha will choose $B_{j}$ with probability $q_{j}$.
The expected value of the arrangement to Albert is
\[A({\mathbf p},{\mathbf q})=
\sum_{i=1}^{2}\sum_{j=1}^{2}a_{ij}p_{i}q_{j}\]
and the expected value of the arrangement to Bertha
\[B({\mathbf p},{\mathbf q})=
\sum_{i=1}^{2}\sum_{j=1}^{2}b_{ij}p_{i}q_{j}\]

If you went to the 1B optimisation course,
then you saw that \emph{in the zero-sum case} 
there is a choice of ${\mathbf p}$ and ${\mathbf q}$ 
such that if Albert chooses ${\mathbf p}$ and
Bertha ${\mathbf q}$ then \emph{even if he knows
Bertha's choice} Albert will not change his choice
and  \emph{even if she knows
Albert's choice} Bertha will not change her choice.


So far so good, but if we consider the non zero-sum case
we can imagine other situations
in which Albert chooses ${\mathbf p}$ and then
Bertha chooses ${\mathbf q}$ but, now knowing 
Bertha's choice, Albert changes his choice to ${\mathbf p}'$
and then, knowing Albert's new choice, Bertha changes
to ${\mathbf q}'$ and then \dots. The question we ask ourselves
is whether there is a `stable choice' of ${\mathbf p}$
and ${\mathbf q}$ such that neither party can do better by
unilaterally choosing a new value. This question is answered
by a remarkable theorem of Nash. 

\begin{theorem}\label{T;Nash stable}\index{Nash stable points} 
Suppose $a_{ij}$ and $b_{ij}$ are real numbers.
Let
\[E=\{(p,q)\,:1\geq p,\,q\geq 0\},\]
set
$p_{1}=p$, $p_{2}=1-p$, $q_{1}=q$, $q_{2}=1-q$,
\[A(p,q)=\sum_{i=1}^{2}\sum_{j=1}^{2}a_{ij}p_{i}q_{j}
\ \text{and}
\ B(p,q)=\sum_{i=1}^{2}\sum_{j=1}^{2}b_{ij}p_{i}q_{j}.\]
Then we can find $(p^{*},q^{*})\in E$ such that
\[B(p^{*},q^{*})\geq B(p^{*},q)\ \text{for all}\ (p^{*},q)\in E\]
and
\[A(p^{*},q^{*})\geq A(p,q^{*})\ \text{for all}\ (p,q^{*})\in E.\]
\end{theorem}

The pair $(p^{*},q^{*})$ is called a Nash equilibrium point
or Nash stable point.


The interested reader should have no difficulty in convincing
herself (given Brouwer's fixed point
theorem in the appropriate dimension) that the result
can be extended to many participants with many choices
to state that there is always a choice of probabilities
such that \emph{no single participant} has an incentive
to change their choice\footnote{However, this applies only to 
single participants. There may be an incentive for two 
or more participants
(if they can agree) to change their choices jointly.}.
Note that the game theory you did in~1B only applies
to two players.

Unfortunately the stable points need not be unique.
Suppose that Albert and Bertha have to choose
scissors or paper. If they both choose scissors they get $\pounds 1$
each. If they both choose paper they get $\pounds 2$ each but
if they disagree they get nothing. It is clear that
the points corresponding to `both choose paper'
and `both choose scissors' are stable. 
The same is true if when they disagree they both get nothing
but Albert gets $\pounds 1$ and Bertha $\pounds 2$
if they both choose scissors whilst, if they both choose paper
the payments are reversed.

\begin{exercise}{\bf[Chicken]}\label{E;chicken}
Albert and Bartholomew drive
cars fast at one another. If they both swerve they both lose
1 prestige points. If one swerves and the other does not
the swerver looses 5 prestige points and the non-swerver
gains 10 prestige points. If neither swerves they both loose 100
points. Identify the Nash equilibrium points.
\end{exercise}

Notice that it is genuinely easy to solve toy problems like this
when they appear in exercises and examinations. First look at the
interior of the square and apply elementary calculus to find
stationary points. Then look
at the interior of each edge and apply elementary calculus
to find stationary points. Finally look at the vertices.
The same idea applies when there are three participants,
but now we need to examine the interior of the cube,
the interior of each face, the interior of each
edge and the vertices in turn.
Obviously if we attack the problem in this way, 
we run into the curse of dimensionality ---
each step is easy but the number of steps increases very rapidly
with the number of participants.
So far as I know, there is no way of avoiding this
phenomenon. (But I know of no real life situation
where we would wish to solve a high dimensional problem.)


It is also clear from examples like the one that
began this section that even if the stable point is unique it may be 
unpleasant for all concerned\footnote{McNamara, the
US Defence Secretary at the time, was of the opinion that,
during the Cuban crisis, all the participants behaved in a perfectly
rational manner and only good luck prevented
a full scale nuclear war.}. 
However this is not the concern of the mathematician.
\section{Dividing the pot} Faced with problems like those
of the previous section, the young and tender hearted 
often ask `Why not cooperate?' It is, of course, true that
under certain conditions people are willing to cooperate,
but, even if these conditions are met, the question
remains of how to divide up the gains due to cooperation.
\begin{exercise}\label{E;Advertising}
(You will be asked to solve this as Exercise~\ref{A2.4}.)
Consider
two rival firms $A$ and $B$ engaged in an advertising war.
So long as the war continues, the additional costs
of advertising mean that the larger firm $A$ loses $3$ million
pounds a year and the smaller firm $B$ loses $1$ million pounds a year.
If they can agree to cease hostilities then $A$ will make
$8$ million a year and $B$ will make $1$ million a year.
How much should $A$ pay $B$ per year to achieve this end\footnote{The
reader may feel that it would be very difficult for
rival firms
to come to an agreement in this way. In fact, it appears
to be so easy that most countries have strict laws against
such behaviour.}?
\end{exercise}


Nash produced a striking answer to this question.
There are objections to his argument,
but I hope the reader will agree with me that
it is a notable contribution.

In order to examine his answer we need to introduce the notion
of a convex set.
\begin{definition}\index{convex set} 
A subset $E$ of ${\mathbb R}^{m}$
is \emph{convex} if, whenever ${\mathbf u},\,{\mathbf v}\in E$
and $1\geq p\geq 0$, we have
\[p{\mathbf u}+(1-p){\mathbf v}\in E.\]
\end{definition}

Nash considers a situation in which $m$ players
must choose a point ${\mathbf x}\in E$ where $E$
is a closed, bounded, convex set in ${\mathbb R}^{m}$.
The value of the outcome to the $j$th participant
is $x_{j}$. To see why is reasonable to take $E$
convex suppose that the participants can choose 
two points ${\mathbf u}$ and ${\mathbf v}$. The participants
can agree among themselves to toss a suitable coin and
choose ${\mathbf u}$ with probability $p$
and ${\mathbf v}$ with probability $1-p$.
The expected value of the outcome to
the $j$th participant
is $pu_{j}+(1-p)v_{j}$, that is to say, the value of the
$j$th component of $p{\mathbf u}+(1-p){\mathbf v}$. 

The participants also know a point ${\mathbf s}\in E$
(the status quo)
which will be the result if they can not agree on any other
point.

Nash argues that a best point ${\mathbf x}^{*}$
if it exists must have the following properties.

(1) $x_{j}^{*}\geq s_{j}$ for all $j$. (Everyone must be at least
as well off as if they failed to agree.)

(2) (Pareto Optimality)\index{Pareto optimality} 
If ${\mathbf x}\in E$ and
$x_{j}\geq x_{j}^{*}$ for all $j$, then ${\mathbf x}={\mathbf x}^{*}$.
(If there is a choice which makes some strictly better off
and nobody worse off, then the participants should take it.)

(3) (Independence of irrelevant alternatives.) Suppose $E'$ is a closed
bounded convex set with $E'\supseteq E$ and ${\mathbf x}^{**}$
is a best point for $E'$. Then, if ${\mathbf x}^{**}\in E$
it follows that ${\mathbf x}^{**}$ is a best point for $E$.

(4) If $E$ is symmetric (that is, if whenever 
${\mathbf x}\in E$ and $y_{1},y_{2},\dots,y_{m}$ is some
rearrangement of $x_{1},x_{2},\dots,x_{m}$, then ${\mathbf y}\in E$)
and ${\mathbf s}$ is symmetric,
then $x^{*}_{1}=x^{*}_{2}=\dots=x_{m}^{*}$. This corresponds
to our beliefs about `fairness'.

(5) Our final assumption is that we must treat the poor man's
penny with the same respect as the rich man's pound. Suppose
that ${\mathbf x}^{*}$ is a best point for $E$. 
If we change coordinates
and consider
\[E'=\{{\mathbf x}'\,:\,x_{j}'=a_{j}x_{j}+b_{j} 
\ \text{for $1\leq j\leq m$ and ${\mathbf x}\in E$}\}\]
with $a_{j}>0$,
then ${\mathbf y}^{*}$ with $y_{j}^{*}=a_{j}x_{j}^{*}+b_{j}$
is a best point for $E'$.
\begin{exercise}\label{E;convex transform} 
Show that the $E'$ defined in (5) above is closed
bounded and convex.
\end{exercise}

There is no difficulty in remembering these conditions
since they each play a particular role in the proof.
If the reader prefers initially only to deal with the case $m=2$, she will 
lose nothing of the argument.
We need a preliminary lemma.
\begin{lemma}\label{L;push to  one side}
If $K$ is a convex set in ${\mathbb R}^{n}$
such that $(1,1,\ldots,1)\in K$
and $\prod_{j=1}^{n}x_{j}\leq 1$ for all ${\mathbf x}\in K$
with $x_{j}\geq 0$ $[1\leq j\leq n]$, then
\[K\subseteq\{{\mathbf x}\,:\,x_{1}+x_{2}+\ldots x_{n}\leq n\}.\]
\end{lemma}


\begin{theorem}\label{T;happy Nash}
Suppose that we agree to the Nash conditions.
If $E$ is closed bounded convex set in ${\mathbb R}^{m}$, 
${\mathbf s}$ is the
status quo point and the function
$f:E\rightarrow{\mathbb R}$ given by
\[f({\mathbf x})=\prod_{j=1}^{m}(x_{j}-s_{j})\]
has a maximum (in $E$) with $x_{j}-s_{j}>0$
at ${\mathbf x}^{*}$, then
${\mathbf x}^{*}$ is the unique best point.
\end{theorem}

We complete our discussion by observing that a best point always exists.
\begin{lemma}\label{L;pushier} 
If $E$ is closed bounded convex set in ${\mathbb R}^{m}$, 
${\mathbf s}\in \Int E$ 
and the function
$f:E\rightarrow{\mathbb R}$ given by
\[f({\mathbf x})=\prod_{j=1}^{m}(x_{j}-s_{j}),\]
then there is a unique point in $E$ with $x_{j}-s_{j}\geq 0$
where $f$ attains a maximum.
\end{lemma}

`There is no patent for immortality under the the moon'
but I suspect that Nash's results will be remembered
long after the last celluloid copy of \emph{A Beautiful Life}
has crumbled to dust.

The book  \emph{Games, Theory and Applications}~\cite{Thomas} by L.~C.~Thomas
maintains a reasonable balance between the technical and non-technical
and would make a good port of first call if you wish to learn more
along these lines.
\section{Approximation by polynomials} It is a guiding
idea of both the calculus and of numerical analysis that
`well behaved functions look like polynomials'.
Like most guiding principles, it needs to be used judiciously.

If asked to justify it, we might mutter something about 
Taylor's Theorem, but Cauchy produced the following example
to show that this is not sufficient\footnote{When we do 1A
this result is a counterexample but, by Part II, if we need
a `partition of unity' or a `smoothing kernel', it has become
an invaluable tool.}.
\begin{exercise}\label{E;Cauchy example}%
\index{Taylor series, counterexample}\index{Cauchy!counterexample}
Let $E:{\mathbb R}\rightarrow{\mathbb R}$
be defined by
\[E(t)= 
\begin{cases} 
\exp(-1/t^{2})&\text{if $t\neq 0$,}\\
0&\text{if $t= 0$.}
\end{cases}
\]

(i) $E$ is infinitely differentiable, except, possibly, at $0$,
with
\[E^{(n)}(t)=P_{n}(1/t)E(t)\]
for all $t\neq 0$ for some polynomial $P_{n}$.

(ii) $E$ is infinitely differentiable everywhere
with
\[E^{(n)}(0)=0.\]

(iii) We have
\[E(t)\neq\sum_{n=0}^{\infty}\frac{E^{(n)}(0)}{n!}t^{n}\]
for all $t\neq 0$.
\end{exercise}
(It is very unlikely that you have not seen this exercise
before, but if you have not you should study it.)

We could also mutter something like `interpolation'.
The reader probably knows all the facts given in the next lemma.
\begin{lemma}\label{L;interpolate polynomial} 
Let $x_{0}$, $x_{1}$,
\dots, $x_{n}$ be distinct points of $[a,b]$.

(i) If $f:[a,b]\rightarrow{\mathbb R}$, then there is at most
one polynomial of degree no greater than $n$ with $P(x_{j})=f(x_{j})$
for $0\leq j\leq n$.

(ii) Write
\[e_{j}(t)=\prod_{k\neq j}\frac{t-x_{k}}{x_{j}-x_{k}}.\]
If $f:[a,b]\rightarrow{\mathbb R}$, then 
\[P=\sum_{j=0}^{n}f(x_{j})e_{j}\]
is a polynomial of degree at most $n$ with
$P(x_{i})=f(x_{i})$ for $0\leq i\leq n$. 
(Thus we can replace `at most' by `exactly'
in (i).) 

(iii) In the language of vector spaces, the $e_{j}$
form a basis for the vector space of polynomials ${\mathcal P}_{n}$
of degree $n$ or less.
\end{lemma}

However polynomials can behave in rather odd ways.
\begin{theorem}\label{T;Chebychev polynomials}\index{Chebychev!polynomials}
There exist polynomials $T_{n}$ of degree
$n$ and $U_{n-1}$ of degree $n-1$ such that
\[T_{n}(\cos\theta)=\cos n\theta\]
for all $\theta$ and
\[U_{n-1}(\cos\theta)=\frac{\sin n\theta}{\sin\theta}\]
for $\sin\theta\neq 0$. The value of $U_{n-1}(\cos\theta)$
when $\sin\theta=0$ is given by continuity and will be $\pm n$.
The roots of $U_{n-1}$ are $\cos(r\pi/n)$ with $1\leq r\leq n-1$
and the roots of $T_{n}$ are $\cos\big((r+\tfrac{1}{2})\pi/n\big)$ with
$0\leq r\leq n-1$.

The coefficient of $t^{n}$ in $T_{n}$ is $2^{n-1}$ for $n\geq 1$.
\end{theorem}

We call $T_{n}$ the Chebychev\footnote{Or Tchebychev, hence the $T$.}
polynomial of degree $n$.
The $U_{n}$ are called Chebychev polynomials of the  second kind.
Looking at the Chebychev polynomials of the second kind, we see
that we can choose a well behaved function $f$ which is
well behaved at $n+1$ reasonably well spaced points but
whose $n$th degree interpolating polynomial is very large
at some other point. It can be shown (though this is harder to prove)
that this kind of thing can happen however we choose 
our points of interpolation. 

A little thought shows that we are not even sure what
it means for one function to look like another. It is natural
to interpret $f$ looks like $g$
as saying that $f$ and $g$ are close in
some metric. However there are a number of `obvious' metrics.
The next exercise will be familiar to almost all my audience.
\begin{exercise}\label{E;distinct metrics} 
Show that the following define metrics
on the space $C([0,1])$ of continuous functions
$f:[0,1]\rightarrow{\mathbb R}$.

(i) $\|f\|_{1}=\int_{0}^{1}|f(t)|\,dt$ defines
a norm with associated distance 
\[d_{1}(f,g)=\|f-g\|_{1}=\int_{0}^{1}|f(t)-g(t)|\,dt.\]

(ii) The equation
\[\langle f,g \rangle=\int_{a}^{b}f(t)g(t)\,dt\]
defines an inner product on $C([a,b])$
with associated norm $\|\ \|_{2}$ and so a distance
\[d_{2}(f,g)=\|f-g\|_{2}=\left(\int_{a}^{b}(f(t)-g(t))^{2}\,dt\right)^{1/2}\]
for the derived norm.


(iii) The equation $\|f\|_{\infty}=\sup_{t\in[0,1]}|f(t)|$
defines a norm and so a distance 
\[d_{3}(f,g)=\|f-g\|_{\infty}=\sup_{t\in[0,1]}|f(t)-g(t)|.\]

Show that 
\[\|f\|_{\infty}\geq \|f\|_{2}\geq \|f\|_{1}.\]

Let
\[f_{n}(t)=
\begin{cases}
(1-nt)&\text{for $0\leq t\leq 1/n$},\\
0&\text{otherwise}.
\end{cases}
\]
Compute  $\|f_{n}\|_{\infty}/\|f_{n}\|_{1}$
and $\|f_{n}\|_{1}/\|f_{n}\|_{2}$. Comment.
\end{exercise}

Each of these metrics has its advantages and all are used
in practice. We shall concentrate on the metric $d_{3}$.
We quote the following result from a previous course
(where it is known as the General Principle of Uniform Convergence).
\begin{theorem} If $[a,b]$ is a closed interval and
$C([a,b])$ is the space of continuous functions on $[a,b]$
then the uniform metric
\[d(f,g)=\|f-g\|_{\infty}\]
is complete.
\end{theorem}

We have now obtained a precise question. If $f$ is a continuous function
can we find polynomials which are 
arbitrarily close in the uniform norm?
This question was answered in the affirmative
by Weierstrass in a paper published
when he was 70 years old.
Since then, several different proofs have been discovered.
We present one due to Bernstein based on probability
theory\footnote{Some other proofs
are given in Exercises~\ref{E;long Bernstein},
\ref{E;kernel Weierstrass} and~\ref{E;Lebesgue}.
It is the author's belief that one can not have too many
(insightful) proofs of Weierstrass's theorem.}.

Before that, we need a definition and theorem which the
reader will have met in a simpler form earlier.
\begin{definition}\index{uniformly continuous}
Let $(X,d)$ and $(Y,\rho)$ be metric spaces.
We say that a function $f:X\rightarrow Y$
is uniformly continuous if, given $\epsilon>0$,
we can find a $\delta>0$ such that $\rho\big(f(a),f(b)\big)<\epsilon$
whenever $d(a,b)<\delta$.
\end{definition}
\begin{theorem}\label{T;uniform continuity} 
If $E$ is a bounded closed set in ${\mathbb R}^{m}$
and $f:E\rightarrow{\mathbb R}^{p}$ is continuous, then
$f$ is uniformly continuous.
\end{theorem}

Although we require probability theory, we only need deal
with the simplest case of a random variable taking a finite number 
of values and, if the reader wishes, she need only prove
the next result in that case.
\begin{theorem}{\bf [Chebychev's inequality]}%
\label{T;Chebychev}\index{Chebychev!inequality}
If $X$ is a real valued bounded random variable, then,
writing
\[\sigma^{2}=\var X={\mathbb E}(X-{\mathbb E}X)^{2},\]
we have
\[\Pr(|X-{\mathbb E}X|\geq a)\leq \frac{\sigma^{2}}{a^{2}}\]
for all $a>0$.
\end{theorem}

\begin{theorem}{\bf [Bernstein]}\label{T;Bernstein} 
\index{Weierstrass's approximation theorem!Bernstein's proof}
Suppose $f:[0,1]\rightarrow{\mathbb R}$
is continuous. 
Let $X_{1}$, $X_{2}$,
\dots $X_{n}$ be independent
identically distributed random variables
with $\Pr(X_{r}=0)=1-t$ and $\Pr(X_{r}=1)=t$ (think of
tossing a biased coin). Let
\[Y_{n}(t)=\frac{X_{1}+X_{2}+\dots+X_{n}}{n}\]
and let
\[p_{n}(t)={\mathbb E}f(Y_{n}(t)).\]
Then

(i) $p_{n}$ is polynomial of degree $n$. Indeed,
\[p_{n}(t)=\sum_{j=0}^{n}\binom{n}{j}f(j/n)t^{j}(1-t)^{n-j}.\]

(ii) $\|p_{n}-f\|_{\infty}\rightarrow 0$ as $n\rightarrow\infty$.
\end{theorem}


Bernstein's result differs from many proofs of Weierstrass's
theorem in giving an elegant \emph{explicit} approximating
polynomial.
\section{Best approximation by polynomials}
Bernstein's theorem gives an explicit approximating polynomial
but, except in very special circumstances, 
not the best approximating polynomial.
(Indeed, we have not yet shown that such a polynomial exists.)

Chebychev was very interested
in this problem and gave a way of telling when we do
have a best approximation.
\begin{theorem}{\bf [The Chebychev equiripple criterion]}%
\label{T;Chebychev equiripple}\index{Chebychev!equiripple criterion}
Let $f:[a,b]\rightarrow{\mathbb R}$ be a continuous
function and $P$ a polynomial of degree at most $n-1$.
Suppose that we can find $a\leq a_{0}< a_{1}< \dots< a_{n}\leq b$
such that, writing $\sigma=\|f-P\|_{\infty}$ we have
either
\begin{align*}
f(a_{j})-P(a_{j})=(-1)^{j}\sigma&\ \text{for all $0\leq j\leq n$}\\
\intertext{or}
f(a_{j})-P(a_{j})=(-1)^{j+1}\sigma&\ \text{for all $0\leq j\leq n$.}
\end{align*}
Then $\|P-f\|_{\infty}\leq\|Q-f\|_{\infty}$ for all polynomials $Q$
of degree
$n-1$ or less.
\end{theorem}

We apply this to find the polynomial of degree $n-1$
which gives the best approximation to $t^{n}$ on $[-1,1]$.
\begin{theorem}\label{T;nice Chebychev} 
Write $S_{n}(t)=t^{n}-2^{1-n}T_{n}(t)$,
where $T_{n}$ is the Chebychev polynomial of degree $n$.
Then (if $n\geq 1$)
\[\sup_{t\in[-1,1]}|t^{n}-Q(t)|\geq  \sup_{t\in[-1,1]}|t^{n}-S_{n}(t)|
= 2^{1-n}\]
for all polynomials $Q$ of degree $n-1$.
\end{theorem}
\begin{corollary}\label{C;naught for naught} 
We work on $[-1,1]$.
 
(i) If $P(t)=\sum_{j=0}^{n}a_{j}t^{j}$ 
is a polynomial of degree $n$
with $|a_{n}|\geq 1$, then $\|P\|_{\infty}\geq 2^{-n+1}$.

(ii) We can find $\epsilon(n)>0$ with the following property.
If $P(t)=\sum_{j=0}^{n}a_{j}t^{j}$ 
is a polynomial of degree at most $n$ and $|a_{k}|\geq 1$ for some
$n\geq k\geq 0$ then $\|P\|_{\infty}\geq \epsilon(n)$.
\end{corollary}

We can now use a compactness argument to prove that
there does exist a best approximation.
\begin{theorem}\label{T;best approximation exists}
If $f:[a,b]\rightarrow{\mathbb R}$ is a continuous
function, then
there exists a polynomial $P$ of degree at most $n$
such that $\|P-f\|_{\infty}\leq\|Q-f\|_{\infty}$ for all polynomials 
$Q$ of degree
$n$ or less.
\end{theorem}
We could also have proved Corollary 8.3~(ii) directly
by a compactness argument without using Chebchev's result.


We have only  shown that the Chebychev criterion 
is a sufficient condition.
However, it can be shown that it is also a necessary one.
The proof is given in Exercise~\ref{Q;ripple necessary}
but is not part of the course.
\section{Gaussian quadrature} How should we attempt to
estimate $\int_{a}^{b}f(x)\,dx$ if we only know $f$ at
certain points? One, rather naive, approach is to find
the interpolating polynomial for those points and integrate that.
This leads rapidly, via Lemma~\ref{L;interpolate polynomial},
to the following result.
\begin{lemma}\label{L;numerical}
Let $x_{0}$, $x_{1}$,
\dots, $x_{n}$ be distinct points of $[a,b]$.
Then there are unique real numbers $A_{0}$, $A_{1}$,
\dots, $A_{n}$ with the property that
\[\int_{a}^{b}P(x)\,dx=\sum_{j=0}^{n}A_{j}P(x_{j})\]
for all polynomials of degree $n$ or less.
\end{lemma}
However our previous remarks about interpolating
polynomials suggest, and experience confirms,
that it may not always be wise to use the approximation
\[\int_{a}^{b}f(x)\,dx\approx\sum_{j=0}^{n}A_{j}f(x_{j})\]
even when $f$ well behaved. 
In the particular case when the interpolation points
are equally spaced, computation suggests that as the number of points 
used increases the $A_{j}$ begin to vary in sign and become large in 
absolute value. It can be shown that this 
is actually the case
and that this means that the approximation can actually get
worse as the number of points increases.

It is rather surprising that there is a choice of points
which avoids this problem. Earlier 
(in Exercise~\ref{E;distinct metrics}~(ii))
we observed that 
the definition
\[\langle f,g\rangle=\int_{-1}^{1}f(t)g(t)\,dt\]
gives an inner product  on the vector space $C([-1,1])$.
Let us recall some results
from vector space theory.
\begin{lemma}\label{L;Gramm}{\bf [Gramm--Schmidt]}
\index{Gramm--Schmidt}Let $V$ be a vector space
with an inner product. Suppose that
${\mathbf e}_{1}$, ${\mathbf e}_{2}$,
\dots, ${\mathbf e}_{n}$ are orthonormal and ${\mathbf f}$
is not in their linear span. If we set
\[{\mathbf v}={\mathbf f}-\sum_{j=1}^{n}
  \langle{\mathbf f},{\mathbf e}_{j}\rangle{\mathbf e}_{j},\]
then
we know that ${\mathbf v}\neq {\boldsymbol 0}$ and
that, setting ${\mathbf e}_{n+1}=\|{\mathbf v}\|^{-1}{\mathbf v}$
the vectors ${\mathbf e}_{1}$, ${\mathbf e}_{2}$,
\dots, ${\mathbf e}_{n+1}$ are orthonormal.
\end{lemma}
Lemma~\ref{L;Gramm}
enables us to make the following definition.
\begin{definition}\index{Legendre polynomials}
The Legendre polynomials $p_{n}$
are the the polynomials given by the following
conditions\footnote{There are various other definitions,
but they all give polynomials of the form
$b_{n}p_{n}$. The only difference is in the choice of $b_{n}$.
As may be seen from Exercise~\ref{E;compute Legendre}
our choice is not very convenient for most uses.}. 

(i) $p_{n}$ is a polynomial of degree $n$ with positive leading
coefficient. 

(ii) ${\displaystyle \int_{-1}^{1}p_{n}(t)p_{m}(t)\,dt=\delta_{nm}
=\begin{cases}1\qquad\text{if $n=m$,}
\\0\qquad\text{otherwise.}\end{cases}}$
\end{definition}
\begin{lemma}\label{L;Legendre roots} 
The $n$th Legendre polynomial $p_{n}$ has $n$ distinct
roots all lying in $(-1,1)$.
\end{lemma}
Gauss had the happy idea of choosing the evaluation
points to be the roots of a Legendre polynomial\index{Gaussian quadrature}.
\begin{theorem}\label{T;Gauss}{\bf [Gaussian quadrature]} 
(i) If $\alpha_{1}$, $\alpha_{2}$,
\dots $\alpha_{n}$ are the $n$ roots of the
$n$th Legendre polynomial $p_{n}$ and
the $A_{j}$ are chosen so that
\[\int_{-1}^{1}P(x)\,dx=\sum_{j=1}^{n}A_{j}P(\alpha_{j})\]
for every polynomial $P$ of degree $n-1$ or less, then,
in fact
\[\int_{-1}^{1}Q(x)\,dx=\sum_{j=1}^{n}A_{j}Q(\alpha_{j})\]
for every polynomial $Q$ of degree $2n-1$ or less.

(ii) If $\beta_{j}\in[-1,1]$ and $B_{j}$ are such that
\[\int_{-1}^{1}Q(x)\,dx=\sum_{j=1}^{n}B_{j}Q(\beta_{j})\]
for every polynomial $Q$ of degree $2n-1$ or less,
then the $\beta_{j}$ are the roots of the $n$th Legendre polynomial.
\end{theorem}

Theorem~\ref{T;Gauss} looks impressive, but it is the next result
which really shows how good Gauss's idea is.
\begin{theorem}\label{T;nice quadrature}\index{Gauss, happy ideas} 
We continue with the notation of Theorem~\ref{T;Gauss}.

(i) $A_{j}\geq 0$ for each $1\leq j\leq n$.

(ii) $\sum_{j=1}^{n}A_{j}=2$.

(iii) If $f:[-1,1]\rightarrow{\mathbb R}$ is continuous and
$P$ is any polynomial of degree at most $2n-1$, then
\[\left|\int_{-1}^{1}f(x)\,dx-
\sum_{j=1}^{n}A_{j}f(\alpha_{j})\right|\leq 4\|f-P\|_{\infty}.\]

(iv) Write $G_{n}f$ for the estimate of $\int_{-1}^{1}f(t)\,dt$
obtained using Gauss's idea with the $n$th Legendre polynomial.
Then, if $f$ is continuous on $[-1,1]$,
\[G_{n}f\rightarrow \int_{-1}^{1}f(t)\,dt\]
as $n\rightarrow\infty$.
\end{theorem}

\section{Distance and compact sets} This section could
come almost anywhere in the notes, but provides some helpful
background to the section on Runge's theorem.
We start by strengthening Lemma~\ref{L;distance closed}. 
\begin{lemma}\label{L,from compact}
If $E$ is a non-empty compact set in ${\mathbb R}^{m}$
and ${\mathbf a}\in {\mathbb R}^{m}$, then there is
a point ${\mathbf e}\in E$ such that
\[\|{\mathbf a}-{\mathbf e}\|=
\inf_{{\mathbf x}\in E}\|{\mathbf a}-{\mathbf x}\|.\]
\end{lemma}

As before we write $d({\mathbf a},E)=
\inf_{{\mathbf x}\in E}\|{\mathbf a}-{\mathbf x}\|$.
\begin{exercise}\label{E;unique convex 1}
(i) Give an example to show that
the point ${\mathbf e}$ in Lemma~\ref{L,from compact}
need not be unique.

(ii) Show that, if $E$ is convex, ${\mathbf e}$
is unique.
\end{exercise}

\begin{lemma}\label{L;compact compact} 
(i) If $E$ and $F$ are non-empty compact sets in ${\mathbb R}^{m}$,
then there exist points ${\mathbf e}\in E$ and ${\mathbf f}\in F$
such that
\[\|{\mathbf e}-{\mathbf f}\|=\inf_{{\mathbf y}\in E}d({\mathbf y},F).\]

(ii) The result in~(i) remains true when $F$ is compact and non-empty
and $E$ is closed and non-empty. 

(iii) The result in~(i) may fail when $E$
and $F$ are closed and non-empty.
\end{lemma}
Let us write $\tau(E,F)=\inf_{{\mathbf y}\in E}d({\mathbf y},F).$
\begin{exercise}\label{E;unique convex 2} 
Give an example to show that
the points ${\mathbf e}$ and ${\mathbf f}$
in Lemma~\ref{L;compact compact}
need not be unique.
\end{exercise}
The statement of the next exercise requires us to recall 
the definition of a metric.
\begin{varthm}[Definition~\ref{D;metric}]
Suppose that
$X$ is a non-empty set
and $d:X^{2}\rightarrow{\mathbb R}$ is a function
such that

(i) $d(x,y)\geq 0$ for all $x,\,y\in X$.

(ii) $d(x,y)=0$ if and only if $x=y$.

(iii) $d(x,y)=d(y,x)$ for all $x,\,y\in X$.

(iv) $d(x,y)+d(y,z)\geq d(x,z)$ for all $x,\,y,\,z\in X$.

Then we say that $d$ is a metric on $X$ and that $(X,d)$
is a metric space.
\end{varthm}

\begin{exercise}\label{E;first try Hausdorff} 
Show that, if we consider the space 
${\mathcal K}$ of non-empty
compact sets in ${\mathbb R}^{m}$, then $\tau$ obeys
conditions~(i) and~(iii) for a metric but not conditions~(ii)
and~(iv).

Show that, if $E,F\in{\mathcal K}$, then $\tau(E,F)=0$ if and
only if $E\cap F\neq\emptyset$.
\end{exercise}

Since $\tau$ does not provide a satisfactory metric on 
${\mathcal K}$, we try some thing else. If $E$ and $F$ are
compact sets in ${\mathbb R}^{m}$, let us set
$\sigma(E,F)=\sup_{{\mathbf y}\in E}d({\mathbf y},F)$.
\begin{exercise}\label{E;Hausdorff try 2} 
Suppose that $E$ and $F$ are non-empty 
compact sets. Show that there exists an ${\mathbf e}\in E$
such that $d({\mathbf e},F)=\sigma(E,F)$.
\end{exercise} 
\begin{exercise}\label{E;Hausdorff try 3} Show that, 
if we consider the space 
${\mathcal K}$ of non-empty
compact sets in ${\mathbb R}^{m}$, then $\sigma$ obeys
condition~(i) for a metric but not conditions~(ii)
and~(iii).

Show that $\sigma(E,F)=0$ if and only if $E\subseteq F$.
\end{exercise}

However, $\sigma$ does obey the triangle inequality.
\begin{lemma}\label{L;start Hausdorff} 
If $E$, $F$ and $G$ are non-empty compact sets
then
\[\sigma(E,G)\leq \sigma(E,F)+\sigma(F,G).\]
\end{lemma}

This enables us to define the Hausdorff metric $\rho$.
\begin{definition} If $E$ and $F$ are non-empty compact
subsets of ${\mathbb R}^{m}$, we set\index{Hausdorff metric}
\[\rho(E,F)=\sigma(E,F)+\sigma(F,E),\]
that is to say,
\[\rho(E,F)=\sup_{{\mathbf e}\in E}\inf_{{\mathbf f}\in F}
\|{\mathbf e}-{\mathbf f}\|
+\sup_{{\mathbf f}\in F}\inf_{{\mathbf e}\in E}
\|{\mathbf e}-{\mathbf f}\|.
 \]
\end{definition}
\begin{theorem}\label{T;Hausdorff hurrah}
The Hausdorff metric $\rho$ is 
indeed a metric on the space ${\mathcal K}$ of non-empty
compact subsets of ${\mathbb R}^{m}$.
\end{theorem}


Indeed, we can say something even stronger which will come in
useful when we give examples of the use of Baire's  theorem
in Section~\ref{S;Baire}
\begin{theorem}\label{T;Hausdorff complete}
The Hausdorff metric $\rho$ is
a complete metric on the space ${\mathcal K}$ of non-empty
compact subsets of ${\mathbb R}^{m}$.
\end{theorem}

Our proof of Theorem~\ref{T;Hausdorff complete} makes use
of two observations.
\begin{theorem}\label{T;decreasing compact} (i) Suppose
that we have a sequence of non-empty compact sets
in ${\mathbb R}^{m}$ such that
\[K_{1}\supseteq K_{2}\supseteq K_{3}\supseteq\ldots.\]
Then $K=\bigcap_{p=1}^{\infty}K_{p}$ is a non-empty compact set.

(ii) Further, $K_{p}\underset{\rho}{\rightarrow} K$ 
as $p\rightarrow\infty$.
\end{theorem}
\begin{lemma}\label{L;extend compact} 
If $K$ is compact in ${\mathbb R}^{m}$ so
is 
\[K+\bar{B}(0,r)=\{{\mathbf x}+{\mathbf y}\,:\,
{\mathbf x}\in K,\ \|{\mathbf y}\|\leq r\}.\]
\end{lemma}
\section{Runge's theorem} The existence of two different introductory
courses in complex variable is one of many mad things in the
Cambridge system\index{lunacy, Cambridge}. 
The contents of this section should be accessible to 
anyone who has gone to \emph{either}. As I shall emphasise
from time to time, the reader will need to know some of the results
from those courses but will not be required to prove them.

Weierstrass's theorem tells us that
every continuous real valued function on $[a,b]$ can be
uniformly approximated by polynomials. Does a similar theorem
hold for complex variable?

Cauchy's theorem enables us to answer with a resounding no.
We write $\bar{z}$ for the complex conjugate of $z$.
\begin{example}\label{E;conjugate}
Let $\bar{D}=\{z\,:\,|z|\leq 1\}$ and define
$f:\bar{D}\rightarrow{\mathbb C}$ by
\[f(z)=\bar{z}.\]
If $P$ is any polynomial, then
\[\sup_{z\in\bar{D}}|f(z)-p(z)|\geq 1.\]
\end{example}

After looking at this example the reader may recall
the following theorem (whose proof does not form part
of this course).
\begin{theorem}\label{T;uniform limit} 
If $\Omega$ is an open subset of
${\mathbb C}$ and $f_{n}:\Omega\rightarrow{\mathbb C}$ is analytic,
then if $f_{n}\rightarrow f$ uniformly on $\Omega$
(or, more generally, if $f_{n}\rightarrow f$ uniformly on 
each compact subset of $\Omega$) then $f$ is analytic.
\end{theorem}

We might now conjecture that every analytic function 
on a well behaved set
can be uniformly approximated by polynomials.
Cauchy's theorem again shows that the matter is not straightforward.
\begin{example}\label{E;polo} 
Let $T=\{z\,:\,1/2\leq |z|\leq 2\}$ and define
$f:T\rightarrow{\mathbb C}$ by
\[f(z)=\frac{1}{z}.\]
If $P$ is any polynomial then
\[\sup_{z\in\bar{T}}|f(z)-p(z)|\geq 1.\]
\end{example}
Thus the best we can hope for is a theorem that tells
us that every analytic function on a suitable set
`without holes' can be uniformly approximated by polynomials.

We shall see that the following definition
gives a suitable `no holes' condition.
\begin{definition}\label{D;connected} 
An open set $U\subseteq {\mathbb C}$ is 
\emph{path connected}\index{path connected} 
if, given $z_{0},\,z_{1}\in U$, we
can find a continuous map $\gamma:[0,1]\rightarrow U$
with $\gamma(0)=z_{0}$ and $\gamma(1)=z_{1}$. 
\end{definition}
We will obtain results for a bounded sets whose
\emph{complement} is path connected. 


The reader may ask why we could not simply use Taylor's
theorem in complex variables. To see that this
would not work
we recall various earlier results. (As I said earlier
the proofs are not part of the
course, but you are expected to know the results.)
\begin{lemma} If $a_{j}\in{\mathbb C}$, then there exists
an $R\in[0,\infty]$ (with suitable conventions when $R=\infty$)
such that $\sum_{j=0}^{\infty}a_{j}z^{j}$ converges
for $|z|<R$ and diverges for $|z|>R$.
\end{lemma}
We call $R$ the radius of convergence of  
$\sum_{j=0}^{\infty}a_{j}z^{j}$.
\begin{lemma} If $\sum_{j=0}^{\infty}a_{j}z^{j}$
has radius of convergence $R$ and $R'<R$ then
$\sum_{j=0}^{\infty}a_{j}z^{j}$ converges uniformly 
for $|z|\leq R'$.
\end{lemma}
\begin{lemma}\label{L;unique power series} 
Suppose that $\sum_{j=0}^{\infty}a_{j}z^{j}$
has radius of convergence $R$ and
that $\sum_{j=0}^{\infty}b_{j}z^{j}$
has radius of convergence $R'$. If there exists an
$R''$ with $0<R''\leq R,R'$ such that
\[\sum_{j=0}^{\infty}a_{j}z^{j}=\sum_{j=0}^{\infty}b_{j}z^{j}\]
for all $|z|<R''$, then $a_{j}=b_{j}$ for all $j$.
\end{lemma}
By a careful use of Taylor's theorem Lemma~\ref{L;unique power series}
can be used to give the following extension. (The proof is not
part of the course but, again, you are expected to know the result.)
\begin{lemma}\label{L;unique analytic} 
Suppose that $f,g:B(w,r)\rightarrow{\mathbb C}$
are analytic. If there is a non-empty open subset $U$ of
$B(w,r)$ such that $f(z)=g(z)$ for all $z\in U$, it follows
that $g=f$.
\end{lemma} 
\begin{exercise}\label{E;no single power} 
(i) If $w\neq 0$, show that we can find a power
series $\sum_{j=0}^{\infty}a_{j}(z-w)^{j}$ with radius
of convergence $|w|$ such that  
\[z^{-1}=\sum_{j=0}^{\infty}a_{j}(z-w)^{j}\]
for all $|z-w|<|w|$.

(ii) Let 
\[\Omega=\{z\,:\, 10^{-2}<|z|<1\}
\setminus\{x\,:\,x\in{\mathbb R},\ x\leq 0\}\]
Show that $\Omega$ is open, path connected and bounded 
and $f(z)=1/z$ defines
a bounded analytic function on $\Omega$, but we can not find
$z_{0}$ and $b_{j}$ such that
\[z^{-1}=\sum_{j=0}^{\infty}b_{j}(z-z_{0})^{j}\]
for all $z\in\Omega$.
\end{exercise}


Let us see what Taylor's theorem actually says.
\begin{theorem}{\bf[Taylor's Theorem]} 
Suppose that $\Omega$ is an open set in ${\mathbb C}$
and $f:\Omega\rightarrow{\mathbb C}$ is analytic.
If the open disc
\[B(z_{0},\delta)=\{z\,:\,|z-z_{0}|<\delta\}\]
lies in $\Omega$, then we can find  $a_{j}\in{\mathbb C}$
such that $\sum_{j=0}^{\infty}a_{j}z^{j}$ has radius of convergence
at least $\delta$ and
\[\sum_{j=0}^{\infty}a_{j}(z-z_{0})^{j}=f(z)\]
for all $z\in B(z_{0},\delta)$.
\end{theorem}

Thus Taylor's theorem for analytic functions says 
(among other things) that
an analytic function can be \emph{locally}
approximated uniformly by polynomials.
Runge's theorem asserts that (under certain conditions)
an analytic function can be \emph{globally}
approximated uniformly by polynomials.
\begin{theorem}{\bf [Runge's theorem]}\label{T;Runge} 
Suppose that
$\Omega$ is an open set and $f:\Omega\rightarrow{\mathbb C}$
is analytic.
Suppose that $K$ is a compact set with $K\subseteq \Omega$
and ${\mathbb C}\setminus K$ path connected. Then given
any $\epsilon>0$, we can find a polynomial  $P$ with
\[\sup_{z\in K}|f(z)-P(z)|<\epsilon.\] 
\end{theorem}
I shall make a number of remarks before moving
on to the proof. The first is that (as might be expected)
Theorem~\ref{T;Runge} is the simplest of a family of
results which go by the name of Runge's theorem.
However, I think that it is fair to say that, once the proof
of this simplest case is understood, both the proofs
and the meanings of the more general theorems
are not hard to grasp.

The second remark is that the reader will
lose very little understanding\footnote{And,
provided she does not twist the examiner's nose, few
marks in the exam.}
if she concentrates 
on the example of Runge's theorem for geometrically simple
$K$ and $\Omega$ (like rectangles and triangles).

Our proof of Runge's theorem splits into several steps.
\begin{lemma}\label{L;Runge contour} Suppose that $K$ 
is a compact set with $K\subseteq \Omega$.
Then we can find a finite set 
of piece-wise linear contours $C_{m}$
lying entirely within $\Omega\setminus K$ such that
\[f(z)=\frac{1}{2\pi i}\sum_{m=1}^{M}\int_{C_{m}}\frac{f(w)}{w-z}\,dw\]
whenever $z\in K$ and $f:\Omega\rightarrow{\mathbb C}$
is analytic.
\end{lemma}

It is worth making the following observation explicit.
\begin{lemma}\label{L;note Runge} 
With the notation and conditions of 
Lemma~\ref{L;Runge contour}, we can find a $\delta>0$
such that $|z-w|\geq\delta$ whenever $z\in K$ and
$w$ is a point of one of the contours $C_{m}$.
\end{lemma} 
We use Lemma~\ref{L;Runge contour} to prove the following
result which takes us closer to  our goal.
\begin{lemma}\label{L:Runge to simple} 
Suppose that $K$ 
is a compact set with $K\subseteq \Omega$.
Then given any  analytic $f:\Omega\rightarrow{\mathbb C}$
and any $\epsilon>0$ we can find an integer $N$,
complex numbers $A_{1},\,A_{2},\, \dots,\,A_{N}$
and $\alpha_{1},\,\alpha_{2},\,\dots,\,\alpha_{N}\in\Omega\setminus K$
such that
\[\left|f(z)-\sum_{n=1}^{N}\frac{A_{n}}{z-\alpha_{n}}\right|
\leq\epsilon\]
for all $z\in K$.
\end{lemma}

Thus Runge's theorems follows at once from the following
special case.
\begin{lemma}\label{L;simple Runge 1} 
Suppose that $K$ is a compact set
and ${\mathbb C}\setminus K$ path connected. Then, given
any $\alpha\notin K$ and
any $\epsilon>0$, we can find a polynomial  $P$ with
\[\left|P(z)-\frac{1}{z-\alpha}\right|
<\epsilon\]
for all $z\in K$.
\end{lemma}

Let us make a temporary definition.
\begin{definition} Let $K$ be a compact set in ${\mathbb C}$.
We write $\Lambda(K)$ for the set of points $\alpha\notin K$
such that, given any $\epsilon>0$, we can find a polynomial  $P$ with
\[\left|P(z)-\frac{1}{z-\alpha}\right|
<\epsilon\]
for all $z\in K$. 
\end{definition}
A series  of observations about $\Lambda(K)$ brings the proof 
of Runge's theorem to a close.
\begin{lemma}\label{L;far Runge} 
Let $K$ be a compact set in ${\mathbb C}$.
Then there exists an $R$ such that $|\alpha|>R$ implies 
$\alpha\in \Lambda(K)$.
\end{lemma} 
\begin{lemma}\label{L;simple Runge 2} 
Let $K$ be a compact set in ${\mathbb C}$.
If $\alpha\in\Lambda(K)$ and $|\alpha-\beta|<d(\alpha,K)$
then $\beta\in\Lambda(K)$.
\end{lemma}
\begin{lemma}\label{L;simple Runge 3}
Suppose that $K$ is a compact set in  ${\mathbb C}$
and ${\mathbb C}\setminus K$ is path connected.
Then $\Lambda(K)={\mathbb C}\setminus K$.
\end{lemma}

Since Lemma~\ref{L;simple Runge 3} is equivalent to
Lemma~\ref{L;simple Runge 1}, this completes the proof
of our version of Runge's theorem.

It is natural to ask if the condition of uniform convergence
can be dropped in Theorem~\ref{T;uniform limit}. 
We can use Runge's theorem to show that it
can not.
\begin{example}\label{E;bite round} 
Let $D=\{z\,:\,|z|<1\}$ and define
$f:D\rightarrow{\mathbb C}$ by
\[f(re^{i\theta})=r^{3/2}e^{3i\theta/2}\]
for $r\geq 0$ and $0<\theta\leq 2\pi$ (so that
$f$ is not even continuous). Then we can find a sequence
of polynomials $P_{n}$ such that $P_{n}(z)\rightarrow f(z)$
as $n\rightarrow\infty$ for all $z\in D$.
\end{example}
\section{Odd numbers}
According to Von Neumann\footnote{Dr Bloom suggests a
a footnote in the 
`The Dancing Wu Li Masters' by Gary Zukav as a source.} 
`In mathematics you don't understand things. You just get used to them.'
The real line is one of the most extraordinary objects 
in mathematics\footnote{I am being modest on behalf of analysis,
I suspect the real line is the most extraordinary object in mathematics.}.
A single apparently innocuous axiom (`every increasing bounded
sequence has a limit' or some equivalent formulation) calls
into being an indescribably complicated object.

We know from~1A that ${\mathbb R}$ is uncountable (a different
proof of this fact  will be given later in Corollary~\ref{C;Cantor}).
But, if we have a finite alphabet of $n$ symbols (including punctuation),
then we can only describe at most $n^{m}$ real numbers in  phrases
exactly $m$ symbols long. Thus  the collection of 
describable real numbers is the countable union of finite (so countable)
sets so (quoting~1A again) countable! We find ourselves
echoing Newton. 
\begin{quote} I do not know what I may appear to the world, 
but to myself I seem to have been only like a boy 
playing on the sea-shore, and diverting myself in now and then 
finding a smoother pebble or a prettier shell than ordinary, 
whilst the great ocean of truth lay all undiscovered before me.
[\emph{Memoirs of the Life, Writings, and Discoveries of Sir Isaac Newton} 
Brewster (Volume II. Ch. 27)]
\end{quote}

Let us look at some of the prettier shells.
\begin{theorem}\label{T;irrational exponential} 
The number $e$ is irrational.\index{e@$e$ irrational}
\end{theorem}
\begin{theorem}\label{T;pi} The number $\pi$ is 
\index{pi@$\pi$ irrational}irrational.
\end{theorem}
Our proof of Theorem~\ref{T;pi} depends on the following lemma.
\begin{lemma}\label{L;onto pi} If we write
$f_{n}(x)=x^{n}(\pi-x)^{n}$ then   
\[\int_{0}^{\pi}f_{n}(x)\sin x\,dx=n!\sum_{j=0}^{n}a_{j}\pi^{j}\]
with $a_{j}$ an integer. 
\end{lemma}

Faced with a proof like that of Theorem~\ref{T;pi} the
reader may cry `How did you think of looking at $f_{n}(x)$?'
The first, though not very helpful, answer is `I did not, I
learnt it from someone else\footnote{Professor Gowers in this case.}'.
The second
is that,
even admitting that we could not have thought of it
in a  thousand years, once we are presented with the argument
we can see a path (though not, I suspect, the actual one)
which it might have been thought of.
We are all familiar with the evaluation of 
$\int_{0}^{\pi}x^{n}\sin x\,dx$ and the fact that this
takes the form $P(\pi)$ where $P$ is polynomial 
of degree at most $n$ with
integer coefficients. It follows that if $Q$ is
a polynomial of degree $n$
with integer coefficients then
$\int_{0}^{\pi}Q(x)\sin x\,dx$ takes the form 
$U(\pi)$ where $u$ is polynomial of degree at most $n$
with integer coefficients. If $\pi=p/q$ then
$q^{n}U(\pi)$ is an integer. We now experiment,
trying to make $\int_{0}^{\pi}Q(x)\sin x\,dx$
lie between $0$ and $1$ in the manner of our proof
that $e$ was irrational.  
 
For what it is worth, I think the restriction `candidates will not
be required to quote elaborate formula from memory' ought
to mean that the examiners remind you of the formula for $f_{n}$
in a question that requires it. However, it is also my opinion 
that examiners,
like umpires, are always right.

It may be worth remembering that, after 300 years we still do not know
if Euler's constant
\[\gamma=\lim_{N\rightarrow\infty}
\left(\sum_{n=1}^{N}\frac{1}{n}-\log N\right)\]
is irrational or not.

If we think of the rationals as `the best understood numbers'
then the algebraic numbers can be thought of as 
`the next best understood numbers'.
\begin{definition}\index{algebraic numbers} 
We say that a real number $\alpha$ is
algebraic if it is a zero of a polynomial with integer coefficients.
Real numbers which are not algebraic are called transcendental.
\end{definition}
\begin{exercise}\label{E;algebraic numbers} 
Show that a real number $\alpha$ is
algebraic if and only if it is a zero of a polynomial with 
rational coefficients.
\end{exercise}
\begin{lemma}\label{L;algebraic countable} 
The algebraic numbers are countable.
\end{lemma}
Since the reals are uncountable, this shows that transcendental
numbers exist.

The argument just given (which you saw in~1A) is due to Cantor.
It is beautiful but non-constructive. It tells us that transcendental
numbers exist (indeed that uncountably many transcendental numbers exist)
without showing us any.

The first proof that transcendentals exist was given
earlier by Liouville\footnote{Once when lecturing to a
  class [Kelvin] used the word `mathematician,'
  and then interrupting himself asked his class: 'Do
  you know what a mathematician is?' Stepping to the blackboard
  he wrote upon it:—
  \[\int_{-\infty}^{\infty}e^{-x^{2}/2}\,dx=\sqrt{2\pi}.\]
  Then putting his finger on what he had written,
  he turned to his class and said: `A mathematician
  is one to whom that is as obvious as that twice
  two makes four is to you. Liouville was a mathematician.'
  [S. P. Thompson, \emph{Life of Lord Kelvin}]}.
It is longer but actually produces particular examples.
\begin{theorem} {\bf [Liouville]}\label{T;Liouville} 
Suppose $\alpha$ is an irrational root of the
equation
\[a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{0}=0\]
where $a_{j}\in{\mathbb Z}$ $[0\leq j\leq n]$, $n\geq 1$ and 
$a_{n}\neq 0$.
Then there is a constant $c>0$ (depending on the $a_{j}$)
such that
\[\left|\alpha-\frac{p}{q}\right|\geq \frac{c}{q^{n}}\]
for all $p,\,q\in{\mathbb Z}$ with $q\neq 0$
\end{theorem}
We can now exhibit a transcendental number.
\begin{theorem}\label{T;Liouville number} The number
\[\sum_{j=0}^{\infty}\frac{1}{10^{j!}}\]
is transcendental.
\end{theorem}
\begin{exercise}\label{E;uncountable Liouville} 
By considering
\[\sum_{n=0}^{\infty}\frac{b_{n}}{10^{n!}}\]
with $b_{j}\in\{1,\,2\}$, give another proof that the
set of transcendental numbers is uncountable.
\end{exercise}

As might be expected, it turned out to be very hard to
show that particular numbers are transcendental.
Hermite proved that $e$ is transcendental and
Lindemann adapted Hermite's method to show that
$\pi$ is transcendental (and so the circle can not be squared).
Alan Baker contributed greatly to this field,
and his book \emph{Transcendental number theory}~\cite{Baker}
contains accessible\footnote{But miraculous.} proofs
of the transcendence of $e$ and $\pi$.
\section{The Baire category theorem}\label{S;Baire}
The following theorem turns
out to be much more useful than its somewhat abstract
formulation makes it appear.
\begin{theorem} {\bf [The Baire category theorem]}%
\label{T;Baire} 
If $(X,d)$ is a complete non-empty metric space and $U_{1}$, $U_{2}$,
\dots are open sets whose complements have empty interior,
then 
\[\bigcap_{j=1}^{\infty}U_{j}\neq\emptyset.\]
\end{theorem}
Taking complements gives the following equivalent form.
\begin{theorem}\label{T;complement Baire}
If $(X,d)$ is a complete non-empty metric space and $F_{1}$, $F_{2}$,
\dots are closed sets with empty interior,
then 
\[\bigcup_{j=1}^{\infty}F_{j}\neq X.\]
\end{theorem}

I think of Baire's theorem in yet another equivalent form.
\begin{theorem}\label{T;informal} Let
$(X,d)$ be a non-empty complete metric space.
Suppose that $P_{j}$ is a property  such that:-

(i) The property of being $P_{j}$
is \emph{stable} in the sense that, given
$x\in X$ which has property $P_{j}$,
we can find an  $\epsilon>0$ such that whenever
$d(x,y)<\epsilon$ the point $y$  has the property $P_{j}$.

(ii) The property of not being $P_{j}$
is \emph{unstable} in the sense that, given
$x\in X$ and $\epsilon>0$, we can find a $y\in X$
with $d(x,y)<\epsilon$ which has the property $P_{j}$.

Then there is an $x_{0}\in X$ which has all of the
of the properties $P_{1}$, $P_{2}$, \ldots.
\end{theorem}

Baire's theorem has given rise to the following
standard definitions\footnote{Your lecturer thinks
that, whilst the concepts defined are very useful, the nomenclature 
is particularly unfortunate.}.
\begin{definition} A set in a metric space is said to be
\emph{nowhere dense}\index{nowhere dense} if its closure has empty interior.
A set in a metric space is said to be of \emph{first category}
\index{first category} if it 
is a subset of a countable union of nowhere dense closed sets. Any set which is
not of first category is said to be of
\emph{second category}\index{second category}.
\end{definition}
Your lecturer will try never to use the words second category
but always to talk about `not first category'.
If all points outside a set of first category have a property
$P$, I shall say that \emph{quasi-all}\index{quasi-all} 
points have property $P$.

Two key facts about first countable sets are stated
in the next lemma.
\begin{lemma}\label{L;Baire obvious}
(i) If $(X,d)$ is a non-empty complete metric space
and $E$ is a subset of first category, then $E\neq X$.

(ii) The countable union of sets of first category is of first category.
\end{lemma}

We need one more definition. 
\begin{definition} (i) If $(X,d)$ is a metric space,
we say that a point $x\in X$ is \emph{isolated}\index{isolated point}
if
we can find a $\delta>0$ such that $B(x,\delta)=\{x\}$.

(ii) If $(X,d)$ is a metric space, we say that a subset
$E$ of $X$ contains no isolated points if, whenever $x\in E$
and $\delta>0$, we have $B(x,\delta)\cap E\neq\{x\}$.
\end{definition}
\begin{theorem}\label{T;no isolated} 
A non-empty complete metric space without isolated 
points is uncountable.
\end{theorem}
\begin{corollary}\label{C;Cantor} The real numbers  are uncountable.
\end{corollary}
The proof we have given here is much closer to Cantor's original
proof than that given in~1A.
It avoids the use of extraneous concepts like decimal representation.

Banach was a master of using the Baire category theorem.
Here is one of his results.
\begin{theorem}\label{T;Banach}\label{T;nowhere}
Consider $C([0,1])$
with the uniform norm. The set of anywhere differentiable
functions is a set of the first category. Thus continuous nowhere
differentiable functions exist.
\end{theorem}

Here is another corollary of Theorem~\ref{T;no isolated}.
\begin{corollary}\label{C;perfect} A non-empty closed subset
of ${\mathbb R}$ without isolated 
points is uncountable. 
\end{corollary}

Do there exist nowhere dense closed subsets of ${\mathbb R}$ with
no isolated points\footnote{Such sets are called perfect.
If they make pretty pictures they are called fractals.
You do not have to remember either name.}?
We shall answer this question by applying Baire's theorem in 
the context of the Hausdorff metric.
\begin{lemma}\label{L;splendid isolation} 
Consider the space $\mathcal K$ of 
non-empty compact subsets of $[0,1]$
with the Hausdorff metric $\rho$. Let
${\mathcal E}_{k}$ be the collection 
of compact sets $E$ such that
there exists an $x\in E$ with $B(x,1/k)\cap E=\{x\}$.

(i)  The
set ${\mathcal E}_{k}$ is closed in the Hausdorff metric.

(ii) The
set ${\mathcal E}_{k}$ is nowhere dense in the Hausdorff metric.

(iii) The set  ${\mathcal E}$ of compact sets 
with an isolated point is of first category
with respect to the Hausdorff metric.
\end{lemma}

\begin{lemma}\label{L;empty interior} Consider the space ${\mathcal K}$
of non-empty compact subsets of $[0,1]$
with the Hausdorff metric $\rho$. 
Let ${\mathcal F}_{j,k}$ be the collection
of compact sets $F$ such that
$F\supseteq [j/k,(j+1)/k]$ $[0\leq j\leq k,\ 1\leq k]$.

(i)  The
set ${\mathcal F}_{j,k}$ is closed in the Hausdorff metric.

(ii) The
set ${\mathcal F}_{j,k}$ is nowhere dense in the Hausdorff metric. 


(ii) The set  ${\mathcal F}$ of compact sets 
with non-empty interior is of first category.
\end{lemma}

\begin{theorem}\label{T;many Cantor} 
The set ${\mathcal C}$ of non-empty
compact sets with empty interior
and no isolated points is the complement of a set of first category 
in the space ${\mathcal K}$
of non-empty compact subsets of $[0,1]$
with the Hausdorff metric $\rho$.
\end{theorem}

Since ${\mathcal K}$ with the Hausdorff metric is complete
it follows that non-empty compact sets with empty interior 
and no isolated points exist.


The following example provides a background to
our next use of Baire category.
\begin{exercise}\label{E;many witches}\index{witchs' hats} 
(i) Show that we can find continuous functions
$g_{n}:[0,1]\rightarrow{\mathbb R}$ such that
$g_{n}(x)\rightarrow 0$ for each $x\in[0,1]$
but
\[\sup_{t\in[0,1]}g_{n}(t)\rightarrow\infty\]
as $n\rightarrow\infty$.

\noindent$[$Hint: Witch's hat.$]$

(ii)
Show that we can find continuous functions
$f_{n}:[0,1]\rightarrow{\mathbb R}$ such that
$f_{n}(x)\rightarrow 0$ for each $x\in[0,1]$
but
\[\sup_{t\in[2^{-r-1},2^{-r}]}f_{n}(t)\rightarrow\infty\]
as $n\rightarrow\infty$
for each integer $r\geq 0$.
\end{exercise}

In spite of the previous example we have the following
remarkable theorem.
\begin{theorem}\label{T;bound on interval} Suppose  that we have
a sequence of continuous functions
$f_{n}:[0,1]\rightarrow{\mathbb R}$ such that
$f_{n}(x)\rightarrow 0$ for each $x\in[0,1]$
as $n\rightarrow\infty$. Then we can find
a non-empty interval $(a,b)\subseteq[0,1]$
and an $M>0$ such that
\[|f_{n}(t)|\leq M\]
for all $t\in(a,b)$ and all $n\geq 1$.
\end{theorem}

A slightly stronger version of the result is given
as Exercise~\ref{E;small bound}.
\section{Continued fractions}\label{S;continued} 
We are used to writing real numbers as decimals, but there are other
ways of specifying real numbers which may be more convenient.
The oldest of these is the method of continued fractions.
Suppose that $x$ is irrational and $1\geq x>0$. 
We know that there is a strictly positive integer $N(x)$
such that
\[\frac{1}{N(x)}\geq x>\frac{1}{N(x)+1}\]
so we can write 
\[x=\frac{1}{N(x)+T(x)}\]
where $T(x)$ is irrational and $1> T(x)\geq 0$.
Thus 
\[Nx=\left[\frac{1}{x}\right],\ Tx=\frac{1}{x}-\left[\frac{1}{x}\right]\].
We can do the same things to $T(x)$ as we did to $x$,
obtaining
\[T(x)=\frac{1}{N(T(x))+T(T(x))}\]
and so, using the standard notation for composition of functions,
\[x=\cfrac{1}{N(x)+\cfrac{1}{NT(x)+T^{2}(x)}}\  .\]
The reader\footnote{As opposed to typesetters; this sort
of thing turned their hair prematurely grey.} 
will have no difficulty in proceeding to the next step
and obtaining
\[x=\cfrac{1}{N(x)+\cfrac{1}{NT(x)+\cfrac{1}{NT^{2}(x)+T^{3}(x)}}}\ ,\]
and so on indefinitely. We call
\[\cfrac{1}{N(x)+\cfrac{1}{NT(x)+\cfrac{1}{NT^{2}(x)+
\cfrac{1}{NT^{3}(x)+\dots}}}}\ \]
the \emph{continued fraction expansion} of $x$.
[Note that, for the moment, this is simply a pretty way
of writing the infinite sequence $N(x)$, $NT(x)$, $NT^{2}(x)$,
\dots. In the next section we shall show first that the
continued fraction can be assigned a numerical meaning  and 
then  that the assigned meaning is, as we might hope, $x$.]

If $y$ is a general irrational number, we call
\[[y]+
\cfrac{1}{N(x)+\cfrac{1}{NT(x)+\cfrac{1}{NT^{2}(x)+
\cfrac{1}{NT^{3}(x)+\dots}}}}\ .\]
the \emph{continued fraction expansion} of $y$.
   
We can do the same thing if $y$ is rational, but
we must allow for the possibility that the process does not continue
indefinitely. It is instructive to carry out the process
in a particular case.
\begin{exercise}\label{E;100/37} Carry out the process outlined above
for $100/37$. Carry out  the process for the rational 
of your choice.
\end{exercise}

Once we have done a couple of examples it is clear that
we are simply echoing Euclid's algorithm\footnote{I think
historians would reverse the order and say that continued fractions
gave rise to Euclid's algorithm}.
\begin{lemma}\label{L;continued Euclid}
(i) Suppose that $r_{k}$, $s_{k}$ are coprime
positive integers with $r_{k}<s_{k}$;
that $r_{k+1}$, $s_{k}$ are coprime
strictly positive integers with $r_{k+1}<s_{k+1}$.
and that $a_{k}$ is a strictly positive integer. If
\[\frac{r_{k}}{s_{k}}=\cfrac{1}{a_{k}+\cfrac{r_{k+1}}{s_{k+1}}},\]
then $s_{k+1}=r_{k}$
\[s_{k}=a_{k}s_{k+1}+r_{k+1}\]
for some positive integer $k_{1}$.
Thus the pair $(r_{k+1},s_{k+1})$ is obtained from $(r_{k},s_{k})$ 
by applying one step of the Euclidean algorithm. 

(ii) If $y$ is a rational number, its continued fraction expansion
(obtained by the method described above) terminates.
\end{lemma}  
\begin{exercise}\label{E;square root} Show that $\sqrt{2}$ has 
continued fraction expansion
\[1+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{2+\dots}}}}.\]
Deduce that $\sqrt{2}$ is irrational.
\end{exercise}

If we look at a random variable with the uniform distribution
on $[0,1]$ then the successive terms in the decimal expansion of $X$
will be independent and will take the value $j$ with
probability $1/10$ $[0\leq j\leq 9]$.
\begin{exercise}\label{E;decimal} (This easy exercise formalises
the remark just made.) If $x\in[0,1)$ let us write
$Dx=10x-[10x]$ (in other words, $Dx$ is the fractional part
of $10x$) and $Nx=[10x]$. Show
that 
\[x=10^{-1}(Dx+Nx)=10^{-1}Nx+10^{-2}NDx+10^{-2}D^{2}x=\dots\]
and write down the next term in the chain of equalities explicitly.

If $X$ is a random variable with uniform distribution
on $[0,1]$, show that $NX$, $NDX$, $ND^{2}X$, $\dots$
are independent and
\[\Pr(ND^{k}X=j)=1/10\]
for $0\leq j\leq 9$.
\end{exercise}
 
Gauss made the following observation\index{Gauss, happy ideas}.
\begin{lemma}\label{L;Gauss} Suppose that $X$ is a random variable on $[0,1)$
with density function 
\[f(x)=\left(\frac{1}{\log 2}\right)\frac{1}{1+x}.\]
Then $TX$ is a random variable with the same 
density function.
\end{lemma}
\begin{corollary}\label{C;continued random}
Suppose that $X$ is a random variable on $[0,1]$
with density function 
\[f(x)=\left(\frac{1}{\log 2}\right)\frac{1}{1+x}.\]
Then 
\[\Pr(NT^{m}X=j)=\frac{1}{\log 2}\int_{1/(j+1)}^{1/j}\frac{dx}{1+x}
=\frac{1}{\log 2}\log\left(\frac{(j+1)^{2}}{j(j+2)}\right).\]
\end{corollary}
\begin{proof}
By Lemma~\ref{L;Gauss},
\begin{align*}
\Pr(NT^{m}X=j)&=\Pr(NX=j)\\
&=\frac{1}{\log 2}
\int_{j^{-1}}^{(j+1)^{-1}}\frac{1}{1+x}\,dx\\
&=\frac{1}{\log 2}
\Big[\log(1+x)\Big]_{(j+1)^{-1}}^{j^{-1}}\\
&=\frac{1}{\log 2}\big(\log(j+2)-\log (j+1)\big)
=\frac{1}{\log 2}\log\frac{j+2}{j+1}.
\end{align*}
\end{proof}
With a little extra work (which we shall not do)
we can show that, if $X$ has the density suggested by Gauss,
then $NX$, $NTX$, $NT^{2}X$, \dots are independent random
variables all with the same probability distribution.
It is also not hard to guess, and not very hard to prove, that
if $Y$ is uniformly distributed on $[0,1]$, then
\[\Pr(NT^{m}Y=j) 
\rightarrow\frac{1}{\log 2}\log\left(\frac{(j+1)^{2}}{j(j+2)}\right).\]
as $m\rightarrow\infty$,
but we shall not take the matter further.
\section{Continued fractions (continued)}\label{S;continued continued}
In the previous section 
we showed how to compute the continued fraction associated with a 
real number $x$, but we did not really consider what
exact meaning was to be assigned to the result. In this
section we show that continued fractions do what we 
might hope they do.

\begin{definition}\label{D;continue}
If $a_{1}$, $a_{2}$, \dots
is a sequence of strictly positive integers and $a_{0}$ is
a positive integer we call
\[a_{0}+\cfrac{1}
{a_{1}+\cfrac{1}
{a_{2}+\cfrac{1}
{a_{3}+\cfrac{1}
{a_{4}+\dots}}}}\]
the continued fraction associated with ${\mathbf a}=(a_{0},a_{1},a_{2},\ldots)$.
\end{definition}
\begin{lemma}\label{L;continued matrices start} 
(i) We use the notation of Definition~\ref{D;continue}.
If we take 
\[r_{n}=a_{n},\ s_{n}=1\]
and define $r_{k}$ and $s_{k}$
in terms  of $r_{k+1}$ and $s_{k+1}$
\[\begin{pmatrix}r_{k}\\s_{k}\end{pmatrix}=
\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}
\begin{pmatrix}r_{k+1}\\s_{k+1}\end{pmatrix},
\]
then
\[\frac{r_{k}}{s_{k}}
=a_{k}+
\cfrac{1}
{a_{k+1}+\cfrac{1}
{a_{k+2}+\cfrac{1}
{a_{k+3}+\cfrac{1}
{a_{k+4}+\cfrac{1}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{1}
{a_{n}}}}}}}}.\]


(ii) If we set
\[\begin{pmatrix}r_{0}\\s_{0}\end{pmatrix}
=\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\dots\
\begin{pmatrix}a_{n-1}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{n}\\1\end{pmatrix},
\]
then
\[\frac{r_{0}}{s_{0}}
=a_{0}+\cfrac{1}
{a_{1}+\cfrac{1}
{a_{2}+\cfrac{1}
{a_{3}+\cfrac{1}
{a_{4}+\cfrac{1}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{1}
{a_{n}}}}}}}}\]
\end{lemma}

We now read everything off in the opposite direction
\begin{lemma}\label{L;continued matrices}
(i) If we set
\[\begin{pmatrix}p_{n}\\q_{n}\end{pmatrix}
=\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\dots\
\begin{pmatrix}a_{n-1}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{n}\\1\end{pmatrix},
\]
then
\[\frac{p_{n}}{q_{n}}
=a_{0}+\cfrac{1}
{a_{1}+\cfrac{1}
{a_{2}+\cfrac{1}
{a_{3}+\cfrac{1}
{a_{4}+\cfrac{1}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{1}
{a_{n}}}}}}}}\]

(ii) Further
\[\begin{pmatrix}p_{n}&p_{n-1}\\q_{n}&q_{n-1}\end{pmatrix}
=\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\cdots
\begin{pmatrix}a_{n-1}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{n}&1\\1&0\end{pmatrix},
\]
\end{lemma}

The pay-off for our work in recasting matters in matricial form
comes in the next theorem.
\begin{theorem}\label{T;continued convergence} 
Choose $p_{j}$ and $q_{j}$ as
in Lemma~\ref{L;continued matrices}.

(i) $p_{k}q_{k-1}-q_{k}p_{k-1}=(-1)^{k+1}$ for all $k$.

(ii) $q_{k}=a_{k}q_{k-1}+q_{k-2}$ and
$p_{k}=a_{k}p_{k-1}+p_{k-2}$ for all $k\geq 2$.

(iii) $p_{k}$ and $q_{k}$ are coprime for all $k$.

(iv)  We have 
\[\frac{p_{2k}}{q_{2k}}>\frac{p_{2k-2}}{q_{2k-2}},
\ \frac{p_{2k-1}}{q_{2k-1}}>\frac{p_{2k+1}}{q_{2k+1}}
\]
and
\[\left|\frac{p_{k}}{q_{k}}-\frac{p_{k+1}}{q_{k+1}}\right|
=\frac{1}{q_{k}q_{k+1}}.\]

(v) Suppose $a_{j}$ is a sequence of strictly positive 
integers for $j\geq 1$ and $a_{0}$ is a positive integer.
Then there exists an $\alpha\in{\mathbb R}$ such that
\[\frac{p_{n}}{q_{n}}\rightarrow \alpha.\]
Further
\[\left|\frac{p_{n}}{q_{n}}-\alpha\right|\leq\frac{1}{q_{n}q_{n+1}}.\]
\end{theorem}
\begin{exercise}\label{E;above below} 
Suppose we have an irrational $x\in(0,1]$
and we form a continued fraction (with $a_{0}=0$)
\[\cfrac{1}
{a_{1}+\cfrac{1}
{a_{2}+\cfrac{1}
{a_{3}+\cfrac{1}
{a_{4}+\dots}}}}\]
in the manner of Section~\ref{S;continued}. Show that
\[\frac{p_{2k}}{q_{2k}}<x<
\frac{p_{2k-1}}{q_{2k-1}}\]
for all $k$ and deduce that $x=\alpha$ where $\alpha$ is
the value of the associated
continued fraction.
\end{exercise} 
\begin{theorem}\label{T;good continue} 
Continuing with the ideas and notation
of Theorem~\ref{T;continued convergence}, $p_{n}/q_{n}$
is closer to $\alpha$ than any other fraction with 
denominator no larger than $q_{n}$. In other words,
\[\left|\frac{p_{n}}{q_{n}}-\alpha\right|
\leq\left|\frac{p}{q}-\alpha\right|\]
whenever $p$ and $q$ are integers with $1\leq q \leq q_{n}$. 
\end{theorem}
\begin{theorem}\label{T;good Liouville} 
If $x$ is irrational, we can find
$u_{n}$ and $v_{n}$ integers with $v_{n}\rightarrow\infty$
such that
\[ \left|\frac{u_{n}}{v_{n}}-x\right|<\frac{1}{v_{n}^{2}}.\]
\end{theorem}

This result should be compared with Theorem~\ref{T;Liouville}.
We give another proof of Theorem~\ref{T;good Liouville} 
in Exercise~\ref{Q;Chest of drawers}. We give a slight
improvement in Exercise~\ref{Q;split}.
\begin{exercise}\label{E;bad quadratic approximation} 
Which earlier result tells us that,
if $\alpha$ is the irrational root of a quadratic
with integer coefficients,
then there exists a $C$ (depending on $\alpha$) such that
\[ \left|\frac{u}{v}-\alpha\right|\geq\frac{C}{v^{2}}\]
whenever $u$ and $v$ are integers with $v\geq 1$?
\end{exercise}

We can treat `terminating continued fractions' and
rationals in the same way.

Speaking rather vaguely, we see
that the occurrence of large $a_{j}$'s in a continued
fraction expansion gives rise to large $q_{m}$'s
and associated good approximations. It is reasonable to
look at the most extreme opposite case.
\begin{exercise}\label{E;Lewis} (i) Show that, if we write
\[\sigma= \cfrac{1}
{1+\cfrac{1}
{1+\cfrac{1}
{1+\cfrac{1}
{1+\dots}}}},\]
then 
\[\sigma=\frac{-1+\sqrt{5}}{2}.\]

(ii) Show that, if  we form $p_{n}$ and $q_{n}$ in the usual way
for the continued fraction above, then
$p_{n}=F_{n}$, $q_{n}=F_{n+1}$ where $F_{m}$ is the $m$th 
Fibonacci number given by $F_{0}=0$, $F_{1}=1$ and
\[F_{m+1}=F_{m}+F_{m-1}.\]

(iii) Show that
\[F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n}.\]
\end{exercise}

\begin{exercise}\label{E;prepare entry} 
Use the continued fraction expansion
of $\sigma$ 
and Theorem~\ref{T;good continue} to show that there exists
an $m>0$ such that
\[\left|\frac{p}{q}-\sigma\right|>\frac{m}{q^{2}}\]
whenever $p$ and $q$ are integers with $q\geq 1$.

Exercise~\ref{Q;bounded entry} gives a more general
version of this idea. Exercise~\ref{A4.11}~(vii) suggests 
a better estimate for $m$.
\end{exercise}
\begin{exercise}\label{E;Carroll} 
In one of Lewis Carroll's favourite
puzzles an $8\times 8$ square is reassembled 
to form a $13\times 5$ rectangle as shown in Figure~\ref{puzzle}.
\begin{figure}[h]
\vspace{10cm}
\caption{Carroll's puzzle}\label{puzzle}
\end{figure}

What is the connection with Exercise~\ref{E;Lewis}?
Can you design the next puzzle in the sequence?
\end{exercise}

Hardy and Wright's 
\emph{An Introduction to the Theory of Numbers}~\cite{Hardy} contains
a chapter on approximation by rationals in which they
show, among other things, that $\sigma$ is indeed
particularly resistant to being so approximated by rationals.
If I was asked to nominate a book to be taken away
by some one leaving \emph{professional} mathematics,
but wishing to keep up an interest in the subject,
this book would be my first choice.  
\section{A nice, but starred, formula}
This section is non-examinable

The notion of a continued fraction can be extended
in many ways. 

We are used to the idea of approximating functions $f$
by polynomials $P$. Sometimes it may be more useful
to approximate $f$ by a rational function $P/Q$ where
$P$ and $Q$ are polynomials. If we approximate by
polynomials we are led to look at Taylor series.
If we approximate by
rational functions it might be worth 
looking at some generalisation of continued
fractions.

Here is a very pretty formula along these lines.
\[\tan x=\cfrac{x}
{1-\cfrac{x^{2}}
{3-\cfrac{x^{2}}
{5-\cfrac{x^{2}}
{7-\dots}}}}.\]
The following theorem of Lambert makes the statement precise.
\begin{theorem}\label{T;Lambert}
If we write
\[R_{n}(x)=\cfrac{x}
{1-\cfrac{x^{2}}
{3-\cfrac{x^{2}}
{\ddots-\cfrac{x^{2}}
{2n-3 -\cfrac{x^{2}}
{2n-1}}}}},\]
then $R_{n}(x)\rightarrow\tan x$
as $n\rightarrow\infty$ for all 
real $x$ with $|x|\leq 1$.
\end{theorem}
In order to attack this we start by generalising an earlier result
\begin{exercise}\label{E;generalise continued matrices}
Suppose that $a_{j}$  
and $b_{j}$ $[j=0,1,2,\dots]$ are chosen so that we never divide by zero
(for example all strictly positive).
Show that if
\[\begin{pmatrix}p_{n}&b_{n}p_{n-1}\\q_{n}&b_{n}q_{n-1}\end{pmatrix}
=\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&b_{1}\\1&0\end{pmatrix}
\dots
\begin{pmatrix}a_{n}&b_{n}\\1&0\end{pmatrix},
\]
then
\[\frac{p_{n}}{q_{n}}
=a_{0}+\cfrac{b_{0}}
{a_{1}+\cfrac{b_{1}}
{a_{2}+\cfrac{b_{2}}
{a_{3}+\cfrac{b_{3}}
{a_{4}+\cfrac{b_{4}}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{b_{n-1}}
{a_{n}}}}}}}}\]

Show that
\begin{align*}
p_{n}&=a_{n}p_{n-1}+b_{n-1}p_{n-2}\\
q_{n}&=a_{n}q_{n-1}+b_{n-1}q_{n-2}.
\end{align*}
\end{exercise}

We now use the following result which is clearly related
to the manipulations used in Lemma~\ref{L;onto pi}.
\begin{lemma}\label{L;more Lambert}
Let us write
\[S_{n}(x)=\frac{1}{2^{n}n!}\int_{0}^{x}(x^{2}-t^{2})^{n}\cos t\,dt.\]

Then $S_{n}(x)=q_{n}(x)\sin x-p_{n}(x)\cos x$
where $p_{n}$ and $q_{n}$ satisfy the recurrence relations
\begin{align*}
p_{n}(x)&=(2n-1)p_{n-1}(x)-x^{2}p_{n-2}(x),\\
q_{n}(x)&=(2n-1)q_{n-1}(x)-x^{2}q_{n-2}(x)
\end{align*}
for $n\geq 2$
and $p_{0}(x)=0$, $q_{0}(x)=1$, $p_{1}(x)=x$, $q_{1}(x)=1$. 
\end{lemma}

The results of this section and other interesting
topics are discussed in a book~\cite{Ball}
which is a model of how a high level
recreational mathematics text should be put together.
\section{Winding numbers} We all know that complex analysis
has a lot to say about `the number of times a curves
goes round a point'. In this final section we make the notion precise.
\begin{theorem}\label{T;track argument} Let 
\[{\mathbb T}=\{z\in{\mathbb C}\,:\,|z|=1\}.\]
If $g:[0,1]\rightarrow{\mathbb T}$ is continuous
with $g(0)=e^{i\theta_{0}}$, then there is a unique
continuous function $\theta:[0,1]\rightarrow{\mathbb R}$
with $\theta(0)=\theta_{0}$
such that $g(t)=e^{i\theta(t)}$ for all $t\in[0,1]$.
\end{theorem}

The uniqueness part of Theorem~\ref{T;track argument}
follows from the next exercise.
\begin{exercise}\label{E;start argument} 
Suppose $\psi,\,\phi:[0,1]\rightarrow{\mathbb R}$
are continuous with $e^{i\psi(t)}=e^{i\phi(t)}$ for all
$t\in[0,1]$. Show that there exists an integer $n$
such that $\psi(t)=\phi(t)+2n\pi$ for all
$t\in[0,1]$.
\end{exercise}
\begin{corollary}\label{C;unwind}
If $\gamma:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$ is continuous
with $\gamma(0)=|\gamma(0)|e^{i\theta_{0}}$, 
then there is a unique
continuous function $\theta:[0,1]\rightarrow{\mathbb R}$
with $\theta(0)=\theta_{0}$
such that $\gamma(t)=|\gamma(t)|e^{i\theta(t)}$.
\end{corollary}

\begin{definition}\label{D;winding}\index{winding number}
If $\gamma:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$
and  $\theta:[0,1]\rightarrow{\mathbb R}$ are continuous
with $\gamma(t)=|\gamma(t)|e^{i\theta(t)}$, then we define
\[w(\gamma,0)=\frac{\theta(1)-\theta(0)}{2\pi}.\]
\end{definition}
Exercise~\ref{E;start argument} shows that  $w(\gamma,0)$
does not depend on the choice of $\theta$.
\begin{exercise}\label{E;closed integer} (i)
If $\gamma:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$
is continuous and $\gamma(0)=\gamma(1)$ (that is to say,
the path is \emph{closed}) show that $w(\gamma,0)$ is an integer.

(ii) Give an example to show that, under the conditions of~(i),
$w(\gamma,0)$ can take any integer value.
\end{exercise}
We are only interested in the winding number of \emph{closed}
curves.

If $a\in{\mathbb C}$, it is natural to define the winding number
round $a$ of a curve given by a continuous map
\[\gamma:[0,1]\rightarrow{\mathbb C}\setminus\{a\}\]
to be
\[w(\gamma,a)=w(\gamma-a,0),\]
but we shall not use this slight extension.

\begin{lemma}\label{L;dogmatic} If
$\gamma_{1},\,\gamma_{2}:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$
then the product $\gamma_{1}\gamma_{2}$ satisfies
\[w(\gamma_{1}\gamma_{2},0)=w(\gamma_{1},0)+w(\gamma_{2},0).\]
\end{lemma}
\begin{lemma} {\bf[Dog walking lemma]}\label{L;dog walk} 
If\index{dog walking lemma}
$\gamma_{1},\,\gamma_{2}:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$
are continuous, $\gamma_{1}(0)=\gamma_{1}(1)$,
$\gamma_{2}(0)=\gamma_{2}(1)$ and
\[|\gamma_{2}(t)|<|\gamma_{1}(t)|\]
for all $t\in[0,1]$, then $\gamma_{1}+\gamma_{2}$
never takes the value $0$ and $w(\gamma_{1}+\gamma_{2},0)=w(\gamma_{1},0)$.
\end{lemma}

Many interesting results in `applied complex analysis'
are obtained by `deforming contours'. The idea of
`continuously deforming curves' 
can be made precise in a rather clever manner.
\begin{definition}\label{D;homotopy}\index{homotopy}
Suppose that $\gamma_{0}$, $\gamma_{1}$ are closed paths
not passing through $0$
(so we have, $\gamma_{j}:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$).
Then we say that $\gamma_{0}$ is \emph{homotopic} to $\gamma_{1}$
by closed curves not passing through zero if
we can find a continuous function
$\Gamma:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
such that
\begin{alignat*}{2}
\Gamma(s,0)&=\Gamma(s,1)&&\qquad\text{for all $s\in[0,1]$},\\
\Gamma(0,t)&=\gamma_{0}(t)&&\qquad\text{for all $t\in[0,1]$},\\
\Gamma(1,t)&=\gamma_{1}(t)&&\qquad\text{for all $t\in[0,1]$}.
\end{alignat*}
\end{definition}
We often write $\gamma_{s}(t)=\Gamma(s,t)$.
\begin{exercise}\label{E;homotopy equivalence} 
If $\gamma_{0}$ and $\gamma_{1}$
satisfy the conditions of Definition~\ref{D;homotopy},
we write $\gamma_{0}\simeq\gamma_{1}$. Show that $\simeq$
is an equivalence relation on  closed curves not passing through zero.
\end{exercise}

The proof of the next theorem illustrates
the utility of Definition~\ref{D;homotopy}.
The proof itself is sometimes referred to
as `dog walking along a canal'.
\begin{theorem}\label{T;canal} If $\gamma_{0}$ and $\gamma_{1}$
satisfy the conditions of Definition~\ref{D;homotopy},
then $w(\gamma_{0},0)=w(\gamma_{1},0)$.
\end{theorem}

As before, let us write
\begin{gather*}
{\bar D}=\{z\in{\mathbb C}\,:\,|z|\leq 1\},\\
D=\{z\in{\mathbb C}\,:\,|z|<1\},\\
\partial D=\{z\in{\mathbb C}\,:\,|z|= 1\}.
\end{gather*}
\begin{corollary}\label{C;dizy dog} Suppose 
$f:{\bar D}\rightarrow{\mathbb C}$
is continuous, $f(z)\neq 0$ for $z\in\partial D$,
and we define $\gamma:[0,1]\rightarrow{\mathbb C}$
by
\[\gamma(t)=f(e^{2\pi it})\]
for all $t\in[0,1]$. If $w(\gamma,0)\neq 0$, then
there
must exist a $z\in D$ with $f(z)=0$.
\end{corollary}

This gives us another proof of the Fundamental Theorem of Algebra
(Theorem~\ref{T;Fundamental Algebra})\index{fundamental theorem of algebra}.
\begin{corollary}\label{C;money}
If we work
in the complex numbers, every non-trivial polynomial has a root.
\end{corollary}

We also obtain a second proof of Brouwer's theorem
in two dimensions in the `no retraction' form 
of Theorem~\ref{T;Brouwer retracts}.)
\begin{corollary}\label{C;second Brouwer}
There does not exist a continuous function 
$f:{\bar D}\rightarrow\partial D$
with $f(z)=z$ for all $z\in \partial D$.
\end{corollary}

The earlier combinatorial 
proof that we gave requires less technology to extend
to higher dimensions.


The contents of this section show that parts of complex analysis
are really just special cases of general `topological theorems'.
On the other hand, other parts (such as Taylor's theorem
and Cauchy's theorem itself) depend crucially on the
the fact that we are dealing with the very restricted class
of functions which satisfy the Cauchy-Riemann equations.

In traditional courses on complex analysis, this fact appears,
if it appears at all, rather late in the day. Beardon's
\emph{Complex Analysis}~\cite{Beardon} shows that
it is possible to do things differently and is well worth
a look\footnote{Though, like other good texts, it will not please
those `who want from books, plain cooking made still plainer
by plain cooks.'}.
\begin{thebibliography}{9}
\bibitem{Adams} C. Adams, \emph{Zombies and Calculus}, 
Princeton University Press, 2014. (I have not read this,
but according to one reviewer,
the book
`shows how calculus can be used to understand 
many different real-world phenomena.')
\bibitem{Baker} A. Baker, \emph{Transcendental number theory},
CUP, 1975.
\bibitem{Ball} K. Ball, 
\emph{Strange Curves,  Counting Rabbits
and Other Mathematical Explorations}, 
Princeton University Press, 2003.
\bibitem{Beardon} A. F. Beardon \emph{Complex Analysis},
Wiley, 1979.
\bibitem{Hardy} G.~H.~Hardy and E.~M.~Wright
\emph{An Introduction to the Theory of Numbers}
OUP, 1937.
\bibitem{Thomas} L.~C.~Thomas \emph{Games, Theory and Applications},
Dover reprint of a book first published by Wiley in 1984.
\end{thebibliography}

\newpage
\section{Question sheet 1}\label{S;sheet one}
\noindent{\bf Note} The Pro-Vice-Chancellor for Education has
determined that the amount of work required by a student to
understand a course should be the same as that required by
any other student. Traditionally, teachers and students in the Faculty
of Mathematics have interpreted this as meaning that each example 
sheet should have exactly twelve questions. The number of questions in the 
example sheets for this course may be reduced to twelve by
omitting any marked with a $\bigstar$.


\begin{question}\label{Q;some metrics}\label{A1.1}
(i) Consider ${\mathbb R}^{n}$.
If we take $d$ to be ordinary Euclidean distance
\[d({\mathbf x},{\mathbf y})=\|{\mathbf x}-{\mathbf y}\|=
\left(\sum_{j=1}^{n}|x_{j}-y_{j}|^{2}\right)^{1/2},\]
show that $({\mathbb R}^{n},d)$ is a metric space.

\noindent[Hint: Use inner products.]

(ii) Consider ${\mathbb C}$. If we take
$d(z,w)=|z-w|$, show that $({\mathbb C},d)$ is a metric space.

(iii) Let $X$ be a non-empty set. Check that, if we write
\[d(x,y)=
\begin{cases}
0&\text{if $x=y$},\\
1&\text{if $x\neq y$},
\end{cases}
\]
then $(X,d)$ is a metric space ($d$ is called the discrete metric).

(iv) Consider $X=\{0,1\}^{n}$. If we take
\[d({\mathbf x},{\mathbf y})=\sum_{j=1}^{n}|x_{j}-y_{j}|,\]
show that $(X,d)$ is a metric space.
\end{question}
\begin{question}\label{A1.2}
(i) Give an example of a continuous bijection 
$f:{\mathbb R}\rightarrow{\mathbb R}$ with no fixed points.

(ii) If $A$ is an infinite countable set, show that
there exists a bijection $f:A\rightarrow A$
with no fixed points. What can you say if $A$ is finite non-empty set?
(Be careful to cover all possible cases.)

$[$Remark: We can replace `infinite countable' by `infinite'
provided we accept the appropriate set theoretic axioms.$]$  
\end{question}
\begin{question}\label{A1.3} (i) Show that a subset $E$ of ${\mathbb R}^{m}$
(with the usual metric) is compact if
every continuous function  $f:E\rightarrow{\mathbb R}$
is bounded.

(ii) Show that a subset $E$ of ${\mathbb R}^{m}$
(with the usual metric) is compact if
every bounded continuous function  $f:E\rightarrow{\mathbb R}$
attains its bounds.
\end{question}
\begin{question}\label{A1.4}
Suppose that $d$ is the usual metric on ${\mathbb R}^{m}$,
$X$ is a compact set in ${\mathbb R}^{m}$
and $f:X\rightarrow X$ is a continuous
\emph{distance increasing} map. In other words,
\[d(f(x),f(y))\geq d(x,y)\]
for all $x,\,y\in X$. The object of the first two parts
of this question
is to show that $f$ must be a surjection. 
                                                                          
(i) Let $f^{0}(x)=x$
$f^{n}(x)=f(f^{n-1}(x))$. Explain why 
$X_{\infty}=\bigcap_{n=0}^{\infty}f^{n}(X)$ 
is compact and why the map $g:X_{\infty}\rightarrow X_{\infty}$ 
is well defined by $f\big(g(y)\big)=y$. 
                                                                          
(ii) If $z\in X$, consider the sequence $f^{n}(z)$.
By using compactness
and part~(i) show that given $\epsilon>0$
we can find an $w\in X_{\infty}$ such that $d(w,z)<\epsilon$. 
Deduce that $f$ is surjective.

(iii) Let $X=\{x\in{\mathbb R}\,:\,x\geq 0\}$. 
Find a continuous function $f:X\rightarrow X$
such that $|f(x)-f(y)|\geq 2|x-y|$ for all $x,\,y\in X$
but $f(X)\neq X$. Why does this not contradict (ii)?

(iv) We work in ${\mathbb C}$.
Let $\alpha$ be irrational and let $\omega=\exp(2\pi\alpha i)$.
If 
\[X=\{\omega^{n}\,:\,n\geq 1\},\]
find a continuous function $f:X\rightarrow X$
such that $|f(w)-f(z)|=|w-z|$ for all $w,\,z\in X$
but $f(X)\neq X$.  Why does this not contradict (ii)?
\end{question}
\begin{question}\label{A1.5} A function $f:{\mathbb R}^{n}
\rightarrow{\mathbb R}$ is called \emph{upper semi-continuous}
if, given ${\mathbf x}\in {\mathbb R}^{n}$ and $\epsilon>0$,
we can find a $\delta>0$ such that
\[\|{\mathbf x}-{\mathbf y}\|<\delta
\Rightarrow f({\mathbf y})\leq f({\mathbf x})+\epsilon.\]

(i) If $E$ is a subset of ${\mathbb R}^{n}$ and
we define the indicator function ${\mathbb I}_{E}$
by
\[{\mathbb I}_{E}({\mathbf x})=
\begin{cases}1&\text{if ${\mathbf x}\in E$,}\\
0&\text{otherwise,}
\end{cases}
\]
show that ${\mathbb I}_{E}$ is  upper semi-continuous
if and only if $E$ is closed.

(ii) State and prove necessary and sufficient conditions
for  $-{\mathbb I}_{E}$ to be  upper semi-continuous.

(iii) If $f:{\mathbb R}^{n}
\rightarrow{\mathbb R}$ is upper semi-continuous
and $K$ is compact show that there exists a ${\mathbf z}\in K$
such that $f({\mathbf z})\geq f({\mathbf k})$
for all ${\mathbf k}\in K$. (In other words $f$ attains a
maximum on $K$.)

(iv) If $g:{\mathbb R}\rightarrow{\mathbb R}$ is defined by 
\[g(x)=
\begin{cases}-1/|x|&\text{if $x\neq 0$,}\\
0&\text{if $x=0$,}
\end{cases}
\]
show that $g$ is upper semi-continuous but
that $g$ is unbounded on $[-1,1]$.
\end{question}
\begin{question}\label{A1.6} Let
\begin{align*}
{\mathbb H}&=\{z\in{\mathbb C}\,:\,\Re z>0\},\\
\bar{\mathbb H}&=\{z\in{\mathbb C}\,:\,\Re z\geq 0\},\\
{\mathbb D}&=\{z\in{\mathbb C}\,:\,|z|<1\},\\
\bar{\mathbb D}&=\{z\in{\mathbb C}\,:\, |z|\leq 1\}.
\end{align*}

(i) Does every bijective continuous map $f:{\mathbb C}\rightarrow{\mathbb C}$
have a fixed point?

(ii) Does every bijective continuous map $f:{\mathbb H}\rightarrow{\mathbb H}$
have a fixed point?

(iii) Does every bijective continuous map 
$f:\bar{\mathbb H}\rightarrow\bar{\mathbb H}$
have a fixed point?

(iv) Does every bijective continuous map $f:{\mathbb D}\rightarrow{\mathbb D}$
have a fixed point?

(v) Does every bijective continuous map 
$f:\bar{\mathbb D}\rightarrow\bar{\mathbb D}$
have a fixed point?

Give reasons for your answers.
\end{question}
\begin{question}(Exercise~\ref{E;two Brouwer})\label{A1.7}
Show that the following four statements are equivalent.

(i) If $f:[0,1]\rightarrow [0,1]$ is continuous, then we can find
a $w\in[0,1]$ such that $f(w)=w$.

(ii) There does not exist a continuous function $g:[0,1]\rightarrow\{0,1\}$
with $g(0)=0$ and $g(1)=1$.
(In topology courses we say that $[0,1]$ is connected.)

(iii) If $A$ and $B$ are closed subsets of $[0,1]$ with
$0\in A$, $1\in B$ and $A\cup B=[0,1]$
then $A\cap B\neq\emptyset$.

(iv)  If $h:[0,1]\rightarrow {\mathbb R}$ is continuous
and $h(0)\leq c\leq h(1)$, then we can find
a $y\in[0,1]$ such that $h(y)=c$.
\end{question} 
\begin{question}(Exercise~\ref{E;two Sperner})\label{A1.8} 
Suppose 
that we colour the points $r/n$
red or blue $[r=0,\,1,\,\dots,\,n]$ with $0$ red
and $1$ blue. Show that there are a pair of neighbouring points 
$u/n$, $(u+1)/n$ of different colours. Use this result
to prove statement~(iii) of Exercise~\ref{E;two Brouwer}.
\end{question}
\begin{question}\label{Q;surjection}\label{A1.9}
Suppose that $g:{\mathbb R}^{2}\rightarrow{\mathbb R}^{2}$
is a continuous function such that there exists a $K>0$ with
$\|g({\mathbf x})-{\mathbf x}\|\leq K$ for all
${\mathbf x}\in{\mathbb R}^{2}$.

(i) By constructing a function $f:{\mathbb R}^{2}\rightarrow{\mathbb R}^{2}$,
taking a disc into itself, and such that
\[f({\mathbf t})={\mathbf t}\Rightarrow g({\mathbf t})={\boldsymbol 0}\] 
show that ${\boldsymbol 0}$ lies in the image of $g$.

(ii) Show that, in fact, $g$ is surjective.

(iii) Is  it necessarily true that $g$ has a fixed point? Give reasons.

(iv) Is $g$ necessarily injective? Give reasons.
\end{question}
\begin{question}\label{A1.10} 
Use the Brouwer fixed point theorem to show that there
is a complex number $z$ with $|z|\leq 1$ and
\[z^{4}-z^{3}+8z^{2}+11z+1=0.\]
\end{question}
\begin{question}\label{Q;Brouwer intersection}\label{A1.11}
Consider the square $S=[-1,1]^{2}$. Suppose
that $\beta,\,\gamma:[-1,1]\rightarrow S$ are continuous
with $\beta(-1)=(-1,-1)$,  $\beta(1)=(1,1)$,
$\gamma(-1)=(-1,1)$,  $\gamma(1)=(1,-1)$.
The object of this question is to show that
there exist $(s_{0},t_{0})\in [-1,1]^{2}$
such that $\beta(s_{0})=\gamma(t_{0})$.
(Note that this is just a formal version
of Exercise~\ref{E;informal intersection}.)

Our proof will be by contradiction, so assume that no
such $(s_{0},t_{0})$ exists. We write
\[\beta(s)=\big(\beta_{1}(s),\beta_{2}(s)\big),
\ \gamma(t)=\big(\gamma_{1}(t),\gamma_{2}(t)\big)\]

(i) Show carefully that the function $F:S\rightarrow S$
given by
\[F(s,t)=\frac{-1}{\max\{|\beta_{1}(s)-\gamma_{1}(t)|,
|\beta_{2}(s)-\gamma_{2}(t)|\}}
\big(\beta_{1}(s)-\gamma_{1}(t),\beta_{2}(s)-\gamma_{2}(t)\big)\]
is well defined and continuous. 

(ii) Show by considering
the possible values of the fixed points of $F$ or otherwise
that $F$ has no fixed points, Brouwer's fixed point theorem now  gives a
contradiction.  
\end{question}
\begin{question}\label{A1.12} 
Here is a variation on Lemma~\ref{L;colour me}~(ii).
It can be proved in the same way.

Suppose that $T$, $I$, $J$, $K$ are as in Lemma~\ref{L;colour me}
and that $A$, $B$ and $C$ are closed subsets of $T$
with
\begin{gather*}A\cup B\cup C=T,\\ 
A\cup B\supseteq I,\ B\cup C\supseteq J,
\ C\cup A\supseteq K,\\
A\supseteq K\cap I,\ B\supseteq I\cap J,\ C\supseteq J\cap K. 
\end{gather*}
Show that $A\cap B\cap C\neq\emptyset$.
\end{question}
\begin{question}\label{Q;Schwarz}$\bigstar$\label{A1.13} 
Cantor started the researches which led him to
his studies of infinite sets by looking at work of Riemann on
trigonometric series. He needed to show that if
$F:[a,b]\rightarrow{\mathbb R}$ is continuous and
\[\frac{F(x+h)-2F(x)+F(x-h)}{h^{2}}\rightarrow 0\]
as $h\rightarrow 0$ for all $x\in (a,b)$ then $F$ is linear.
(Note that there are no differentiability conditions on $F$.)
Schwarz was able to supply a proof.

(i) Suppose that $F:[a,b]\rightarrow{\mathbb R}$ is continuous,
$F(a)=F(b)$ and there exists an $\epsilon>0$ such that
\[\limsup_{h\rightarrow 0}\frac{F(x+h)-2F(x)+F(x-h)}{h^{2}}\geq \epsilon\]
for all $x\in (a,b)$. Show that $F$ cannot attain a maximum at
any $x\in(a,b)$. Deduce that
\[F(x)\leq F(a)\]
for all $x\in [a,b]$.

(ii) Suppose that $F:[a,b]\rightarrow{\mathbb R}$ is continuous,
$F(a)=F(b)$ and
\[\limsup_{h\rightarrow 0}\frac{F(x+h)-2F(x)+F(x-h)}{h^{2}}\geq 0\]
for all $x\in (a,b)$. Let $c=(a+b)/2$.
By considering $G(x)=F(x)+\epsilon (x-c)^{2}/4$ or otherwise,
show that
\[F(x)\leq F(a)\]
for all $x\in [a,b]$.  

(iii) Suppose that $F:[a,b]\rightarrow{\mathbb R}$ is continuous,
$F(a)=F(b)$ and
\[\lim_{h\rightarrow 0}\frac{F(x+h)-2F(x)+F(x-h)}{h^{2}}=0\]
for all $x\in (a,b)$. By considering $F$ and $-F$ show
that
\[F(x)=F(a)\]
for all $x\in [a,b]$. 

(iv)  Show that if
$F:[a,b]\rightarrow{\mathbb R}$ is continuous and
\[\frac{F(x+h)-2F(x)+F(x-h)}{h^{2}}\rightarrow 0\]
as $h\rightarrow 0$ for all $x\in (a,b)$ then $F$ is linear.
\end{question}
\begin{question}$\bigstar$\label{A1.14}
As usual $\bar{D}$ is the closed unit disc in ${\mathbb R}^{2}$
and $\partial D$ its boundary. Let us write
\[\Delta=\{({\mathbf x},{\mathbf y})\in\bar{D}^{2}\,:\,
{\mathbf x}\neq{\mathbf y}\}\]
and consider $\Delta$ as a subset of ${\mathbb R}^{4}$ with the
usual metric.
We define $F:\Delta\rightarrow\partial D$ as follows.

Given $({\mathbf x},{\mathbf y})\in\Gamma$, take the line
from  ${\mathbf x}$ to ${\mathbf y}$ and extend it
(in the ${\mathbf x}$ to ${\mathbf y}$ direction) until it first
hits the boundary at ${\mathbf z}$. We write 
$F({\mathbf x},{\mathbf y})={\mathbf z}$.

In the proof of Theorem~\ref{T;Brouwer retracts} 
I claimed that it was obvious that $F$ was continuous. 
Suppose, if possible, that $g:\bar{D}\rightarrow\bar{D}$ is a continuous
map with $g({\mathbf x})\neq{\mathbf x}$ for all ${\mathbf x}\in\bar{D}$.
Explain why, if my claim is true, the map
\[{\mathbf x}\mapsto F\big({\mathbf x},g({\mathbf x})\big)\]
is a continuous map.   

The claimed result is obvious (in some sense) and you may take
it as obvious in the exam. However, if we can not prove the
obvious it ceases to be obvious. This question 
outlines one method of proof, but, frankly, the
reader may find it easier to find their own method.
Any correct method counts as a solution.

(i) Suppose that $0<y_{0}<1$, $x_{0}>0$ and $x_{0}^{2}+y_{0}^{2}=1$. 
Show that, given $\epsilon>0$
we can find an $\eta>0$ such that if $x^{2}+y^{2}=1$,
$x>0$ and $|y-y_{0}|<\eta$ implies $\|(x,y)-(x_{0},y_{0})\|<\epsilon$.

(ii)  Suppose that $(x_{1},y_{0}),(x_{2},y_{0})\in{\bar D}$,
$y_{0}\geq 0$ and
$x_{1}\neq x_{2}$. By using~(i), or otherwise, show
that, given any $\epsilon>0$, we can find a $\delta>0$
such that, whenever
\[\|(x_{1}',y_{1}')-(x_{1},y)\|,\,\|(x_{2}',y_{2}')-(x_{2},y)\|<\delta\]
and $(x_{1}',y_{1}'),\,(x_{2}',y_{2}')\in\bar{D}$, we have
$(x_{1}',y_{1}')\neq (x_{2}',y_{2}')$ and
\[F\big((x_{1}',y_{1}'),(x_{2}',y_{2}')\big)=(u,v)
\ \text{with}\ |v-y|<\epsilon.\]

(iii) Hence show that $F:\Delta\rightarrow\bar{D}$ is continuous.
\end{question}
\clearpage
\section{Question sheet 2}
\begin{question}\label{A2.1} 
  In the two player game of Hawks and Doves\footnote{This
    has nothing to do with the question but I cannot resist
    passing on the information that TfL employs
    hawks to clear its larger stations of pigeons.
    The hawks actually catch pigeons, but
    are not allowed to eat them, because
    London pigeons have too many diseases.},
player~$i$ chooses a probability $p_{i}$ which
announce publicly. Players may change their mind
before the game begins but must stick to their last
announced decision.

Once the game begins, player~$i$ becomes a hawk with probability
$p_{i}$ and a dove with probability $1-p_{i}$. Two doves
divide food so that each gets $V/2$. A hawk scares
off a dove so the hawk gets $V$ and the dove $0$.
Two hawks fight, the winner gets $V-D$ and the looser
$-D$ ($D$ is the damage). The probability of winning such
an encounter is $1/2$ for each bird.

If $V>2D$ show that there is only one Nash equilibrium point.
Give a simple explanation of this fact.

If $V<2D$ show that there are three equilibrium points
and identify them.

What happens if $V=2D$?
\end{question}
\begin{question}\label{A2.2} 
(i) Suppose that $E$ is a compact convex set
in ${\mathbb R}^{n}$, that 
$\alpha:{\mathbb R}^{n}\rightarrow {\mathbb R}^{m}$ is linear
and ${\mathbf b}\in{\mathbb R}^{m}$. Show that
\[\{{\mathbf b}+\alpha{\mathbf x}\,:\,{\mathbf x}\in E\}\]
is compact and convex.

(ii) Suppose that $E$ is a compact convex set
in ${\mathbb R}^{n}$, that 
$f:{\mathbb R}^{n}\rightarrow {\mathbb R}^{m}$ is continuous
and ${\mathbf b}\in{\mathbb R}^{m}$. Set
\[E'=\{{\mathbf b}+f({\mathbf x})\,:\,{\mathbf x}\in E\}\]

\ (a) Is $E'$ necessarily convex if $n=1$?  

\ (b) Is $E'$ necessarily convex if $m=1$?

\ (c) $E'$ necessarily convex for general $m$ and $n$?

Give reasons.
\end{question}
\begin{question}\label{A2.3}
(If you have done the 1B optimisation course.)
We use the notation of Theorem~\ref{T;Nash stable}.
Suppose that $a_{ij}=-b_{ij}$, that is to say that
Albert's gain is Bertha's loss.
Explain why the 1B
game theoretic solution will always be a Nash equilibrium
point and vice versa.
\end{question}
\begin{question}\label{A2.4}(This is Exercise~\ref{E;Advertising})
Consider
two rival firms $A$ and $B$ engaged in an advertising war.
So long as the war continues, the additional costs
of advertising mean that the larger firm $A$ loses $3$ million
pounds a year and the smaller firm $B$ loses $1$ million pounds a year.
If they can agree to cease hostilities then $A$ will make
$8$ million a year and $B$ will make $1$ million a year.
How much does Nash say 
should $A$ pay $B$ per year to achieve this end/

$[$One way of doing this is to apply an affine transformation.$]$
\end{question}
\begin{question}\label{Q;unit ball}\label{A2.5} 
Consider the continuous functions on $[0,1]$ with the
uniform norm.
Show that the unit ball
\[\{f\in C([0,1])\,:\,\|f\|_{\infty}\leq 1\}\]
is a closed bounded subset of the complete space 
$(C([0,1]),\|\ \|_{\infty})$,
but is not compact.
\end{question}

\begin{question}\label{A2.6} 
(i) Let  $f:[0,1]\rightarrow{\mathbb R}$
be a continuous function which is not a polynomial.
If $p_{n}$ is a polynomial of degree $d_{n}$
and $p_{n}\rightarrow f$ uniformly on $[0,1]$, show
that $d_{n}\rightarrow \infty$.

$[$Hint. Look at Corollary~\ref{C;naught for naught}.$]$

(ii) If $q_{n}$ is a polynomials of degree $e_{n}$
with $e_{n}\rightarrow\infty$
and $q_{n}\rightarrow g$ uniformly on $[0,1]$,
does it follow that $g$ is not a polynomial?
Give reasons.
\end{question}
\begin{question}\label{A2.7}
Show that no formula of the form
\[\int_{-1}^{1}f(t)\,dt=\sum_{j=1}^{n}A_{j}f(x_{j})\]
(with $x_{j}, A_{j}\in{\mathbb R}$) can hold
for polynomials $f$ of degree at most $2n$.
\end{question}
\begin{question}\label{A2.8} Let $f:[0,1]\rightarrow{\mathbb R}$
and $g:[-1,1]\rightarrow{\mathbb R}$ be continuous.

(i) By using the Weierstrass approximation theorem,
show that
\[\int_{0}^{1}x^{n}f(x)\,dx=0\ \text{for all $n\geq 0$}
\Rightarrow f\ \text{is the zero function}.\]

(ii) Show that
\[\int_{0}^{1}x^{2n}f(x)\,dx=0\ \text{for all $n\geq 0$}
\Rightarrow f\ \text{is the zero function}.\] 

(iii) Is it true that if $\int_{0}^{1}x^{2n+1}f(x)\,dx=0$ 
for all $n\geq 0$, then $f$ must be the zero-function?
Give reasons.

(iv) Is it true that, if $\int_{-1}^{1}x^{2n}g(x)\,dx$=0 
for all $n\geq 0$, then $g$ must be the zero-function?
Give reasons.
\end{question}
\begin{question}\label{A2.9} 
(i) (This just to remind you that 
discontinuous functions come in many shapes and sizes.)
Let $f:{\mathbb R}\rightarrow{\mathbb R}$
be given by $f(x)=\sin 1/x$ for $x\neq 0$ and $f(0)=a$. Show that,
whatever the choice of $a$, $f$ is discontinuous.

(ii) Does there exist a discontinuous function
$g:[0,1]\rightarrow{\mathbb R}$ which can be
approximated uniformly by polynomials? Why?

(iii) Does there exist a smooth function
$h:{\mathbb R}\rightarrow{\mathbb R}$ which cannot be
approximated uniformly by polynomials? Prove
your answer.

(iv) If $f:{\mathbb R}\rightarrow{\mathbb R}$
is continuous, does  there always exist a sequence of polynomials $p_{n}$
with $p_{n}(x)\rightarrow f(x)$ for each $x$ as $n\rightarrow\infty$.
\end{question}
\begin{question}\label{A2.10} 
We say that a function
$f:{\mathbb R}\rightarrow{\mathbb R}$
has the intermediate value property if whenever $a,b\in{\mathbb R}$
and $f(a)\geq c\geq f(b)$ we can find a $t$ in the closed
interval with end points $a$ and $b$ such that $f(t)=c$.

(i) Give an example of a function satisfying the intermediate value
property which is not continuous.

(ii) Show that if $f$ has the intermediate value property 
and in addition $f^{-1}(\alpha)$ is closed for every $\alpha$ in a dense
subset of of ${\mathbb R}$ then $f$ is continuous.
\end{question}
\begin{question}$\bigstar$\label{A2.11} 
Are the following statements true or false?
Give reasons.

(i) If $f:(0,1)\rightarrow{\mathbb R}$ is continuous,
we can find a sequence of polynomials $P_{n}$ converging
uniformly to $f$ on every compact subset of $(0,1)$.

(ii) If $g:(0,1)\rightarrow{\mathbb R}$ is continuously differentiable
we can find a sequence of polynomials $Q_{n}$ with $Q'_{n}$
converging uniformly to $g'$ and $Q_{n}$
converging uniformly to $g$
on every compact subset of $(0,1)$.

(iii) If $h:(0,1)\rightarrow{\mathbb R}$ is continuous
and bounded we can find a sequence of polynomials $R_{n}$
with 
\[\sup_{t\in (0,1)}|R_{n}(t)|\leq  \sup_{t\in (0,1)}|h(t)|\]
converging
uniformly to $h$ on every compact subset of $(0,1)$.

\end{question} 
\begin{question}$\bigstar$\label{A2.12} Compute
the Chebychev polynomials $T_{n}$ of the first kind
for $n=0,\,1,\,2\,\dots,\,4$
and the Chebychev polynomials $U_{n-1}$ of the second
kind for $n=1,\,2\,\dots,\,4$.

Recall that 
we say that a function $f;[-1,1]\rightarrow{\mathbb R}$
is \emph{even} if $f(x)=f(-x)$ for all $x$ and 
\emph{odd} if $f(x)=-f(-x)$ for all $x$.

Explain why we know, without calculation,
that the Chebychev polynomials $T_{n}$
are even when $n$ is even and odd when $n$ is odd.
What can you say about the Chebychev polynomials $U_{n}$
of the second kind?
\end{question}
\begin{question}\label{A2.13}
The Chebychev polynomials are orthogonal
with respect to a certain non-zero positive weight function $w$.
In other words,
\[\int_{-1}^{1}T_{m}(x)T_{n}(x)w(x)\,dx=0\]
for all $m\neq n$. Use a change of variables
to find a suitable $w$.
\end{question}
\begin{question}\label{E;compute Legendre}$\bigstar$\label{A2.14}
(i) Use the Gramm--Schmidt method
(see Lemma~\ref{L;Gramm}) to compute the Legendre
polynomials $p_{n}$ for $n=0,\,1,\,2,\,3,\,4$.
You may leave your answers in the form $A_{n}p_{n}$
(i.e. ignore normalisation).

(ii) Explain why we know, without calculation,
that the Legendre polynomials $p_{n}$
are even when $n$ is even and odd when $n$ is odd.

(iii) Explain why
\[\frac{d^{m}\ }{dx^{m}}(1-x)^{n}(1+x)^{n}\]
vanishes when $x=1$ or $x=-1$ whenever $m<n$.

Suppose that
\[P_{n}(x)=\frac{d^{n}\ }{dx^{n}}(1-x^{2})^{n}.\]
Use integration by parts to show that
\[\int_{-1}^{1}P_{n}(x)P_{m}(x)\,dx=0\]
for $m\neq n$. Conclude
that the $P_{n}$ are scalar multiple of the
Legendre polynomials $p_{n}$. 
 
(iv) Compute $P_{n}$ for $n=0,\,1,\,2,\,3,\,4$
and check that these verify the last sentence
of (iii). 

(iv) Let $u_{n}(x)=x^{n}$. Find the choice of $v$
which minimises
\[\|u_{n}-v\|_{2}=
\left(\int_{-1}^{1}|x^{n}-v(x)|^{2}\,dx\right)^{1/2}\]
for $v$ a polynomial of degree at most $n-1$
\end{question}
\begin{question}\label{A2.15} 
Are the following statements true or false.
Give reasons. 

(i) For all $n\geq 1$, there exists a polynomial $P_{n}$
of degree at most $n$ such that
\[P_{n}(\cosh t)=\cosh nt.\]

(ii) For all $n\geq 1$ there exists a polynomial $Q_{n}$
of degree at most $n$ such that
\[Q_{n}(\cosh t)=\sinh nt.\]

(iii) For all $n\geq 1$ there exists a polynomial $R_{n}$
of degree at most $n$ such that
\[R_{n}(\sin t)=\sin nt.\]
\end{question}
\begin{question}$\bigstar$\label{A2.16}
(i) Suppose $f:[a,b]\rightarrow{\mathbb R}$
is continuous and $\epsilon>0$. Why can we find
an infinitely differentiable function $g:[a,b]\rightarrow{\mathbb R}$
such that $\|f-g\|_{\infty}<\epsilon$.


(ii) By using Chebychev polynomials
and Weierstrass's approximation theorem, show that
given any continuous $f:[0,\pi]\rightarrow{\mathbb R}$
and any $\epsilon>0$
we can find $N$ and $a_{j}\in{\mathbb R}$ $0\leq j\leq N$
such that
\[\left|f(s)-\sum_{j=0}^{N}a_{j}\cos js\right|<\epsilon\]
for all $s\in[0,\pi]$.

(iii) Let $\epsilon>0$. If $f:[0,\pi]\rightarrow{\mathbb R}$
is continuous with $f(0)=0$, show that
we can find $N$ and $b_{j}\in{\mathbb R}$ $0\leq j\leq N$
such that
\[\left|f(s)-b_{0}s-\sum_{j=0}^{N}b_{j}\sin js\right|<\epsilon\]
for all $s\in[0,\pi]$.

(iv) Let $\epsilon>0$. If $f:[0,\pi]\rightarrow{\mathbb R}$
is continuous with $f(0)=f(\pi)=0$, show that
we can find $N$ and $b_{j}\in{\mathbb R}$, $0\leq j\leq N$
such that
\[\left|f(s)-\sum_{j=0}^{N}b_{j}\sin js\right|<\epsilon\]
for all $s\in[0,\pi]$.

(v) Hence show that,
given any continuous $f:[-\pi,\pi]\rightarrow{\mathbb R}$
with $f(-\pi)=f(\pi)$
and any $\epsilon>0$,
we can find $N$ and $\alpha_{j},\beta_{j}\in{\mathbb R}$
such that
\[\left|f(t)-\sum_{j=0}^{N}b_{j}\cos jt
-\sum_{j=1}^{N}c_{j}\sin jt\right|<\epsilon\]
for all $t\in[-\pi,\pi]$.
\end{question} 
\clearpage
\section{Question Sheet 3}
\begin{question}\label{A3.1} Let $f:[-1,1]\rightarrow{\mathbb R}$ be
a function and let $M>0$. Show that there
exists at most one polynomial of degree $n$ such
that
\[|f(x)-P(x)|\leq M|x|^{n+1}\]
for all $x\in [-1,1]$.

Must there always exist such a $P$ if $f$ is everywhere infinitely
differentiable and we choose $M$ sufficiently large?
\end{question} 
\begin{question}\label{E;slow Tchebychev}\label{A3.2} 
Let $T_{j}$ be the $j$th Chebychev
polynomial. Suppose that $\gamma_{j}$ is a sequence
of non-negative numbers such that $\sum_{j=1}^{\infty}\gamma_{j}$
converges. Explain why  $\sum_{j=1}^{\infty}\gamma_{j}T_{3^{j}}$
converges uniformly on $[-1,1]$ to a  continuous function $f$.

Let us write $P_{n}=\sum_{j=1}^{n}\gamma_{j}T_{3^{j}}$.
Show that we can find points
\[-1\leq x_{0}<x_{1}<\ldots<x_{3^{n+1}}\leq 1\]
such that
\[f(x_{k})-P_{n}(x_{k})=(-1)^{k+1}\sum_{j=n+1}^{\infty}\gamma_{j}.\]
\end{question}
\begin{question}\label{A3.3}
Use Exercise~\ref{E;slow Tchebychev} to show that,
given any decreasing sequence $\delta_{n}\rightarrow 0$,
we can find a continuous function $f:[-1,1]\rightarrow{\mathbb R}$ 
such that
(writing $\|\ \|_{\infty}$ for the uniform norm on $[-1,1]$)
\[\inf\{\|f-P\|_{\infty}\,:\,\text{$P$ a polynomial of degree
at most $n$}\}\geq \delta_{n}.\]

Why does this not contradict the Weierstrass approximation theorem?
\end{question}
\begin{question}\label{A3.4}
Use the ideas of Theorem~\ref{T;Bernstein}
to show that, if $f:[0,1]^{2}\rightarrow{\mathbb R}$
is continuous, then, given $\epsilon>0$,
we can find a polynomial $P$ in
two variables such that
\[|f(x,y)-P(x,y)|<\epsilon\]
for all $x,\,y\in[0,1]$.
\end{question}
\begin{question}\label{A3.5}
(Not very much to do with the course
but a nice question which you should have 
met at least once in your life.) 
Suppose $f:[-1,1]^{2}\rightarrow{\mathbb R}$
is a bounded function such that the map $x\mapsto f(x,y)$ is continuous for
each fixed $y$ and the map  $y\mapsto f(x,y)$ is continuous for
each fixed $x$. By means of a proof or counterexample
establish whether $f$ is necessarily continuous.
\end{question}
The next three questions give alternative proofs of
Weierstrass's theorem.
\index{Weierstrass's approximation theorem!other proofs} Each 
involves some heavy lifting, 
but each introduces ideas which are very useful in a variety
of circumstances. If you are finding the course heavy going,
or your busy social schedule limits the time you can spend
thinking to an absolute minimum, you can skip them. 
If you want to do any sort of analysis in the future  
they are highly recommended.
\begin{question}\label{A3.6}\label{E;long Bernstein} 
Here is an alternative
proof of Bernstein's theorem using a different set of ideas.

(i) Let $f\in C([0,1])$. Show that given $\epsilon>0$ we can find an $A>0$
such that
\[f(x)+A(t-x)^{2}+\epsilon/2\geq f(t)\geq f(x)-A(t-x)^{2}-\epsilon/2\]
for all $t,\,x\in [0,1]$.

(ii) Now show that we can find an $N$ such that, writing 
\[h_{r}(t)=f(r/N)+A(t-r/N)^{2},\ g_{r}(t)
=f(r/N)-A(t-r/N)^{2},\]
we have
\[g_{r}(t)+\epsilon\geq f(t)\geq h_{r}(t)-\epsilon\]
for $|t-r/N|\leq 1/N$. (You may find it helpful
to draw diagrams here and in~(iii).)

(iii) We say that a linear map $S:C([0,1])\rightarrow C([0,1])$ is positive
if $F(t)\geq 0$ for all $t\in[0,1]$ implies $SF(t)\geq 0$ for all $t\in [0,1]$.
Suppose that $S$ is such a positive linear operator.
Show that if $F(t)\geq G(t)$ for all $t\in[0,1]$, 
then $(SF)(t)\geq (SG)(t)$ for all $t\in [0,1]$
$[F,\,G\in C([0,1])]$.
Show also that if, $F\in C([0,1])$, 
then $\|SF\|_{\infty}\leq\|S1\|_{\infty}\|F\|_{\infty}$.

(iv) Write $e_{r}(t)=t^{r}$. Suppose that $S_{n}$ 
is a sequence of positive linear
functions such that $\|S_{n}e_{r}-e_{r}\|_{\infty}\rightarrow 0$ 
as $n\rightarrow\infty$
for $r=0$, $r=1$ and $r=2$. Show, using~(ii), or otherwise, that
$\|S_{n}f-f\|_{\infty}\rightarrow 0$ as $n\rightarrow\infty$ for 
all $f\in C([0,1])$.

(v) Let
\[(S_{n}f)(t)=\sum_{j=0}^{n}\binom{n}{j}f(j/n)t^{j}(1-t)^{n-j}.\]
Verify that $S_{n}$ satisfies the hypotheses of part~(iv) and
deduce Bernstein's theorem.
\end{question}
\begin{question}$\bigstar$\label{E;kernel Weierstrass}\label{A3.7}
Here is another proof of Weierstrass's
theorem which is closer to his original
proof. We wish to show show that any continuous function
function $f:[-1/2,1/2]\rightarrow{\mathbb R}$ can
be uniformly approximated by polynomials on $[-1/2,1/2]$. 
To do this we 
show that any continuous function 
$g:{\mathbb R}\rightarrow{\mathbb R}$ with $g(x)=0$
for $|x|\geq 1$   can
be uniformly approximated by polynomials on $[-1/2,1/2]$.
Why does this give the desired result?

Let 
\[L_{n}(x)=\begin{cases}(4-x^{2})^{n}&\text{for $|x|\leq 2$,}\\
0&\text{otherwise,}
\end{cases}
\]
let
\[A_{n}=\int_{-\infty}^{\infty}L_{n}(x)\,dx\]
and let $K_{n}(x)=A_{n}^{-1}L_{n}(x)$.

(i) Show that
\[P_{n}(x)=K_{n}*g(x)=\int_{-\infty}^{\infty}K_{n}(x-t)g(t)\,dt\]
is a polynomial in $x$ on the interval $[-1/2,1/2]$
It may be helpful to recall that
$f*g=g*f$.)

(ii) Let $\delta>0$ be fixed. Show that
$K_{n}(x)\rightarrow 0$ uniformly for $|x|\geq\delta$ 
and
\[\int_{-\delta}^{\delta}K_{n}(x)\,dx\rightarrow 1\]
as $n\rightarrow\infty$.

(iii) Use the fact that $g$ is bounded and uniformly
continuous together with the formula
\[P_{n}(x)=\int_{-\delta}^{\delta}K_{n}(t)g(x-t)\,dt
+\int_{t\notin(-\delta,\delta)}K_{n}(t)g(x-t)\,dt\]
to show that $P_{n}(x)\rightarrow g(x)$ uniformly
on $[-1/2,1/2]$.
\end{question}
\begin{question}\label{E;Lebesgue}\label{A3.8} 
Here is another proof
of Weierstrass's theorem, this time due to Lebesgue.

(i) If $a<b$ sketch the graph of $|x-a|-|x-b|$.

(ii) Show that if $g:[0,1]\rightarrow{\mathbb R}$
is piece-wise linear, then we can find $n\geq 1$,
$\lambda_{j}\in{\mathbb R}$ and $a_{j}\in[0,1]$
such that
\[g(t)=\lambda_{0}+\sum_{j=1}^{n}\lambda_{j}|t-a_{j}|.\]
Deduce that, given $f:[0,1]\rightarrow{\mathbb R}$
and $\epsilon>0$, we can find $n\geq 1$,
$\lambda_{j}\in{\mathbb R}$ and $a_{j}\in[0,1]$
such that
\[\left|f(t)-\lambda_{0}-\sum_{j=1}^{n}\lambda_{j}|t-a_{j}|\right|
<\epsilon.\]

(iii) Let
\[u_{n}(t)=3\sqrt{\left(1+\frac{1}{n}\right)-
\left(1-\frac{t^{2}}{9}\right)}.\]
Explain using results on the general binomial expansion
(which you need not prove) why $u_{n}$ can be uniformly
approximated by polynomials on $[-2,2]$.

Explain why $u_{n}(t)\rightarrow |t|$ uniformly on $[-2,2]$
as $n\rightarrow\infty$. Deduce that there exist polynomials $q_{r}$
with $q_{r}(t)\rightarrow|t|$ uniformly on $[-1,1]$ as 
$r\rightarrow\infty$.

(iv) Use (ii) and (iii) to prove the Weierstrass approximation
theorem.

\noindent$[$Lebesgue's idea provides the basis for the proof 
of the more general Stone--Weierstrass theorem.$]$
\end{question}
\begin{question}\label{A3.9}(This will look less odd if you have done the 
previous exercise.)

(i) Let a sequence of distinct
$x_{n}$ form a dense subset of $[0,1]$
with $x_{0}=0$, $x_{1}=1$. If $f\in C([0,1])$, define
$f_{n}:[0,1]\rightarrow{\mathbb R}$ to be the simplest
piece-wise linear function with $f_{n}(x_{j})=f(x_{j})$
for $0\leq j\leq n$. Show that $f_{n}\rightarrow f$
uniformly.

(ii) Use (i) to show that there exists a sequence of
continuous functions $\phi_{n}$ such that, for each
$f\in C([0,1])$ there exists a unique sequence $a_{n}$
such that 
\[\sum_{j=0}^{n}a_{j}\phi_{j}\rightarrow f\]
uniformly on $[0,1]$.

\noindent$[$In practice the sequence $x_{j}$ is
usually taken to be $0$, $1$, $1/2$, $1/4$, $3/4$
$1/8$, $3/8$, $5/8$, $7/8$,$1/16$, $3/16$, \ldots.$]$
\end{question} 
\begin{question}$\bigstar$\label{Q;ripple necessary}
In Theorem~\ref{T;best approximation exists}\label{A3.10}
we saw that, if $f:[a,b]\rightarrow{\mathbb R}$ is a continuous
function there exists a polynomial $P$, of degree at most $n-1$,
such that $\|P-f\|_{\infty}\leq\|Q-f\|_{\infty}$ for all polynomials
$Q$ degree $n$ or less. 
The object of this question is to 
show that the polynomial $P$ satisfies the equiripple
criterion. 

We claim that we can find 
$a\leq a_{0}\leq a_{1}\leq \dots\leq a_{n}\leq b$
such that, writing $\sigma=\|f-P\|_{\infty}$ we have
either
\begin{align*}
f(a_{j})-P(a_{j})=(-1)^{j}\sigma&\ \text{for all $0\leq j\leq n$}\\
\intertext{or}
f(a_{j})-P(a_{j})=(-1)^{j+1}\sigma&\ \text{for all $0\leq j\leq n$.}
\end{align*}

Our proof will be by reductio ad absurdum.

We assume without loss of generality that 
$[a,b]=[0,1]$ and $\sigma=1$.
 

(i) Write $g=f-P$.
Explain why we can find an integer $N\geq 1$ such that,
if $1\leq r\leq N$, at least one of the following statements
must be true
\begin{align*}
g(x)\geq 1/2&\ \text{for all $x\in[(r-1)/N,r/N]$},\\
\intertext{or}
g(x)\leq -1/2&\ \text{for all $x\in[(r-1)/N,r/N]$},\\
\intertext{or}
|g(x)|\leq 3/4&\ \text{for all $x\in[(r-1)/N,r/N]$}.
\end{align*}

(ii) Using the result of~(i), show that, if our putative
theorem is false, we can find an integer $q\leq n$, integers
\[0=u(1)<v(1)<u(2)<v(2)<\dots<u(q)<v(q)=N\]
and $w\in\{0,1\}$ such that
\begin{align*}
(-1)^{w+j}g(x)>-1&\ \text{for all $x\in[u(j)/N,v(j)/N]$}\\
|g(x)|<1&\ \text{for all $x\in[v(j)/N,u(j+1)/N]$}.
\end{align*}
Without loss of generality, we take $w=0$.

(iii) Explain why we can find an $\eta>0$ with
\begin{align*}
(-1)^{j}g(x)>-1+\eta&\ \text{for all $x\in[u(j)/N,v(j)/N]$}\\
|g(x)|<1-\eta&\ \text{for all $x\in[v(j)/N,u(j+1)/N]$},
\end{align*}
for all $j$. We may take $\eta<1/8$ and will do so.

(iv) Explain how to find a polynomial $R$ of degree $n$ or
less with $\|R\|_{\infty}=1$ such
that 
\[(-1)^{j}R(x)>0\ \text{for all $x\in[u(j)/N,v(j)/N]$}\]
and $j=1,2,\dots,q$.

(v) Show that
\[|g(x)-(\eta/2)R(x)|<1-\eta/2\]
for all $x\in[0,1]$.
Hence obtain a contradiction.
\end{question}
\clearpage
\begin{question}\label{E;small bound}\label{A3.11} 
Suppose  that we have
a sequence of continuous functions
$f_{n}:[0,1]\rightarrow{\mathbb R}$ such that
$f_{n}(x)\rightarrow 0$ for each $x\in[0,1]$
as $n\rightarrow\infty$. Then, given $\epsilon>0$, we can find
a non-empty interval $(a,b)\subseteq[0,1]$
and an $N(\epsilon)$ such that
\[|f_{n}(t)|\leq \epsilon\]
for all $t\in(a,b)$ and all $n\geq N(\epsilon)$.

\noindent\emph{Hint} Consider the sets
\[E_{N}=\{x\in[0,1]\,:\,|f_{n}(x)|\leq\epsilon, \text{for all}\ n\geq N\}.\]
\end{question}
\begin{question}\label{A3.12}
Suppose that $f:[1,\infty)\rightarrow{\mathbb R}$
is a continuous function and $f(nx)\rightarrow 0$ as $n\rightarrow\infty$
for each $x\in[1,\infty)$. Show that $f(x)\rightarrow 0$
as $x\rightarrow\infty$.
\end{question}
\begin{question}$\bigstar$\label{A3.13} 
(i) Consider $C([0,1])$ with the uniform norm.
If $M$ is strictly positive
integer, let $\mathcal{E}_{M}$ be the set of $f\in C([0,1])$ such that
whenever $N\geq 1$ and
\[0\leq x_{0}<x_{1}<x_{2}<\ldots<x_{N}\leq 1\]
we have
\[\sum_{j=1}^{N}|f(x_{j-1})-f(x_{j})|\leq M.\]
Show that ${\mathcal E}_{M}$ is closed with dense complement.
Deduce  that there is a set ${\mathcal G}$ which is the complement
of a set of first category
such that, given any $f\in{\mathcal G}$ and any $M\geq 1$, we can find
$N\geq 1$ and
\[0\leq x_{0}<x_{1}<x_{2}<\ldots<x_{N}\leq 1\]
with
\[\sum_{j=1}^{N}|f(x_{j-1})-f(x_{j})|>M.\]

(ii) Show that there is a set ${\mathcal H}$ which is the complement
of a set of first category
such that, given any $f\in{\mathcal H}$, any $a$ and $b$ with
$0\leq a<b\leq 1$ and any $M\geq 1$, we can find
$N\geq 1$ and
\[a\leq x_{0}<x_{1}<x_{2}<\ldots<x_{N}\leq b\]
with
\[\sum_{j=1}^{N}|f(x_{j-1})-f(x_{j})|>M.\]
\end{question}

\begin{question}\label{A3.14}  
Let $h:[0,1]\rightarrow{\mathbb R}$ be a
continuous
strictly increasing function with $h(0)=0$. We say that 
a compact set $E$ is thin if, given $\epsilon>0$,
we can find a finite collection of intervals $I_{j}$
of length $l_{j}$ $[N\geq j\geq 1]$ such that
\[E\subseteq\bigcup_{j=1}^{N}I_{j},
\ \text{but}\ \sum_{j=1}^{N}h(l_{j})<\epsilon.\]

Show that the set ${\mathcal C}$ of thin compact sets 
is the complement of a set of first category
in the space ${\mathcal K}$
of compact subsets of $[0,1]$
with the Hausdorff metric $\rho$.
\end{question}
\begin{question}$\bigstar$\label{A3.15} 
Let $A=\{z\in{\mathbb C}\,:\,1/2<|z|<1\}$
and let  $D=\{z\in{\mathbb C}\,:\,|z|<1\}$.
Suppose that $f:A\rightarrow{\mathbb C}$ is analytic
and we can find polynomials $p_{n}$ with $p_{n}(z)\rightarrow f(z)$
uniformly on $A$. Show that we can find an analytic function
$g:D\rightarrow{\mathbb C}$ with $f(z)=g(z)$ for all $z\in A$.

\noindent[Hint: Use the maximum modulus principle
and the general principle of uniform convergence.]
\end{question}
\begin{question}\label{A3.16} (i) We work in ${\mathbb C}$.
Show that
there exists a sequence of polynomials
$P_{n}$ such that
\[
P_{n}(z)\rightarrow
\begin{cases}
1&\text{if $|z|<1$ and $\Re z\geq 0$}\\
0&\text{if $|z|<1$ and $\Re z< 0$}
\end{cases}
\]
as $n\rightarrow\infty$.

\noindent[Hint: Recall that, if $\Omega_{1}$ and $\Omega_{2}$
are disjoint open sets and $f(z)=0$ for   $z\in\Omega_{1}$ 
and $f(z)=1$ for $z\in \Omega_{2}$, then $f$ is analytic
on $\Omega_{1}\cup\Omega_{2}$.]

(ii)  Show that
there exists a sequence of polynomials
$Q_{n}$ such that
\[
Q_{n}(z)\rightarrow
\begin{cases}
1&\text{if $\Re z\geq 0$}\\
0&\text{if $\Re z< 0$}
\end{cases}
\]
as $n\rightarrow\infty$.
\end{question}

\clearpage
\section{Question sheet 4}\label{S;sheet four}
\begin{question}\label{A4.1} By quoting the appropriate theorems,
show that, if $\Omega$ is an open set in ${\mathbb C}$,
then $f:\Omega\rightarrow{\mathbb C}$ is analytic
if and only if, whenever $K$ is a compact subset of
$\Omega$ with path-connected complement
and $\epsilon>0$, we can find a polynomial
$P$ with $|f(z)-P(z)|<\epsilon$ for all $z\in K$.
\end{question}
\begin{question}\label{A4.1a} In this exercise we suppose
that $K$ is a bounded compact subset
of ${\mathbb C}$ and $E$ is a non-empty
bounded connected component
of ${\mathbb C}\setminus K$. Give a simple example
of such a $K$ and $E$. Our object is to show that
if $a\in E$ the function $f(z)=(z-a)^{-1}$
is not uniformly approximable on $K$
by polynomials.

Suppose $P$ is a polynomial with $|p(z)-(z-a)^{-1}|\leq\epsilon$
or all $z\in K$. By observing that the boundary $\partial E$
of $E$ lies in $K$ and using the maximum modulus principle
deduce that  $|p(w)(w-a)-1|\leq\epsilon\sup_{z\in K}|z-a|$. 
By choosing $w$ appropriately deduce that
$\epsilon\geq (\sup_{z\in K}|z-a|)^{-1}$.  
\end{question} 
\begin{question}\label{A4.2} Show that $\cos 1$ is irrational.
Show more generally that $\cos 1/n$ is irrational whenever
$n$ is a non zero integer.
\end{question}
\begin{question}\label{A4.3} Use the idea of Louiville's theorem
to write down a continued fraction whose value
is transcendental. Justify your answer.
\end{question}
\begin{question}\label{Q;Chest of drawers}\label{A4.4}
Let us write $\langle y\rangle=y-[y]$ so that
$\langle y\rangle$ is the fractional part of $y$

Suppose that  $x$ is irrational.
If $m$ is strictly positive integer consider
the $m+1$ points
\[0=\langle 0x\rangle,\ \langle 1x\rangle,
\ \ldots,\ \langle kx\rangle,\ \ldots,
\  \langle mx\rangle\]
and explain why there must exist integers $r$
and $s$ with $0\leq s<r\leq m$ and
\[|\langle rx\rangle- \langle sx\rangle|\leq 1/m.\]
Deduce that we can find an integer $v$ with $1\leq v\leq m$
and and integer $u$ with
\[|vx-u|\leq 1/m\]
and so with
\[\left|x-\frac{u}{v}\right|\leq \frac{1}{mv}\leq \frac{1}{v^{2}}.\]

Deduce that we can find $u_{n}$, $v_{n}$ integers
with $v_{n}\rightarrow\infty$ such that
\[\left|x-\frac{u_{n}}{v_{n}}\right|\leq \frac{1}{v_{n}^{2}}.\]
\end{question}
\begin{question}\label{A4.5} Determine the continued fraction expansion
of $71/49$ and use your result to find the rational number
with denominator no greater than $10$ which best approximates
$71/49$.
\end{question}
\begin{question}\label{A4.6} 
(i) Determine the continued fraction expansions of
$\sqrt 3$.

(ii) Explain why the form of the continued fraction shows that
$\sqrt 3$ is irrational.

(iii) Let $p_{n}/q_{n}$ be the $n$th convergent for $\sqrt{3}$.
Compute $(p_{n}/q_{n})^{2}$ for $n=1,\,2,\,3,\,4,\,5$.
\end{question}
\begin{question}\label{A4.7} 
Let $a$ and $b$ be strictly positive integers. If
\[x=\cfrac{1}
{a+\cfrac{1}
{b+\cfrac{1}
{a+\cfrac{1}
{b+\dots}}}},\] 
show that $ax^{2}+abx-b=0$
\end{question}
\begin{question}\label{A4.8}\label{Q;split} 
If $x$ is irrational, we can find
$u_{n}$ and $v_{n}$ show that we can find
integers with $v_{n}\rightarrow\infty$
such that
\[ \left|\frac{u_{n}}{v_{n}}-x\right|<\frac{1}{2v_{n}^{2}}.\]

\noindent$[$Hint: Show that, in fact, at least one of the convergents
$p_{n}/q_{n}$ or $p_{n+1}/q_{n+1}$ must satisfy the required
inequality.$]$ 
\end{question}
\begin{question}\label{Q;bounded entry}\label{A4.9} 
Show that if all the integers $a_{n}$
in the continued fraction 
\[x=\cfrac{1}
{a_{1}+\cfrac{1}
{a_{2}+\cfrac{1}
{a_{3}+\cfrac{1}
{a_{4}+\dots}}}},\]
are bounded, then there exists an $M>0$
such that
\[\left|x-\frac{p}{q}\right|>\frac{M}{q^{2}}\]
for all integers $p$ and $q$ with $q\neq 0$.
\end{question}


\begin{question}\label{A4.11}
The Fibonacci
sequence has many interesting aspects. (It is,
so far as I know the only series with its own
Fanzine --- \emph{ The Fibonacci Quarterly}.)

(i) Find the general solution of the difference equation
\[u_{n+1}=u_{n}+u_{n-1}.\]
The Fibonacci series is the particular solution $F_{n}=u_{n}$
with $u_{0}=0$, $u_{1}=1$. Write $F_{n}$ in the appropriate form.

(ii) Show, by using (i), or otherwise, that if $n\geq 1$,
$F_{n}$ is the closest integer to
\[\frac{1}{\sqrt 5}\left(\frac{1+\sqrt 5}{2}\right)^{n}.\]
We call
\[\tau= \frac{1+\sqrt 5}{2}\]
the golden ratio.

(iii) Prove the two identities
\begin{gather*}
F_{2n+1}=F_{n}^{2}+F_{n+1}^{2}\\
F_{2n}=F_{n}(F_{n-1}+F_{n+1})
\end{gather*}
by using the result of (i).

(iv) Explain why
\[\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}=A^{n}\]
where 
\[A=\begin{pmatrix}1&1\\1&0\end{pmatrix}.\]
Use the result $A^{n+m}=A^{n}A^{m}$ to deduce
that
\begin{gather*}
F_{n+m+1}=F_{n+1}F_{m+1}+F_{n}F_{m}\\
F_{n+m}=F_{n}F_{m+1}+F_{n-1}F_{m}.
\end{gather*}
Obtain~(iii) as a special case.

(v) Let $x_{n}=F_{n+1}/F_{n}$. Use~(iii) to express $x_{2n}$
as a rational function of $x_{n}$.

(vi) Suppose now we take $y_{k}=x_{2^{k}}$. 
Write down $y_{n+1}$ as a rational function of $y_{n}$.
Use  (i) to show
that $y_{k}$ converges very rapidly to $\tau$.
Can you link this with the Newton--Raphson
method for finding a root of a particular function?

(vii) What is the relation between $\tau$ and the $\sigma$
of Exercise~15.9.
Use the result of part~(i) to obtain an estimate
for 
\[\frac{F_{n}}{F_{n+1}}-\sigma\]
correct to within a constant multiple of $\sigma^{4n}$.

\end{question}
\begin{question}\label{Q;special dog}\label{A4.12} 
Let $p(z)=z^{2}-4z+3$ and let 
$\gamma:[0,1]\rightarrow{\mathbb C}$ be given by $\gamma(t)=p(2e^{2\pi it})$.
Show that closed path associated with $\gamma$ does not pass through $0$.

Compute $w(\gamma,0)$ 

(i) Non-rigorously direct from the definition by
obtaining enough information about $\gamma$,
(You could write the real and imaginary parts
of $\gamma(t)$ in terms of $\cos t$ and $\sin t$.)

(ii) by factoring, and

(iii) by the dog walking lemma.
\end{question}
\begin{question}$\bigstar$\label{A4.13} Suppose that 
$\gamma:[0,1]\rightarrow{\mathbb C}\setminus\{0\}$
is a continuously differentiable function
with $\gamma(0)=\gamma(1)$.

If we define $r:[0,1]\rightarrow {\mathbb C}$
by
\[r(t)=\exp\left(\int_{0}^{t}\frac{\gamma'(s)}{\gamma(s)}\,ds\right)\]
compute the derivative of $r(t)/\gamma(t)$ and deduce
that
\[w(\gamma,0)=\frac{1}{2\pi i}
\int_{0}^{1}\frac{\gamma'(s)}{\gamma(s)}\,ds.\]

Use this result and the residue theorem to compute
$w(\gamma,0)$ in Exercise~\ref{Q;special dog}.

\noindent$[$The example used in the last two questions has
been chosen to make things easy. However, if you are prepared
to work hard, it is possible to obtain enough information
about $\gamma$ to find the winding number 
of closed curves even in quite
complicated cases. If many winding numbers are required
(as may be the case when studying stability in an engineering
context then we can use numerical methods (this question
suggests a possibility, though not necessarily a good one) 
together with
the knowledge that the winding number is an integer  
to obtain winding numbers on an industrial scale.$]$
\end{question}
\begin{question}$\bigstar$\label{A4.10}  
Take your electronic calculator out of 
your old school satchel (or use the expensive piece of equipment
on which you play games) and find the first few terms
of the continued fraction for $\pi$ (or, more strictly
for the rational number that your calculator gives when
you ask it for $\pi$.) Compute first few associated convergents
(what we have called $3+p_{n}/q_{n}$). 

Verify that $355/113$ is an extremely good approximation
for $\pi$ and explain why this is so. Apparently
the approximation
was first discovered by the astronomer Tsu Ch'ung-Chih 
in the fifth century A.D.

The entries $a_{n}$ in the continued fraction expansion for
$\pi$ look, so far as anyone knows, just like those
you would expect from a random real number (in a sense made
precise in Corollary~\ref{C;continued random}).

I would be inclined to say that this was precisely what one should expect
if there was not a beautiful expansion (using a generalisation
of the kind of continued fraction discussed in the course)
found by Lord Brouncker in 1654.
\[\frac{\pi}{4}=1+\cfrac{1^{2}}
{1+\cfrac{3^{2}}
{2+\cfrac{5^{2}}
{2+\cfrac{7^{2}}
{2+\dots}}}}.\]

You may easily verify that the first convergents
are 
\[1,\ ,1-\frac{1}{3},\, 1-\frac{1}{3}+\frac{1}{5}-,\ \dots\]
and, if your name is Euler, that the $n$th convergent
is
\[\sum_{j=0}^{n}\frac{(-1)^{j}}{2j+1}\]
and then, if your name is Leibniz, you will prove
the result
\[\sum_{j=0}^{n}\frac{(-1)^{j}}{2j+1}\rightarrow \frac{\pi}{4}.\]
The convergence is, however, terribly slow and
it is no wonder that Huygen's initially disbelieved
Brouncker's result.
\end{question}
\printindex
\end{document}
