MATHEMATICAL TRIPOS Part II

Thursday, 6 June, 2019 9:00 am to 12:00 pm MAT2

PAPER 3

Before you begin read these instructions carefully.

The examination paper is divided into two sections. Each question in Section II
carries twice the number of marks of each question in Section I. Section II questions
also carry an alpha or beta quality mark and Section I questions carry a beta quality
mark.
Candidates may obtain credit from attempts on at most six questions from Section
I and from any number of questions from Section II.
Write on one side of the paper only and begin each answer on a separate sheet.
Write legibly; otherwise you place yourself at a grave disadvantage.

At the end of the examination:

Tie up your answers in bundles, marked A, B, C, . . ., J according to the code letter
affixed to each question. Include in the same bundle all questions from Sections I
and II with the same code letter.
Attach a completed gold cover sheet to each bundle.
You must also complete a green master cover sheet listing all the questions you have
attempted.
Every cover sheet must bear your examination number and desk number.

STATIONERY REQUIREMENTS
Gold cover sheet
Green master cover sheet
Script paper
Rough paper

You may not start to read the questions

printed on the subsequent pages until
instructed to do so by the Invigilator.
 2

SECTION I
1I Number Theory
Let f = (a, b, c) be a positive definite binary quadratic form with integer coefficients.
What does it meanpto say that f is reduced? Show that if f is reduced and has discriminant
d, then |b| 6 a 6 |d| /3 and b ≡ d (mod 2). Deduce that for fixed d < 0, there are only
finitely many reduced f of discriminant d.
Find all reduced positive definite binary quadratic forms of discriminant −15.

2H Topics in Analysis
State Nash’s theorem for a non zero-sum game in the case of two players with two
choices.
The role playing game Tixerb involves two players. Before the game begins, each
player i chooses a pi with 0 6 pi 6 1 which they announce. They may change their choice
as many times as they wish, but, once the game begins, no further changes are allowed.
When the game starts, player i becomes a Dark Lord with probability pi and a harmless
peasant with probability 1 − pi . If one player is a Dark Lord and the other a peasant the
Lord gets 2 points and the peasant −2. If both are peasants they get 1 point each, if both
Lords they get −U each. Show that there exists a U0 , to be found, such that, if U > U0
there will be three choices of (p1 , p2 ) for which neither player can increase the expected
value of their outcome by changing their choice unilaterally, but, if U0 > U , there will
only be one. Find the appropriate (p1 , p2 ) in each case.

3G Coding and Cryptography

What does it mean to transmit reliably at rate R through a binary symmetric
channel (BSC) with error probability p?
Assuming Shannon’s second coding theorem (also known as Shannon’s noisy coding
theorem), compute the supremum of all possible reliable transmission rates of a BSC.
Describe qualitatively the behaviour of the capacity as p varies. Your answer should
address the following cases,

(i) p is small,

(ii) p = 1/2,

(iii) p > 1/2.

Part II, Paper 3

 3

4H Automata and Formal Languages

(a) Define what it means for a context-free grammar (CFG) to be in Chomsky
normal form (CNF). Can a CFG in CNF ever define a language containing ǫ? If GChom
denotes the result of converting an arbitrary CFG G into one in CNF, state the relationship
between L(G) and L(GChom ).
(b) Let G be a CFG in CNF. Give an algorithm that, on input of any word v on
the terminals of G, decides if v ∈ L(G) or not. Explain why your algorithm works.
(c) Convert the following CFG G into a grammar in CNF:

S → Sbb | aS | T

T → cc
Does L(G) = L(GChom ) in this case? Justify your answer.

5J Statistical Modelling
(a) For a given model with likelihood L(β), β ∈ Rp , define the Fisher information
matrix in terms of the Hessian of the log-likelihood.
Consider a generalised linear model with design matrix X ∈ Rn×p , output variables
y ∈ Rn , a bijective link function, mean parameters µ = (µ1 , . . . , µn ) and dispersion
parameters σ12 = . . . = σn2 = σ 2 . Assume σ 2 is known.
(b) State the form of the log-likelihood.
(c) For the canonical link, show that when the parameter σ 2 is known, the Fisher
information matrix is equal to
σ −2 X T W X,
for a diagonal matrix W depending on the means µ. Identify W .

Part II, Paper 3 [TURN OVER]

 4

6C Mathematical Biology
A model of wound healing in one spatial dimension is given by

∂S ∂2S
= rS(1 − S) + D ,
∂t ∂x2
where S(x, t) gives the density of healthy tissue at spatial position x at time t and r and
D are positive constants.
By setting S(x, t) = f (ξ) where ξ = x − ct, seek a steady travelling wave solution
where f (ξ) tends to one for large negative ξ and tends to zero for large positive ξ. By
linearising around the leading edge, where f ≈ 1, find the possible wave speeds c of the
system. Assuming that the full nonlinear system will settle to the slowest possible speed,
express the wave speed as a function of D and r.
Consider now a situation where the tissue is destroyed in some window of length
W , i.e. S(x, 0) = 0 for 0 < x < W for some constant W > 0 and S(x, 0) is equal to one
elsewhere. Explain what will happen for subsequent times, illustrating your answer with
sketches of S(x, t). Determine approximately how long it will take for this wound to heal (in
the sense that S is close to one everywhere).

7A Further Complex Methods

The equation
zw′′ + w = 0
has solutions of the form
Z
w(z) = ezt f (t)dt,
γ

for suitably chosen contours γ and some suitable function f (t).

(a) Find f (t) and determine the required condition on γ, which you should express
in terms of z and t.
(b) Use the result of part (a) to specify a possible contour with the help of a clearly
labelled diagram.

Part II, Paper 3

 5

8E Classical Dynamics
A simple harmonic oscillator of mass m and spring constant k has the equation of
motion
mẍ = −kx .

(a) Describe the orbits of the system in phase space. State how the action I of
the oscillator is related to a geometrical property of the orbits in phase space. Derive
the action–angle variables (θ, I) and give the form of the Hamiltonian of the oscillator in
action–angle variables.
(b) Suppose now that the spring constant k varies in time. Under what conditions
does the theory of adiabatic invariance apply? Assuming that these conditions hold,
identify an adiabatic invariant and determine how the energy and amplitude of the
oscillator vary with k in this approximation.

9B Cosmology
Consider a spherically symmetric distribution of mass with density ρ(r) at distance
r from the centre. Derive the pressure support equation that the pressure P (r) has to
satisfy for the system to be in static equilibrium.
Assume now that the mass density obeys ρ(r) = Ar 2 P (r), for some positive constant
A. Determine whether or not the system has a stable solution corresponding to a star of
finite radius.

Part II, Paper 3 [TURN OVER]

 6

10D Quantum Information and Computation

Let Bn denote the set of all n-bit strings and write N = 2n . Let I denote the
identity operator on n qubits and for G = {x1 , x2 , . . . , xk } ⊂ Bn introduce the n-qubit
operator
Q = −Hn I0 Hn IG
where Hn = H ⊗ . . . ⊗ H is the Hadamard operation on each of the n qubits, and I0 and
IG are given by
X
I0 = I − 2 |00 . . . 0i h00 . . . 0| IG = I − 2 |xi hx| .
x∈G

Also introduce the states

1 X 1 X 1 X
|ψ0 i = √ |xi |ψG i = √ |xi |ψB i = √ |xi .
N x∈Bn k x∈G N − k x∈G
/

Let P denote the real span of |ψ0 i and |ψG i.

(a) Show that Q maps P to itself, and derive a geometrical interpretation of the
action of Q on P, stating clearly any results from Euclidean geometry that you use.
(b) Let f : Bn → B1 be the Boolean function such that f (x) = 1 iff x ∈ G. Suppose
that k = N/4. Show that we can obtain an x ∈ G with certainty by using just one
application of the standard quantum oracle Uf for f (together with other operations that
are independent of f ).

Part II, Paper 3

 7

SECTION II
11I Number Theory
Let p > 2 be a prime.
(a) What does it mean to say that an integer g is a primitive root mod p?
(b) Let k be an integer with 0 6 k < p − 1. Let
p−1
X
Sk = xk .
x=0

Show that Sk ≡ 0 (mod p). [Recall that by convention 00 = 1.]

(c) Let f (X, Y, Z) = aX 2 + bY 2 + cZ 2 for some a, b, c ∈ Z, and let g = 1 − f p−1 .
Show that for any x, y, z ∈ Z, g(x, y, z) ≡ 0 or 1 (mod p), and that
X
g(x, y, z) ≡ 0 (mod p).
x,y,z∈{0,1,...,p−1}

Hence show that there exist integers x, y, z, not all divisible by p, such that f (x, y, z) ≡ 0
(mod p).

12H Automata and Formal Languages

(a) State the s-m-n theorem and the recursion theorem.
(b) State and prove Rice’s theorem.
(c) Show that if g : N20 → N0 is partial recursive, then there is some e ∈ N0 such
that
fe,1 (y) = g(e, y) ∀y ∈ N0 .

(d) Show there exists some m ∈ N0 such that Wm has exactly m2 elements.
(e) Given n ∈ N0 , is it possible to compute whether or not the number of elements
of Wn is a (finite) perfect square? Justify your answer.
[In this question N0 denotes the set of non-negative integers. Any use of Church’s thesis
in your answers should be explicitly stated.]

Part II, Paper 3 [TURN OVER]

 8

13C Mathematical Biology

(a) A stochastic birth-death process has a master equation given by

dpn
= λ(pn−1 − pn ) + β [(n + 1)pn+1 − npn ] ,
dt
where pn (t) is the probability that there are n individuals in the population at time t for
n = 0, 1, 2, . . . and pn = 0 for n < 0.

(i) Give a brief interpretation of λ and β.

∂φ
(ii) Derive an equation for ∂t , where φ is the generating function
∞
X
φ(s, t) = sn pn (t).
n=0

(iii) Assuming that the generating function φ takes the form

φ(s, t) = e(s−1) f (t) ,

find f (t) and hence show that, as t → ∞, both the mean hni and variance σ 2
of the population size tend to constant values, which you should determine.

(b) Now suppose an extra process is included: k individuals are added to the
population at rate ǫ(n).

(i) Write down the new master equation, and explain why, for k > 1, the approach
used in part (a) will fail.

(ii) By working with the master equation directly, find a differential equation for
the rate of change of the mean population size hni.

(iii) Now take ǫ(n) = an + b for positive constants a and b. Show that for β > ak
the mean population size tends to a constant, which you should determine.
Briefly describe what happens for β < ak.

Part II, Paper 3

 9

14B Cosmology
[You may work in units of the speed of light, so that c = 1.]
Consider the process where protons and electrons combine to form neutral hydrogen
atoms;

p+ + e− ↔ H 0 + γ.

Let np , ne and nH denote the number densities for protons, electrons and hydrogen atoms
respectively. The ionization energy of hydrogen is denoted I. State and derive Saha’s
equation for the ratio ne np /nH , clearly describing the steps required.
[You may use without proof the following formula for the equilibrium number density
of a non-relativistic species a with ga degenerate states of mass m at temperature T such
that kB T ≪ m,
 3/2
2πmkB T
na = ga exp ([µ − m] /kB T ) ,
h2

where µ is the chemical potential and kB and h are the Boltzmann and Planck constants
respectively.]
The photon number density nγ is given as

16π
nγ = ζ(3) (kB T )3 ,
h3
where ζ(3) ≃ 1.20. Consider now the fractional ionization Xe = ne /(ne + nH ). In our
universe ne + nH = np + nH ≃ ηnγ where η is the baryon-to-photon number ratio. Find
an expression for the ratio

(1 − Xe )
Xe2

in terms of kB T , η, I and the particle masses. One might expect neutral hydrogen to form
at a temperature given by kB T ∼ I ∼ 13 eV, but instead in our universe it forms at the
much lower temperature kB T ∼ 0.3 eV. Briefly explain why this happens. Estimate the
temperature at which neutral hydrogen would form in a hypothetical universe with η = 1.
Briefly explain your answer.

Part II, Paper 3 [TURN OVER]

 10

15D Quantum Information and Computation

Let Hd denote a d-dimensional state space with orthonormal basis {|yi : y ∈ Zd }.
For any f : Zm → Zn let Uf be the operator on Hm ⊗ Hn defined by

Uf |xi |yi = |xi |y + f (x) mod ni

for all x ∈ Zm and y ∈ Zn .

(a) Define QF T , the quantum Fourier transform mod d (for any chosen d).
(b) Let S on Hd (for any chosen d) denote the operator defined by

S |yi = |y + 1 mod di

for y ∈ Zd . Show that the Fourier basis states |ξx i = QF T |xi for x ∈ Zd are eigenstates
of S. By expressing Uf in terms of S find a basis of eigenstates of Uf and determine the
corresponding eigenvalues.
(c) Consider the following oracle promise problem:
Input: an oracle for a function f : Z3 → Z3 .
Promise: f has the form f (x) = sx + t where s and t are unknown coefficients (and with
all arithmetic being mod 3).
Problem: Determine s with certainty.
Can this problem be solved by a single query to a classical oracle for f (and possible
further processing independent of f )? Give a reason for your answer.
Using the results of part (b) or otherwise, give a quantum algorithm for this problem
that makes just one query to the quantum oracle Uf for f .
(d) For any f : Z3 → Z3 , let f1 (x) = f (x + 1) and f2 (x) = −f (x) (all arithmetic
being mod 3). Show how Uf1 and Uf2 can each be implemented with one use of Uf together
with other unitary gates that are independent of f .
(e) Consider now the oracle problem of the form in part (c) except that now f is a
quadratic function f (x) = ax2 + bx + c with unknown coefficients a, b, c (and all arithmetic
being mod 3), and the problem is to determine the coefficient a with certainty. Using the
results of part (d) or otherwise, give a quantum algorithm for this problem that makes
just two queries to the quantum oracle for f .

Part II, Paper 3

 11

16I Logic and Set Theory

Define the von Neumann hierarchy of sets Vα . Show that each Vα is transitive, and
explain why Vα ⊂ Vβ whenever α 6 β. Prove that every set x is a member of some Vα .
Which of the following are true and which are false? Give proofs or counterexamples
as appropriate. [You may assume standard properties of rank.]

(i) If the rank of a set x is a (non-zero) limit then x is infinite.

(ii) If the rank of a set x is countable then x is countable.

(iii) If every finite subset of a set x has rank at most α then x has rank at most α.

(iv) For every ordinal α there exists a set of rank α.

17G Graph Theory

(a) What does it mean to say that a graph is bipartite?
(b) Show that G is bipartite if and only if it contains no cycles of odd length.
(c) Show that if G is bipartite then

ex (n; G)
n
→ 0
2

as n → ∞.
[You may use without proof the Erdős–Stone theorem provided it is stated precisely.]
(d) Let G be a graph of order n with m edges. Let U be a random subset of V (G)
containing each vertex of G independently with probability 12 . Let X be the number of
edges with precisely one vertex in U . Find, with justification, E(X), and deduce that G
contains a bipartite subgraph with at least m
2 edges.
By using another method of choosing a random subset of V (G), or otherwise, show
mn
that if n is even then G contains a bipartite subgraph with at least 2(n−1) edges.

Part II, Paper 3 [TURN OVER]

 12

18F Galois Theory

Let k be a field. For m a positive integer, consider X m − 1 ∈ k[X], where either
char k = 0, or char k = p with p not dividing m; explain why the polynomial has distinct
roots in a splitting field.
For m a positive integer, define the mth cyclotomic polynomial Φm ∈ C[X] and
show that it is a monic polynomial in Z[X]. Prove that Φm is irreducible over Q for all m.
[Hint: If Φm = f g, with f, g ∈ Z[X] and f monic irreducible with 0 < deg f < deg Φm ,
and ε is a root of f , show first that εp is a root of f for any prime p not dividing m.]
Let F = X 8 + X 7 − X 5 − X 4 − X 3 + X + 1 ∈ Z[X]; by considering the product
(X 2 − X + 1)F , or otherwise, show that F is irreducible over Q.

19I Representation Theory

In this question all representations are complex and G is a finite group.
(a) State and prove Mackey’s theorem. State the Frobenius reciprocity theorem.
(b) Let X be a finite G-set and let CX be the corresponding permutation represen-
tation. Pick any orbit of G on X: it is isomorphic as a G-set to G/H for some subgroup
H of G. Write down the character of C(G/H).

(i) Let CG be the trivial representation of G. Show that CX may be written as

a direct sum
CX = CG ⊕ V
for some representation V .

(ii) Using the results of (a) compute the character inner product h1H ↑G , 1H ↑G iG
in terms of the number of (H, H) double cosets.

(iii) Now suppose that |X| > 2, so that V 6= 0. By writing C(G/H) as a direct
sum of irreducible representations, deduce from (ii) that the representation V
is irreducible if and only if G acts 2-transitively. In that case, show that V is
not the trivial representation.

Part II, Paper 3

 13

20F Algebraic Topology

Let K be a simplicial complex, and L a subcomplex. As usual, Ck (K) denotes the
group of k-chains of K, and Ck (L) denotes the group of k-chains of L.
(a) Let
Ck (K, L) = Ck (K)/Ck (L)
for each integer k. Prove that the boundary map of K descends to give C• (K, L) the
structure of a chain complex.
(b) The homology groups of K relative to L, denoted by Hk (K, L), are defined to
be the homology groups of the chain complex C• (K, L). Prove that there is a long exact
sequence that relates the homology groups of K relative to L to the homology groups of
K and the homology groups of L.
(c) Let Dn be the closed n-dimensional disc, and S n−1 be the (n − 1)-dimensional
sphere. Exhibit simplicial complexes Kn and subcomplexes Ln−1 such that Dn ∼ = |Kn | in
such a way that |Ln−1 | is identified with S n−1 .
(d) Compute the relative homology groups Hk (Kn , Ln−1 ), for all integers k > 0 and
n > 2 where Kn and Ln−1 are as in (c).

21H Linear Analysis

(a) Let X be a Banach space and consider the open unit ball B = {x ∈ X : kxk < 1}.
Let T : X → X be a bounded operator. Prove that T (B) ⊃ B implies T (B) ⊃ B.
(b) Let P be the vector space of all polynomials in one variable with real coefficients.
Let k · k be any norm on P . Show that (P, k · k) is not complete.
(c) Let f : C → C be entire, and assume that for every z ∈ C there is n such that
f (n) (z)= 0 where f (n) is the n-th derivative of f . Prove that f is a polynomial.
[You may use that an entire function vanishing on an open subset of C must vanish
everywhere.]
(d) A Banach space X is said to be uniformly convex if for every ε ∈ (0, 2] there
is δ > 0 such that for all x, y ∈ X such that kxk = kyk = 1 and kx − yk > ε, one has
k(x + y)/2k 6 1 − δ. Prove that ℓ2 is uniformly convex.

Part II, Paper 3 [TURN OVER]

 14

22H Analysis of Functions

(a) Prove that in a finite-dimensional normed vector space the weak and strong
topologies coincide.
(b) Prove that in a normed vector space X, a weakly convergent sequence is
bounded. [Any form of the Banach–Steinhaus theorem may be used, as long as you
state it clearly.]
(c) Let ℓ1 be the space of real-valued absolutely summable sequences. Suppose (ak )
is a weakly convergent sequence in ℓ1 which does not converge strongly. Show there is a
constant ε > 0 and a sequence (xk ) in ℓ1 which satisfies xk ⇀ 0 and kxk kℓ1 > ε for all
k > 1.
With (xk ) as above, show there is some y ∈ ℓ∞ and a subsequence (xkn ) of (xk ) with
> ε/3 for all n. Deduce that every weakly convergent sequence in ℓ1 is strongly
hxkn , yi
convergent.
[Hint: Define y so that yi = sign xki n for bn−1 < i 6 bn , where the sequence of
integers bn should be defined inductively along with xkn .]
(d) Is the conclusion of part (c) still true if we replace ℓ1 by L1 ([0, 2π])?

23F Riemann Surfaces

Let Λ be a lattice in C, and f : C/Λ → C/Λ a holomorphic map of complex tori.
Show that f lifts to a linear map F : C → C.
Give the definition of ℘(z) := ℘Λ (z), the Weierstrass ℘-function for Λ. Show that
there exist constants g2 , g3 such that

℘′ (z)2 = 4℘(z)3 − g2 ℘(z) − g3 .

Suppose f ∈ Aut(C/Λ), that is, f : C/Λ → C/Λ is a biholomorphic group

homomorphism. Prove that there exists a lift F (z) = ζz of f , where ζ is a root of
unity for which there exist m, n ∈ Z such that ζ 2 + mζ + n = 0.

Part II, Paper 3

 15

24F Algebraic Geometry

Let W ⊆ A2 be the curve defined by the equation y 3 = x4 + 1 over the complex
numbers C, and let X ⊆ P2 be its closure.
(a) Show X is smooth.
(b) Determine the ramification points of the map X → P1 defined by

(x : y : z) 7→ (x : z).

Using this, determine the Euler characteristic and genus of X, stating clearly any theorems
that you are using.
dx
(c) Let ω = y2
∈ KX . Compute νp (ω) for all p ∈ X, and determine a basis for
L(KX ).

25H Differential Geometry

(a) Let α : (a, b) → R2 be a regular curve without self intersection given by
α(v) = (f (v), g(v)) with f (v) > 0 for v ∈ (a, b).
Consider the local parametrisation given by

φ : (0, 2π) × (a, b) → R3 ,

where φ(u, v) = (f (v) cos u, f (v) sin u, g(v)).

(i) Show that the image φ((0, 2π) × (a, b)) defines a regular surface S in R3 .

(ii) If γ(s) = φ(u(s), v(s)) is a geodesic in S parametrised by arc length, then show
that f (v(s))2 u′ (s) is constant in s. If θ(s) denotes the angle that the geodesic
makes with the parallel S ∩ {z = g(v(s))}, then show that f (v(s)) cos θ(s) is
constant in s.

(b) Now assume that α(v) = (f (v), g(v)) extends to a smooth curve α : [a, b] → R2
such that f (a) = 0, f (b) = 0, f ′ (a) 6= 0, f ′ (b) 6= 0. Let S be the closure of S in R3 .

(i) State a necessary and sufficient condition on α(v) for S to be a compact regular
surface. Justify your answer.

(ii) If S is a compact regular surface, and γ : (−∞, ∞) → S is a geodesic, show that

there exists a non-empty open subset U ⊂ S such that γ((−∞, ∞)) ∩ U = ∅.

Part II, Paper 3 [TURN OVER]

 16

26K Probability and Measure

(a) Let X and Y be real random variables such that E[f (X)] = E[f (Y )] for every
compactly supported continuous function f . Show that X and Y have the same law.
(b) Given a real random variable Z, let ϕZ (s) = E(eisZ ) be its characteristic
function. Prove the identity
ZZ Z
−isx
g(εs)f (x)e ϕZ (s)ds dx = ĝ(t) E[f (Z − εt)]dt

for real ε > 0, where is f is continuous and compactly supported, and where g is a Lebesgue
integrable function such that ĝ is also Lebesgue integrable, where
Z
ĝ(t) = g(x)eitx dx

is its Fourier transform. Use the above identity to derive a formula for E[f (Z)] in terms
of ϕZ , and recover the fact that ϕZ determines the law of Z uniquely.
(c) Let X and Y be bounded random variables such that E(X n ) = E(Y n ) for every
positive integer n. Show that X and Y have the same law.
(d) The Laplace transform ψZ (s) of a non-negative random variable Z is defined by
the formula
ψZ (s) = E(e−sZ )
for s > 0. Let X and Y be (possibly unbounded) non-negative random variables such that
ψX (s) = ψY (s) for all s > 0. Show that X and Y have the same law.
(e) Let
1 k −x
f (x; k) = 1{x>0} x e
k!
where k is a non-negative integer and 1{x>0} is the indicator function of the interval
(0, +∞).
Given non-negative integers k1 , . . . , kn , suppose that the random variables X1 , . . . , Xn
are independent with Xi having density function f (·; ki ). Find the density of the random
variable X1 +· · ·+Xn .

Part II, Paper 3

 17

27K Applied Probability

(a) What does it mean to say that a continuous-time Markov chain X = (Xt : 0 6
t 6 T ) with state space S is reversible in equilibrium? State the detailed balance equations,
and show that any probability distribution on S satisfying them is invariant for the chain.
(b) Customers arrive in a shop in the manner of a Poisson process with rate λ > 0.
There are s servers, and capacity for up to N people waiting for service. Any customer
arriving when the shop is full (in that the total number of customers present is N +s) is not
admitted and never returns. Service times are exponentially distributed with parameter
µ > 0, and they are independent of one another and of the arrivals process. Describe the
number Xt of customers in the shop at time t as a Markov chain.
Calculate the invariant distribution π of X = (Xt : t > 0), and explain why π is the
unique invariant distribution. Show that X is reversible in equilibrium.
[Any general result from the course may be used without proof, but must be stated
clearly.]

28J Principles of Statistics

We consider the exponential model {f (·, θ) : θ ∈ (0, ∞)}, where

f (x, θ) = θe−θx for x > 0 .

We observe an i.i.d. sample X1 , . . . , Xn from the model.

(a) Compute the maximum likelihood estimator θ̂M LE for θ. What is the limit in
√
distribution of n(θ̂M LE − θ)?
(b) Consider the Bayesian setting and place a Gamma(α, β), α, β > 0, prior for θ
with density
β α α−1
π(θ) = θ exp(−βθ) for θ > 0 ,
Γ(α)
where Γ is the Gamma function satisfying Γ(α + 1) = αΓ(α) for all α > 0. What is the
posterior distribution for θ? What is the Bayes estimator θ̂π for the squared loss?
(c) Show that the Bayes estimator is consistent. What is the limiting distribution
√
of n(θ̂π − θ)?
[You may use results from the course, provided you state them clearly.]

Part II, Paper 3 [TURN OVER]

 18

29K Stochastic Financial Models

In the Black–Scholes model the price π(C) at time 0 for a European option of the
form C = f (ST ) with maturity T > 0 is given by

−rT
Z ∞  √
 1 2
π(C) = e f S0 exp σ T y + (r − 21 σ 2 )T √ e−y /2 dy.
−∞ 2π

(a) Find the price at time 0 of a European call option with maturity T > 0 and
strike price K > 0 in terms of the standard normal distribution function. Derive the
put-call parity to find the price of the corresponding European put option.
(b) The digital call option with maturity T > 0 and strike price K > 0 has payoff
given by
(
1 if ST > K,
CdigCall =
0 otherwise.

What is the value of the option at any time t ∈ [0, T ]? Determine the number of units of
the risky asset that are held in the hedging strategy at time t.
(c) The digital put option with maturity T > 0 and strike price K > 0 has payoff
(
1 if ST < K,
CdigPut =
0 otherwise.

Find the put-call parity for digital options and deduce the Black–Scholes price at time 0
for a digital put.

Part II, Paper 3

 19

30A Asymptotic Methods

(a) State Watson’s lemma for the case when all the functions and variables involved
are real, and use it to calculate the asymptotic approximation as x → ∞ for the integral
I, where Z ∞
I= e−xt sin(t2 ) dt.
0

(b) The Bessel function Jν (z) of the first kind of order ν has integral representation

1  z ν Z 1
Jν (z) = √ eizt (1 − t2 )ν−1/2 dt ,
Γ(ν + 21 ) π 2 −1

where Γ is the Gamma function, Re(ν) > 1/2 and z is in general a complex variable. The
complex version of Watson’s lemma is obtained by replacing x with the complex variable
z, and is valid for |z| → ∞ and |arg(z)| 6 π/2−δ < π/2, for some δ such that 0 < δ < π/2.
Use this version to derive an asymptotic expansion for Jν (z) as |z| → ∞ . For what values
of arg(z) is this approximation valid?
[Hint: You may find the substitution t = 2τ − 1 useful. ]

31E Dynamical Systems

Consider a dynamical system of the form

ẋ = x(1 − y + ax) ,
ẏ = ry(−1 + x − by) ,

on Λ = {(x, y) : x > 0 and y > 0}, where a, b and r are real constants and r > 0.
(a) For a = b = 0, by considering a function of the form V (x, y) = f (x) + g(y), show
that all trajectories in Λ are either periodic orbits or a fixed point.
(b) Using the same V , show that no periodic orbits in Λ persist for small a and b if
ab < 0 .
RT
[Hint: for a = b = 0 on the periodic orbits with period T , show that 0 (1 − x)dt = 0
RT RT 
and hence that 0 x(1 − x)dt = 0 −(1 − x)2 + (1 − x) dt < 0.]


(c) By considering Dulac’s criterion with φ = 1/(xy), show that there are no periodic
orbits in Λ if ab < 0.
(d) Purely by consideration of the existence of fixed points in Λ and their Poincaré
indices, determine those (a, b) for which the possibility of periodic orbits can be excluded.
(e) Combining the results above, sketch the a-b plane showing where periodic orbits
in Λ might still be possible.

Part II, Paper 3 [TURN OVER]

 20

32C Integrable Systems

Suppose ψ s : (x, u) 7→ (x̃, ũ) is a smooth one-parameter group of transformations
acting on R2 , with infinitesimal generator
∂ ∂
V = ξ(x, u) + η(x, u) .
∂x ∂u

(a) Define the nth prolongation Pr(n) V of V , and show that

n
(n)
X ∂
Pr V =V + ηi ,
i=1
∂u(i)

where you should give an explicit formula to determine the ηi recursively in terms of ξ
and η.
(b) Find the nth prolongation of each of the following generators:

∂ ∂ ∂
V1 = , V2 = x , V3 = x 2 .
∂x ∂x ∂x

(c) Given a smooth, real-valued, function u = u(x), the Schwarzian derivative is

defined by,
ux uxxx − 32 u2xx
S = S[u] := .
u2x
Show that,
Pr(3) Vi (S) = ci S,
for i = 1, 2, 3 where ci are real functions which you should determine. What can you
deduce about the symmetries of the equations:

(i) S[u] = 0,

(ii) S[u] = 1,
1
(iii) S[u] = x2
?

Part II, Paper 3

 21

33B Principles of Quantum Mechanics

Consider the Hamiltonian H = H0 + V , where V is a small perturbation. If
H0 |ni = En |ni, write down an expression for the eigenvalues of H, correct to second
order in the perturbation, assuming the energy levels of H0 are non-degenerate.
In a certain three-state system, H0 and V take the form

0 ǫ ǫ2
   
E1 0 0
H0 =  0 E2 0  and V = V0  ǫ 0 0  ,
0 0 E3 ǫ2 0 0

with V0 and ǫ real, positive constants and ǫ ≪ 1.

(a) Consider first the case E1 = E2 6= E3 and |ǫV0 /(E3 − E2 )| ≪ 1. Use the results
of degenerate perturbation theory to obtain the energy eigenvalues correct to order ǫ.
(b) Now consider the different case E3 = E2 6= E1 and |ǫV0 /(E2 − E1 )| ≪ 1. Use
the results of non-degenerate perturbation theory to obtain the energy eigenvalues correct
to order ǫ2 . Why is it not necessary to use degenerate perturbation theory in this case?
(c) Obtain the exact energy eigenvalues in case (b), and compare these to your
perturbative results by expanding to second order in ǫ.

Part II, Paper 3 [TURN OVER]

 22

34B Applications of Quantum Mechanics

A Hamiltonian H is invariant under the discrete translational symmetry of a Bravais
lattice Λ. This means that there exists a unitary translation operator Tr such that
[H, Tr ] = 0 for all r ∈ Λ. State and prove Bloch’s theorem for H.
Consider the two-dimensional Bravais lattice Λ defined by the basis vectors
a √ a √
a1 = ( 3, 1) , a2 = ( 3, −1) .
2 2
Find basis vectors b1 and b2 for the reciprocal lattice. Sketch the Brillouin zone. Explain
why the Brillouin zone has only two physically distinct corners. Show that the positions
of these corners may be taken to be K = 13 (2b1 + b2 ) and K′ = 31 (b1 + 2b2 ).
The dynamics of a single electron moving on the lattice Λ is described by a tight-
binding model with Hamiltonian
Xh  i
H= E0 |rihr| − λ |rihr + a1 | + |rihr + a2 | + |r + a1 ihr| + |r + a2 ihr| ,
r∈Λ

where E0 and λ are real parameters. What is the energy spectrum as a function of the
wave vector k in the Brillouin zone? How does the energy vary along the boundary of the
Brillouin zone between K and K′ ? What is the width of the band?
In a real material, each site of the lattice Λ contains an atom with a certain valency.
Explain how the conducting properties of the material depend on the valency.
Suppose now that there is a second band, with minimum E = E0 + ∆. For what
values of ∆ and the valency is the material an insulator?

35D Statistical Physics

What is meant by the chemical potential µ of a thermodynamic system? Derive
the Gibbs distribution for a system at temperature T and chemical potential µ (and fixed
volume) with variable particle number N .
Consider a non-interacting, two-dimensional gas of N fermionic particles in a region
of fixed area, at temperature T and chemical potential µ. Using the Gibbs distribution,
find the mean occupation number nF (ε) of a one-particle quantum state of energy ε. Show
that the density of states g(ε) is independent of ε and deduce that the mean number of
particles between energies ε and ε + dε is very well approximated for T ≪ εF by
N dε
(ε−ε )/T + 1
,
εF e F

where εF is the Fermi energy. Show that, for T small, the heat capacity of the gas has a
power-law dependence on T , and find the power.

Part II, Paper 3

 23

36E Electrodynamics
A time-dependent charge distribution ρ(t, x) localised in some region of size a near
the origin varies periodically in time with characteristic angular frequency ω. Explain
briefly the circumstances under which the dipole approximation for the fields sourced by
the charge distribution is valid.
Far from the origin, for r = |x| ≫ a, the vector potential A(t, x) sourced by the
charge distribution ρ(t, x) is given by the approximate expression

µ0
Z
d3 x′ J t − r/c, x′ ,


A(t, x) ≃
4πr

where J(t, x) is the corresponding current density. Show that, in the dipole approximation,
the large-distance behaviour of the magnetic field is given by,
µ0
B(t, x) ≃ − x̂ × p̈ (t − r/c) ,
4πrc
where p(t) is the electric dipole moment of the charge distribution. Assuming that, in the
same approximation, the corresponding electric field is given as E = −cx̂ × B, evaluate
the flux of energy through the surface element of a large sphere of radius R centred at the
origin. Hence show that the total power P (t) radiated by the charge distribution is given
by
µ0
P (t) = |p̈ (t − R/c)|2 .
6πc

A particle of charge q and mass m undergoes simple harmonic motion in the x-direction
with time period T = 2π/ω and amplitude A such that

x(t) = A sin (ωt) ix . (⋆)

Here ix is a unit vector in the x-direction. Calculate the total power P (t) radiated through
a large sphere centred at the origin in the dipole approximation and determine its time
averaged value,

1 T
Z
hP i = P (t) dt .
T 0

For what values of the parameters A and ω is the dipole approximation valid?
Now suppose that the energy of the particle with trajectory (⋆) is given by the usual
non-relativistic formula for a harmonic oscillator i.e. E = m|ẋ|2 /2 + mω 2 |x|2 /2, and that
the particle loses energy due to the emission of radiation at a rate corresponding to the
time-averaged power hP i. Work out the half-life of this system (i.e. the time t1/2 such
that E(t1/2 ) = E(0)/2). Explain why the non-relativistic approximation for the motion
of the particle is reliable as long as the dipole approximation is valid.

Part II, Paper 3 [TURN OVER]

 24

37D General Relativity

(a) Let M be a manifold with coordinates xµ . The commutator of two vector fields
V and W is defined as
[V , W ]α = V ν ∂ν W α − W ν ∂ν V α .

(i) Show that [V , W ] transforms like a vector field under a change of coordinates
from xµ to x̃µ .

(ii) Show that the commutator of any two basis vectors vanishes, i.e.
 
∂ ∂
, = 0.
∂xα ∂xβ

(iii) Show that if V and W are linear combinations (not necessarily with constant
coefficients) of n vector fields Z (a) , a = 1, . . . , n that all commute with one
another, then the commutator [V , W ] is a linear combination of the same n
fields Z (a) .

[You may use without proof the following relations which hold for any vector fields
V 1 , V 2 , V 3 and any function f :

[V 1 , V 2 ] = − [V 2 , V 1 ] , (1)
[V 1 , V 2 + V 3 ] = [V 1 , V 2 ] + [V 1 , V 3 ] , (2)
[V 1 , f V 2 ] = f [V 1 , V 2 ] + V 1 (f ) V 2 , (3)

but you should clearly indicate each time relation (1), (2), or (3) is used.]
(b) Consider the 2-dimensional manifold R2 with Cartesian coordinates (x1 , x2 ) =
(x, y) carrying the Euclidean metric gαβ = δαβ .

(i) Express the coordinate basis vectors ∂r and ∂θ , where r and θ denote the usual
polar coordinates, in terms of their Cartesian counterparts.

(ii) Define the unit vectors

∂r ∂θ
r̂ = , θ̂ =
||∂r || ||∂θ ||

and show that (r̂, θ̂) are not a coordinate basis, i.e. there exist no coordinates
z α such that r̂ = ∂/∂z 1 and θ̂ = ∂/∂z 2 .

Part II, Paper 3

 25

38A Fluid Dynamics

For a fluid with kinematic viscosity ν, the steady axisymmetric boundary-layer
equations for flow primarily in the z-direction are
 
∂w ∂w ν ∂ ∂w
u +w = r ,
∂r ∂z r ∂r ∂r
1 ∂(ru) ∂w
+ = 0,
r ∂r ∂z
where u is the fluid velocity in the r-direction and w is the fluid velocity in the z-direction.
A thin, steady, axisymmetric jet emerges from a point at the origin and flows along the
z-axis in a fluid which is at rest far from the z-axis.

(a) Show that the momentum flux

Z ∞
M := rw2 dr
0

is independent of the position z along the jet. Deduce that the thickness δ(z) of the jet
increases linearly with z. Determine the scaling dependence on z of the centre-line velocity
W (z). Hence show that the jet entrains fluid.

(b) A similarity solution for the streamfunction,

ψ(x, y, z) = νzg(η) with η := r/z,

exists if g satisfies the second order differential equation

ηg′′ − g′ + gg ′ = 0.

Using appropriate boundary and normalisation conditions (which you should state clearly)
to solve this equation, show that

12M η 2
g(η) = .
32ν 2 + 3M η 2

Part II, Paper 3 [TURN OVER]

 26

39A Waves
(a) Derive the wave equation for perturbation pressure for linearised sound waves
in a compressible gas.
(b) For a single plane wave show that the perturbation pressure and the velocity are
linearly proportional and find the constant of proportionality, i.e. the acoustic impedance.
(c) Gas occupies a tube lying parallel to the x-axis. In the regions x < 0 and x > L
the gas has uniform density ρ0 and sound speed c0 . For 0 < x < L the temperature of the
gas has been adjusted so that it has uniform density ρ1 and sound speed c1 . A harmonic
plane wave with frequency ω and unit amplitude is incident from x = −∞. If T is the (in
general complex) amplitude of the wave transmitted into x > L, show that

2 − 1
|T | = cos2 k1 L + 1 2
4 λ + λ−1 sin2 k1 L ,

where λ = ρ1 c1 /ρ0 c0 and k1 = ω/c1 . Discuss both of the limits λ ≪ 1 and λ ≫ 1.

40C Numerical Analysis

The diffusion equation

ut = uxx , 0 6 x 6 1, t > 0,

with the initial condition u(x, 0) = φ(x), 0 6 x 6 1, and boundary conditions u(0, t) =
u(1, t) = 0, is discretised by unm ≈ u(mh, nk) with k = ∆t, h = ∆x = 1/(1 + M ). The
Courant number is given by µ = k/h2 .
(a) The system is solved numerically by the method

un+1 = unm + µ unm−1 − 2unm + unm+1 ,

m m = 1, 2, ..., M, n > 0.

Prove directly that µ 6 1/2 implies convergence.

(b) Now consider the method
1 n+1 n+1 1
aun+1 n+1 n n n n



m − 4 (µ − c) um−1 − 2um + um+1 = aum + 4 (µ + c) um−1 − 2um + um+1 ,

where a and c are real constants. Using an eigenvalue analysis and carefully justifying
each step, determine conditions on µ, a and c for this method to be stable.
[You may use the notation [β, α, β] for the tridiagonal matrix with α along the diag-
onal, and β along the sub- and super-diagonals and use without proof any relevant theorems
about such matrices.]

END OF PAPER

Part II, Paper 3