Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 4

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ has at most $d$ roots. To prove it, use mathematical induction on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, polynomial division in the field ${\mathbb{F}}_p$ gives $f(X)=(X-a)q(X)$ with $\mathrm{deg}q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.

Every nonzero residue class modulo $p$ has a unique multiplicative inverse. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and thereforeThis is Wilson theorem.

Now write $p-1=kq$. By Fermat's little theorem, every nonzero class is a root ofThe second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv 1(\mathrm{mod}p)$ has exactly $k$ solutions.

A subset $A$ of a metric space is nowhere dense when the interior of its closure is empty. One form of the Baire category theorem says that a nonempty complete metric space cannot be a countable union of nowhere dense closed sets; equivalently, a countable intersection of dense open sets is dense.

Fix $\epsilon >0$ and work in the complete interval $[1,2]$. For $N\ge 1$ define the closed setThe sets are closed by the continuity of $f$, and the assumed pointwise convergence gives $[1,2]={\bigcup }_N{E}_N$. The Baire category theorem therefore gives an $N$ and a nonempty open interval $(a,b)\subseteq [1,2]$ contained in $E_N$.

The intervals $[na,nb]$ overlap once $(n+1)a\le nb$, which holds for every sufficiently large natural number $n$. Their union consequently contains a half-line. Every sufficiently large $t$ can therefore be written as $t=nx$ with $n\ge N$ and $x\in (a,b)$, and then $|f(t)|=|f(nx)|\le \epsilon$. Since $\epsilon$ was arbitrary, $f(t)\to 0$ as $t\to \infty$.

A cipher has perfect secrecy when the conditional probability of every plaintext given a ciphertext equals its prior probability: $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$ whenever $\mathrm{Pr}(C=c)>0$. Equivalently, the plaintext and ciphertext are independent random variables.

Fix a ciphertext $c$ that can occur. Perfect secrecy requires every possible plaintext $m$ to remain possible after observing $c$. For a deterministic decryption rule, two different plaintexts producing $c$ require two different keys, so the key space has cardinality at least that of the message space.

In a one-time pad, the message and key belong to the same finite additive group, the key is uniform and independent of the message, and encryption is $C=M+K$. For every $m,c$ there is exactly one key $k=c-m$, soindependent of $m$. Bayes theorem then gives $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$, proving perfect secrecy.

Perform every addition in the finite field ${\mathbb{F}}_2$. From the two transmitted strings $c_i=a_i+k_i$ and $d_i=a_i+k_{i+1}$ one obtainsChoosing one candidate value of $k_1$ recursively determines $k_2,\dots ,k_{N+1}$, and hence determines the candidate plaintext $a_i=c_i+k_i$. There are only two candidates: changing $k_1$ complements every recovered key bit and every plaintext bit. The information that the message makes sense normally selects the intended candidate.

Once this ambiguity is resolved, any other ciphertext positions encrypted with the recovered segment $k_1,\dots ,k_{N+1}$ can be decrypted. Key bits outside that segment remain independent and uniformly distributed, so this mistake gives no information about messages using only those bits. This is the two-time pad attack: reusing related one-time-pad key material destroys perfect secrecy.

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals and $a$ is a terminal symbol; one may additionally allow the new start production $S_0\to ϵ$ when the language contains the empty string, provided $S_0$ never appears on a right-hand side.

The standard conversion proceeds as follows.

The terminal alphabet $\Sigma$ may be kept unchanged throughout, although unused terminals may be discarded by convention. Every stage preserves the generated language, with the explicit protection of $ϵ$ at the start-symbol stage. For example,is already in Chomsky normal form and generates the infinite language $\{a^n:n\ge 1\}$, so its conversion may be the grammar itself.

The individual t-tests only test each regression coefficient after adjusting for the other covariate. Here neither covariate is individually significant at conventional levels, but from the abbreviated coefficient table alone one cannot conclude that neither explains the response: strong multicollinearity can make both standard errors large even when the covariates are jointly useful.

The full F-test has $p<2.2\times 10^{-16}$ and tests the null hypothesis that both slope coefficients vanish. It decisively rejects that hypothesis, while $R^2=0.8126$ says the fitted model explains about $81\%$ of the sample variation. Together with the insignificant individual t-tests, this is characteristic of multicollinearity: the two covariates explain the response jointly, but the output does not identify either one as having a separately estimable effect.

Here the full F-test has $p=0.9834$ and $R^2\approx 0$. There is no evidence against the joint null hypothesis that both slopes vanish, and hence no evidence in this model that either covariate explains the response.

The intercept-only model has $49$ residual degrees of freedom, so the sample size is $50$. The one-covariate model and full model therefore have respectively $48$ and $47$ residual degrees of freedom. The completed sequential analysis of variance table hasThus the missing sums of squares are $133.617$ and $0.014$, and the corresponding F-statistics are approximately $203.8$ and $0.0214$. The first p-value is below $2\times 10^{-16}$; the second is approximately $0.8845$. The tiny second increment is consistent with the reported t-test because, for one added coefficient, the partial F-statistic equals the squared t-statistic up to displayed rounding.

This is a Yule process, a pure birth process with state-dependent birth rate ${\lambda }_n=\lambda n$. Probability flows into state $n$ from $n-1$ and leaves it for $n+1$, so the master equation is

Put $q=e^{-\lambda t}$ and propose $P_n=q(1-q{)}^{n-1}$. The initial condition follows from $q(0)=1$. Since $q^{\prime }=-\lambda q$,On the other hand,and expanding the bracket gives the same expression. The formula also sums to one by the geometric series, so it is the required probability mass function.

The distribution is the geometric distribution on $\{1,2,\dots \}$ with success parameter $q=e^{-\lambda t}$. Its expected value is thereforeEquivalently, multiplying the master equation by $n$ and summing gives $m^{\prime }(t)=\lambda m(t)$ with $m(0)=1$.

With the stated sign convention, write $t=y-x$ to obtainThe Cauchy principal value of the cosine part vanishes by oddness, while the Dirichlet integral givesThus the Hilbert transform has Fourier multiplier $-i\mathrm{sgn}(\omega )$. Taking the real part yields

Write the position of a mass element relative to the center of mass as $\mathbf{r}$, so its inertial-frame velocity is $\dot{\mathbf{X}}+\mathbf{\omega }\times \mathbf{r}$. The center-of-mass identity $\int \mathbf{r}dm=0$ removes all cross terms. Define the inertia tensor about the center of mass byThe total angular momentum about the origin and kinetic energy are then

Let $\rho (r)=C{r}^{-1}\sin (\pi r/R)$. Spherical symmetry makes $I=I_{0}1$. The mass normalization isso $C=M/(4R^2)$. A moment about any diameter isTherefore

Chemical equilibrium for $p+e^{-}\rightleftharpoons H+\gamma$ gives ${\mu }_p+{\mu }_e={\mu }_H$, because the photon chemical potential vanishes. Applying the nonrelativistic number-density formula to all three massive species and taking the ratio givesUse charge neutrality $n_p=n_e$, the Hydrogen binding energy $E_{\mathrm{bind}}=m_p{c}^2+m_e{c}^2-m_H{c}^2$, $m_H\simeq m_p$, and the ground-state statistical weights $g_H=g_p{g}_e$. ThenThe approximations are a dilute, nondegenerate ideal gas in thermal and chemical equilibrium, nonrelativistic electrons, protons and hydrogen, negligible excited hydrogen states, and negligible corrections from the proton-to-hydrogen mass ratio. This relation is the Saha ionization equation.

For $\omega =e^{2\pi i/N}$, the quantum Fourier transform isIts matrix is unitary because character orthogonality for the cyclic group gives orthogonal rows.

For $N=4$, the binary label $10$ is the integer $2$, sowhere $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ and $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. It is a product state and hence has no quantum entanglement.

Applying the transform twice givesBy the finite geometric series, the inner sum over $y$ is $N$ when $x+z\equiv 0(\mathrm{mod}N)$ and zero otherwise. Thereforewhich is the stated $|N-x⟩$ with the label interpreted modulo $N$.

The map $x\mapsto -x$ is an involution, soIf $\lambda$ is an eigenvalue of ${\mathrm{QFT}}_N$, then ${\lambda }^4=1$. Hence every eigenvalue belongs toBecause $X^4-1$ has distinct roots, the transform is diagonalizable; which fourth roots occur and their multiplicities depend on $N$.

An arithmetic function $f$ is multiplicative when $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime. If $m$ and $n$ are coprime, every divisor $d$ of $mn$ has a unique factorization $d=d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Hence the Dirichlet convolution of multiplicative functions satisfiesand $(f\star g)(1)=1$, so it is multiplicative.

Let $\epsilon$ be the identity for Dirichlet convolution, with $\epsilon (1)=1$ and $\epsilon (n)=0$ for $n>1$. The Möbius function satisfies $\mu \star 1=\epsilon$. Therefore, using commutativity and associativity,This is the Möbius inversion formula.

Take both functions to be the constant arithmetic function $1$. Thenso the divisor function is multiplicative by part (a). For $s$ with $\mathrm{Re}s>1$, the relevant Dirichlet series are absolutely convergent, so their Cauchy product may be rearranged:Equivalently, Dirichlet convolution becomes multiplication of absolutely convergent Dirichlet series.

Let $P=p_1{p}_2\cdots p_{k+1}$ be the product of the first $k+1$ primes, and take $n=P^a$ for positive integers $a$. The prime factorization givesTheir ratio isThus every sufficiently large $a$ gives $\tau (P^a)\ge (\log P^a{)}^k$, producing infinitely many such $n$.

If $n={\prod }_{p^{\alpha }\parallel n}{p}^{\alpha }$, multiplicativity and the prime-power formula for the divisor function giveChoose $P_0=2^{1/ϵ}$. For $p\ge P_0$ and $\alpha \ge 1$, the elementary bound $\alpha +1\le 2^{\alpha }$ givesFor each of the finitely many primes $p<P_0$, the sequence $(\alpha +1)p^{-\alpha ϵ}$ tends to zero and therefore has a finite maximum $M_p$ over $\alpha \ge 0$. Consequentlyuniformly in $n$, which proves $\tau (n)\le C(ϵ)n^{ϵ}$.

Liouville approximation theorem states that if $\alpha$ is a real algebraic number of degree $d\ge 2$, then there is a constant $c(\alpha )>0$ such thatfor every rational $p/q$ with $q>0$. The strict inequality may be replaced by a non-strict one after changing the constant.

The convergents satisfyso $(p_n,q_n)$ and $(p_{n-1},q_{n-1})$ form an integer basis of ${\mathbb{Z}}^2$. Put ${\delta }_j=q_j\alpha -p_j$. Consecutive errors have opposite signs and $|{\delta }_{n-1}|>|{\delta }_n|$.

For integers $p,q$ with $0<q\le q_n$, writeIf $s>0$, the denominator bound forces $r\le 0$, while if $s<0$ positivity forces $r\ge 1$. Because ${\delta }_n$ and ${\delta }_{n-1}$ have opposite signs, in either case $s\ne 0$ impliesIf $s=0$, the denominator bound gives $r=1$ unless the fraction is zero or has the same value as $p_n/q_n$. Thus $p_n/q_n$ is a best approximation of the second kind. Dividing by $q\le q_n$ gives

Suppose $a_j\le A$ for every $j$. Given $b>0$, choose the first convergent denominator $q_m\ge b$. Then $q_{m-1}<b$ and the recurrence gives $q_m=a_m{q}_{m-1}+q_{m-2}<(A+1)b$. Part (i), applied at index $m$, gives $|b\alpha -a|\ge |q_m\alpha -p_m|$.

If ${\alpha }_{m+1}=[a_{m+1};a_{m+2},\dots ]$ is the complete quotient, the exact error formula isSince ${\alpha }_{m+1}<A+1$, this is greater than $1/((A+2)q_m)$ and therefore greater than $1/((A+1)(A+2)b)$. It follows that every rational $a/b$ satisfiesThus one may take $c=((A+1)(A+2){)}^{-1}$.

Consecutive convergents obey the standard error estimateIf the partial quotients are unbounded, then for every $c>0$ there are infinitely many indices with $a_{n+1}>1/c$; otherwise the whole sequence would be bounded after adjoining its finite initial segment. At each such index,The denominators of the infinite continued fraction tend to infinity, so these give infinitely many distinct rational numbers of the required kind.

A generalized linear model assumes independent responses from one exponential dispersion family,where ${\sigma }_i^2=a_i{\sigma }^2$, ${\mu }_i=\mathbb{E}[Y_i]=b^{\prime }({\theta }_i)$, and a link function relates the mean to the linear predictor by $g(\mu )=X\beta$. It follows from normalization of the density after shifting the natural parameter thatIndependence therefore gives the joint moment-generating functionwhenever every shifted natural parameter lies in its natural-parameter domain.

Let $m=1/{\sigma }^2$. Within block $i$, the $m$ replicated observations have dispersion $a_i$ and common natural parameter ${\theta }_i$. Evaluating their joint MGF at the blockwise argument ${\sigma }^2{t}_i$ givesMultiplying over blocks reproduces the MGF of $Y$ from part (a). Since moment-generating functions uniquely determine distributions in this family, $\bar{Y}\stackrel{d}{=}Y$.