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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

Atomic one-variable formulas reduce to polynomial equalities and inequalities after clearing terms. Their solution sets are basic by the supplied fact. Basic sets are closed under finite union, intersection, and complement; structural induction through the Boolean connectives therefore proves the claim.

Solved by gpt-5.6-sol high.

Quantifier elimination makes $S=\{x:\exists y(y^2=x)\}$ basic. It contains every square and no negative element. If some $a>0$ were not a square, $S$ would have a boundary inside $(0,\infty )$; but multiplication by positive squares and the ordered-field inequalities force membership to be locally constant along positive multiplicative intervals, contradicting the finite-endpoint form of a basic set. Hence every positive element, and also zero, is a square.

Solved by gpt-5.6-sol high.

If $Av=\lambda v$, choose $i$ with $|v_i|$ maximal. Then $|\lambda ||v_i|=|{\sum }_{j\sim i}{v}_j|\le d(i)|v_i|\le \Delta |v_i|$, so $|\lambda |\le \Delta$.

Solved by gpt-5.6-sol high.

For a $\Delta$-regular graph, $A1=\Delta 1$. Conversely equality in the preceding maximum-coordinate proof propagates equal absolute values and compatible signs through connectedness, forcing every vertex degree $\Delta$. Perron-Frobenius, or the same equality argument, makes the eigenspace one-dimensional.

Solved by gpt-5.6-sol high.

$(A^r{)}_{ij}$ counts length-$r$ walks from $i$ to $j$, so $\mathrm{tr}{A}^r$ counts length-$r$ closed walks. The given power sums identify the spectrum as $5$ once, $\sqrt{5}$ and $-\sqrt{5}$ three times each, and $-1$ five times. Thus $n=12$, regular degree $d=5$, and the size is $nd/2=30$.

Solved by gpt-5.6-sol high.

Strong regularity $(n,d,a,b)$ means degree $d$, with $a$ common neighbours for adjacent pairs and $b$ for nonadjacent pairs. Counting two-step walks gives $(n-d-1)b=d(d-a-1)$; eigenvalue multiplicities impose the standard rationality condition. Here $a=0,b=3$, so $n=1+d(d+2)/3$. Applying multiplicity integrality to roots of $x^2+3x+3-d$ leaves $d\in \{1,3,21\}$. For $d=3$, $K_{3,3}$ is the required example.

Solved by gpt-5.6-sol high.

Finite means $[L:K]<\infty$; algebraic means every element satisfies a nonzero polynomial over $K$. Linear dependence among $1,x,\dots ,x^n$ proves finite implies algebraic. The algebraic closure $\overline{\mathbb{Q}}/\mathbb{Q}$ is algebraic but infinite.

Solved by gpt-5.6-sol high.

An algebraic $x$ is separable when its minimal polynomial has distinct roots. In characteristic zero its derivative cannot vanish. In characteristic $p$, repeatedly write an inseparable minimal polynomial as a polynomial in $X^p$; after finitely many steps the minimal polynomial of $x^{p^n}$ has nonzero derivative and is separable.

Solved by gpt-5.6-sol high.

Let $\alpha =2^{1/6}=\sqrt{2}/\sqrt[3]{2}$. Then $L=\mathbb{Q}(\alpha ,{\zeta }_3)$ is the splitting field of $X^6-2$. Eisenstein gives $[\mathbb{Q}(\alpha ):\mathbb{Q}]=6$, and adjoining nonreal ${\zeta }_3$ doubles it, so the degree is 12 and the extension is Galois. Valuation at a prime above 2 forces $n\mid 6$ if $x^n=2$; conversely $x={\alpha }^{6/n}$ works for $n=1,2,3,6$.

Solved by gpt-5.6-sol high.

$SU(2)=\{A:A^{\ast }A=I,\det A=1\}$; every element is $\left(\begin{array}{cc}a& b\\ -\bar{b}& \bar{a}\end{array}\right)$ with $|a{|}^2+|b{|}^2=1$, giving $S^3$. A maximal torus is $T=\{\mathrm{diag}(e^{it},e^{-it})\}$. A noncentral conjugacy class is determined by trace $2\cos t$, has stabilizer $T$, and is $SU(2)/T\simeq S^2$; it meets $T$ at the two inverse diagonal elements. Since $SU(2)$ has no nontrivial continuous characters, $\det \rho =1$.

Solved by gpt-5.6-sol high.

Map the quaternion generators to $i{\sigma }_x,i{\sigma }_y$ (and their products), obtaining the unique two-dimensional irreducible $V$ and an embedding $Q_8\subset SU(2)$. Clebsch-Gordan gives $V\otimes V\simeq {\mathrm{Sym}}^{2}V\oplus 1$ and $V^{\otimes 3}\simeq {\mathrm{Sym}}^{3}V\oplus V\oplus V$. On restriction, ${\mathrm{Sym}}^{2}V$ is the sum of the three nontrivial one-dimensional characters of $Q_8$, while the other summand is trivial.

Solved by gpt-5.6-sol high.

Subdivide the torus so $p,q$ are vertices and add an edge path between them; identifying its endpoints yields a finite simplicial model, so $X$ is triangulable.

Solved by gpt-5.6-sol high.

Identifying two points in a path-connected space is homotopy equivalent to adjoining a circle, so $X\simeq T^2\vee S^1$. Hence $H_0=\mathbb{Z}$, $H_1={\mathbb{Z}}^3$, $H_2=\mathbb{Z}$, and all higher homology vanishes.

Solved by gpt-5.6-sol high.

No. Collapse the one-skeleton of the torus summand to obtain a map $X\to S^2$ inducing degree one on $H_2$. A null-homotopic map induces zero on reduced homology.

Solved by gpt-5.6-sol high.

$\sigma (T)=\{\lambda :T-\lambda I\text{ is not invertible}\}$ and $r(T)={\sup }_{\lambda \in \sigma (T)}|\lambda |$, well-defined because the spectrum is nonempty compact. If $|\lambda |>\Vert T^n{\Vert }^{1/n}$, factor $T^n-{\lambda }^{n}I$ and use a Neumann series; spectral mapping then excludes $\lambda$. Thus $r(T)\le {\inf }_n\Vert T^n{\Vert }^{1/n}$.

Solved by gpt-5.6-sol high.

Complex Stone-Weierstrass requires a self-conjugate unital subalgebra separating points; apply real Stone-Weierstrass to real and imaginary parts. Finite sums $f(x)g(y)$ form such a self-conjugate unital subalgebra of $C(K\times L)$ and separate points, so they are dense.

Solved by gpt-5.6-sol high.

$\Vert T_{h}f{\Vert }_{\infty }\le \Vert h{\Vert }_{\infty }\Vert f{\Vert }_{\infty }$, so $T_h$ is bounded, and $h\mapsto T_h$ is linear with operator norm at most one.

Solved by gpt-5.6-sol high.

Approximate $h$ uniformly by finite sums $\sum f_j(x)g_j(y)$; their integral operators have finite-dimensional range and converge in operator norm, so $T_h$ is compact. If $h(x,y)=0$ for $x\le y$, iterated integration over an ordered simplex gives $\Vert T_h^n\Vert \le \Vert h{\Vert }_{\infty }^n/n!$. Thus $r(T_h)=0$, and compact spectral theory gives $\sigma (T_h)=\{0\}$.