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

A reduced positive definite binary quadratic form $[a,b,c]$ satisfieswith $b\ge 0$ when either $|b|=a$ or $a=c$. For $d\equiv 0$ or $3(\mathrm{mod}4)$, the class number of a negative discriminant $h(-d)$ is the number of proper equivalence classes of primitive positive definite integral forms of discriminant $-d$, equivalently the number of their reduced representatives.

WritePartitioning the $k$ complete prime-power factors between $r$ and $s$ gives $2^k$ ordered factorizations $d=rs$ with $\gcd (r,s)=1$. After identifying $(r,s)$ with $(s,r)$, there are $2^{k-1}$ choices with $r\le s$. Each gives the primitive reduced formwhose discriminant is $-4rs=-4d$. The uniqueness of reduced representatives makes these classes distinct, proving the coprime-factorization lower bound for a quadratic-form class number

The inequality can be strict. For $d=5$, there is one distinct prime factor, while the reduced primitive forms of discriminant $-20$ areThus $h(-20)=2>1=2^{1-1}$.

The Baire category theorem says that a complete metric space cannot be a countable union of nowhere-dense closed sets. Equivalently, every countable intersection of open dense sets is dense.

A point $x$ of a metric space is an isolated point when some $\epsilon >0$ satisfies $B(x,\epsilon )=\{x\}$.

False. The rational numbers with the Euclidean metric are countable and have no isolated point.

False. Every discrete metric space is complete and every one of its points is isolated; a singleton is the smallest example.

False. The interval $(0,1)$ with the Euclidean metric is uncountable and has no isolated points, but the Cauchy sequence $1/n$ has no limit in the space.

False. A singleton, or $\mathbb{Z}$ with the discrete metric, is complete and countable.

True. If a nonempty countable complete metric space had no isolated point, every singleton would be closed and nowhere dense. Their countable union would be the whole space, contradicting the Baire category theorem. This is the basic isolated points in a countable complete metric space argument.

False. The subspaceis closed and hence complete, and it is countable; however, $0$ is not isolated.

True. Part (v) supplies one isolated point $p$. Since $\{p\}$ is open, $X\setminus \{p\}$ is closed and therefore complete. It is nonempty when $X$ has at least two points, so part (v) applied to this subspace supplies an isolated point $q$. Because $d(p,q)>0$, a sufficiently small ball showing that $q$ is isolated in the subspace also avoids $p$; hence $q$ is isolated in $X$.

True. If there were only finitely many isolated points, delete all of them. The remainder would be a nonempty closed, countable, complete subspace, so part (v) would give it an isolated point. Its positive distance from the finite deleted set would make it isolated in the original space as well, a contradiction. Thus the stronger isolated points in a countable complete metric space result applies.

The original binary Hamming code has parameters $[7,4,3]$, so it has $2^4=16$ codewords. Its minimum distance three makes the radius-one balls about its codewords disjoint. Each ball hasvectors, and $16\cdot 8=128=2^7$, the size of the ambient space. Equality in the Hamming bound therefore shows that these balls partition ${\mathbb{F}}_2^7$: the code is perfect.

The added bit is the overall parity bit. The original minimum-weight words have weight three, so they acquire a parity bit equal to one and have extended weight four. Every original even-weight difference keeps its weight, while every odd-weight difference gains one; hence the new minimum distance is four.

The minimum-distance error-detection and correction guarantee therefore says that the code detects three errors and corrects one error.

Yes, for a binary code. Correcting $e$ errors requires minimum distance at least $2e+1$. Apply the parity extension: append to each word the bit that makes its total weight even. Every odd distance increases by one and every even distance is unchanged, so the extended minimum distance is at least $2e+2$. It therefore detects every pattern of at most $2e+1$ errors.

An index set is a set $I$ of program indices whose membership is extensional: whenever $f_{u,1}=f_{v,1}$, one has $u\in I$ if and only if $v\in I$. It is nontrivial when it is neither empty nor the set of all indices.

For the fixed effective enumeration of unary partial computable functions, the infinite-domain index set is

The Rice theorem states that every nontrivial index set of partial computable functions is not computable.

Fix $x_0\in X$. The property defining ${\mathbf{Inf}}_X$ depends only on the partial function computed, so it is an index set. It is nontrivial: an index of the nowhere-defined function is outside it, whereas an index of the total constant function $n\mapsto x_0$ has infinite domain and range $\{x_0\}\subseteq X$, and hence lies in it. The Rice theorem now shows that this infinite-domain range-restriction index set is not computable.

Put $K=nY$. Apart from a factor independent of $p$, the likelihood isThus the score function and Fisher information matrix are

The Newton method and Fisher scoring updates are respectivelySince $\hat{p}=Y$, initialization at $p^{(0)}=Y$ requires zero steps for either algorithm. Moreover,so binomial-proportion Fisher scoring reaches the MLE in one step from every interior $p^{(0)}\ne Y$.

In the SIR model with demography and permanent immunity, $\mu$ is the common per-capita death rate and, through the term $\mu N$, the replacement birth rate. The coefficient $\beta$ is the mass-action transmission rate per susceptible-infective pair, and $\nu$ is the per-capita recovery rate from infection into permanent immunity.

The infective equation isSince $X\le N$, the threshold population isIf $N<N_c$ and $\delta =\mu +\nu -\beta N>0$, thenAlsoAny steady state with $Y>0$ would require $X=N_c>N$, which is impossible. Thus the infection cannot be maintained, and both infected and immune populations tend to zero from every admissible initial condition.

For a positive equilibrium, $Y^{\prime }=0$ gives $X^{\ast }=N_c$. The equations $Z^{\prime }=0$ and $X^{\ast }+Y^{\ast }+Z^{\ast }=N$ then give the Endemic equilibrium of the SIR model with demographywhich is strictly positive when $N>N_c$.

Use $Z=N-X-Y$ to reduce to the $(X,Y)$ system. At the endemic equilibrium its Jacobian isIts trace is negative and its determinant is $\beta Y^{\ast }(\mu +\nu )>0$. The two eigenvalues therefore have negative real part, so the endemic equilibrium is locally asymptotically stable.

Substitutingand using $z{e}^{zt}={\partial }_t{e}^{zt}$ givesIt is therefore enough to requireand choose $\gamma$ so that the integral converges and $e^{zt}{t}^{3}f(t)$ vanishes at its endpoints. Solving the amplitude equation,

For $x>0$, take the real contour $\gamma =(-\infty ,0)$. At $t\to 0^{-}$ the factor $e^{-1/t^2}$ kills every power, while at $t\to -\infty$ the factor $e^{xt}$ makes the integrand and endpoint term vanish. The laplace integral solution of a singular third-order equation is thereforeWith $u=-1/t$, and absorbing a minus sign into the arbitrary constant, this becomes

The generalized momentum conjugate to $q$ is

A coordinate $q$ is an ignorable coordinate when $L$ has no explicit dependence on it, so $\partial L/\partial q=0$. Its Euler--Lagrange equation iswhich proves that $p_q$ is conserved.

Let $q=(q_1,q_2,q_3)$ and $n=(1,1,1)$. Sincethe Lagrangian depends on $q$ only through $|q{|}^2$ and $(q\cdot n{)}^2$, and on the velocity through $|\dot{q}{|}^2$. Rotations about the $n$-axis preserve all three quantities, proving the invariance.

The axially symmetric isotropic-mass Lagrangian therefore conserves the axial angular momentumup to an irrelevant normalization of $n$. Since $L$ has no explicit time dependence, conservation of energy from time-translation invariance gives the second conserved quantity

Chemical equilibrium gives ${\mu }_D={\mu }_p+{\mu }_n$. Substitution of the three Maxwell--Boltzmann densities therefore cancels the chemical potentials and leaves the rest-mass factorUsing $g_p=g_n=2$, $g_D=4$, $m_n\simeq m_p$, and $m_D\simeq 2m_p$, the translational prefactor isHence

Because $X_i=n_i/n_B$,Using $n_B=\eta n_{\gamma }$ and the given photon density in the deuterium equilibrium abundance formula givesAlthough the exponential favors deuterium once $k_{B}T<B_D$, the very small factor $\eta$ expresses the enormous excess of photons. The high-energy tail therefore photodissociates newly formed deuterium until the temperature is well below $B_D/k_B$; this is the deuterium bottleneck.

A larger $\eta$ increases the deuterium fraction at fixed temperature, so the bottleneck ends at a higher temperature and earlier time. With weak decoupling unchanged, fewer free neutrons then beta-decay before nuclear reactions bind them. Since primordial helium production is neutron-limited, the baryon-density effect on primordial helium makes $Y_{\mathrm{He}}$ larger than the standard value.

The powers areThus the least positive period is $\boxed{r=3}$.

The possible values are $y\in \{1,4,7\}$. Each occurs for four of the twelve equally weighted values of $x$, so

The equality $f(x)=4$ holds exactly for $x\equiv 1(\mathrm{mod}3)$. Projecting onto the measured second-register value and normalizing gives

With $\omega =e^{2\pi i/12}$, the quantum Fourier transform acts by(The opposite phase convention gives the same measurement probabilities.)

Applying the transform to the coset state gives amplitudefor $|c⟩$. The geometric sum vanishes unless ${\omega }^{3c}=1$, which means $c\equiv 0(\mathrm{mod}4)$. For $c=0,4,8$ its magnitude is $4/(2\sqrt{12})=1/\sqrt{3}$. Thus the quantum Fourier transform of a periodic coset state gives

Put $A_j=\left(\begin{array}{cc}{a}_j& b_j\\ 1& 0\end{array}\right)$. The identityfollows by induction: multiplying the formula for $n-1$ by $A_n$ gives the two stated recurrences in the first column and $b_n(p_{n-1},q_{n-1}{)}^T$ in the second. The associated Möbius transformations $z\mapsto a_j+b_j/z$, applied from the right to $a_n$, show that the first-column ratio is the displayed positive generalized continued fraction.

Now set every $b_j=1$. Taking determinants in the matrix identity givesConsequently adjacent convergents differ byThe recurrence and $a_j\ge 1$ imply $q_{n+1}\ge q_n+q_{n-1}$, so $q_n\to \infty$. The determinant signs show that the even convergents increase, the odd convergents decrease, and every even one is below every odd one. Their adjacent separation tends to zero, so both subsequences have a common limit $x$. Since $x$ lies between each adjacent pair, the convergence of a positive simple continued fraction gives exactly

If all $a_j=1$ as well, the recurrence and initial values giveThe characteristic roots of $F_{n+2}=F_{n+1}+F_n$ are
$\varphi =(1+\sqrt{5})/2$ and $\psi =(1-\sqrt{5})/2=-{\varphi }^{-1}$, henceTherefore $F_{n+2}/F_{n+1}\to \varphi$. Moreover,Using $F_n{\varphi }^{-n}\to 1/\sqrt{5}$ yieldsandThis is the all-one continued fraction and Fibonacci ratios case.

In the Rabin cryptosystem, the public key is $N=pq$, usually with distinct secret primes $p,q\equiv 3(\mathrm{mod}4)$. A message $m$ is encrypted asKnowing $p$ and $q$, the receiver finds the two square roots of $c$ modulo each prime and combines them by the Chinese remainder theorem, obtaining the four square roots modulo $N$; redundancy identifies the intended message.

Factoring $N$ plainly enables this decryption. Conversely, suppose an algorithm returns a square root of a chosen quadratic residue. Choose random invertible $x$, submit $x^2\mathrm{mod}N$, and receive a root $y$. With probability at least $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$; thenis a nontrivial factor. Thus decryption and factoring are equivalent up to a randomized polynomial-time reduction.

For the RSA cryptosystem, choose $N=pq$ and a public exponent $e$ coprime to $\varphi (N)$. The public key is $(N,e)$, while the private exponent satisfiesEncryption sends $m$ to $c\equiv m^e(\mathrm{mod}N)$, and decryption computes $c^d\equiv m(\mathrm{mod}N)$.

Let the intercepted ciphertexts beSince $\gcd (e_i,e_j)=1$, the extended Euclidean algorithm gives integers $a,b$ with $a{e}_i+b{e}_j=1$. The common-modulus RSA attack recoversNegative powers are evaluated using modular inverses. If an inverse does not exist, its greatest common divisor with $N$ already factors the modulus.

Yes. Your public and private exponents reveal $ed-1$, a nonzero multiple of $\lambda (N)$. The standard RSA private exponent reveals the factorization algorithm uses repeated squaring of random residues to obtain a nontrivial square root of one and hence factors $N$ with a greatest common divisor. Once $p$ and $q$ are known, compute $\varphi (N)$ and invert every other customer's public exponent to obtain that customer's private exponent.

An elliptic function is a meromorphic $f:\mathbb{C}\to \hat{\mathbb{C}}$ with two real-linearly independent periods ${\omega }_1,{\omega }_2$. A fundamental cell may be taken as the half-open parallelogramwith $z_0$ chosen so that its boundary contains no zero or pole under discussion. The argument principle and cancellation on opposite sides show that a nonconstant elliptic function has the same number of zeros and poles in a cell, counting multiplicity.