Part II, 2019

Algebraic Geometry

• Paper 1, Section II, F

  Algebraic Geometry | Part II, 2019

  (a) Let $k$ be an algebraically closed field of characteristic 0 . Consider the algebraic variety $V \subset \mathbb{A}^{3}$ defined over $k$ by the polynomials

  $$x y, \quad y^{2}-z^{3}+x z, \quad \text { and } x(x+y+2 z+1)$$

  Determine

  (i) the irreducible components of $V$,

  (ii) the tangent space at each point of $V$,

  (iii) for each irreducible component, the smooth points of that component, and

  (iv) the dimensions of the irreducible components.

  (b) Let $L \supseteq K$ be a finite extension of fields, and $\operatorname{dim}_{K} L=n$. Identify $L$ with $\mathbb{A}^{n}$ over $K$ and show that

  $$U=\{\alpha \in L \mid K[\alpha]=L\}$$

  is the complement in $\mathbb{A}^{n}$ of the vanishing set of some polynomial. [You need not show that $U$ is non-empty. You may assume that $K[\alpha]=L$ if and only if $1, \alpha, \ldots, \alpha^{n-1}$ form a basis of $L$ over $K$.]

  comment

• Paper 2, Section II, F

  Algebraic Geometry | Part II, 2019

  (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 3, Section II, F

  Algebraic Geometry | Part II, 2019

  Let $W \subseteq \mathbb{A}^{2}$ be the curve defined by the equation $y^{3}=x^{4}+1$ over the complex numbers $\mathbb{C}$, and let $X \subseteq \mathbb{P}^{2}$ be its closure.

  (a) Show $X$ is smooth.

  (b) Determine the ramification points of the $\operatorname{map} X \rightarrow \mathbb{P}^{1}$ defined by

  $$(x: y: z) \mapsto(x: z) .$$

  Using this, determine the Euler characteristic and genus of $X$, stating clearly any theorems that you are using.

  (c) Let $\omega=\frac{d x}{y^{2}} \in \mathcal{K}_{X}$. Compute $\nu_{p}(\omega)$ for all $p \in X$, and determine a basis for $\mathcal{L}\left(\mathcal{K}_{X}\right)$

  comment

• Paper 4, Section II, F

  Algebraic Geometry | Part II, 2019

  (a) Let $X \subseteq \mathbb{P}^{2}$ be a smooth projective plane curve, defined by a homogeneous polynomial $F(x, y, z)$ of degree $d$ over the complex numbers $\mathbb{C}$.

  (i) Define the divisor $[X \cap H]$, where $H$ is a hyperplane in $\mathbb{P}^{2}$ not contained in $X$, and prove that it has degree $d$.

  (ii) Give (without proof) an expression for the degree of $\mathcal{K}_{X}$ in terms of $d$.

  (iii) Show that $X$ does not have genus 2 .

  (b) Let $X$ be a smooth projective curve of genus $g$ over the complex numbers $\mathbb{C}$. For $p \in X$ let

  $G(p)=\left\{n \in \mathbb{N} \mid\right.$ there is no $f \in k(X)$ with $v_{p}(f)=n$, and $v_{q}(f) \leqslant 0$ for all $\left.q \neq p\right\} .$

  (i) Define $\ell(D)$, for a divisor $D$.

  (ii) Show that for all $p \in X$,

  $$\ell(n p)= \begin{cases}\ell((n-1) p) & \text { for } n \in G(p) \\ \ell((n-1) p)+1 & \text { otherwise }\end{cases}$$

  (iii) Show that $G(p)$ has exactly $g$ elements. [Hint: What happens for large $n$ ?]

  (iv) Now suppose that $X$ has genus 2 . Show that $G(p)=\{1,2\}$ or $G(p)=\{1,3\}$.

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

  comment

Algebraic Topology

• Paper 1, Section II, F

  Algebraic Topology | Part II, 2019

  In this question, $X$ and $Y$ are path-connected, locally simply connected spaces.

  (a) Let $f: Y \rightarrow X$ be a continuous map, and $\widehat{X}$a path-connected covering space of $X$. State and prove a uniqueness statement for lifts of $f$ to $\widehat{X}$.

  (b) Let $p: \widehat{X} \rightarrow X$ be a covering map. A covering transformation of $p$ is a homeomorphism $\phi: \widehat{X} \rightarrow \widehat{X}$such that $p \circ \phi=p$. For each integer $n \geqslant 3$, give an example of a space $X$ and an $n$-sheeted covering map $p_{n}: \widehat{X}_{n} \rightarrow X$ such that the only covering transformation of $p_{n}$ is the identity map. Justify your answer. [Hint: Take $X$ to be a wedge of two circles.]

  (c) Is there a space $X$ and a 2-sheeted covering map $p_{2}: \widehat{X}_{2} \rightarrow X$ for which the only covering transformation of $p_{2}$ is the identity? Justify your answer briefly.

  comment

• Paper 2, Section II, F

  Algebraic Topology | Part II, 2019

  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 3, Section II, F

  Algebraic Topology | Part II, 2019

  Let $K$ be a simplicial complex, and $L$ a subcomplex. As usual, $C_{k}(K)$ denotes the group of $k$-chains of $K$, and $C_{k}(L)$ denotes the group of $k$-chains of $L$.

  (a) Let

  $$C_{k}(K, L)=C_{k}(K) / C_{k}(L)$$

  for each integer $k$. Prove that the boundary map of $K$ descends to give $C_{\bullet}(K, L)$ the structure of a chain complex.

  (b) The homology groups of $K$ relative to $L$, denoted by $H_{k}(K, L)$, are defined to be the homology groups of the chain complex $C_{\bullet}(K, L)$. Prove that there is a long exact sequence that relates the homology groups of $K$ relative to $L$ to the homology groups of $K$ and the homology groups of $L$.

  (c) Let $D_{n}$ be the closed $n$-dimensional disc, and $S^{n-1}$ be the $(n-1)$-dimensional sphere. Exhibit simplicial complexes $K_{n}$ and subcomplexes $L_{n-1}$ such that $D_{n} \cong\left|K_{n}\right|$ in such a way that $\left|L_{n-1}\right|$ is identified with $S^{n-1}$.

  (d) Compute the relative homology groups $H_{k}\left(K_{n}, L_{n-1}\right)$, for all integers $k \geqslant 0$ and $n \geqslant 2$ where $K_{n}$ and $L_{n-1}$ are as in (c).

  comment

• Paper 4, Section II, F

  Algebraic Topology | Part II, 2019

  State the Lefschetz fixed point theorem.

  Let $n \geqslant 2$ be an integer, and $x_{0} \in S^{2}$ a choice of base point. Define a space

  $$X:=\left(S^{2} \times \mathbb{Z} / n \mathbb{Z}\right) / \sim$$

  where $\mathbb{Z} / n \mathbb{Z}$ is discrete and $\sim$ is the smallest equivalence relation such that $\left(x_{0}, i\right) \sim$ $\left(-x_{0}, i+1\right)$ for all $i \in \mathbb{Z} / n \mathbb{Z}$. Let $\phi: X \rightarrow X$ be a homeomorphism without fixed points. Use the Lefschetz fixed point theorem to prove the following facts.

  (i) If $\phi^{3}=\mathrm{Id}_{X}$ then $n$ is divisible by 3 .

  (ii) If $\phi^{2}=\operatorname{Id}_{X}$ then $n$ is even.

  comment

Analysis of Functions

• Paper 1, Section II, H

  Analysis of Functions | Part II, 2019

  (a) Consider the topology $\mathcal{T}$ on the natural numbers $\mathbb{N} \subset \mathbb{R}$ induced by the standard topology on $\mathbb{R}$. Prove it is the discrete topology; i.e. $\mathcal{T}=\mathcal{P}(\mathbb{N})$ is the power set of $\mathbb{N}$.

  (b) Describe the corresponding Borel sets on $\mathbb{N}$ and prove that any function $f: \mathbb{N} \rightarrow \mathbb{R}$ or $f: \mathbb{N} \rightarrow[0,+\infty]$ is measurable.

  (c) Using Lebesgue integration theory, define $\sum_{n \geqslant 1} f(n) \in[0,+\infty]$ for a function $f: \mathbb{N} \rightarrow[0,+\infty]$ and then $\sum_{n \geqslant 1} f(n) \in \mathbb{C}$ for $f: \mathbb{N} \rightarrow \mathbb{C}$. State any condition needed for the sum of the latter series to be defined. What is a simple function in this setting, and which simple functions have finite sum?

  (d) State and prove the Beppo Levi theorem (also known as the monotone convergence theorem).

  (e) Consider $f: \mathbb{R} \times \mathbb{N} \rightarrow[0,+\infty]$ such that for any $n \in \mathbb{N}$, the function $t \mapsto f(t, n)$ is non-decreasing. Prove that

  $$\lim _{t \rightarrow \infty} \sum_{n \geqslant 1} f(t, n)=\sum_{n \geqslant 1} \lim _{t \rightarrow \infty} f(t, n) .$$

  Show that this need not be the case if we drop the hypothesis that $t \mapsto f(t, n)$ is nondecreasing, even if all the relevant limits exist.

  comment

• Paper 3, Section II, H

  Analysis of Functions | Part II, 2019

  (a) Prove that in a finite-dimensional normed vector space the weak and strong topologies coincide.

  (b) Prove that in a normed vector space $X$, a weakly convergent sequence is bounded. [Any form of the Banach-Steinhaus theorem may be used, as long as you state it clearly.]

  (c) Let $\ell^{1}$ be the space of real-valued absolutely summable sequences. Suppose $\left(a^{k}\right)$ is a weakly convergent sequence in $\ell^{1}$ which does not converge strongly. Show there is a constant $\varepsilon>0$ and a sequence $\left(x^{k}\right)$ in $\ell^{1}$ which satisfies $x^{k} \rightarrow 0$ and $\left\|x^{k}\right\|_{\ell^{1}} \geqslant \varepsilon$ for all $k \geqslant 1$.

  With $\left(x^{k}\right)$ as above, show there is some $y \in \ell^{\infty}$ and a subsequence $\left(x^{k_{n}}\right)$ of $\left(x^{k}\right)$ with $\left\langle x^{k_{n}}, y\right\rangle \geqslant \varepsilon / 3$ for all $n$. Deduce that every weakly convergent sequence in $\ell^{1}$ is strongly convergent.

  [Hint: Define $y$ so that $y_{i}=\operatorname{sign} x_{i}^{k_{n}}$ for $b_{n-1}<i \leqslant b_{n}$, where the sequence of integers $b_{n}$ should be defined inductively along with $\left.x^{k_{n}} .\right]$

  (d) Is the conclusion of part (c) still true if we replace $\ell^{1}$ by $L^{1}([0,2 \pi]) ?$

  comment

• Paper 4, Section II, H

  Analysis of Functions | Part II, 2019

  (a) Let $(\mathcal{H},\langle\cdot, \cdot\rangle)$ be a real Hilbert space and let $B: \mathcal{H} \times \mathcal{H} \rightarrow \mathbb{R}$ be a bilinear map. If $B$ is continuous prove that there is an $M>0$ such that $|B(u, v)| \leqslant M\|u\|\|v\|$ for all $u, v \in \mathcal{H}$. [You may use any form of the Banach-Steinhaus theorem as long as you state it clearly.]

  (b) Now suppose that $B$ defined as above is bilinear and continuous, and assume also that it is coercive: i.e. there is a $C>0$ such that $B(u, u) \geqslant C\|u\|^{2}$ for all $u \in \mathcal{H}$. Prove that for any $f \in \mathcal{H}$, there exists a unique $v_{f} \in \mathcal{H}$ such that $B\left(u, v_{f}\right)=\langle u, f\rangle$ for all $u \in \mathcal{H}$.

  [Hint: show that there is a bounded invertible linear operator $L$ with bounded inverse so that $B(u, v)=\langle u, L v\rangle$ for all $u, v \in \mathcal{H}$. You may use any form of the Riesz representation theorem as long as you state it clearly.]

  (c) Define the Sobolev space $H_{0}^{1}(\Omega)$, where $\Omega \subset \mathbb{R}^{d}$ is open and bounded.

  (d) Suppose $f \in L^{2}(\Omega)$ and $A \in \mathbb{R}^{d}$ with $|A|_{2}<2$, where $|\cdot|_{2}$ is the Euclidean norm on $\mathbb{R}^{d}$. Consider the Dirichlet problem

  $$-\Delta v+v+A \cdot \nabla v=f \quad \text { in } \Omega, \quad v=0 \quad \text { in } \partial \Omega$$

  Using the result of part (b), prove there is a unique weak solution $v \in H_{0}^{1}(\Omega)$.

  (e) Now assume that $\Omega$ is the open unit disk in $\mathbb{R}^{2}$ and $g$ is a smooth function on $\mathbb{S}^{1}$. Sketch how you would solve the following variant:

  $$-\Delta v+v+A \cdot \nabla v=0 \quad \text { in } \Omega, \quad v=g \quad \text { in } \partial \Omega .$$

  [Hint: Reduce to the result of part (d).]

  comment

Applications of Quantum Mechanics

• Paper 1, Section II, B

  Applications of Quantum Mechanics | Part II, 2019

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

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

  where $\mathbf{p}$ is the canonical momentum.

  [ In the following you may use without proof any results concerning the spectrum of the harmonic oscillator as long as they are stated clearly.]

  (a) Let $\mathbf{E}=\mathbf{0}$. Choose a gauge which preserves translational symmetry in the $y$ direction. Determine the spectrum of the system, restricted to states with $p_{z}=0$. The system is further restricted to lie in a rectangle of area $A=L_{x} L_{y}$, with sides of length $L_{x}$ and $L_{y}$ parallel to the $x$ - and $y$-axes respectively. Assuming periodic boundary conditions in the $y$-direction, estimate the degeneracy of each Landau level.

  (b) Consider the introduction of an additional electric field $\mathbf{E}=(\mathcal{E}, 0,0)$. Choosing a suitable gauge (with the same choice of vector potential $\mathbf{A}$ as in part (a)), write down the resulting Hamiltonian. Find the energy spectrum for a particle on $\mathbb{R}^{3}$ again restricted to states with $p_{z}=0$.

  Define the group velocity of the electron and show that its $y$-component is given by $v_{y}=-\mathcal{E} / B$.

  When the system is further restricted to a rectangle of area $A$ as above, show that the previous degeneracy of the Landau levels is lifted and determine the resulting energy gap $\Delta E$ between the ground-state and the first excited state.

  comment

• Paper 2, Section II, B

  Applications of Quantum Mechanics | Part II, 2019

  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 3, Section II, B

  Applications of Quantum Mechanics | Part II, 2019

  A Hamiltonian $H$ is invariant under the discrete translational symmetry of a Bravais lattice $\Lambda$. This means that there exists a unitary translation operator $T_{\mathbf{r}}$ such that $\left[H, T_{\mathbf{r}}\right]=0$ for all $\mathbf{r} \in \Lambda$. State and prove Bloch's theorem for $H$.

  Consider the two-dimensional Bravais lattice $\Lambda$ defined by the basis vectors

  $$\mathbf{a}_{1}=\frac{a}{2}(\sqrt{3}, 1), \quad \mathbf{a}_{2}=\frac{a}{2}(\sqrt{3},-1)$$

  Find basis vectors $\mathbf{b}_{1}$ and $\mathbf{b}_{2}$ for the reciprocal lattice. Sketch the Brillouin zone. Explain why the Brillouin zone has only two physically distinct corners. Show that the positions of these corners may be taken to be $\mathbf{K}=\frac{1}{3}\left(2 \mathbf{b}_{1}+\mathbf{b}_{2}\right)$ and $\mathbf{K}^{\prime}=\frac{1}{3}\left(\mathbf{b}_{1}+2 \mathbf{b}_{2}\right)$.

  The dynamics of a single electron moving on the lattice $\Lambda$ is described by a tightbinding model with Hamiltonian

  $$H=\sum_{\mathbf{r} \in \Lambda}\left[E_{0}|\mathbf{r}\rangle\langle\mathbf{r}|-\lambda\left(|\mathbf{r}\rangle\left\langle\mathbf{r}+\mathbf{a}_{1}|+| \mathbf{r}\right\rangle\left\langle\mathbf{r}+\mathbf{a}_{2}|+| \mathbf{r}+\mathbf{a}_{1}\right\rangle\left\langle\mathbf{r}|+| \mathbf{r}+\mathbf{a}_{2}\right\rangle\langle\mathbf{r}|\right)\right]$$

  where $E_{0}$ and $\lambda$ are real parameters. What is the energy spectrum as a function of the wave vector $\mathbf{k}$ in the Brillouin zone? How does the energy vary along the boundary of the Brillouin zone between $\mathbf{K}$ and $\mathbf{K}^{\prime}$ ? What is the width of the band?

  In a real material, each site of the lattice $\Lambda$ contains an atom with a certain valency. Explain how the conducting properties of the material depend on the valency.

  Suppose now that there is a second band, with minimum $E=E_{0}+\Delta$. For what values of $\Delta$ and the valency is the material an insulator?

  comment

• Paper 4, Section II, B

  Applications of Quantum Mechanics | Part II, 2019

  (a) A classical beam of particles scatters off a spherically symmetric potential $V(r)$. Draw a diagram to illustrate the differential cross-section $d \sigma / d \Omega$, and use this to derive an expression for $d \sigma / d \Omega$ in terms of the impact parameter $b$ and the scattering angle $\theta$.

  A quantum beam of particles of mass $m$ and momentum $p=\hbar k$ is incident along the $z$-axis and scatters off a spherically symmetric potential $V(r)$. Write down the asymptotic form of the wavefunction $\psi$ in terms of the scattering amplitude $f(\theta)$. By considering the probability current $\mathbf{J}=-i(\hbar / 2 m)\left(\psi^{\star} \nabla \psi-\left(\nabla \psi^{\star}\right) \psi\right)$, derive an expression for the differential cross-section $d \sigma / d \Omega$ in terms of $f(\theta)$.

  (b) The solution $\psi(\mathbf{r})$ of the radial Schrödinger equation for a particle of mass $m$ and wave number $k$ moving in a spherically symmetric potential $V(r)$ has the asymptotic form

  $$\psi(\mathbf{r}) \sim \sum_{l=0}^{\infty}\left[A_{l}(k) \frac{\sin \left(k r-\frac{l \pi}{2}\right)}{k r}-B_{l}(k) \frac{\cos \left(k r-\frac{l \pi}{2}\right)}{k r}\right] P_{l}(\cos \theta)$$

  valid for $k r \gg 1$, where $A_{l}(k)$ and $B_{l}(k)$ are constants and $P_{l}$ denotes the $l$ th Legendre polynomial. Define the S-matrix element $S_{l}$ and the corresponding phase shift $\delta_{l}$ for the partial wave of angular momentum $l$, in terms of $A_{l}(k)$ and $B_{l}(k)$. Define also the scattering length $a_{s}$ for the potential $V$.

  Outside some core region, $r>r_{0}$, the Schrödinger equation for some such potential is solved by the s-wave (i.e. $l=0$ ) wavefunction $\psi(\mathbf{r})=\psi(r)$ with,

  $$\psi(r)=\frac{e^{-i k r}}{r}+\frac{k+i \lambda \tanh (\lambda r)}{k-i \lambda} \frac{e^{i k r}}{r}$$

  where $\lambda>0$ is a constant. Extract the S-matrix element $S_{0}$, the phase shift $\delta_{0}$ and the scattering length $a_{s}$. Deduce that the potential $V(r)$ has a bound state of zero angular momentum and compute its energy. Give the form of the (un-normalised) bound state wavefunction in the region $r>r_{0}$.

  comment

Applied Probability

• Paper 1, Section II, K

  Applied Probability | Part II, 2019

  Let $S$ be a countable set, and let $P=\left(p_{i, j}: i, j \in S\right)$ be a Markov transition matrix with $p_{i, i}=0$ for all $i$. Let $Y=\left(Y_{n}: n=0,1,2, \ldots\right)$ be a discrete-time Markov chain on the state space $S$ with transition matrix $P$.

  The continuous-time process $X=\left(X_{t}: t \geqslant 0\right)$ is constructed as follows. Let $\left(U_{m}: m=0,1,2, \ldots\right)$ be independent, identically distributed random variables having the exponential distribution with mean 1. Let $g$ be a function on $S$ such that $\varepsilon<g(i)<\frac{1}{\varepsilon}$ for all $i \in S$ and some constant $\varepsilon>0$. Let $V_{m}=U_{m} / g\left(Y_{m}\right)$ for $m \geqslant 0$. Let $T_{0}=0$ and $T_{n}=\sum_{m=0}^{n-1} V_{m}$ for $n \geqslant 1$. Finally, let $X_{t}=Y_{n}$ for $T_{n} \leqslant t<T_{n+1}$.

  (a) Explain briefly why $X$ is a continuous-time Markov chain on $S$, and write down its generator in terms of $P$ and the vector $g=(g(i): i \in S)$.

  (b) What does it mean to say that the chain $X$ is irreducible? What does it mean to say a state $i \in S$ is (i) recurrent and (ii) positive recurrent?

  (c) Show that

  (i) $X$ is irreducible if and only if $Y$ is irreducible;

  (ii) $X$ is recurrent if and only if $Y$ is recurrent.

  (d) Suppose $Y$ is irreducible and positive recurrent with invariant distribution $\pi$. Express the invariant distribution of $X$ in terms of $\pi$ and $g$.

  comment

• Paper 2, Section II, K

  Applied Probability | Part II, 2019

  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 3, Section II, K

  Applied Probability | Part II, 2019

  (a) What does it mean to say that a continuous-time Markov chain $X=\left(X_{t}: 0 \leqslant\right.$ $t \leqslant T$ ) with state space $S$ is reversible in equilibrium? State the detailed balance equations, and show that any probability distribution on $S$ satisfying them is invariant for the chain.

  (b) Customers arrive in a shop in the manner of a Poisson process with rate $\lambda>0$. There are $s$ servers, and capacity for up to $N$ people waiting for service. Any customer arriving when the shop is full (in that the total number of customers present is $N+s$ ) is not admitted and never returns. Service times are exponentially distributed with parameter $\mu>0$, and they are independent of one another and of the arrivals process. Describe the number $X_{t}$ of customers in the shop at time $t$ as a Markov chain.

  Calculate the invariant distribution $\pi$ of $X=\left(X_{t}: t \geqslant 0\right)$, and explain why $\pi$ is the unique invariant distribution. Show that $X$ is reversible in equilibrium.

  [Any general result from the course may be used without proof, but must be stated clearly.]

  comment

• Paper 4, Section II, K

  Applied Probability | Part II, 2019

  (a) Let $\lambda: \mathbb{R}^{d} \rightarrow[0, \infty)$ be such that $\Lambda(A):=\int_{A} \lambda(\mathbf{x}) d \mathbf{x}$ is finite for any bounded measurable set $A \subseteq \mathbb{R}^{d}$. State the properties which define a (non-homogeneous) Poisson process $\Pi$ on $\mathbb{R}^{d}$ with intensity function $\lambda$.

  (b) Let $\Pi$ be a Poisson process on $\mathbb{R}^{d}$ with intensity function $\lambda$, and let $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^{s}$ be a given function. Give a clear statement of the necessary conditions on the pair $\Lambda, f$ subject to which $f(\Pi)$ is a Poisson process on $\mathbb{R}^{s}$. When these conditions hold, express the mean measure of $f(\Pi)$ in terms of $\Lambda$ and $f$.

  (c) Let $\Pi$ be a homogeneous Poisson process on $\mathbb{R}^{2}$ with constant intensity 1 , and let $f: \mathbb{R}^{2} \rightarrow[0, \infty)$ be given by $f\left(x_{1}, x_{2}\right)=x_{1}^{2}+x_{2}^{2}$. Show that $f(\Pi)$ is a homogeneous Poisson process on $[0, \infty)$ with constant intensity $\pi$.

  Let $R_{1}, R_{2}, \ldots$ be an increasing sequence of positive random variables such that the points of $f(\Pi)$ are $R_{1}^{2}, R_{2}^{2}, \ldots$ Show that $R_{k}$ has density function

  $$h_{k}(r)=\frac{1}{(k-1) !} 2 \pi r\left(\pi r^{2}\right)^{k-1} e^{-\pi r^{2}}, \quad r>0$$

  comment

Asymptotic Methods

• Paper 2, Section II, A

  Asymptotic Methods | Part II, 2019

  (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 3, Section II, A

  Asymptotic Methods | Part II, 2019

  (a) State Watson's lemma for the case when all the functions and variables involved are real, and use it to calculate the asymptotic approximation as $x \rightarrow \infty$ for the integral $I$, where

  $$I=\int_{0}^{\infty} e^{-x t} \sin \left(t^{2}\right) d t$$

  (b) The Bessel function $J_{\nu}(z)$ of the first kind of order $\nu$ has integral representation

  $$J_{\nu}(z)=\frac{1}{\Gamma\left(\nu+\frac{1}{2}\right) \sqrt{\pi}}\left(\frac{z}{2}\right)^{\nu} \int_{-1}^{1} e^{i z t}\left(1-t^{2}\right)^{\nu-1 / 2} d t$$

  where $\Gamma$ is the Gamma function, $\operatorname{Re}(\nu)>1 / 2$ and $z$ is in general a complex variable. The complex version of Watson's lemma is obtained by replacing $x$ with the complex variable $z$, and is valid for $|z| \rightarrow \infty$ and $|\arg (z)| \leqslant \pi / 2-\delta<\pi / 2$, for some $\delta$ such that $0<\delta<\pi / 2$. Use this version to derive an asymptotic expansion for $J_{\nu}(z)$ as $|z| \rightarrow \infty$. For what values of $\arg (z)$ is this approximation valid?

  [Hint: You may find the substitution $t=2 \tau-1$ useful.]

  comment

• Paper 4, Section II, A

  Asymptotic Methods | Part II, 2019

  Consider, for small $\epsilon$, the equation

  $$\epsilon^{2} \frac{d^{2} \psi}{d x^{2}}-q(x) \psi=0$$

  Assume that $(*)$ has bounded solutions with two turning points $a, b$ where $b>a, q^{\prime}(b)>0$ and $q^{\prime}(a)<0$.

  (a) Use the WKB approximation to derive the relationship

  $$\frac{1}{\epsilon} \int_{a}^{b}|q(\xi)|^{1 / 2} d \xi=\left(n+\frac{1}{2}\right) \pi \text { with } n=0,1,2, \cdots$$

  [You may quote without proof any standard results or formulae from WKB theory.]

  (b) In suitable units, the radial Schrödinger equation for a spherically symmetric potential given by $V(r)=-V_{0} / r$, for constant $V_{0}$, can be recast in the standard form $(*)$ as:

  $$\frac{\hbar^{2}}{2 m} \frac{d^{2} \psi}{d x^{2}}+e^{2 x}\left[\lambda-V\left(e^{x}\right)-\frac{\hbar^{2}}{2 m}\left(l+\frac{1}{2}\right)^{2} e^{-2 x}\right] \psi=0$$

  where $r=e^{x}$ and $\epsilon=\hbar / \sqrt{2 m}$ is a small parameter.

  Use result $(* *)$ to show that the energies of the bound states (i.e $\lambda=-|\lambda|<0)$ are approximated by the expression:

  $$E=-|\lambda|=-\frac{m}{2 \hbar^{2}} \frac{V_{0}^{2}}{(n+l+1)^{2}}$$

  [You may use the result

  $$\left.\int_{a}^{b} \frac{1}{r} \sqrt{(r-a)(b-r)} d r=(\pi / 2)[\sqrt{b}-\sqrt{a}]^{2} .\right]$$

  comment

Automata and Formal Languages

• Paper 1, Section I, H

  Automata and Formal Languages | Part II, 2019

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

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

  (i) $\left\{w w^{R} \mid w \in\{a, b\}^{*}\right\}$, where $w^{R}$ is the reverse of the word $w$.

  (ii) $\left\{0^{p} 1^{p} \mid p\right.$ is a prime $\}$.

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

  (c) Let $L$ and $M$ be CFLs. Show that the concatenation $L M$ is also a CFL.

  comment

• Paper 1, Section II, H

  Automata and Formal Languages | Part II, 2019

  Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton (DFA). Define what it means for two states of $D$ to be equivalent. Define the minimal DFA $D / \sim$ for $D$.

  Let $D$ be a DFA with no inaccessible states, and suppose that $A$ is another DFA on the same alphabet as $D$ and for which $\mathcal{L}(D)=\mathcal{L}(A)$. Show that $A$ has at least as many states as $D / \sim$. [You may use results from the course as long as you state them clearly.]

  Construct a minimal DFA (that is, one with the smallest possible number of states) over the alphabet $\{0,1\}$ which accepts precisely the set of binary numbers which are multiples of 7. You may have leading zeros in your inputs (e.g.: 00101). Prove that your DFA is minimal by finding a distinguishing word for each pair of states.

  comment

• Paper 2, Section I, H

  Automata and Formal Languages | Part II, 2019

  (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 3, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2019

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Can a CFG in CNF ever define a language containing $\epsilon$ ? If $G_{\text {Chom }}$ denotes the result of converting an arbitrary CFG $G$ into one in CNF, state the relationship between $\mathcal{L}(G)$ and $\mathcal{L}\left(G_{\text {Chom }}\right)$.

  (b) Let $G$ be a CFG in CNF. Give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not. Explain why your algorithm works.

  (c) Convert the following CFG $G$ into a grammar in CNF:

  $$\begin{aligned} S \rightarrow & S b b|a S| T \\ & T \rightarrow c c \end{aligned}$$

  Does $\mathcal{L}(G)=\mathcal{L}\left(G_{\text {Chom }}\right)$ in this case? Justify your answer.

  comment

• Paper 3, Section II, 12H

  Automata and Formal Languages | Part II, 2019

  (a) State the $s-m-n$ theorem and the recursion theorem.

  (b) State and prove Rice's theorem.

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

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

  (d) Show there exists some $m \in \mathbb{N}_{0}$ such that $W_{m}$ has exactly $m^{2}$ elements.

  (e) Given $n \in \mathbb{N}_{0}$, is it possible to compute whether or not the number of elements of $W_{n}$ is a (finite) perfect square? Justify your answer.

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

  comment

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

  Automata and Formal Languages | Part II, 2019

  (a) Which of the following are regular languages? Justify your answers.

  (i) $\left\{w^{n} \mid w \in\{a, b\}^{*}, n \geqslant 2\right\}$.

  (ii) $\left\{w \in\{a, b, c\}^{*} \mid w\right.$ contains an odd number of $b$ 's and an even number of $c$ 's $\}$.

  (iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ contains no more than 7 consecutive 0 's $\}$.

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

  $$L:=\left\{w a b^{n} \mid w \in\{a, b\}^{*}, n \in \mathbb{K}\right\} \cup\{b\}^{*}$$

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

  comment

Classical Dynamics

• Paper 1, Section I, E

  Classical Dynamics | Part II, 2019

  (a) A mechanical system with $n$ degrees of freedom has the Lagrangian $L(\mathbf{q}, \dot{\mathbf{q}})$, where $\mathbf{q}=\left(q_{1}, \ldots, q_{n}\right)$ are the generalized coordinates and $\dot{\mathbf{q}}=d \mathbf{q} / d t$.

  Suppose that $L$ is invariant under the continuous symmetry transformation $\mathbf{q}(t) \mapsto$ $\mathbf{Q}(s, t)$, where $s$ is a real parameter and $\mathbf{Q}(0, t)=\mathbf{q}(t)$. State and prove Noether's theorem for this system.

  (b) A particle of mass $m$ moves in a conservative force field with potential energy $V(\mathbf{r})$, where $\mathbf{r}$ is the position vector in three-dimensional space.

  Let $(r, \phi, z)$ be cylindrical polar coordinates. $V(\mathbf{r})$ is said to have helical symmetry if it is of the form

  $$V(\mathbf{r})=f(r, \phi-k z),$$

  for some constant $k$. Show that a particle moving in a potential with helical symmetry has a conserved quantity that is a linear combination of angular and linear momenta.

  comment

• Paper 2, Section I, E

  Classical Dynamics | Part II, 2019

  (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

  Classical Dynamics | Part II, 2019

  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 3, Section I, E

  Classical Dynamics | Part II, 2019

  A simple harmonic oscillator of mass $m$ and spring constant $k$ has the equation of motion

  $$m \ddot{x}=-k x .$$

  (a) Describe the orbits of the system in phase space. State how the action $I$ of the oscillator is related to a geometrical property of the orbits in phase space. Derive the action-angle variables $(\theta, I)$ and give the form of the Hamiltonian of the oscillator in action-angle variables.

  (b) Suppose now that the spring constant $k$ varies in time. Under what conditions does the theory of adiabatic invariance apply? Assuming that these conditions hold, identify an adiabatic invariant and determine how the energy and amplitude of the oscillator vary with $k$ in this approximation.

  comment

• Paper 4, Section I, E

  Classical Dynamics | Part II, 2019

  (a) The angular momentum of a rigid body about its centre of mass is conserved.

  Derive Euler's equations,

  $$\begin{aligned} &I_{1} \dot{\omega}_{1}=\left(I_{2}-I_{3}\right) \omega_{2} \omega_{3} \\ &I_{2} \dot{\omega}_{2}=\left(I_{3}-I_{1}\right) \omega_{3} \omega_{1} \\ &I_{3} \dot{\omega}_{3}=\left(I_{1}-I_{2}\right) \omega_{1} \omega_{2} \end{aligned}$$

  explaining the meaning of the quantities appearing in the equations.

  (b) Show that there are two independent conserved quantities that are quadratic functions of $\boldsymbol{\omega}=\left(\omega_{1}, \omega_{2}, \omega_{3}\right)$, and give a physical interpretation of them.

  (c) Derive a linear approximation to Euler's equations that applies when $\left|\omega_{1}\right| \ll\left|\omega_{3}\right|$ and $\left|\omega_{2}\right| \ll\left|\omega_{3}\right|$. Use this to determine the stability of rotation about each of the three principal axes of an asymmetric top.

  comment

• Paper 4, Section II, E

  Classical Dynamics | Part II, 2019

  (a) Explain what is meant by a Lagrange top. You may assume that such a top has the Lagrangian

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

  in terms of the Euler angles $(\theta, \phi, \psi)$. State the meaning of the quantities $I_{1}, I_{3}, M$ and $l$ appearing in this expression.

  Explain why the quantity

  $$p_{\psi}=\frac{\partial L}{\partial \dot{\psi}}$$

  is conserved, and give two other independent integrals of motion.

  Show that steady precession, with a constant value of $\theta \in\left(0, \frac{\pi}{2}\right)$, is possible if

  $$p_{\psi}^{2} \geqslant 4 M g l I_{1} \cos \theta .$$

  (b) A rigid body of mass $M$ is of uniform density and its surface is defined by

  $$x_{1}^{2}+x_{2}^{2}=x_{3}^{2}-\frac{x_{3}^{3}}{h}$$

  where $h$ is a positive constant and $\left(x_{1}, x_{2}, x_{3}\right)$ are Cartesian coordinates in the body frame.

  Calculate the values of $I_{1}, I_{3}$ and $l$ for this symmetric top, when it rotates about the sharp point at the origin of this coordinate system.

  comment

Coding and Cryptography

• Paper 1, Section I, G

  Coding and Cryptography | Part II, 2019

  Let $X$ and $Y$ be discrete random variables taking finitely many values. Define the conditional entropy $H(X \mid Y)$. Suppose $Z$ is another discrete random variable taking values in a finite alphabet, and prove that

  $$H(X \mid Y) \leqslant H(X \mid Y, Z)+H(Z)$$

  [You may use the equality $H(X, Y)=H(X \mid Y)+H(Y)$ and the inequality $H(X \mid Y) \leqslant$ $H(X) .]$

  State and prove Fano's inequality.

  comment

• Paper 1, Section II, G

  Coding and Cryptography | Part II, 2019

  What does it mean to say that $C$ is a binary linear code of length $n$, rank $k$ and minimum distance $d$ ? Let $C$ be such a code.

  (a) Prove that $n \geqslant d+k-1$.

  Let $x=\left(x_{1}, \ldots, x_{n}\right) \in C$ be a codeword with exactly $d$ non-zero digits.

  (b) Prove that puncturing $C$ on the non-zero digits of $x$ produces a code $C^{\prime}$ of length $n-d, \operatorname{rank} k-1$ and minimum distance $d^{\prime}$ for some $d^{\prime} \geqslant\left\lceil\frac{d}{2}\right\rceil$.

  (c) Deduce that $n \geqslant d+\sum_{1 \leqslant l \leqslant k-1}\left\lceil\frac{d}{2^{t}}\right\rceil$.

  comment

• Paper 2, Section I, G

  Coding and Cryptography | Part II, 2019

  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

  Coding and Cryptography | Part II, 2019

  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 3, Section I, G

  Coding and Cryptography | Part II, 2019

  What does it mean to transmit reliably at rate $R$ through a binary symmetric channel $(\mathrm{BSC})$ with error probability $p$ ?

  Assuming Shannon's second coding theorem (also known as Shannon's noisy coding theorem), compute the supremum of all possible reliable transmission rates of a BSC. Describe qualitatively the behaviour of the capacity as $p$ varies. Your answer should address the following cases,

  (i) $p$ is small,

  (ii) $p=1 / 2$,

  (iii) $p>1 / 2$.

  comment

• Paper 4, Section I, $3 G$

  Coding and Cryptography | Part II, 2019

  (a) Describe Diffie-Hellman key exchange. Why is it believed to be a secure system?

  (b) Consider the following authentication procedure. Alice chooses public key $N$ for the Rabin-Williams cryptosystem. To be sure we are in communication with Alice we send her a 'random item' $r \equiv m^{2} \bmod N$. On receiving $r$, Alice proceeds to decode using her knowledge of the factorisation of $N$ and finds a square root $m_{1}$ of $r$. She returns $m_{1}$ to us and we check $r \equiv m_{1}^{2} \bmod N$. Is this authentication procedure secure? Justify your answer.

  comment

Cosmology

• Paper 1, Section I, B

  Cosmology | Part II, 2019

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

  By considering a spherical distribution of matter with total mass $M$ and radius $R$ and an infinitesimal mass $\delta m$ located somewhere on its surface, derive the Friedmann equation describing the evolution of the scale factor $a(t)$ appearing in the relation $R(t)=R_{0} a(t) / a\left(t_{0}\right)$ for a spatially-flat FLRW spacetime.

  Consider now a spatially-flat, contracting universe filled by a single component with energy density $\rho$, which evolves with time as $\rho(t)=\rho_{0}\left[a(t) / a\left(t_{0}\right)\right]^{-4}$. Solve the Friedmann equation for $a(t)$ with $a\left(t_{0}\right)=1$.

  comment

• Paper 1, Section II, 15B

  Cosmology | Part II, 2019

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

  Consider a spatially-flat FLRW universe with a single, canonical, homogeneous scalar field $\phi(t)$ with a potential $V(\phi)$. Recall the Friedmann equation and the Raychaudhuri equation (also known as the acceleration equation)

  $$\begin{aligned} \left(\frac{\dot{a}}{a}\right)^{2} &=H^{2}=\frac{8 \pi G}{3}\left[\frac{1}{2} \dot{\phi}^{2}+V\right] \\ \frac{\ddot{a}}{a} &=-\frac{8 \pi G}{3}\left(\dot{\phi}^{2}-V\right) \end{aligned}$$

  (a) Assuming $\dot{\phi} \neq 0$, derive the equations of motion for $\phi$, i.e.

  $$\ddot{\phi}+3 H \dot{\phi}+\partial_{\phi} V=0 .$$

  (b) Assuming the special case $V(\phi)=\lambda \phi^{4}$, find $\phi(t)$, for some initial value $\phi\left(t_{0}\right)=\phi_{0}$ in the slow-roll approximation, i.e. assuming that $\dot{\phi}^{2} \ll 2 V$ and $\ddot{\phi} \ll 3 H \dot{\phi}$.

  (c) The number $N$ of efoldings is defined by $d N=d \ln a$. Using the chain rule, express $d N$ first in terms of $d t$ and then in terms of $d \phi$. Write the resulting relation between $d N$ and $d \phi$ in terms of $V$ and $\partial_{\phi} V$ only, using the slow-roll approximation.

  (d) Compute the number $N$ of efoldings of expansion between some initial value $\phi_{i}<0$ and a final value $\phi_{f}<0$ (so that $\dot{\phi}>0$ throughout).

  (e) Discuss qualitatively the horizon and flatness problems in the old hot big bang model (i.e. without inflation) and how inflation addresses them.

  comment

• Paper 2, Section I, B

  Cosmology | Part II, 2019

  [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 3, Section I, B

  Cosmology | Part II, 2019

  Consider a spherically symmetric distribution of mass with density $\rho(r)$ at distance $r$ from the centre. Derive the pressure support equation that the pressure $P(r)$ has to satisfy for the system to be in static equilibrium.

  Assume now that the mass density obeys $\rho(r)=A r^{2} P(r)$, for some positive constant A. Determine whether or not the system has a stable solution corresponding to a star of finite radius.

  comment

• Paper 3, Section II, B

  Cosmology | Part II, 2019

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

  Consider the process where protons and electrons combine to form neutral hydrogen atoms;

  $$p^{+}+e^{-} \leftrightarrow H^{0}+\gamma$$

  Let $n_{p}, n_{e}$ and $n_{H}$ denote the number densities for protons, electrons and hydrogen atoms respectively. The ionization energy of hydrogen is denoted $I$. State and derive $S a h a$ 's equation for the ratio $n_{e} n_{p} / n_{H}$, clearly describing the steps required.

  [You may use without proof the following formula for the equilibrium number density of a non-relativistic species $a$ with $g_{a}$ degenerate states of mass $m$ at temperature $T$ such that $k_{B} T \ll m$,

  $$n_{a}=g_{a}\left(\frac{2 \pi m k_{B} T}{h^{2}}\right)^{3 / 2} \exp \left([\mu-m] / k_{B} T\right)$$