Part II 2006

• 1.I.1H

  Number Theory

  Part II, 2006

  State the theorem of the primitive root for an odd prime power modulus.

  Prove that 3 is a primitive root modulo $7^{n}$ for all integers $n \geqslant 1$. Is 2 a primitive root modulo $7^{n}$ for all integers $n \geqslant 1$ ?

  Prove that there is no primitive root modulo 8 .

  comment

• 2.I.1H

  Number Theory

  Part II, 2006

  Prove that all binary quadratic forms of discriminant $-7$ are equivalent to $x^{2}+x y+2 y^{2} .$

  Determine which prime numbers $p$ are represented by $x^{2}+x y+2 y^{2}$.

  comment

• 3.I.2G

  Topics in Analysis

  Part II, 2006

  Let $a_{0}, a_{1}, a_{2}, \ldots$ be positive integers and, for each $n$, let

  $$\frac{p_{n}}{q_{n}}=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+} \cdot \ddots+\frac{1}{a_{n}}}$$

  with $\left(p_{n}, q_{n}\right)=1$.

  Obtain an expression for the matrix $\left(\begin{array}{cc}p_{n} & p_{n-1} \\ q_{n} & q_{n-1}\end{array}\right)$ and use it to show that $p_{n} q_{n-1}-q_{n} p_{n-1}=(-1)^{n+1} .$

  comment

• 2.II.26J

  Applied Probability

  Part II, 2006

  (a) Define a renewal process $\left(X_{t}\right)$ with independent, identically-distributed holding times $S_{1}, S_{2}, \ldots .$ State without proof the strong law of large numbers for $\left(X_{t}\right)$. State without proof the elementary renewal theorem for the mean value $m(t)=\mathbb{E} X_{t}$.

  (b) A circular bus route consists of ten bus stops. At exactly 5am, the bus starts letting passengers in at the main bus station (stop 1). It then proceeds to stop 2 where it stops to let passengers in and out. It continues in this fashion, stopping at stops 3 to 10 in sequence. After leaving stop 10, the bus heads to stop 1 and the cycle repeats. The travel times between stops are exponentially distributed with mean 4 minutes, and the time required to let passengers in and out at each stop are exponentially distributed with mean 1 minute. Calculate approximately the average number of times the bus has gone round its route by $1 \mathrm{pm}$.

  When the driver's shift finishes, at exactly $1 \mathrm{pm}$, he immediately throws all the passengers off the bus if the bus is already stopped, or otherwise, he drives to the next stop and then throws the passengers off. He then drives as fast as he can round the rest of the route to the main bus station. Giving reasons but not proofs, calculate approximately the average number of stops he will drive past at the end of his shift while on his way back to the main bus station, not including either the stop at which he throws off the passengers or the station itself.

  comment

• 3.II.25J

  Applied Probability

  Part II, 2006

  A passenger plane with $N$ numbered seats is about to take off; $N-1$ seats have already been taken, and now the last passenger enters the cabin. The first $N-1$ passengers were advised by the crew, rather imprudently, to take their seats completely at random, but the last passenger is determined to sit in the place indicated on his ticket. If his place is free, he takes it, and the plane is ready to fly. However, if his seat is taken, he insists that the occupier vacates it. In this case the occupier decides to follow the same rule: if the free seat is his, he takes it, otherwise he insists on his place being vacated. The same policy is then adopted by the next unfortunate passenger, and so on. Each move takes a random time which is exponentially distributed with mean $\mu^{-1}$. What is the expected duration of the plane delay caused by these displacements?

  comment

• 4.II.26J

  Applied Probability

  Part II, 2006

  (a) Let $\left(N_{t}\right)_{t \geqslant 0}$ be a Poisson process of rate $\lambda>0$. Let $p$ be a number between 0 and 1 and suppose that each jump in $\left(N_{t}\right)$ is counted as type one with probability $p$ and type two with probability $1-p$, independently for different jumps and independently of the Poisson process. Let $M_{t}^{(1)}$ be the number of type-one jumps and $M_{t}^{(2)}=N_{t}-M_{t}^{(1)}$ the number of type-two jumps by time $t$. What can you say about the pair of processes $\left(M_{t}^{(1)}\right)_{t \geqslant 0}$ and $\left(M_{t}^{(2)}\right)_{t \geqslant 0}$ ? What if we fix probabilities $p_{1}, \ldots, p_{m}$ with $p_{1}+\ldots+p_{m}=1$ and consider $m$ types instead of two?

  (b) A person collects coupons one at a time, at jump times of a Poisson process $\left(N_{t}\right)_{t \geqslant 0}$ of rate $\lambda$. There are $m$ types of coupons, and each time a coupon of type $j$ is obtained with probability $p_{j}$, independently of the previously collected coupons and independently of the Poisson process. Let $T$ be the first time when a complete set of coupon types is collected. Show that

  $$\mathbb{P}(T<t)=\prod_{j=1}^{m}\left(1-e^{-p_{j} \lambda t}\right)$$

  Let $L=N_{T}$ be the total number of coupons collected by the time the complete set of coupon types is obtained. Show that $\lambda \mathbb{E} T=\mathbb{E} L$. Hence, or otherwise, deduce that $\mathbb{E} L$ does not depend on $\lambda$.

  comment

• 1.II $. 27 \mathrm{~J} \quad$

  Principles of Statistics

  Part II, 2006

  (a) What is a loss function? What is a decision rule? What is the risk function of a decision rule? What is the Bayes risk of a decision rule with respect to a prior $\pi$ ?

  (b) Let $\theta \mapsto R(\theta, d)$ denote the risk function of decision rule $d$, and let $r(\pi, d)$ denote the Bayes risk of decision rule $d$ with respect to prior $\pi$. Suppose that $d^{*}$ is a decision rule and $\pi_{0}$ is a prior over the parameter space $\Theta$ with the two properties

  (i) $r\left(\pi_{0}, d^{*}\right)=\min _{d} r\left(\pi_{0}, d\right)$

  (ii) $\sup _{\theta} R\left(\theta, d^{*}\right)=r\left(\pi_{0}, d^{*}\right)$.

  Prove that $d^{*}$ is minimax.

  (c) Suppose now that $\Theta=\mathcal{A}=\mathbb{R}$, where $\mathcal{A}$ is the space of possible actions, and that the loss function is

  $$L(\theta, a)=\exp (-\lambda a \theta),$$

  where $\lambda$ is a positive constant. If the law of the observation $X$ given parameter $\theta$ is $N\left(\theta, \sigma^{2}\right)$, where $\sigma>0$ is known, show (using (b) or otherwise) that the rule

  $$d^{*}(x)=x / \sigma^{2} \lambda$$

  is minimax.

  comment

• 2.II.27J

  Principles of Statistics

  Part II, 2006

  Let $\{f(\cdot \mid \theta): \theta \in \Theta\}$ be a parametric family of densities for observation $X$. What does it mean to say that the statistic $T \equiv T(X)$ is sufficient for $\theta$ ? What does it mean to say that $T$ is minimal sufficient?

  State the Rao-Blackwell theorem. State the Cramér-Rao lower bound for the variance of an unbiased estimator of a (scalar) parameter, taking care to specify any assumptions needed.

  Let $X_{1}, \ldots, X_{n}$ be a sample from a $U(0, \theta)$ distribution, where the positive parameter $\theta$ is unknown. Find a minimal sufficient statistic $T$ for $\theta$. If $h(T)$ is an unbiased estimator for $\theta$, find the form of $h$, and deduce that this estimator is minimum-variance unbiased. Would it be possible to reach this conclusion using the Cramér-Rao lower bound?

  comment

• 3.II.26J

  Principles of Statistics

  Part II, 2006

  Write an essay on the rôle of the Metropolis-Hastings algorithm in computational Bayesian inference on a parametric model. You may for simplicity assume that the parameter space is finite. Your essay should:

  (a) explain what problem in Bayesian inference the Metropolis-Hastings algorithm is used to tackle;

  (b) fully justify that the algorithm does indeed deliver the required information about the model;

  (c) discuss any implementational issues that need care.

  comment

• 4.II.27J

  Principles of Statistics

  Part II, 2006

  (a) State the strong law of large numbers. State the central limit theorem.

  (b) Assuming whatever regularity conditions you require, show that if $\hat{\theta}_{n} \equiv \hat{\theta}_{n}\left(X_{1}, \ldots, X_{n}\right)$ is the maximum-likelihood estimator of the unknown parameter $\theta$ based on an independent identically distributed sample of size $n$, then under $P_{\theta}$

  $$\sqrt{n}\left(\hat{\theta}_{n}-\theta\right) \rightarrow N\left(0, J(\theta)^{-1}\right) \quad \text { in distribution }$$

  as $n \rightarrow \infty$, where $J(\theta)$ is a matrix which you should identify. A rigorous derivation is not required.

  (c) Suppose that $X_{1}, X_{2}, \ldots$ are independent binomial $\operatorname{Bin}(1, \theta)$ random variables. It is required to test $H_{0}: \theta=\frac{1}{2}$ against the alternative $H_{1}: \theta \in(0,1)$. Show that the construction of a likelihood-ratio test leads us to the statistic

  $$T_{n}=2 n\left\{\hat{\theta}_{n} \log \hat{\theta}_{n}+\left(1-\hat{\theta}_{n}\right) \log \left(1-\hat{\theta}_{n}\right)+\log 2\right\}$$

  where $\hat{\theta}_{n} \equiv n^{-1} \sum_{k=1}^{n} X_{k}$. Stating clearly any result to which you appeal, for large $n$, what approximately is the distribution of $T_{n}$ under $H_{0}$ ? Writing $\hat{\theta}_{n}=\frac{1}{2}+Z_{n}$, and assuming that $Z_{n}$ is small, show that

  $$T_{n} \simeq 4 n Z_{n}^{2}$$

  Using this and the central limit theorem, briefly justify the approximate distribution of $T_{n}$ given by asymptotic maximum-likelihood theory. What could you say if the assumption that $Z_{n}$ is small failed?

  comment

• 1.II.28I

  Stochastic Financial Models

  Part II, 2006

  Over two periods a stock price $\left\{S_{t}: t=0,1,2\right\}$ moves on a binomial tree.

  

  Assuming that the riskless rate is constant at $r=1 / 3$, verify that all risk-neutral up-probabilities are given by one value $p \in(0,1)$. Find the time- 0 value of the following three put options all struck at $K=S_{0}=864=2^{5} \times 3^{3}$, with expiry 2 :

  (a) a European put;

  (b) an American put;

  (c) a European put modified by raising the strike to $K=992$ at time 1 if the stock went down in the first period.

  comment

• 2.II.28I

  Stochastic Financial Models

  Part II, 2006

  (a) In the context of a single-period financial market with $n$ traded assets and a single riskless asset earning interest at rate $r$, what is an arbitrage? What is an equivalent martingale measure? Explain marginal utility pricing, and how it leads to an equivalent martingale measure.

  (b) Consider the following single-period market with two assets. The first is a riskless bond, worth 1 at time 0 , and 1 at time 1 . The second is a share, worth 1 at time 0 and worth $S_{1}$ at time 1 , where $S_{1}$ is uniformly distributed on the interval $[0, a]$, where $a>0$. Under what condition on $a$ is this model arbitrage free? When it is, characterise the set $\mathcal{E}$ of equivalent martingale measures.

  An agent with $C^{2}$ utility $U$ and with wealth $w$ at time 0 aims to pick the number $\theta$ of shares to hold so as to maximise his expected utility of wealth at time 1 . Show that he will choose $\theta$ to be positive if and only if $a>2$.

  An option pays $\left(S_{1}-1\right)^{+}$at time 1 . Assuming that $a=2$, deduce that the agent's price for this option will be $1 / 4$, and show that the range of possible prices for this option as the pricing measure varies in $\mathcal{E}$ is the interval $\left(0, \frac{1}{2}\right)$.

  comment

• 3.II.27I

  Stochastic Financial Models

  Part II, 2006

  Let $r$ denote the riskless rate and let $\sigma>0$ be a fixed volatility parameter.

  (a) Let $\left(S_{t}\right)_{t \geqslant 0}$ be a Black-Scholes asset with zero dividends:

  $$S_{t}=S_{0} \exp \left(\sigma B_{t}+\left(r-\sigma^{2} / 2\right) t\right),$$

  where $B$ is standard Brownian motion. Derive the Black-Scholes partial differential equation for the price of a European option on $S$ with bounded payoff $\varphi\left(S_{T}\right)$ at expiry $T$ :

  $$\partial_{t} V+\frac{1}{2} \sigma^{2} S^{2} \partial_{S S} V+r S \partial_{S} V-r V=0, \quad V(T, \cdot)=\varphi(\cdot)$$

  [You may use the fact that for $C^{2}$ functions $f: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ satisfying exponential growth conditions, and standard Brownian motion $B$, the process

  $$C_{t}^{f}=f\left(t, B_{t}\right)-\int_{0}^{t}\left(\partial_{t} f+\frac{1}{2} \partial_{B B} f\right)\left(s, B_{s}\right) d s$$

  is a martingale.]

  (b) Indicate the changes in your argument when the asset pays dividends continuously at rate $D>0$. Find the corresponding Black-Scholes partial differential equation.

  (c) Assume $D=0$. Find a closed form solution for the time-0 price of a European power option with payoff $S_{T}^{n}$.

  comment

• 4.I.2G

  Topics in Analysis

  Part II, 2006

  (a) State the Baire category theorem, in its closed-sets version.

  (b) For every $n \in \mathbb{N}$ let $f_{n}$ be a continuous function from $\mathbb{R}$ to $\mathbb{R}$, and let $g(x)=1$ when $x$ is rational and 0 otherwise. For each $N \in \mathbb{N}$, let

  $$F_{N}=\left\{x \in \mathbb{R}: \forall n \geqslant N \quad f_{n}(x) \leqslant \frac{1}{3} \quad \text { or } \quad f_{n}(x) \geqslant \frac{2}{3}\right\} .$$

  By applying the Baire category theorem, prove that the functions $f_{n}$ cannot converge pointwise to $g$. (That is, it is not the case that $f_{n}(x) \rightarrow g(x)$ for every $x \in \mathbb{R}$.)

  comment

• 4.II.28I

  Stochastic Financial Models

  Part II, 2006

  State the definitions of a martingale and a stopping time.

  State and prove the optional sampling theorem.

  If $\left(M_{n}, \mathcal{F}_{n}\right)_{n \geqslant 0}$ is a martingale, under what conditions is it true that $M_{n}$ converges with probability 1 as $n \rightarrow \infty$ ? Show by an example that some condition is necessary.

  A market consists of $K>1$ agents, each of whom is either optimistic or pessimistic. At each time $n=0,1, \ldots$, one of the agents is selected at random, and chooses to talk to one of the other agents (again selected at random), whose type he then adopts. If choices in different periods are independent, show that the proportion of pessimists is a martingale. What can you say about the limiting behaviour of the proportion of pessimists as time $n$ tends to infinity?

  comment

• 2.II.29I

  Optimization and Control

  Part II, 2006

  A policy $\pi$ is to be chosen to maximize

  $$F(\pi, x)=\mathbb{E}_{\pi}\left[\sum_{t \geqslant 0} \beta^{t} r\left(x_{t}, u_{t}\right) \mid x_{0}=x\right]$$

  where $0<\beta \leqslant 1$. Assuming that $r \geqslant 0$, prove that $\pi$ is optimal if $F(\pi, x)$ satisfies the optimality equation.

  An investor receives at time $t$ an income of $x_{t}$ of which he spends $u_{t}$, subject to $0 \leqslant u_{t} \leqslant x_{t}$. The reward is $r\left(x_{t}, u_{t}\right)=u_{t}$, and his income evolves as

  $$x_{t+1}=x_{t}+\left(x_{t}-u_{t}\right) \varepsilon_{t},$$

  where $\left(\varepsilon_{t}\right)_{t \geqslant 0}$ is a sequence of independent random variables with common mean $\theta>0$. If $0<\beta \leqslant 1 /(1+\theta)$, show that the optimal policy is to take $u_{t}=x_{t}$ for all $t$.

  What can you say about the problem if $\beta>1 /(1+\theta) ?$

  comment

• 3.II.28I

  Optimization and Control

  Part II, 2006

  A discrete-time controlled Markov process evolves according to

  $$X_{t+1}=\lambda X_{t}+u_{t}+\varepsilon_{t}, \quad t=0,1, \ldots,$$

  where the $\varepsilon$ are independent zero-mean random variables with common variance $\sigma^{2}$, and $\lambda$ is a known constant.

  Consider the problem of minimizing

  $$F_{t, T}(x)=\mathbb{E}\left[\sum_{j=t}^{T-1} \beta^{j-t} C\left(X_{j}, u_{j}\right)+\beta^{T-t} R\left(X_{T}\right)\right],$$

  where $C(x, u)=\frac{1}{2}\left(u^{2}+a x^{2}\right), \beta \in(0,1)$ and $R(x)=\frac{1}{2} a_{0} x^{2}+b_{0}$. Show that the optimal control at time $j$ takes the form $u_{j}=k_{T-j} X_{j}$ for certain constants $k_{i}$. Show also that the minimized value for $F_{t, T}(x)$ is of the form

  $$\frac{1}{2} a_{T-t} x^{2}+b_{T-t}$$

  for certain constants $a_{j}, b_{j}$. Explain how these constants are to be calculated. Prove that the equation

  $$f(z) \equiv a+\frac{\lambda^{2} \beta z}{1+\beta z}=z$$

  has a unique positive solution $z=a_{*}$, and that the sequence $\left(a_{j}\right)_{j} \geqslant 0$ converges monotonically to $a_{*}$.

  Prove that the sequence $\left(b_{j}\right)_{j \geqslant 0}$ converges, to the limit

  $$b_{*} \equiv \frac{\beta \sigma^{2} a_{*}}{2(1-\beta)} .$$

  Finally, prove that $k_{j} \rightarrow k_{*} \equiv-\beta a_{*} \lambda /\left(1+\beta a_{*}\right)$.

  comment

• 4.II.29I

  Optimization and Control

  Part II, 2006

  An investor has a (possibly negative) bank balance $x(t)$ at time $t$. For given positive $x(0), T, \mu, A$ and $r$, he wishes to choose his spending rate $u(t) \geqslant 0$ so as to maximize

  $$\Phi(u ; \mu) \equiv \int_{0}^{T} e^{-\beta t} \log u(t) d t+\mu e^{-\beta T} x(T),$$

  where $d x(t) / d t=A+r x(t)-u(t)$. Find the investor's optimal choice of control $u(t)=u_{*}(t ; \mu)$.

  Let $x_{*}(t ; \mu)$ denote the optimally-controlled bank balance. By considering next how $x_{*}(T ; \mu)$ depends on $\mu$, show that there is a unique positive $\mu_{*}$ such that $x_{*}\left(T ; \mu_{*}\right)=0$. If the original problem is modified by setting $\mu=0$, but requiring that $x(T) \geqslant 0$, show that the optimal control for this modified problem is $u(t)=u_{*}\left(t ; \mu_{*}\right)$.

  comment

• 1.II.29A

  Partial Differential Equations

  Part II, 2006

  (a) State a local existence theorem for solving first order quasi-linear partial differential equations with data specified on a smooth hypersurface.

  (b) Solve the equation

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

  with boundary condition $u(x, 0)=f(x)$ where $f \in C^{1}(\mathbb{R})$, making clear the domain on which your solution is $C^{1}$. Comment on this domain with reference to the noncharacteristic condition for an initial hypersurface (including a definition of this concept).

  (c) Solve the equation

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

  with boundary condition $u(x, 0)=x$ and show that your solution is $C^{1}$ on some open set containing the initial hypersurface $y=0$. Comment on the significance of this, again with reference to the non-characteristic condition.

  comment

• 2.II.30A

  Partial Differential Equations

  Part II, 2006

  Define a fundamental solution of a constant-coefficient linear partial differential operator, and prove that the distribution defined by the function $N: \mathbb{R}^{3} \rightarrow \mathbb{R}$

  $$N(x)=(4 \pi|x|)^{-1}$$

  is a fundamental solution of the operator $-\Delta$ on $\mathbb{R}^{3}$.

  State and prove the mean value property for harmonic functions on $\mathbb{R}^{3}$ and deduce that any two smooth solutions of

  $$-\Delta u=f, \quad f \in C^{\infty}\left(\mathbb{R}^{3}\right)$$

  which satisfy the condition

  $$\lim _{|x| \rightarrow \infty} u(x)=0$$

  are in fact equal

  comment

• 3.II.29A

  Partial Differential Equations

  Part II, 2006

  Write down the formula for the solution $u=u(t, x)$ for $t>0$ of the initial value problem for the $n$-dimensional heat equation

  $$\begin{gathered} \frac{\partial u}{\partial t}-\Delta u=0 \\ u(0, x)=g(x) \end{gathered}$$

  for $g: \mathbb{R}^{n} \rightarrow \mathbb{C}$ a given smooth bounded function.

  State and prove the Duhamel principle giving the solution $v(t, x)$ for $t>0$ to the inhomogeneous initial value problem

  $$\begin{aligned} &\frac{\partial v}{\partial t}-\Delta v=f \\ &v(0, x)=g(x) \end{aligned}$$

  for $f=f(t, x)$ a given smooth bounded function.

  For the case $n=4$ and when $f=f(x)$ is a fixed Schwartz function (independent of $t)$, find $v(t, x)$ and show that $w(x)=\lim _{t \rightarrow+\infty} v(t, x)$ is a solution of

  $$-\Delta w=f \text {. }$$

  [Hint: you may use without proof the fact that the fundamental solution of the Laplacian on $\mathbb{R}^{4}$ is $\left.-1 /\left(4 \pi^{2}|x|^{2}\right) .\right]$

  comment

• 4.II.30A

  Partial Differential Equations

  Part II, 2006

  (a) State the Fourier inversion theorem for Schwartz functions $\mathcal{S}(\mathbb{R})$ on the real line. Define the Fourier transform of a tempered distribution and compute the Fourier transform of the distribution defined by the function $F(x)=\frac{1}{2}$ for $-t \leqslant x \leqslant+t$ and $F(x)=0$ otherwise. (Here $t$ is any positive number.)

  Use the Fourier transform in the $x$ variable to deduce a formula for the solution to the one dimensional wave equation

  $$u_{t t}-u_{x x}=0, \quad \text { with initial data } \quad u(0, x)=0, \quad u_{t}(0, x)=g(x),$$

  for $g$ a Schwartz function. Explain what is meant by "finite propagation speed" and briefly explain why the formula you have derived is in fact valid for arbitrary smooth $g \in C^{\infty}(\mathbb{R})$.

  (b) State a theorem on the representation of a smooth $2 \pi$-periodic function $g$ as a Fourier series

  $$g(x)=\sum_{\alpha \in \mathbb{Z}} \hat{g}(\alpha) e^{i \alpha x}$$

  and derive a representation for solutions to $(*)$ as Fourier series in $x$.

  (c) Verify that the formulae obtained in (a) and (b) agree for the case of smooth $2 \pi$ periodic $g$.

  comment

• 1.II $. 30 \mathrm{~B}$

  Asymptotic Methods

  Part II, 2006

  Two real functions $p(t), q(t)$ of a real variable $t$ are given on an interval $[0, b]$, where $b>0$. Suppose that $q(t)$ attains its minimum precisely at $t=0$, with $q^{\prime}(0)=0$, and that $q^{\prime \prime}(0)>0$. For a real argument $x$, define

  $$I(x)=\int_{0}^{b} p(t) e^{-x q(t)} d t$$

  Explain how to obtain the leading asymptotic behaviour of $I(x)$ as $x \rightarrow+\infty$ (Laplace's method).

  The modified Bessel function $I_{\nu}(x)$ is defined for $x>0$ by:

  $$I_{\nu}(x)=\frac{1}{\pi} \int_{0}^{\pi} e^{x \cos \theta} \cos (\nu \theta) d \theta-\frac{\sin (\nu \pi)}{\pi} \int_{0}^{\infty} e^{-x(\cosh t)-\nu t} d t .$$

  Show that

  $$I_{\nu}(x) \sim \frac{e^{x}}{\sqrt{2 \pi x}}$$

  as $x \rightarrow \infty$ with $\nu$ fixed.

  comment

• 3.II $. 30$ B

  Asymptotic Methods

  Part II, 2006

  The Airy function $\operatorname{Ai}(z)$ is defined by

  $$\operatorname{Ai}(z)=\frac{1}{2 \pi i} \int_{C} \exp \left(-\frac{1}{3} t^{3}+z t\right) d t$$

  where the contour $C$ begins at infinity along the ray $\arg (t)=4 \pi / 3$ and ends at infinity along the ray $\arg (t)=2 \pi / 3$. Restricting attention to the case where $z$ is real and positive, use the method of steepest descent to obtain the leading term in the asymptotic expansion for $\operatorname{Ai}(z)$ as $z \rightarrow \infty$ :

  $$\operatorname{Ai}(z) \sim \frac{\exp \left(-\frac{2}{3} z^{3 / 2}\right)}{2 \pi^{1 / 2} z^{1 / 4}}$$

  $\left[\right.$ Hint: put $\left.t=z^{1 / 2} \tau .\right]$

  comment

• 1.I $. 3 \mathrm{~F} \quad$

  Geometry and Groups

  Part II, 2006

  Suppose $S_{i}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is a similarity with contraction factor $c_{i} \in(0,1)$ for $1 \leqslant i \leqslant k$. Let $X$ be the unique non-empty compact invariant set for the $S_{i}$ 's. State a formula for the Hausdorff dimension of $X$, under an assumption on the $S_{i}$ 's you should state. Hence compute the Hausdorff dimension of the subset $X$ of the square $[0,1]^{2}$ defined by dividing the square into a $5 \times 5$ array of squares, removing the open middle square $(2 / 5,3 / 5)^{2}$, then removing the middle $1 / 25$ th of each of the remaining 24 squares, and so on.

  comment

• 4.II $. 31 \mathrm{~B}$

  Asymptotic Methods

  Part II, 2006

  (a) Outline the Liouville-Green approximation to solutions $w(z)$ of the ordinary differential equation

  $$\frac{d^{2} w}{d z^{2}}=f(z) w$$

  in a neighbourhood of infinity, in the case that, near infinity, $f(z)$ has the convergent series expansion

  $$f(z)=\sum_{s=0}^{\infty} \frac{f_{s}}{z^{s}}$$

  with $f_{0} \neq 0$.

  In the case

  $$f(z)=1+\frac{1}{z}+\frac{2}{z^{2}},$$

  explain why you expect a basis of two asymptotic solutions $w_{1}(z), w_{2}(z)$, with

  $$\begin{aligned} &w_{1}(z) \sim z^{\frac{1}{2}} e^{z}\left(1+\frac{a_{1}}{z}+\frac{a_{2}}{z^{2}}+\cdots\right), \\ &w_{2}(z) \sim z^{-\frac{1}{2}} e^{-z}\left(1+\frac{b_{1}}{z}+\frac{b_{2}}{z^{2}}+\cdots\right), \end{aligned}$$

  as $z \rightarrow+\infty$, and show that $a_{1}=-\frac{9}{8}$.

  (b) Determine, at leading order in the large positive real parameter $\lambda$, an approximation to the solution $u(x)$ of the eigenvalue problem:

  $$u^{\prime \prime}(x)+\lambda^{2} g(x) u(x)=0 ; \quad u(0)=u(1)=0$$

  where $g(x)$ is greater than a positive constant for $x \in[0,1]$.

  comment

• 1.II.31E

  Integrable Systems

  Part II, 2006

  (a) Let $q(x, t)$ satisfy the heat equation

  $$\frac{\partial q}{\partial t}=\frac{\partial^{2} q}{\partial x^{2}}$$

  Find the function $X$, which depends linearly on $\partial q / \partial x, q, k$, such that the heat equation can be written in the form

  $$\frac{\partial}{\partial t}\left(e^{-i k x+k^{2} t} q\right)+\frac{\partial}{\partial x}\left(e^{-i k x+k^{2} t} X\right)=0, \quad k \in \mathbb{C} .$$

  Use this equation to construct a Lax pair for the heat equation.

  (b) Use the above result, as well as the Cole-Hopf transformation, to construct a Lax pair for the Burgers equation

  $$\frac{\partial Q}{\partial t}-2 Q \frac{\partial Q}{\partial x}=\frac{\partial^{2} Q}{\partial x^{2}}$$

  (c) Find the second-order ordinary differential equation satisfied by the similarity solution of the so-called cylindrical $\mathrm{KdV}$ equation:

  $$\frac{\partial q}{\partial t}+\frac{\partial^{3} q}{\partial x^{3}}+q \frac{\partial q}{\partial x}+\frac{q}{3 t}=0, \quad t \neq 0$$

  comment

• 2.II.31E

  Integrable Systems

  Part II, 2006

  Let $\phi(t)$ satisfy the singular integral equation

  $$\left(t^{4}+t^{3}-t^{2}\right) \frac{\phi(t)}{2}+\frac{\left(t^{4}-t^{3}-t^{2}\right)}{2 \pi i} \oint_{C} \frac{\phi(\tau)}{\tau-t} d \tau=(A-1) t^{3}+t^{2}$$

  where $C$ denotes the circle of radius 2 centred on the origin, $\oint$ denotes the principal value integral and $A$ is a constant. Derive the associated Riemann-Hilbert problem, and compute the canonical solution of the corresponding homogeneous problem.

  Find the value of $A$ such that $\phi(t)$ exists, and compute the unique solution $\phi(t)$ if $A$ takes this value.

  comment

• 3.II.31E

  Integrable Systems

  Part II, 2006

  The solution of the initial value problem of the $\mathrm{KdV}$ equation is given by

  $$q(x, t)=-2 i \lim _{k \rightarrow \infty} k \frac{\partial N}{\partial x}(x, t, k),$$

  where the scalar function $N(x, t, k)$ can be obtained by solving the following RiemannHilbert problem:

  $$\frac{M(x, t, k)}{a(k)}=N(x, t,-k)+\frac{b(k)}{a(k)} \exp \left(2 i k x+8 i k^{3} t\right) N(x, t, k), \quad k \in \mathbb{R},$$

  $M, N$ and $a$ are the boundary values of functions of $k$ that are analytic for $\operatorname{Im} k>0$ and tend to unity as $k \rightarrow \infty$. The functions $a(k)$ and $b(k)$ can be determined from the initial condition $q(x, 0)$.

  Assume that $M$ can be written in the form

  $$\frac{M}{a}=\mathcal{M}(x, t, k)+\frac{c \exp \left(-2 p x+8 p^{3} t\right) N(x, t, i p)}{k-i p}, \quad \operatorname{Im} k \geqslant 0,$$

  where $\mathcal{M}$ as a function of $k$ is analytic for $\operatorname{Im} k>0$ and tends to unity as $k \rightarrow \infty ; c$ and $p$ are constants and $p>0$.

  (a) By solving the above Riemann-Hilbert problem find a linear equation relating $N(x, t, k)$ and $N(x, t, i p)$.

  (b) By solving this equation explicitly in the case that $b=0$ and letting $c=2 i p e^{-2 x_{0}}$, compute the one-soliton solution.

  (c) Assume that $q(x, 0)$ is such that $a(k)$ has a simple zero at $k=i p$. Discuss the dominant form of the solution as $t \rightarrow \infty$ and $x / t=O(1)$.

  comment

• 1.II.32D

  Principles of Quantum Mechanics

  Part II, 2006

  A particle in one dimension has position and momentum operators $\hat{x}$ and $\hat{p}$. Explain how to introduce the position-space wavefunction $\psi(x)$ for a quantum state $|\psi\rangle$ and use this to derive a formula for $\||\psi\rangle \|^{2}$. Find the wavefunctions for $\hat{x}|\psi\rangle$ and $\hat{p}|\psi\rangle$ in terms of $\psi(x)$, stating clearly any standard properties of position and momentum eigenstates which you require.

  Define annihilation and creation operators $a$ and $a^{\dagger}$ for a harmonic oscillator of unit mass and frequency and write the Hamiltonian

  $$H=\frac{1}{2} \hat{p}^{2}+\frac{1}{2} \hat{x}^{2}$$

  in terms of them. Let $\left|\psi_{\alpha}\right\rangle$ be a normalized eigenstate of $a$ with eigenvalue $\alpha$, a complex number. Show that $\left|\psi_{\alpha}\right\rangle$ cannot be an eigenstate of $H$ unless $\alpha=0$, and that $\left|\psi_{0}\right\rangle$ is an eigenstate of $H$ with the lowest possible energy. Find a normalized wavefunction for $\left|\psi_{\alpha}\right\rangle$ for any $\alpha$. Do there exist normalizable eigenstates of $a^{\dagger}$ ? Justify your answer.

  comment

• 2.II.32A

  Principles of Quantum Mechanics

  Part II, 2006

  Let $|\uparrow\rangle$ and $|\downarrow\rangle$ denote the eigenstates of $S_{z}$ for a particle of spin $\frac{1}{2}$. Show that

  $$|\uparrow \theta\rangle=\cos \frac{\theta}{2}|\uparrow\rangle+\sin \frac{\theta}{2}|\downarrow\rangle, \quad|\downarrow \theta\rangle=-\sin \frac{\theta}{2}|\uparrow\rangle+\cos \frac{\theta}{2}|\downarrow\rangle$$

  are eigenstates of $S_{z} \cos \theta+S_{x} \sin \theta$ for any $\theta$. Show also that the composite state

  $$|\chi\rangle=\frac{1}{\sqrt{2}}(|\uparrow\rangle|\downarrow\rangle-|\downarrow\rangle|\uparrow\rangle),$$

  for two spin- $\frac{1}{2}$ particles, is unchanged under a transformation

  $$|\uparrow\rangle \mapsto|\uparrow \theta\rangle, \quad|\downarrow\rangle \mapsto|\downarrow \theta\rangle$$

  applied to all one-particle states. Hence, by considering the action of certain components of the spin operator for the composite system, show that $|\chi\rangle$ is a state of total spin zero.

  Two spin- $\frac{1}{2}$ particles A and B have combined spin zero (as in the state $|\chi\rangle$ above) but are widely separated in space. A magnetic field is applied to particle B in such a way that its spin states are transformed according to $(*)$, for a certain value of $\theta$, while the spin states of particle A are unaffected. Once this has been done, a measurement is made of $S_{z}$ for particle A, followed by a measurement of $S_{z}$ for particle B. List the possible results for this pair of measurements and find the total probability, in terms of $\theta$, for each pair of outcomes to occur. For which outcomes is the two-particle system left in an eigenstate of the combined total spin operator, $S^{2}$, and what is the eigenvalue for each such outcome?

  $$\left[\sigma_{x}=\left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right), \quad \sigma_{y}=\left(\begin{array}{cc} 0 & -i \\ i & 0 \end{array}\right), \quad \sigma_{z}=\left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right) \cdot\right]$$

  comment

• 3.II.32D

  Principles of Quantum Mechanics

  Part II, 2006

  Consider a Hamiltonian $H$ with known eigenstates and eigenvalues (possibly degenerate). Derive a general method for calculating the energies of a new Hamiltonian $H+\lambda V$ to first order in the parameter $\lambda$. Apply this method to find approximate expressions for the new energies close to an eigenvalue $E$ of $H$, given that there are just two orthonormal eigenstates $|1\rangle$ and $|2\rangle$ corresponding to $E$ and that

  $$\langle 1|V| 1\rangle=\langle 2|V| 2\rangle=\alpha, \quad\langle 1|V| 2\rangle=\langle 2|V| 1\rangle=\beta$$

  A charged particle of mass $m$ moves in two-dimensional space but is confined to a square box $0 \leqslant x, y \leqslant a$. In the absence of any potential within this region the allowed wavefunctions are

  $$\psi_{p q}(x, y)=\frac{2}{a} \sin \frac{p \pi x}{a} \sin \frac{q \pi y}{a}, \quad p, q=1,2, \ldots$$

  inside the box, and zero outside. A weak electric field is now applied, modifying the Hamiltonian by a term $\lambda x y / a^{2}$, where $\lambda m a^{2} / \hbar^{2}$ is small. Show that the three lowest new energy levels for the particle are approximately

  $$\frac{\hbar^{2} \pi^{2}}{m a^{2}}+\frac{\lambda}{4}, \quad \frac{5 \hbar^{2} \pi^{2}}{2 m a^{2}}+\lambda\left(\frac{1}{4} \pm\left(\frac{4}{3 \pi}\right)^{4}\right)$$

  [It may help to recall that $2 \sin \theta \sin \varphi=\cos (\theta-\varphi)-\cos (\theta+\varphi)$.]

  comment

• 4.II.32A

  Principles of Quantum Mechanics

  Part II, 2006

  Define the Heisenberg picture of quantum mechanics in relation to the Schrödinger picture and explain how these formulations give rise to identical physical predictions. Derive an equation of motion for an operator in the Heisenberg picture, assuming the operator is independent of time in the Schrödinger picture.

  State clearly the form of the unitary operator corresponding to a rotation through an angle $\theta$ about an axis $\mathbf{n}$ (a unit vector) for a general quantum system. Verify your statement for the case in which the system is a single particle by considering the effect of an infinitesimal rotation on the particle's position $\hat{\mathbf{x}}$ and on its spin $\mathbf{S}$.

  Show that if the Hamiltonian for a particle is of the form

  $$H=\frac{1}{2 m} \hat{\mathbf{p}}^{2}+U\left(\hat{\mathbf{x}}^{2}\right) \hat{\mathbf{x}} \cdot \mathbf{S}$$

  then all components of the total angular momentum are independent of time in the Heisenberg picture. Is the same true for either orbital or spin angular momentum?

  [You may quote commutation relations involving components of $\hat{\mathbf{x}}, \hat{\mathbf{p}}, \mathbf{L}$ and $\mathbf{S}$.]

  comment

• 1.II.33A

  Applications of Quantum Mechanics

  Part II, 2006

  Consider a particle of mass $m$ and momentum $\hbar k$ moving under the influence of a spherically symmetric potential $V(r)$ such that $V(r)=0$ for $r \geqslant a$. Define the scattering amplitude $f(\theta)$ and the phase shift $\delta_{\ell}(k)$. Here $\theta$ is the scattering angle. How is $f(\theta)$ related to the differential cross section?

  Obtain the partial-wave expansion

  $$f(\theta)=\frac{1}{k} \sum_{\ell=0}^{\infty}(2 \ell+1) e^{i \delta_{\ell}} \sin \delta_{\ell} P_{\ell}(\cos \theta) .$$

  Let $R_{\ell}(r)$ be a solution of the radial Schrödinger equation, regular at $r=0$, for energy $\hbar^{2} k^{2} / 2 m$ and angular momentum $\ell$. Let

  $$Q_{\ell}(k)=a \frac{R_{\ell}^{\prime}(a)}{R_{\ell}(a)}-k a \frac{j_{\ell}^{\prime}(k a)}{j_{\ell}(k a)}$$

  Obtain the relation

  $$\tan \delta_{\ell}=\frac{Q_{\ell}(k) j_{\ell}^{2}(k a) k a}{Q_{\ell}(k) n_{\ell}(k a) j_{\ell}(k a) k a-1} .$$

  Suppose that

  $$\tan \delta_{\ell} \approx \frac{\gamma}{k_{0}-k},$$

  for some $\ell$, with all other $\delta_{\ell}$ small for $k \approx k_{0}$. What does this imply for the differential cross section when $k \approx k_{0}$ ?

  [For $V=0$, the two independent solutions of the radial Schrödinger equation are $j_{\ell}(k r)$ and $n_{\ell}(k r)$ with

  $$\begin{aligned} j_{\ell}(\rho) & \sim \frac{1}{\rho} \sin \left(\rho-\frac{1}{2} \ell \pi\right), \quad n_{\ell}(\rho) \sim-\frac{1}{\rho} \cos \left(\rho-\frac{1}{2} \ell \pi\right) \quad \text { as } \quad \rho \rightarrow \infty \\ e^{i \rho \cos \theta} &=\sum_{\ell=0}^{\infty}(2 \ell+1) i^{\ell} j_{\ell}(\rho) P_{\ell}(\cos \theta) \end{aligned}$$

  Note that the Wronskian $\rho^{2}\left(j_{\ell}(\rho) n_{\ell}^{\prime}(\rho)-j_{\ell}^{\prime}(\rho) n_{\ell}(\rho)\right)$ is independent of $\left.\rho .\right]$

  comment

• 2.II.33D

  Applications of Quantum Mechanics

  Part II, 2006

  State and prove Bloch's theorem for the electron wave functions for a periodic potential $V(\mathbf{r})=V(\mathbf{r}+\mathbf{l})$ where $\mathbf{l}=\sum_{i} n_{i} \mathbf{a}_{i}$ is a lattice vector.

  What is the reciprocal lattice? Explain why the Bloch wave-vector $\mathbf{k}$ is arbitrary up to $\mathbf{k} \rightarrow \mathbf{k}+\mathbf{g}$, where $\mathbf{g}$ is a reciprocal lattice vector.

  Describe in outline why one can expect energy bands $E_{n}(\mathbf{k})=E_{n}(\mathbf{k}+\mathbf{g})$. Explain how $\mathbf{k}$ may be restricted to a Brillouin zone $B$ and show that the number of states in volume $d^{3} k$ is

  $$\frac{2}{(2 \pi)^{3}} \mathrm{~d}^{3} k$$

  Assuming that the velocity of an electron in the energy band with Bloch wave-vector $\mathbf{k}$ is

  $$\mathbf{v}(\mathbf{k})=\frac{1}{\hbar} \frac{\partial}{\partial \mathbf{k}} E_{n}(\mathbf{k})$$

  show that the contribution to the electric current from a full energy band is zero. Given that $n(\mathbf{k})=1$ for each occupied energy level, show that the contribution to the current density is then

  $$\mathbf{j}=-e \frac{2}{(2 \pi)^{3}} \int_{B} \mathrm{~d}^{3} k n(\mathbf{k}) \mathbf{v}(\mathbf{k})$$

  where $-e$ is the electron charge.

  comment

• 1.II.12F

  Geometry and Groups

  Part II, 2006

  Compute the area of the ball of radius $r$ around a point in the hyperbolic plane. Deduce that, for any tessellation of the hyperbolic plane by congruent, compact tiles, the number of tiles which are at most $n$ "steps" away from a given tile grows exponentially in $n$. Give an explicit example of a tessellation of the hyperbolic plane.

  comment

• 3.II.33A

  Applications of Quantum Mechanics

  Part II, 2006

  Consider a one-dimensional crystal of lattice space $b$, with atoms having positions $x_{s}$ and momenta $p_{s}, s=0,1,2, \ldots, N-1$, such that the classical Hamiltonian is

  $$H=\sum_{s=0}^{N-1}\left(\frac{p_{s}^{2}}{2 m}+\frac{1}{2} m \lambda^{2}\left(x_{s+1}-x_{s}-b\right)^{2}\right)$$

  where we identify $x_{N}=x_{0}$. Show how this may be quantized to give the energy eigenstates consisting of a ground state $|0\rangle$ together with free phonons with energy $\hbar \omega\left(k_{r}\right)$ where $k_{r}=2 \pi r / N b$ for suitable integers $r$. Obtain the following expression for the quantum operator $x_{s}$

  $$x_{s}=s b+\left(\frac{\hbar}{2 m N}\right)^{\frac{1}{2}} \sum_{r} \frac{1}{\sqrt{\omega\left(k_{r}\right)}}\left(a_{r} e^{i k_{r} s b}+a_{r}^{\dagger} e^{-i k_{r} s b}\right)$$

  where $a_{r}, a_{r}^{\dagger}$ are annihilation and creation operators, respectively.

  An interaction involves the matrix element

  $$M=\sum_{s=0}^{N-1}\left\langle 0\left|e^{i q x_{s}}\right| 0\right\rangle .$$

  Calculate this and show that $|M|^{2}$ has its largest value when $q=2 \pi n / b$ for integer $n$.

  Disregard the case $\omega\left(k_{r}\right)=0$.

  [You may use the relations

  $$\sum_{s=0}^{N-1} e^{i k_{r} s b}= \begin{cases}N, & r=N b \\ 0 & \text { otherwise }\end{cases}$$

  and $e^{A+B}=e^{A} e^{B} e^{-\frac{1}{2}[A, B]}$ if $[A, B]$ commutes with $A$ and with $\left.B .\right]$

  comment

• 4.II.33D

  Applications of Quantum Mechanics

  Part II, 2006

  For the one-dimensional potential

  $$V(x)=-\frac{\hbar^{2} \lambda}{m} \sum_{n} \delta(x-n a)$$

  solve the Schrödinger equation for negative energy and obtain an equation that determines possible energy bands. Show that the results agree with the tight-binding model in appropriate limits.

  [It may be useful to note that $\left.V(x)=-\frac{\hbar^{2} \lambda}{m a} \sum_{n} e^{2 \pi i n x / a} .\right]$

  comment

• 2.II.34D

  Statistical Physics

  Part II, 2006

  What is meant by the heat capacity $C_{V}$ of a thermodynamic system? By establishing a suitable Maxwell identity, show that

  $$\left.\frac{\partial C_{V}}{\partial V}\right|_{T}=\left.T \frac{\partial^{2} P}{\partial T^{2}}\right|_{V} .$$

  In a certain model of $N$ interacting particles in a volume $V$ and at temperature $T$, the partition function is

  $$Z=\frac{1}{N !}(V-a N)^{N}(b T)^{3 N / 2}$$

  where $a$ and $b$ are constants. Find the equation of state and the entropy for this gas of particles. Find the energy and hence the heat capacity $C_{V}$ of the gas, and verify that the relation $(*)$ is satisfied.

  comment

• 3.II.34D

  Statistical Physics

  Part II, 2006

  What is meant by the chemical potential of a thermodynamic system? Derive the Gibbs distribution with variable particle number $N$, for a system at temperature $T$ and chemical potential $\mu$. (You may assume that the volume does not vary.)

  Consider a non-interacting gas of fermions in a box of fixed volume, at temperature $T$ and chemical potential $\mu$. Use the Gibbs distribution to find the mean occupation number of a one-particle quantum state of energy $\varepsilon$. Assuming that the density of states is $C \varepsilon^{1 / 2}$, for some constant $C$, deduce that the mean number of particles with energies between $\varepsilon$ and $\varepsilon+d \varepsilon$ is

  $$\frac{C \varepsilon^{\frac{1}{2}} d \varepsilon}{e^{(\varepsilon-\mu) / T}+1} .$$

  Why can $\mu$ be identified with the Fermi energy $\varepsilon_{F}$ when $T=0$ ? Estimate the number of particles with energies greater than $\varepsilon_{F}$ when $T$ is small but non-zero.

  comment

• 4.II.34D

  Statistical Physics

  Part II, 2006

  Two examples of phenomenological temperature measurements are (i) the mark reached along the length of a liquid-in-glass thermometer; and (ii) the wavelength of the brightest colour of electromagnetic radiation emitted by a hot body (used, for example, to measure the surface temperature of a star).

  Give the definition of temperature in statistical physics, and explain how the analysis of ideal gases and black body radiation is used to calibrate and improve phenomenological temperature measurements like those mentioned above. You should give brief derivations of any key results that you use.

  comment

• 1.II $. 34 \mathrm{E} \quad$

  Electrodynamics

  Part II, 2006

  $\mathcal{S}$ and $\mathcal{S}^{\prime}$ are two reference frames with $\mathcal{S}^{\prime}$ moving with constant speed $v$ in the $x$-direction relative to $\mathcal{S}$. The co-ordinates $x^{a}$ and ${x^{\prime}}^{a}$ are related by $d x^{\prime a}=L^{a}{ }_{b} d x^{b}$ where

  $$L_{b}^{a}=\left(\begin{array}{cccc} \gamma & -\gamma v & 0 & 0 \\ -\gamma v & \gamma & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right)$$

  and $\gamma=\left(1-v^{2}\right)^{-1 / 2}$. What is the transformation rule for the scalar potential $\varphi$ and vector potential A between the two frames?

  As seen in $\mathcal{S}^{\prime}$ there is an infinite uniform stationary distribution of charge along the $x$-axis with uniform line density $\sigma$. Determine the electric and magnetic fields $\mathbf{E}$ and B both in $\mathcal{S}^{\prime}$ and $\mathcal{S}$. Check your answer by verifying explicitly the invariance of the two quadratic Lorentz invariants.

  Comment briefly on the limit $|v| \ll 1$.

  comment

• $3 . \mathrm{II} . 35 \mathrm{E} \quad$

  Electrodynamics

  Part II, 2006

  A particle of rest mass $m$ and charge $q$ is moving along a trajectory $x^{a}(s)$, where $s$ is the particle's proper time, in a given external electromagnetic field with 4-potential $A^{a}\left(x^{c}\right)$. Consider the action principle $\delta S=0$ where the action is $S=\int L d s$ and

  $$L\left(s, x^{a}, \dot{x}^{a}\right)=-m \sqrt{\eta_{a b} \dot{x}^{a} \dot{x}^{b}}-q A_{a}\left(x^{c}\right) \dot{x}^{a},$$

  and variations are taken with fixed endpoints.

  Show first that the action is invariant both under reparametrizations $s \rightarrow \alpha s+\beta$ where $\alpha$ and $\beta$ are constants and also under a change of electromagnetic gauge. Next define the generalized momentum $P_{a}=\partial L / \partial \dot{x}^{a}$, and obtain the equation of motion

  $$m \ddot{x}^{a}=q F_{b}^{a} \dot{x}^{b},$$

  where the tensor $F^{a}{ }_{b}$ should be defined and you may assume that $d / d s\left(\eta_{a b} \dot{x}^{a} \dot{x}^{b}\right)=0$. Then verify from $(*)$ that indeed $d / d s\left(\eta_{a b} \dot{x}^{a} \dot{x}^{b}\right)=0$.

  How does $P_{a}$ differ from the momentum $p_{a}$ of an uncharged particle? Comment briefly on the principle of minimal coupling.

  comment

• 4.II $. 35 \mathrm{E} \quad$

  Electrodynamics

  Part II, 2006

  The retarded scalar potential produced by a charge distribution $\rho\left(t^{\prime}, \mathbf{x}^{\prime}\right)$ is

  $$\varphi(t, \mathbf{x})=\frac{1}{4 \pi \epsilon_{0}} \int d^{3} x^{\prime} \frac{\rho\left(t-R, \mathbf{x}^{\prime}\right)}{R},$$

  where $R=|\mathbf{R}|$ and $\mathbf{R}=\mathbf{x}-\mathbf{x}^{\prime}$. By use of an appropriate delta function rewrite the integral as an integral over both $d^{3} x^{\prime}$ and $d t^{\prime}$ involving $\rho\left(t^{\prime}, \mathbf{x}^{\prime}\right)$.

  Now specialize to a point charge $q$ moving on a path $\mathbf{x}^{\prime}=\mathbf{x}_{0}\left(t^{\prime}\right)$ so that we may set

  $$\rho\left(t^{\prime}, \mathbf{x}^{\prime}\right)=q \delta^{(3)}\left(\mathbf{x}^{\prime}-\mathbf{x}_{0}\left(t^{\prime}\right)\right) .$$

  By performing the volume integral first obtain the Liénard-Wiechert potential

  $$\varphi(t, \mathbf{x})=\frac{q}{4 \pi \epsilon_{0}} \frac{1}{\left(R^{*}-\mathbf{v} \cdot \mathbf{R}^{*}\right)},$$

  where $\mathbf{R}^{*}$ and $\mathbf{v}$ should be specified.

  Obtain the corresponding result for the magnetic potential.

  comment

• 1.II.35A

  General Relativity

  Part II, 2006

  Let $\phi(x)$ be a scalar field and $\nabla_{a}$ denote the Levi-Civita covariant derivative operator of a metric tensor $g_{a b}$. Show that

  $$\nabla_{a} \nabla_{b} \phi=\nabla_{b} \nabla_{a} \phi$$

  If the Ricci tensor, $R_{a b}$, of the metric $g_{a b}$ satisfies

  $$R_{a b}=\partial_{a} \phi \partial_{b} \phi,$$

  find the energy momentum tensor $T_{a b}$ and use the contracted Bianchi identity to show that, if $\partial_{a} \phi \neq 0$, then

  $$\nabla_{a} \nabla^{a} \phi=0$$

  Show further that $(*)$ implies

  $$\partial_{a}\left(\sqrt{-g} g^{a b} \partial_{b} \phi\right)=0$$

  comment

• 2.II.35A

  General Relativity

  Part II, 2006

  The Schwarzschild metric is

  $$d s^{2}=\left(1-\frac{2 M}{r}\right)^{-1} d r^{2}+r^{2}\left(d \theta^{2}+\sin ^{2} \theta d \phi^{2}\right)-\left(1-\frac{2 M}{r}\right) d t^{2}$$

  Writing $u=1 / r$, obtain the equation

  $$\frac{d^{2} u}{d \phi^{2}}+u=3 M u^{2}$$

  determining the spatial orbit of a null (massless) particle moving in the equatorial plane $\theta=\pi / 2$.

  Verify that two solutions of $(*)$ are

  $$\begin{aligned} \text { (i) } u &=\frac{1}{3 M}, \quad \text { and } \\ \text { (ii) } \quad u &=\frac{1}{3 M}-\frac{1}{M} \frac{1}{\cosh \phi+1} . \end{aligned}$$

  What is the significance of solution (i)? Sketch solution (ii) and describe its relation to solution (i).

  Show that, near $\phi=\cosh ^{-1} 2$, one may approximate the solution (ii) by

  $$r \sin \left(\phi-\cosh ^{-1} 2\right) \approx \sqrt{27} M$$

  and hence obtain the impact parameter.

  comment

• 2.I.3F

  Geometry and Groups

  Part II, 2006

  Determine whether the following elements of $\operatorname{PSL}_{2}(\mathbb{R})$ are elliptic, parabolic, or hyperbolic. Justify your answers.

  $$\left(\begin{array}{cc} 5 & 8 \\ -2 & -3 \end{array}\right), \quad\left(\begin{array}{cc} -3 & 1 \\ 2 & -1 \end{array}\right)$$

  In the case of the first of these transformations find the fixed points.

  comment

• 4.II.36A

  General Relativity

  Part II, 2006

  What are local inertial co-ordinates? What is their physical significance and how are they related to the equivalence principle?

  If $V_{a}$ are the components of a covariant vector field, show that

  $$\partial_{a} V_{b}-\partial_{b} V_{a}$$

  are the components of an anti-symmetric second rank covariant tensor field.

  If $K^{a}$ are the components of a contravariant vector field and $g_{a b}$ the components of a metric tensor, let

  $$Q_{a b}=K^{c} \partial_{c} g_{a b}+g_{a c} \partial_{b} K^{c}+g_{c b} \partial_{a} K^{c}$$

  Show that

  $$Q_{a b}=2 \nabla_{(a} K_{b)},$$

  where $K_{a}=g_{a b} K^{b}$, and $\nabla_{a}$ is the Levi-Civita covariant derivative operator of the metric $g_{a b}$.

  In a particular co-ordinate system $\left(x^{1}, x^{2}, x^{3}, x^{4}\right)$, it is given that $K^{a}=(0,0,0,1)$, $Q_{a b}=0$. Deduce that, in this co-ordinate system, the metric tensor $g_{a b}$ is independent of the co-ordinate $x^{4}$. Hence show that

  $$\nabla_{a} K_{b}=\frac{1}{2}\left(\partial_{a} K_{b}-\partial_{b} K_{a}\right)$$

  and that

  $$E=-K_{a} \frac{d x^{a}}{d \lambda}$$

  is constant along every geodesic $x^{a}(\lambda)$ in every co-ordinate system.

  What further conditions must one impose on $K^{a}$ and $d x^{a} / d \lambda$ to ensure that the metric is stationary and that $E$ is proportional to the energy of a particle moving along the geodesic?

  comment

• 1.II.36B

  Fluid Dynamics II

  Part II, 2006

  Write down the boundary conditions that are satisfied at the interface between two viscous fluids in motion. Briefly discuss the physical meaning of these boundary conditions.

  A layer of incompressible fluid of density $\rho$ and viscosity $\mu$ flows steadily down a plane inclined at an angle $\theta$ to the horizontal. The layer is of uniform thickness $h$ measured perpendicular to the plane and the viscosity of the overlying air can be neglected. Using co-ordinates parallel and perpendicular to the plane, write down the equations of motion, and the boundary conditions on the plane and on the free top surface. Determine the pressure and velocity fields. Show that the volume flux down the plane is $\frac{1}{3} \rho g h^{3} \sin \theta / \mu$ per unit cross-slope width.

  Consider now the case where a second layer of fluid, of uniform thickness $\alpha h$, viscosity $\beta \mu$, and density $\rho$ flows steadily on top of the first layer. Determine the pressure and velocity fields in each layer. Why does the velocity profile in the bottom layer depend on $\alpha$ but not on $\beta$ ?

  comment

• 2.II.36B

  Fluid Dynamics II

  Part II, 2006

  A very long cylinder of radius a translates steadily at speed $V$ in a direction perpendicular to its axis and parallel to a plane boundary. The centre of the cylinder remains a distance $a+b$ above the plane, where $b \ll a$, and the motion takes place through an incompressible fluid of viscosity $\mu$.

  Consider the force $F$ per unit length parallel to the plane that must be applied to the cylinder to maintain the motion. Explain why $F$ scales according to $F \propto \mu V(a / b)^{1 / 2}$.

  Approximating the lower cylindrical surface by a parabola, or otherwise, determine the velocity and pressure gradient fields in the space between the cylinder and the plane. Hence, by considering the shear stress on the plane, or otherwise, calculate $F$ explicitly.

  [You may use

  $$\int_{-\infty}^{\infty}\left(1+x^{2}\right)^{-1} d x=\pi, \quad \int_{-\infty}^{\infty}\left(1+x^{2}\right)^{-2} d x=\frac{1}{2} \pi \quad \text { and } \quad \int_{-\infty}^{\infty}\left(1+x^{2}\right)^{-3} d x=\frac{3}{8} \pi$$

  comment

• 3.II.36B

  Fluid Dynamics II

  Part II, 2006

  Define the rate of strain tensor $e_{i j}$ in terms of the velocity components $u_{i}$.

  Write down the relation between $e_{i j}$, the pressure $p$ and the stress tensor $\sigma_{i j}$ in an incompressible Newtonian fluid of viscosity $\mu$.

  Prove that $2 \mu e_{i j} e_{i j}$ is the local rate of dissipation per unit volume in the fluid.

  Incompressible fluid of density $\rho$ and viscosity $\mu$ occupies the semi-infinite domain $y>0$ above a rigid plane boundary $y=0$ that oscillates with velocity $(V \cos \omega t, 0,0)$, where $V$ and $\omega$ are constants. The fluid is at rest at $y=\infty$. Determine the velocity field produced by the boundary motion after any transients have decayed.

  Evaluate the time-averaged rate of dissipation in the fluid, per unit area of boundary.

  comment

• 4.II.37B

  Fluid Dynamics II

  Part II, 2006

  A line force of magnitude $F$ is applied in the positive $x$-direction to an unbounded fluid, generating a thin two-dimensional jet along the positive $x$-axis. The fluid is at rest at $y=\pm \infty$ and there is negligible motion in $x<0$. Write down the pressure gradient within the boundary layer. Deduce that the function $M(x)$ defined by

  $$M(x)=\int_{-\infty}^{\infty} \rho u^{2}(x, y) d y$$

  is independent of $x$ for $x>0$. Interpret this result, and explain why $M=F$. Use scaling arguments to deduce that there is a similarity solution having stream function

  $$\psi=(F \nu x / \rho)^{1 / 3} f(\eta) \quad \text { where } \quad \eta=y\left(F / \rho \nu^{2} x^{2}\right)^{1 / 3}$$

  Hence show that $f$ satisfies

  $$3 f^{\prime \prime \prime}+f^{\prime 2}+f f^{\prime \prime}=0 .$$

  Show that a solution of $(*)$ is

  $$f(\eta)=A \tanh (A \eta / 6)$$

  where $A$ is a constant to be determined by requiring that $M$ is independent of $x$. Find the volume flux, $Q(x)$, in the jet. Briefly indicate why $Q(x)$ increases as $x$ increases.

  [Hint: You may use $\left.\int_{-\infty}^{\infty} \operatorname{sech}^{4}(x) d x=4 / 3 .\right]$

  comment

• 1.II $37 \mathrm{C}$

  Waves

  Part II, 2006

  An elastic solid occupies the region $y<0$. The wave speeds in the solid are $c_{\mathrm{p}}$ and $c_{\mathrm{s}}$. A P-wave with dilatational potential

  $$\phi=\exp \left\{i k\left(x \sin \theta+y \cos \theta-c_{\mathrm{p}} t\right)\right\}$$

  is incident from $y<0$ on a rigid barrier at $y=0$. Obtain the reflected waves.

  Are there circumstances where the reflected S-wave is evanescent? Give reasons for your answer.

  comment

• $2 . \mathrm{II} . 37 \mathrm{C} \quad$

  Waves

  Part II, 2006

  The dispersion relation for waves in deep water is

  $$\omega^{2}=g|k|$$

  At time $t=0$ the water is at rest and the elevation of its free surface is $\zeta=\zeta_{0} \exp (-|x| / b)$ where $b$ is a positive constant. Use Fourier analysis to find an integral expression for $\zeta(x, t)$ when $t>0$.

  Use the method of stationary phase to find $\zeta(V t, t)$ for fixed $V>0$ and $t \rightarrow \infty$.

  $$\left[\int_{-\infty}^{\infty} \exp \left(i k x-\frac{|x|}{b}\right) d x=\frac{2 b}{1+k^{2} b^{2}} ; \quad \int_{-\infty}^{\infty} \exp \left(-a x^{2}\right) d x=\sqrt{\frac{\pi}{a}}(\operatorname{Re} a \geqslant 0) \cdot\right]$$

  comment

• $3 . \mathrm{II} . 37 \mathrm{C} \quad$

  Waves

  Part II, 2006

  An acoustic waveguide consists of a long straight tube $z>0$ with square crosssection $0<x<a, 0<y<a$ bounded by rigid walls. The sound speed of the gas in the tube is $c_{0}$. Find the dispersion relation for the propagation of sound waves along the tube. Show that for every dispersive mode there is a cut-off frequency, and determine the lowest cut-off frequency $\omega_{\min }$.

  An acoustic disturbance is excited at $z=0$ with a prescribed pressure perturbation $\tilde{p}(x, y, 0, t)=\tilde{P}(x, y) \exp (-i \omega t)$ with $\omega=\frac{1}{2} \omega_{\mathrm{min}}$. Find the pressure perturbation $\tilde{p}(x, y, z, t)$ at distances $z \gg a$ along the tube.

  comment

• 4.II $. 38 \mathrm{C} \quad$

  Waves

  Part II, 2006

  Obtain an expression for the compressive energy $W(\rho)$ per unit volume for adiabatic motion of a perfect gas, for which the pressure $p$ is given in terms of the density $\rho$ by a relation of the form

  $$p=p_{0}\left(\rho / \rho_{0}\right)^{\gamma},$$

  where $p_{0}, \rho_{0}$ and $\gamma$ are positive constants.

  For one-dimensional motion with speed $u$ write down expressions for the mass flux and the momentum flux. Deduce from the energy flux $u\left(p+W+\frac{1}{2} \rho u^{2}\right)$ together with the mass flux that if the motion is steady then

  $$\frac{\gamma}{\gamma-1} \frac{p}{\rho}+\frac{1}{2} u^{2}=\text { constant }$$

  A one-dimensional shock wave propagates at constant speed along a tube containing the gas. Ahead of the shock the gas is at rest with pressure $p_{0}$ and density $\rho_{0}$. Behind the shock the pressure is maintained at the constant value $(1+\beta) p_{0}$ with $\beta>0$. Determine the density $\rho_{1}$ behind the shock, assuming that $(\dagger)$ holds throughout the flow.

  For small $\beta$ show that the changes in pressure and density across the shock satisfy the adiabatic relation $(*)$ approximately, correect to order $\beta^{2}$.

  comment

• 1.II.38C

  Numerical Analysis

  Part II, 2006

  (a) Define the Jacobi method with relaxation for solving the linear system $A x=b$.

  (b) Let $A$ be a symmetric positive definite matrix with diagonal part $D$ such that the matrix $2 D-A$ is also positive definite. Prove that the iteration always converges if the relaxation parameter $\omega$ is equal to 1 .

  (c) Let $A$ be the tridiagonal matrix with diagonal elements $a_{i i}=1$ and off-diagonal elements $a_{i+1, i}=a_{i, i+1}=1 / 4$. Prove that convergence occurs if $\omega$ satisfies $0<\omega \leqslant 4 / 3$. Explain briefly why the choice $\omega=1$ is optimal.

  [You may quote without proof any relevant result about the convergence of iterative methods and about the eigenvalues of matrices.]

  comment

• 3.I.3F

  Geometry and Groups

  Part II, 2006

  Let $G$ be a discrete subgroup of the Möbius group. Define the limit set of $G$ in $S^{2}$. If $G$ contains two loxodromic elements whose fixed point sets in $S^{2}$ are different, show that the limit set of $G$ contains no isolated points.

  comment

• 2.II.38C

  Numerical Analysis

  Part II, 2006

  In the unit square the Poisson equation $\nabla^{2} u=f$, with zero Dirichlet boundary conditions, is being solved by the five-point formula using a square grid of mesh size $h=1 /(M+1)$,

  $$u_{i, j-1}+u_{i, j+1}+u_{i-1, j}+u_{i+1, j}-4 u_{i, j}=h^{2} f_{i, j} .$$

  Let $u(x, y)$ be the exact solution, and let $e_{i, j}=u_{i, j}-u(i h, j h)$ be the error of the five-point formula at the $(i, j)$ th grid point. Justifying each step, prove that

  $$\left[\sum_{i, j=1}^{M}\left|e_{i, j}\right|^{2}\right]^{1 / 2} \leqslant c h, \quad h \rightarrow 0$$

  where $c$ is some constant.

  comment

• 3.II.38C

  Numerical Analysis

  Part II, 2006

  (a) For the equation $y^{\prime}=f(t, y)$, consider the following multistep method with $s$ steps,

  $$\sum_{i=0}^{s} \rho_{i} y_{n+i}=h \sum_{i=0}^{s} \sigma_{i} f\left(t_{n+i}, y_{n+i}\right)$$

  where $h$ is the step size and $\rho_{i}, \sigma_{i}$ are specified constants with $\rho_{s}=1$. Prove that this method is of order $p$ if and only if

  $$\sum_{i=0}^{s} \rho_{i} Q\left(t_{n+i}\right)=h \sum_{i=0}^{s} \sigma_{i} Q^{\prime}\left(t_{n+i}\right)$$

  for any polynomial $Q$ of degree $\leqslant p$. Deduce that there is no $s$-step method of order $2 s+1$.

  [You may use the fact that, for any $a_{i}, b_{i}$, the Hermite interpolation problem

  $$Q\left(x_{i}\right)=a_{i}, \quad Q^{\prime}\left(x_{i}\right)=b_{i}, \quad i=0, \ldots, s$$

  is uniquely solvable in the space of polynomials of degree $2 s+1 .]$

  (b) State the Dahlquist equivalence theorem regarding the convergence of a multistep method. Determine all the values of the real parameter $a \neq 0$ for which the multistep method

  $$y_{n+3}+(2 a-3)\left[y_{n+2}-y_{n+1}\right]-y_{n}=h a\left[f_{n+2}+f_{n+1}\right]$$

  is convergent, and determine the order of convergence.

  comment

• 4.II.39C

  Numerical Analysis

  Part II, 2006

  The difference equation

  $$u_{m}^{n+1}=u_{m}^{n}+\frac{3}{2} \mu\left(u_{m-1}^{n}-2 u_{m}^{n}+u_{m+1}^{n}\right)-\frac{1}{2} \mu\left(u_{m-1}^{n-1}-2 u_{m}^{n-1}+u_{m+1}^{n-1}\right),$$

  where $\mu=\Delta t /(\Delta x)^{2}$, is used to approximate a solution of the diffusion equation $u_{t}=u_{x x}$.

  (a) Prove that, as $\Delta t \rightarrow 0$ with constant $\mu$, the local error of the method is $\mathcal{O}(\Delta t)^{2}$.

  (b) Applying the Fourier stability test, show that the method is stable if and only if $\mu \leqslant \frac{1}{4}$.

  comment

• 4.I.3F

  Geometry and Groups

  Part II, 2006

  What is a crystallographic group in the Euclidean plane? Prove that, if $G$ is crystallographic and $g$ is a nontrivial rotation in $G$, then $g$ has order $2,3,4$, or 6 .

  comment

• 4.II.12F

  Geometry and Groups

  Part II, 2006

  Let $G$ be a discrete subgroup of $\operatorname{PSL}_{2}(\mathbb{C})$. Show that $G$ is countable. Let $G=\left\{g_{1}, g_{2}, \ldots\right\}$ be some enumeration of the elements of $G$. Show that for any point $p$ in hyperbolic 3-space $\mathbb{H}^{3}$, the distance $d_{h y p}\left(p, g_{n}(p)\right)$ tends to infinity. Deduce that a subgroup $G$ of $\mathrm{PSL}_{2}(\mathbb{C})$ is discrete if and only if it acts properly discontinuously on $\mathbb{H}^{3}$.

  comment

• 1.I.4G

  Coding and Cryptography

  Part II, 2006

  Define a linear feedback shift register. Explain the Berlekamp-Massey method for "breaking" a key stream produced by a linear feedback shift register of unknown length. Use it to find the feedback polynomial of a linear feedback shift register with output sequence

  $$010111100010 \ldots$$

  comment

• 2.I.4G

  Coding and Cryptography

  Part II, 2006

  Let $\Sigma_{1}$ and $\Sigma_{2}$ be alphabets of sizes $m$ and $a$. What does it mean to say that an $a$-ary code $f: \Sigma_{1} \rightarrow \Sigma_{2}^{*}$ is decipherable? Show that if $f$ is decipherable then the word lengths $s_{1}, \ldots, s_{m}$ satisfy

  $$\sum_{i=1}^{m} a^{-s_{i}} \leqslant 1$$

  Find a decipherable binary code consisting of codewords 011, 0111, 01111, 11111, and three further codewords of length 2. How do you know the example you have given is decipherable?

  comment

• 3.I.1H

  Number Theory

  Part II, 2006

  Let $N=p_{1} p_{2} \ldots p_{r}$ be a product of distinct primes, and let $\lambda(N)$ be the least common multiple of $p_{1}-1, p_{2}-1, \ldots, p_{r}-1$. Prove that

  $$a^{\lambda(N)} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .$$

  Now take $N=7 \times 13 \times 19$, and prove that

  $$a^{N-1} \equiv 1 \bmod N \quad \text { when } \quad(a, N)=1 .$$

  comment

• 2.II.12G

  Coding and Cryptography

  Part II, 2006

  Define a cyclic code. Show that there is a bijection between the cyclic codes of length $n$, and the factors of $X^{n}-1$ in $\mathbb{F}_{2}[X]$.

  If $n$ is an odd integer then we can find a finite extension $K$ of $\mathbb{F}_{2}$ that contains a primitive $n$th root of unity $\alpha$. Show that a cyclic code of length $n$ with defining set $\left\{\alpha, \alpha^{2}, \ldots, \alpha^{\delta-1}\right\}$ has minimum distance at least $\delta$. Show that if $n=7$ and $\delta=3$ then we obtain Hamming's original code.

  [You may quote a formula for the Vandermonde determinant without proof.]

  comment

• 3.I.4G

  Coding and Cryptography

  Part II, 2006

  What does it mean to say that a binary code $C$ has length $n$, size $m$ and minimum distance $d$ ? Let $A(n, d)$ be the largest value of $m$ for which there exists an $[n, m, d]$-code. Prove that

  $$\frac{2^{n}}{V(n, d-1)} \leqslant A(n, d) \leqslant \frac{2^{n}}{V\left(n,\left\lfloor\frac{1}{2}(d-1)\right\rfloor\right)}$$

  where $V(n, r)=\sum_{j=0}^{r}\left(\begin{array}{l}n \\ j\end{array}\right)$.

  comment

• 3.II.12G

  Coding and Cryptography

  Part II, 2006

  Describe the RSA system with public key $(N, e)$ and private key $(N, d)$. Briefly discuss the possible advantages or disadvantages of taking (i) $e=2^{16}+1$ or (ii) $d=2^{16}+1$.

  Explain how to factor $N$ when both the private key and public key are known.

  Describe the bit commitment problem, and briefly indicate how RSA can be used to solve it.

  comment

• 4.I.4G

  Coding and Cryptography

  Part II, 2006

  A binary erasure channel with erasure probability $p$ is a discrete memoryless channel with channel matrix

  $$\left(\begin{array}{ccc} 1-p & p & 0 \\ 0 & p & 1-p \end{array}\right)$$

  State Shannon's second coding theorem, and use it to compute the capacity of this channel.

  comment

• 1.I.5I

  Statistical Modelling

  Part II, 2006

  Assume that observations $Y=\left(Y_{1}, \ldots, Y_{n}\right)^{T}$ satisfy the linear model

  $$Y=X \beta+\epsilon$$

  where $X$ is an $n \times p$ matrix of known constants of full $\operatorname{rank} p<n$, where $\beta=\left(\beta_{1}, \ldots, \beta_{p}\right)^{T}$ is unknown and $\epsilon \sim N_{n}\left(0, \sigma^{2} I\right)$. Write down a $(1-\alpha)$-level confidence set for $\beta$.

  Define Cook's distance for the observation $\left(x_{i}, Y_{i}\right)$, where $x_{i}^{T}$ is the $i$ th row of $X$. Give its interpretation in terms of confidence sets for $\beta$.

  In the above model with $n=50$ and $p=2$, you observe that one observation has Cook's distance 1.3. Would you be concerned about the influence of this observation?

  [You may find some of the following facts useful:

  (i) If $Z \sim \chi_{2}^{2}$, then $\mathbb{P}(Z \leqslant 0.21)=0.1, \mathbb{P}(Z \leqslant 1.39)=0.5$ and $\mathbb{P}(Z \leqslant 4.61)=0.9$.

  (ii) If $Z \sim F_{2,48}$, then $\mathbb{P}(Z \leqslant 0.11)=0.1, \mathbb{P}(Z \leqslant 0.70)=0.5$ and $\mathbb{P}(Z \leqslant 2.42)=0.9$.

  (iii) If $Z \sim F_{48,2}$, then $\mathbb{P}(Z \leqslant 0.41)=0.1, \mathbb{P}(Z \leqslant 1.42)=0.5$ and $\mathbb{P}(Z \leqslant 9.47)=0.9$. ]

  comment

• 1.II.13I

  Statistical Modelling

  Part II, 2006

  The table below gives a year-by-year summary of the career batting record of the baseball player Babe Ruth. The first column gives his age at the start of each season and the second gives the number of 'At Bats' (AB) he had during the season. For each At Bat, it is recorded whether or not he scored a 'Hit'. The third column gives the total number of Hits he scored in the season, and the final column gives his 'Average' for the season, defined as the number of Hits divided by the number of At Bats.

  $\begin{array}{rrrr}\text { Age } & \text { AB } & \text { Hits } & \text { Average } \\ 19 & 10 & 2 & 0.200 \\ 20 & 92 & 29 & 0.315 \\ 21 & 136 & 37 & 0.272 \\ 22 & 123 & 40 & 0.325 \\ 23 & 317 & 95 & 0.300 \\ 24 & 432 & 139 & 0.322 \\ 25 & 457 & 172 & 0.376 \\ 26 & 540 & 204 & 0.378 \\ 27 & 406 & 128 & 0.315 \\ 28 & 522 & 205 & 0.393 \\ 29 & 529 & 200 & 0.378 \\ 30 & 359 & 134 & 0.373 \\ 31 & 495 & 184 & 0.372 \\ 32 & 540 & 192 & 0.356 \\ 33 & 536 & 173 & 0.323 \\ 34 & 499 & 172 & 0.345 \\ 35 & 518 & 186 & 0.359 \\ 36 & 534 & 199 & 0.373 \\ 39 & 365 & 156 & 0.341 \\ 30 & 72 & 13 & 0.181 \\ 359 & 138 & 0.301 \\ 32 & 105 & 0.288 \\ 3 & & & \\ 3 & 123\end{array}$

  Explain and interpret the $\mathrm{R}$ commands below. In particular, you should explain the model that is being fitted, the approximation leading to the given standard errors and the test that is being performed in the last line of output.

  

  Assuming that any required packages are loaded, draw a careful sketch of the graph that you would expect to see on entering the following lines of code:

  

  comment

• 2.I.5I

  Statistical Modelling

  Part II, 2006

  Let $Y_{1}, \ldots, Y_{n}$ be independent Poisson random variables with means $\mu_{1}, \ldots, \mu_{n}$, for $i=1, \ldots, n$, where $\log \left(\mu_{i}\right)=\beta x_{i}$, for some known constants $x_{i}$ and an unknown parameter $\beta$. Find the log-likelihood for $\beta$.

  By first computing the first and second derivatives of the log-likelihood for $\beta$, explain the algorithm you would use to find the maximum likelihood estimator, $\hat{\beta}$.

  comment

• 3.I.5I

  Statistical Modelling

  Part II, 2006

  Consider a generalized linear model for independent observations $Y_{1}, \ldots, Y_{n}$, with $\mathbb{E}\left(Y_{i}\right)=\mu_{i}$ for $i=1, \ldots, n$. What is a linear predictor? What is meant by the link function? If $Y_{i}$ has model function (or density) of the form

  $$f\left(y_{i} ; \mu_{i}, \sigma^{2}\right)=\exp \left[\frac{1}{\sigma^{2}}\left\{\theta\left(\mu_{i}\right) y_{i}-K\left(\theta\left(\mu_{i}\right)\right)\right\}\right] a\left(\sigma^{2}, y_{i}\right)$$

  for $y_{i} \in \mathcal{Y} \subseteq \mathbb{R}, \mu_{i} \in \mathcal{M} \subseteq \mathbb{R}, \sigma^{2} \in \Phi \subseteq(0, \infty)$, where $a\left(\sigma^{2}, y_{i}\right)$ is a known positive function, define the canonical link function.

  Now suppose that $Y_{1}, \ldots, Y_{n}$ are independent with $Y_{i} \sim \operatorname{Bin}\left(1, \mu_{i}\right)$ for $i=1, \ldots, n$. Derive the canonical link function.

  comment

• 4.I.5I

  Statistical Modelling

  Part II, 2006

  The table below summarises the yearly numbers of named storms in the Atlantic basin over the period 1944-2004, and also gives an index of average July ocean temperature in the northern hemisphere over the same period. To save space, only the data for the first four and last four years are shown.

  $\begin{array}{rrr}\text { Year } & \text { Storms } & \text { Temp } \\ 1944 & 11 & 0.165 \\ 1945 & 11 & 0.080 \\ 1946 & 6 & 0.000 \\ 1947 & 9 & -0.024 \\ \vdots & \vdots & \vdots \\ 2001 & 15 & 0.592 \\ 2002 & 12 & 0.627 \\ 2003 & 16 & 0.608 \\ 2004 & 15 & 0.546\end{array}$

  Explain and interpret the $\mathrm{R}$ commands and (slightly abbreviated) output below.

  

  In 2005 , the ocean temperature index was 0.743. Explain how you would predict the number of named storms for that year.

  comment

• 4.II.13I

  Statistical Modelling

  Part II, 2006

  Consider a linear model for $Y=\left(Y_{1}, \ldots, Y_{n}\right)^{T}$ given by

  $$Y=X \beta+\epsilon,$$

  where $X$ is a known $n \times p$ matrix of full rank $p<n$, where $\beta$ is an unknown vector and $\epsilon \sim N_{n}\left(0, \sigma^{2} I\right)$. Derive an expression for the maximum likelihood estimator $\hat{\beta}$ of $\beta$, and write down its distribution.

  Find also the maximum likelihood estimator $\hat{\sigma}^{2}$ of $\sigma^{2}$, and derive its distribution.

  [You may use Cochran's theorem, provided that it is stated carefully. You may also assume that the matrix $P=X\left(X^{T} X\right)^{-1} X^{T}$ has rank $p$, and that $I-P$ has rank $n-p$.]

  comment

• 3.II.11H

  Number Theory

  Part II, 2006

  State the prime number theorem, and Dirichlet's theorem on primes in arithmetic progression.

  If $p$ is an odd prime number, prove that $-1$ is a quadratic residue modulo $p$ if and only if $p \equiv 1 \bmod 4$.

  Let $p_{1}, \ldots, p_{m}$ be distinct prime numbers, and define

  $$N_{1}=4 p_{1} \ldots p_{m}-1, \quad N_{2}=4\left(p_{1} \ldots p_{m}\right)^{2}+1$$

  Prove that $N_{1}$ has at least one prime factor which is congruent to $3 \bmod 4$, and that every prime factor of $N_{2}$ must be congruent to $1 \bmod 4$.

  Deduce that there are infinitely many primes which are congruent to $1 \bmod 4$, and infinitely many primes which are congruent to $3 \bmod 4$.

  comment

• 1.I.6B

  Mathematical Biology

  Part II, 2006

  A large population of some species has probability $P(n, t)$ of taking the value $n$ at time $t$. Explain the use of the generating function $\phi(s, t)=\sum_{n=0}^{\infty} s^{n} P(n, t)$, and give expressions for $P(n, t)$ and $\langle n\rangle$ in terms of $\phi$.

  A particular population is subject to a birth-death process, so that the probability of an increase from $n$ to $n+1$ in unit time is $\alpha+\beta n$, while the probability of a decrease from $n$ to $n-1$ is $\gamma n$, with $\gamma>\beta$. Show that the master equation for $P(n, t)$ is

  $$\frac{\partial P(n, t)}{\partial t}=(\alpha+\beta(n-1)) P(n-1, t)+\gamma(n+1) P(n+1, t)-(\alpha+(\beta+\gamma) n) P(n, t)$$

  Derive the equation satisfied by $\phi$, and show that in the statistically steady state, when $\phi$ and $P$ are independent of time, $\phi$ takes the form

  $$\phi(s)=\left(\frac{\gamma-\beta}{\gamma-\beta s}\right)^{\alpha / \beta}$$

  Using the equation for $\phi$, or otherwise, find $\langle n\rangle$.

  comment

• 2.I.6B

  Mathematical Biology

  Part II, 2006

  Two interacting populations of prey and predators, with populations $u(t), v(t)$ respectively, obey the evolution equations (with all parameters positive)

  $$\begin{aligned} &\frac{d u}{d t}=u\left(\mu_{1}-\alpha_{1} v-\delta u\right) \\ &\frac{d v}{d t}=v\left(-\mu_{2}+\alpha_{2} u\right)-\epsilon \end{aligned}$$

  Give an explanation in terms of population dynamics of each of the terms in these equations.

  Show that if $\alpha_{2} \mu_{1}>\delta \mu_{2}$ there are two non-trivial fixed points with $u, v \neq 0$, provided $\epsilon$ is sufficiently small. Find the trace and determinant of the Jacobian in terms of $u, v$ and show that, when $\delta$ and $\epsilon$ are very small, the fixed point with $u \approx \mu_{1} / \delta$, $v \approx \epsilon \delta / \mu_{1} \alpha_{2}$ is always unstable.

  comment

• 2.II.13B

  Mathematical Biology

  Part II, 2006

  Consider the discrete predator-prey model for two populations $N_{t}, P_{t}$ of prey and predators, respectively:

  $$\left.\begin{array}{rl} N_{t+T} & =r N_{t} \exp \left(-a P_{t}\right) \\ P_{t+T} & =s N_{t}\left(1-b \exp \left(-a P_{t}\right)\right) \end{array}\right\},$$

  where $r, s, a, b$ are constants, all assumed to be positive.

  (a) Give plausible explanations of the meanings of $T, r, s, a, b$.

  (b) Nondimensionalize equations $(*)$ to show that with appropriate rescaling they may be reduced to the form

  $$\left.\begin{array}{l} n_{t+1}=r n_{t} \exp \left(-p_{t}\right) \\ p_{t+1}=n_{t}\left(1-b \exp \left(-p_{t}\right)\right) \end{array}\right\}$$

  (c) Now assume that $b<1, r>1$. Show that the origin is unstable, and that there is a nontrivial fixed point $(n, p)=\left(n_{c}(b, r), p_{c}(b, r)\right)$. Investigate the stability of this point by writing $\left(n_{t}, p_{t}\right)=\left(n_{c}+n_{t}^{\prime}, p_{c}+p_{t}^{\prime}\right)$ and linearizing. Express the linearized equations as a second order recurrence relation for $n_{t}^{\prime}$, and hence show that $n_{t}^{\prime}$ satisfies an equation of the form

  $$n_{t}^{\prime}=A \lambda_{1}^{t}+B \lambda_{2}^{t}$$

  where the quantities $\lambda_{1,2}$ satisfy $\lambda_{1}+\lambda_{2}=1+b n_{c} / r, \lambda_{1} \lambda_{2}=n_{c}$ and $A, B$ are constants. Give a similar expression for $p_{t}^{\prime}$ for the same values of $A, B$.

  Show that when $r$ is just greater than unity the $\lambda_{i}(i=1,2)$ are real and both less than unity, while if $n_{c}$ is just greater than unity then the $\lambda_{i}$ are complex with modulus greater than one. Show also that $n_{c}$ increases monotonically with $r$ and that if the roots are real neither of them can be unity.

  Deduce that the fixed point is stable for sufficiently small $r$ but loses stability for a value of $r$ that depends on $b$ but is certainly less than $e=\exp (1)$. Give an equation that determines the value of $r$ where stability is lost, and an equation that gives the argument of the eigenvalue at this point. Sketch the behaviour of the moduli of the eigenvalues as functions of $r$.

  comment

• 3.I.6B

  Mathematical Biology

  Part II, 2006

  The SIR epidemic model for an infectious disease divides the population $N$ into three categories of susceptible $S(t)$, infected $I(t)$ and recovered (non-infectious) $R(t)$. It is supposed that the disease is non-lethal, so that the population does not change in time.

  Explain the reasons for the terms in the following model equations:

  $$\frac{d S}{d t}=p R-r I S, \quad \frac{d I}{d t}=r I S-a I, \quad \frac{d R}{d t}=a I-p R$$

  At time $t=0, S \approx N$ while $I, R \ll 1$.

  (a) Show that if $r N<a$ no epidemic occurs.

  (b) Now suppose that $p>0$ and there is an epidemic. Show that the system has a nontrivial fixed point, and that it is stable to small disturbances. Show also that for both small and large $p$ both the trace and the determinant of the Jacobian matrix are $O(p)$, and deduce that the matrix has complex eigenvalues for sufficiently small $p$, and real eigenvalues for sufficiently large $p$.

  comment

• 3.II.13B

  Mathematical Biology

  Part II, 2006

  A chemical system with concentrations $u(x, t), v(x, t)$ obeys the coupled reactiondiffusion equations

  $$\begin{aligned} &\frac{d u}{d t}=r u+u^{2}-u v+\kappa_{1} \frac{d^{2} u}{d x^{2}} \\ &\frac{d v}{d t}=s\left(u^{2}-v\right)+\kappa_{2} \frac{d^{2} v}{d x^{2}} \end{aligned}$$

  where $r, s, \kappa_{1}, \kappa_{2}$ are constants with $s, \kappa_{1}, \kappa_{2}$ positive.

  (a) Find conditions on $r, s$ such that there is a steady homogeneous solution $u=u_{0}$, $v=u_{0}^{2}$ which is stable to spatially homogeneous perturbations.

  (b) Investigate the stability of this homogeneous solution to disturbances proportional to $\exp (i k x)$. Assuming that a solution satisfying the conditions of part (a) exists, find the region of parameter space in which the solution is stable to space-dependent disturbances, and show in particular that one boundary of this region for fixed $s$ is given by

  $$d \equiv \sqrt{\frac{\kappa_{2}}{\kappa_{1}}}=\sqrt{2 s}+\frac{1}{u_{0}} \sqrt{s\left(2 u_{0}^{2}-u_{0}\right)}$$

  Sketch the various regions of existence and stability of steady, spatially homogeneous solutions in the $\left(d, u_{0}\right)$ plane for the case $s=2$.

  (c) Show that the critical wavenumber $k=k_{c}$ for the onset of the instability satisfies the relation

  $$k_{c}^{2}=\frac{1}{\sqrt{\kappa_{1} \kappa_{2}}}\left[\frac{s(d-\sqrt{2 s})}{d(2 \sqrt{2 s}-d)}\right] .$$

  Explain carefully what happens when $d<\sqrt{2 s}$ and when $d>2 \sqrt{2 s}$.

  comment

• 4.I.6B

  Mathematical Biology

  Part II, 2006

  A nonlinear model of insect dispersal with exponential death rate takes the form (for insect population $n(x, t)$ )

  $$\frac{\partial n}{\partial t}=-\mu n+\frac{\partial}{\partial x}\left(n \frac{\partial n}{\partial x}\right)$$

  At time $t=0$ the total insect population is $Q$, and all the insects are at the origin. A solution is sought in the form

  $$n=\frac{e^{-\mu t}}{\lambda(t)} f(\eta) ; \quad \eta=\frac{x}{\lambda(t)}, \quad \lambda(0)=0$$

  (a) Verify that $\int_{-\infty}^{\infty} f d \eta=Q$, provided $f$ decays sufficiently rapidly as $|x| \rightarrow \infty$.

  (b) Show, by substituting the form of $n$ given in equation $(\dagger)$ into equation $(*)$, that $(*)$ is satisfied, for nonzero $f$, when

  $$\frac{d \lambda}{d t}=\lambda^{-2} e^{-\mu t} \quad \text { and } \quad \frac{d f}{d \eta}=-\eta$$

  Hence find the complete solution and show that the insect population is always confined to a finite region that never exceeds the range

  $$|x| \leqslant\left(\frac{9 Q}{2 \mu}\right)^{1 / 3}$$

  comment

• 1.I.7E

  Dynamical Systems

  Part II, 2006

  Find the fixed points of the system

  $$\begin{aligned} &\dot{x}=x(x+2 y-3) \\ &\dot{y}=y(3-2 x-y) \end{aligned}$$

  Local linearization shows that all the fixed points with $x y=0$ are saddle points. Why can you be certain that this remains true when nonlinear terms are taken into account? Classify the fixed point with $x y \neq 0$ by its local linearization. Show that the equation has Hamiltonian form, and thus that your classification is correct even when the nonlinear effects are included.

  Sketch the phase plane.

  comment

• 1.II.14E

  Dynamical Systems

  Part II, 2006

  (a) An autonomous dynamical system $\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$ in $\mathbb{R}^{2}$ has a periodic orbit $\mathbf{x}=\mathbf{X}(t)$ with period $T$. The linearized evolution of a small perturbation $\mathbf{x}=\mathbf{X}(t)+\boldsymbol{\eta}(t)$ is given by $\eta_{i}(t)=\Phi_{i j}(t) \eta_{j}(0)$. Obtain the differential equation and initial condition satisfied by the matrix $\boldsymbol{\Phi}(t)$.

  Define the Floquet multipliers of the orbit. Explain why one of the multipliers is always unity and show that the other is given by

  $$\exp \left(\int_{0}^{T} \nabla \cdot \mathbf{f}(\mathbf{X}(t)) d t\right)$$

  (b) Use the 'energy-balance' method for nearly Hamiltonian systems to find a leadingorder approximation to the amplitude of the limit cycle of the equation

  $$\ddot{x}+\epsilon\left(\alpha x^{2}+\beta \dot{x}^{2}-\gamma\right) \dot{x}+x=0,$$

  where $0<\epsilon \ll 1$ and $(\alpha+3 \beta) \gamma>0$.

  Compute a leading-order approximation to the nontrivial Floquet multiplier of the limit cycle and hence determine its stability.

  [You may assume that $\int_{0}^{2 \pi} \sin ^{2} \theta \cos ^{2} \theta d \theta=\pi / 4$ and $\int_{0}^{2 \pi} \cos ^{4} \theta d \theta=3 \pi / 4$.]

  comment

• 2.I.7E

  Dynamical Systems

  Part II, 2006

  Explain what is meant by a strict Lyapunov function on a domain $\mathcal{D}$ containing the origin for a dynamical system $\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$ in $\mathbb{R}^{n}$. Define the domain of stability of a fixed point $\mathbf{x}_{0}$.

  By considering the function $V=\frac{1}{2}\left(x^{2}+y^{2}\right)$ show that the origin is an asymptotically stable fixed point of

  $$\begin{aligned} &\dot{x}=-2 x+y+x^{3}-x y^{2} \\ &\dot{y}=-x-2 y+6 x^{2} y+4 y^{3} \end{aligned}$$

  Show also that its domain of stability includes $x^{2}+y^{2}<\frac{1}{2}$ and is contained in $x^{2}+y^{2} \leqslant 2$.

  comment

• 2.II.14E

  Dynamical Systems

  Part II, 2006

  Let $F: I \rightarrow I$ be a continuous one-dimensional map of an interval $I \subset \mathbb{R}$. Explain what is meant by saying (a) that $F$ has a horseshoe, (b) that $F$ is chaotic (Glendinning's definition).

  Consider the tent map defined on the interval $[0,1]$ by

  $$F(x)= \begin{cases}\mu x & 0 \leqslant x<\frac{1}{2} \\ \mu(1-x) & \frac{1}{2} \leqslant x \leqslant 1\end{cases}$$

  with $1<\mu \leqslant 2$.

  Find the non-zero fixed point $x_{0}$ and the points $x_{-1}<\frac{1}{2}<x_{-2}$ that satisfy

  $$F^{2}\left(x_{-2}\right)=F\left(x_{-1}\right)=x_{0} .$$

  Sketch a graph of $F$ and $F^{2}$ showing the points corresponding to $x_{-2}, x_{-1}$ and $x_{0}$. Hence show that $F^{2}$ has a horseshoe if $\mu \geqslant 2^{1 / 2}$.

  Explain briefly why $F^{4}$ has a horseshoe when $2^{1 / 4} \leqslant \mu<2^{1 / 2}$ and why there are periodic points arbitrarily close to $x_{0}$ for $\mu \geqslant 2^{1 / 2}$, but no such points for $2^{1 / 4} \leqslant \mu<2^{1 / 2}$.

  comment

• 4.I.1H

  Number Theory

  Part II, 2006

  Let $x$ be a real number greater than or equal to 2 , and define

  $$P(x)=\prod_{p \leqslant x}\left(1-\frac{1}{p}\right)$$

  where the product is taken over all primes $p$ which are less than or equal to $x$. Prove that $P(x) \rightarrow 0$ as $x \rightarrow \infty$, and deduce that $\sum_{p} \frac{1}{p}$ diverges when the summation is taken over all primes $p$.

  comment

• 3.I.7E

  Dynamical Systems

  Part II, 2006

  State the normal-form equations for (a) a saddle-node bifurcation, (b) a transcritical bifurcation, and (c) a pitchfork bifurcation, for a dynamical system $\dot{x}=f(x, \mu)$.

  Consider the system

  $$\begin{aligned} &\dot{x}=\mu+y-x^{2}+2 x y+3 y^{2} \\ &\dot{y}=-y+2 x^{2}+3 x y \end{aligned}$$

  Compute the extended centre manifold near $x=y=\mu=0$, and the evolution equation on the centre manifold, both correct to second order in $x$ and $\mu$. Deduce the type of bifurcation and show that the equation can be put in normal form, to the same order, by a change of variables of the form $T=\alpha t, X=x-\beta \mu, \tilde{\mu}=\gamma(\mu)$ for suitably chosen $\alpha, \beta$ and $\gamma(\mu)$.

  comment

• 4.I.7E

  Dynamical Systems

  Part II, 2006

  Consider the logistic map $F(x)=\mu x(1-x)$ for $0 \leqslant x \leqslant 1,0 \leqslant \mu \leqslant 4$. Show that there is a period-doubling bifurcation of the nontrivial fixed point at $\mu=3$. Show further that the bifurcating 2 -cycle $\left(x_{1}, x_{2}\right)$ is given by the roots of

  $$\mu^{2} x^{2}-\mu(\mu+1) x+\mu+1=0 .$$

  Show that there is a second period-doubling bifurcation at $\mu=1+\sqrt{6}$.

  comment

• 1.I.8E

  Further Complex Methods

  Part II, 2006

  The function $f(t)$ satisfies $f(t)=0$ for $t<1$ and

  $$f(t+1)-\frac{1}{2} f(t)=H(t),$$

  where $H(t)$ is the Heaviside step function. By taking Laplace transforms, show that, for $t \geqslant 1$,

  $$f(t)=2+2^{1-t} \sum_{n=-\infty}^{\infty} \frac{e^{2 \pi n i t}}{2 \pi n i-\log 2}$$

  and verify directly from the inversion integral that your solution satisfies $f(t)=0$ for $t<1$.

  comment

• 2.I.8E

  Further Complex Methods

  Part II, 2006

  The function $F(t)$ is defined, for $\operatorname{Re} t>-1$, by

  $$F(t)=\int_{0}^{\infty} \frac{u^{t} e^{-u}}{1+u} d u$$

  and by analytic continuation elsewhere in the complex $t$-plane. By considering the integral of a suitable function round a Hankel contour, obtain the analytic continuation of $F(t)$ and hence show that singularities of $F(t)$ can occur only at $z=-1,-2,-3, \ldots$.

  comment

• 3.I.8E

  Further Complex Methods

  Part II, 2006

  Show that, for $b \neq 0$,

  $$\mathcal{P} \int_{0}^{\infty} \frac{\cos u}{u^{2}-b^{2}} d u=-\frac{\pi}{2 b} \sin b$$

  where $\mathcal{P}$ denotes the Cauchy principal value.

  comment

• 3.II.14E

  Further Complex Methods

  Part II, 2006

  It is given that the hypergeometric function $F(a, b ; c ; z)$ is the solution of the hypergeometric equation determined by the Papperitz symbol

  $$P\left\{\begin{array}{ccc} 0 & \infty & 1 \\ 0 & a & 0 \\ 1-c & b & c-a-b \end{array}\right\}$$

  that is analytic at $z=0$ and satisfies $F(a, b ; c ; 0)=1$, and that for $\operatorname{Re}(c-a-b)>0$

  $$F(a, b ; c ; 1)=\frac{\Gamma(c) \Gamma(c-a-b)}{\Gamma(c-a) \Gamma(c-b)} .$$

  [You may assume that $a, b, c$ are such that $F(a, b ; c ; 1)$ exists.]

  (a) Show, by manipulating Papperitz symbols, that

  $$F(a, b ; c ; z)=(1-z)^{-a} F\left(a, c-b ; c ; \frac{z}{z-1}\right) \quad(|\arg (1-z)|<\pi) .$$

  (b) Let $w_{1}(z)=(-z)^{-a} F\left(a, 1+a-c ; 1+a-b ; \frac{1}{z}\right)$, where $|\arg (-z)|<\pi$. Show that $w_{1}(z)$ satisfies the hypergeometric equation determined by $(*)$.

  (c) By considering the limit $z \rightarrow \infty$ in parts (a) and (b) above, deduce that, for $|\arg (-z)|<\pi$,

  $$F(a, b ; c ; z)=\frac{\Gamma(c) \Gamma(b-a)}{\Gamma(b) \Gamma(c-a)} w_{1}(z)+(\text { a similar term with } a \text { and } b \text { interchanged })$$

  comment

• 4.I.8E

  Further Complex Methods

  Part II, 2006

  By means of the change of variable $u=r s, v=r(1-s)$ in a suitable double integral, or otherwise, show that for $\operatorname{Re} z>0$

  $$\left[\Gamma\left(\frac{1}{2} z\right)\right]^{2}=B\left(\frac{1}{2} z, \frac{1}{2} z\right) \Gamma(z)$$

  Deduce that, if $\Gamma(z)=0$ for some $z$ with $\operatorname{Re} z>0$, then $\Gamma\left(z / 2^{m}\right)=0$ for any positive integer $m$.

  Prove that $\Gamma(z) \neq 0$ for any $z$.

  comment

• 4.II.14E

  Further Complex Methods

  Part II, 2006

  Let $I=\int_{0}^{1}\left[x\left(1-x^{2}\right)\right]^{1 / 3} d x$

  (a) Express $I$ in terms of an integral of the form $\oint\left(z^{3}-z\right)^{1 / 3} d z$, where the path of integration is a large circle. You should explain carefully which branch of $\left(z^{3}-z\right)^{1 / 3}$ you choose, by using polar co-ordinates with respect to the branch points. Hence show that $I=\frac{1}{6} \pi \operatorname{cosec} \frac{1}{3} \pi$.

  (b) Give an alternative method of evaluating $I$, by making a suitable change of variable and expressing $I$ in terms of a beta function.

  comment

• 1.I.9C

  Classical Dynamics

  Part II, 2006

  Hamilton's equations for a system with $n$ degrees of freedom can be written in vector form as

  $$\dot{\mathbf{x}}=J \frac{\partial H}{\partial \mathbf{x}}$$

  where $\mathbf{x}=\left(q_{1}, \ldots, q_{n}, p_{1}, \ldots, p_{n}\right)^{T}$ is a $2 n$-vector and the $2 n \times 2 n$ matrix $J$ takes the form

  $$J=\left(\begin{array}{cc} 0 & 1 \\ -1 & 0 \end{array}\right)$$

  where 1 is the $n \times n$ identity matrix. Derive the condition for a transformation of the form $x_{i} \rightarrow y_{i}(\mathbf{x})$ to be canonical. For a system with a single degree of freedom, show that the following transformation is canonical for all nonzero values of $\alpha$ :

  $$Q=\tan ^{-1}\left(\frac{\alpha q}{p}\right), \quad P=\frac{1}{2}\left(\alpha q^{2}+\frac{p^{2}}{\alpha}\right)$$

  comment

• 1.II.15C

  Classical Dynamics

  Part II, 2006

  (a) In the Hamiltonian framework, the action is defined as

  $$S=\int\left(p_{a} \dot{q}_{a}-H\left(q_{a}, p_{a}, t\right)\right) d t$$

  Derive Hamilton's equations from the principle of least action. Briefly explain how the functional variations in this derivation differ from those in the derivation of Lagrange's equations from the principle of least action. Show that $H$ is a constant of the motion whenever $\partial H / \partial t=0$.

  (b) What is the invariant quantity arising in Liouville's theorem? Does the theorem depend on assuming $\partial H / \partial t=0$ ? State and prove Liouville's theorem for a system with a single degree of freedom.

  (c) A particle of mass $m$ bounces elastically along a perpendicular between two parallel walls a distance $b$ apart. Sketch the path of a single cycle in phase space, assuming that the velocity changes discontinuously at the wall. Compute the action $I=\oint p d q$ as a function of the energy $E$ and the constants $m, b$. Verify that the period of oscillation $T$ is given by $T=d I / d E$. Suppose now that the distance $b$ changes slowly. What is the relevant adiabatic invariant? How does $E$ change as a function of $b$ ?

  comment

• 4.II.11H

  Number Theory

  Part II, 2006

  Define the notion of a Fermat, Euler, and strong pseudo-prime to the base $b$, where $b$ is an integer greater than $1 .$

  Let $N$ be an odd integer greater than 1. Prove that:

  (a) If $N$ is a prime number, then $N$ is a strong pseudo-prime for every base $b$ with $(b, N)=1$.

  (b) If there exists a base $b_{1}$ with $1<b_{1}<N$ and $\left(b_{1}, N\right)=1$ for which $N$ is not a pseudo-prime, then in fact $N$ is not a pseudo-prime for at least half of all bases $b$ with $1<b<N$ and $(b, N)=1$.

  Prove that 341 is a Fermat pseudo-prime, but not an Euler pseudo-prime, to the base $2 .$

  comment

• 2.I.9C

  Classical Dynamics

  Part II, 2006

  Two point masses, each of mass $m$, are constrained to lie on a straight line and are connected to each other by a spring of force constant $k$. The left-hand mass is also connected to a wall on the left by a spring of force constant $j$. The right-hand mass is similarly connected to a wall on the right, by a spring of force constant $\ell$, so that the potential energy is

  $$V=\frac{1}{2} k\left(\eta_{1}-\eta_{2}\right)^{2}+\frac{1}{2} j \eta_{1}^{2}+\frac{1}{2} \ell \eta_{2}^{2}$$

  where $\eta_{i}$ is the distance from equilibrium of the $i^{\text {th }}$mass. Derive the equations of motion. Find the frequencies of the normal modes.

  comment

• 3.I.9C

  Classical Dynamics

  Part II, 2006

  A pendulum of length $\ell$ oscillates in the $x y$ plane, making an angle $\theta(t)$ with the vertical $y$ axis. The pivot is attached to a moving lift that descends with constant acceleration $a$, so that the position of the bob is

  $$x=\ell \sin \theta, \quad y=\frac{1}{2} a t^{2}+\ell \cos \theta .$$

  Given that the Lagrangian for an unconstrained particle is

  $$L=\frac{1}{2} m\left(\dot{x}^{2}+\dot{y}^{2}\right)+m g y,$$

  determine the Lagrangian for the pendulum in terms of the generalized coordinate $\theta$. Derive the equation of motion in terms of $\theta$. What is the motion when $a=g$ ?

  Find the equilibrium configurations for arbitrary $a$. Determine which configuration is stable when

  $$\text { (i) } a<g$$

  and when

  $$\text { (ii) } a>g \text {. }$$

  comment

• 3.II.15C

  Classical Dynamics

  Part II, 2006

  A particle of mass $m$ is constrained to move on the surface of a sphere of radius $\ell$.

  The Lagrangian is given in spherical polar coordinates by

  $$L=\frac{1}{2} m \ell^{2}\left(\dot{\theta}^{2}+\dot{\phi}^{2} \sin ^{2} \theta\right)+m g \ell \cos \theta,$$

  where gravity $g$ is constant. Find the two constants of the motion.

  The particle is projected horizontally with velocity $v$ from a point whose depth below the centre is $\ell \cos \theta=D$. Find $v$ such that the particle trajectory

  (i) just grazes the horizontal equatorial plane $\theta=\pi / 2$;

  (ii) remains at depth $D$ for all time $t$.

  comment

• 4.I.9C

  Classical Dynamics

  Part II, 2006

  Calculate the principal moments of inertia for a uniform cylinder, of mass $M$, radius $R$ and height $2 h$, about its centre of mass. For what height-to-radius ratio does the cylinder spin like a sphere?

  comment

• 1.I.10D

  Cosmology

  Part II, 2006

  (a) Introduce the concept of comoving co-ordinates in a homogeneous and isotropic universe and explain how the velocity of a galaxy is determined by the scale factor $a$. Express the Hubble parameter $H_{0}$ today in terms of the scale factor.

  (b) The Raychaudhuri equation states that the acceleration of the universe is determined by the mass density $\rho$ and the pressure $P$ as

  $$\frac{\ddot{a}}{a}=-\frac{4 \pi G}{3}\left(\rho+3 P / c^{2}\right)$$

  Now assume that the matter constituents of the universe satisfy $\rho+3 P / c^{2} \geqslant 0$. In this case explain clearly why the Hubble time $H_{0}^{-1}$ sets an upper limit on the age of the universe; equivalently, that the scale factor must vanish $\left(a\left(t_{i}\right)=0\right)$ at some time $t_{i}<t_{0}$ with $t_{0}-t_{i} \leqslant H_{0}^{-1}$.

  The observed Hubble time is $H_{0}^{-1}=1 \times 10^{10}$ years. Discuss two reasons why the above upper limit does not seem to apply to our universe.

  comment

• 2.I.10D

  Cosmology

  Part II, 2006

  The total energy of a gas can be expressed in terms of a momentum integral

  $$E=\int_{0}^{\infty} \mathcal{E}(p) \bar{n}(p) d p$$

  where $p$ is the particle momentum, $\mathcal{E}(p)=c \sqrt{p^{2}+m^{2} c^{2}}$ is the particle energy and $\bar{n}(p) d p$ is the average number of particles in the momentum range $p \rightarrow p+d p$. Consider particles in a cubic box of side $L$ with $p \propto L^{-1}$. Explain why the momentum varies as

  $$\frac{d p}{d V}=-\frac{p}{3 V}$$

  Consider the overall change in energy $d E$ due to the volume change $d V$. Given that the volume varies slowly, use the thermodynamic result $d E=-P d V$ (at fixed particle number $N$ and entropy $S$ ) to find the pressure

  $$P=\frac{1}{3 V} \int_{0}^{\infty} p \mathcal{E}^{\prime}(p) \bar{n}(p) d p .$$

  Use this expression to derive the equation of state for an ultrarelativistic gas.

  During the radiation-dominated era, photons remain in equilibrium with energy density $\epsilon_{\gamma} \propto T^{4}$ and number density $n_{\gamma} \propto T^{3}$. Briefly explain why the photon temperature falls inversely with the scale factor, $T \propto a^{-1}$. Discuss the implications for photon number and entropy conservation.

  comment

• 2.II.15D

  Cosmology

  Part II, 2006

  (a) Consider a homogeneous and isotropic universe filled with relativistic matter of mass density $\rho(t)$ and scale factor $a(t)$. Consider the energy $E(t) \equiv \rho(t) c^{2} V(t)$ of a small fluid element in a comoving volume $V_{0}$ where $V(t)=a^{3}(t) V_{0}$. Show that for slow (adiabatic) changes in volume, the density will satisfy the fluid conservation equation

  $$\dot{\rho}=-3 \frac{\dot{a}}{a}\left(\rho+P / c^{2}\right)$$

  where $P$ is the pressure.

  (b) Suppose that a flat $(k=0)$ universe is filled with two matter components:

  (i) radiation with an equation of state $P_{\mathrm{r}}=\frac{1}{3} \rho_{\mathrm{r}} c^{2}$.

  (ii) a gas of cosmic strings with an equation of state $P_{\mathrm{s}}=-\frac{1}{3} \rho_{\mathrm{s}} c^{2}$.

  Use the fluid conservation equation to show that the total relativistic mass density behaves as

  $$\rho=\frac{\rho_{\mathrm{r} 0}}{a^{4}}+\frac{\rho_{\mathrm{s} 0}}{a^{2}},$$

  where $\rho_{\mathrm{r} 0}$ and $\rho_{\mathrm{s} 0}$ are respectively the radiation and string densities today (that is, at $t=t_{0}$ when $a\left(t_{0}\right)=1$ ). Assuming that both the Hubble parameter today $H_{0}$ and the ratio $\beta \equiv \rho_{\mathrm{r} 0} / \rho_{\mathrm{s} 0}$ are known, show that the Friedmann equation can be rewritten as

  $$\left(\frac{\dot{a}}{a}\right)^{2}=\frac{H_{0}^{2}}{a^{4}}\left(\frac{a^{2}+\beta}{1+\beta}\right) .$$

  Solve this equation to find the following solution for the scale factor

  $$a(t)=\frac{\left(H_{0} t\right)^{1 / 2}}{(1+\beta)^{1 / 2}}\left[H_{0} t+2 \beta^{1 / 2}(1+\beta)^{1 / 2}\right]^{1 / 2} .$$

  Show that the scale factor has the expected asymptotic behaviour at early times $t \rightarrow 0$.

  Hence show that the age of this universe today is

  $$t_{0}=H_{0}^{-1}(1+\beta)^{1 / 2}\left[(1+\beta)^{1 / 2}-\beta^{1 / 2}\right]$$

  and that the time $t_{\mathrm{eq}}$ of equal radiation and string densities $\left(\rho_{\mathrm{r}}=\rho_{\mathrm{s}}\right)$ is

  $$t_{\mathrm{eq}}=H_{0}^{-1}(\sqrt{2}-1) \beta^{1 / 2}(1+\beta)^{1 / 2}$$

  comment

• 3.I.10D

  Cosmology

  Part II, 2006

  (a) Consider a spherically symmetric star with outer radius $R$, density $\rho(r)$ and pressure $P(r)$. By balancing the gravitational force on a shell at radius $r$ against the force due to the pressure gradient, derive the pressure support equation

  $$\frac{d P}{d r}=-\frac{G m \rho}{r^{2}}$$

  where $m(r)=\int_{0}^{r} \rho\left(r^{\prime}\right) 4 \pi r^{\prime 2} d r^{\prime}$. Show that this implies

  $$\frac{d}{d r}\left(\frac{r^{2}}{\rho} \frac{d P}{d r}\right)=-4 \pi G r^{2} \rho$$

  Suggest appropriate boundary conditions at $r=0$ and $r=R$, together with a brief justification.

  (b) Describe qualitatively the endpoint of stellar evolution for our sun when all its nuclear fuel is spent. Your discussion should briefly cover electron degeneracy pressure and the relevance of stability against inverse beta-decay.

  [Note that $m_{n}-m_{p} \approx 2.6 m_{e}$, where $m_{n}, m_{p}, m_{e}$ are the masses of the neutron, proton and electron respectively.]

  comment

• 4.I.10D

  Cosmology

  Part II, 2006

  The number density of fermions of mass $m$ at equilibrium in the early universe with temperature $T$, is given by the integral

  $$n=\frac{4 \pi}{h^{3}} \int_{0}^{\infty} \frac{p^{2} d p}{\exp [(\mathcal{E}(p)-\mu) / k T]+1}$$

  where $\mathcal{E}(p)=c \sqrt{p^{2}+m^{2} c^{2}}$, and $\mu$ is the chemical potential. Assuming that the fermions remain in equilibrium when they become non-relativistic $\left(k T, \mu \ll m c^{2}\right)$, show that the number density can be expressed as

  $$n=\left(\frac{2 \pi m k T}{h^{2}}\right)^{3 / 2} \exp \left[\left(\mu-m c^{2}\right) / k T\right]$$

  [Hint: You may assume $\left.\int_{0}^{\infty} d x e^{-\sigma^{2} x^{2}}=\sqrt{\pi} /(2 \sigma), \quad(\sigma>0) .\right]$

  Suppose that the fermions decouple at a temperature given by $k T=m c^{2} / \alpha$ where $\alpha \gg 1$. Assume also that $\mu=0$. By comparing with the photon number density at $n_{\gamma}=16 \pi \zeta(3)(k T / h c)^{3}$, where $\zeta(3)=\sum_{n=1}^{\infty} n^{-3}=1.202 \ldots$, show that the ratio of number densities at decoupling is given by

  $$\frac{n}{n_{\gamma}}=\frac{\sqrt{2 \pi}}{8 \zeta(3)} \alpha^{3 / 2} e^{-\alpha}$$

  Now assume that $\alpha \approx 20$, (which implies $n / n_{\gamma} \approx 5 \times 10^{-8}$ ), and that the fermion mass $m=m_{p} / 20$, where $m_{p}$ is the proton mass. Explain clearly why this new fermion would be a good candidate for solving the dark matter problem of the standard cosmology.

  comment

• 4.II.15D

  Cosmology

  Part II, 2006

  The perturbed motion of cold dark matter particles (pressure-free, $P=0$ ) in an expanding universe can be parametrized by the trajectories

  $$\mathbf{r}(\mathbf{q}, t)=a(t)[\mathbf{q}+\boldsymbol{\psi}(\mathbf{q}, t)]$$

  where $a(t)$ is the scale factor of the universe, $\mathbf{q}$ is the unperturbed comoving trajectory and $\boldsymbol{\psi}$ is the comoving displacement. The particle equation of motion is $\ddot{\mathbf{r}}=-\nabla \Phi$, where the Newtonian potential satisfies the Poisson equation $\nabla^{2} \Phi=4 \pi G \rho$ with mass density $\rho(\mathbf{r}, t)$.

  (a) Discuss how matter conservation in a small volume $d^{3} \mathbf{r}$ ensures that the perturbed density $\rho(\mathbf{r}, t)$ and the unperturbed background density $\bar{\rho}(t)$ are related by

  $$\rho(\mathbf{r}, t) d^{3} \mathbf{r}=\bar{\rho}(t) a^{3}(t) d^{3} \mathbf{q}$$

  By changing co-ordinates with the Jacobian

  $$\left|\partial r_{i} / \partial q_{j}\right|^{-1}=\left|a \delta_{i j}+a \partial \psi_{i} / \partial q_{j}\right|^{-1} \approx a^{-3}\left(1-\nabla_{q} \cdot \psi\right),$$

  show that the fractional density perturbation $\delta(\mathbf{q}, t)$ can be written to leading order as

  $$\delta \equiv \frac{\rho-\bar{\rho}}{\bar{\rho}}=-\nabla_{q} \cdot \psi,$$

  where $\nabla_{q} \cdot \boldsymbol{\psi}=\sum_{i} \partial \psi_{i} / \partial q_{i}$.

  Use this result to integrate the Poisson equation once. Hence, express the particle equation of motion in terms of the comoving displacement as

  $$\ddot{\boldsymbol{\psi}}+2 \frac{\dot{a}}{a} \dot{\boldsymbol{\psi}}-4 \pi G \bar{\rho} \boldsymbol{\psi}=0$$

  Infer that the density perturbation evolution equation is

  $$\ddot{\delta}+2 \frac{\dot{a}}{a} \dot{\delta}-4 \pi G \bar{\rho} \delta=0$$

  [Hint: You may assume that the integral of $\nabla^{2} \Phi=4 \pi G \bar{\rho}$ is $\nabla \Phi=-4 \pi G \bar{\rho} \mathbf{r} / 3$. Note also that the Raychaudhuri equation (for $P=0$ ) is $\ddot{a} / a=-4 \pi G \bar{\rho} / 3 .$.]

  (b) Find the general solution of equation $(*)$ in a flat $(k=0)$ universe dominated by cold dark matter $(P=0)$. Discuss the effect of late-time $\Lambda$ or dark energy domination on the growth of density perturbations.

  comment

• 1.I.2G

  Topics in Analysis

  Part II, 2006

  State Brouwer's fixed-point theorem, and also an equivalent version of the theorem that concerns retractions of the disc. Prove that these two versions are equivalent.

  comment

• 1.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain what it means for a poset to be chain-complete. State Zorn's Lemma, and use it to prove that, for any two elements $a$ and $b$ of a distributive lattice $L$ with $b \not{\leftarrow} a$, there exists a lattice homomorphism $f: L \rightarrow\{0,1\}$ with $f(a)=0$ and $f(b)=1$. Explain briefly how this result implies the completeness theorem for propositional logic.

  comment

• 2.II.16H

  Logic and Set Theory

  Part II, 2006

  Which of the following statements are true, and which false? Justify your answers.

  (a) For any ordinals $\alpha$ and $\beta$ with $\beta \neq 0$, there exist ordinals $\gamma$ and $\delta$ with $\delta<\beta$ such that $\alpha=\beta . \gamma+\delta$.

  (b) For any ordinals $\alpha$ and $\beta$ with $\beta \neq 0$, there exist ordinals $\gamma$ and $\delta$ with $\delta<\beta$ such that $\alpha=\gamma \cdot \beta+\delta$.

  (c) $\alpha \cdot(\beta+\gamma)=\alpha \cdot \beta+\alpha \cdot \gamma$ for all $\alpha, \beta, \gamma$.

  (d) $(\alpha+\beta) \cdot \gamma=\alpha \cdot \gamma+\beta \cdot \gamma$ for all $\alpha, \beta, \gamma$.

  (e) Any ordinal of the form $\omega . \alpha$ is a limit ordinal.

  (f) Any limit ordinal is of the form $\omega . \alpha$.

  comment

• 3.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain what is meant by a structure for a first-order signature $\Sigma$, and describe how first-order formulae over $\Sigma$ are interpreted in a given structure. Show that if $B$ is a substructure of $A$, and $\phi$ is a quantifier-free formula (with $n$ free variables), then

  $$\llbracket \phi \rrbracket_{B}=\llbracket \phi \rrbracket_{A} \cap B^{n}$$

  A first-order theory is said to be inductive if its axioms all have the form

  $$\left(\forall x_{1}, \ldots, x_{n}\right)\left(\exists y_{1}, \ldots, y_{m}\right) \phi$$

  where $\phi$ is quantifier-free (and either of the strings $x_{1}, \ldots, x_{n}$ or $y_{1}, \ldots, y_{m}$ may be empty). If $T$ is an inductive theory, and $A$ is a structure for the appropriate signature, show that the poset of those substructures of $A$ which are $T$-models is chain-complete.

  Which of the following can be expressed as inductive theories over the signature with one binary predicate symbol $\leqslant$ ? Justify your answers.

  (a) The theory of totally ordered sets without greatest or least elements.

  (b) The theory of totally ordered sets with greatest and least elements.

  comment

• 4.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain carefully what is meant by a well-founded relation on a set. State the recursion theorem, and use it to prove that a binary relation $r$ on a set $a$ is well-founded if and only if there exists a function $f$ from $a$ to some ordinal $\alpha$ such that $(x, y) \in r$ implies $f(x)<f(y)$.

  Deduce, using the axiom of choice, that any well-founded relation on a set may be extended to a well-ordering.

  comment

• 1.II .17F

  Graph Theory

  Part II, 2006

  State and prove Euler's formula relating the number of vertices, edges and faces of a connected plane graph

  Deduce that a planar graph of order $n \geqslant 3$ has size at most $3 n-6$. What bound can be given if the planar graph contains no triangles?

  Without invoking the four colour theorem, prove that a planar graph that contains no triangles is 4-colourable.

  comment

• 2.II.17F

  Graph Theory

  Part II, 2006

  Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. State Hall's necessary condition for $G$ to have a matching from $X$ to $Y$, and prove that it is sufficient.

  Deduce a necessary and sufficient condition for $G$ to have $|X|-d$ independent edges, where $d$ is a natural number.

  Show that the maximum size of a set of independent edges in $G$ is equal to the minimum size of a subset $S \subset V(G)$ such that every edge of $G$ has an end vertex in $S$.

  comment

• 3.II.17F

  Graph Theory

  Part II, 2006

  Let $R(s)$ be the least integer $n$ such that every colouring of the edges of $K_{n}$ with two colours contains a monochromatic $K_{s}$. Prove that $R(s)$ exists.

  Prove that a connected graph of maximum degree $d \geqslant 2$ and order $d^{k}$ contains two vertices distance at least $k$ apart.

  Let $C(s)$ be the least integer $n$ such that every connected graph of order $n$ contains, as an induced subgraph, either a complete graph $K_{s}$, a star $K_{1, s}$ or a path $P_{s}$ of length $s$. Show that $C(s) \leqslant R(s)^{s}$.

  comment

• 4.II.17F

  Graph Theory

  Part II, 2006

  What is meant by a graph $G$ of order $n$ being strongly regular with parameters $(d, a, b) ?$ Show that, if such a graph $G$ exists and $b>0$, then

  $$\frac{1}{2}\left\{n-1+\frac{(n-1)(b-a)-2 d}{\sqrt{(a-b)^{2}+4(d-b)}}\right\}$$

  is an integer.

  Let $G$ be a graph containing no triangles, in which every pair of non-adjacent vertices has exactly three common neighbours. Show that $G$ must be $d$-regular and $|G|=1+d(d+2) / 3$ for some $d \in\{1,3,21\}$. Show that such a graph exists for $d=3$.

  comment

• 1.II.18H

  Galois Theory

  Part II, 2006

  Let $K$ be a field and $f$ a separable polynomial over $K$ of degree $n$. Explain what is meant by the Galois group $G$ of $f$ over $K$. Show that $G$ is a transitive subgroup of $S_{n}$ if and only if $f$ is irreducible. Deduce that if $n$ is prime, then $f$ is irreducible if and only if $G$ contains an $n$-cycle.

  Let $f$ be a polynomial with integer coefficients, and $p$ a prime such that $\bar{f}$, the reduction of $f$ modulo $p$, is separable. State a theorem relating the Galois group of $f$ over $\mathbb{Q}$ to that of $\bar{f}$ over $\mathbb{F}_{p}$.

  Determine the Galois group of the polynomial $x^{5}-15 x-3$ over $\mathbb{Q}$.

  comment

• 2.II.18H

  Galois Theory

  Part II, 2006

  Write an essay on ruler and compass construction.

  comment

• 1.II.11G

  Topics in Analysis

  Part II, 2006

  Let $\mathbb{T}=\{z:|z|=1\}$ be the unit circle in $\mathbb{C}$, and let $\phi: \mathbb{T} \rightarrow \mathbb{C}$ be a continuous function that never takes the value 0 . Define the degree (or winding number) of $\phi$ about 0 . [You need not prove that the degree is well-defined.]

  Denote the degree of $\phi$ about 0 by $w(\phi)$. Prove the following facts.

  (i) If $\phi_{1}$ and $\phi_{2}$ are two functions with the properties of $\phi$ above, then $w\left(\phi_{1} \cdot \phi_{2}\right)=$ $w\left(\phi_{1}\right)+w\left(\phi_{2}\right)$

  (ii) If $\psi$ is any continuous function such that $|\psi(z)|<|\phi(z)|$ for every $z \in \mathbb{T}$, then $w(\phi+\psi)=w(\phi)$.

  Using these facts, calculate the degree $w(\phi)$ when $\phi$ is given by the formula $\phi(z)=$ $(3 z-2)(z-3)(2 z+1)+1 .$

  comment

• 3.II.18H

  Galois Theory

  Part II, 2006

  Let $K$ be a field and $m$ a positive integer, not divisible by the characteristic of $K$. Let $L$ be the splitting field of the polynomial $X^{m}-1$ over $K$. Show that $\operatorname{Gal}(L / K)$ is isomorphic to a subgroup of $(\mathbb{Z} / m \mathbb{Z})^{*}$.

  Now assume that $K$ is a finite field with $q$ elements. Show that $[L: K]$ is equal to the order of the residue class of $q$ in the group $(\mathbb{Z} / m \mathbb{Z})^{*}$. Hence or otherwise show that the splitting field of $X^{11}-1$ over $\mathbb{F}_{4}$ has degree 5 .

  comment

• 4.II.18H

  Galois Theory

  Part II, 2006

  Let $K$ be a field of characteristic different from 2 .

  Show that if $L / K$ is an extension of degree 2 , then $L=K(x)$ for some $x \in L$ such that $x^{2}=a \in K$. Show also that if $L^{\prime}=K(y)$ with $0 \neq y^{2}=b \in K$ then $L$ and $L^{\prime}$ are isomorphic (as extensions of $K$ ) if and only $b / a$ is a square in $K$.

  Now suppose that $F=K\left(x_{1}, \ldots, x_{n}\right)$ where $0 \neq x_{i}^{2}=a_{i} \in K$. Show that $F / K$ is a Galois extension, with Galois group isomorphic to $(\mathbb{Z} / 2 \mathbb{Z})^{m}$ for some $m \leqslant n$. By considering the subgroups of $\operatorname{Gal}(F / K)$, show that if $K \subset L \subset F$ and $[L: K]=2$, then $L=K(y)$ where $y=\prod_{i \in I} x_{i}$ for some subset $I \subset\{1, \ldots, n\}$.

  comment

• 1.II.19F

  Representation Theory

  Part II, 2006

  (a) Let $G$ be a finite group and $X$ a finite set on which $G$ acts. Define the permutation representation $\mathbb{C}[X]$ and compute its character.

  (b) Let $G$ and $U$ be the following subgroups of $\mathrm{GL}_{2}\left(\mathbb{F}_{p}\right)$, where $p$ is a prime,

  $$G=\left\{\left(\begin{array}{cc} a & b \\ 0 & 1 \end{array}\right) \mid a \in \mathbb{F}_{p}^{\times}, b \in \mathbb{F}_{p}\right\}, \quad U=\left\{\left(\begin{array}{ll} 1 & b \\ 0 & 1 \end{array}\right) \mid b \in \mathbb{F}_{p}\right\}$$

  (i) Decompose $\mathbb{C}[G / U]$ into irreducible representations.

  (ii) Let $\psi: U \rightarrow \mathbb{C}^{\times}$be a non-trivial, one-dimensional representation. Determine the character of the induced representation $\operatorname{Ind}_{U}^{G} \psi$, and decompose $\operatorname{Ind}_{U}^{G} \psi$ into irreducible representations.

  (iii) List all of the irreducible representations of $G$ and show that your list is complete.

  comment

• 2.II.19F

  Representation Theory

  Part II, 2006

  (a) Let $G$ be $S_{4}$, the symmetric group on four letters. Determine the character table of $G$.

  [Begin by listing the conjugacy classes and their orders.]

  (b) For each irreducible representation $V$ of $G=S_{4}$, decompose $\operatorname{Res}_{A_{4}}^{S_{4}}(V)$ into irreducible representations. You must justify your answer.

  comment

• 3.II.19F

  Representation Theory

  Part II, 2006

  (a) Let $G=\mathrm{SU}_{2}$, and let $V_{n}$ be the space of homogeneous polynomials of degree $n$ in the variables $x$ and $y$. Thus $\operatorname{dim} V_{n}=n+1$. Define the action of $G$ on $V_{n}$ and show that $V_{n}$ is an irreducible representation of $G$.

  (b) Decompose $V_{3} \otimes V_{3}$ into irreducible representations. Decompose $\wedge^{2} V_{3}$ and $\mathrm{S}^{2} V_{3}$ into irreducible representations.

  (c) Given any representation $V$ of a group $G$, define the dual representation $V^{*}$. Show that $V_{n}^{*}$ is isomorphic to $V_{n}$ as a representation of $\mathrm{SU}_{2}$.

  [You may use any results from the lectures provided that you state them clearly.]

  comment

• 4.II.19F

  Representation Theory

  Part II, 2006

  In this question, all vector spaces will be complex.

  (a) Let $A$ be a finite abelian group.

  (i) Show directly from the definitions that any irreducible representation must be one-dimensional.

  (ii) Show that $A$ has a faithful one-dimensional representation if and only if $A$ is cyclic.

  (b) Now let $G$ be an arbitrary finite group and suppose that the centre of $G$ is nontrivial. Write $Z=\{z \in G \mid z g=g z \quad \forall g \in G\}$ for this centre.

  (i) Let $W$ be an irreducible representation of $G$. Show that $\operatorname{Res}_{Z}^{G} W=\operatorname{dim} W \cdot \chi$, where $\chi$ is an irreducible representation of $Z$.

  (ii) Show that every irreducible representation of $Z$ occurs in this way.

  (iii) Suppose that $Z$ is not a cyclic group. Show that there does not exist an irreducible representation $W$ of $G$ such that every irreducible representation $V$ occurs as a summand of $W^{\otimes n}$ for some $n$.

  comment

• 1.II.20G

  Number Fields

  Part II, 2006

  Let $\alpha, \beta, \gamma$ denote the zeros of the polynomial $x^{3}-n x-1$, where $n$ is an integer. The discriminant of the polynomial is defined as

  $$\Delta=\Delta\left(1, \alpha, \alpha^{2}\right)=(\alpha-\beta)^{2}(\beta-\gamma)^{2}(\gamma-\alpha)^{2}$$

  Prove that, if $\Delta$ is square-free, then $1, \alpha, \alpha^{2}$ is an integral basis for $k=\mathbb{Q}(\alpha)$.

  By verifying that

  $$\alpha(\alpha-\beta)(\alpha-\gamma)=2 n \alpha+3$$

  and further that the field norm of the expression on the left is $-\Delta$, or otherwise, show that $\Delta=4 n^{3}-27$. Hence prove that, when $n=1$ and $n=2$, an integral basis for $k$ is $1, \alpha, \alpha^{2}$.

  comment

• 2.II.20G

  Number Fields

  Part II, 2006

  Let $K=\mathbb{Q}(\sqrt{26})$ and let $\varepsilon=5+\sqrt{26}$. By Dedekind's theorem, or otherwise, show that the ideal equations

  $$2=[2, \varepsilon+1]^{2}, \quad 5=[5, \varepsilon+1][5, \varepsilon-1], \quad[\varepsilon+1]=[2, \varepsilon+1][5, \varepsilon+1]$$

  hold in $K$. Deduce that $K$ has class number 2 .

  Show that $\varepsilon$ is the fundamental unit in $K$. Hence verify that all solutions in integers $x, y$ of the equation $x^{2}-26 y^{2}=\pm 10$ are given by

  $$x+\sqrt{26} y=\pm \varepsilon^{n}(\varepsilon \pm 1) \quad(n=0, \pm 1, \pm 2, \ldots) .$$

  [It may be assumed that the Minkowski constant for $K$ is $\frac{1}{2}$.]

  comment

• 4.II.20G

  Number Fields

  Part II, 2006

  Let $\zeta=e^{2 \pi i / 5}$ and let $K=\mathbb{Q}(\zeta)$. Show that the discriminant of $K$ is 125 . Hence prove that the ideals in $K$ are all principal.

  Verify that $\left(1-\zeta^{n}\right) /(1-\zeta)$ is a unit in $K$ for each integer $n$ with $1 \leqslant n \leqslant 4$. Deduce that $5 /(1-\zeta)^{4}$ is a unit in $K$. Hence show that the ideal $[1-\zeta]$ is prime and totally ramified in $K$. Indicate briefly why there are no other ramified prime ideals in $K$.

  [It can be assumed that $\zeta, \zeta^{2}, \zeta^{3}, \zeta^{4}$ is an integral basis for $K$ and that the Minkowski constant for $K$ is $3 /\left(2 \pi^{2}\right)$.]

  comment

• 1.II.21H

  Algebraic Topology

  Part II, 2006

  Compute the homology groups of the "pinched torus" obtained by identifying a meridian circle $S^{1} \times\{p\}$ on the torus $S^{1} \times S^{1}$ to a point, for some point $p \in S^{1}$.

  comment

• 2.I.2G

  Topics in Analysis

  Part II, 2006

  (a) State Chebyshev's equal ripple criterion.

  (b) Let $f:[-1,1] \rightarrow \mathbb{R}$ be defined by

  $$f(x)=\cos 4 \pi x$$

  and let $g$ be a polynomial of degree 7 . Prove that there exists an $x \in[-1,1]$ such that $|f(x)-g(x)| \geqslant 1$.

  comment

• 2.II.21H

  Algebraic Topology

  Part II, 2006

  State the simplicial approximation theorem. Compute the number of 0 -simplices (vertices) in the barycentric subdivision of an $n$-simplex and also compute the number of $n$-simplices. Finally, show that there are at most countably many homotopy classes of continuous maps from the 2-sphere to itself.

  comment

• 3.II.20H

  Algebraic Topology

  Part II, 2006

  Let $X$ be the union of two circles identified at a point: the "figure eight". Classify all the connected double covering spaces of $X$. If we view these double coverings just as topological spaces, determine which of them are homeomorphic to each other and which are not.

  comment

• 4.II.21H

  Algebraic Topology

  Part II, 2006

  Fix a point $p$ in the torus $S^{1} \times S^{1}$. Let $G$ be the group of homeomorphisms $f$ from the torus $S^{1} \times S^{1}$ to itself such that $f(p)=p$. Determine a non-trivial homomorphism $\phi$ from $G$ to the group $\operatorname{GL}(2, \mathbb{Z})$.

  [The group $\mathrm{GL}(2, \mathbb{Z})$ consists of $2 \times 2$ matrices with integer coefficients that have an inverse which also has integer coefficients.]

  Establish whether each $f$ in the kernel of $\phi$ is homotopic to the identity map.

  comment

• 1.II.22G

  Linear Analysis

  Part II, 2006

  Let $U$ be a vector space. Define what it means for two norms $\|\cdot\|_{1}$ and $\left\|_{\cdot} \cdot\right\|_{2}$ on $U$ to be Lipschitz equivalent. Give an example of a vector space and two norms which are not Lipschitz equivalent.

  Show that, if $U$ is finite dimensional, all norms on $U$ are Lipschitz equivalent. Deduce that a finite dimensional subspace of a normed vector space is closed.

  Show that a normed vector space $W$ is finite dimensional if and only if $W$ contains a non-empty open set with compact closure.

  comment

• 2.II.22G

  Linear Analysis

  Part II, 2006

  Let $X$ be a metric space. Define what it means for a subset $E \subset X$ to be of first or second category. State and prove a version of the Baire category theorem. For $1 \leqslant p \leqslant \infty$, show that the set $\ell_{p}$ is of first category in the normed space $\ell_{r}$ when $r>p$ and $\ell_{r}$ is given its standard norm. What about $r=p$ ?

  comment

• 3.II.21G

  Linear Analysis

  Part II, 2006

  Let $X$ be a complex Banach space. We say a sequence $x^{i} \in X$ converges to $x \in X$ weakly if $\phi\left(x^{i}\right) \rightarrow \phi(x)$ for all $\phi \in X^{*}$. Let $T: X \rightarrow Y$ be bounded and linear. Show that if $x^{i}$ converges to $x$ weakly, then $T x^{i}$ converges to $T x$ weakly.

  Now let $X=\ell_{2}$. Show that for a sequence $x^{i} \in X, i=1,2, \ldots$, with $\left\|x^{i}\right\| \leqslant 1$, there exists a subsequence $x^{i_{k}}$ such that $x^{i_{k}}$ converges weakly to some $x \in X$ with $\|x\| \leqslant 1$.

  Now let $Y=\ell_{1}$, and show that $y^{i} \in Y$ converges to $y \in Y$ weakly if and only if $y^{i} \rightarrow y$ in the usual sense.

  Define what it means for a linear operator $T: X \rightarrow Y$ to be compact, and deduce from the above that any bounded linear $T: \ell_{2} \rightarrow \ell_{1}$ is compact.

  comment

• 4.II.22G

  Linear Analysis

  Part II, 2006

  Let $H$ be a complex Hilbert space. Define what it means for a linear operator $T: H \rightarrow H$ to be self-adjoint. State a version of the spectral theorem for compact selfadjoint operators on a Hilbert space. Give an example of a Hilbert space $H$ and a compact self-adjoint operator on $H$ with infinite dimensional range. Define the notions spectrum, point spectrum, and resolvent set, and describe these in the case of the operator you wrote down. Justify your answers.

  comment

• 1.II.23F

  Riemann Surfaces

  Part II, 2006

  Let $\Lambda=\mathbb{Z}+\mathbb{Z} \tau$ be a lattice in $\mathbb{C}$, where $\tau$ is a fixed complex number with positive imaginary part. The Weierstrass $\wp$-function is the unique meromorphic $\Lambda$-periodic function on $\mathbb{C}$ such that $\wp$ is holomorphic on $\mathbb{C} \backslash \Lambda$, and $\wp(z)-1 / z^{2} \rightarrow 0$ as $z \rightarrow 0$.

  Show that $\wp(-z)=\wp(z)$ and find all the zeros of $\wp^{\prime}$ in $\mathbb{C}$.

  Show that $\wp$ satisfies a differential equation

  $$\wp^{\prime}(z)^{2}=Q(\wp(z))$$

  for some cubic polynomial $Q(w)$. Further show that

  $$Q(w)=4\left(w-\wp\left(\frac{1}{2}\right)\right)\left(w-\wp\left(\frac{1}{2} \tau\right)\right)\left(w-\wp\left(\frac{1}{2}(1+\tau)\right)\right)$$

  and that the three roots of $Q$ are distinct.

  [Standard properties of meromorphic doubly-periodic functions may be used without proof provided these are accurately stated, but any properties of the $\wp$-function that you use must be deduced from first principles.]

  comment

• 2.II.23F

  Riemann Surfaces

  Part II, 2006

  Define the terms Riemann surface, holomorphic map between Riemann surfaces, and biholomorphic map.

  (a) Prove that if two holomorphic maps $f, g$ coincide on a non-empty open subset of a connected Riemann surface $R$ then $f=g$ everywhere on $R$.

  (b) Prove that if $f: R \rightarrow S$ is a non-constant holomorphic map between Riemann surfaces and $p \in R$ then there is a choice of co-ordinate charts $\phi$ near $p$ and $\psi$ near $f(p)$, such that $\left(\psi \circ f \circ \phi^{-1}\right)(z)=z^{n}$, for some non-negative integer $n$. Deduce that a holomorphic bijective map between Riemann surfaces is biholomorphic.

  [The inverse function theorem for holomorphic functions on open domains in $\mathbb{C}$ may be used without proof if accurately stated.]

  comment

• $3 . \mathrm{II} . 22 \mathrm{~F} \quad$

  Riemann Surfaces

  Part II, 2006

  Define the branching order $v_{f}(p)$ at a point $p$ and the degree of a non-constant holomorphic map $f$ between compact Riemann surfaces. State the Riemann-Hurwitz formula.

  Let $W_{m} \subset \mathbb{C}^{2}$ be an affine curve defined by the equation $s^{m}=t^{m}+1$, where $m \geqslant 2$ is an integer. Show that the projective curve $\bar{W}_{m} \subset \mathbb{P}^{2}$ corresponding to $W_{m}$ is non-singular and identify the points of $\bar{W}_{m} \backslash W_{m}$. Let $F$ be a continuous map from $\bar{W}_{m}$ to the Riemann sphere $S^{2}=\mathbb{C} \cup\{\infty\}$, such that the restriction of $F$ to $W_{m}$ is given by $F(s, t)=s$. Show that $F$ is holomorphic on $\bar{W}_{m}$. Find the degree and the ramification points of $F$ on $\bar{W}_{m}$ and their branching orders. Determine the genus of $\bar{W}_{m}$.

  [Basic properties of the complex structure on an algebraic curve may be used without proof if accurately stated.]

  comment

• 2.II.11G

  Topics in Analysis

  Part II, 2006

  (a) Let $K$ be a closed subset of the unit disc in $\mathbb{C}$. Let $f: \mathbb{C} \rightarrow \mathbb{C}$ be a rational function with all its poles of modulus strictly greater than 1 . Explain why $f$ can be approximated uniformly on $K$ by polynomials.

  [Standard results from complex analysis may be assumed.]

  (b) With $K$ as above, define $\Lambda$ to be the set of all $\lambda \in \mathbb{C} \backslash K$ such that the function $(z-\lambda)^{-1}$ can be uniformly approximated on $K$ by polynomials. If $\lambda \in \Lambda$, prove that there is some $\delta>0$ such that $\mu \in \Lambda$ whenever $|\lambda-\mu|<\delta$.

  comment

• 4.II.23F

  Riemann Surfaces

  Part II, 2006

  Define what is meant by a divisor on a compact Riemann surface, the degree of a divisor, and a linear equivalence between divisors. For a divisor $D$, define $\ell(D)$ and show that if a divisor $D^{\prime}$ is linearly equivalent to $D$ then $\ell(D)=\ell\left(D^{\prime}\right)$. Determine, without using the Riemann-Roch theorem, the value $\ell(P)$ in the case when $P$ is a point on the Riemann sphere $S^{2}$.

  [You may use without proof any results about holomorphic maps on $S^{2}$ provided that these are accurately stated.]

  State the Riemann-Roch theorem for a compact connected Riemann surface $C$. (You are not required to give a definition of a canonical divisor.) Show, by considering an appropriate divisor, that if $C$ has genus $g$ then $C$ admits a non-constant meromorphic function (that is a holomorphic map $C \rightarrow S^{2}$ ) of degree at most $g+1$.

  comment

• 1.II.24H

  Differential Geometry

  Part II, 2006

  (a) State and prove the inverse function theorem for a smooth map $f: X \rightarrow Y$ between manifolds without boundary.

  [You may assume the inverse function theorem for functions in Euclidean space.]

  (b) Let $p$ be a real polynomial in $k$ variables such that for some integer $m \geqslant 1$,

  $$p\left(t x_{1}, \ldots, t x_{k}\right)=t^{m} p\left(x_{1}, \ldots, x_{k}\right)$$

  for all real $t>0$ and all $y=\left(x_{1}, \ldots, x_{k}\right) \in \mathbb{R}^{k}$. Prove that the set $X_{a}$ of points $y$ where $p(y)=a$ is a $(k-1)$-dimensional submanifold of $\mathbb{R}^{k}$, provided it is not empty and $a \neq 0$.

  [You may use the pre-image theorem provided that it is clearly stated.]

  (c) Show that the manifolds $X_{a}$ with $a>0$ are all diffeomorphic. Is $X_{a}$ with $a>0$ necessarily diffeomorphic to $X_{b}$ with $b<0$ ?

  comment

• 2.II $24 \mathrm{H} \quad$

  Differential Geometry

  Part II, 2006

  Let $S \subset \mathbb{R}^{3}$ be a surface.

  (a) Define the exponential map $\exp _{p}$ at a point $p \in S$. Assuming that exp ${ }_{p}$ is smooth, show that $\exp _{p}$ is a diffeomorphism in a neighbourhood of the origin in $T_{p} S$.

  (b) Given a parametrization around $p \in S$, define the Christoffel symbols and show that they only depend on the coefficients of the first fundamental form.

  (c) Consider a system of normal co-ordinates centred at $p$, that is, Cartesian coordinates $(x, y)$ in $T_{p} S$ and parametrization given by $(x, y) \mapsto \exp _{p}\left(x e_{1}+y e_{2}\right)$, where $\left\{e_{1}, e_{2}\right\}$ is an orthonormal basis of $T_{p} S$. Show that all of the Christoffel symbols are zero at $p$.

  comment

• 3.II.23H

  Differential Geometry

  Part II, 2006

  Let $S \subset \mathbb{R}^{3}$ be a connected oriented surface.

  (a) Define the Gauss map $N: S \rightarrow S^{2}$ of $S$. Given $p \in S$, show that the derivative of $N$,

  $$d N_{p}: T_{p} S \rightarrow T_{N(p)} S^{2}=T_{p} S$$

  is self-adjoint.

  (b) Show that if $N$ is a diffeomorphism, then the Gaussian curvature is positive everywhere. Is the converse true?

  comment

• 4.II.24H

  Differential Geometry

  Part II, 2006

  (a) Let $S \subset \mathbb{R}^{3}$ be an oriented surface and let $\lambda$ be a real number. Given a point $p \in S$ and a vector $v \in T_{p} S$ with unit norm, show that there exist $\varepsilon>0$ and a unique curve $\gamma:(-\varepsilon, \varepsilon) \rightarrow S$ parametrized by arc-length and with constant geodesic curvature $\lambda$ such that $\gamma(0)=p$ and $\dot{\gamma}(0)=v$.

  [You may use the theorem on existence and uniqueness of solutions of ordinary differential equations.]

  (b) Let $S$ be an oriented surface with positive Gaussian curvature and diffeomorphic to $S^{2}$. Show that two simple closed geodesics in $S$ must intersect. Is it true that two smooth simple closed curves in $S$ with constant geodesic curvature $\lambda \neq 0$ must intersect?

  comment

• 1.II $. 25 \mathrm{~J} \quad$

  Probability and Measure

  Part II, 2006

  Let $\left(X_{n}\right)_{n \in \mathbb{N}}$ be a sequence of (real-valued, Borel-measurable) random variables on the probability space $(\Omega, \mathcal{A}, \mathbb{P})$.

  (a) Let $\left(A_{n}\right)_{n \in \mathbb{N}}$ be a sequence of events in $\mathcal{A}$.

  What does it mean for the events $\left(A_{n}\right)_{n \in \mathbb{N}}$ to be independent?

  What does it mean for the random variables $\left(X_{n}\right)_{n \in \mathbb{N}}$ to be independent?

  (b) Define the tail $\sigma$-algebra $\mathcal{T}$ for a sequence $\left(X_{n}\right)_{n \in \mathbb{N}}$ and state Kolmogorov's $0-1$ law.

  (c) Consider the following events in $\mathcal{A}$,

  $$\begin{gathered} \left\{X_{n} \leqslant 0 \text { eventually }\right\} \\ \left\{\lim _{n \rightarrow \infty} X_{1}+\ldots+X_{n} \text { exists }\right\} \\ \left\{X_{1}+\ldots+X_{n} \leqslant 0 \text { infinitely often }\right\} \end{gathered}$$

  Which of them are tail events for $\left(X_{n}\right)_{n \in \mathbb{N}}$ ? Justify your answers.

  (d) Let $\left(X_{n}\right)_{n \in \mathbb{N}}$ be independent random variables with

  $$\mathbb{P}\left(X_{n}=0\right)=\mathbb{P}\left(X_{n}=1\right)=\frac{1}{2} \quad \text { for all } n \in \mathbb{N},$$

  and define $U_{n}=X_{1} X_{2}+X_{2} X_{3}+\ldots+X_{2 n} X_{2 n+1}$.

  Show that $U_{n} / n \rightarrow c$ a.s. for some $c \in \mathbb{R}$, and determine $c$.

  [Standard results may be used without proof, but should be clearly stated.]

  comment

• 2.II $. 25 \mathrm{~J} \quad$

  Probability and Measure

  Part II, 2006

  (a) What is meant by saying that $(\Omega, \mathcal{A}, \mu)$ is a measure space? Your answer should include clear definitions of any terms used.

  (b) Consider the following sequence of Borel-measurable functions on the measure space $(\mathbb{R}, \mathcal{L}, \lambda)$, with the Lebesgue $\sigma$-algebra $\mathcal{L}$ and Lebesgue measure $\lambda$ :

  $$f_{n}(x)=\left\{\begin{array}{ll} 1 / n & \text { if } 0 \leqslant x \leqslant e^{n} ; \\ 0 & \text { otherwise } \end{array} \quad \text { for } n \in \mathbb{N}\right.$$

  For each $p \in[1, \infty]$, decide whether the sequence $\left(f_{n}\right)_{n \in \mathbb{N}}$ converges in $L^{p}$ as $n \rightarrow \infty$.

  Does $\left(f_{n}\right)_{n \in \mathbb{N}}$ converge almost everywhere?

  Does $\left(f_{n}\right)_{n \in \mathbb{N}}$ converge in measure?

  Justify your answers.

  For parts (c) and (d), let $\left(f_{n}\right)_{n \in \mathbb{N}}$ be a sequence of real-valued, Borel-measurable functions on a probability space $(\Omega, \mathcal{A}, \mu)$.

  (c) Prove that $\left\{x \in \Omega: f_{n}(x)\right.$ converges to a finite limit $\} \in \mathcal{A}$.

  (d) Show that $f_{n} \rightarrow 0$ almost surely if and only if $\sup _{m \geqslant n}\left|f_{m}\right| \rightarrow 0$ in probability.

  comment

• $3 . \mathrm{II} . 24 \mathrm{~J} \quad$

  Probability and Measure

  Part II, 2006

  Let $X$ be a real-valued random variable. Define the characteristic function $\phi_{X}$. Show that $\phi_{X}(u) \in \mathbb{R}$ for all $u \in \mathbb{R}$ if and only if $X$ and $-X$ have the same distribution.

  For parts (a) and (b) below, let $X$ and $Y$ be independent and identically distributed random variables.

  (a) Show that $X=Y$ almost surely implies that $X$ is almost surely constant.

  (b) Suppose that there exists $\varepsilon>0$ such that $\left|\phi_{X}(u)\right|=1$ for all $|u|<\varepsilon$. Calculate $\phi_{X-Y}$ to show that $\mathbb{E}(1-\cos (u(X-Y)))=0$ for all $|u|<\varepsilon$, and conclude that $X$ is almost surely constant.

  (c) Let $X, Y$, and $Z$ be independent $\mathrm{N}(0,1)$ random variables. Calculate the characteristic function of $\eta=X Y-Z$, given that $\phi_{X}(u)=e^{-u^{2} / 2}$.

  comment

• 4.II $. 25 \mathrm{~J} \quad$

  Probability and Measure

  Part II, 2006

  Let $(\Omega, \mathcal{A}, \mu)$ be a measure space and $f: \Omega \rightarrow \mathbb{R}$ a measurable function.

  (a) Explain what is meant by saying that $f$ is integrable, and how the integral $\int_{\Omega} f d \mu$ is defined, starting with integrals of $\mathcal{A}$-simple functions.

  [Your answer should consist of clear definitions, including the ones for $\mathcal{A}$-simple functions and their integrals.]

  (b) For $f: \Omega \rightarrow[0, \infty)$ give a specific sequence $\left(g_{n}\right)_{n \in \mathbb{N}}$ of $\mathcal{A}$-simple functions such that $0 \leqslant g_{n} \leqslant f$ and $g_{n}(x) \rightarrow f(x)$ for all $x \in \Omega$. Justify your answer.

  (c) Suppose that that $\mu(\Omega)<\infty$ and let $f_{1}, f_{2}, \ldots: \Omega \rightarrow \mathbb{R}$ be measurable functions such that $f_{n}(x) \rightarrow 0$ for all $x \in \Omega$. Prove that, if

  $$\lim _{c \rightarrow \infty} \sup _{n \in \mathbb{N}} \int_{\left|f_{n}\right|>c}\left|f_{n}\right| d \mu=0$$

  then $\int_{\Omega} f_{n} d \mu \rightarrow 0$.

  Give an example with $\mu(\Omega)<\infty$ such that $f_{n}(x) \rightarrow 0$ for all $x \in \Omega$, but $\int_{\Omega} f_{n} d \mu \nrightarrow 0$, and justify your answer.

  (d) State and prove Fatou's Lemma for a sequence of non-negative measurable functions.

  [Standard results on measurability and integration may be used without proof.]

  comment

• 1.II.26J

  Applied Probability

  Part II, 2006

  (a) What is a $Q$-matrix? What is the relationship between the transition matrix $P(t)$ of a continuous time Markov process and its generator $Q$ ?

  (b) A pond has three lily pads, labelled 1, 2, and 3. The pond is also the home of a frog that hops from pad to pad in a random fashion. The position of the frog is a continuous time Markov process on $\{1,2,3\}$ with generator

  $$Q=\left(\begin{array}{ccc} -1 & 1 & 0 \\ 1 & -2 & 1 \\ 1 & 0 & -1 \end{array}\right)$$

  Sketch an arrow diagram corresponding to $Q$ and determine the communicating classes. Find the probability that the frog is on pad 2 in equilibrium. Find the probability that the frog is on pad 2 at time $t$ given that the frog is on pad 1 at time 0 .

  comment