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

Write an integral binary quadratic form as $[a,b,c]=a{x}^2+bxy+c{y}^2$. It is positive definite when $a>0$ and its discriminant $D=b^2-4ac$ is negative. Two forms are properly equivalent when one is obtained from the other by a change of variables in ${\mathrm{SL}}_2(\mathbb{Z})$. A reduced positive definite binary quadratic form satisfieswith $b\ge 0$ when $|b|=a$ or $a=c$.

To prove reduction, choose in a proper equivalence class a form whose positive leading coefficient $a$ is minimal. Replacing $x$ by $x+ny$ changes $b$ by $2an$, so choose $n$ to arrange $|b|\le a$. If the resulting $c<a$, the determinant-one substitution $(x,y)\mapsto (-y,x)$ would put $c$ in the leading position, contradicting minimality. Thus $a\le c$. Sign changes on the boundary give the stated convention. Hence every positive definite form is properly equivalent to a reduced one.

A unimodular integral substitution is a bijection of ${\mathbb{Z}}^2$, so properly equivalent forms represent exactly the same integers.

Both given forms have discriminant $-23$. Reduction givesThe two reduced forms represent the same integers becausean integral change of variables of determinant $-1$. They are not properly equivalent: the uniqueness theorem for reduced positive definite forms says that each proper class has one reduced representative, and $[2,1,3]\ne [2,-1,3]$. Therefore the original forms represent the same integers but are not equivalent in the required proper sense.

A set is of first Baire category, or meagre, when it is a countable union of nowhere dense sets. The statement is true: a countable union of countable unions of nowhere dense sets is again a countable union of nowhere dense sets.

The relevant Baire category theorem says that a nonempty complete metric space is not meagre in itself.

False. Fix $y_0\in \mathbb{R}$ and takeThis closed set has empty interior in ${\mathbb{R}}^2$, so it is nowhere dense and hence meagre. Its section at $y_0$ is $C_{y_0}=\mathbb{R}$, which is not meagre in itself by the Baire category theorem.

True. Write $C={\bigcup }_{n\ge 1}{C}_n$ with every $C_n$ nowhere dense in $\mathbb{R}$. ThenThe closure of $C_n\times \mathbb{R}$ is
$\overline{C_n}\times \mathbb{R}$, which has empty interior because $\overline{C_n}$ has empty interior. Each product is therefore nowhere dense, so $A$ is meagre in ${\mathbb{R}}^2$.

False. The coordinate axesare both closed nowhere dense subsets of ${\mathbb{R}}^2$, but every $(x,y)$ is $(x,0)+(0,y)$, sowhich is not meagre by the Baire category theorem.

A discrete memoryless channel has finite input alphabet $\mathcal{A}$, finite output alphabet $\mathcal{B}$, and transition probabilities $P(y\mid x)$; successive outputs are conditionally independent given the corresponding inputs. The Shannon second coding theorem states that rates belowadmit block codes with error probability tending to zero, whereas rates above $C$ cannot have vanishing error.

For any joint input law of $(X_1,X_2)$, conditional independence of the product channel givesChoose $X_1$ and $X_2$ independently with capacity-achieving input laws for their respective channels. Then the inequality becomes equality, so the product-channel capacity is

The pumping lemma for regular languages states that if $L$ is regular, then some $p\ge 1$ has the following property: every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for every $i\ge 0$. Indeed, while a deterministic finite automaton with $p$ states reads the first $p$ symbols, two of the first $p+1$ visited states coincide; the intervening nonempty loop may be traversed any number of times.

The language $\{0^{n^2}1:n\ge 0\}$ is not regular. If its pumping length were $p$, apply the lemma to $w=0^{p^2}1$. The pumped block is $y=0^r$ for some $1\le r\le p$. Pumping once more gives $p^2+r$ zeros, butso their number is not a square.

The language $\{0^n{1}^n:n\ge 0\}$ is not regular. For pumping length $p$, take $0^p{1}^p$. Any permitted pumped block lies entirely among the initial zeros. Pumping it down changes the number of zeros without changing the number of ones, producing a word outside the language and contradicting the pumping lemma.

This language is not regular. If it were regular, its intersection with the regular language $0^{\ast }{1}^{\ast }$ would be regular because regular languages are closed under intersection. That intersection is exactlywhich part (ii) proved nonregular.

A one-parameter exponential family has densitieswith support independent of the natural parameter $\theta$. In the present canonical setting the natural statistic is $T(y)=y$.

Independence gives the joint densityBy the factorization criterion, its dependence on the sample relevant to $\theta$ is only through ${\sum }_i{Y}_i$, equivalently through $\overline{Y}$. Thus $\overline{Y}$ is a sufficient statistic for $\theta$.

The log-likelihood has derivativeDifferentiating the normalizing identity for the family givesHence an interior maximum satisfies, and under nondegeneracy uniquely satisfies,

SetThenThe steady states arewhere the coexistence state is biologically relevant exactly when $\beta >1$.

The Jacobian isFor $\beta >1$, the origin has eigenvalues $\rho ,1$ and is an unstable node. At $(1,0)$ the eigenvalues are $-\rho$ and $1-\beta$, so it is a stable node. At the coexistence state,so it is a saddle.

The nullclines are $x=0$, $x+\alpha y=1$, $y=0$, and $x=1/\beta$. The stable manifold of the coexistence saddle separates trajectories tending to $(1,0)$ from trajectories on which $x\to 0$ and $y$ grows without bound. The coordinate axes are invariant.

There is no stable positive coexistence state: the only one is a saddle for every $\rho ,\alpha >0$ when $\beta >1$. Moreover, the Bendixson-Dulac criterion with Dulac function $B(x,y)=1/(xy)$ applies in the positive quadrant, sinceThus no periodic orbit can support long-term coexistence. Except on the saddle's stable manifold, one species is excluded: species 2 becomes extinct for initial data in the basin of $(1,0)$, ecologically when species 1 is sufficiently abundant and species 2 sufficiently scarce. On the other side, species 1 becomes extinct and the unregulated second species grows.

Choose paths from $0$ to $z$ in the cut plane and deform them continuously with the endpoint, never crossing the specified cut. With $0\le \arg z<2\pi$, use the sheet reached from the positive real axis; when an endpoint is moved into the left half-plane, the path passes around the upper endpoint $i$ of the cut. The cut makes all such admissible paths homotopic with fixed endpoints, so the integral is single valued and its endpoint derivative is $(1+z^2{)}^{-1/2}$; hence it is analytic.

For $z=-\sinh u$, continue the endpoint counterclockwise from the positive real axis through the upper half-plane. Inthe continued square root equals $-\cosh u$ at $z=-\sinh u$. The logarithm is reached with argument $\pi$, and therefore

The identitiesshow directly why continuation without an argument restriction is multivalued. The complete set of values of the multivalued inverse hyperbolic sine at $\sinh u$ is

Order the phase-space coordinates asThen Hamilton's equations areThe Poisson bracket is

For $X=X(x)$ with Jacobian $J_{ab}=\partial X_a/\partial x_b$, the chain rule givesThis has Hamiltonian form with the same canonical matrix for every $H$ exactly whenTaking determinants gives $(\det J{)}^2=1$; the symplectic condition fixes the orientation, so $\det J=1$. Hence the change-of-variables formula shows that the phase-space volume element is invariant. This is Liouville theorem in Hamiltonian mechanics.

By the shell theorem, only the mass inside the particle's radius contributes:The conserved Newtonian energy per unit particle mass isWriting $r=a(t)r_0$ and using conservation of enclosed mass, so that $\rho a^3$ is constant, givesThis is the first Friedmann equation without a cosmological constant.

The derivation has two central defects. It uses instantaneous Newtonian gravity and omits the relativistic gravitational effect of pressure, so it is not valid for general cosmological matter. It also starts from a finite ball with a preferred centre and boundary, contrary to exact homogeneity and isotropy; the assumption $r\ll L$ only hides that defect locally.

In the BB84 protocol, Alice independently chooses $n$ random bits and, for each bit, a random computational or Hadamard basis. She sends the corresponding states $|0⟩,|1⟩,|+⟩,|-⟩$ through the noiseless quantum channel. Bob independently chooses one of the two bases for each qubit and measures. Over the public classical channel they reveal only their basis choices and retain positions where the choices agree. Each position survives with probability $1/2$, so the expected secret-key length is $n/2$. In the ideal no-eavesdropper setting their retained bits agree exactly.

The controlled-NOT leaves computational-basis signals unentangled:For the two Hadamard-basis choices it givesBoth outputs are maximally entangled Bell states.

Conditioned on a sifted-key position, Alice and Bob used the computational basis with probability $1/2$ and the Hadamard basis with probability $1/2$. Eve causes no error in the computational basis. In the Hadamard basis Bob's reduced state is maximally mixed, so his bit is wrong with probability $1/2$. The final bit-error rate is therefore

Let $X\sim \mathrm{Bin}(n,t)$ and $Y\sim \mathrm{Bin}(n,s)$ be independent. The displayed Bernstein polynomial isGiven $\epsilon >0$, uniform continuity of $f$ supplies $\delta >0$ such that changing both coordinates by less than $\delta$ changes $f$ by less than $\epsilon$. If $M=\Vert f{\Vert }_{\infty }$, then Chebyshev inequality and
$\mathrm{Var}(X/n),\mathrm{Var}(Y/n)\le 1/(4n)$ give, uniformly in $(t,s)$,Thus $B_{n}f\to f$ uniformly.

Each $B_{n}f$ is a polynomial, whose iterated integrals may be interchanged term by term. Uniform convergence permits passage to the limit in both iterated integrals, proving the asserted continuous-function form of Fubini's theorem.

Now suppose every monomial moment of $f$ vanishes. By linearity,
$\int \int pf=0$ for every two-variable polynomial $p$. The just-proved Bernstein approximation gives polynomials $p_n\to f$ uniformly. Thereforeso $\boxed{f=0}$. Statement (i) is true.

True. An affine change of variables carries $[a,b{]}^2$ to $[0,1{]}^2$. Equivalently, polynomials in $s,t$ are uniformly dense on $[a,b{]}^2$ by the rescaled Bernstein construction. The moment assumptions annihilate every polynomial, so approximating $f$ itself again gives $\int f^2=0$ and hence $f=0$.

False. Take $f(s,t)=s$. Then $s^{2n}{t}^{2m}f(s,t)$ is odd in $s$, so every stated integral over $[-1,1{]}^2$ vanishes, although $f$ is not zero.

True. The map $(s,t)\mapsto (s^2,t^2)$ is a homeomorphism of $[0,1{]}^2$. Hence every continuous $f(s,t)$ can be written as $g(s^2,t^2)$ for continuous
$g(u,v)=f(\sqrt{u},\sqrt{v})$. Bernstein polynomials approximate $g(u,v)$ uniformly, so polynomials in $s^2,t^2$ approximate $f$ uniformly. The assumed even moments annihilate all such polynomials; approximating $f$ and passing to $\int f^2$ proves $f=0$.

In the Rabin cryptosystem, the public key is $N=pq$ and encryption sends an encoded message $m$ toKnowing $p,q$, the receiver finds the two square roots modulo each prime and combines them with the Chinese remainder theorem to obtain four roots modulo $N$; prescribed redundancy identifies the intended one.

Omicron hasThe Chinese remainder theorem determines $m^2$ uniquely modulo $N{N}^{\prime }$ (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since $1\le m<N<N^{\prime }$, one has $m^2<N{N}^{\prime }$, so this residue is the ordinary integer $m^2$. Taking its positive integer square root recovers $m$.

This does not normally decrypt another ciphertext sent under only one modulus. The recovered pair reveals no nontrivial square root collision modulo that modulus and hence supplies no factorization; breaking a single Rabin instance remains equivalent to factoring its modulus.

The discrete logarithm problem asks, given $g$ and $h\equiv g^a(\mathrm{mod}p)$, to recover $a$ modulo $p-1$. In the Diffie-Hellman key exchange, Alice sends $g^a$, Bob sends $g^b$, and both compute $g^{ab}$. An enemy able to compute discrete logarithms recovers $a$ or $b$ from the public messages and hence obtains the key.

For three participants with private exponents $a,b,c$, circulate three tokens around a directed ring. Start with $g^a,g^b,g^c$; whenever a participant receives a token, they raise it to their private exponent and pass it on. Arrange the three cyclic routes so that after two transmissions each participant receives one token to which all three exponents have been applied. Every participant then haswhile the public transcript contains only proper subproducts.

For $n$ participants, start token $g^{a_i}$ at participant $i$ and pass it successively through the other $n-1$ participants in cyclic order, each raising it to their exponent. Choose the cyclic starts so that one completed token ends at each participant. Every final token equalsThere are $n$ tokens and $n-1$ transmissions per token, for exactlycommunications. Security rests on the corresponding generalized Diffie--Hellman problem.

Substitution ofand integration by parts giveThus takeand require the endpoint term to vanish. Infinite contour ends must lie in sectors where $\mathrm{Re}(t^4)>0$, namely sectors centred on the positive and negative real and imaginary axes, each of angular width $\pi /4$.

Let the common final segment be the positive real ray from $0$ to $+\infty$, and choose the initial rays from $-\infty$, $+i\infty$, and $-i\infty$ to $0$. Call the resulting contours ${\gamma }_1,{\gamma }_2,{\gamma }_3$. PutSince $w_i^{(r)}(0)={\int }_{{\gamma }_i}{t}^r{e}^{-t^4/4}dt$, for $r=0,1,2$ the three rows areConsequentlyUsing the Gamma function reflection identity,The initial-data vectors are therefore linearly independent, so the three contour integrals are linearly independent solutions.

Scale the unit ball by $(u,v,w)\mapsto (au,bv,cw)$. Symmetry makes all products of inertia vanish, while the unit-ball averages satisfy
$⟨u^2⟩=⟨v^2⟩=⟨w^2⟩=1/5$. The inertia tensor about the centre is therefore

For torque-free motion, the inertial angular momentum $\mathbf{L}=I\mathbf{\omega }$ and energy
$T=\frac{1}{2}\mathbf{\omega }\cdot I\mathbf{\omega }$ are constant. Consider the energy ellipsoidwhich is fixed in the body. At its point $\mathbf{x}=\mathbf{\omega }$, its normal is
$I\mathbf{\omega }=\mathbf{L}$, and its tangent plane isThis plane has fixed normal and fixed distance $2T/|\mathbf{L}|$ from the origin, so it is the invariable plane. The material velocity of the contact vector is
$\mathbf{\omega }\times \mathbf{\omega }=0$. Thus the contact point is instantaneously at rest and the ellipsoid rolls without slipping on the plane. This is the Poinsot construction.

When $a=b<c$, the ellipsoid is an axisymmetric rigid body withThe angle between its symmetry axis and the fixed angular momentum is constant. In an inertial frame the symmetry axis precesses uniformly around $\mathbf{L}$, while the body simultaneously spins about that axis. The angular-velocity vector also traces a circular cone about $\mathbf{L}$. The limiting cases are pure rotation about the symmetry axis and pure rotation about a perpendicular principal axis.

A Bell measurement is the projective measurement of two qubits in the orthonormal Bell state basisIts four classical outcomes identify the corresponding rank-one projector.

Alice holds the unknown input $|\alpha ⟩$ and one qubit of a shared $|{\varphi }^{+}⟩$ pair; Bob holds the other. Alice performs a Bell measurement on her two qubits and sends its two-bit outcome to Bob. For outcomes
${\varphi }^{+},{\varphi }^{-},{\psi }^{+},{\psi }^{-}$, Bob's qubit is respectivelyup to global phase. Bob applies respectively $I,Z,X,ZX$ and obtains $|\alpha ⟩$. This is quantum teleportation.

Replacing the resource by $(I\otimes U)|{\varphi }^{+}⟩$ applies $U$ to Bob's uncorrected output. If $P\in \{I,Z,X,XZ\}$ labels the Bell outcome, the uncorrected state is $UP|\alpha ⟩$, and the unchanged correction producesThus the four outputs are $U|\alpha ⟩$, $ZUZ|\alpha ⟩$, $XUX|\alpha ⟩$, and $(XZ{)}^{-1}U(XZ)|\alpha ⟩$, up to global phases.

For two nonorthogonal input states $|\alpha ⟩,|\beta ⟩$, preservation of inner products by $G$ givesHence the two output-program states agree up to phase. Any two qubit states can be joined through a state nonorthogonal to both, so after absorbing phases
$|{\tilde{P}}_U⟩$ is independent of the input.

Inner-product preservation between programs for $U$ and $V$ givesfor all $|\alpha ⟩,|\beta ⟩$. If $⟨P_U|P_V⟩\ne 0$, this identity forces every matrix element of $U^{†}V$ to be the same scalar multiple of the corresponding identity matrix element. Hence $U^{†}V=e^{i\theta }I$, contrary to physical distinctness. Therefore