• # Paper 3, Section II, I

In this question, all varieties are over an algebraically closed field $k$ of characteristic zero.

What does it mean for a projective variety to be smooth? Give an example of a smooth affine variety $X \subset \mathbb{A}_{k}^{n}$ whose projective closure $\bar{X} \subset \mathbb{P}_{k}^{n}$ is not smooth.

What is the genus of a smooth projective curve? Let $X \subset \mathbb{P}_{k}^{4}$ be the hypersurface $V\left(X_{0}^{3}+X_{1}^{3}+X_{2}^{3}+X_{3}^{3}+X_{4}^{3}\right)$. Prove that $X$ contains a smooth curve of genus $1 .$

Let $C \subset \mathbb{P}_{k}^{2}$ be an irreducible curve of degree 2 . Prove that $C$ is isomorphic to $\mathbb{P}_{k}^{1}$.

We define a generalized conic in $\mathbb{P}_{k}^{2}$ to be the vanishing locus of a non-zero homogeneous quadratic polynomial in 3 variables. Show that there is a bijection between the set of generalized conics in $\mathbb{P}_{k}^{2}$ and the projective space $\mathbb{P}_{k}^{5}$, which maps the conic $V(f)$ to the point whose coordinates are the coefficients of $f$.

(i) Let $R^{\circ} \subset \mathbb{P}_{k}^{5}$ be the subset of conics that consist of unions of two distinct lines. Prove that $R^{\circ}$ is not Zariski closed, and calculate its dimension.

(ii) Let $I$ be the homogeneous ideal of polynomials vanishing on $R^{\circ}$. Determine generators for the ideal $I$.

comment

• # Paper 3, Section II, 20F

Let $X$ be a space. We define the cone of $X$ to be

$C X:=(X \times I) / \sim$

where $\left(x_{1}, t_{1}\right) \sim\left(x_{2}, t_{2}\right)$ if and only if either $t_{1}=t_{2}=1$ or $\left(x_{1}, t_{1}\right)=\left(x_{2}, t_{2}\right)$.

(a) Show that if $X$ is triangulable, so is $C X$. Calculate $H_{i}(C X)$. [You may use any results proved in the course.]

(b) Let $K$ be a simplicial complex and $L \subseteq K$ a subcomplex. Let $X=|K|, A=|L|$, and let $X^{\prime}$ be the space obtained by identifying $|L| \subseteq|K|$ with $|L| \times\{0\} \subseteq C|L|$. Show that there is a long exact sequence

\begin{aligned} \cdots \rightarrow & H_{i+1}\left(X^{\prime}\right) \rightarrow H_{i}(A) \rightarrow H_{i}(X) \rightarrow H_{i}\left(X^{\prime}\right) \rightarrow H_{i-1}(A) \rightarrow \cdots \\ & \cdots \rightarrow H_{1}\left(X^{\prime}\right) \rightarrow H_{0}(A) \rightarrow \mathbb{Z} \oplus H_{0}(X) \rightarrow H_{0}\left(X^{\prime}\right) \rightarrow 0 \end{aligned}

(c) In part (b), suppose that $X=S^{1} \times S^{1}$ and $A=S^{1} \times\{x\} \subseteq X$ for some $x \in S^{1}$. Calculate $H_{i}\left(X^{\prime}\right)$ for all $i$.

comment

• # Paper 3, Section II, H

(a) State the Riemann-Lebesgue lemma. Show that the Fourier transform maps $\mathscr{S}\left(\mathbb{R}^{n}\right)$ to itself continuously.

(b) For some $s \geqslant 0$, let $f \in L^{1}\left(\mathbb{R}^{3}\right) \cap H^{s}\left(\mathbb{R}^{3}\right)$. Consider the following system of equations for $\mathbf{B}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$

$\nabla \cdot \mathbf{B}=f, \quad \boldsymbol{\nabla} \times \mathbf{B}=\mathbf{0}$

Show that there exists a unique $\mathbf{B}=\left(B_{1}, B_{2}, B_{3}\right)$ solving the equations with $B_{j} \in$ $H^{s+1}\left(\mathbb{R}^{3}\right)$ for $j=1,2,3$. You need not find $\mathbf{B}$ explicitly, but should give an expression for the Fourier transform of $B_{j}$. Show that there exists a constant $C>0$ such that

$\left\|B_{j}\right\|_{H^{s+1}} \leqslant C\left(\|f\|_{L^{1}}+\|f\|_{H^{s}}\right), \quad j=1,2,3$

For what values of $s$ can we conclude that $B_{j} \in C^{1}\left(\mathbb{R}^{n}\right)$ ?

comment

• # Paper 3, Section II, 34B

(a) In three dimensions, define a Bravais lattice $\Lambda$ and its reciprocal lattice $\Lambda^{*}$.

A particle is subject to a potential $V(\mathbf{x})$ with $V(\mathbf{x})=V(\mathbf{x}+\mathbf{r})$ for $\mathbf{x} \in \mathbb{R}^{3}$ and $\mathbf{r} \in \Lambda$. State and prove Bloch's theorem and specify how the Brillouin zone is related to the reciprocal lattice.

(b) A body-centred cubic lattice $\Lambda_{B C C}$ consists of the union of the points of a cubic lattice $\Lambda_{1}$ and all the points $\Lambda_{2}$ at the centre of each cube:

\begin{aligned} \Lambda_{B C C} & \equiv \Lambda_{1} \cup \Lambda_{2}, \\ \Lambda_{1} & \equiv\left\{\mathbf{r} \in \mathbb{R}^{3}: \mathbf{r}=n_{1} \hat{\mathbf{i}}+n_{2} \hat{\mathbf{j}}+n_{3} \hat{\mathbf{k}}, \text { with } n_{1,2,3} \in \mathbb{Z}\right\}, \\ \Lambda_{2} & \equiv\left\{\mathbf{r} \in \mathbb{R}^{3}: \mathbf{r}=\frac{1}{2}(\hat{\mathbf{i}}+\hat{\mathbf{j}}+\hat{\mathbf{k}})+\mathbf{r}^{\prime}, \text { with } \mathbf{r}^{\prime} \in \Lambda_{1}\right\}, \end{aligned}

where $\hat{\mathbf{i}}, \hat{\mathbf{j}}$ and $\hat{\mathbf{k}}$ are unit vectors parallel to the Cartesian coordinates in $\mathbb{R}^{3}$. Show that $\Lambda_{B C C}$ is a Bravais lattice and determine the primitive vectors $\mathbf{a}_{1}, \mathbf{a}_{2}$ and $\mathbf{a}_{3}$.

Find the reciprocal lattice $\Lambda_{B C C}^{*} .$ Briefly explain what sort of lattice it is.

$\left[\right.$ Hint: The matrix $M=\frac{1}{2}\left(\begin{array}{ccc}-1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1\end{array}\right)$ has inverse $M^{-1}=\left(\begin{array}{lll}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{array}\right)$.

comment

• # Paper 3, Section II, $27 \mathrm{~K}$

(a) Customers arrive at a queue at the event times of a Poisson process of rate $\lambda$. The queue is served by two independent servers with exponential service times with parameter $\mu$ each. If the queue has length $n$, an arriving customer joins with probability $r^{n}$ and leaves otherwise (where $\left.r \in(0,1]\right)$. For which $\lambda>0, \mu>0$ and $r \in(0,1]$ is there a stationary distribution?

(b) A supermarket allows a maximum of $N$ customers to shop at the same time. Customers arrive at the event times of a Poisson process of rate 1 , they enter the supermarket when possible, and they leave forever for another supermarket otherwise. Customers already in the supermarket pay and leave at the event times of an independent Poisson process of rate $\mu$. When is there a unique stationary distribution for the number of customers in the supermarket? If it exists, find it.

(c) In the situation of part (b), started from equilibrium, show that the departure process is Poissonian.

comment

• # Paper 3, Section II, 30A

(a) Carefully state Watson's lemma.

(b) Use the method of steepest descent and Watson's lemma to obtain an infinite asymptotic expansion of the function

$I(x)=\int_{-\infty}^{\infty} \frac{e^{-x\left(z^{2}-2 i z\right)}}{1-i z} d z \quad \text { as } \quad x \rightarrow \infty$

comment

• # Paper 3, Section I, F

Define a regular expression $R$ and explain how this gives rise to a language $\mathcal{L}(R)$.

Define a deterministic finite-state automaton $D$ and the language $\mathcal{L}(D)$ that it accepts.

State the relationship between languages obtained from regular expressions and languages accepted by deterministic finite-state automata.

Let $L$ and $M$ be regular languages. Is $L \cup M$ always regular? What about $L \cap M$ ?

Now suppose that $L_{1}, L_{2}, \ldots$ are regular languages. Is the countable union $\bigcup L_{i}$ always regular? What about the countable intersection $\bigcap L_{i}$ ?

comment
• # Paper 3, Section II, $12 F$

Suppose that $G$ is a context-free grammar without $\epsilon$-productions. Given a derivation of some word $w$ in the language $L$ of $G$, describe a parse tree for this derivation.

State and prove the pumping lemma for $L$. How would your proof differ if you did not assume that $G$ was in Chomsky normal form, but merely that $G$ has no $\epsilon$ - or unit productions?

For the alphabet $\Sigma=\{a, b\}$ of terminal symbols, state whether the following languages over $\Sigma$ are context free, giving reasons for your answer. (i) $\left\{a^{i} b^{i} a^{i} \mid i \geqslant 0\right\}$, (ii) $\left\{a^{i} b^{j} \mid i \geqslant j \geqslant 0\right\}$, (iii) $\left\{w a b w \mid w \in\{a, b\}^{*}\right\}$.

comment

• # Paper 3 , Section I, D

The Lagrangian of a particle of mass $m$ and charge $q$ in an electromagnetic field takes the form

$L=\frac{1}{2} m|\dot{\mathbf{r}}|^{2}+q(-\phi+\dot{\mathbf{r}} \cdot \mathbf{A})$

Explain the meaning of $\phi$ and $\mathbf{A}$, and how they are related to the electric and magnetic fields.

Obtain the canonical momentum $\mathbf{p}$ and the Hamiltonian $H(\mathbf{r}, \mathbf{p}, t)$.

Suppose that the electric and magnetic fields have Cartesian components $(E, 0,0)$ and $(0,0, B)$, respectively, where $E$ and $B$ are positive constants. Explain why the Hamiltonian of the particle can be taken to be

$H=\frac{p_{x}^{2}}{2 m}+\frac{\left(p_{y}-q B x\right)^{2}}{2 m}+\frac{p_{z}^{2}}{2 m}-q E x$

State three independent integrals of motion in this case.

comment

• # Paper 3, Section I, K

Let $d \geqslant 2$. Define the Hamming code $C$ of length $2^{d}-1$. Explain what it means to be a perfect code and show that $C$ is a perfect code.

Suppose you are using the Hamming code of length $2^{d}-1$ and you receive the message $111 \ldots 10$ of length $2^{d}-1$. How would you decode this message using minimum distance decoding? Explain why this leads to correct decoding if at most one channel error has occurred.

comment

• # Paper 3, Section I, 9B

The expansion of the universe during inflation is governed by the Friedmann equation

$\left(\frac{\dot{a}}{a}\right)^{2}=\frac{8 \pi G}{3}\left[\frac{1}{2} \dot{\phi}^{2}+V(\phi)\right]$

and the equation of motion for the inflaton field $\phi$,

$\ddot{\phi}+3 \frac{\dot{a}}{a} \dot{\phi}+\frac{\mathrm{d} V}{\mathrm{~d} \phi}=0 .$

Consider the potential

$V=V_{0} e^{-\lambda \phi}$

with $V_{0}>0$ and $\lambda>0$.

(a) Show that the inflationary equations have the exact solution

$a(t)=\left(\frac{t}{t_{0}}\right)^{\gamma} \quad \text { and } \quad \phi=\phi_{0}+\alpha \log t$

for arbitrary $t_{0}$ and appropriate choices of $\alpha, \gamma$ and $\phi_{0}$. Determine the range of $\lambda$ for which the solution exists. For what values of $\lambda$ does inflation occur?

(b) Using the inflaton equation of motion and

$\rho=\frac{1}{2} \dot{\phi}^{2}+V$

together with the continuity equation

$\dot{\rho}+3 \frac{\dot{a}}{a}(\rho+P)=0,$

determine $P$.

(c) What is the range of the pressure energy density ratio $\omega \equiv P / \rho$ for which inflation occurs?

comment
• # Paper 3, Section II, B

(a) Consider a closed universe endowed with cosmological constant $\Lambda>0$ and filled with radiation with pressure $P$ and energy density $\rho$. Using the equation of state $P=\frac{1}{3} \rho$ and the continuity equation

$\dot{\rho}+\frac{3 \dot{a}}{a}(\rho+P)=0,$

determine how $\rho$ depends on $a$. Give the physical interpretation of the scaling of $\rho$ with

(b) For such a universe the Friedmann equation reads

$\left(\frac{\dot{a}}{a}\right)^{2}=\frac{8 \pi G}{3 c^{2}} \rho-\frac{c^{2}}{R^{2} a^{2}}+\frac{\Lambda}{3}$

What is the physical meaning of $R ?$

(c) Making the substitution $a(t)=\alpha \tilde{a}(t)$, determine $\alpha$ and $\Gamma>0$ such that the Friedmann equation takes the form

$\left(\frac{\dot{\tilde{a}}}{\tilde{a}}\right)^{2}=\frac{\Gamma}{\tilde{a}^{4}}-\frac{1}{\tilde{a}^{2}}+\frac{\Lambda}{3} .$

Using the substitution $y(t)=\tilde{a}(t)^{2}$ and the boundary condition $y(0)=0$, deduce the boundary condition for $\dot{y}(0)$.

Show that

$\ddot{y}=\frac{4 \Lambda}{3} y-2$

and hence that

$\tilde{a}^{2}(t)=\frac{3}{2 \Lambda}\left[1-\cosh \left(\sqrt{\frac{4 \Lambda}{3}} t\right)+\lambda \sinh \left(\sqrt{\frac{4 \Lambda}{3}} t\right)\right]$

Express the constant $\lambda$ in terms of $\Lambda$ and $\Gamma$.

Sketch the graphs of $\tilde{a}(t)$ for the cases $\lambda>1, \lambda<1$ and $\lambda=1$.

comment

• # Paper 3, Section II, F

Let $X$ and $Y$ be smooth boundaryless manifolds. Suppose $f: X \rightarrow Y$ is a smooth map. What does it mean for $y \in Y$ to be a regular value of $f$ ? State Sard's theorem and the stack-of-records theorem.

Suppose $g: X \rightarrow Y$ is another smooth map. What does it mean for $f$ and $g$ to be smoothly homotopic? Assume now that $X$ is compact, and has the same dimension as $Y$. Suppose that $y \in Y$ is a regular value for both $X$ and $Y$. Prove that

$\# f^{-1}(y)=\# g^{-1}(y)(\bmod 2)$

Let $U \subset S^{n}$ be a non-empty open subset of the sphere. Suppose that $h: S^{n} \rightarrow S^{n}$ is a smooth map such that $\# h^{-1}(y)=1(\bmod 2)$ for all $y \in U$. Show that there must exist a pair of antipodal points on $S^{n}$ which is mapped to another pair of antipodal points by $h$.

[You may assume results about compact 1-manifolds provided they are accurately stated.]

comment

• # Paper 3, Section II, A

Consider the system

\begin{aligned} &\dot{x}=\mu y+\beta x y+y^{2}, \\ &\dot{y}=x-y-x^{2} \end{aligned}

where $\mu$ and $\beta$ are constants with $\beta>0$.

(a) Find the fixed points, and classify those on $y=0$. State how the number of fixed points depends on $\mu$ and $\beta$. Hence, or otherwise, deduce the values of $\mu$ at which stationary bifurcations occur for fixed $\beta>0$.

(b) Sketch bifurcation diagrams in the $(\mu, x)$-plane for the cases $0<\beta<1, \beta=1$ and $\beta>1$, indicating the stability of the fixed points and the type of the bifurcations in each case. [You are not required to prove that the stabilities or bifurcation types are as you indicate.]

(c) For the case $\beta=1$, analyse the bifurcation at $\mu=-1$ using extended centre manifold theory and verify that the evolution equation on the centre manifold matches the behaviour you deduced from the bifurcation diagram in part (b).

(d) For $0<\mu+1 \ll 1$, sketch the phase plane in the immediate neighbourhood of where the bifurcation of part (c) occurs.

comment

• # Paper 3, Section II, 36C

(a) Derive the Larmor formula for the total power $P$ emitted through a large sphere of radius $R$ by a non-relativistic particle of mass $m$ and charge $q$ with trajectory $\mathbf{x}(t)$. You may assume that the electric and magnetic fields describing radiation due to a source localised near the origin with electric dipole moment $\mathbf{p}(t)$ can be approximated as

\begin{aligned} &\mathbf{B}_{\operatorname{Rad}}(\mathbf{x}, t)=-\frac{\mu_{0}}{4 \pi r c} \widehat{\mathbf{x}} \times \ddot{\mathbf{p}}(t-r / c) \\ &\mathbf{E}_{\mathrm{Rad}}(\mathbf{x}, t)=-c \widehat{\mathbf{x}} \times \mathbf{B}_{\operatorname{Rad}}(\mathbf{x}, t) \end{aligned}

Here, the radial distance $r=|\mathbf{x}|$ is assumed to be much larger than the wavelength of emitted radiation which, in turn, is large compared to the spatial extent of the source.

(b) A non-relativistic particle of mass $m$, moving at speed $v$ along the $x$-axis in the positive direction, encounters a step potential of width $L$ and height $V_{0}>0$ described by

$V(x)= \begin{cases}0, & x<0 \\ f(x), & 0 \leqslant x \leqslant L \\ V_{0}, & x>L\end{cases}$

where $f(x)$ is a monotonically increasing function with $f(0)=0$ and $f(L)=V_{0}$. The particle carries charge $q$ and loses energy by emitting electromagnetic radiation. Assume that the total energy loss through emission $\Delta E_{\text {Rad }}$ is negligible compared with the particle's initial kinetic energy $E=m v^{2} / 2$. For $E>V_{0}$, show that the total energy lost is

$\Delta E_{\mathrm{Rad}}=\frac{q^{2} \mu_{0}}{6 \pi m^{2} c} \sqrt{\frac{m}{2}} \int_{0}^{L} d x \frac{1}{\sqrt{E-f(x)}}\left(\frac{d f}{d x}\right)^{2}$

Find the total energy lost also for the case $E.

(c) Take $f(x)=V_{0} x / L$ and explicitly evaluate the particle energy loss $\Delta E_{\text {Rad }}$ in each of the cases $E>V_{0}$ and $E. What is the maximum value attained by $\Delta E_{\text {Rad }}$ as $E$ is varied?

comment

• # Paper 3, Section II, 38A

Viscous fluid occupying $z>0$ is bounded by a rigid plane at $z=0$ and is extracted through a small hole at the origin at a constant flow rate $Q=2 \pi A$. Assume that for sufficiently small values of $R=|\mathbf{x}|$ the velocity $\mathbf{u}(\mathbf{x})$ is well-approximated by

$\mathbf{u}=-\frac{A \mathbf{x}}{R^{3}}$

except within a thin axisymmetric boundary layer near $z=0$.

(a) Estimate the Reynolds number of the flow as a function of $R$, and thus give an estimate for how small $R$ needs to be for such a solution to be applicable. Show that the radial pressure gradient is proportional to $R^{-5}$.

(b) In cylindrical polar coordinates $(r, \theta, z)$, the steady axisymmetric boundary-layer equations for the velocity components $(u, 0, w)$ can be written as

$u \frac{\partial u}{\partial r}+w \frac{\partial u}{\partial z}=-\frac{1}{\rho} \frac{d P}{d r}+\nu \frac{\partial^{2} u}{\partial z^{2}}, \quad \text { where } \quad u=-\frac{1}{r} \frac{\partial \Psi}{\partial z}, \quad w=\frac{1}{r} \frac{\partial \Psi}{\partial r}$

and $\Psi(r, z)$ is the Stokes streamfunction. Verify that the condition of incompressibility is satisfied by the use of $\Psi$.

Use scaling arguments to estimate the thickness $\delta(r)$ of the boundary layer near $z=0$ and then to motivate seeking a similarity solution of the form

$\Psi=(A \nu r)^{1 / 2} F(\eta), \quad \text { where } \quad \eta=z / \delta(r)$

(c) Obtain the differential equation satisfied by $F$, and state the conditions that would determine its solution. [You are not required to find this solution.]

By considering the flux in the boundary layer, explain why there should be a correction to the approximation $(*)$ of relative magnitude $(\nu R / A)^{1 / 2} \ll 1$.

comment

• # Paper 3 , Section I, 7E

The Beta function is defined by

$B(p, q)=\int_{0}^{1} t^{p-1}(1-t)^{q-1} d t$

for $\operatorname{Re} p>0$ and $\operatorname{Re} q>0$.

(a) Prove that $B(p, q)=B(q, p)$ and find $B(1, q)$.

(b) Show that $(p+z) B(p, z+1)=z B(p, z)$.

(c) For each fixed $p$ with $\operatorname{Re} p>0$, use part (b) to obtain the analytic continuation of $B(p, z)$ as an analytic function of $z \in \mathbb{C}$, with the exception of the points $z=$ $0,-1,-2,-3, \ldots$

(d) Use part (c) to determine the type of singularity that the function $B(p, z)$ has at $z=0,-1,-2,-3, \ldots$, for fixed $p$ with $\operatorname{Re} p>0$.

comment

• # Paper 3, Section II, 18I

Define the elementary symmetric functions in the variables $x_{1}, \ldots, x_{n}$. State the fundamental theorem of symmetric functions.

Let $f(x)=x^{n}+a_{n-1} x^{n-1}+\cdots+a_{0} \in K[x]$, where $K$ is a field. Define the discriminant of $f$, and explain why it is a polynomial in $a_{0}, \ldots, a_{n-1}$.

Compute the discriminant of $x^{5}+q$.

Let $f(x)=x^{5}+p x^{2}+q$. When does the discriminant of $f(x)$ equal zero? Compute the discriminant of $f(x)$.

comment

• # Paper 3, Section II, 37C

(a) Determine the signature of the metric tensor $g_{\mu \nu}$ given by

$g_{\mu \nu}=\left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1 \end{array}\right)$

Is it Riemannian, Lorentzian, or neither?

(b) Consider a stationary black hole with the Schwarzschild metric:

$d s^{2}=-\left(1-\frac{2 M}{r}\right) d t^{2}+\left(1-\frac{2 M}{r}\right)^{-1} d r^{2}+r^{2} d \Omega^{2}$

These coordinates break down at the horizon $r=2 M$. By making a change of coordinates, show that this metric can be converted to infalling Eddington-Finkelstein coordinates.

(c) A spherically symmetric, narrow pulse of radiation with total energy $E$ falls radially inwards at the speed of light from infinity, towards the origin of a spherically symmetric spacetime that is otherwise empty. Assume that the radial width $\lambda$ of the pulse is very small compared to the energy $(\lambda \ll E)$, and the pulse can therefore be treated as instantaneous.

(i) Write down a metric for the region outside the pulse, which is free from coordinate singularities. Briefly justify your answer. For what range of coordinates is this metric valid?

(ii) Write down a metric for the region inside the pulse. Briefly justify your answer. For what range of coordinates is this metric valid?

(iii) What is the final state of the system?

comment

• # Paper 3, Section II, 17G

(a) Define the Ramsey number $R(k)$ and show that $R(k) \leqslant 4^{k}$.

Show that every 2-coloured complete graph $K_{n}$ with $n \geqslant 2$ contains a monochromatic spanning tree. Is the same true if $K_{n}$ is coloured with 3 colours? Give a proof or counterexample.

(b) Let $G=(V, E)$ be a graph. Show that the number of paths of length 2 in $G$ is

$\sum_{x \in V} d(x)(d(x)-1) .$

Now consider a 2-coloured complete graph $K_{n}$ with $n \geqslant 3$. Show that the number of monochromatic triangles in $K_{n}$ is

$\frac{1}{2} \sum_{x}\left\{\left(\begin{array}{c} d_{r}(x) \\ 2 \end{array}\right)+\left(\begin{array}{c} d_{b}(x) \\ 2 \end{array}\right)\right\}-\frac{1}{2}\left(\begin{array}{l} n \\ 3 \end{array}\right)$

where $d_{r}(x)$ denotes the number of red edges incident with a vertex $x$ and $d_{b}(x)=$ $(n-1)-d_{r}(x)$ denotes the number of blue edges incident with $x$. [Hint: Count paths of length 2 in two different ways.]

comment

• # Paper 3, Section II, 32D

(a) Consider the group of transformations of $\mathbb{R}^{2}$ given by $g_{1}^{s}:(t, x) \mapsto(\tilde{t}, \tilde{x})=$ $(t, x+s t)$, where $s \in \mathbb{R}$. Show that this acts as a group of Lie symmetries for the equation $d^{2} x / d t^{2}=0$.

(b) Let $\left(\psi_{1}, \psi_{2}\right) \in \mathbb{R}^{2}$ and define $\psi=\psi_{1}+i \psi_{2}$. Show that the vector field $\psi_{1} \partial_{\psi_{2}}-\psi_{2} \partial_{\psi_{1}}$ generates the group of phase rotations $g_{2}^{s}: \psi \rightarrow e^{i s} \psi$.

(c) Show that the transformations of $\mathbb{R}^{2} \times \mathbb{C}$ defined by

$g^{s}:(t, x, \psi) \mapsto(\tilde{t}, \tilde{x}, \tilde{\psi})=\left(t, x+s t, \psi e^{i s x+i s^{2} t / 2}\right)$

form a one-parameter group generated by the vector field

$V=t \partial_{x}+x\left(\psi_{1} \partial_{\psi_{2}}-\psi_{2} \partial_{\psi_{1}}\right)=t \partial_{x}+i x\left(\psi \partial_{\psi}-\psi^{*} \partial_{\psi^{*}}\right)$

and find the second prolongation $\operatorname{Pr}^{(2)} g^{s}$ of the action of $\left\{g^{s}\right\}$. Hence find the coefficients $\eta^{0}$ and $\eta^{11}$ in the second prolongation of $V$,

$\mathrm{pr}^{(2)} V=t \partial_{x}+\left(i x \psi \partial_{\psi}+\eta^{0} \partial_{\psi_{t}}+\eta^{1} \partial_{\psi_{x}}+\eta^{00} \partial_{\psi_{t t}}+\eta^{01} \partial_{\psi_{x t}}+\eta^{11} \partial_{\psi_{x x}}+\right.$ complex conjugate $)$.

(d) Show that the group $\left\{g^{s}\right\}$ of transformations in part (c) acts as a group of Lie symmetries for the nonlinear Schrödinger equation $i \partial_{t} \psi+\frac{1}{2} \partial_{x}^{2} \psi+|\psi|^{2} \psi=0$. Given that $a e^{i a^{2} t / 2} \operatorname{sech}(a x)$ solves the nonlinear Schrödinger equation for any $a \in \mathbb{R}$, find a solution which describes a solitary wave travelling at arbitrary speed $s \in \mathbb{R}$.

comment

• # Paper 3, Section II, H

(a) State the Arzela-Ascoli theorem, including the definition of equicontinuity.

(b) Consider a sequence $\left(f_{n}\right)$ of continuous real-valued functions on $\mathbb{R}$ such that for all $x \in \mathbb{R},\left(f_{n}(x)\right)$ is bounded and the sequence is equicontinuous at $x$. Prove that there exists $f \in C(\mathbb{R})$ and a subsequence $\left(f_{\varphi(n)}\right)$ such that $f_{\varphi(n)} \rightarrow f$ uniformly on any closed bounded interval.

(c) Let $K$ be a Hausdorff compact topological space, and $C(K)$ the real-valued continuous functions on $K$. Let $\mathcal{K} \subset C(K)$ be a compact subset of $C(K)$. Prove that the collection of functions $\mathcal{K}$ is equicontinuous.

(d) We say that a Hausdorff topological space $X$ is locally compact if every point has a compact neighbourhood. Let $X$ be such a space, $K \subset X$ compact and $U \subset X$ open such that $K \subset U$. Prove that there exists $f: X \rightarrow \mathbb{R}$ continuous with compact support contained in $U$ and equal to 1 on $K$. [Hint: Construct an open set $V$ such that $K \subset V \subset \bar{V} \subset U$ and $\bar{V}$ is compact, and use Urysohn's lemma to construct a function in $\bar{V}$ and then extend it by zero.]

comment

• # Paper 3, Section II, 16G

(a) Let $\kappa$ and $\lambda$ be cardinals. What does it mean to say that $\kappa<\lambda$ ? Explain briefly why, assuming the Axiom of Choice, every infinite cardinal is of the form $\aleph_{\alpha}$ for some ordinal $\alpha$, and that for every ordinal $\alpha$ we have $\aleph_{\alpha+1}<2^{2^{\aleph_{\alpha}}}$.

(b) Henceforth, you should not assume the Axiom of Choice.

Show that, for any set $x$, there is an injection from $x$ to its power set $\mathcal{P} x$, but there is no bijection from $x$ to $\mathcal{P} x$. Deduce that if $\kappa$ is a cardinal then $\kappa<2^{\kappa}$.

Let $x$ and $y$ be sets, and suppose that there exists a surjection $f: x \rightarrow y$. Show that there exists an injection $g: \mathcal{P} y \rightarrow \mathcal{P} x$.

Let $\alpha$ be an ordinal. Prove that $\aleph_{\alpha} \aleph_{\alpha}=\aleph_{\alpha}$.

By considering $\mathcal{P}\left(\omega_{\alpha} \times \omega_{\alpha}\right)$ as the set of relations on $\omega_{\alpha}$, or otherwise, show that there exists a surjection $f: \mathcal{P}\left(\omega_{\alpha} \times \omega_{\alpha}\right) \rightarrow \omega_{\alpha+1}$. Deduce that $\aleph_{\alpha+1}<2^{2^{\kappa_{\alpha}}}$.

comment

• # Paper 3, Section I, E

The population density $n(a, t)$ of individuals of age $a$ at time $t$ satisfies the partial differential equation

$\frac{\partial n}{\partial t}+\frac{\partial n}{\partial a}=-d(a) n(a, t)$

with the boundary condition

$n(0, t)=\int_{0}^{\infty} b(a) n(a, t) d a$

where $b(a)$ and $d(a)$ are, respectively, the per capita age-dependent birth and death rates.

(a) What is the biological interpretation of the boundary condition?

(b) Solve equation (1) assuming a separable form of solution, $n(a, t)=A(a) T(t)$.

(c) Use equation (2) to obtain a necessary condition for the existence of a separable solution to the full problem.

(d) For a birth rate $b(a)=\beta e^{-\lambda a}$ with $\lambda>0$ and an age-independent death rate $d$, show that a separable solution to the full problem exists and find the critical value of $\beta$ above which the population density grows with time.

comment
• # Paper 3, Section II, 13E

Consider an epidemic spreading in a population that has been aggregated by age into groups numbered $i=1, \ldots, M$. The $i$ th age group has size $N_{i}$ and the numbers of susceptible, infective and recovered individuals in this group are, respectively, $S_{i}, I_{i}$ and $R_{i}$. The spread of the infection is governed by the equations

\begin{aligned} \frac{d S_{i}}{d t} &=-\lambda_{i}(t) S_{i} \\ \frac{d I_{i}}{d t} &=\lambda_{i}(t) S_{i}-\gamma I_{i} \\ \frac{d R_{i}}{d t} &=\gamma I_{i} \end{aligned}

where

$\lambda_{i}(t)=\beta \sum_{j=1}^{M} C_{i j} \frac{I_{j}}{N_{j}},$

and $C_{i j}$ is a matrix satisfying $N_{i} C_{i j}=N_{j} C_{j i}$, for $i, j=1, \ldots, M$.

(a) Describe the biological meaning of the terms in equations (1) and (2), of the matrix $C_{i j}$ and the condition it satisfies, and of the lack of dependence of $\beta$ and $\gamma$ on $i$.

State the condition on the matrix $C_{i j}$ that would ensure the absence of any transmission of infection between age groups.

(b) In the early stages of an epidemic, $S_{i} \approx N_{i}$ and $I_{i} \ll N_{i}$. Use this information to linearise the dynamics appropriately, and show that the linearised system predicts

$\mathbf{I}(t)=\exp [\gamma(\mathbf{L}-\mathbf{1}) t] \mathbf{I}(0),$

where $\mathbf{I}(t)=\left[I_{1}(t), \ldots, I_{M}(t)\right]$ is the vector of infectives at time $t, \mathbf{1}$ is the $M \times M$ identity matrix and $\mathbf{L}$ is a matrix that should be determined.

(c) Deduce a condition on the eigenvalues of the matrix $\mathbf{C}$ that allows the epidemic to grow.

comment

• # Paper 3, Section I, I

Define the continued fraction expansion of $\theta \in \mathbb{R}$, and show that this expansion terminates if and only if $\theta \in \mathbb{Q}$.

Define the convergents $\left(p_{n} / q_{n}\right)_{n \geqslant-1}$ of the continued fraction expansion of $\theta$, and show that for all $n \geqslant 0$,

$p_{n} q_{n-1}-p_{n-1} q_{n}=(-1)^{n-1} .$

Deduce that if $\theta \in \mathbb{R} \backslash \mathbb{Q}$, then for all $n \geqslant 0$, at least one of

$\left|\theta-\frac{p_{n}}{q_{n}}\right|<\frac{1}{2 q_{n}^{2}} \quad \text { and } \quad\left|\theta-\frac{p_{n+1}}{q_{n+1}}\right|<\frac{1}{2 q_{n+1}^{2}}$

must hold.

[You may assume that $\theta$ lies strictly between $p_{n} / q_{n}$ and $p_{n+1} / q_{n+1}$ for all $n \geqslant 0 .$ ]

comment
• # Paper 3, Section II, I

State what it means for two binary quadratic forms to be equivalent, and define the class number $h(d)$.

Let $m$ be a positive integer, and let $f$ be a binary quadratic form. Show that $f$ properly represents $m$ if and only if $f$ is equivalent to a binary quadratic form

$m x^{2}+b x y+c y^{2}$

for some integers $b$ and $c$.

Let $d<0$ be an integer such that $d \equiv 0$ or $1 \bmod 4$. Show that $m$ is properly represented by some binary quadratic form of discriminant $d$ if and only if $d$ is a square modulo $4 m$.

Fix a positive integer $A \geqslant 2$. Show that $n^{2}+n+A$ is composite for some integer $n$ such that $0 \leqslant n \leqslant A-2$ if and only if $d=1-4 A$ is a square modulo $4 p$ for some prime $p.

Deduce that $h(1-4 A)=1$ if and only if $n^{2}+n+A$ is prime for all $n=0,1, \ldots, A-2$.

comment

• # Paper 3, Section II, 40E

Consider discretisation of the diffusion equation

$\frac{\partial u}{\partial t}=\frac{\partial^{2} u}{\partial x^{2}}, \quad 0 \leqslant t \leqslant 1$

by the Crank-Nicholson method:

$u_{m}^{n+1}-\frac{1}{2} \mu\left(u_{m-1}^{n+1}-2 u_{m}^{n+1}+u_{m+1}^{n+1}\right)=u_{m}^{n}+\frac{1}{2} \mu\left(u_{m-1}^{n}-2 u_{m}^{n}+u_{m+1}^{n}\right), \quad n=0, \ldots, N,$

where $\mu=\frac{k}{h^{2}}$ is the Courant number, $h$ is the step size in the space discretisation, $k=\frac{1}{N+1}$ is the step size in the time discretisation, and $u_{m}^{n} \approx u(m h, n k)$, where $u(x, t)$ is the solution of $(*)$. The initial condition $u(x, 0)=u_{0}(x)$ is given.

(a) Consider the Cauchy problem for $(*)$ on the whole line, $x \in \mathbb{R}$ (thus $m \in \mathbb{Z}$ ), and derive the formula for the amplification factor of the Crank-Nicholson method ( $\dagger$ ). Use the amplification factor to show that the Crank-Nicholson method is stable for the Cauchy problem for all $\mu>0$.

[You may quote basic properties of the Fourier transform mentioned in lectures, but not the theorem on sufficient and necessary conditions on the amplification factor to have stability.]

(b) Consider $(*)$ on the interval $0 \leqslant x \leqslant 1$ (thus $m=1, \ldots, M$ and $h=\frac{1}{M+1}$ ) with Dirichlet boundary conditions $u(0, t)=\phi_{0}(t)$ and $u(1, t)=\phi_{1}(t)$, for some sufficiently smooth functions $\phi_{0}$ and $\phi_{1}$. Show directly (without using the Lax equivalence theorem) that, given sufficient smoothness of $u$, the Crank-Nicholson method is convergent, for any $\mu>0$, in the norm defined by $\|\boldsymbol{\eta}\|_{2, h}=\left(h \sum_{m=1}^{M}\left|\eta_{m}\right|^{2}\right)^{1 / 2}$ for $\boldsymbol{\eta} \in \mathbb{R}^{M}$.

[You may assume that the Trapezoidal method has local order 3 , and that the standard three-point centred discretisation of the second derivative (as used in the CrankNicholson method) has local order 2.]

comment

• # Paper 3, Section II, B

(a) A quantum system with total angular momentum $j_{1}$ is combined with another of total angular momentum $j_{2}$. What are the possible values of the total angular momentum $j$ of the combined system? For given $j$, what are the possible values of the angular momentum along any axis?

(b) Consider the case $j_{1}=j_{2}$. Explain why all the states with $j=2 j_{1}-1$ are antisymmetric under exchange of the angular momenta of the two subsystems, while all the states with $j=2 j_{1}-2$ are symmetric.

(c) An exotic particle $X$ of spin 0 and negative intrinsic parity decays into a pair of indistinguishable particles $Y$. Assume each $Y$ particle has spin 1 and that the decay process conserves parity. Find the probability that the direction of travel of the $Y$ particles is observed to lie at an angle $\theta \in(\pi / 4,3 \pi / 4)$ from some axis along which their total spin is observed to be $+\hbar$ ?

comment

• # Paper 3, Section II, J

Let $X_{1}, \ldots, X_{n} \sim$ iid $\operatorname{Gamma}(\alpha, \beta)$ for some known $\alpha>0$ and some unknown $\beta>0$. [The gamma distribution has probability density function

$f(x)=\frac{\beta^{\alpha}}{\Gamma(\alpha)} x^{\alpha-1} e^{-\beta x}, \quad x>0$

and its mean and variance are $\alpha / \beta$ and $\alpha / \beta^{2}$, respectively.]

(a) Find the maximum likelihood estimator $\hat{\beta}$ for $\beta$ and derive the distributional limit of $\sqrt{n}(\hat{\beta}-\beta)$. [You may not use the asymptotic normality of the maximum likelihood estimator proved in the course.]

(b) Construct an asymptotic $(1-\gamma)$-level confidence interval for $\beta$ and show that it has the correct (asymptotic) coverage.

(c) Write down all the steps needed to construct a candidate to an asymptotic $(1-\gamma)$-level confidence interval for $\beta$ using the nonparametric bootstrap.

comment

• # Paper 3, Section II, $26 \mathrm{H}$

Show that random variables $X_{1}, \ldots, X_{N}$ defined on some probability space $(\Omega, \mathcal{F}, \mathbb{P})$ are independent if and only if

$\mathbb{E}\left(\prod_{n=1}^{N} f_{n}\left(X_{n}\right)\right)=\prod_{n=1}^{N} \mathbb{E}\left(f_{n}\left(X_{n}\right)\right)$

for all bounded measurable functions $f_{n}: \mathbb{R} \rightarrow \mathbb{R}, n=1, \ldots, N$.

Now let $\left(X_{n}: n \in \mathbb{N}\right)$ be an infinite sequence of independent Gaussian random variables with zero means, $\mathbb{E} X_{n}=0$, and finite variances, $\mathbb{E} X_{n}^{2}=\sigma_{n}^{2}>0$. Show that the series $\sum_{n=1}^{\infty} X_{n}$ converges in $L^{2}(\mathbb{P})$ if and only if $\sum_{n=1}^{\infty} \sigma_{n}^{2}<\infty$.

[You may use without proof that $\mathbb{E}\left[e^{i u X_{n}}\right]=e^{-u^{2} \sigma_{n}^{2} / 2}$ for $u \in \mathbb{R}$.]

comment

• # Paper 3 , Section I, D

Let $|\psi\rangle_{A B}$ be the joint state of a bipartite system $A B$ with subsystems $A$ and $B$ separated in space. Suppose that Alice and Bob have access only to subsystems $A$ and $B$ respectively, on which they can perform local quantum operations.

Alice performs a unitary operation $U$ on $A$ and then a (generally incomplete) measurement on $A$, with projectors $\left\{\Pi_{a}\right\}$ labelled by her possible measurement outcomes $a$. Then Bob performs a complete measurement on $B$ relative to the orthonormal basis $\{|b\rangle\}$ labelled by his possible outcomes $b$.

Show that the probability distribution of Bob's measurement outcomes is unaffected by whether or not Alice actually performs the local operations on $A$ described above.

comment
• # Paper 3, Section II, D

Let $\mathcal{B}_{n}$ denote the set of all $n$-bit strings and let $\mathcal{H}_{n}$ denote the space of $n$ qubits.

(a) Suppose $f: \mathcal{B}_{2} \rightarrow \mathcal{B}_{1}$ has the property that $f\left(x_{0}\right)=1$ for a unique $x_{0} \in \mathcal{B}_{2}$ and suppose we have a quantum oracle $U_{f}$.

(i) Let $\left|\psi_{0}\right\rangle=\frac{1}{2} \sum_{x \in \mathcal{B}_{2}}|x\rangle$ and introduce the operators

$I_{x_{0}}=I_{2}-2\left|x_{0}\right\rangle\left\langle x_{0}\right| \quad \text { and } \quad J=I_{2}-2\left|\psi_{0}\right\rangle\left\langle\psi_{0}\right|$

on $\mathcal{H}_{2}$, where $I_{2}$ is the identity operator. Give a geometrical description of the actions of $-J, I_{x_{0}}$ and $Q=-J I_{x_{0}}$ on the 2-dimensional subspace of $\mathcal{H}_{2}$ given by the real span of $\left|x_{0}\right\rangle$ and $\left|\psi_{0}\right\rangle$. [You may assume without proof that the product of two reflections in $\mathbb{R}^{2}$ is a rotation through twice the angle between the mirror lines.]

(ii) Using the results of part (i), or otherwise, show how we may determine $x_{0}$ with certainty, starting with a supply of qubits each in state $|0\rangle$ and using $U_{f}$ only once, together with other quantum operations that are independent of $f$.

(b) Suppose $\mathcal{H}_{n}=A \oplus A^{\perp}$, where $A$ is a fixed linear subspace with orthogonal complement $A^{\perp}$. Let $\Pi_{A}$ denote the projection operator onto $A$ and let $I_{A}=I-2 \Pi_{A}$, where $I$ is the identity operator on $\mathcal{H}_{n}$.

(i) Show that any $|\xi\rangle \in \mathcal{H}_{n}$ can be written as $|\xi\rangle=\sin \theta|\alpha\rangle+\cos \theta|\beta\rangle$, where $\theta \in[0, \pi / 2]$, and $|\alpha\rangle \in A$ and $|\beta\rangle \in A^{\perp}$ are normalised.

(ii) Let $I_{\xi}=I-2|\xi\rangle\langle\xi|$ and $Q=-I_{\xi} I_{A}$. Show that $Q|\alpha\rangle=-\sin 2 \theta|\beta\rangle+\cos 2 \theta|\alpha\rangle$.

(iii) Now assume, in addition, that $Q|\beta\rangle=\cos 2 \theta|\beta\rangle+\sin 2 \theta|\alpha\rangle$ and that $|\xi\rangle=$ $U|0 \ldots 0\rangle$ for some unitary operation $U$. Suppose we can implement the operators $U, U^{\dagger}, I_{A}$ as well as the operation $I-2|0 \ldots 0\rangle\langle 0 \ldots 0|$. In the case $\theta=\pi / 10$, show how the $n$-qubit state $|\alpha\rangle$ may be made exactly from $|0 \ldots 0\rangle$ by a process that succeeds with certainty.

comment

• # Paper 3, Section II, I

In this question we work over $\mathbb{C}$.

(a) (i) Let $H$ be a subgroup of a finite group $G$. Given an $H$-space $W$, define the complex vector space $V=\operatorname{Ind}_{H}^{G}(W)$. Define, with justification, the $G$-action on $V$.

(ii) Write $\mathcal{C}(g)$ for the conjugacy class of $g \in G$. Suppose that $H \cap \mathcal{C}(g)$ breaks up into $s$ conjugacy classes of $H$ with representatives $x_{1}, \ldots, x_{s}$. If $\psi$ is a character of $H$, write down, without proof, a formula for the induced character $\operatorname{Ind}_{H}^{G}(\psi)$ as a certain sum of character values $\psi\left(x_{i}\right)$.

(b) Define permutations $a, b \in S_{7}$ by $a=\left(\begin{array}{llllll}1 & 2 & 3 & 4 & 5 & 6\end{array}\right), b=(235)(476)$ and let $G$ be the subgroup $\langle a, b\rangle$ of $S_{7}$. It is given that the elements of $G$ are all of the form $a^{i} b^{j}$ for $0 \leqslant i \leqslant 6,0 \leqslant j \leqslant 2$ and that $G$ has order 21 .

(i) Find the orders of the centralisers $C_{G}(a)$ and $C_{G}(b)$. Hence show that there are five conjugacy classes of $G$.

(ii) Find all characters of degree 1 of $G$ by lifting from a suitable quotient group.

(iii) Let $H=\langle a\rangle$. By first inducing linear characters of $H$ using the formula stated in part (a)(ii), find the remaining irreducible characters of $G$.

comment

• # Paper 3, Section II, F

(a) Let $f: \mathbb{C} \rightarrow \mathbb{C}$ be a polynomial of degree $d>0$, and let $m_{1}, \ldots, m_{k}$ be the multiplicities of the ramification points of $f$. Prove that

$\sum_{i=1}^{k}\left(m_{i}-1\right)=d-1$

Show that, for any list of integers $m_{1}, \ldots, m_{k} \geqslant 2$ satisfying $(*)$, there is a polynomial $f$ of degree $d$ such that the $m_{i}$ are the multiplicities of the ramification points of $f$.

(b) Let $f: \mathbb{C}_{\infty} \rightarrow \mathbb{C}_{\infty}$ be an analytic map, and let $B$ be the set of branch points. Prove that the restriction $f: \mathbb{C}_{\infty} \backslash f^{-1}(B) \rightarrow \mathbb{C}_{\infty} \backslash B$ is a regular covering map. Given $z_{0} \notin B$, explain how a closed loop $\gamma$ in $\mathbb{C}_{\infty} \backslash B$ gives rise to a permutation $\sigma_{\gamma}$ of $f^{-1}\left(z_{0}\right)$. Show that the group of all such permutations is transitive, and that the permutation $\sigma_{\gamma}$ only depends on $\gamma$ up to homotopy.

(c) Prove that there is no meromorphic function $f: \mathbb{C}_{\infty} \rightarrow \mathbb{C}_{\infty}$ of degree 4 with branch points $B=\{0,1, \infty\}$ such that every preimage of 0 and 1 has ramification index 2 , while some preimage of $\infty$ has ramification index equal to 3. [Hint: You may use the fact that every non-trivial product of $(2,2)$-cycles in the symmetric group $S_{4}$ is a $(2,2)$-cycle.]

comment

• # Paper 3, Section I, J

Consider the normal linear model $Y \mid X \sim \mathrm{N}\left(X \beta, \sigma^{2} I\right)$, where $X$ is a $n \times p$ design matrix, $Y$ is a vector of responses, $I$ is the $n \times n$ identity matrix, and $\beta, \sigma^{2}$ are unknown parameters.

Derive the maximum likelihood estimator of the pair $\beta$ and $\sigma^{2}$. What is the distribution of the estimator of $\sigma^{2}$ ? Use it to construct a $(1-\alpha)$-level confidence interval of $\sigma^{2}$. [You may use without proof the fact that the "hat matrix" $H=X\left(X^{T} X\right)^{-1} X^{T}$