MATHEMATICAL TRIPOS Part II Friday 8 June 2007 9 to 12 PAPER 4 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. Candidates may attempt at most six questions from Section I and any number of questions from Section II. Complete answers are preferred to fragments. 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 gold cover sheet to each bundle; write the code letter in the box marked ‘EXAMINER LETTER’ on the cover sheet. 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 You may not start to read the questions printed on the subsequent pages until instructed to do so by the Invigilator.2 SECTION I 1F Number Theory Prove Legendre’s formula relating (x) and (px) for any positive real number x. Use this formula to compute (48). 2F Topics in Analysis State Brouwer’s fixed point theorem for a triangle in two dimensions. Let A = (aij) be a 3 × 3 matrix with real positive entries and such that all its columns are non-zero vectors. Show that A has an eigenvector with positive entries. 3G Geometry of Group Actions Let be a circle on the Riemann sphere. Explain what it means to say that two points of the sphere are inverse points for the circle . Show that, for each point z on the Riemann sphere, there is a unique point z0 with z, z0 inverse points. Define inversion in . Prove that the composition of an even number of inversions is a M¨obius transformattion 4G Coding and Cryptography What is a linear feedback shift register? Explain the Berlekamp–Massey method for recovering the feedback polynomial of a linear feedback shift register from its output. Illustrate in the case when we observe output 1 0 1 0 1 1 0 0 1 0 0 0 . . . . Paper 43 5I Statistical Modelling Consider the normal linear model Y = X+ " in vector notation, where Y = 0@ Y1 ...Yn1A, X = 0B@ xT1...xTn 1CA, = 0B@ 1 ...p1CA, " = 0@ "1 ..."n1A, "i i.i.d. N(0, 2), where xTi = (xi1, . . . , xip) is known and X is of full rank (p < n). Give expressions for maximum likelihood estimators ˆ and ˆ2 of and 2 respectively, and state their joint distribution. Suppose that there is a new pair (x, y), independent of (x1, y1), . . . , (xn, yn), satisfying the relationship y= xT+ ", where "N(0, 2). We suppose that xis known, and estimate yby ˜y = xT ˆ . State the distribution of ˜y − y˜, where ˜2 = n n − p ˆ2 and 2 = xT(XTX)−1x+ 1. Find the form of a (1 − )–level prediction interval for y. 6B Mathematical Biology The non-dimensional equations for two competing populations are du dt = u(1 − ) − 1u2, ddt = (1 − u) − 22. Explain the meaning of each term in these equations. Find all the fixed points of this system when > 0, 0 < 1 < 1 and 0 < 2 < 1, and investigate their stability. Paper 4 [TURN OVER4 7E Dynamical Systems By considering the binary representation of the sawtooth map, F(x) = 2x [mod 1] for x 2 [0, 1), show that: (i) F has sensitive dependence on initial conditions on [0, 1). (ii) F has topological transitivity on [0, 1). (iii) Periodic points are dense in [0, 1). Find all the 4-cycles of F and express them as fractions. 8B Further Complex Methods The hypergeometric function F(a, b; c; z) is defined by F(a, b; c; z) = K Z 1 0 tb−1(1 − t)c−b−1(1 − tz)−adt where |arg(1 −tz)| < and K is a constant determined by the condition F(a, b; c; 0) = 1. (i) Express K in terms of Gamma functions. (ii) By considering the nth derivative F(n)(a, b; c; 0), show that F(a, b; c; z) = F(b, a; c; z). Paper 45 9C Classical Dynamics (a) Show that the principal moments of inertia for the oblate spheroid of mass M defined by (x21 + x22 ) a2 + x23 a2(1 − e2) 6 1 are given by (I1, I2, I3) = 25Ma2 (1 − 12 e2, 1 − 12 e2, 1). Here a is the semi-major axis and e is the eccentricity. [You may assume that a sphere of radius a has principal moments of inertia 25Ma2.] (b) The spheroid in part (a) rotates about an axis that is not a principal axis. Euler’s equations governing the angular velocity (!1, !2, !3) as viewed in the body frame are I1 d!1 dt = (I2 − I3)!2!3 , I2 d!2 dt = (I3 − I1)!3!1 , and I3 d!3 dt = (I1 − I2)!1!2 . Show that !3 is constant. Show further that the angular momentum vector precesses around the x3 axis with period P = 2(2 − e2) e2!3 . Paper 4 [TURN OVER6 10A Cosmology The equation governing density perturbation modes k(t) in a matter-dominated universe (with a(t) = (t/t0)2/3) is ¨k + 2 ˙aa ˙k − 32 ˙aa2 k = 0 , where k is the comoving wavevector. Find the general solution for the perturbation, showing that there is a growing mode such that k(t) a(t) a(ti) k(ti) (t ti) . Show that the physical wavelength corresponding to the comoving wavenumber k = |k| crosses the Hubble radius cH−1 at a time tk given by tk t0 = k0 k 3 , where k0 = 2cH−1 0 . According to inflationary theory, the amplitude of the variance at horizon-crossing is constant, that is, h|k(tk)|2i = AV −1/k3 where A and V (the volume) are constants. Given this amplitude and the results obtained above, deduce that the power spectrum today takes the form P(k) V h|k(t0)|2i = Ak40 k . Paper 47 SECTION II 11F Number Theory Let p be a prime number, and let f(x) be a polynomial with integer coefficients, whose leading coefficient is not divisible by p. Prove that the congruence f(x) 0 (mod p) has at most d solutions, where d is the degree of f(x). Deduce that all coefficients of the polynomial xp−1 − 1 − (x − 1)(x − 2) · · · (x − p + 1)must be divisible by p, and prove that: (i) (p − 1)! + 1 0 (mod p); (ii) if p is odd, the numerator of the fraction up = 1 + 12 + · · · + 1 p − 1 is divisible by p. Assume now that p > 5. Show by example that (i) cannot be strengthened to (p − 1)! + 1 0 (mod p2). 12G Geometry of Group Actions Explain what it means to say that a group G is a Kleinian group. What is the definition of the limit set for the group G? Prove that a fixed point of a parabolic element in G must lie in the limit set. Show that the matrix 1 + aw −aw2 a 1 − aw represents a parabolic transformation for any non-zero choice of the complex numbers a and w. Find its fixed point. The Gaussian integers are Z[i] = {m+ in : m, n 2 Z}. Let G be the set of M¨obius transformations z 7! az + b cz + d with a, b, c, d 2 Z[i] and ad − bc = 1. Prove that G is a Kleinian group. For each point w = p + iq r with p, q, r non-zero integers, find a parabolic transformation T 2 G that fixes w. Deduce that the limit set for G is all of the Riemann sphere. Paper 4 [TURN OVER8 13I Statistical Modelling Let Y have a Gamma distribution with density f(y; , ) = y−1 () e−y . Show that the Gamma distribution is of exponential dispersion family form. Deduce directly the corresponding expressions for E[Y ] and Var[Y ] in terms of and . What is the canonical link function? Let p < n. Consider a generalised linear model (g.l.m.) for responses yi, i = 1, . . . , n with random component defined by the Gamma distribution with canonical link g(µ), so that g(µi) = i = xTi , where = (1, . . . , p)T is the vector of unknown regression coefficients and xi = (xi1, . . . , xip)T is the vector of known values of the explanatory variables for the ith observation, i = 1, . . . , n. Obtain expressions for the score function and Fisher information matrix and explain how these can be used in order to approximate ˆ , the maximum likelihood estimator (m.l.e.) of . [Use the canonical link function and assume that the dispersion parameter is known.] Finally, obtain an expression for the deviance for a comparison of the full (saturaated model to the g.l.m. with canonical link using the m.l.e. ˆ (or estimated mean ˆµ = X ˆ ). Paper 49 14E Dynamical Systems Consider the one-dimensional map F : R ! R defined by xi+1 = F(xi) = xi(ax2i + bxi + µ), where a and b are constants, µ is a parameter and a 6= 0. (i) Find the fixed points of F and determine the linear stability of x = 0. Hence show that there are bifurcations at µ = 1, at µ = −1 and, if b 6= 0, at µ = 1 + b2/4a. Sketch the bifurcation diagram for each of the cases: (1) a > b = 0, (2) a, b > 0 and (3) a, b < 0. In each case show the locus and stability of the fixed points in the (µ, x)-plane, and state the type of each bifurcation. [Assume that there are no further bifurcations in the region sketched.] (ii) For the case F(x) = x(µ − x2) (i.e. a = −1, b = 0), you may assume that F2(x) = x + x(µ − 1 − x2)(µ + 1 − x2)(1 − µx2 + x4) . Show that there are at most three 2-cycles and determine when they exist. By considering F0(xi)F0(xi+1), or otherwise, show further that one 2-cycle is always unstable when it exists and that the others are unstable when µ > p5. Sketch the bifurcation diagram showing the locus and stability of the fixed points and 2-cycles. State briefly what you would expect to occur in the region µ > p5. Paper 4 [TURN OVER10 15C Classical Dynamics The Hamiltonian for an oscillating particle with one degree of freedom is H = p2 2m + V (q, ) . The mass m is a constant, and is a function of time t alone. Write down Hamilton’s equations and use them to show thatdH dt = @H @ddt . Now consider a case in which is constant and the oscillation is exactly periodic. Denote the constant value of H in that case by E. Consider the quantity I = (2)−1 H p dq, where the integral is taken over a single oscillation cycle. For any given function V (q, ) show that I can be expressed as a function of E and alone, namely I = I(E, ) = (2m)1/2 2I E − V (q, ) 1/2 dq , where the sign of the integrand alternates between the two halves of the oscillation cycle. Let be the period of oscillation. Show that the function I(E, ) has partial derivatives @ I @E = 2and @ I @= − 1 2I @V @dt . You may assume without proof that @/@E and @/@may be taken inside the integral. Now let change very slowly with time t , by a negligible amount during an oscillation cycle. Assuming that, to sufficient approximation, dhHi dt = @hHi @ddt where hHi is the average value of H over an oscillation cycle, and that d I dt = @ I @E dhHi dt + @ I @ddt , deduce that d I/dt = 0 , carefully explaining your reasoning. When V (q, ) = q2n with n a positive integer and positive, deduce that hHi = C1/(n+1) for slowly-varying , where C is a constant. [Do not try to solve Hamilton’s equations. Rather, consider the form taken by I. ] Paper 411 16G Set Theory and Logic Explain what is meant by a well-founded binary relation on a set. Given a set a, we say that a mapping f : a ! Pa is recursive if, given any set b equipped with a mapping g : Pb ! b, there exists a unique h: a ! b such that h = ghf, where h: Pa ! Pb denotes the mapping a0 7! {h(x) | x 2 a0}. Show that f is recursive if and only if the relation {hx, yi | x 2 f(y)} is well-founded. [If you need to use any form of the recursion theorem, you should prove it.] 17H Graph Theory Let G be a graph with n vertices and m edges. Show that if G contains no C4, then m 6 n4 (1 + p4n − 3). Let C4(G) denote the number of subgraphs of G isomorphic to C4. Show that if m > n(n−1) 4 , then G contains at least n(n−1)(n−3) 8 paths of length 2. By considering the numbers r1, r2, . . . , r(n2 ) of vertices joined to each pair of vertices of G, deduce that C4(G) > 12n2(n − 3)/4 2 . Now let G = G(n, 1/2) be the random graph on {1, 2, . . . , n} in which each pair of vertices is joined independently with probability 1/2. Find the expectation E(C4(G)) of C4(G). Deduce that if 0 < < 1/2, then PrC4(G) 6 (1 + 2) 3 16n4> . 18F Galois Theory Let f(x) 2 K[x] be a monic polynomial, L a splitting field for f, 1, . . . , n the roots of f in L. Let 4(f) = Qi K , 0 if ST 6 K . It can be interpreted as a bet that the stock will be worth at least K at time T. Find a formula for its value at time t, in terms of the spot price St . Find a formula for its Delta (i.e. its hedge ratio). How does the Delta behave as t ! T ? Why is it difficult, in practice, to hedge such an instrument? 29I Optimization and Control Consider the scalar controllable linear system, whose state Xn evolves by Xn+1 = Xn + Un + "n+1, with observations Yn given by Yn+1 = Xn + n+1. Here, Un is the control variable, which is to be determined on the basis of the observations up to time n, and "n, n are independent N(0, 1) random variables. You wish to minimize the long-run average expected cost, where the instantaneous cost at time n is X2n + U2n. You may assume that the optimal control in equilibrium has the form Un = −K ˆXn, where ˆXn is given by a recursion of the form ˆXn+1 = ˆXn + Un + H(Yn+1 − ˆXn), and where H is chosen so that n = Xn − ˆXn is independent of the observations up to time n. Show that K = H = (p5 − 1)/2 = 2/(p5 + 1), and determine the minimal long-run average expected cost. You are not expected to simplify the arithmetic form of your answer but should show clearly how you have obtained it. Paper 417 30A Partial Differential Equations State and prove the mean value property for harmonic functions on R3. Obtain a generalization of the mean value property for sub-harmonic functions on R3, i.e. C2 functions for which −u(x) 6 0 for all x 2 R3. Let 2 C2(R3;C) solve the equation −+ iV (x)= 0 , where V is a real-valued continuous function. By considering the function w(x) = |(x)|2 show that, on any ball B(y,R) = {x : kx − yk < R} R3, sup x2B(y,R) |(x)| 6 sup kx−yk=R |(x)|. Paper 4 [TURN OVER18 31B Asymptotic Methods Consider the time-independent Schr¨odinger equation d2 dx2 + 2q(x) (x) = 0, where 1 denotes ~−1 and q(x) denotes 2m[E − V (x)]. Suppose that q(x) > 0 for a < x < b, and q(x) < 0 for −1 < x < a and b < x < 1 and consider a bound state (x). Write down the possible Liouville–Green approximate solutions for (x) in each region, given that ! 0 as |x| ! 1. Assume that q(x) may be approximated by q0(a)(x−a) near x = a, where q0(a) > 0, and by q0(b)(x − b) near x = b, where q0(b) < 0. The Airy function Ai(z) satisfies d2(Ai) dz2 − z(Ai) = 0 and has the asymptotic expansions Ai(z) 12−1/2z−1/4 exp−23z3/2as z ! +1, and Ai(z) −1/2|z|−1/4 cos 23|z|3/2− 4 as z ! −1. Deduce that the energies E of bound states are given approximately by the WKB condition: Z b a q1/2(x) dx = n + 12 (n = 0, 1, 2, . . .). Paper 419 32D Principles of Quantum Mechanics The Hamiltonian for a particle of spin 12 in a magnetic field B is H = −12~B · where x = 0 1 1 0, y = 0 −i i 0 , z = 1 0 0 −1, and is a constant (the motion of the particle in space can be ignored). Consider a magnetic field which is independent of time. Writing B = Bn, where n is a unit vector, calculate the time evolution operator and show that if the particle is initially in a state |i the probability of measuring it to be in an orthogonal state |0i after a time t is | h0|n · |i |2 sin2 Bt 2 . Evaluate this to find the probability for a transition from a state of spin up along the z direction to one of spin down along the z direction when B = (Bx, 0,Bz). Now consider a magnetic field whose x and y components are time-dependent but small: B = (Acos t, Asin t, Bz ) . Show that the probability for a transition from a spin-up state at time zero to a spin-down state at time t (with spin measured along the z direction, as before) is approximately A Bz+2 sin2 (Bz+)t 2 , where you may assume |A| << |Bz+−1| . Comment on how this compares, when = 0, with the result for a time-independent field. [The first-order transition amplitude due to a perturbation V (t) is − i~ Z t 0 dt0ei(E0−E)t0/~h0|V (t0)|i where |i and |0i are orthogonal eigenstates of the unperturbed Hamiltonian with eigenvalues E and E0 respectively. ] Paper 4 [TURN OVER20 33A Applications of Quantum Mechanics Consider a 1-dimensional chain of 2N atoms of mass m (with N large and with periodic boundary conditions). The interactions between neighbouring atoms are modelled by springs with alternating spring constants K and G, with K > G. K G K G K G m m m m m In equilibrium, the separation of the atoms is a, the natural length of the springs. Find the frequencies of the longitudinal modes of vibration for this system, and show that they are labelled by a wavenumber q that is restricted to a Brillouin zone. Identify the acoustic and optical bands of the vibration spectrum, and determine approximations for the frequencies near the centre of the Brillouin zone. What is the frequency gap between the acoustic and optical bands at the zone boundary? Describe briefly the properties of the phonons in this system. 34D Statistical Physics Consider a classical gas of diatomic molecules whose orientation is fixed by a strong magnetic field. The molecules are not free to rotate, but they are free to vibrate. Assuming that the vibrations are approximately harmonic, calculate the contribution to the partition function due to vibrations. Evaluate the free energy F = −kT lnZ, where Z is the total partition function for the gas, and hence calculate the entropy. [Note that R1−1 exp(−au2)du = p/a and R10 u2 exp(−au2)du = p/4a3/2. You may approximate lnN! by N lnN − N.] Paper 421 35E Electrodynamics An action S['] = Z d4xL(', ',a) is given, where '(x) is a scalar field. Explain heuristically how to compute the functional derivative S/'. Consider the action for electromagnetism, S[Aa] = −Z d4x 1 4µ0 FabFab + JaAa. Here Ja is the 4-current density, Aa is the 4-potential and Fab = Ab,a−Aa,b is the Maxwell field tensor. Obtain Maxwell’s equations in 4-vector form. Another action that is sometimes suggested is bS[Aa] = −Z d4x 1 2µ0Aa,bAa,b + JaAa. Under which additional assumption can Maxwell’s equations be obtained using this action? Using this additional assumption establish the relationship between the actions S and bS. Paper 4 [TURN OVER22 36A General Relativity Consider a particle on a trajectory xa(). Show that the geodesic equations, with affine parameter , coincide with the variational equations obtained by varying the integral I = Z 1 0 gab(x)dxa ddxb dd, the end-points being fixed. In the case that f(r) = 1 − 2GMu, show that the space-time metric is given in the form ds2 = −f(r) dt2 + 1 f(r) dr2 + r2(d2 + sin2 d2) , for a certain function f(r). Assuming the particle motion takes place in the plane = 2 show that dd= h r2 , dt d= E f(r) , for h,E constants. Writing u = 1/r, obtain the equation du d2 + f(r) u2 = − k h2 f(r) + E2 h2 , where k can be chosen to be 1 or 0, according to whether the particle is massive or massless. In the case that f(r) = 1 − GMu, show that d2u d2 + u = k GM h2 + 3GMu2 . In the massive case, show that there is an approximate solution of the form u = 1` 1 + e cos (), where 1 − = 3GM ` . What is the interpretation of this solution? Paper 423 37B Fluid Dynamics II (i) Assuming that axisymmetric incompressible flow u = (uR, u, 0), with vorticity (0, 0, !) in spherical polar coordinates (R, , ) satisfies the equations u = r × 0, 0, Rsin , ! = − 1 Rsin D2, where D2 @2 @R2 + sinR2 @ @1 sin@ @, show that for Stokes flow satisfies the equation D4= 0. () (ii) A rigid sphere of radius a moves at velocity Uˆz through viscous fluid of density and dynamic viscosity µ which is at rest at infinity. Assuming Stokes flow and by applying the boundary conditions at R = a and as R ! 1, verify that = (AR+B/R) sin2 is the appropriate solution to () for this flow, where A and B are to be determined. (iii) Hence find the velocity field outside the sphere. Without direct calculation, explain why the drag is in the z direction and has magnitude proportional to U. (iv) A second identical sphere is introduced into the flow, at a distance b a from the first, and moving at the same velocity. Justify the assertion that, when the two spheres are at the same height, or when one is vertically above the other, the drag on each sphere is the same. Calculate the leading correction to the drag in each case, to leading order in a/b. [You may quote without proof the fact that, for an axisymmetric function F(R, ), r × (0, 0, F) = 1 Rsin @ @(sin F), − 1R @ @R(RF), 0in spherical polar coordinates (R, , ).] Paper 4 [TURN OVER24 38C Waves Show that, for a plane acoustic wave, the acoustic intensity ˜p u may be written as 0c0|u|2ˆkin the standard notation. Derive the general spherically-symmetric solution of the wave equation. Use it to find the velocity potential (r, t) for waves radiated into an unbounded fluid by a pulsating sphere of radius a (1 + " ei!t) (" 1) . By considering the far field, or otherwise, find the time-average rate at which energy is radiated by the sphere. You may assume that r2= 1 r2 @ @r r2 @@r . 39C Numerical Analysis (a) Suppose that A is a real n × n matrix, and that w 2 Rn and 1 2 R are given so that Aw = 1w. Further, let S be a non-singular matrix such that Sw = ce(1), where e(1) is the first coordinate vector and c 6= 0. Let bA = SAS−1. Prove that the eigenvalues of A are 1 together with the eigenvalues of the bottom right (n − 1) × (n − 1) submatrix of bA. (b) Suppose again that A is a real n × n matrix, and that two linearly independent vectors v,w 2 Rn are given such that the linear subspace L{v,w} spanned by v and w is invariant under the action of A, i.e., x 2 L{v,w} ) Ax 2 L{v,w}. Denote by V an n × 2 matrix whose two columns are the vectors v and w, and let S be a non-singular matrix such that R = SV is upper triangular, that is, R = SV = S × 26664 v1 w1 v2 w2 v3 w3 : : vn wn 37775= 26664 r11 r12 0 r22 0 0 : : 0 0 37775. Again let bA = SAS−1. Prove that the eigenvalues of A are the eigenvalues of the top left 2 × 2 submatrix of bA together with the eigenvalues of the bottom right (n − 2) × (n − 2) submatrix of bA. END OF PAPER Paper 4