• # Paper 2, Section II, F

(a) Let $A$ be a commutative algebra over a field $k$, and $p: A \rightarrow k$ a $k$-linear homomorphism. Define $\operatorname{Der}(A, p)$, the derivations of $A$ centered in $p$, and define the tangent space $T_{p} A$ in terms of this.

Show directly from your definition that if $f \in A$ is not a zero divisor and $p(f) \neq 0$, then the natural map $T_{p} A\left[\frac{1}{f}\right] \rightarrow T_{p} A$ is an isomorphism.

(b) Suppose $k$ is an algebraically closed field and $\lambda_{i} \in k$ for $1 \leqslant i \leqslant r$. Let

$X=\left\{(x, y) \in \mathbb{A}^{2} \mid x \neq 0, y \neq 0, y^{2}=\left(x-\lambda_{1}\right) \cdots\left(x-\lambda_{r}\right)\right\}$

Find a surjective map $X \rightarrow \mathbb{A}^{1}$. Justify your answer.

comment

• # Paper 2, Section II, F

Let $T=S^{1} \times S^{1}, U=S^{1} \times D^{2}$ and $V=D^{2} \times S^{1}$. Let $i: T \rightarrow U, j: T \rightarrow V$ be the natural inclusion maps. Consider the space $S:=U \cup_{T} V$; that is,

$S:=(U \sqcup V) / \sim$

where $\sim$ is the smallest equivalence relation such that $i(x) \sim j(x)$ for all $x \in T$.

(a) Prove that $S$ is homeomorphic to the 3 -sphere $S^{3}$.

[Hint: It may help to think of $S^{3}$ as contained in $\mathbb{C}^{2}$.]

(b) Identify $T$ as a quotient of the square $I \times I$ in the usual way. Let $K$ be the circle in $T$ given by the equation $y=\frac{2}{3} x \bmod 1 . K$ is illustrated in the figure below.

Compute a presentation for $\pi_{1}(S-K)$, where $S-K$ is the complement of $K$ in $S$, and deduce that $\pi_{1}(S-K)$ is non-abelian.

comment

• # Paper 2, Section II, B

Give an account of the variational principle for establishing an upper bound on the ground state energy of a Hamiltonian $H$.

A particle of mass $m$ moves in one dimension and experiences the potential $V=A|x|^{n}$ with $n$ an integer. Use a variational argument to prove the virial theorem,

$2\langle T\rangle_{0}=n\langle V\rangle_{0}$

where $\langle\cdot\rangle_{0}$ denotes the expectation value in the true ground state. Deduce that there is no normalisable ground state for $n \leqslant-3$.

For the case $n=1$, use the ansatz $\psi(x) \propto e^{-\alpha^{2} x^{2}}$ to find an estimate for the energy of the ground state.

comment

• # Paper 2, Section II, K

Let $X=\left(X_{t}: t \geqslant 0\right)$ be a Markov chain on the non-negative integers with generator $G=\left(g_{i, j}\right)$ given by

\begin{aligned} g_{i, i+1} &=\lambda_{i}, & & i \geqslant 0 \\ g_{i, 0} &=\lambda_{i} \rho_{i}, & & i>0 \\ g_{i, j} &=0, & & j \neq 0, i, i+1 \end{aligned}

for a given collection of positive numbers $\lambda_{i}, \rho_{i}$.

(a) State the transition matrix of the jump chain $Y$ of $X$.

(b) Why is $X$ not reversible?

(c) Prove that $X$ is transient if and only if $\prod_{i}\left(1+\rho_{i}\right)<\infty$.

(d) Assume that $\prod_{i}\left(1+\rho_{i}\right)<\infty$. Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for $X$ to be explosive.

(e) Derive a necessary and sufficient condition on the parameters $\lambda_{i}, \rho_{i}$ for the existence of an invariant measure for $X$.

[You may use any general results from the course concerning Markov chains and pure birth processes so long as they are clearly stated.]

comment

• # Paper 2, Section II, A

(a) Define formally what it means for a real valued function $f(x)$ to have an asymptotic expansion about $x_{0}$, given by

$f(x) \sim \sum_{n=0}^{\infty} f_{n}\left(x-x_{0}\right)^{n} \text { as } x \rightarrow x_{0}$

Use this definition to prove the following properties.

(i) If both $f(x)$ and $g(x)$ have asymptotic expansions about $x_{0}$, then $h(x)=f(x)+g(x)$ also has an asymptotic expansion about $x_{0} .$

(ii) If $f(x)$ has an asymptotic expansion about $x_{0}$ and is integrable, then

$\int_{x_{0}}^{x} f(\xi) d \xi \sim \sum_{n=0}^{\infty} \frac{f_{n}}{n+1}\left(x-x_{0}\right)^{n+1} \text { as } x \rightarrow x_{0}$

(b) Obtain, with justification, the first three terms in the asymptotic expansion as $x \rightarrow \infty$ of the complementary error function, $\operatorname{erfc}(x)$, defined as

$\operatorname{erfc}(x):=\frac{1}{\sqrt{2 \pi}} \int_{x}^{\infty} e^{-t^{2}} d t$

comment

• # Paper 2, Section I, H

(a) Define a recursive set and a recursively enumerable (r.e.) set. Prove that $E \subseteq \mathbb{N}_{0}$ is recursive if and only if both $E$ and $\mathbb{N}_{0} \backslash E$ are r.e. sets.

(b) Let $E=\left\{f_{n, k}\left(m_{1}, \ldots, m_{k}\right) \mid\left(m_{1}, \ldots, m_{k}\right) \in \mathbb{N}_{0}^{k}\right\}$ for some fixed $k \geqslant 1$ and some fixed register machine code $n$. Show that $E=\left\{m \in \mathbb{N}_{0} \mid f_{j, 1}(m) \downarrow\right\}$ for some fixed register machine code $j$. Hence show that $E$ is an r.e. set.

(c) Show that the function $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$ defined below is primitive recursive.

$f(n)= \begin{cases}n-1 & \text { if } n>0 \\ 0 & \text { if } n=0\end{cases}$

[Any use of Church's thesis in your answers should be explicitly stated. In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers.]

comment

• # Paper 2, Section I, E

(a) State Hamilton's equations for a system with $n$ degrees of freedom and Hamilto$\operatorname{nian} H(\mathbf{q}, \mathbf{p}, t)$, where $(\mathbf{q}, \mathbf{p})=\left(q_{1}, \ldots, q_{n}, p_{1}, \ldots, p_{n}\right)$ are canonical phase-space variables.

(b) Define the Poisson bracket $\{f, g\}$ of two functions $f(\mathbf{q}, \mathbf{p}, t)$ and $g(\mathbf{q}, \mathbf{p}, t)$.

(c) State the canonical commutation relations of the variables $\mathbf{q}$ and $\mathbf{p}$.

(d) Show that the time-evolution of any function $f(\mathbf{q}, \mathbf{p}, t)$ is given by

$\frac{d f}{d t}=\{f, H\}+\frac{\partial f}{\partial t}$

(e) Show further that the Poisson bracket of any two conserved quantities is also a conserved quantity.

[You may assume the Jacobi identity,

$\{f,\{g, h\}\}+\{g,\{h, f\}\}+\{h,\{f, g\}\}=0 .]$

comment
• # Paper 2, Section II, E

The Lagrangian of a particle of mass $m$ and charge $q$ moving in an electromagnetic field described by scalar and vector potentials $\phi(\mathbf{r}, t)$ and $\mathbf{A}(\mathbf{r}, t)$ is

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

where $\mathbf{r}(t)$ is the position vector of the particle and $\dot{\mathbf{r}}=d \mathbf{r} / d t$.

(a) Show that Lagrange's equations are equivalent to the equation of motion

$m \ddot{\mathbf{r}}=q(\mathbf{E}+\mathbf{v} \times \mathbf{B}),$

where

$\mathbf{E}=-\nabla \phi-\frac{\partial \mathbf{A}}{\partial t}, \quad \mathbf{B}=\nabla \times \mathbf{A}$

are the electric and magnetic fields.

(b) Show that the related Hamiltonian is

$H=\frac{|\mathbf{p}-q \mathbf{A}|^{2}}{2 m}+q \phi,$

where $\mathbf{p}=m \dot{\mathbf{r}}+q \mathbf{A}$. Obtain Hamilton's equations for this system.

(c) Verify that the electric and magnetic fields remain unchanged if the scalar and vector potentials are transformed according to

where $f(\mathbf{r}, t)$ is a scalar field. Show that the transformed Lagrangian $\tilde{L}$ differs from $L$ by the total time-derivative of a certain quantity. Why does this leave the form of Lagrange's equations invariant? Show that the transformed Hamiltonian $\tilde{H}$ and phase-space variables $(\mathbf{r}, \tilde{\mathbf{p}})$ are related to $H$ and $(\mathbf{r}, \mathbf{p})$ by a canonical transformation.

[Hint: In standard notation, the canonical transformation associated with the type-2 generating function $F_{2}(\mathbf{q}, \mathbf{P}, t)$ is given by

$\left.\mathbf{p}=\frac{\partial F_{2}}{\partial \mathbf{q}}, \quad \mathbf{Q}=\frac{\partial F_{2}}{\partial \mathbf{P}}, \quad K=H+\frac{\partial F_{2}}{\partial t} .\right]$

\begin{aligned} & \phi \mapsto \tilde{\phi}=\phi-\frac{\partial f}{\partial t}, \\ & \mathbf{A} \mapsto \tilde{\mathbf{A}}=\mathbf{A}+\nabla f, \end{aligned}

comment

• # Paper 2, Section I, G

Define the binary Hamming code of length $n=2^{l}-1$ for $l \geqslant 3$. Define a perfect code. Show that a binary Hamming code is perfect.

What is the weight of the dual code of a binary Hamming code when $l=3 ?$

comment
• # Paper 2, Section II, G

Describe the Huffman coding scheme and prove that Huffman codes are optimal.

Are the following statements true or false? Justify your answers.

(i) Given $m$ messages with probabilities $p_{1} \geqslant p_{2} \geqslant \cdots \geqslant p_{m}$ a Huffman coding will assign a unique set of word lengths.

(ii) An optimal code must be Huffman.

(iii) Suppose the $m$ words of a Huffman code have word lengths $s_{1}, s_{2}, \ldots, s_{m}$. Then

$\sum_{i=1}^{m} 2^{-s_{i}}=1$

[Throughout this question you may assume that a decipherable code with prescribed word lengths exists if and only if there is a prefix-free code with the same word lengths.]

comment

• # Paper 2, Section I, B

[You may work in units of the speed of light, so that $c=1$.]

(a) Combining the Friedmann and continuity equations

$H^{2}=\frac{8 \pi G}{3} \rho, \quad \dot{\rho}+3 H(\rho+P)=0$

derive the Raychaudhuri equation (also known as the acceleration equation) which expresses $\ddot{a} / a$ in terms of the energy density $\rho$ and the pressure $P$.

(b) Assuming an equation of state $P=w \rho$ with constant $w$, for what $w$ is the expansion of the universe accelerated or decelerated?

(c) Consider an expanding, spatially-flat FLRW universe with both a cosmological constant and non-relativistic matter (also known as dust) with energy densities $\rho_{c c}$ and $\rho_{d u s t}$ respectively. At some time corresponding to $a_{e q}$, the energy densities of these two components are equal $\rho_{c c}\left(a_{e q}\right)=\rho_{d u s t}\left(a_{e q}\right)$. Is the expansion of the universe accelerated or decelerated at this time?

(d) For what numerical value of $a / a_{e q}$ does the universe transition from deceleration to acceleration?

comment

• # Paper 2, Section II, H

(a) Let $\alpha:(a, b) \rightarrow \mathbb{R}^{3}$ be a smooth regular curve parametrised by arclength. For $s \in(a, b)$, define the curvature $k(s)$ and (where defined) the torsion $\tau(s)$ of $\alpha$. What condition must be satisfied in order for the torsion to be defined? Derive the Frenet equations.

(b) If $\tau(s)$ is defined and equal to 0 for all $s \in(a, b)$, show that $\alpha$ lies in a plane.

(c) State the fundamental theorem for regular curves in $\mathbb{R}^{3}$, giving necessary and sufficient conditions for when curves $\alpha(s)$ and $\widetilde{\alpha}(s)$ are related by a proper Euclidean motion.

(d) Now suppose that $\widetilde{\alpha}:(a, b) \rightarrow \mathbb{R}^{3}$ is another smooth regular curve parametrised by arclength, and that $\widetilde{k}(s)$ and $\tilde{\tau}(s)$ are its curvature and torsion. Determine whether the following statements are true or false. Justify your answer in each case.

(i) If $\tau(s)=0$ whenever it is defined, then $\alpha$ lies in a plane.

(ii) If $\tau(s)$ is defined and equal to 0 for all but one value of $s$ in $(a, b)$, then $\alpha$ lies in a plane.

(iii) If $k(s)=\tilde{k}(s)$ for all $s, \tau(s)$ and $\tilde{\tau}(s)$ are defined for all $s \neq s_{0}$, and $\tau(s)=\tilde{\tau}(s)$ for all $s \neq s_{0}$, then $\alpha$ and $\widetilde{\alpha}$are related by a rigid motion.

comment

• # Paper 2, Section II, E

For a map $F: \Lambda \rightarrow \Lambda$ give the definitions of chaos according to (i) Devaney (Dchaos) and (ii) Glendinning (G-chaos).

Consider the dynamical system

$F(x)=a x \quad(\bmod 1)$

on $\Lambda=[0,1)$, for $a>1$ (note that $a$ is not necessarily an integer). For both definitions of chaos, show that this system is chaotic.

comment

• # Paper 2, Section II, A

A viscous fluid is contained in a channel between rigid planes $y=-h$ and $y=h$. The fluid in the upper region $\sigma (with $-h<\sigma ) has dynamic viscosity $\mu_{-}$ while the fluid in the lower region $-h has dynamic viscosity $\mu_{+}>\mu_{-}$. The plane at $y=h$ moves with velocity $U_{-}$and the plane at $y=-h$ moves with velocity $U_{+}$, both in the $x$ direction. You may ignore the effect of gravity.

(a) Find the steady, unidirectional solution of the Navier-Stokes equations in which the interface between the two fluids remains at $y=\sigma$.

(b) Using the solution from part (a):

(i) calculate the stress exerted by the fluids on the two boundaries;

(ii) calculate the total viscous dissipation rate in the fluids;

(iii) demonstrate that the rate of working by boundaries balances the viscous dissipation rate in the fluids.

(c) Consider the situation where $U_{+}+U_{-}=0$. Defining the volume flux in the upper region as $Q_{-}$and the volume flux in the lower region as $Q_{+}$, show that their ratio is independent of $\sigma$ and satisfies

$\frac{Q_{-}}{Q_{+}}=-\frac{\mu_{-}}{\mu_{+}}$

comment

• # Paper 2, Section I, A

Assume that $|f(z) / z| \rightarrow 0$ as $|z| \rightarrow \infty$ and that $f(z)$ is analytic in the upper half-plane (including the real axis). Evaluate

$\mathcal{P} \int_{-\infty}^{\infty} \frac{f(x)}{x\left(x^{2}+a^{2}\right)} d x$

where $a$ is a positive real number.

[You must state clearly any standard results involving contour integrals that you use.]

comment
• # Paper 2, Section II, A

The Riemann zeta function is defined as

$\zeta(z):=\sum_{n=1}^{\infty} \frac{1}{n^{z}}$

for $R e(z)>1$, and by analytic continuation to the rest of $\mathbb{C}$ except at singular points. The integral representation of ( $\dagger$ ) for $\operatorname{Re}(z)>1$ is given by

$\zeta(z)=\frac{1}{\Gamma(z)} \int_{0}^{\infty} \frac{t^{z-1}}{e^{t}-1} d t$

where $\Gamma$ is the Gamma function.

(a) The Hankel representation is defined as

$\zeta(z)=\frac{\Gamma(1-z)}{2 \pi i} \int_{-\infty}^{\left(0^{+}\right)} \frac{t^{z-1}}{e^{-t}-1} d t$

Explain briefly why this representation gives an analytic continuation of $\zeta(z)$ as defined in ( $\ddagger$ ) to all $z$ other than $z=1$, using a diagram to illustrate what is meant by the upper limit of the integral in $(\star)$.

[You may assume $\Gamma(z) \Gamma(1-z)=\pi / \sin (\pi z)$.]

(b) Find

$\operatorname{Res}\left(\frac{t^{-z}}{e^{-t}-1}, t=2 \pi i n\right)$

where $n$ is an integer and the poles are simple.

(c) By considering

$\int_{\gamma} \frac{t^{-z}}{e^{-t}-1} d t$

where $\gamma$ is a suitably modified Hankel contour and using the result of part (b), derive the reflection formula:

$\zeta(1-z)=2^{1-z} \pi^{-z} \cos \left(\frac{1}{2} \pi z\right) \Gamma(z) \zeta(z)$

comment

• # Paper 2, Section II, F

For any prime $p \neq 5$, explain briefly why the Galois group of $X^{5}-1$ over $\mathbb{F}_{p}$ is cyclic of order $d$, where $d=1$ if $p \equiv 1 \bmod 5, d=4$ if $p \equiv 2,3 \bmod 5$, and $d=2$ if $p \equiv 4$ $\bmod 5 .$

Show that the splitting field of $X^{5}-5$ over $\mathbb{Q}$ is an extension of degree 20 .

For any prime $p \neq 5$, prove that $X^{5}-5 \in \mathbb{F}_{p}[X]$ does not have an irreducible cubic as a factor. For $p \equiv 2$ or $3 \bmod 5$, show that $X^{5}-5$ is the product of a linear factor and an irreducible quartic over $\mathbb{F}_{p}$. For $p \equiv 1 \bmod 5$, show that either $X^{5}-5$ is irreducible over $\mathbb{F}_{p}$ or it splits completely.

[You may assume the reduction mod p criterion for finding cycle types in the Galois group of a monic polynomial over $\mathbb{Z}$ and standard facts about finite fields.]

comment

• # Paper 2, Section II, D

Consider the spacetime metric

$d s^{2}=-f(r) d t^{2}+\frac{1}{f(r)} d r^{2}+r^{2}\left(d \theta^{2}+\sin ^{2} \theta d \phi^{2}\right), \quad \text { with } \quad f(r)=1-\frac{2 m}{r}-H^{2} r^{2}$

where $H>0$ and $m>0$ are constants.

(a) Write down the Lagrangian for geodesics in this spacetime, determine three independent constants of motion and show that geodesics obey the equation

$\dot{r}^{2}+V(r)=E^{2}$

where $E$ is constant, the overdot denotes differentiation with respect to an affine parameter and $V(r)$ is a potential function to be determined.

(b) Sketch the potential $V(r)$ for the case of null geodesics, find any circular null geodesics of this spacetime, and determine whether they are stable or unstable.

(c) Show that $f(r)$ has two positive roots $r_{-}$and $r_{+}$if $m H<1 / \sqrt{27}$ and that these satisfy the relation $r_{-}<1 /(\sqrt{3} H).

(d) Describe in one sentence the physical significance of those points where $f(r)=0$.

comment

• # Paper 2, Section II, 17G

(a) Suppose that the edges of the complete graph $K_{6}$ are coloured blue and yellow. Show that it must contain a monochromatic triangle. Does this remain true if $K_{6}$ is replaced by $K_{5}$ ?

(b) Let $t \geqslant 1$. Suppose that the edges of the complete graph $K_{3 t-1}$ are coloured blue and yellow. Show that it must contain $t$ edges of the same colour with no two sharing a vertex. Is there any $t \geqslant 1$ for which this remains true if $K_{3 t-1}$ is replaced by $K_{3 t-2}$ ?

(c) Now let $t \geqslant 2$. Suppose that the edges of the complete graph $K_{n}$ are coloured blue and yellow in such a way that there are a blue triangle and a yellow triangle with no vertices in common. Show that there are also a blue triangle and a yellow triangle that do have a vertex in common. Hence, or otherwise, show that whenever the edges of the complete graph $K_{5 t}$ are coloured blue and yellow it must contain $t$ monochromatic triangles, all of the same colour, with no two sharing a vertex. Is there any $t \geqslant 2$ for which this remains true if $K_{5 t}$ is replaced by $K_{5 t-1}$ ? [You may assume that whenever the edges of the complete graph $K_{10}$ are coloured blue and yellow it must contain two monochromatic triangles of the same colour with no vertices in common.]

comment

• # Paper 2, Section II, C

Suppose $p=p(x)$ is a smooth, real-valued, function of $x \in \mathbb{R}$ which satisfies $p(x)>0$ for all $x$ and $p(x) \rightarrow 1, p_{x}(x), p_{x x}(x) \rightarrow 0$ as $|x| \rightarrow \infty$. Consider the Sturm-Liouville operator:

$L \psi:=-\frac{d}{d x}\left(p^{2} \frac{d \psi}{d x}\right)$

which acts on smooth, complex-valued, functions $\psi=\psi(x)$. You may assume that for any $k>0$ there exists a unique function $\varphi_{k}(x)$ which satisfies:

$L \varphi_{k}=k^{2} \varphi_{k}$

and has the asymptotic behaviour:

$\varphi_{k}(x) \sim \begin{cases}e^{-i k x} & \text { as } x \rightarrow-\infty \\ a(k) e^{-i k x}+b(k) e^{i k x} & \text { as } x \rightarrow+\infty\end{cases}$

(a) By analogy with the standard Schrödinger scattering problem, define the reflection and transmission coefficients: $R(k), T(k)$. Show that $|R(k)|^{2}+|T(k)|^{2}=1$. [Hint: You may wish to consider $W(x)=p(x)^{2}\left[\psi_{1}(x) \psi_{2}^{\prime}(x)-\psi_{2}(x) \psi_{1}^{\prime}(x)\right]$ for suitable functions $\psi_{1}$ and $\left.\psi_{2} \cdot\right]$

(b) Show that, if $\kappa>0$, there exists no non-trivial normalizable solution $\psi$ to the equation

$L \psi=-\kappa^{2} \psi$

Assume now that $p=p(x, t)$, such that $p(x, t)>0$ and $p(x, t) \rightarrow 1, p_{x}(x, t), p_{x x}(x, t) \rightarrow$ 0 as $|x| \rightarrow \infty$. You are given that the operator $A$ defined by:

$A \psi:=-4 p^{3} \frac{d^{3} \psi}{d x^{3}}-18 p^{2} p_{x} \frac{d^{2} \psi}{d x^{2}}-\left(12 p p_{x}^{2}+6 p^{2} p_{x x}\right) \frac{d \psi}{d x}$

satisfies:

$(L A-A L) \psi=-\frac{d}{d x}\left(2 p^{4} p_{x x x} \frac{d \psi}{d x}\right)$

(c) Show that $L, A$ form a Lax pair if the Harry Dym equation,

$p_{t}=p^{3} p_{x x x}$

is satisfied. [You may assume $L=L^{\dagger}, A=-A^{\dagger}$.]

(d) Assuming that $p$ solves the Harry Dym equation, find how the transmission and reflection amplitudes evolve as functions of $t$.

comment

• # Paper 2, Section II, H

(a) State the real version of the Stone-Weierstrass theorem and state the UrysohnTietze extension theorem.

(b) In this part, you may assume that there is a sequence of polynomials $P_{i}$ such that $\sup _{x \in[0,1]}\left|P_{i}(x)-\sqrt{x}\right| \rightarrow 0$ as $i \rightarrow \infty$.

Let $f:[0,1] \rightarrow \mathbb{R}$ be a continuous piecewise linear function which is linear on $[0,1 / 2]$ and on $[1 / 2,1]$. Using the polynomials $P_{i}$ mentioned above (but not assuming any form of the Stone-Weierstrass theorem), prove that there are polynomials $Q_{i}$ such that $\sup _{x \in[0,1]}\left|Q_{i}(x)-f(x)\right| \rightarrow 0$ as $i \rightarrow \infty$.

(d) Which of the following families of functions are relatively compact in $C[0,1]$ with the supremum norm? Justify your answer.

\begin{aligned} &\mathcal{F}_{1}=\left\{x \mapsto \frac{\sin (\pi n x)}{n}: n \in \mathbb{N}\right\} \\ &\mathcal{F}_{2}=\left\{x \mapsto \frac{\sin (\pi n x)}{n^{1 / 2}}: n \in \mathbb{N}\right\} \\ &\mathcal{F}_{3}=\{x \mapsto \sin (\pi n x): n \in \mathbb{N}\} \end{aligned}

[In this question $\mathbb{N}$ denotes the set of positive integers.]

comment

• # Paper 2, Section II, I

Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent.

Which of the following assertions about ordinals $\alpha, \beta$ and $\gamma$ are always true, and which can be false? Give proofs or counterexamples as appropriate.

(i) $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$.

(ii) If $\alpha$ and $\beta$ are uncountable then $\alpha+\beta=\beta+\alpha$.

(iii) $\alpha(\beta \gamma)=(\alpha \beta) \gamma$.

(iv) If $\alpha$ and $\beta$ are infinite and $\alpha+\beta=\beta+\alpha$ then $\alpha \beta=\beta \alpha$.

comment

• # Paper 2, Section I, C

An activator-inhibitor system for $u(x, t)$ and $v(x, t)$ is described by the equations

\begin{aligned} \frac{\partial u}{\partial t} &=u v^{2}-a+D \frac{\partial^{2} u}{\partial x^{2}} \\ \frac{\partial v}{\partial t} &=v-u v^{2}+\frac{\partial^{2} v}{\partial x^{2}} \end{aligned}

where $a, D>0$.

Find the range of $a$ for which the spatially homogeneous system has a stable equilibrium solution with $u>0$ and $v>0$.

For the case when the homogeneous system is stable, consider spatial perturbations proportional to $\cos (k x)$ to the equilibrium solution found above. Give a condition on $D$ in terms of $a$ for the system to have a Turing instability (a spatial instability).

comment

• # Paper 2, Section II, G

(a) Let $L$ be a number field. State Minkowski's upper bound for the norm of a representative for a given class of the ideal class group $\mathrm{Cl}\left(\mathcal{O}_{L}\right)$.

(b) Now let $K=\mathbb{Q}(\sqrt{-47})$ and $\omega=\frac{1}{2}(1+\sqrt{-47})$. Using Dedekind's criterion, or otherwise, factorise the ideals $(\omega)$ and $(2+\omega)$ as products of non-zero prime ideals of $\mathcal{O}_{K}$.

(c) Show that $\mathrm{Cl}\left(\mathcal{O}_{K}\right)$ is cyclic, and determine its order.

[You may assume that $\left.\mathcal{O}_{K}=\mathbb{Z}[\omega] .\right]$

comment

• # Paper 2, Section I, I

Define the Jacobi symbol $\left(\frac{a}{n}\right)$, where $a, n \in \mathbb{Z}$ and $n$ is odd and positive.

State and prove the Law of Quadratic Reciprocity for the Jacobi symbol. [You may use Quadratic Reciprocity for the Legendre symbol without proof but should state it clearly.]

Compute the Jacobi symbol $\left(\frac{503}{2019}\right)$.

comment

• # Paper 2, Section II, C

The Poisson equation on the unit square, equipped with zero boundary conditions, is discretized with the 9-point scheme:

\begin{aligned} &-\frac{10}{3} u_{i, j}+\frac{2}{3}\left(u_{i+1, j}+u_{i-1, j}+u_{i, j+1}+u_{i, j-1}\right) \\ &+\frac{1}{6}\left(u_{i+1, j+1}+u_{i+1, j-1}+u_{i-1, j+1}+u_{i-1, j-1}\right)=h^{2} f_{i, j} \end{aligned}

where $1 \leqslant i, j \leqslant m, u_{i, j} \approx u(i h, j h)$, and $(i h, j h)$ are the grid points with $h=\frac{1}{m+1}$. We also assume that $u_{0, j}=u_{i, 0}=u_{m+1, j}=u_{i, m+1}=0$.

(a) Prove that all $m \times m$ tridiagonal symmetric Toeplitz (TST-) matrices

$H=[\beta, \alpha, \beta]:=\left[\begin{array}{cccc} \alpha & \beta & & \\ \beta & \alpha & \ddots & \\ & \ddots & \ddots & \beta \\ & & \beta & \alpha \end{array}\right] \in \mathbb{R}^{m \times m}$

share the same eigenvectors $\boldsymbol{q}_{k}$ with the components $(\sin j k \pi h)_{j=1}^{m}$ for $k=1, \ldots, m$. Find expressions for the corresponding eigenvalues $\lambda_{k}$ for $k=1, \ldots, m$. Deduce that $H=Q D Q^{-1}$, where $D=\operatorname{diag}\left\{\lambda_{k}\right\}$ and $Q$ is the matrix $(\sin i j \pi h)_{i, j=1}^{m} .$

(b) Show that, by arranging the grid points ( $i h, j h)$ into a one-dimensional array by columns, the 9 -points scheme results in the following system of linear equations of the form

$A \boldsymbol{u}=\boldsymbol{b} \Leftrightarrow\left[\begin{array}{cccc} B & C & & \\ C & B & \ddots & \\ & \ddots & \ddots & C \\ & & C & B \end{array}\right]\left[\begin{array}{c} \boldsymbol{u}_{1} \\ \boldsymbol{u}_{2} \\ \vdots \\ \boldsymbol{u}_{m} \end{array}\right]=\left[\begin{array}{c} \boldsymbol{b}_{1} \\ \boldsymbol{b}_{2} \\ \vdots \\ \boldsymbol{b}_{m} \end{array}\right]$

where $A \in \mathbb{R}^{m^{2} \times m^{2}}$, the vectors $\boldsymbol{u}_{k}, \boldsymbol{b}_{k} \in \mathbb{R}^{m}$ are portions of $\boldsymbol{u}, \boldsymbol{b} \in \mathbb{R}^{m^{2}}$, respectively, and $B, C$ are $m \times m$ TST-matrices whose elements you should determine.

(c) Using $\boldsymbol{v}_{k}=Q^{-1} \boldsymbol{u}_{k}, \boldsymbol{c}_{k}=Q^{-1} \boldsymbol{b}_{k}$, show that (2) is equivalent to

$\left[\begin{array}{cccc} D & E & & \\ E & D & \ddots & \\ & \ddots & \ddots & E \\ & & E & D \end{array}\right]\left[\begin{array}{c} \boldsymbol{v}_{1} \\ \boldsymbol{v}_{2} \\ \vdots \\ \boldsymbol{v}_{m} \end{array}\right]=\left[\begin{array}{c} \boldsymbol{c}_{1} \\ \boldsymbol{c}_{2} \\ \vdots \\ \boldsymbol{c}_{m} \end{array}\right]$

where $D$ and $E$ are diagonal matrices.

(d) Show that, by appropriate reordering of the grid, the system (3) is reduced to $m$ uncoupled $m \times m$ systems of the form

$\Lambda_{k} \widehat{v}_{k}=\widehat{c}_{k}, \quad k=1, \ldots, m$

Determine the elements of the matrices $\Lambda_{k}$.

comment

• # Paper 2, Section II, B

(a) Let $|i\rangle$ and $|j\rangle$ be two eigenstates of a time-independent Hamiltonian $H_{0}$, separated in energy by $\hbar \omega_{i j}$. At time $t=0$ the system is perturbed by a small, time independent operator $V$. The perturbation is turned off at time $t=T$. Show that if the system is initially in state $|i\rangle$, the probability of a transition to state $|j\rangle$ is approximately

$P_{i j}=4|\langle i|V| j\rangle|^{2} \frac{\sin ^{2}\left(\omega_{i j} T / 2\right)}{\left(\hbar \omega_{i j}\right)^{2}}$

(b) An uncharged particle with spin one-half and magnetic moment $\mu$ travels at speed $v$ through a region of uniform magnetic field $\mathbf{B}=(0,0, B)$. Over a length $L$ of its path, an additional perpendicular magnetic field $b$ is applied. The spin-dependent part of the Hamiltonian is

$H(t)= \begin{cases}-\mu\left(B \sigma_{z}+b \sigma_{x}\right) & \text { while } 0

where $\sigma_{z}$ and $\sigma_{x}$ are Pauli matrices. The particle initially has its spin aligned along the direction of $\mathbf{B}=(0,0, B)$. Find the probability that it makes a transition to the state with opposite spin

(i) by assuming $b \ll B$ and using your result from part (a),

(ii) by finding the exact evolution of the state.

[Hint: for any 3-vector $\mathbf{a}, e^{i \mathbf{a} \cdot \boldsymbol{\sigma}}=(\cos a) I+(i \sin a) \hat{\mathbf{a}} \cdot \boldsymbol{\sigma}$, where $I$ is the $2 \times 2$ unit matrix, $\boldsymbol{\sigma}=\left(\sigma_{x}, \sigma_{y}, \sigma_{z}\right), \quad a=|\mathbf{a}|$ and $\left.\hat{\mathbf{a}}=\mathbf{a} /|\mathbf{a}| .\right]$

comment

• # Paper 2, Section II, J

(a) We consider the model $\{\operatorname{Poisson}(\theta): \theta \in(0, \infty)\}$ and an i.i.d. sample $X_{1}, \ldots, X_{n}$ from it. Compute the expectation and variance of $X_{1}$ and check they are equal. Find the maximum likelihood estimator $\hat{\theta}_{M L E}$ for $\theta$ and, using its form, derive the limit in distribution of $\sqrt{n}\left(\hat{\theta}_{M L E}-\theta\right)$.

(b) In practice, Poisson-looking data show overdispersion, i.e., the sample variance is larger than the sample expectation. For $\pi \in[0,1]$ and $\lambda \in(0, \infty)$, let $p_{\pi, \lambda}: \mathbb{N}_{0} \rightarrow[0,1]$,

$k \mapsto p_{\pi, \lambda}(k)= \begin{cases}\pi e^{-\lambda} \frac{\lambda^{k}}{k !} & \text { for } k \geqslant 1 \\ (1-\pi)+\pi e^{-\lambda} & \text { for } k=0\end{cases}$

Show that this defines a distribution. Does it model overdispersion? Justify your answer.

(c) Let $Y_{1}, \ldots, Y_{n}$ be an i.i.d. sample from $p_{\pi, \lambda}$. Assume $\lambda$ is known. Find the maximum likelihood estimator $\hat{\pi}_{M L E}$ for $\pi$.

(d) Furthermore, assume that, for any $\pi \in[0,1], \sqrt{n}\left(\hat{\pi}_{M L E}-\pi\right)$ converges in distribution to a random variable $Z$ as $n \rightarrow \infty$. Suppose we wanted to test the null hypothesis that our data arises from the model in part (a). Before making any further computations, can we necessarily expect $Z$ to follow a normal distribution under the null hypothesis? Explain. Check your answer by computing the appropriate distribution.

[You may use results from the course, provided you state it clearly.]

comment

• # Paper 2, Section II, K

(a) Let $\left(X_{i}, \mathcal{A}_{i}\right)$ for $i=1,2$ be two measurable spaces. Define the product $\sigma$-algebra $\mathcal{A}_{1} \otimes \mathcal{A}_{2}$ on the Cartesian product $X_{1} \times X_{2}$. Given a probability measure $\mu_{i}$ on $\left(X_{i}, \mathcal{A}_{i}\right)$ for each $i=1,2$, define the product measure $\mu_{1} \otimes \mu_{2}$. Assuming the existence of a product measure, explain why it is unique. [You may use standard results from the course if clearly stated.]

(b) Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space on which the real random variables $U$ and $V$ are defined. Explain what is meant when one says that $U$ has law $\mu$. On what measurable space is the measure $\mu$ defined? Explain what it means for $U$ and $V$ to be independent random variables.

(c) Now let $X=\left[-\frac{1}{2}, \frac{1}{2}\right]$, let $\mathcal{A}$ be its Borel $\sigma$-algebra and let $\mu$ be Lebesgue measure. Give an example of a measure $\eta$ on the product $(X \times X, \mathcal{A} \otimes \mathcal{A})$ such that $\eta(X \times A)=\mu(A)=\eta(A \times X)$ for every Borel set $A$, but such that $\eta$ is not Lebesgue measure on $X \times X$.

(d) Let $\eta$ be as in part (c) and let $I, J \subset X$ be intervals of length $x$ and $y$ respectively. Show that

$x+y-1 \leqslant \eta(I \times J) \leqslant \min \{x, y\}$

(e) Let $X$ be as in part (c). Fix $d \geqslant 2$ and let $\Pi_{i}$ denote the projection $\Pi_{i}\left(x_{1}, \ldots, x_{d}\right)=\left(x_{1}, \ldots, x_{i-1}, x_{i+1}, \ldots, x_{d}\right)$ from $X^{d}$ to $X^{d-1}$. Construct a probability measure $\eta$ on $X^{d}$, such that the image under each $\Pi_{i}$ coincides with the $(d-1)$-dimensional Lebesgue measure, while $\eta$ itself is not the $d$-dimensional Lebesgue measure. $[$ Hint: Consider the following collection of $2 d-1$ independent random variables: $U_{1}, \ldots, U_{d}$ uniformly distributed on $\left[0, \frac{1}{2}\right]$, and $\varepsilon_{1}, \ldots, \varepsilon_{d-1}$ such that $\mathbb{P}\left(\varepsilon_{i}=1\right)=\mathbb{P}\left(\varepsilon_{i}=-1\right)=\frac{1}{2}$ for each $i .]$

comment

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

The BB84 quantum key distribution protocol begins with Alice choosing two uniformly random bit strings $X=x_{1} x_{2} \ldots x_{m}$ and $Y=y_{1} y_{2} \ldots y_{m}$.

(a) In terms of these strings, describe Alice's process of conjugate coding for the BB84 protocol.

(b) Suppose Alice and Bob are distantly separated in space and have available a noiseless quantum channel on which there is no eavesdropping. They can also communicate classically publicly. For this idealised situation, describe the steps of the BB84 protocol that results in Alice and Bob sharing a secret key of expected length $m / 2$.

(c) Suppose now that an eavesdropper Eve taps into the channel and carries out the following action on each passing qubit. With probability $1-p$, Eve lets it pass undisturbed, and with probability $p$ she chooses a bit $w \in\{0,1\}$ uniformly at random and measures the qubit in basis $B_{w}$ where $B_{0}=\{|0\rangle,|1\rangle\}$ and $B_{1}=\{(|0\rangle+|1\rangle) / \sqrt{2},(|0\rangle-|1\rangle) / \sqrt{2}\}$. After measurement Eve sends the post-measurement state on to Bob. Calculate the bit error rate for Alice and Bob's final key in part (b) that results from Eve's action.

comment
• # Paper 2, Section II, D

Let $\left|\alpha_{0}\right\rangle \neq\left|\alpha_{1}\right\rangle$ be two quantum states and let $p_{0}$ and $p_{1}$ be associated probabilities with $p_{0}+p_{1}=1, p_{0} \neq 0, p_{1} \neq 0$ and $p_{0} \geqslant p_{1}$. Alice chooses state $\left|\alpha_{i}\right\rangle$ with probability $p_{i}$ and sends it to Bob. Upon receiving it, Bob performs a 2-outcome measurement $\mathcal{M}$ with outcomes labelled 0 and 1 , in an attempt to identify which state Alice sent.

(a) By using the extremal property of eigenvalues, or otherwise, show that the operator $D=p_{0}\left|\alpha_{0}\right\rangle\left\langle\alpha_{0}\left|-p_{1}\right| \alpha_{1}\right\rangle\left\langle\alpha_{1}\right|$ has exactly two nonzero eigenvalues, one of which is positive and the other negative.

(b) Let $P_{S}$ denote the probability that Bob correctly identifies Alice's sent state. If the measurement $\mathcal{M}$ comprises orthogonal projectors $\left\{\Pi_{0}, \Pi_{1}\right\}$ (corresponding to outcomes 0 and 1 respectively) give an expression for $P_{S}$ in terms of $p_{1}, \Pi_{0}$ and $D$.

(c) Show that the optimal success probability $P_{S}^{\text {opt }}$, i.e. the maximum attainable value of $P_{S}$, is

$P_{S}^{\mathrm{opt}}=\frac{1+\sqrt{1-4 p_{0} p_{1} \cos ^{2} \theta}}{2}$

where $\cos \theta=\left|\left\langle\alpha_{0} \mid \alpha_{1}\right\rangle\right|$.

(d) Suppose we now place the following extra requirement on Bob's discrimination process: whenever Bob obtains output 0 then the state sent by Alice was definitely $\left|\alpha_{0}\right\rangle$. Show that Bob's $P_{S}^{\mathrm{opt}}$ now satisfies $P_{S}^{\mathrm{opt}} \geqslant 1-p_{0} \cos ^{2} \theta$.

comment

• # Paper 2, Section II, I

(a) For any finite group $G$, let $\rho_{1}, \ldots, \rho_{k}$ be a complete set of non-isomorphic complex irreducible representations of $G$, with dimensions $n_{1}, \ldots n_{k}$, respectively. Show that

$\sum_{j=1}^{k} n_{j}^{2}=|G|$

(b) Let $A, B, C, D$ be the matrices

and let $G=\langle A, B, C, D\rangle$. Write $Z=-I_{4}$.

(i) Prove that the derived subgroup $G^{\prime}=\langle Z\rangle$.

(ii) Show that for all $g \in G, g^{2} \in\langle Z\rangle$, and deduce that $G$ is a 2-group of order at most 32 .

(iii) Prove that the given representation of $G$ of degree 4 is irreducible.

(iv) Prove that $G$ has order 32 , and find all the irreducible representations of $G$.

\begin{aligned} & A=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\0 & -1 & 0 & 0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 & -1\end{array}\right), \quad B=\left(\begin{array}{llll}0 & 1 & 0 & 0 \\1 & 0 & 0 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & 1 & 0\end{array}\right) \\ & C=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & -1 & 0 \\0 & 0 & 0 & -1\end{array}\right), \quad D=\left(\begin{array}{llll}0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 \\0 & 1 & 0 & 0\end{array}\right) \end{aligned}

comment

• # Paper 2, Section II, F

(a) Prove that $z \mapsto z^{4}$ as a map from the upper half-plane $\mathbb{H}$ to $\mathbb{C} \backslash\{0\}$ is a covering map which is not regular.

(b) Determine the set of singular points on the unit circle for

$h(z)=\sum_{n=0}^{\infty}(-1)^{n}(2 n+1) z^{n}$

(c) Suppose $f: \Delta \backslash\{0\} \rightarrow \Delta \backslash\{0\}$ is a holomorphic map where $\Delta$ is the unit disk. Prove that $f$ extends to a holomorphic map $\tilde{f}: \Delta \rightarrow \Delta$. If additionally $f$ is biholomorphic, prove that $\tilde{f}(0)=0$.

(d) Suppose that $g: \mathbb{C} \hookrightarrow R$ is a holomorphic injection with $R$ a compact Riemann surface. Prove that $R$ has genus 0 , stating carefully any theorems you use.

comment

• # Paper 2, Section I, J

The cycling data frame contains the results of a study on the effects of cycling to work among 1,000 participants with asthma, a respiratory illness. Half of the participants, chosen uniformly at random, received a monetary incentive to cycle to work, and the other half did not. The variables in the data frame are:

• miles: the average number of miles cycled per week

• episodes: the number of asthma episodes experienced during the study

• incentive: whether or not a monetary incentive to cycle was given

• history: the number of asthma episodes in the year preceding the study

Consider the $R$ code below and its abbreviated output.

$>\operatorname{lm} .1=\operatorname{lm}$ (episodes miles $+$ history, data=cycling)

$>\operatorname{summary}(1 \mathrm{~lm} .1)$

Coefficients:

Estimate Std. Error $t$ value $\operatorname{Pr}(>|t|)$

(Intercept) $0.66937 \quad 0.07965 \quad 8.404<2 \mathrm{e}-16 * * *$

miles $\quad-0.04917 \quad 0.01839-2.6740 .00761 * *$

history $1.489540 .0481830 .918<2 \mathrm{e}-16 * * *$

$>\operatorname{lm} .2=\operatorname{lm}($ episodes $~$incentive $+$ history, data=cycling)

$>$ summary (lm.2)

Coefficients:

Estimate Std. Error $t$ value $\operatorname{Pr}(>|t|)$

(Intercept) $0.09539 \quad 0.06960 \quad 1.371 \quad 0.171$

incentiveYes $0.91387 \quad 0.06504 \quad 14.051<2 \mathrm{e}-16 * * *$

history $1.46806 \quad 0.04346 \quad 33.782<2 \mathrm{e}-16 * * *$

$>\operatorname{lm} .3=\operatorname{lm}($ miles incentive $+$ history, data=cycling)

$>\operatorname{summary}(\operatorname{lm} .3)$

Coefficients :

Estimate Std. Error t value $\operatorname{Pr}(>|t|)$

(Intercept) $1.47050 \quad 0.11682 \quad 12.588<2 \mathrm{e}-16 * * *$

incentiveYes $1.73282 \quad 0.10917 \quad 15.872<2 \mathrm{e}-16 * * *$

history $\quad 0.47322 \quad 0.07294 \quad 6.487 \quad 1.37 \mathrm{e}-10 * * *$

(a) For each of the fitted models, briefly explain what can be inferred about participants with similar histories.

(b) Based on this analysis and the experimental design, is it advisable for a participant with asthma to cycle to work more often? Explain.

comment

• # Paper 2, Section II, D

Using the classical statistical mechanics of a gas of molecules with negligible interactions, derive the ideal gas law. Explain briefly to what extent this law is independent of the molecule's internal structure.

Calculate the entropy $S$ of a monatomic gas of low density, with negligible interactions. Deduce the equation relating the pressure $P$ and volume $V$ of the gas on a curve in the $PV$-plane along which $S$ is constant.

[You may use $\int_{-\infty}^{\infty} e^{-\alpha x^{2}} d x=\left(\frac{\pi}{\alpha}\right)^{\frac{1}{2}}$ for $\left.\alpha>0 .\right]$

comment

• # Paper 2, Section II, $29 K$

(a) In the context of a multi-period model in discrete time, what does it mean to say that a probability measure is an equivalent martingale measure?

(b) State the fundamental theorem of asset pricing.

(c) Consider a single-period model with one risky asset $S^{1}$ having initial price $S_{0}^{1}=1$. At time 1 its value $S_{1}^{1}$ is a random variable on $(\Omega, \mathcal{F}, \mathbb{P})$ of the form

$S_{1}^{1}=\exp (\sigma Z+m), \quad m \in \mathbb{R}, \sigma>0,$

where $Z \sim \mathcal{N}(0,1)$. Assume that there is a riskless numéraire $S^{0}$ with $S_{0}^{0}=S_{1}^{0}=1$. Show that there is no arbitrage in this model.

[Hint: You may find it useful to consider a density of the form $\exp (\tilde{\sigma} Z+\tilde{m})$ and find suitable $\tilde{m}$ and $\tilde{\sigma}$. You may use without proof that if $X$ is a normal random variable then $\mathbb{E}\left(e^{X}\right)=\exp \left(\mathbb{E}(X)+\frac{1}{2} \operatorname{Var}(X)\right)$.]

(d) Now consider a multi-period model with one risky asset $S^{1}$ having a non-random initial price $S_{0}^{1}=1$ and a price process $\left(S_{t}^{1}\right)_{t \in\{0, \ldots, T\}}$ of the form

$S_{t}^{1}=\prod_{i=1}^{t} \exp \left(\sigma_{i} Z_{i}+m_{i}\right), \quad m_{i} \in \mathbb{R}, \sigma_{i}>0$