• # Paper 1, Section II, I

Let $k$ be an algebraically closed field.

(a) Let $X$ and $Y$ be varieties defined over $k$. Given a function $f: X \rightarrow Y$, define what it means for $f$ to be a morphism of varieties.

(b) If $X$ is an affine variety, show that the coordinate ring $A(X)$ coincides with the ring of regular functions on $X$. [Hint: You may assume a form of the Hilbert Nullstellensatz.]

(c) Now suppose $X$ and $Y$ are affine varieties. Show that if $X$ and $Y$ are isomorphic, then there is an isomorphism of $k$-algebras $A(X) \cong A(Y)$.

(d) Show that $Z\left(x^{2}-y^{3}\right) \subseteq \mathbb{A}^{2}$ is not isomorphic to $\mathbb{A}^{1}$.

comment
• # Paper 2, Section II, I

Let $k$ be an algebraically closed field of any characteristic.

(a) Define what it means for a variety $X$ to be non-singular at a point $P \in X$.

(b) Let $X \subseteq \mathbb{P}^{n}$ be a hypersurface $Z(f)$ for $f \in k\left[x_{0}, \ldots, x_{n}\right]$ an irreducible homogeneous polynomial. Show that the set of singular points of $X$ is $Z(I)$, where $I \subseteq$ $k\left[x_{0}, \ldots, x_{n}\right]$ is the ideal generated by $\partial f / \partial x_{0}, \ldots, \partial f / \partial x_{n} .$

(c) Consider the projective plane curve corresponding to the affine curve in $\mathbb{A}^{2}$ given by the equation

$x^{4}+x^{2} y^{2}+y^{2}+1=0 .$

Find the singular points of this projective curve if char $k \neq 2$. What goes wrong if char $k=2$ ?

comment
• # Paper 3, Section II, I

(a) Define what it means to give a rational map between algebraic varieties. Define a birational map.

(b) Let

$X=Z\left(y^{2}-x^{2}(x-1)\right) \subseteq \mathbb{A}^{2}$

Define a birational map from $X$ to $\mathbb{A}^{1}$. [Hint: Consider lines through the origin.]

(c) Let $Y \subseteq \mathbb{A}^{3}$ be the surface given by the equation

$x_{1}^{2} x_{2}+x_{2}^{2} x_{3}+x_{3}^{2} x_{1}=0 .$

Consider the blow-up $X \subseteq \mathbb{A}^{3} \times \mathbb{P}^{2}$ of $\mathbb{A}^{3}$ at the origin, i.e. the subvariety of $\mathbb{A}^{3} \times \mathbb{P}^{2}$ defined by the equations $x_{i} y_{j}=x_{j} y_{i}$ for $1 \leqslant i, with $y_{1}, y_{2}, y_{3}$ coordinates on $\mathbb{P}^{2}$. Let $\varphi: X \rightarrow \mathbb{A}^{3}$ be the projection and $E=\varphi^{-1}(0)$. Recall that the proper transform $\tilde{Y}$ of $Y$ is the closure of $\varphi^{-1}(Y) \backslash E$ in $X$. Give equations for $\tilde{Y}$, and describe the fibres of the morphism $\left.\varphi\right|_{\widetilde{Y}}: \widetilde{Y} \rightarrow Y$.

comment
• # Paper 4, Section II, I

(a) Let $X$ and $Y$ be non-singular projective curves over a field $k$ and let $\varphi: X \rightarrow Y$ be a non-constant morphism. Define the ramification degree $e_{P}$ of $\varphi$ at a point $P \in X$.

(b) Suppose char $k \neq 2$. Let $X=Z(f)$ be the plane cubic with $f=x_{0} x_{2}^{2}-x_{1}^{3}+x_{0}^{2} x_{1}$, and let $Y=\mathbb{P}^{1}$. Explain how the projection

$\left(x_{0}: x_{1}: x_{2}\right) \mapsto\left(x_{0}: x_{1}\right)$

defines a morphism $\varphi: X \rightarrow Y$. Determine the degree of $\varphi$ and the ramification degrees $e_{P}$ for all $P \in X$.

(c) Let $X$ be a non-singular projective curve and let $P \in X$. Show that there is a non-constant rational function on $X$ which is regular on $X \backslash\{P\}$.

comment

• # Paper 1, Section II, I

Let $X$ be a topological space and let $x_{0}$ and $x_{1}$ be points of $X$.

(a) Explain how a path $u:[0,1] \rightarrow X$ from $x_{0}$ to $x_{1}$ defines a map $u_{\sharp}: \pi_{1}\left(X, x_{0}\right) \rightarrow$ $\pi_{1}\left(X, x_{1}\right)$.

(b) Prove that $u_{\sharp}$ is an isomorphism of groups.

(c) Let $\alpha, \beta:\left(S^{1}, 1\right) \rightarrow\left(X, x_{0}\right)$ be based loops in $X$. Suppose that $\alpha, \beta$ are homotopic as unbased maps, i.e. the homotopy is not assumed to respect basepoints. Show that the corresponding elements of $\pi_{1}\left(X, x_{0}\right)$ are conjugate.

(d) Take $X$ to be the 2-torus $S^{1} \times S^{1}$. If $\alpha, \beta$ are homotopic as unbased loops as in part (c), then exhibit a based homotopy between them. Interpret this fact algebraically.

(e) Exhibit a pair of elements in the fundamental group of $S^{1} \vee S^{1}$ which are homotopic as unbased loops but not as based loops. Justify your answer.

comment
• # Paper 2, Section II, I

(a) (i) Define the push-out of the following diagram of groups.

When is a push-out a free product with amalgamation?

(ii) State the Seifert-van Kampen theorem.

(b) Let $X=\mathbb{R} P^{2} \vee S^{1}$ (recalling that $\mathbb{R} P^{2}$ is the real projective plane), and let $x \in X$.

(i) Compute the fundamental group $\pi_{1}(X, x)$ of the space $X$.

(ii) Show that there is a surjective homomorphism $\phi: \pi_{1}(X, x) \rightarrow S_{3}$, where $S_{3}$ is the symmetric group on three elements.

(c) Let $\widehat{X} \rightarrow X$ be the covering space corresponding to the kernel of $\phi$.

(i) Draw $\widehat{X}$and justify your answer carefully.

(ii) Does $\widehat{X}$retract to a graph? Justify your answer briefly.

(iii) Does $\widehat{X}$deformation retract to a graph? Justify your answer briefly.

comment
• # Paper 3, Section II, I

The $n$-torus is the product of $n$ circles:

$T^{n}=\underbrace{S^{1} \times \ldots \times S^{1}}_{n \text { times }} .$

For all $n \geqslant 1$ and $0 \leqslant k \leqslant n$, compute $H_{k}\left(T^{n}\right)$.

[You may assume that relevant spaces are triangulable, but you should state carefully any version of any theorem that you use.]

comment
• # Paper 4, Section II, I

Recall that $\mathbb{R} P^{n}$ is real projective $n$-space, the quotient of $S^{n}$ obtained by identifying antipodal points. Consider the standard embedding of $S^{n}$ as the unit sphere in $\mathbb{R}^{n+1}$.

(a) For $n$ odd, show that there exists a continuous map $f: S^{n} \rightarrow S^{n}$ such that $f(x)$ is orthogonal to $x$, for all $x \in S^{n}$.

(b) Exhibit a triangulation of $\mathbb{R} P^{n}$.

(c) Describe the map $H_{n}\left(S^{n}\right) \rightarrow H_{n}\left(S^{n}\right)$ induced by the antipodal map, justifying your answer.

(d) Show that, for $n$ even, there is no continuous map $f: S^{n} \rightarrow S^{n}$ such that $f(x)$ is orthogonal to $x$ for all $x \in S^{n}$.

comment

• # Paper 1, Section II, $22 F$

Consider a sequence $f_{n}: \mathbb{R} \rightarrow \mathbb{R}$ of measurable functions converging pointwise to a function $f: \mathbb{R} \rightarrow \mathbb{R}$. The Lebesgue measure is denoted by $\lambda$.

(a) Consider a Borel set $A \subset \mathbb{R}$ with finite Lebesgue measure $\lambda(A)<+\infty$. Define for $k, n \geqslant 1$ the sets

$E_{n}^{(k)}:=\bigcap_{m \geqslant n}\left\{x \in A|| f_{m}(x)-f(x) \mid \leqslant \frac{1}{k}\right\}$

Prove that for any $k, n \geqslant 1$, one has $E_{n}^{(k)} \subset E_{n+1}^{(k)}$ and $E_{n}^{(k+1)} \subset E_{n}^{(k)}$. Prove that for any $k \geqslant 1, A=\cup_{n \geqslant 1} E_{n}^{(k)}$.

(b) Consider a Borel set $A \subset \mathbb{R}$ with finite Lebesgue measure $\lambda(A)<+\infty$. Prove that for any $\varepsilon>0$, there is a Borel set $A_{\varepsilon} \subset A$ for which $\lambda\left(A \backslash A_{\varepsilon}\right) \leqslant \varepsilon$ and such that $f_{n}$ converges to $f$ uniformly on $A_{\varepsilon}$ as $n \rightarrow+\infty$. Is the latter still true when $\lambda(A)=+\infty$ ?

(c) Assume additionally that $f_{n} \in L^{p}(\mathbb{R})$ for some $p \in(1,+\infty]$, and there exists an $M \geqslant 0$ for which $\left\|f_{n}\right\|_{L^{p}(\mathbb{R})} \leqslant M$ for all $n \geqslant 1$. Prove that $f \in L^{p}(\mathbb{R})$.

(d) Let $f_{n}$ and $f$ be as in part (c). Consider a Borel set $A \subset \mathbb{R}$ with finite Lebesgue measure $\lambda(A)<+\infty$. Prove that $f_{n}, f$ are integrable on $A$ and $\int_{A} f_{n} d \lambda \rightarrow \int_{A} f d \lambda$ as $n \rightarrow \infty$. Deduce that $f_{n}$ converges weakly to $f$ in $L^{p}(\mathbb{R})$ when $p<+\infty$. Does the convergence have to be strong?

comment
• # Paper 3, Section II, F

Denote by $C_{0}\left(\mathbb{R}^{n}\right)$ the space of continuous complex-valued functions on $\mathbb{R}^{n}$ converging to zero at infinity. Denote by $\mathcal{F} f(\xi)=\int_{\mathbb{R}^{n}} e^{-2 i \pi x \cdot \xi} f(x) d x$ the Fourier transform of $f \in L^{1}\left(\mathbb{R}^{n}\right)$.

(i) Prove that the image of $L^{1}\left(\mathbb{R}^{n}\right)$ under $\mathcal{F}$ is included and dense in $C_{0}\left(\mathbb{R}^{n}\right)$, and that $\mathcal{F}: L^{1}\left(\mathbb{R}^{n}\right) \rightarrow C_{0}\left(\mathbb{R}^{n}\right)$ is injective. [Fourier inversion can be used without proof when properly stated.]

(ii) Calculate the Fourier transform of $\chi_{[a, b]}$, the characteristic function of $[a, b] \subset \mathbb{R}$.

(iii) Prove that $g_{n}:=\chi_{[-n, n]} * \chi_{[-1,1]}$ belongs to $C_{0}(\mathbb{R})$ and is the Fourier transform of a function $h_{n} \in L^{1}(\mathbb{R})$, which you should determine.

(iv) Using the functions $h_{n}, g_{n}$ and the open mapping theorem, deduce that the Fourier transform is not surjective from $L^{1}(\mathbb{R})$ to $C_{0}(\mathbb{R})$.

comment
• # Paper 4, Section II, $22 F$

Consider $\mathbb{R}^{n}$ with the Lebesgue measure. Denote by $\mathcal{F} f(\xi)=\int_{\mathbb{R}^{n}} e^{-2 i \pi x \cdot \xi} f(x) d x$ the Fourier transform of $f \in L^{1}\left(\mathbb{R}^{n}\right)$ and by $\hat{f}$ the Fourier-Plancherel transform of $f \in L^{2}\left(\mathbb{R}^{n}\right)$. Let $\chi_{R}(\xi):=\left(1-\frac{|\xi|}{R}\right) \chi_{|\xi| \leqslant R}$ for $R>0$ and define for $s \in \mathbb{R}_{+}$

$H^{s}\left(\mathbb{R}^{n}\right):=\left\{f \in L^{2}\left(\mathbb{R}^{n}\right) \mid\left(1+|\cdot|^{2}\right)^{s / 2} \hat{f}(\cdot) \in L^{2}\left(\mathbb{R}^{n}\right)\right\}$

(i) Prove that $H^{s}\left(\mathbb{R}^{n}\right)$ is a vector subspace of $L^{2}\left(\mathbb{R}^{n}\right)$, and is a Hilbert space for the inner product $\langle f, g\rangle:=\int_{\mathbb{R}^{n}}\left(1+|\xi|^{2}\right)^{s} \hat{f}(\xi) \overline{\hat{g}(\xi)} d \xi$, where $\bar{z}$ denotes the complex conjugate of $z \in \mathbb{C}$.

(ii) Construct a function $f \in H^{s}(\mathbb{R}), s \in(0,1 / 2)$, that is not almost everywhere equal to a continuous function.

(iii) For $f \in L^{1}\left(\mathbb{R}^{n}\right)$, prove that $F_{R}: x \mapsto \int_{\mathbb{R}^{n}} \mathcal{F} f(\xi) \chi_{R}(\xi) e^{2 i \pi x \cdot \xi} d \xi$ is a well-defined function and that $F_{R} \in L^{1}\left(\mathbb{R}^{n}\right)$ converges to $f$ in $L^{1}\left(\mathbb{R}^{n}\right)$ as $R \rightarrow+\infty$.

[Hint: Prove that $F_{R}=K_{R} * f$ where $K_{R}$ is an approximation of the unit as $R \rightarrow+\infty .]$

(iv) Deduce that if $f \in L^{1}\left(\mathbb{R}^{n}\right)$ and $\left(1+|\cdot|^{2}\right)^{s / 2} \mathcal{F} f(\cdot) \in L^{2}\left(\mathbb{R}^{n}\right)$ then $f \in H^{s}\left(\mathbb{R}^{n}\right)$.

[Hint: Prove that: (1) there is a sequence $R_{k} \rightarrow+\infty$ such that $K_{R_{k}} * f$ converges to $f$ almost everywhere; (2) $K_{R} * f$ is uniformly bounded in $L^{2}\left(\mathbb{R}^{n}\right)$ as $R \rightarrow+\infty$.]

comment

• # Paper 1, Section II, C

A one-dimensional lattice has $N$ sites with lattice spacing $a$. In the tight-binding approximation, the Hamiltonian describing a single electron is given by

$H=E_{0} \sum_{n}|n\rangle\langle n|-J \sum_{n}(|n\rangle\langle n+1|+| n+1\rangle\langle n|)$

where $|n\rangle$ is the normalised state of the electron localised on the $n^{\text {th }}$lattice site. Using periodic boundary conditions $|N+1\rangle \equiv|1\rangle$, solve for the spectrum of this Hamiltonian to derive the dispersion relation

$E(k)=E_{0}-2 J \cos (k a)$

Define the Brillouin zone. Determine the number of states in the Brillouin zone.

Calculate the velocity $v$ and effective mass $m^{\star}$ of the particle. For which values of $k$ is the effective mass negative?

In the semi-classical approximation, derive an expression for the time-dependence of the position of the electron in a constant electric field.

Describe how the concepts of metals and insulators arise in the model above.

comment
• # Paper 2, Section II, C

Give an account of the variational method for establishing an upper bound on the ground-state energy of a Hamiltonian $H$ with a discrete spectrum $H|n\rangle=E_{n}|n\rangle$, where $E_{n} \leqslant E_{n+1}, n=0,1,2 \ldots$

A particle of mass $m$ moves in the three-dimensional potential

$V(r)=-\frac{A e^{-\mu r}}{r}$

where $A, \mu>0$ are constants and $r$ is the distance to the origin. Using the normalised variational wavefunction

$\psi(r)=\sqrt{\frac{\alpha^{3}}{\pi}} e^{-\alpha r}$

show that the expected energy is given by

$E(\alpha)=\frac{\hbar^{2} \alpha^{2}}{2 m}-\frac{4 A \alpha^{3}}{(\mu+2 \alpha)^{2}}$

Explain why there is necessarily a bound state when $\mu. What can you say about the existence of a bound state when $\mu \geqslant A m / \hbar^{2}$ ?

[Hint: The Laplacian in spherical polar coordinates is

$\left.\nabla^{2}=\frac{1}{r^{2}} \frac{\partial}{\partial r}\left(r^{2} \frac{\partial}{\partial r}\right)+\frac{1}{r^{2} \sin \theta} \frac{\partial}{\partial \theta}\left(\sin \theta \frac{\partial}{\partial \theta}\right)+\frac{1}{r^{2} \sin ^{2} \theta} \frac{\partial^{2}}{\partial \phi^{2}}\right]$

comment
• # Paper 3, Section II, C

A particle of mass $m$ and charge $q$ moving in a uniform magnetic field $\mathbf{B}=\boldsymbol{\nabla} \times \mathbf{A}=$ $(0,0, B)$ is described by the Hamiltonian

$H=\frac{1}{2 m}(\mathbf{p}-q \mathbf{A})^{2}$

where $\mathbf{p}$ is the canonical momentum, which obeys $\left[x_{i}, p_{j}\right]=i \hbar \delta_{i j}$. The mechanical momentum is defined as $\boldsymbol{\pi}=\mathbf{p}-q \mathbf{A}$. Show that

$\left[\pi_{x}, \pi_{y}\right]=i q \hbar B$

Define

$a=\frac{1}{\sqrt{2 q \hbar B}}\left(\pi_{x}+i \pi_{y}\right) \quad \text { and } \quad a^{\dagger}=\frac{1}{\sqrt{2 q \hbar B}}\left(\pi_{x}-i \pi_{y}\right) \text {. }$

Derive the commutation relation obeyed by $a$ and $a^{\dagger}$. Write the Hamiltonian in terms of $a$ and $a^{\dagger}$ and hence solve for the spectrum.

In symmetric gauge, states in the lowest Landau level with $k_{z}=0$ have wavefunctions

$\psi(x, y)=(x+i y)^{M} e^{-q B r^{2} / 4 \hbar}$

where $r^{2}=x^{2}+y^{2}$ and $M$ is a positive integer. By considering the profiles of these wavefunctions, estimate how many lowest Landau level states can fit in a disc of radius $R$.

comment
• # Paper 4, Section II, C

(a) In one dimension, a particle of mass $m$ is scattered by a potential $V(x)$ where $V(x) \rightarrow 0$ as $|x| \rightarrow \infty$. For wavenumber $k>0$, the incoming $(\mathcal{I})$ and outgoing $(\mathcal{O})$ asymptotic plane wave states with positive $(+)$ and negative $(-)$ parity are given by

$\begin{array}{rr} \mathcal{I}_{+}(x)=e^{-i k|x|}, & \mathcal{I}_{-}(x)=\operatorname{sign}(x) e^{-i k|x|} \\ \mathcal{O}_{+}(x)=e^{+i k|x|}, & \mathcal{O}_{-}(x)=-\operatorname{sign}(x) e^{+i k|x|} \end{array}$

(i) Explain how this basis may be used to define the $S$-matrix,

$\mathcal{S}^{P}=\left(\begin{array}{cc} S_{++} & S_{+-} \\ S_{-+} & S_{--} \end{array}\right)$

(ii) For what choice of potential would you expect $S_{+-}=S_{-+}=0$ ? Why?

(b) The potential $V(x)$ is given by

$V(x)=V_{0}[\delta(x-a)+\delta(x+a)]$

with $V_{0}$ a constant.

(i) Show that

$S_{--}(k)=e^{-2 i k a}\left[\frac{\left(2 k-i U_{0}\right) e^{i k a}+i U_{0} e^{-i k a}}{\left(2 k+i U_{0}\right) e^{-i k a}-i U_{0} e^{i k a}}\right]$

where $U_{0}=2 m V_{0} / \hbar^{2}$. Verify that $\left|S_{--}\right|^{2}=1$. Explain the physical meaning of this result.

(ii) For $V_{0}<0$, by considering the poles or zeros of $S_{--}(k)$, show that there exists one bound state of negative parity if $a U_{0}<-1$.

(iii) For $V_{0}>0$ and $a U_{0} \gg 1$, show that $S_{--}(k)$ has a pole at

$k a=\pi+\alpha-i \gamma$

where $\alpha$ and $\gamma$ are real and

$\alpha=-\frac{\pi}{a U_{0}}+O\left(\frac{1}{\left(a U_{0}\right)^{2}}\right) \quad \text { and } \quad \gamma=\left(\frac{\pi}{a U_{0}}\right)^{2}+O\left(\frac{1}{\left(a U_{0}\right)^{3}}\right)$

Explain the physical significance of this result.

comment

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

(a) Define a continuous time Markov chain $X$ with infinitesimal generator $Q$ and jump chain $Y$.

(b) Let $i$ be a transient state of a continuous-time Markov chain $X$ with $X(0)=i$. Show that the time spent in state $i$ has an exponential distribution and explicitly state its parameter.

[You may use the fact that if $S \sim \operatorname{Exp}(\lambda)$, then $\mathbb{E}\left[e^{\theta S}\right]=\lambda /(\lambda-\theta)$ for $\theta<\lambda$.]

(c) Let $X$ be an asymmetric random walk in continuous time on the non-negative integers with reflection at 0 , so that

$q_{i, j}= \begin{cases}\lambda & \text { if } \quad j=i+1, i \geqslant 0 \\ \mu & \text { if } \quad j=i-1, i \geqslant 1\end{cases}$

Suppose that $X(0)=0$ and $\lambda>\mu$. Show that for all $r \geqslant 1$, the total time $T_{r}$ spent in state $r$ is exponentially distributed with parameter $\lambda-\mu$.

Assume now that $X(0)$ has some general distribution with probability generating function $G$. Find the expected amount of time spent at 0 in terms of $G$.

comment
• # Paper 2, Section II, K

(a) Give the definition of a Poisson process on $\mathbb{R}_{+}$. Let $X$ be a Poisson process on $\mathbb{R}_{+}$. Show that conditional on $\left\{X_{t}=n\right\}$, the jump times $J_{1}, \ldots, J_{n}$ have joint density function

$f\left(t_{1}, \ldots, t_{n}\right)=\frac{n !}{t^{n}} \mathbf{1}\left(0 \leqslant t_{1} \leqslant \ldots \leqslant t_{n} \leqslant t\right)$

where $\boldsymbol{I}(A)$ is the indicator of the set $A$.

(b) Let $N$ be a Poisson process on $\mathbb{R}_{+}$with intensity $\lambda$ and jump times $\left\{J_{k}\right\}$. If $g: \mathbb{R}_{+} \rightarrow \mathbb{R}$ is a real function, we define for all $t>0$

$\mathcal{R}(g)[0, t]=\left\{g\left(J_{k}\right): k \in \mathbb{N}, J_{k} \leqslant t\right\}$

Show that for all $t>0$ the following is true

$\mathbb{P}(0 \in \mathcal{R}(g)[0, t])=1-\exp \left(-\lambda \int_{0}^{t} \mathbf{I}(g(s)=0) d s\right)$

comment
• # Paper 3, Section II, K

(a) Define the Moran model and Kingman's $n$-coalescent. Define Kingman's infinite coalescent.

Show that Kingman's infinite coalescent comes down from infinity. In other words, with probability one, the number of blocks of $\Pi_{t}$ is finite at any time $t>0$.

(b) Give the definition of a renewal process.

Let $\left(X_{i}\right)$ denote the sequence of inter-arrival times of the renewal process $N$. Suppose that $\mathbb{E}\left[X_{1}\right]>0$.

Prove that $\mathbb{P}(N(t) \rightarrow \infty$ as $t \rightarrow \infty)=1$.

Prove that $\mathbb{E}\left[e^{\theta N(t)}\right]<\infty$ for some strictly positive $\theta$.

[Hint: Consider the renewal process with inter-arrival times $X_{k}^{\prime}=\varepsilon \mathbf{1}\left(X_{k} \geqslant \varepsilon\right)$ for some suitable $\varepsilon>0$.]

comment
• # Paper 4, Section II, $26 K$

(a) Give the definition of an $M / M / 1$ queue. Prove that if $\lambda$ is the arrival rate and $\mu$ the service rate and $\lambda<\mu$, then the length of the queue is a positive recurrent Markov chain. What is the equilibrium distribution?

If the queue is in equilibrium and a customer arrives at some time $t$, what is the distribution of the waiting time (time spent waiting in the queue plus service time)?

(b) We now modify the above queue: on completion of service a customer leaves with probability $\delta$, or goes to the back of the queue with probability $1-\delta$. Find the distribution of the total time a customer spends being served.

Hence show that equilibrium is possible if $\lambda<\delta \mu$ and find the stationary distribution.

Show that, in equilibrium, the departure process is Poisson.

[You may use relevant theorems provided you state them clearly.]

comment

• # Paper 2, Section II, E

Consider the function

$f_{\nu}(x) \equiv \frac{1}{2 \pi} \int_{C} \exp [-i x \sin z+i \nu z] d z$

where the contour $C$ is the boundary of the half-strip $\{z:-\pi<\operatorname{Re} z<\pi$ and $\operatorname{Im} z>0\}$, taken anti-clockwise.

Use integration by parts and the method of stationary phase to:

(i) Obtain the leading term for $f_{\nu}(x)$ coming from the vertical lines $z=\pm \pi+i y(0<$ $y<+\infty)$ for large $x>0$.

(ii) Show that the leading term in the asymptotic expansion of the function $f_{\nu}(x)$ for large positive $x$ is

$\sqrt{\frac{2}{\pi x}} \cos \left(x-\frac{1}{2} \nu \pi-\frac{\pi}{4}\right)$

and obtain an estimate for the remainder as $O\left(x^{-a}\right)$ for some $a$ to be determined.

comment
• # Paper 3, Section II, E

Consider the integral representation for the modified Bessel function

$I_{0}(x)=\frac{1}{2 \pi i} \oint_{C} t^{-1} \exp \left[\frac{i x}{2}\left(t-\frac{1}{t}\right)\right] d t$

where $C$ is a simple closed contour containing the origin, taken anti-clockwise.

Use the method of steepest descent to determine the full asymptotic expansion of $I_{0}(x)$ for large real positive $x .$

comment
• # Paper 4, Section II, E

Consider solutions to the equation

$\frac{d^{2} y}{d x^{2}}=\left(\frac{1}{4}+\frac{\mu^{2}-\frac{1}{4}}{x^{2}}\right) y$

of the form

$y(x)=\exp \left[S_{0}(x)+S_{1}(x)+S_{2}(x)+\ldots\right]$

with the assumption that, for large positive $x$, the function $S_{j}(x)$ is small compared to $S_{j-1}(x)$ for all $j=1,2 \ldots$

Obtain equations for the $S_{j}(x), j=0,1,2 \ldots$, which are formally equivalent to ( $)$. Solve explicitly for $S_{0}$ and $S_{1}$. Show that it is consistent to assume that $S_{j}(x)=c_{j} x^{-(j-1)}$ for some constants $c_{j}$. Give a recursion relation for the $c_{j}$.

Deduce that there exist two linearly independent solutions to $(\star)$ with asymptotic expansions as $x \rightarrow+\infty$ of the form

$y_{\pm}(x) \sim e^{\pm x / 2}\left(1+\sum_{j=1}^{\infty} A_{j}^{\pm} x^{-j}\right)$

Determine a recursion relation for the $A_{j}^{\pm}$. Compute $A_{1}^{\pm}$and $A_{2}^{\pm}$.

comment

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

(a) Prove that every regular language is also a context-free language (CFL).

(b) Show that, for any fixed $n>0$, the set of regular expressions over the alphabet $\left\{a_{1}, \ldots, a_{n}\right\}$ is a CFL, but not a regular language.

comment
• # Paper 1, Section II, $11 H$

(a) Give an encoding to integers of all deterministic finite-state automata (DFAs). [Here the alphabet of each such DFA is always taken from the set $\{0,1, \ldots\}$, and the states for each such DFA are always taken from the set $\left.\left\{q_{0}, q_{1}, \ldots\right\} .\right]$

(b) Show that the set of codes for which the corresponding DFA $D_{n}$ accepts a finite language is recursive. Moreover, if the language $\mathcal{L}\left(D_{n}\right)$ is finite, show that we can compute its size $\left|\mathcal{L}\left(D_{n}\right)\right|$ from $n$.

comment
• # Paper 2, Section I, $4 \mathrm{H}$

(a) Give explicit examples, with justification, of a language over some finite alphabet $\Sigma$ which is:

(i) context-free, but not regular;

(ii) recursive, but not context-free.

(b) Give explicit examples, with justification, of a subset of $\mathbb{N}$ which is:

(i) recursively enumerable, but not recursive;

(ii) neither recursively enumerable, nor having recursively enumerable complement in $\mathbb{N}$.

comment
• # Paper 3, Section I, 4H

(a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Give an example, with justification, of a context-free language (CFL) which is not defined by any CFG in CNF.

(b) Show that the intersection of two CFLs need not be a CFL.

(c) Let $L$ be a CFL over an alphabet $\Sigma$. Show that $\Sigma^{*} \backslash L$ need not be a CFL.

comment
• # Paper 3, Section II, $11 \mathrm{H}$ Automata and formal languages

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

(b) State the $s-m-n$ theorem, and use it to prove that a set $X \subseteq \mathbb{N}$ is r.e. if and only if $X \leqslant_{m} \mathbb{K}$.

(c) Consider the sets of integers $P, Q \subseteq \mathbb{N}$ defined via

\begin{aligned} &P:=\left\{n \in \mathbb{N} \mid n \text { codes a program and } W_{n} \text { is finite }\right\} \\ &Q:=\left\{n \in \mathbb{N} \mid n \text { codes a program and } W_{n} \text { is recursive }\right\} \end{aligned}

Show that $P \leqslant \leqslant_{m} Q$.

comment
• # Paper 4, Section I, $4 \mathrm{H}$

(a) Describe the process for converting a deterministic finite-state automaton $D$ into a regular expression $R$ defining the same language, $\mathcal{L}(D)=\mathcal{L}(R)$. [You need only outline the steps, without proof, but you should clearly define all terminology you introduce.]

(b) Consider the language $L$ over the alphabet $\{0,1\}$ defined via

$L:=\left\{w 01^{n} \mid w \in\{0,1\}^{*}, n \in \mathbb{K}\right\} \cup\{1\}^{*} .$

Show that $L$ satisfies the pumping lemma for regular languages but is not a regular language itself.

comment

• # Paper 1, Section I, E

Consider a Lagrangian system with Lagrangian $L\left(x_{A}, \dot{x}_{A}, t\right)$, where $A=1, \ldots, 3 N$, and constraints

$f_{\alpha}\left(x_{A}, t\right)=0, \quad \alpha=1, \ldots, 3 N-n .$

Use the method of Lagrange multipliers to show that this is equivalent to a system with Lagrangian $\mathcal{L}\left(q_{i}, \dot{q}_{i}, t\right) \equiv L\left(x_{A}\left(q_{i}, t\right), \dot{x}_{A}\left(q_{i}, \dot{q}_{i}, t\right), t\right)$, where $i=1, \ldots, n$, and $q_{i}$ are coordinates on the surface of constraints.

Consider a bead of unit mass in $\mathbb{R}^{2}$ constrained to move (with no potential) on a wire given by an equation $y=f(x)$, where $(x, y)$ are Cartesian coordinates. Show that the Euler-Lagrange equations take the form

$\frac{d}{d t} \frac{\partial \mathcal{L}}{\partial \dot{x}}=\frac{\partial \mathcal{L}}{\partial x}$

for some $\mathcal{L}=\mathcal{L}(x, \dot{x})$ which should be specified. Find one first integral of the EulerLagrange equations, and thus show that

$t=F(x)$

where $F(x)$ should be given in the form of an integral.

[Hint: You may assume that the Euler-Lagrange equations hold in all coordinate systems.]

comment
• # Paper 2, Section I, E

Derive the Lagrange equations from the principle of stationary action

$S[q]=\int_{t_{0}}^{t_{1}} \mathcal{L}\left(q_{i}(t), \dot{q}_{i}(t), t\right) d t, \quad \delta S=0$

where the end points $q_{i}\left(t_{0}\right)$ and $q_{i}\left(t_{1}\right)$ are fixed.

Let $\phi$ and $\mathbf{A}$ be a scalar and a vector, respectively, depending on $\mathbf{r}=(x, y, z)$. Consider the Lagrangian

$\mathcal{L}=\frac{m \dot{\mathbf{r}}^{2}}{2}-(\phi-\dot{\mathbf{r}} \cdot \mathbf{A})$

and show that the resulting Euler-Lagrange equations are invariant under the transformations

$\phi \rightarrow \phi+\alpha \frac{\partial F}{\partial t}, \quad \mathbf{A} \rightarrow \mathbf{A}+\nabla F,$

where $F=F(\mathbf{r}, t)$ is an arbitrary function, and $\alpha$ is a constant which should be determined.

comment
• # Paper 2, Section II, E

Show that an object's inertia tensor about a point displaced from the centre of mass by a vector $\mathbf{c}$ is given by

$\left(I_{\mathbf{c}}\right)_{a b}=\left(I_{0}\right)_{a b}+M\left(|\mathbf{c}|^{2} \delta_{a b}-c_{a} c_{b}\right),$

where $M$ is the total mass of the object, and $\left(I_{0}\right)_{a b}$ is the inertia tensor about the centre of mass.

Find the inertia tensor of a cube of uniform density, with edge of length $L$, about one of its vertices.

comment
• # Paper 3, Section I, E

Define an integrable system with $2 n$-dimensional phase space. Define angle-action variables.

Consider a two-dimensional phase space with the Hamiltonian

$H=\frac{p^{2}}{2 m}+\frac{1}{2} q^{2 k}$

where $k$ is a positive integer and the mass $m=m(t)$ changes slowly in time. Use the fact that the action is an adiabatic invariant to show that the energy varies in time as $m^{c}$, where $c$ is a constant which should be found.

comment
• # Paper 4, Section I, E

Consider the Poisson bracket structure on $\mathbb{R}^{3}$ given by

$\{x, y\}=z, \quad\{y, z\}=x, \quad\{z, x\}=y$

and show that $\left\{f, \rho^{2}\right\}=0$, where $\rho^{2}=x^{2}+y^{2}+z^{2}$ and $f: \mathbb{R}^{3} \rightarrow \mathbb{R}$ is any polynomial function on $\mathbb{R}^{3}$.

Let $H=\left(A x^{2}+B y^{2}+C z^{2}\right) / 2$, where $A, B, C$ are positive constants. Find the explicit form of Hamilton's equations

$\dot{\mathbf{r}}=\{\mathbf{r}, H\}, \quad \text { where } \quad \mathbf{r}=(x, y, z)$

Find a condition on $A, B, C$ such that the oscillation described by

$x=1+\alpha(t), \quad y=\beta(t), \quad z=\gamma(t)$

is linearly unstable, where $\alpha(t), \beta(t), \gamma(t)$ are small.

comment
• # Paper 4, Section II, $14 \mathrm{E}$

Explain how geodesics of a Riemannian metric

$g=g_{a b}\left(x^{c}\right) d x^{a} d x^{b}$

arise from the kinetic Lagrangian

$\mathcal{L}=\frac{1}{2} g_{a b}\left(x^{c}\right) \dot{x}^{a} \dot{x}^{b}$

where $a, b=1, \ldots, n$.

Find geodesics of the metric on the upper half plane

$\Sigma=\left\{(x, y) \in \mathbb{R}^{2}, y>0\right\}$

with the metric

$g=\frac{d x^{2}+d y^{2}}{y^{2}}$

and sketch the geodesic containing the points $(2,3)$ and $(10,3)$.

[Hint: Consider $d y / d x .]$

comment

• # Paper 1, Section I, G

Let $C$ be a binary code of length $n$. Define the following decoding rules: (i) ideal observer, (ii) maximum likelihood, (iii) minimum distance.

Let $p$ denote the probability that a digit is mistransmitted and suppose $p<1 / 2$. Prove that maximum likelihood and minimum distance decoding agree.

Suppose codewords 000 and 111 are sent with probabilities $4 / 5$ and $1 / 5$ respectively with error probability $p=1 / 4$. If we receive 110 , how should it be decoded according to the three decoding rules above?

comment
• # Paper 1, Section II, G

Let $C$ be a binary linear code. Explain what it means for $C$ to have length $n$ and $\operatorname{rank} k$. Explain what it means for a codeword of $C$ to have weight $j$.

Suppose $C$ has length $n$, rank $k$, and $A_{j}$ codewords of weight $j$. The weight enumerator polynomial of $C$ is given by

$W_{C}(s, t)=\sum_{j=0}^{n} A_{j} s^{j} t^{n-j}$

What is $W_{C}(1,1) ?$ Prove that $W_{C}(s, t)=W_{C}(t, s)$ if and only if $W_{C}(1,0)=1$.

Define the dual code $C^{\perp}$ of $C$.

(i) Let $\mathbf{y} \in \mathbb{F}_{2}^{n}$. Show that

$\sum_{\mathbf{x} \in C}(-1)^{\mathbf{x} \cdot \mathbf{y}}= \begin{cases}2^{k}, & \text { if } \mathbf{y} \in C^{\perp} \\ 0, & \text { otherwise }\end{cases}$

(ii) Extend the definition of weight to give a weight $w(\mathbf{y})$ for $\mathbf{y} \in \mathbb{F}_{2}^{n}$. Suppose that for $t$ real and all $\mathbf{x} \in C$

$\sum_{\mathbf{y} \in \mathbb{F}_{2}^{n}} t^{w(\mathbf{y})}(-1)^{\mathbf{x} \cdot \mathbf{y}}=(1-t)^{w(\mathbf{x})}(1+t)^{n-w(\mathbf{x})}$

For $s$ real, by evaluating

$\sum_{\mathbf{x} \in C}\left(\sum_{\mathbf{y} \in \mathbb{F}_{2}^{n}}(-1)^{\mathbf{x} \cdot \mathbf{y}}\left(\frac{s}{t}\right)^{w(\mathbf{y})}\right)$

in two different ways, show that

$W_{C^{\perp}}(s, t)=2^{-k} W_{C}(t-s, t+s) .$

comment
• # Paper 2, Section I, G

Prove 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 II, G

Define the entropy, $H(X)$, of a random variable $X$. State and prove Gibbs' inequality.

Hence, or otherwise, show that $H\left(p_{1}, p_{2}, p_{3}\right) \leqslant H\left(p_{1}, 1-p_{1}\right)+\left(1-p_{1}\right)$ and determine when equality occurs.

Show that the Discrete Memoryless Channel with channel matrix

$\left(\begin{array}{ccc} 1-\alpha-\beta & \alpha & \beta \\ \alpha & 1-\alpha-\beta & \beta \end{array}\right)$

has capacity $C=(1-\beta)(1-\log (1-\beta))+(1-\alpha-\beta) \log (1-\alpha-\beta)+\alpha \log \alpha$.

comment
• # Paper 3, Section I, G

Find and describe all binary cyclic codes of length 7 . Pair each code with its dual code. Justify your answer.

comment
• # Paper 4, Section I, G

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

Give a simple example of how the system is vulnerable to a homomorphism attack.

Describe the El-Gamal signature scheme and explain how this can defeat a homomorphism attack.

comment

• # Paper 1, Section I, C

In a homogeneous and isotropic universe, describe the relative displacement $\mathbf{r}(t)$ of two galaxies in terms of a scale factor $a(t)$. Show how the relative velocity $\mathbf{v}(t)$ of these galaxies is given by the relation $\mathbf{v}(t)=H(t) \mathbf{r}(t)$, where you should specify $H(t)$ in terms of $a(t)$.

From special relativity, the Doppler shift of light emitted by a particle moving away radially with speed $v$ can be approximated by

$\frac{\lambda_{0}}{\lambda_{\mathrm{e}}}=\sqrt{\frac{1+v / c}{1-v / c}}=1+\frac{v}{c}+\mathcal{O}\left(\frac{v^{2}}{c^{2}}\right)$

where $\lambda_{e}$ is the wavelength of emitted light and $\lambda_{0}$ is the observed wavelength. For the observed light from distant galaxies in a homogeneous and isotropic expanding universe, show that the redshift defined by $1+z \equiv \lambda_{0} / \lambda_{\mathrm{e}}$ is given by

$1+z=\frac{a\left(t_{0}\right)}{a\left(t_{\mathrm{e}}\right)}$

where $t_{\mathrm{e}}$ is the time of emission and $t_{0}$ is the observation time.

comment
• # Paper 1, Section II, C

The evolution of a flat $(k=0)$ homogeneous and isotropic universe with scale factor $a(t)$, mass density $\rho(t)$ and pressure $P(t)$ obeys the Friedmann and energy conservation equations

$\begin{array}{r} H^{2}(t)=\left(\frac{\dot{a}}{a}\right)^{2}=\frac{8 \pi G}{3} \rho+\frac{\Lambda c^{2}}{3} \\ \dot{\rho}=-3 \frac{\dot{a}}{a}\left(\rho+P / c^{2}\right) \end{array}$

where $H(t)$ is the Hubble parameter (observed today $t=t_{0}$ with value $H_{0}=H\left(t_{0}\right)$ ) and $\Lambda>0$ is the cosmological constant.

Use these two equations to derive the acceleration equation

$\frac{\ddot{a}}{a}=-\frac{4 \pi G}{3}\left(\rho+3 P / c^{2}\right)+\frac{\Lambda c^{2}}{3}$

For pressure-free matter $\left(\rho=\rho_{\mathrm{M}}\right.$ and $\left.P_{\mathrm{M}}=0\right)$, solve the energy conservation equation to show that the Friedmann and acceleration equations can be re-expressed as

$\begin{gathered} H=H_{0} \sqrt{\frac{\Omega_{\mathrm{M}}}{a^{3}}+\Omega_{\Lambda}} \\ \frac{\ddot{a}}{a}=-\frac{H_{0}^{2}}{2}\left[\frac{\Omega_{\mathrm{M}}}{a^{3}}-2 \Omega_{\Lambda}\right] \end{gathered}$

where we have taken $a\left(t_{0}\right)=1$ and we have defined the relative densities today $\left(t=t_{0}\right)$ as

$\Omega_{\mathrm{M}}=\frac{8 \pi G}{3 H_{0}^{2}} \rho_{\mathrm{M}}\left(t_{0}\right) \quad \text { and } \quad \Omega_{\Lambda}=\frac{\Lambda c^{2}}{3 H_{0}^{2}}$

Solve the Friedmann equation and show that the scale factor can be expressed as

$a(t)=\left(\frac{\Omega_{\mathrm{M}}}{\Omega_{\Lambda}}\right)^{1 / 3} \sinh ^{2 / 3}\left(\frac{3}{2} \sqrt{\Omega_{\Lambda}} H_{0} t\right)$

Find an expression for the time $\bar{t}$ at which the matter density $\rho_{\mathrm{M}}$ and the effective density caused by the cosmological constant $\Lambda$ are equal. (You need not evaluate this explicitly.)

comment
• # Paper 2, Section I, C

In a homogeneous and isotropic universe $(\Lambda=0)$, the acceleration equation for the scale factor $a(t)$ is given by

$\frac{\ddot{a}}{a}=-\frac{4 \pi G}{3}\left(\rho+3 P / c^{2}\right),$

where $\rho(t)$ is the mass density and $P(t)$ is the pressure.

If the matter content of the universe obeys the strong energy condition $\rho+3 P / c^{2} \geqslant 0$, show that the acceleration equation can be rewritten as $\dot{H}+H^{2} \leqslant 0$, with Hubble parameter $H(t)=\dot{a} / a$. Show that

$H \geqslant \frac{1}{H_{0}^{-1}+t-t_{0}}$

where $H_{0}=H\left(t_{0}\right)$ is the measured value today at $t=t_{0}$. Hence, or otherwise, show that

$a(t) \leqslant 1+H_{0}\left(t-t_{0}\right)$

Use this inequality to find an upper bound on the age of the universe.

comment
• # Paper 3, Section I, C

(a) In the early universe electrons, protons and neutral hydrogen are in thermal equilibrium and interact via,

$e^{-}+p^{+} \leftrightharpoons H+\gamma$

The non-relativistic number density of particles in thermal equlibrium is

$n_{i}=g_{i}\left(\frac{2 \pi m_{i} k T}{h^{2}}\right)^{\frac{3}{2}} \exp \left(\frac{\mu_{i}-m_{i} c^{2}}{k T}\right)$

where, for each species $i, g_{i}$ is the number of degrees of freedom, $m_{i}$ is its mass, and $\mu_{i}$ is its chemical potential. [You may assume $g_{e}=g_{p}=2$ and $g_{H}=4$.]

Stating any assumptions required, use these expressions to derive the Saha equation which governs the relative abundances of electrons, protons and hydrogen,

$\frac{n_{e} n_{p}}{n_{H}}=\left(\frac{2 \pi m_{e} k T}{h^{2}}\right)^{\frac{3}{2}} \exp \left(-\frac{I}{k T}\right)$

where $I$ is the binding energy of hydrogen, which should be defined.

(b) Naively, we might expect that the majority of electrons and protons combine to form neutral hydrogen once the temperature drops below the binding energy, i.e. $k T \lesssim I$. In fact recombination does not happen until a much lower temperature, when $k T \approx 0.03 I$. Briefly explain why this is.

[Hint: It may help to consider the relative abundances of particles in the early universe.]

comment
• # Paper 3, Section II, C

(a) The scalar moment of inertia for a system of $N$ particles is given by

$I=\sum_{i=1}^{N} m_{i} \mathbf{r}_{i} \cdot \mathbf{r}_{i}$

where $m_{i}$ is the particle's mass and $\mathbf{r}_{i}$ is a vector giving the particle's position. Show that, for non-relativistic particles,

$\frac{1}{2} \frac{d^{2} I}{d t^{2}}=2 K+\sum_{i=1}^{N} \mathbf{F}_{i} \cdot \mathbf{r}_{i}$

where $K$ is the total kinetic energy of the system and $\mathbf{F}_{i}$ is the total force on particle

Assume that any two particles $i$ and $j$ interact gravitationally with potential energy

$V_{i j}=-\frac{G m_{i} m_{j}}{\left|\mathbf{r}_{i}-\mathbf{r}_{j}\right|}$

Show that

$\sum_{i=1}^{N} \mathbf{F}_{i} \cdot \mathbf{r}_{i}=V$