• # Paper 4, Section II, F

Let $P_{0}, \ldots, P_{n}$ be a basis for the homogeneous polynomials of degree $n$ in variables $Z_{0}$ and $Z_{1}$. Then the image of the $\operatorname{map} \mathbb{P}^{1} \rightarrow \mathbb{P}^{n}$ given by

$\left[Z_{0}, Z_{1}\right] \mapsto\left[P_{0}\left(Z_{0}, Z_{1}\right), \ldots, P_{n}\left(Z_{0}, Z_{1}\right)\right]$

is called a rational normal curve.

Let $p_{1}, \ldots, p_{n+3}$ be a collection of points in general linear position in $\mathbb{P}^{n}$. Prove that there exists a unique rational normal curve in $\mathbb{P}^{n}$ passing through these points.

Choose a basis of homogeneous polynomials of degree 3 as above, and give generators for the homogeneous ideal of the corresponding rational normal curve.

comment

• # Paper 4 , Section II, 21F

In this question, you may assume all spaces involved are triangulable.

(a) (i) State and prove the Mayer-Vietoris theorem. [You may assume the theorem that states that a short exact sequence of chain complexes gives rise to a long exact sequence of homology groups.]

(ii) Use Mayer-Vietoris to calculate the homology groups of an oriented surface of genus $g$.

(b) Let $S$ be an oriented surface of genus $g$, and let $D_{1}, \ldots, D_{n}$ be a collection of mutually disjoint closed subsets of $S$ with each $D_{i}$ homeomorphic to a two-dimensional disk. Let $D_{i}^{\circ}$ denote the interior of $D_{i}$, homeomorphic to an open two-dimensional disk, and let

$T:=S \backslash\left(D_{1}^{\circ} \cup \cdots \cup D_{n}^{\circ}\right)$

Show that

$H_{i}(T)= \begin{cases}\mathbb{Z} & i=0 \\ \mathbb{Z}^{2 g+n-1} & i=1 \\ 0 & \text { otherwise }\end{cases}$

(c) Let $T$ be the surface given in (b) when $S=S^{2}$ and $n=3$. Let $f: T \rightarrow S^{1} \times S^{1}$ be a map. Does there exist a map $g: S^{1} \times S^{1} \rightarrow T$ such that $f \circ g$ is homotopic to the identity map? Justify your answer.

comment

• # Paper 4, Section II, 23I

(a) Define the Sobolev space $H^{s}\left(\mathbb{R}^{n}\right)$ for $s \in \mathbb{R}$.

(b) Let $k$ be a non-negative integer and let $s>k+\frac{n}{2}$. Show that if $u \in H^{s}\left(\mathbb{R}^{n}\right)$ then there exists $u^{*} \in C^{k}\left(\mathbb{R}^{n}\right)$ with $u=u^{*}$ almost everywhere.

(c) Show that if $f \in H^{s}\left(\mathbb{R}^{n}\right)$ for some $s \in \mathbb{R}$, there exists a unique $u \in H^{s+4}\left(\mathbb{R}^{n}\right)$ which solves:

$\Delta \Delta u+\Delta u+u=f$

in a distributional sense. Prove that there exists a constant $C>0$, independent of $f$, such that:

$\|u\|_{H^{s+4}} \leqslant C\|f\|_{H^{s}}$

For which $s$ will $u$ be a classical solution?

comment

• # Paper 4, Section II, $34 C$

(a) For a particle of charge $q$ moving in an electromagnetic field with vector potential $\boldsymbol{A}$ and scalar potential $\phi$, write down the classical Hamiltonian and the equations of motion.

(b) Consider the vector and scalar potentials

$\boldsymbol{A}=\frac{B}{2}(-y, x, 0), \quad \phi=0$

(i) Solve the equations of motion. Define and compute the cyclotron frequency $\omega_{B}$.

(ii) Write down the quantum Hamiltonian of the system in terms of the angular momentum operator

$L_{z}=x p_{y}-y p_{x}$

Show that the states

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

for any function $f$, are energy eigenstates and compute their energy. Define Landau levels and discuss this result in relation to them.

(iii) Show that for $f(w)=w^{M}$, the wavefunctions in ( $\dagger$ ) are eigenstates of angular momentum and compute the corresponding eigenvalue. These wavefunctions peak in a ring around the origin. Estimate its radius. Using these two facts or otherwise, estimate the degeneracy of Landau levels.

comment

• # Paper 4, Section II, K

(i) Explain the notation $\mathrm{M}(\lambda) / \mathrm{M}(\mu) / 1$ in the context of queueing theory. [In the following, you may use without proof the fact that $\pi_{n}=(\lambda / \mu)^{n}$ is the invariant distribution of such a queue when $0<\lambda<\mu$.

(ii) In a shop queue, some customers rejoin the queue after having been served. Let $\lambda, \beta \in(0, \infty)$ and $\delta \in(0,1)$. Consider a $\mathrm{M}(\lambda) / \mathrm{M}(\mu) / 1$ queue subject to the modification that, on completion of service, each customer leaves the shop with probability $\delta$, or rejoins the shop queue with probability $1-\delta$. Different customers behave independently of one another, and all service times are independent random variables.

Find the distribution of the total time a given customer spends being served by the server. Hence show that equilibrium is possible if $\lambda<\delta \mu$, and find the invariant distribution of the queue-length in this case.

(iii) Show that, in equilibrium, the departure process is Poissonian, whereas, assuming the rejoining customers go to the end of the queue, the process of customers arriving at the queue (including the rejoining ones) is not Poissonian.

comment

• # Paper 4, Section II, A

Consider the differential equation

$\tag{†} y^{\prime \prime}-y^{\prime}-\frac{2(x+1)}{x^{2}} y=0$

(i) Classify what type of regularity/singularity equation $(†)$ has at $x=\infty$.

(ii) Find a transformation that maps equation ($†$) to an equation of the form

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

(iii) Find the leading-order term of the asymptotic expansions of the solutions of equation $(*)$, as $x \rightarrow \infty$, using the Liouville-Green method.

(iv) Derive the leading-order term of the asymptotic expansion of the solutions $y$ of ($†$). Check that one of them is an exact solution for $(†)$.

comment

• # Paper 4, Section I, $4 F$

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

Describe without proof each stage in the process of converting a CFG $G=$ $(N, \Sigma, P, S)$ into an equivalent CFG $\bar{G}$ which is in CNF. For each of these stages, when are the nonterminals $N$ left unchanged? What about the terminals $\Sigma$ and the generated language $\mathcal{L}(G)$ ?

Give an example of a CFG $G$ whose generated language $\mathcal{L}(G)$ is infinite and equal to $\mathcal{L}(\bar{G})$.

comment

• # Paper 4, Section I, B

Derive expressions for the angular momentum and kinetic energy of a rigid body in terms of its mass $M$, the position $\mathbf{X}(t)$ of its centre of mass, its inertia tensor $I$ (which should be defined) about its centre of mass, and its angular velocity $\boldsymbol{\omega}$.

A spherical planet of mass $M$ and radius $R$ has density proportional to $r^{-1} \sin (\pi r / R)$. Given that $\int_{0}^{\pi} x \sin x d x=\pi$ and $\int_{0}^{\pi} x^{3} \sin x d x=\pi\left(\pi^{2}-6\right)$, evaluate the inertia tensor of the planet in terms of $M$ and $R$.

comment
• # Paper 4, Section II, B

(a) Explain how the Hamiltonian $H(\mathbf{q}, \mathbf{p}, t)$ of a system can be obtained from its Lagrangian $L(\mathbf{q}, \dot{\mathbf{q}}, t)$. Deduce that the action can be written as

$S=\int(\mathbf{p} \cdot d \mathbf{q}-H d t)$

Show that Hamilton's equations are obtained if the action, computed between fixed initial and final configurations $\mathbf{q}\left(t_{1}\right)$ and $\mathbf{q}\left(t_{2}\right)$, is minimized with respect to independent variations of $\mathbf{q}$ and $\mathbf{p}$.

(b) Let $(\mathbf{Q}, \mathbf{P})$ be a new set of coordinates on the same phase space. If the old and new coordinates are related by a type-2 generating function $F_{2}(\mathbf{q}, \mathbf{P}, t)$ such that

$\mathbf{p}=\frac{\partial F_{2}}{\partial \mathbf{q}}, \quad \mathbf{Q}=\frac{\partial F_{2}}{\partial \mathbf{P}}$

deduce that the canonical form of Hamilton's equations applies in the new coordinates, but with a new Hamiltonian given by

$K=H+\frac{\partial F_{2}}{\partial t}$

(c) For each of the Hamiltonians (i) $H=H(p)$, (ii) $H=\frac{1}{2}\left(q^{2}+p^{2}\right)$,

express the general solution $(q(t), p(t))$ at time $t$ in terms of the initial values given by $(Q, P)=(q(0), p(0))$ at time $t=0$. In each case, show that the transformation from $(q, p)$ to $(Q, P)$ is canonical for all values of $t$, and find the corresponding generating function $F_{2}(q, P, t)$ explicitly.

comment

• # Paper 4, Section I, I

(a) What does it mean to say that a cipher has perfect secrecy? Show that if a cipher has perfect secrecy then there must be at least as many possible keys as there are possible plaintext messages. What is a one-time pad? Show that a one-time pad has perfect secrecy.

(b) I encrypt a binary sequence $a_{1}, a_{2}, \ldots, a_{N}$ using a one-time pad with key sequence $k_{1}, k_{2}, k_{3}, \ldots .$ I transmit $a_{1}+k_{1}, a_{2}+k_{2}, \ldots, a_{N}+k_{N}$ to you. Then, by mistake, I also transmit $a_{1}+k_{2}, a_{2}+k_{3}, \ldots, a_{N}+k_{N+1}$ to you. Assuming that you know I have made this error, and that my message makes sense, how would you go about finding my message? Can you now decipher other messages sent using the same part of the key sequence? Briefly justify your answer.

comment

• # Paper 4 , Section I, D

At temperature $T$ and chemical potential $\mu$, the number density of a non-relativistic particle species with mass $m \gg k_{B} T / c^{2}$ is given by

$n=g\left(\frac{m k_{B} T}{2 \pi \hbar^{2}}\right)^{3 / 2} e^{-\left(m c^{2}-\mu\right) / k_{B} T},$

where $g$ is the number of degrees of freedom of this particle.

At recombination, electrons and protons combine to form hydrogen. Use the result above to derive the Saha equation

$n_{H} \approx n_{e}^{2}\left(\frac{2 \pi \hbar^{2}}{m_{e} k_{B} T}\right)^{3 / 2} e^{E_{\mathrm{bind}} / k_{B} T}$

where $n_{H}$ is the number density of hydrogen atoms, $n_{e}$ the number density of electrons, $m_{e}$ the mass of the electron and $E_{\text {bind }}$ the binding energy of hydrogen. State any assumptions that you use in this derivation.

comment

• # Paper 4, Section II, I

(a) State the Gauss-Bonnet theorem for compact regular surfaces $S \subset \mathbb{R}^{3}$ without boundary. Identify all expressions occurring in any formulae.

(b) Let $S \subset \mathbb{R}^{3}$ be a compact regular surface without boundary and suppose that its Gaussian curvature $K(x) \geqslant 0$ for all $x \in S$. Show that $S$ is diffeomorphic to the sphere.

Let $S_{n}$ be a sequence of compact regular surfaces in $\mathbb{R}^{3}$ and let $K_{n}(x)$ denote the Gaussian curvature of $S_{n}$ at $x \in S_{n}$. Suppose that

$\limsup _{n \rightarrow \infty} \inf _{x \in S_{n}} K_{n}(x) \geqslant 0$

(c) Give an example to show that it does not follow that for all sufficiently large $n$ the surface $S_{n}$ is diffeomorphic to the sphere.

(d) Now assume, in addition to $(\star)$, that all of the following conditions hold:

(1) There exists a constant $R<\infty$ such that for all $n, S_{n}$ is contained in a ball of radius $R$ around the origin.

(2) There exists a constant $M<\infty$ such that $\operatorname{Area}\left(S_{n}\right) \leqslant M$ for all $n$.

(3) There exists a constant $\epsilon_{0}>0$ such that for all $n$, all points $p \in S_{n}$ admit a geodesic polar coordinate system centred at $p$ of radius at least $\epsilon_{0}$.

(4) There exists a constant $C<\infty$ such that on all such geodesic polar neighbourhoods, $\left|\partial_{r} K_{n}\right| \leqslant C$ for all $n$, where $r$ denotes a geodesic polar coordinate.

(i) Show that for all sufficiently large $n$, the surface $S_{n}$ is diffeomorphic to the sphere. [Hint: It may be useful to identify a geodesic polar ball $B\left(p_{n}, \epsilon_{0}\right)$ in each $S_{n}$ for which $\int_{B\left(p_{n}, \epsilon_{0}\right)} K_{n} d A$ is bounded below by a positive constant independent of $n$.]

(ii) Explain how your example from (c) fails to satisfy one or more of these extra conditions (1)-(4).

[You may use without proof the standard computations for geodesic polar coordinates: $E=1, F=0, \lim _{r \rightarrow 0} G(r, \theta)=0, \lim _{r \rightarrow 0}(\sqrt{G})_{r}(r, \theta)=1$, and $\left.(\sqrt{G})_{r r}=-K \sqrt{G} .\right]$

comment

• # Paper 4, Section II, E

(a) Let $F: I \rightarrow I$ be a continuous map defined on an interval $I \subset \mathbb{R}$. Define what it means (i) for $F$ to have a horseshoe and (ii) for $F$ to be chaotic. [Glendinning's definition should be used throughout this question.]

(b) Consider the map defined on the interval $[-1,1]$ by

$F(x)=1-\mu|x|$

with $0<\mu \leqslant 2$.

(i) Sketch $F(x)$ and $F^{2}(x)$ for a case when $0<\mu<1$ and a case when $1<\mu<2$.

(ii) Describe fully the long term dynamics for $0<\mu<1$. What happens for $\mu=1$ ?

(iii) When does $F$ have a horseshoe? When does $F^{2}$ have a horseshoe?

(iv) For what values of $\mu$ is the map $F$ chaotic?

comment

• # Paper 4 , Section II, 36D

(a) A dielectric medium exhibits a linear response if the electric displacement $\mathbf{D}(\mathbf{x}, t)$ and magnetizing field $\mathbf{H}(\mathbf{x}, t)$ are related to the electric and magnetic fields, $\mathbf{E}(\mathbf{x}, t)$ and $\mathbf{B}(\mathbf{x}, t)$, as

$\mathbf{D}=\epsilon \mathbf{E}, \quad \mathbf{B}=\mu \mathbf{H}$

where $\epsilon$ and $\mu$ are constants characterising the electric and magnetic polarisability of the material respectively. Write down the Maxwell equations obeyed by the fields $\mathbf{D}, \mathbf{H}, \mathbf{B}$ and $\mathbf{E}$ in this medium in the absence of free charges or currents.

(b) Two such media with constants $\epsilon_{-}$and $\epsilon_{+}$(but the same $\mu$ ) fill the regions $x<0$ and $x>0$ respectively in three-dimensions with Cartesian coordinates $(x, y, z)$.

(i) Starting from Maxwell's equations, derive the appropriate boundary conditions at $x=0$ for a time-independent electric field $\mathbf{E}(\mathbf{x})$.

(ii) Consider a candidate solution of Maxwell's equations describing the reflection and transmission of an incident electromagnetic wave of wave vector $\mathbf{k}_{I}$ and angular frequency $\omega_{I}$ off the interface at $x=0$. The electric field is given as,

$\mathbf{E}(\mathbf{x}, t)=\left\{\begin{array}{cc} \sum_{X=I, R} \operatorname{Im}\left[\mathbf{E}_{X} \exp \left(i \mathbf{k}_{X} \cdot \mathbf{x}-i \omega_{X} t\right)\right], & x<0 \\ \operatorname{Im}\left[\mathbf{E}_{T} \exp \left(i \mathbf{k}_{T} \cdot \mathbf{x}-i \omega_{T} t\right)\right], & x>0 \end{array}\right.$

where $\mathbf{E}_{I}, \mathbf{E}_{R}$ and $\mathbf{E}_{T}$ are constant real vectors and $\operatorname{Im}[z]$ denotes the imaginary part of a complex number $z$. Give conditions on the parameters $\mathbf{E}_{X}, \mathbf{k}_{X}, \omega_{X}$ for $X=I, R, T$, such that the above expression for the electric field $\mathbf{E}(\mathbf{x}, t)$ solves Maxwell's equations for all $x \neq 0$, together with an appropriate magnetic field $\mathbf{B}(\mathbf{x}, t)$ which you should determine.

(iii) We now parametrize the incident wave vector as $\mathbf{k}_{I}=k_{I}\left(\cos \left(\theta_{I}\right) \hat{\mathbf{i}}_{x}+\sin \left(\theta_{I}\right) \hat{\mathbf{i}}_{z}\right)$, where $\hat{\mathbf{i}}_{x}$ and $\hat{\mathbf{i}}_{z}$ are unit vectors in the $x$ - and $z$-directions respectively, and choose the incident polarisation vector to satisfy $\mathbf{E}_{I} \cdot \hat{\mathbf{i}}_{x}=0$. By imposing appropriate boundary conditions for $\mathbf{E}(\mathbf{x}, t)$ at $x=0$, which you may assume to be the same as those for the time-independent case considered above, determine the Cartesian components of the wavevector $\mathbf{k}_{T}$ as functions of $k_{I}, \theta_{I}, \epsilon_{+}$and $\epsilon_{-}$.

(iv) For $\epsilon_{+}<\epsilon_{-}$find a critical value $\theta_{I}^{\text {cr }}$ of the angle of incidence $\theta_{I}$ above which there is no real solution for the wavevector $\mathbf{k}_{T}$. Write down a solution for $\mathbf{E}(\mathbf{x}, t)$ when $\theta_{I}>\theta_{I}^{\mathrm{cr}}$ and comment on its form.

comment

• # Paper 4 , Section II, 38B

Consider a two-dimensional horizontal vortex sheet of strength $U$ in a homogeneous inviscid fluid at height $h$ above a horizontal rigid boundary at $y=0$ so that the fluid velocity is

$\boldsymbol{u}=\left\{\begin{array}{cr} U \hat{\boldsymbol{x}}, & 0

(i) Investigate the linear instability of the sheet by determining the relevant dispersion relation for small, inviscid, irrotational perturbations. For what wavelengths is the sheet unstable?

(ii) Evaluate the temporal growth rate and the wave propagation speed in the limits of both short and long waves. Using these results, sketch how the growth rate varies with the wavenumber.

(iii) Comment briefly on how the introduction of a stable density difference (fluid in $y>h$ is less dense than that in $0 ) and surface tension at the interface would affect the growth rates.

comment

• # Paper 4, Section I, E

The Hilbert transform of a function $f(x)$ is defined by

$\mathcal{H}(f)(y):=\frac{1}{\pi} \mathcal{P} \int_{-\infty}^{+\infty} \frac{f(x)}{y-x} d x$

Calculate the Hilbert transform of $f(x)=\cos \omega x$, where $\omega$ is a non-zero real constant.

comment

• # Paper 4, Section II, 18G

(a) Let $K$ be a field. Define the discriminant $\Delta(f)$ of a polynomial $f(x) \in K[x]$, and explain why it is in $K$, carefully stating any theorems you use.

Compute the discriminant of $x^{4}+r x+s$.

(b) Let $K$ be a field and let $f(x) \in K[x]$ be a quartic polynomial with roots $\alpha_{1}, \ldots, \alpha_{4}$ such that $\alpha_{1}+\cdots+\alpha_{4}=0$.

Define the resolvant cubic $g(x)$ of $f(x)$.

Suppose that $\Delta(f)$ is a square in $K$. Prove that the resolvant cubic is irreducible if and only if $G a l(f)=A_{4}$. Determine the possible Galois groups Gal $(f)$ if $g(x)$ is reducible.

The resolvant cubic of $x^{4}+r x+s$ is $x^{3}-4 s x-r^{2}$. Using this, or otherwise, determine $\operatorname{Gal}(f)$, where $f(x)=x^{4}+8 x+12 \in \mathbb{Q}[x]$. [You may use without proof that $f$ is irreducible.]

comment

• # Paper 4 , Section II, 37D

In linearized general relativity, we consider spacetime metrics that are perturbatively close to Minkowski, $g_{\mu \nu}=\eta_{\mu \nu}+h_{\mu \nu}$, where $\eta_{\mu \nu}=\operatorname{diag}(-1,1,1,1)$ and $h_{\mu \nu}=\mathcal{O}(\epsilon) \ll 1$. In the Lorenz gauge, the Einstein tensor, at linear order, is given by

$\tag{†} G_{\mu \nu}=-\frac{1}{2} \square \bar{h}_{\mu \nu}, \quad \bar{h}_{\mu \nu}=h_{\mu \nu}-\frac{1}{2} \eta_{\mu \nu} h$

where $\square=\eta^{\mu \nu} \partial_{\mu} \partial_{\nu}$ and $h=\eta^{\mu \nu} h_{\mu \nu}$.

(i) Show that the (fully nonlinear) Einstein equations $G_{\alpha \beta}=8 \pi T_{\alpha \beta}$ can be equivalently written in terms of the Ricci tensor $R_{\alpha \beta}$ as

$R_{\alpha \beta}=8 \pi\left(T_{\alpha \beta}-\frac{1}{2} g_{\alpha \beta} T\right), \quad T=g^{\mu \nu} T_{\mu \nu}$

Show likewise that equation $(†)$ can be written as

$\square h_{\mu \nu}=-16 \pi\left(T_{\mu \nu}-\frac{1}{2} \eta_{\mu \nu} T\right)$

(ii) In the Newtonian limit we consider matter sources with small velocities $v \ll 1$ such that time derivatives $\partial / \partial t \sim v \partial / \partial x^{i}$ can be neglected relative to spatial derivatives, and the only non-negligible component of the energy-momentum tensor is the energy density $T_{00}=\rho$. Show that in this limit, we recover from equation $(*)$ the Poisson equation $\vec{\nabla}^{2} \Phi=4 \pi \rho$ of Newtonian gravity if we identify $h_{00}=-2 \Phi$.

(iii) A point particle of mass $M$ is modelled by the energy density $\rho=M \delta(r)$. Derive the Newtonian potential $\Phi$ for this point particle by solving the Poisson equation.

[You can assume the solution of $\vec{\nabla}^{2} \varphi=f(\boldsymbol{r})$ is $\varphi(\boldsymbol{r})=-\int \frac{f\left(\boldsymbol{r}^{\prime}\right)}{4 \pi\left|\boldsymbol{r}-\boldsymbol{r}^{\prime}\right|} d^{3} r^{\prime} .$ ]

(iv) Now consider the Einstein equations with a small positive cosmological constant, $G_{\alpha \beta}+\Lambda g_{\alpha \beta}=8 \pi T_{\alpha \beta}, \Lambda=\mathcal{O}(\epsilon)>0$. Repeat the steps of questions (i)-(iii), again identifying $h_{00}=-2 \Phi$, to show that the Newtonian limit is now described by the Poisson equation $\vec{\nabla}^{2} \Phi=4 \pi \rho-\Lambda$, and that a solution for the potential of a point particle is given by

$\Phi=-\frac{M}{r}-B r^{2}$

where $B$ is a constant you should determine. Briefly discuss the effect of the $B r^{2}$ term and determine for which range of the radius $r$ the weak-field limit is a justified approximation. [Hint: Absorb the term $\Lambda g_{\alpha \beta}$ as part of the energy-momentum tensor. Note also that in spherical symmetry $\vec{\nabla}^{2} f=\frac{1}{r} \frac{\partial^{2}}{\partial r^{2}}(r f)$.]

comment

• # Paper 4 , Section II, $17 G$

State and prove Vizing's theorem about the chromatic index $\chi^{\prime}(G)$ of a graph $G$.

Let $K_{m, n}$ be the complete bipartite graph with class sizes $m$ and $n$. By first considering $\chi^{\prime}\left(K_{n, n}\right)$, find $\chi^{\prime}\left(K_{m, n}\right)$ for all $m$ and $n$.

Let $G$ be the graph of order $2 n+1$ obtained by subdividing a single edge of $K_{n, n}$ by a new vertex. Show that $\chi^{\prime}(G)=\Delta(G)+1$, where $\Delta(G)$ is the maximum degree of $G$.

comment

• # Paper 4, Section II, I

(a) For $K$ a compact Hausdorff space, what does it mean to say that a set $S \subset C(K)$ is equicontinuous. State and prove the Arzelà-Ascoli theorem.

(b) Suppose $K$ is a compact Hausdorff space for which $C(K)$ is a countable union of equicontinuous sets. Prove that $K$ is finite.

(c) Let $F: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ be a bounded, continuous function and let $x_{0} \in \mathbb{R}^{n}$. Consider the problem of finding a differentiable function $x:[0,1] \rightarrow \mathbb{R}^{n}$ with

$x(0)=x_{0} \quad \text { and } \quad x^{\prime}(t)=F(x(t))$

for all $t \in[0,1]$. For each $k=1,2,3, \ldots$, let $x_{k}:[0,1] \rightarrow \mathbb{R}^{n}$ be defined by setting $x_{k}(0)=x_{0}$ and

$x_{k}(t)=x_{0}+\int_{0}^{t} F\left(y_{k}(s)\right) d s$

for $t \in[0,1]$, where

$y_{k}(t)=x_{k}\left(\frac{j}{k}\right)$

for $t \in\left(\frac{j}{k}, \frac{j+1}{k}\right]$ and $j \in\{0,1, \ldots, k-1\}$.

(i) Verify that $x_{k}$ is well-defined and continuous on $[0,1]$ for each $k$.

(ii) Prove that there exists a differentiable function $x:[0,1] \rightarrow \mathbb{R}^{n}$ solving (*) for $t \in[0,1]$.

comment

• # Paper 4, Section II, 16H

(a) State Zorn's lemma.

[Throughout the remainder of this question, assume Zorn's lemma.]

(b) Let $P$ be a poset in which every non-empty chain has an upper bound and let $x \in P$. By considering the poset $P_{x}=\{y \in P \mid x \leqslant y\}$, show that $P$ has a maximal element $\sigma$ with $x \leqslant \sigma$.

(c) A filter is a non-empty subset $\mathcal{F} \subset \mathcal{P}(\mathbb{N})$ satisfying the following three conditions:

• if $A, B \in \mathcal{F}$ then $A \cap B \in \mathcal{F}$

• if $A \in \mathcal{F}$ and $A \subset B$ then $B \in \mathcal{F}$

• $\emptyset \notin \mathcal{F} .$

An ultrafilter is a filter $\mathcal{U}$ such that for all $A \subset \mathbb{N}$ we have either $A \in \mathcal{U}$ or $A^{c} \in \mathcal{U}$, where $A^{c}=\mathbb{N} \backslash A$.

(i) For each $n \in \mathbb{N}$, show that $\mathcal{U}_{n}=\{A \subset \mathbb{N} \mid n \in A\}$ is an ultrafilter.

(ii) Show that $\mathcal{F}=\left\{A \subset \mathbb{N} \mid A^{c}\right.$ is finite $\}$ is a filter but not an ultrafilter, and that for all $n \in \mathbb{N}$ we have $\mathcal{F} \not \subset \mathcal{U}_{n}$.

(iii) Does there exist an ultrafilter $\mathcal{U}$ such that $\mathcal{U} \neq \mathcal{U}_{n}$ for any $n \in \mathbb{N}$ ? Justify your answer.

comment

• # Paper 4, Section I, B

Consider a population process in which the probability of transition from a state with $n$ individuals to a state with $n+1$ individuals in the interval $(t, t+\Delta t)$ is $\lambda n \Delta t$ for small $\Delta t$.

(i) Write down the master equation for the probability, $P_{n}(t)$, of the state $n$ at time $t$ for $n \geqslant 1$

(ii) Assuming an initial distribution

$P_{n}(0)= \begin{cases}1, & \text { if } n=1 \\ 0, & \text { if } n>1\end{cases}$

show that

$P_{n}(t)=\exp (-\lambda t)(1-\exp (-\lambda t))^{n-1}$

(iii) Hence, determine the mean of $n$ for $t>0$.

comment
• # Paper 4, Section II, 14B

Consider the stochastic catalytic reaction

$E \leftrightharpoons E S, \quad E S \rightarrow E+P$

in which a single enzyme $E$ complexes reversibly to $E S$ (at forward rate $k_{1}$ and reverse rate $k_{1}^{\prime}$ ) and decomposes into product $P$ (at forward rate $k_{2}$ ), regenerating enzyme $E$. Assume there is sufficient substrate $S$ so that this catalytic cycle can continue indefinitely. Let $P(E, n)$ be the probability of the state with enzyme $E$ and $n$ products and $P(E S, n)$ the probability of the state with complex $E S$ and $n$ products, these states being mutually exclusive.

(i) Write down the master equation for the probabilities $P(E, n)$ and $P(E S, n)$ for $n \geqslant 0$

(ii) Assuming an initial state with zero products, solve the master equation for $P(E, 0)$ and $P(E S, 0)$.

(iii) Hence find the probability distribution $f(\tau)$ of the time $\tau$ taken to form the first product.

(iv) Obtain the mean of $\tau$.

comment

• # Paper 4, Section II, J

Suppose we have input-output pairs $\left(x_{1}, y_{1}\right), \ldots,\left(x_{n}, y_{n}\right) \in \mathbb{R}^{p} \times\{-1,1\}$. Consider the empirical risk minimisation problem with hypothesis class

$\mathcal{H}=\left\{x \mapsto x^{T} \beta: \beta \in C\right\}$

where $C$ is a non-empty closed convex subset of $\mathbb{R}^{p}$, and logistic loss

$\ell(h(x), y)=\log _{2}\left(1+e^{-y h(x)}\right),$

for $h \in \mathcal{H}$ and $(x, y) \in \mathbb{R}^{p} \times\{-1,1\}$.

(i) Show that the objective function $f$ of the optimisation problem is convex.

(ii) Let $\pi_{C}(x)$ denote the projection of $x$ onto $C$. Describe the procedure of stochastic gradient descent (SGD) for minimisation of $f$ above, giving explicit forms for any gradients used in the algorithm.

(iii) Suppose $\hat{\beta}$ minimises $f(\beta)$ over $\beta \in C$. Suppose $\max _{i=1, \ldots, n}\left\|x_{i}\right\|_{2} \leqslant M$ and $\sup _{\beta \in C}\|\beta\|_{2} \leqslant R$. Prove that the output $\bar{\beta}$ of $k$ iterations of the SGD algorithm with some fixed step size $\eta$ (which you should specify), satisfies

$\mathbb{E} f(\bar{\beta})-f(\hat{\beta}) \leqslant \frac{2 M R}{\log (2) \sqrt{k}}$

(iv) Now suppose that the step size at iteration $s$ is $\eta_{s}>0$ for each $s=1, \ldots, k$. Show that, writing $\beta_{s}$ for the $s$ th iterate of SGD, we have

$\mathbb{E} f(\tilde{\beta})-f(\hat{\beta}) \leqslant \frac{A_{2} M^{2}}{2 A_{1}\{\log (2)\}^{2}}+\frac{2 R^{2}}{A_{1}}$

where

$\tilde{\beta}=\frac{1}{A_{1}} \sum_{s=1}^{k} \eta_{s} \beta_{s}, \quad A_{1}=\sum_{s=1}^{k} \eta_{s} \quad \text { and } \quad A_{2}=\sum_{s=1}^{k} \eta_{s}^{2}$

[You may use standard properties of convex functions and projections onto closed convex sets without proof provided you state them.]

comment

• # Paper 4, Section II, 20G

Let $K$ be a number field of degree $n$, and let $\left\{\sigma_{i}: K \hookrightarrow \mathbb{C}\right\}$ be the set of complex embeddings of $K$. Show that if $\alpha \in \mathcal{O}_{K}$ satisfies $\left|\sigma_{i}(\alpha)\right|=1$ for every $i$, then $\alpha$ is a root of unity. Prove also that there exists $c>1$ such that if $\alpha \in \mathcal{O}_{K}$ and $\left|\sigma_{i}(\alpha)\right| for all $i$, then $\alpha$ is a root of unity.

State Dirichlet's Unit theorem.

Let $K \subset \mathbb{R}$ be a real quadratic field. Assuming Dirichlet's Unit theorem, show that the set of units of $K$ which are greater than 1 has a smallest element $\epsilon$, and that the group of units of $K$ is then $\left\{\pm \epsilon^{n} \mid n \in \mathbb{Z}\right\}$. Determine $\epsilon$ for $\mathbb{Q}(\sqrt{11})$, justifying your result. [If you use the continued fraction algorithm, you must prove it in full.]

comment

• # Paper 4 , Section II, 11H

(a) What does it mean to say that a function $f: \mathbb{N} \rightarrow \mathbb{C}$ is multiplicative? Show that if $f, g: \mathbb{N} \rightarrow \mathbb{C}$ are both multiplicative, then so is $f \star g: \mathbb{N} \rightarrow \mathbb{C}$, defined for all $n \in \mathbb{N}$ by

$f \star g(n)=\sum_{d \mid n} f(d) g\left(\frac{n}{d}\right)$

Show that if $f=\mu \star g$, where $\mu$ is the Möbius function, then $g=f \star 1$, where 1 denotes the constant function 1 .

(b) Let $\tau(n)$ denote the number of positive divisors of $n$. Find $f, g: \mathbb{N} \rightarrow \mathbb{C}$ such that $\tau=f \star g$, and deduce that $\tau$ is multiplicative. Hence or otherwise show that for all $s \in \mathbb{C}$ with $\operatorname{Re}(s)>1$,

$\sum_{n=1}^{\infty} \frac{\tau(n)}{n^{s}}=\zeta(s)^{2}$

where $\zeta$ is the Riemann zeta function.

(c) Fix $k \in \mathbb{N}$. By considering suitable powers of the product of the first $k+1$ primes, show that

$\tau(n) \geqslant(\log n)^{k}$

for infinitely many $n \in \mathbb{N}$.

(d) Fix $\epsilon>0$. Show that

$\frac{\tau(n)}{n^{\epsilon}}=\prod_{p \text { prime, } p^{\alpha}|| n} \frac{(\alpha+1)}{p^{\alpha \epsilon}}$

where $p^{\alpha} \| n$ denotes the fact that $\alpha \in \mathbb{N}$ is such that $p^{\alpha} \mid n$ but $p^{\alpha+1} \nmid n$. Deduce that there exists a positive constant $C(\epsilon)$ depending only on $\epsilon$ such that for all $n \in \mathbb{N}, \tau(n) \leqslant C(\epsilon) n^{\epsilon} .$

comment
• # Paper 4, Section I, H

Let $p$ be a prime.

State and prove Lagrange's theorem on the number of solutions of a polynomial congruence modulo $p$. Deduce that $(p-1) ! \equiv-1 \bmod p$.

Let $k$ be a positive integer such that $k \mid(p-1)$. Show that the congruence

$x^{k} \equiv 1 \quad \bmod p$

has precisely $k$ solutions modulo $p$.

comment

• # Paper 4 , Section II, 40E

(a) For a function $f=f(x, y)$ which is real analytic in $\mathbb{R}^{2}$ and 2-periodic in each variable, its Fourier expansion is given by the formula

$f(x, y)=\sum_{m, n \in \mathbb{Z}} \widehat{f}_{m, n} e^{i \pi m x+i \pi n y}, \quad \widehat{f}_{m, n}=\frac{1}{4} \int_{-1}^{1} \int_{-1}^{1} f(t, \theta) e^{-i \pi m t-i \pi n \theta} d t d \theta$

Derive expressions for the Fourier coefficients of partial derivatives $f_{x}, f_{y}$ and those of the product $h(x, y)=f(x, y) g(x, y)$ in terms of $\widehat{f}_{m, n}$ and $\widehat{g}_{m, n}$.

(b) Let $u(x, y)$ be the 2-periodic solution in $\mathbb{R}^{2}$ of the general second-order elliptic PDE

$\left(a u_{x}\right)_{x}+\left(a u_{y}\right)_{y}=f$

where $a$ and $f$ are both real analytic and 2-periodic, and $a(x, y)>0$. We impose the normalisation condition $\int_{-1}^{1} \int_{-1}^{1} u d x d y=0$ and note from the PDE $\int_{-1}^{1} \int_{-1}^{1} f d x d y=0$.

Construct explicitly the infinite-dimensional linear algebraic system that arises from the application of the Fourier spectral method to the above equation, and explain how to truncate this system to a finite-dimensional one.

(c) Specify the truncated system for the unknowns $\left\{\widehat{u}_{m, n}\right\}$ for the case

$a(x, y)=5+2 \cos \pi x+2 \cos \pi y$

and prove that, for any ordering of the Fourier coefficients $\left\{\widehat{u}_{m, n}\right\}$ into one-dimensional array, the resulting system is symmetric and positive definite. [You may use the Gershgorin theorem without proof.]

comment

• # Paper 4, Section II,

Briefly explain why the density operator $\rho$ obeys $\rho \geqslant 0$ and $\operatorname{Tr}(\rho)=1$. What is meant by a pure state and a mixed state?

A two-state system evolves under the Hamiltonian $H=\hbar \boldsymbol{\omega} \cdot \boldsymbol{\sigma}$, where $\boldsymbol{\omega}$ is a constant vector and $\sigma$ are the Pauli matrices. At time $t$ the system is described by a density operator

$\rho(t)=\frac{1}{2}\left(1_{\mathcal{H}}+\mathbf{a}(t) \cdot \boldsymbol{\sigma}\right)$

where $1_{\mathcal{H}}$ is the identity operator. Initially, the vector $\mathbf{a}(0)=\mathbf{a}$ obeys $|\mathbf{a}|<1$ and $\mathbf{a} \cdot \boldsymbol{\omega}=0$. Find $\rho(t)$ in terms of a and $\boldsymbol{\omega}$. At what time, if any, is the system definitely in the state $\left|\uparrow_{x}\right\rangle$ that obeys $\sigma_{x}\left|\uparrow_{x}\right\rangle=+\left|\uparrow_{x}\right\rangle ?$

comment

• # Paper 4 , Section II, J

Consider $X_{1}, \ldots, X_{n}$ drawn from a statistical model $\{f(\cdot, \theta): \theta \in \Theta\}, \Theta=\mathbb{R}^{p}$, with non-singular Fisher information matrix $I(\theta)$. For $\theta_{0} \in \Theta, h \in \mathbb{R}^{p}$, define likelihood ratios

$Z_{n}(h)=\log \frac{\prod_{i=1}^{n} f\left(X_{i}, \theta_{0}+h / \sqrt{n}\right)}{\prod_{i=1}^{n} f\left(X_{i}, \theta_{0}\right)}, \quad X_{i} \sim^{i . i . d .} f\left(\cdot, \theta_{0}\right)$

Next consider the probability density functions $\left(p_{h}: h \in \mathbb{R}^{p}\right)$ of normal distributions $N\left(h, I\left(\theta_{0}\right)^{-1}\right)$ with corresponding likelihood ratios given by

$Z(h)=\log \frac{p_{h}(X)}{p_{0}(X)}, \quad X \sim p_{0} .$

Show that for every fixed $h \in \mathbb{R}^{p}$, the random variables $Z_{n}(h)$ converge in distribution as $n \rightarrow \infty$ to $Z(h) .$

[You may assume suitable regularity conditions of the model $\{f(\cdot, \theta): \theta \in \Theta\}$ without specification, and results on uniform laws of large numbers from lectures can be used without proof.]

comment

• # Paper 4, Section II, K

(a) State and prove the strong law of large numbers for sequences of i.i.d. random variables with a finite moment of order 4 .

(b) Let $\left(X_{k}\right)_{k \geqslant 1}$ be a sequence of independent random variables such that

$\mathbb{P}\left(X_{k}=1\right)=\mathbb{P}\left(X_{k}=-1\right)=\frac{1}{2}$

Let $\left(a_{k}\right)_{k \geqslant 1}$ be a sequence of real numbers such that

$\sum_{k \geqslant 1} a_{k}^{2}<\infty$

Set

$S_{n}:=\sum_{k=1}^{n} a_{k} X_{k}$

(i) Show that $S_{n}$ converges in $\mathbb{L}^{2}$ to a random variable $S$ as $n \rightarrow \infty$. Does it converge in $\mathbb{L}^{1}$ ? Does it converge in law?

(ii) Show that $\|S\|_{4} \leqslant 3^{1 / 4}\|S\|_{2}$.

(iii) Let $\left(Y_{k}\right)_{k \geqslant 1}$ be a sequence of i.i.d. standard Gaussian random variables, i.e. each $Y_{k}$ is distributed as $\mathcal{N}(0,1)$. Show that then $\sum_{k=1}^{n} a_{k} Y_{k}$ converges in law as $n \rightarrow \infty$ to a random variable and determine the law of the limit.

comment

• # Paper 4, Section I, C

(i) What is the action of $\mathrm{QFT}_{N}$ on a state $|x\rangle$, where $x \in\{0,1,2, \ldots, N-1\}$ and $\mathrm{QFT}_{N}$ denotes the Quantum Fourier Transform modulo $N$ ?

(ii) For the case $N=4$ write $0,1,2,3$ respectively in binary as $00,01,10,11$ thereby identifying the four-dimensional space as that of two qubits. Show that $\mathrm{QFT}_{N}|10\rangle$ is an unentangled state of the two qubits.

(iii) Prove that $\left(\mathrm{QFT}_{N}\right)^{2}|x\rangle=|N-x\rangle$, where $\left(\mathrm{QFT}_{N}\right)^{2} \equiv \mathrm{QFT}_{N} \circ \mathrm{QFT}_{N}$.

[Hint: For $\omega=e^{2 \pi i / N}, \sum_{m=0}^{N-1} \omega^{m K}=0$ if $K$ is not a multiple of $N$.]

(iv) What is the action of $\left(\mathrm{QFT}_{N}\right)^{4}$ on a state $|x\rangle$, for any $x \in\{0,1,2, \ldots, N-1\}$ ? Use the above to determine what the eigenvalues of $\mathrm{QFT}_{N}$ are.

comment

• # Paper 4, Section II, F

(a) State and prove Burnside's lemma. Deduce that if a finite group $G$ acts 2transitively on a set $X$ then the corresponding permutation character has precisely two (distinct) irreducible summands.

(b) Suppose that $\mathbb{F}_{q}$ is a field with $q$ elements. Write down a list of conjugacy class representatives for $G L_{2}\left(\mathbb{F}_{q}\right)$. Consider the natural action of $G L_{2}\left(\mathbb{F}_{q}\right)$ on the set of lines through the origin in $\mathbb{F}_{q}^{2}$. What values does the corresponding permutation character take on each conjugacy class representative in your list? Decompose this permutation character into irreducible characters.

comment

• # Paper 4, Section I, J

Suppose you have a data frame with variables response, covar1, and covar2. You run the following commands on $R$.

$\begin{array}{llllll}\text { covar2 } & 0.3755 & 2.5978 & 0.145 & 0.886\end{array}$

...

(a) Consider the following three scenarios:

(i) All the output you have is the abbreviated output of summary (model) above.

(ii) You have the abbreviated output of summary (model) above together with

Residual standard error: $0.8097$ on 47 degrees of freedom

Multiple R-squared: $0.8126$, Adjusted R-squared: $0.8046$

F-statistic: $101.9$ on 2 and 47 DF, p-value: < $2.2 e-16$

(iii) You have the abbreviated output of summary (model) above together with

Residual standard error: $0.9184$ on 47 degrees of freedom

Multiple R-squared: $0.000712$, Adjusted R-squared: $-0.04181$

F-statistic: $0.01674$ on 2 and 47 DF, p-value: $0.9834$

What conclusion can you draw about which variables explain the response in each of the three scenarios? Explain.

(b) Assume now that you have the abbreviated output of summary (model) above together with

anova(lm(response $~ 1), \operatorname{lm}($ response $\sim \operatorname{covar} 1)$, model $)$

What are the values of the entries with a question mark? [You may express your answers as arithmetic expressions if necessary].

comment
• # Paper 4, Section II, J

(a) Define a generalised linear model $(\mathrm{GLM})$ with design matrix $X \in \mathbb{R}^{n \times p}$, output variables $Y:=\left(Y_{1}, \ldots, Y_{n}\right)^{T}$ and parameters $\mu:=\left(\mu_{1}, \ldots, \mu_{n}\right)^{T}, \beta \in \mathbb{R}^{p}$ and $\sigma_{i}^{2}:=a_{i} \sigma^{2} \in(0, \infty), i=1, \ldots, n$. Derive the moment generating function of $Y$, i.e. give an expression for $\mathbb{E}\left[\exp \left(t^{T} Y\right)\right], t \in \mathbb{R}^{n}$, wherever it is well-defined.

Assume from now on that the GLM satisfies the usual regularity assumptions, $X$ has full column rank, and $\sigma^{2}$ is known and satisfies $1 / \sigma^{2} \in \mathbb{N}$.

(b) Let $\tilde{Y}:=\left(\tilde{Y}_{1}, \ldots, \tilde{Y}_{n / \sigma^{2}}\right)^{T}$ be the output variables of a GLM from the same family as that of part (a) and parameters $\tilde{\mu}:=\left(\tilde{\mu}_{1}, \ldots, \tilde{\mu}_{n / \sigma^{2}}\right)^{T}$ and $\tilde{\sigma}^{2}:=\left(\tilde{\sigma}_{1}^{2}, \ldots, \tilde{\sigma}_{n / \sigma^{2}}^{2}\right)$. Suppose the output variables may be split into $n$ blocks of size $1 / \sigma^{2}$ with constant parameters. To be precise, for each block $i=1, \ldots, n$, if $j \in\left\{(i-1) / \sigma^{2}+1, \ldots, i / \sigma^{2}\right\}$ then

$\tilde{\mu}_{j}=\mu_{i} \quad \text { and } \quad \tilde{\sigma}_{j}^{2}=a_{i}$

with $\mu_{i}=\mu_{i}(\beta)$ and $a_{i}$ defined as in part $($ a $)$. Let $\bar{Y}:=\left(\bar{Y}_{1}, \ldots, \bar{Y}_{n}\right)^{T}$, where $\bar{Y}_{i}:=$ $\sigma^{2} \sum_{k=1}^{1 / \sigma^{2}} \tilde{Y}_{(i-1) / \sigma^{2}+k}$.

(i) Show that $\bar{Y}$ is equal to $Y$ in distribution. [Hint: you may use without proof that moment generating functions uniquely determine distributions from exponential dispersion families.]

(ii) For any $\tilde{y} \in \mathbb{R}^{n / \sigma^{2}}$, let $\bar{y}=\left(\bar{y}_{1}, \ldots, \bar{y}_{n}\right)^{T}$, where $\bar{y}_{i}:=\sigma^{2} \sum_{k=1}^{1 / \sigma^{2}} \tilde{y}_{(i-1) / \sigma^{2}+k}$. Show that the model function of $\tilde{Y}$ satisfies

$f\left(\tilde{y} ; \tilde{\mu}, \tilde{\sigma}^{2}\right)=g_{1}\left(\bar{y} ; \tilde{\mu}, \tilde{\sigma}^{2}\right) \times g_{2}\left(\tilde{y} ; \tilde{\sigma}^{2}\right)$

for some functions $g_{1}, g_{2}$, and conclude that $\bar{Y}$ is a sufficient statistic for $\beta$ from $\tilde{Y}$.

(iii) For the model and data from part (a), let $\hat{\mu}$ be the maximum likelihood estimator for $\mu$ and let $D(Y ; \mu)$ be the deviance at $\mu$. Using (i) and (ii), show that

$\frac{D(Y ; \hat{\mu})}{\sigma^{2}}={ }^{d} 2 \log \left\{\frac{\sup _{\tilde{\mu}^{\prime} \in \widetilde{\mathcal{M}}_{1}} f\left(\tilde{Y} ; \tilde{\mu}^{\prime}, \tilde{\sigma}^{2}\right)}{\sup _{\tilde{\mu}^{\prime} \in \widetilde{\mathcal{M}}_{0}} f\left(\tilde{Y} ; \tilde{\mu}^{\prime}, \tilde{\sigma}^{2}\right)}\right\}$

where $=^{d}$ means equality in distribution and $\widetilde{\mathcal{M}}_{0}$ and $\widetilde{\mathcal{M}}_{1}$ are nested subspaces of $\mathbb{R}^{n / \sigma^{2}}$ which you should specify. Argue that $\operatorname{dim}\left(\widetilde{\mathcal{M}}_{1}\right)=n$ and $\operatorname{dim}\left(\widetilde{\mathcal{M}}_{0}\right)=p$, and, assuming the usual regularity assumptions, conclude that

$\frac{D(Y ; \hat{\mu})}{\sigma^{2}} \rightarrow^{d} \chi_{n-p}^{2} \quad \text { as } \sigma^{2} \rightarrow 0$

stating the name of the result from class that you use.

comment

• # Paper 4, Section II, A

Consider a classical gas of $N$ particles in volume $V$, where the total energy is the standard kinetic energy plus a potential $U\left(\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{N}\right)$ depending on the relative locations of the particles $\left\{\mathbf{x}_{i}: 1 \leqslant i \leqslant N\right\}$<