Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3

Write $f=[a,b,c]$. Two integral binary quadratic forms $f$ and $g$ are equivalent if there is a matrixsuch thatEquivalently, the group ${\mathrm{SL}}_2(\mathbb{Z})$ acts on forms by integral unimodular changes of variables.

Suppose $g=[A,B,C]$ is obtained from $f=[a,b,c]$ by such a change of variables. Expanding shows that each of $A,B,C$ is an integer linear combination of $a,b,c$. Therefore every common divisor of $a,b,c$ divides $A,B,C$.

The inverse of a matrix in ${\mathrm{SL}}_2(\mathbb{Z})$ again has integral entries and determinant one. Applying the same argument to $U^{-1}$ shows that every common divisor of $A,B,C$ divides $a,b,c$. The two coefficient triples consequently have the same greatest common divisor, up to sign, so one form is primitive exactly when the other is.

Every proper equivalence class of a positive definite form contains a unique reduced form $[a,b,c]$, wherewith $b\ge 0$ when equality occurs in either inequality. Its discriminant isFor a reduced positive definite form, $3a^2\le 80$, so $1\le a\le 5$. Also $b$ is even andChecking the finitely many possibilities with $|b|\le a\le c$ givesEach coefficient triple has greatest common divisor one. By uniqueness of reduced representatives, these are four distinct classes. Hence the requested number is

Runge's polynomial approximation theorem says that if $K\subset \mathbb{C}$ is compact, $\mathbb{C}\setminus K$ is connected, and $f$ is holomorphic on a neighborhood of $K$, then for every $\epsilon >0$ there is a polynomial $p$ such that

LetThis arc is compact, its complement is connected, and $1/z$ is holomorphic on a neighborhood of it. Applying Runge with error $1/n$ gives a polynomial $q_n$ satisfyingwhich is the requested uniform approximation.

For the pointwise construction, for $n\ge 2$ setThe three pieces are disjoint compact sets and $\mathbb{C}\setminus K_n$ is connected. Define a function on a neighborhood of $K_n$ to equal $1$, $-1$, and $0$ on neighborhoods of $K_n^{+}$, $K_n^{-}$, and $K_n^0$, respectively. It is holomorphic because those neighborhoods may be chosen disjoint. Runge supplies a polynomial $P_n$ such thatEvery fixed point with $|z|<1$ eventually belongs to the appropriate one of these three sets, according to the sign of its real part. These inequalities therefore give precisely the asserted pointwise limits.

Let $\alpha$ be a primitive $n$th root of unity in an extension of ${\mathbb{F}}_q$, where $\gcd (n,q)=1$. A BCH code of length $n$, initial exponent $b$, and design distance $\delta$ is the cyclic code whose generator polynomial is the least common multiple over ${\mathbb{F}}_q$ of the minimal polynomials ofThus every codeword polynomial $c(X)$ vanishes at these $\delta -1$ consecutive powers.

Suppose a nonzero codeword has weight $w<\delta$, withwhere the positions $i_{\ell }$ are distinct modulo $n$ and every $c_{\ell }$ is nonzero. The first $w$ root conditions giveThe coefficient matrix is a Vandermonde matrix in the distinct elements ${\alpha }^{i_1},\dots ,{\alpha }^{i_w}$, followed by multiplication of its columns by the nonzero factors ${\alpha }^{b{i}_{\ell }}$. Its determinant is thereforeHence all $c_{\ell }$ would be zero, a contradiction. The minimum distance consequently satisfies $d\ge \delta$.

A code of minimum distance $d$ detects every pattern of at most $d-1$ errors and uniquely corrects every pattern of at most $\lfloor (d-1)/2\rfloor$ errors, because Hamming balls of that radius are disjoint. A BCH code of design distance $\delta$ is therefore guaranteed to detect $\delta -1$ errors and to correcterrors; its actual capabilities may be larger if $d>\delta$.

The instruction $-(0,p,q)$ goes to $p$ if register $0$ is empty; otherwise it deletes the final letter and goes to $q$.

For $M$, an empty input goes directly from $q_S$ to $q_1$, where a $1$ is appended. On a nonempty input, state $q_0$ deletes every letter; once the register is empty it goes to $q_2$ and appends $0$. Hence

For $N$, the initial instruction tests whether the final letter is $0$. If it is, state $q_3$ deletes the entire word and then goes to $q_1$, producing $1$. Otherwise state $q_0$ deletes the entire word and goes to $q_2$, producing $0$. Thusthe set of nonempty binary words ending in $0$.

Use the same program as $N$, replacing only its first line by a test for a final $1$:If the input ends in $1$, the $q_3$ loop erases it and eventually appends output $1$. Every other input, including the empty word, follows the $q_0$ loop and produces $0$. This is the characteristic function of $\{w1:w\in \mathbb{B}\}$.

Rename the old halt state $q_H$ as a nonhalting state $q_F$, including every occurrence of $q_H$ in the original program, and introduce a new halt state $q_H$. Attach the following output-flipping routine:Because the original machine computes a characteristic function, it reaches $q_F$ with register $0$ containing exactly $0$ or $1$. The routine tests that symbol, removes it, and appends its complement. It therefore halts with $1-{\chi }_X(w)={\chi }_{\mathbb{B}\setminus X}(w)$.

Let $Y_1,\dots ,Y_n$ be independent. In the general exponential-dispersion formulation, with known weights $w_i>0$ and common dispersion $\varphi >0$, their densities have the formThusThe systematic component is ${\eta }_i=x_i^T\beta$, and a specified one-to-one differentiable link relates it to the mean byThe unknown model parameters are the regression coefficient $\beta$ and, when it is not fixed by the family, the dispersion $\varphi$.

The log-likelihood isup to terms independent of the parameters, where ${\theta }_i$ is determined from $g^{-1}(x_i^T\beta )=b^{\prime }({\theta }_i)$.

For a Poisson response,so the natural parameter is $\theta =\log \mu$ and $b(\theta )=e^{\theta }$. The canonical link sets the linear predictor equal to the natural parameter and is therefore

The delay $\tau$ is the time between an individual's presence in the population and its contribution to the current growth rate, for example a maturation or gestation time. Thus reproduction at time $t$ is determined by the reproductive population at time $t-\tau$.

For $0\le t\le \tau$, the delayed argument lies in the prescribed history, so $n^{\prime }(t)=r$ and $n(t)=1+rt$. For $\tau \le t\le 2\tau$,Integrating from $\tau$ and using $n(\tau )=1+r\tau$ gives

Set $\omega =\pi /(2\tau )$. The condition $r\tau =-\pi /2$ says $r=-\omega$. ThensatisfiesIt is periodic with period $2\pi /\omega =4\tau$. Every nonzero such solution is negative during half of each period, so it cannot represent a population size.

For $\mathrm{Re}z>0$, absolute convergence permits the double-integral calculationPut $r=s+t$ and $u=t/(s+t)$, so $s=r(1-u)$, $t=ru$, and the Jacobian has magnitude $r$. The first quadrant becomes $r>0$, $0<u<1$, and therefore

As $z\to 0$ within the right half-plane, the functional equation $\Gamma (1+z)=z\Gamma (z)$ and continuity at $1$ giveUsing part (a),

At height $z$ from the vertex, the cone has cross-sectional area $\pi R^2{z}^2/l^2$. Hence

The parallel-axis theorem isThe displacement is along ${\mathbf{e}}_3$, so it changes the two transverse moments but not the axial one. Thus, writing the vertex moments as $I_1=I_2=I$ and $I_3=J$,and

Take $\theta$ to be the angle between ${\mathbf{e}}_3$ and the upward vertical. From the supplied angular-velocity components,ThereforeBoth $\psi$ and $\varphi$ are cyclic. Their conserved conjugate momenta areand $p_{\theta }=I\dot{\theta }$. Solving for the velocities and taking the Legendre transform gives

Fix the two conserved momenta $p_{\psi }=\lambda$ and $p_{\varphi }=\mu$. The remaining canonical variables $(\theta ,p_{\theta })$ form a two-dimensional phase space with Hamiltonianwhere

An upright spinning solution has $\theta =0$, $p_{\theta }=0$, and necessarily $\mu =\lambda$, since the vertical and body-axis angular momenta then coincide. On that momentum level,Near zero,Thus the upright configuration is a strict local minimum of the reduced Hamiltonian, and hence stable, whenHere $\lambda$ is the angular momentum about the symmetry axis. This proves stability for sufficiently large axial angular momentum.

Since $a(\tau )=(\tau /{\tau }_0{)}^2$, the conformal Hubble parameter is $\mathcal{H}=2/\tau$. With ${\Omega }_M=1$, the mode equation becomesSubstitution of $\delta ={\tau }^{\beta }$ givesThe two independent solutions are therefore ${\tau }^2$ and ${\tau }^{-3}$, so

The physical horizon size at conformal time $\tau$ is $a(\tau )c\tau$. Horizon crossing occurs when it equals the physical wavelength:and hence

At late times the decaying mode is neglected, so the growing solution in part (a) obeys $\delta \propto {\tau }^2\propto a$. For the equality-crossing mode this gives

A mode that crosses during matter domination subsequently grows byIts present amplitude is consequentlyNowSquaring therefore gives

Since ${\tau }_H\propto k^{-1}$, modes crossing chronologically between equality and today satisfy $k_0\le k\le k_{\mathrm{eq}}$. The reverse ordering printed with the target formula is inconsistent with the stated definitions of $k_0$ and $k_{\mathrm{eq}}$; it does not affect the spectrum calculation.

Write $x=x_1{x}_2$. Since the marked word is $11$, the required oracle is a single Toffoli gate with $x_1$ and $x_2$ as its two controls and the answer qubit $y$ as its target:The target flips exactly when both controls are one, which is exactly when $x=11$.

Let $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Applying the oracle with this answer qubit produces phase kickback:Inside $A$, the $X$ gates on both search qubits conjugate the phase oracle for $11$. Hencewhere $I_0=I-2|00⟩⟨00|$.

The first oracle similarly acts on the search register as $I_{x_0}=I-2|x_0⟩⟨x_0|$. Reading the remaining gates from right to left, the search-register operation after its initial Hadamards is thereforewhile the answer qubit remains in $|-⟩$.