• # Paper 3, Section II, F

(i) Suppose $f(x, y)=0$ is an affine equation whose projective completion is a smooth projective curve. Give a basis for the vector space of holomorphic differential forms on this curve. [You are not required to prove your assertion.]

Let $C \subset \mathbb{P}^{2}$ be the plane curve given by the vanishing of the polynomial

$X_{0}^{4}-X_{1}^{4}-X_{2}^{4}=0$

over the complex numbers.

(ii) Prove that $C$ is nonsingular.

(iii) Let $\ell$ be a line in $\mathbb{P}^{2}$ and define $D$ to be the divisor $\ell \cap C$. Prove that $D$ is a canonical divisor on $C$.

(iv) Calculate the minimum degree $d$ such that there exists a non-constant map

$C \rightarrow \mathbb{P}^{1}$

of degree $d$.

[You may use any results from the lectures provided that they are stated clearly.]

comment

• # Paper 3, Section II, 20F

Let $K$ be a simplicial complex with four vertices $v_{1}, \ldots, v_{4}$ with simplices $\left\langle v_{1}, v_{2}, v_{3}\right\rangle$, $\left\langle v_{1}, v_{4}\right\rangle$ and $\left\langle v_{2}, v_{4}\right\rangle$ and their faces.

(a) Draw a picture of $|K|$, labelling the vertices.

(b) Using the definition of homology, calculate $H_{n}(K)$ for all $n$.

(c) Let $L$ be the subcomplex of $K$ consisting of the vertices $v_{1}, v_{2}, v_{4}$ and the 1 simplices $\left\langle v_{1}, v_{2}\right\rangle,\left\langle v_{1}, v_{4}\right\rangle,\left\langle v_{2}, v_{4}\right\rangle$. Let $i: L \rightarrow K$ be the inclusion. Construct a simplicial $\operatorname{map} j: K \rightarrow L$ such that the topological realisation $|j|$ of $j$ is a homotopy inverse to $|i|$. Construct an explicit chain homotopy $h: C_{\bullet}(K) \rightarrow C_{\bullet}(K)$ between $i_{\bullet} \circ j_{\bullet}$ and $\mathrm{id}_{C_{\bullet}(K)}$, and verify that $h$ is a chain homotopy.

comment

• # Paper 3, Section II, 22I

Let $X$ be a Banach space.

(a) Define the dual space $X^{\prime}$, giving an expression for $\|\Lambda\|_{X^{\prime}}$ for $\Lambda \in X^{\prime}$. If $Y=L^{p}\left(\mathbb{R}^{n}\right)$ for some $1 \leqslant p<\infty$, identify $Y^{\prime}$ giving an expression for a general element of $Y^{\prime}$. [You need not prove your assertion.]

(b) For a sequence $\left(\Lambda_{i}\right)_{i=1}^{\infty}$ with $\Lambda_{i} \in X^{\prime}$, what is meant by: (i) $\Lambda_{i} \rightarrow \Lambda$, (ii) $\Lambda_{i} \rightarrow \Lambda$ (iii) $\Lambda_{i} \stackrel{*}{\rightarrow} \Lambda$ ? Show that (i) $\Longrightarrow$ (ii) $\Longrightarrow$ (iii). Find a sequence $\left(f_{i}\right)_{i=1}^{\infty}$ with $f_{i} \in$ $L^{\infty}(\mathbb{R})=\left(L^{1}(\mathbb{R})\right)^{\prime}$ such that, for some $f, g \in L^{\infty}\left(\mathbb{R}^{n}\right)$ :

$f_{i} \stackrel{*}{\rightarrow} f, \quad f_{i}^{2} \stackrel{*}{\rightarrow} g, \quad g \neq f^{2} .$

(c) For $f \in C_{c}^{0}\left(\mathbb{R}^{n}\right)$, let $\Lambda: C_{c}^{0}\left(\mathbb{R}^{n}\right) \rightarrow \mathbb{C}$ be the map $\Lambda f=f(0)$. Show that $\Lambda$ may be extended to a continuous linear map $\tilde{\Lambda}: L^{\infty}\left(\mathbb{R}^{n}\right) \rightarrow \mathbb{C}$, and deduce that $\left(L^{\infty}\left(\mathbb{R}^{n}\right)\right)^{\prime} \neq L^{1}\left(\mathbb{R}^{n}\right)$. For which $1 \leqslant p \leqslant \infty$ is $L^{p}\left(\mathbb{R}^{n}\right)$ reflexive? [You may use without proof the Hahn-Banach theorem].

comment

• # Paper 3, Section II, C

(a) For the quantum scattering of a beam of particles in three dimensions off a spherically symmetric potential $V(r)$ that vanishes at large $r$, discuss the boundary conditions satisfied by the wavefunction $\psi$ and define the scattering amplitude $f(\theta)$. Assuming the asymptotic form

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

state the constraints on $f_{l}$ imposed by the unitarity of the $S$-matrix and define the phase shifts $\delta_{l}$.

(b) For $V_{0}>0$, consider the specific potential

$V(r)=\left\{\begin{array}{lc} \infty, & r \leqslant a \\ -V_{0}, & a2 a \end{array}\right.$

(i) Show that the s-wave phase shift $\delta_{0}$ obeys

$\tan \left(\delta_{0}\right)=\frac{k \cos (2 k a)-\kappa \cot (\kappa a) \sin (2 k a)}{k \sin (2 k a)+\kappa \cot (\kappa a) \cos (2 k a)},$

where $\kappa^{2}=k^{2}+2 m V_{0} / \hbar^{2}$.

(ii) Compute the scattering length $a_{s}$ and find for which values of $\kappa$ it diverges. Discuss briefly the physical interpretation of the divergences. [Hint: you may find this trigonometric identity useful

$\left.\tan (A+B)=\frac{\tan A+\tan B}{1-\tan A \tan B} .\right]$

comment

• # Paper 3, Section II, 27K

Define a renewal-reward process, and state the renewal-reward theorem.

A machine $M$ is repaired at time $t=0$. After any repair, it functions without intervention for a time that is exponentially distributed with parameter $\lambda$, at which point it breaks down (assume the usual independence). Following any repair at time $T$, say, it is inspected at times $T, T+m, T+2 m, \ldots$, and instantly repaired if found to be broken (the inspection schedule is then restarted). Find the long run proportion of time that $M$ is working. [You may express your answer in terms of an integral.]

comment

• # Paper 3, Section II, D

(a) Find the leading order term of the asymptotic expansion, as $x \rightarrow \infty$, of the integral

$I(x)=\int_{0}^{3 \pi} e^{(t+x \cos t)} d t$

(b) Find the first two leading nonzero terms of the asymptotic expansion, as $x \rightarrow \infty$, of the integral

$J(x)=\int_{0}^{\pi}(1-\cos t) e^{-x \ln (1+t)} d t$

comment

• # Paper 3, Section I, F

Define a context-free grammar $G$, a sentence of $G$ and the language $\mathcal{L}(G)$ generated by $G$.

For the alphabet $\Sigma=\{a, b\}$, which of the following languages over $\Sigma$ are contextfree? (i) $\left\{a^{2 m} b^{2 m} \mid m \geqslant 0\right\}$,

(ii) $\left\{a^{m^{2}} b^{m^{2}} \mid m \geqslant 0\right\}$.

[You may assume standard results without proof if clearly stated.]

comment
• # Paper 3, Section II, F

Give the definition of a deterministic finite state automaton and of a regular language.

State and prove the pumping lemma for regular languages.

Let $S=\left\{2^{n} \mid n=0,1,2, \ldots\right\}$ be the subset of $\mathbb{N}$ consisting of the powers of 2 .

If we write the elements of $S$ in base 2 (with no preceding zeros), is $S$ a regular language over $\{0,1\}$ ?

Now suppose we write the elements of $S$ in base 10 (again with no preceding zeros). Show that $S$ is not a regular language over $\{0,1,2,3,4,5,6,7,8,9\}$. [Hint: Give a proof by contradiction; use the above lemma to obtain a sequence $a_{1}, a_{2}, \ldots$ of powers of 2, then consider $a_{i+1}-10^{d} a_{i}$ for $i=1,2,3, \ldots$ and a suitable fixed d.]

comment

• # Paper 3, Section I, B

A particle of mass $m$ experiences a repulsive central force of magnitude $k / r^{2}$, where $r=|\mathbf{r}|$ is its distance from the origin. Write down the Hamiltonian of the system.

The Laplace-Runge-Lenz vector for this system is defined by

$\mathbf{A}=\mathbf{p} \times \mathbf{L}+m k \hat{\mathbf{r}}$

where $\mathbf{L}=\mathbf{r} \times \mathbf{p}$ is the angular momentum and $\hat{\mathbf{r}}=\mathbf{r} / r$ is the radial unit vector. Show that

$\{\mathbf{L}, H\}=\{\mathbf{A}, H\}=\mathbf{0},$

where $\{\cdot, \cdot\}$ is the Poisson bracket. What are the integrals of motion of the system? Show that the polar equation of the orbit can be written as

$r=\frac{\lambda}{e \cos \theta-1},$

where $\lambda$ and $e$ are non-negative constants.

comment

• # Paper 3, Section I, I

Let $N$ and $p$ be very large positive integers with $p$ a prime and $p>N$. The Chair of the Committee is able to inscribe pairs of very large integers on discs. The Chair wishes to inscribe a collection of discs in such a way that any Committee member who acquires $r$ of the discs and knows the prime $p$ can deduce the integer $N$, but owning $r-1$ discs will give no information whatsoever. What strategy should the Chair follow?

[You may use without proof standard properties of the determinant of the $r \times r$ Vandermonde matrix.]

comment

• # Paper 3, Section I, D

At temperature $T$, with $\beta=1 /\left(k_{B} T\right)$, the distribution of ultra-relativistic particles with momentum $\mathbf{p}$ is given by

$n(\mathbf{p})=\frac{1}{e^{\beta p c} \mp 1},$

where the minus sign is for bosons and the plus $\operatorname{sign}$ for fermions, and with $p=|\mathbf{p}|$.

Show that the total number of fermions, $n_{\mathrm{f}}$, is related to the total number of bosons, $n_{\mathrm{b}}$, by $n_{\mathrm{f}}=\frac{3}{4} n_{\mathrm{b}}$.

Show that the total energy density of fermions, $\rho_{\mathrm{f}}$, is related to the total energy density of bosons, $\rho_{\mathrm{b}}$, by $\rho_{\mathrm{f}}=\frac{7}{8} \rho_{\mathrm{b}}$.

comment
• # Paper 3, Section II, D

In an expanding spacetime, the density contrast $\delta(\mathbf{x}, t)$ satisfies the linearised equation

$\ddot{\delta}+2 H \dot{\delta}-c_{s}^{2}\left(\frac{1}{a^{2}} \nabla^{2}+k_{J}^{2}\right) \delta=0,$

where $a$ is the scale factor, $H$ is the Hubble parameter, $c_{s}$ is a constant, and $k_{J}$ is the Jeans wavenumber, defined by

$c_{s}^{2} k_{J}^{2}=\frac{4 \pi G}{c^{2}} \bar{\rho}(t)$

with $\bar{\rho}(t)$ the background, homogeneous energy density.

(i) Solve for $\delta(\mathbf{x}, t)$ in a static universe, with $a=1$ and $H=0$ and $\bar{\rho}$ constant. Identify two regimes: one in which sound waves propagate, and one in which there is an instability.

(ii) In a matter-dominated universe with $\bar{\rho} \sim 1 / a^{3}$, use the Friedmann equation $H^{2}=8 \pi G \bar{\rho} / 3 c^{2}$ to find the growing and decaying long-wavelength modes of $\delta$ as a function of $a$.

(iii) Assuming $c_{s}^{2} \approx c_{s}^{2} k_{J}^{2} \approx 0$ in equation $(*)$, find the growth of matter perturbations in a radiation-dominated universe and find the growth of matter perturbations in a curvature-dominated universe.

comment

• # Paper 3, Section II, I

(a) Show that for a compact regular surface $S \subset \mathbb{R}^{3}$, there exists a point $p \in S$ such that $K(p)>0$, where $K$ denotes the Gaussian curvature. Show that if $S$ is contained in a closed ball of radius $R$ in $\mathbb{R}^{3}$, then there is a point $p$ such that $K(p) \geqslant R^{-2}$.

(b) For a regular surface $S \subset \mathbb{R}^{3}$, give the definition of a geodesic polar coordinate system at a point $p \in S$. Show that in such a coordinate system, $\lim _{r \rightarrow 0} G(r, \theta)=0$, $\lim _{r \rightarrow 0}(\sqrt{G})_{r}(r, \theta)=1, E(r, \theta)=1$ and $F(r, \theta)=0$. [You may use without proof standard properties of the exponential map provided you state them clearly.]

(c) Let $S \subset \mathbb{R}^{3}$ be a regular surface. Show that if $K \leqslant 0$, then any geodesic polar coordinate ball $B\left(p, \epsilon_{0}\right) \subset S$ of radius $\epsilon_{0}$ around $p$ has area satisfying

$\text { Area } B\left(p, \epsilon_{0}\right) \geqslant \pi \epsilon_{0}^{2}$

[You may use without proof the identity $(\sqrt{G})_{r r}(r, \theta)=-\sqrt{G} K$.]

(d) Let $S \subset \mathbb{R}^{3}$ be a regular surface, and now suppose $-\infty for some constant $0. Given any constant $0<\gamma<1$, show that there exists $\epsilon_{0}>0$, depending only on $C$ and $\gamma$, so that if $B(p, \epsilon) \subset S$ is any geodesic polar coordinate ball of radius $\epsilon \leqslant \epsilon_{0}$, then

$\text { Area } B(p, \epsilon) \geqslant \gamma \pi \epsilon^{2}$

[Hint: For any fixed $\theta_{0}$, consider the function $f(r):=\sqrt{G}\left(r, \theta_{0}\right)-\alpha \sin (\sqrt{C} r)$, for all $0<$ $\alpha<\frac{1}{\sqrt{C}}$. Derive the relation $f^{\prime \prime} \geqslant-C f$ and show $f(r)>0$ for an appropriate range of $r .$ The following variant of Wirtinger's inequality may be useful and can be assumed without proof: if $g$ is a $C^{1}$ function on $[0, L]$ vanishing at 0 , then $\int_{0}^{L}|g(x)|^{2} d x \leqslant \frac{L}{2 \pi} \int_{0}^{L}\left|g^{\prime}(x)\right|^{2} d x$.]

comment

• # Paper 3, Section II, E

(a) A dynamical system $\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$ has a fixed point at the origin. Define the terms asymptotic stability, Lyapunov function and domain of stability of the fixed point $\mathbf{x}=\mathbf{0}$. State and prove Lyapunov's first theorem and state (without proof) La Salle's invariance principle.

(b) Consider the system

\begin{aligned} \dot{x} &=-2 x+x^{3}+\sin (2 y), \\ \dot{y} &=-x-y^{3} \end{aligned}

(i) Show that trajectories cannot leave the square $S=\{(x, y):|x|<1,|y|<1\}$. Show also that there are no fixed points in $S$ other than the origin. Is this enough to deduce that $S$ is in the domain of stability of the origin?

(ii) Construct a Lyapunov function of the form $V=x^{2} / 2+g(y)$. Deduce that the origin is asymptotically stable.

(iii) Find the largest rectangle of the form $|x| on which $V$ is a strict Lyapunov function. Is this enough to deduce that this region is in the domain of stability of the origin?

(iv) Purely from using the Lyapunov function $V$, what is the most that can be deduced about the domain of stability of the origin?

comment

• # Paper 3, Section II, D

The Maxwell stress tensor $\sigma$ of the electromagnetic fields is a two-index Cartesian tensor with components

$\sigma_{i j}=-\epsilon_{0}\left(E_{i} E_{j}-\frac{1}{2}|\mathbf{E}|^{2} \delta_{i j}\right)-\frac{1}{\mu_{0}}\left(B_{i} B_{j}-\frac{1}{2}|\mathbf{B}|^{2} \delta_{i j}\right)$

where $i, j=1,2,3$, and $E_{i}$ and $B_{i}$ denote the Cartesian components of the electric and magnetic fields $\mathbf{E}(\mathbf{x}, t)$ and $\mathbf{B}(\mathbf{x}, t)$ respectively.

(i) Consider an electromagnetic field sourced by charge and current densities denoted by $\rho(\mathbf{x}, t)$ and $\mathbf{J}(\mathbf{x}, t)$ respectively. Using Maxwell's equations and the Lorentz force law, show that the components of $\sigma$ obey the equation

$\sum_{j=1}^{3} \frac{\partial \sigma_{i j}}{\partial x_{j}}+\frac{\partial g_{i}}{\partial t}=-(\rho \mathbf{E}+\mathbf{J} \times \mathbf{B})_{i}$

where $g_{i}$, for $i=1,2,3$, are the components of a vector field $\mathbf{g}(\mathbf{x}, t)$ which you should give explicitly in terms of $\mathbf{E}$ and $\mathbf{B}$. Explain the physical interpretation of this equation and of the quantities $\sigma$ and $\mathbf{g}$.

(ii) A localised source near the origin, $\mathbf{x}=0$, emits electromagnetic radiation. Far from the source, the resulting electric and magnetic fields can be approximated as

$\mathbf{B}(\mathbf{x}, t) \simeq \mathbf{B}_{0}(\mathbf{x}) \sin (\omega t-\mathbf{k} \cdot \mathbf{x}), \quad \mathbf{E}(\mathbf{x}, t) \simeq \mathbf{E}_{0}(\mathbf{x}) \sin (\omega t-\mathbf{k} \cdot \mathbf{x})$

where $\mathbf{B}_{0}(\mathbf{x})=\frac{\mu_{0} \omega^{2}}{4 \pi r c} \hat{\mathbf{x}} \times \mathbf{p}_{0}$ and $\mathbf{E}_{0}(\mathbf{x})=-c \hat{\mathbf{x}} \times \mathbf{B}_{0}(\mathbf{x})$ with $r=|\mathbf{x}|$ and $\hat{\mathbf{x}}=\mathbf{x} / r$. Here, $\mathbf{k}=(\omega / c) \hat{\mathbf{x}}$ and $\mathbf{p}_{0}$ is a constant vector.

Calculate the pressure exerted by these fields on a spherical shell of very large radius $R$ centred on the origin. [You may assume that $\mathbf{E}$ and $\mathbf{B}$ vanish for $r>R$ and that the shell material is absorbant, i.e. no reflected wave is generated.]

comment

• # Paper 3, Section II, 38B

(a) Briefly outline the derivation of the boundary layer equation

$u u_{x}+v u_{y}=U d U / d x+\nu u_{y y}$

explaining the significance of the symbols used and what sets the $x$-direction.

(b) Viscous fluid occupies the sector $0<\theta<\alpha$ in cylindrical coordinates which is bounded by rigid walls and there is a line sink at the origin of strength $\alpha Q$ with $Q / \nu \gg 1$. Assume that vorticity is confined to boundary layers along the rigid walls $\theta=0$ $(x>0, y=0)$ and $\theta=\alpha$.

(i) Find the flow outside the boundary layers and clarify why boundary layers exist at all.

(ii) Show that the boundary layer thickness along the wall $y=0$ is proportional to

$\delta:=\left(\frac{\nu}{Q}\right)^{1 / 2} x$

(iii) Show that the boundary layer equation admits a similarity solution for the streamfunction $\psi(x, y)$ of the form

$\psi=(\nu Q)^{1 / 2} f(\eta)$

where $\eta=y / \delta$. You should find the equation and boundary conditions satisfied by $f$.

(iv) Verify that

$\frac{d f}{d \eta}=\frac{5-\cosh (\sqrt{2} \eta+c)}{1+\cosh (\sqrt{2} \eta+c)}$

yields a solution provided the constant $c$ has one of two possible values. Which is the likely physical choice?

comment

• # Paper 3, Section I, E

The Weierstrass elliptic function is defined by

$\mathcal{P}(z)=\frac{1}{z^{2}}+\sum_{m, n}\left[\frac{1}{\left(z-\omega_{m, n}\right)^{2}}-\frac{1}{\omega_{m, n^{2}}}\right]$

where $\omega_{m, n}=m \omega_{1}+n \omega_{2}$, with non-zero periods $\left(\omega_{1}, \omega_{2}\right)$ such that $\omega_{1} / \omega_{2}$ is not real, and where $(m, n)$ are integers not both zero.

(i) Show that, in a neighbourhood of $z=0$,

$\mathcal{P}(z)=\frac{1}{z^{2}}+\frac{1}{20} g_{2} z^{2}+\frac{1}{28} g_{3} z^{4}+O\left(z^{6}\right)$

where

$g_{2}=60 \sum_{m, n}\left(\omega_{m, n}\right)^{-4}, \quad g_{3}=140 \sum_{m, n}\left(\omega_{m, n}\right)^{-6}$

(ii) Deduce that $\mathcal{P}$ satisfies

$\left(\frac{d \mathcal{P}}{d z}\right)^{2}=4 \mathcal{P}^{3}-g_{2} \mathcal{P}-g_{3}$

comment

• # Paper 3, Section II, 18G

(a) Let $L / K$ be a Galois extension of fields, with $\operatorname{Aut}(L / K)=A_{10}$, the alternating group on 10 elements. Find $[L: K]$.

Let $f(x)=x^{2}+b x+c \in K[x]$ be an irreducible polynomial, char $K \neq 2$. Show that $f(x)$ remains irreducible in $L[x] .$

(b) Let $L=\mathbb{Q}\left[\xi_{11}\right]$, where $\xi_{11}$ is a primitive $11^{\text {th }}$root of unity.

Determine all subfields $M \subseteq L$. Which are Galois over $\mathbb{Q}$ ?

For each proper subfield $M$, show that an element in $M$ which is not in $\mathbb{Q}$ must be primitive, and give an example of such an element explicitly in terms of $\xi_{11}$ for each $M$. [You do not need to justify that your examples are not in $\mathbb{Q}$.]

Find a primitive element for the extension $L / \mathbb{Q}$.

comment

• # Paper 3, Section II, 37D

(a) Let $(\mathcal{M}, \boldsymbol{g})$ be a four-dimensional spacetime and let $\boldsymbol{T}$ denote the rank $\left(\begin{array}{l}1 \\ 1\end{array}\right)$ tensor defined by

$\boldsymbol{T}: \mathcal{T}_{p}^{*}(\mathcal{M}) \times \mathcal{T}_{p}(\mathcal{M}) \rightarrow \mathbb{R}, \quad(\boldsymbol{\eta}, \boldsymbol{V}) \mapsto \boldsymbol{\eta}(\boldsymbol{V}), \quad \forall \boldsymbol{\eta} \in \mathcal{T}_{p}^{*}(\mathcal{M}), \quad \boldsymbol{V} \in \mathcal{T}_{p}(\mathcal{M})$

Determine the components of the tensor $\boldsymbol{T}$ and use the general law for the transformation of tensor components under a change of coordinates to show that the components of $\boldsymbol{T}$ are the same in any coordinate system.

(b) In Cartesian coordinates $(t, x, y, z)$ the Minkowski metric is given by

$d s^{2}=-d t^{2}+d x^{2}+d y^{2}+d z^{2} .$

Spheroidal coordinates $(r, \theta, \phi)$ are defined through

\begin{aligned} x &=\sqrt{r^{2}+a^{2}} \sin \theta \cos \phi \\ y &=\sqrt{r^{2}+a^{2}} \sin \theta \sin \phi \\ z &=r \cos \theta \end{aligned}

where $a \geqslant 0$ is a real constant.

(i) Show that the Minkowski metric in coordinates $(t, r, \theta, \phi)$ is given by

$d s^{2}=-d t^{2}+\frac{r^{2}+a^{2} \cos ^{2} \theta}{r^{2}+a^{2}} d r^{2}+\left(r^{2}+a^{2} \cos ^{2} \theta\right) d \theta^{2}+\left(r^{2}+a^{2}\right) \sin ^{2} \theta d \phi^{2}$

(ii) Transform the metric ( $\dagger$ ) to null coordinates given by $u=t-r, R=r$ and show that $\partial / \partial R$ is not a null vector field for $a>0$.

(iii) Determine a new azimuthal angle $\varphi=\phi-F(R)$ such that in the new coordinate system $(u, R, \theta, \varphi)$, the vector field $\partial / \partial R$ is null for any $a \geqslant 0$. Write down the Minkowski metric in this new coordinate system.

comment

• # Paper 3, Section II, $17 \mathrm{G}$

(i) State and prove Turán's theorem.

(ii) Let $G$ be a graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges. Show that $G$ must contain a triangle, and that if $n=2$ then $G$ contains two triangles.

(iii) Show that if every edge of $G$ lies in a triangle then $G$ contains at least $\left(n^{2}+1\right) / 3$ triangles.

(iv) Suppose that $G$ has some edge $u v$ contained in no triangles. Show that $\Gamma(u) \cap \Gamma(v)=\emptyset$, and that if $|\Gamma(u)|+|\Gamma(v)|=2 n$ then $\Gamma(u)$ and $\Gamma(v)$ are not both independent sets.

By induction on $n$, or otherwise, show that every graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges contains at least $n$ triangles. [Hint: If uv is an edge that is contained in no triangles, consider $G-u-v$.]

comment

• # Paper 3, Section II, 32C

(a) Given a smooth vector field

$V=V_{1}(x, u) \frac{\partial}{\partial x}+\phi(x, u) \frac{\partial}{\partial u}$

on $\mathbb{R}^{2}$ define the prolongation of $V$ of arbitrary order $N$.

Calculate the prolongation of order two for the group $S O(2)$ of transformations of $\mathbb{R}^{2}$ given for $s \in \mathbb{R}$ by

$g^{s}\left(\begin{array}{l} u \\ x \end{array}\right)=\left(\begin{array}{l} u \cos s-x \sin s \\ u \sin s+x \cos s \end{array}\right)$

and hence, or otherwise, calculate the prolongation of order two of the vector field $V=-x \partial_{u}+u \partial_{x}$. Show that both of the equations $u_{x x}=0$ and $u_{x x}=\left(1+u_{x}^{2}\right)^{\frac{3}{2}}$ are invariant under this action of $S O(2)$, and interpret this geometrically.

(b) Show that the sine-Gordon equation

$\frac{\partial^{2} u}{\partial X \partial T}=\sin u$

admits the group $\left\{g^{s}\right\}_{s \in \mathbb{R}}$, where

$g^{s}:\left(\begin{array}{c} X \\ T \\ u \end{array}\right) \mapsto\left(\begin{array}{c} e^{s} X \\ e^{-s} T \\ u \end{array}\right)$

as a group of Lie point symmetries. Show that there is a group invariant solution of the form $u(X, T)=F(z)$ where $z$ is an invariant formed from the independent variables, and hence obtain a second order equation for $w=w(z)$ where $\exp [i F]=w$.

comment

• # Paper 3, Section II, I

Let $H$ be a separable complex Hilbert space.

(a) For an operator $T: H \rightarrow H$, define the spectrum and point spectrum. Define what it means for $T$ to be: (i) a compact operator; (ii) a self-adjoint operator and (iii) a finite rank operator.

(b) Suppose $T: H \rightarrow H$ is compact. Prove that given any $\delta>0$, there exists a finite-dimensional subspace $E \subset H$ such that $\left\|T\left(e_{n}\right)-P_{E} T\left(e_{n}\right)\right\|<\delta$ for each $n$, where $\left\{e_{1}, e_{2}, e_{3}, \ldots\right\}$ is an orthonormal basis for $H$ and $P_{E}$ denotes the orthogonal projection onto $E$. Deduce that a compact operator is the operator norm limit of finite rank operators.

(c) Suppose that $S: H \rightarrow H$ has finite rank and $\lambda \in \mathbb{C} \backslash\{0\}$ is not an eigenvalue of $S$. Prove that $S-\lambda I$ is surjective. [You may wish to consider the action of $S(S-\lambda I)$ on $\left.\operatorname{ker}(S)^{\perp} .\right]$

(d) Suppose $T: H \rightarrow H$ is compact and $\lambda \in \mathbb{C} \backslash\{0\}$ is not an eigenvalue of $T$. Prove that the image of $T-\lambda I$ is dense in $H$.

Prove also that $T-\lambda I$ is bounded below, i.e. prove also that there exists a constant $c>0$ such that $\|(T-\lambda I) x\| \geqslant c\|x\|$ for all $x \in H$. Deduce that $T-\lambda I$ is surjective.

comment

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

Let $(V, \in)$ be a model of ZF. Give the definition of a class and a function class in $V$. Use the concept of function class to give a short, informal statement of the Axiom of Replacement.

Let $z_{0}=\omega$ and, for each $n \in \omega$, let $z_{n+1}=\mathcal{P} z_{n}$. Show that $y=\left\{z_{n} \mid n \in \omega\right\}$ is a set.

We say that a set $x$ is small if there is an injection from $x$ to $z_{n}$ for some $n \in \omega$. Let HS be the class of sets $x$ such that every member of $\mathrm{TC}(\{x\})$ is small, where $\mathrm{TC}(\{x\})$ is the transitive closure of $\{x\}$. Show that $n \in \mathbf{H S}$ for all $n \in \omega$ and deduce that $\omega \in \mathbf{H S}$. Show further that $z_{n} \in \mathbf{H S}$ for all $n \in \omega$. Deduce that $y \in \mathbf{H S}$.

Is $(\mathbf{H S}, \in)$ a model of ZF? Justify your answer.

$[$ Recall that $0=\emptyset$ and that $n+1=n \cup\{n\}$ for all $n \in \omega .]$

comment

• # Paper 3, Section I, B

Consider a model for the common cold in which the population is partitioned into susceptible $(S)$, infective $(I)$, and recovered $(R)$ categories, which satisfy

\begin{aligned} \frac{d S}{d t} &=\alpha R-\beta S I \\ \frac{d I}{d t} &=\beta S I-\gamma I \\ \frac{d R}{d t} &=\gamma I-\alpha R \end{aligned}

where $\alpha, \beta$ and $\gamma$ are positive constants.

(i) Show that the sum $N \equiv S+I+R$ does not change in time.

(ii) Determine the condition, in terms of $\beta, \gamma$ and $N$, for an endemic steady state to exist, that is, a time-independent state with a non-zero number of infectives.

(iii) By considering a reduced set of equations for $S$ and $I$ only, show that the endemic steady state identified in (ii) above, if it exists, is stable.

comment
• # Paper 3, Section II, 13B

The larva of a parasitic worm disperses in one dimension while laying eggs at rate $\lambda>0$. The larvae die at rate $\mu$ and have diffusivity $D$, so that their density, $n(x, t)$, obeys

$\frac{\partial n}{\partial t}=D \frac{\partial^{2} n}{\partial x^{2}}-\mu n, \quad(D>0, \mu>0)$

The eggs do not diffuse, so that their density, $e(x, t)$, obeys

$\frac{\partial e}{\partial t}=\lambda n$

At $t=0$ there are no eggs and $N$ larvae concentrated at $x=0$, so that $n(x, 0)=N \delta(x)$.

(i) Determine $n(x, t)$ for $t>0$. Show that $n(x, t) \rightarrow 0$ as $t \rightarrow \infty$.

(ii) Determine the limit of $e(x, t)$ as $t \rightarrow \infty$.

(iii) Provide a physical explanation for the remnant density of the eggs identified in part (ii).

[You may quote without proof the results

\begin{aligned} \int_{-\infty}^{\infty} \exp \left(-x^{2}\right) d x &=\sqrt{\pi} \\ \int_{-\infty}^{\infty} \frac{\exp (i k x)}{k^{2}+\alpha^{2}} d k &=\pi \exp (-\alpha|x|) / \alpha, \quad \alpha>0 \end{aligned}

comment

• # Paper 3, Section I, $1 \mathrm{H}$

Let $N \geqslant 3$ be an odd integer and $b$ an integer with $(b, N)=1$. What does it mean to say that $N$ is an Euler pseudoprime to base $b$ ?

Show that if $N$ is not an Euler pseudoprime to some base $b_{0}$, then it is not an Euler pseudoprime to at least half the bases $\{1 \leqslant b.

Show that if $N$ is odd and composite, then there exists an integer $b$ such that $N$ is not an Euler pseudoprime to base $b$.

comment
• # Paper 3, Section II, 11H

Let $p$ be an odd prime.

(i) Define the Legendre symbol $\left(\frac{x}{p}\right)$, and show that when $(x, p)=1$, then $\left(\frac{x^{-1}}{p}\right)=\left(\frac{x}{p}\right)$.

(ii) State and prove Gauss's lemma, and use it to evaluate $\left(\frac{-1}{p}\right)$. [You may assume Euler's criterion.]

(iii) Prove that

$\sum_{x=1}^{p}\left(\frac{x}{p}\right)=0$

and deduce that

$\sum_{x=1}^{p}\left(\frac{x(x+1)}{p}\right)=-1$

Hence or otherwise determine the number of pairs of consecutive integers $z, z+1$ such that $1 \leqslant z, z+1 \leqslant p-1$ and both $z$ and $z+1$ are quadratic residues $\bmod p$.

comment

• # Paper 3, Section II, 40E

(a) Give the definition of a normal matrix. Prove that if $A$ is normal, then the (Euclidean) matrix $\ell_{2}$-norm of $A$ is equal to its spectral radius, i.e., $\|A\|_{2}=\rho(A)$.

(b) The advection equation

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

is discretized by the Crank-Nicolson scheme

$u_{m}^{n+1}-u_{m}^{n}=\frac{1}{4} \mu\left(u_{m+1}^{n+1}-u_{m-1}^{n+1}\right)+\frac{1}{4} \mu\left(u_{m+1}^{n}-u_{m-1}^{n}\right), \quad m=1,2, \ldots, M, \quad n \in \mathbb{Z}_{+}$

Here, $\mu=\frac{k}{h}$ is the Courant number, with $k=\Delta t, h=\Delta x=\frac{1}{M+1}$, and $u_{m}^{n}$ is an approximation to $u(m h, n k)$.

Using the eigenvalue analysis and carefully justifying each step, determine conditions on $\mu>0$ for which the method is stable. [Hint: All M $\times M$ Toeplitz anti-symmetric tridiagonal (TAT) matrices have the same set of orthogonal eigenvectors, and a TAT matrix with the elements $a_{j, j}=a$ and $a_{j, j+1}=-a_{j, j-1}=b$ has the eigenvalues $\lambda_{k}=a+2 \mathrm{i} b \cos \frac{\pi k}{M+1}$ where $\mathrm{i}=\sqrt{-1}$. ]

(c) Consider the same advection equation for the Cauchy problem $(x \in \mathbb{R}, 0 \leqslant t \leqslant$ $T)$. Now it is discretized by the two-step leapfrog scheme

$u_{m}^{n+1}=\mu\left(u_{m+1}^{n}-u_{m-1}^{n}\right)+u_{m}^{n-1} .$

Applying the Fourier technique, find the range of $\mu>0$ for which the method is stable.

comment

• # Paper 3, Section II, 33A

Explain what is meant by the terms boson and fermion.

Three distinguishable spin-1 particles are governed by the Hamiltonian

$H=\frac{2 \lambda}{\hbar^{2}}\left(\mathbf{S}_{1} \cdot \mathbf{S}_{2}+\mathbf{S}_{2} \cdot \mathbf{S}_{3}+\mathbf{S}_{3} \cdot \mathbf{S}_{1}\right)$

where $\mathbf{S}_{i}$ is the spin operator of particle $i$ and $\lambda$ is a positive constant. How many spin states are possible altogether? By considering the total spin operator, determine the eigenvalues and corresponding degeneracies of the Hamiltonian.

Now consider the case that all three particles are indistinguishable and all have the same spatial wavefunction. What are the degeneracies of the Hamiltonian in this case?

comment

• # Paper 3, Section II, J

Let $\Theta=\mathbb{R}^{p}$, let $\mu>0$ be a probability density function on $\Theta$ and suppose we are given a further auxiliary conditional probability density function $q(\cdot \mid t)>0, t \in \Theta$, on $\Theta$ from which we can generate random draws. Consider a sequence of random variables $\left\{\vartheta_{m}: m \in \mathbb{N}\right\}$ generated as follows:

• For $m \in \mathbb{N}$ and given $\vartheta_{m}$, generate a new draw $s_{m} \sim q\left(\cdot \mid \vartheta_{m}\right)$.

• Define

$\vartheta_{m+1}= \begin{cases}s_{m}, & \text { with probability } \rho\left(\vartheta_{m}, s_{m}\right) \\ \vartheta_{m}, & \text { with probability } 1-\rho\left(\vartheta_{m}, s_{m}\right)\end{cases}$

where $\rho(t, s)=\min \left\{\frac{\mu(s)}{\mu(t)} \frac{q(t \mid s)}{q(s \mid t)}, 1\right\}$.

(i) Show that the Markov chain $\left(\vartheta_{m}\right)$ has invariant measure $\mu$, that is, show that for all (measurable) subsets $B \subset \Theta$ and all $m \in \mathbb{N}$ we have

$\int_{\Theta} \operatorname{Pr}\left(\vartheta_{m+1} \in B \mid \vartheta_{m}=t\right) \mu(t) d t=\int_{B} \mu(\theta) d \theta$

(ii) Now suppose that $\mu$ is the posterior probability density function arising in a statistical model $\{f(\cdot, \theta): \theta \in \Theta\}$ with observations $x$ and a $N\left(0, I_{p}\right)$ prior distribution on $\theta$. Derive a family $\{q(\cdot \mid t): t \in \Theta\}$ such that in the above algorithm the acceptance probability $\rho(t, s)$ is a function of the likelihood ratio $f(x, s) / f(x, t)$, and for which the probability density function $q(\cdot \mid t)$ has covariance matrix $2 \delta I_{p}$ for all $t \in \Theta$.

comment

• # Paper 3, Section II, 26K

Let $(X, \mathcal{A}, m, T)$ be a probability measure preserving system.

(a) State what it means for $(X, \mathcal{A}, m, T)$ to be ergodic.

(b) State Kolmogorov's 0-1 law for a sequence of independent random variables. What does it imply for the canonical model associated with an i.i.d. random process?

(c) Consider the special case when $X=[0,1], \mathcal{A}$ is the $\sigma$-algebra of Borel subsets, and $T$ is the map defined as

$T x=\left\{\begin{array}{l} 2 x, \quad \text { if } x \in\left[0, \frac{1}{2}\right] \\ 2-2 x, \quad \text { if } x \in\left[\frac{1}{2}, 1\right] \end{array}\right.$

(i) Check that the Lebesgue measure $m$ on $[0,1]$ is indeed an invariant probability measure for $T$.

(ii) Let $X_{0}:=1_{\left(0, \frac{1}{2}\right)}$ and $X_{n}:=X_{0} \circ T^{n}$ for $n \geqslant 1$. Show that $\left(X_{n}\right)_{n \geqslant 0}$ forms a sequence of i.i.d. random variables on $(X, \mathcal{A}, m)$, and that the $\sigma$-algebra $\sigma\left(X_{0}, X_{1}, \ldots\right)$ is all of $\mathcal{A}$. [Hint: check first that for any integer $n \geqslant 0, T^{-n}\left(0, \frac{1}{2}\right)$ is a disjoint union of $2^{n}$ intervals of length $1 / 2^{n+1}$.]

(iii) Is $(X, \mathcal{A}, m, T)$ ergodic? Justify your answer.

comment

• # Paper 3, Section I, $10 C$

For $\phi \in[0,2 \pi)$ and $|\psi\rangle \in \mathbb{C}^{4}$ consider the operator

$R_{\psi}^{\phi}=\mathbb{I}-\left(1-e^{i \phi}\right)|\psi\rangle\langle\psi|$

Let $U$ be a unitary operator on $\mathbb{C}^{4}=\mathbb{C}^{2} \otimes \mathbb{C}^{2}$ with action on $|00\rangle$ given as follows

$\tag{†} U|00\rangle=\sqrt{p}|g\rangle+\sqrt{1-p}|b\rangle=:\left|\psi_{\mathrm{in}}\right\rangle$

where $p$ is a constant in $[0,1]$ and $|g\rangle,|b\rangle \in \mathbb{C}^{4}$ are orthonormal states.

(i) Give an explicit expression of the state $R_{g}^{\phi} U|00\rangle$.

(ii) Find a $|\psi\rangle \in \mathbb{C}^{4}$ for which $R_{\psi}^{\pi}=U R_{00}^{\pi} U^{\dagger}$.

(iii) Choosing $p=1 / 4$ in equation ($\dagger$), calculate the state $U R_{00}^{\pi} U^{\dagger} R_{g}^{\phi} U|00\rangle$. For what choice of $\phi \in[0,2 \pi)$ is this state proportional to $|g\rangle$ ?

(iv) Describe how the above considerations can be used to find a marked element $g$ in a list of four items $\left\{g, b_{1}, b_{2}, b_{3}\right\}$. Assume that you have the state $|00\rangle$ and can act on it with a unitary operator that prepares the uniform superposition of four orthonormal basis states $|g\rangle,\left|b_{1}\right\rangle,\left|b_{2}\right\rangle,\left|b_{3}\right\rangle$ of $\mathbb{C}^{4}$. [You may use the operators $U$ (defined in (†)), $U^{\dagger}$ and $R_{\psi}^{\phi}$ for any choice of $\phi \in[0,2 \pi)$ and any $|\psi\rangle \in \mathbb{C}^{4}$.]

comment
• # Paper 3, Section II, C

Consider the quantum oracle $U_{f}$ for a function $f: B_{n} \rightarrow B_{n}$ which acts on the state $|x\rangle|y\rangle$ of $2 n$ qubits as follows:

$U_{f}|x\rangle|y\rangle=|x\rangle|y \oplus f(x)\rangle$

The function $f$ is promised to have the following property: there exists a $z \in B_{n}$ such that for any $x, y \in B_{n}$,

$[f(x)=f(y)] \text { if and only if } x \oplus y \in\left\{0^{n}, z\right\}$

where $0^{n} \equiv(0,0, \ldots, 0) \in B_{n}$.

(a) What is the nature of the function $f$ for the case in which $z=0^{n}$, and for the case in which $z \neq 0^{n}$ ?

(b) Suppose initially each of the $2 n$ qubits are in the state $|0\rangle$. They are then subject to the following operations:

1. Each of the first $n$ qubits forming an input register are acted on by Hadamard gates;

2. The $2 n$ qubits are then acted on by the quantum oracle $U_{f}$;

3. Next, the qubits in the input register are individually acted on by Hadamard gates.

(i) List the states of the $2 n$ qubits after each of the above operations; the expression for the final state should involve the $n$-bit "dot product" which is defined as follows:

$a \cdot b=\left(a_{1} b_{1}+a_{2} b_{2}+\ldots+a_{n} b_{n}\right) \bmod 2$

where $a, b \in B_{n}$ with $a=\left(a_{1}, \ldots, a_{n}\right)$ and $b=\left(b_{1}, \ldots, b_{n}\right)$.

(ii) Justify that if $z=0^{n}$ then for any $y \in B_{n}$ and any $\varphi(x, y) \in\{-1$, $+1\}$, the following identity holds:

$\| \sum_{x \in B_{n}} \varphi(x, y)|f(x)\rangle\left\|^{2}=\right\| \sum_{x \in B_{n}} \varphi(x, y)|x\rangle \|^{2}$

(iii) For the case $z=0^{n}$, what is the probability that a measurement of the input register, relative to the computational basis of $\mathbb{C}^{n}$ results in a string $y \in B_{n}$ ?

(iv) For the case $z \neq 0^{n}$, show that the probability that the above-mentioned measurement of the input register results in a string $y \in B_{n}$, is equal to the following:

zero for all strings $y \in B_{n}$ satisfying $y \cdot z=1$, and $2^{-(n-1)}$ for any fixed string $y \in B_{n}$ satisfying $y \cdot z=0$.

[State any identity you may employ. You may use $(x \oplus z) \cdot y=(x \cdot y) \oplus(z \cdot y), \forall x, y, z \in B_{n}$.]

comment

• # Paper 3, Section II, F

State Mackey's restriction formula and Frobenius reciprocity for characters. Deduce Mackey's irreducibility criterion for an induced representation.

For $n \geqslant 2$ show that if $S_{n-1}$ is the subgroup of $S_{n}$ consisting of the elements that fix $n$, and $W$ is a complex representation of $S_{n-1}$, then $\operatorname{Ind}_{S_{n-1}}^{S_{n}} W$ is not irreducible.

comment

• # Paper 3, Section II, F

Let $\Lambda=\langle\lambda, \mu\rangle \subseteq \mathbb{C}$ be a lattice. Give the definition of the associated Weierstrass $\wp$-function as an infinite sum, and prove that it converges. [You may use without proof the fact that

$\sum_{w \in \Lambda \backslash\{0\}} \frac{1}{|w|^{t}}$

converges if and only if $t>2$.]

Consider the half-lattice points

$z_{1}=\lambda / 2, \quad z_{2}=\mu / 2, \quad z_{3}=(\lambda+\mu) / 2,$

and let $e_{i}=\wp\left(z_{i}\right)$. Using basic properties of $\wp$, explain why the values $e_{1}, e_{2}, e_{3}$ are distinct

Give an example of a lattice $\Lambda$ and a conformal equivalence $\theta: \mathbb{C} / \Lambda \rightarrow \mathbb{C} / \Lambda$ such that $\theta$ acts transitively on the images of the half-lattice points $z_{1}, z_{2}, z_{3}$.

comment

• # Paper 3, Section I, J

Suppose we have data $\left(Y_{1}, x_{1}^{T}\right), \ldots,\left(Y_{n}, x_{n}^{T}\right)$, where the $Y_{i}$ are independent conditional on the design matrix $X$ whose rows are the $x_{i}^{T}, i=1, \ldots, n$. Suppose that given $x_{i}$, the true probability density function of $Y_{i}$ is $f_{x_{i}}$, so that the data is generated from an element of a model $\mathcal{F}:=\left\{\left(f_{x_{i}}(\cdot ; \theta)\right)_{i=1}^{n}, \theta \in \Theta\right\}$ for some $\Theta \subseteq \mathbb{R}^{q}$ and $q \in \mathbb{N}$.

(a) Define the log-likelihood function for $\mathcal{F}$, the maximum likelihood estimator of $\theta$ and Akaike's Information Criterion (AIC) for $\mathcal{F}$.

From now on let $\mathcal{F}$ be the normal linear model, i.e. $Y:=\left(Y_{1}, \ldots, Y_{n}\right)^{T}=X \beta+\varepsilon$, where $X \in \mathbb{R}^{n \times p}$ has full column rank and $\varepsilon \sim N_{n}\left(0, \sigma^{2} I\right)$.

(b) Let $\hat{\sigma}^{2}$ denote the maximum likelihood estimator of $\sigma^{2}$. Show that the AIC of $\mathcal{F}$ is

$n\left(1+\log \left(2 \pi \hat{\sigma}^{2}\right)\right)+2(p+1)$

(c) Let $\chi_{n-p}^{2}$ be a chi-squared distribution on $n-p$ degrees of freedom. Using any results from the course, show that the distribution of the AIC of $\mathcal{F}$ is

$n \log \left(\chi_{n-p}^{2}\right)+n\left(\log \left(2 \pi \sigma^{2} / n\right)+1\right)+2(p+1)$

$\left[\right.$