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

For $n=\prod p_i^{e_i}$ odd, define $(a/n)=\prod (a/p_i{)}^{e_i}$. Multiplying quadratic reciprocity for all prime-factor pairs givesfor positive odd coprime $a,n$; the sign exponents add modulo two, proving Jacobi reciprocity from Legendre reciprocity. Since $959=7\cdot 137$, $(5/7)=-1$ and $(5/137)=(2/5)=-1$, so $(5/959)=1$. Nevertheless $5$ is a nonresidue modulo both prime factors, so $x^2\equiv 5(\mathrm{mod}959)$ has no solution.

A subset is dense when every nonempty open set meets it, equivalently its closure is the whole space. Baire category theorem says a complete metric space has dense intersection for every countable family of open dense sets. Hereso Baire makes $S$ dense. It need not be open: enumerate the rationals $q_j$ and take $A_j=[0,1]\setminus \{q_1,\dots ,q_j\}$, giving the irrationals. Nor need ${\cap }_j{A}_j$ be nonempty: take $A_1=\varnothing$ and $A_j=[0,1]$ for $j\ge 2$.

A cyclic code is a linear subspace invariant under cyclic coordinate shift. Identifying words with ${\mathbb{F}}_2[X]/(X^n-1)$ makes such codes exactly ideals. Since this quotient is a principal ideal ring, every code is generated uniquely by a monic divisor of $X^n-1$. For $n=7$,so its three distinct irreducible factors have $2^3=8$ monic divisors and there are eight cyclic codes.

A DFA consists of finite $Q$, alphabet $\Sigma$, transition $\delta$, initial $q_0$, and accepting set $F$. Extend by $\hat{\delta }(q,ϵ)=q$ and $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w),a)$. It accepts $\{w:\hat{\delta }(q_0,w)\in F\}$; a language is regular if some DFA accepts it.

The pumping lemma for regular languages says that for some $N$, every accepted word $w$ of length at least $N$ factors $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{k}z$ accepted for every $k\ge 0$.

Regular. A DFA need only remember the current run length of $b$'s, using states $0,\dots ,99$ and a rejecting sink at 100.

Since $w_i=(ab{)}^{2^{i-1}}$, the language is $\{(ab{)}^{2^j}:j\ge 0\}$. If it were regular, pumping a sufficiently long member would alter its number of $ab$ blocks by a fixed positive amount, producing non-powers of two for some pumping exponent. Hence it is not regular.

The residual-versus-fitted smooth curve bends downward, indicating nonlinearity, and the spread increases at high fitted values. The Q-Q plot is close centrally but departs in both tails, with observations 12, 17, and 67 notable. The scale-location trend confirms heteroscedasticity. The leverage plot identifies observations 1 and 4 as high leverage and 67 as a large residual, with potentially material Cook distance. The additive Gaussian linear model is therefore doubtful. Inspect those observations, transform sale price (often logarithmically), add nonlinear or interaction terms and omitted predictors such as lot size and age, and use weighted or robust regression if unequal variance remains.

The reaction is $F(n)=-n(n-A)(n-B)$. Its homogeneous equilibria are $0,A,B$; $F^{\prime }(0)<0$ and $F^{\prime }(B)<0$, while $F^{\prime }(A)>0$. Thus the stable equilibria are $0$ and $B$.

Substitution $n=f(\xi )$, $\xi =x-ct$, gives $f^{\prime \prime }+c{f}^{\prime }+F(f)=0$ with $f(-\infty )=0$, $f(\infty )=B$. Multiplying by $f^{\prime }$ gives $-c\int (f^{\prime }{)}^{2}d\xi ={\int }_0^{B}F(s)ds=B^4(1-2A/B)/12$. The populated state invades the empty state when $c<0$, equivalently $B>2A$; this is the condition preventing eventual extinction.

A point $z_0$ is regular singular when $(z-z_0)p$ and $(z-z_0{)}^{2}q$ are analytic there. The Papperitz symbol records the three singular points and their two local exponents. Here the finite points are $0,1$ and the third is $\infty$. The indicial equations give exponents $(0,-1)$ at $0$ and $(0,0)$ at $1$. Comparing with the hypergeometric equation gives $c=2$, $a+b=2$, $ab=1$, hence $a=b=1$ and exponents $(1,1)$ at infinity. Thus

For the standard symplectic form, $D_f={\sum }_a(f_{p_a}{\partial }_{q^a}-f_{q^a}{\partial }_{p_a})$; a transformation is canonical when it preserves the symplectic form, equivalently Poisson brackets. The Jacobi identity gives $[D_f,D_g]=D_{\{f,g\}}$ with the stated convention. For $Z^A=e^{-s{D}_f}{z}^A$, differentiate $\{Z^A,Z^B\}$ in $s$; Jacobi makes the derivative the Lie transport of the bracket, preserving the canonical constant brackets at $s=0$. Hence every map in the one-parameter flow is canonical.

Substitution gives $\dot{\varphi }=2M_{\mathrm{Pl}}/t$, $\ddot{\varphi }=-2M_{\mathrm{Pl}}/t^2$ and $V=V_{\ast }{e}^{-{\varphi }_{\ast }/M_{\mathrm{Pl}}}(t_{\ast }/t{)}^2=10M_{\mathrm{Pl}}^2/t^2$, exactly satisfying both equations when ${\varphi }_{\ast }=M_{\mathrm{Pl}}\log (V_{\ast }{t}_{\ast }^2/(10M_{\mathrm{Pl}}^2))$. Since $a\propto t^2$, $\ddot{a}>0$: it inflates. $N=2\log (t_{\ast }/t)$ and $\Delta \varphi =2M_{\mathrm{Pl}}\log (t_{\ast }/t)=N{M}_{\mathrm{Pl}}$, so 60 e-folds require a field excursion about $60M_{\mathrm{Pl}}$.

In a decelerating universe the comoving Hubble radius grows, so regions now in causal contact extrapolate to many disconnected early Hubble patches. Inflation shrinks the comoving Hubble radius and stretches one causal patch beyond the present horizon. Radiation scaling gives a present-horizon physical size at $10^{-35}$ s of roughly $c{t}_0(a/a_0)\sim c{t}_0(t/t_0{)}^{1/2}\sim 1$ m. Comparing this with the inflationary Hubble length (about $ct\sim 10^{-27}$ m at that epoch) requires $e^N\sim 10^{27}$, or $N\simeq 62$ (order 60).

The all-zero amplitude is $2^{-n}{\sum }_x(-1{)}^{f(x)}=1-2k/2^n$, so its probability is $(1-2k/2^n{)}^2$. For a general nontrivial $k$ it lies strictly between zero and one.

For constant $f$, $k=0$ or $2^n$, so the all-zero result occurs with probability one.

For perfect balance, $k=2^{n-1}$ and the all-zero probability is zero. For other balances the one-shot outcomes overlap the constant case. Repeat Deutsch-Jozsa algorithm and declare nonconstant upon any nonzero result. Constants are never misclassified; a $k$-balanced function fails after $R$ trials with probability $q^R$, $q=(1-2k/2^n{)}^2$. It suffices that $R\ge \log ϵ/\log q$, using that many oracle calls.

With $p_{-1}=1,p_0=a_0$, $q_{-1}=0,q_0=1$ and $p_n=a_n{p}_{n-1}+p_{n-2}$, $q_n=a_n{q}_{n-1}+q_{n-2}$, induction gives $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n+1}$. Matrix multiplication gives $[a_0,\dots ,a_n,\beta ]=(p_n\beta +p_{n-1})/(q_n\beta +q_{n-1})$; monotonicity in $\beta >0$ places it strictly between the adjacent convergents.

Apply the formula to the complete quotient and use the determinant identity to express $b_n$. Eliminating the complete quotient from the consecutive expressions yields the stated quadratic for $q_{n+1}/q_n$. Taking the compatible signs for adjacent indices and using $c_n\le b_j$ gives

If all but finitely many convergents had $b_n>1/\sqrt{5}$, then eventually $c_n>1/\sqrt{5}$. Part (b) would imply $c_n{a}_{n+1}\le \sqrt{1-4c_n^2}<c_n$, impossible since $a_{n+1}\ge 1$. Thus infinitely many $b_n\le 1/\sqrt{5}$, which is exactly $|\theta -p_n/q_n|\le 1/(\sqrt{5}{q}_n^2)$.

A register machine has finitely many natural-number registers and labelled increment, conditional decrement/jump, and halt instructions. Starting with the input in designated registers, instructions determine a partial computation. Encode the finite instruction list by a standard effective Gödel coding, giving each machine an index in $\mathbb{N}$.

For machine index $m$, $f_{m,k}$ is the partial $k$-ary function computed by that machine under the fixed coding, and $W_m$ is its halting domain (equivalently the r.e. set enumerated by machine $m$, under the course convention).

Kleene's recursion theorem says that for every total recursive map $f$ on program indices there is an index $e$ with the same partial function as program $f(e)$.

Take $i$ to index a machine halting on every input, so $W_i=\mathbb{N}$, and $j$ to index a machine halting on no input, so $W_j=\varnothing$.

If $g_0$ were total recursive, its recursion-theorem fixed point $e$ would satisfy $W_e=W_j$ when $e\in \mathrm{Inf}$ and $W_e=W_i$ when $e\in \mathrm{Fin}$, a contradiction in either case. The same argument applies to $g_1$. A total recursive reduction $h$ with $n\in \mathrm{Inf}⟺h(n)\in \mathrm{Fin}$ would provide such a forbidden switch (and would collapse the known distinct arithmetical complexities), so none exists.

For jump rate $W(n,r)$ from $n$ to $n+r$, probability enters state $n$ from $n-r$ and leaves it from $n$. The resulting kramers-Moyal master equation is

When jumps are small relative to a large population and moments exist, the Kramers-Moyal expansion through second order givesThis Fokker-Planck equation is a conservation law with vanishing boundary flux; $u$ is the drift and $D$ the diffusivity. Equal constant rates for jumps $r=\pm 1$ give pure diffusion.

Integration by parts gives $d⟨x⟩/dt=⟨u⟩$ and $d\mathrm{var}x/dt=2⟨D⟩+2\mathrm{Cov}(x,u)$.

Here $u=-2\sinh (\lambda x)$ and $D=\cosh (\lambda x)$. Zero stationary flux gives $(DP{)}^{\prime }=uP$, so $P\propto D^{-1}\exp \int u/D,dx\propto \cosh (\lambda x{)}^{-(1+2/\lambda )}$, a symmetric unimodal distribution.

For constants $u=a-b$ and $D=(a+b)/2$, $z=x-ut$ removes drift and gives ${\tilde{P}}_t=D{\tilde{P}}_{zz}$.

At the earliest negative minimum, $\tilde{P}=0$, ${\tilde{P}}_z=0$, ${\tilde{P}}_{zz}\ge 0$, so the diffusion equation gives ${\tilde{P}}_t\ge 0$, contradicting first passage below zero. This is the maximum principle.

The third Kramers-Moyal expansion coefficient is $F=\frac{1}{6}{\sum }_r{r}^{3}W=(a-b)/6$. At a first minimum the third derivative has no fixed sign, so the maximum-principle argument fails; finite truncations beyond second order need not preserve positivity.

Writing $r=a(q+\psi )$ to first order gives $x^{\prime \prime }+\mathcal{H}{x}^{\prime }\simeq {\psi }^{\prime \prime }+\mathcal{H}{\psi }^{\prime }=-{\nabla }_q\phi$. The perturbation of Poisson's equation is ${\nabla }_q^2\phi =(4\pi G/c^2)a^2{\bar{\rho }}_M{\delta }_M$.

The Jacobian is $a^3\det (I+\partial \psi /\partial q)\simeq a^3(1+\nabla \cdot \psi )$, so mass conservation gives ${\delta }_M=-\nabla \cdot \psi$. Taking the divergence of (i) and using Poisson yields ${\delta }_M^{\prime \prime }+\mathcal{H}{\delta }_M^{\prime }-(4\pi G/c^2){\bar{\rho }}_M{a}^2{\delta }_M=0$.

Set ${\delta }_R=e^{-S}u$ and neglect $S^{\prime \prime }$, $(S^{\prime }{)}^2$, and slow variation relative to $k^2$. Cancelling the first derivative gives $S^{\prime }=\alpha k/(2\mathcal{H})$, hence $S={\int }^{\tau }\alpha k/(2\mathcal{H})d{\tau }^{\prime }$, and $u^{\prime \prime }+(c^2{k}^2/3)u\simeq 0$. Thus acoustic oscillations are exponentially damped, unlike pressureless matter perturbations, which have a growing mode.

Across the cut $A|BC$, the two conditional $BC$ vectors $\alpha |00⟩$ and $\gamma |00⟩+\beta |11⟩$ are linearly independent when $\alpha \beta \ne 0$, so the Schmidt rank exceeds one. Hence the state cannot be a three-qubit product for any $\gamma$.

Charlie measures in the $X$ basis and sends one bit to Alice or Bob; the remaining pair becomes $|{\Phi }^{+}⟩$ or $|{\Phi }^{-}⟩$, corrected by a local $Z$. Alice then performs standard teleportation: CNOT from $|\xi ⟩$ to her GHZ qubit, Hadamard, two computational measurements, and sends the two outcomes to Bob, who applies the corresponding Pauli correction.

No. Without classical communication Bob's reduced state is independent of Alice's unknown input by no-signalling, whereas successful transfer would make it equal to that input.

Reordering as $A_1{A}_2{B}_1{B}_2$ gives ${\alpha }^2|0000⟩+\alpha \beta (|0011⟩+|1100⟩)+{\beta }^2|1111⟩$. Each party applies CNOT $1\to 2$ and measures qubit 2. When both obtain 1, qubits $A_1{B}_1$ are proportional to $|00⟩+|11⟩$. The success probability is $2|\alpha \beta {|}^2$.

After local phases, take $\alpha ,\beta \ge 0$. Alice measures with Kraus operators $M_1=\mathrm{diag}(\alpha ,\beta )$ and $M_2=\mathrm{diag}(\beta ,\alpha )$, which satisfy $M_1^{†}{M}_1+M_2^{†}{M}_2=I$. Outcome 1 directly gives $\alpha |00⟩+\beta |11⟩$. Outcome 2 gives $\beta |00⟩+\alpha |11⟩$; Alice tells Bob the outcome and both apply $X$, swapping the two coefficients. Thus the conversion succeeds with certainty, in agreement with Nielsen majorization.

A class is axiomatisable if it is exactly the class of models of some set of first-order sentences in the given language.

Compactness theorem says a set of first-order sentences has a model whenever each finite subset has a model.

If a theory axiomatized precisely the Archimedean fields, add a constant $c$ and sentences $t_n<c$ for every $n$. Every finite subset has an Archimedean model with $c$ sufficiently large, so compactness gives a model of the whole set. Its field reduct satisfies the proposed theory but is non-Archimedean, a contradiction.