Part II, 2016, Paper 2

# Part II, 2016, Paper 2

### Jump to course

Paper 2, Section II, H

commentIn this question we work over an algebraically closed field of characteristic zero. Let $X^{o}=Z\left(x^{6}+x y^{5}+y^{6}-1\right) \subset \mathbb{A}^{2}$ and let $X \subset \mathbb{P}^{2}$ be the closure of $X^{o}$ in $\mathbb{P}^{2} .$

(a) Show that $X$ is a non-singular curve.

(b) Show that $\omega=d x /\left(5 x y^{4}+6 y^{5}\right)$ is a regular differential on $X$.

(c) Compute the divisor of $\omega$. What is the genus of $X$ ?

Paper 2, Section II, G

comment(a) Let $K, L$ be simplicial complexes, and $f:|K| \rightarrow|L|$ a continuous map. What does it mean to say that $g: K \rightarrow L$ is a simplicial approximation to $f ?$

(b) Define the barycentric subdivision of a simplicial complex $K$, and state the Simplicial Approximation Theorem.

(c) Show that if $g$ is a simplicial approximation to $f$ then $f \simeq|g|$.

(d) Show that the natural inclusion $\left|K^{(1)}\right| \rightarrow|K|$ induces a surjective map on fundamental groups.

Paper 2, Section II, A

commentA particle of mass $m$ moves in three dimensions subject to a potential $V(\mathbf{r})$ localised near the origin. The wavefunction for a scattering process with incident particle of wavevector $\mathbf{k}$ is denoted $\psi(\mathbf{k}, \mathbf{r})$. With reference to the asymptotic form of $\psi$, define the scattering amplitude $f\left(\mathbf{k}, \mathbf{k}^{\prime}\right)$, where $\mathbf{k}^{\prime}$ is the wavevector of the outgoing particle with $\left|\mathbf{k}^{\prime}\right|=|\mathbf{k}|=k$.

By recasting the Schrödinger equation for $\psi(\mathbf{k}, \mathbf{r})$ as an integral equation, show that

$f\left(\mathbf{k}, \mathbf{k}^{\prime}\right)=-\frac{m}{2 \pi \hbar^{2}} \int d^{3} \mathbf{r}^{\prime} \exp \left(-i \mathbf{k}^{\prime} \cdot \mathbf{r}^{\prime}\right) V\left(\mathbf{r}^{\prime}\right) \psi\left(\mathbf{k}, \mathbf{r}^{\prime}\right)$

[You may assume that

$\mathcal{G}(k ; \mathbf{r})=-\frac{1}{4 \pi|\mathbf{r}|} \exp (i k|\mathbf{r}|)$

is the Green's function for $\nabla^{2}+k^{2}$ which obeys the appropriate boundary conditions for a scattering solution.]

Now suppose $V(\mathbf{r})=\lambda U(\mathbf{r})$, where $\lambda \ll 1$ is a dimensionless constant. Determine the first two non-zero terms in the expansion of $f\left(\mathbf{k}, \mathbf{k}^{\prime}\right)$ in powers of $\lambda$, giving each term explicitly as an integral over one or more position variables $\mathbf{r}, \mathbf{r}^{\prime}, \ldots$

Evaluate the contribution to $f\left(\mathbf{k}, \mathbf{k}^{\prime}\right)$ of order $\lambda$ in the case $U(\mathbf{r})=\delta(|\mathbf{r}|-a)$, expressing the answer as a function of $a, k$ and the scattering angle $\theta$ (defined so that $\left.\mathbf{k} \cdot \mathbf{k}^{\prime}=k^{2} \cos \theta\right)$.

Paper 2, Section II, J

comment(a) Define an $M / M / \infty$ queue and write without proof its stationary distribution. State Burke's theorem for an $M / M / \infty$ queue.

(b) Let $X$ be an $M / M / \infty$ queue with arrival rate $\lambda$ and service rate $\mu$ started from the stationary distribution. For each $t$, denote by $A_{1}(t)$ the last time before $t$ that a customer departed the queue and $A_{2}(t)$ the first time after $t$ that a customer departed the queue. If there is no arrival before time $t$, then we set $A_{1}(t)=0$. What is the limit as $t \rightarrow \infty$ of $\mathbb{E}\left[A_{2}(t)-A_{1}(t)\right]$ ? Explain.

(c) Consider a system of $N$ queues serving a finite number $K$ of customers in the following way: at station $1 \leqslant i \leqslant N$, customers are served immediately and the service times are independent exponentially distributed with parameter $\mu_{i}$; after service, each customer goes to station $j$ with probability $p_{i j}>0$. We assume here that the system is closed, i.e., $\sum_{j} p_{i j}=1$ for all $1 \leqslant i \leqslant N$.

Let $S=\left\{\left(n_{1}, \ldots, n_{N}\right): n_{i} \in \mathbb{N}, \sum_{i=1}^{N} n_{i}=K\right\}$ be the state space of the Markov chain. Write down its $Q$-matrix. Also write down the $Q$-matrix $R$ corresponding to the position in the network of one customer (that is, when $K=1$ ). Show that there is a unique distribution $\left(\lambda_{i}\right)_{1 \leqslant i \leqslant N}$ such that $\lambda R=0$. Show that

$\pi(n)=C_{N} \prod_{i=1}^{N} \frac{\lambda_{i}^{n_{i}}}{n_{i} !}, \quad n=\left(n_{1}, \ldots, n_{N}\right) \in S$

defines an invariant measure for the chain. Are the queue lengths independent at equilibrium?

Paper 2, Section II, C

commentWhat is meant by the asymptotic relation

$f(z) \sim g(z) \quad \text { as } \quad z \rightarrow z_{0}, \operatorname{Arg}\left(z-z_{0}\right) \in\left(\theta_{0}, \theta_{1}\right) ?$

Show that

$\sinh \left(z^{-1}\right) \sim \frac{1}{2} \exp \left(z^{-1}\right) \quad \text { as } \quad z \rightarrow 0, \operatorname{Arg} z \in(-\pi / 2, \pi / 2),$

and find the corresponding result in the sector $\operatorname{Arg} z \in(\pi / 2,3 \pi / 2)$.

What is meant by the asymptotic expansion

$f(z) \sim \sum_{j=0}^{\infty} c_{j}\left(z-z_{0}\right)^{j} \quad \text { as } \quad z \rightarrow z_{0}, \operatorname{Arg}\left(z-z_{0}\right) \in\left(\theta_{0}, \theta_{1}\right) ?$

Show that the coefficients $\left\{c_{j}\right\}_{j=0}^{\infty}$ are determined uniquely by $f$. Show that if $f$ is analytic at $z_{0}$, then its Taylor series is an asymptotic expansion for $f$ as $z \rightarrow z_{0}\left(\right.$ for any $\left.\operatorname{Arg}\left(z-z_{0}\right)\right)$.

Show that

$u(x, t)=\int_{-\infty}^{\infty} \exp \left(-i k^{2} t+i k x\right) f(k) d k$

defines a solution of the equation $i \partial_{t} u+\partial_{x}^{2} u=0$ for any smooth and rapidly decreasing function $f$. Use the method of stationary phase to calculate the leading-order behaviour of $u(\lambda t, t)$ as $t \rightarrow+\infty$, for fixed $\lambda$.

Paper 2, Section $\mathbf{I}$, $4 F$

comment(a) Which of the following are regular languages? Justify your answers.

(i) $\left\{w \in\{a, b\}^{*} \mid w\right.$ is a nonempty string of alternating $a$ 's and $b$ 's $\}$.

(ii) $\left\{w a b w \mid w \in\{a, b\}^{*}\right\}$.

(b) Write down a nondeterministic finite-state automaton with $\epsilon$-transitions which accepts the language given by the regular expression $(\mathbf{a}+\mathbf{b})^{*}(\mathbf{b} \mathbf{b}+\mathbf{a}) \mathbf{b}$. Describe in words what this language is.

(c) Is the following language regular? Justify your answer.

$\left\{w \in\{a, b\}^{*} \mid w \text { does not end in } a b \text { or } b b b\right\}$

Paper 2, Section I, E

commentConsider the Lagrangian

$L=A\left(\dot{\theta}^{2}+\dot{\phi}^{2} \sin ^{2} \theta\right)+B(\dot{\psi}+\dot{\phi} \cos \theta)^{2}-C(\cos \theta)^{k}$

where $A, B, C$ are positive constants and $k$ is a positive integer. Find three conserved quantities and show that $u=\cos \theta$ satisfies

$\dot{u}^{2}=f(u)$

where $f(u)$ is a polynomial of degree $k+2$ which should be determined.

Paper 2, Section II, E

commentDefine what it means for the transformation $\mathbb{R}^{2 n} \rightarrow \mathbb{R}^{2 n}$ given by

$\left(q_{i}, p_{i}\right) \mapsto\left(Q_{i}\left(q_{j}, p_{j}\right), P_{i}\left(q_{j}, p_{j}\right)\right), \quad i, j=1, \ldots, n$

to be canonical. Show that a transformation is canonical if and only if

$\left\{Q_{i}, Q_{j}\right\}=0, \quad\left\{P_{i}, P_{j}\right\}=0, \quad\left\{Q_{i}, P_{j}\right\}=\delta_{i j}$

Show that the transformation $\mathbb{R}^{2} \rightarrow \mathbb{R}^{2}$ given by

$Q=q \cos \epsilon-p \sin \epsilon, \quad P=q \sin \epsilon+p \cos \epsilon$

is canonical for any real constant $\epsilon$. Find the corresponding generating function.

Paper 2, Section I, G

commentShow that the binary channel with channel matrix

$\left(\begin{array}{ll} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \end{array}\right)$

has capacity $\log 5-2$.

Paper 2, Section II, G

commentDefine a $B C H$ code of length $n$, where $n$ is odd, over the field of 2 elements with design distance $\delta$. Show that the minimum weight of such a code is at least $\delta$. [Results about the Vandermonde determinant may be quoted without proof, provided they are stated clearly.]

Let $\omega \in \mathbb{F}_{16}$ be a root of $X^{4}+X+1$. Let $C$ be the $\mathrm{BCH}$ code of length 15 with defining set $\left\{\omega, \omega^{2}, \omega^{3}, \omega^{4}\right\}$. Find the generator polynomial of $C$ and the rank of $C$. Determine the error positions of the following received words:

(i) $r(X)=1+X^{6}+X^{7}+X^{8}$,

(ii) $r(X)=1+X+X^{4}+X^{5}+X^{6}+X^{9}$.

Paper 2, Section I, C

commentA spherical cloud of mass $M$ has radius $r(t)$ and initial radius $r(0)=R$. It contains material with uniform mass density $\rho(t)$, and zero pressure. Ignoring the cosmological constant, show that if it is initially at rest at $t=0$ and the subsequent gravitational collapse is governed by Newton's law $\ddot{r}=-G M / r^{2}$, then

$\dot{r}^{2}=2 G M\left(\frac{1}{r}-\frac{1}{R}\right) .$

Suppose $r$ is given parametrically by

$r=R \cos ^{2} \theta$

where $\theta=0$ at $t=0$. Derive a relation between $\theta$ and $t$ and hence show that the cloud collapses to radius $r=0$ at

$t=\sqrt{\frac{3 \pi}{32 G \rho_{0}}},$

where $\rho_{0}$ is the initial mass density of the cloud.

Paper 2, Section II, G

commentIf an embedded surface $S \subset \mathbf{R}^{3}$ contains a line $L$, show that the Gaussian curvature is non-positive at each point of $L$. Give an example where the Gaussian curvature is zero at each point of $L$.

Consider the helicoid $S$ given as the image of $\mathbf{R}^{2}$ in $\mathbf{R}^{3}$ under the map

$\phi(u, v)=(\sinh v \cos u, \sinh v \sin u, u) .$

What is the image of the corresponding Gauss map? Show that the Gaussian curvature at a point $\phi(u, v) \in S$ is given by $-1 / \cosh ^{4} v$, and hence is strictly negative everywhere. Show moreover that there is a line in $S$ passing through any point of $S$.

[General results concerning the first and second fundamental forms on an oriented embedded surface $S \subset \mathbf{R}^{3}$ and the Gauss map may be used without proof in this question.]

Paper 2, Section II, E

commentConsider the nonlinear oscillator

$\begin{aligned} \dot{x} &=y-\mu x\left(\frac{1}{2}|x|-1\right), \\ \dot{y} &=-x \end{aligned}$

(a) Use the Hamiltonian for $\mu=0$ to find a constraint on the size of the domain of stability of the origin when $\mu<0$.

(b) Assume that given $\mu>0$ there exists an $R$ such that all trajectories eventually remain within the region $|\mathbf{x}| \leqslant R$. Show that there must be a limit cycle, stating carefully any result that you use. [You need not show that there is only one periodic orbit.]

(c) Use the energy-balance method to find the approximate amplitude of the limit cycle for $0<\mu \ll 1$.

(d) Find the approximate shape of the limit cycle for $\mu \gg 1$, and calculate the leading-order approximation to its period.

Paper 2, Section II, B

commentFor a two-dimensional flow in plane polar coordinates $(r, \theta)$, state the relationship between the streamfunction $\psi(r, \theta)$ and the flow components $u_{r}$ and $u_{\theta}$. Show that the vorticity $\omega$ is given by $\omega=-\nabla^{2} \psi$, and deduce that the streamfunction for a steady two-dimensional Stokes flow satisfies the biharmonic equation

$\nabla^{4} \psi=0$

A rigid stationary circular disk of radius $a$ occupies the region $r \leqslant a$. The flow far from the disk tends to a steady straining flow $\mathbf{u}_{\infty}=(-E x, E y)$, where $E$ is a constant. Inertial forces may be neglected. Calculate the streamfunction, $\psi_{\infty}(r, \theta)$, for the far-field flow.

By making an appropriate assumption about its dependence on $\theta$, find the streamfunction $\psi$ for the flow around the disk, and deduce the flow components, $u_{r}(r, \theta)$ and $u_{\theta}(r, \theta)$.

Calculate the tangential surface stress, $\sigma_{r \theta}$, acting on the boundary of the disk.

$[$ Hints: In plane polar coordinates $(r, \theta)$,

$\begin{gathered} \boldsymbol{\nabla} \cdot \mathbf{u}=\frac{1}{r} \frac{\partial\left(r u_{r}\right)}{\partial r}+\frac{1}{r} \frac{\partial u_{\theta}}{\partial \theta}, \quad \omega=\frac{1}{r} \frac{\partial\left(r u_{\theta}\right)}{\partial r}-\frac{1}{r} \frac{\partial u_{r}}{\partial \theta} \\ \nabla^{2} V=\frac{1}{r} \frac{\partial}{\partial r}\left(r \frac{\partial V}{\partial r}\right)+\frac{1}{r^{2}} \frac{\partial^{2} V}{\partial \theta^{2}}, \quad e_{r \theta}=\frac{1}{2}\left(r \frac{\partial}{\partial r}\left(\frac{u_{\theta}}{r}\right)+\frac{1}{r} \frac{\partial u_{r}}{\partial \theta}\right) \end{gathered}$

Paper 2, Section I, A

commentThe Euler product formula for the Gamma function is

$\Gamma(z)=\lim _{n \rightarrow \infty} \frac{n ! n^{z}}{z(z+1) \ldots(z+n)}$

Use this to show that

$\frac{\Gamma(2 z)}{2^{2 z} \Gamma(z) \Gamma\left(z+\frac{1}{2}\right)}=c,$

where $c$ is a constant, independent of $z$. Find the value of $c$.

Paper 2, Section II, A

commentThe Hurwitz zeta function $\zeta_{\mathrm{H}}(s, q)$ is defined for $\operatorname{Re}(q)>0$ by

$\zeta_{\mathrm{H}}(s, q)=\sum_{n=0}^{\infty} \frac{1}{(q+n)^{s}}$

State without proof the complex values of $s$ for which this series converges.

Consider the integral

$I(s, q)=\frac{\Gamma(1-s)}{2 \pi i} \int_{\mathcal{C}} d z \frac{z^{s-1} e^{q z}}{1-e^{z}}$

where $\mathcal{C}$ is the Hankel contour. Show that $I(s, q)$ provides an analytic continuation of the Hurwitz zeta function for all $s \neq 1$. Include in your account a careful discussion of removable singularities. [Hint: $\Gamma(s) \Gamma(1-s)=\pi / \sin (\pi s)$.]

Show that $I(s, q)$ has a simple pole at $s=1$ and find its residue.

Paper 2, Section II, H

comment(a) Let $K \subseteq L$ be a finite separable field extension. Show that there exist only finitely many intermediate fields $K \subseteq F \subseteq L$.

(b) Define what is meant by a normal extension. Is $\mathbb{Q} \subseteq \mathbb{Q}(\sqrt{1+\sqrt{7}})$ a normal extension? Justify your answer.

(c) Prove Artin's lemma, which states: if $K \subseteq L$ is a field extension, $H$ is a finite subgroup of $\operatorname{Aut}_{K}(L)$, and $F:=L^{H}$ is the fixed field of $H$, then $F \subseteq L$ is a Galois extension with $\operatorname{Gal}(L / F)=H$.

Paper 2, Section II, D

commentThe Kasner (vacuum) cosmological model is defined by the line element

$d s^{2}=-c^{2} d t^{2}+t^{2 p_{1}} d x^{2}+t^{2 p_{2}} d y^{2}+t^{2 p_{3}} d z^{2} \quad \text { with } \quad t>0$

where $p_{1}, p_{2}, p_{3}$ are constants with $p_{1}+p_{2}+p_{3}=p_{1}^{2}+p_{2}^{2}+p_{3}^{2}=1$ and $0<p_{1}<1$. Show that $p_{2} p_{3}<0$.

Write down four equations that determine the null geodesics of the Kasner model.

If $k^{a}$ is the tangent vector to the trajectory of a photon and $u^{a}$ is the four-velocity of a comoving observer (i.e., an observer at rest in the $(t, x, y, z)$ coordinate system above), what is the physical interpretation of $k_{a} u^{a}$ ?

Let $O$ be a comoving observer at the origin, $x=y=z=0$, and let $S$ be a comoving source of photons located on one of the spatial coordinate axes.

(i) Show that photons emitted by $S$ and observed by $O$ can be either redshifted or blue-shifted, depending on the location of $S$.

(ii) Given any fixed time $t=T$, show that there are locations for $S$ on each coordinate axis from which no photons reach $O$ for $t \leqslant T$.

Now suppose that $p_{1}=1$ and $p_{2}=p_{3}=0$. Does the property in (ii) still hold?

Paper 2, Section II, G

commentDefine the Turán graph $T_{r}(n)$, where $r$ and $n$ are positive integers with $n \geqslant r$. For which $r$ and $n$ is $T_{r}(n)$ regular? For which $r$ and $n$ does $T_{r}(n)$ contain $T_{4}(8)$ as a subgraph?

State and prove Turán's theorem.

Let $x_{1}, \ldots, x_{n}$ be unit vectors in the plane. Prove that the number of pairs $i<j$ for which $x_{i}+x_{j}$ has length less than 1 is at most $\left\lfloor n^{2} / 4\right\rfloor$.

Paper 2, Section II, D

commentWhat does it mean for $g^{\epsilon}:(x, u) \mapsto(\tilde{x}, \tilde{u})$ to describe a 1-parameter group of transformations? Explain how to compute the vector field

$V=\xi(x, u) \frac{\partial}{\partial x}+\eta(x, u) \frac{\partial}{\partial u}$

that generates such a 1-parameter group of transformations.

Suppose now $u=u(x)$. Define the $n$th prolongation, $\mathrm{pr}^{(n)} g^{\epsilon}$, of $g^{\epsilon}$ and the vector field which generates it. If $V$ is defined by $(*)$ show that

$\mathrm{pr}^{(n)} V=V+\sum_{k=1}^{n} \eta_{k} \frac{\partial}{\partial u^{(k)}}$

where $u^{(k)}=\mathrm{d}^{k} u / \mathrm{d} x^{k}$ and $\eta_{k}$ are functions to be determined.

The curvature of the curve $u=u(x)$ in the $(x, u)$-plane is given by

$\kappa=\frac{u_{x x}}{\left(1+u_{x}^{2}\right)^{3 / 2}}$

Rotations in the $(x, u)$-plane are generated by the vector field

$W=x \frac{\partial}{\partial u}-u \frac{\partial}{\partial x}$

Show that the curvature $\kappa$ at a point along a plane curve is invariant under such rotations. Find two further transformations that leave $\kappa$ invariant.

Paper 2, Section II, I

comment(a) Let $K$ be a topological space and let $C_{\mathbb{R}}(K)$ denote the normed vector space of bounded continuous real-valued functions on $K$ with the norm $\|f\|_{C_{\mathbb{R}}(K)}=\sup _{x \in K}|f(x)|$. Define the terms uniformly bounded, equicontinuous and relatively compact as applied to subsets $S \subset C_{\mathbb{R}}(K)$.

(b) The Arzela-Ascoli theorem [which you need not prove] states in particular that if $K$ is compact and $S \subset C_{\mathbb{R}}(K)$ is uniformly bounded and equicontinuous, then $S$ is relatively compact. Show by examples that each of the compactness of $K$, uniform boundedness of $S$, and equicontinuity of $S$ are necessary conditions for this conclusion.

(c) Let $L$ be a topological space. Assume that there exists a sequence of compact subsets $K_{n}$ of $L$ such that $K_{1} \subset K_{2} \subset K_{3} \subset \cdots \subset L$ and $\bigcup_{n=1}^{\infty} K_{n}=L$. Suppose $S \subset C_{\mathbb{R}}(L)$ is uniformly bounded and equicontinuous and moreover satisfies the condition that, for every $\epsilon>0$, there exists $n \in \mathbb{N}$ such that $|f(x)|<\epsilon$ for every $x \in L \backslash K_{n}$ and for every $f \in S$. Show that $S$ is relatively compact.

Paper 2, Section II, F

commentDefine the von Neumann hierarchy of sets $V_{\alpha}$, and show that each $V_{\alpha}$ is a transitive set. Explain what is meant by saying that a binary relation on a set is well-founded and extensional. State Mostowski's Theorem.

Let $r$ be the binary relation on $\omega$ defined by: $\langle m, n\rangle \in r$ if and only if $2^{m}$ appears in the base-2 expansion of $n$ (i.e., the unique expression for $n$ as a sum of distinct powers of 2 ). Show that $r$ is well-founded and extensional. To which transitive set is $(\omega, r)$ isomorphic? Justify your answer.

Paper 2, Section I, B

comment(a) The populations of two competing species satisfy

$\begin{aligned} \frac{d N_{1}}{d t} &=N_{1}\left[b_{1}-\lambda\left(N_{1}+N_{2}\right)\right] \\ \frac{d N_{2}}{d t} &=N_{2}\left[b_{2}-\lambda\left(N_{1}+N_{2}\right)\right] \end{aligned}$

where $b_{1}>b_{2}>0$ and $\lambda>0$. Sketch the phase diagram (limiting attention to $\left.N_{1}, N_{2} \geqslant 0\right)$.

The relative abundance of species 1 is defined by $U=N_{1} /\left(N_{1}+N_{2}\right)$. Show that

$\frac{d U}{d t}=A U(1-U)$

where $A$ is a constant that should be determined.

(b) Consider the spatial system

$\frac{\partial u}{\partial t}=u(1-u)+D \frac{\partial^{2} u}{\partial x^{2}}$

and consider a travelling-wave solution of the form $u(x, t)=f(x-c t)$ representing one species $(u=1)$ invading territory previously occupied by another species $(u=0)$. By linearising near the front of the invasion, show that the wave speed is given by $c=2 \sqrt{D}$.

[You may assume that the solution to the full nonlinear system will settle to the slowest possible linear wave speed.]

Paper 2, Section II, F

comment(a) Prove that $5+2 \sqrt{6}$ is a fundamental unit in $\mathbb{Q}(\sqrt{6})$. [You may not assume the continued fraction algorithm.]

(b) Determine the ideal class group of $\mathbb{Q}(\sqrt{-55})$.

Paper 2, Section I, I

commentDefine the Legendre symbol and the Jacobi symbol. Compute the Jacobi symbols $\left(\frac{202}{11189}\right)$ and $\left(\frac{974}{1001}\right)$, stating clearly any properties of these symbols that you use.

Paper 2, Section II, B

comment(a) The advection equation

$u_{t}=u_{x}, \quad 0 \leqslant x \leqslant 1, t \geqslant 0$

is discretised using an equidistant grid with stepsizes $\Delta x=h$ and $\Delta t=k$. The spatial derivatives are approximated with central differences and the resulting ODEs are approximated with the trapezoidal rule. Write down the relevant difference equation for determining $\left(u_{m}^{n+1}\right)$ from $\left(u_{m}^{n}\right)$. What is the name of this scheme? What is the local truncation error?

The boundary condition is periodic, $u(0, t)=u(1, t)$. Explain briefly how to write the discretised scheme in the form $B \mathbf{u}^{n+1}=C \mathbf{u}^{n}$, where the matrices $B$ and $C$, to be identified, have a circulant form. Using matrix analysis, find the range of $\mu=\Delta t / \Delta x$ for which the scheme is stable. [Standard results may be used without proof if quoted carefully.]

[Hint: An $n \times n$ circulant matrix has the form

$A=\left(\begin{array}{cccc} a_{0} & a_{1} & \cdots & a_{n-1} \\ a_{n-1} & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & a_{1} \\ a_{1} & \cdots & a_{n-1} & a_{0} \end{array}\right)$

All such matrices have the same set of eigenvectors $\mathbf{v}_{\ell}=\left(\omega^{j \ell}\right)_{j=0}^{n-1}, \ell=0,1, \ldots, n-1$, where $\omega=e^{2 \pi i / n}$, and the corresponding eigenvalues are $\lambda_{\ell}=\sum_{k=0}^{n-1} a_{k} \omega^{k \ell}$.]

(b) Consider the advection equation on the unit square

$u_{t}=a u_{x}+b u_{y}, \quad 0 \leqslant x, y \leqslant 1, t \geqslant 0$

where $u$ satisfies doubly periodic boundary conditions, $u(0, y)=u(1, y), u(x, 0)=u(x, 1)$, and $a(x, y)$ and $b(x, y)$ are given doubly periodic functions. The system is discretised with the Crank-Nicolson scheme, with central differences for the space derivatives, using an equidistant grid with stepsizes $\Delta x=\Delta y=h$ and $\Delta t=k$. Write down the relevant difference equation, and show how to write the scheme in the form

$\mathbf{u}^{n+1}=\left(I-\frac{1}{4} \mu A\right)^{-1}\left(I+\frac{1}{4} \mu A\right) \mathbf{u}^{n}$

where the matrix $A$ should be identified. Describe how (*) can be approximated by Strang splitting, and explain the advantages of doing so.

[Hint: Inversion of the matrix $B$ in part (a) has a similar computational cost to that of a tridiagonal matrix.]

Paper 2, Section II, K

commentConsider a Markov decision problem with finite state space $X$, value function $F$ and dynamic programming equation $F=\mathcal{L} F$, where

$(\mathcal{L} \phi)(i)=\min _{a \in\{0,1\}}\left\{c(i, a)+\beta \sum_{j \in X} P_{i j}(a) \phi(j)\right\} .$

Suppose $0<\beta<1$, and $|c(i, a)| \leqslant B$ for all $i \in X, a \in\{0,1\}$. Prove there exists a deterministic stationary Markov policy that is optimal, explaining what the italicised words mean.

Let $F_{n}=\mathcal{L}^{n} F_{0}$, where $F_{0}=0$, and $M_{n}=\max _{i \in X}\left|F(i)-F_{n}(i)\right|$. Prove that

$M_{n} \leqslant \beta M_{n-1} \leqslant \beta^{n} B /(1-\beta) .$

Deduce that the value iteration algorithm converges to an optimal policy in a finite number of iterations.

Paper 2, Section II, A

comment(a) Let $|j m\rangle$ be standard, normalised angular momentum eigenstates with labels specifying eigenvalues for $\mathbf{J}^{2}$ and $J_{3}$. Taking units in which $\hbar=1$,

$J_{\pm}|j m\rangle=\{(j \mp m)(j \pm m+1)\}^{1 / 2}|j m \pm 1\rangle .$

Check the coefficients above by computing norms of states, quoting any angular momentum commutation relations that you require.

(b) Two particles, each of spin $s>0$, have combined spin states $|J M\rangle$. Find expressions for all such states with $M=2 s-1$ in terms of product states.

(c) Suppose that the particles in part (b) move about their centre of mass with a spatial wavefunction that is a spherically symmetric function of relative position. If the particles are identical, what spin states $|J 2 s-1\rangle$ are allowed? Justify your answer.

(d) Now consider two particles of spin 1 that are not identical and are both at rest. If the 3-component of the spin of each particle is zero, what is the probability that their total, combined spin is zero?

Paper 2, Section II,

comment(a) State and prove the Cramér-Rao inequality in a parametric model $\{f(\theta): \theta \in \Theta\}$, where $\Theta \subseteq \mathbb{R}$. [Necessary regularity conditions on the model need not be specified.]

(b) Let $X_{1}, \ldots, X_{n}$ be i.i.d. Poisson random variables with unknown parameter $E X_{1}=\theta>0$. For $\bar{X}_{n}=(1 / n) \sum_{i=1}^{n} X_{i}$ and $S^{2}=(n-1)^{-1} \sum_{i=1}^{n}\left(X_{i}-\bar{X}_{n}\right)^{2}$ define

$T_{\alpha}=\alpha \bar{X}_{n}+(1-\alpha) S^{2}, \quad 0 \leqslant \alpha \leqslant 1$

Show that $\operatorname{Var}_{\theta}\left(T_{\alpha}\right) \geqslant \operatorname{Var}_{\theta}\left(\bar{X}_{n}\right)$ for all values of $\alpha, \theta$.

Now suppose $\tilde{\theta}=\tilde{\theta}\left(X_{1}, \ldots, X_{n}\right)$ is an estimator of $\theta$ with possibly nonzero bias $B(\theta)=E_{\theta} \tilde{\theta}-\theta$. Suppose the function $B$ is monotone increasing on $(0, \infty)$. Prove that the mean-squared errors satisfy

$E_{\theta}\left(\tilde{\theta}_{n}-\theta\right)^{2} \geqslant E_{\theta}\left(\bar{X}_{n}-\theta\right)^{2} \text { for all } \theta \in \Theta$

Paper 2, Section II, J

comment(a) State Jensen's inequality. Give the definition of $\|\cdot\|_{L^{p}}$ and the space $L^{p}$ for $1<p<\infty$. If $\|f-g\|_{L^{p}}=0$, is it true that $f=g$ ? Justify your answer. State and prove Hölder's inequality using Jensen's inequality.

(b) Suppose that $(E, \mathcal{E}, \mu)$ is a finite measure space. Show that if $1<q<p$ and $f \in L^{p}(E)$ then $f \in L^{q}(E)$. Give the definition of $\|\cdot\|_{L^{\infty}}$ and show that $\|f\|_{L^{p}} \rightarrow\|f\|_{L^{\infty}}$ as $p \rightarrow \infty$.

(c) Suppose that $1<q<p<\infty$. Show that if $f$ belongs to both $L^{p}(\mathbb{R})$ and $L^{q}(\mathbb{R})$, then $f \in L^{r}(\mathbb{R})$ for any $r \in[q, p]$. If $f \in L^{p}(\mathbb{R})$, must we have $f \in L^{q}(\mathbb{R})$ ? Give a proof or a counterexample.

Paper 2, Section II, I

commentShow that the 1-dimensional (complex) characters of a finite group $G$ form a group under pointwise multiplication. Denote this group by $\widehat{G}$. Show that if $g \in G$, the map $\chi \mapsto \chi(g)$ from $\widehat{G}$to $\mathbb{C}$ is a character of $\widehat{G}$, hence an element of $\widehat{G}$. What is the kernel of the $\operatorname{map} G \rightarrow \widehat{\widehat{G}}$?

Show that if $G$ is abelian the map $G \rightarrow \widehat{\widehat{G}}$is an isomorphism. Deduce, from the structure theorem for finite abelian groups, that the groups $G$ and $\widehat{G}$are isomorphic as abstract groups.

Paper 2, Section II, H

commentSuppose that $f: \mathbb{C} / \Lambda_{1} \rightarrow \mathbb{C} / \Lambda_{2}$ is a holomorphic map of complex tori, and let $\pi_{j}$ denote the projection map $\mathbb{C} \rightarrow \mathbb{C} / \Lambda_{j}$ for $j=1,2$. Show that there is a holomorphic map $F: \mathbb{C} \rightarrow \mathbb{C}$ such that $\pi_{2} F=f \pi_{1} .$

Prove that $F(z)=\lambda z+\mu$ for some $\lambda, \mu \in \mathbb{C}$. Hence deduce that two complex tori $\mathbb{C} / \Lambda_{1}$ and $\mathbb{C} / \Lambda_{2}$ are conformally equivalent if and only if the lattices are related by $\Lambda_{2}=\lambda \Lambda_{1}$ for some $\lambda \in \mathbb{C}^{*}$.

Paper 2, Section I, K

commentDefine an exponential dispersion family. Prove that the range of the natural parameter, $\Theta$, is an open interval. Derive the mean and variance as a function of the log normalizing constant.

[Hint: Use the convexity of $e^{x}$, i.e. $e^{p x+(1-p) y} \leqslant p e^{x}+(1-p) e^{y}$ for all $\left.p \in[0,1] .\right]$

Paper 2, Section II, C

comment(a) What is meant by the canonical ensemble? Consider a system in the canonical ensemble that can be in states $|n\rangle, n=0,1,2, \ldots$ with energies $E_{n}$. Write down the partition function for this system and the probability $p(n)$ that the system is in state $|n\rangle$. Derive an expression for the average energy $\langle E\rangle$ in terms of the partition function.

(b) Consider an anharmonic oscillator with energy levels

$\hbar \omega\left[\left(n+\frac{1}{2}\right)+\delta\left(n+\frac{1}{2}\right)^{2}\right], \quad n=0,1,2, \ldots$

where $\omega$ is a positive constant and $0<\delta \ll 1$ is a small constant. Let the oscillator be in contact with a reservoir at temperature $T$. Show that, to linear order in $\delta$, the partition function $Z_{1}$ for the oscillator is given by

$Z_{1}=\frac{c_{1}}{\sinh \frac{x}{2}}\left[1+\delta c_{2} x\left(1+\frac{2}{\sinh ^{2} \frac{x}{2}}\right)\right], \quad x=\frac{\hbar \omega}{k_{B} T}$

where $c_{1}$ and $c_{2}$ are constants to be determined. Also show that, to linear order in $\delta$, the average energy of a system of $N$ uncoupled oscillators of this type is given by

$\langle E\rangle=\frac{N \hbar \omega}{2}\left\{c_{3} \operatorname{coth} \frac{x}{2}+\delta\left[c_{4}+\frac{c_{5}}{\sinh ^{2} \frac{x}{2}}\left(1-x \operatorname{coth} \frac{x}{2}\right)\right]\right\}$

where $c_{3}, c_{4}, c_{5}$ are constants to be determined.

Paper 2, Section II, K

commentIn the context of the Black-Scholes model, let $S_{0}$ be the initial price of the stock, and let $\sigma$ be its volatility. Assume that the risk-free interest rate is zero and the stock pays no dividends. Let $\operatorname{EC}\left(S_{0}, K, \sigma, T\right)$ denote the initial price of a European call option with strike $K$ and maturity date $T$.

(a) Show that the Black-Scholes formula can be written in the form

$\mathrm{EC}\left(S_{0}, K, \sigma, T\right)=S_{0} \Phi\left(d_{1}\right)-K \Phi\left(d_{2}\right)$

where $d_{1}$ and $d_{2}$ depend on $S_{0}, K, \sigma$ and $T$, and $\Phi$ is the standard normal distribution function.

(b) Let $\operatorname{EP}\left(S_{0}, K, \sigma, T\right)$ be the initial price of a put option with strike $K$ and maturity $T$. Show that

$\operatorname{EP}\left(S_{0}, K, \sigma, T\right)=\operatorname{EC}\left(S_{0}, K, \sigma, T\right)+K-S_{0}$

(c) Show that

$\operatorname{EP}\left(S_{0}, K, \sigma, T\right)=\operatorname{EC}\left(K, S_{0}, \sigma, T\right)$

(d) Consider a European contingent claim with maturity $T$ and payout

$S_{T} I_{\left\{S_{T} \leqslant K\right\}}-K I_{\left\{S_{T}>K\right\}}$

Assuming $K>S_{0}$, show that its initial price can be written as $\mathrm{EC}\left(S_{0}, K, \hat{\sigma}, T\right)$ for a volatility parameter $\hat{\sigma}$ which you should express in terms of $S_{0}, K, \sigma$ and $T$.

Paper 2, Section I, H

commentDefine what it means for a subset $E$ of $\mathbb{R}^{n}$ to be convex. Which of the following statements about a convex set $E$ in $\mathbb{R}^{n}$ (with the usual norm) are always true, and which are sometimes false? Give proofs or counterexamples as appropriate.

(i) The closure of $E$ is convex.

(ii) The interior of $E$ is convex.

(iii) If $\alpha: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is linear, then $\alpha(E)$ is convex.

(iv) If $f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is continuous, then $f(E)$ is convex.

Paper 2, Section II, H

commentProve Bernstein's theorem, which states that if $f:[0,1] \rightarrow \mathbb{R}$ is continuous and

$f_{m}(t)=\sum_{r=0}^{m}\left(\begin{array}{c} m \\ r \end{array}\right) f(r / m) t^{r}(1-t)^{m-r}$

then $f_{m}(t) \rightarrow f(t)$ uniformly on $[0,1]$. [Theorems from probability theory may be used without proof provided they are clearly stated.]

Deduce Weierstrass's theorem on polynomial approximation for any closed interval.

Proving any results on Chebyshev polynomials that you need, show that, if $g:[0, \pi] \rightarrow \mathbb{R}$ is continuous and $\epsilon>0$, then we can find an $N \geqslant 0$ and $a_{j} \in \mathbb{R}$, for $0 \leqslant j \leqslant N$, such that

$\left|g(t)-\sum_{j=0}^{N} a_{j} \cos j t\right| \leqslant \epsilon$

for all $t \in[0, \pi]$. Deduce that $\int_{0}^{\pi} g(t) \cos n t d t \rightarrow 0$ as $n \rightarrow \infty$.

Paper 2, Section II, 37D

commentStarting from the equations for one-dimensional unsteady flow of a perfect gas at constant entropy, show that the Riemann invariants

$R_{\pm}=u \pm \frac{2\left(c-c_{0}\right)}{\gamma-1}$

are constant on characteristics $C_{\pm}$given by $d x / d t=u \pm c$, where $u(x, t)$ is the speed of the gas, $c(x, t)$ is the local speed of sound, $c_{0}$ is a constant and $\gamma>1$ is the exponent in the adiabatic equation of state for $p(\rho)$.

At time $t=0$ the gas occupies $x>0$ and is at rest at uniform density $\rho_{0}$, pressure $p_{0}$ and sound speed $c_{0}$. For $t>0$, a piston initially at $x=0$ has position $x=X(t)$, where

$X(t)=-U_{0} t\left(1-\frac{t}{2 t_{0}}\right)$

and $U_{0}$ and $t_{0}$ are positive constants. For the case $0<U_{0}<2 c_{0} /(\gamma-1)$, sketch the piston path $x=X(t)$ and the $C_{+}$characteristics in $x \geqslant X(t)$ in the $(x, t)$-plane, and find the time and place at which a shock first forms in the gas.

Do likewise for the case $U_{0}>2 c_{0} /(\gamma-1)$.