Part II, 2002, Paper 2

Algebraic Curves

• B2.10

  Algebraic Curves | Part II, 2002

  For $N \geq 1$, let $V_{N}$ be the (irreducible) projective plane curve $V_{N}: X^{N}+Y^{N}+Z^{N}=0$ over an algebraically closed field of characteristic zero.

  Show that $V_{N}$ is smooth (non-singular). For $m, n \geq 1$, let $\alpha_{m, n}: V_{m n} \rightarrow V_{m}$ be the morphism $\alpha_{m, n}(X: Y: Z)=\left(X^{n}: Y^{n}: Z^{n}\right)$. Determine the degree of $\alpha_{m, n}$, its points of ramification and the corresponding ramification indices.

  Applying the Riemann-Hurwitz formula to $\alpha_{1, n}$, determine the genus of $V_{n}$.

  comment

Algebraic Topology

• B2.8

  Algebraic Topology | Part II, 2002

  Show that the fundamental group $G$ of the Klein bottle is infinite. Show that $G$ contains an abelian subgroup of finite index. Show that $G$ is not abelian.

  comment

Algorithms and Networks

• A2.10

  Algorithms and Networks | Part II, 2002

  (i) Let $G$ be a directed network with nodes $N$, arcs $A$ and capacities specified on each of the arcs. Define the terms feasible flow, divergence, cut, upper and lower cut capacities. Given two disjoint sets of nodes $N^{+}$and $N^{-}$, what does it mean to say that a cut $Q$ separates $N^{+}$from $N^{-}$? Prove that the flux of a feasible flow $x$ from $N^{+}$to $N^{-}$is bounded above by the upper capacity of $Q$, for any cut $Q$ separating $N^{+}$from $N^{-}$.

  (ii) Define the maximum-flow and minimum-cut problems. State the max-flow min-cut theorem and outline the main steps of the maximum-flow algorithm. Use the algorithm to find the maximum flow between the nodes 1 and 5 in a network whose node set is $\{1,2, \ldots, 5\}$, where the lower capacity of each arc is 0 and the upper capacity $c_{i j}$ of the directed arc joining node $i$ to node $j$ is given by the $(i, j)$-entry in the matrix

  $$\left(\begin{array}{ccccc} 0 & 7 & 9 & 8 & 0 \\ 0 & 0 & 6 & 8 & 4 \\ 0 & 9 & 0 & 2 & 10 \\ 0 & 3 & 7 & 0 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$$

  [The painted-network theorem can be used without proof but should be stated clearly. You may assume in your description of the maximum-flow algorithm that you are given an initial feasible flow.]

  comment

Applications of Quantum Mechanics

• B2.22

  Applications of Quantum Mechanics | Part II, 2002

  Define the reciprocal lattice for a lattice $L$ with lattice vectors $\ell$.

  A beam of electrons, with wave vector $\mathbf{k}$, is incident on a Bravais lattice $L$ with a large number of atoms, $N$. If the scattering amplitude for scattering on an individual atom in the direction $\hat{\mathbf{k}}^{\prime}$ is $f\left(\hat{\mathbf{k}}^{\prime}\right)$, show that the scattering amplitude for the whole lattice

  $$\sum_{\ell \in L} e^{i \mathbf{q} \cdot \ell} f\left(\hat{\mathbf{k}}^{\prime}\right), \quad \mathbf{q}=\mathbf{k}-|\mathbf{k}| \hat{\mathbf{k}}^{\prime}$$

  Derive the formula for the differential cross section

  $$\frac{\mathrm{d} \sigma}{\mathrm{d} \Omega}=N\left|f\left(\hat{\mathbf{k}}^{\prime}\right)\right|^{2} \Delta(\mathbf{q}),$$

  obtaining an explicit form for $\Delta(\mathbf{q})$. Show that $\Delta(\mathbf{q})$ is strongly peaked when $\mathbf{q}=\mathbf{g}$, a reciprocal lattice vector. Show that this leads to the Bragg formula $2 d \sin \frac{\theta}{2}=\lambda$, where $\theta$ is the scattering angle, $\lambda$ the electron wavelength and $d$ the separation between planes of atoms in the lattice.

  comment

Applied Probability

• B2.13

  Applied Probability | Part II, 2002

  Two enthusiastic probability students, Ros and Guil, sit an examination which starts at time 0 and ends at time $T$; they both decide to use the time to attempt a proof of a difficult theorem which carries a lot of extra marks.

  Ros' strategy is to write the proof continuously at a constant speed $\lambda$ lines per unit time. In a time interval of length $\delta t$ he has a probability $\mu \delta t+o(\delta t)$ of realising he has made a mistake. If that happens he instantly panics, erases everything he has written and starts all over again.

  Guil, on the other hand, keeps cool and thinks carefully about what he is doing. In a time interval of length $\delta t$, he has a probability $\lambda \delta t+o(\delta t)$ of writing the next line of proof and for each line he has written a probability $\mu \delta t+o(\delta t)$ of finding a mistake in that line, independently of all other lines he has written. When a mistake is found, he erases that line and carries on as usual, hoping for the best.

  Both Ros and Guil realise that, even if they manage to finish the proof, they will not recognise that they have done so and will carry on writing as much as they can.

  (a) Calculate $p_{l}(t)$, the probability that, for Ros, the length of his completed proof at time $t \geqslant l / \lambda$ is at least $l$.

  (b) Let $q_{n}(t)$ be the probability that Guil has $n$ lines of proof at time $t>0$. Show that

  $$\frac{\partial Q}{\partial t}=(s-1)\left(\lambda Q-\mu \frac{\partial Q}{\partial s}\right)$$

  where $Q(s, t)=\sum_{n=0}^{\infty} s^{n} q_{n}(t)$.

  (c) Suppose now that every time Ros starts all over again, the time until the next mistake has distribution $F$, independently of the past history. Write down a renewal-type integral equation satisfied by $l(t)$, the expected length of Ros' proof at time $t$. What is the expected length of proof produced by him at the end of the examination if $F$ is the exponential distribution with mean $1 / \mu$ ?

  (d) What is the expected length of proof produced by Guil at the end of the examination if each line that he writes survives for a length of time with distribution $F$, independently of all other lines?

  comment

Coding and Cryptography

• A2.9

  Coding and Cryptography | Part II, 2002

  (i) Explain the idea of public key cryptography. Give an example of a public key system, explaining how it works.

  (ii) What is a general feedback register of length $d$ with initial fill $\left(X_{0}, \ldots, X_{d-1}\right)$ ? What is the maximal period of such a register, and why? What does it mean for such a register to be linear?

  Describe and justify the Berlekamp-Massey algorithm for breaking a cypher stream arising from a general linear feedback register of unknown length.

  Use the Berlekamp-Massey algorithm to find a linear recurrence in $\mathbb{F}_{2}$ with first eight terms $1,1,0,0,1,0,1,1$.

  comment

Combinatorics

• B2.5

  Combinatorics | Part II, 2002

  State and prove the local $L Y M$ inequality. Explain carefully when equality holds.

  Define the colex order and state the Kruskal-Katona theorem. Deduce that, if $n$ and $r$ are fixed positive integers with $1 \leqslant r \leqslant n-1$, then for every $1 \leqslant m \leqslant\left(\begin{array}{l}n \\ r\end{array}\right)$ we have

  $$\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n]^{(r)},|\mathcal{A}|=m\right\}=\min \left\{|\partial \mathcal{A}|: \mathcal{A} \subset[n+1]^{(r)},|\mathcal{A}|=m\right\}$$

  By a suitable choice of $n, r$ and $m$, show that this result does not remain true if we replace the lower shadow $\partial A$ with the upper shadow $\partial^{+} \mathcal{A}$.

  comment

Computational Statistics and Statistical Modelling

• A2.12

  Computational Statistics and Statistical Modelling | Part II, 2002

  (i) Suppose that the random variable $Y$ has density function of the form

  $$f(y \mid \theta, \phi)=\exp \left[\frac{y \theta-b(\theta)}{\phi}+c(y, \phi)\right]$$

  where $\phi>0$. Show that $Y$ has expectation $b^{\prime}(\theta)$ and variance $\phi b^{\prime \prime}(\theta)$.

  (ii) Suppose now that $Y_{1}, \ldots, Y_{n}$ are independent negative exponential variables, with $Y_{i}$ having density function $f\left(y_{i} \mid \mu_{i}\right)=\frac{1}{\mu_{i}} e^{-y_{i} / \mu_{i}}$ for $y_{i}>0$. Suppose further that $g\left(\mu_{i}\right)=\beta^{T} x_{i}$ for $1 \leqslant i \leqslant n$, where $g(\cdot)$ is a known 'link' function, and $x_{1}, \ldots, x_{n}$ are given covariate vectors, each of dimension $p$. Discuss carefully the problem of finding $\hat{\beta}$, the maximum-likelihood estimator of $\beta$, firstly for the case $g\left(\mu_{i}\right)=1 / \mu_{i}$, and secondly for the case $g(\mu)=\log \mu_{i}$; in both cases you should state the large-sample distribution of $\hat{\beta}$.

  [Any standard theorems used need not be proved.]

  comment

Differentiable Manifolds

• B2.7

  Differentiable Manifolds | Part II, 2002

  State, giving your reasons, whether the following are true or false.

  (a) Diffeomorphic connected manifolds must have the same dimension.

  (b) Every non-zero vector bundle has a nowhere-zero section.

  (c) Every projective space admits a volume form.

  (d) If a manifold $M$ has Euler characteristic zero, then $M$ is orientable.

  comment

Dynamics of Differential Equations

• A2.6 B2.4

  Dynamics of Differential Equations | Part II, 2002

  (i) Define the terms stable manifold and unstable manifold of a hyperbolic fixed point $\mathbf{x}_{0}$ of a dynamical system. State carefully the stable manifold theorem.

  Give an approximation, correct to fourth order in $|\mathbf{x}|$, for the stable and unstable manifolds of the origin for the system

  $$\left(\begin{array}{c} \dot{x} \\ \dot{y} \end{array}\right)=\left(\begin{array}{c} x+x^{2}-y^{2} \\ -y+x^{2} \end{array}\right) .$$

  (ii) State, without proof, the centre manifold theorem. Show that the fixed point at the origin of the system

  $$\begin{aligned} &\dot{x}=y-x+a x^{3}, \\ &\dot{y}=r x-y-z y \\ &\dot{z}=-z+x y \end{aligned}$$

  where $a$ is a constant, is non-hyperbolic at $r=1$.

  Using new coordinates $v=x+y, w=x-y$, find the centre manifold in the form

  $$w=\alpha v^{3}+\ldots, \quad z=\beta v^{2}+\gamma v^{4}+\ldots$$

  for constants $\alpha, \beta, \gamma$ to be determined. Hence find the evolution equation on the centre manifold in the form

  $$\dot{v}=\frac{1}{8}(a-1) v^{3}+\left(\frac{(3 a+1)(a+1)}{128}+\frac{(a-1)}{32}\right) v^{5}+\ldots$$

  Ignoring higher order terms, give conditions on $a$ that guarantee that the origin is asymptotically stable.

  comment

Electrodynamics

• B2.20

  Electrodynamics | Part II, 2002

  A particle of rest mass $m$ and charge $q$ moves in an electromagnetic field given by a potential $A_{a}$ along a trajectory $x^{a}(\tau)$, where $\tau$ is the proper time along the particle's worldline. The action for such a particle is

  $$I=\int\left(m \sqrt{-\eta_{a b} \dot{x}^{a} \dot{x}^{b}}-q A_{a} \dot{x}^{a}\right) d \tau .$$

  Show that the Euler-Lagrange equations resulting from this action reproduce the relativistic equation of motion for the particle.

  Suppose that the particle is moving in the electrostatic field of a fixed point charge $Q$ with radial electric field $E_{r}$ given by

  $$E_{r}=\frac{Q}{4 \pi \epsilon_{0} r^{2}} .$$

  Show that one can choose a gauge such that $A_{i}=0$ and only $A_{0} \neq 0$. Find $A_{0}$.

  Assume that the particle executes planar motion, which in spherical polar coordinates $(r, \theta, \phi)$ can be taken to be in the plane $\theta=\pi / 2$. Derive the equations of motion for $t$ and $\phi$.

  By using the fact that $\eta_{a b} \dot{x}^{a} \dot{x}^{b}=-1$, find the equation of motion for $r$, and hence show that the shape of the orbit is described by

  $$\frac{d r}{d \phi}=\pm \frac{r^{2}}{\ell} \sqrt{\left(E+\frac{\gamma}{r}\right)^{2}-1-\frac{\ell^{2}}{r^{2}}}$$

  where $E(>1)$ and $\ell$ are constants of integration and $\gamma$ is to be determined.

  By putting $u=1 / r$ or otherwise, show that if $\gamma^{2}<\ell^{2}$ then the orbits are bounded and generally not closed, and show that the angle between successive minimal values of $r$ is $2 \pi\left(1-\gamma^{2} / \ell^{2}\right)^{-1 / 2}$.

  comment

Electromagnetism

• A2.5

  Electromagnetism | Part II, 2002

  (i) Show that the Lorentz force corresponds to a curvature force and the gradient of a magnetic pressure, and that it can be written as the divergence of a second rank tensor, the Maxwell stress tensor.

  Consider the potential field $\mathbf{B}$ given by $\mathbf{B}=-\nabla \Phi$, where

  $$\Phi(x, y)=\left(\frac{B_{0}}{k}\right) \cos k x e^{-k y}$$

  referred to cartesian coordinates $(x, y, z)$. Obtain the Maxwell stress tensor and verify that its divergence vanishes.

  (ii) The magnetic field in a stellar atmosphere is maintained by steady currents and the Lorentz force vanishes. Show that there is a scalar field $\alpha$ such that $\nabla \wedge \mathbf{B}=\alpha \mathbf{B}$ and $\mathbf{B} \cdot \nabla \alpha=0$. Show further that if $\alpha$ is constant, then $\nabla^{2} \mathbf{B}+\alpha^{2} \mathbf{B}=0$. Obtain a solution in the form $\mathbf{B}=\left(B_{1}(z), B_{2}(z), 0\right)$; describe the structure of this field and sketch its variation in the $z$-direction.

  comment

Fluid Dynamics II

• B2.24

  Fluid Dynamics II | Part II, 2002

  A thin layer of liquid of kinematic viscosity $\nu$ flows under the influence of gravity down a plane inclined at an angle $\alpha$ to the horizontal $(0 \leq \alpha \leq \pi / 2)$. With origin $O$ on the plane, and axes $O x$ down the line of steepest slope and $O y$ normal to the plane, the free surface is given by $y=h(x, t)$, where $|\partial h / \partial x| \ll 1$. The pressure distribution in the liquid may be assumed to be hydrostatic. Using the approximations of lubrication theory, show that

  $$\frac{\partial h}{\partial t}=\frac{g}{3 \nu} \frac{\partial}{\partial x}\left\{h^{3}\left(\cos \alpha \frac{\partial h}{\partial x}-\sin \alpha\right)\right\} .$$

  Now suppose that

  $$h=h_{0}+\eta(x, t)$$

  where

  $$\eta(x, 0)=\eta_{0} e^{-x^{2} / a^{2}}$$

  and $h_{0}, \eta_{0}$ and $a$ are constants with $\eta_{0} \ll a, h_{0}$. Show that, to leading order,

  $$\eta(x, t)=\frac{a \eta_{0}}{\left(a^{2}+4 D t\right)^{1 / 2}} \exp \left\{-\frac{(x-U t)^{2}}{a^{2}+4 D t}\right\}$$

  where $U$ and $D$ are constants to be determined.

  Explain in physical terms the meaning of this solution.

  comment

Foundations of Quantum Mechanics

• A2.13 B2.21

  Foundations of Quantum Mechanics | Part II, 2002

  (i) A Hamiltonian $H_{0}$ has energy eigenvalues $E_{r}$ and corresponding non-degenerate eigenstates $|r\rangle$. Show that under a small change in the Hamiltonian $\delta H$,

  $$\delta|r\rangle=\sum_{s \neq r} \frac{\langle s|\delta H| r\rangle}{E_{r}-E_{s}}|s\rangle,$$

  and derive the related formula for the change in the energy eigenvalue $E_{r}$ to first and second order in $\delta H$.

  (ii) The Hamiltonian for a particle moving in one dimension is $H=H_{0}+\lambda H^{\prime}$, where $H_{0}=p^{2} / 2 m+V(x), H^{\prime}=p / m$ and $\lambda$ is small. Show that

  $$\frac{i}{\hbar}\left[H_{0}, x\right]=H^{\prime}$$

  and hence that

  $$\delta E_{r}=-\lambda^{2} \frac{i}{\hbar}\left\langle r\left|H^{\prime} x\right| r\right\rangle=\lambda^{2} \frac{i}{\hbar}\left\langle r\left|x H^{\prime}\right| r\right\rangle$$

  to second order in $\lambda$.

  Deduce that $\delta E_{r}$ is independent of the particular state $|r\rangle$ and explain why this change in energy is exact to all orders in $\lambda$.

  comment

Functional Analysis

• A2.3 B2.2

  Functional Analysis | Part II, 2002

  (i) State and prove the parallelogram law for Hilbert spaces.

  Suppose that $K$ is a closed linear subspace of a Hilbert space $H$ and that $x \in H$. Show that $x$ is orthogonal to $K$ if and only if 0 is the nearest point to $x$ in $K$.

  (ii) Suppose that $H$ is a Hilbert space and that $\phi$ is a continuous linear functional on $H$ with $\|\phi\|=1$. Show that there is a sequence $\left(h_{n}\right)$ of unit vectors in $H$ with $\phi\left(h_{n}\right)$ real and $\phi\left(h_{n}\right)>1-1 / n$.

  Show that $h_{n}$ converges to a unit vector $h$, and that $\phi(h)=1$.

  Show that $h$ is orthogonal to $N$, the null space of $\phi$, and also that $H=N \oplus \operatorname{span}(h)$.

  Show that $\phi(k)=\langle k, h\rangle$, for all $k \in H$.

  comment

General Relativity

• A2.15 B2.23

  General Relativity | Part II, 2002

  (i) Consider the line element describing the interior of a star,

  $$d s^{2}=e^{2 \alpha(r)} d r^{2}+r^{2}\left(d \theta^{2}+\sin ^{2} \theta d \phi^{2}\right)-e^{2 \gamma(r)} d t^{2},$$

  defined for $0 \leq r \leq r_{0}$ by

  $$e^{-2 \alpha(r)}=1-A r^{2}$$

  and

  $$e^{\gamma(r)}=\frac{3}{2} e^{-\alpha_{0}}-\frac{1}{2} e^{-\alpha(r)}$$

  Here $A=2 M / r_{0}^{3}, M$ is the mass of the star, and $\alpha_{0}$ is defined to be $\alpha\left(r_{0}\right)$.

  The star is made of a perfect fluid with energy-momentum tensor

  $$T_{a b}=(p+\rho) u_{a} u_{b}+p g_{a b} .$$

  Here $u^{a}$ is the 4 -velocity of the fluid which is at rest, the density $\rho$ is constant throughout the star $\left(0 \leq r \leq r_{0}\right)$ and the pressure $p=p(r)$ depends only on the radial coordinate. Write down the Einstein field equations and show that (in geometrical units with $G=c=1$ ) they may equivalently be written as

  $$R_{a b}=8 \pi(p+\rho) u_{a} u_{b}+4 \pi(p-\rho) g_{a b} .$$

  (ii) Using the formulae below, or otherwise, show that for $0 \leq r \leq r_{0}$ one has

  $$\rho=\frac{3 A}{8 \pi}, \quad p(r)=\frac{3 A}{8 \pi}\left(\frac{e^{-\alpha(r)}-e^{-\alpha_{0}}}{3 e^{-\alpha_{0}}-e^{-\alpha(r)}}\right)$$

  [The non-zero components of the Ricci tensor are:

  $$\begin{gathered} R_{11}=-\gamma^{\prime \prime}+\alpha^{\prime} \gamma^{\prime}-\gamma^{\prime 2}+\frac{2 \alpha^{\prime}}{r}, \quad R_{22}=e^{-2 \alpha}\left[\left(\alpha^{\prime}-\gamma^{\prime}\right) r-1\right]+1 \\ R_{33}=\sin ^{2} \theta R_{22}, \quad R_{44}=e^{2 \gamma-2 \alpha}\left[\gamma^{\prime \prime}-\alpha^{\prime} \gamma^{\prime}+\gamma^{\prime 2}+\frac{2 \gamma^{\prime}}{r}\right] \end{gathered}$$

  Note that

  $$\alpha^{\prime}=A r e^{2 \alpha}, \quad \gamma^{\prime}=\frac{1}{2} A r e^{\alpha-\gamma}, \quad \gamma^{\prime \prime}=\frac{1}{2} A e^{\alpha-\gamma}+\frac{1}{2} A^{2} r^{2} e^{3 \alpha-\gamma}-\frac{1}{4} A^{2} r^{2} e^{2 \alpha-2 \gamma} \text { ] ] }$$

  comment

Geometry of Surfaces

• A2.7

  Geometry of Surfaces | Part II, 2002

  (i)

  Consider the surface

  $$z=\frac{1}{2}\left(\lambda x^{2}+\mu y^{2}\right)+h(x, y)$$

  where $h(x, y)$ is a term of order at least 3 in $x, y$. Calculate the first fundamental form at $x=y=0$.

  (ii) Calculate the second fundamental form, at $x=y=0$, of the surface given in Part (i). Calculate the Gaussian curvature. Explain why your answer is consistent with Gauss' "Theorema Egregium".

  comment

Graph Theory

• A2.8

  Graph Theory | Part II, 2002

  (i) Define the chromatic polynomial $p(G ; t)$ of the graph $G$, and establish the standard identity

  $$p(G ; t)=p(G-e ; t)-p(G / e ; t),$$

  where $e$ is an edge of $G$. Deduce that, if $G$ has $n$ vertices and $m$ edges, then

  $$p(G ; t)=a_{n} t^{n}-a_{n-1} t^{n-1}+a_{n-2} t^{n-2}+\ldots+(-1)^{n} a_{0},$$

  where $a_{n}=1, a_{n-1}=m$ and $a_{j} \geq 0$ for $0 \leq j \leq n$.

  (ii) Let $G$ and $p(G ; t)$ be as in Part (i). Show that if $G$ has $k$ components $G_{1}, \ldots, G_{k}$ then $p(G ; t)=\prod_{i=1}^{k} p\left(G_{i} ; t\right)$. Deduce that $a_{k}>0$ and $a_{j}=0$ for $0 \leq j<k$.

  Show that if $G$ is a tree then $p(G ; t)=t(t-1)^{n-1}$. Must the converse hold? Justify your answer.

  Show that if $p(G ; t)=p\left(T_{r}(n) ; t\right)$, where $T_{r}(n)$ is a Turán graph, then $G=T_{r}(n)$.

  comment

Groups, Rings and Fields

• A2.4 B2.3

  Groups, Rings and Fields | Part II, 2002

  (i) Show that the ring $\mathbb{Z}[i]$ is Euclidean.

  (ii) What are the units in $\mathbb{Z}[i]$ ? What are the primes in $\mathbb{Z}[i]$ ? Justify your answers. Factorize $11+7 i$ into primes in $\mathbb{Z}[i]$.

  comment

Information Theory

• B2.14

  Information Theory | Part II, 2002

  Define the binary Hamming code of length $n=2^{\ell}-1$ and its dual. Prove that the Hamming code is perfect. Prove that in the dual code:

  (i) The weight of any non-zero codeword equals $2^{\ell-1}$;

  (ii) The distance between any pair of words equals $2^{\ell-1}$.

  [You may quote results from the course provided that they are carefully stated.]

  comment

Logic, Computation and Set Theory

• B2.11

  Logic, Computation and Set Theory | Part II, 2002

  Explain what is meant by a structure for a first-order language and by a model for a first-order theory. If $T$ is a first-order theory whose axioms are all universal sentences (that is, sentences of the form $\left(\forall x_{1} \ldots x_{n}\right) p$ where $p$ is quantifier-free), show that every substructure of a $T$-model is a $T$-model.

  Now let $T$ be an arbitrary first-order theory in a language $L$, and let $M$ be an $L$-structure satisfying all the universal sentences which are derivable from the axioms of $T$. If $p$ is a quantifier-free formula (with free variables $x_{1}, \ldots, x_{n}$ say) whose interpretation $[p]_{M}$ is a nonempty subset of $M^{n}$, show that $T \cup\left\{\left(\exists x_{1} \cdots x_{n}\right) p\right\}$ is consistent.

  Let $L^{\prime}$ be the language obtained from $L$ by adjoining a new constant $\widehat{a}$for each element $a$ of $M$, and let

  $$T^{\prime}=T \cup\left\{p\left[\widehat{a}_{1}, \ldots, \widehat{a}_{n} / x_{1}, \ldots, x_{n}\right] \mid p \text { is quantifier-free and }\left(a_{1}, \ldots, a_{n}\right) \in[p]_{M}\right\}$$

  Show that $T^{\prime}$ has a model. [You may use the Completeness and Compactness Theorems.] Explain briefly why any such model contains a substructure isomorphic to $M$.

  comment

Markov Chains

• A2.1

  Markov Chains | Part II, 2002

  (i) In each of the following cases, the state-space $I$ and non-zero transition rates $q_{i j}$ $(i \neq j)$ of a continuous-time Markov chain are given. Determine in which cases the chain is explosive.

  (ii) Children arrive at a see-saw according to a Poisson process of rate 1 . Initially there are no children. The first child to arrive waits at the see-saw. When the second child arrives, they play on the see-saw. When the third child arrives, they all decide to go and play on the merry-go-round. The cycle then repeats. Show that the number of children at the see-saw evolves as a Markov Chain and determine its generator matrix. Find the probability that there are no children at the see-saw at time $t$.

  Hence obtain the identity

  $$\sum_{n=0}^{\infty} e^{-t} \frac{t^{3 n}}{(3 n) !}=\frac{1}{3}+\frac{2}{3} e^{-\frac{3}{2} t} \cos \frac{\sqrt{3}}{2} t$$

  $$\begin{aligned} & \text { (a) } I=\{1,2,3, \ldots\}, \quad q_{i, i+1}=i^{2}, \quad i \in I \text {, } \\ & \text { (b) } \quad I=\mathbb{Z}, \quad q_{i, i-1}=q_{i, i+1}=2^{i}, \quad i \in I \text {. } \end{aligned}$$

  comment

Mathematical Methods

• A2.17

  Mathematical Methods | Part II, 2002

  (i) Show that the equation

  $$\epsilon x^{4}-x^{2}+5 x-6=0, \quad|\epsilon| \ll 1$$

  has roots in the neighbourhood of $x=2$ and $x=3$. Find the first two terms of an expansion in $\epsilon$ for each of these roots.

  Find a suitable series expansion for the other two roots and calculate the first two terms in each case.

  (ii) Describe, giving reasons for the steps taken, how the leading-order approximation for $\lambda \gg 1$ to an integral of the form

  $$I(\lambda) \equiv \int_{A}^{B} f(t) e^{i \lambda g(t)} d t$$

  where $\lambda$ and $g$ are real, may be found by the method of stationary phase. Consider the cases where (a) $g^{\prime}(t)$ has one simple zero at $t=t_{0}$ with $A<t_{0}<B$; (b) $g^{\prime}(t)$ has more than one simple zero in $A<t<B$; and (c) $g^{\prime}(t)$ has only a simple zero at $t=B$. What is the order of magnitude of $I(\lambda)$ if $g^{\prime}(t)$ is non-zero for $A \leq t \leq B$ ?

  Use the method of stationary phase to find the leading-order approximation to

  $$J(\lambda) \equiv \int_{0}^{1} \sin \left[\lambda\left(2 t^{4}-t\right)\right] d t$$

  for $\lambda \gg 1$.

  [You may use the fact that $\int_{-\infty}^{\infty} e^{i u^{2}} d u=\sqrt{\pi} e^{i \pi / 4}$.]

  comment

Methods of Mathematical Physics

• B2.18

  Methods of Mathematical Physics | Part II, 2002

  Show that

  $$\mathcal{P} \int_{-\infty}^{\infty} \frac{t^{z-1}}{t-a} d t=\pi i a^{z-1},$$

  where $a$ is real and positive, $0<\operatorname{Re}(z)<1$ and $\mathcal{P}$ denotes the Cauchy principal value; the principal branches of $t^{z}$ etc. are implied. Deduce that

  $$\int_{0}^{\infty} \frac{t^{z-1}}{t+a} d t=\pi a^{z-1} \operatorname{cosec} \pi z$$

  and that

  $$\mathcal{P} \int_{0}^{\infty} \frac{t^{z-1}}{t-a} d t=-\pi a^{z-1} \cot \pi z$$

  Use $(*)$ to show that, if $\operatorname{Im}(b)>0$, then

  $$\int_{0}^{\infty} \frac{t^{z-1}}{t-b} d t=-\pi b^{z-1}(\cot \pi z-i)$$

  What is the value of this integral if $\operatorname{Im}(b)<0$ ?

  comment

Nonlinear Waves

• A2.18

  Nonlinear Waves | Part II, 2002

  (i) Find a travelling wave solution of unchanging shape for the modified Burgers equation (with $\alpha>0$ )

  $$\frac{\partial u}{\partial t}+u^{2} \frac{\partial u}{\partial x}=\alpha \frac{\partial^{2} u}{\partial x^{2}}$$

  with $u=0$ far ahead of the wave and $u=1$ far behind. What is the velocity of the wave? Sketch the shape of the wave.

  (ii) Explain why the method of characteristics, when applied to an equation of the type

  $$\frac{\partial u}{\partial t}+c(u) \frac{\partial u}{\partial x}=0$$

  with initial data $u(x, 0)=f(x)$, sometimes gives a multi-valued solution. State the shockfitting algorithm that gives a single-valued solution, and explain how it is justified.

  Consider the equation above, with $c(u)=u^{2}$. Suppose that

  $$u(x, 0)=\left\{\begin{array}{ll} 0 & x \geq 0 \\ 1 & x<0 \end{array} .\right.$$

  Sketch the characteristics in the $(x, t)$ plane. Show that a shock forms immediately, and calculate the velocity at which it moves.

  comment

Number Fields

• B2.9

  Number Fields | Part II, 2002

  Let $K=\mathbb{Q}(\sqrt{35})$. By Dedekind's theorem, or otherwise, show that the ideal equations

  $$2=[2, \omega]^{2}, \quad 5=[5, \omega]^{2}, \quad[\omega]=[2, \omega][5, \omega]$$

  hold in $K$, where $\omega=5+\sqrt{35}$. Deduce that $K$ has class number 2 .

  Verify that $1+\omega$ is the fundamental unit in $K$. Hence show that the complete solution in integers $x, y$ of the equation $x^{2}-35 y^{2}=-10$ is given by

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

  Calculate the particular solution $x, y$ for $n=1$.

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

  comment

Numerical Analysis

• A2.19 B2.19

  Numerical Analysis | Part II, 2002

  (i)

  Given the finite-difference method

  $$\sum_{k=-r}^{s} \alpha_{k} u_{m+k}^{n+1}=\sum_{k=-r}^{s} \beta_{k} u_{m+k}^{n}, \quad m, n \in \mathbb{Z}, n \geqslant 0$$

  define

  $$H(z)=\frac{\sum_{k=-r}^{s} \beta_{k} z^{k}}{\sum_{k=-r}^{s} \alpha_{k} z^{k}}$$

  Prove that this method is stable if and only if

  $$\left|H\left(e^{i \theta}\right)\right| \leqslant 1, \quad-\pi \leqslant \theta \leqslant \pi .$$

  [You may quote without proof known properties of the Fourier transform.]

  (ii) Find the range of the parameter $\mu$ such that the method

  $$(1-2 \mu) u_{m-1}^{n+1}+4 \mu u_{m}^{n+1}+(1-2 \mu) u_{m+1}^{n+1}=u_{m-1}^{n}+u_{m+1}^{n}$$

  is stable. Supposing that this method is used to solve the diffusion equation for $u(x, t)$, determine the order of magnitude of the local error as a power of $\Delta x$.

  comment

Optimization and Control

• B2.15

  Optimization and Control | Part II, 2002

  State Pontryagin's maximum principle (PMP) for the problem of minimizing

  $$\int_{0}^{T} c(x(t), u(t)) d t+K(x(T))$$

  where $x(t) \in \mathbb{R}^{n}, u(t) \in \mathbb{R}^{m}, d x / d t=a(x(t), u(t))$; here, $x(0)$ and $T$ are given, and $x(T)$ is unconstrained.

  Consider the two-dimensional problem in which $d x_{1} / d t=x_{2}, d x_{2} / d t=u$, $c(x, u)=\frac{1}{2} u^{2}$ and $K(x(T))=\frac{1}{2} q x_{1}(T)^{2}, q>0$. Show that, by use of a variable $z(t)=x_{1}(t)+x_{2}(t)(T-t)$, one can rewrite this problem as an equivalent one-dimensional problem.

  Use PMP to solve this one-dimensional problem, showing that the optimal control can be expressed as $u(t)=-q z(T)(T-t)$, where $z(T)=z(0) /\left(1+\frac{1}{3} q T^{3}\right)$.

  Express $u(t)$ in a feedback form of $u(t)=k(t) z(t)$ for some $k(t)$.

  Suppose that the initial state $x(0)$ is perturbed by a small amount to $x(0)+\left(\epsilon_{1}, \epsilon_{2}\right)$. Give an expression (in terms of $\epsilon_{1}, \epsilon_{2}, x(0), q$ and $T$ ) for the increase in minimal cost.

  comment

Partial Differential Equations

• B2.17

  Partial Differential Equations | Part II, 2002

  (a) Define the convolution $f * g$ of two functions. Write down a formula for a solution $u:[0, \infty) \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ to the initial value problem

  $$\frac{\partial u}{\partial t}-\Delta u=0$$

  together with the boundary condition

  $$u(0, x)=f(x)$$

  for $f$ a bounded continuous function on $\mathbb{R}^{n}$. Comment briefly on the uniqueness of the solution.

  (b) State and prove the Duhamel principle giving the solution (for $t>0$ ) to the equation

  $$\frac{\partial u}{\partial t}-\Delta u=g$$

  together with the boundary condition

  $$u(0, x)=f(x)$$

  in terms of your answer to (a).

  (c) Show that if $v:[0, \infty) \times \mathbb{R}^{n} \rightarrow \mathbb{R}$ is the solution to

  $$\frac{\partial v}{\partial t}-\Delta v=G$$

  together with the boundary condition

  $$v(0, x)=f(x)$$

  with $G(t, x) \leq g(t, x)$ for all $(t, x)$ then $v(t, x) \leq u(t, x)$ for all $(t, x) \in(0, \infty) \times \mathbb{R}^{n}$.

  Finally show that if in addition there exists a point $\left(t_{0}, x_{0}\right)$ at which there is strict inequality in the assumption i.e.

  $$G\left(t_{0}, x_{0}\right)<g\left(t_{0}, x_{0}\right)$$

  then in fact

  $$v(t, x)<u(t, x)$$

  whenever $t>t_{0}$.

  comment

Principles of Dynamics

• A2.2 B2.1

  Principles of Dynamics | Part II, 2002

  (i) A number $N$ of non-interacting particles move in one dimension in a potential $V(x, t)$. Write down the Hamiltonian and Hamilton's equations for one particle.

  At time $t$, the number density of particles in phase space is $f(x, p, t)$. Write down the time derivative of $f$ along a particle's trajectory. By equating the rate of change of the number of particles in a fixed domain $V$ in phase space to the flux into $V$ across its boundary, deduce that $f$ is a constant along any particle's trajectory.

  (ii) Suppose that $V(x)=\frac{1}{2} m \omega^{2} x^{2}$, and particles are injected in such a manner that the phase space density is a constant $f_{1}$ at any point of phase space corresponding to a particle energy being smaller than $E_{1}$ and zero elsewhere. How many particles are present?

  Suppose now that the potential is very slowly altered to the square well form

  $$V(x)=\left\{\begin{array}{cc} 0, & -L<x<L \\ \infty & \text { elsewhere } \end{array}\right.$$

  Show that the greatest particle energy is now

  $$E_{2}=\frac{\pi^{2}}{8} \frac{E_{1}^{2}}{m L^{2} \omega^{2}} .$$

  comment

Principles of Statistics

• A2.11 B2.16

  Principles of Statistics | Part II, 2002

  (i) Let $X$ be a random variable with density function $f(x ; \theta)$. Consider testing the simple null hypothesis $H_{0}: \theta=\theta_{0}$ against the simple alternative hypothesis $H_{1}: \theta=\theta_{1}$.

  What is the form of the optimal size $\alpha$ classical hypothesis test?

  Compare the form of the test with the Bayesian test based on the Bayes factor, and with the Bayes decision rule under the 0-1 loss function, under which a loss of 1 is incurred for an incorrect decision and a loss of 0 is incurred for a correct decision.

  (ii) What does it mean to say that a family of densities $\{f(x ; \theta), \theta \in \Theta\}$ with real scalar parameter $\theta$ is of monotone likelihood ratio?

  Suppose $X$ has a distribution from a family which is of monotone likelihood ratio with respect to a statistic $t(X)$ and that it is required to test $H_{0}: \theta \leqslant \theta_{0}$ against $H_{1}: \theta>\theta_{0}$.

  State, without proof, a theorem which establishes the existence of a uniformly most powerful test and describe in detail the form of the test.

  Let $X_{1}, \ldots, X_{n}$ be independent, identically distributed $U(0, \theta), \theta>0$. Find a uniformly most powerful size $\alpha$ test of $H_{0}: \theta \leqslant \theta_{0}$ against $H_{1}: \theta>\theta_{0}$, and find its power function. Show that we may construct a different, randomised, size $\alpha$ test with the same power function for $\theta \geqslant \theta_{0}$.

  comment

Probability and Measure

• B2.12

  Probability and Measure | Part II, 2002

  Let $\left(X_{n}\right)$ be a sequence of non-negative random variables on a common probability space with $\mathbb{E} X_{n} \leqslant 1$, such that $X_{n} \rightarrow 0$ almost surely. Determine which of the following statements are necessarily true, justifying your answers carefully: (a) $\mathbb{P}\left(X_{n} \geqslant 1\right) \rightarrow 0$ as $n \rightarrow \infty$; (b) $\mathbb{E} X_{n} \rightarrow 0$ as $n \rightarrow \infty$; (c) $\mathbb{E}\left(\sin \left(X_{n}\right)\right) \rightarrow 0$ as $n \rightarrow \infty$; (d) $\mathbb{E}\left(\sqrt{X_{n}}\right) \rightarrow 0$ as $n \rightarrow \infty$.

  [Standard limit theorems for integrals, and results about uniform integrability, may be used without proof provided that they are clearly stated.]

  comment

Quantum Physics

• A2.14

  Quantum Physics | Part II, 2002

  (i) A simple model of a one-dimensional crystal consists of an infinite array of sites equally spaced with separation $a$. An electron occupies the $n$th site with a probability amplitude $c_{n}$. The time-dependent Schrödinger equation governing these amplitudes is

  $$i \hbar \frac{d c_{n}}{d t}=E_{0} c_{n}-A\left(c_{n-1}+c_{n+1}\right)$$

  where $E_{0}$ is the energy of an electron at an isolated site and the amplitude for transition between neighbouring sites is $A>0$. By examining a solution of the form

  $$c_{n}=e^{i k a n-i E t / \hbar}$$

  show that $E$, the energy of the electron in the crystal, lies in a band

  $$E_{0}-2 A \leq E \leq E_{0}+2 A$$

  Identify the Brillouin zone for this model and explain its significance.

  (ii) In the above model the electron is now subject to an electric field $\mathcal{E}$ in the direction of increasing $n$. Given that the charge on the electron is $-e$ write down the norm of the time-dependent Schrödinger equation for the probability amplitudes. Show that it has a solution of the form

  $$c_{n}=\exp \left\{-\frac{i}{\hbar} \int_{0}^{t} \epsilon\left(t^{\prime}\right) d t^{\prime}+i\left(k-\frac{e \mathcal{E} t}{\hbar}\right) n a\right\}$$

  where

  $$\epsilon(t)=E_{0}-2 A \cos \left(\left(k-\frac{e \mathcal{E} t}{\hbar}\right) a\right)$$

  Explain briefly how to interpret this result and use it to show that the dynamical behaviour of an electron near the bottom of the energy band is the same as that for a free particle in the presence of an electric field with an effective mass $m^{*}=\hbar^{2} /\left(2 A a^{2}\right)$.

  comment

Representation Theory

• B2.6

  Representation Theory | Part II, 2002

  State and prove Schur's Lemma. Deduce that the centre of a finite group $G$ with a faithful irreducible complex representation $\rho$ is cyclic and that $Z(\rho(G))$ consists of scalar transformations.

  Let $G$ be the subgroup of order 18 of the symmetric group $S_{6}$ given by

  $$G=\langle(123),(456),(23)(56)\rangle$$

  Show that $G$ has a normal subgroup of order 9 and four normal subgroups of order 3 . By considering quotients, show that $G$ has two representations of dimension 1 and four inequivalent irreducible representations of degree 2 . Deduce that $G$ has no faithful irreducible complex representations.

  Show finally that if $G$ is a finite group with trivial centre and $H$ is a subgroup of $G$ with non-trivial centre, then any faithful representation of $G$ is reducible on restriction to $H$.

  comment

Theoretical Geophysics

• A2.16

  Theoretical Geophysics | Part II, 2002

  (i) State the equations that relate strain to displacement and stress to strain in a linear, isotropic elastic solid.

  In the absence of body forces, the Euler equation for infinitesimal deformations of a solid of density $\rho$ is

  $$\rho \frac{\partial^{2} u_{i}}{\partial t^{2}}=\frac{\partial \sigma_{i j}}{\partial x_{j}}$$

  Derive an equation for $\mathbf{u}(\mathbf{x}, t)$ in a linear, isotropic, homogeneous elastic solid. Hence show that both the dilatation $\theta=\boldsymbol{\nabla} \cdot \mathbf{u}$ and the rotation $\boldsymbol{\omega}=\nabla \wedge \mathbf{u}$ satisfy wave equations and find the corresponding wave speeds $\alpha$ and $\beta$.

  (ii) The ray parameter $p=r \sin i / v$ is constant along seismic rays in a spherically symmetric Earth, where $v(r)$ is the relevant wave speed $(\alpha$ or $\beta)$ and $i(r)$ is the angle between the ray and the local radial direction.

  Express $\tan i$ and sec $i$ in terms of $p$ and the variable $\eta(r)=r / v$. Hence show that the angular distance and travel time between a surface source and receiver, both at radius $R$, are given by

  $$\Delta(p)=2 \int_{r_{m}}^{R} \frac{p}{r} \frac{d r}{\left(\eta^{2}-p^{2}\right)^{1 / 2}} \quad, \quad T(p)=2 \int_{r_{m}}^{R} \frac{\eta^{2}}{r} \frac{d r}{\left(\eta^{2}-p^{2}\right)^{1 / 2}}$$

  where $r_{m}$ is the minimum radius attained by the ray. What is $\eta\left(r_{m}\right)$ ?

  A simple Earth model has a solid mantle in $R / 2<r<R$ and a liquid core in $r<R / 2$. If $\alpha(r)=A / r$ in the mantle, where $A$ is a constant, find $\Delta(p)$ and $T(p)$ for $\mathrm{P}$-arrivals (direct paths lying entirely in the mantle), and show that

  $$T=\frac{R^{2} \sin \Delta}{A}$$

  [You may assume that $\int \frac{d u}{u \sqrt{u-1}}=2 \cos ^{-1}\left(\frac{1}{\sqrt{u}}\right)$.]

  Sketch the $T-\Delta$ curves for $\mathrm{P}$ and $\mathrm{PcP}$ arrivals on the same diagram and explain briefly why they terminate at $\Delta=\cos ^{-1} \frac{1}{4}$.

  comment