# Part II, 2018

### Jump to course

Paper 1, Section II, I

comment(a) Let $k$ be an uncountable field, $\mathcal{M} \subseteq k\left[x_{1}, \ldots, x_{n}\right]$ a maximal ideal and $A=k\left[x_{1}, \ldots, x_{n}\right] / \mathcal{M} .$

Show that every element of $A$ is algebraic over $k$.

(b) Now assume that $k$ is algebraically closed. Suppose that $J \subset k\left[x_{1}, \ldots, x_{n}\right]$ is an ideal, and that $f \in k\left[x_{1}, \ldots, x_{n}\right]$ vanishes on $Z(J)$. Using the result of part (a) or otherwise, show that $f^{N} \in J$ for some $N \geqslant 1$.

(c) Let $f: X \rightarrow Y$ be a morphism of affine algebraic varieties. Show $\overline{f(X)}=Y$ if and only if the map $f^{*}: k[Y] \rightarrow k[X]$ is injective.

Suppose now that $\overline{f(X)}=Y$, and that $X$ and $Y$ are irreducible. Define the dimension of $X, \operatorname{dim} X$, and show $\operatorname{dim} X \geqslant \operatorname{dim} Y$. [You may use whichever definition of $\operatorname{dim} X$ you find most convenient.]

Paper 2, Section II, I

comment(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}$.

Paper 3, Section II, I

comment(a) State the Riemann-Roch theorem.

(b) Let $E$ be a smooth projective curve of genus 1 over an algebraically closed field $k$, with char $k \neq 2,3$. Show that there exists an isomorphism from $E$ to the plane cubic in $\mathbf{P}^{2}$ defined by the equation

$y^{2}=\left(x-\lambda_{1}\right)\left(x-\lambda_{2}\right)\left(x-\lambda_{3}\right)$

for some distinct $\lambda_{1}, \lambda_{2}, \lambda_{3} \in k$.

(c) Let $Q$ be the point at infinity on $E$. Show that the map $E \rightarrow C l^{0}(E), P \mapsto[P-Q]$ is an isomorphism.

Describe how this defines a group structure on $E$. Denote addition by $\boxplus$. Determine all the points $P \in E$ with $P \boxplus P=Q$ in terms of the equation of the plane curve in part (b).

Paper 4, Section II, I

commentState a theorem which describes the canonical divisor of a smooth plane curve $C$ in terms of the divisor of a hyperplane section. Express the degree of the canonical divisor $K_{C}$ and the genus of $C$ in terms of the degree of $C$. [You need not prove these statements.]

From now on, we work over $\mathbb{C}$. Consider the curve in $\mathbf{A}^{2}$ defined by the equation

$y+x^{3}+x y^{3}=0$

Let $C$ be its projective completion. Show that $C$ is smooth.

Compute the genus of $C$ by applying the Riemann-Hurwitz theorem to the morphism $C \rightarrow \mathbf{P}^{1}$ induced from the rational map $(x, y) \mapsto y$. [You may assume that the discriminant of $x^{3}+a x+b$ is $-4 a^{3}-27 b^{2}$.]

Paper 1, Section II, H

comment(a) Let $V$ be the vector space of 3-dimensional upper-triangular matrices with real entries:

$V=\left\{\left(\begin{array}{ccc} 1 & x & y \\ 0 & 1 & z \\ 0 & 0 & 1 \end{array}\right) \mid x, y, z \in \mathbb{R}\right\}$

Let $\Gamma$ be the set of elements of $V$ for which $x, y, z$ are integers. Notice that $\Gamma$ is a subgroup of $G L_{3}(\mathbb{R})$; let $\Gamma$ act on $V$ by left-multiplication and let $N=\Gamma \backslash V$. Show that the quotient $\operatorname{map} V \rightarrow N$ is a covering map.

(b) Consider the unit circle $S^{1} \subseteq \mathbb{C}$, and let $T=S^{1} \times S^{1}$. Show that the map $f: T \rightarrow T$ defined by

$f(z, w)=(z w, w)$

is a homeomorphism.

(c) Let $M=[0,1] \times T / \sim$, where $\sim$ is the smallest equivalence relation satisfying

$(1, x) \sim(0, f(x))$

for all $x \in T$. Prove that $N$ and $M$ are homeomorphic by exhibiting a homeomorphism $M \rightarrow N$. [You may assume without proof that $N$ is Hausdorff.]

(d) Prove that $\pi_{1}(M) \cong \Gamma$.

Paper 2, Section II, H

comment(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$.

Paper 3, Section II, H

comment(a) State a version of the Seifert-van Kampen theorem for a cell complex $X$ written as the union of two subcomplexes $Y, Z$.

(b) Let

$X_{n}=\underbrace{S^{1} \vee \ldots \vee S^{1}}_{n} \vee \mathbb{R} P^{2}$

for $n \geqslant 1$, and take any $x_{0} \in X_{n}$. Write down a presentation for $\pi_{1}\left(X_{n}, x_{0}\right)$.

(c) By computing a homology group of a suitable four-sheeted covering space of $X_{n}$, prove that $X_{n}$ is not homotopy equivalent to a compact, connected surface whenever $n \geqslant 1$.

Paper 4, Section II, H

comment(a) State the Mayer-Vietoris theorem for a union of simplicial complexes

$K=M \cup N$

with $L=M \cap N$.

(b) Construct the map $\partial_{*}: H_{k}(K) \rightarrow H_{k-1}(L)$ that appears in the statement of the theorem. [You do not need to prove that the map is well defined, or a homomorphism.]

(c) Let $K$ be a simplicial complex with $|K|$ homeomorphic to the $n$-dimensional sphere $S^{n}$, for $n \geqslant 2$. Let $M \subseteq K$ be a subcomplex with $|M|$ homeomorphic to $S^{n-1} \times[-1,1]$. Suppose that $K=M \cup N$, such that $L=M \cap N$ has polyhedron $|L|$ identified with $S^{n-1} \times\{-1,1\} \subseteq S^{n-1} \times[-1,1]$. Prove that $|N|$ has two path components.

Paper 1, Section II, F

comment(a) Consider a measure space $(X, \mathcal{A}, \mu)$ and a complex-valued measurable function $F$ on $X$. Prove that for any $\varphi:[0,+\infty) \rightarrow[0,+\infty)$ differentiable and increasing such that $\varphi(0)=0$, then

$\int_{X} \varphi(|F(x)|) \mathrm{d} \mu(x)=\int_{0}^{+\infty} \varphi^{\prime}(s) \mu(\{|F|>s\}) \mathrm{d} \lambda(s)$

where $\lambda$ is the Lebesgue measure.

(b) Consider a complex-valued measurable function $f \in L^{1}\left(\mathbb{R}^{n}\right) \cap L^{\infty}\left(\mathbb{R}^{n}\right)$ and its maximal function $M f(x)=\sup _{r>0} \frac{1}{|B(x, r)|} \int_{B(x, r)}|f| \mathrm{d} \lambda$. Prove that for $p \in(1,+\infty)$ there is a constant $c_{p}>0$ such that $\|M f\|_{L^{p}\left(\mathbb{R}^{n}\right)} \leqslant c_{p}\|f\|_{L^{p}\left(\mathbb{R}^{n}\right)}$.

[Hint: Split $f=f_{0}+f_{1}$ with $f_{0}=f \chi_{\{|f|>s / 2\}}$ and $f_{1}=f \chi_{\{|f| \leqslant s / 2\}}$ and prove that $\lambda(\{M f>s\}) \leqslant \lambda\left(\left\{M f_{0}>s / 2\right\}\right)$. Then use the maximal inequality $\lambda(\{M f>s\}) \leqslant$ $\frac{C_{1}}{s}\|f\|_{L^{1}\left(\mathbb{R}^{n}\right)}$ for some constant $\left.C_{1}>0 .\right]$

(c) Consider $p, q \in(1,+\infty)$ with $p<q$ and $\alpha \in(0, n)$ such that $1 / q=1 / p-\alpha / n$. Define $I_{\alpha}|f|(x):=\int_{\mathbb{R}^{n}} \frac{|f(y)|}{|x-y|^{n-\alpha}} \mathrm{d} \lambda(y)$ and prove $I_{\alpha}|f|(x) \leqslant\|f\|_{L^{p}\left(\mathbb{R}^{n}\right)}^{\alpha p / n} M f(x)^{1-\alpha p / n}$.

[Hint: Split the integral into $|x-y| \geqslant r$ and $|x-y| \in\left[2^{-k-1} r, 2^{-k} r\right)$ for all $k \geqslant 0$, given some suitable $r>0 .]$

Paper 3, Section II, $22 F$

comment(a) Let $(X, \mathcal{A}, \mu)$ be a measure space. Define the spaces $L^{p}(X)$ for $p \in[1, \infty]$. Prove that if $\mu(X)<\infty$ then $L^{q}(X) \subset L^{p}(X)$ for all $1 \leqslant p<q \leqslant \infty$.

(b) Now let $X=\mathbb{R}^{n}$ endowed with Borel sets and Lebesgue measure. Describe the dual spaces of $L^{p}(X)$ for $p \in[1, \infty)$. Define reflexivity and say which $L^{p}(X)$ are reflexive. Prove that $L^{1}(X)$ is not the dual space of $L^{\infty}(X)$

(c) Now let $X \subset \mathbb{R}^{n}$ be a Borel subset and consider the measure space $(X, \mathcal{A}, \mu)$ induced from Borel sets and Lebesgue measure on $\mathbb{R}^{n}$.

(i) Given any $p \in[1, \infty]$, prove that any sequence $\left(f_{n}\right)$ in $L^{p}(X)$ converging in $L^{p}(X)$ to some $f \in L^{p}(X)$ admits a subsequence converging almost everywhere to $f$.

(ii) Prove that if $L^{q}(X) \subset L^{p}(X)$ for $1 \leqslant p<q \leqslant \infty$ then $\mu(X)<\infty$. [Hint: You might want to prove first that the inclusion is continuous with the help of one of the corollaries of Baire's category theorem.]

Paper 4, Section II, 23F

commentHere and below, $\Phi: \mathbb{R} \rightarrow \mathbb{R}$ is smooth such that $\int_{\mathbb{R}} e^{-\Phi(x)} \mathrm{d} x=1$ and

$\lim _{|x| \rightarrow+\infty}\left(\frac{\left|\Phi^{\prime}(x)\right|^{2}}{4}-\frac{\Phi^{\prime \prime}(x)}{2}\right)=\ell \in(0,+\infty)$

$C_{c}^{1}(\mathbb{R})$ denotes the set of continuously differentiable complex-valued functions with compact support on $\mathbb{R}$.

(a) Prove that there are constants $R_{0}>0, \lambda_{1}>0$ and $K_{1}>0$ so that for any $R \geqslant R_{0}$ and $h \in C_{c}^{1}(\mathbb{R})$ :

$\int_{\mathbb{R}}\left|h^{\prime}(x)\right|^{2} e^{-\Phi(x)} d x \geqslant \lambda_{1} \int_{\{|x| \geqslant R\}}|h(x)|^{2} e^{-\Phi(x)} d x-K_{1} \int_{\{|x| \leqslant R\}}|h(x)|^{2} e^{-\Phi(x)} d x$

[Hint: Denote $g:=h e^{-\Phi / 2}$, expand the square and integrate by parts.]

(b) Prove that, given any $R>0$, there is a $C_{R}>0$ so that for any $h \in C^{1}([-R, R])$ with $\int_{-R}^{+R} h(x) e^{-\Phi(x)} d x=0$ :

$\max _{x \in[-R, R]}|h(x)|+\operatorname{sip}_{\{x, y \in[-R, R], x \neq y\}} \frac{|h(x)-h(y)|}{|x-y|^{1 / 2}} \leqslant C_{R}\left(\int_{-R}^{+R}\left|h^{\prime}(x)\right|^{2} e^{-\Phi(x)} d x\right)^{1 / 2}$

[Hint: Use the fundamental theorem of calculus to control the second term of the left-hand side, and then compare $h$ to its weighted mean to control the first term of the left-hand side.]

(c) Prove that, given any $R>0$, there is a $\lambda_{R}>0$ so that for any $h \in C^{1}([-R, R])$ :

$\int_{-R}^{+R}\left|h^{\prime}(x)\right|^{2} e^{-\Phi(x)} d x \geqslant \lambda_{R} \int_{-R}^{+R}\left|h(x)-\frac{\int_{-R}^{+R} h(y) e^{-\Phi(y)} d y}{\int_{-R}^{+R} e^{-\Phi(y)} d y}\right|^{2} e^{-\Phi(x)} d x$

[Hint: Show first that one can reduce to the case $\int_{-R}^{+R} h e^{-\Phi}=0$. Then argue by contradiction with the help of the Arzelà-Ascoli theorem and part (b).]

(d) Deduce that there is a $\lambda_{0}>0$ so that for any $h \in C_{c}^{1}(\mathbb{R})$ :

$\int_{\mathbb{R}}\left|h^{\prime}(x)\right|^{2} e^{-\Phi(x)} d x \geqslant \lambda_{0} \int_{\mathbb{R}}\left|h(x)-\left(\int_{\mathbb{R}} h(y) e^{-\Phi(y)} d y\right)\right|^{2} e^{-\Phi(x)} d x$

[Hint: Show first that one can reduce to the case $\int_{\mathbb{R}} h e^{-\Phi}=0$. Then combine the inequality (a), multiplied by a constant of the form $\epsilon=\epsilon_{0} \lambda_{R}$ (where $\epsilon_{0}>0$ is chosen so that $\epsilon$ be sufficiently small), and the inequality (c).]

Paper 1, Section II, A

commentA particle of mass $m$ moves in one dimension in a periodic potential $V(x)$ satisfying $V(x+a)=V(x)$. Define the Floquet matrix $F$. Show that $\operatorname{det} F=1$ and explain why Tr $F$ is real. Show that allowed bands occur for energies such that $(\operatorname{Tr} F)^{2}<4$. Consider the potential

$V(x)=-\frac{\hbar^{2} \lambda}{m} \sum_{n=-\infty}^{+\infty} \delta(x-n a)$

For states of negative energy, construct the Floquet matrix with respect to the basis of states $e^{\pm \mu x}$. Derive an inequality for the values of $\mu$ in an allowed energy band.

For states of positive energy, construct the Floquet matrix with respect to the basis of states $e^{\pm i k x}$. Derive an inequality for the values of $k$ in an allowed energy band.

Show that the state with zero energy lies in a forbidden region for $\lambda a>2$.

Paper 2, Section II, A

commentConsider 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?

Paper 3, Section II, A

commentA beam of particles of mass $m$ and momentum $p=\hbar k$ is incident along the $z$-axis. The beam scatters off a spherically symmetric potential $V(r)$. Write down the asymptotic form of the wavefunction in terms of the scattering amplitude $f(\theta)$.

The incoming plane wave and the scattering amplitude can be expanded in partial waves as,

$\begin{gathered} e^{i k r \cos \theta} \sim \frac{1}{2 i k r} \sum_{l=0}^{\infty}(2 l+1)\left(e^{i k r}-(-1)^{l} e^{-i k r}\right) P_{l}(\cos \theta) \\ f(\theta)=\sum_{l=0}^{\infty} \frac{2 l+1}{k} f_{l} P_{l}(\cos \theta) \end{gathered}$

where $P_{l}$ are Legendre polynomials. Define the $S$-matrix. Assuming that the S-matrix is unitary, explain why we can write

$f_{l}=e^{i \delta_{l}} \sin \delta_{l}$

for some real phase shifts $\delta_{l}$. Obtain an expression for the total cross-section $\sigma_{T}$ in terms of the phase shifts $\delta_{l}$.

[Hint: You may use the orthogonality of Legendre polynomials:

$\left.\int_{-1}^{+1} d w P_{l}(w) P_{l^{\prime}}(w)=\frac{2}{2 l+1} \delta_{l l^{\prime}} .\right]$

Consider the repulsive, spherical potential

$V(r)=\left\{\begin{array}{cc} +V_{0} & r<a \\ 0 & r>a \end{array}\right.$

where $V_{0}=\hbar^{2} \gamma^{2} / 2 m$. By considering the s-wave solution to the Schrödinger equation, show that

$\frac{\tan \left(k a+\delta_{0}\right)}{k a}=\frac{\tanh \left(\sqrt{\gamma^{2}-k^{2}} a\right)}{\sqrt{\gamma^{2}-k^{2}} a}$

For low momenta, $k a \ll 1$, compute the s-wave contribution to the total cross-section. Comment on the physical interpretation of your result in the limit $\gamma a \rightarrow \infty$.

Paper 4, Section II, A

commentDefine a Bravais lattice $\Lambda$ in three dimensions. Define the reciprocal lattice $\Lambda^{\star}$. Define the Brillouin zone.

An FCC lattice has a basis of primitive vectors given by

$\mathbf{a}_{1}=\frac{a}{2}\left(\mathbf{e}_{2}+\mathbf{e}_{3}\right), \quad \mathbf{a}_{2}=\frac{a}{2}\left(\mathbf{e}_{1}+\mathbf{e}_{3}\right), \quad \mathbf{a}_{3}=\frac{a}{2}\left(\mathbf{e}_{1}+\mathbf{e}_{2}\right),$

where $\mathbf{e}_{i}$ is an orthonormal basis of $\mathbb{R}^{3}$. Find a basis of reciprocal lattice vectors. What is the volume of the Brillouin zone?

The asymptotic wavefunction for a particle, of wavevector $\mathbf{k}$, scattering off a potential $V(\mathbf{r})$ is

$\psi(\mathbf{r}) \sim e^{i \mathbf{k} \cdot \mathbf{r}}+f_{\mathrm{V}}\left(\mathbf{k} ; \mathbf{k}^{\prime}\right) \frac{e^{i k r}}{r}$

where $\mathbf{k}^{\prime}=k \hat{\mathbf{r}}$ and $f_{\mathrm{V}}\left(\mathbf{k} ; \mathbf{k}^{\prime}\right)$ is the scattering amplitude. Give a formula for the Born approximation to the scattering amplitude.

Scattering of a particle off a single atom is modelled by a potential $V(\mathbf{r})=V_{0} \delta(r-d)$ with $\delta$-function support on a spherical shell, $r=|\mathbf{r}|=d$ centred at the origin. Calculate the Born approximation to the scattering amplitude, denoting the resulting expression as $\tilde{f}_{V}\left(\mathbf{k} ; \mathbf{k}^{\prime}\right)$.

Scattering of a particle off a crystal consisting of atoms located at the vertices of a lattice $\Lambda$ is modelled by a potential

$V_{\Lambda}=\sum_{\mathbf{R} \in \Lambda} V(\mathbf{r}-\mathbf{R})$

where $V(\mathbf{r})=V_{0} \delta(r-d)$ as above. Calculate the Born approximation to the scattering amplitude giving your answer in terms of your approximate expression $\tilde{f}_{\mathrm{V}}$ for scattering off a single atom. Show that the resulting amplitude vanishes unless the momentum transfer $\mathbf{q}=\mathbf{k}-\mathbf{k}^{\prime}$ lies in the reciprocal lattice $\Lambda^{\star}$.

For the particular FCC lattice considered above, show that, when $k=|\mathbf{k}|>2 \pi / a$, scattering occurs for two values of the scattering angle, $\theta_{1}$ and $\theta_{2}$, related by

$\frac{\sin \left(\frac{\theta_{1}}{2}\right)}{\sin \left(\frac{\theta_{2}}{2}\right)}=\frac{2}{\sqrt{3}}$

Paper 1, Section II, J

commentLet $\lambda:[0, \infty) \rightarrow(0, \infty)$ be a continuous function. Explain what is meant by an inhomogeneous Poisson process with intensity function $\lambda$.

Let $\left(N_{t}: t \geqslant 0\right)$ be such an inhomogeneous Poisson process, and let $M_{t}=N_{g(t)}$ where $g:[0, \infty) \rightarrow[0, \infty)$ is strictly increasing, differentiable and satisfies $g(0)=0$. Show that $M$ is a homogeneous Poisson process with intensity 1 if $\Lambda(g(t))=t$ for all $t$, where $\Lambda(t)=\int_{0}^{t} \lambda(u) d u$. Deduce that $N_{t}$ has the Poisson distribution with mean $\Lambda(t)$.

Bicycles arrive at the start of a long road in the manner of a Poisson process $N=\left(N_{t}: t \geqslant 0\right)$ with constant intensity $\lambda$. The $i$ th bicycle has constant velocity $V_{i}$, where $V_{1}, V_{2}, \ldots$ are independent, identically distributed random variables, which are independent of $N$. Cyclists can overtake one another freely. Show that the number of bicycles on the first $x$ miles of the road at time $t$ has the Poisson distribution with parameter $\lambda \mathbb{E}\left(V^{-1} \min \{x, V t\}\right)$.

Paper 2, Section II, J

commentLet $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$.

Paper 3, Section II, J

commentIndividuals arrive in a shop in the manner of a Poisson process with intensity $\lambda$, and they await service in the order of their arrival. Their service times are independent, identically distributed random variables $S_{1}, S_{2}, \ldots$. For $n \geqslant 1$, let $Q_{n}$ be the number remaining in the shop immediately after the $n$th departure. Show that

$Q_{n+1}=A_{n}+Q_{n}-h\left(Q_{n}\right)$

where $A_{n}$ is the number of arrivals during the $(n+1)$ th service period, and $h(x)=$ $\min \{1, x\}$.

Show that

$\mathbb{E}\left(A_{n}\right)=\rho, \quad \mathbb{E}\left(A_{n}^{2}\right)=\rho+\lambda^{2} \mathbb{E}\left(S^{2}\right),$

where $S$ is a typical service period, and $\rho=\lambda \mathbb{E}(S)$ is the traffic intensity of the queue.

Suppose $\rho<1$, and the queue is in equilibrium in the sense that $Q_{n}$ and $Q_{n+1}$ have the same distribution for all $n$. Express $\mathbb{E}\left(Q_{n}\right)$ in terms of $\lambda, \mathbb{E}(S), \mathbb{E}\left(S^{2}\right)$. Deduce that the mean waiting time (prior to service) of a typical individual is $\frac{1}{2} \lambda \mathbb{E}\left(S^{2}\right) /(1-\rho)$.

Paper 4, Section II, J

commentLet $X_{1}, X_{2}, \ldots$ be independent, identically distributed random variables with finite mean $\mu$. Explain what is meant by saying that the random variable $M$ is a stopping time with respect to the sequence $\left(X_{i}: i=1,2, \ldots\right)$.

Let $M$ be a stopping time with finite mean $\mathbb{E}(M)$. Prove Wald's equation:

$\mathbb{E}\left(\sum_{i=1}^{M} X_{i}\right)=\mu \mathbb{E}(M)$

[Here and in the following, you may use any standard theorem about integration.]

Suppose the $X_{i}$ are strictly positive, and let $N$ be the renewal process with interarrival times $\left(X_{i}: i=1,2, \ldots\right)$. Prove that $m(t)=\mathbb{E}\left(N_{t}\right)$ satisfies the elementary renewal theorem:

$\frac{1}{t} m(t) \rightarrow \frac{1}{\mu} \quad \text { as } t \rightarrow \infty .$

A computer keyboard contains 100 different keys, including the lower and upper case letters, the usual symbols, and the space bar. A monkey taps the keys uniformly at random. Find the mean number of keys tapped until the first appearance of the sequence 'lava' as a sequence of 4 consecutive characters.

Find the mean number of keys tapped until the first appearance of the sequence 'aa' as a sequence of 2 consecutive characters.

Paper 2, Section II, B

commentGiven 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)$.

Paper 3, Section II, B

comment(a) Find the curves of steepest descent emanating from $t=0$ for the integral

$J_{x}(x)=\frac{1}{2 \pi i} \int_{C} e^{x(\sinh t-t)} d t$

for $x>0$ and determine the angles at which they meet at $t=0$, and their asymptotes at infinity.

(b) An integral representation for the Bessel function $K_{\nu}(x)$ for real $x>0$ is

$K_{\nu}(x)=\frac{1}{2} \int_{-\infty}^{+\infty} e^{\nu h(t)} d t \quad, \quad h(t)=t-\left(\frac{x}{\nu}\right) \cosh t$

Show that, as $\nu \rightarrow+\infty$, with $x$ fixed,

$K_{\nu}(x) \sim\left(\frac{\pi}{2 \nu}\right)^{\frac{1}{2}}\left(\frac{2 \nu}{e x}\right)^{\nu}$

Paper 4, Section II, B

commentShow that

$I_{0}(x)=\frac{1}{\pi} \int_{0}^{\pi} e^{x \cos \theta} d \theta$

is a solution to the equation

$x y^{\prime \prime}+y^{\prime}-x y=0,$

and obtain the first two terms in the asymptotic expansion of $I_{0}(x)$ as $x \rightarrow+\infty$.

For $x>0$, define a new dependent variable $w(x)=x^{\frac{1}{2}} y(x)$, and show that if $y$ solves the preceding equation then

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

Obtain the Liouville-Green approximate solutions to this equation for large positive $x$, and compare with your asymptotic expansion for $I_{0}(x)$ at the leading order.

Paper 1, Section I, G

comment(a) State the pumping lemma for context-free languages (CFLs).

(b) Which of the following are CFLs? Justify your answers.

(i) $\left\{w w \mid w \in\{a, b, c\}^{*}\right\}$

(ii) $\left\{a^{m} b^{n} c^{k} d^{l} \mid 3 m=4 n\right.$ and $\left.2 k=5 l\right\}$

(iii) $\left\{a^{3^{n}} \mid n \geqslant 0\right\}$

(c) Let $L$ be a CFL. Show that $L^{*}$ is also a CFL.

Paper 1, Section II, G

comment(a) Define the halting set $\mathbb{K}$. Prove that $\mathbb{K}$ is recursively enumerable, but not recursive.

(b) Given $A, B \subseteq \mathbb{N}$, define a many-one reduction of $A$ to $B$. Show that if $B$ is recursively enumerable and $A \leqslant_{m} B$, then $A$ is also recursively enumerable.

(c) Show that each of the functions $f(n)=2 n$ and $g(n)=2 n+1$ are both partial recursive and total, by building them up as partial recursive functions.

(d) Let $X, Y \subseteq \mathbb{N}$. We define the set $X \oplus Y$ via

$X \oplus Y:=\{2 x \mid x \in X\} \cup\{2 y+1 \mid y \in Y\}$

(i) Show that both $X \leqslant_{m} X \oplus Y$ and $Y \leqslant_{m} X \oplus Y$.

(ii) Using the above, or otherwise, give an explicit example of a subset $C$ of $\mathbb{N}$ for which neither $C$ nor $\mathbb{N} \backslash C$ are recursively enumerable.

(iii) For every $Z \subseteq \mathbb{N}$, show that if $X \leqslant_{m} Z$ and $Y \leqslant_{m} Z$ then $X \oplus Y \leqslant_{m} Z$.

[Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]

Paper 2, Section I, G

comment(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)$.

Paper 3, Section I, G

comment(a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form ( $\mathrm{CNF})$.

(b) Give an algorithm for converting a CFG $G$ into a corresponding CFG $G_{\text {Chom }}$ in CNF satisfying $\mathcal{L}\left(G_{\text {Chom }}\right)=\mathcal{L}(G)-\{\epsilon\}$. [You need only outline the steps, without proof.]

(c) Convert the following $\mathrm{CFG}\ G$ :

$S \rightarrow A S c \mid B, \quad A \rightarrow a, \quad B \rightarrow b$

into a grammar in CNF.

Paper 3, Section II, G

comment(a) State and prove the pumping lemma for regular languages.

(b) Let $D$ be a minimal deterministic finite-state automaton whose language $\mathcal{L}(D)$ is finite. Let $\Gamma_{D}$ be the transition diagram of $D$, and suppose there exists a non-empty closed path $\gamma$ in $\Gamma_{D}$ starting and ending at state $p$.

(i) Show that there is no path in $\Gamma_{D}$ from $p$ to any accept state of $D$.

(ii) Show that there is no path in $\Gamma_{D}$ from $p$ to any other state of $D$.

Paper 4, Section I, 4G

comment(a) State the $s-m-n$ theorem, the recursion theorem, and Rice's theorem.

(b) Show that if $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ is partial recursive, then there is some $e \in \mathbb{N}$ such that

$f_{e, 1}(y)=g(e, y) \quad \forall y \in \mathbb{N}$

(c) By considering the partial function $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ given by

$g(x, y)= \begin{cases}0 & \text { if } y<x \\ \uparrow & \text { otherwise }\end{cases}$

show there exists some $m \in \mathbb{N}$ such that $W_{m}$ has exactly $m$ elements.

(d) Given $n \in \mathbb{N}$, is it possible to compute whether or not $W_{n}$ has exactly 9 elements? Justify your answer.

[Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]

Paper 1, Section I, B

commentDerive Hamilton's equations from an action principle.

Consider a two-dimensional phase space with the Hamiltonian $H=p^{2}+q^{-2}$. Show that $F=p q-c t H$ is the first integral for some constant $c$ which should be determined. By considering the surfaces of constant $F$ in the extended phase space, solve Hamilton's equations, and sketch the orbits in the phase space.

Paper 2, Section I, B

commentLet $\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.

Paper 2, Section II, B

commentDefine 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$.

Paper 3, Section I, B

commentThree particles of unit mass move along a line in a potential

$V=\frac{1}{2}\left(\left(x_{1}-x_{2}\right)^{2}+\left(x_{1}-x_{3}\right)^{2}+\left(x_{3}-x_{2}\right)^{2}+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}\right)$

where $x_{i}$ is the coordinate of the $i$ th particle, $i=1,2,3$.

Write the Lagrangian in the form

$\mathcal{L}=\frac{1}{2} T_{i j} \dot{x}_{i} \dot{x}_{j}-\frac{1}{2} V_{i j} x_{i} x_{j}$

and specify the matrices $T_{i j}$ and $V_{i j}$.

Find the normal frequencies and normal modes for this system.

Paper 4, Section I, B

commentState and prove Noether's theorem in Lagrangian mechanics.

Consider a Lagrangian

$\mathcal{L}=\frac{1}{2} \frac{\dot{x}^{2}+\dot{y}^{2}}{y^{2}}-V\left(\frac{x}{y}\right)$

for a particle moving in the upper half-plane $\left\{(x, y) \in \mathbb{R}^{2}, y>0\right\}$ in a potential $V$ which only depends on $x / y$. Find two independent first integrals.

Paper 4, Section II, B

commentGiven a Lagrangian $\mathcal{L}\left(q_{i}, \dot{q}_{i}, t\right)$ with degrees of freedom $q_{i}$, define the Hamiltonian and show how Hamilton's equations arise from the Lagrange equations and the Legendre transform.

Consider the Lagrangian for a symmetric top moving in constant gravity:

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

where $A, B, M, g$ and $l$ are constants. Construct the corresponding Hamiltonian, and find three independent Poisson-commuting first integrals of Hamilton's equations.

Paper 1, Section I, H

commentState and prove Shannon's noiseless coding theorem. [You may use Gibbs' and Kraft's inequalities as long as they are clearly stated.]

Paper 1, Section II, H

commentDefine the bar product $C_{1} \mid C_{2}$ of binary linear codes $C_{1}$ and $C_{2}$, where $C_{2}$ is a subcode of $C_{1}$. Relate the rank and minimum distance of $C_{1} \mid C_{2}$ to those of $C_{1}$ and $C_{2}$ and justify your answer.

What is a parity check matrix for a linear code? If $C_{1}$ has parity check matrix $P_{1}$ and $C_{2}$ has parity check matrix $P_{2}$, find a parity check matrix for $C_{1} \mid C_{2}$.

Using the bar product construction, or otherwise, define the Reed-Muller code $R M(d, r)$ for $0 \leqslant r \leqslant d$. Compute the rank of $R M(d, r)$. Show that all but two codewords in $R M(d, 1)$ have the same weight. Given $d$, for which $r$ is it true that all elements of $R M(d, r)$ have even weight? Justify your answer.

Paper 2, Section I, H

commentWhat 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}$.

Paper 2, Section II, H

commentDescribe 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$.

Paper 3, Section $I$, H

commentCompute the rank and minimum distance of the cyclic code with generator polynomial $g(X)=X^{3}+X^{2}+1$ and parity check polynomial $h(X)=X^{4}+X^{3}+X^{2}+1$. Now let $\alpha$ be a root of $g(X)$ in the field with 8 elements. We receive the word $r(X)=X^{2}+X+1$ $\left(\bmod X^{7}-1\right)$. Verify that $r(\alpha)=\alpha^{4}$, and hence decode $r(X)$ using minimum-distance decoding.

Paper 4, Section I, H

commentWhat is a linear feedback shift register? Explain the Berlekamp-Massey method for recovering a feedback polynomial of a linear feedback shift register from its output. Illustrate the method in the case when we observe output

$010111100010 \ldots$

Paper 1, Section I, B

commentFor a homogeneous and isotropic universe filled with pressure-free matter $(P=0)$, the Friedmann and Raychaudhuri equations are, respectively,

$\left(\frac{\dot{a}}{a}\right)^{2}+\frac{k c^{2}}{a^{2}}=\frac{8 \pi G}{3} \rho \quad \text { and } \quad \frac{\ddot{a}}{a}=-\frac{4 \pi G}{3} \rho,$

with mass density $\rho$, curvature $k$, and where $\dot{a} \equiv d a / d t$. Using conformal time $\tau$ with $d \tau=d t / a$, show that the relative density parameter can be expressed as

$\Omega(t) \equiv \frac{\rho}{\rho_{\text {crit }}}=\frac{8 \pi G \rho a^{2}}{3 \mathcal{H}^{2}}$

where $\mathcal{H}=\frac{1}{a} \frac{d a}{d \tau}$ and $\rho_{\text {crit }}$ is the critical density of a flat $k=0$ universe (Einstein-de Sitter). Use conformal time $\tau$ again to show that the Friedmann and Raychaudhuri equations can be re-expressed as

$\frac{k c^{2}}{\mathcal{H}^{2}}=\Omega-1 \quad \text { and } \quad 2 \frac{d \mathcal{H}}{d \tau}+\mathcal{H}^{2}+k c^{2}=0$

From these derive the evolution equation for the density parameter $\Omega$ :

$\frac{d \Omega}{d \tau}=\mathcal{H} \Omega(\Omega-1)$

Plot the qualitative behaviour of $\Omega$ as a function of time relative to the expanding Einsteinde Sitter model with $\Omega=1$ (i.e., include curves initially with $\Omega>1$ and $\Omega<1$ ).

Paper 1, Section II, B

commentA flat $(k=0)$ homogeneous and isotropic universe with scale factor $a(t)$ is filled with a scalar field $\phi(t)$ with potential $V(\phi)$. Its evolution satisfies the Friedmann and scalar field equations,

$H^{2}=\frac{1}{3 M_{\mathrm{Pl}}^{2}}\left(\frac{1}{2} \dot{\phi}^{2}+c^{2} V(\phi)\right), \quad \ddot{\phi}+3 H \dot{\phi}+c^{2} \frac{d V}{d \phi}=0$

where $H(t)=\frac{\dot{a}}{a}$ is the Hubble parameter, $M_{\mathrm{Pl}}$ is the reduced Planck mass, and dots denote derivatives with respect to cosmic time $t$, e.g. $\dot{\phi} \equiv d \phi / d t$.

(a) Use these equations to derive the Raychaudhuri equation, expressed in the form:

$\dot{H}=-\frac{1}{2 M_{\mathrm{Pl}}^{2}} \dot{\phi}^{2}$

(b) Consider the following ansatz for the scalar field evolution,

$\phi(t)=\phi_{0} \ln \tanh (\lambda t)$

where $\lambda, \phi_{0}$ are constants. Find the specific cosmological solution,

$\begin{aligned} H(t) &=\lambda \frac{\phi_{0}^{2}}{M_{\mathrm{Pl}}^{2}} \operatorname{coth}(2 \lambda t) \\ a(t) &=a_{0}[\sinh (2 \lambda t)]^{\phi_{0}^{2} / 2 M_{\mathrm{Pl}}^{2}}, \quad a_{0} \text { constant. } \end{aligned}$

(c) Hence, show that the Hubble parameter can be expressed in terms of $\phi$ as

$H(\phi)=\lambda \frac{\phi_{0}^{2}}{M_{\mathrm{P} 1}^{2}} \cosh \left(\frac{\phi}{\phi_{0}}\right),$

and that the scalar field ansatz solution ( $\dagger$ ) requires the following form for the potential:

$V(\phi)=\frac{2 \lambda^{2} \phi_{0}^{2}}{c^{2}}\left[\left(\frac{3 \phi_{0}^{2}}{2 M_{\mathrm{Pl}}^{2}}-1\right) \cosh ^{2}\left(\frac{\phi}{\phi_{0}}\right)+1\right]$

(d) Assume that the given parameters in $V(\phi)$ are such that $2 / 3<\phi_{0}^{2} / M_{\mathrm{Pl}}^{2}<2$. Show that the asymptotic limit for the cosmological solution as $t \rightarrow 0$ exhibits decelerating power law evolution and that there is an accelerating solution as $t \rightarrow \infty$, that is,

$\begin{array}{lll} t \rightarrow 0, & \phi \rightarrow-\infty, & a(t) \sim t^{\phi_{0}^{2} / 2 M_{\mathrm{Pl}}^{2}} \\ t \rightarrow \infty, & \phi \rightarrow 0, & a(t) \sim \exp \left(\lambda \phi_{0}^{2} t / M_{\mathrm{Pl}}^{2}\right) . \end{array}$

Find the time $t_{\mathrm{acc}}$ at which the solution transitions from deceleration to acceleration.

Paper 2, Section I, B

(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}$