\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\\In a Time of Covid}
\author{T.~W.~K\"{o}rner}
\maketitle
\begin{footnotesize}
{\bf Small print}
In normal times these notes would be a supplement
to the actual lectures with the statements of theorems
in one portion of the notes and the proofs in
a separate portion. (If you would prefer such a system
then the old notes are available from my home page.)
Instead I suspect the actual lectures will be a supplement
to these notes. I strongly advise writing out your own notes
at some time.
I suggest that you print out these notes and refer to them
when watching the lectures. I shall do my best to keep to the same
order and use the same notation as is used in the notes.
This course is not intended as a foundation
for further courses, so the lecturer is allowed substantial
flexibility. Exam questions will
only cover topics in these notes but unless specifically
stated otherwise, anything lectured in the course
will be considered examinable.
I will not talk about
topological spaces but confine myself to ordinary Euclidean
spaces ${\mathbb R}^{n}$, ${\mathbb C}$ and complete
metric spaces.
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 pdf and tex format
from my home page
\begin{center}
{\bf http://www.dpmms.cam.ac.uk/\~{}twk/}
\end{center}
\end{footnotesize}
Under present circumstances corrections are \emph{particularly welcome}
(email me at twk@dpmms.cam.ac.uk).
\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 metric on $X$ and that $(X,d)$
is a 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)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 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}
\begin{proof}[Solution] (i) If $y\in B(x,r)$ then
$\delta=r-d(x,y)>0$. Now observe that, if $z\in B(y,\delta)$,
then
\[d(x,z)\leq d(x,y)+d(y,z)0$.
Choose $y_{n}\in B(y,1/n)\cap E$. We have $y_{n}\in E$,
$y_{n}\xrightarrow[d]{}y$ and yet $y\notin E$. Thus $E$ is not closed.
(iii) Suppose that $X\setminus E$ is not closed. Then there
is a sequence $y_{n}\notin E$ with
$y_{n}\xrightarrow[d]{}y$ and yet $y\in E$.
Thus $B(y,r)\nsubseteq E$ for all $r>0$ and $E$ is not open.
\end{proof}
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}
\begin{proof}[Solution]
Suppose $x_{n}\xrightarrow[d]{}x$.
Let $\epsilon>0$. We can find an $N$ such that
$d(x_{n},x)<\epsilon/2$ for all $n\geq N$. It follows that
\[d(x_{n},x_{m})\leq d(x_{n},x)+d(x,x_{m})
<\epsilon/2+\epsilon/2=\epsilon\]
for all $n,\,m\geq N$.
\end{proof}
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}
\begin{proof}
(i) Let $\epsilon>0$. We can find an $N$
such that $d(x_{n},x_{m})<\epsilon/2$ for $m,\,n\geq N$.
We can now find a $J$ such that $n(J)\geq N$ and
$d(x_{n(J)},x)<\epsilon/2$. We now observe that, if
$m\geq N$, we get
\[d(x_{m},x)\leq d(x_{m},x_{n(J)})+d(x_{n(J)},x)
<\epsilon/2+\epsilon/2=\epsilon.\]
(ii) If $x_{n}$ is Cauchy we can find a strictly increasing
sequence $n(j)$ with
\[d(x_{n},x_{m})<\epsilon(j)\]
for all $n,\, m\geq n(j)$. By hypothesis, $x_{n(j)}$ converges
as $j\rightarrow\infty$. Part~(i) now tells us
that the sequence $x_{n}$
converges.
\end{proof}
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}
\begin{proof}[Solution]
(i) Observe that, whenever $x,\,y,\,z\in Y$,
\begin{gather*}
d_{Y}(x,y)=d(x,y)\geq 0,\\
d_{Y}(x,y)=0\Leftrightarrow d(x,y)=0\Leftrightarrow x=y,\\
d_{Y}(x,y)=d(x,y)=d(y,x)=d_{Y}(y,x),\\
d_{Y}(x,y)+d_{Y}(y,z)=d(x,y)+d(y,z)\geq d(x,z)
=d_{Y}(x,z).
\end{gather*}
(ii) Suppose the sequence $x_{n}$ is Cauchy in $(Y,d_{Y})$.
Then the sequence $x_{n}$ is Cauchy in $(X,d)$, so
$x_{n}\rightarrow x$ for some $x\in X$. But $Y$ is closed,
so $x\in Y$ and $x_{n}\rightarrow x$ in $(Y,d_{Y})$.
(iii) If $y_{n}\in Y$ and $y_{n}\rightarrow y$ in $(X,d)$,
then $y_{n}$ is Cauchy in $(X,d)$, so Cauchy in $(Y,d_{Y})$, so
$y_{n}\rightarrow z$ in $(Y,d_{y})$ for some $z\in Y$.
It follows that $y_{n}\rightarrow z$ in $(X,d)$ so,
by the uniqueness of limits, $y=z\in Y$. Thus $Y$ is closed.
\end{proof}
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.
\begin{proof}[Proof Theorem~\ref{T;Euclid} for $n=2$]
We prove the
case when $n=2$. Suppose
that ${\mathbf x}_{n}=(x_{n},y_{n})$
is Cauchy in ${\mathbb R}^{2}$. Since
\[|x_{n}-x_{m}|\leq \|{\mathbf x}_{n}-{\mathbf x}_{m}\|,\]
$x_{n}$ is Cauchy in ${\mathbb R}$
and by our 1A theorem (Theorem~\ref{T;junior Cauchy})
converges to a limit $x$.
Similarly $y_{n}$ converges to a limit $y$ in ${\mathbb R}$.
If we set ${\mathbf x}=(x,y)$, then
\[\|{\mathbf x}_{n}-{\mathbf x}\|\leq |x_{n}-x|+|y_{n}-y|
\rightarrow 0\]
as $n\rightarrow\infty$.
\end{proof}
\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}
\begin{proof} We prove the case $m=2$.
Write ${\mathbf x}_{n}=(x_{n},y_{n})$. We have
that $x_{n}$ is a bounded sequence in ${\mathbb R}$ and
so (by the 1A result) there exists an $x\in{\mathbb R}$
and a sequence $n(j)\rightarrow\infty$ such that
$x_{n(j)}\rightarrow x$ as $j\rightarrow\infty$.
Now $y_{n(j)}$ is a bounded sequence
in ${\mathbb R}$ and
so there exists a $y\in{\mathbb R}$
and a sequence $j(k)\rightarrow\infty$
such that $y_{n(j(k))}\rightarrow y$
as $k\rightarrow\infty$. Now set $r(k)=n(j(k))$
and ${\mathbf x}=(x,y)$ to obtain
$r(k)\rightarrow\infty$
and ${\mathbf x}_{r(k)}\rightarrow{\mathbf x}$
as $k\rightarrow\infty$.
\end{proof}
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}
\begin{proof}[Theorem~\ref{T;closed bounded}]
(i) Since ${\mathbf x}_{r}\in E$, we know that the
${\mathbf x}_{r}$ form a bounded sequence and so
have a convergent subsequence
${\mathbf x}_{r(k)}\rightarrow{\mathbf x}$.
Since $E$ is closed, ${\mathbf x}\in E$.
(ii) If $E$ is not bounded, we can find ${\mathbf x}_{r}\in E$
with $\|{\mathbf x}_{r+1}\|\geq \|{\mathbf x}_{r}\|+1$.
If $r>s$
\[\|{\mathbf x}_{r}-{\mathbf x}_{s}\|\geq
\|{\mathbf x}_{r}\|-\|{\mathbf x}_{s}\|\geq 1,\]
so no subsequence can be Cauchy and so no subsequence can converge.
If $E$ is not closed, we can find ${\mathbf x}_{r}\in E$
and ${\mathbf x}\notin E$ such that
${\mathbf x}_{r}\rightarrow{\mathbf x}$. Any subsequence
of ${\mathbf x}_{r}$ will still converge to ${\mathbf x}\notin E$.
\end{proof}
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 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 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}
\begin{proof}[Solution]
(i) Suppose $f^{-1}(U)$ is open whenever $U$ is.
If $x\in X$, $\epsilon>0$, we know that $B(f(x),\epsilon)$
is an open subset of $Y$, so $f^{-1}\big(B(f(x),\epsilon)\big)$
is an open subset of $X$ containing $x$. Thus we can find a
$\delta>0$ with
$B(x,\delta)\subseteq f^{-1}\big(B(f(x),\epsilon)\big)$.
In other words,
\[z\in B(x,\delta)\Rightarrow f(z)\in B(f(x),\epsilon).\]
Thus $f$ is continuous.
Conversely, if $f$ is continuous and $U$ open in $Y$,
then, given $x\in X$ with $f(x)\in U$, we can find a
$\delta>0$ such that $B(f(x),\delta)\subseteq U$
and an $\epsilon>0$ such that
\[z\in B(x,\delta)\Rightarrow f(z)\in B(f(x),\epsilon).\]
Thus $B(x,\epsilon)\subseteq f^{-1}(U)$. We have shown
that $f^{-1}(U)$ is open.
(ii) Complementation. If $f^{-1}(F)$ is closed for
all $F$ closed then
\[U\ \text{open}\Rightarrow Y\setminus U\ \text{closed}
\Rightarrow X\setminus f^{-1}(U)=f^{-1}(Y\setminus U)
\ \text{closed}
\Rightarrow f^{-1}(U)\ \text{open},\]
so $f$ is continuous.
The converse is proved similarly.
\end{proof}
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}
\begin{proof} If $d(x,A)=0$, then we can find
$x_{n}\in A$ such that $d(x_{n},x)\leq 1/n$, so $x_{n}\rightarrow x$.
But $A$ is closed, so $x\in A$.
Let $x,\,y\in X$. Given $\epsilon>0$, we can find $a\in A$ such
that $d(x,a)\leq d(x,A)+\epsilon$. Now
\[d(y,A)\leq d(y,a)\leq d(x,y)+d(x,a)\leq d(x,y)+d(x,A)+\epsilon.\]
Since $\epsilon$ was arbitrary,
\[d(y,A)\leq d(x,y)+d(x,A).\]
The same argument shows that $d(x,A)\leq d(x,y)+d(y,A)$ so
\[|d(x,A)-d(y,A)|\leq d(x,y).\]
This shows that the map $x\mapsto d(x,A)$ is continuous.
\end{proof}
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}
\begin{proof}
Suppose that $y_{n}\in f(E)$. Then $y_{n}=f(x_{n})$
for some $x_{n}\in E$. By the Bolzano--Weierstrass
property, we can find $n(j)\rightarrow\infty$ and $x\in E$
such that $x_{n(j)}\rightarrow x$ as $j\rightarrow\infty$.
Now, by continuity,
\[y_{n(j)}=f(x_{n(j)})\rightarrow f(x)\in f(E)\]
so we are done.
\end{proof}
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}
\begin{proof}
By Theorem~\ref{T;Compact image}, $f(E)$ is closed and
bounded. Since $f(E)$ is non-empty, it has a supremum
(see 1A), $\alpha$, say. By the definition of the
supremum, we can find ${\mathbf a}_{n}\in E$
such that
\[\alpha-1/n\leq f({\mathbf a}_{n})\leq \alpha.\]
By the Bolzano--Weierstrass
property, we can find $n(j)\rightarrow\infty$
and ${\mathbf a}\in E$
such that ${\mathbf a}_{n(j)}\rightarrow{\mathbf a}$
as $j\rightarrow\infty$. We have
$f({\mathbf a}_{n(j)})\rightarrow f({\mathbf a})$,
so $f({\mathbf a})=\alpha$. Thus
\[f({\mathbf a})\geq f({\mathbf x})\]
for all ${\mathbf x}\in E$. We find ${\mathbf b}$
in a similar manner.
\end{proof}
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}
\begin{proof}
Let $n\geq 1$.
Suppose $P(z)=\sum_{j=0}^{n}a_{j}z^{j}$ where, without
loss of generality, we take $a_{n}=1$.
If $R\geq 2(2+\sum_{j=0}^{n-1}|a_{j}|)$,
then, whenever $|z|\geq R$, we have
\begin{align*}
|P(z)|&\geq |z|^{n}- \sum_{j=0}^{n-1}|a_{j}||z|^{j}\\
&=|z|^{n}\left(1-\sum_{j=0}^{n-1}|a_{j}||z|^{j-n}\right)\\
&\geq |z|^{n}/2>|a_{0}|.
\end{align*}
Since $\bar{D}_{R}=\{z\in{\mathbb C}:|z|\leq R\}$ is closed
and bounded (that is to say compact) and the map $z\mapsto|P(z)|$
is continuous, $|P|$ attains a minimum on $\bar{D}_{R}$
at a point $z_{0}$, say. By the previous paragraph,
$|z_{0}|0$ such that $|P(z)|\geq |P(z_{0})|$
for all $|z-z_{0}|<\delta$.
By replacing $P(z)$ by $P(z-z_{0})$, we may assume
that $z_{0}=0$ so that $|P(z)|\geq |P(0)|$
for all $|z|<\delta$. If $a_{0}=0$, then we have
$P(0)=0$ and we are done.
We show that the assumption that $a_{0}\neq 0$ leads to
a contradiction. Observe that
\[P(z)=\sum_{j=m}^{n}a_{j}z^{j}+a_{0}
=a_{0}\left(1-\sum_{j=m}^{n}b_{j}z^{j}\right)\]
with $a_{m}\neq 0$ and so $b_{m}\neq 0$. Choose $\theta$
so that $b_{m}\exp(im\theta)$ is real and positive.
Then
\[|P(\eta\exp i\theta)|\leq |a_{0}|-|b_{m}|\eta^{m}
+|a_{0}|\eta^{m+1}\sum_{j=m}^{n}|b_{j}|
\leq |a_{0}|-|b_{m}|\eta^{m}/2<|P(0)|\]
when $\eta$ is strictly positive and sufficiently
small. We have the required
contradiction.
\end{proof}
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}
\begin{proof}[Solution]
(i) Let $S(m)$ be the statement that, if
$P$ is a polynomial of degree $n$ with $n\leq m$
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.\]
Suppose that $S(m)$ is true and $P$ is a polynomial of degree
$m+1$. Then $P(z)=Az^{m+1}+Q(z)$ where $A\neq 0$ and $Q$
is a polynomial of degree at most $m$. We have
\[P(z)=A(z-a)z^{m}+q(z)\]
where $q(z)=Q(z)+az^{m}$, so $q$ is a polynomial of degree
at most $m$ and, by the inductive hypothesis,
\[q(z)=(z-a)u(z)+r\]
with $u$ a polynomial of degree at most $m-1$.
Thus $P(z)=(z-a)Q(z)+r$ with $Q(z)=A z^{m}+u(z)$.
We have shown that $S(m+1)$ is true.
Now $S(1)$ is true, since $cz+d=c(z-a)+(d-ca)$, so the required
result follows by induction.
(ii) We have $P(z)=(z-a)Q(z)+r$ by (i). Setting $z=a$, we have
$0=P(a)=r$ so $r=0$ and the result follows.
(iii) If $P_{n}$ has degree $n\geq 1$, then the fundamental theorem
of algebra tells us that $P_{n}$ has a root $a_{n}$. By~(ii),
there exists a polynomial $P_{n-1}$ of degree $n-1$
such that
\[P(z)=(z-a_{n})P_{n-1}(z).\]
Using induction, we deduce that
\[P_{n}(z)=P_{0}(z)\prod_{j=1}^{n}(z-a_{j}),\]
where $P_{0}(z)$ is a polynomial of degree $0$,
that is to say, $P_{0}(z)=A$ with $A$ a constant.
(iv) If $P$ is not the zero polynomial,
then (iii) tells we can find $m\leq n$
such that
\[P(z)=A\prod_{j=1}^{m}(z-a_{j})\]
with $A,\,a_{1},\,a_{2},\,\dots,\,a_{m}\in{\mathbb C}$
and $A\neq 0$.
Now $P(z)=0$ if and only if $z=a_{j}$ for some $1\leq j\leq m$.
The result follows.
\end{proof}
\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 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 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 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}
\begin{proof}[Solution]
There are a wide variety of ways of doing this
exercise. Any way that works is fine.
(i) If $x\in \Int E$, we can find a $\delta>0$ such
that $B(x,2\delta)\subseteq E$. If $y\in B(x,\delta)$,
then, by the triangle inequality,
\[z\in B(y,\delta)\Rightarrow z\in B(x,2\delta)\subseteq E.\]
Thus $\Int E$ is open.
If $V$ is open and $V\subseteq E$, then, if $v\in V$,
there exists a $\delta>0$ with $B(v,\delta)\subseteq V\subseteq E$.
Thus $V\subseteq \Int E$.
(ii) If $x_{n}\in \Cl E$ and $x_{n}\rightarrow x$,
then we can find $y_{n}\in E$ such that $d(y_{n},x_{n})<1/n$.
By the triangle inequality,
\[d(y_{n},x)\leq d(y_{n},x_{n})+d(x_{n},x)\rightarrow 0+0=0\]
so $x\in \Cl E$.
If $F$ is closed and $F\supseteq E$, then, whenever
$x_{n}\in E$ and $x_{n}\rightarrow x$, we have $x_{n}\in F$,
so $x\in F$. Thus $F\supseteq \Cl E$.
(iii) The complement of an open set is closed and the intersection
of two closed sets is closed, so
\[\partial E=\Cl E\cap (\Int E)^{c}\]
is closed.
(iv) If $E$ is closed, then we can find an $R>0$
such that $E\subseteq\bar{B}(0,R)$. Since $\bar{B}(0,R)$
is closed, $\Cl E\subseteq \bar{B}(0,R)$.
\end{proof}
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{proof}
We prove the result for $m=2$.
Since
$\Cl\Omega$ is compact, we know that $\phi$ attains a maximum
at some point $(x_{0},y_{0})\in\Cl\Omega$. We need to show that
it is impossible that $(x_{0},y_{0})\in\Omega$.
Suppose, if possible, that $(x_{0},y_{0})\in\Omega$. Since
$\Omega$ is open, we can find a $\delta>0$ such that
$B\big((x_{0},y_{0}),\delta\big)\subseteq\Omega$.
Consider the function
$f(y)=\phi(x_{0},y)$ defined for $y\in(y_{0}-\delta,y_{0}+\delta)$.
We have $f$ twice differentiable with a maximum at $y_{0}$.
Thus, by 1A analysis, $f''(y_{0})\leq 0$. It follows that
\[\frac{\partial^{2}\phi}{\partial y^{2}}(x_{0},y_{0})\leq 0.\]
The same argument applies for the partial derivatives with
respect to $x$, so
\[\triangledown^{2}\phi(x_{0},y_{0})=
\frac{\partial^{2}\phi}{\partial x^{2}}(x_{0},y_{0})
+\frac{\partial^{2}\phi}{\partial y^{2}}(x_{0},y_{0})\leq 0\]
contradicting our hypotheses.
\end{proof}
\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{proof} Again we prove the
result for $m=2$.
Let $\psi(x,y)=x^{2}+y^{2}$. Since $\psi$ is continuous and
$\Cl\Omega$ is compact, we know that there exists a $M$ with
$M\geq\psi(x,y)$ for all $(x,y)\in\Cl\Omega$. By direct calculation,
$\triangledown^{2}\psi=4$ everywhere.
Set $\phi_{n}=\phi+n^{-1}\psi$. Then $\phi_{n}$ satisfies the conditions
of Lemma~\ref{L;up Laplace} with $\epsilon=4/n$. It follows that
there is an ${\mathbf x}_{n}=(x_{n},y_{n})\in\partial \Omega$ with
\[\phi_{n}({\mathbf x}_{n})\geq \phi_{n}({\mathbf t})\]
for all ${\mathbf t}\in\Cl\Omega$. Automatically,
\[\phi({\mathbf x}_{n})\geq \phi({\mathbf t})-8M/n.\]
Since $\partial \Omega$ is compact, we can find an
${\mathbf x}\in\partial \Omega$
and $n(j)\rightarrow\infty$ such that
${\mathbf x}_{n(j)}\rightarrow{\mathbf x}$. By continuity
\[\phi({\mathbf x})\geq \phi({\mathbf t})\]
for all ${\mathbf t}\in\Cl\Omega$.
\end{proof}
\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{proof}[Solution]
The map $z\mapsto|f(z)|$ is continuous so, by compactness,
there exists a $z_{0}=x_{0}+iy_{0}\in \Cl\Omega$ with
$|f(z_{0})|\geq |f(z)|$ for all $z\in\Cl\Omega$. By replacing
$f(z)$ by $e^{i\theta}f(z)$, we may assume that $f(z_{0})$ is real
and positive.
Write $f(x+iy)=u(x,y)+iv(x,y)$ with $u$ and $v$ real. We have
\[u(x_{0},y_{0})=|f(z_{0})|\geq |f(x+iy)|\geq u(x,y)\]
and $u$ satisfies Laplace's equation. Thus there exists
a $x_{1}+iy_{1}=z_{1}\in \partial\Omega$ such that
$u(x_{1},y_{1})=u(x_{0},y_{0})$ and so $|f(z_{1})|\geq|f(z)|$
for all $z\in\Cl\Omega$.
\end{proof}
\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}
\begin{proof} Observe that,
if $\tau=\phi-\psi$, then $\tau$ satisfies the conditions
of Theorem~\ref{T;down Laplace} and so attains its maximum
on $\partial \Omega$. But $\tau=0$ on $\partial\Omega$. Thus
$\tau({\mathbf x})\leq 0$ for ${\mathbf x}=\Cl\Omega$. The same argument
applied to $-\tau$ shows that
$-\tau({\mathbf x})\leq 0$ for ${\mathbf x}=\Cl\Omega$.
Thus $\tau=0$ on $\Cl\Omega$ and we are done.
\end{proof}
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 is 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 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 $00$ and $B({\mathbf x},\delta)\subseteq\Omega$.
Thus $\Omega$ is open.
Observe that $(0,1/n)\rightarrow (0,0)$, so
${\boldsymbol 0}\in\Cl\Omega$. Again, if $\|{\mathbf x}\|=1$,
then $(1-1/n){\mathbf x}\rightarrow{\mathbf x}$, so
${\mathbf x}\in\Cl\Omega$. Thus
$\Cl\Omega\supseteq\bar{B}({\boldsymbol 0},1)$. Since
$\bar{B}({\boldsymbol 0},1)$ is closed
$\Cl\Omega=\bar{B}({\boldsymbol 0},1)$.
Finally,
\[\partial\Omega=\Cl \Omega\setminus\Int\Omega
=\Cl \Omega\setminus\Omega=
\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|=1\}
\cup\{{\boldsymbol 0}\}.\]
(ii) Let $T$ be a rotation with centre the origin.
If $\psi=\phi T$, then (using the chain rule if you do not know
the result already from applied courses)
\[\triangledown^{2}\psi=0.\]
But
\[\psi({\mathbf x})
=\begin{cases}
0&\text{if $\|{\mathbf x}\|=1$},\\
1&\text{if ${\mathbf x}={\boldsymbol 0}$}.
\end{cases}
\]
Thus, by uniqueness, $\psi=\phi$ and so,
since $T$ was an arbitrary rotation,
\[\phi({\mathbf x})=f(\|{\mathbf x}\|)\]
for some function $f:[0,1]\rightarrow {\mathbb R}$.
(iii) The chain rule gives
\[\frac{\partial \phi}{\partial x}
=f'(r)\frac{x}{r}
\ \text{and}
\ \frac{\partial^{2} \phi}{\partial x^{2}}
=f''(r)\frac{x^{2}}{r^{2}}+f'(r)\left(\frac{1}{r}-\frac{x^{2}}{r^{3}}
\right)\]
so, using the parallel result for derivatives with respect to $y$,
\[\triangledown^{2}\phi=f''(r)+f'(r)r^{-1}
=r^{-1}\frac{d\ }{dr}\big(rf(r)\big).\]
(Or we can just quote this result from applied courses.)
Thus
\[\frac{d\ }{dr}\big(rf(r)\big)=0\]
so $rf'(r)=B$ and $f(r)=A+B\log r$ for appropriate
constants $A$ and $B$.
(iv) We need $f(r)\rightarrow 1$ as $r\rightarrow 0+$,
so $B=0$ and $A=1$. This gives $f(1)=1$, contradicting
the condition
$\phi({\mathbf x})
=0$ if $\|{\mathbf x}\|=1$.
\end{proof}
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
holds 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}
\begin{proof} Observe that
$f=g^{-1}Fg$ is a continuous function from $\bar{D}$
to $\bar{D}$ and so, by Theorem~\ref{T;fix disc},
has a fixed point $w$. Set $a=g(w)$.
\end{proof}
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}
\begin{proof}
\noindent{(i)$\Rightarrow$ (ii)} Suppose, if possible, that there
exists a continuous function $g:{\bar D}\rightarrow\partial D$
with $g({\mathbf x})={\mathbf x}$ for all ${\mathbf x}\in \partial D$.
If $T$ is a rotation through $\pi$ about ${\boldsymbol 0}$,
then $f=T\circ g$ is a continuous function from ${\bar D}$
to itself with no fixed points, contradicting~(i).
\noindent{(ii)$\Rightarrow$ (i)} Suppose, if possible, that
$f:{\bar D}\rightarrow {\bar D}$ is a continuous function
with no fixed points. If we define
\[E=\{({\mathbf x},{\mathbf y})\in {\bar D}^{2}
\,:\,{\mathbf x}\neq{\mathbf y}\}\]
and $u:E\rightarrow \partial D$ by taking $u({\mathbf x},{\mathbf y})$ to be the
point where the straight line joining ${\mathbf x}$ to ${\mathbf y}$ in the
indicated direction cuts $\partial D$ then $u$ is continuous.
(We shall take this as geometrically obvious.
The algebraic details are messy
(but made easier if you use the fact
that the composition of continuous functions is continuous).
The really conscientious student
can do Exercise~\ref{A1.14}.)
Using the chain rule for continuous functions, we see that
\[g({\mathbf x})=u\big({\mathbf x},f({\mathbf x})\big)\]
defines a retraction mapping from $\bar{D}$ to $\partial D$,
contradicting (ii).
\end{proof}
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}
\begin{proof}
\noindent{(i)$\Rightarrow$(ii)} Suppose, if possible,
that $\tilde{k}$ exists with
the properties stated in (ii), Then,
if $T$ is a rotation through $\pi$,
about ${\boldsymbol 0}$,
we see that $f=T\circ\tilde{k}$ is a continuous map from $\bar{D}$
to $\bar{D}$
without a fixed point. By Theorem~\ref{T;Brouwer retracts}
this contradicts (i).
\noindent{(ii)$\Rightarrow$(i)} If $\tilde{k}$ is a continuous retract
from $\bar{D}$ to $\partial D$, then it certainly satisfies (ii).
\noindent{(iii)$\Leftrightarrow$(ii)} We use an argument of the type used for
Lemma~\ref{L;fix you}.
\end{proof}
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}
\begin{proof}[Lemma~\ref{L;colour me}]
\noindent{(ii)$\Rightarrow$(i)} Let $h:{\bar T}\rightarrow{\partial T}$
be continuous with $h(I)\subseteq I$, $h(J)\subseteq J$,
$h(K)\subseteq K$. Let $A=h^{-1}(I)$, $B=h^{-1}(J)$, $C=h^{-1}(K)$.
Since $h$ is continuous $A$, $B$ and $C$ are closed. Since
$I\cup J\cup K={\partial D}$, $A\cup B\cup C={\bar D}$.
But
\[A\cap B\cap C=h^{-1}(I)\cap h^{-1}(J)\cap h^{-1}(K)=
h^{-1}(I\cap J\cap K)=h^{-1}(\emptyset)=\emptyset\]
contradicting~(ii).
\noindent{(i)$\Rightarrow$(ii)}
Suppose that $A$, $B$ and $C$ are closed subsets of $T$ with
$A\supseteq I$, $B\supseteq J$, $C\supseteq K$,
$A\cup B\cup C=T$,
and $A\cap B\cap C=\emptyset$.
We consider $T$
as the triangle
\[T=\{(x,y,z)\in{\mathbb R}^{3}\,:\,
x+y+z=1,\ x,\,y,\,z\geq 0\}.\]
(In my school days we called these `barycentric
coordinates'\index{barycentric coordinates}.) If ${\mathbf x}\in T$, we know that
${\mathbf x}$ lies in at most two of the sets $A$, $B$
and $C$ so (by Lemma~\ref{L;distance closed})
at least one of $d({\mathbf x},A)$, $d({\mathbf x}, B)$
and $d({\mathbf x}, C)$ is non-zero. Thus
\[h({\mathbf x})=\frac{1}
{d({\mathbf x},A)+d({\mathbf x}, B)
+d({\mathbf x}, C)}
{\big(d({\mathbf x},A),d({\mathbf x}, B),d({\mathbf x}, C)\big)}\]
defines a continuous function $h:T\rightarrow T$.
If ${\mathbf x}\in I$, then $d({\mathbf x},A)=0$
and so $h({\mathbf x})\in I$. Similarly
$h(J)\subseteq J$ and $h(K)\subseteq K$
contradicting (i).
\end{proof}
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}
\begin{proof} Given
an edge of the grid joining vertices $u$
and $v$ we assign a value $E(u,v)$ to the edge
by a rule which ensures that, if $u$ and $v$
have the same colour, $E(u,v)=0$, if $u$ and $v$,
have different colours $X$ and $Y$, then
$E(u,v)=\zeta(X,Y)$ with $\zeta(X,Y)=-\zeta(Y,X)$
and $\zeta(X,Y)=\pm 1$.
This table which follows gives an example.
\begin{center}
\begin{tabular}{ccc}
colour $u$&colour $v$&$E(u,v)$\\
R&R&0\\
R&G&1\\
R&B&-1\\
G&R&-1\\
G&G&0\\
G&B&1\\
B&R&1\\
B&G&-1\\
B&B&0
\end{tabular}
\end{center}
If $uvw$ is a grid triangle then, by inspection, the sum of the
edge values (going round anticlockwise) is zero unless
all of the vertices have different colours. By considering
internal cancellation, the total sum of the edge values
is the sum of the edge values going round the outer edge
and this is non-zero. Thus one of the grid triangles
must have all three vertices of different colours.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;colour me}~(ii)]
Suppose that $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$.
Take a triangular grid formed by $n$ equally spaced
parallel lines for each of the three sides dividing
$T$ into a grid of congruent triangles. Colour the
vertices red, blue or green so that
all the red vertices lie in $A$, all the blue vertices
lie in $B$ and all the green vertices lie in $C$,
making sure that the outside edges are coloured
as required by Lemma~\ref{L;Sperner}.
Lemma~\ref{L;Sperner} tells us that there is a grid
triangle with vertex ${\mathbf a}_{n}$ red, so in $A$,
vertex ${\mathbf b}_{n}\in B$ and ${\mathbf c}_{n}\in C$.
By compactness, we can find $n(j)\rightarrow\infty$
and ${\mathbf x}\in T$ such that
${\mathbf a}_{n(j)}\rightarrow {\mathbf x}$
and so
${\mathbf b}_{n(j)}\rightarrow {\mathbf x}$,
${\mathbf c}_{n(j)}\rightarrow {\mathbf x}$.
Since $A$, $B$ and $C$ are closed
${\mathbf x}\in A\cap B\cap C$,
so $A\cap B\cap C\ne\emptyset$
\end{proof}
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}
\begin{proof}[Solution]
$T$ is a closed triangle in the appropriate plane.
If ${\mathbf X}\in T$ and we write ${\mathbf y}=T{\mathbf x}$,
then $y_{i}\geq 0$ and
\[
\sum_{i=1}^{3}y_{i}=\sum_{i=1}^{3}\sum_{j=1}^{3}a_{ij}x_{j}
=\sum_{j=1}^{3}\sum_{i=1}^{3}a_{ij}x_{j}\\
=\sum_{j=1}^{3}x_{j}=1,
\]
so ${\mathbf y}\in T$. Thus $T$ is a continuous map of $T$ into itself
and has a fixed point ${\mathbf e}$.
We observe that ${\mathbf e}$
is an eigenvector lying in $T$ with eigenvalue $1$.
\end{proof}
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
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}\]
In 1B 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}
\begin{proof}
Let ${\tilde E}=\{(p,1-p,q,1-q)\,:\,0\leq p,q\leq 1\}$.
(Thus ${\tilde E}$ is
a two dimensional square embedded in ${\mathbb R}^{4}$.)
Suppose $({\mathbf p},{\mathbf q})\in {\tilde E}$. Write
\[u_{1}({\mathbf p},{\mathbf q})=
\max\{0,A(1,0,{\mathbf q})-A({\mathbf p},{\mathbf q})\}.\]
Thus $u_{1}$ is Albert's expected gain if,
instead of choosing ${\mathbf p}$
when Bertha chooses ${\mathbf q}$, he chooses $(1,0)$ and
Bertha maintains her choice \emph{provided this is positive}
and $u_{1}$ is zero otherwise. Similarly
\[u_{2}({\mathbf p},{\mathbf q})=
\max\{0,A(0,1,{\mathbf q})-A({\mathbf p},{\mathbf q})\},\]
so $u_{2}$ is Albert's expected gain if,
instead of choosing ${\mathbf p}$
when Bertha chooses ${\mathbf q}$, he chooses $(0,1)$ and
Bertha maintains her choice \emph{provided this is positive}
and $u_{2}$ is zero otherwise.
In the same way, we take
\[v_{1}({\mathbf p},{\mathbf q})=
\max\{0,B({\mathbf p},1,0)-B({\mathbf p},{\mathbf q})\}.\]
and
\[v_{2}({\mathbf p},{\mathbf q})=
\max\{0,B({\mathbf p},0,1)-B({\mathbf p},{\mathbf q})\}.\]
Now define
\[g({\mathbf p},{\mathbf q})=({\mathbf p}',{\mathbf q}')\]
with
\[{\mathbf p}'=\frac{{\mathbf p}+{\mathbf u}({\mathbf p},{\mathbf q})}
{1+u_{1}({\mathbf p},{\mathbf q})+u_{2}({\mathbf p},{\mathbf q})}\]
and
\[{\mathbf q}'=\frac{{\mathbf q}+{\mathbf v}({\mathbf p},{\mathbf q})}
{1+v_{1}({\mathbf p},{\mathbf q})+v_{2}({\mathbf p},{\mathbf q})}.\]
We observe that $g$ is a well defined continuous function from
${\tilde E}$ into itself and so
has a fixed point $({\mathbf p}^{*},{\mathbf q}^{*})$.
We claim that $({\mathbf p}^{*},{\mathbf q}^{*})$ is a Nash stable point.
Suppose, if possible, that
$A\big((r,1-r),{\mathbf q}^{*}\big)>A\big((p^{*},1-p^{*}),{\mathbf q}^{*}\big)$.
Without loss of generality, we may suppose that $r>p^{*}$ so that
\[A\big((1,0),{\mathbf q}^{*}\big)>A\big((p^{*},1-p^{*}),{\mathbf q}^{*}\big)\]
and
\[A\big((0,1),{\mathbf q}^{*}\big)0$ and
$u_{2}({\mathbf p}^{*},{\mathbf q}^{*})=0$, whence ${\mathbf p}^{*}=(1,0)$
and $u_{1}({\mathbf p}^{*},{\mathbf q}^{*})=0$ which contradicts our earlier
assertion.
We have shown that
\[A\big({\mathbf p}^{*},{\mathbf q}^{*}\big)
\geq A\big((p,1-p),{\mathbf q}^{*}\big)\]
for all $1\geq p\geq 0$. The same argument shows that
\[B\big({\mathbf p}^{*},{\mathbf q}^{*}\big)
\geq B\big({\mathbf p}^{*},(q,1-q)\big)\]
for all $1\geq q\geq 0$ so we are done.
\end{proof}
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]} 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}
\begin{proof}[Solution] Suppose that $A$ swerves with probability $a$
and $B$ with probability $b$. The value of the game to $A$ is
\[V(a,b)=-ab+10(1-a)b-5a(1-b)-100(1-a)(1-b).\]
If $00$,
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 above is closed
bounded and convex.
\end{exercise}
\begin{proof}[Solution]
If ${\mathbf x}',\,{\mathbf y}'\in E'$
and $0\leq t\leq 1$, then
\[x_{j}'=a_{j}x_{j}+b_{j},\ y_{j}'=a_{j}y_{j}+b_{j}\]
with ${\mathbf x},\,{\mathbf y}\in E$
and so
\[tx_{j}'+(1-t)y_{j}'=a_{j}(tx_{j}+(1-t)y_{j})+b_{j}\]
for all $j$. But $t{\mathbf x}+(1-t){\mathbf y}\in E$,
since $E$ is convex,
so $t{\mathbf x}'+(1-t){\mathbf y}'\in E'$
and is convex.
We now recall Theorem~\ref{T;Compact image}
and observe that
$E'$ is the continuous image of a compact set so compact.
\end{proof}
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{proof} If ${\mathbf x}\in K$ and $0\leq t\leq 1$,
then, since
${\mathbf 1}\in K$ and $K$ is convex, we have
\[(1-t){\mathbf 1}+t{\mathbf x}\in K\] so, by our hypothesis,
\begin{align*}
1&\geq \prod_{j=1}^{n}\big(tx_{j}+(1-t)\big)=\prod_{j=1}^{n}\big(1+t(x_{j}-1)\big)\\
&=1+t\sum_{j=1}^{n}(x_{j}-1)+t^{2}P(t)
\end{align*}
where $P$ is a polynomial with coefficients depending on ${\mathbf x}$.
It follows that, if $0\leq t\leq 1$, we have
\[0\geq \sum_{j=1}^{n}(x_{j}-1)+tP(t).\]
Allowing $t\rightarrow 0+$ gives
\[0\geq \sum_{j=1}^{n}(x_{j}-1),\]
which is the desired result.
\end{proof}
\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}
\begin{proof}
The Nash conditions mean that the problem is
invariant under affine transformation
(i.e. transformations of the type discussed in
Exercise~\ref{E;Convex transform}).
Thus we may assume that ${\mathbf s}={\boldsymbol 0}$.
If the hyperboloid $\prod_{j=1}^{n} y_{j}=K$
touches the convex set $E'$ at ${\bf y}$ (with $y_{j}>0$)
then the transformation $x_{j}=K^{-1/n}y_{j}/y_{j}^{*}$
gives a hyperboloid $\prod_{j=1}^{n} x_{j}=1$
touching a convex set $E$ at $(1,1,\ldots,1)$.
Thus we may assume that ${\mathbf s}={\boldsymbol 0}$
and
$x_{1}^{*}=x_{2}^{*}=\dots=x_{n}^{*}=1$.
By Lemma~\ref{L;push to one side}, we have
\[K\subseteq L=\{{\mathbf x}:\sum_{j=1}^{n}x_{j}\leq n\},\]
and, by the independence of irrelevant alternatives,
if ${\mathbf x}^{*}$ is best for $L$, it is best for $K$.
Now $L$ is symmetric so any best point ${\mathbf x}$ for $L$
must lie on $x_{1}=x_{2}=\ldots=x_{n}$. But, amongst these points, only
${\mathbf x}^{*}$ is Pareto optimal so we are done.
\end{proof}
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}
\begin{proof}[Lemma~\ref{L;pushier}] By compactness, there is
a point ${\mathbf x}^{*}$ where $f$ attains its maximum. By
translation, we may suppose ${\mathbf s}={\boldsymbol 0}$
and, re-scaling the axes, we may suppose
${\mathbf x}^{*}={\mathbf e}=(1,1,\ldots,1)$.
Lemma~\ref{L;push to one side} tells us that
\[\{{\mathbf k}\in K\,:\,k_{j}\geq 0\ \forall j\}\subseteq
\{{\mathbf x}\in K\,:\,x_{j}\geq 0\ \forall j
\ \text{and}\ x_{1}+x_{2}+\ldots+x_{n}=n\}.\]
The uniqueness of the maximum now follows from the conditions
for equality in the arithmetic geometric inequality.
\end{proof}
`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.)
\begin{proof}[Solution for Exercise~\ref{E;Cauchy example}]
(i) We use induction on $n$ to show that $E$ is $n$
times differentiable with
\[E^{(n)}(t)=P_{n}(1/t)E(t)\]
for all $t\neq 0$ and some polynomial $P_{n}$.
The result is certainly true for $n=0$ with $P_{0}=1$.
If it is true for $n=m$, then the standard rules for
differentiation show that $E^{(m)}$ is differentiable with
\[E^{(m+1)}(t)=t^{-2}P_{m}'(1/t)E(t)-2t^{-3}P_{m}(1/t)E(t)=P_{m+1}(1/t)E(t)\]
for all $t\neq 0$ and the polynomial
$P_{m+1}(s)=s^{2}P_{m}'(s)-2s^{3}P_{m}(s)$.
(ii) We use induction on $n$ to show that $E$ is $n$
times differentiable at $0$ with
\[E^{(n)}(0)=0.\]
The result is true for $n=0$.
If it is true for $n=m$, then
\[\frac{E^{(m)}(h)-E^{(m)}(0)}{h}=h^{-1}P(h^{-1})E(h)\rightarrow 0\]
as $h\rightarrow 0$, so it is true for $n=m+1$.
(iii) We have
\[E(t)\neq 0=\sum_{n=0}^{\infty}\frac{0}{n!}t^{n}
=\sum_{n=0}^{\infty}\frac{E^{(n)}(0)}{n!}t^{n}\]
for all $t\neq 0$, as stated.
\end{proof}
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}
\begin{proof}
(i) If $P$ and $Q$ have degree at most $n$
and
\[P(x_{j})=Q(x_{j})=f(x_{j})\]
for $0\leq j\leq n$,
then $P-Q$ is a polynomial of degree at most $n$
vanishing at at least $n+1$ points. Thus $P-Q=0$,
by Exercise~\ref{E;roots}, so $P=Q$.
(ii) We observe that $e_{j}(x_{i})=1$ if $i=j$, but
$e_{j}(x_{i})=0$ otherwise and that $e_{j}$ is a
polynomial of degree $n$. Thus
\[P=\sum_{j=0}^{n}f(x_{j})e_{j}\]
is a polynomial of degree at most $n$ with
\[P(x_{i})=\sum_{j=0}^{n}f(x_{j})e_{j}(x_{i})
=f(x_{i})\]
for $0\leq i\leq n$.
(iii) It is easy to check that ${\mathcal P}_{n}$
is a vector space. Part~(ii) shows that the $e_{j}$ span
${\mathcal P}_{n}$. If
\[\sum_{j=0}^{n}\lambda_{j}e_{j}=0,\]
then
\[\lambda_{i}=\sum_{j=0}^{n}\lambda_{j}e_{j}(x_{i})=0\]
for each $i$, so the the $e_{j}$
are linearly independent.
\end{proof}
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}
\begin{proof}
By de Moivre's theorem,
\begin{align*}
\cos& n\theta+i\sin n\theta=(\cos\theta+i\sin\theta)^{n}\\
&=\sum_{r=0}^{n}i^{r}\binom{n}{r}(\cos\theta)^{n-r}(\sin \theta)^{r}\\
&=\sum_{0\leq 2r\leq n}(-1)^{r}
\binom{n}{2r}(\cos\theta)^{n-2r}(\sin \theta)^{2r}\\
&\qquad\qquad+i\sin\theta\sum_{0\leq 2r\leq n-1}(-1)^{r}
\binom{n}{2r+1}(\cos\theta)^{n-1-2r}(\sin \theta)^{2r}\\
&=\sum_{0\leq 2r\leq n}(-1)^{r}
\binom{n}{2r}(\cos\theta)^{n-2r}\big(1-(\cos\theta)^{2}\big)^{r}\\
&\qquad\qquad+i\sin\theta\sum_{0\leq 2r\leq n-1}(-1)^{r}
\binom{n}{2r+1}(\cos\theta)^{n-1-2r}\big(1-(\cos \theta)^{2}\big)^{r}\\
&=T_{n}(\cos\theta)+i\sin\theta U_{n-1}(\cos\theta),
\end{align*}
where $T_{n}$ is a polynomial of degree at most $n$
and $U_{n-1}$ a polynomial of degree at most $n-1$.
Taking real and imaginary parts, we obtain
\[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$, $U_{n-1}(1)=n$, $U_{n-1}(-1)=(-1)^{n-1}n$ .
The roots of $U_{n-1}$ and $T_{n}$ can be read off
directly and show that the two polynomials have full
degree.
The coefficient of $t^{n}$ in $T_{n}$ is
\[\sum_{0\leq 2r\leq n}\binom{n}{2r}
=\frac{1}{2}\big((1+1)^{n}+(1-1)^{n}\big)=2^{n-1}\]
for $n\geq 1$.
\end{proof}
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}
\begin{proof}[Solution]
The key result that we use in (i) and (ii) is
that, if $f\in C([0,1])$, $f(t)\geq 0$ for all $t\in[0,1]$
and $\int_{0}^{1}|f(t)|\,dt=0$, then
$f(t)=0$ for all $t\in[0,1]$.
(i) Observe that
\[\|f\|_{1}=\int_{0}^{1}|f(t)|\,dt\geq 0\]
and that, if $\|f\|_{1}=0$, then
\[\int_{0}^{1}|f(t)|\,dt=0,\]
so $|f(t)|=0$ for
all $t$, so $f(t)=0$ for all $t$ and $f=0$.
Further
\[\|\lambda f\|_{1}=\int_{0}^{1}|\lambda||f(t)|\,dt
=|\lambda|\int_{0}^{1}|f(t)|\,dt=|\lambda|\|f\|_{1}\]
and, since $|f(t)+g(t)|\leq |f(t)|+|g(t)|$, we have
\[\|f+g\|_{1}=\int_{0}^{1}|f(t)+g(t)|\,dt
\leq \int_{0}^{1}|f(t)|+|g(t)|\,dt=\|f\|_{1}+\|g\|_{1},\]
so we have a norm.
(ii) We have
\[\langle f,f\rangle=\int_{0}^{1}f(t)^{2}\,dt\geq 0.\]
If $\langle f,f\rangle=0$, then $\int_{0}^{1}f(t)^{2}\,dt=0$,
so $f(t)^{2}=0$ for
all $t$, so $f(t)=0$ for all $t$ and $f=0$.
We have
\[
\langle f,g\rangle=\int_{0}^{1}f(t)g(t)\,dt
=\int_{0}^{1}g(t)f(t)\,dt
=\langle g,f \rangle\]
and
\begin{align*}
\langle f+g,h\rangle
&=\int_{0}^{1}(f(t)+g(t))h(t)\,dt\\
&=\int_{0}^{1}f(t)h(t)\,dt+\int_{0}^{1}g(t)h(t)\,dt
=\langle f,h\rangle
+\langle g,h\rangle
\end{align*}
whilst
\[\langle\lambda f,g\rangle
=\int_{0}^{1}\lambda f(t)g(t)\,dt
=\lambda\int_{0}^{1}f(t)g(t)\,dt
=\lambda\langle f,g\rangle,\]
so we have an inner product.
(iii) Observe that $|f(t)|\geq 0$,so
\[\|f\|_{\infty}=\sup_{t\in[0,1]}|f(t)|\geq 0,\]
that
\[\|f\|_{\infty}=0\Rightarrow\sup_{t\in[0,1]} |f(t)|=0
\Rightarrow |f(t)|=0\ \forall t\Rightarrow f=0,\]
that
\[\|\lambda f\|_{\infty}=\sup_{t\in[0,1]}|\lambda f(t)|
=\sup_{t\in[0,1]}|\lambda||f(t)|=|\lambda|\sup_{t\in[0,1]}|f(t)|
=\lambda \|f\|_{\infty},\]
and, that, since $|f(t)+g(t)|\leq |f(t)|+|g(t)|$,
\begin{align*}
\|f+g\|_{\infty}&=\sup_{t\in[0,1]}|f(t)+g(t)|
\leq \sup_{t\in[0,1]}(|f(t)|+|g(t)|)\\
&\leq \sup_{t,s\in[0,1]}(|f(t)|+|g(s)|)=\|f\|_{\infty}+\|g\|_{\infty},
\end{align*}
so we are done.
The Cauchy--Schwarz inequality gives
\[\|f\|_{2}=\|f\|_{2}\|1\|_{2}\geq\langle |f|,1\rangle=\|f\|_{1}.\]
First year analysis gives
\[\|f\|_{\infty}=\|f^{2}\|^{1/2}_{\infty}
=\left(\int_{0}^{1}f(t)^{2}\,dt\right)^{1/2}=\|f\|_{1}.\].
If $f_{n}$ is as stated, $\|f_{n}\|_{1}=2\int_{0}^{1/n}nt\,dt=1/n$,
$\|f_{n}\|_{\infty}=1$ and
\[\|f_{n}\|_{2}=\left(2\int_{0}^{1/n}(nt)^{2}\,dt\right)^{1/2}
=\left(\frac{2}{3n}\right)^{1/2}.\]
Thus
$\|f_{n}\|_{\infty}/\|f_{n}\|_{1}=n\rightarrow\infty$
and $\|f_{n}\|_{1}/\|f_{n}\|_{2}=(3/2)^{1/2}n^{1/2}\rightarrow\infty$
as $n\rightarrow\infty$. We have genuinely different
measures of difference.
\end{proof}
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}
\begin{proof}
Suppose that $f$ is not uniformly continuous.
Then we can find an $\epsilon>0$
and ${\mathbf x}_{n},\,{\mathbf y}_{n}\in E$ such that
\[\|{\mathbf x}_{n}-{\mathbf y}_{n}\|\leq 1/n
\ \text{and}\ \|f({\mathbf x}_{n})-f({\mathbf y}_{n})\|\geq \epsilon.\]
By compactness, we can find ${\mathbf e}\in E$
and $n(j)\rightarrow\infty$ such that
${\mathbf x}_{n(j)}\rightarrow{\mathbf e}$.
The triangle inequality tells us that
${\mathbf y}_{n(j)}\rightarrow{\mathbf e}$
and so
\[\|f({\mathbf x}_{n(j)})-f({\mathbf y}_{n(j)})\|
\leq \|f({\mathbf x}_{n(j)})-f({\mathbf e})\|+
\|f({\mathbf y}_{n(j)})-f({\mathbf e})\|
\rightarrow 0+0=0.\]
We have a contradiction.
\end{proof}
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{proof} By replacing $X$ by $Y=X-{\mathbb E}X$,
we may suppose that ${\mathbb E}X=0$.
Let
\[{\mathbb I}_{{\mathbb R}\setminus (-a,a)}(t)=
\begin{cases}0&\text{if $|t|0$. By uniform continuity we can find
an $\eta>0$ such that $|f(t)-f(s)|\leq\epsilon$ for $|t-s|\leq\eta$
and $t,\,s\in[0,1]$. Thus, using Chebychev's inequality,
\begin{align*}
|p_{n}(t)-f(t)|&=\big|{\mathbb E}\big(f(Y_{n})-f(t)\big)\big|
\leq {\mathbb E}|f(Y_{n})-f(t)|\\
&\leq \epsilon\Pr(|Y_{n}-t|<\eta)+2\|f\|_{\infty}\Pr(|Y_{n}-t|\geq\eta)\\
&\leq \epsilon+2\|f\|_{\infty}\Pr(|Y_{n}-{\mathbb E}Y_{n}|\geq\eta)\\
&\leq \epsilon+2\|f\|_{\infty}\eta^{-2}/n\leq 3\epsilon,
\end{align*}
provided only that $n\geq \epsilon^{-1}(2\|f\|+1)\eta^{-2}$. Since
$\epsilon$ is arbitrary, the result follows.
\end{proof}
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}
\begin{proof}
Without loss of generality, suppose that
\[f(a_{j})-P(a_{j})=(-1)^{j}\sigma\ \text{for all $0\leq j\leq n$}.\]
Suppose, if possible, that $Q$ is a polynomial of degree
$n-1$ or less such that $\|P-f\|_{\infty}>\|Q-f\|_{\infty}$.
We look at $R=P-Q$. Note first that $R$ is a polynomial of degree
at most $n-1$. If $j$ is odd,
\begin{align*}
R(a_{j})&=\big(P(a_{j})-f(a_{j})\big)+\big(f(a_{j})-Q(a_{j})\big)\\
&=|P(a_{j})-f(a_{j})|+\big(f(a_{j})-Q(a_{j})\big)\\
&\geq |P(a_{j})-f(a_{j})|-\|Q-f\|_{\infty}
=\|P-f\|_{\infty}-\|Q-f\|_{\infty}>0.
\end{align*}
and a similar argument shows that
\[R(a_{j})<0\]
when $j$ is even.
The intermediate value theorem now tells that $R$ has at least $n$
zeros, so $R=0$ and $P=Q$, contradicting our initial assumption.
\end{proof}
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{proof}
If $t=\cos\theta$, then
\[t^{n}-S_{n}(t)=2^{1-n}T_{n}(t)=2^{1-n}\cos n\theta\]
Thus
\[|t^{n}-S_{n}(t)|\leq 2^{1-n}\]
for $t\in [-1,1]$ and
\[t^{n}-S_{n}(t)=(-1)^{j}2^{1-n}\]
for $t=\cos j\pi/n$ $[0\leq j\leq n]$.
The stated result now follows from the equiripple criterion.
\end{proof}
\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}
\begin{proof}
(i) This is just a restatement of Theorem~\ref{T;nice Chebychev}.
(ii) Let $\Gamma(n)$ be the statement given in (ii)
with the extra condition $\epsilon_{n}\leq 1$.
$\Gamma(0)$ is true with $\epsilon_{0}=1$ by inspection.
Suppose that $\Gamma_{n}$ is true, that
$P(t)=\sum_{j=0}^{n+1}a_{j}t^{j}$
is a polynomial of degree at most $n+1$,
and that $|a_{k}|\geq 1$ for some
$n+1\geq k\geq 0$. If $|a_{n+1}|\leq\epsilon_{n}/2$,
then
\[P(t)=a_{n+1}t^{n+1}+Q(t)\]
where $Q(t)=\sum_{j=0}^{n}a_{j}t^{j}$
is a polynomial of degree at most $n+1$ and $|a_{k}|\geq 1$ for some
$n\geq k\geq 0$. Thus
\[\|P\|_{\infty}\geq\|Q\|_{\infty}-|a_{n+1}|\geq \epsilon_{n}/2.\]
On the other hand, if $|a_{n+1}|\geq\epsilon_{n}/2$,
then part~(i) tells us that
\[\|P\|_{\infty}\geq 2^{-n+1}\epsilon_{n}/2=2^{-n}\epsilon_{n}.\]
Thus, whatever the value of $a_{n+1}$,
\[\|P\|_{\infty}\geq 2^{-n-1}\epsilon_{n}\]
and $\Gamma(n+1)$ holds with $\epsilon_{n+1}=2^{-n-1}\epsilon_{n}$.
The required result holds by induction.
\end{proof}
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}
\begin{proof}
By rescaling and translation, we may suppose
that $[a,b]=[-1,1]$.
Consider the map $F:{\mathbb R}^{n+1}\rightarrow{\mathbb R}$
given by $F({\mathbf a})=\|f-Q\|_{\infty}$ where
\[Q(t)=\sum_{j=0}^{n}a_{j}t^{j}.\]
Recalling the inequality
$\big||d(f,g)|-|d(f,h)|\big|\leq d(g,h)$, we have
\[|F({\mathbf a})-F({\mathbf b})|\leq\sup_{t\in[-1,1]}
\left| \sum_{j=0}^{n}a_{j}t^{j}-\sum_{j=0}^{n}b_{j}t^{j}\right|
\leq\sum_{j=0}^{n}|a_{j}-b_{j}|\leq (n+1)\|{\mathbf a}-{\mathbf b}\|,\]
so $F$ is continuous. Also
\[F({\mathbf a})\geq \sup_{t\in[-1,1]}
\left| \sum_{j=0}^{n}a_{j}t^{j}\right|-\|f\|_{\infty}\]
so, by Corollary~\ref{C;naught for naught}~(ii),
we can find a $K>0$ such that
\[{\mathbf a}\notin[-K,K]^{n+1}\Rightarrow
F({\mathbf a})\geq F({\boldsymbol 0}).\]
By compactness, $F$ attains a minimum at some point
${\mathbf p}\in [-K,K]^{n+1}$ and
\[P(t)=\sum_{j=0}^{n}p_{j}t^{j}\]
is the required polynomial.
\end{proof}
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}
\begin{proof}
As in Lemma~\ref{L;interpolate polynomial},
we take
\[e_{k}(x)=\prod_{j\neq k}\frac{x-x_{j}}{x_{k}-x_{j}}.\]
If
\[\int_{a}^{b}P(x)\,dx=\sum_{j=0}^{n}A_{j}P(x_{j})\]
for all polynomials of degree $n$ or less,
then, setting $P=e_{k}$, gives us
\[A_{k}=\int_{a}^{b}e_{k}(x)\,dx,\]
proving uniqueness.
On the other hand, if $P$ has degree $n$ or less,
\[Q=P-\sum_{j=0}^{n}P(x_{j})e_{j}\]
has degree $n$ or less but vanishes at the $n+1$
points $x_{j}$. Thus $Q=0$ and
\[P=\sum_{j=0}^{n}P(x_{j})e_{j},\]
whence
\[\int_{a}^{b}P(x)\,dx=\sum_{j=0}^{n}A_{j}P(x_{j})\]
with
\[A_{j}=\int_{a}^{b}e_{j}(x)\,dx.\]
\end{proof}
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 increase.
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}\]
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}
\begin{proof} Linear independence
shows that ${\mathbf v}\neq {\boldsymbol 0}$.
We have $\|{\mathbf e}_{n+1}\|=\|{\mathbf v}\|^{-1}\|{\mathbf v}\|=1$.
Now
\begin{align*}
\langle{\mathbf v},{\mathbf e}_{k}\rangle
&=\left\langle{\mathbf f}-\sum_{j=1}^{n}
\langle{\mathbf f},{\mathbf e}_{j}\rangle
{\mathbf e}_{j},{\mathbf e}_{k}
\right\rangle\\
&=\langle{\mathbf f},{\mathbf e}_{k}\rangle
-\sum_{j=1}^{n}
\langle{\mathbf f},{\mathbf e}_{j}\rangle
\langle{\mathbf e}_{k},{\mathbf e}_{j}\rangle\\
&=\langle{\mathbf f},{\mathbf e}_{k}\rangle
-\langle{\mathbf f},{\mathbf e}_{k}\rangle=0
\end{align*}
so
$\langle{\mathbf e}_{n+1},{\mathbf e}_{k}\rangle=0$
for all $1\leq k\leq n$.
\end{proof}
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.}.
(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}
\begin{proof} Suppose that $p_{n}$ has $k$ roots
$\alpha_{j}$ of \emph{odd} order
(that is to say the polynomial changes sign at the root) on $(-1,1)$.
If we set $Q(t)=\prod_{j=1}^{k}(t-\alpha_{j})$,
then $p_{n}(t)Q(t)$ is a continuous single
signed not everywhere zero function so
\[\int_{-1}^{1}Q(t)p_{n}(t)\,dt\neq 0.\]
Thus $Q$ has degree at least $n$, so $k\geq n$.
It follows that $k=n$ and all of the roots of $p_{n}$
are simple lying in $(-1,1)$.
\end{proof}
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}
\begin{proof}
(i) By long division, $Q=p_{n}S+T$, where $S$ and $T$
are polynomials of degree at most $n-1$. Thus
\begin{align*}
\int_{-1}^{1}&Q(x)\,dx=\int_{-1}^{1}S(x)p_{n}(x)\,dx+
\int_{-1}^{1}T(x)\,dx=\int_{-1}^{1}T(x)\,dx\\
&=\sum_{j=1}^{n}A_{j}T(\alpha_{j})
=\sum_{j=1}^{n}A_{j}T(\alpha_{j})
+\sum_{j=1}^{n}A_{j}p_{n}(\alpha_{j})S(\alpha_{j})
=\sum_{j=1}^{n}A_{j}Q(\alpha_{j}).
\end{align*}
(ii) Let $P(x)=\prod_{j=1}^{n}(x-\beta_{j})$.
If $R$ is a polynomial of degree $n-1$
or less,
then $RP$ has degree at most $2n-1$,
so
\[\int_{-1}^{1}R(x)P(x)\,dx
=\sum_{j=1}^{n}B_{j}R(\beta_{j})P(\beta_{j}).\]
Thus $\langle P,R\rangle=0$ for all polynomials
of degree $n-1$ or less, so $P$ is a scalar multiple
of the $n$th Legendre polynomial
$p_{n}$ and the $\beta_{j}$ are the roots $p_{n}$.
\end{proof}
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}
\begin{proof}
(i) Let
\[P_{k}(x)=\left(
\prod_{j\neq k}\frac{x-x_{j}}{x_{k}-x_{j}}\right)^{2}.\]
Then $P_{k}$ has degree $2n-2$, so
\[0<\int_{-1}^{1}P_{k}(x)\,dx=\sum_{j=1}^{n}A_{j}P_{k}(\alpha_{j})=A_{k}.\]
(ii) Taking $P=1$ in the formula, we obtain
\[2=\int_{-1}^{1}1\,dx=\sum_{j=1}^{n}A_{j}.\]
(iii) We have
\begin{align*}
\left|\int_{-1}^{1}f(x)\,dx\right.&\left.-
\sum_{j=1}^{n}A_{j}f(\alpha_{j})\right|\\
&=\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx-
\sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx\right|
+\left| \sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq \int_{-1}^{1}|f(x)-P(x)|\,dx
+\sum_{j=1}^{n}A_{j}|f(\alpha_{j})-P(\alpha_{j})|\\
&\leq 2\|f-P\|_{\infty}+\sum_{j=1}^{n}A_{j}\|f-P\|_{\infty}
\leq 4\|f-P\|_{\infty}.
\end{align*}
(iv) Let $\epsilon>0$.
By Weierstrass's theorem, we can find a polynomial
$P$ such that $\|f-P\|_{\infty}\leq\epsilon/4$.
Then, if $n$ is greater than the degree of $P$,
part~(iii) tells us that
\[\left|\int_{-1}^{1}f(x)\,dx-G_{n}f\right|\leq 4\|f-P\|_{\infty}
\leq\epsilon.\]
\end{proof}
\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}
\begin{proof}
It is a standard observation about metric spaces $(X,d)$
that, since
$d(x,y)+d(y,z)\geq d(x,z)$, we have
$d(y,z)\geq d(x,z)-d(x,y)$ and similarly
$d(y,z)=d(z,y)\geq d(x,y)-d(x,z)$, so that
\[d(y,z)\geq |d(x,z)-d(x,y)|.\]
Thus, if we write $f({\mathbf x})=
\|{\mathbf a}-{\mathbf x}\|$,
we have
\[|f({\mathbf x})-f({\mathbf y})|\leq\|{\mathbf x}-{\mathbf y}\|,\]
so $f$ is continuous and attains its minimum
on the compact set $E$.
\end{proof}
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{proof}[Solution]
(i) Consider $n=2$,
\[E=\{(x,y)\,:\,x^{2}+y^{2}=1\}
\ \text{and}\ {\mathbf e}={\boldsymbol 0}.\]
Any point of $E$ will do.
(ii) Suppose that $E$ is convex,
${\mathbf e},\ {\mathbf f}\in E$ and
$\|{\mathbf a}-{\mathbf e}\|=\|{\mathbf a}-{\mathbf f}\|$.
Then
\[\frac{{\mathbf e}+{\mathbf f}}{2}\in E\]
but the parallelogram law tells us that
\begin{align*}
4\|{\mathbf a}-{\mathbf e}\|^{2}&=
2\|{\mathbf a}-{\mathbf e}\|^{2}+\|{\mathbf a}-{\mathbf f}\|^{2}\\
&=\|({\mathbf a}-{\mathbf e})+({\mathbf a}-{\mathbf f})\|^{2}
+\|({\mathbf a}-{\mathbf e})-({\mathbf a}-{\mathbf f})\|^{2}\\
&=4\left\|{\mathbf a}-\frac{{\mathbf e}+{\mathbf f}}{2}\right\|^{2}
+\|{\mathbf e}-{\mathbf f}\|^{2}
\end{align*}
and so
\[\left\|{\mathbf a}-\frac{{\mathbf e}+{\mathbf f}}{2}\right\|
\leq \|{\mathbf a}-{\mathbf e}|\]
with equality only if ${\mathbf e}={\mathbf f}$.
(Alternatively draw a diagram and use a little school geometry
to obtain the same result.)
\end{proof}
\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}
\begin{proof}
(i) Recall that, if ${\mathbf u}\in{\mathbb R}^{n}$,
then we can find ${\mathbf v}\in F$ such that
$\|{\mathbf u}-{\mathbf v}\|=d({\mathbf u},F)$.
If ${\mathbf u}'\in{\mathbb R}^{n}$, then
\[d({\mathbf u}',F)\leq\|{\mathbf u}'-{\mathbf v}\|
\leq\|{\mathbf u}'-{\mathbf u}\|+\|{\mathbf u}-{\mathbf v}\|
=\|{\mathbf u}'-{\mathbf u}\|+d({\mathbf u},F).\]
The same argument shows that
$d({\mathbf u},F)\leq
\|{\mathbf u}'-{\mathbf u}\|+d({\mathbf u}',F)$.
Thus
\[|d({\mathbf u},F)-d({\mathbf u}',F)|\leq
\|{\mathbf u}'-{\mathbf u}\|.\]
and the map ${\mathbf u}\mapsto d({\mathbf u},F)$ is continuous.
By compactness, it attains its minimum on $E$
and this is the required result.
(ii) Chose ${\mathbf u}\in E$.
Since $F$ is bounded we can find an $R$
such that $B({\boldsymbol u},R)\supseteq F$. Let
\[E^{*}=\bar{B}({\mathbf u},2R+1)\cap E.\]
If ${\mathbf e}\in E\setminus E^{*}$, then
$d({\mathbf e},F)\geq d({\mathbf u},F)+1$.
Since $E^{*}$ is compact, part~(i) tells us that there
exist a ${\mathbf e}\in E^{*}$ and a ${\mathbf f}\in F$
such that
\[\|{\mathbf e}-{\mathbf f}\|=\inf_{{\mathbf y}\in E^{*}}d({\mathbf y},F)\]
and so by the previous paragraph
\[\|{\mathbf e}-{\mathbf f}\|=\inf_{{\mathbf y}\in E}d({\mathbf y},F)\]
(iii) Let $n=1$, $E=\{r+1/r\,:\,r\in{\mathbb Z},\ r\geq 2\}$
and $F=\{r\,:\,r\in{\mathbb Z},\ r\geq 2\}$.
We have $E$ and $F$ closed and $\tau(E,F)=0$, but
$|e-f|>0$ for all $e\in E$, $f\in F$.
\end{proof}
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}
\begin{proof}[Solution]
Repeat the counter-example of Exercise~\ref{E;unique convex 1}.
Take $n=2$,
\[E=\{(x,y)\,:\,x^{2}+y^{2}=1\},\ F=\{{\boldsymbol 0}\}.\]
\end{proof}
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}
\begin{proof}[Solution]
(i) follows directly from the definition.
(Alternatively take the ${\mathbf e}$ and
${\mathbf f}$ of Lemma~\ref{L;compact compact}~(i) and observe that
$\tau(E,f)=\|{\mathbf e}-{\mathbf f}\|\geq 0$.)
Lemma~\ref{L;compact compact}~(i) also shows that
\[\tau(F,E)\leq \|{\mathbf e}-{\mathbf f}\|=\tau(E,F).\]
Interchanging $E$ and $F$, yields $\tau(E,F)\leq\tau(F,E)$
so $\tau(E,F)=\tau(F,E)$.
If we work with $n=1$, setting $E=\{0\}$, $F=\{0,1\}$,
gives $\tau(E,F)=0$, but $E\neq F$.
If we work with $n=1$, then
setting $E=\{0\}$, $F=\{0,1\}$, $G=\{1\}$
gives $\tau(E,F)+\tau(F,G)=0+0=0$, but $\tau(E,g)=1$.
\end{proof}
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{proof}[Solution]
In our proof of Lemma~\ref{L;compact compact}~(i)
we showed that ${\mathbf u}\mapsto d({\mathbf u},F)$
is continuous. It follows that it attains its maximum on
the compact set $E$.
\end{proof}
\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}
\begin{proof}[Solution]
Since $d({\mathbf e},F)\geq 0$ for all ${\mathbf e}$,
we have $\sigma(E,F)\geq 0$.
If $n=1$, $E=\{0\}$, $F=[0,1]$, then
$\sigma(E,F)=0$, but $\sigma(F,E)=1$,
so conditions~(ii)
and~(iii) fail.
\[\sigma(E,F)=0
\Leftrightarrow d({\mathbf e},F)=0\ \forall {\mathbf e}\in E
\Leftrightarrow {\mathbf e}\in F\ \forall{\mathbf e}\in E
\Leftrightarrow E\subseteq F.\]
\end{proof}
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}
\begin{proof}[Lemma~\ref{L;start Hausdorff}]
Given ${\mathbf e}\in E$, we can find ${\mathbf f}\in F$
such that $\|{\mathbf e}-{\mathbf f}\|=d({\mathbf e},F)$.
If ${\mathbf g}\in G$, then
\begin{align*}
d({\mathbf e},G)
&\leq\|{\mathbf e}-{\mathbf g}\|\leq
\|{\mathbf e}-{\mathbf f}\|+\|{\mathbf f}-{\mathbf g}\|\\
&=d({\mathbf e},F)+\|{\mathbf f}-{\mathbf g}.\|
\end{align*}
Since ${\mathbf g}\in G$ was arbitrary,
\[d({\mathbf e},G)\leq d({\mathbf e},F)+d({\mathbf f},G)
\leq \sigma(E,F)+\sigma(F,G)\]
and so
\[\sigma(E,G)\leq \sigma(E,F)+\sigma(F,G).\]
\end{proof}
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}
\begin{proof}
Observe that
\begin{gather*}
\rho(E,F)=\sigma(E,F)+\sigma(F,E)\geq 0\\
\rho(E,F)=0\Leftrightarrow\sigma(E,F)=\sigma(F,E)=0
\Leftrightarrow E\subseteq F,\ F\subseteq E\Leftrightarrow E=F\\
\rho(E,F)=\sigma(E,F)+\sigma(F,E)
=\sigma(F,E)+\sigma(E,F)=\rho(F,E)\\
\rho(E,F)+\rho(F,G)
=\sigma(E,F)+\sigma(F,G)+\sigma(G,F)+\sigma(F,E)\\
\geq \sigma(E,G)+\sigma(G,E)=\rho(E,G),
\end{gather*}
as desired.
\end{proof}
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{proof} (i) This part may be familiar from~1B.
(Indeed the reader may
well be able to supply a more sophisticated
proof.) Since the intersection of
closed sets is closed and the intersection of bounded sets
is bounded we only have to show that $K$ is non-empty.
Choose
${\mathbf x}_{n}\in K_{n}$. Since $K_{1}$ is compact and
${\mathbf x}_{n}\in K_{1}$ for every $n$ we can find
an ${\mathbf x}\in K_{1}$ and $n(j)\geq j$ such
that ${\mathbf x}_{n(j)}\rightarrow{\mathbf x}$
(in the Euclidean metric) as $j\rightarrow\infty$.
Automatically,
\[{\mathbf x}_{n(j)}\in K_{n(j)}\subseteq K_{j}\subseteq K_{p}\]
for all $j\geq p$, so, since $K_{p}$ is closed,
${\mathbf x}\in K_{p}$ for all $p\geq 1$. It follows
that ${\mathbf x}\in K$ and $K$ is non-empty.
(ii) Since $K\subseteq K_{p}$ it follows
that
\[\rho(K,K_{p})=\sup_{{\mathbf e}\in K_{p}}\inf_{{\mathbf k}\in K}
\|{\mathbf e}-{\mathbf k}\|\]
and, in particular that $\rho(K,K_{p})$ is a decreasing
positive sequence.
Thus if $K_{p}\underset{\rho}{\nrightarrow}K$ there must exist an
$\eta>0$ with
\[\rho(K,K_{p})\geq 2\eta\]
and there must exist ${\mathbf k}_{p}\in K_{p}$
with
\[\|{\mathbf k}_{p}-{\mathbf k}\|\geq\eta\]
for all ${\mathbf k}\in K$.
Since $K_{1}$ is compact and
${\mathbf k}_{p}\in K_{1}$ for every $p$ we can find
an ${\mathbf x}\in K_{1}$ and $p(j)\geq j$ such
that ${\mathbf k}_{p(j)}\rightarrow{\mathbf x}$
(in the Euclidean metric) as $j\rightarrow\infty$.
As in part~(i), we know that ${\mathbf x}\in K$
so
\[\|{\mathbf k}_{p(j)}-{\mathbf x}\|\geq\eta.\]
for all $j$ giving us a contradiction.
Part~(ii) follows by reductio ad absurdum.
\end{proof}
\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}
\begin{proof}
If ${\mathbf z}_{n}\in K+\bar{B}(0,r)$, then
${\mathbf z}_{n}={\mathbf x}_{n}+{\mathbf y}_{n}$
with ${\mathbf x}_{n}\in K$, $\|{\mathbf y}_{n}\|\leq r$.
By compactness, we can first extract a convergent subsequence
${\mathbf x}_{n(j)}\in K$ and then a convergent
subsequence ${\mathbf y}_{n(j(k))}\in \bar{B}(0,r)$.
It follows that
${\mathbf z}_{n(j(k))}={\mathbf x}_{n(j(k))}+{\mathbf y}_{n(j(k))}$
converges to a point in $K+\bar{B}(0,r)$ so we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Hausdorff complete}] By
Lemma~\ref{L;fast Cauchy}, it suffices to show that, if
we have sequence of non-empty compact sets with
$\rho(E_{n},E_{n+1})<8^{-n}$ for $n\geq 1$, then the
sequence converges. Set
\[K_{n}=E_{n}+\bar{B}(0,6\times 8^{-n}).\]
Then $K_{n}$ is compact and $\rho(E_{n},K_{n})=6\times 8^{-n}$
so it is sufficient to show that $K_{n}$ converges.
To do this, we observe that $K_{n+1}\subseteq K_{n}$ and
so we may apply Theorem~\ref{T;decreasing compact}.
\end{proof}
\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.
\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}
\begin{proof}
Observe that, taking $C$ to be the
contour $z=e^{i\theta}$ as $\theta$ runs from $0$ to $2\pi$,
we have
\begin{align*}
\sup_{z\in\bar{D}}|f(z)-p(z)|&
\geq\frac{1}{2\pi}\left|\int_{C}f(z)-p(z)\,dz\right|\\
&=\frac{1}{2\pi}\left|\int_{C}f(z)\,dz\right|
=\frac{1}{2\pi}
\left|\int_{0}^{2\pi}e^{-i\theta}ie^{i\theta}\,d\theta\right|\\
&=\frac{1}{2\pi}\left|\int_{0}^{2\pi}i\,d\theta\right|
=1.
\end{align*}
\end{proof}
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}
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}
\begin{proof} By
exactly the same computations as in
Example~\ref{E;conjugate},
\[\sup_{z\in T}|f(z)-p(z)|
\geq\frac{1}{2\pi}\left|\int_{C}f(z)-p(z)\,dz\right|
=1.\]
\end{proof}
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$.
\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'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}
\begin{proof} We may suppose
$K$ non-empty.
Since $K$ is compact, ${\mathbb C}\setminus\Omega$
closed and the two sets are disjoint, it follows that
$\eta=\tau(K,{\mathbb C}\setminus\Omega)/8>0$
(i.e. $|k-w|>8\eta$ for all $k\in K$, $w\notin\Omega$).
Consider a grid of squares side $\eta$. We consider the
collection $\Gamma$ of closed squares $S$ lying entirely
within $\Omega$ with boundary contours $C(S)$.
Observe that
\[\bigcup_{S\in\Gamma}C(S)\supseteq\{k+u\,:k\in K,\ |u|\leq2\eta\}\]
By Cauchy's theorem
\[f(z)=\frac{1}{2\pi i}\sum_{S\in\Gamma}\int_{C(S)}\frac{f(w)}{w-z}\,dw\]
for all $z\in K$ such that $z$ does not lie on the boundary
of some $S$. By cancelling internal sides,
\[f(z)=\sum_{m=1}^{M}\int_{C_{m}}\frac{f(w)}{w-z}\,dw\tag*{$\bigstar$}\]
with the piece-wise linear contours $C_{m}$ $[1\leq m\leq M]$
lying entirely within $\Omega\setminus K$.
We deal with the case when $z$ lies on the boundary
of some $S$ by erasing any sides through $z$ and repeating the
argument with the new (non-regular) grid. (Alternatively,
we could observe that both sides of equation $\bigstar$
are continuous.)
\end{proof}
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}
\begin{proof}[Lemma~\ref{L;note Runge}] Observe that
$K$ and $\bigcup_{m=1}^{M} C_{m}$ are compact and disjoint.
\end{proof}
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}
\begin{proof}
By Lemma 11.13 it is sufficient to show that,
if $C$ is a straight line segment joining
lying in $\Omega\setminus K$,
then, given $\epsilon$, we can find $B_{m}\in{\mathbb C}$ and
$\beta_{m}\in C$ with
\[\left|\frac{1}{2\pi i}\int_{C}\frac{f(w)}{w-z}\,dw
-\sum_{m=1}^{M}\frac{B_{m}}{z-\beta_{m}}\right|
<\epsilon\]
for all $z\in K$.
To this end, note that
\[\frac{1}{2\pi i}\int_{C}\frac{f(w)}{w-z}\,dw
=\int_{0}^{1}F(t,z)\,dt\]
where $F:[0,1]\times K\rightarrow{\mathbb C}$
is defined by
\[F(t,z)=\frac{1}{2\pi i}\frac{f(\gamma(t))}{\gamma(t)-z}\gamma'(t)\]
with $\gamma(t)=(1-t)z_{1}+tz_{2}$.
Since $[0,1]\times K$ is compact and $F$ is continuous, $F$ must
be uniformly continuous so there exists a $\delta>0$
such that
\[|F(t,z)-F(s,z)|<\epsilon\ \text{for all}\ |t-s|<\delta.\]
If we choose an integer $M>\delta^{-1}$ and set
$F_{M}(t,z)=F(m/M,z)$ whenever $(m-1)/M0$, we can find a polynomial $P$ with
\[\left|P(z)-\frac{1}{z-\alpha}\right|
<\epsilon\]
for all $z\in K$.
\end{lemma}
\begin{proof}[Proof of Theorem~\ref{T;Runge}
from Lemma~\ref{L;simple Runge 1}]
We use the result and notation of Lemma~\ref{L:Runge to simple}.
Choose polynomials $P_{n}$ such that
\[\left|P_{n}(z)-\frac{1}{z-\alpha_{n}}\right|
\leq\frac{\epsilon}{(N+1)(|A_{n}|+1)}\]
for all $z\in K$. Then, if
\[P(z)=\sum_{n=1}^{N}A_{n}P_{n}(z),\]
$P$ is a polynomial and
\begin{align*}
|f(z)-P(z)|&\leq
\left|f(z)-\sum_{n=1}^{N}\frac{A_{n}}{z-\alpha_{n}}\right|
+\sum_{n=1}^{N}|A_{n}|
\left|P_{n}(z)-\frac{1}{z-\alpha_{n}}\right|\\
&\leq \epsilon+N\frac{\epsilon}{N+1}\leq 2\epsilon.
\end{align*}
Since $\epsilon$ was arbitrary the result follows.
\end{proof}
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{proof}
Since $K$ is compact, it is bounded and
we can find an $R>0$ such that $|z|R$
\[\frac{-1}{\alpha}\sum_{r=0}^{n}\frac{z^{r}}{\alpha^{r}}
\rightarrow \frac{-1}{\alpha}\times \frac{1}{1-(z/\alpha)}
= \frac{1}{z-\alpha}\]
uniformly for $|z|\leq R/2$ and so for $z\in K$.
\end{proof}
\begin{lemma}\label{L;simple Runge 2}
Let $K$ be a compact set in ${\mathbb C}$.
If $\alpha\in\Lambda(K)$ and $|\alpha-\beta|0$,
there exists an $N$ with
\[\left|\frac{1}{z-\beta}-\sum_{j=0}^{N}
\frac{(\beta-\alpha)^{j}}{(z-\alpha)^{j+1}}\right|
<\epsilon/2\]
for all $z\in K$. By the first paragraph, we can find an $M$
such that
\[\left|
\frac{(\beta-\alpha)^{j}}{(z-\alpha)^{j+1}}
-(\beta-\alpha)^{j}P_{M}(z)^{j}\right|<\epsilon/(2N+4)\]
for each $0\leq j\leq N$ and so
\[\left|\frac{1}{z-\beta}-\sum_{j=0}^{N}
(\beta-\alpha)^{j}P_{M}(z)^{j}\right|
<\epsilon\]
for all $z\in K$. We have shown that $\beta\in\Lambda(K)$.
\end{proof}
\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}
\begin{proof}
Let $a\in {\mathbb C}\setminus K$. By
Lemma~\ref{L;far Runge}, $\Lambda(K)$ is non-empty
so we may choose a $b\in\Lambda(K)$.
Since ${\mathbb C}\setminus K$ is path connected
we can find a continuous
$\gamma:[0,1]\rightarrow {\mathbb C}\setminus K$
with $\gamma(0)=b$, $\gamma(1)=a$. The continuous image of
a compact set is compact and $\gamma([0,1])\cap K=\emptyset$
so (see Lemma~\ref{L;compact compact}) there exists a $\delta>0$
such that $|\gamma(t)-k|>\delta$ for all $k\in K$ and all
$t\in[0,1]$.
By uniform continuity, we can find an $N$ such that
\[|s-t|\leq 1/N\Rightarrow |\gamma(t)-\gamma(s)|<\delta/2.\]
Writing $x_{r}=\gamma(r/N)$, we see that $x_{0}=b\in \Lambda(K)$
and, applying Lemma~\ref{L;simple Runge 2},
\[x_{r-1}\in \Lambda(K)\Rightarrow x_{r}\in \Lambda(K)\]
for $1\leq r\leq N$. Thus $a=x_{N}\in \Lambda(K)$
and we are done.
\end{proof}
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}
\begin{proof}[Solution] Consider the map $T_{n}$ given by
\[T_{n}(z)=(2^{-n}+z)\exp(-2^{-n}i\pi)\]
(a translation followed by a rotation).
Let $g_{n}=T_{n}^{-1}fT_{n}$ and
\[l_{n}=\{r\exp(i2^{-n})-2^{-n}\,:\,r\in{\mathbb R},\ r\geq 0\}
=T_{n}^{-1}\{x\,:\,x\in{\mathbb R},\ x\geq 0\}\]
so $g_{n}$ is analytic on ${\mathbb C}\setminus l_{n}$.
We see that $g_{n}(z)\rightarrow f(z)$ pointwise
as $n\rightarrow\infty$.
(The reader may find it convenient
to examine the case when $z=x$ with $x$ real and $x\geq 0$
separately.)
We now set
\[U_{n}=l_{n}+\Int D(0,2^{-8n})=\{z+w,\,:\,z\in l_{n},\ |w|<2^{-8n}\}\]
so that $U_{n}$ is open and $U_{n}\cap U_{m}=\emptyset$ for $n\neq m$.
Finally we take
\[K_{n}=\Cl{D}\setminus U_{n}\]
so that $K_{n}$ is compact. By Runge's theorem we can
find a polynomial $P_{n}$ such that $|P_{n}(z)-g_{n}(z)|\leq 2^{-n}$
for all $z\in K_{n}$.
Now choose a particular $z\in D$. We know that there exists
an $N$ (depending on $z$) such that $z\in K_{n}$ for all $n\geq N$.
Considering only $n\geq N$, we have $|P_{n}(z)-g_{n}(z)|\rightarrow 0$
and (as we observed in the first paragraph) $g_{n}(z)\rightarrow f(z)$
so $P_{n}(z)\rightarrow f(z)$ as $n\rightarrow\infty$.
Since $z$ was arbitrary, we are done.
\end{proof}
Thus the pointwise limit of analytic functions need not be
analytic.
\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{proof}
This is probably familiar from 1A.
Suppose, if possible, that $e=p/q$ with $p$ and $q$
integers and $q\geq 2$. Then
\[q!e\ \text{and}\ q!\sum_{r=0}^{q}\frac{1}{r!}\]
are integers so
\[M=q!\sum_{r=q+1}^{\infty}\frac{1}{r!}=
q!e-q!\sum_{r=0}^{q}\frac{1}{r!}\]
is an integer. But
\[
00$ (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}
\begin{proof}
Let
\[P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{0}.\]
Since
a polynomial has only finitely many roots,
we can find an $R\geq 1$ such that all the
roots of $P$ lie in $[-R+1,R-1]$. If we take $01$ such that $|P'(t)|\leq M$
for $t\in [-R,R]$. (We could also prove this directly.)
If $\alpha$ is an irrational root,
$p,\,q\in{\mathbb Z}$ with $q\neq 0$,
$p/q\in [-R,R]$ and $P(p/q)\neq 0$, then
the mean value theorem yields
\[|P(\alpha)-P(p/q)|\leq M\left|\alpha-\frac{p}{q}\right|\]
so, since $P(\alpha)=0$,
\[|P(p/q)|\leq M\left|\alpha-\frac{p}{q}\right|.\]
Now $q^{n}P(p/q)$ is a non-zero integer, so
$|q^{n}P(p/q)|\geq 1$ and
\[q^{-n}\leq M\left|\alpha-\frac{p}{q}\right|,\]
that is to say
\[M^{-1}q^{-n}\leq\left|\alpha-\frac{p}{q}\right|.\]
Since there are only a finite number of roots
and so only a finite number of irrational roots,
we know that there is a $c'>0$ such that
\[\left|\alpha-\frac{p}{q}\right|\geq c'q^{-n}\]
whenever $\alpha$ is an irrational root,
$p,\,q\in{\mathbb Z}$ with $q\neq 0$ and $P(p/q)=0$.
Taking $c=\min\{M^{-1},c',1\}$, we have the required result.
\end{proof}
We say that `irrational algebraic numbers are not
well approximated by rationals'.
\begin{theorem}\label{T;Liouville number} The number
\[\sum_{j=0}^{\infty}\frac{1}{10^{j!}}\]
is transcendental.
\end{theorem}
\begin{proof}
Let
\[L=\sum_{n=0}^{\infty}\frac{1}{10^{n!}}.\]
We observe that $L$ is irrational since its decimal
expansion is not recurring.
If $q_{m}=10^{m!}$ and
\[p_{m}=q_{m}\sum_{n=0}^{m}\frac{1}{10^{n!}},\]
then $p_{m}$ and $q_{m}$ are integers with $q_{m}\neq 0$.
We observe that
\[
\left|L-\frac{p_{m}}{q_{m}}\right|
=\sum_{j=m+1}^{\infty}\frac{1}{10^{j!}}
\leq \frac{1}{10^{(m+1)!}} \sum_{j=0}^{\infty}\frac{1}{10^{j}}
\leq\frac{2}{10^{(m+1)!}}
\]
and, given any $c>0$ and any integer $n\geq 1$, we can find an
$m$ such that
\[\left|L-\frac{p_{m}}{q_{m}}\right|\leq \frac{2}{10^{(m+1)!}}
< \frac{c}{q^{n}}.\]
Thus Theorem~\ref{T;Liouville} tells us that
$L$ is transcendental.
\end{proof}
\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}
\begin{proof}[Solution] Essentially
the same argument as for Theorem~\ref{T;Liouville number}
tells us that
\[\sum_{n=0}^{\infty}\frac{b_{j}}{10^{n!}}\]
with $b_{j}\in\{1,\,2\}$ is transcendental.
The map
\[\theta:\{0,1\}^{\mathbb N}\rightarrow{\mathbb R}\]
given by
\[\theta({\boldsymbol \zeta})
=\sum_{n=0}^{\infty}\frac{\zeta(j)+1}{10^{n!}}\]
is injective and its image (as we have just seen) consists
of transcendental numbers. Since, as we
saw in 1A, the set $\{0,1\}^{\mathbb N}$ is uncountable
and $\theta$ is injective, $\theta({\mathbb N})$ is uncountable
and we are done.
\end{proof}
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}
\begin{proof}
We construct $x_{j}\in X$ and $\delta_{j}>0$
inductively as follows. Choose any $x_{0}\in X$ and
set $\delta_{0}=1$.
Suppose that $x_{j}$ and $\delta_{j}$ have been found. Since
$X\setminus U_{j+1}$ has empty interior, we can find
an $x_{j+1}\in U_{j+1}$ with $d(x_{j+1},x_{j})\leq \delta_{j}/4$.
Since $U_{j+1}$ is open we can find a $\delta_{j+1}>0$
with $\delta_{j+1}\leq\delta_{j}/4$ such that
$B(x_{j+1},\delta_{j+1})\subseteq U_{j+1}$.
By induction, $\delta_{j+k}\leq 4^{-k}\delta_{j}$ for $j,k\geq 0$,
so,
if $m\geq n\geq 0$,
\begin{align*}
d(x_{n},x_{m})&\leq\sum_{r=0}^{m-n-1}d(x_{n+r},x_{n+r+1})\\
&\leq \sum_{r=0}^{m-n-1}\delta_{n+r}/4\leq
\sum_{r=0}^{m-n-1}\delta_{n}4^{-r-1}\leq \delta_{n}/2,
\end{align*}
so the sequence $x_{n}$ is Cauchy and so converges to
some point $a$.
We observe that
\[d(x_{n},a)\leq d(x_{n},x_{m})+d(x_{m},a)
\leq \delta_{n}/2+d(x_{m},a)\rightarrow \delta_{n}/2\]
as $m\rightarrow\infty$. Thus
\[d(x_{n},a)\leq d(x_{n},x_{m})+d(x_{m},a)
\leq \delta_{n}/2+d(x_{m},a)\rightarrow \delta_{n}/2\]
as $m\rightarrow\infty$. Thus
\[a\in B(x_{j},\delta_{j})\subseteq U_{j}\]
for all $j\geq 1$ and
\[a\in\bigcap_{j=1}^{\infty}U_{j}.\]
The result is proved
\end{proof}
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}
\begin{proof}[Proof of the equivalence of Theorems~\ref{T;Baire}
and~\ref{T;complement Baire}] Set $F_{j}=X\setminus U_{j}$.
\end{proof}
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}
\begin{proof}[Proof of the equivalence of Theorems~\ref{T;Baire}
and~\ref{T;informal}]
Let $x$ have the property $P_{j}$ if
and only if $x\notin U_{j}$.
\end{proof}
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}
\begin{proof}
(i) This is just a restatement of
Theorem~\ref{T;complement Baire}.
(ii) The countable union of countable sets is countable.
\end{proof}
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{proof}
Suppose that $(E,d)$ is a non-empty countable
complete space with no isolated points.
Then each $\{e\}$ with $e\in E$ is closed
(since singletons are always closed in metric spaces).
However, since $e$ not isolated,
$B(x,\delta)\not\subseteq \{e\}$ for all $\delta>0$,
so $\{e\}$ is not open and $\{e\}$ has empty interior.
Thus $E$ is the countable union of closed sets
$\{e\}$ with empty interior contradicting
Theorem~\ref{T;complement Baire}.
The required result follows by reductio ad absurdum.
\end{proof}
\begin{corollary}\label{C;Cantor} The real numbers are uncountable.
\end{corollary}
\begin{proof}
Observe that ${\mathbb R}$ with the usual metric
is complete without isolated points.
Theorem~\ref{T;no isolated} now tells us that
${\mathbb R}$ is uncountable.
\end{proof}
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}
\begin{proof}
Banach's clever idea is to consider the set
$E_{m}$ consisting of all those $f\in C([0,1])$
such that there exists an $x\in[0,1]$
with the property
\[|f(x)-f(y)|\leq m|x-y|\]
for all $y\in[0,1]$. Our proof falls into several parts.
(a) We show that, if $f$ is differentiable at some point
$x\in [0,1]$, then there exists a positive integer $m$
such that $f\in E_{m}$. It will then follow that
any
$g\in C([0,1])\setminus\bigcup_{m=1}^{\infty}E_{m}$
is nowhere differentiable.
To this end, suppose that $f$ is differentiable
at $x$. We can find an $\epsilon>0$ such that
\[\left|\frac{f(x+h)-f(x)}{h}-f'(x)\right|\leq 1\]
for all $0<|h|<\epsilon $, when $x+h\in [0,1]$.
Thus
\[|f(x+h)-f(x)|\leq (|f'(x)|+1)|h|\]
for all $0<|h|<\epsilon $ when $x+h\in [0,1]$.
We thus have
\[|f(x)-f(y)|\leq (|f'(x)|+1)|x-y|\]
for all $y\in[0,1]$ such that $|y-x|<\epsilon$.
If we choose $m$ with $m\geq |f'(x)|+1$ and
$m\geq 2K\epsilon^{-1}$, we will have $f\in E_{m}$.
(b) We now show that $E_{m}$ is closed.
Suppose that $f_{n}\in E_{m}$ and
$\|f_{n}-f\|_{\infty}\rightarrow 0$.
By definition, there exists an $x_{n}\in[0,1]$ with the property
\[|f_{n}(x_{n})-f(y)|\leq m|x_{n}-y|\]
for all $y\in[0,1]$. By the Bolzano--Weierstrass
property, we can find $x\in[0,1]$
and $n(r)\rightarrow\infty$ such that
$x_{n(r)}\rightarrow x$ as $r\rightarrow\infty$.
Let $y\in [0,1]$. We have
\begin{align*}
|f(x)-f(y)|&\leq |f(x)-f(x_{n(r)})|
+|f(x_{n(r)})-f_{n(r)}(x_{n(r)})|\\
&\qquad\qquad+|f_{n(r)}(x_{n(r)})-f_{n(r)}(y)|
+|f_{n(r)}(y)-f(y)|\\
&\leq 2\|f-f_{n(r)}\|_{\infty}+|f(x)-f(x_{n(r)})|
+m|x_{n(r)}-y|\\
&\rightarrow 0+0+m|x-y|=m|x-y|.
\end{align*}
Since $y$ was arbitrary, $f\in E_{m}$.
(c) Next we show that $E_{m}$ has a dense complement.
Suppose that $f\in C([0,1])$ and $\epsilon>0$.
By Weierstrass's theorem on polynomial
approximation (see Theorem~\ref{T;Bernstein}),
we can find a polynomial $P$ such that
\[\|f-P\|_{\infty}\leq \epsilon/3.\]
Since $P$ is continuously differentiable,
there is a $K$ such that $|P'(t)|\leq K$
for all $t\in[0,1]$. By the mean value theorem,
it follows that
\[|P(x)-P(y)|\leq K|x-y|\]
for all $x,\,y\in[0,1]$.
Let $g(t)=P(t)+(\epsilon/3)\cos 2\pi Nt$. Automatically,
\[\|g-f\|_{\infty}\leq \|f-P\|_{\infty}+\epsilon/3
\leq 2\epsilon/3<\epsilon.\]
We claim that, provided only that $N$ is large enough,
$g\notin E_{m}$.
To see this choose $r$ an integer with $0\leq r\leq N-1$
such that $0\leq x-r/N\leq 1/N$. We have
\begin{align*}
\max\{|g(r/N)-g(x)|&,|g((r+1)/N)-g(x)|\}\\
&\geq\frac{|g(r/N)-g(x)|+|g((r+1)/N)-g(x)|}{2}\\
&\geq\frac{|g(r/N)-g((r+1)/N)|}{2}\\
&\geq\frac{2\epsilon/3-|P(r/N)-P((r+1)/N)|}{2}\\
&\geq \epsilon/3-K/N\geq \epsilon/6\geq 4m/N.
\end{align*}
Thus at least one of the statements
\[|g(r/N)-g(x)|>m|r/n-x|\ \text{or}
\ |g((r+1)/N)-g(x)|>m|(r+1)/n-x|\]
is true for $N$ sufficiently large (with
$N$ not depending on the choice of $x$).
(d) Thus $\bigcup_{m=1}^{\infty}E_{m}$ is a set of first category
and we are done.
\end{proof}
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}
\begin{proof} Observe that
a closed subset of a complete metric space
is complete under the inherited metric
and that ${\mathbb R}$ is complete under the standard metric.
\end{proof}
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{proof}
(i) Suppose that $E_{n}\in {\mathcal E}_{k}$
and $E_{n}\rightarrow E$ in the Hausdorff metric.
By definition we can find $x_{n}\in E_{n}$ with
$B(x_{n},1/k)\cap E=\{x_{n}\}$. By Bolzano--Weierstrass,
we can find $n(j)\rightarrow\infty$ and $x\in[0,1]$
such that $|x_{n}(j)-x|\rightarrow 0$. We observe
that $x\in E$.
Suppose, if possible, that $B(x,1/k)\cap E\neq\{x\}$.
Then we can find a $y\in E$ such that $|x-y|<1/k$.
Set $\delta=(1/k-|x-y|)/2$. Since
$E_{n}\rightarrow E$ and $n(j)\rightarrow\infty$,
we can find a $J$ such that the Hausdorff distance
$\rho(E_{n(J)},E)<\delta$ and so there exists a
$y'\in E_{n(J)}$ with $|y'-y|<\delta$ and so with
$|x_{n(J)}-y'|<1/k$, contrary to our hypothesis.
Thus $E\in {\mathcal E}_{k}$ and ${\mathcal E}_{k}$
is closed.
(ii) Let $G\in{\mathcal K}$ and let $\epsilon>0$.
Choose an integer $N>5(\epsilon^{-1}+k+1)$.
Let
\[F=\{r/N\,:\,|r/N-x|\leq 4/N\ \text{for some $x\in G$}\}.\]
By construction,
\[\sigma(G,F)=\sup_{{\mathbf y}\in G}d(y,F)\leq 1/N
\ \text{and}
\ \sigma(F,G)=\sup_{{\mathbf y}\in F}d(y,G)\leq 4/N\]
so
\[\rho(G,F)=\sigma(G,F)+\sigma(F,G)\leq 5/N<\epsilon\]
But, if $y\in G$, then either $y+1/N$ or $y-1/N$
(or both) lies in $G$, so $G\notin {\mathcal E}_{k}$.
(iii) Observe that
${\mathcal E}=\cup_{k=1}^{\infty}{\mathcal E}_{k}$.
\end{proof}
\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{proof}[Lemma~\ref{L;empty interior}]
(i) Suppose that $F_{n}\in {\mathcal F}_{j,k}$
and $F_{n}\rightarrow F$ in the Hausdorff metric.
By definition, $F_{n}\supseteq[j/k,(j+1)/k]$, so
$F\supseteq[j/k,(j+1)/k]$.
Thus ${\mathcal F}_{j,k}$ is closed
(ii) Let $G\in{\mathcal K}$ and let $\epsilon>0$.
Choose an integer $N>2\epsilon^{-1}+1$.
Let
\[E=\{r/N\,:\,|r/N-x|\leq 1/N\ \text{for some $x\in G$}\}.\]
By construction,
\[\sigma(G,E)=\sup_{{\mathbf y}\in G}d(y,E)\leq 1/N
\ \text{and}
\ \sigma(E,G)=\sup_{{\mathbf y}\in E}d(y,G)\leq 1/N\]
so
\[\rho(G,E)=\sigma(G,E)+\sigma(E,G)\leq 2/N<\epsilon\]
but $E\notin{\mathcal F}_{j,k}$.
(iii) Observe that
${\mathcal F}=\bigcup_{k=1}^{\infty}\bigcup_{j=0}^{k}{\mathcal F}_{j,k}$,
so ${\mathcal F}$ is the countable union of closed nowhere dense sets.
\end{proof}
\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}
\begin{proof} With the notation of
Lemmas~\ref{L;splendid isolation} and~\ref{L;empty interior},
\[{\mathcal K}\setminus{\mathcal C}={\mathcal E}\cup{\mathcal F}.\]
Since the union of two first category sets is of first category,
${\mathcal K}\setminus{\mathcal C}$ is of the first category.
\end{proof}
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}
\begin{proof}[Solution]
(i) (This may be familiar from~1B.) Set
\[g_{n}(x)=
\begin{cases}
2^{2n}x&\text{if $0\leq x\leq 2^{-n-1}$,}\\
2^{2n}(2^{-n}-x)&\text{if $2^{-n-1}\leq x\leq 2^{-n}$,}\\
0&\text{otherwise.}
\end{cases}\]
If $x\neq 0$, then $x\geq 2^{-m}$ for some $m$
and so $g_{n}(x)=0$ for $n\geq m$. Since $g_{n}(0)=0$
for all $n$, we have $g_{n}(x)\rightarrow 0$ as
$n\rightarrow\infty$ for all $x$.
However,
\[\sup_{t\in[0,1]}g_{n}(t)=g(2^{-n-1})=2^{n-1}\rightarrow\infty\]
as $n\rightarrow\infty$.
(ii) Extend $g_{n}$ to a function on ${\mathbb R}$ by setting
$g_{n}(t)=0$ for $t\notin[0,1]$.
Set $f_{n}(t)=\sum_{j=1}^{\infty}2^{-j}g_{n}\big(2^{j}(t-2^{-j})\big)$
and use~(i).
\end{proof}
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}
\begin{proof}
Observe that
\[E_{n,m}=\{x\,:\,|f_{n}(x)|\leq m\}=f_{n}^{-1}([-m,m])\]
is closed (since $f_{n}$ is continuous), so
\[E_{m}=\bigcap_{n=1}^{\infty}E_{n,m}\]
is.
If we fix $x\in[0,1]$ for the moment, we know that
$f_{n}(x)\rightarrow 0$
as $n\rightarrow\infty$. In particular,
we can find an $N(x)$ such that $|f_{n}(x)|\leq 1$
for all $n\geq N(x)$. Thus
\[|f_{n}(x)|\leq \max\{1,\max_{1\leq j\leq N(x)}|f_{n}(x)|\}\]
and so $x\in E_{m(x)}$ for some integer $m(x)$.
The previous paragraph shows that
\[[0,1]=\bigcup_{m=1}^{\infty}E_{m},\]
but Baire's category theorem tells us that $[0,1]$
cannot be the countable union of closed sets with
empty interior. Thus there must exist an $M$ such that
$E_{M}$ has non-empty interior, so $E_{M}\supseteq(a,b)$
for some non-empty interval $(a,b)$.
\end{proof}
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 asigned a numerical meaning and
then that the asigned 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}
\begin{proof}[Solution]
\begin{align*}
\frac{100}{37}&=2+\frac{26}{37},\\
\frac{37}{26}&=1+\frac{11}{26},\\
\frac{26}{11}&=2+\frac{4}{11},\\
\frac{11}{4}&=2+\frac{3}{4},\\
\frac{4}{3}&=1+\frac{1}{3}.
\end{align*}
Thus
\[\frac{100}{37}=2+\cfrac{1}
{1+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{1+\cfrac{1}
{3}}}}}.\]
\end{proof}
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}\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{proof}
(i) Using Lemma~\ref{L;continued matrices}~(ii),
we have
\begin{align*}
p_{k}q_{k-1}-q_{k}p_{k-1}
&=\det\begin{pmatrix}p_{k}&p_{k-1}\\q_{k}&q_{k-1}\end{pmatrix}\\
&=\det\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\cdots
\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}\\
&=\det\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\det\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\cdots
\det\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}\\
&=(-1)^{k+1}.
\end{align*}
(ii) Either use the matricial formula
\[\begin{pmatrix}p_{k}&p_{k-1}\\q_{k}&q_{k-1}\end{pmatrix}
=\begin{pmatrix}p_{k-1}&p_{k-2}\\q_{k-1}&q_{k-2}\end{pmatrix}
\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}
\]
or direct computation.
(iii) Follows from the formula of~(i).
(iv) By~(ii) (or direct observation),
the $q_{k}$ form a strictly increasing sequence
of strictly positive integers. Thus the
$q_{k-1}q_{k}$ form a strictly increasing sequence
of strictly positive integers.
The formula of~(i) gives
\[\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}=(-1)^{k+1}
\frac{1}{q_{k}q_{k-1}},\]
so the remark of the previous paragraph shows
that
\[\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\]
is an alternating sequence with decreasing magnitude.
Thus
\[\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}}.\]
We also have
\[\left|\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\right|
=\frac{1}{q_{k}q_{k-1}}\rightarrow 0.\]
(v) A decreasing sequence bounded below tends to a limit,
so
\[\frac{p_{2k+1}}{q_{2k+1}}\rightarrow\alpha\]
as $k\rightarrow\infty$ for some $\alpha$.
Since
\[\left|\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\right|
\rightarrow 0\]
this tells us that
\[\frac{p_{2k}}{q_{2k}}\rightarrow\alpha\]
as $k\rightarrow\infty$. Thus
\[\frac{p_{n}}{q_{n}}\rightarrow \alpha\]
and
\[\frac{p_{2k+1}}{q_{2k+1}}>\alpha>\frac{p_{2k}}{q_{2k}}.\]
\end{proof}
Naturally we call $\alpha$ the value of the associated
continued fraction.
\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}}}}\]
is the manner of Section~\ref{S;continued}. Show that
\[\frac{p_{2k}}{q_{2k}}0$
\[s>t>0\Rightarrow\frac{1}{a+t}>\frac{1}{a+s}.\]
Thus (using a formal induction if more details are required)
\[\frac{p_{2k}}{q_{2k}}0$, we must have
\[\sigma=\frac{-1+\sqrt{5}}{2}.\]
(ii) By Theorem~\ref{T;continued convergence}~(iii),
$q_{k}=a_{k}q_{k-1}+q_{k-2}$ and
$p_{k}=a_{k}p_{k-1}+p_{k-2}$ with $a_{k}=1$.
Thus
\[q_{k}=q_{k-1}+q_{k-2}\ \text{and}
\ p_{k}=p_{k-1}+p_{k-2}.\]
Now $q_{0}=1=F_{1}$, $q_{1}=1=F_{2}$, $p_{0}=0=F_{0}$,
$p_{1}=1=F_{1}$, so by an inductive argument
(or general knowledge
of recurrence relations),
\[q_{n}=F_{n+1}\ \text{and}\ p_{n}=F_{n}.\]
(iii) By Theorem~\ref{T;continued convergence}~(i),
\[F_{n+1}F_{n-1}-F_{n}^{2}=
-(p_{n-1}q_{n}-q_{n-1}p_{n})=(-1)^{n+1}.\]
\end{proof}
\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{proof}[Solution]
By Theorem~\ref{T;good continue} $F_{n}/F_{n+1}$
is closer to $\sigma$ than any other fraction with
denominator no larger than $F_{n+1}$.
Thus
\begin{align*}
\left|\frac{p}{q}-\sigma\right|&\geq
\max\left\{\left|\frac{F_{n}}{F_{n+1}}-\sigma\right|,
\left|\frac{F_{n+1}}{F_{n+2}}-\sigma\right|\right\}\
\geq\frac{1}{2}
\left(\left|\frac{F_{n}}{F_{n+1}}-\sigma\right|+
\left|\frac{F_{n+1}}{F_{n+2}}-\sigma\right|\right)\\
&=\frac{1}{2}
\left|\frac{F_{n}}{F_{n+1}}-\frac{F_{n+1}}{F_{n+2}}\right|\
=\frac{1}{2F_{n+1}F_{n+2}}
\end{align*}
whenever $q\leq F_{n}$ and so whenever $F_{n-1}\leq q\leq F_{n}$.
Now $F_{r}\leq 2F_{r-1}$ so
\[\left|\frac{p}{q}-\sigma\right|\geq \frac{1}{2F_{n+1}F_{n+2}}
\geq \frac{1}{64 F_{n-1}^{2}}\geq \frac{1}{64 q^{2}}\]
whenever $F_{n-1}\leq q\leq F_{n}$ for all $n\geq 2$
and the result follows.
\end{proof}
\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}
\begin{proof}[Solution]
Observe that $F_{5}=5$, $F_{6}=8$, $F_{7}=13$
so the difference in areas is $1$ so we only need to hide
one unit of area.
Identify the Fibonacci numbers in the diagram and
generalise.
\end{proof}
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 formula (not lectured in 2020/2021)}
This section is non-examinable
and will not be lectured on this year.
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}
\begin{proof}[Solution]
(i) The proof follows the lines of that of
Lemma~\ref{L;continued matrices start}.
Observe that, if $s,\,r\neq 0$,
\[\begin{pmatrix}r'\\s'\end{pmatrix}
=\begin{pmatrix}a&b\\1&0\end{pmatrix}
\begin{pmatrix}r\\s\end{pmatrix}
=\begin{pmatrix}ar+bs\\r\end{pmatrix},
\]
and
\[\frac{ar+bs}{r}=a+\frac{b}{r/s}.\]
Thus, by induction, if
\[\begin{pmatrix}p_{n}\\q_{n}\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-1}&b_{n-1}\\1&0\end{pmatrix}
\begin{pmatrix}a_{n}\\1\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}}}}}}}}.\]
Observe that
\begin{align*}
\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-1}&b_{n-1}\\1&0\end{pmatrix}
\begin{pmatrix}1\\0\end{pmatrix}\\
&=\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}\dots
\begin{pmatrix}a_{n-2}&b_{n-2}\\1&0\end{pmatrix}
\begin{pmatrix}a_{n-1}\\1\end{pmatrix}
=\begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix}
\end{align*}
and thus
\[\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}.
\]
We deduce that
\[\begin{pmatrix}p_{n}&b_{n}p_{n-1}\\q_{n}&b_{n}q_{n-1}\end{pmatrix}
=\begin{pmatrix}p_{n-1}&b_{n-1}p_{n-2}\\q_{n-1}&b_{n-1}q_{n-2}\end{pmatrix}
\begin{pmatrix}a_{n}&b_{n}\\1&0\end{pmatrix}.\]
Looking at the first column gives
\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*}
as required.
\end{proof}
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}
\begin{proof} We have
\[S_{0}(x)=\int_{0}^{x}\cos t\,dt=\sin x,\]
so $p_{0}(x)=0$, $q_{0}(x)=1$. Integration by parts gives
\begin{align*}
S_{1}(x)&=\frac{1}{2}\int_{0}^{x}(x^{2}-t^{2})\cos t\,dt\\
&=\left[\frac{1}{2}(x^{2}-t^{2})\sin t\right]_{0}^{x}
+\int_{0}^{x}t\sin t\,dt
=\int_{0}^{x}t\sin t\,dt\\
&=\left[-t\cos t\right]_{0}^{x}+\int_{0}^{x}t\cos t\,dt
=-x\cos x+\sin x
\end{align*}
so $p_{1}(x)=x$, $q_{1}(x)=1$.
If $n\geq 2$, a similar repeated integration by parts
gives
\begin{align*}
S_{n}(x)&=\frac{1}{2^{n}n!}\int_{0}^{x}(x^{2}-t^{2})^{n}\cos t\,dt\\
&=\left[\frac{1}{2^{n}n!}(x^{2}-t^{2})^{n}\sin t\right]_{0}^{x}
+\frac{1}{2^{n-1}(n-1)!}\int_{0}^{x}t(x^{2}-t^{2})^{n-1}\sin t\,dt\\
&=\frac{1}{2^{n-1}(n-1)!}\int_{0}^{x}t(x^{2}-t^{2})^{n-1}\sin t\,dt\\
&=\frac{1}{2^{n-1}(n-1)!}\left[-t(x^{2}-t^{2})^{n-1}\cos t\right]_{0}^{x}\\
&\qquad+\frac{1}{2^{n-1}(n-1)!}
\int_{0}^{x}\big((x^{2}-t^{2})^{n-1}-2(n-1)t^{2}(x^{2}-t^{2})^{n-2}\big)
\cos t \,dt\\
&=S_{n-1}(x)-\frac{1}{2^{n-2}(n-2)!}
\int_{0}^{x}\big(t^{2}(x^{2}-t^{2})^{n-2}\big)\cos t\,dt\\
&=S_{n-1}(x)+\frac{1}{2^{n-2}(n-2)!}
\int_{0}^{x}\big((x^{2}-t^{2})t^{2}(x^{2}-t^{2})^{n-2}\big)\cos t\,dt\\
&\qquad-x^{2}\int_{0}^{x}(x^{2}-t^{2})^{n-2}\cos t\,dt\\
&=(2n-1)S_{n-1}(x)-x^{2}S_{n-2}(x).
\end{align*}
Thus
\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*}
and we are done.
\end{proof}
\begin{proof}[Theorem~\ref{T;Lambert}]
Since
\[S_{n}(x)=q_{n}(x)\sin x-p_{n}(x)\cos x,\]
rearrangement gives
\[\tan x=\frac{p_{n}(x)}{q_{n}(x)}
+\frac{S_{n}(x)}{q_{n}(x)\cos x}\]
so we need to show that
\[\frac{S_{n}(x)}{q_{n}(x)\cos x}\rightarrow 0.\]
It is easy to see that
\begin{align*}
|S_{n}(x)|&\leq
\left|\frac{1}{2^{n}n!}\int_{0}^{x}(x^{2}-t^{2})^{n}\cos t\,dt\right|\\
&\leq \frac{1}{2^{n}n!}|x||x|^{2n}\rightarrow 0
\end{align*}
as $n\rightarrow\infty$ for all $x$.
We shall show that if $|x|\leq 1$ then $q_{n}(x)\rightarrow\infty$.
(Actually it can be shown that $|q_{n}(x)|\rightarrow\infty$
for all $x$.) Observe that
\[q_{n}(x)=(2n-1)q_{n-1}(x)-x^{2}q_{n-2}(x)\]
so, if $|x|\leq 1$,
\[q_{n}(x)\geq (2n-1)q_{n-1}(x)-q_{n-2}(x)\geq 3q_{n-1}(x)-q_{n-2}(x)\]
for $n\geq 2$. Since $q_{0}(x)=q_{1}(x)=1$ we have
$q_{2}(x)\geq 2$ and a simple induction gives
$q_{n}(x)\geq 2^{n-1}$ for $n\geq 1$ and $|x|\leq 1$.
Notice the rapidity of convergence of the continued fraction
in this case.
\end{proof}
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}
\begin{proof}
We prove existence,
leaving uniqueness to follow
from Exercise~\ref{E;start argument}.
Let $E$ be the set of $u\in[0,1]$
for which there exists a
continuous function $\theta:[0,u]\rightarrow{\mathbb R}$
with $\theta(0)=\theta_{0}$
such that $g(t)=e^{i\theta(t)}$ for all $t\in[0,u]$.
Since $0\in E$ (just take $\theta(0)=\theta_{0}$)
and $E$ is bounded, $E$ must have an upper bound
$w$.
Suppose that $w\in(0,1)$. Since $g$ is continuous,
we can find a $\delta>0$ such that
$(w-2\delta,w+2\delta)\subseteq [0,1]$ and
$|g(t)-g(w)|<1/2$ for $t\in(w-2\delta,w+2\delta)$
We know that there is a unique continuous function
\[\phi:\{z\,:\,|z-1|<1/2,\ |z|=1\}\rightarrow [-\pi/2,\pi/2]\]
such that
\[z=e^{i\phi(z)}
\ \text{for all}\ |z-1|<1/2,\ |z|=1.\]
Thus, if we choose $\theta_{1}$ such that $e^{i\theta_{1}}=g(w)$
and define
$\tilde{\theta}:(w-2\delta,w+2\delta)\rightarrow [-\pi/2,\pi/2]$ by
\[\tilde{\theta}(t)=\theta_{1}+\phi\big(g(t)/g(w)\big)\]
we will have $\tilde{\theta}$ continuous and
\[g(t)=e^{i\tilde{\theta}(t)}\]
for $t\in (w-2\delta,w+2\delta)$.
By the definition of an upper bound, we can find
$u\in (w-\delta,w]$ and a continuous function
$\psi:[0,u]\rightarrow{\mathbb R}$
with $\psi(0)=\theta_{0}$
such that $g(t)=e^{i\psi(t)}$ for all $t\in[0,u]$.
Since
\[e^{i\tilde{\theta}(u)}=g(u)=e^{i\psi(u)}\]
we must have $\tilde{\theta}(u)=\psi(u)+2N\pi$
for some integer $N$.
Taking
\[\theta(t)=
\begin{cases}
\psi(t)&\text{for $t\in[0,u]$}\\
\tilde{\theta}(t)-2N\pi&\text{for $t\in[u,u+\delta]$}
\end{cases}\]
we see that $\theta:[0,u+\delta]\rightarrow{\mathbb R}$
is a continuous function with $\theta(0)=\theta_{0}$
such that $g(t)=e^{i\theta(t)}$ for all $t\in[0,u+\delta]$.
Thus $u+\delta\in E$ and $u+\delta>w$, contradicting our assumption
that $u$ is an upper bound.
A similar argument show that $0$ is not an upper bound.
Thus $\sup E=1$ and much the same argument as above
shows that $1\in E$,
so we are done.
\end{proof}
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{proof}[Solution] Observe that
$f:[0,1]\rightarrow{\mathbb R}$ defined by
\[f(t)= \frac{\psi(t)-\phi(t)}{2\pi}\]
is an integer valued continuous function on $[0,1]$
and so must be constant. (Or quote the intermediate value
theorem directly.)
\end{proof}
\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{proof} Set
$g(t)=\gamma(t)/|\gamma(t)|$ and use Theorem~\ref{T;track argument}.
\end{proof}
\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}
\begin{proof}[Solution]
(i) Since $\gamma(0)\neq 0$ and
\[|\gamma(0)|e^{i\theta(0)}=\gamma(0)=\gamma(1)
=|\gamma(1)|e^{i\theta(1)}=|\gamma(0)|e^{i\theta(1)},\]
we have $e^{i(\theta(1)-\theta(0))}=1$, so $\theta(1)-\theta(0)$
is an integer multiple of $2\pi$.
(ii) If we take $\gamma(t)=\exp(irt)$, we get
$w(\gamma,0)=r$ $[r\in{\mathbb Z}]$
\end{proof}
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{proof}
By Corollary~\ref{C;unwind}, we can write
\[\gamma_{j}(t)=|\gamma_{j}(t)|\exp\big(i\theta_{j}(t)\big)\]
with $\theta_{j}:[0,1]\rightarrow{\mathbb R}$ continuous.
We now have
\begin{align*}
\gamma_{1}(t)\gamma_{2}(t)&
=|\gamma_{1}(t)|\exp\big(i\theta_{1}(t)\big)
|\gamma_{2}(t)|\exp\big(i\theta_{2}(t)\big)\\
&=|\gamma_{1}(t)\gamma_{2}(t)|
\exp\big(i(\theta_{1}(t)+\theta_{2}(t))\big),
\end{align*}
so that
\begin{align*}
w(\gamma_{1}\gamma_{2},0)&=\frac{1}{2\pi}
\big(
\big(\theta_{1}(1)+\theta_{2}(1)\big)-
\big(\theta_{1}(0)+\theta_{2}(0)\big)\\
&=\frac{1}{2\pi}
\big(\theta_{1}(1)-\theta_{1}(0)\big)+
\frac{1}{2\pi}
\big(\theta_{2}(1)-\theta_{2}(0)\big)
=w(\gamma_{1},0)+w(\gamma_{2},0).
\end{align*}
\end{proof}
\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}
\begin{proof}
This argument may be familiar from 1B
complex variable.
Write $\gamma(t)=\big(1+\gamma_{2}(t)/\gamma_{1}(t)\big)$.
By Lemma~\ref{L;dogmatic},
\[w(\gamma_{1}+\gamma_{2},0)=w(\gamma_{1}\gamma,0)
=w(\gamma_{1},0)+w(\gamma,0),\]
so it suffices to prove that $w(\gamma,0)=0$.
We shall do this by noting that
$|\gamma_{2}(t)/\gamma_{1}(t)|<1$ and so
\[\Re\gamma(t)>0\]
for all $t\in[0,1]$.
By Corollary~\ref{C;unwind}, we can write
\[\gamma(t)=|\gamma(t)|\exp\big(i\theta(t)\big)\]
with $\theta:[0,1]\rightarrow{\mathbb R}$ continuous
and $\theta(0)\in(-\pi/2,\pi/2)$. If $|\theta(t)|\geq\pi/2$
for any $t\in[0,1]$, the intermediate value theorem tells
us that there is an $s\in[0,t]$ such that
$|\theta(s)|=\pi/2$ and so $\Re\gamma(s)=0$, which
is impossible. Thus $|\theta(t)|<\pi/2$
for all $t\in [0,1]$.
In particular $|\theta(0)|,|\theta(1)|<\pi/2$,
so $|\theta(1)-\theta(0)|<\pi$. It follows that
$w(\gamma,0)$ is an integer with $|w(\gamma,0)|<1/2$
and so $w(\gamma,0)=0$.
\end{proof}
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}
\begin{proof}[Solution]
Setting
\[\Gamma(s,t)=\gamma(t),\]
we see that $\gamma\simeq\gamma$.
If $\gamma_{0}\simeq\gamma_{1}$, then 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*}
If we set $\tilde{\Gamma}(s,t)=\Gamma(1-s,t)$,
then
$\tilde{\Gamma}:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
is a continuous function
such that
\begin{alignat*}{2}
\tilde{\Gamma}(s,0)&=\tilde{\Gamma}(s,1)
&&\qquad\text{for all $s\in[0,1]$},\\
\tilde{\Gamma}(0,t)&=\gamma_{1}(t)
&&\qquad\text{for all $t\in[0,1]$},\\
\tilde{\Gamma}(1,t)&=\gamma_{0}(t)&&\qquad\text{for all $t\in[0,1]$},
\end{alignat*}
and so $\gamma_{1}\simeq\gamma_{0}$.
If $\gamma_{0}\simeq\gamma_{1}$ and
$\gamma_{1}\simeq\gamma_{2}$,
then we can find
a continuous functions
$\Gamma_{j}:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
such that
\begin{alignat*}{2}
\Gamma_{j}(s,0)&=\Gamma_{j}(s,1)&&\qquad\text{for all $s\in[0,1]$},\\
\Gamma_{j}(0,t)&=\gamma_{0+j}(t)&&\qquad\text{for all $t\in[0,1]$},\\
\Gamma_{j}(1,t)&=\gamma_{1+j}(t)&&\qquad\text{for all $t\in[0,1]$}
\end{alignat*}
for $j=0,\,1$.
If we set
\[\Gamma(s,t)=\begin{cases}
\Gamma_{0}(2s,t)&\text{for all $s\in[0,1/2]$, $t\in[0,1]$}\\
\Gamma_{1}(2s-1,t)&\text{for all $s\in(1/2,1]$, $t\in[0,1]$}
\end{cases}\]
then
$\Gamma:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
is a continuous function
such that
\begin{alignat*}{2}
\tilde{\Gamma}(s,0)&=\tilde{\Gamma}(s,1)
&&\qquad\text{for all $s\in[0,1]$},\\
\tilde{\Gamma}(0,t)&=\gamma_{0}(t)
&&\qquad\text{for all $t\in[0,1]$},\\
\tilde{\Gamma}(1,t)&=\gamma_{2}(t)&&\qquad\text{for all $t\in[0,1]$},
\end{alignat*}
and so $\gamma_{0}\simeq\gamma_{2}$.
\end{proof}
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}
\begin{proof}
Let $\Gamma$ be as in Definition~\ref{D;homotopy}.
The map $(s,t)\mapsto |\Gamma(s,t)|$ is continuous
so, by compactness, $|\Gamma(s,t)|$ attains a minimum
$m$ on the compact set $[0,1]^{2}$. Since $\Gamma$ is never zero,
we must have $m>0$.
By compactness (see Theorem~\ref{T;uniform continuity}
if necessary), $\Gamma$ is uniformly continuous and so
we can find a strictly positive integer $N$ such that
\[|s-s'|,|t-t'|<2/N\Rightarrow |\Gamma(s,t)-\Gamma(s',t')|m/2\\
&>\big|\Gamma\big(r/N,t\big)-\Gamma\big((r+1)/N,t\big)\big|
=|\beta_{r}(t)-\beta_{r+1}(t)|
\end{align*}
for all $t\in[0,1]$, so by the dog walking lemma
(Lemma~\ref{L;dog walk}),
\[w(\beta_{r},0)=w(\beta_{r+1},0)\]
for all $0\leq r\leq N-1$. It follows that
\[w(\gamma_{0},0)= w(\beta_{0},0)=w(\beta_{N},0)=
w(\gamma_{1},0).\]
\end{proof}
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}
\begin{proof}
Suppose, if possible, that
$f(z)\neq 0$ for $z\in D$.
The nowhere-zero
function $G:[0,1]^{2}\mapsto{\mathbb C}$
given by
\[G(s,t)=f(se^{2\pi it})\]
is continuous with $G(s,0)=G(s,1)$ for all
$s\in[0,1]$,
$G(1,t)=\gamma(t)$
and $G(0,t)=\gamma_{0}(t)$
where $\gamma_{0}(t)=f(0)$
for all $t\in[0,1]$. Thus $\gamma$
and $\gamma_{0}$ are homotopic
closed curves not passing through $0$.
By Theorem~\ref{T;canal},
$w(\gamma,0)=w(\gamma_{0},0)=0$
contradicting our hypothesis.
\end{proof}
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}
\begin{proof}
It is sufficient to consider polynomials $P$
of the form
\[P(z)=z^{n}+Q(z)\]
with $Q(z)=\sum_{j=0}^{n-1}a_{j}z^{j}$.
If we set $R=1+\sum_{j=0}^{n-1}|a_{j}|$
and consider $p(z)=R^{-n}p(Rz)$
we see that $P$ has a root if $p$ has root
and that
\[p(z)=z^{n}+q(z)\]
with $|q(z)|<1$ when $|z|=1$.
By the dog walking lemma, the map
$t\mapsto p(e^{2\pi it})$ for $t\in[0,1]$
has the same winding number
as
$t\mapsto (e^{2\pi it})^{n}=e^{2\pi int}$,
that is to say, $n$. By Corollary~\ref{C;dizy dog},
there
must exist a $z\in D$ with $p(z)=0$,
so we are done.
\end{proof}
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}
\begin{proof}
Suppose such a function existed.
The continuous map $G:[0,1]^{2}\rightarrow\partial D$
given by
\[G(s,t)=f(se^{2\pi it})\]
gives a homotopy between $\gamma_{0}$
defined by $\gamma_{0}(t)=f(0)$ and
$\gamma_{1}$ defined by $\gamma_{1}(t)=f(t)=e^{2\pi t}$
using closed curves not passing through $0$.
By Theorem~\ref{T;canal}, this gives
\[1=w(\gamma_{1},0)=w(\gamma_{0},0)=0,\]
which is absurd.
The required result follows by reductio ad absurdum.
\end{proof}
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
\begin{verse}
`You are old, Father William' the young man said,\\
And your hair has become very white;\\
And yet you incessantly stand on your head\\
Do you think, at your age, it is right?'
`In my youth' Father William replied to his son,\\
`I feared it might injure the brain;\\
But, now that I'm perfectly sure I have none,\\
Why, I do it again and again.'
`You are old' said the youth `as I mentioned before,\\
And have grown most uncommonly fat;\\
Yet you turned a back-somersault in at the door –\\
Pray, what is the reason of that?'
`In my youth' said the sage, as he shook his grey locks,\\
`I kept all my limbs very supple\\
By the use of this ointment – one shilling the box –\\
Allow me to sell you a couple?'
`You are old' said the youth `and your jaws are too weak\\
For anything tougher than suet;\\
Yet you finished the goose, with the bones and the beak –\\
Pray how did you manage to do it?'
`In my youth' said his father `I took to the law,\\
And argued each case with my wife;\\
And the muscular strength, which it gave to my jaw,\\
Has lasted the rest of my life.'
`You are old' said the youth `one would hardly suppose\\
That your eye was as steady as ever;\\
Yet you balanced an eel on the end of your nose –\\
What made you so awfully clever?'
`I have answered three questions, and that is enough'\\
Said his father; `don't give yourself airs!\\
Do you think I can listen all day to such stuff?\\
Be off, or I'll kick you down stairs!'
\begin{flushright}
Lewis Carroll
\end{flushright}
\end{verse}
\clearpage
\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. If we write
\[d(x,y)=
\begin{cases}
0&\text{if $x=y$},\\
1&\text{if $x\neq y$},
\end{cases}
\]
show that $(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}|\]
then $(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 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 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$.
(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 that 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 $00$ 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,
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}$, then
\[\{{\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 $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.
\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 $m0$. 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}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**0$, then 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 the 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 say 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$ and integers
\[0=u(1)-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}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****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 s0$
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}
**