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

A primitive root modulo $N$ is a unit of order $\phi (N)$; a nonzero quadratic residue modulo an odd prime $p$ is a square.

If a primitive root $g$ modulo $p$ were $x^2$, then its order would divide $(p-1)/2$, the order of the subgroup of squares, contradicting ${\mathrm{ord}}_p(g)=p-1$.

Modulo $11$, $2$ has order $10$, so the primitive roots are $2^k$ for $\gcd (k,10)=1$:Finally $2^{10}=1024\equiv 56\not\equiv 1(\mathrm{mod}121)$, so the lifting criterion makes $2$ primitive modulo $121$. It is plainly the smallest possible positive primitive root.

The planar Brouwer fixed-point theorem says every continuous $F:D^2\to D^2$ has a fixed point. The equivalent no-retraction theorem says no continuous $r:D^2\to S^1$ restricts to the identity on $S^1$. A fixed-point-free map gives a retraction by extending the ray from $F(x)$ through $x$ to the boundary; a retraction followed by the antipodal map gives a fixed-point-free self-map.

Suppose the stated sphere map is not onto and omits $p$. Compactness gives $\epsilon >0$ such that its image lies in $S^2\setminus B_{\epsilon }(p)$. That set is homeomorphic to a closed disc. Restricting $f$ to it gives a continuous self-map of a disc, so Brouwer supplies a fixed point, contrary to the hypothesis. Hence $f$ is surjective.

Apply Huffman coding. Combining weightsgives, for example,Any consistent interchange of siblings is equivalent.

For the binary code above, the lengths are $1,2,3,5,5,5,5$. ThusThis is optimal by Huffman coding.

The ternary merges are $(.02,.03,.04)\mapsto .09$, then $(.04,.09,.14)\mapsto .27$, then $(.27,.28,.45)\mapsto 1$. One code isIts expected length is

The basic functions are zero $Z(\mathbf{x})=0$, successor $S(n)=n+1$, and projections $P_i^k(\mathbf{x})=x_i$. Close these under composition and primitive recursion:

Define $A(0,m)=m$ and $A(n+1,m)=S(A(n,m))$. This is primitive recursion from a projection and successor, so $A(n,m)=n+m$ is primitive recursive function.

If $f$ is primitive recursive, then $d(n)=f(P_1^1(n),P_1^1(n))$ is obtained by composition with projections. Hence the diagonal is primitive recursive.

Assume a complete list $f$ were primitive recursive. Closure under diagonal composition and successor makesprimitive recursive. Completeness gives a row $n$ with $f(n,k)=d(k)$ for every $k$, but at $k=n$ this says $f(n,n)=f(n,n)+1$. This is the diagonal argument.

The normal linear model is $Y=X\beta +\epsilon$ with $\epsilon \sim N(0,{\sigma }^2{I}_n)$. Full column rank givesWith hat matrix $H=X(X^{T}X{)}^{-1}{X}^T$, the $i$th regression leverage is $h_{ii}$. Since $e=(I-H)Y=(I-H)\epsilon$ and $I-H$ is an orthogonal projection,High-leverage observations can move their own fitted values strongly and may exert disproportionate influence; residual size alone can therefore conceal them.

The cross-infection terms transfer susceptible individuals into the infected class: $\beta S\hat{I}$ is male incidence caused by infected females and $\hat{\beta }\hat{S}I$ is female incidence caused by infected males. The terms $\nu I$ and $\hat{\nu }\hat{I}$ are recovery flows back to susceptibility. Adding each susceptible-infected pair shows that $N$ and $\hat{N}$ are conserved.

Substitute $S=N-I$ and $\hat{S}=\hat{N}-\hat{I}$:Besides the origin, solve both nullcline equations. Eliminating one infected population givesThe assumed epidemic threshold inequality makes both positive.

At the origin the Jacobian isThus it is a saddle and unstable. At the positive equilibrium the trace is negative. The product of the off-diagonal entries is $\nu \hat{\nu }$ by the nullcline identities, while the product of the magnitudes of the diagonal entries is strictly larger, so the determinant is positive. Both eigenvalues therefore have negative real part and the endemic equilibrium is stable.

The ordinary integral fails because the simple real poles at $-2$ and $3$ produce nonintegrable logarithmic singularities. Partial fractions giveClosing above for $\omega >0$ and below for $\omega <0$, with symmetric semicircular indentations, yieldsTaking real and imaginary parts,All integrals here run over $\mathbb{R}$.

Stationarity of the action under variations with fixed endpoints gives the Euler-Lagrange equation. The generalized momentum is $p=\partial L/\partial \dot{q}$. The Legendre transform in mechanics isafter solving $p(q,\dot{q},t)$ for $\dot{q}$. This requires at least local invertibility, ${\partial }^{2}L/\partial {\dot{q}}^2\ne 0$; global single-valuedness requires global invertibility.

By Hamiltonian of a charged particle,

HereHence

Differentiate $\mathcal{G}={\sum }_i{\mathbf{p}}_i\cdot {\mathbf{r}}_i$:

Pair the $ij$ and $ji$ terms and use ${\mathbf{f}}_{ji}=-{\mathbf{f}}_{ij}$:For gravity, ${\mathbf{f}}_{ij}=-G{m}^2({\mathbf{r}}_i-{\mathbf{r}}_j)/|{\mathbf{r}}_i-{\mathbf{r}}_j{|}^3$, so each summand is $-G{m}^2/|{\mathbf{r}}_i-{\mathbf{r}}_j|$. Their sum is $V$.

For a confined system, $\mathcal{G}(t)$ stays bounded, so its long-time averaged derivative is zero. The preceding identities give the virial theorem

Estimate $T\sim M⟨v^2⟩/2$ and $V\sim -G{M}^2/⟨R⟩$. The virial theorem givesup to a profile-dependent factor. If this exceeds the stellar/gas luminous mass, the difference is attributed primarily to dark matter (with modelling uncertainties and non-equilibrium effects checked).

The quantum no-signalling principle says Alice's uncommunicated local choice cannot alter Bob's reduced state. Expanding the two tensor products cancels the cross terms and givesAlice obtains either result with probability $1/2$; conditionally Bob has probability ${\cos }^2\theta$ or ${\sin }^2\theta$ of $0$, respectively. Averaging,independent of $\theta$, exactly as no-signalling requires.

The Helstrom-Holevo bound for equal priors isPerfect cloning twice changes overlap $c$ to $c^2$, so discrimination would succeed with $\frac{1}{2}(1+\sqrt{1-c^4})$, strictly exceeding $\frac{1}{2}(1+\sqrt{1-c^2})$ for $0<c<1$. For $|0⟩,|+⟩$, $c=1/\sqrt{2}$, producing $\frac{1}{2}(1+\sqrt{3}/2)>\frac{1}{2}(1+1/\sqrt{2})$, a contradiction.

The parity-check matrix has rank $3$, so its kernel has dimension $7-3=4$ and size $16$; see linear code. Its columns are precisely the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$. Thus no weight-one or weight-two word is in the kernel, while three dependent columns give a weight-three word. Hence $d=3$.

By parity extension, each code keeps size $16$, gains length $8$, and has distance $4$. Extension is injective. A common extended word punctures to a word in $H\cap K$, so only the zero and all-one words occur; both extend to $00000000$ and $11111111$.

Write the three blocks as $u=a+x$, $v=b+x$, $w=a+b+x$. Over ${\mathbb{F}}_2$,Thus the parameters are unique and $|G|=|H^{\prime }{|}^2|K^{\prime }|=16^3=2^{12}$.

Every nonzero word has weight divisible by $4$. Weight $4$ is impossible: using $u+v=a+b$, $u+w=b$, $v+w=a$, and $u+v+w=x$, the distance-four properties force any nonzero one of these sums to have weight $4$; coordinate counting in total weight $4$ then forces two blocks to vanish, which would put a nontrivial word in $H^{\prime }\cap K^{\prime }$. That intersection contains only $0$ and $1$, and $1$ gives block weight at least $8$. Hence $d(G)\ge 8$, and taking $a\ne 0,b=x=0$ gives weight $2\mathrm{wt}(a)=8$, so $d(G)=8$.

Puncturing gives a binary code of length $23$, size $2^{12}$, and distance at least $7$. Radius-three balls are disjoint andThe Hamming bound is an equality, so $G^{-}$ is perfect.

A variable-based grammar is $(N,\Sigma ,P,S)$ with disjoint nonterminals and terminals, productions between words over $N\cup \Sigma$, and start variable $S$. Its language is $\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

A type-2 rule is $A\to \alpha$ with one nonterminal $A$ on the left; a type-2 grammar and its language are context-free languages. The required repetition criterion is the pumping lemma for context-free languages.

This language is context-free. One grammar iswhich independently chooses at least one outer $a,c$ pair and at least one $b$.

It is not context-free. Intersecting it with the regular language $a^{\ast }{b}^{\ast }{c}^{\ast }$ would give $\{a^n{b}^n{c}^n:n\ge 0\}$, which violates the pumping lemma for context-free languages. Context-free languages are closed under intersection with regular languages.

No production introduces $A$, so the two rules containing $A$ are unreachable. The effective derivations areThus the language is $\{a^n{b}^n{c}^n:n\ge 1\}$, which is not context-free language, although the displayed grammar itself also visibly has non-type-2 left sides.

For one observation,Thus this is an exponential family with natural parameter $\theta =\log \lambda$, statistic $T(y)=y$, base measure $1/y!$, and cumulant $A(\theta )=e^{\theta }$.

For nonnegative $y_i$ summing to $m$, divide the joint Poisson mass by $P(M=m)=e^{-{\lambda }_{+}}{\lambda }_{+}^m/m!$:This is independent Poisson conditioning.

In the log-linear model fit1 has only three main effects, so its fitted mean factors into a species factor, a diameter factor, and a height factor: mutual independence. Fit2 adds the species-diameter interaction, allowing those variables to associate, while asserting $\text{Height}\perp (\text{Species},\text{Diameter})$.

The likelihood-ratio deviance drop $12.606$ on one degree of freedom has $p=0.0003845$, strong evidence against species-diameter independence. Test fit2's remaining independence claim by comparing it with a model adding both Species:Height and Diameter:Height interactions (equivalently compare fit2 with the saturated model); its residual deviance $12.431$ is assessed against ${\chi }_3^2$.

Put $\Gamma (z)=I(z)$ for $\Re z>0$. Integration by parts gives $\Gamma (z+1)=z\Gamma (z)$, both proving $\Gamma (n)=(n-1)!$ and defining the meromorphic continuation. A keyhole-contour evaluation of ${\int }_0^{\infty }{t}^{z-1}/(1+t)dt$ gives

Forthe reflection formula at $z$ and $z+\frac{1}{2}$ gives $g(z+1)-g(z)=-2\log 2$. Thus $h(z)=g(z)+2z\log 2$ is entire and $1$-periodic; poles and zeros have cancelled in the quotient. Its Fourier expansion and the exponential growth bound make it a finite Laurent polynomial in $e^{2\pi iz}$; the same growth bound for $e^h$ excludes every nonconstant mode. Hence $h=b$. At $z=1/2$, $e^b=2\sqrt{\pi }$, yielding the duplication formula.

Set $z=1/6$ and use reflection at $1/3$:Therefore

The conservation equation with $P=w\rho$ gives $d\rho /\rho =-3(1+w)da/a$, henceThe critical density and density parameter are

Radiation has $w=1/3$, matter $w=0$, and a cosmological constant has constant density. With negligible curvature and present-day normalization,where the present density fractions sum to one.

Phantom energy with $w=-4/3$ has ${\rho }_P\propto a$, so flatness givesFor $b^2=1+{\beta }^{2}a$, integration yieldsSolving gives the displayed scale factorFor $1-\Omega \ll 1$ and times near $t_0$, this approaches de Sitter growth $e^{H_0\sqrt{\Omega }(t-t_0)}$. The denominator vanishes atEven a tiny phantom fraction therefore ends expansion in finite time; its divergent density ultimately disrupts loosely bound systems.

A choice function on a family $\mathcal{A}$ of nonempty sets satisfies $c(A)\in A$. Zermelo's theorem says every set has a total order under which every nonempty subset has a least element.

Choose from every nonempty subset of $X$. By transfinite recursion setwhile the remainder is nonempty. This cannot continue through Hartogs theorem's ordinal $h(X)$, since that would inject $h(X)$ into $X$. It therefore exhausts $X$ at some ordinal, and the selection order well-orders $X$.