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}$.

Solved by gpt-5.6-sol high.

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\}$.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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,

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

The generalized momentum conjugate to $q$ is

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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)$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.