• # Paper 4, Section II, I

Let $C$ be a smooth irreducible projective algebraic curve over an algebraically closed field.

Let $D$ be an effective divisor on $C$. Prove that the vector space $L(D)$ of rational functions with poles bounded by $D$ is finite dimensional.

Let $D$ and $E$ be linearly equivalent divisors on $C$. Exhibit an isomorphism between the vector spaces $L(D)$ and $L(E)$.

What is a canonical divisor on $C$ ? State the Riemann-Roch theorem and use it to calculate the degree of a canonical divisor in terms of the genus of $C$.

Prove that the canonical divisor on a smooth cubic plane curve is linearly equivalent to the zero divisor.

comment

• # Paper 4, Section II, 21F

(a) Define the Euler characteristic of a triangulable space $X$.

(b) Let $\Sigma_{g}$ be an orientable surface of genus $g$. A $\operatorname{map} \pi: \Sigma_{g} \rightarrow S^{2}$ is a doublebranched cover if there is a set $Q=\left\{p_{1}, \ldots, p_{n}\right\} \subseteq S^{2}$ of branch points, such that the restriction $\pi: \Sigma_{g} \backslash \pi^{-1}(Q) \rightarrow S^{2} \backslash Q$ is a covering map of degree 2 , but for each $p \in Q$, $\pi^{-1}(p)$ consists of one point. By carefully choosing a triangulation of $S^{2}$, use the Euler characteristic to find a formula relating $g$ and $n$.

comment

• # Paper 4, Section II, $23 \mathrm{H}$

Fix $1 and let $q$ satisfy $p^{-1}+q^{-1}=1$

(a) Let $\left(f_{j}\right)$ be a sequence of functions in $L^{p}\left(\mathbb{R}^{n}\right)$. For $f \in L^{p}\left(\mathbb{R}^{n}\right)$, what is meant by (i) $f_{j} \rightarrow f$ in $L^{p}\left(\mathbb{R}^{n}\right)$ and (ii) $f_{j} \rightarrow f$ in $L^{p}\left(\mathbb{R}^{n}\right)$ ? Show that if $f_{j} \rightarrow f$, then

$\|f\|_{L^{p}} \leqslant \liminf _{j \rightarrow \infty}\left\|f_{j}\right\|_{L^{p}}$

(b) Suppose that $\left(g_{j}\right)$ is a sequence with $g_{j} \in L^{p}\left(\mathbb{R}^{n}\right)$, and that there exists $K>0$ such that $\left\|g_{j}\right\|_{L^{p}} \leqslant K$ for all $j$. Show that there exists $g \in L^{p}\left(\mathbb{R}^{n}\right)$ and a subsequence $\left(g_{j_{k}}\right)_{k=1}^{\infty}$, such that for any sequence $\left(h_{k}\right)$ with $h_{k} \in L^{q}\left(\mathbb{R}^{n}\right)$ and $h_{k} \rightarrow h \in L^{q}\left(\mathbb{R}^{n}\right)$, we have

$\lim _{k \rightarrow \infty} \int_{\mathbb{R}^{n}} g_{j_{k}} h_{k} d x=\int_{\mathbb{R}^{n}} g h d x .$

Give an example to show that the result need not hold if the condition $h_{k} \rightarrow h$ is replaced by $h_{k} \rightarrow h$ in $L^{q}\left(\mathbb{R}^{n}\right)$.

comment

• # Paper 4, Section II, B

(a) Consider the nearly free electron model in one dimension with mass $m$ and periodic potential $V(x)=\lambda U(x)$ with $0<\lambda \ll 1$ and

$U(x)=\sum_{l=-\infty}^{\infty} U_{l} \exp \left(\frac{2 \pi i}{a} l x\right)$

Ignoring degeneracies, the energy spectrum of Bloch states with wavenumber $k$ is

$E(k)=E_{0}(k)+\lambda\langle k|U| k\rangle+\lambda^{2} \sum_{k^{\prime} \neq k} \frac{\left\langle k|U| k^{\prime}\right\rangle\left\langle k^{\prime}|U| k\right\rangle}{E_{0}(k)-E_{0}\left(k^{\prime}\right)}+\mathcal{O}\left(\lambda^{3}\right)$

where $\{|k\rangle\}$ are normalized eigenstates of the free Hamiltonian with wavenumber $k$. What is $E_{0}$ in this formula?

If we impose periodic boundary conditions on the wavefunctions, $\psi(x)=\psi(x+L)$ with $L=N a$ and $N$ a positive integer, what are the allowed values of $k$ and $k^{\prime}$ ? Determine $\left\langle k|U| k^{\prime}\right\rangle$ for these allowed values.

(b) State when the above expression for $E(k)$ ceases to be a good approximation and explain why. Quoting any result you need from degenerate perturbation theory, calculate to $\mathcal{O}(\lambda)$ the location and width of the band gaps.

(c) Determine the allowed energy bands for each of the potentials

\begin{aligned} &\text { (i) } V(x)=2 \lambda \cos \left(\frac{2 \pi x}{a}\right) \text {, } \\ &\text { (ii) } V(x)=\lambda a \sum_{n=-\infty}^{\infty} \delta(x-n a) \text {. } \end{aligned}

(d) Briefly discuss a macroscopic physical consequence of the existence of energy bands.

comment

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

Let $(X(t))_{t \geqslant 0}$ be a continuous-time Markov process with state space $I=\{1, \ldots, n\}$ and generator $Q=\left(q_{i j}\right)_{i, j \in I}$ satisfying $q_{i j}=q_{j i}$ for all $i, j \in I$. The local time up to time $t>0$ of $X$ is the random vector $L(t)=\left(L_{i}(t)\right)_{i \in I} \in \mathbb{R}^{n}$ defined by

$L_{i}(t)=\int_{0}^{t} 1_{X(s)=i} d s \quad(i \in I)$

(a) Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be any function that is differentiable with respect to its second argument, and set

$f_{t}(i, \ell)=\mathbb{E}_{i} f(X(t), \ell+L(t)), \quad\left(i \in I, \ell \in \mathbb{R}^{n}\right)$

Show that

$\frac{\partial}{\partial t} f_{t}(i, \ell)=M f_{t}(i, \ell)$

where

$M f(i, \ell)=\sum_{j \in I} q_{i j} f(j, \ell)+\frac{\partial}{\partial \ell_{i}} f(i, \ell)$

(b) For $y \in \mathbb{R}^{n}$, write $y^{2}=\left(y_{i}^{2}\right)_{i \in I} \in[0, \infty)^{n}$ for the vector of squares of the components of $y$. Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function such that $f(i, \ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Using integration by parts, or otherwise, show that for all $i$

$-\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} \sum_{j=1}^{n} y_{j} M f\left(j, \frac{1}{2} y^{2}\right) d y=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) f\left(i, \frac{1}{2} y^{2}\right) d y,$

where $y^{T} Q y$ denotes $\sum_{k, m \in I} y_{k} q_{k m} y_{m}$.

(c) Let $g: \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function with $g(\ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Given $t>0, j \in I$, now let

$f(i, \ell)=\mathbb{E}_{i}\left[g(\ell+L(t)) 1_{X(t)=j}\right]$

in part (b) and deduce, using part (a), that

\begin{aligned} \int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} y_{j} g\left(\frac{1}{2} y^{2}\right) d y \\ &=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right)\left(\int_{0}^{\infty} \mathbb{E}_{i}\left[1_{X(t)=j} g\left(\frac{1}{2} y^{2}+L(t)\right)\right] d t\right) d y \end{aligned}

[You may exchange the order of integrals and derivatives without justification.]

comment

• # Paper 4, Section II, A

(a) Classify the nature of the point at $\infty$ for the ordinary differential equation

$y^{\prime \prime}+\frac{2}{x} y^{\prime}+\left(\frac{1}{x}-\frac{1}{x^{2}}\right) y=0 .$

(b) Find a transformation from $(*)$ to an equation of the form

$u^{\prime \prime}+q(x) u=0$

and determine $q(x)$.

(c) Given $u(x)$ satisfies ( $\dagger$, use the Liouville-Green method to find the first three terms in an asymptotic approximation as $x \rightarrow \infty$ for $u(x)$, verifying the consistency of any approximations made.

(d) Hence obtain corresponding asymptotic approximations as $x \rightarrow \infty$ of two linearly independent solutions $y(x)$ of $(*)$.

comment

• # Paper 4, Section I, $4 \mathrm{~F}$

State the pumping lemma for regular languages.

Which of the following languages over the alphabet $\{0,1\}$ are regular?

(i) $\left\{0^{i} 1^{i} 01 \mid i \geqslant 0\right\}$.

(ii) $\left\{w \bar{w} \mid w \in\{0,1\}^{*}\right\}$ where $\bar{w}$ is the reverse of the word $w$.

(iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ does not contain the subwords 01 or 10$\}$.

comment

• # Paper 4, Section I, D

Briefly describe a physical object (a Lagrange top) whose Lagrangian is

$L=\frac{1}{2} I_{1}\left(\dot{\theta}^{2}+\dot{\phi}^{2} \sin ^{2} \theta\right)+\frac{1}{2} I_{3}(\dot{\psi}+\dot{\phi} \cos \theta)^{2}-M g l \cos \theta$

Explain the meaning of the symbols in this equation.

Write down three independent integrals of motion for this system, and show that the nutation of the top is governed by the equation

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

where $u=\cos \theta$ and $f(u)$ is a certain cubic function that you need not determine.

comment
• # Paper 4, Section II, 15D

(a) Let $(\mathbf{q}, \mathbf{p})$ be a set of canonical phase-space variables for a Hamiltonian system with $n$ degrees of freedom. Define the Poisson bracket $\{f, g\}$ of two functions $f(\mathbf{q}, \mathbf{p})$ and $g(\mathbf{q}, \mathbf{p})$. Write down the canonical commutation relations that imply that a second set $(\mathbf{Q}, \mathbf{P})$ of phase-space variables is also canonical.

(b) Consider the near-identity transformation

$\mathbf{Q}=\mathbf{q}+\delta \mathbf{q}, \quad \mathbf{P}=\mathbf{p}+\delta \mathbf{p}$

where $\delta \mathbf{q}(\mathbf{q}, \mathbf{p})$ and $\delta \mathbf{p}(\mathbf{q}, \mathbf{p})$ are small. Determine the approximate forms of the canonical commutation relations, accurate to first order in $\delta \mathbf{q}$ and $\delta \mathbf{p}$. Show that these are satisfied when

$\delta \mathbf{q}=\epsilon \frac{\partial F}{\partial \mathbf{p}}, \quad \delta \mathbf{p}=-\epsilon \frac{\partial F}{\partial \mathbf{q}}$

where $\epsilon$ is a small parameter and $F(\mathbf{q}, \mathbf{p})$ is some function of the phase-space variables.

(c) In the limit $\epsilon \rightarrow 0$ this near-identity transformation is called the infinitesimal canonical transformation generated by $F$. Let $H(\mathbf{q}, \mathbf{p})$ be an autonomous Hamiltonian. Show that the change in the Hamiltonian induced by the infinitesimal canonical transformation is

$\delta H=-\epsilon\{F, H\} .$

Explain why $F$ is an integral of motion if and only if the Hamiltonian is invariant under the infinitesimal canonical transformation generated by $F$.

(d) The Hamiltonian of the gravitational $N$-body problem in three-dimensional space is

$H=\frac{1}{2} \sum_{i=1}^{N} \frac{\left|\mathbf{p}_{i}\right|^{2}}{2 m_{i}}-\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \frac{G m_{i} m_{j}}{\left|\mathbf{r}_{i}-\mathbf{r}_{j}\right|}$

where $m_{i}, \mathbf{r}_{i}$ and $\mathbf{p}_{i}$ are the mass, position and momentum of body $i$. Determine the form of $F$ and the infinitesimal canonical transformation that correspond to the translational symmetry of the system.

comment

• # Paper 4 , Section I, $3 K$

Describe the Rabin scheme for coding a message $x$ as $x^{2}$ modulo a certain integer $N$.

Describe the RSA encryption scheme with public key $(N, e)$ and private key $d$.

[In both cases you should explain how you encrypt and decrypt.]

Give an advantage and a disadvantage that the Rabin scheme has over the RSA scheme.

comment

• # Paper 4, Section I, B

A collection of $N$ particles, with masses $m_{i}$ and positions $\mathbf{x}_{i}$, interact through a gravitational potential

$V=\sum_{i

Assume that the system is gravitationally bound, and that the positions $\mathbf{x}_{i}$ and velocities $\dot{\mathbf{x}}_{i}$ are bounded for all time. Further, define the time average of a quantity $X$ by

$\bar{X}=\lim _{t \rightarrow \infty} \frac{1}{t} \int_{0}^{t} X\left(t^{\prime}\right) \mathrm{d} t^{\prime}$

(a) Assuming that the time average of the kinetic energy $T$ and potential energy $V$ are well defined, show that

$\bar{T}=-\frac{1}{2} \bar{V}$

[You should consider the quantity $I=\frac{1}{2} \sum_{i=1}^{N} m_{i} \mathbf{x}_{i} \cdot \mathbf{x}_{i}$, with all $\mathbf{x}_{i}$ measured relative to the centre of mass.]

(b) Explain how part (a) can be used, together with observations, to provide evidence in favour of dark matter. [You may assume that time averaging may be replaced by an average over particles.]

comment

• # Paper 4, Section II, F

Let $I \subset \mathbb{R}$ be an interval, and $S \subset \mathbb{R}^{3}$ be a surface. Assume that $\alpha: I \rightarrow S$ is a regular curve parametrised by arc-length. Define the geodesic curvature of $\alpha$. What does it mean for $\alpha$ to be a geodesic curve?

State the global Gauss-Bonnet theorem including boundary terms.

Suppose that $S \subset \mathbb{R}^{3}$ is a surface diffeomorphic to a cylinder. How large can the number of simple closed geodesics on $S$ be in each of the following cases?

(i) $S$ has Gaussian curvature everywhere zero;

(ii) $S$ has Gaussian curvature everywhere positive;

(iii) $S$ has Gaussian curvature everywhere negative.

In cases where there can be two or more simple closed geodesics, must they always be disjoint? Justify your answer.

[A formula for the Gaussian curvature of a surface of revolution may be used without proof if clearly stated. You may also use the fact that a piecewise smooth curve on a cylinder without self-intersections either bounds a domain homeomorphic to a disc or is homotopic to the waist-curve of the cylinder.]

comment

• # Paper 4, Section II, A

(a) A continuous map $F$ of an interval into itself has a periodic orbit of period 3 . Prove that $F$ also has periodic orbits of period $n$ for all positive integers $n$.

(b) What is the minimum number of distinct orbits of $F$ of periods 2,4 and 5 ? Explain your reasoning with a directed graph. [Formal proof is not required.]

(c) Consider the piecewise linear map $F:[0,1] \rightarrow[0,1]$ defined by linear segments between $F(0)=\frac{1}{2}, F\left(\frac{1}{2}\right)=1$ and $F(1)=0$. Calculate the orbits of periods 2,4 and 5 that are obtained from the directed graph in part (b).

[In part (a) you may assume without proof:

(i) If $U$ and $V$ are non-empty closed bounded intervals such that $V \subseteq F(U)$ then there is a closed bounded interval $K \subseteq U$ such that $F(K)=V$.

(ii) The Intermediate Value Theorem.]

comment

• # Paper 4, Section II, 36C

(a) Define the electric displacement $\mathbf{D}(\mathbf{x}, t)$ for a medium which exhibits a linear response with polarisation constant $\epsilon$ to an applied electric field $\mathbf{E}(\mathbf{x}, t)$ with polarisation constant $\epsilon$. Write down the effective Maxwell equation obeyed by $\mathbf{D}(\mathbf{x})$ in the timeindependent case and in the absence of any additional mobile charges in the medium. Describe appropriate boundary conditions for the electric field at an interface between two regions with differing values of the polarisation constant. [You should discuss separately the components of the field normal to and tangential to the interface.]

(b) Consider a sphere of radius $a$, centred at the origin, composed of dielectric material with polarisation constant $\epsilon$ placed in a vacuum and subjected to a constant, asymptotically homogeneous, electric field, $\mathbf{E}(\mathbf{x}, t)=\mathbf{E}(\mathbf{x})$ with $\mathbf{E}(\mathbf{x}) \rightarrow \mathbf{E}_{0}$ as $|\mathbf{x}| \rightarrow \infty$. Using the ansatz

$\mathbf{E}(\mathbf{x})= \begin{cases}\alpha \mathbf{E}_{0}, & |\mathbf{x}|a\end{cases}$

with constants $\alpha, \beta$ and $\delta$ to be determined, find a solution to Maxwell's equations with appropriate boundary conditions at $|\mathbf{x}|=a$.

(c) By comparing your solution with the long-range electric field due to a dipole consisting of electric charges $\pm q$ located at displacements $\pm \mathbf{d} / 2$ find the induced electric dipole moment of the dielectric sphere.

comment

• # Paper 4, Section II, A

Consider a steady axisymmetric flow with components $(-\alpha r, v(r), 2 \alpha z)$ in cylindrical polar coordinates $(r, \theta, z)$, where $\alpha$ is a positive constant. The fluid has density $\rho$ and kinematic viscosity $\nu$.

(a) Briefly describe the flow and confirm that it is incompressible.

(b) Show that the vorticity has one component $\omega(r)$, in the $z$ direction. Write down the corresponding vorticity equation and derive the solution

$\omega=\omega_{0} e^{-\alpha r^{2} /(2 \nu)}$

Hence find $v(r)$ and show that it has a maximum at some finite radius $r^{*}$, indicating how $r^{*}$ scales with $\nu$ and $\alpha$.

(c) Find an expression for the net advection of angular momentum, prv, into the finite cylinder defined by $r \leqslant r_{0}$ and $-z_{0} \leqslant z \leqslant z_{0}$. Show that this is always positive and asymptotes to the value

$\frac{8 \pi \rho z_{0} \omega_{0} \nu^{2}}{\alpha}$

as $r_{0} \rightarrow \infty$

(d) Show that the torque exerted on the cylinder of part (c) by the exterior flow is always negative and demonstrate that it exactly balances the net advection of angular momentum. Comment on why this has to be so.

[You may assume that for a flow $(u, v, w)$ in cylindrical polar coordinates

\begin{aligned} & e_{r \theta}=\frac{r}{2} \frac{\partial}{\partial r}\left(\frac{v}{r}\right)+\frac{1}{2 r} \frac{\partial u}{\partial \theta}, \quad e_{\theta z}=\frac{1}{2 r} \frac{\partial w}{\partial \theta}+\frac{1}{2} \frac{\partial v}{\partial z}, \quad e_{r z}=\frac{1}{2} \frac{\partial u}{\partial z}+\frac{1}{2} \frac{\partial w}{\partial r} \\ & \text { and } \left.\boldsymbol{\omega}=\frac{1}{r}\left|\begin{array}{ccc}\mathbf{e}_{r} & r \mathbf{e}_{\theta} & \mathbf{e}_{z} \\\partial / \partial r & \partial / \partial \theta & \partial / \partial z \\u & r v & w\end{array}\right| .\right] \end{aligned}

comment

• # Paper 4 , Section I, 7E

(a) Explain in general terms the meaning of the Papperitz symbol

$P\left\{\begin{array}{cccc} a & b & c & \\ \alpha & \beta & \gamma & z \\ \alpha^{\prime} & \beta^{\prime} & \gamma^{\prime} & \end{array}\right\}$

State a condition satisfied by $\alpha, \beta, \gamma, \alpha^{\prime}, \beta^{\prime}$ and $\gamma^{\prime}$. [You need not write down any differential equations explicitly, but should provide explicit explanation of the meaning of $a, b, c, \alpha, \beta, \gamma, \alpha^{\prime}, \beta^{\prime}$ and $\left.\gamma^{\prime} .\right]$

(b) The Papperitz symbol

$P\left\{\begin{array}{cccc} 1 & -1 & \infty & \\ -m / 2 & m / 2 & n & z \\ m / 2 & -m / 2 & 1-n \end{array}\right\}$

where $n, m$ are constants, can be transformed into

$P\left\{\begin{array}{cccc} 0 & 1 & \infty & \\ 0 & 0 & n & \frac{1-z}{2} \\ m & -m & 1-n & \end{array}\right\}$

(i) Provide an explicit description of the transformations required to obtain ( $*)$ from $(t)$.

(ii) One of the solutions to the $P$-equation that corresponds to $(*)$ is a hypergeometric function $F\left(a, b ; c ; z^{\prime}\right)$. Express $a, b, c$ and $z^{\prime}$ in terms of $n, m$ and $z$.

comment

• # Paper 4 , Section II, 18I

Let $L$ be a field, and $G$ a group which acts on $L$ by field automorphisms.

(a) Explain the meaning of the phrase in italics in the previous sentence.

Show that the set $L^{G}$ of fixed points is a subfield of $L$.

(b) Suppose that $G$ is finite, and set $K=L^{G}$. Let $\alpha \in L$. Show that $\alpha$ is algebraic and separable over $K$, and that the degree of $\alpha$ over $K$ divides the order of $G$.

Assume that $\alpha$ is a primitive element for the extension $L / K$, and that $G$ is a subgroup of $\operatorname{Aut}(L)$. What is the degree of $\alpha$ over $K$ ? Justify your answer.

(c) Let $L=\mathbb{C}(z)$, and let $\zeta_{n}$ be a primitive $n$th root of unity in $\mathbb{C}$ for some integer $n>1$. Show that the $\mathbb{C}$-automorphisms $\sigma, \tau$ of $L$ defined by

$\sigma(z)=\zeta_{n} z, \quad \tau(z)=1 / z$

generate a group $G$ isomorphic to the dihedral group of order $2 n$.

Find an element $w \in L$ for which $L^{G}=\mathbb{C}(w)$.

comment

• # Paper 4 , Section II, $37 \mathrm{C}$

(a) A flat $(k=0)$, isotropic and homogeneous universe has metric $g_{\alpha \beta}$ given by

$d s^{2}=-d t^{2}+a^{2}(t)\left(d x^{2}+d y^{2}+d z^{2}\right)$

(i) Show that the non-vanishing Christoffel symbols and Ricci tensor components are

$\Gamma_{i i}^{0}=a \dot{a}, \quad \Gamma_{0 i}^{i}=\Gamma_{i 0}^{i}=\frac{\dot{a}}{a}, \quad R_{00}=-3 \frac{\ddot{a}}{a}, \quad R_{i i}=a \ddot{a}+2 \dot{a}^{2}$

where dots are time derivatives and $i \in\{1,2,3\}$ (no summation assumed).

(ii) Derive the first-order Friedmann equation from the Einstein equations, $G_{\alpha \beta}+\Lambda g_{\alpha \beta}=8 \pi T_{\alpha \beta} .$

(b) Consider a flat universe described by ( $\dagger$ ) with $\Lambda=0$ in which late-time acceleration is driven by "phantom" dark energy obeying an equation of state with pressure $P_{\mathrm{ph}}=w \rho_{\mathrm{ph}}$, where $w<-1$ and the energy density $\rho_{\mathrm{ph}}>0$. The remaining matter is dust, so we have $\rho=\rho_{\mathrm{ph}}+\rho_{\mathrm{dust}}$ with each component separately obeying $\dot{\rho}=-3 \frac{\dot{a}}{a}(\rho+P)$.

(i) Calculate an approximate solution for the scale factor $a(t)$ that is valid at late times. Show that the asymptotic behaviour is given by a Big Rip, that is, a singularity in which $a \rightarrow \infty$ at some finite time $t^{*}$.

(ii) Sketch a diagram of the scale factor $a$ as a function of $t$ for a convenient choice of $w$, ensuring that it includes (1) the Big Bang, (2) matter domination, (3) phantom-energy domination, and (4) the Big Rip. Label these epochs and mark them on the axes.

(iii) Most reasonable classical matter fields obey the null energy condition, which states that the energy-momentum tensor everywhere satisfies $T_{\alpha \beta} V^{\alpha} V^{\beta} \geqslant 0$ for any null vector $V^{\alpha}$. Determine if this applies to phantom energy.

[The energy-momentum tensor for a perfect fluid is $\left.T_{\alpha \beta}=(\rho+P) u_{\alpha} u_{\beta}+P g_{\alpha \beta}\right]$

comment

• # Paper 4, Section II, 17G

State and prove Hall's theorem, giving any definitions required by the proof (e.g. of an $M$-alternating path).

Let $G=(V, E)$ be a (not necessarily bipartite) graph, and let $\gamma(G)$ be the size of the largest matching in $G$. Let $\beta(G)$ be the smallest $k$ for which there exist $k$ vertices $v_{1}, \ldots, v_{k} \in V$ such that every edge in $G$ is incident with at least one of $v_{1}, \ldots, v_{k}$. Show that $\gamma(G) \leqslant \beta(G)$ and that $\beta(G) \leqslant 2 \gamma(G)$. For each positive integer $k$, find a graph $G$ with $\beta(G)=2 k$ and $\gamma(G)=k$. Determine $\beta(G)$ and $\gamma(G)$ when $G$ is the Turan graph $T_{3}(30)$ on 30 vertices.

By using Hall's theorem, or otherwise, show that if $G$ is a bipartite graph then $\gamma(G)=\beta(G) .$

Define the chromatic index $\chi^{\prime}(G)$ of a graph $G$. Prove that if $n=2^{r}$ with $r \geqslant 1$ then $\chi^{\prime}\left(K_{n}\right)=n-1$.

comment

• # Paper 4, Section II, H

(a) Let $\left(H_{1},\langle\cdot, \cdot\rangle_{1}\right),\left(H_{2},\langle\cdot, \cdot\rangle_{2}\right)$ be two Hilbert spaces, and $T: H_{1} \rightarrow H_{2}$ be a bounded linear operator. Show that there exists a unique bounded linear operator $T^{*}: H_{2} \rightarrow H_{1}$ such that

$\left\langle T x_{1}, x_{2}\right\rangle_{2}=\left\langle x_{1}, T^{*} x_{2}\right\rangle_{1}, \quad \forall x_{1} \in H_{1}, x_{2} \in H_{2}$

(b) Let $H$ be a separable Hilbert space. We say that a sequence $\left(e_{i}\right)$ is a frame of $H$ if there exists $A, B>0$ such that

$\forall x \in H, \quad A\|x\|^{2} \leqslant \sum_{i \geqslant 1}\left|\left\langle x, e_{i}\right\rangle\right|^{2} \leqslant B\|x\|^{2}$

State briefly why such a frame exists. From now on, let $\left(e_{i}\right)$ be a frame of $H$. Show that $\operatorname{Span}\left\{e_{i}\right\}$ is dense in $H$.

(c) Show that the linear map $U: H \rightarrow \ell^{2}$ given by $U(x)=\left(\left\langle x, e_{i}\right\rangle\right)_{i \geqslant 1}$ is bounded and compute its adjoint $U^{*}$.

(d) Assume now that $\left(e_{i}\right)$ is a Hilbertian (orthonormal) basis of $H$ and let $a \in H$. Show that the Hilbert cube $\mathcal{C}_{a}=\left\{x \in H\right.$ such that $\left.\forall i \geqslant 1,\left|\left\langle x, e_{i}\right\rangle\right| \leqslant\left|\left\langle a, e_{i}\right\rangle\right|\right\}$ is a compact subset of $H$.

comment

• # Paper 4, Section II, 16G

Write down the Axiom of Foundation.

What is the transitive closure of a set $x$ ? Prove carefully that every set $x$ has a transitive closure. State and prove the principle of $\in$-induction.

Let $(V, \in)$ be a model of $\mathrm{ZF}$. Let $F: V \rightarrow V$ be a surjective function class such that for all $x, y \in V$ we have $F(x) \in F(y)$ if and only if $x \in y$. Show, by $\in$-induction or otherwise, that $F$ is the identity.

comment

• # Paper 4, Section I, E

A marine population grows logistically and disperses by diffusion. It is moderately predated on up to a distance $L$ from a straight coast. Beyond that distance, predation is sufficiently excessive to eliminate the population. The density $n(x, t)$ of the population at a distance $x from the coast satisfies

$\frac{\partial n}{\partial t}=r n\left(1-\frac{n}{K}\right)-\delta n+D \frac{\partial^{2} n}{\partial x^{2}}$

subject to the boundary conditions

$\frac{\partial n}{\partial x}=0 \text { at } x=0, \quad n=0 \text { at } x=L$

(a) Interpret the terms on the right-hand side of $(*)$, commenting on their dependence on $n$. Interpret the boundary conditions.

(b) Show that a non-zero population is viable if $r>\delta$ and

$L>\frac{\pi}{2} \sqrt{\frac{D}{r-\delta}}$

Interpret these conditions.

comment
• # Paper 4, Section II, E

The spatial density $n(x, t)$ of a population at location $x$ and time $t$ satisfies

$\frac{\partial n}{\partial t}=f(n)+D \frac{\partial^{2} n}{\partial x^{2}}$

where $f(n)=-n(n-r)(n-1), 0 and $D>0$.

(a) Give a biological example of the sort of phenomenon that this equation describes.

(b) Show that there are three spatially homogeneous and stationary solutions to $(*)$, of which two are linearly stable to homogeneous perturbations and one is linearly unstable.

(c) For $r=\frac{1}{2}$, find the stationary solution to $(*)$ subject to the conditions

$\lim _{x \rightarrow-\infty} n(x)=1, \quad \lim _{x \rightarrow \infty} n(x)=0 \quad \text { and } \quad n(0)=\frac{1}{2}$

(d) Write down the differential equation that is satisfied by a travelling-wave solution to $(*)$ of the form $n(x, t)=u(x-c t)$. Let $n_{0}(x)$ be the solution from part (c). Verify that $n_{0}(x-c t)$ satisfies this differential equation for $r \neq \frac{1}{2}$, provided the speed $c$ is chosen appropriately. [Hint: Consider the change to the equation from part (c).]

(e) State how the sign of $c$ depends on $r$, and give a brief qualitative explanation for why this should be the case.

comment

• # Paper 4, Section II, J

Let $D=\left(x_{i}, y_{i}\right)_{i=1}^{n}$ be a dataset of $n$ input-output pairs lying in $\mathbb{R}^{p} \times[-M, M]$ for $M \in \mathbb{R}$. Describe the random-forest algorithm as applied to $D$ using decision trees $\left(\hat{T}^{(b)}\right)_{b=1}^{B}$ to produce a fitted regression function $f_{\mathrm{rf}}$. [You need not explain in detail the construction of decision trees, but should describe any modifications specific to the random-forest algorithm.]

Briefly explain why for each $x \in \mathbb{R}^{p}$ and $b=1, \ldots, B$, we have $\hat{T}^{(b)}(x) \in[-M, M]$.

State the bounded-differences inequality.

Treating $D$ as deterministic, show that with probability at least $1-\delta$,

$\sup _{x \in \mathbb{R}^{p}}\left|f_{\mathrm{rf}}(x)-\mu(x)\right| \leqslant M \sqrt{\frac{2 \log (1 / \delta)}{B}}+\mathbb{E}\left(\sup _{x \in \mathbb{R}^{p}}\left|f_{\mathrm{rf}}(x)-\mu(x)\right|\right),$

where $\mu(x):=\mathbb{E} f_{\mathrm{rf}}(x)$.

$\left[\right.$ Hint: Treat each $\hat{T}^{(b)}$ as a random variable taking values in an appropriate space $\mathcal{Z}$ (of functions), and consider a function $G$ satisfying

$G\left(\hat{T}^{(1)}, \ldots, \hat{T}^{(B)}\right)=\sup _{x \in \mathbb{R}^{p}}\left|f_{\mathrm{rf}}(x)-\mu(x)\right|$

comment

• # Paper 4 , Section II, 20G

(a) Compute the class group of $K=\mathbb{Q}(\sqrt{30})$. Find also the fundamental unit of $K$, stating clearly any general results you use.

[The Minkowski bound for a real quadratic field is $\left|d_{K}\right|^{1 / 2} / 2 .$ ]

(b) Let $K=\mathbb{Q}(\sqrt{d})$ be real quadratic, with embeddings $\sigma_{1}, \sigma_{2} \hookrightarrow \mathbb{R}$. An element $\alpha \in K$ is totally positive if $\sigma_{1}(\alpha)>0$ and $\sigma_{2}(\alpha)>0$. Show that the totally positive elements of $K$ form a subgroup of the multiplicative group $K^{*}$ of index 4 .

Let $I, J \subset \mathcal{O}_{K}$ be non-zero ideals. We say that $I$ is narrowly equivalent to $J$ if there exists a totally positive element $\alpha$ of $K$ such that $I=\alpha J$. Show that this is an equivalence relation, and that the equivalence classes form a group under multiplication. Show also that the order of this group equals

$\begin{cases}\text { the class number } h_{K} \text { of } K & \text { if the fundamental unit of } K \text { has norm }-1 \\ 2 h_{K} & \text { otherwise. }\end{cases}$

comment

• # Paper 4, Section I, I

Let $p$ be a prime, and let $N=\left(\begin{array}{c}2 n \\ n\end{array}\right)$ for some positive integer $n$.

Show that if a prime power $p^{k}$ divides $N$ for some $k \geqslant 1$, then $p^{k} \leqslant 2 n$.

Given a positive real $x$, define $\psi(x)=\sum_{n \leqslant x} \Lambda(n)$, where $\Lambda(n)$ is the von Mangoldt function, taking the value $\log p$ if $n=p^{k}$ for some prime $p$ and integer $k \geqslant 1$, and 0 otherwise. Show that

$\psi(x)=\sum_{p \leqslant x, p \text { prime }}\left\lfloor\frac{\log x}{\log p}\right\rfloor \log p$

Deduce that for all integers $n>1, \psi(2 n) \geqslant n \log 2$.

comment
• # Paper 4, Section II, I

(a) 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 a (Fermat) pseudoprime to base b?

Let $b, k \geqslant 2$ be integers. Show that if $N \geqslant 3$ is an odd composite integer dividing $b^{k}-1$ and satisfying $N \equiv 1 \bmod k$, then $N$ is a pseudoprime to base $b$.

(b) Fix $b \geqslant 2$. Let $p$ be an odd prime not dividing $b^{2}-1$, and let

$n=\frac{b^{p}-1}{b-1} \quad \text { and } \quad m=\frac{b^{p}+1}{b+1} .$

Use the conclusion of part (a) to show that $N=n m$ is a pseudoprime to base $b$. Deduce that there are infinitely many pseudoprimes to base $b$.

(c) Let $b, k \geqslant 2$ be integers, and let $n=p_{1} \cdots p_{k}$, where $p_{1}, p_{2}, \ldots, p_{k}$ are distinct primes not dividing $2 b$. For each $j=1,2, \ldots, k$, let $r_{j}=n / p_{j}$. Show that $n$ is a pseudoprime to base $b$ if and only if for all $j=1,2, \ldots, k$, the order of $b$ modulo $p_{j}$ divides $r_{j}-1$.

(d) By considering products of prime factors of $2^{k}-1$ and $2^{k}+1$ for primes $k \geqslant 5$, deduce that there are infinitely many pseudoprimes to base 2 with two prime factors.

[Hint: You may assume that $\operatorname{gcd}(j, k)=1$ for $j, k \geqslant 1$ implies $\operatorname{gcd}\left(2^{j}-1,2^{k}-1\right)=1$, and that for $k>3,2^{k}+1$ is not a power of 3.]

comment

• # Paper 4 , Section II, 40E

(a) Show that if $A$ and $B$ are real matrices such that both $A$ and $A-B-B^{T}$ are symmetric positive definite, then the spectral radius of $H=-(A-B)^{-1} B$ is strictly less than $1 .$

(b) Consider the Poisson equation $\nabla^{2} u=f$ (with zero Dirichlet boundary condition) on the unit square, where $f$ is some smooth function. Given $m \in \mathbb{N}$ and an equidistant grid on the unit square with stepsize $h=1 /(m+1)$, the standard five-point method is given by

$u_{i-1, j}+u_{i+1, j}+u_{i, j-1}+u_{i, j+1}-4 u_{i, j}=h^{2} f_{i, j}, \quad i, j=1, \ldots, m$

where $f_{i, j}=f(i h, j h)$ and $u_{0, j}=u_{m+1, j}=u_{i, 0}=u_{i, m+1}=0$. Equation $(*)$ can be written as a linear system $A x=b$, where $A \in \mathbb{R}^{m^{2} \times m^{2}}$ and $b \in \mathbb{R}^{m^{2}}$ both depend on the chosen ordering of the grid points.

Use the result in part (a) to show that the Gauss-Seidel method converges for the linear system $A x=b$ described above, regardless of the choice of ordering of the grid points.

[You may quote convergence results - based on the spectral radius of the iteration matrix - mentioned in the lecture notes.]

comment

• # Paper 4, Section II, 33B

(a) A quantum system has Hamiltonian $H=H_{0}+V(t)$. Let $\{|n\rangle\}_{n \in \mathbb{N}_{0}}$ be an orthonormal basis of $H_{0}$ eigenstates, with corresponding energies $E_{n}=\hbar \omega_{n}$. For $t<0$, $V(t)=0$ and the system is in state $|0\rangle$. Calculate the probability that it is found to be in state $|1\rangle$ at time $t>0$, correct to lowest non-trivial order in $V$.

(b) Now suppose $\{|0\rangle,|1\rangle\}$ form a basis of the Hilbert space, with respect to which

$\left(\begin{array}{cc} \langle 0|H| 0\rangle & \langle 0|H| 1\rangle \\ \langle 1|H| 0\rangle & \langle 1|H| 1\rangle \end{array}\right)=\left(\begin{array}{cc} \hbar \omega_{0} & \hbar v \Theta(t) e^{i \omega t} \\ \hbar v \Theta(t) e^{-i \omega t} & \hbar \omega_{1} \end{array}\right)$

where $\Theta(t)$ is the Heaviside step function and $v$ is a real constant. Calculate the exact probability that the system is in state $|1\rangle$ at time $t$. For which frequency $\omega$ is this probability maximized?

comment

• # Paper 4, Section II, J

Suppose that $X \mid \theta \sim \operatorname{Poisson}(\theta), \theta>0$, and suppose the prior $\pi$ on $\theta$ is a gamma distribution with parameters $\alpha>0$ and $\beta>0$. [Recall that $\pi$ has probability density function

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

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

(a) Find the $\pi$-Bayes estimator for $\theta$ for the quadratic loss, and derive its quadratic risk function.

(b) Suppose we wish to estimate $\mu=e^{-\theta}=\mathbb{P}_{\theta}(X=0)$. Find the $\pi$-Bayes estimator for $\mu$ for the quadratic loss, and derive its quadratic risk function. [Hint: The moment generating function of a Poisson $(\theta)$ distribution is $M(t)=\exp \left(\theta\left(e^{t}-1\right)\right)$ for $t \in \mathbb{R}$, and that of a Gamma $(\alpha, \beta)$ distribution is $M(t)=(1-t / \beta)^{-\alpha}$ for $t<\beta$.]

(c) State a sufficient condition for an admissible estimator to be minimax, and give a proof of this fact.

(d) For each of the estimators in parts (a) and (b), is it possible to deduce using the condition in (c) that the estimator is minimax for some value of $\alpha$ and $\beta$ ? Justify your answer.

comment

• # Paper 4, Section II, 26H

Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space. Show that for any sequence $A_{n} \in \mathcal{F}$ satisfying $\sum_{n=1}^{\infty} \mathbb{P}\left(A_{n}\right)<\infty$ one necessarily has $\mathbb{P}\left(\limsup A_{n} A_{n}\right)=0 .$

Let $\left(X_{n}: n \in \mathbb{N}\right)$ and $X$ be random variables defined on $(\Omega, \mathcal{F}, \mathbb{P})$. Show that $X_{n} \rightarrow X$ almost surely as $n \rightarrow \infty$ implies that $X_{n} \rightarrow X$ in probability as $n \rightarrow \infty$.

Show that $X_{n} \rightarrow X$ in probability as $n \rightarrow \infty$ if and only if for every subsequence $X_{n(k)}$ there exists a further subsequence $X_{n(k(r))}$ such that $X_{n(k(r))} \rightarrow X$ almost surely as $r \rightarrow \infty$.

comment

• # Paper 4, Section I, $10 D$

Let $\mathcal{H}$ be a state space of dimension $N$ with standard orthonormal basis $\{|k\rangle\}$ labelled by $k \in \mathbb{Z}_{N}$. Let QFT denote the quantum Fourier transform $\bmod N$ and let $S$ denote the operation defined by $S|k\rangle=|k+1 \bmod N\rangle$.

(a) Introduce the basis $\left\{\left|\chi_{k}\right\rangle\right\}$ defined by $\left|\chi_{k}\right\rangle=\mathrm{QFT}^{-1}|k\rangle$. Show that each $\left|\chi_{k}\right\rangle$ is an eigenstate of $S$ and determine the corresponding eigenvalue.

(b) By expressing a generic state $|v\rangle \in \mathcal{H}$ in the $\left\{\left|\chi_{k}\right\rangle\right\}$ basis, show that QFT $|v\rangle$ and QFT $(S|v\rangle)$ have the same output distribution if measured in the standard basis.

(c) Let $A, r$ be positive integers with $A r=N$, and let $x_{0}$ be an integer with $0 \leqslant x_{0}. Suppose that we are given the state

$|\xi\rangle=\frac{1}{\sqrt{A}} \sum_{j=0}^{A-1}\left|x_{0}+j r \bmod N\right\rangle$

where $x_{0}$ and $r$ are unknown to us. Using part (b) or otherwise, show that a standard basis measurement on QFT $|\xi\rangle$ has an output distribution that is independent of $x_{0}$.

comment

• # Paper 4, Section II, I

(a) Define the group $S^{1}$. Sketch a proof of the classification of the irreducible continuous representations of $S^{1}$. Show directly that the characters obey an orthogonality relation.

(b) Define the group $S U(2)$.

(i) Show that there is a bijection between the conjugacy classes in $G=S U(2)$ and the subset $[-1,1]$ of the real line. [If you use facts about a maximal torus $T$, you should prove them.]

(ii) Write $\mathcal{O}_{x}$ for the conjugacy class indexed by an element $x$, where $-1. Show that $\mathcal{O}_{x}$ is homeomorphic to $S^{2}$. [Hint: First show that $\mathcal{O}_{x}$ is in bijection with $G / T$.

(iii) Let $t: G \rightarrow[-1,1]$ be the parametrisation of conjugacy classes from part (i). Determine the representation of $G$ whose character is the function $g \mapsto 8 t(g)^{3}$.

comment

• # Paper 4 , Section I, J

The data frame data contains the daily number of new avian influenza cases in a large poultry farm.

Write down the model being fitted by the $R$ code below. Does the model seem to provide a satisfactory fit to the data? Justify your answer.

The owner of the farm estimated that the size of the epidemic was initially doubling every 7 days. Is that estimate supported by the analysis below? [You may need $\log 2 \approx 0.69$.]

comment
• # Paper 4, Section II, J

Let $X$ be an $n \times p$ non-random design matrix and $Y$ be a $n$-vector of random responses. Suppose $Y \sim N\left(\mu, \sigma^{2} I\right)$, where $\mu$ is an unknown vector and $\sigma^{2}>0$ is known.

(a) Let $\lambda \geqslant 0$ be a constant. Consider the ridge regression problem

$\hat{\beta}_{\lambda}=\arg \min _{\beta}\|Y-X \beta\|^{2}+\lambda\|\beta\|^{2} .$

Let $\hat{\mu}_{\lambda}=X \hat{\beta}_{\lambda}$ be the fitted values. Show that $\hat{\mu}_{\lambda}=H_{\lambda} Y$, where

$H_{\lambda}=X\left(X^{T} X+\lambda I\right)^{-1} X^{T}$

(b) Show that

$\mathbb{E}\left(\left\|Y-\hat{\mu}_{\lambda}\right\|^{2}\right)=\left\|\left(I-H_{\lambda}\right) \mu\right\|^{2}+\left\{n-2 \operatorname{trace}\left(H_{\lambda}\right)+\operatorname{trace}\left(H_{\lambda}^{2}\right)\right\} \sigma^{2}$

(c) Let $Y^{*}=\mu+\epsilon^{*}$, where $\epsilon^{*} \sim \mathrm{N}\left(0, \sigma^{2} I\right)$ is independent of $Y$. Show that $\left\|Y-\hat{\mu}_{\lambda}\right\|^{2}+2 \sigma^{2} \operatorname{trace}\left(H_{\lambda}\right)$ is an unbiased estimator of $\mathbb{E}\left(\left\|Y^{*}-\hat{\mu}_{\lambda}\right\|^{2}\right)$.

(d) Describe the behaviour (monotonicity and limits) of $\mathbb{E}\left(\left\|Y^{*}-\hat{\mu}_{\lambda}\right\|^{2}\right)$ as a function of $\lambda$ when $p=n$ and $X=I$. What is the minimum value of $\mathbb{E}\left(\left\|Y^{*}-\hat{\mu}_{\lambda}\right\|^{2}\right)$ ?

comment

• # Paper 4, Section II, 35C

(a) Explain what is meant by a first-order phase transition and a second-order phase transition.

(b) Explain why the (Helmholtz) free energy is the appropriate thermodynamic potential to consider at fixed $T, V$ and $N$.

(c) Consider a ferromagnet with free energy

$F(T, m)=F_{0}(T)+\frac{a}{2}\left(T-T_{c}\right) m^{2}+\frac{b}{4} m^{4}$

where $T$ is the temperature, $m$ is the magnetization, and $a, b, T_{c}>0$ are constants.

Find the equilibrium value of $m$ at high and low temperatures. Hence, evaluate the equilibrium thermodynamic free energy as a function of $T$ and compute the entropy and heat capacity. Determine the jump in the heat capacity and identify the order of the phase transition.

(d) Now consider a ferromagnet with free energy

$F(T, m)=F_{0}(T)+\frac{a}{2}\left(T-T_{c}\right) m^{2}+\frac{b}{4} m^{4}+\frac{c}{6} m^{6}$

where $a, b, c, T_{c}$ are constants with $a, c, T_{c}>0$, but $b \leqslant 0$.

Find the equilibrium value of $m$ at high and low temperatures. What is the order of the phase transition?

For $b=0$ determine the behaviour of the heat capacity at high and low temperatures.

comment

• # Paper 4, Section II, 29K

(a) What does it mean to say that a stochastic process is a Brownian motion? Show that, if $\left(W_{t}\right)_{t \geqslant 0}$ is a continuous Gaussian process such that $\mathbb{E}\left(W_{t}\right)=0$ and $\mathbb{E}\left(W_{s} W_{t}\right)=s$ for all $0 \leqslant s \leqslant t$, then $\left(W_{t}\right)_{t \geqslant 0}$ is a Brownian motion.

For the rest of the question, let $\left(W_{t}\right)_{t \geqslant 0}$ be a Brownian motion.

(b) Let $\widehat{W}_{0}=0$