Part II, 2002, Paper 4

Algebraic Curves

• B4.9

  Algebraic Curves | Part II, 2002

  Write an essay on the Riemann-Roch theorem and some of its applications.

  comment

Algebraic Topology

• B4.5

  Algebraic Topology | Part II, 2002

  State the Mayer-Vietoris theorem for a finite simplicial complex $X$ which is the union of closed subcomplexes $A$ and $B$. Define all the maps in the long exact sequence. Prove that the sequence is exact at the term $H_{i} X$, for every $i \geqslant 0$.

  comment

Algorithms and Networks

• A4.11

  Algorithms and Networks | Part II, 2002

  Write an essay on Strong Lagrangian problems. You should give an account of duality and how it relates to the Strong Lagrangian property. In particular, establish carefully the relationship between the Strong Lagrangian property and supporting hyperplanes.

  Also, give an example of a class of problems that are Strong Lagrangian. [You should explain carefully why your example has the Strong Lagrangian property.]

  comment

Applications of Quantum Mechanics

• B4.24

  Applications of Quantum Mechanics | Part II, 2002

  Explain the variational method for computing the ground state energy for a quantum Hamiltonian.

  For the one-dimensional Hamiltonian

  $$H=\frac{1}{2} p^{2}+\lambda x^{4},$$

  obtain an approximate form for the ground state energy by considering as a trial state the state $|w\rangle$ defined by $a|w\rangle=0$, where $\langle w \mid w\rangle=1$ and $a=(w / 2 \hbar)^{\frac{1}{2}}(x+i p / w)$.

  [It is useful to note that $\left\langle w\left|\left(a+a^{\dagger}\right)^{4}\right| w\right\rangle=\left\langle w\left|\left(a^{2} a^{\dagger 2}+a a^{\dagger} a a^{\dagger}\right)\right| w\right\rangle$.]

  Explain why the states $a^{\dagger}|w\rangle$ may be used as trial states for calculating the first excited energy level.

  comment

Applied Probability

• B4.12

  Applied Probability | Part II, 2002

  Define a Poisson random measure. State and prove the Product Theorem for the jump times $J_{n}$ of a Poisson process with constant rate $\lambda$ and independent random variables $Y_{n}$ with law $\mu$. Write down the corresponding result for a Poisson process $\Pi$ in a space $E=\mathbb{R}^{d}$ with rate $\lambda(x)(x \in E)$ when we associate with each $X \in \Pi$ an independent random variable $m_{X}$ with density $\rho(X, d m)$.

  Prove Campbell's Theorem, i.e. show that if $M$ is a Poisson random measure on the space $E$ with intensity measure $\nu$ and $a: E \rightarrow \mathbb{R}$ is a bounded measurable function then

  $$\mathbf{E}\left[e^{\theta \Sigma}\right]=\exp \left(\int_{E}\left(e^{\theta a(y)}-1\right) \nu(d y)\right)$$

  where

  $$\Sigma=\int_{E} a(y) M(d y)=\sum_{X \in \Pi} a(X)$$

  Stars are scattered over three-dimensional space $\mathbb{R}^{3}$ in a Poisson process $\Pi$ with density $\nu(X)\left(X \in \mathbb{R}^{3}\right)$. Masses of the stars are independent random variables; the mass $m_{X}$ of a star at $X$ has the density $\rho(X, d m)$. The gravitational potential at the origin is given by

  $$F=\sum_{X \in \Pi} \frac{G m_{X}}{|X|}$$

  where $G$ is a constant. Find the moment generating function $\mathbf{E}\left[e^{\theta F}\right]$.

  A galaxy occupies a sphere of radius $R$ centred at the origin. The density of stars is $\nu(\mathbf{x})=1 /|\mathbf{x}|$ for points $\mathbf{x}$ inside the sphere; the mass of each star has the exponential distribution with mean $M$. Calculate the expected potential due to the galaxy at the origin. Let $C$ be a positive constant. Find the distribution of the distance from the origin to the nearest star whose contribution to the potential $F$ is at least $C$.

  comment

Combinatorics

• B4.1

  Combinatorics | Part II, 2002

  Write an essay on Ramsey theory. You should include the finite and infinite versions of Ramsey's theorem, together with a discussion of upper and lower bounds in the finite case.

  [You may restrict your attention to colourings by just 2 colours.]

  comment

Computational Statistics and Statistical Modelling

• A4.14

  Computational Statistics and Statistical Modelling | Part II, 2002

  Assume that the $n$-dimensional observation vector $Y$ may be written as $Y=X \beta+\epsilon$, where $X$ is a given $n \times p$ matrix of rank $p, \beta$ is an unknown vector, with $\beta^{T}=\left(\beta_{1}, \ldots, \beta_{p}\right)$, and

  $$\epsilon \sim N_{n}\left(0, \sigma^{2} I\right)$$

  where $\sigma^{2}$ is unknown. Find $\hat{\beta}$, the least-squares estimator of $\beta$, and describe (without proof) how you would test

  $$H_{0}: \beta_{\nu}=0$$

  for a given $\nu$.

  Indicate briefly two plots that you could use as a check of the assumption $(*)$.

  Continued opposite Sulphur dioxide is one of the major air pollutants. A data-set presented by Sokal and Rohlf (1981) was collected on 41 US cities in 1969-71, corresponding to the following variables:

  $Y=$ sulphur dioxide content of air in micrograms per cubic metre

  $X 1=$ average annual temperature in degrees Fahrenheit

  $X 2$ = number of manufacturing enterprises employing 20 or more workers

  $X 3=$ population size (1970 census) in thousands

  $X 4=$ average annual wind speed in miles per hour

  $X 5=$ average annual precipitation in inches

  $X 6=$ average annual of days with precipitation per year $.$

  Interpret the $R$ output that follows below, quoting any standard theorems that you need to use.

  $$\begin{aligned} &>\text { next. } \operatorname{lm}-\operatorname{lm}(\log (\mathrm{Y}) \sim \mathrm{X} 1+\mathrm{X} 2+\mathrm{X} 3+\mathrm{X} 4+\mathrm{X} 5+\mathrm{X} 6) \\ &>\text { summary }(\text { next.lm }) \\ &\text { Call: } \operatorname{lm}(\text { formula }=\log (\mathrm{Y}) \sim \mathrm{X} 1+\mathrm{X} 2+\mathrm{X} 3+\mathrm{X} 4+\mathrm{X} 5+\mathrm{X} 6) \end{aligned}$$

  $$\begin{aligned} & \text { Call: } \operatorname{lm}(\text { formula }=\log (\mathrm{Y}) \sim \mathrm{X} 1+\mathrm{X} 2+\mathrm{X} 3+\mathrm{X} 4+\mathrm{X} 5+\mathrm{X} 6) \end{aligned}$$

  Residuals :

  $$\begin{array}{rrrrr} \text { Min } & 1 Q & \text { Median } & 3 Q & \text { Max } \\ \hline .79548 & -0.25538 & -0.01968 & 0.28328 & 0.98029 \end{array}$$

  $\begin{array}{lllll}-0.79548 & -0.25538 & -0.01968 & 0.28328 & 0.98029\end{array}$

  $\begin{array}{lrlcll}\text { Coefficients: } & & & & & \\ & \text { Estimate } & \text { Std. Error } & \text { t value } & \operatorname{Pr}(>|t|) & \\ \text { (Intercept) } & 7.2532456 & 1.4483686 & 5.008 & 1.68 \mathrm{e}-05 & * * * \\ \text { X1 } & -0.0599017 & 0.0190138 & -3.150 & 0.00339 & * * \\ \text { X2 } & 0.0012639 & 0.0004820 & 2.622 & 0.01298 & * \\ \text { X3 } & -0.0007077 & 0.0004632 & -1.528 & 0.13580 & \\ \text { X4 } & -0.1697171 & 0.0555563 & -3.055 & 0.00436 & * * \\ \text { X5 } & 0.0173723 & 0.0111036 & 1.565 & 0.12695 & \\ \text { X6 } & 0.0004347 & 0.0049591 & 0.088 & 0.93066\end{array}$

  Signif. codes: 0 ', $0.001$ ', $0.01$ ', $0.05$ ':

  Residual standard error: $0.448$ on 34 degrees of freedom

  Multiple R-Squared: $0.6541$

  F-statistic: $10.72$ on 6 and 34 degrees of freedom, p-value: $1.126 \mathrm{e}-06$

  comment

Differentiable Manifolds

• B4.4

  Differentiable Manifolds | Part II, 2002

  State and prove Stokes' Theorem for compact oriented manifolds-with-boundary.

  [You may assume results relating local forms on the manifold with those on its boundary provided you state them clearly.]

  Deduce that every differentiable map of the unit ball in $\mathbb{R}^{n}$ to itself has a fixed point.

  comment

Dynamical Systems

• B4.17

  Dynamical Systems | Part II, 2002

  Let $\mathcal{S}$ be a metric space, $F$ a map of $\mathcal{S}$ to itself and $P$ a point of $\mathcal{S}$. Define an attractor for $F$ and an omega point of the orbit of $P$ under $F$.

  Let $f$ be the map of $\mathbb{R}$ to itself given by

  $$f(x)=x+\frac{1}{2}+c \sin ^{2} 2 \pi x$$

  where $c>0$ is so small that $f^{\prime}(x)>0$ for all $x$, and let $F$ be the map of $\mathbb{R} / \mathbb{Z}$ to itself induced by $f$. What points if any are

  (a) attractors for $F^{2}$,

  (b) omega points of the orbit of some point $P$ under $F$ ?

  Is the cycle $\left\{0, \frac{1}{2}\right\}$ an attractor?

  In the notation of the first two sentences, let $\mathcal{C}$ be a cycle of order $M$ and assume that $F$ is continuous. Prove that $\mathcal{C}$ is an attractor for $F$ if and only if each point of $\mathcal{C}$ is an attractor for $F^{M}$.

  comment

Dynamics of Differential Equations

• A4.6

  Dynamics of Differential Equations | Part II, 2002

  Define the terms homoclinic orbit, heteroclinic orbit and heteroclinic loop. In the case of a dynamical system that possesses a homoclinic orbit, explain, without detailed calculation, how to calculate its stability.

  A second order dynamical system depends on two parameters $\mu_{1}$ and $\mu_{2}$. When $\mu_{1}=\mu_{2}=0$ there is a heteroclinic loop between the points $P_{1}, P_{2}$ as in the diagram.

  

  When $\mu_{1}, \mu_{2}$ are small there are trajectories that pass close to the fixed points $P_{1}, P_{2}$ :

  By adapting the method used above for trajectories near homoclinic orbits, show that the distances $y_{n}, y_{n+1}$ to the stable manifold at $P_{1}$ on successive returns are related to $z_{n}$, $z_{n+1}$, the corresponding distances near $P_{2}$, by coupled equations of the form

  $$\left.\begin{array}{rl} z_{n} & =\left(y_{n}\right)^{\gamma_{1}}+\mu_{1}, \\ y_{n+1} & =\left(z_{n}\right)^{\gamma_{2}}+\mu_{2}, \end{array}\right\}$$

  where any arbitrary constants have been removed by rescaling, and $\gamma_{1}, \gamma_{2}$ depend on conditions near $P_{1}, P_{2}$. Show from these equations that there is a stable heteroclinic orbit $\left(\mu_{1}=\mu_{2}=0\right)$ if $\gamma_{1} \gamma_{2}>1$. Show also that in the marginal situation $\gamma_{1}=2, \gamma_{2}=\frac{1}{2}$ there can be a stable fixed point for small positive $y, z$ if $\mu_{2}<0, \mu_{2}^{2}<\mu_{1}$. Explain carefully the form of the orbit of the original dynamical system represented by the solution of the above map when $\mu_{2}^{2}=\mu_{1}$.

  comment

Electrodynamics

• B4.21

  Electrodynamics | Part II, 2002

  Derive Larmor's formula for the rate at which radiation is produced by a particle of charge $q$ moving along a trajectory $\mathbf{x}(t)$.

  A non-relativistic particle of mass $m$, charge $q$ and energy $E$ is incident along a radial line in a central potential $V(r)$. The potential is vanishingly small for $r$ very large, but increases without bound as $r \rightarrow 0$. Show that the total amount of energy $\mathcal{E}$ radiated by the particle is

  $$\mathcal{E}=\frac{\mu_{0} q^{2}}{3 \pi m^{2}} \sqrt{\frac{m}{2}} \int_{r_{0}}^{\infty} \frac{1}{\sqrt{E-V(r)}}\left(\frac{d V}{d r}\right)^{2} d r$$

  where $V\left(r_{0}\right)=E$.

  Suppose that $V$ is the Coulomb potential $V(r)=A / r$. Evaluate $\mathcal{E}$.

  comment

Electromagnetism

• A4.5

  Electromagnetism | Part II, 2002

  State the four integral relationships between the electric field $\mathbf{E}$ and the magnetic field $\mathbf{B}$ and explain their physical significance. Derive Maxwell's equations from these relationships and show that $\mathbf{E}$ and $\mathbf{B}$ can be described by a scalar potential $\phi$ and a vector potential A which satisfy the inhomogeneous wave equations

  $$\begin{gathered} \nabla^{2} \phi-\epsilon_{0} \mu_{0} \frac{\partial^{2} \phi}{\partial t^{2}}=-\frac{\rho}{\epsilon_{0}} \\ \nabla^{2} \mathbf{A}-\epsilon_{0} \mu_{0} \frac{\partial^{2} \mathbf{A}}{\partial t^{2}}=-\mu_{0} \mathbf{j} \end{gathered}$$

  If the current $\mathbf{j}$ satisfies Ohm's law and the charge density $\rho=0$, show that plane waves of the form

  $$\mathbf{A}=A(z, t) e^{i \omega t} \hat{\mathbf{x}},$$

  where $\hat{\mathbf{x}}$ is a unit vector in the $x$-direction of cartesian axes $(x, y, z)$, are damped. Find an approximate expression for $A(z, t)$ when $\omega \ll \sigma / \epsilon_{0}$, where $\sigma$ is the electrical conductivity.

  comment

Fluid Dynamics II

• B4.26

  Fluid Dynamics II | Part II, 2002

  Write an essay on boundary-layer theory and its application to the generation of lift in aerodynamics.

  You should include discussion of the derivation of the boundary-layer equation, the similarity transformation leading to the Falkner-Skan equation, the influence of an adverse pressure gradient, and the mechanism(s) by which circulation is generated in flow past bodies with a sharp trailing edge.

  comment

Foundations of Quantum Mechanics

• A4.15 B4.22

  Foundations of Quantum Mechanics | Part II, 2002

  Discuss the consequences of indistinguishability for a quantum mechanical state consisting of two identical, non-interacting particles when the particles have (a) spin zero, (b) spin 1/2.

  The stationary Schrödinger equation for one particle in the potential

  $$-\frac{2 e^{2}}{4 \pi \epsilon_{0} r}$$

  has normalized, spherically symmetric, real wave functions $\psi_{n}(\mathbf{r})$ and energy eigenvalues $E_{n}$ with $E_{0}<E_{1}<E_{2}<\cdots$. What are the consequences of the Pauli exclusion principle for the ground state of the helium atom? Assuming that wavefunctions which are not spherically symmetric can be ignored, what are the states of the first excited energy level of the helium atom?

  [You may assume here that the electrons are non-interacting.]

  Show that, taking into account the interaction between the two electrons, the estimate for the energy of the ground state of the helium atom is

  $$2 E_{0}+\frac{e^{2}}{4 \pi \epsilon_{0}} \int \frac{d^{3} \mathbf{r}_{1} d^{3} \mathbf{r}_{2}}{\left|\mathbf{r}_{1}-\mathbf{r}_{2}\right|} \psi_{0}^{2}\left(\mathbf{r}_{1}\right) \psi_{0}^{2}\left(\mathbf{r}_{2}\right)$$

  comment

Functional Analysis

• A4.3

  Functional Analysis | Part II, 2002

  Define the distribution function $\Phi_{f}$ of a non-negative measurable function $f$ on the interval $I=[0,1]$. Show that $\Phi_{f}$ is a decreasing non-negative function on $[0, \infty]$ which is continuous on the right.

  Define the Lebesgue integral $\int_{I} f d m$. Show that $\int_{I} f d m=0$ if and only if $f=0$ almost everywhere.

  Suppose that $f$ is a non-negative Riemann integrable function on $[0,1]$. Show that there are an increasing sequence $\left(g_{n}\right)$ and a decreasing sequence $\left(h_{n}\right)$ of non-negative step functions with $g_{n} \leqslant f \leqslant h_{n}$ such that $\int_{0}^{1}\left(h_{n}(x)-g_{n}(x)\right) d x \rightarrow 0$.

  Show that the functions $g=\lim _{n} g_{n}$ and $h=\lim _{n} h_{n}$ are equal almost everywhere, that $f$ is measurable and that the Lebesgue integral $\int_{I} f d m$ is equal to the Riemann integral $\int_{0}^{1} f(x) d x$.

  Suppose that $j$ is a Riemann integrable function on $[0,1]$ and that $j(x)>0$ for all $x$. Show that $\int_{0}^{1} j(x) d x>0$.

  comment

Galois Theory

• B4.3

  Galois Theory | Part II, 2002

  Suppose $K, L$ are fields and $\sigma_{1}, \ldots, \sigma_{m}$ are distinct embeddings of $K$ into $L$. Prove that there do not exist elements $\lambda_{1}, \ldots, \lambda_{m}$ of $L$ (not all zero) such that $\lambda_{1} \sigma_{1}(x)+\ldots+$ $\lambda_{m} \sigma_{m}(x)=0$ for all $x \in K$. Deduce that if $K / k$ is a finite extension of fields, and $\sigma_{1}, \ldots, \sigma_{m}$ are distinct $k$-automorphisms of $K$, then $m \leqslant[K: k]$.

  Suppose now that $K$ is a Galois extension of $k$ with Galois group cyclic of order $n$, where $n$ is not divisible by the characteristic. If $k$ contains a primitive $n$th root of unity, prove that $K$ is a radical extension of $k$. Explain briefly the relevance of this result to the problem of solubility of cubics by radicals.

  comment

General Relativity

• A4.17 B4.25

  General Relativity | Part II, 2002

  With respect to the Schwarzschild coordinates $(r, \theta, \phi, t)$, the Schwarzschild geometry is given by

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

  where $r_{s}=2 M$ is the Schwarzschild radius and $M$ is the Schwarzschild mass. Show that, by a suitable choice of $(\theta, \phi)$, the general geodesic can regarded as moving in the equatorial plane $\theta=\pi / 2$. Obtain the equations governing timelike and null geodesics in terms of $u(\phi)$, where $u=1 / r$.

  Discuss light bending and perihelion precession in the solar system.

  comment

Graph Theory

• A4.9

  Graph Theory | Part II, 2002

  Write an essay on connectivity in graphs.

  Your essay should include proofs of at least two major theorems, along with a discussion of one or two significant corollaries.

  comment

Groups, Rings and Fields

• A4.4

  Groups, Rings and Fields | Part II, 2002

  Let $F$ be a finite field. Show that there is a unique prime $p$ for which $F$ contains the field $\mathbb{F}_{p}$ of $p$ elements. Prove that $F$ contains $p^{n}$ elements, for some $n \in \mathbb{N}$. Show that $x^{p^{n}}=x$ for all $x \in F$, and hence find a polynomial $f \in \mathbb{F}_{p}[X]$ such that $F$ is the splitting field of $f$. Show that, up to isomorphism, $F$ is the unique field $\mathbb{F}_{p^{n}}$ of size $p^{n}$.

  [Standard results about splitting fields may be assumed.]

  Prove that the mapping sending $x$ to $x^{p}$ is an automorphism of $\mathbb{F}_{p^{n}}$. Deduce that the Galois group Gal $\left(\mathbb{F}_{p^{n}} / \mathbb{F}_{p}\right)$ is cyclic of order $n$. For which $m$ is $\mathbb{F}_{p^{m}}$ a subfield of $\mathbb{F}_{p^{n}}$ ?

  comment

Hilbert Spaces

• B4.7

  Hilbert Spaces | Part II, 2002

  Throughout this question, $H$ is an infinite-dimensional, separable Hilbert space. You may use, without proof, any theorems about compact operators that you require.

  Define a Fredholm operator $T$, on a Hilbert space $H$, and define the index of $T$.

  (i) Prove that if $T$ is Fredholm then $\operatorname{im} T$ is closed.

  (ii) Let $F \in \mathcal{B}(H)$ and let $F$ have finite rank. Prove that $F^{*}$ also has finite rank.

  (iii) Let $T=I+F$, where $I$ is the identity operator on $H$ and $F$ has finite rank; let $E=\operatorname{im} F+\operatorname{im} F^{*}$. By considering $T \mid E$ and $T \mid E^{\perp}$ (or otherwise) prove that $T$ is Fredholm with ind $T=0$.

  (iv) Let $T \in \mathcal{B}(H)$ be Fredholm with ind $T=0$. Prove that $T=A+F$, where $A$ is invertible and $F$ has finite rank.

  [You may wish to note that $T$ effects an isomorphism from $(\operatorname{ker} T)^{\perp}$ onto $\operatorname{im} T$; also ker $T$ and $(\operatorname{im} T)^{\perp}$ have the same finite dimension.]

  (v) Deduce from (iii) and (iv) that $T \in \mathcal{B}(H)$ is Fredholm with ind $T=0$ if and only if $T=A+K$ with $A$ invertible and $K$ compact.

  (vi) Explain briefly, by considering suitable shift operators on $\ell^{2}$ (i.e. not using any theorems about Fredholm operators) that, for each $k \in \mathbb{Z}$, there is a Fredholm operator $S$ on $H$ with ind $S=k$.

  comment

Information Theory

• B4.13

  Information Theory | Part II, 2002

  Define the Huffman binary encoding procedure and prove its optimality among decipherable codes.

  comment

Logic, Computation and Set Theory

• A4.8

  Logic, Computation and Set Theory | Part II, 2002

  Let $P$ be a set of primitive propositions. Let $L(P)$ denote the set of all compound propositions over $P$, and let $S$ be a subset of $L(P)$. Consider the relation $\preceq$ on $L(P)$ defined by

  $$s \preceq s t \text { if and only if } S \cup\{s\} \vdash t .$$

  Prove that $\preceq_{S}$ is reflexive and transitive. Deduce that if we define $\approx_{S}$ by $\left(s \approx_{S} t\right.$ if and only if $s \preceq_{S} t$ and $\left.t \preceq \preceq_{S} s\right)$, then $\approx_{S}$ is an equivalence relation and the quotient $B_{S}=L(P) / \approx_{S}$ is partially ordered by the relation $\leqslant_{S}$ induced by $\preccurlyeq_{S}$ (that is, $[s] \leqslant_{S}[t]$ if and only if $s \preccurlyeq_{S} t$, where square brackets denote equivalence classes).

  Assuming the result that $B_{S}$ is a Boolean algebra with lattice operations induced by the logical operations on $L(P)$ (that is, $[s] \wedge[t]=[s \wedge t]$, etc.), show that there is a bijection between the following two sets:

  (a) The set of lattice homomorphisms $B_{S} \rightarrow\{0,1\}$.

  (b) The set of models of the propositional theory $S$.

  Deduce that the completeness theorem for propositional logic is equivalent to the assertion that, for any Boolean algebra $B$ with more than one element, there exists a homomorphism $B \rightarrow\{0,1\}$.

  [You may assume the result that the completeness theorem implies the compactness theorem.]

  comment

• B4.10

  Logic, Computation and Set Theory | Part II, 2002

  Explain what is meant by a well-ordering of a set.

  Without assuming Zorn's Lemma, show that the power-set of any well-ordered set can be given a total (linear) ordering.

  By a selection function for a set $A$, we mean a function $f: P A \rightarrow P A$ such that $f(B) \subset B$ for all $B \subset A, f(B) \neq \emptyset$ for all $B \neq \emptyset$, and $f(B) \neq B$ if $B$ has more than one element. Suppose given a selection function $f$. Given a mapping $g: \alpha \rightarrow[0,1]$ for some ordinal $\alpha$, we define a subset $B(f, g) \subset A$ recursively as follows:

  $$\begin{aligned} &B(f, g)=A \quad \text { if } \alpha=0, \\ &B(f, g)=f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=1 \\ &B(f, g)=B\left(f,\left.g\right|_{\beta}\right) \backslash f\left(B\left(f,\left.g\right|_{\beta}\right)\right) \quad \text { if } \alpha=\beta^{+} \text {and } g(\beta)=0 \\ &B(f, g)=\bigcap\left\{B\left(f,\left.g\right|_{\beta}\right) \mid \beta<\alpha\right\} \quad \text { if } \alpha \text { is a limit ordinal. } \end{aligned}$$

  Show that, for any $x \in A$ and any ordinal $\alpha$, there exists a function $g$ with domain $\alpha$ such that $x \in B(f, g)$.

  [It may help to observe that $g$ is uniquely determined by $x$ and $\alpha$, though you need not show this explicitly.]

  Show also that there exists $\alpha$ such that, for every $g$ with domain $\alpha, B(f, g)$ is either empty or a singleton.

  Deduce that the assertion 'Every set has a selection function' implies that every set can be totally ordered.

  [Hartogs' Lemma may be assumed, provided you state it precisely.]

  comment

Markov Chains

• A4.1

  Markov Chains | Part II, 2002

  Write an essay on the long-time behaviour of discrete-time Markov chains on a finite state space. Your essay should include discussion of the convergence of probabilities as well as almost-sure behaviour. You should also explain what happens when the chain is not irreducible.

  comment

Mathematical Methods

• A4.21

  Mathematical Methods | Part II, 2002

  State Watson's lemma giving an asymptotic expansion as $\lambda \rightarrow \infty$ for an integral of the form

  $$I_{1}=\int_{0}^{A} f(t) e^{-\lambda t} d t, \quad A>0$$

  Show how this result may be used to find an asymptotic expansion as $\lambda \rightarrow \infty$ for an integral of the form

  $$I_{2}=\int_{-A}^{B} f(t) e^{-\lambda t^{2}} d t, \quad A>0, B>0$$

  Hence derive Laplace's method for obtaining an asymptotic expansion as $\lambda \rightarrow \infty$ for an integral of the form

  $$I_{3}=\int_{a}^{b} f(t) e^{\lambda \phi(t)} d t$$

  where $\phi(t)$ is differentiable, for the cases: (i) $\phi^{\prime}(t)<0$ in $a \leq t \leq b$; and (ii) $\phi^{\prime}(t)$ has a simple zero at $t=c$ with $a<c<b$ and $\phi^{\prime \prime}(c)<0$.

  Find the first two terms in the asymptotic expansion as $x \rightarrow \infty$ of

  $$I_{4}=\int_{-\infty}^{\infty} \log \left(1+t^{2}\right) e^{-x t^{2}} d t$$

  [You may leave your answer expressed in terms of $\Gamma$-functions.]

  comment

Methods of Mathematical Physics

• B4.19

  Methods of Mathematical Physics | Part II, 2002

  Let

  $$I(\lambda, a)=\int_{-i \infty}^{i \infty} \frac{e^{\lambda\left(t^{3}-3 t\right)}}{t^{2}-a^{2}} d t$$

  where $\lambda$ is real, $a$ is real and non-zero, and the path of integration runs up the imaginary axis. Show that, if $a^{2}>1$,

  $$I(\lambda, a) \sim \frac{i e^{-2 \lambda}}{1-a^{2}} \sqrt{\frac{\pi}{3 \lambda}}$$

  as $\lambda \rightarrow+\infty$ and sketch the relevant steepest descent path.

  What is the corresponding result if $a^{2}<1$ ?

  comment

Number Fields

• B4.6

  Number Fields | Part II, 2002

  Write an essay on one the following topics.

  (i) Dirichlet's unit theorem and the Pell equation.

  (ii) Ideals and the fundamental theorem of arithmetic.

  (iii) Dedekind's theorem and the factorisation of primes. (You should treat explicitly either the case of quadratic fields or that of the cyclotomic field.)

  comment

Number Theory

• A4.10

  Number Theory | Part II, 2002

  Write an essay on quadratic reciprocity. Your essay should include (i) a proof of the law of quadratic reciprocity for the Legendre symbol, (ii) a proof of the law of quadratic reciprocity for the Jacobi symbol, and (iii) a comment on why this latter law is useful in primality testing.

  comment

Numerical Analysis

• A4.22 B4.20

  Numerical Analysis | Part II, 2002

  Write an essay on the method of conjugate gradients. You should describe the algorithm, present an analysis of its properties and discuss its advantages.

  [Any theorems quoted should be stated precisely but need not be proved.]

  comment

Optimization and Control

• B4.14

  Optimization and Control | Part II, 2002

  A discrete-time decision process is defined on a finite set of states $I$ as follows. Upon entry to state $i_{t}$ at time $t$ the decision-maker observes a variable $\xi_{t}$. He then chooses the next state freely within $I$, at a cost of $c\left(i_{t}, \xi_{t}, i_{t+1}\right)$. Here $\left\{\xi_{0}, \xi_{1}, \ldots\right\}$ is a sequence of integer-valued, identically distributed random variables. Suppose there exist $\left\{\phi_{i}: i \in I\right\}$ and $\lambda$ such that for all $i \in I$

  $$\phi_{i}+\lambda=\sum_{k \in \mathbb{Z}} P\left(\xi_{t}=k\right) \min _{i^{\prime} \in I}\left[c\left(i, k, i^{\prime}\right)+\phi_{i^{\prime}}\right] .$$

  Let $\pi$ denote a policy. Show that

  $$\lambda=\inf _{\pi} \limsup _{t \rightarrow \infty} E_{\pi}\left[\frac{1}{t} \sum_{s=0}^{t-1} c\left(i_{s}, \xi_{s}, i_{s+1}\right)\right]$$

  At the start of each month a boat manufacturer receives orders for 1, 2 or 3 boats. These numbers are equally likely and independent from month to month. He can produce $j$ boats in a month at a cost of $6+3 j$ units. All orders are filled at the end of the month in which they are ordered. It is possible to make extra boats, ending the month with a stock of $i$ unsold boats, but $i$ cannot be more than 2 , and a holding cost of $c i$ is incurred during any month that starts with $i$ unsold boats in stock. Write down an optimality equation that can be used to find the long-run expected average-cost.

  Let $\pi$ be the policy of only ever producing sufficient boats to fill the present month's orders. Show that it is optimal if and only if $c \geqslant 2$.

  Suppose $c<2$. Starting from $\pi$, what policy is obtained after applying one step of the policy-improvement algorithm?

  comment

Partial Differential Equations

• B4.18

  Partial Differential Equations | Part II, 2002

  Discuss the notion of fundamental solution for a linear partial differential equation with constant coefficients.

  comment

Principles of Dynamics

• A4.2

  Principles of Dynamics | Part II, 2002

  Explain how the orientation of a rigid body can be specified by means of the three Eulerian angles, $\theta, \phi$ and $\psi$.

  An axisymmetric top of mass $M$ has principal moments of inertia $A, A$ and $C$, and is spinning with angular speed $n$ about its axis of symmetry. Its centre of mass lies a distance $h$ from the fixed point of support. Initially the axis of symmetry points vertically upwards. It then suffers a small disturbance. For what values of the spin is the initial configuration stable?

  If the spin is such that the initial configuration is unstable, what is the lowest angle reached by the symmetry axis in the nutation of the top? Find the maximum and minimum values of the precessional angular velocity $\dot{\phi}$.

  comment

Principles of Statistics

• A4.13 B4.15

  Principles of Statistics | Part II, 2002

  (a) Let $X_{1}, \ldots, X_{n}$ be independent, identically distributed random variables from a one-parameter distribution with density function

  $$f(x ; \theta)=h(x) g(\theta) \exp \{\theta t(x)\}, x \in \mathbb{R} .$$

  Explain in detail how you would test

  $$H_{0}: \theta=\theta_{0} \text { against } H_{1}: \theta \neq \theta_{0} \text {. }$$

  What is the general form of a conjugate prior density for $\theta$ in a Bayesian analysis of this distribution?

  (b) Let $Y_{1}, Y_{2}$ be independent Poisson random variables, with means $(1-\psi) \lambda$ and $\psi \lambda$ respectively, with $\lambda$ known.

  Explain why the Conditionality Principle leads to inference about $\psi$ being drawn from the conditional distribution of $Y_{2}$, given $Y_{1}+Y_{2}$. What is this conditional distribution?

  (c) Suppose $Y_{1}, Y_{2}$ have distributions as in (b), but that $\lambda$ is now unknown.

  Explain in detail how you would test $H_{0}: \psi=\psi_{0}$ against $H_{1}: \psi \neq \psi_{0}$, and describe the optimality properties of your test.

  [Any general results you use should be stated clearly, but need not be proved.]

  comment

Probability and Measure

• B4.11

  Probability and Measure | Part II, 2002

  State Birkhoff's Almost Everywhere Ergodic Theorem for measure-preserving transformations. Define what it means for a sequence of random variables to be stationary. Explain briefly how the stationarity of a sequence of random variables implies that a particular transformation is measure-preserving.

  A bag contains one white ball and one black ball. At each stage of a process one ball is picked from the bag (uniformly at random) and then returned to the bag together with another ball of the same colour. Let $X_{n}$ be a random variable which takes the value 0 if the $n$th ball added to the bag is white and 1 if it is black.

  (a) Show that the sequence $X_{1}, X_{2}, X_{3}, \ldots$ is stationary and hence that the proportion of black balls in the bag converges almost surely to some random variable $R$.

  (b) Find the distribution of $R$.

  [The fact that almost-sure convergence implies convergence in distribution may be used without proof.]

  comment

Quantum Physics

• A4.16

  Quantum Physics | Part II, 2002

  Explain how the energy band structure for electrons determines the conductivity properties of crystalline materials.

  A semiconductor has a conduction band with a lower edge $E_{c}$ and a valence band with an upper edge $E_{v}$. Assuming that the density of states for electrons in the conduction band is

  $$\rho_{c}(E)=B_{c}\left(E-E_{c}\right)^{\frac{1}{2}}, \quad E>E_{c}$$

  and in the valence band is

  $$\rho_{v}(E)=B_{v}\left(E_{v}-E\right)^{\frac{1}{2}}, \quad E<E_{v}$$

  where $B_{c}$ and $B_{v}$ are constants characteristic of the semiconductor, explain why at low temperatures the chemical potential for electrons lies close to the mid-point of the gap between the two bands.

  Describe what is meant by the doping of a semiconductor and explain the distinction between $n$-type and $p$-type semiconductors, and discuss the low temperature limit of the chemical potential in both cases. Show that, whatever the degree and type of doping,

  $$n_{e} n_{p}=B_{c} B_{v}[\Gamma(3 / 2)]^{2}(k T)^{3} e^{-\left(E_{c}-E_{v}\right) / k T}$$

  where $n_{e}$ is the density of electrons in the conduction band and $n_{p}$ is the density of holes in the valence band.

  comment

Representation Theory

• B4.2

  Representation Theory | Part II, 2002

  Write an essay on the representation theory of $S U_{2}$.

  comment

Riemann Surfaces

• B4.8

  Riemann Surfaces | Part II, 2002

  A holomorphic map $p: S \rightarrow T$ between Riemann surfaces is called a covering map if every $t \in T$ has a neighbourhood $V$ for which $p^{-1}(V)$ breaks up as a disjoint union of open subsets $U_{\alpha}$ on which $p: U_{\alpha} \rightarrow V$ is biholomorphic.

  (a) Suppose that $f: R \rightarrow T$ is any holomorphic map of connected Riemann surfaces, $R$ is simply connected and $p: S \rightarrow T$ is a covering map. By considering the lifts of paths from $T$ to $S$, or otherwise, prove that $f$ lifts to a holomorphic map $\widetilde{f}: R \rightarrow S$, i.e. that there exists an $\widetilde{f}$ with $f=p \circ \widetilde{f}$.

  (b) Write down a biholomorphic map from the unit disk $\Delta=\{z \in \mathbb{C}:|z|<1\}$ onto a half-plane. Show that the unit disk $\Delta$ uniformizes the punctured unit disk $\Delta^{\times}=\Delta-\{0\}$ by constructing an explicit covering map $p: \Delta \rightarrow \Delta^{\times}$.

  (c) Using the uniformization theorem, or otherwise, prove that any holomorphic map from $\mathbb{C}$ to a compact Riemann surface of genus greater than one is constant.

  comment

Statistical Physics

• B4.23

  Statistical Physics | Part II, 2002

  A perfect gas in equilibrium in a volume $V$ has quantum stationary states $|i\rangle$ with energies $E_{i}$. In a Boltzmann distribution, the probability that the system is in state $|i\rangle$ is $\rho_{i}=Z^{-1} e^{-E_{i} / k T}$. The entropy is defined to be $S=-k \sum_{i} \rho_{i} \log \rho_{i}$.

  For two nearby states establish the equation

  $$d E=T d S-P d V$$

  where $E$ and $P$ should be defined.

  For reversible changes show that

  $$d S=\frac{\delta Q}{T}$$

  where $\delta Q$ is the amount of heat transferred in the exchange.

  Define $C_{V}$, the heat capacity at constant volume.

  A system with constant heat capacity $C_{V}$ initially at temperature $T$ is heated at constant volume to a temperature $\Theta$. Show that the change in entropy is $\Delta S=$ $C_{V} \log (\Theta / T)$.

  Explain what is meant by isothermal and adiabatic transitions.

  Briefly, describe the Carnot cycle and define its efficiency. Explain briefly why no heat engine can be more efficient than one whose operation is based on a Carnot cycle.

  Three identical bodies with constant heat capacity at fixed volume $C_{V}$, are initially at temperatures $T_{1}, T_{2}, T_{3}$, respectively. Heat engines operate between the bodies with no input of work or heat from the outside and the respective temperatures are changed to $\Theta_{1}, \Theta_{2}, \Theta_{3}$, the volume of the bodies remaining constant. Show that, if the heat engines operate on a Carnot cycle, then

  $$\Theta_{1} \Theta_{2} \Theta_{3}=A, \quad \Theta_{1}+\Theta_{2}+\Theta_{3}=B$$

  where $A=T_{1} T_{2} T_{3}$ and $B=T_{1}+T_{2}+T_{3}$.

  Hence show that the maximum temperature to which any one of the bodies can be raised is $\Theta$ where

  $$\Theta+2\left(\frac{A}{\Theta}\right)^{1 / 2}=B$$

  Show that a solution is $\Theta=T$ if initially $T_{1}=T_{2}=T_{3}=T$. Do you expect there to be any other solutions?

  Find $\Theta$ if initially $T_{1}=300 \mathrm{~K}, T_{2}=300 \mathrm{~K}, T_{3}=100 \mathrm{~K}$.

  [Hint: Choose to maximize one temperature and impose the constraints above using Lagrange multipliers. ]

  comment

Statistical Physics and Cosmology

• A4.18

  Statistical Physics and Cosmology | Part II, 2002

  What is an ideal gas? Explain how the microstates of an ideal gas of indistinguishable particles can be labelled by a set of integers. What range of values do these integers take for (a) a boson gas and (b) a Fermi gas?

  Let $E_{i}$ be the energy of the $i$-th one-particle energy eigenstate of an ideal gas in thermal equilibrium at temperature $T$ and let $p_{i}\left(n_{i}\right)$ be the probability that there are $n_{i}$ particles of the gas in this state. Given that

  $$p_{i}\left(n_{i}\right)=e^{-\beta E_{i} n_{i}} / Z_{i} \quad\left(\beta=\frac{1}{k T}\right)$$

  determine the normalization factor $Z_{i}$ for (a) a boson gas and (b) a Fermi gas. Hence obtain an expression for $\bar{n}_{i}$, the average number of particles in the $i$-th one-particle energy eigenstate for both cases (a) and (b).

  In the case of a Fermi gas, write down (without proof) the generalization of your formula for $\bar{n}_{i}$ to a gas at non-zero chemical potential $\mu$. Show how it leads to the concept of a Fermi energy $\epsilon_{F}$ for a gas at zero temperature. How is $\epsilon_{F}$ related to the Fermi momentum $p_{F}$ for (a) a non-relativistic gas and (b) an ultra-relativistic gas?

  In an approximation in which the discrete set of energies $E_{i}$ is replaced with a continuous set with momentum $p$, the density of one-particle states with momentum in the range $p$ to $p+d p$ is $g(p) d p$. Explain briefly why

  $$g(p) \propto p^{2} V$$

  where $V$ is the volume of the gas. Using this formula, obtain an expression for the total energy $E$ of an ultra-relativistic gas at zero chemical potential as an integral over $p$. Hence show that

  $$\frac{E}{V} \propto T^{\alpha},$$

  where $\alpha$ is a number that you should compute. Why does this result apply to a photon gas?

  Using the formula $(*)$ for a non-relativistic Fermi gas at zero temperature, obtain an expression for the particle number density $n$ in terms of the Fermi momentum and provide a physical interpretation of this formula in terms of the typical de Broglie wavelength. Obtain an analogous formula for the (internal) energy density and hence show that the pressure $P$ behaves as

  $$P \propto n^{\gamma}$$

  where $\gamma$ is a number that you should compute. [You need not prove any relation between the pressure and the energy density you use.] What is the origin of this pressure given that $T=0$ by assumption? Explain briefly and qualitatively how it is relevant to the stability of white dwarf stars.

  comment

Stochastic Financial Models

• A4.12 B4.16

  Stochastic Financial Models | Part II, 2002

  Write an essay on the Black-Scholes formula for the price of a European call option on a stock. Your account should include a derivation of the formula and a careful analysis of its dependence on the parameters of the model.

  comment

Theoretical Geophysics

• A4.20

  Theoretical Geophysics | Part II, 2002

  The equation of motion for small displacements $\mathbf{u}$ in a homogeneous, isotropic, elastic material is

  $$\rho \frac{\partial^{2} \mathbf{u}}{\partial t^{2}}=(\lambda+2 \mu) \nabla(\boldsymbol{\nabla} \cdot \mathbf{u})-\mu \boldsymbol{\nabla} \wedge(\boldsymbol{\nabla} \wedge \mathbf{u})$$

  where $\lambda$ and $\mu$ are the Lamé constants. Derive the conditions satisfied by the polarisation $\mathbf{P}$ and (real) vector slowness s of plane-wave solutions $\mathbf{u}=\mathbf{P} f(\mathbf{s} \cdot \mathbf{x}-t)$, where $f$ is an arbitrary scalar function. Describe the division of these waves into $P$-waves, $S H$-waves and $S V$-waves.

  A plane harmonic $S V$-wave of the form

  $$\mathbf{u}=\left(s_{3}, 0,-s_{1}\right) \exp \left[i \omega\left(s_{1} x_{1}+s_{3} x_{3}-t\right)\right]$$

  travelling through homogeneous elastic material of $P$-wave speed $\alpha$ and $S$-wave speed $\beta$ is incident from $x_{3}<0$ on the boundary $x_{3}=0$ of rigid material in $x_{3}>0$ in which the displacement is identically zero.

  Write down the form of the reflected wavefield in $x_{3}<0$. Calculate the amplitudes of the reflected waves in terms of the components of the slowness vectors.

  Derive expressions for the components of the incident and reflected slowness vectors, in terms of the wavespeeds and the angle of incidence $\theta_{0}$. Hence show that there is no reflected $S V$-wave if

  $$\sin ^{2} \theta_{0}=\frac{\beta^{2}}{\alpha^{2}+\beta^{2}}$$

  Sketch the rays produced if the region $x_{3}>0$ is fluid instead of rigid.

  comment

Transport Processes

• A4.19

  Transport Processes | Part II, 2002

  (a) A biological vessel is modelled two-dimensionally as a fluid-filled channel bounded by parallel plane walls $y=\pm a$, embedded in an infinite region of fluid-saturated tissue. In the tissue a solute has concentration $C^{o u t}(y, t)$, diffuses with diffusivity $D$ and is consumed by biological activity at a rate $k C^{o u t}$ per unit volume, where $D$ and $k$ are constants. By considering the solute balance in a slice of tissue of infinitesimal thickness, show that

  $$C_{t}^{o u t}=D C_{y y}^{o u t}-k C^{\text {out }} .$$

  A steady concentration profile $C^{o u t}(y)$ results from a flux $\beta\left(C^{i n}-C_{a}^{o u t}\right)$, per unit area of wall, of solute from the channel into the tissue, where $C^{i n}$ is a constant concentration of solute that is maintained in the channel and $C_{a}^{\text {out }}=C^{\text {out }}(a)$. Write down the boundary conditions satisfied by $C^{\text {out }}(y)$. Solve for $C^{\text {out }}(y)$ and show that

  $$C_{a}^{o u t}=\frac{\gamma}{\gamma+1} C^{i n}$$

  where $\gamma=\beta / \sqrt{k D}$.

  (b) Now let the solute be supplied by steady flow down the channel from one end, $x=0$, with the channel taken to be semi-infinite in the $x$-direction. The cross-sectionally averaged velocity in the channel $u(x)$ varies due to a flux of fluid from the tissue to the channel (by osmosis) equal to $\lambda\left(C^{i n}-C_{a}^{\text {out }}\right)$ per unit area. Neglect both the variation of $C^{i n}(x)$ across the channel and diffusion in the $x$-direction.

  By considering conservation of fluid, show that

  $$a u_{x}=\lambda\left(C^{i n}-C_{a}^{o u t}\right)$$

  and write down the corresponding equation derived from conservation of solute. Deduce that

  $$u\left(\lambda C^{i n}+\beta\right)=u_{0}\left(\lambda C_{0}^{i n}+\beta\right),$$

  where $u_{0}=u(0)$ and $C_{0}^{i n}=C^{i n}(0)$.

  Assuming that equation $(*)$ still holds, even though $C^{\text {out }}$is now a function of $x$ as well as $y$, show that $u(x)$ satisfies the ordinary differential equation

  $$(\gamma+1) a u u_{x}+\beta u=u_{0}\left(\lambda C_{0}^{i n}+\beta\right)$$

  Find scales $\hat{x}$ and $\hat{u}$ such that the dimensionless variables $U=u / \hat{u}$ and $X=x / \hat{x}$ satisfy

  $$U U_{X}+U=1$$

  Derive the solution $(1-U) e^{U}=A e^{-X}$ and find the constant $A$.

  To what values do $u$ and $C_{i n}$ tend as $x \rightarrow \infty$ ?

  comment

Waves in Fluid and Solid Media

• B4.27

  Waves in Fluid and Solid Media | Part II, 2002

  Write down the equation governing linearized displacements $\mathbf{u}(\mathbf{x}, t)$ in a uniform elastic medium of density $\rho$ and Lamé constants $\lambda$ and $\mu$. Derive solutions for monochromatic plane $P$ and $S$ waves, and find the corresponding wave speeds $c_{P}$ and $c_{S}$.

  Such an elastic solid occupies the half-space $z>0$, and the boundary $z=0$ is clamped rigidly so that $\mathbf{u}(x, y, 0, t)=\mathbf{0}$. A plane $S V$-wave with frequency $\omega$ and wavenumber $(k, 0,-m)$ is incident on the boundary. At some angles of incidence, there results both a reflected $S V$-wave with frequency $\omega^{\prime}$ and wavenumber $\left(k^{\prime}, 0, m^{\prime}\right)$ and a reflected $P$-wave with frequency $\omega^{\prime \prime}$ and wavenumber $\left(k^{\prime \prime}, 0, m^{\prime \prime}\right)$. Relate the frequencies and wavenumbers of the reflected waves to those of the incident wave. At what angles of incidence will there be a reflected $P$-wave?

  Find the amplitudes of the reflected waves as multiples of the amplitude of the incident wave. Confirm that these amplitudes give the sum of the time-averaged vertical fluxes of energy of the reflected waves equal to the time-averaged vertical flux of energy of the incident wave.

  [Results concerning the energy flux, energy density and kinetic energy density in a plane elastic wave may be quoted without proof.]

  comment