Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2

The Euler totient function counts integers $1\le a\le n$ with $\gcd (a,n)=1$. The Möbius function has $\mu (1)=1$, is zero when a prime square divides $n$, and equals $(-1{)}^r$ when $n$ is a product of $r$ distinct primes. Consequentlybecause for $n>1$ the sum over squarefree divisors is $(1-1{)}^r$.

The Möbius inversion formula is $g(n)={\sum }_{d\mid n}\mu (d)f(n/d)$. Substituting the divisor sum defining $f$ and collecting the coefficient of $g(e)$ givesThis proof uses only finite sums, so no convergence hypothesis is needed.

Classifying $1,\dots ,n$ by their greatest common divisor with $n$ gives ${\sum }_{d\mid n}\phi (d)=n$: the class with greatest common divisor $n/d$ contains exactly $\phi (d)$ integers. Applying the Möbius inversion formula yieldsThe Riemann zeta function is $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\mathrm{Re}s>1$. Absolute convergence justifies multiplication of Dirichlet series. The divisor identity for the Möbius function gives $\sum \mu (n)n^{-s}=1/\zeta (s)$ there. For $\mathrm{Re}s>2$ both factors below converge absolutely, and their Dirichlet convolution is the Euler totient function:

A degree-$n$ Legendre polynomial $P_n$ is orthogonal, for integration on $[-1,1]$, to every polynomial of degree at most $n-1$, and has $n$ distinct roots in $(-1,1)$. Divide $p$ by $P_n$:The Orthogonality of Legendre polynomials gives $\int p=\int r$. At every quadrature node $x_j$, $p(x_j)=r(x_j)$. The assumed exactness for $r$ therefore proves exactness up to degree $2n-1$, the characteristic property of Gaussian quadrature.

Use the Lagrange interpolation polynomialIts square has degree $2n-2$, so the exactness already proved givesThe positive weights of Gaussian quadrature follow because ${\ell }_j$ is a nonzero continuous polynomial. Thus these Gaussian quadrature weights are in fact positive, rather than merely nonnegative.

Apply the Gaussian quadrature rule to the constant polynomial $1$. Exactness gives ${\sum }_{j=1}^n{A}_j=2$.

To prove convergence of positive quadrature on continuous functions, for a continuous $f$, the Weierstrass approximation theorem supplies a polynomial $p$ with $\Vert f-p{\Vert }_{\infty }<\epsilon$. For every sufficiently large $n$, the Gaussian quadrature rule is exact for this fixed polynomial. Positivity of its weights and their sum $2$ then giveSince $\epsilon$ is arbitrary, $Q_n(f)\to {\int }_{-1}^{1}f$. Notice that no differentiability of $f$ is needed; uniform polynomial approximation and positivity provide the whole argument.

The Shannon entropy, in bits, isFor a prescribed alphabet distribution and code alphabet, an optimal code is a uniquely decodable code minimizing expected codeword length. Huffman coding produces an optimal binary prefix code, and its minimum is also the minimum among binary uniquely decodable codes.

Two optimal binary prefix codes, listing words in the order $a,b,c,d,e$, areTheir length vectors are $(2,2,2,3,3)$ and $(1,2,3,4,4)$, and both have expected length $2.2$ bits. To verify optimality rather than just equal length, run Huffman coding. First combine $d,e$ into a node of weight $0.2$. Among the resulting three weight-$0.2$ nodes, combining $b,c$ and then combining the remaining weight-$0.2$ node with one weight-$0.4$ node gives the first length vector. Instead combine $c$ with the $d,e$ node, then combine that weight-$0.4$ node with $b$, and finally with $a$; this gives the second. Each step combines two smallest current weights, so both constructions are Huffman coding trees. Ties therefore allow different optimal length profiles.

Writing $y_i$ for the observed counts, independence of the Poisson distributions gives the log-likelihoodIts score function and negative second derivative areUnless all $x_i$ vanish, $J(\beta )>0$, so the log-likelihood is strictly concave. Use Newton method, starting from a finite ${\beta }_0$, withStop when the score function or the change in $\beta$ is small; a reduced step can ensure that the log-likelihood increases. Any finite zero of the score function is the unique maximum-likelihood estimator.

Existence needs a qualification. If the nonzero $x_i$ include both signs, $U$ decreases from $+\infty$ to $-\infty$, so a finite root exists. If all nonzero $x_i$ are positive, a finite root exists exactly when ${\sum }_i{x}_i{y}_i>0$; otherwise the supremum is approached as $\beta \to -\infty$. The corresponding condition for all negative $x_i$ is ${\sum }_i{x}_i{y}_i<0$, with a supremum at $+\infty$ otherwise. When all $x_i=0$, the parameter is unidentifiable. These cases explain when the iterative algorithm actually has a finite estimate to find.

At a positive spatially homogeneous equilibrium point, $v=u^2$ and $2+u-v=0$. Hence $(u,v)=(2,4)$. The reaction Jacobian matrix there isThe two-dimensional Routh-Hurwitz stability criterion gives strict linear asymptotic stability for $a>2$, and instability for $0<a<2$.

For a spatial mode with $s=k^2$, the reaction-diffusion linearization is $J_s=J-\mathrm{diag}(s,ds)$. When $a>2$, its trace is negative for every $s\ge 0$, whileA growing mode exists precisely when this quadratic is negative at some $s>0$. Its minimum must occur at positive $s$, and must be strictly negative, givingWith $z=d/a$, the latter inequality becomes $4z^2-28z+1>0$. Selecting the root compatible with $2d>a$ yields the Turing instability thresholdThe unstable band isOn a bounded domain a boundary condition must permit a mode in this band. Equality at the threshold gives a neutral mode, not positive growth.

At $a=2$, the homogeneous linearization has purely imaginary eigenvalues, so it is not strictly linearly asymptotically stable. If “stable” is read as nonlinear stability, the boundary deserves attention. Put $x=u-2$, $y=(v-4-x)/\sqrt{3}$, and $x=r\cos \theta$, $y=r\sin \theta$. The exact equations give $\dot{r}=r^{2}F(\theta )$, $\dot{\theta }=\omega +rG(\theta )$, where $\omega =2\sqrt{3}$,Expanding $dr/d\theta$ through cubic order, ${\int }_0^{2\pi }F=0$ cancels the quadratic displacement. The correction from the quadratic change in $r$ also integrates to zero, because it is proportional to $(\int F{)}^2$. Since ${\int }_0^{2\pi }FG=\pi /(2\sqrt{3})$, the Poincaré return map isThis cubic return-map stability of a weak focus shows that $a=2$ is a weak attracting focus. The strict linear range used in the Turing instability calculation is $a>2$; the positive homogeneous equilibrium is also nonlinearly asymptotically stable at the boundary $a=2$. For that boundary, $\mathrm{tr}{J}_s=-(1+d)s<0$ for every nonzero spatial mode. The same strict Turing instability threshold and unstable band therefore also apply there, with the homogeneous mode understood through nonlinear stability.

Analytic continuation extends a holomorphic function by holomorphic elements agreeing on overlaps; along a path, a chain of overlapping neighbourhoods transports the initial element. The identity theorem makes compatible continuation unique on connected overlaps, although different paths can lead to different branches.

Choose the principal complex logarithm and the slit domain $D=\mathbb{C}\setminus [1,\infty )$. On $D$, the functionis holomorphic, with the removable value $h(0)=1$. The domain $D$ is simply connected, so $h$ has a primitive and its integral from $0$ to $z$ is independent of the path in $D$. For $|z|<1$, the uniformly convergent power series on compact subdiscs givesTherefore $f$ is a single-valued analytic continuation of the dilogarithm to $\mathbb{C}\setminus [1,\infty )$. The apparent problem at $0$ is removable; $1$ is a genuine branch point, even though the function has a finite one-sided limit there, because its derivative has a logarithmic singularity. Other cuts from $1$ to infinity give corresponding branches.

The two cyclic Euler angles give conserved canonical momentaHere $L_3$ is the body-axis angular momentum and $L_z$ the vertical angular momentum. Thus ${\omega }_3=L_3/I_3$ is constant. Since the Lagrangian has no explicit time dependence, the energy is also conserved:These are the three independent conserved quantities furnished by the continuous symmetries of the heavy symmetric top.

Eliminate the cyclic velocities using $\dot{\varphi }=(L_z-L_3\cos \theta )/(I_1{\sin }^2\theta )$. The conserved energy becomesDifferentiating the effective potential giveswhich is also the $\theta$ Euler-Lagrange equation. Hence $I_1\ddot{\theta }=-V_{\mathrm{eff}}^{\prime }(\theta )$. Deriving it directly from the Euler-Lagrange equation ensures it also holds at turning points, where division by $\dot{\theta }$ in an energy argument would be invalid.

For nonvertical uniform precession of a heavy symmetric top, write $\dot{\varphi }=\Omega$ and fix $\theta$. The $\theta$ Euler-Lagrange equation reduces toFor $\cos \theta \ne 0$ its solutions areFor $0<\theta <\pi /2$, uniform precession therefore requires $|{\omega }_3|\ge 2\sqrt{I_{1}Mgl\cos \theta }/I_3$. For $\pi /2<\theta <\pi$, the discriminant is positive for every spin, including zero. At $\theta =\pi /2$, the condition is $\Omega =Mgl/(I_3{\omega }_3)$, requiring nonzero spin. Once this condition holds, choose $L_z=I_1\Omega {\sin }^2\theta +L_3\cos \theta$ and $\dot{\psi }={\omega }_3-\Omega \cos \theta$; both cyclic equations are then satisfied. The exactly vertical configurations are also solutions for arbitrary spin, but the azimuthal member of the Euler angles is degenerate there, so their existence is separate from this nonvertical discriminant condition.

The flat matter-dominated Friedmann equation gives $\rho =1/(6\pi G{t}^2)$ when $a=t^{2/3}$. With $P=C{\rho }^{4/3}$,For linear density modes with polytropic pressure, substitution gives the Euler-Cauchy equationA power law has exponent satisfying $n(n-1)+4n/3+{\bar{c}}_s^2{k}^2-2/3=0$. Thus, for distinct roots,For $k\ll k_J$, the two modes approach $t^{2/3}$ and $t^{-1}$: gravity produces a growing linear cosmological density perturbation and a decaying mode. For $k\gg k_J$, put $\nu =\sqrt{{\bar{c}}_s^2{k}^2-25/36}$; the real solution isThese are pressure-supported oscillations with a decaying envelope. For the repeated-root cosmological density mode $k=k_J$, the complete solution is $t^{-1/6}(A_k+B_k\log t)$. The specified $k_J=5/(6{\bar{c}}_s)$ separates real exponents from logarithmic oscillations; the growing exponent actually crosses zero at $k=\sqrt{2/3}/{\bar{c}}_s$, a slightly smaller value.

Sperner's lemma says that a triangulated triangle whose vertices are labelled $1,2,3$, with each outer vertex having its own label and each boundary edge using only its endpoint labels, contains a small triangle with all three labels. In fact the number of such triangles is odd. Count incidences of small triangles with edges labelled $1,2$. Interior edges contribute twice. On the outer $1,2$ edge, the number of changes between these labels is odd; the other two outer edges contribute zero. A small triangle contributes one incidence if it has all three labels, two if it uses both $1,2$ but not $3$, and zero otherwise. The total parity proves the assertion.

The resulting no-retraction theorem is: there is no continuous retraction of a closed disc onto its boundary. Work first with a closed triangle $P$. If $r:P\to \partial P$ fixes the boundary, colour each vertex of increasingly fine triangulations by an index of a largest barycentric coordinate of $r(v)$. The largest coordinate is at least $1/3$; on the boundary the colouring satisfies Sperner's lemma. Choose a tricoloured small triangle in each triangulation. By compactness and shrinking mesh, a subsequence of their three vertices converges to one point $x$. Continuity forces all three barycentric coordinates of $r(x)$ to be at least $1/3$, so $r(x)$ is the triangle's centre, contradicting $r(x)\in \partial P$. A homeomorphism of a disc with $P$ proves the disc assertion.

Brouwer fixed-point theorem states that every continuous self-map $F$ of a closed disc has a fixed point. If it had none, the ray from $F(x)$ through $x$ would meet the boundary beyond $x$, continuously in $x$. That intersection defines a retraction, since a boundary point is already the outgoing intersection. This contradicts the no-retraction theorem.

Finally fix $y\in {\mathbb{R}}^2$ and define $F_y(x)=y+x-g(x)$. The displacement bound implies $\Vert F_y(x)-y\Vert \le K$, so $F_y$ maps the closed radius-$K$ disc centred at $y$ into itself. Brouwer fixed-point theorem gives $F_y(x)=x$, which is exactly $g(x)=y$. Since $y$ was arbitrary, $g$ is surjective.

In RSA, choose $N=pq$ with distinct large primes, an exponent $e$ coprime to $\phi (N)$, and $d$ satisfying $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep $d$ secret. Encrypt a residue $m$ as $c=m^e\mathrm{mod}N$ and decrypt by $c^d\mathrm{mod}N$. Fermat's little theorem on each prime and the Chinese remainder theorem prove decryption, including messages not coprime to $N$.

A customer knows a nonzero multiple $M=ed-1$ of $\phi (N)$. Write $M=2^{s}t$ with $t$ odd. Choose a base $a$ at random. A nontrivial $\gcd (a,N)$ already factors $N$. Otherwise compute $a^t,a^{2t},\dots ,a^{2^{s}t}$ modulo $N$. The last entry is $1$. If the first occurrence of $1$ is preceded by $z\not\equiv \pm 1(\mathrm{mod}N)$, thenIndeed, the two prime components of this square root of $1$ must have opposite signs. This procedure succeeds for some bases: by the Chinese remainder theorem, choose a base whose component modulo $p$ has order $2$ and whose component modulo $q$ has order $1$. Its odd $t$-th power is already a nontrivial square root of $1$. Trying bases therefore gives an explicit factoring algorithm, and repeated random choices give the usual efficient attack. More precisely, if the two components' orders have different powers of $2$, the procedure succeeds. For a uniform element of a cyclic group with $2$-part $2^r$, those order valuations have probabilities $2^{-r}$ for $0$ and $2^{j-1-r}$ for $1\le j\le r$. Independence of the two prime components shows that equal valuations have probability at most $1/2$. Thus a random unit succeeds with probability at least $1/2$. Once $N$ is factored, every customer's private exponent is computable. The exceptional $ed=1$ is an identity cipher and is already insecure.

For the outsider's RSA common-modulus attack, find integers $a,b$ with $a{e}_1+b{e}_2=1$ by Bézout's identity. For a unit message,using modular inverses for negative powers. If a ciphertext is a nonzero nonunit, its greatest common divisor with $N$ factors $N$ instead; zero ciphertext corresponds to the zero message for a squarefree modulus. The common message is recoverable without a private key. For a generic unit message this alone does not supply the factorization or all private keys, so it does not demonstrate a complete break for unrelated messages. The nonunit case does give that stronger break.

For $\mathrm{Re}s>1$, expand $(e^t-1{)}^{-1}={\sum }_{n\ge 1}{e}^{-nt}$. Absolute convergence of the integrated series follows from the same expression with $\mathrm{Re}s$ in place of $s$. Integrating termwise and substituting $u=nt$ givesThis proves the Mellin transform representation of the Riemann zeta function.

Take the Hankel contour along the lower side of the negative axis towards zero, around zero counterclockwise, and back along the upper side. For $\mathrm{Re}s>1$ the small-circle contribution tends to zero. On the lower and upper rays, respectively, $\arg t=-\pi ,+\pi$, so the two integrals combine toThe gamma reflection formula now proves agreement of the two representations. At an integer $s=m\ge 2$, the contour integral has a zero while $\Gamma (1-s)$ has a pole: their product is interpreted by its finite limit, equal to $\zeta (m)$, not by multiplying literal zero and infinity.

For nonpositive integers the integrand is single-valued, and the contour closes around zero. Sincethe residue of $t^{-1}/(e^{-t}-1)$ is $-1/2$, giving $\zeta (0)=-1/2$. Alsois odd. Its Laurent series therefore has only odd powers. Multiplication by $t^{-2n-1}$ cannot produce a $t^{-1}$ term, and the subtracted constant cannot do so when $n\ge 1$. Hence the contour integral vanishes and $\zeta (-2n)=0$ for every positive integer $n$.

The canonical momentum is $p=L_{\dot{q}}$, and a regular Legendre transform in mechanics defines $H(q,p,t)=p\dot{q}-L(q,\dot{q},t)$ after solving for $\dot{q}$. Its differential isbecause the $d\dot{q}$ terms cancel. With the Euler-Lagrange equation $\dot{p}=L_q$, this gives Hamilton's equationsIn particular $H_q=-L_q$ at corresponding velocities, so a cyclic coordinate for the Lagrangian is also cyclic for the Hamiltonian.

The canonical momenta are $p_x=m\dot{x}$, $p_y=m\dot{y}+qBx$, $p_z=m\dot{z}$. The Legendre transform in mechanics givesHamilton's equations areThus $\ddot{x}=\Omega \dot{y}$, $\ddot{y}=-\Omega \dot{x}-qE/m$, and $\ddot{z}=0$, where $\Omega =qB/m$. The signs also follow from $\mathbf{E}=-E{\mathbf{e}}_y$ and $\mathbf{B}=B{\mathbf{e}}_z$.

For $Bq\ne 0$, put $v_d=-E/B$, $a=v_{x0}-v_d$, $b=v_{y0}$. The motion isDifferentiation verifies both equations and all initial conditions. The centre of the circular motion has the electric drift velocity $-E{\mathbf{e}}_x/B$. For $B=0$, take $x=x_0+v_{x0}t$, $y=y_0+v_{y0}t-qE{t}^2/(2m)$ and the same $z$. For $q=0$, the particle moves freely.

The recursive definition of ordinal addition is $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ for a nonzero limit ordinal $\lambda$. The synthetic definition is the order type of the ordered disjoint union of a copy of $\alpha$ followed by a copy of $\beta$.

For the synthetic operation, adding the empty order does nothing, adding a successor appends one final point, and concatenation with a limit order is the increasing union of the initial concatenations with all its proper initial segments. Their order types have supremum ${\sup }_{\beta <\lambda }(\alpha +\beta )$. Thus the synthetic operation satisfies the recursive equations. Transfinite induction gives uniqueness of the recursively defined operation, proving equivalence.

The recursive definitions of ordinal multiplication and ordinal exponentiation areThe last equation in each line is for nonzero limit $\lambda$. In particular the convention $0^0=1$ belongs to this recursive definition.

The first assertion is false: $1<2$, but $1+\omega =2+\omega =\omega$. The second is true. In the concatenation definition of ordinal addition, the copy of $\alpha$ is a proper initial segment of the copy of $\beta$ when $\alpha <\beta$, so $\gamma +\alpha$ is a proper initial segment of $\gamma +\beta$.

No. The definition of ordinal exponentiation gives $2^{\omega }={\sup }_n{2}^n=\omega ={\sup }_n{3}^n=3^{\omega }$, although $2<3$.

No such ordinal exists. For $\alpha >1$, ordinal multiplication gives ${\alpha }^2=\alpha \alpha \ge \alpha \cdot 2=\alpha +\alpha >\alpha$. Since ordinal exponentiation is nondecreasing in the exponent for base $\alpha >1$, ${\alpha }^{\omega }\ge {\alpha }^2>\alpha$.

For every countable ordinal $\beta$, ${\omega }^{\beta }$ is countable: successor stages use a countable product, and countable limit stages a countable union. Hence ${\omega }^{{\omega }_1}={\sup }_{\beta <{\omega }_1}{\omega }^{\beta }\le {\omega }_1$. Conversely ${\omega }^{\beta }\ge \beta$ by transfinite induction, so these values are cofinal in ${\omega }_1$. Therefore ${\omega }^{{\omega }_1}={\omega }_1$.

It is not the least fixed point. Set $a_0=1$, $a_{n+1}={\omega }^{a_n}$ and define epsilon zero as ${\epsilon }_0={\sup }_n{a}_n$. This is countable, and continuity of ordinal exponentiation at limits gives ${\omega }^{{\epsilon }_0}={\sup }_n{\omega }^{a_n}={\epsilon }_0$. Any fixed point of $\alpha \mapsto {\omega }^{\alpha }$ dominates every $a_n$ by induction, hence dominates ${\epsilon }_0$. Thus the least fixed point is ${\epsilon }_0<{\omega }_1$.

The graph Ramsey number $R(s,t)$ is the least $N$ for which every graph on $N$ vertices has a clique of size $s$ or an independent set of size $t$; $R(s)=R(s,s)$ is the diagonal Ramsey number. The base cases are $R(2,t)=t$ and $R(s,2)=s$.

Assume the smaller parameters already have finite graph Ramsey numbers, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and

Induction with Pascal's identity gives the binomial upper bound for a Ramsey number $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. Thus $R(s)\le \left(\genfrac{}{}{0ex}{}{2s-2}{s-1}\right)\le 4^{s-1}$, proving $R(s)=O(4^s)$.

For the lower bound, take a binomial random graph $G(n,1/2)$. The expected total number of $s$-cliques and independent $s$-sets isFor $n=\lfloor 2^{s/2}/2\rfloor$, this is at most $2^{1-s/2}/s!<1$ for all sufficiently large $s$. Some graph therefore has neither forbidden set, so $R(s)>n$. This proves $R(s)=\Omega (2^{s/2})$ by the probabilistic method.