Part II, 2018, Paper 2

Algebraic Geometry

• Paper 2, Section II, I

  Algebraic Geometry | Part II, 2018

  (a) Let $X \subseteq \mathbf{A}^{n}$ be an affine algebraic variety defined over the field $k$.

  Define the tangent space $T_{p} X$ for $p \in X$, and the dimension of $X$ in terms of $T_{p} X$.

  Suppose that $k$ is an algebraically closed field with char $k>0$. Show directly from your definition that if $X=Z(f)$, where $f \in k\left[x_{1}, \ldots, x_{n}\right]$ is irreducible, then $\operatorname{dim} X=n-1$.

  [Any form of the Nullstellensatz may be used if you state it clearly.]

  (b) Suppose that char $k=0$, and let $W$ be the vector space of homogeneous polynomials of degree $d$ in 3 variables over $k$. Show that

  $$U=\left\{(f, p) \in W \times k^{3} \mid Z(f-1) \text { is a smooth surface at } p\right\}$$

  is a non-empty Zariski open subset of $W \times k^{3}$.

  comment

Algebraic Topology

• Paper 2, Section II, H

  Algebraic Topology | Part II, 2018

  (a) Define the first barycentric subdivision $K^{\prime}$ of a simplicial complex $K$. Hence define the $r^{t h}$ barycentric subdivision $K^{(r)}$. [You do not need to prove that $K^{\prime}$ is a simplicial complex.]

  (b) Define the mesh $\mu(K)$ of a simplicial complex $K$. State a result that describes the behaviour of $\mu\left(K^{(r)}\right)$ as $r \rightarrow \infty$.

  (c) Define a simplicial approximation to a continuous map of polyhedra

  $$f:|K| \rightarrow|L|$$

  Prove that, if $g$ is a simplicial approximation to $f$, then the realisation $|g|:|K| \rightarrow|L|$ is homotopic to $f$.

  (d) State and prove the simplicial approximation theorem. [You may use the Lebesgue number lemma without proof, as long as you state it clearly.]

  (e) Prove that every continuous map of spheres $S^{n} \rightarrow S^{m}$ is homotopic to a constant map when $n<m$.

  comment

Applications of Quantum Mechanics

• Paper 2, Section II, A

  Applications of Quantum Mechanics | Part II, 2018

  Consider a one-dimensional chain of $2 N \gg 1$ atoms, each of mass $m$. Impose periodic boundary conditions. The forces between neighbouring atoms are modelled as springs, with alternating spring constants $\lambda$ and $\alpha \lambda$. In equilibrium, the separation between the atoms is $a$.

  Denote the position of the $n^{\text {th }}$atom as $x_{n}(t)$. Let $u_{n}(t)=x_{n}(t)-n a$ be the displacement from equilibrium. Write down the equations of motion of the system.

  Show that the longitudinal modes of vibration are labelled by a wavenumber $k$ that is restricted to lie in a Brillouin zone. Find the frequency spectrum. What is the frequency gap at the edge of the Brillouin zone? Show that the gap vanishes when $\alpha=1$. Determine approximations for the frequencies near the centre of the Brillouin zone. Plot the frequency spectrum. What is the speed of sound in this system?

  comment

Applied Probability

• Paper 2, Section II, J

  Applied Probability | Part II, 2018

  Let $X=\left(X_{t}: t \geqslant 0\right)$ be a continuous-time Markov chain on the finite state space $S$. Define the terms generator (or Q-matrix) and invariant distribution, and derive an equation that links the generator $G$ and any invariant distribution $\pi$. Comment on the possible non-uniqueness of invariant distributions.

  Suppose $X$ is irreducible, and let $N=\left(N_{t}: t \geqslant 0\right)$ be a Poisson process with intensity $\lambda$, that is independent of $X$. Let $Y_{n}$ be the value of $X$ immediately after the $n$th arrival-time of $N$ (and $\left.Y_{0}=X_{0}\right)$. Show that $\left(Y_{n}: n=0,1, \ldots\right)$ is a discrete-time Markov chain, state its transition matrix and prove that it has the same invariant distribution as $X$.

  comment

Asymptotic Methods

• Paper 2, Section II, B

  Asymptotic Methods | Part II, 2018

  Given that $\int_{-\infty}^{+\infty} e^{-u^{2}} d u=\sqrt{\pi}$ obtain the value of $\lim _{R \rightarrow+\infty} \int_{-R}^{+R} e^{-i t u^{2}} d u$ for real positive $t$. Also obtain the value of $\lim _{R \rightarrow+\infty} \int_{0}^{R} e^{-i t u^{3}} d u$, for real positive $t$, in terms of $\Gamma\left(\frac{4}{3}\right)=\int_{0}^{+\infty} e^{-u^{3}} d u .$

  For $\alpha>0, x>0$, let

  $$Q_{\alpha}(x)=\frac{1}{\pi} \int_{0}^{\pi} \cos (x \sin \theta-\alpha \theta) d \theta$$

  Find the leading terms in the asymptotic expansions as $x \rightarrow+\infty$ of (i) $Q_{\alpha}(x)$ with $\alpha$ fixed, and (ii) of $Q_{x}(x)$.

  comment

Automata and Formal Languages

• Paper 2, Section I, G

  Automata and Formal Languages | Part II, 2018

  (a) Let $E=\left(Q_{E}, \Sigma, \delta_{E}, q_{0}, F_{E}\right)$ be a nondeterministic finite-state automaton with $\epsilon$-transitions $(\epsilon$-NFA). Define the deterministic finite-state automaton (DFA) $D=\left(Q_{D}, \Sigma, \delta_{D}, q_{D}, F_{D}\right)$ obtained from $E$ via the subset construction with $\epsilon$-transitions.

  (b) Let $E$ and $D$ be as above. By inducting on lengths of words, prove that

  $$\hat{\delta}_{E}\left(q_{0}, w\right)=\hat{\delta}_{D}\left(q_{D}, w\right) \text { for all } w \in \Sigma^{*}$$

  (c) Deduce that $\mathcal{L}(D)=\mathcal{L}(E)$.

  comment

Classical Dynamics

• Paper 2, Section I, B

  Classical Dynamics | Part II, 2018

  Let $\mathbf{x}=x \mathbf{i}+y \mathbf{j}+z \mathbf{k}$. Consider a Lagrangian

  $$\mathcal{L}=\frac{1}{2} \dot{\mathbf{x}}^{2}+y \dot{x}$$

  of a particle constrained to move on a sphere $|\mathbf{x}|=1 / c$ of radius $1 / c$. Use Lagrange multipliers to show that

  $$\ddot{\mathbf{x}}+\ddot{y} \mathbf{i}-\dot{x} \mathbf{j}+c^{2}\left(|\dot{\mathbf{x}}|^{2}+y \dot{x}-x \dot{y}\right) \mathbf{x}=0$$

  Now, consider the system $(*)$ with $c=0$, and find the particle trajectories.

  comment

• Paper 2, Section II, B

  Classical Dynamics | Part II, 2018

  Define a body frame $\mathbf{e}_{a}(t), a=1,2,3$ of a rotating rigid body, and show that there exists a vector $\boldsymbol{\omega}=\left(\omega_{1}, \omega_{2}, \omega_{3}\right)$ such that

  $$\dot{\mathbf{e}}_{a}=\boldsymbol{\omega} \times \mathbf{e}_{a}$$

  Let $\mathbf{L}=I_{1} \omega_{1}(t) \mathbf{e}_{1}+I_{2} \omega_{2}(t) \mathbf{e}_{2}+I_{3} \omega_{3}(t) \mathbf{e}_{3}$ be the angular momentum of a free rigid body expressed in the body frame. Derive the Euler equations from the conservation of angular momentum.

  Verify that the kinetic energy $E$, and the total angular momentum $L^{2}$ are conserved. Hence show that

  $$\dot{\omega}_{3}^{2}=f\left(\omega_{3}\right),$$

  where $f\left(\omega_{3}\right)$ is a quartic polynomial which should be explicitly determined in terms of $L^{2}$ and $E$.

  comment

Coding and Cryptography

• Paper 2, Section I, H

  Coding and Cryptography | Part II, 2018

  What is the channel matrix of a binary symmetric channel with error probability $p$ ?

  State the maximum likelihood decoding rule and the minimum distance decoding rule. Prove that if $p<1 / 2$, then they agree.

  Let $C$ be the repetition code $\{000,111\}$. Suppose a codeword from $C$ is sent through a binary symmetric channel with error probability $p$. Show that, if the minimum distance decoding rule is used, then the probability of error is $3 p^{2}-2 p^{3}$.

  comment

• Paper 2, Section II, H

  Coding and Cryptography | Part II, 2018

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

  Suppose $N=p q$ with $p$ and $q$ distinct odd primes and $1 \leqslant x \leqslant N$ with $x$ and $N$ coprime. Denote the order of $x$ in $\mathbb{F}_{p}^{*}$ by $\mathrm{O}_{p}(x)$. Further suppose $\Phi(N)$ divides $2^{a} b$ where $b$ is odd. If $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ prove that there exists $0 \leqslant t<a$ such that the greatest common divisor of $x^{2^{t} b}-1$ and $N$ is a nontrivial factor of $N$. Further, prove that the number of $x$ satisfying $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ is $\geqslant \Phi(N) / 2$.

  Hence, or otherwise, prove that finding the private key $d$ from the public key $(N, e)$ is essentially as difficult as factoring $N$.

  Suppose a message $m$ is sent using the $\mathrm{RSA}$ scheme with $e=43$ and $N=77$, and $c=5$ is the received text. What is $m$ ?

  An integer $m$ satisfying $1 \leqslant m \leqslant N-1$ is called a fixed point if it is encrypted to itself. Prove that if $m$ is a fixed point then so is $N-m$.

  comment

Cosmology

• Paper 2, Section I, B

  Cosmology | Part II, 2018

  (a) Consider a homogeneous and isotropic universe with a uniform distribution of galaxies. For three galaxies at positions $\mathbf{r}_{A}, \mathbf{r}_{B}, \mathbf{r}_{C}$, show that spatial homogeneity implies that their non-relativistic velocities $\mathbf{v}(\mathbf{r})$ must satisfy

  $$\mathbf{v}\left(\mathbf{r}_{B}-\mathbf{r}_{A}\right)=\mathbf{v}\left(\mathbf{r}_{B}-\mathbf{r}_{C}\right)-\mathbf{v}\left(\mathbf{r}_{A}-\mathbf{r}_{C}\right)$$

  and hence that the velocity field coordinates $v_{i}$ are linearly related to the position coordinates $r_{j}$ via

  $$v_{i}=H_{i j} r_{j}$$

  where the matrix coefficients $H_{i j}$ are independent of the position. Show why isotropy then implies Hubble's law

  $$\mathbf{v}=H \mathbf{r}, \quad \text { with } H \text { independent of } \mathbf{r}$$

  Explain how the velocity of a galaxy is determined by the scale factor $a$ and express the Hubble parameter $H_{0}$ today in terms of $a$.

  (b) Define the cosmological horizon $d_{H}(t)$. For an Einstein-de Sitter universe with $a(t) \propto t^{2 / 3}$, calculate $d_{H}\left(t_{0}\right)$ at $t=t_{0}$ today in terms of $H_{0}$. Briefly describe the horizon problem of the standard cosmology.

  comment

Differential Geometry

• Paper 2, Section II, I

  Differential Geometry | Part II, 2018

  Let $\gamma(t):[a, b] \rightarrow \mathbb{R}^{3}$ denote a regular curve.

  (a) Show that there exists a parametrization of $\gamma$ by arc length.

  (b) Under the assumption that the curvature is non-zero, define the torsion of $\gamma$. Give an example of two curves $\gamma_{1}$ and $\gamma_{2}$ in $\mathbb{R}^{3}$ whose curvature (as a function of arc length $s$ ) coincides and is non-vanishing, but for which the curves are not related by a rigid motion, i.e. such that $\gamma_{1}(s)$ is not identically $\rho_{(R, T)}\left(\gamma_{2}(s)\right)$ where $R \in S O(3), T \in \mathbb{R}^{3}$ and

  $$\rho_{(R, T)}(v):=T+R v$$

  (c) Give an example of a simple closed curve $\gamma$, other than a circle, which is preserved by a non-trivial rigid motion, i.e. which satisfies

  $$\rho_{(R, T)}(v) \in \gamma([a, b]) \text { for all } v \in \gamma([a, b])$$

  for some choice of $R \in S O(3), T \in \mathbb{R}^{3}$ with $(R, T) \neq(\mathrm{Id}, 0)$. Justify your answer.

  (d) Now show that a simple closed curve $\gamma$ which is preserved by a nontrivial smooth 1-parameter family of rigid motions is necessarily a circle, i.e. show the following:

  Let $(R, T):(-\epsilon, \epsilon) \rightarrow S O(3) \times \mathbb{R}^{3}$ be a regular curve. If for all $\tilde{t} \in(-\epsilon, \epsilon)$,

  $$\rho_{(R(\tilde{t}), T(\tilde{t}))}(v) \in \gamma([a, b]) \text { for all } v \in \gamma([a, b]) \text {, }$$

  then $\gamma([a, b])$ is a circle. [You may use the fact that the set of fixed points of a non-trivial rigid motion is either $\emptyset$ or a line $L \subset \mathbb{R}^{3}$.]

  comment

Dynamical Systems

• Paper 2, Section II, 32E

  Dynamical Systems | Part II, 2018

  Consider the system

  $$\dot{x}=y, \quad \dot{y}=x-x^{3}+\epsilon\left(1-\alpha x^{2}\right) y,$$

  where $\alpha$ and $\epsilon$ are real constants, and $0 \leqslant \epsilon \ll 1$. Find and classify the fixed points.

  Show that when $\epsilon=0$ the system is Hamiltonian and find $H$. Sketch the phase plane for this case.

  Suppose now that $0<\epsilon \ll 1$. Show that the small change in $H$ following a trajectory of the perturbed system around an orbit $H=H_{0}$ of the unperturbed system is given to leading order by an equation of the form

  $$\Delta H=\epsilon \int_{x_{1}}^{x_{2}} F\left(x ; \alpha, H_{0}\right) d x$$

  where $F$ should be found explicitly, and where $x_{1}$ and $x_{2}$ are the minimum and maximum values of $x$ on the unperturbed orbit.

  Use the energy-balance method to find the value of $\alpha$, correct to leading order in $\epsilon$, for which the system has a homoclinic orbit. [Hint: The substitution $u=1-\frac{1}{2} x^{2}$ may prove useful.]

  Over what range of $\alpha$ would you expect there to be periodic solutions that enclose only one of the fixed points?

  comment

Fluid Dynamics II

• Paper 2, Section II, C

  Fluid Dynamics II | Part II, 2018

  An initially unperturbed two-dimensional inviscid jet in $-h<y<h$ has uniform speed $U$ in the $x$ direction, while the surrounding fluid is stationary. The unperturbed velocity field $\mathbf{u}=(u, v)$ is therefore given by

  $$\begin{array}{ll} u=0 & \text { in } \quad y>h \\ u=U & \text { in } \quad-h<y<h \\ u=0 & \text { in } \quad y<-h \end{array}$$

  Consider separately disturbances in which the layer occupies $-h-\eta<y<h+\eta($ varicose disturbances) and disturbances in which the layer occupies $-h+\eta<y<h+\eta($ sinuous disturbances $)$, where $\eta(x, t)=\hat{\eta} e^{i k x+\sigma t}$, and determine the dispersion relation $\sigma(k)$ in each case.

  Find asymptotic expressions for the real part $\sigma_{R}$ of $\sigma$ in the limits $k \rightarrow 0$ and $k \rightarrow \infty$ and draw sketches of $\sigma_{R}(k)$ in each case.

  Compare the rates of growth of the two types of disturbance.

  comment

Further Complex Methods

• Paper 2, Section $I$, $7 \mathrm{~B}$

  Further Complex Methods | Part II, 2018

  Show that

  $$\int_{-\infty}^{\infty} \frac{\cos n x-\cos m x}{x^{2}} d x=\pi(m-n),$$

  in the sense of Cauchy principal value, where $n$ and $m$ are positive integers. [State clearly any standard results involving contour integrals that you use.]

  comment

• Paper 2, Section II, B

  Further Complex Methods | Part II, 2018

  Consider a multi-valued function $w(z)$.

  (a) Explain what is meant by a branch point and a branch cut.

  (b) Consider $z=e^{w}$.

  (i) By writing $z=r e^{i \theta}$, where $0 \leqslant \theta<2 \pi$, and $w=u+i v$, deduce the expression for $w(z)$ in terms of $r$ and $\theta$. Hence, show that $w$ is infinitely valued and state its principal value.

  (ii) Show that $z=0$ and $z=\infty$ are the branch points of $w$. Deduce that the line $\operatorname{Im} z=0, \operatorname{Re} z>0$ is a possible choice of branch cut.

  (iii) Use the Cauchy-Riemann conditions to show that $w$ is analytic in the cut plane. Show that $\frac{d w}{d z}=\frac{1}{z}$.

  comment

Galois Theory

• Paper 2, Section II, I

  Galois Theory | Part II, 2018

  Let $K$ be a field and let $f(t)$ be a monic polynomial with coefficients in $K$. What is meant by a splitting field $L$ for $f(t)$ over $K$ ? Show that such a splitting field exists and is unique up to isomorphism.

  Now suppose that $K$ is a finite field. Prove that $L$ is a Galois extension of $K$ with cyclic Galois group. Prove also that the degree of $L$ over $K$ is equal to the least common multiple of the degrees of the irreducible factors of $f(t)$ over $K$.

  Now suppose $K$ is the field with two elements, and let

  $$\mathcal{P}_{n}=\{f(t) \in K[t] \mid f \text { has degree } n \text { and is irreducible over } K\}$$

  How many elements does the set $\mathcal{P}_{9}$ have?

  comment

General Relativity

• Paper 2, Section II, E

  General Relativity | Part II, 2018

  The Friedmann equations and the conservation of energy-momentum for a spatially homogeneous and isotropic universe are given by:

  $$3 \frac{\dot{a}^{2}+k}{a^{2}}-\Lambda=8 \pi \rho, \quad \frac{2 a \ddot{a}+\dot{a}^{2}+k}{a^{2}}-\Lambda=-8 \pi P, \quad \dot{\rho}=-3 \frac{\dot{a}}{a}(P+\rho),$$

  where $a$ is the scale factor, $\rho$ the energy density, $P$ the pressure, $\Lambda$ the cosmological constant and $k=+1,0,-1$.

  (a) Show that for an equation of state $P=w \rho, w=$ constant, the energy density obeys $\rho=\frac{3 \mu}{8 \pi} a^{-3(1+w)}$, for some constant $\mu$.

  (b) Consider the case of a matter dominated universe, $w=0$, with $\Lambda=0$. Write the equation of motion for the scale factor $a$ in the form of an effective potential equation,

  $$\dot{a}^{2}+V(a)=C$$

  where you should determine the constant $C$ and the potential $V(a)$. Sketch the potential $V(a)$ together with the possible values of $C$ and qualitatively discuss the long-term dynamics of an initially small and expanding universe for the cases $k=+1,0,-1$.

  (c) Repeat the analysis of part (b), again assuming $w=0$, for the cases:

  (i) $\Lambda>0, k=-1$,

  (ii) $\Lambda<0, k=0$,

  (iii) $\Lambda>0, k=1$.

  Discuss all qualitatively different possibilities for the dynamics of the universe in each case.

  comment

Graph Theory

• Paper 2, Section II, I

  Graph Theory | Part II, 2018

  Let $G$ be a graph and $A, B \subset V(G)$. Show that if every $A B$-separator in $G$ has order at least $k$ then there exist $k$ vertex-disjoint $A B$-paths in $G$.

  Let $k \geqslant 3$ and assume that $G$ is $k$-connected. Show that $G$ must contain a cycle of length at least $k$.

  Assume further that $|G| \geqslant 2 k$. Must $G$ contain a cycle of length at least $2 k ?$ Justify your answer.

  What is the largest integer $n$ such that any 3-connected graph $G$ with $|G| \geqslant n$ must contain a cycle of length at least $n$ ?

  [No form of Menger's theorem or of the max-flow-min-cut theorem may be assumed without proof.]

  comment

Integrable Systems

• Paper 2, Section II, A

  Integrable Systems | Part II, 2018

  (a) Let $\mathcal{L}, \mathcal{A}$ be two families of linear operators, depending on a parameter $t$, which act on a Hilbert space $H$ with inner product $(,$, . Suppose further that for each $t, \mathcal{L}$ is self-adjoint and that $\mathcal{A}$ is anti-self-adjoint. State $L a x$ 's equation for the pair $\mathcal{L}, \mathcal{A}$, and show that if it holds then the eigenvalues of $\mathcal{L}$ are independent of $t$.

  (b) For $\psi, \phi: \mathbb{R} \rightarrow \mathbb{C}$, define the inner product:

  $$(\psi, \phi):=\int_{-\infty}^{\infty} \overline{\psi(x)} \phi(x) d x$$

  Let $L, A$ be the operators:

  $$\begin{gathered} L \psi:=i \frac{d^{3} \psi}{d x^{3}}-i\left(q \frac{d \psi}{d x}+\frac{d}{d x}(q \psi)\right)+p \psi \\ A \psi:=3 i \frac{d^{2} \psi}{d x^{2}}-4 i q \psi \end{gathered}$$

  where $p=p(x, t), q=q(x, t)$ are smooth, real-valued functions. You may assume that the normalised eigenfunctions of $L$ are smooth functions of $x, t$, which decay rapidly as $|x| \rightarrow \infty$ for all $t$.

  (i) Show that if $\psi, \phi$ are smooth and rapidly decaying towards infinity then:

  $$(L \psi, \phi)=(\psi, L \phi), \quad(A \psi, \phi)=-(\psi, A \phi)$$

  Deduce that the eigenvalues of $L$ are real.

  (ii) Show that if Lax's equation holds for $L, A$, then $q$ must satisfy the Boussinesq equation:

  $$q_{t t}=a q_{x x x x}+b\left(q^{2}\right)_{x x}$$

  where $a, b$ are constants whose values you should determine. [You may assume without proof that the identity:

  $$L A \psi=A L \psi-3 i\left(p_{x} \frac{d \psi}{d x}+\frac{d}{d x}\left(p_{x} \psi\right)\right)+\left[q_{x x x}-4\left(q^{2}\right)_{x}\right] \psi$$

  holds for smooth, rapidly decaying $\psi .]$

  comment

Linear Analysis

• Paper 2, Section II, F

  Linear Analysis | Part II, 2018

  Let $X, Y$ be Banach spaces and let $\mathcal{B}(X, Y)$ denote the space of bounded linear operators $T: X \rightarrow Y$.

  (a) Define what it means for a bounded linear operator $T: X \rightarrow Y$ to be compact. Let $T_{i}: X \rightarrow Y$ be linear operators with finite rank, i.e., $T_{i}(X)$ is finite-dimensional. Assume that the sequence $T_{i}$ converges to $T$ in $\mathcal{B}(X, Y)$. Show that $T$ is compact.

  (b) Let $T: X \rightarrow Y$ be compact. Show that the dual map $T^{*}: Y^{*} \rightarrow X^{*}$ is compact. [Hint: You may use the Arzelà-Ascoli theorem.]

  (c) Let $X$ be a Hilbert space and let $T: X \rightarrow X$ be a compact operator. Let $\left(\lambda_{j}\right)$ be an infinite sequence of eigenvalues of $T$ with eigenvectors $x_{j}$. Assume that the eigenvectors are orthogonal to each other. Show that $\lambda_{j} \rightarrow 0$.

  comment

Logic and Set Theory

• Paper 2, Section II, G

  Logic and Set Theory | Part II, 2018

  State and prove the Knaster-Tarski Fixed-Point Theorem. Deduce the SchröderBernstein Theorem.

  Show that the poset $P$ of all countable subsets of $\mathbb{R}$ (ordered by inclusion) is not complete.

  Find an order-preserving function $f: P \rightarrow P$ that does not have a fixed point. [Hint: Start by well-ordering the reals.]

  comment

Mathematical Biology

• Paper 2, Section I, C

  Mathematical Biology | Part II, 2018

  Consider a model of an epidemic consisting of populations of susceptible, $S(t)$, infected, $I(t)$, and recovered, $R(t)$, individuals that obey the following differential equations

  $$\begin{aligned} \frac{d S}{d t} &=a R-b S I \\ \frac{d I}{d t} &=b S I-c I \\ \frac{d R}{d t} &=c I-a R \end{aligned}$$

  where $a, b$ and $c$ are constant. Show that the sum of susceptible, infected and recovered individuals is a constant $N$. Find the fixed points of the dynamics and deduce the condition for an endemic state with a positive number of infected individuals. Expressing $R$ in terms of $S, I$ and $N$, reduce the system of equations to two coupled differential equations and, hence, deduce the conditions for the fixed point to be a node or a focus. How do small perturbations of the populations relax to the steady state in each case?

  comment

Number Fields

• Paper 2, Section II, 20G

  Number Fields | Part II, 2018

  Let $p \equiv 1 \bmod 4$ be a prime, and let $\omega=e^{2 \pi i / p}$. Let $L=\mathbb{Q}(\omega)$.

  (a) Show that $[L: \mathbb{Q}]=p-1$.

  (b) Calculate $\operatorname{disc}\left(1, \omega, \omega^{2}, \ldots, \omega^{p-2}\right)$. Deduce that $\sqrt{p} \in L$.

  (c) Now suppose $p=5$. Prove that $\mathcal{O}_{L}^{\times}=\left\{\pm \omega^{a}\left(\frac{1}{2}+\frac{\sqrt{5}}{2}\right)^{b} \mid a, b \in \mathbb{Z}\right\}$. [You may use any general result without proof, provided that you state it precisely.]

  comment

Number Theory

• Paper 2, Section I, G

  Number Theory | Part II, 2018

  Define the Legendre symbol, and state Gauss's lemma. Show that if $p$ is an odd prime, then

  $$\left(\frac{2}{p}\right)=(-1)^{\left(p^{2}-1\right) / 8}$$

  Use the law of quadratic reciprocity to compute $\left(\frac{105}{149}\right)$.

  comment

Numerical Analysis

• Paper 2, Section II, E

  Numerical Analysis | Part II, 2018

  The Poisson equation $\frac{d^{2} u}{d x^{2}}=f$ in the unit interval $[0,1]$, with $u(0)=u(1)=0$, is discretised with the formula

  $$u_{i-1}-2 u_{i}+u_{i+1}=h^{2} f_{i}, \quad 1 \leqslant i \leqslant n,$$

  where $u_{0}=u_{n+1}=0, h=(n+1)^{-1}$, the grid points are at $x=i h$ and $u_{i} \approx u(i h)$.

  (a) Write the above system of equations in the vector form $A \boldsymbol{u}=\boldsymbol{b}$ and describe the relaxed Jacobi method with relaxation parameter $\omega$ for solving this linear system.

  (b) For $\boldsymbol{x}^{*}$ and $\boldsymbol{x}^{(\nu)}$ being the exact and the iterated solution, respectively, let $\boldsymbol{e}^{(\nu)}:=\boldsymbol{x}^{(\nu)}-\boldsymbol{x}^{*}$ be the error and $H_{\omega}$ be the iteration matrix, so that

  $$\boldsymbol{e}^{(\nu+1)}=H_{\omega} \boldsymbol{e}^{(\nu)}$$

  Express $H_{\omega}$ in terms of the matrix $A$ and the relaxation parameter $\omega$. Using the fact that for any $n \times n$ Toeplitz symmetric tridiagonal matrix, the eigenvectors $\boldsymbol{v}_{k}(k=1, \ldots, n)$ have the form:

  $$\boldsymbol{v}_{k}=(\sin i k x)_{i=1}^{n}, \quad x=\frac{\pi}{n+1}$$

  find the eigenvalues $\lambda_{k}(A)$ of $A$. Hence deduce the eigenvalues $\lambda_{k}(\omega)$ of $H_{\omega}$.

  (c) For $A$ as above, let

  $$\boldsymbol{e}^{(\nu)}=\sum_{k=1}^{n} a_{k}^{(\nu)} \boldsymbol{v}_{k}$$

  be the expansion of the error with respect to the eigenvectors $\left(\boldsymbol{v}_{k}\right)$ of $H_{\omega}$.

  Find the range of the parameter $\omega$ which provides convergence of the method for any $n$, and prove that, for any such $\omega$, the rate of convergence $e^{(\nu)} \rightarrow 0$ is not faster than $\left(1-c / n^{2}\right)^{\nu}$ when $n$ is large.

  (d) Show that, for an appropriate range of $\omega$, the high frequency components $a_{k}^{(\nu)}$ $\left(\frac{n+1}{2} \leqslant k \leqslant n\right)$ of the error $e^{(\nu)}$ tend to zero much faster than the rate obtained in part (c). Determine the optimal parameter $\omega_{*}$ which provides the largest supression of the high frequency components per iteration, and find the corresponding attenuation factor $\mu_{*}$ assuming $n$ is large. That is, find the least $\mu_{\omega}$ such that $\left|a_{k}^{(\nu+1)}\right| \leqslant \mu_{\omega}\left|a_{k}^{(\nu)}\right|$ for $\frac{n+1}{2} \leqslant k \leqslant n$.

  comment

Optimisation and Control

• Paper 2, Section II, $30 K$

  Optimisation and Control | Part II, 2018

  (a) A ball may be in one of $n$ boxes. A search of the $i^{\text {th }}$box costs $c_{i}>0$ and finds the ball with probability $\alpha_{i}>0$ if the ball is in that box. We are given initial probabilities $\left(P_{i}^{1}, i=1,2, \ldots, n\right)$ that the ball is in the $i^{\text {th }}$box.

  Show that the policy which at time $t=1,2, \ldots$ searches the box with the maximal value of $\alpha_{i} P_{i}^{t} / c_{i}$ minimises the expected searching cost until the ball is found, where $P_{i}^{t}$ is the probability (given everything that has occurred up to time $t$ ) that the ball is in box $i$.

  (b) Next suppose that a reward $R_{i}>0$ is earned if the ball is found in the $i^{\text {th }}$box. Suppose also that we may decide to stop at any time. Develop the dynamic programming equation for the value function starting from the probability distribution $\left(P_{i}^{t}, i=1,2, \ldots, n\right)$.

  Show that if $\sum_{i} c_{i} /\left(\alpha_{i} R_{i}\right)<1$ then it is never optimal to stop searching until the ball is found. In this case, is the policy defined in part (a) optimal?

  comment

Principles of Quantum Mechanics

• Paper 2, Section II, D

  Principles of Quantum Mechanics | Part II, 2018

  Explain what is meant by the intrinsic parity of a particle.

  In each of the decay processes below, parity is conserved.

  A deuteron $\left(d^{+}\right)$has intrinsic parity $\eta_{d}=+1$ and spin $s=1$. A negatively charged pion $\left(\pi^{-}\right)$has spin $s=0$. The ground state of a hydrogenic 'atom' formed from a deuteron and a pion decays to two identical neutrons $(n)$, each of spin $s=\frac{1}{2}$ and parity $\eta_{n}=+1$. Deduce the intrinsic parity of the pion.

  The $\Delta^{-}$particle has spin $s=\frac{3}{2}$ and decays as

  $$\Delta^{-} \rightarrow \pi^{-}+n .$$

  What are the allowed values of the orbital angular momentum? In the centre of mass frame, the vector $\mathbf{r}_{\pi}-\mathbf{r}_{n}$ joining the pion to the neutron makes an angle $\theta$ to the $\hat{\mathbf{z}}$-axis. The final state is an eigenstate of $J_{z}$ and the spatial probability distribution is proportional to $\cos ^{2} \theta$. Deduce the intrinsic parity of the $\Delta^{-}$.

  [Hint: You may use the fact that the first three Legendre polynomials are given by

  $$\left.P_{0}(x)=1, \quad P_{1}(x)=x, \quad P_{2}(x)=\frac{1}{2}\left(3 x^{2}-1\right) . \quad\right]$$

  comment

Principles of Statistics

• Paper 2, Section II, $28 K$

  Principles of Statistics | Part II, 2018

  We consider the model $\left\{\mathcal{N}\left(\theta, I_{p}\right), \theta \in \mathbb{R}^{p}\right\}$ of a Gaussian distribution in dimension $p \geqslant 3$, with unknown mean $\theta$ and known identity covariance matrix $I_{p}$. We estimate $\theta$ based on one observation $X \sim \mathcal{N}\left(\theta, I_{p}\right)$, under the loss function

  $$\ell(\theta, \delta)=\|\theta-\delta\|_{2}^{2}$$

  (a) Define the risk of an estimator $\hat{\theta}$. Compute the maximum likelihood estimator $\hat{\theta}_{M L E}$ of $\theta$ and its risk for any $\theta \in \mathbb{R}^{p}$.

  (b) Define what an admissible estimator is. Is $\hat{\theta}_{M L E}$ admissible?

  (c) For any $c>0$, let $\pi_{c}(\theta)$ be the prior $\mathcal{N}\left(0, c^{2} I_{p}\right)$. Find a Bayes optimal estimator $\hat{\theta}_{c}$ under this prior with the quadratic loss, and compute its Bayes risk.

  (d) Show that $\hat{\theta}_{M L E}$ is minimax.

  [You may use results from the course provided that you state them clearly.]

  comment

Probability and Measure

• Paper 2, Section II, J

  Probability and Measure | Part II, 2018

  Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space. Let $\left(X_{n}\right)_{n \geqslant 1}$ be a sequence of random variables with $\mathbb{E}\left(\left|X_{n}\right|^{2}\right) \leqslant 1$ for all $n \geqslant 1$.

  (a) Suppose $Z$ is another random variable such that $\mathbb{E}\left(|Z|^{2}\right)<\infty$. Why is $Z X_{n}$ integrable for each $n$ ?

  (b) Assume $\mathbb{E}\left(Z X_{n}\right) \underset{n \rightarrow \infty}{\longrightarrow} 0$ for every random variable $Z$ on $(\Omega, \mathcal{F}, \mathbb{P})$ such that $\mathbb{E}\left(|Z|^{2}\right)<\infty$. Show that there is a subsequence $Y_{k}:=X_{n_{k}}, k \geqslant 1$, such that

  $$\frac{1}{N} \sum_{k=1}^{N} Y_{k} \underset{N \rightarrow \infty}{\longrightarrow} 0 \text { in } \mathbb{L}^{2}$$

  (c) Assume that $X_{n} \rightarrow X$ in probability. Show that $X \in \mathbb{L}^{2}$. Show that $X_{n} \rightarrow X$ in $\mathbb{L}^{1}$. Must it converge also in $\mathbb{L}^{2} ?$ Justify your answer.

  (d) Assume that the $\left(X_{n}\right)_{n \geqslant 1}$ are independent. Give a necessary and sufficient condition on the sequence $\left(\mathbb{E}\left(X_{n}\right)_{n \geqslant 1}\right)$ for the sequence

  $$Y_{N}=\frac{1}{N} \sum_{k=1}^{N} X_{k}$$

  to converge in $\mathbb{L}^{2}$.

  comment

Quantum Information and Computation

• Paper 2, Section I, $10 D$

  Quantum Information and Computation | Part II, 2018

  (a) The classical controlled- $N O T$ operation applied to the 2-bit string $b 0$ (for $b=0$ or 1 ) achieves the cloning of $b$, i.e. the result is $b b$. Let $C X$ denote the quantum controlled$X$ (or controlled-NOT) operation on two qubits. For which qubit states $|\psi\rangle=a|0\rangle+b|1\rangle$ will the application of $C X$ to $|\psi\rangle|0\rangle$ (with the first qubit being the control qubit) achieve the cloning of $|\psi\rangle$ ? Justify your answer.

  (b) Let $\left|\alpha_{0}\right\rangle$ and $\left|\alpha_{1}\right\rangle$ be two distinct non-orthogonal quantum states. State and prove the quantum no-cloning theorem for unitary processes.

  comment

• Paper 2, Section II, D

  Quantum Information and Computation | Part II, 2018

  (a) Suppose that Alice and Bob are distantly separated in space and each has one qubit of the 2-qubit state $\left|\phi^{+}\right\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$. They also have the ability to perform local unitary quantum operations and local computational basis measurements, and to communicate only classically. Alice has a 1-qubit state $|\alpha\rangle$ (whose identity is unknown to her) which she wants to communicate to Bob. Show how this can be achieved using only the operational resources, listed above, that they have available.

  Suppose now that a third party, called Charlie, joins Alice and Bob. They are all mutually distantly separated in space and each holds one qubit of the 3-qubit state

  $$|\gamma\rangle=\frac{1}{\sqrt{2}}(|000\rangle+|111\rangle) .$$

  As previously with Alice and Bob, they are able to communicate with each other only classically, e.g. by telephone, and they can each also perform only local unitary operations and local computational basis measurements. Alice and Bob phone Charlie to say that they want to do some quantum teleportation and they need a shared $\left|\phi^{+}\right\rangle$state (as defined above). Show how Charlie can grant them their wish (with certainty), given their joint possession of $|\gamma\rangle$ and using only their allowed operational resources. [Hint: It may be useful to consider application of an appropriate Hadamard gate action.]

  (b) State the quantum no-signalling principle for a bipartite state $|\psi\rangle_{A B}$ of the composite system $A B$.

  Suppose we are given an unknown one of the two states

  $$\begin{aligned} &\left|\phi^{+}\right\rangle_{A B}=\frac{1}{\sqrt{2}}\left(|00\rangle_{A B}+|11\rangle_{A B}\right) \\ &\left|\phi^{-}\right\rangle_{A B}=\frac{1}{\sqrt{2}}\left(|00\rangle_{A B}-|11\rangle_{A B}\right) \end{aligned}$$

  and we wish to identify which state we have. Show that the minimum error probability for this state discrimination task is zero.

  Suppose now that we have access only to qubit $B$ of the received state. Show that we can now do no better in the state discrimination task than just making a random guess as to which state we have.

  comment

Representation Theory

• Paper 2, Section II, I

  Representation Theory | Part II, 2018

  (a) Suppose $H$ is a subgroup of a finite group $G, \chi$ is an irreducible character of $G$ and $\varphi_{1}, \ldots, \varphi_{r}$ are the irreducible characters of $H$. Show that in the restriction $\chi \downarrow_{H}=a_{1} \varphi_{1}+\cdots+a_{r} \varphi_{r}$, the multiplicities $a_{1}, \ldots, a_{r}$ satisfy

  $$\sum_{i=1}^{r} a_{i}^{2} \leqslant|G: H|$$

  Determine necessary and sufficient conditions under which the inequality in ( $\uparrow$ ) is actually an equality.

  (b) Henceforth suppose that $H$ is a (normal) subgroup of index 2 in $G$, and that $\chi$ is an irreducible character of $G$.

  Lift the non-trivial linear character of $G / H$ to obtain a linear character of $G$ which satisfies

  $$\lambda(g)= \begin{cases}1 & \text { if } g \in H \\ -1 & \text { if } g \notin H\end{cases}$$

  (i) Show that the following are equivalent:

  (1) $\chi \downarrow_{H}$ is irreducible;

  (2) $\chi(g) \neq 0$ for some $g \in G$ with $g \notin H$;

  (3) the characters $\chi$ and $\chi \lambda$ of $G$ are not equal.

  (ii) Suppose now that $\chi \downarrow_{H}$ is irreducible. Show that if $\psi$ is an irreducible character of $G$ which satisfies

  $$\psi \downarrow_{H}=\chi \downarrow_{H}$$

  then either $\psi=\chi$ or $\psi=\chi \lambda .$

  (iii) Suppose that $\chi \downarrow_{H}$ is the sum of two irreducible characters of $H$, say $\chi \downarrow_{H}=\psi_{1}+\psi_{2}$. If $\phi$ is an irreducible character of $G$ such that $\phi \downarrow_{H}$ has $\psi_{1}$ or $\psi_{2}$ as a constituent, show that $\phi=\chi$.

  (c) Suppose that $G$ is a finite group with a subgroup $K$ of index 3 , and let $\chi$ be an irreducible character of $G$. Prove that

  $$\left\langle\chi \downarrow_{K}, \chi \downarrow_{K}\right\rangle_{K}=1,2 \text { or } 3$$

  Give examples to show that each possibility can occur, giving brief justification in each case.

  comment

Riemann Surfaces

• Paper 2, Section II, F

  Riemann Surfaces | Part II, 2018

  State the uniformisation theorem. List without proof the Riemann surfaces which are uniformised by $\mathbb{C}_{\infty}$ and those uniformised by $\mathbb{C}$.

  Let $U$ be a domain in $\mathbb{C}$ whose complement consists of more than one point. Deduce that $U$ is uniformised by the open unit disk.

  Let $R$ be a compact Riemann surface of genus $g$ and $P_{1}, \ldots, P_{n}$ be distinct points of $R$. Show that $R \backslash\left\{P_{1}, \ldots, P_{n}\right\}$ is uniformised by the open unit disk if and only if $2 g-2+n>0$, and by $\mathbb{C}$ if and only if $2 g-2+n=0$ or $-1$.

  Let $\Lambda$ be a lattice and $X=\mathbb{C} / \Lambda$ a complex torus. Show that an analytic map $f: \mathbb{C} \rightarrow X$ is either surjective or constant.

  Give with proof an example of a pair of Riemann surfaces which are homeomorphic but not conformally equivalent.

  comment

Statistical Modelling

• Paper 2, Section I, $\mathbf{5 J}$

  Statistical Modelling | Part II, 2018

  Consider a linear model $Y=X \beta+\sigma^{2} \varepsilon$ with $\varepsilon \sim N(0, I)$, where the design matrix $X$ is $n$ by $p$. Provide an expression for the $F$-statistic used to test the hypothesis $\beta_{p_{0}+1}=\beta_{p_{0}+2}=\cdots=\beta_{p}=0$ for $p_{0}<p$. Show that it is a monotone function of a log-likelihood ratio statistic.

  comment

Statistical Physics

• Paper 2, Section II, A

  Statistical Physics | Part II, 2018

  (a) Starting from the canonical ensemble, derive the Maxwell-Boltzmann distribution for the velocities of particles in a classical gas of atoms of mass $m$. Derive also the distribution of speeds $v$ of the particles. Calculate the most probable speed.

  (b) A certain atom emits photons of frequency $\omega_{0}$. A gas of these atoms is contained in a box. A small hole is cut in a wall of the box so that photons can escape in the positive $x$-direction where they are received by a detector. The frequency of the photons received is Doppler shifted according to the formula

  $$\omega=\omega_{0}\left(1+\frac{v_{x}}{c}\right)$$

  where $v_{x}$ is the $x$-component of the velocity of the atom that emits the photon and $c$ is the speed of light. Let $T$ be the temperature of the gas.

  (i) Calculate the mean value $\langle\omega\rangle$ of $\omega$.

  (ii) Calculate the standard deviation $\sqrt{\left\langle(\omega-\langle\omega\rangle)^{2}\right\rangle}$.

  (iii) Show that the relative number of photons received with frequency between $\omega$ and $\omega+d \omega$ is $I(\omega) d \omega$ where

  $$I(\omega) \propto \exp \left(-a\left(\omega-\omega_{0}\right)^{2}\right)$$

  for some coefficient $a$ to be determined. Hence explain how observations of the radiation emitted by the gas can be used to measure its temperature.

  comment

Stochastic Financial Models

• Paper 2, Section II, K

  Stochastic Financial Models | Part II, 2018

  Consider the Black-Scholes model, i.e. a market model with one risky asset with price $S_{t}$ at time $t$ given by

  $$S_{t}=S_{0} \exp \left(\sigma B_{t}+\mu t\right),$$

  where $\left(B_{t}\right)_{t \geqslant 0}$ denotes a Brownian motion on $(\Omega, \mathcal{F}, \mathbb{P}), \mu>0$ the constant growth rate, $\sigma>0$ the constant volatility and $S_{0}>0$ the initial price of the asset. Assume that the riskless rate of interest is $r \geqslant 0$.

  (a) Consider a European option $C=f\left(S_{T}\right)$ with expiry $T>0$ for any bounded, continuous function $f: \mathbb{R} \rightarrow \mathbb{R}$. Use the Cameron-Martin theorem to characterize the equivalent martingale measure and deduce the following formula for the price $\pi_{C}$ of $C$ at time 0 :

  $$\pi_{C}=e^{-r T} \int_{-\infty}^{\infty} f\left(S_{0} \exp \left(\sigma \sqrt{T} y+\left(r-\frac{1}{2} \sigma^{2}\right) T\right)\right) \frac{1}{\sqrt{2 \pi}} e^{-y^{2} / 2} d y$$

  (b) Find the price at time 0 of a European option with maturity $T>0$ and payoff $C=\left(S_{T}\right)^{\gamma}$ for some $\gamma>1$. What is the value of the option at any time $t \in[0, T] ?$ Determine a hedging strategy (you only need to specify how many units of the risky asset are held at any time $t$ ).

  comment

Topics in Analysis

• Paper 2, Section I, $2 F$

  Topics in Analysis | Part II, 2018

  For $\mathbf{x} \in \mathbb{R}^{n}$ we write $\mathbf{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$. Define

  $$P:=\left\{\mathbf{x} \in \mathbb{R}^{n}: x_{j} \geqslant 0 \text { for } 1 \leqslant j \leqslant n\right\} .$$

  (a) Suppose that $L$ is a convex subset of $P$, that $(1,1, \ldots, 1) \in L$ and that $\prod_{j=1}^{n} x_{j} \leqslant 1$ for all $\mathbf{x} \in L$. Show that $\sum_{j=1}^{n} x_{j} \leqslant n$ for all $\mathbf{x} \in L$.

  (b) Suppose that $K$ is a non-empty closed bounded convex subset of $P$. Show that there is a $\mathbf{u} \in K$ such that $\prod_{j=1}^{n} x_{j} \leqslant \prod_{j=1}^{n} u_{j}$ for all $\mathbf{x} \in K$. If $u_{j} \neq 0$ for each $j$ with $1 \leqslant j \leqslant n$, show that

  $$\sum_{j=1}^{n} \frac{x_{j}}{u_{j}} \leqslant n$$

  for all $\mathbf{x} \in K$, and that $\mathbf{u}$ is unique.

  comment

• Paper 2, Section II, F

  Topics in Analysis | Part II, 2018

  (a) Give Bernstein's probabilistic proof of Weierstrass's theorem.

  (b) Are the following statements true or false? Justify your answer in each case.

  (i) If $f: \mathbb{R} \rightarrow \mathbb{R}$ is continuous, then there exists a sequence of polynomials $P_{n}$ converging pointwise to $f$ on $\mathbb{R}$.

  (ii) If $f: \mathbb{R} \rightarrow \mathbb{R}$ is continuous, then there exists a sequence of polynomials $P_{n}$ converging uniformly to $f$ on $\mathbb{R}$.

  (iii) If $f:(0,1] \rightarrow \mathbb{R}$ is continuous and bounded, then there exists a sequence of polynomials $P_{n}$ converging uniformly to $f$ on $(0,1]$.

  (iv) If $f:[0,1] \rightarrow \mathbb{R}$ is continuous and $x_{1}, x_{2}, \ldots, x_{m}$ are distinct points in $[0,1]$, then there exists a sequence of polynomials $P_{n}$ with $P_{n}\left(x_{j}\right)=f\left(x_{j}\right)$, for $j=1, \ldots, m$, converging uniformly to $f$ on $[0,1]$.

  (v) If $f:[0,1] \rightarrow \mathbb{R}$ is $m$ times continuously differentiable, then there exists a sequence of polynomials $P_{n}$ such that $P_{n}^{(r)} \rightarrow f^{(r)}$ uniformly on $[0,1]$ for each $r=0, \ldots, m$.

  comment

Waves

• Paper 2, Section II, C

  Waves | Part II, 2018

  A perfect gas occupies the region $x>0$ of a tube that lies parallel to the $x$-axis. The gas is initially at rest, with density $\rho_{1}$, pressure $p_{1}$, speed of sound $c_{1}$ and specific heat ratio $\gamma$. For times $t>0$ a piston, initially at $x=0$, is pushed into the gas at a constant speed $V$. A shock wave propagates at constant speed $U$ into the undisturbed gas ahead of the piston. Show that the excess pressure in the gas next to the piston, $p_{2}-p_{1} \equiv \beta p_{1}$, is given implicitly by the expression

  $$V^{2}=\frac{2 \beta^{2}}{2 \gamma+(\gamma+1) \beta} \frac{p_{1}}{\rho_{1}}$$

  Show also that

  $$\frac{U^{2}}{c_{1}^{2}}=1+\frac{\gamma+1}{2 \gamma} \beta$$

  and interpret this result.

  [Hint: You may assume for a perfect gas that the speed of sound is given by

  $$c^{2}=\frac{\gamma p}{\rho}$$

  and that the internal energy per unit mass is given by

  $$e=\frac{1}{\gamma-1} \frac{p}{\rho}$$

  comment