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

For an odd prime $p$, the Legendre symbol isGauss lemma says that if $p\nmid a$ and $N$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, none of $2,4,\dots ,p-1$ needs reduction modulo $p$, and the terms exceeding $p/2$ are those with $j>p/4$. HenceChecking $p\equiv 1,3,5,7(\mathrm{mod}8)$ shows that $N$ has the same parity as $(p^2-1)/8$. Therefore

By quadratic reciprocity, and because $149\equiv 1(\mathrm{mod}4)$,The three factors are $-1,1,1$, respectively, so

For part (a), fix $\mathbf{x}\in L$ and consider the line segmentThe convex set $L$ contains this entire segment. Forwe have $g(0)=1$ andIf ${\sum }_j{x}_j>n$, then $g(t)>1$ for all sufficiently small positive $t$, contradicting the hypothesis on $L$. Thus

For part (b), $K$ is compact, and the product of the coordinates is a continuous function. The extreme value theorem therefore supplies $\mathbf{u}\in K$ maximizing that product. Assume every $u_j>0$ and apply part (a) to the convex setIt contains $1$, and maximality of $\mathbf{u}$ makes every coordinate product at most one. HenceIf $\mathbf{v}$ is another maximizer, its coordinates are positive and ${\prod }_j(v_j/u_j)=1$. The arithmetic-geometric mean inequality giveswhile the displayed inequality gives the reverse bound. Equality in the arithmetic-geometric mean inequality forces every $v_j/u_j=1$. Therefore the maximizer $\mathbf{u}$ is unique.

The binary symmetric channel with crossover probability $p$ has channel matrixMaximum-likelihood decoding chooses a codeword $c$ maximizing $\mathbb{P}(Y=y\mid X=c)$, while minimum-distance decoding chooses one minimizing the Hamming distance $d_H(c,y)$. For a block of length $n$ sent through a binary symmetric channel,When $p<1/2$, the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.

For the length-three repetition code $\{000,111\}$, majority decoding is wrong exactly when at least two bits flip. Therefore

For a set $S\subseteq Q_E$, let $E(S)$ be its epsilon closure, and putThe subset construction with epsilon transitions gives the deterministic finite automatonUnreachable subsets may be deleted from $Q_D$ without changing the recognized language.

Let ${\hat{\delta }}_E(q_0,w)$ mean all states reachable after reading $w$, allowing arbitrary epsilon transitions before, between, and after its symbols. We prove by mathematical induction on $|w|$ thatFor $w=ϵ$, both sides equal $E(\{q_0\})=q_D$. Suppose the claim holds for $w$, and append $a\in \Sigma$. By the definitions of the extended transition functions and the subset construction,This completes the induction.

A word $w$ is accepted by the Epsilon-NFA precisely whenBy part (b), this reached subset is exactly ${\hat{\delta }}_D(q_D,w)$, and by the definition of $F_D$ the intersection condition is equivalent to ${\hat{\delta }}_D(q_D,w)\in F_D$. Hence

Let $RS{S}_0$ and $RS{S}_1$ be the residual sums of squares under the restricted model with $p_0$ coefficients and the full model with $p$ coefficients. Assuming $X$ has full column rank, the nested-model F-test usesUnder the null hypothesis this has the $F_{p-p_0,n-p}$ distribution.

Maximizing the Gaussian likelihood over $\beta$ and the unknown variance gives ${\hat{\sigma }}^2=RSS/n$. Thus the likelihood-ratio test statistic isSincewe obtainThe logarithm is strictly increasing, so the two test statistics give exactly the same rejection ordering.

Adding the three equations of the SIRS model givessoAt a fixed point, $I(bS-c)=0$. The disease-free equilibrium isFor an endemic equilibrium $I^{\ast }>0$, one has $S^{\ast }=c/b$ and $a{R}^{\ast }=c{I}^{\ast }$. Conservation then givesIt exists with positive infected population exactly whenequivalently when the basic reproduction number $bN/c$ exceeds one.

Eliminating $R=N-S-I$ yieldsAt the endemic equilibrium its Jacobian matrix isIts trace and determinant areTherefore the endemic equilibrium is locally asymptotically stable. It is a stable node whenand a stable focus when the inequality is reversed. Near a node, perturbations are sums of two nonoscillatory decaying exponentials. Near a focus, they execute damped oscillations with decay rate $-T/2$ and angular frequency $\sqrt{4D-T^2}/2$.

Integration by parts is legitimate after symmetrically excluding a neighborhood of zero; the boundary terms vanish because $\cos (nx)-\cos (mx)=O(x^2)$ at zero and is bounded at infinity. HenceThe standard Dirichlet integral, obtained by closing the contour for $e^{iaz}/z$ in the upper half-plane and indenting above its pole at zero, isTherefore

In Cartesian coordinates the Lagrangian isIntroduce a Lagrange multiplier $\lambda$ for $x^2+y^2+z^2=c^{-2}$. The Euler-Lagrange equations becomeorDifferentiating the constraint twice givesTaking the scalar product of the vector equation with $\mathbf{x}$ therefore yieldsSubstitution gives

For $c=0$, the equations have the first integralsWriting $X=x+B$ and $Y=y-A$ gives $\dot{X}=-Y$ and $\dot{Y}=X$. Hence every trajectory isThese are helices of unit angular frequency about a line parallel to the $z$ axis, including circles when $C=0$ and a straight line when $R=0$.

Spatial homogeneity says that the velocity of $B$ relative to $A$ depends only on their separation. Comparing both galaxies with $C$ givesThus $\mathbf{v}(\mathbf{x}-\mathbf{y})=\mathbf{v}(\mathbf{x})-\mathbf{v}(\mathbf{y})$, so continuity of the macroscopic velocity field turns this Cauchy functional equation into a linear map:Isotropy requires $RH=HR$ for every rotation matrix $R$. The only such rank-two tensor is a scalar multiple of the identity, and henceThis is the Hubble law. A comoving galaxy has physical position $\mathbf{r}(t)=a(t)\mathbf{x}$, so

The physical particle horizon isFor an Einstein-de Sitter universe, $a(t)\propto t^{2/3}$, soSince $H_0=2/(3t_0)$,The Horizon problem is that widely separated regions of the observed universe have nearly identical conditions even though, in a decelerating standard Big Bang history, their past light cones do not overlap early enough to establish causal thermal equilibrium.

For $|\psi ⟩=a|0⟩+b|1⟩$, the Controlled-NOT gate givesA cloned product would instead beEquality up to a physically irrelevant global phase requires $ab=0$. ThusFor a genuine superposition it creates quantum entanglement instead of two independent copies.

The no-cloning theorem for two pure states states that no single unitary operator can clone two distinct nonorthogonal states. Suppose, to the contrary, thatPreservation of the inner product by $U$ givesWriting $z=⟨{\alpha }_0|{\alpha }_1⟩$, this requires $z=0$ or $z=1$. The first case is orthogonality; the second means that the normalized states represent the same ray. Both contradict the assumptions. Therefore distinct nonorthogonal quantum states cannot be cloned by a unitary process.

For $f\in C[0,1]$, define its Bernstein polynomialIf $X_{n,x}\sim \mathrm{Bin}(n,x)$, thenLet $M=\Vert f{\Vert }_{\infty }$. By uniform continuity, for any $\epsilon >0$ choose $\delta >0$ such that $|f(u)-f(v)|<\epsilon /2$ whenever $|u-v|<\delta$. Splitting the expectation according to that event and using Chebyshev's inequality gives, uniformly in $x$,For sufficiently large $n$ this is below $\epsilon$. Thus $B_{n}f\to f$ uniformly on $[0,1]$. An affine change of variable treats every compact interval, proving the Weierstrass approximation theorem.

True. For each $n$, the Weierstrass approximation theorem gives a polynomial $P_n$ such thatFor each fixed $x\in \mathbb{R}$, this estimate applies once $n\ge |x|$, so $P_n(x)\to f(x)$ pointwise.

False. Take the bounded nonconstant continuous function $f(x)=\sin x$. If polynomials $P_n$ converged uniformly to $f$ on $\mathbb{R}$, then each sufficiently late $P_n$ would be bounded on $\mathbb{R}$ and hence constant. A uniform limit of constants is constant, a contradiction. More generally, the globally uniform limit of real polynomials is itself a polynomial.

False. The bounded continuous function $f(x)=\sin (1/x)$ on $(0,1]$ has no limit at zero. If polynomials converged uniformly to it there, they would be uniformly Cauchy on $(0,1]$ and hence on $[0,1]$ by continuity at zero. Their uniform limit on $[0,1]$ would continuously extend $f$ to zero, which is impossible.

True. First choose polynomials $Q_n\to f$ uniformly by the Weierstrass approximation theorem. Let $L_1,\dots ,L_m$ be the Lagrange interpolation polynomials for the nodes $x_1,\dots ,x_m$, so $L_j(x_i)={\delta }_{ij}$. SetThen $P_n(x_j)=f(x_j)$ for every $j$, while

True. By the Weierstrass approximation theorem, choose polynomials $q_n$ with $q_n\to f^{(m)}$ uniformly. Define $P_n$ by integrating $q_n$ exactly $m$ times and choose the $m$ integration constants so thatThen $P_n^{(m)}=q_n$, and repeated use of the fundamental theorem of calculus givesEvery derivative therefore converges uniformly as required.

In the RSA cryptosystem, choose distinct primes $p,q$, set $N=pq$, and choose $e$ with $\gcd (e,\varphi (N))=1$. The public key is $(N,e)$; the private exponent satisfiesA message $m$ is encrypted and decrypted by

Suppose $\varphi (N)\mid 2^{a}b$, where $b$ is odd. For a unit $x$ modulo $N$, both $O_p(x^b)$ and $O_q(x^b)$ are powers of two dividing $2^a$. If these orders differ, assume without loss of generality thatTaking $t=r<a$ givesand hencea nontrivial factor.

To count successful $x$, write $p-1=2^{r}u$ and $q-1=2^{s}v$ with $u,v$ odd. Raising to the odd power $b$, which is divisible by the odd parts, maps a uniformly chosen element of each cyclic multiplicative group uniformly onto its Sylow two-subgroup. In a cyclic group of order $2^r$, the probability of order $1$ is $2^{-r}$ and that of order $2^j$ is $2^{j-1-r}$ for $1\le j\le r$. If $r\le s$, the probability that the two resulting orders agree isThus at least half of the $\varphi (N)$ units satisfy $O_p(x^b)\ne O_q(x^b)$.

Knowing $d$ reveals the multiple $ed-1$ of $\varphi (N)$. Writing $ed-1=2^{a}b$ with $b$ odd and trying random units therefore yields a factor with probability at least one half per trial; nonunits already reveal a factor by taking their greatest common divisor with $N$. Conversely, factoring $N$ gives $\varphi (N)$ and hence $d=e^{-1}(\mathrm{mod}\varphi (N))$. This proves that recovering the private key is computationally equivalent, up to randomized polynomial-time work, to factoring the RSA modulus, as summarized by RSA private exponent reveals the factorization.

For $N=77$ and $e=43$, $\varphi (N)=60$ andTherefore

Finally, $e$ is odd because it is coprime to the even integer $\varphi (N)$. If $m^e\equiv m(\mathrm{mod}N)$, thenThus fixed points occur in complementary pairs $m,N-m$, which is the Complementary RSA fixed points property.

A branch point of a multivalued analytic function is a point around which analytic continuation along a closed loop can return a different value. A branch cut is a curve or union of curves removed from the domain so that loops causing this monodromy are excluded and one single-valued branch can be chosen.

Write $z=r{e}^{i\theta }$ with $r>0$ and $0\le \theta <2\pi$, and write $w=u+iv$. Sincewe haveThus the inverse of the exponential is the infinitely valued complex logarithmFor the angle convention in the question, its principal value is

On taking $z$ once anticlockwise around zero, $\theta$ increases by $2\pi$ and $w$ changes by $2\pi i$; hence zero is a branch point. Under the coordinate $\zeta =1/z$, a loop around $\zeta =0$ corresponds to a loop around infinity and produces the opposite increment, so infinity is also a branch point. Removing any curve joining the two branch points prevents such loops. With $0<\arg z<2\pi$, one possible branch cut is therefore

On the cut plane choose $0<\theta <2\pi$. For $z=x+iy$,Their derivatives areThe Cauchy-Riemann equations hold, so this branch is holomorphic. Its derivative is

A principal body frame is an orthonormal basis ${\mathbf{e}}_a(t)$ fixed in the rotating body and aligned with its principal axes. If $R(t)$ is the rotation matrix whose columns are these vectors, differentiating $R^{T}R=I$ shows that $\dot{R}{R}^T$ is skew-symmetric. Every skew-symmetric linear map in three dimensions is cross product with a unique vector $\mathbf{\omega }$, so

For any vector $\mathbf{A}=A_a{\mathbf{e}}_a$,Applying this to the conserved angular momentumgives the Euler equations for a torque-free rigid body: