Part II, 2021

Algebraic Geometry

• Paper 1, Section II, I

  Algebraic Geometry | Part II, 2021

  Let $k$ be an algebraically closed field and let $V \subset \mathbb{A}_{k}^{n}$ be a non-empty affine variety. Show that $V$ is a finite union of irreducible subvarieties.

  Let $V_{1}$ and $V_{2}$ be subvarieties of $\mathbb{A}_{k}^{n}$ given by the vanishing loci of ideals $I_{1}$ and $I_{2}$ respectively. Prove the following assertions.

  (i) The variety $V_{1} \cap V_{2}$ is equal to the vanishing locus of the ideal $I_{1}+I_{2}$.

  (ii) The variety $V_{1} \cup V_{2}$ is equal to the vanishing locus of the ideal $I_{1} \cap I_{2}$.

  Decompose the vanishing locus

  $$\mathbb{V}\left(X^{2}+Y^{2}-1, X^{2}-Z^{2}-1\right) \subset \mathbb{A}_{\mathbb{C}}^{3}$$

  into irreducible components.

  Let $V \subset \mathbb{A}_{k}^{3}$ be the union of the three coordinate axes. Let $W$ be the union of three distinct lines through the point $(0,0)$ in $\mathbb{A}_{k}^{2}$. Prove that $W$ is not isomorphic to $V$.

  comment

• Paper 2, Section II, I

  Algebraic Geometry | Part II, 2021

  Let $k$ be an algebraically closed field and $n \geqslant 1$. Exhibit $G L(n, k)$ as an open subset of affine space $\mathbb{A}_{k}^{n^{2}}$. Deduce that $G L(n, k)$ is smooth. Prove that it is also irreducible.

  Prove that $G L(n, k)$ is isomorphic to a closed subvariety in an affine space.

  Show that the matrix multiplication map

  $$G L(n, k) \times G L(n, k) \rightarrow G L(n, k)$$

  that sends a pair of matrices to their product is a morphism.

  Prove that any morphism from $\mathbb{A}_{k}^{n}$ to $\mathbb{A}_{k}^{1}\setminus\{0\}$ is constant.

  Prove that for $n \geqslant 2$ any morphism from $\mathbb{P}_{k}^{n}$ to $\mathbb{P}_{k}^{1}$ is constant.

  comment

• Paper 3, Section II, I

  Algebraic Geometry | Part II, 2021

  In this question, all varieties are over an algebraically closed field $k$ of characteristic zero.

  What does it mean for a projective variety to be smooth? Give an example of a smooth affine variety $X \subset \mathbb{A}_{k}^{n}$ whose projective closure $\bar{X} \subset \mathbb{P}_{k}^{n}$ is not smooth.

  What is the genus of a smooth projective curve? Let $X \subset \mathbb{P}_{k}^{4}$ be the hypersurface $V\left(X_{0}^{3}+X_{1}^{3}+X_{2}^{3}+X_{3}^{3}+X_{4}^{3}\right)$. Prove that $X$ contains a smooth curve of genus $1 .$

  Let $C \subset \mathbb{P}_{k}^{2}$ be an irreducible curve of degree 2 . Prove that $C$ is isomorphic to $\mathbb{P}_{k}^{1}$.

  We define a generalized conic in $\mathbb{P}_{k}^{2}$ to be the vanishing locus of a non-zero homogeneous quadratic polynomial in 3 variables. Show that there is a bijection between the set of generalized conics in $\mathbb{P}_{k}^{2}$ and the projective space $\mathbb{P}_{k}^{5}$, which maps the conic $V(f)$ to the point whose coordinates are the coefficients of $f$.

  (i) Let $R^{\circ} \subset \mathbb{P}_{k}^{5}$ be the subset of conics that consist of unions of two distinct lines. Prove that $R^{\circ}$ is not Zariski closed, and calculate its dimension.

  (ii) Let $I$ be the homogeneous ideal of polynomials vanishing on $R^{\circ}$. Determine generators for the ideal $I$.

  comment

• Paper 4, Section II, I

  Algebraic Geometry | Part II, 2021

  Let $C$ be a smooth irreducible projective algebraic curve over an algebraically closed field.

  Let $D$ be an effective divisor on $C$. Prove that the vector space $L(D)$ of rational functions with poles bounded by $D$ is finite dimensional.

  Let $D$ and $E$ be linearly equivalent divisors on $C$. Exhibit an isomorphism between the vector spaces $L(D)$ and $L(E)$.

  What is a canonical divisor on $C$ ? State the Riemann-Roch theorem and use it to calculate the degree of a canonical divisor in terms of the genus of $C$.

  Prove that the canonical divisor on a smooth cubic plane curve is linearly equivalent to the zero divisor.

  comment

Algebraic Topology

• Paper 1, Section II, 21F

  Algebraic Topology | Part II, 2021

  (a) What does it mean for two spaces $X$ and $Y$ to be homotopy equivalent?

  (b) What does it mean for a subspace $Y \subseteq X$ to be a retract of a space $X$ ? What does it mean for a space $X$ to be contractible? Show that a retract of a contractible space is contractible.

  (c) Let $X$ be a space and $A \subseteq X$ a subspace. We say the pair $(X, A)$ has the homotopy extension property if, for any pair of maps $f: X \times\{0\} \rightarrow Y$ and $H^{\prime}: A \times I \rightarrow Y$ with

  $$\left.f\right|_{A \times\{0\}}=\left.H^{\prime}\right|_{A \times\{0\}},$$

  there exists a map $H: X \times I \rightarrow Y$ with

  $$\left.H\right|_{X \times\{0\}}=f,\left.\quad H\right|_{A \times I}=H^{\prime}$$

  Now suppose that $A \subseteq X$ is contractible. Denote by $X / A$ the quotient of $X$ by the equivalence relation $x \sim x^{\prime}$ if and only if $x=x^{\prime}$ or $x, x^{\prime} \in A$. Show that, if $(X, A)$ satisfies the homotopy extension property, then $X$ and $X / A$ are homotopy equivalent.

  comment

• Paper 2, Section II, 21F

  Algebraic Topology | Part II, 2021

  (a) State a suitable version of the Seifert-van Kampen theorem and use it to calculate the fundamental groups of the torus $T^{2}:=S^{1} \times S^{1}$ and of the real projective plane $\mathbb{R P}^{2}$.

  (b) Show that there are no covering maps $T^{2} \rightarrow \mathbb{R} \mathbb{P}^{2}$ or $\mathbb{R P}^{2} \rightarrow T^{2}$.

  (c) Consider the following covering space of $S^{1} \vee S^{1}$ :

  

  Here the line segments labelled $a$ and $b$ are mapped to the two different copies of $S^{1}$ contained in $S^{1} \vee S^{1}$, with orientations as indicated.

  Using the Galois correspondence with basepoints, identify a subgroup of

  $$\pi_{1}\left(S^{1} \vee S^{1}, x_{0}\right)=F_{2}$$

  (where $x_{0}$ is the wedge point) that corresponds to this covering space.

  comment

• Paper 3, Section II, 20F

  Algebraic Topology | Part II, 2021

  Let $X$ be a space. We define the cone of $X$ to be

  $$C X:=(X \times I) / \sim$$

  where $\left(x_{1}, t_{1}\right) \sim\left(x_{2}, t_{2}\right)$ if and only if either $t_{1}=t_{2}=1$ or $\left(x_{1}, t_{1}\right)=\left(x_{2}, t_{2}\right)$.

  (a) Show that if $X$ is triangulable, so is $C X$. Calculate $H_{i}(C X)$. [You may use any results proved in the course.]

  (b) Let $K$ be a simplicial complex and $L \subseteq K$ a subcomplex. Let $X=|K|, A=|L|$, and let $X^{\prime}$ be the space obtained by identifying $|L| \subseteq|K|$ with $|L| \times\{0\} \subseteq C|L|$. Show that there is a long exact sequence

  $$\begin{aligned} \cdots \rightarrow & H_{i+1}\left(X^{\prime}\right) \rightarrow H_{i}(A) \rightarrow H_{i}(X) \rightarrow H_{i}\left(X^{\prime}\right) \rightarrow H_{i-1}(A) \rightarrow \cdots \\ & \cdots \rightarrow H_{1}\left(X^{\prime}\right) \rightarrow H_{0}(A) \rightarrow \mathbb{Z} \oplus H_{0}(X) \rightarrow H_{0}\left(X^{\prime}\right) \rightarrow 0 \end{aligned}$$

  (c) In part (b), suppose that $X=S^{1} \times S^{1}$ and $A=S^{1} \times\{x\} \subseteq X$ for some $x \in S^{1}$. Calculate $H_{i}\left(X^{\prime}\right)$ for all $i$.

  comment

• Paper 4, Section II, 21F

  Algebraic Topology | Part II, 2021

  (a) Define the Euler characteristic of a triangulable space $X$.

  (b) Let $\Sigma_{g}$ be an orientable surface of genus $g$. A $\operatorname{map} \pi: \Sigma_{g} \rightarrow S^{2}$ is a doublebranched cover if there is a set $Q=\left\{p_{1}, \ldots, p_{n}\right\} \subseteq S^{2}$ of branch points, such that the restriction $\pi: \Sigma_{g} \backslash \pi^{-1}(Q) \rightarrow S^{2} \backslash Q$ is a covering map of degree 2 , but for each $p \in Q$, $\pi^{-1}(p)$ consists of one point. By carefully choosing a triangulation of $S^{2}$, use the Euler characteristic to find a formula relating $g$ and $n$.

  comment

Analysis of Functions

• Paper 1, Section II, $23 \mathrm{H}$

  Analysis of Functions | Part II, 2021

  Below, $\mathcal{M}$ is the $\sigma$-algebra of Lebesgue measurable sets and $\lambda$ is Lebesgue measure.

  (a) State the Lebesgue differentiation theorem for an integrable function $f: \mathbb{R}^{n} \rightarrow \mathbb{C}$. Let $g: \mathbb{R} \rightarrow \mathbb{C}$ be integrable and define $G: \mathbb{R} \rightarrow \mathbb{C}$ by $G(x):=\int_{[a, x]} g d \lambda$ for some $a \in \mathbb{R}$. Show that $G$ is differentiable $\lambda$-almost everywhere.

  (b) Suppose $h: \mathbb{R} \rightarrow \mathbb{R}$ is strictly increasing, continuous, and maps sets of $\lambda$-measure zero to sets of $\lambda$-measure zero. Show that we can define a measure $\nu$ on $\mathcal{M}$ by setting $\nu(A):=\lambda(h(A))$ for $A \in \mathcal{M}$, and establish that $\nu \ll \lambda$. Deduce that $h$ is differentiable $\lambda$-almost everywhere. Does the result continue to hold if $h$ is assumed to be non-decreasing rather than strictly increasing?

  [You may assume without proof that a strictly increasing, continuous, function $w: \mathbb{R} \rightarrow \mathbb{R}$ is injective, and $w^{-1}: w(\mathbb{R}) \rightarrow \mathbb{R}$ is continuous.]

  comment

• Paper 2, Section II, H

  Analysis of Functions | Part II, 2021

  Define the Schwartz space, $\mathscr{S}\left(\mathbb{R}^{n}\right)$, and the space of tempered distributions, $\mathscr{S}^{\prime}\left(\mathbb{R}^{n}\right)$, stating what it means for a sequence to converge in each space.

  For a $C^{k}$ function $f: \mathbb{R}^{n} \rightarrow \mathbb{C}$, and non-negative integers $N, k$, we say $f \in X_{N, k}$ if

  $$\|f\|_{N, k}:=\sup _{x \in \mathbb{R}^{n} ;|\alpha| \leqslant k}\left|\left(1+|x|^{2}\right)^{\frac{N}{2}} D^{\alpha} f(x)\right|<\infty$$

  You may assume that $X_{N, k}$ equipped with $\|\cdot\|_{N, k}$ is a Banach space in which $\mathscr{S}\left(\mathbb{R}^{n}\right)$ is dense.

  (a) Show that if $u \in \mathscr{S}^{\prime}\left(\mathbb{R}^{n}\right)$ there exist $N, k \in \mathbb{Z}_{\geqslant 0}$ and $C>0$ such that

  $$|u[\phi]| \leqslant C\|\phi\|_{N, k} \text { for all } \phi \in \mathscr{S}\left(\mathbb{R}^{n}\right)$$

  Deduce that there exists a unique $\tilde{u} \in X_{N, k}^{\prime}$ such that $\tilde{u}[\phi]=u[\phi]$ for all $\phi \in \mathscr{S}\left(\mathbb{R}^{n}\right)$.

  (b) Recall that $v \in \mathscr{S}^{\prime}\left(\mathbb{R}^{n}\right)$ is positive if $v[\phi] \geqslant 0$ for all $\phi \in \mathscr{S}\left(\mathbb{R}^{n}\right)$ satisfying $\phi \geqslant 0$. Show that if $v \in \mathscr{S}^{\prime}\left(\mathbb{R}^{n}\right)$ is positive, then there exist $M \in \mathbb{Z}_{\geqslant 0}$ and $K>0$ such that

  $$|v[\phi]| \leqslant K\|\phi\|_{M, 0}, \quad \text { for all } \phi \in \mathscr{S}\left(\mathbb{R}^{n}\right)$$

  $\left[\right.$ Hint: Note that $\left.|\phi(x)| \leqslant\|\phi\|_{M, 0}\left(1+|x|^{2}\right)^{-\frac{M}{2}} \cdot\right]$

  comment

• Paper 3, Section II, H

  Analysis of Functions | Part II, 2021

  (a) State the Riemann-Lebesgue lemma. Show that the Fourier transform maps $\mathscr{S}\left(\mathbb{R}^{n}\right)$ to itself continuously.

  (b) For some $s \geqslant 0$, let $f \in L^{1}\left(\mathbb{R}^{3}\right) \cap H^{s}\left(\mathbb{R}^{3}\right)$. Consider the following system of equations for $\mathbf{B}: \mathbb{R}^{3} \rightarrow \mathbb{R}^{3}$

  $$\nabla \cdot \mathbf{B}=f, \quad \boldsymbol{\nabla} \times \mathbf{B}=\mathbf{0}$$

  Show that there exists a unique $\mathbf{B}=\left(B_{1}, B_{2}, B_{3}\right)$ solving the equations with $B_{j} \in$ $H^{s+1}\left(\mathbb{R}^{3}\right)$ for $j=1,2,3$. You need not find $\mathbf{B}$ explicitly, but should give an expression for the Fourier transform of $B_{j}$. Show that there exists a constant $C>0$ such that

  $$\left\|B_{j}\right\|_{H^{s+1}} \leqslant C\left(\|f\|_{L^{1}}+\|f\|_{H^{s}}\right), \quad j=1,2,3$$

  For what values of $s$ can we conclude that $B_{j} \in C^{1}\left(\mathbb{R}^{n}\right)$ ?

  comment

• Paper 4, Section II, $23 \mathrm{H}$

  Analysis of Functions | Part II, 2021

  Fix $1<p<\infty$ and let $q$ satisfy $p^{-1}+q^{-1}=1$

  (a) Let $\left(f_{j}\right)$ be a sequence of functions in $L^{p}\left(\mathbb{R}^{n}\right)$. For $f \in L^{p}\left(\mathbb{R}^{n}\right)$, what is meant by (i) $f_{j} \rightarrow f$ in $L^{p}\left(\mathbb{R}^{n}\right)$ and (ii) $f_{j} \rightarrow f$ in $L^{p}\left(\mathbb{R}^{n}\right)$ ? Show that if $f_{j} \rightarrow f$, then

  $$\|f\|_{L^{p}} \leqslant \liminf _{j \rightarrow \infty}\left\|f_{j}\right\|_{L^{p}}$$

  (b) Suppose that $\left(g_{j}\right)$ is a sequence with $g_{j} \in L^{p}\left(\mathbb{R}^{n}\right)$, and that there exists $K>0$ such that $\left\|g_{j}\right\|_{L^{p}} \leqslant K$ for all $j$. Show that there exists $g \in L^{p}\left(\mathbb{R}^{n}\right)$ and a subsequence $\left(g_{j_{k}}\right)_{k=1}^{\infty}$, such that for any sequence $\left(h_{k}\right)$ with $h_{k} \in L^{q}\left(\mathbb{R}^{n}\right)$ and $h_{k} \rightarrow h \in L^{q}\left(\mathbb{R}^{n}\right)$, we have

  $$\lim _{k \rightarrow \infty} \int_{\mathbb{R}^{n}} g_{j_{k}} h_{k} d x=\int_{\mathbb{R}^{n}} g h d x .$$

  Give an example to show that the result need not hold if the condition $h_{k} \rightarrow h$ is replaced by $h_{k} \rightarrow h$ in $L^{q}\left(\mathbb{R}^{n}\right)$.

  comment

Applications of Quantum Mechanics

• Paper 1, Section II, B

  Applications of Quantum Mechanics | Part II, 2021

  (a) Discuss the variational principle that allows one to derive an upper bound on the energy $E_{0}$ of the ground state for a particle in one dimension subject to a potential $V(x)$.

  If $V(x)=V(-x)$, how could you adapt the variational principle to derive an upper bound on the energy $E_{1}$ of the first excited state?

  (b) Consider a particle of mass $2 m=\hbar^{2}$ (in certain units) subject to a potential

  $$V(x)=-V_{0} e^{-x^{2}} \quad \text { with } \quad V_{0}>0$$

  (i) Using the trial wavefunction

  $$\psi(x)=e^{-\frac{1}{2} x^{2} a}$$

  with $a>0$, derive the upper bound $E_{0} \leqslant E(a)$, where

  $$E(a)=\frac{1}{2} a-V_{0} \frac{\sqrt{a}}{\sqrt{1+a}}$$

  (ii) Find the zero of $E(a)$ in $a>0$ and show that any extremum must obey

  $$(1+a)^{3}=\frac{V_{0}^{2}}{a} .$$

  (iii) By sketching $E(a)$ or otherwise, deduce that there must always be a minimum in $a>0$. Hence deduce the existence of a bound state.

  (iv) Working perturbatively in $0<V_{0} \ll 1$, show that

  $$-V_{0}<E_{0} \leqslant-\frac{1}{2} V_{0}^{2}+\mathcal{O}\left(V_{0}^{3}\right)$$

  [Hint: You may use that $\int_{-\infty}^{\infty} e^{-b x^{2}} d x=\sqrt{\frac{\pi}{b}}$ for $\left.b>0 .\right]$

  comment

• Paper 2, Section II, 36B

  Applications of Quantum Mechanics | Part II, 2021

  (a) The $s$-wave solution $\psi_{0}$ for the scattering problem of a particle of mass $m$ and momentum $\hbar k$ has the asymptotic form

  $$\psi_{0}(r) \sim \frac{A}{r}[\sin (k r)+g(k) \cos (k r)]$$

  Define the phase shift $\delta_{0}$ and verify that $\tan \delta_{0}=g(k)$.

  (b) Define the scattering amplitude $f$. For a spherically symmetric potential of finite range, starting from $\sigma_{T}=\int|f|^{2} d \Omega$, derive the expression

  $$\sigma_{T}=\frac{4 \pi}{k^{2}} \sum_{l=0}^{\infty}(2 l+1) \sin ^{2} \delta_{l}$$

  giving the cross-section $\sigma_{T}$ in terms of the phase shifts $\delta_{l}$ of the partial waves.

  (c) For $g(k)=-k / K$ with $K>0$, show that a bound state exists and compute its energy. Neglecting the contributions from partial waves with $l>0$, show that

  $$\sigma_{T} \approx \frac{4 \pi}{K^{2}+k^{2}}$$

  (d) For $g(k)=\gamma /\left(K_{0}-k\right)$ with $K_{0}>0, \gamma>0$ compute the $s$-wave contribution to $\sigma_{T}$. Working to leading order in $\gamma \ll K_{0}$, show that $\sigma_{T}$ has a local maximum at $k=K_{0}$. Interpret this fact in terms of a resonance and compute its energy and decay width.

  comment

• Paper 3, Section II, 34B

  Applications of Quantum Mechanics | Part II, 2021

  (a) In three dimensions, define a Bravais lattice $\Lambda$ and its reciprocal lattice $\Lambda^{*}$.

  A particle is subject to a potential $V(\mathbf{x})$ with $V(\mathbf{x})=V(\mathbf{x}+\mathbf{r})$ for $\mathbf{x} \in \mathbb{R}^{3}$ and $\mathbf{r} \in \Lambda$. State and prove Bloch's theorem and specify how the Brillouin zone is related to the reciprocal lattice.

  (b) A body-centred cubic lattice $\Lambda_{B C C}$ consists of the union of the points of a cubic lattice $\Lambda_{1}$ and all the points $\Lambda_{2}$ at the centre of each cube:

  $$\begin{aligned} \Lambda_{B C C} & \equiv \Lambda_{1} \cup \Lambda_{2}, \\ \Lambda_{1} & \equiv\left\{\mathbf{r} \in \mathbb{R}^{3}: \mathbf{r}=n_{1} \hat{\mathbf{i}}+n_{2} \hat{\mathbf{j}}+n_{3} \hat{\mathbf{k}}, \text { with } n_{1,2,3} \in \mathbb{Z}\right\}, \\ \Lambda_{2} & \equiv\left\{\mathbf{r} \in \mathbb{R}^{3}: \mathbf{r}=\frac{1}{2}(\hat{\mathbf{i}}+\hat{\mathbf{j}}+\hat{\mathbf{k}})+\mathbf{r}^{\prime}, \text { with } \mathbf{r}^{\prime} \in \Lambda_{1}\right\}, \end{aligned}$$

  where $\hat{\mathbf{i}}, \hat{\mathbf{j}}$ and $\hat{\mathbf{k}}$ are unit vectors parallel to the Cartesian coordinates in $\mathbb{R}^{3}$. Show that $\Lambda_{B C C}$ is a Bravais lattice and determine the primitive vectors $\mathbf{a}_{1}, \mathbf{a}_{2}$ and $\mathbf{a}_{3}$.

  Find the reciprocal lattice $\Lambda_{B C C}^{*} .$ Briefly explain what sort of lattice it is.

  $\left[\right.$ Hint: The matrix $M=\frac{1}{2}\left(\begin{array}{ccc}-1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1\end{array}\right)$ has inverse $M^{-1}=\left(\begin{array}{lll}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{array}\right)$.

  comment

• Paper 4, Section II, B

  Applications of Quantum Mechanics | Part II, 2021

  (a) Consider the nearly free electron model in one dimension with mass $m$ and periodic potential $V(x)=\lambda U(x)$ with $0<\lambda \ll 1$ and

  $$U(x)=\sum_{l=-\infty}^{\infty} U_{l} \exp \left(\frac{2 \pi i}{a} l x\right)$$

  Ignoring degeneracies, the energy spectrum of Bloch states with wavenumber $k$ is

  $$E(k)=E_{0}(k)+\lambda\langle k|U| k\rangle+\lambda^{2} \sum_{k^{\prime} \neq k} \frac{\left\langle k|U| k^{\prime}\right\rangle\left\langle k^{\prime}|U| k\right\rangle}{E_{0}(k)-E_{0}\left(k^{\prime}\right)}+\mathcal{O}\left(\lambda^{3}\right)$$

  where $\{|k\rangle\}$ are normalized eigenstates of the free Hamiltonian with wavenumber $k$. What is $E_{0}$ in this formula?

  If we impose periodic boundary conditions on the wavefunctions, $\psi(x)=\psi(x+L)$ with $L=N a$ and $N$ a positive integer, what are the allowed values of $k$ and $k^{\prime}$ ? Determine $\left\langle k|U| k^{\prime}\right\rangle$ for these allowed values.

  (b) State when the above expression for $E(k)$ ceases to be a good approximation and explain why. Quoting any result you need from degenerate perturbation theory, calculate to $\mathcal{O}(\lambda)$ the location and width of the band gaps.

  (c) Determine the allowed energy bands for each of the potentials

  $$\begin{aligned} &\text { (i) } V(x)=2 \lambda \cos \left(\frac{2 \pi x}{a}\right) \text {, } \\ &\text { (ii) } V(x)=\lambda a \sum_{n=-\infty}^{\infty} \delta(x-n a) \text {. } \end{aligned}$$

  (d) Briefly discuss a macroscopic physical consequence of the existence of energy bands.

  comment

Applied Probability

• Paper 1, Section II, 28K

  Applied Probability | Part II, 2021

  The particles of an Ideal Gas form a spatial Poisson process on $\mathbb{R}^{3}$ with constant intensity $z>0$, called the activity of the gas.

  (a) Prove that the independent mixture of two Ideal Gases with activities $z_{1}$ and $z_{2}$ is again an Ideal Gas. What is its activity? [You must prove any results about Poisson processes that you use. The independent mixture of two gases with particles $\Pi_{1} \subset \mathbb{R}^{3}$ and $\Pi_{2} \subset \mathbb{R}^{3}$ is given by $\left.\Pi_{1} \cup \Pi_{2} .\right]$

  (b) For an Ideal Gas of activity $z>0$, find the limiting distribution of

  $$\frac{N\left(V_{i}\right)-\mathbb{E} N\left(V_{i}\right)}{\sqrt{\left|V_{i}\right|}}$$

  as $i \rightarrow \infty$ for a given sequence of subsets $V_{i} \subset \mathbb{R}^{3}$ with $\left|V_{i}\right| \rightarrow \infty$.

  (c) Let $g: \mathbb{R}^{3} \rightarrow \mathbb{R}$ be a smooth non-negative function vanishing outside a bounded subset of $\mathbb{R}^{3}$. Find the mean and variance of $\sum_{x} g(x)$, where the sum runs over the particles $x \in \mathbb{R}^{3}$ of an ideal gas of activity $z>0$. [You may use the properties of spatial Poisson processes established in the lectures.]

  [Hint: recall that the characteristic function of a Poisson random variable with mean $\lambda$ is $\left.e^{\left(e^{i t}-1\right) \lambda} \cdot\right]$

  comment

• Paper 2, Section II, $28 K$

  Applied Probability | Part II, 2021

  Let $X$ be an irreducible, non-explosive, continuous-time Markov process on the state space $\mathbb{Z}$ with generator $Q=\left(q_{x, y}\right)_{x, y \in \mathbb{Z}}$.

  (a) Define its jump chain $Y$ and prove that it is a discrete-time Markov chain.

  (b) Define what it means for $X$ to be recurrent and prove that $X$ is recurrent if and only if its jump chain $Y$ is recurrent. Prove also that this is the case if the transition semigroup $\left(p_{x, y}(t)\right)$ satisfies

  $$\int_{0}^{\infty} p_{0,0}(t) d t=\infty$$

  (c) Show that $X$ is recurrent for at least one of the following generators:

  $$\begin{array}{cc} q_{x, y}=(1+|x|)^{-2} e^{-|x-y|^{2}} & (x \neq y), \\ q_{x, y}=(1+|x-y|)^{-2} e^{-|x|^{2}} & (x \neq y) . \end{array}$$

  [Hint: You may use that the semigroup associated with a $Q$-matrix on $\mathbb{Z}$ such that $q_{x, y}$ depends only on $x-y$ (and has sufficient decay) can be written as

  $$p_{x, y}(t)=\frac{1}{2 \pi} \int_{-\pi}^{\pi} e^{-t \lambda(k)} e^{i k(x-y)} d k$$

  where $\lambda(k)=\sum_{y} q_{0, y}\left(1-e^{i k y}\right)$. You may also find the bound $1-\cos x \leqslant x^{2} / 2$ useful. $]$

  comment

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

  Applied Probability | Part II, 2021

  (a) Customers arrive at a queue at the event times of a Poisson process of rate $\lambda$. The queue is served by two independent servers with exponential service times with parameter $\mu$ each. If the queue has length $n$, an arriving customer joins with probability $r^{n}$ and leaves otherwise (where $\left.r \in(0,1]\right)$. For which $\lambda>0, \mu>0$ and $r \in(0,1]$ is there a stationary distribution?

  (b) A supermarket allows a maximum of $N$ customers to shop at the same time. Customers arrive at the event times of a Poisson process of rate 1 , they enter the supermarket when possible, and they leave forever for another supermarket otherwise. Customers already in the supermarket pay and leave at the event times of an independent Poisson process of rate $\mu$. When is there a unique stationary distribution for the number of customers in the supermarket? If it exists, find it.

  (c) In the situation of part (b), started from equilibrium, show that the departure process is Poissonian.

  comment

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

  Applied Probability | Part II, 2021

  Let $(X(t))_{t \geqslant 0}$ be a continuous-time Markov process with state space $I=\{1, \ldots, n\}$ and generator $Q=\left(q_{i j}\right)_{i, j \in I}$ satisfying $q_{i j}=q_{j i}$ for all $i, j \in I$. The local time up to time $t>0$ of $X$ is the random vector $L(t)=\left(L_{i}(t)\right)_{i \in I} \in \mathbb{R}^{n}$ defined by

  $$L_{i}(t)=\int_{0}^{t} 1_{X(s)=i} d s \quad(i \in I)$$

  (a) Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be any function that is differentiable with respect to its second argument, and set

  $$f_{t}(i, \ell)=\mathbb{E}_{i} f(X(t), \ell+L(t)), \quad\left(i \in I, \ell \in \mathbb{R}^{n}\right)$$

  Show that

  $$\frac{\partial}{\partial t} f_{t}(i, \ell)=M f_{t}(i, \ell)$$

  where

  $$M f(i, \ell)=\sum_{j \in I} q_{i j} f(j, \ell)+\frac{\partial}{\partial \ell_{i}} f(i, \ell)$$

  (b) For $y \in \mathbb{R}^{n}$, write $y^{2}=\left(y_{i}^{2}\right)_{i \in I} \in[0, \infty)^{n}$ for the vector of squares of the components of $y$. Let $f: I \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function such that $f(i, \ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Using integration by parts, or otherwise, show that for all $i$

  $$-\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} \sum_{j=1}^{n} y_{j} M f\left(j, \frac{1}{2} y^{2}\right) d y=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) f\left(i, \frac{1}{2} y^{2}\right) d y,$$

  where $y^{T} Q y$ denotes $\sum_{k, m \in I} y_{k} q_{k m} y_{m}$.

  (c) Let $g: \mathbb{R}^{n} \rightarrow \mathbb{R}$ be a function with $g(\ell)=0$ whenever $\sum_{j}\left|\ell_{j}\right| \geqslant T$ for some fixed $T$. Given $t>0, j \in I$, now let

  $$f(i, \ell)=\mathbb{E}_{i}\left[g(\ell+L(t)) 1_{X(t)=j}\right]$$

  in part (b) and deduce, using part (a), that

  $$\begin{aligned} \int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right) y_{i} y_{j} g\left(\frac{1}{2} y^{2}\right) d y \\ &=\int_{\mathbb{R}^{n}} \exp \left(\frac{1}{2} y^{T} Q y\right)\left(\int_{0}^{\infty} \mathbb{E}_{i}\left[1_{X(t)=j} g\left(\frac{1}{2} y^{2}+L(t)\right)\right] d t\right) d y \end{aligned}$$

  [You may exchange the order of integrals and derivatives without justification.]

  comment

Asymptotic Methods

• Paper 2, Section II, 32A

  Asymptotic Methods | Part II, 2021

  (a) Let $x(t)$ and $\phi_{n}(t)$, for $n=0,1,2, \ldots$, be real-valued functions on $\mathbb{R}$.

  (i) Define what it means for the sequence $\left\{\phi_{n}(t)\right\}_{n=0}^{\infty}$ to be an asymptotic sequence as $t \rightarrow \infty$.

  (ii) Define what it means for $x(t)$ to have the asymptotic expansion

  $$x(t) \sim \sum_{n=0}^{\infty} a_{n} \phi_{n}(t) \quad \text { as } \quad t \rightarrow \infty$$

  (b) Use the method of stationary phase to calculate the leading-order asymptotic approximation as $x \rightarrow \infty$ of

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

  [You may assume that $\int_{-\infty}^{\infty} e^{i u^{2}} d u=\sqrt{\pi} e^{i \pi / 4}$.]

  (c) Use Laplace's method to calculate the leading-order asymptotic approximation as $x \rightarrow \infty$ of

  $$J(x)=\int_{0}^{1} \sinh \left(x\left(2 t^{4}-t^{2}\right)\right) d t$$

  [In parts (b) and (c) you should include brief qualitative reasons for the origin of the leading-order contributions, but you do not need to give a formal justification.]

  comment

• Paper 3, Section II, 30A

  Asymptotic Methods | Part II, 2021

  (a) Carefully state Watson's lemma.

  (b) Use the method of steepest descent and Watson's lemma to obtain an infinite asymptotic expansion of the function

  $$I(x)=\int_{-\infty}^{\infty} \frac{e^{-x\left(z^{2}-2 i z\right)}}{1-i z} d z \quad \text { as } \quad x \rightarrow \infty$$

  comment

• Paper 4, Section II, A

  Asymptotic Methods | Part II, 2021

  (a) Classify the nature of the point at $\infty$ for the ordinary differential equation

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

  (b) Find a transformation from $(*)$ to an equation of the form

  $$u^{\prime \prime}+q(x) u=0$$

  and determine $q(x)$.

  (c) Given $u(x)$ satisfies ( $\dagger$, use the Liouville-Green method to find the first three terms in an asymptotic approximation as $x \rightarrow \infty$ for $u(x)$, verifying the consistency of any approximations made.

  (d) Hence obtain corresponding asymptotic approximations as $x \rightarrow \infty$ of two linearly independent solutions $y(x)$ of $(*)$.

  comment

Automata and Formal Languages

• Paper 1, Section I, F

  Automata and Formal Languages | Part II, 2021

  Let $f_{n, k}$ be the partial function on $k$ variables that is computed by the $n$th machine (or the empty function if $n$ does not encode a machine).

  Define the halting set $\mathbb{K}$.

  Given $A, B \subseteq \mathbb{N}$, what is a many-one reduction $A \leqslant_{m} B$ of $A$ to $B$ ?

  State the $s-m-n$ theorem and use it to show that a subset $X$ of $\mathbb{N}$ is recursively enumerable if and only if $X \leqslant_{m} \mathbb{K}$.

  Give an example of a set $S \subseteq \mathbb{N}$ with $\mathbb{K} \leqslant_{m} S$ but $\mathbb{K} \neq S$.

  [You may assume that $\mathbb{K}$ is recursively enumerable and that $0 \notin \mathbb{K}$.]

  comment

• Paper 1, Section II, F

  Automata and Formal Languages | Part II, 2021

  For $k \geqslant 1$ give the definition of a partial recursive function $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ in terms of basic functions, composition, recursion and minimisation.

  Show that the following partial functions from $\mathbb{N}$ to $\mathbb{N}$ are partial recursive: (i) $s(n)= \begin{cases}1 & n=0 \\ 0 & n \geqslant 1\end{cases}$ (ii) $r(n)= \begin{cases}1 & n \text { odd } \\ 0 & n \text { even } \text {, }\end{cases}$ (iii) $p(n)=\left\{\begin{array}{l}\text { undefined if } n \text { is odd } \\ 0 \text { if } n \text { is even }\end{array}\right.$

  Which of these can be defined without using minimisation?

  What is the class of functions $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ that can be defined using only basic functions and composition? [Hint: See which functions you can obtain and then show that these form a class that is closed with respect to the above.]

  Show directly that every function in this class is computable.

  comment

• Paper 2, Section I, F

  Automata and Formal Languages | Part II, 2021

  Assuming the definition of a deterministic finite-state automaton (DFA) $D=$ $\left(Q, \Sigma, \delta, q_{0}, F\right)$, what is the extended transition function $\hat{\delta}$ for $D$ ? Also assuming the definition of a nondeterministic finite-state automaton (NFA) $N$, what is $\hat{\delta}$ in this case?

  Define the languages accepted by $D$ and $N$, respectively, in terms of $\hat{\delta}$.

  Given an NFA $N$ as above, describe the subset construction and show that the resulting DFA $\bar{N}$ accepts the same language as $N$. If $N$ has one accept state then how many does $\bar{N}$ have?

  comment

• Paper 3, Section I, F

  Automata and Formal Languages | Part II, 2021

  Define a regular expression $R$ and explain how this gives rise to a language $\mathcal{L}(R)$.

  Define a deterministic finite-state automaton $D$ and the language $\mathcal{L}(D)$ that it accepts.

  State the relationship between languages obtained from regular expressions and languages accepted by deterministic finite-state automata.

  Let $L$ and $M$ be regular languages. Is $L \cup M$ always regular? What about $L \cap M$ ?

  Now suppose that $L_{1}, L_{2}, \ldots$ are regular languages. Is the countable union $\bigcup L_{i}$ always regular? What about the countable intersection $\bigcap L_{i}$ ?

  comment

• Paper 3, Section II, $12 F$

  Automata and Formal Languages | Part II, 2021

  Suppose that $G$ is a context-free grammar without $\epsilon$-productions. Given a derivation of some word $w$ in the language $L$ of $G$, describe a parse tree for this derivation.

  State and prove the pumping lemma for $L$. How would your proof differ if you did not assume that $G$ was in Chomsky normal form, but merely that $G$ has no $\epsilon$ - or unit productions?

  For the alphabet $\Sigma=\{a, b\}$ of terminal symbols, state whether the following languages over $\Sigma$ are context free, giving reasons for your answer. (i) $\left\{a^{i} b^{i} a^{i} \mid i \geqslant 0\right\}$, (ii) $\left\{a^{i} b^{j} \mid i \geqslant j \geqslant 0\right\}$, (iii) $\left\{w a b w \mid w \in\{a, b\}^{*}\right\}$.

  comment

• Paper 4, Section I, $4 \mathrm{~F}$

  Automata and Formal Languages | Part II, 2021

  State the pumping lemma for regular languages.

  Which of the following languages over the alphabet $\{0,1\}$ are regular?

  (i) $\left\{0^{i} 1^{i} 01 \mid i \geqslant 0\right\}$.

  (ii) $\left\{w \bar{w} \mid w \in\{0,1\}^{*}\right\}$ where $\bar{w}$ is the reverse of the word $w$.

  (iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ does not contain the subwords 01 or 10$\}$.

  comment

Classical Dynamics

• Paper 1, Section I, D

  Classical Dynamics | Part II, 2021

  Two equal masses $m$ move along a straight line between two stationary walls. The mass on the left is connected to the wall on its left by a spring of spring constant $k_{1}$, and the mass on the right is connected to the wall on its right by a spring of spring constant $k_{2}$. The two masses are connected by a third spring of spring constant $k_{3}$.

  (a) Show that the Lagrangian of the system can be written in the form

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

  where $x_{i}(t)$, for $i=1,2$, are the displacements of the two masses from their equilibrium positions, and $T_{i j}$ and $V_{i j}$ are symmetric $2 \times 2$ matrices that should be determined.

  (b) Let

  $$k_{1}=k(1+\epsilon \delta), \quad k_{2}=k(1-\epsilon \delta), \quad k_{3}=k \epsilon,$$

  where $k>0, \epsilon>0$ and $|\epsilon \delta|<1$. Using Lagrange's equations of motion, show that the angular frequencies $\omega$ of the normal modes of the system are given by

  $$\omega^{2}=\lambda \frac{k}{m}$$

  where

  $$\lambda=1+\epsilon\left(1 \pm \sqrt{1+\delta^{2}}\right)$$

  comment

• Paper 2, Section I, D

  Classical Dynamics | Part II, 2021

  Show that, in a uniform gravitational field, the net gravitational torque on a system of particles, about its centre of mass, is zero.

  Let $S$ be an inertial frame of reference, and let $S^{\prime}$ be the frame of reference with the same origin and rotating with angular velocity $\boldsymbol{\omega}(t)$ with respect to $S$. You may assume that the rates of change of a vector $v$ observed in the two frames are related by

  $$\left(\frac{d \mathbf{v}}{d t}\right)_{S}=\left(\frac{d \mathbf{v}}{d t}\right)_{S^{\prime}}+\omega \times \mathbf{v} .$$

  Derive Euler's equations for the torque-free motion of a rigid body.

  Show that the general torque-free motion of a symmetric top involves precession of the angular-velocity vector about the symmetry axis of the body. Determine how the direction and rate of precession depend on the moments of inertia of the body and its angular velocity.

  comment

• Paper 2, Section II, D

  Classical Dynamics | Part II, 2021

  (a) Show that the Hamiltonian

  $$H=\frac{1}{2} p^{2}+\frac{1}{2} \omega^{2} q^{2},$$

  where $\omega$ is a positive constant, describes a simple harmonic oscillator with angular frequency $\omega$. Show that the energy $E$ and the action $I$ of the oscillator are related by $E=\omega I$.

  (b) Let $0<\epsilon<2$ be a constant. Verify that the differential equation

  $$\ddot{x}+\frac{x}{(\epsilon t)^{2}}=0 \quad \text { subject to } \quad x(1)=0, \quad \dot{x}(1)=1$$

  is solved by

  $$x(t)=\frac{\sqrt{t}}{k} \sin (k \log t)$$

  when $t>1$, where $k$ is a constant you should determine in terms of $\epsilon$.

  (c) Show that the solution in part (b) obeys

  $$\frac{1}{2} \dot{x}^{2}+\frac{1}{2} \frac{x^{2}}{(\epsilon t)^{2}}=\frac{1-\cos (2 k \log t)+2 k \sin (2 k \log t)+4 k^{2}}{8 k^{2} t}$$

  Hence show that the fractional variation of the action in the limit $\epsilon \ll 1$ is $O(\epsilon)$, but that these variations do not accumulate. Comment on this behaviour in relation to the theory of adiabatic invariance.

  comment

• Paper 3 , Section I, D

  Classical Dynamics | Part II, 2021

  The Lagrangian of a particle of mass $m$ and charge $q$ in an electromagnetic field takes the form

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

  Explain the meaning of $\phi$ and $\mathbf{A}$, and how they are related to the electric and magnetic fields.

  Obtain the canonical momentum $\mathbf{p}$ and the Hamiltonian $H(\mathbf{r}, \mathbf{p}, t)$.

  Suppose that the electric and magnetic fields have Cartesian components $(E, 0,0)$ and $(0,0, B)$, respectively, where $E$ and $B$ are positive constants. Explain why the Hamiltonian of the particle can be taken to be

  $$H=\frac{p_{x}^{2}}{2 m}+\frac{\left(p_{y}-q B x\right)^{2}}{2 m}+\frac{p_{z}^{2}}{2 m}-q E x$$

  State three independent integrals of motion in this case.

  comment

• Paper 4, Section I, D

  Classical Dynamics | Part II, 2021

  Briefly describe a physical object (a Lagrange top) whose Lagrangian is

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

  Explain the meaning of the symbols in this equation.

  Write down three independent integrals of motion for this system, and show that the nutation of the top is governed by the equation

  $$\dot{u}^{2}=f(u),$$

  where $u=\cos \theta$ and $f(u)$ is a certain cubic function that you need not determine.

  comment

• Paper 4, Section II, 15D

  Classical Dynamics | Part II, 2021

  (a) Let $(\mathbf{q}, \mathbf{p})$ be a set of canonical phase-space variables for a Hamiltonian system with $n$ degrees of freedom. Define the Poisson bracket $\{f, g\}$ of two functions $f(\mathbf{q}, \mathbf{p})$ and $g(\mathbf{q}, \mathbf{p})$. Write down the canonical commutation relations that imply that a second set $(\mathbf{Q}, \mathbf{P})$ of phase-space variables is also canonical.

  (b) Consider the near-identity transformation

  $$\mathbf{Q}=\mathbf{q}+\delta \mathbf{q}, \quad \mathbf{P}=\mathbf{p}+\delta \mathbf{p}$$

  where $\delta \mathbf{q}(\mathbf{q}, \mathbf{p})$ and $\delta \mathbf{p}(\mathbf{q}, \mathbf{p})$ are small. Determine the approximate forms of the canonical commutation relations, accurate to first order in $\delta \mathbf{q}$ and $\delta \mathbf{p}$. Show that these are satisfied when

  $$\delta \mathbf{q}=\epsilon \frac{\partial F}{\partial \mathbf{p}}, \quad \delta \mathbf{p}=-\epsilon \frac{\partial F}{\partial \mathbf{q}}$$

  where $\epsilon$ is a small parameter and $F(\mathbf{q}, \mathbf{p})$ is some function of the phase-space variables.

  (c) In the limit $\epsilon \rightarrow 0$ this near-identity transformation is called the infinitesimal canonical transformation generated by $F$. Let $H(\mathbf{q}, \mathbf{p})$ be an autonomous Hamiltonian. Show that the change in the Hamiltonian induced by the infinitesimal canonical transformation is

  $$\delta H=-\epsilon\{F, H\} .$$

  Explain why $F$ is an integral of motion if and only if the Hamiltonian is invariant under the infinitesimal canonical transformation generated by $F$.

  (d) The Hamiltonian of the gravitational $N$-body problem in three-dimensional space is

  $$H=\frac{1}{2} \sum_{i=1}^{N} \frac{\left|\mathbf{p}_{i}\right|^{2}}{2 m_{i}}-\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \frac{G m_{i} m_{j}}{\left|\mathbf{r}_{i}-\mathbf{r}_{j}\right|}$$

  where $m_{i}, \mathbf{r}_{i}$ and $\mathbf{p}_{i}$ are the mass, position and momentum of body $i$. Determine the form of $F$ and the infinitesimal canonical transformation that correspond to the translational symmetry of the system.

  comment

Coding and Cryptography

• Paper 1, Section I, $3 K$

  Coding and Cryptography | Part II, 2021

  Let $C$ be an $[n, m, d]$ code. Define the parameters $n, m$ and $d$. In each of the following cases define the new code and give its parameters.

  (i) $C^{+}$is the parity extension of $C$.

  (ii) $C^{-}$is the punctured code (assume $n \geqslant 2$ ).

  (iii) $\bar{C}$ is the shortened code (assume $n \geqslant 2$ ).

  Let $C=\{000,100,010,001,110,101,011,111\}$. Suppose the parity extension of $C$ is transmitted through a binary symmetric channel where $p$ is the probability of a single-bit error in the channel. Calculate the probability that an error in the transmission of a single codeword is not noticed.

  comment

• Paper 1, Section II, $11 K$

  Coding and Cryptography | Part II, 2021

  Let $\Sigma_{1}=\left\{\mu_{1}, \ldots, \mu_{N}\right\}$ be a finite alphabet and $X$ a random variable that takes each value $\mu_{i}$ with probability $p_{i}$. Define the entropy $H(X)$ of $X$.

  Suppose $\Sigma_{2}=\{0,1\}$ and $c: \Sigma_{1} \rightarrow \Sigma_{2}^{*}$ is a decipherable code. Write down an expression for the expected word length $E(S)$ of $c$.

  Prove that the minimum expected word length $S^{*}$ of a decipherable code $c: \Sigma_{1} \rightarrow \Sigma_{2}^{*}$ satisfies

  $$H(X) \leqslant S^{*}<H(X)+1 .$$

  [You can use Kraft's and Gibbs' inequalities as long as they are clearly stated.]

  Suppose a decipherable binary code has word lengths $s_{1}, \ldots, s_{N}$. Show that

  $$N \log N \leqslant s_{1}+\cdots+s_{N} .$$

  Suppose $X$ is a source that emits $N$ sourcewords $a_{1}, \ldots, a_{N}$ and $p_{i}$ is the probability that $a_{i}$ is emitted, where $p_{1} \geqslant p_{2} \geqslant \cdots \geqslant p_{N}$. Let $b_{1}=0$ and $b_{i}=\sum_{j=1}^{i-1} p_{j}$ for $2 \leqslant i \leqslant N$. Let $s_{i}=\left\lceil-\log p_{i}\right\rceil$ for $1 \leqslant i \leqslant N$. Now define a code $c$ by $c\left(a_{i}\right)=b_{i}^{*}$ where $b_{i}^{*}$ is the (fractional part of the) binary expansion of $b_{i}$ to $s_{i}$ decimal places. Prove that this defines a decipherable code.

  What does it mean for a code to be optimal? Is the code $c$ defined in the previous paragraph in terms of the $b_{i}^{*}$ necessarily optimal? Justify your answer.

  comment

• Paper 2, Section I, K

  Coding and Cryptography | Part II, 2021

  State Shannon's noisy coding theorem for a binary symmetric channel, defining the terms involved.

  Suppose a channel matrix, with output alphabet of size $n$, is such that the entries in each row are the elements of the set $\left\{p_{1}, \ldots, p_{n}\right\}$ in some order. Further suppose that all columns are permutations of one another. Show that the channel's information capacity $C$ is given by

  $$C=\log n+\sum_{i=1}^{n} p_{i} \log p_{i}$$

  Show that the information capacity of the channel matrix

  $$\left(\begin{array}{cccc} \frac{1}{3} & \frac{1}{3} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} \end{array}\right)$$