# Part II, 2010, Paper 2

### Jump to course

Paper 2, Section II, G

commentLet $X=X_{n, m, r}$ be the set of $n \times m$ matrices of rank at most $r$ over a field $k$. Show that $X_{n, m, r}$ is naturally an affine subvariety of $\mathbf{A}^{n m}$ and that $X_{n, m, r}$ is a Zariski closed subvariety of $X_{n, m, r+1}$.

Show that if $r<\min (n, m)$, then 0 is a singular point of $X$.

Determine the dimension of $X_{5,2,1}$.

Paper 2, Section II, $\mathbf{2 1 H}$

commentLet $G$ be the finitely presented group $G=\left\langle a, b \mid a^{2} b^{3} a^{3} b^{2}=1\right\rangle$. Construct a path connected space $X$ with $\pi_{1}(X, x) \cong G$. Show that $X$ has a unique connected double cover $\pi: Y \rightarrow X$, and give a presentation for $\pi_{1}(Y, y)$.

Paper 2, Section II, B

commentA beam of particles of mass $m$ and momentum $p=\hbar k$ is incident along the $z$-axis. Write down the asymptotic form of the wave function which describes scattering under the influence of a spherically symmetric potential $V(r)$ and which defines the scattering amplitude $f(\theta)$.

Given that, for large $r$,

$e^{i k r \cos \theta} \sim \frac{1}{2 i k r} \sum_{l=0}^{\infty}(2 l+1)\left(e^{i k r}-(-1)^{l} e^{-i k r}\right) P_{l}(\cos \theta),$

show how to derive the partial-wave expansion of the scattering amplitude in the form

$f(\theta)=\frac{1}{k} \sum_{l=0}^{\infty}(2 l+1) e^{i \delta_{l}} \sin \delta_{l} P_{l}(\cos \theta)$

Obtain an expression for the total cross-section, $\sigma$.

Let $V(r)$ have the form

$V(r)=\left\{\begin{array}{cl} -V_{0}, & r<a \\ 0, & r>a \end{array}\right.$

where $V_{0}=\frac{\hbar^{2}}{2 m} \gamma^{2}$

Show that the $l=0$ phase-shift $\delta_{0}$ satisfies

$\frac{\tan \left(k a+\delta_{0}\right)}{k a}=\frac{\tan \kappa a}{\kappa a},$

where $\kappa^{2}=k^{2}+\gamma^{2}$.

Assume $\gamma$ to be large compared with $k$ so that $\kappa$ may be approximated by $\gamma$. Show, using graphical methods or otherwise, that there are values for $k$ for which $\delta_{0}(k)=n \pi$ for some integer $n$, which should not be calculated. Show that the smallest value, $k_{0}$, of $k$ for which this condition holds certainly satisfies $k_{0}<3 \pi / 2 a$.

Paper 2, Section II, I

comment(a) Let $S_{k}$ be the sum of $k$ independent exponential random variables of rate $k \mu$. Compute the moment generating function $\phi_{S_{k}}(\theta)=\mathbb{E} e^{\theta S_{k}}$ of $S_{k}$. Show that, as $k \rightarrow \infty$, functions $\phi_{S_{k}}(\theta)$ converge to a limit. Describe the random variable $S$ for which the limiting function $\lim _{k \rightarrow \infty} \phi_{S_{k}}(\theta)$ coincides with $\mathbb{E} e^{\theta S}$.

(b) Define the $M / G / 1$ queue with infinite capacity (sometimes written $M / G / 1 / \infty$ ). Introduce the embedded discrete-time Markov chain $\left(X_{n}\right)$ and write down the recursive relation between $X_{n}$ and $X_{n-1}$.

Consider, for each fixed $k$ and for $0<\lambda<\mu$, an $\mathrm{M} / \mathrm{G} / 1 / \infty$ queue with arrival rate $\lambda$ and with service times distributed as $S_{k}$. Assume that the queue is empty at time 0 . Let $T_{k}$ be the earliest time at which a customer departs leaving the queue empty. Let $A$ be the first arrival time and $B_{k}=T_{k}-A$ the length of the busy period.

(c) Prove that the moment generating functions $\phi_{B_{k}}(\theta)=\mathbb{E} e^{\theta B_{k}}$ and $\phi_{S_{k}}(\theta)$ are related by the equation

$\phi_{B_{k}}(\theta)=\phi_{S_{k}}\left(\theta-\lambda\left(1-\phi_{B_{k}}(\theta)\right)\right)$

(d) Prove that the moment generating functions $\phi_{T_{k}}(\theta)=\mathbb{E} e^{\theta T_{k}}$ and $\phi_{S_{k}}(\theta)$ are related by the equation

$\frac{\lambda-\theta}{\lambda} \phi_{T_{k}}(\theta)=\phi_{S_{k}}\left((\lambda-\theta)\left(\phi_{T_{k}}(\theta)-1\right)\right)$

(e) Assume that, for all $\theta<\lambda$,

$\lim _{k \rightarrow \infty} \phi_{B_{k}}(\theta)=\mathbb{E} e^{\theta B}, \quad \lim _{k \rightarrow \infty} \phi_{T_{k}}(\theta)=\mathbb{E} e^{\theta T},$

for some random variables $B$ and $T$. Calculate $\mathbb{E} B$ and $\mathbb{E} T$. What service time distribution do these values correspond to?

Paper 2, Section I, D

commentGiven the form

$T=\frac{1}{2} T_{i j} \dot{q}_{i} \dot{q}_{j}, \quad V=\frac{1}{2} V_{i j} q_{i} q_{j}$

for the kinetic energy $T$ and potential energy $V$ of a mechanical system, deduce Lagrange's equations of motion.

A light elastic string of length $4 b$, fixed at both ends, has three particles, each of mass $m$, attached at distances $b, 2 b, 3 b$ from one end. Gravity can be neglected. The particles vibrate with small oscillations transversely to the string, the tension $S$ in the string providing the restoring force. Take the displacements of the particles, $q_{i}, i=1,2,3$, to be the generalized coordinates. Take units such that $m=1, S / b=1$ and show that

$V=\frac{1}{2}\left[q_{1}^{2}+\left(q_{1}-q_{2}\right)^{2}+\left(q_{2}-q_{3}\right)^{2}+{q_{3}}^{2}\right]$

Find the normal-mode frequencies for this system.

Paper 2, Section II, D

commentAn axially-symmetric top of mass $m$ is free to rotate about a fixed point $O$ on its axis. The principal moments of inertia about $O$ are $A, A, C$, and the centre of gravity $G$ is at a distance $\ell$ from $O$. Define Euler angles $\theta, \phi$ and $\psi$ which specify the orientation of the top, where $\theta$ is the inclination of $O G$ to the upward vertical. Show that there are three conserved quantities for the motion, and give their physical meaning.

Initially, the top is spinning with angular velocity $n$ about $O G$, with $G$ vertically above $O$, before being disturbed slightly. Show that, in the subsequent motion, $\theta$ will remain close to zero provided $C^{2} n^{2}>4 m g \ell A$, but that if $C^{2} n^{2}<4 m g \ell A$, then $\theta$ will attain a maximum value given by

$\cos \theta \simeq\left(C^{2} n^{2} / 2 m g \ell A\right)-1$

Paper 2, Section I, $4 \mathrm{H}$

commentDescribe the standard Hamming code of length 7 , proving that it corrects a single error. Find its weight enumeration polynomial.

Paper 2, Section II, H

commentThe Van der Monde matrix $V\left(x_{0}, x_{1}, \ldots, x_{r-1}\right)$ is the $r \times r$ matrix with $(i, j)$ th entry $x_{i-1}^{j-1}$. Find an expression for $\operatorname{det} V\left(x_{0}, x_{1}, \ldots, x_{r-1}\right)$ as a product. Explain why this expression holds if we work modulo $p$ a prime.

Show that $\operatorname{det} V\left(x_{0}, x_{1}, \ldots, x_{r-1}\right) \equiv 0$ modulo $p$ if $r>p$, and that there exist $x_{0}, \ldots, x_{p-1}$ such that $\operatorname{det} V\left(x_{0}, x_{1}, \ldots, x_{p-1}\right) \not \equiv 0$. By using Wilson's theorem, or otherwise, find the possible values of $\operatorname{det} V\left(x_{0}, x_{1}, \ldots, x_{p-1}\right)$ modulo $p$.

The Dark Lord Y'Trinti has acquired the services of the dwarf Trigon who can engrave pairs of very large integers on very small rings. The Dark Lord wishes Trigon to engrave $n$ rings in such a way that anyone who acquires $r$ of the rings and knows the Prime Perilous $p$ can deduce the Integer $N$ of Power, but owning $r-1$ rings will give no information whatsoever. The integers $N$ and $p$ are very large and $p>N$. Advise the Dark Lord.

For reasons to be explained in the prequel, Trigon engraves an $(n+1)$ st ring with random integers. A band of heroes (who know the Prime Perilous and all the information contained in this question) set out to recover the rings. What, if anything, can they say, with very high probability, about the Integer of Power if they have $r$ rings (possibly including the fake)? What can they say if they have $r+1$ rings? What if they have $r+2$ rings?

Paper 2, Section I, D

commentThe number density $n=N / V$ for a photon gas in equilibrium is given by

$n=\frac{8 \pi}{c^{3}} \int_{0}^{\infty} \frac{\nu^{2}}{e^{h \nu / k T}-1} d \nu$

where $\nu$ is the photon frequency. By letting $x=h \nu / k T$, show that

$n=\alpha T^{3}$

where $\alpha$ is a constant which need not be evaluated.

The photon entropy density is given by

$s=\beta T^{3}$

where $\beta$ is a constant. By considering the entropy, explain why a photon gas cools as the universe expands.

Paper 2, Section II, H

comment(i) State and prove the isoperimetric inequality for plane curves. You may appeal to Wirtinger's inequality as long as you state it precisely.

(ii) State Fenchel's theorem for curves in space.

(iii) Let $\alpha: I \rightarrow \mathbb{R}^{2}$ be a closed regular plane curve bounding a region $K$. Suppose $K \supset\left[p_{1}, p_{1}+d_{1}\right] \times\left[p_{2}, p_{2}+d_{2}\right]$, for $d_{1}>0, d_{2}>0$, i.e. $K$ contains a rectangle of dimensions $d_{1}, d_{2}$. Let $k(s)$ denote the signed curvature of $\alpha$ with respect to the inward pointing normal, where $\alpha$ is parametrised anticlockwise. Show that there exists an $s_{0} \in I$ such that $k\left(s_{0}\right) \leqslant \sqrt{\pi /\left(d_{1} d_{2}\right)}$.

Paper 2, Section I, D

commentConsider the 2-dimensional flow

$\dot{x}=\mu\left(\frac{1}{3} x^{3}-x\right)+y, \quad \dot{y}=-x$

where the parameter $\mu>0$. Using Lyapunov's approach, discuss the stability of the fixed point and its domain of attraction. Relevant definitions or theorems that you use should be stated carefully, but proofs are not required.

Paper 2, Section II, A

commentWhat is lubrication theory? Explain the assumptions that go into the theory.

Viscous fluid with dynamic viscosity $\mu$ and density $\rho$ is contained between two flat plates, which approach each other at uniform speed $V$. The first is fixed at $y=0,-L<x<L$. The second has its ends at $\left(-L, h_{0}-\Delta h-V t\right),\left(L, h_{0}+\Delta h-V t\right)$, where $\Delta h \sim h_{0} \ll L$. There is no flow in the $z$ direction, and all variation in $z$ may be neglected. There is no applied pressure gradient in the $x$ direction.

Assuming that $V$ is so small that lubrication theory applies, derive an expression for the horizontal volume flux $Q(x)$ at $t=0$, in terms of the pressure gradient. Show that mass conservation implies that $d Q / d x=V$, so that $Q(L)-Q(-L)=2 V L$. Derive another relation between $Q(L)$ and $Q(-L)$ by setting the pressures at $x=\pm L$ to be equal, and hence show that

$Q(\pm L)=V L\left(\frac{\Delta h}{h_{0}} \pm 1\right)$

Show that lubrication theory applies if $V \ll \mu / h_{0} \rho$.

Paper 2, Section I, E

commentDefine

$F^{\pm}(x)=\lim _{\epsilon \rightarrow 0} \frac{1}{2 \pi i} \int_{-\infty}^{\infty} \frac{f(t)}{t-(x \pm i \epsilon)} d t, \quad x \in \mathbb{R}$

Using the fact that

$F^{\pm}(x)=\pm \frac{f(x)}{2}+\frac{1}{2 \pi i} P \int_{-\infty}^{\infty} \frac{f(t)}{t-x} d t, \quad x \in \mathbb{R}$

where $P$ denotes the Cauchy principal value, find two complex-valued functions $F^{+}(z)$ and $F^{-}(z)$ which satisfy the following conditions

$F^{+}(z)$ and $F^{-}(z)$ are analytic for $\operatorname{Im} z>0$ and $\operatorname{Im} z<0$ respectively, $z=x+i y$;

$F^{+}(x)-F^{-}(x)=\frac{\sin x}{x}, \quad x \in \mathbb{R}$;

$F^{\pm}(z)=\mathrm{O}\left(\frac{1}{z}\right), \quad z \rightarrow \infty, \quad \operatorname{Im} z \neq 0$.

Paper 2, Section II, 14E

commentLet

$I(z)=i \oint_{C} \frac{u^{z-1}}{u^{2}-4 u+1} d u$

where $C$ is a closed anti-clockwise contour which consists of the unit circle joined to a loop around a branch cut along the negative axis between $-1$ and 0 . Show that

$I(z)=F(z)+G(z)$

where

$F(z)=2 \sin (\pi z) \int_{0}^{1} \frac{x^{z-1}}{x^{2}+4 x+1} d x, \quad \operatorname{Re} z>0$

and

$G(z)=\frac{1}{2} \int_{-\pi}^{\pi} \frac{e^{i(z-1) \theta}}{1+2 \sin ^{2} \frac{\theta}{2}} d \theta, \quad z \in \mathbb{C}$

Evaluate $I(z)$ using Cauchy's theorem. Explain how this may be used to obtain an analytic continuation of $F(z)$ valid for all $z \in \mathbb{C}$.

Paper 2, Section II, H

comment(1) Let $F=\mathbb{Q}(\sqrt[3]{5}, \sqrt{5}, i)$. What is the degree of $F / \mathbb{Q}$ ? Justify your answer.

(2) Let $F$ be a splitting field of $X^{4}-5$ over $\mathbb{Q}$. Determine the Galois group $\operatorname{Gal}(F / \mathbb{Q})$. Determine all the subextensions of $F / \mathbb{Q}$, expressing each in the form $\mathbb{Q}(x)$ or $\mathbb{Q}(x, y)$ for some $x, y \in F$.

[Hint: If an automorphism $\rho$ of a field $X$ has order 2 , then for every $x \in X$ the element $x+\rho(x)$ is fixed by $\rho$.]

Paper 2, Section II, B

commentA vector field $k^{a}$ which satisfies

$k_{a ; b}+k_{b ; a}=0$

is called a Killing vector field. Prove that $k^{a}$ is a Killing vector field if and only if

$k^{c} g_{a b, c}+k_{, b}^{c} g_{a c}+k_{, a}^{c} g_{b c}=0$

Prove also that if $V^{a}$ satisfies

$V_{; b}^{a} V^{b}=0$

then

$\left(V^{a} k_{a}\right)_{, b} V^{b}=0$

for any Killing vector field $k^{a}$.

In the two-dimensional space-time with coordinates $x^{a}=(u, v)$ and line element

$d s^{2}=-d u^{2}+u^{2} d v^{2}$

verify that $(0,1), e^{-v}\left(1, u^{-1}\right)$ and $e^{v}\left(-1, u^{-1}\right)$ are Killing vector fields. Show, by using $(*)$ with $V^{a}$ the tangent vector to a geodesic, that geodesics in this space-time are given by

$\alpha e^{v}+\beta e^{-v}=2 \gamma u^{-1}$

where $\alpha, \beta$ and $\gamma$ are arbitrary real constants.

Paper 2, Section I, F

commentShow that a map $T: \mathbb{R}^{2} \rightarrow \mathbb{R}^{2}$ is an isometry for the Euclidean metric on the plane $\mathbb{R}^{2}$ if and only if there is a vector $\boldsymbol{v} \in \mathbb{R}^{2}$ and an orthogonal linear map $B \in \mathrm{O}(2)$ with

$T(\boldsymbol{x})=B(\boldsymbol{x})+\boldsymbol{v} \quad \text { for all } \boldsymbol{x} \in \mathbb{R}^{2}$

When $T$ is an isometry with $\operatorname{det} B=-1$, show that $T$ is either a reflection or a glide reflection.

Paper 2, Section II, F

commentLet $G$ be a bipartite graph with vertex classes $X$ and $Y$. What does it mean to say that $G$ contains a matching from $X$ to $Y$ ?

State and prove Hall's Marriage Theorem, giving a necessary and sufficient condition for $G$ to contain a matching from $X$ to $Y$.

Now assume that $G$ does contain a matching (from $X$ to $Y$ ). For a subset $A \subset X$, $\Gamma(A)$ denotes the set of vertices adjacent to some vertex in $A$.

(i) Suppose $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$. Show that every edge of $G$ is contained in a matching.

(ii) Suppose that every edge of $G$ is contained in a matching and that $G$ is connected. Show that $|\Gamma(A)|>|A|$ for every $A \subset X$ with $A \neq \emptyset, X$.

(iii) For each $n \geqslant 2$, give an example of $G$ with $|X|=n$ such that every edge is contained in a matching but $|\Gamma(A)|=|A|$ for some $A \subset X$ with $A \neq \emptyset, X$.

(iv) Suppose that every edge of $G$ is contained in a matching. Must every pair of independent edges in $G$ be contained in a matching? Give a proof or counterexample as appropriate.

[No form of Menger's Theorem or of the Max-Flow-Min-Cut Theorem may be assumed without proof.]

Paper 2, Section II, E

commentConsider the Gelfand-Levitan-Marchenko (GLM) integral equation

$K(x, y)+F(x+y)+\int_{x}^{\infty} K(x, z) F(z+y) d z=0$

with $F(x)=\sum_{1}^{N} \beta_{n} e^{-c_{n} x}$, where $c_{1}, \ldots, c_{N}$ are positive constants and $\beta_{1}, \ldots, \beta_{N}$ are constants. Consider separable solutions of the form

$K(x, y)=\sum_{n=1}^{N} K_{n}(x) e^{-c_{n} y}$

and reduce the GLM equation to a linear system

$\sum_{m=1}^{N} A_{n m}(x) K_{m}(x)=B_{n}(x)$

where the matrix $A_{n m}(x)$ and the vector $B_{n}(x)$ should be determined.

How is $K$ related to solutions of the $K d V$ equation?

Set $N=1, c_{1}=c, \beta_{1}=\beta \exp \left(8 c^{3} t\right)$ where $c, \beta$ are constants. Show that the corresponding one soliton solution of the $\mathrm{KdV}$ equation is given by

$u(x, t)=-\frac{4 \beta_{1} c e^{-2 c x}}{\left(1+\left(\beta_{1} / 2 c\right) e^{-2 c x}\right)^{2}}$

[You may use any facts about the Inverse Scattering Transform without proof.]

Paper 2, Section II, H

commentFor a sequence $x=\left(x_{1}, x_{2}, \ldots\right)$ with $x_{j} \in \mathbb{C}$ for all $j \geqslant 1$, let

$\|x\|_{\infty}:=\sup _{j \geqslant 1}\left|x_{j}\right|$

and $\ell^{\infty}=\left\{x=\left(x_{1}, x_{2}, \ldots\right): x_{j} \in \mathbb{C}\right.$ for all $j \geqslant 1$ and $\left.\|x\|_{\infty}<\infty\right\}$.

a) Prove that $\ell^{\infty}$ is a Banach space.

b) Define

$c_{0}=\left\{x=\left(x_{1}, x_{2}, \ldots\right) \in \ell^{\infty}: \lim _{j \rightarrow \infty} x_{j}=0\right\}$

and

$\ell^{1}=\left\{x=\left(x_{1}, x_{2}, \ldots\right): x_{j} \in \mathbb{C} \text { for all } j \in \mathbb{N} \text { and }\|x\|_{1}=\sum_{\ell=1}^{\infty}\left|x_{\ell}\right|<\infty\right\}$

Show that $c_{0}$ is a closed subspace of $\ell^{\infty}$. Show that $c_{0}^{*} \simeq \ell^{1}$.

[Hint: find an isometric isomorphism from $\ell^{1}$ to $\left.c_{0}^{*} .\right]$

c) Let

$c_{00}=\left\{x=\left(x_{1}, x_{2}, \ldots\right) \in \ell^{\infty}: x_{j}=0 \text { for all } j \text { large enough }\right\} .$

Is $c_{00}$ a closed subspace of $\ell^{\infty} ?$ If not, what is the closure of $c_{00} ?$

Paper 2, Section II, G

commentLet $\alpha$ be a non-zero ordinal. Prove that there exists a greatest ordinal $\beta$ such that $\omega^{\beta} \leqslant \alpha$. Explain why there exists an ordinal $\gamma$ with $\omega^{\beta}+\gamma=\alpha$. Prove that $\gamma$ is unique, and that $\gamma<\alpha$.

A non-zero ordinal $\alpha$ is called decomposable if it can be written as the sum of two smaller non-zero ordinals. Deduce that if $\alpha$ is not a power of $\omega$ then $\alpha$ is decomposable.

Conversely, prove that if $\alpha$ is a power of $\omega$ then $\alpha$ is not decomposable.

[Hint: consider the cases $\alpha=\omega^{\beta}$ ( $\beta$ a successor) and $\alpha=\omega^{\beta}$ ( $\beta$ a limit) separately.]

Paper 2, Section $I$, A

commentThe population of a certain species subjected to a specific kind of predation is modelled by the difference equation

$u_{t+1}=a \frac{u_{t}^{2}}{b^{2}+u_{t}^{2}}, \quad a>0$

Determine the equilibria and show that if $a^{2}>4 b^{2}$ it is possible for the population to be driven to extinction if it becomes less than a critical size which you should find. Explain your reasoning by means of a cobweb diagram.

Paper 2, Section II, A

commentThe radially symmetric spread of an insect population density $n(r, t)$ in the plane is described by the equation

$\frac{\partial n}{\partial t}=\frac{D_{0}}{r} \frac{\partial}{\partial r}\left[r\left(\frac{n}{n_{0}}\right)^{2} \frac{\partial n}{\partial r}\right]$

Suppose $Q$ insects are released at $r=0$ at $t=0$. We wish to find a similarity solution to $(*)$ in the form

$n(r, t)=\frac{n_{0}}{\lambda^{2}(t)} F\left(\frac{r}{r_{0} \lambda(t)}\right)$

Show first that the PDE $(*)$ reduces to an ODE for $F$ if $\lambda(t)$ obeys the equation

$\lambda^{5} \frac{d \lambda}{d t}=C \frac{D_{0}}{r_{0}^{2}}$

where $C$ is an arbitrary constant (that may be set to unity), and then obtain $\lambda(t)$ and $F$ such that $F(0)=1$ and $F(\xi)=0$ for $\xi \geqslant 1$. Determine $r_{0}$ in terms of $n_{0}$ and $Q$. Sketch the function $n(r, t)$ at various times to indicate its qualitative behaviour.

Paper 2, Section II, G

commentCalculate the class group of the field $\mathbb{Q}(\sqrt{-14})$.

Paper 2, Section I, G

commentLet $p$ be an odd prime number. If $n$ is an integer prime to $p$, define $\left(\frac{n}{p}\right)$.

(i) Prove that $\chi(n)=\left(\frac{n}{p}\right)$ defines a homomorphism from $(\mathbb{Z} / p \mathbb{Z})^{\times}$to the group $\{\pm 1\}$. What is the value of $\chi(-1) ?$

(ii) If $p \equiv 1 \bmod 4$, prove that $\sum_{n=1}^{p-1} \chi(n) n=0$.

Paper 2, Section II, A

commentThe inverse discrete Fourier transform $\mathcal{F}_{n}^{-1}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is given by the formula

$\mathbf{x}=\mathcal{F}_{n}^{-1} \mathbf{y}, \quad \text { where } \quad x_{\ell}=\sum_{j=0}^{n-1} \omega_{n}^{j \ell} y_{j}, \quad \ell=0, \ldots, n-1$

Here, $\omega_{n}=\exp (2 \pi i / n)$ is the primitive root of unity of degree $n$, and $n=2^{p}, p=1,2, \ldots$

(1) Show how to assemble $\mathbf{x}=\mathcal{F}_{2 m}^{-1} \mathbf{y}$ in a small number of operations if we already know the Fourier transforms of the even and odd portions of $\mathbf{y}$ :

$\mathbf{x}^{(\mathrm{E})}=\mathcal{F}_{m}^{-1} \mathbf{y}^{(\mathrm{E})}, \quad \mathbf{x}^{(\mathrm{O})}=\mathcal{F}_{m}^{-1} \mathbf{y}^{(\mathrm{O})}$

(2) Describe the Fast Fourier Transform (FFT) method for evaluating $\mathbf{x}$ and draw a relevant diagram for $n=8$.

(3) Find the costs of the FFT for $n=2^{p}$ (only multiplications count).

(4) For $n=4$, using the FFT technique, find $\mathbf{x}=\mathcal{F}_{4}^{-1} \mathbf{y}, \quad$ for $\quad \mathbf{y}=[1,1,-1,-1], \quad$ and $\quad \mathbf{y}=[1,-1,1,-1]$

Paper 2, Section II, J

comment(a) Suppose that

$\left(\begin{array}{l} X \\ Y \end{array}\right) \sim N\left(\left(\begin{array}{l} \mu_{X} \\ \mu_{Y} \end{array}\right),\left(\begin{array}{ll} V_{X X} & V_{X Y} \\ V_{Y X} & V_{Y Y} \end{array}\right)\right)$

Prove that conditional on $Y=y$, the distribution of $X$ is again multivariate normal, with mean $\mu_{X}+V_{X Y} V_{Y Y}^{-1}\left(y-\mu_{Y}\right)$ and covariance $V_{X X}-V_{X Y} V_{Y Y}^{-1} V_{Y X}$.

(b) The $\mathbb{R}^{d}$-valued process $X$ evolves in discrete time according to the dynamics

$X_{t+1}=A X_{t}+\varepsilon_{t+1}$

where $A$ is a constant $d \times d$ matrix, and $\varepsilon_{t}$ are independent, with common $N\left(0, \Sigma_{\varepsilon}\right)$ distribution. The process $X$ is not observed directly; instead, all that is seen is the process $Y$ defined as

$Y_{t}=C X_{t}+\eta_{t},$

where $\eta_{t}$ are independent of each other and of the $\varepsilon_{t}$, with common $N\left(0, \Sigma_{\eta}\right)$ distribution.

If the observer has the prior distribution $X_{0} \sim N\left(\hat{X}_{0}, V_{0}\right)$ for $X_{0}$, prove that at all later times the distribution of $X_{t}$ conditional on $\mathcal{Y}_{t} \equiv\left(Y_{1}, \ldots, Y_{t}\right)$ is again normally distributed, with mean $\hat{X}_{t}$ and covariance $V_{t}$ which evolve as

$\begin{aligned} \hat{X}_{t+1} &=A \hat{X}_{t}+M_{t} C^{T}\left(\Sigma_{\eta}+C M_{t} C^{T}\right)^{-1}\left(Y_{t+1}-C A \hat{X}_{t}\right) \\ V_{t+1} &=M_{t}-M_{t} C^{T}\left(\Sigma_{\eta}+C M_{t} C^{T}\right)^{-1} C M_{t} \end{aligned}$

where

$M_{t}=A V_{t} A^{T}+\Sigma_{\varepsilon}$

(c) In the special case where both $X$ and $Y$ are one-dimensional, and $A=C=1$, $\Sigma_{\varepsilon}=0$, find the form of the updating recursion. Show in particular that

$\frac{1}{V_{t+1}}=\frac{1}{V_{t}}+\frac{1}{\Sigma_{\eta}}$

and that

$\frac{\hat{X}_{t+1}}{V_{t+1}}=\frac{\hat{X}_{t}}{V_{t}}+\frac{Y_{t+1}}{\Sigma_{\eta}}$

Hence deduce that, with probability one,

$\lim _{t \rightarrow \infty} \hat{X}_{t}=\lim _{t \rightarrow \infty} t^{-1} \sum_{j=1}^{t} Y_{j}$

Paper 2, Section II, E

comment(a) State the Lax-Milgram lemma. Use it to prove that there exists a unique function $u$ in the space

$H_{\partial}^{2}(\Omega)=\left\{u \in H^{2}(\Omega) ;\left.u\right|_{\partial \Omega}=\partial u /\left.\partial \gamma\right|_{\partial \Omega}=0\right\}$

where $\Omega$ is a bounded domain in $\mathbb{R}^{n}$ with smooth boundary and $\gamma$ its outwards unit normal vector, which is the weak solution of the equations

$\begin{aligned} \Delta^{2} u &=f \text { in } \Omega, \\ u &=\frac{\partial u}{\partial \gamma}=0 \text { on } \partial \Omega, \end{aligned}$

for $f \in L^{2}(\Omega), \Delta$ the Laplacian and $\Delta^{2}=\Delta \Delta$.

[Hint: Use regularity of the solution of the Dirichlet problem for the Poisson equation.]

(b) Let $\Omega \subset \mathbb{R}^{n}$ be a bounded domain with smooth boundary. Let $u \in H^{1}(\Omega)$ and denote

$\bar{u}=\int_{\Omega} u d^{n} x / \int_{\Omega} d^{n} x$

The following Poincaré-type inequality is known to hold

$\|u-\bar{u}\|_{L^{2}} \leqslant C\|\nabla u\|_{L^{2}}$

where $C$ only depends on $\Omega$. Use the Lax-Milgram lemma and this Poincaré-type inequality to prove that the Neumann problem

$\begin{aligned} &\Delta u=f \text { in } \Omega \\ &\frac{\partial u}{\partial \gamma}=0 \text { on } \partial \Omega \end{aligned}$

has a unique weak solution in the space

$H_{-}^{1}(\Omega)=H^{1}(\Omega) \cap\{u: \Omega \rightarrow \mathbb{R} ; \bar{u}=0\}$

if and only if $\bar{f}=0$.

Paper 2, Section II, C

commentConsider a joint eigenstate of $\mathbf{J}^{2}$ and $J_{3},|j m\rangle$. Write down a unitary operator $U(\mathbf{n}, \theta)$ for rotation of the state by an angle $\theta$ about an axis with direction $\mathbf{n}$, where $\mathbf{n}$ is a unit vector. How would a state with zero orbital angular momentum transform under such a rotation?

What is the relation between the angular momentum operator $\mathbf{J}$ and the Pauli matrices $\boldsymbol{\sigma}$ when $j=\frac{1}{2}$ ? Explicitly calculate $(\mathbf{J} \cdot \mathbf{a})^{2}$, for an arbitrary real vector $\mathbf{a}$, in this case. What are the eigenvalues of the operator $\mathbf{J} \cdot \mathbf{a}$ ? Show that the unitary rotation operator for $j=\frac{1}{2}$ can be expressed as

$U(\mathbf{n}, \theta)=\cos \frac{\theta}{2}-i \mathbf{n} \cdot \boldsymbol{\sigma} \sin \frac{\theta}{2}$

Starting with a state $\left|\frac{1}{2} m\right\rangle$ the component of angular momentum along a direction $\mathbf{n}^{\prime}$, making and angle $\theta$ with the $z$-axis, is susequently measured to be $m^{\prime}$. Immediately after this measurement the state is $\left|\frac{1}{2} m^{\prime}\right\rangle_{\theta}$. Write down an eigenvalue equation for $\left|\frac{1}{2} m^{\prime}\right\rangle_{\theta}$ in terms of $\mathbf{n}^{\prime} \cdot \mathbf{J}$. Show that the probability for measuring an angular momentum of $m^{\prime} \hbar$ along the direction $\mathbf{n}^{\prime}$ is, assuming $\mathbf{n}^{\prime}$ is in the $x-z$ plane,

$\left|\left\langle\frac{1}{2} m \mid \frac{1}{2} m^{\prime}\right\rangle_{\theta}\right|^{2}=\left|\left\langle\frac{1}{2} m|U(\mathbf{y}, \theta)| \frac{1}{2} m^{\prime}\right\rangle\right|^{2},$

where $\mathbf{y}$ is a unit vector in the $y$-direction. Using $(*)$ show that the probability that $m=+\frac{1}{2}, m^{\prime}=-\frac{1}{2}$ is of the form

$A+B \cos ^{2} \frac{\theta}{2}$

determining the integers $A$ and $B$ in the process.

[Assume $\hbar=1$. The Pauli matrices are

$\sigma_{1}=\left(\begin{array}{ll} 0 & 1 \\ 1 & 0 \end{array}\right), \quad \sigma_{2}=\left(\begin{array}{rr} 0 & -i \\ i & 0 \end{array}\right), \quad \sigma_{3}=\left(\begin{array}{rr} 1 & 0 \\ 0 & -1 \end{array}\right)$

Paper 2, Section II, J

commentDefine the Kolmogorov-Smirnov statistic for testing the null hypothesis that real random variables $X_{1}, \ldots, X_{n}$ are independently and identically distributed with specified continuous, strictly increasing distribution function $F$, and show that its null distribution does not depend on $F$.

A composite hypothesis $H_{0}$ specifies that, when the unknown positive parameter $\Theta$ takes value $\theta$, the random variables $X_{1}, \ldots, X_{n}$ arise independently from the uniform distribution $\mathrm{U}[0, \theta]$. Letting $J:=\arg \max _{1 \leqslant i \leqslant n} X_{i}$, show that, under $H_{0}$, the statistic $\left(J, X_{J}\right)$ is sufficient for $\Theta$. Show further that, given $\left\{J=j, X_{j}=\xi\right\}$, the random variables $\left(X_{i}: i \neq j\right)$ are independent and have the $\mathrm{U}[0, \xi]$ distribution. How might you apply the Kolmogorov-Smirnov test to test the hypothesis $H_{0}$ ?

Paper 2, Section II, I

commentShow that any two probability measures which agree on a $\pi$-system also agree on the $\sigma$-algebra generated by that $\pi$-system.

State Fubini's theorem for non-negative measurable functions.

Let $\mu$ denote Lebesgue measure on $\mathbb{R}^{2}$. Fix $s \in[0,1)$. Set $c=\sqrt{1-s^{2}}$ and $\lambda=\sqrt{c}$. Consider the linear maps $f, g, h: \mathbb{R}^{2} \rightarrow \mathbb{R}^{2}$ given by

$f(x, y)=\left(\lambda^{-1} x, \lambda y\right), \quad g(x, y)=(x, s x+y), \quad h(x, y)=(x-s y, y)$

Show that $\mu=\mu \circ f^{-1}$ and that $\mu=\mu \circ g^{-1}$. You must justify any assertion you make concerning the values taken by $\mu$.

Compute $r=f \circ h \circ g \circ f$. Deduce that $\mu$ is invariant under rotations.

Paper 2, Section II, F

commentDefine the concepts of induction and restriction of characters. State and prove the Frobenius Reciprocity Theorem.

Let $H$ be a subgroup of $G$ and let $g \in G$. We write $\mathcal{C}(g)$ for the conjugacy class of $g$ in $G$, and write $C_{G}(g)$ for the centraliser of $g$ in $G$. Suppose that $H \cap \mathcal{C}(g)$ breaks up into $m$ conjugacy classes of $H$, with representatives $x_{1}, x_{2}, \ldots, x_{m}$.

Let $\psi$ be a character of $H$. Writing $\operatorname{Ind}_{H}^{G}(\psi)$ for the induced character, prove that

(i) if no element of $\mathcal{C}(g)$ lies in $H$, then $\operatorname{Ind}_{H}^{G}(\psi)(g)=0$,

(ii) if some element of $\mathcal{C}(g)$ lies in $H$, then

$\operatorname{Ind}_{H}^{G}(\psi)(g)=\left|C_{G}(g)\right| \sum_{i=1}^{m} \frac{\psi\left(x_{i}\right)}{\left|C_{H}\left(x_{i}\right)\right|} .$

Let $G=S_{4}$ and let $H=\langle a, b\rangle$, where $a=\left(\begin{array}{llll}1 & 2 & 3 & 4\end{array}\right)$ and $b=\left(\begin{array}{l}1\end{array}\right.$ dihedral group and write down its character table. Restrict each $G$-conjugacy class to $H$ and calculate the $H$-conjugacy classes contained in each restriction. Given a character $\psi$ of $H$, express Ind ${ }_{H}^{G}(\psi)(g)$ in terms of $\psi$, where $g$ runs through a set of conjugacy classes of $G$. Use your calculation to find the values of all the irreducible characters of $H$ induced to $G$.

$\begin{aligned} & a=\left(\begin{array}{lllll}1 & 2 & 3 & 5 & 6\end{array}\right)(789101112), \\ & b=\left(\begin{array}{llll}1 & 7 & 4 & 10\end{array}\right)\left(\begin{array}{llll}2 & 12 & 5 & 9\end{array}\right)(368), \end{aligned}$

Paper 2, Section II, G

commentGiven a complete analytic function $\mathcal{F}$ on a domain $U \subset \mathbb{C}$, describe briefly how the space of germs construction yields a Riemann surface $R$ associated to $\mathcal{F}$ together with a covering map $\pi: R \rightarrow U$ (proofs not required).

In the case when $\pi$ is regular, explain briefly how, given a point $P \in U$, any closed curve in $U$ with initial and final points $P$ yields a permutation of the set $\pi^{-1}(P)$.

Now consider the Riemann surface $R$ associated with the complete analytic function

$\left(z^{2}-1\right)^{1 / 2}+\left(z^{2}-4\right)^{1 / 2}$

on $U=\mathbb{C} \backslash\{\pm 1, \pm 2\}$, with regular covering map $\pi: R \rightarrow U$. Which subgroup of the full symmetric group of $\pi^{-1}(P)$ is obtained in this way from all such closed curves (with initial and final points $P)$ ?

Paper 2, Section I, J

commentSuppose you have a parametric model consisting of probability mass functions $f(y ; \theta), \theta \in \Theta \subset \mathbb{R}$. Given a sample $Y_{1}, \ldots, Y_{n}$ from $f(y ; \theta)$, define the maximum likelihood estimator $\hat{\theta}_{n}$ for $\theta$ and, assuming standard regularity conditions hold, state the asymptotic distribution of $\sqrt{n}\left(\hat{\theta}_{n}-\theta\right)$.

Compute the Fisher information of a single observation in the case where $f(y ; \theta)$ is the probability mass function of a Poisson random variable with parameter $\theta$. If $Y_{1}, \ldots, Y_{n}$ are independent and identically distributed random variables having a Poisson distribution with parameter $\theta$, show that $\bar{Y}=\frac{1}{n} \sum_{i=1}^{n} Y_{i}$ and $S=\frac{1}{n-1} \sum_{i=1}^{n}\left(Y_{i}-\bar{Y}\right)^{2}$ are unbiased estimators for $\theta$. Without calculating the variance of $S$, show that there is no reason to prefer $S$ over $\bar{Y}$.

[You may use the fact that the asymptotic variance of $\sqrt{n}\left(\hat{\theta}_{n}-\theta\right)$ is a lower bound for the variance of any unbiased estimator.]

Paper 2, Section II, C

commentConsider a 3-dimensional gas of $N$ non-interacting particles in a box of size $L$ where the allowed momenta are $\left\{\mathbf{p}_{i}\right\}$. Assuming the particles have an energy $\epsilon(|\mathbf{p}|), \epsilon^{\prime}(p)>0$, calculate the density of states $g(\epsilon) d \epsilon$ as $L \rightarrow \infty$.

Treating the particles as classical explain why the partition function is

$Z=\frac{z^{N}}{N !}, \quad z=\int_{0}^{\infty} d \epsilon g(\epsilon) e^{-\epsilon / k T}$

Obtain an expression for the total energy $E$.

Why is $\mathbf{p}_{i} \propto 1 / L ?$ By considering the dependence of the energies on the volume $V$ show that the pressure $P$ is given by

$P V=\frac{N}{3 z} \int_{0}^{\infty} d \epsilon g(\epsilon) p \epsilon^{\prime}(p) e^{-\epsilon / k T}$

What are the results for the pressure for non-relativistic particles and also for relativistic particles when their mass can be neglected?

What is the thermal wavelength for non-relativistic particles? Why are the classical results correct if the thermal wavelength is much smaller than the mean particle separation?

Paper 2, Section II, I

commentWhat is a martingale? What is a supermartingale? What is a stopping time?

Let $M=\left(M_{n}\right)_{n \geqslant 0}$ be a martingale and $\hat{M}=\left(\hat{M}_{n}\right)_{n \geqslant 0}$ a supermartingale with respect to a common filtration. If $M_{0}=\hat{M}_{0}$, show that $\mathbb{E} M_{T} \geqslant \mathbb{E} \hat{M}_{T}$ for any bounded stopping time $T$.

[If you use a general result about supermartingales, you must prove it.]

Consider a market with one stock with prices $S=\left(S_{n}\right)_{n \geqslant 0}$ and constant interest rate $r$. Explain why an investor's wealth $X$ satisfies

$X_{n}=(1+r) X_{n-1}+\pi_{n}\left[S_{n}-(1+r) S_{n-1}\right]$

where $\pi_{n}$ is the number of shares of the stock held during the $n$th period.

Given an initial wealth $X_{0}$, an investor seeks to maximize $\mathbb{E} U\left(X_{N}\right)$ where $U$ is a given utility function. Suppose the stock price is such that $S_{n}=S_{n-1} \xi_{n}$ where $\left(\xi_{n}\right)_{n} \geqslant 1$ is a sequence of independent and identically distributed random variables. Let $V$ be defined inductively by

$V(n, x, s)=\sup _{p \in \mathbb{R}} \mathbb{E} V\left[n+1,(1+r) x-p s\left(1+r-\xi_{1}\right), s \xi_{1}\right]$

with terminal condition $V(N, x, s)=U(x)$ for all $x, s \in \mathbb{R}$.

Show that the process $\left(V\left(n, X_{n}, S_{n}\right)\right)_{0 \leqslant n \leqslant N}$ is a supermartingale for any trading strategy $\pi$.

Suppose $\pi^{*}$ is a trading strategy such that the corresponding wealth process $X^{*}$ makes $\left(V\left(n, X_{n}^{*}, S_{n}\right)\right)_{0} \leqslant n \leqslant N$ a martingale. Show that $\pi^{*}$ is optimal.

Paper 2, Section I, F

comment(a) State the Weierstrass approximation theorem concerning continuous real functions on the closed interval $[0,1]$.

(b) Let $f:[0,1] \rightarrow \mathbb{R}$ be continuous.

(i) If $\int_{0}^{1} f(x) x^{n} d x=0$ for each $n=0,1,2, \ldots$, prove that $f$ is the zero function.

(ii) If we only assume that $\int_{0}^{1} f(x) x^{2 n} d x=0$ for each $n=0,1,2, \ldots$, prove that it still follows that $f$ is the zero function.

[If you use the Stone-Weierstrass theorem, you must prove it.]

(iii) If we only assume that $\int_{0}^{1} f(x) x^{2 n+1} d x=0$ for each $n=0,1,2, \ldots$, does it still follow that $f$ is the zero function? Justify your answer.

Paper 2, Section II, 11F

Let

$B_{r}(0)=\left\{(x, y) \in \mathbb{R}^{2}: x^{2}+y^{2}<r^{2}\right\},$

$B=B_{1}(0)$, and

$C=\left\{(x, y) \in \mathbb{R}^{2}: x^{2}+y^{2}=1\right\}$

Let $D=B \cup C$.

(i) State the Brouwer fixed point theorem on the plane.

(ii) Show that the Brouwer fixed point theorem on the plane is equivalent to the nonexistence of a continuous map $F: D \rightarrow C$ such that $F(p)=p$