Part IA, 2018

# Part IA, 2018

### Jump to course

Paper 1, Section I, $4 \mathrm{D}$

commentDefine the radius of convergence $R$ of a complex power series $\sum a_{n} z^{n}$. Prove that $\sum a_{n} z^{n}$ converges whenever $|z|<R$ and diverges whenever $|z|>R$.

If $\left|a_{n}\right| \leqslant\left|b_{n}\right|$ for all $n$ does it follow that the radius of convergence of $\sum a_{n} z^{n}$ is at least that of $\sum b_{n} z^{n}$ ? Justify your answer.

Paper 1, Section I, E

commentProve that an increasing sequence in $\mathbb{R}$ that is bounded above converges.

Let $f: \mathbb{R} \rightarrow(0, \infty)$ be a decreasing function. Let $x_{1}=1$ and $x_{n+1}=x_{n}+f\left(x_{n}\right)$. Prove that $x_{n} \rightarrow \infty$ as $n \rightarrow \infty$.

Paper 1, Section II, $10 F$

comment(a) Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be differentiable at $x_{0} \in \mathbb{R}$. Show that $f$ is continuous at $x_{0}$.

(b) State the Mean Value Theorem. Prove the following inequalities:

$\left|\cos \left(e^{-x}\right)-\cos \left(e^{-y}\right)\right| \leqslant|x-y| \quad \text { for } x, y \geqslant 0$

and

$\log (1+x) \leqslant \frac{x}{\sqrt{1+x}} \text { for } x \geqslant 0 .$

(c) Determine at which points the following functions from $\mathbb{R}$ to $\mathbb{R}$ are differentiable, and find their derivatives at the points at which they are differentiable:

$f(x)=\left\{\begin{array}{ll} |x|^{x} & \text { if } x \neq 0 \\ 1 & \text { if } x=0, \end{array} \quad g(x)=\cos (|x|), \quad h(x)=x|x|\right.$

(d) Determine the points at which the following function from $\mathbb{R}$ to $\mathbb{R}$ is continuous:

$f(x)= \begin{cases}0 & \text { if } x \notin \mathbb{Q} \text { or } x=0 \\ 1 / q & \text { if } x=p / q \text { where } p \in \mathbb{Z} \backslash\{0\} \text { and } q \in \mathbb{N} \text { are relatively prime. }\end{cases}$

Paper 1, Section II, D

comment(a) Let $q_{1}, q_{2}, \ldots$ be a fixed enumeration of the rationals in $[0,1]$. For positive reals $a_{1}, a_{2}, \ldots$, define a function $f$ from $[0,1]$ to $\mathbb{R}$ by setting $f\left(q_{n}\right)=a_{n}$ for each $n$ and $f(x)=0$ for $x$ irrational. Prove that if $a_{n} \rightarrow 0$ then $f$ is Riemann integrable. If $a_{n} \rightarrow 0$, can $f$ be Riemann integrable? Justify your answer.

(b) State and prove the Fundamental Theorem of Calculus.

Let $f$ be a differentiable function from $\mathbb{R}$ to $\mathbb{R}$, and set $g(x)=f^{\prime}(x)$ for $0 \leqslant x \leqslant 1$. Must $g$ be Riemann integrable on $[0,1]$ ?

Paper 1, Section II, E

commentState and prove the Comparison Test for real series.

Assume $0 \leqslant x_{n}<1$ for all $n \in \mathbb{N}$. Show that if $\sum x_{n}$ converges, then so do $\sum x_{n}^{2}$ and $\sum \frac{x_{n}}{1-x_{n}}$. In each case, does the converse hold? Justify your answers.

Let $\left(x_{n}\right)$ be a decreasing sequence of positive reals. Show that if $\sum x_{n}$ converges, then $n x_{n} \rightarrow 0$ as $n \rightarrow \infty$. Does the converse hold? If $\sum x_{n}$ converges, must it be the case that $(n \log n) x_{n} \rightarrow 0$ as $n \rightarrow \infty$ ? Justify your answers.

Paper 1, Section II, F

comment(a) Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a function, and let $x \in \mathbb{R}$. Define what it means for $f$ to be continuous at $x$. Show that $f$ is continuous at $x$ if and only if $f\left(x_{n}\right) \rightarrow f(x)$ for every sequence $\left(x_{n}\right)$ with $x_{n} \rightarrow x$.

(b) Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a non-constant polynomial. Show that its image $\{f(x): x \in \mathbb{R}\}$ is either the real line $\mathbb{R}$, the interval $[a, \infty)$ for some $a \in \mathbb{R}$, or the interval $(-\infty, a]$ for some $a \in \mathbb{R}$.

(c) Let $\alpha>1$, let $f:(0, \infty) \rightarrow \mathbb{R}$ be continuous, and assume that $f(x)=f\left(x^{\alpha}\right)$ holds for all $x>0$. Show that $f$ must be constant.

Is this also true when the condition that $f$ be continuous is dropped?

Paper 2, Section I, B

commentShow that for given $P(x, y), Q(x, y)$ there is a function $F(x, y)$ such that, for any function $y(x)$,

$P(x, y)+Q(x, y) \frac{d y}{d x}=\frac{d}{d x} F(x, y)$

if and only if

$\frac{\partial P}{\partial y}=\frac{\partial Q}{\partial x}$

Now solve the equation

$(2 y+3 x) \frac{d y}{d x}+4 x^{3}+3 y=0$

Paper 2, Section I, B

commentConsider the following difference equation for real $u_{n}$ :

$u_{n+1}=a u_{n}\left(1-u_{n}^{2}\right)$

where $a$ is a real constant.

For $-\infty<a<\infty$ find the steady-state solutions, i.e. those with $u_{n+1}=u_{n}$ for all $n$, and determine their stability, making it clear how the number of solutions and the stability properties vary with $a$. [You need not consider in detail particular values of $a$ which separate intervals with different stability properties.]

Paper 2, Section II, B

commentThe function $u(x, y)$ satisfies the partial differential equation

$a \frac{\partial^{2} u}{\partial x^{2}}+b \frac{\partial^{2} u}{\partial x \partial y}+c \frac{\partial^{2} u}{\partial y^{2}}=0$

where $a, b$ and $c$ are non-zero constants.

Defining the variables $\xi=\alpha x+y$ and $\eta=\beta x+y$, where $\alpha$ and $\beta$ are constants, and writing $v(\xi, \eta)=u(x, y)$ show that

$a \frac{\partial^{2} u}{\partial x^{2}}+b \frac{\partial^{2} u}{\partial x \partial y}+c \frac{\partial^{2} u}{\partial y^{2}}=A(\alpha, \beta) \frac{\partial^{2} v}{\partial \xi^{2}}+B(\alpha, \beta) \frac{\partial^{2} v}{\partial \xi \partial \eta}+C(\alpha, \beta) \frac{\partial^{2} v}{\partial \eta^{2}},$

where you should determine the functions $A(\alpha, \beta), B(\alpha, \beta)$ and $C(\alpha, \beta)$.

If the quadratic $a s^{2}+b s+c=0$ has distinct real roots then show that $\alpha$ and $\beta$ can be chosen such that $A(\alpha, \beta)=C(\alpha, \beta)=0$ and $B(\alpha, \beta) \neq 0$.

If the quadratic $a s^{2}+b s+c=0$ has a repeated root then show that $\alpha$ and $\beta$ can be chosen such that $A(\alpha, \beta)=B(\alpha, \beta)=0$ and $C(\alpha, \beta) \neq 0$.

Hence find the general solutions of the equations

$\frac{\partial^{2} u}{\partial x^{2}}+3 \frac{\partial^{2} u}{\partial x \partial y}+2 \frac{\partial^{2} u}{\partial y^{2}}=0$

and

$\frac{\partial^{2} u}{\partial x^{2}}+2 \frac{\partial^{2} u}{\partial x \partial y}+\frac{\partial^{2} u}{\partial y^{2}}=0$

Paper 2, Section II, B

commentBy choosing a suitable basis, solve the equation

$\left(\begin{array}{ll} 1 & 2 \\ 1 & 0 \end{array}\right)\left(\begin{array}{l} \dot{x} \\ \dot{y} \end{array}\right)+\left(\begin{array}{cc} -2 & 5 \\ 2 & -1 \end{array}\right)\left(\begin{array}{l} x \\ y \end{array}\right)=e^{-4 t}\left(\begin{array}{c} 3 b \\ 2 \end{array}\right)+e^{-t}\left(\begin{array}{c} -3 \\ c-1 \end{array}\right)$

subject to the initial conditions $x(0)=0, y(0)=0$.

Explain briefly what happens in the cases $b=2$ or $c=2$.

Paper 2, Section II, B

commentThe temperature $T$ in an oven is controlled by a heater which provides heat at rate $Q(t)$. The temperature of a pizza in the oven is $U$. Room temperature is the constant value $T_{r}$.

$T$ and $U$ satisfy the coupled differential equations

$\begin{aligned} \frac{d T}{d t} &=-a\left(T-T_{r}\right)+Q(t) \\ \frac{d U}{d t} &=-b(U-T) \end{aligned}$

where $a$ and $b$ are positive constants. Briefly explain the various terms appearing in the above equations.

Heating may be provided by a short-lived pulse at $t=0$, with $Q(t)=Q_{1}(t)=\delta(t)$ or by constant heating over a finite period $0<t<\tau$, with $Q(t)=Q_{2}(t)=\tau^{-1}(H(t)-H(t-$ $\tau)$, where $\delta(t)$ and $H(t)$ are respectively the Dirac delta function and the Heaviside step function. Again briefly, explain how the given formulae for $Q_{1}(t)$ and $Q_{2}(t)$ are consistent with their description and why the total heat supplied by the two heating protocols is the same.

For $t<0, T=U=T_{r}$. Find the solutions for $T(t)$ and $U(t)$ for $t>0$, for each of $Q(t)=Q_{1}(t)$ and $Q(t)=Q_{2}(t)$, denoted respectively by $T_{1}(t)$ and $U_{1}(t)$, and $T_{2}(t)$ and $U_{2}(t)$. Explain clearly any assumptions that you make about continuity of the solutions in time.

Show that the solutions $T_{2}(t)$ and $U_{2}(t)$ tend respectively to $T_{1}(t)$ and $U_{1}(t)$ in the limit as $\tau \rightarrow 0$ and explain why.

Paper 2, Section II, B

commentConsider the differential equation

$x^{2} \frac{d^{2} y}{d x^{2}}+x \frac{d y}{d x}-\left(x^{2}+\alpha^{2}\right) y=0$

What values of $x$ are ordinary points of the differential equation? What values of $x$ are singular points of the differential equation, and are they regular singular points or irregular singular points? Give clear definitions of these terms to support your answers.

For $\alpha$ not equal to an integer there are two linearly independent power series solutions about $x=0$. Give the forms of the two power series and the recurrence relations that specify the relation between successive coefficients. Give explicitly the first three terms in each power series.

For $\alpha$ equal to an integer explain carefully why the forms you have specified do not give two linearly independent power series solutions. Show that for such values of $\alpha$ there is (up to multiplication by a constant) one power series solution, and give the recurrence relation between coefficients. Give explicitly the first three terms.

If $y_{1}(x)$ is a solution of the above second-order differential equation then

$y_{2}(x)=y_{1}(x) \int_{c}^{x} \frac{1}{s\left[y_{1}(s)\right]^{2}} d s$

where $c$ is an arbitrarily chosen constant, is a second solution that is linearly independent of $y_{1}(x)$. For the case $\alpha=1$, taking $y_{1}(x)$ to be a power series, explain why the second solution $y_{2}(x)$ is not a power series.

[You may assume that any power series you use are convergent.]

Paper 4, Section I, 3A

comment(a) Define an inertial frame.

(b) Specify three different types of Galilean transformation on inertial frames whose space coordinates are $\mathbf{x}$ and whose time coordinate is $t$.

(c) State the Principle of Galilean Relativity.

(d) Write down the equation of motion for a particle in one dimension $x$ in a potential $V(x)$. Prove that energy is conserved. A particle is at position $x_{0}$ at time $t_{0}$. Find an expression for time $t$ as a function of $x$ in terms of an integral involving $V$.

(e) Write down the $x$ values of any equilibria and state (without justification) whether they are stable or unstable for:

(i) $V(x)=\left(x^{2}-4\right)^{2}$

(ii) $V(x)=e^{-1 / x^{2}}$ for $x \neq 0$ and $V(0)=0$.

Paper 4, Section I, A

commentExplain what is meant by a central force acting on a particle moving in three dimensions.

Show that the angular momentum of a particle about the origin for a central force is conserved, and hence that its path lies in a plane.

Show that, in the approximation in which the Sun is regarded as fixed and only its gravitational field is considered, a straight line joining the Sun and an orbiting planet sweeps out equal areas in equal time (Kepler's second law).

Paper 4, Section II, A

commentThe position $\mathbf{x}=(x, y, z)$ and velocity $\dot{\mathbf{x}}$ of a particle of mass $m$ are measured in a frame which rotates at constant angular velocity $\omega$ with respect to an inertial frame. The particle is subject to a force $\mathbf{F}=-9 m|\boldsymbol{\omega}|^{2} \mathbf{x}$. What is the equation of motion of the particle?

Find the trajectory of the particle in the coordinates $(x, y, z)$ if $\boldsymbol{\omega}=(0,0, \omega)$ and at $t=0, \mathbf{x}=(1,0,0)$ and $\dot{\mathbf{x}}=(0,0,0)$.

Find the maximum value of the speed $|\dot{\mathbf{x}}|$ of the particle and the times at which it travels at this speed.

[Hint: You may find using the variable $\xi=x+i y$ helpful.]

Paper 4, Section II, A

commentWrite down the Lorentz force law for a charge $q$ travelling at velocity $\mathbf{v}$ in an electric field $\mathbf{E}$ and magnetic field $\mathbf{B}$.

In a space station which is in an inertial frame, an experiment is performed in vacuo where a ball is released from rest a distance $h$ from a wall. The ball has charge $q>0$ and at time $t$, it is a distance $z(t)$ from the wall. A constant electric field of magnitude $E$ points toward the wall in a perpendicular direction, but there is no magnetic field. Find the speed of the ball on its first impact.

Every time the ball bounces, its speed is reduced by a factor $\gamma<1$. Show that the total distance travelled by the ball before it comes to rest is

$L=h \frac{q_{1}(\gamma)}{q_{2}(\gamma)}$

where $q_{1}$ and $q_{2}$ are quadratic functions which you should find explicitly.

A gas leak fills the apparatus with an atmosphere and the experiment is repeated. The ball now experiences an additional drag force $\mathbf{D}=-\alpha|\mathbf{v}| \mathbf{v}$, where $\mathbf{v}$ is the instantaneous velocity of the ball and $\alpha>0$. Solve the system before the first bounce, finding an explicit solution for the distance $z(t)$ between the ball and the wall as a function of time of the form

$z(t)=h-A f(B t)$

where $f$ is a function and $A$ and $B$ are dimensional constants, all of which you should find explicitly.

Paper 4, Section II, A

commentDefine the 4-momentum $P$ of a particle of rest mass $m$ and velocity $\mathbf{u}$. Calculate the power series expansion of the component $P^{0}$ for small $|\mathbf{u}| / c$ (where $c$ is the speed of light in vacuo) up to and including terms of order $|\mathbf{u}|^{4}$, and interpret the first two terms.

(a) At CERN, anti-protons are made by colliding a moving proton with another proton at rest in a fixed target. The collision in question produces three protons and an anti-proton. Assume that the rest mass of a proton is identical to the rest mass of an anti-proton. What is the smallest possible speed of the incoming proton (measured in the laboratory frame)?

(b) A moving particle of rest mass $M$ decays into $N$ particles with 4 -momenta $Q_{i}$, and rest masses $m_{i}$, where $i=1,2, \ldots, N$. Show that

$M=\frac{1}{c} \sqrt{\left(\sum_{i=1}^{N} Q_{i}\right) \cdot\left(\sum_{j=1}^{N} Q_{j}\right)}$

Thus, show that

$M \geqslant \sum_{i=1}^{N} m_{i}$

(c) A particle $A$ decays into particle $B$ and a massless particle 1 . Particle $B$ subsequently decays into particle $C$ and a massless particle 2 . Show that

$0 \leqslant\left(Q_{1}+Q_{2}\right) \cdot\left(Q_{1}+Q_{2}\right) \leqslant \frac{\left(m_{A}^{2}-m_{B}^{2}\right)\left(m_{B}^{2}-m_{C}^{2}\right) c^{2}}{m_{B}^{2}}$

where $Q_{1}$ and $Q_{2}$ are the 4-momenta of particles 1 and 2 respectively and $m_{A}, m_{B}, m_{C}$ are the masses of particles $A, B$ and $C$ respectively.

Paper 4, Section II, A

commentConsider a rigid body, whose shape and density distribution are rotationally symmetric about a horizontal axis. The body has mass $M$, radius $a$ and moment of inertia $I$ about its axis of rotational symmetry and is rolling down a non-slip slope inclined at an angle $\alpha$ to the horizontal. By considering its energy, calculate the acceleration of the disc down the slope in terms of the quantities introduced above and $g$, the acceleration due to gravity.

(a) A sphere with density proportional to $r^{c}$ (where $r$ is distance to the sphere's centre and $c$ is a positive constant) is launched up a non-slip slope of constant incline at the same time, level and speed as a vertical disc of constant density. Find $c$ such that the sphere and the disc return to their launch points at the same time.

(b) Two spherical glass marbles of equal radius are released from rest at time $t=0$ on an inclined non-slip slope of constant incline from the same level. The glass in each marble is of constant and equal density, but the second marble has two spherical air bubbles in it whose radii are half the radius of the marbles, initially centred directly above and below the marble's centre, respectively. Each bubble is centred half-way between the centre of the marble and its surface. At a later time $t$, find the ratio of the distance travelled by the first marble and the second. [ You may state without proof any theorems that you use and neglect the mass of air in the bubbles. ]

Paper 3, Section I, D

commentProve that every member of $O(3)$ is a product of at most three reflections.

Is every member of $O(3)$ a product of at most two reflections? Justify your answer.

Paper 3, Section I, D

commentFind the order and the sign of the permutation $(13)(2457)(815) \in S_{8}$.

How many elements of $S_{6}$ have order $6 ?$ And how many have order $3 ?$

What is the greatest order of any element of $A_{9}$ ?

Paper 3, Section II, D

commentState and prove the Direct Product Theorem.

Is the group $O(3)$ isomorphic to $S O(3) \times C_{2} ?$ Is $O(2)$ isomorphic to $S O(2) \times C_{2}$ ?

Let $U(2)$ denote the group of all invertible $2 \times 2$ complex matrices $A$ with $A \bar{A}^{\mathrm{T}}=I$, and let $S U(2)$ be the subgroup of $U(2)$ consisting of those matrices with determinant $1 .$

Determine the centre of $U(2)$.

Write down a surjective homomorphism from $U(2)$ to the group $T$ of all unit-length complex numbers whose kernel is $S U(2)$. Is $U(2)$ isomorphic to $S U(2) \times T$ ?

Paper 3, Section II, D

commentDefine the quotient group $G / H$, where $H$ is a normal subgroup of a group $G$. You should check that your definition is well-defined. Explain why, for $G$ finite, the greatest order of any element of $G / H$ is at most the greatest order of any element of $G$.

Show that a subgroup $H$ of a group $G$ is normal if and only if there is a homomorphism from $G$ to some group whose kernel is $H$.

A group is called metacyclic if it has a cyclic normal subgroup $H$ such that $G / H$ is cyclic. Show that every dihedral group is metacyclic.

Which groups of order 8 are metacyclic? Is $A_{4}$ metacyclic? For which $n \leqslant 5$ is $S_{n}$ metacyclic?

Paper 3, Section II, D

commentLet $g$ be an element of a group $G$. We define a map $g^{*}$ from $G$ to $G$ by sending $x$ to $g x g^{-1}$. Show that $g^{*}$ is an automorphism of $G$ (that is, an isomorphism from $G$ to $G$ ).

Now let $A$ denote the group of automorphisms of $G$ (with the group operation being composition), and define a map $\theta$ from $G$ to $A$ by setting $\theta(g)=g^{*}$. Show that $\theta$ is a homomorphism. What is the kernel of $\theta$ ?

Prove that the image of $\theta$ is a normal subgroup of $A$.

Show that if $G$ is cyclic then $A$ is abelian. If $G$ is abelian, must $A$ be abelian? Justify your answer.

Paper 3, Section II, D

commentDefine the sign of a permutation $\sigma \in S_{n}$. You should show that it is well-defined, and also that it is multiplicative (in other words, that it gives a homomorphism from $S_{n}$ to $\{\pm 1\})$.

Show also that (for $n \geqslant 2$ ) this is the only surjective homomorphism from $S_{n}$ to $\{\pm 1\}$.

Paper 4, Section I, E

commentGiven $n \in \mathbb{N}$, show that $\sqrt{n}$ is either an integer or irrational.

Let $\alpha$ and $\beta$ be irrational numbers and $q$ be rational. Which of $\alpha+q, \alpha+\beta, \alpha \beta, \alpha^{q}$ and $\alpha^{\beta}$ must be irrational? Justify your answers. [Hint: For the last part consider $\sqrt{2}^{\sqrt{2}}$.]

Paper 4, Section I, E

commentState Fermat's theorem.

Let $p$ be a prime such that $p \equiv 3(\bmod 4)$. Prove that there is no solution to $x^{2} \equiv-1(\bmod p) .$

Show that there are infinitely many primes congruent to $1(\bmod 4)$.

Paper 4, Section II, $5 E$

commentLet $n$ be a positive integer. Show that for any $a$ coprime to $n$, there is a unique $b$ $(\bmod n)$ such that $a b \equiv 1(\bmod n)$. Show also that if $a$ and $b$ are integers coprime to $n$, then $a b$ is also coprime to $n$. [Any version of Bezout's theorem may be used without proof provided it is clearly stated.]

State and prove Wilson's theorem.

Let $n$ be a positive integer and $p$ be a prime. Show that the exponent of $p$ in the prime factorisation of $n$ ! is given by $\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^{2}}\right\rfloor$ where $\lfloor x\rfloor$ denotes the integer part of $x$.

Evaluate $20! \mod 23$ and $100! \mod 10^{249}$

Let $p$ be a prime and $0<k<p^{m}$. Let $\ell$ be the exponent of $p$ in the prime factorisation of $k$. Find the exponent of $p$ in the prime factorisation of $\left(\begin{array}{c}p^{m} \\ k\end{array}\right)$, in terms of $m$ and $\ell$.

Paper 4, Section II, $7 \mathrm{E}$

commentLet $n \in \mathbb{N}$ and $A_{1}, \ldots, A_{n}$ be subsets of a finite set $X$. Let $0 \leqslant t \leqslant n$. Show that if $x \in X$ belongs to $A_{i}$ for exactly $m$ values of $i$, then

$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t} \mathbf{1}_{A_{S}}(x)= \begin{cases}0 & \text { if } m \neq t \\ 1 & \text { if } m=t\end{cases}$

where $A_{S}=\bigcap_{i \in S} A_{i}$ with the convention that $A_{\emptyset}=X$, and $\mathbf{1}_{A_{S}}$ denotes the indicator function of $A_{S} \cdot\left[\right.$ Hint: Set $M=\left\{i: x \in A_{i}\right\}$ and consider for which $S \subset\{1, \ldots, n\}$ one has $\mathbf{1}_{A_{S}}(x)=1$.]

Use this to show that the number of elements of $X$ that belong to $A_{i}$ for exactly $t$ values of $i$ is

$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t}\left|A_{S}\right| .$

Deduce the Inclusion-Exclusion Principle.

Using the Inclusion-Exclusion Principle, prove a formula for the Euler totient function $\varphi(N)$ in terms of the distinct prime factors of $N$.

A Carmichael number is a composite number $n$ such that $x^{n-1} \equiv 1(\bmod n)$ for every integer $x$ coprime to $n$. Show that if $n=q_{1} q_{2} \ldots q_{k}$ is the product of $k \geqslant 2$ distinct primes $q_{1}, \ldots, q_{k}$ satisfying $q_{j}-1 \mid n-1$ for $j=1, \ldots, k$, then $n$ is a Carmichael number.

Paper 4, Section II, 8E

commentDefine what it means for a set to be countable.

Show that for any set $X$, there is no surjection from $X$ onto the power set $\mathcal{P}(X)$. Deduce that the set $\{0,1\}^{\mathbb{N}}$ of all infinite $0-1$ sequences is uncountable.

Let $\mathcal{L}$ be the set of sequences $\left(F_{n}\right)_{n=0}^{\infty}$ of subsets $F_{0} \subset F_{1} \subset F_{2} \subset \ldots$ of $\mathbb{N}$ such that $\left|F_{n}\right|=n$ for all $n \in \mathbb{N}$ and $\bigcup_{n} F_{n}=\mathbb{N}$. Let $\mathcal{L}_{0}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n}$ for all but finitely many $n \in \mathbb{N}$. Let $\mathcal{L}_{1}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n+1}$ for all but finitely many $n \in \mathbb{N}$. For each of $\mathcal{L}_{0}$ and $\mathcal{L}_{1}$ determine whether it is countable or uncountable. Justify your answers.

Paper 4, Section II, E

commentFor $n \in \mathbb{N}$ let $Q_{n}=\{0,1\}^{n}$ denote the set of all $0-1$ sequences of length $n$. We define the distance $d(x, y)$ between two elements $x$ and $y$ of $Q_{n}$ to be the number of coordinates in which they differ. Show that $d(x, z) \leqslant d(x, y)+d(y, z)$ for all $x, y, z \in Q_{n}$.

For $x \in Q_{n}$ and $1 \leqslant j \leqslant n$ let $B(x, j)=\left\{y \in Q_{n}: d(y, x) \leqslant j\right\}$. Show that $|B(x, j)|=\sum_{i=0}^{j}\left(\begin{array}{c}n \\ i\end{array}\right)$.

A subset $C$ of $Q_{n}$ is called a $k$-code if $d(x, y) \geqslant 2 k+1$ for all $x, y \in C$ with $x \neq y$. Let $M(n, k)$ be the maximum possible value of $|C|$ for a $k$-code $C$ in $Q_{n}$. Show that

$2^{n}\left(\sum_{i=0}^{2 k}\left(\begin{array}{c} n \\ i \end{array}\right)\right)^{-1} \leqslant M(n, k) \leqslant 2^{n}\left(\sum_{i=0}^{k}\left(\begin{array}{l} n \\ i \end{array}\right)\right)^{-1}$

Find $M(4,1)$, carefully justifying your answer.

Paper 2, Section I, F

comment(a) State the Cauchy-Schwarz inequality and Markov's inequality. State and prove Jensen's inequality.

(b) For a discrete random variable $X$, show that $\operatorname{Var}(X)=0$ implies that $X$ is constant, i.e. there is $x \in \mathbb{R}$ such that $\mathbb{P}(X=x)=1$.

Paper 2, Section I, F

commentLet $X$ and $Y$ be independent Poisson random variables with parameters $\lambda$ and $\mu$ respectively.

(i) Show that $X+Y$ is Poisson with parameter $\lambda+\mu$.

(ii) Show that the conditional distribution of $X$ given $X+Y=n$ is binomial, and find its parameters.

Paper 2, Section II, 10F

comment(a) Let $X$ and $Y$ be independent random variables taking values $\pm 1$, each with probability $\frac{1}{2}$, and let $Z=X Y$. Show that $X, Y$ and $Z$ are pairwise independent. Are they independent?

(b) Let $X$ and $Y$ be discrete random variables with mean 0 , variance 1 , covariance $\rho$. Show that $\mathbb{E} \max \left\{X^{2}, Y^{2}\right\} \leqslant 1+\sqrt{1-\rho^{2}}$.

(c) Let $X_{1}, X_{2}, X_{3}$ be discrete random variables. Writing $a_{i j}=\mathbb{P}\left(X_{i}>X_{j}\right)$, show that $\min \left\{a_{12}, a_{23}, a_{31}\right\} \leqslant \frac{2}{3}$.

Paper 2, Section II, F

commentFor a symmetric simple random walk $\left(X_{n}\right)$ on $\mathbb{Z}$ starting at 0 , let $M_{n}=\max _{i \leqslant n} X_{i}$.

(i) For $m \geqslant 0$ and $x \in \mathbb{Z}$, show that

$\mathbb{P}\left(M_{n} \geqslant m, X_{n}=x\right)= \begin{cases}\mathbb{P}\left(X_{n}=x\right) & \text { if } x \geqslant m \\ \mathbb{P}\left(X_{n}=2 m-x\right) & \text { if } x<m\end{cases}$

(ii) For $m \geqslant 0$, show that $\mathbb{P}\left(M_{n} \geqslant m\right)=\mathbb{P}\left(X_{n}=m\right)+2 \sum_{x>m} \mathbb{P}\left(X_{n}=x\right)$ and that

$\mathbb{P}\left(M_{n}=m\right)=\mathbb{P}\left(X_{n}=m\right)+\mathbb{P}\left(X_{n}=m+1\right)$

(iii) Prove that $\mathbb{E}\left(M_{n}^{2}\right)<\mathbb{E}\left(X_{n}^{2}\right)$.

Paper 2, Section II, F

comment(a) Consider a Galton-Watson process $\left(X_{n}\right)$. Prove that the extinction probability $q$ is the smallest non-negative solution of the equation $q=F(q)$ where $F(t)=\mathbb{E}\left(t^{X_{1}}\right)$. [You should prove any properties of Galton-Watson processes that you use.]

In the case of a Galton-Watson process with

$\mathbb{P}\left(X_{1}=1\right)=1 / 4, \quad \mathbb{P}\left(X_{1}=3\right)=3 / 4$

find the mean population size and compute the extinction probability.

(b) For each $n \in \mathbb{N}$, let $Y_{n}$ be a random variable with distribution $\operatorname{Poisson}(n)$. Show that

$\frac{Y_{n}-n}{\sqrt{n}} \rightarrow Z$

in distribution, where $Z$ is a standard normal random variable.

Deduce that

$\lim _{n \rightarrow \infty} e^{-n} \sum_{k=0}^{n} \frac{n^{k}}{k !}=\frac{1}{2}$

Paper 2, Section II, F

comment(a) Let $Y$ and $Z$ be independent discrete random variables taking values in sets $S_{1}$ and $S_{2}$ respectively, and let $F: S_{1} \times S_{2} \rightarrow \mathbb{R}$ be a function.

Let $E(z)=\mathbb{E} F(Y, z)$. Show that

$\mathbb{E} E(Z)=\mathbb{E} F(Y, Z) .$

Let $V(z)=\mathbb{E}\left(F(Y, z)^{2}\right)-(\mathbb{E} F(Y, z))^{2}$. Show that

$\operatorname{Var} F(Y, Z)=\mathbb{E} V(Z)+\operatorname{Var} E(Z)$

(b) Let $X_{1}, \ldots, X_{n}$ be independent Bernoulli $(p)$ random variables. For any function $F:\{0,1\} \rightarrow \mathbb{R}$, show that

$\operatorname{Var} F\left(X_{1}\right)=p(1-p)(F(1)-F(0))^{2}$

Let $\{0,1\}^{n}$ denote the set of all $0-1$ sequences of length $n$. By induction, or otherwise, show that for any function $F:\{0,1\}^{n} \rightarrow \mathbb{R}$,

$\operatorname{Var} F(X) \leqslant p(1-p) \sum_{i=1}^{n} \mathbb{E}\left(\left(F(X)-F\left(X^{i}\right)\right)^{2}\right)$

where $X=\left(X_{1}, \ldots, X_{n}\right)$ and $X^{i}=\left(X_{1}, \ldots, X_{i-1}, 1-X_{i}, X_{i+1}, \ldots, X_{n}\right)$.

Paper 3, Section I, $4 \mathbf{C}$

commentIn plane polar coordinates $(r, \theta)$, the orthonormal basis vectors $\mathbf{e}_{r}$ and $\mathbf{e}_{\theta}$ satisfy

$\frac{\partial \mathbf{e}_{r}}{\partial r}=\frac{\partial \mathbf{e}_{\theta}}{\partial r}=\mathbf{0}, \quad \frac{\partial \mathbf{e}_{r}}{\partial \theta}=\mathbf{e}_{\theta}, \quad \frac{\partial \mathbf{e}_{\theta}}{\partial \theta}=-\mathbf{e}_{r}, \quad \text { and } \quad \boldsymbol{\nabla}=\mathbf{e}_{r} \frac{\partial}{\partial r}+\mathbf{e}_{\theta} \frac{1}{r} \frac{\partial}{\partial \theta}$

Hence derive the expression $\nabla \cdot \nabla \phi=\frac{1}{r} \frac{\partial}{\partial r}\left(r \frac{\partial \phi}{\partial r}\right)+\frac{1}{r^{2}} \frac{\partial^{2} \phi}{\partial \theta^{2}}$ for the Laplacian operator $\nabla^{2}$.

Calculate the Laplacian of $\phi(r, \theta)=\alpha r^{\beta} \cos (\gamma \theta)$, where $\alpha, \beta$ and $\gamma$ are constants. Hence find all solutions to the equation

$\nabla^{2} \phi=0 \quad \text { in } \quad 0 \leqslant r \leqslant a, \quad \text { with } \quad \partial \phi / \partial r=\cos (2 \theta) \text { on } r=a$

Explain briefly how you know that there are no other solutions.

Paper 3, Section I, C

commentDerive a formula for the curvature of the two-dimensional curve $\mathbf{x}(u)=(u, f(u))$.

Verify your result for the semicircle with radius $a$ given by $f(u)=\sqrt{a^{2}-u^{2}}$.

Paper 3, Section II, C

comment(a) Suppose that a tensor $T_{i j}$ can be decomposed as

$T_{i j}=S_{i j}+\epsilon_{i j k} V_{k}$

where $S_{i j}$ is symmetric. Obtain expressions for $S_{i j}$ and $V_{k}$ in terms of $T_{i j}$, and check that $(*)$ is satisfied.

(b) State the most general form of an isotropic tensor of rank $k$ for $k=0,1,2,3$, and verify that your answers are isotropic.

(c) The general form of an isotropic tensor of rank 4 is

$T_{i j k l}=\alpha \delta_{i j} \delta_{k l}+\beta \delta_{i k} \delta_{j l}+\gamma \delta_{i l} \delta_{j k}$

Suppose that $A_{i j}$ and $B_{i j}$ satisfy the linear relationship $A_{i j}=T_{i j k l} B_{k l}$, where $T_{i j k l}$ is isotropic. Express $B_{i j}$ in terms of $A_{i j}$, assuming that $\beta^{2} \neq \gamma^{2}$ and $3 \alpha+\beta+\gamma \neq 0$. If instead $\beta=-\gamma \neq 0$ and $\alpha \neq 0$, find all $B_{i j}$ such that $A_{i j}=0$.

(d) Suppose that $C_{i j}$ and $D_{i j}$ satisfy the quadratic relationship $C_{i j}=T_{i j k l m n} D_{k l} D_{m n}$, where $T_{i j k l m n}$ is an isotropic tensor of rank 6 . If $C_{i j}$ is symmetric and $D_{i j}$ is antisymmetric, find the most general non-zero form of $T_{i j k l m n} D_{k l} D_{m n}$ and prove that there are only two independent terms. [Hint: You do not need to use the general form of an isotropic tensor of rank 6.]

Paper 3, Section II, C

commentUse Maxwell's equations,

$\boldsymbol{\nabla} \cdot \mathbf{E}=\rho, \quad \boldsymbol{\nabla} \cdot \mathbf{B}=0, \quad \boldsymbol{\nabla} \times \mathbf{E}=-\frac{\partial \mathbf{B}}{\partial t}, \quad \boldsymbol{\nabla} \times \mathbf{B}=\mathbf{J}+\frac{\partial \mathbf{E}}{\partial t}$

to derive expressions for $\frac{\partial^{2} \mathbf{E}}{\partial t^{2}}-\nabla^{2} \mathbf{E}$ and $\frac{\partial^{2} \mathbf{B}}{\partial t^{2}}-\nabla^{2} \mathbf{B}$ in terms of $\rho$ and $\mathbf{J}$.

Now suppose that there exists a scalar potential $\phi$ such that $\mathbf{E}=-\nabla \phi$, and $\phi \rightarrow 0$ as $r \rightarrow \infty$. If $\rho=\rho(r)$ is spherically symmetric, calculate $\mathbf{E}$ using Gauss's flux method, i.e. by integrating a suitable equation inside a sphere centred at the origin. Use your result to find $\mathbf{E}$ and $\phi$ in the case when $\rho=1$ for $r<a$ and $\rho=0$ otherwise.

For each integer $n \geqslant 0$, let $S_{n}$ be the sphere of radius $4^{-n}$ centred at the point $\left(1-4^{-n}, 0,0\right)$. Suppose that $\rho$ vanishes outside $S_{0}$, and has the constant value $2^{n}$ in the volume between $S_{n}$ and $S_{n+1}$ for $n \geqslant 0$. Calculate $\mathbf{E}$ and $\phi$ at the point $(1,0,0)$.

Paper 3, Section II, C

commentState the formula of Stokes's theorem, specifying any orientation where needed.

Let $\mathbf{F}=\left(y^{2} z, x z+2 x y z, 0\right)$. Calculate $\boldsymbol{\nabla} \times \mathbf{F}$ and verify that $\boldsymbol{\nabla} \cdot \boldsymbol{\nabla} \times \mathbf{F}=0$.

Sketch the surface $S$ defined as the union of the surface $z=-1,1 \leqslant x^{2}+y^{2} \leqslant 4$ and the surface $x^{2}+y^{2}+z=3,1 \leqslant x^{2}+y^{2} \leqslant 4$.

Verify Stokes's theorem for $\mathbf{F}$ on $S$.

Paper 3, Section II, C

commentGiven a one-to-one mapping $u=u(x, y)$ and $v=v(x, y)$ between the region $D$ in the $(x, y)$-plane and the region $D^{\prime}$ in the $(u, v)$-plane, state the formula for transforming the integral $\iint_{D} f(x, y) d x d y$ into an integral over $D^{\prime}$, with the Jacobian expressed explicitly in terms of the partial derivatives of $u$ and $v$.

Let $D$ be the region $x^{2}+y^{2} \leqslant 1, y \geqslant 0$ and consider the change of variables $u=x+y$ and $v=x^{2}+y^{2}$. Sketch $D$, the curves of constant $u$ and the curves of constant $v$ in the $(x, y)$-plane. Find and sketch the image $D^{\prime}$ of $D$ in the $(u, v)$-plane.

Calculate $I=\iint_{D}(x+y) d x d y$ using this change of variables. Check your answer by calculating $I$ directly.

Paper 1, Section I, A

commentThe map $\boldsymbol{\Phi}(\mathbf{x})=\alpha(\mathbf{n} \cdot \mathbf{x}) \mathbf{n}-\mathbf{n} \times(\mathbf{n} \times \mathbf{x})$ is defined for $\mathbf{x} \in \mathbb{R}^{3}$, where $\mathbf{n}$ is a unit vector in $\mathbb{R}^{3}$ and $\alpha$ is a real constant.

(i) Find the values of $\alpha$ for which the inverse map $\Phi^{-1}$ exists, as well as the inverse map itself in these cases.

(ii) When $\boldsymbol{\Phi}$ is not invertible, find its image and kernel. What is the value of the rank and the value of the nullity of $\Phi$ ?

(iii) Let $\mathbf{y}=\mathbf{\Phi}(\mathbf{x})$. Find the components $A_{i j}$ of the matrix $A$ such that $y_{i}=A_{i j} x_{j}$. When $\Phi$ is invertible, find the components of the matrix $B$ such that $x_{i}=B_{i j} y_{j}$.

Paper 1, Section I, C

commentFor $z, w \in \mathbb{C}$ define the principal value of $z^{w}$. State de Moivre's theorem.

Hence solve the equations (i) $z^{6}=\sqrt{3}+i$, (ii) $z^{1 / 6}=\sqrt{3}+i$, (iii) $i^{z}=\sqrt{3}+i$ (iv) $\left(e^{5 i \pi / 2}\right)^{z}=\sqrt{3}+i$

[In each expression, the principal value is to be taken.]

Paper 1, Section II, $5 \mathbf{V}$

commentLet $\mathbf{x}, \mathbf{y} \in \mathbb{R}^{n}$ be non-zero real vectors. Define the inner product $\mathbf{x} \cdot \mathbf{y}$ in terms of the components $x_{i}$ and $y_{i}$, and define the norm $|\mathbf{x}|$. Prove that $\mathbf{x} \cdot \mathbf{y} \leqslant|\mathbf{x}||\mathbf{y}|$. When does equality hold? Express the angle between $\mathbf{x}$ and $\mathbf{y}$ in terms of their inner product.

Use suffix notation to expand $(\mathbf{a} \times \mathbf{b}) \cdot(\mathbf{b} \times \mathbf{c})$.

Let $\mathbf{a}, \mathbf{b}, \mathbf{c}$ be given unit vectors in $\mathbb{R}^{3}$, and let $\mathbf{m}=(\mathbf{a} \times \mathbf{b})+(\mathbf{b} \times \mathbf{c})+(\mathbf{c} \times \mathbf{a})$. Obtain expressions for the angle between $\mathbf{m}$ and each of $\mathbf{a}, \mathbf{b}$ and $\mathbf{c}$, in terms of $\mathbf{a}, \mathbf{b}, \mathbf{c}$ and $|\mathbf{m}|$. Calculate $|\mathbf{m}|$ for the particular case when the angles between $\mathbf{a}, \mathbf{b}$ and $\mathbf{c}$ are all equal to $\theta$, and check your result for an example with $\theta=0$ and an example with $\theta=\pi / 2$.

Consider three planes in $\mathbb{R}^{3}$ passing through the points $\mathbf{p}, \mathbf{q}$ and $\mathbf{r}$, respectively, with unit normals $\mathbf{a}, \mathbf{b}$ and $\mathbf{c}$, respectively. State a condition that must be satisfied for the three planes to intersect at a single point, and find the intersection point.

Paper 1, Section II, A

commentWhat is the definition of an orthogonal matrix $M$ ?

Write down a $2 \times 2$ matrix $R$ representing the rotation of a 2-dimensional vector $(x, y)$ by an angle $\theta$ around the origin. Show that $R$ is indeed orthogonal.

Take a matrix

$A=\left(\begin{array}{ll} a & b \\ b & c \end{array}\right)$

where $a, b, c$ are real. Suppose that the $2 \times 2$ matrix $B=R A R^{T}$ is diagonal. Determine all possible values of $\theta$.

Show that the diagonal entries of $B$ are the eigenvalues of $A$ and express them in terms of the determinant and trace of $A$.

Using the above results, or otherwise, find the elements of the matrix

$\left(\begin{array}{ll} 1 & 2 \\ 2 & 1 \end{array}\right)^{2 N}$

as a function of $N$, where $N$ is a natural number.

Paper 1, Section II, B

commentLet $A$ be a real symmetric $n \times n$ matrix.

(a) Prove the following:

(i) Each eigenvalue of $A$ is real and there is a corresponding real eigenvector.

(ii) Eigenvectors corresponding to different eigenvalues are orthogonal.

(iii) If there are $n$ distinct eigenvalues then the matrix is diagonalisable.

Assuming that $A$ has $n$ distinct eigenvalues, explain briefly how to choose (up to an arbitrary scalar factor) the vector $v$ such that $\frac{v^{T} A v}{v^{T} v}$ is maximised.

(b) A scalar $\lambda$ and a non-zero vector $v$ such that

$A v=\lambda B v$

are called, for a specified $n \times n$ matrix $B$, respectively a generalised eigenvalue and a generalised eigenvector of $A$.

Assume the matrix $B$ is real, symmetric and positive definite (i.e. $\left(u^{*}\right)^{T} B u>0$ for all non-zero complex vectors $u$ ).

Prove the following:

(i) If $\lambda$ is a generalised eigenvalue of $A$ then it is a root of $\operatorname{det}(A-\lambda B)=0$.

(ii) Each generalised eigenvalue of $A$ is real and there is a corresponding real generalised eigenvector.

(iii) Two generalised eigenvectors $u, v$, corresponding to different generalised eigenvalues, are orthogonal in the sense that $u^{T} B v=0$.

(c) Find, up to an arbitrary scalar factor, the vector $v$ such that the value of $F(v)=\frac{v^{T} A v}{v^{T} B v}$ is maximised, and the corresponding value of $F(v)$, where

$A=\left(\begin{array}{ccc} 4 & 2 & 0 \\ 2 & 3 & 0 \\ 0 & 0 & 10 \end{array}\right) \quad \text { and } \quad B=\left(\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 3 \end{array}\right)$

Paper 1, Section II, B

comment(a) Consider the matrix

$R=\left(\begin{array}{ccc} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{array}\right)$

representing a rotation about the $z$-axis through an angle $\theta$.

Show that $R$ has three eigenvalues in $\mathbb{C}$ each with modulus 1 , of which one is real and two are complex (in general), and give the relation of the real eigenvector and the two complex eigenvalues to the properties of the rotation.

Now consider the rotation composed of a rotation by angle $\pi / 2$ about the $z$-axis followed by a rotation by angle $\pi / 2$ about the $x$-axis. Determine the rotation axis $\mathbf{n}$ and the magnitude of the angle of rotation $\phi$.

(b) A surface in $\mathbb{R}^{3}$ is given by

$7 x^{2}+4 x y+3 y^{2}+2 x z+3 z^{2}=1 .$

By considering a suitable eigenvalue problem, show that the surface is an ellipsoid, find the lengths of its semi-axes and find the position of the two points on the surface that are closest to the origin.