• # Paper 1, Section II, F

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

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 1, Section II, H

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

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

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

(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 1, Section I, H

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

(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

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

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

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

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

[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

[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 1, Section II, H

Let $n \geqslant 1$ be an integer.

(a) Show that $\mathbb{S}^{n}=\left\{x \in \mathbb{R}^{n+1}: x_{1}^{2}+\cdots+x_{n+1}^{2}=1\right\}$ defines a submanifold of $\mathbb{R}^{n+1}$ and identify explicitly its tangent space $T_{x} \mathbb{S}^{n}$ for any $x \in \mathbb{S}^{n}$.

(b) Show that the matrix group $S O(n) \subset \mathbb{R}^{n^{2}}$ defines a submanifold. Identify explicitly the tangent space $T_{R} S O(n)$ for any $R \in S O(n)$.

(c) Given $v \in \mathbb{S}^{n}$, show that the set $S_{v}=\{R \in S O(n+1): R v=v\}$ defines a submanifold $S_{v} \subset S O(n+1)$ and compute its dimension. For $v \neq w$, is it ever the case that $S_{v}$ and $S_{w}$ are transversal?

[You may use standard theorems from the course concerning regular values and transversality.]

comment

• # Paper 1, Section II, E

For a dynamical system of the form $\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$, give the definition of the alpha-limit set $\alpha(\mathbf{x})$ and the omega-limit set $\omega(\mathbf{x})$ of a point $\mathbf{x}$.

Consider the dynamical system

\begin{aligned} &\dot{x}=x^{2}-1, \\ &\dot{y}=k x y, \end{aligned}

where $\mathbf{x}=(x, y) \in \mathbb{R}^{2}$ and $k$ is a real constant. Answer the following for all values of $k$, taking care over boundary cases (both in $k$ and in $\mathbf{x}$ ).

(i) What symmetries does this system have?

(ii) Find and classify the fixed points of this system.

(iii) Does this system have any periodic orbits?

(iv) Give $\alpha(\mathbf{x})$ and $\omega(\mathbf{x})$ (considering all $\mathbf{x} \in \mathbb{R}^{2}$ ).

(v) For $\mathbf{x}_{0}=\left(0, y_{0}\right)$, give the orbit of $\mathbf{x}_{0}$ (considering all $y_{0} \in \mathbb{R}$ ). You should give your answer in the form $y=y\left(x, y_{0}, k\right)$, and specify the range of $x$.

comment

• # Paper 1, Section II, E

A relativistic particle of charge $q$ and mass $m$ moves in a background electromagnetic field. The four-velocity $u^{\mu}(\tau)$ of the particle at proper time $\tau$ is determined by the equation of motion,

$m \frac{d u^{\mu}}{d \tau}=q F_{\nu}^{\mu} u^{\nu} .$

Here $F_{\nu}^{\mu}=\eta_{\nu \rho} F^{\mu \rho}$, where $F_{\mu \nu}$ is the electromagnetic field strength tensor and Lorentz indices are raised and lowered with the metric tensor $\eta=\operatorname{diag}\{-1,+1,+1,+1\}$. In the case of a constant, homogeneous field, write down the solution of this equation giving $u^{\mu}(\tau)$ in terms of its initial value $u^{\mu}(0)$.

[In the following you may use the relation, given below, between the components of the field strength tensor $F_{\mu \nu}$, for $\mu, \nu=0,1,2,3$, and those of the electric and magnetic fields $\mathbf{E}=\left(E_{1}, E_{2}, E_{3}\right)$ and $\mathbf{B}=\left(B_{1}, B_{2}, B_{3}\right)$,

$F_{i 0}=-F_{0 i}=\frac{1}{c} E_{i}, \quad F_{i j}=\varepsilon_{i j k} B_{k}$

for $i, j=1,2,3 .]$

Suppose that, in some inertial frame with spacetime coordinates $\mathbf{x}=(x, y, z)$ and $t$, the electric and magnetic fields are parallel to the $x$-axis with magnitudes $E$ and $B$ respectively. At time $t=\tau=0$ the 3 -velocity $\mathbf{v}=d \mathbf{x} / d t$ of the particle has initial value $\mathbf{v}(0)=\left(0, v_{0}, 0\right)$. Find the subsequent trajectory of the particle in this frame, giving coordinates $x, y, z$ and $t$ as functions of the proper time $\tau$.

Find the motion in the $x$-direction explicitly, giving $x$ as a function of coordinate time $t$. Comment on the form of the solution at early and late times. Show that, when projected onto the $y-z$ plane, the particle undergoes circular motion which is periodic in proper time. Find the radius $R$ of the circle and proper time period of the motion $\Delta \tau$ in terms of $q, m, E, B$ and $v_{0}$. The resulting trajectory therefore has the form of a helix with varying pitch $P_{n}:=\Delta x_{n} / R$ where $\Delta x_{n}$ is the distance in the $x$-direction travelled by the particle during the $n$ 'th period of its motion in the $y-z$ plane. Show that, for $n \gg 1$,

$P_{n} \sim A \exp \left(\frac{2 \pi E n}{c B}\right),$

where $A$ is a constant which you should determine.

comment

• # Paper 1, Section II, A

A disc of radius $R$ and weight $W$ hovers at a height $h$ on a cushion of air above a horizontal air table - a fine porous plate through which air of density $\rho$ and dynamic viscosity $\mu$ is pumped upward at constant speed $V$. You may assume that the air flow is axisymmetric with no flow in the azimuthal direction, and that the effect of gravity on the air may be ignored.

(a) Write down the relevant components of the Navier-Stokes equations. By estimating the size of the individual terms, simplify these equations when $\varepsilon:=h / R \ll 1$ and $R e:=\rho V h / \mu \ll 1$.

(b) Explain briefly why it is reasonable to expect that the vertical velocity of the air below the disc is a function of distance above the air table alone, and thus find the steady pressure distribution below the disc. Hence show that

$W=\frac{3 \pi \mu V R}{2 \varepsilon^{3}}$

comment

• # Paper 1, Section I, A

The Beta function is defined by

$B(p, q):=\int_{0}^{1} t^{p-1}(1-t)^{q-1} d t=\frac{\Gamma(p) \Gamma(q)}{\Gamma(p+q)}$

where $\operatorname{Re} p>0, \operatorname{Re} q>0$, and $\Gamma$ is the Gamma function.

(a) By using a suitable substitution and properties of Beta and Gamma functions, show that

$\int_{0}^{1} \frac{d x}{\sqrt{1-x^{4}}}=\frac{[\Gamma(1 / 4)]^{2}}{\sqrt{32 \pi}}$

(b) Deduce that

$K(1 / \sqrt{2})=\frac{4[\Gamma(5 / 4)]^{2}}{\sqrt{\pi}}$

where $K(k)$ is the complete elliptic integral, defined as

$K(k):=\int_{0}^{1} \frac{d t}{\sqrt{\left(1-t^{2}\right)\left(1-k^{2} t^{2}\right)}}$

[Hint: You might find the change of variable $x=t\left(2-t^{2}\right)^{-1 / 2}$ helpful in part (b).]

comment
• # Paper 1, Section II, A

(a) Consider the Papperitz symbol (or P-symbol):

$\tag{†} P\left\{\begin{array}{cccc} a & b & c & \\ \alpha & \beta & \gamma & z \\ \alpha^{\prime} & \beta^{\prime} & \gamma^{\prime} & \end{array}\right\}$

Explain in general terms what this $P$-symbol represents.

[You need not write down any differential equations explicitly, but should provide an explanation of the meaning of $a, b, c, \alpha, \beta, \gamma, \alpha^{\prime}, \beta^{\prime}$ and $\left.\gamma^{\prime} .\right]$

(b) Prove that the action of $[(z-a) /(z-b)]^{\delta}$ on $(†)$ results in the exponential shifting,

$\tag{‡} P\left\{\begin{array}{cccc} a & b & c \\ \alpha+\delta & \beta-\delta & \gamma & z \\ \alpha^{\prime}+\delta & \beta^{\prime}-\delta & \gamma^{\prime} \end{array}\right\}$

[Hint: It may prove useful to start by considering the relationship between two solutions, $\omega$ and $\omega_{1}$, which satisfy the $P$-equations described by the respective $P$-symbols ($†$) and $‡$]

(c) Explain what is meant by a Möbius transformation of a second order differential equation. By using suitable transformations acting on $(†)$, show how to obtain the $P$ symbol

$\tag{*} P\left\{\begin{array}{cccc} 0 & 1 & \infty \\ 0 & 0 & a & z \\ 1-c & c-a-b & b \end{array}\right\}$

which corresponds to the hypergeometric equation.

(d) The hypergeometric function $F(a, b, c ; z)$ is defined to be the solution of the differential equation corresponding to $(\star)$ that is analytic at $z=0$ with $F(a, b, c ; 0)=1$, which corresponds to the exponent zero. Use exponential shifting to show that the second solution, which corresponds to the exponent $1-c$, is

$z^{1-c} F(a-c+1, b-c+1,2-c ; z) .$

comment

• # Paper 1, Section II, 18F

(a) Suppose $K, L$ are fields and $\sigma_{1}, \ldots, \sigma_{m}$ are distinct embeddings of $K$ into $L$. Prove that there do not exist elements $\lambda_{1}, \ldots, \lambda_{m}$ of $L$ (not all zero) such that

$\lambda_{1} \sigma_{1}(x)+\cdots+\lambda_{m} \sigma_{m}(x)=0 \quad \text { for all } x \in K$

(b) For a finite field extension $K$ of a field $k$ and for $\sigma_{1}, \ldots, \sigma_{m}$ distinct $k$ automorphisms of $K$, show that $m \leqslant[K: k]$. In particular, if $G$ is a finite group of field automorphisms of a field $K$ with $K^{G}$ the fixed field, deduce that $|G| \leqslant\left[K: K^{G}\right]$.

(c) If $K=\mathbb{Q}(x, y)$ with $x, y$ independent transcendentals over $\mathbb{Q}$, consider the group $G$ generated by automorphisms $\sigma$ and $\tau$ of $K$, where

$\sigma(x)=y, \sigma(y)=-x \quad \text { and } \quad \tau(x)=x, \tau(y)=-y .$

Prove that $|G|=8$ and that $K^{G}=\mathbb{Q}\left(x^{2}+y^{2}, x^{2} y^{2}\right)$.

comment

• # Paper 1, Section II, D

Let $(\mathcal{M}, \boldsymbol{g})$ be a spacetime and $\boldsymbol{\Gamma}$ the Levi-Civita connection of the metric $\boldsymbol{g}$. The Riemann tensor of this spacetime is given in terms of the connection by

$R_{\rho \alpha \beta}^{\gamma}=\partial_{\alpha} \Gamma_{\rho \beta}^{\gamma}-\partial_{\beta} \Gamma_{\rho \alpha}^{\gamma}+\Gamma_{\rho \beta}^{\mu} \Gamma_{\mu \alpha}^{\gamma}-\Gamma_{\rho \alpha}^{\mu} \Gamma_{\mu \beta}^{\gamma}$

The contracted Bianchi identities ensure that the Einstein tensor satisfies

$\nabla^{\mu} G_{\mu \nu}=0$

(a) Show that the Riemann tensor obeys the symmetry

$R_{\rho \alpha \beta}^{\mu}+R_{\beta \rho \alpha}^{\mu}+R_{\alpha \beta \rho}^{\mu}=0 .$

(b) Show that a vector field $V^{\alpha}$ satisfies the Ricci identity

$2 \nabla_{[\alpha} \nabla_{\beta]} V^{\gamma}=\nabla_{\alpha} \nabla_{\beta} V^{\gamma}-\nabla_{\beta} \nabla_{\alpha} V^{\gamma}=R_{\rho \alpha \beta}^{\gamma} V^{\rho}$

Calculate the analogous expression for a rank $\left(\begin{array}{l}2 \\ 0\end{array}\right)$ tensor $T^{\mu \nu}$, i.e. calculate $\nabla_{[\alpha} \nabla_{\beta]} T^{\mu \nu}$ in terms of the Riemann tensor.

(c) Let $K^{\alpha}$ be a vector that satisfies the Killing equation

$\nabla_{\alpha} K_{\beta}+\nabla_{\beta} K_{\alpha}=0$

Use the symmetry relation of part (a) to show that

$\begin{gathered} \nabla_{\nu} \nabla_{\mu} K^{\alpha}=R_{\mu \nu \beta}^{\alpha} K^{\beta} \\ \nabla^{\mu} \nabla_{\mu} K^{\alpha}=-R_{\beta}^{\alpha} K^{\beta} \end{gathered}$

where $R_{\alpha \beta}$ is the Ricci tensor.

(d) Show that

$K^{\alpha} \nabla_{\alpha} R=2 \nabla^{[\mu} \nabla^{\lambda]} \nabla_{[\mu} K_{\lambda]},$

and use the result of part (b) to show that the right hand side evaluates to zero, hence showing that $K^{\alpha} \nabla_{\alpha} R=0$.

comment

• # Paper 1, Section II, 17G

Let $G$ be a connected $d$-regular graph.

(a) Show that $d$ is an eigenvalue of $G$ with multiplicity 1 and eigenvector

$e=(11 \ldots 1)^{T}$

(b) Suppose that $G$ is strongly regular. Show that $G$ has at most three distinct eigenvalues.

(c) Conversely, suppose that $G$ has precisely three distinct eigenvalues $d, \lambda$ and $\mu$. Let $A$ be the adjacency matrix of $G$ and let

$B=A^{2}-(\lambda+\mu) A+\lambda \mu I .$

Show that if $v$ is an eigenvector of $G$ that is not a scalar multiple of $e$ then $B v=0$. Deduce that $B$ is a scalar multiple of the matrix $J$ whose entries are all equal to one. Hence show that, for $i \neq j,\left(A^{2}\right)_{i j}$ depends only on whether or not vertices $i$ and $j$ are adjacent, and so $G$ is strongly regular.

(d) Which connected $d$-regular graphs have precisely two eigenvalues? Justify your answer.

comment

• # Paper 1, Section II, C

Let $M=\mathbb{R}^{2 n}=\left\{(\mathbf{q}, \mathbf{p}) \mid \mathbf{q}, \mathbf{p} \in \mathbb{R}^{n}\right\}$ be equipped with its standard Poisson bracket.

(a) Given a Hamiltonian function $H=H(\mathbf{q}, \mathbf{p})$, write down Hamilton's equations for $(M, H)$. Define a first integral of the system and state what it means that the system is integrable.

(b) Show that if $n=1$ then every Hamiltonian system is integrable whenever

$\left(\frac{\partial H}{\partial q}, \frac{\partial H}{\partial p}\right) \neq \mathbf{0}$

Let $\tilde{M}=\mathbb{R}^{2 m}=\left\{(\tilde{\mathbf{q}}, \tilde{\mathbf{p}}) \mid \tilde{\mathbf{q}}, \tilde{\mathbf{p}} \in \mathbb{R}^{m}\right\}$ be another phase space, equipped with its standard Poisson bracket. Suppose that $\tilde{H}=\tilde{H}(\tilde{\mathbf{q}}, \tilde{\mathbf{p}})$ is a Hamiltonian function for $\tilde{M}$. Define $\mathbf{Q}=\left(q_{1}, \ldots, q_{n}, \tilde{q}_{1}, \ldots, \tilde{q}_{m}\right), \mathbf{P}=\left(p_{1}, \ldots, p_{n}, \tilde{p}_{1}, \ldots, \tilde{p}_{m}\right)$ and let the combined phase space $\mathcal{M}=\mathbb{R}^{2(n+m)}=\{(\mathbf{Q}, \mathbf{P})\}$ be equipped with the standard Poisson bracket.

(c) Show that if $(M, H)$ and $(\tilde{M}, \tilde{H})$ are both integrable, then so is $(\mathcal{M}, \mathcal{H})$, where the combined Hamiltonian is given by:

$\mathcal{H}(\mathbf{Q}, \mathbf{P})=H(\mathbf{q}, \mathbf{p})+\tilde{H}(\tilde{\mathbf{q}}, \tilde{\mathbf{p}})$

(d) Consider the $n$-dimensional simple harmonic oscillator with phase space $M$ and Hamiltonian $H$ given by:

$H=\frac{1}{2} p_{1}^{2}+\ldots+\frac{1}{2} p_{n}^{2}+\frac{1}{2} \omega_{1}^{2} q_{1}^{2}+\ldots+\frac{1}{2} \omega_{n}^{2} q_{n}^{2}$

where $\omega_{i}>0$. Using the results above, or otherwise, show that $(M, H)$ is integrable for $(\mathbf{q}, \mathbf{p}) \neq \mathbf{0}$.

(e) Is it true that every bounded orbit of an integrable system is necessarily periodic? You should justify your answer.

comment

• # Paper 1, Section II, H

Let $F$ be the space of real-valued sequences with only finitely many nonzero terms.

(a) For any $p \in[1, \infty)$, show that $F$ is dense in $\ell^{p}$. Is $F$ dense in $\ell^{\infty} ?$ Justify your answer.

(b) Let $p \in[1, \infty)$, and let $T: F \rightarrow F$ be an operator that is bounded in the $\|\cdot\|_{p}$-norm, i.e., there exists a $C$ such that $\|T x\|_{p} \leqslant C\|x\|_{p}$ for all $x \in F$. Show that there is a unique bounded operator $\widetilde{T}: \ell^{p} \rightarrow \ell^{p}$ satisfying $\left.\widetilde{T}\right|_{F}=T$, and that $\|\widetilde{T}\|_{p} \leqslant C$.

(c) For each $p \in[1, \infty]$ and for each $i=1, \ldots, 5$ determine if there is a bounded operator from $\ell^{p}$ to $\ell^{p}$ (in the $\|\cdot\|_{p}$ norm) whose restriction to $F$ is given by $T_{i}$ :

$\begin{gathered} \left(T_{1} x\right)_{n}=n x_{n}, \quad\left(T_{2} x\right)_{n}=n\left(x_{n}-x_{n+1}\right), \quad\left(T_{3} x\right)_{n}=\frac{x_{n}}{n}, \\ \left(T_{4} x\right)_{n}=\frac{x_{1}}{n^{1 / 2}}, \quad\left(T_{5} x\right)_{n}=\frac{\sum_{j=1}^{n} x_{j}}{2^{n}} \end{gathered}$

(d) Let $X$ be a normed vector space such that the closed unit ball $\overline{B_{1}(0)}$ is compact. Prove that $X$ is finite dimensional.

comment

• # Paper 1, Section II, I

State the completeness theorem for propositional logic. Explain briefly how the proof of this theorem changes from the usual proof in the case when the set of primitive propositions may be uncountable.

State the compactness theorem and the decidability theorem, and deduce them from the completeness theorem.

A poset $(X,<)$ is called two-dimensional if there exist total orders $<_{1}$ and $<_{2}$ on $X$ such that $x if and only if $x<_{1} y$ and $x<_{2} y$. By applying the compactness theorem for propositional logic, show that if every finite subset of a poset is two-dimensional then so is the poset itself.

[Hint: Take primitive propositions $p_{x, y}$ and $q_{x, y}$, for each distinct $x, y \in X$, with the intended interpretation that $p_{x, y}$ is true if and only if $x<_{1} y$ and $q_{x, y}$ is true if and only if $x<_2 y .]$

comment

• # Paper 1, Section $I$, $\mathbf{6 C}$

An animal population has annual dynamics, breeding in the summer and hibernating through the winter. At year $t$, the number of individuals alive who were born a years ago is given by $n_{a, t}$. Each individual of age $a$ gives birth to $b_{a}$ offspring, and after the summer has a probability $\mu_{a}$ of dying during the winter. [You may assume that individuals do not give birth during the year in which they are born.]

Explain carefully why the following equations, together with initial conditions, are appropriate to describe the system:

\begin{aligned} n_{0, t} &=\sum_{a=1}^{\infty} n_{a, t} b_{a} \\ n_{a+1, t+1} &=\left(1-\mu_{a}\right) n_{a, t}, \end{aligned}

Seek a solution of the form $n_{a, t}=r_{a} \gamma^{t}$ where $\gamma$ and $r_{a}$, for $a=1,2,3 \ldots$, are constants. Show $\gamma$ must satisfy $\phi(\gamma)=1$ where

$\phi(\gamma)=\sum_{a=1}^{\infty}\left(\prod_{i=0}^{a-1}\left(1-\mu_{i}\right)\right) \gamma^{-a} b_{a}$

Explain why, for any reasonable set of parameters $\mu_{i}$ and $b_{i}$, the equation $\phi(\gamma)=1$ has a unique solution. Explain also how $\phi(1)$ can be used to determine if the population will grow or shrink.

comment

• # Paper 1, Section II, 20G

Let $K=\mathbb{Q}(\sqrt{2})$.

(a) Write down the ring of integers $\mathcal{O}_{K}$.

(b) State Dirichlet's unit theorem, and use it to determine all elements of the group of units $\mathcal{O}_{K}^{\times}$.

(c) Let $P \subset \mathcal{O}_{K}$ denote the ideal generated by $3+\sqrt{2}$. Show that the group

$G=\left\{\alpha \in \mathcal{O}_{K}^{\times} \mid \alpha \equiv 1 \bmod P\right\}$

is cyclic, and find a generator.

comment

• # Paper 1, Section I, I

(a) State and prove the Chinese remainder theorem.

(b) Let $N$ be an odd positive composite integer, and $b$ a positive integer with $(b, N)=1$. What does it mean to say that $N$ is a Fermat pseudoprime to base b? Show that 35 is a Fermat pseudoprime to base $b$ if and only if $b$ is congruent to one of $1,6,29$ or $34(\bmod 35)$.

comment

• # Paper 1, Section II, C

(a) Describe the Jacobi method for solving a system of linear equations $A \boldsymbol{x}=\boldsymbol{b}$ as a particular case of splitting, and state the criterion for its convergence in terms of the iteration matrix.

(b) For the case when

$A=\left[\begin{array}{lll} 1 & \alpha & \alpha \\ \alpha & 1 & \alpha \\ \alpha & \alpha & 1 \end{array}\right]$

find the exact range of the parameter $\alpha$ for which the Jacobi method converges.

(c) State the Householder-John theorem and deduce that the Jacobi method converges if $A$ is a symmetric positive-definite tridiagonal matrix.

comment

• # Paper 1, Section II, B

A $d=3$ isotropic harmonic oscillator of mass $\mu$ and frequency $\omega$ has lowering operators

$\mathbf{A}=\frac{1}{\sqrt{2 \mu \hbar \omega}}(\mu \omega \mathbf{X}+\mathrm{i} \mathbf{P})$

where $\mathbf{X}$ and $\mathbf{P}$ are the position and momentum operators. Assuming the standard commutation relations for $\mathbf{X}$ and $\mathbf{P}$, evaluate the commutators $\left[A_{i}^{\dagger}, A_{j}^{\dagger}\right],\left[A_{i}, A_{j}\right]$ and $\left[A_{i}, A_{j}^{\dagger}\right]$, for $i, j=1,2,3$, among the components of the raising and lowering operators.

How is the ground state $|\mathbf{0}\rangle$ of the oscillator defined? How are normalised higher excited states obtained from $|\mathbf{0}\rangle$ ? [You should determine the appropriate normalisation constant for each energy eigenstate.]

By expressing the orbital angular momentum operator $\mathbf{L}$ in terms of the raising and lowering operators, show that each first excited state of the isotropic oscillator has total orbital angular momentum quantum number $\ell=1$, and find a linear combination $|\psi\rangle$ of these first excited states obeying $L_{z}|\psi\rangle=+\hbar|\psi\rangle$ and $\||\psi\rangle \|=1$.

comment

• # Paper 1, Section II, J

In a regression problem, for a given $X \in \mathbb{R}^{n \times p}$ fixed, we observe $Y \in \mathbb{R}^{n}$ such that

$Y=X \theta_{0}+\varepsilon$

for an unknown $\theta_{0} \in \mathbb{R}^{p}$ and $\varepsilon$ random such that $\varepsilon \sim \mathcal{N}\left(0, \sigma^{2} I_{n}\right)$ for some known $\sigma^{2}>0$.

(a) When $p \leqslant n$ and $X$ has rank $p$, compute the maximum likelihood estimator $\hat{\theta}_{M L E}$ for $\theta_{0}$. When $p>n$, what issue is there with the likelihood maximisation approach and how many maximisers of the likelihood are there (if any)?

(b) For any $\lambda>0$ fixed, we consider $\hat{\theta}_{\lambda}$ minimising

$\|Y-X \theta\|_{2}^{2}+\lambda\|\theta\|_{2}^{2}$

over $\mathbb{R}^{p}$. Derive an expression for $\hat{\theta}_{\lambda}$ and show it is well defined, i.e., there is a unique minimiser for every $X, Y$ and $\lambda$.

Assume $p \leqslant n$ and that $X$ has rank $p$. Let $\Sigma=X^{\top} X$ and note that $\Sigma=V \Lambda V^{\top}$ for some orthogonal matrix $V$ and some diagonal matrix $\Lambda$ whose diagonal entries satisfy $\Lambda_{1,1} \geqslant \Lambda_{2,2} \geqslant \ldots \geqslant \Lambda_{p, p}$. Assume that the columns of $X$ have mean zero.

(c) Denote the columns of $U=X V$ by $u_{1}, \ldots, u_{p}$. Show that they are sample principal components, i.e., that their pairwise sample correlations are zero and that they have sample variances $n^{-1} \Lambda_{1,1}, \ldots, n^{-1} \Lambda_{p, p}$, respectively. [Hint: the sample covariance between $u_{i}$ and $u_{j}$ is $n^{-1} u_{i}^{\top} u_{j}$.]

(d) Show that

$\hat{Y}_{M L E}=X \hat{\theta}_{M L E}=U \Lambda^{-1} U^{\top} Y .$

Conclude that prediction $\hat{Y}_{M L E}$ is the closest point to $Y$ within the subspace spanned by the normalised sample principal components of part (c).

(e) Show that

$\hat{Y}_{\lambda}=X \hat{\theta}_{\lambda}=U\left(\Lambda+\lambda I_{p}\right)^{-1} U^{\top} Y$

Assume $\Lambda_{1,1}, \Lambda_{2,2}, \ldots, \Lambda_{q, q}>>\lambda>>\Lambda_{q+1, q+1}, \ldots, \Lambda_{p, p}$ for some $1 \leqslant q. Conclude that prediction $\hat{Y}_{\lambda}$ is approximately the closest point to $Y$ within the subspace spanned by the $q$ normalised sample principal components of part (c) with the greatest variance.

comment

• # Paper 1, Section II, K

Let $\mathbf{X}=\left(X_{1}, \ldots, X_{d}\right)$ be an $\mathbb{R}^{d}$-valued random variable. Given $u=\left(u_{1}, \ldots, u_{d}\right) \in$ $\mathbb{R}^{d}$ we let

$\phi_{\mathbf{X}}(u)=\mathbb{E}\left(e^{i\langle u, \mathbf{X}\rangle}\right)$

be its characteristic function, where $\langle\cdot, \cdot\rangle$ is the usual inner product on $\mathbb{R}^{d}$.

(a) Suppose $\mathbf{X}$ is a Gaussian vector with mean 0 and covariance matrix $\sigma^{2} I_{d}$, where $\sigma>0$ and $I_{d}$ is the $d \times d$ identity matrix. What is the formula for the characteristic function $\phi_{\mathbf{X}}$ in the case $d=1$ ? Derive from it a formula for $\phi_{\mathbf{X}}$ in the case $d \geqslant 2$.

(b) We now no longer assume that $\mathbf{X}$ is necessarily a Gaussian vector. Instead we assume that the $X_{i}$ 's are independent random variables and that the random vector $A \mathbf{X}$ has the same law as $\mathbf{X}$ for every orthogonal matrix $A$. Furthermore we assume that $d \geqslant 2$.

(i) Show that there exists a continuous function $f:[0,+\infty) \rightarrow \mathbb{R}$ such that

$\phi_{\mathbf{X}}(u)=f\left(u_{1}^{2}+\ldots+u_{d}^{2}\right)$

[You may use the fact that for every two vectors $u, v \in \mathbb{R}^{d}$ such that $\langle u, u\rangle=\langle v, v\rangle$ there is an orthogonal matrix $A$ such that $A u=v$. ]

(ii) Show that for all $r_{1}, r_{2} \geqslant 0$

$f\left(r_{1}+r_{2}\right)=f\left(r_{1}\right) f\left(r_{2}\right) .$

(iii) Deduce that $f$ takes values in $(0,1]$, and furthermore that there exists $\alpha \geqslant 0$ such that $f(r)=e^{-r \alpha}$, for all $r \geqslant 0$.

(iv) What must be the law of $\mathbf{X}$ ?

[Standard properties of characteristic functions from the course may be used without proof if clearly stated.]

comment

• # Paper 1, Section I, $10 D$ Introduce the 2 -qubit states

$\left|\beta_{x z}\right\rangle=\left(Z^{z} X^{x}\right) \otimes I\left(\frac{|00\rangle+|11\rangle}{\sqrt{2}}\right)$

where $X$ and $Z$ are the standard qubit Pauli operations and $x, z \in\{0,1\}$.

(a) For any 1-qubit state $|\alpha\rangle$ show that the 3 -qubit state $|\alpha\rangle_{C}\left|\beta_{00}\right\rangle_{A B}$ of system $C A B$ can be expressed as

$|\alpha\rangle_{C}\left|\beta_{00}\right\rangle_{A B}=\frac{1}{2} \sum_{x, z=0}^{1}\left|\beta_{x z}\right\rangle_{C A}\left|\mu_{x z}\right\rangle_{B}$

where the 1 -qubit states $\left|\mu_{x z}\right\rangle$ are uniquely determined. Show that $\left|\mu_{10}\right\rangle=X|\alpha\rangle$.

(b) In addition to $\left|\mu_{10}\right\rangle=X|\alpha\rangle$ you may now assume that $\left|\mu_{x z}\right\rangle=X^{x} Z^{z}|\alpha\rangle$. Alice and Bob are separated distantly in space and share a $\left|\beta_{00}\right\rangle_{A B}$ state with $A$ and $B$ labelling qubits held by Alice and Bob respectively. Alice also has a qubit $C$ in state $|\alpha\rangle$ whose identity is unknown to her. Using the results of part (a) show how she can transfer the state of $C$ to Bob using only local operations and classical communication, i.e. the sending of quantum states across space is not allowed.

(c) Suppose that in part (b), while sharing the $\left|\beta_{00}\right\rangle_{A B}$ state, Alice and Bob are also unable to engage in any classical communication, i.e. they are able only to perform local operations. Can Alice now, perhaps by a modified process, transfer the state of $C$ to Bob? Give a reason for your answer.

comment

• # Paper 1, Section II, I

(a) State and prove Schur's lemma over $\mathbb{C}$.

In the remainder of this question we work over $\mathbb{R}$.

(b) Let $G$ be the cyclic group of order 3 .

(i) Write the regular $\mathbb{R} G$-module as a direct sum of irreducible submodules.

(ii) Find all the intertwining homomorphisms between the irreducible $\mathbb{R} G$-modules. Deduce that the conclusion of Schur's lemma is false if we replace $\mathbb{C}$ by $\mathbb{R}$.

(c) Henceforth let $G$ be a cyclic group of order $n$. Show that

(i) if $n$ is even, the regular $\mathbb{R} G$-module is a direct sum of two (non-isomorphic) 1dimensional irreducible submodules and $(n-2) / 2$ (non-isomorphic) 2-dimensional irreducible submodules;

(ii) if $n$ is odd, the regular $\mathbb{R} G$-module is a direct sum of one 1-dimensional irreducible submodule and $(n-1) / 2$ (non-isomorphic) 2-dimensional irreducible submodules.

comment

• # Paper 1, Section II, F

Define $X^{\prime}:=\left\{(x, y) \in \mathbb{C}^{2}: x^{3} y+y^{3}+x=0\right\}$.

(a) Prove by defining an atlas that $X^{\prime}$ is a Riemann surface.

(b) Now assume that by adding finitely many points, it is possible to compactify $X^{\prime}$ to a Riemann surface $X$ so that the coordinate projections extend to holomorphic maps $\pi_{x}$ and $\pi_{y}$ from $X$ to $\mathbb{C}_{\infty}$. Compute the genus of $X$.

(c) Assume that any holomorphic automorphism of $X^{\prime}$ extends to a holomorphic automorphism of $X$. Prove that the group Aut $(\mathrm{X})$ of holomorphic automorphisms of $X$ contains an element $\phi$ of order 7 . Prove further that there exists a holomorphic map $\pi: X \rightarrow \mathbb{C}_{\infty}$ which satisfies $\pi \circ \phi=\pi$.

comment

• # Paper 1, Section I, J

The Gamma distribution with shape parameter $\alpha>0$ and scale parameter $\lambda>0$ has probability density function

$f(y ; \alpha, \lambda)=\frac{\lambda^{\alpha}}{\Gamma(\alpha)} y^{\alpha-1} e^{-\lambda y} \quad \text { for } y>0$

Give the definition of an exponential dispersion family and show that the set of Gamma distributions forms one such family. Find the cumulant generating function and derive the mean and variance of the Gamma distribution as a function of $\alpha$ and $\lambda$.

comment
• # Paper 1, Section II, J

The ice_cream data frame contains the result of a blind tasting of 90 ice creams, each of which is rated as poor, good, or excellent. It also contains the price of each ice cream classified into three categories. Consider the $R$ code below and its output.

(a) Write down the generalised linear model fitted by the code above.

(b) Prove that the fitted values resulting from the maximum likelihood estimator of the coefficients in this model are identical to those resulting from the maximum likelihood estimator when fitting a Multinomial model which assumes the number of ice creams at each price level is fixed.

(c) Using the output above, perform a goodness-of-fit test at the $1 \%$ level, specifying the null hypothesis, the test statistic, its asymptotic null distribution, any assumptions of the test and the decision from your test. (d) If we believe that better ice creams are more expensive, what could be a more powerful test against the model fitted above and why?

comment

• # Paper 1, Section II, D

(a) Explain, from a macroscopic and microscopic point of view, what is meant by an adiabatic change. A system has access to heat baths at temperatures $T_{1}$ and $T_{2}$, with $T_{2}>T_{1}$. Show that the most effective method for repeatedly converting heat to work, using this system, is by combining isothermal and adiabatic changes. Define the efficiency and calculate it in terms of $T_{1}$ and $T_{2}$.

(b) A thermal system (of constant volume) undergoes a phase transition at temperature $T_{\mathrm{c}}$. The heat capacity of the system is measured to be

$C= \begin{cases}\alpha T & \text { for } TT_{\mathrm{c}}\end{cases}$

where $\alpha, \beta$ are constants. A theoretical calculation of the entropy $S$ for $T>T_{\mathrm{c}}$ leads to

$S=\beta \log T+\gamma$

How can the value of the theoretically-obtained constant $\gamma$ be verified using macroscopically measurable quantities?

comment

• # Paper 1, Section II, 30K

(a) What does it mean to say that $\left(M_{n}, \mathcal{F}_{n}\right)_{n \geqslant 0}$ is a martingale? (b) Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain defined by $X_{0}=0$ and

\begin{aligned} & \mathbb{P}\left[X_{n}=0 \mid X_{n-1}=0\right]=1-\frac{1}{n} \end{aligned}

\begin{aligned} &\mathbb{P}\left[X_{n}=1 \mid X_{n-1}=0\right]=\mathbb{P}\left[X_{n}=-1 \mid X_{n-1}=0\right]=\frac{1}{2 n} \\ &\mathbb{P}\left[X_{n}=0 \mid X_{n-1}=0\right]=1-\frac{1}{n} \end{aligned}

and

$\mathbb{P}\left[X_{n}=n X_{n-1} \mid X_{n-1} \neq 0\right]=\frac{1}{n}, \quad \mathbb{P}\left[X_{n}=0 \mid X_{n-1} \neq 0\right]=1-\frac{1}{n}$

for $n \geqslant 1$. Show that $\left(X_{n}\right)_{n \geqslant 0}$ is a martingale with respect to the filtration $\left(\mathcal{F}_{n}\right)_{n} \geqslant 0$ where $\mathcal{F}_{0}$ is trivial and $\mathcal{F}_{n}=\sigma\left(X_{1}, \ldots, X_{n}\right)$ for $n \geqslant 1$.

(c) Let $M=\left(M_{n}\right)_{n \geqslant 0}$ be adapted with respect to a filtration $\left(\mathcal{F}_{n}\right)_{n \geqslant 0}$ with $\mathbb{E}\left[\left|M_{n}\right|\right]<\infty$ for all $n$. Show that the following are equivalent:

(i) $M$ is a martingale.

(ii) For every stopping time $\tau$, the stopped process $M^{\tau}$ defined by $M_{n}^{\tau}:=M_{n \wedge \tau}$, $n \geqslant 0$, is a martingale.

(iii) $\mathbb{E}\left[M_{n \wedge \tau}\right]=\mathbb{E}\left[M_{0}\right]$ for all $n \geqslant 0$ and every stopping time $\tau$.

[Hint: To show that (iii) implies (i) you might find it useful to consider the stopping time

$T(\omega):= \begin{cases}n & \text { if } \omega \in A, \\ n+1 & \text { if } \omega \notin A,\end{cases}$

for any $\left.A \in \mathcal{F}_{n .} .\right]$