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

Legendre formula giveswhose summands are zero or one. If the sum is at least $k$, some nonzero summand has index $j\ge k$, whence $p^k\le p^j\le 2n$.

Grouping the von Mangoldt function by prime givesEvery prime-power contribution to $\log \left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ occurs in $\psi (2n)$ by the first part. Finally $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)={\prod }_{j=1}^n(n+j)/j\ge 2^n$, so $\psi (2n)\ge n\log 2$.

The Brouwer fixed-point theorem says that every continuous map from a closed two-dimensional disk to itself has a fixed point.

The equivalent no-retraction theorem says there is no continuous retraction of the closed disk onto its boundary circle. A fixed-point-free map gives a retraction by projecting from $f(x)$ through $x$ to the boundary; conversely a retraction composed with the antipodal boundary map gives a fixed-point-free self-map.

On the simplex define $f(x)=Ax/(1^{T}Ax)$. Strict positivity makes the denominator positive and maps the simplex continuously into its interior. By Brouwer fixed-point theorem, $f(x)=x$ for some $x$. Thus $Ax=\lambda x$, where $\lambda =1^{T}Ax>0$, and because $Ax$ is strictly positive, so is $x$.

For Rabin cryptosystem, choose primes $p,q\equiv 3(\mathrm{mod}4)$, publish $N=pq$, and encrypt $x$ as $x^2\mathrm{mod}N$. The factors let the receiver take square roots modulo $p$ and $q$ and combine them using the Chinese remainder theorem; redundancy identifies the intended one of four roots.

For RSA cryptosystem, choose $N=pq$, select $e$ coprime to $\phi (N)$ and $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Encrypt $x$ as $x^e$ and decrypt by raising to $d$ modulo $N$. Rabin inversion is provably equivalent to factoring, while ordinary RSA lacks that reduction; Rabin's disadvantage is its fourfold decryption ambiguity.

The pumping lemma for regular languages says that sufficiently long accepted words split as $xyz$ with $|xy|\le P$, $|y|>0$, and $x{y}^{k}z$ accepted for all $k\ge 0$. Applying it to $0^P{1}^{P}01$ pumps only zeros, so language (i) is not regular.

This language is not regular. Intersecting with the regular language $0^{\ast }110^{\ast }$ isolates strings whose two zero blocks must have equal length; the pumping lemma then gives a contradiction.

A word containing neither $01$ nor $10$ cannot change symbol. The language is therefore $0^{\ast }\cup 1^{\ast }$, hence is regular.

This is Poisson regression with independent counts and log mean $\log {\mu }_d=1.5624+0.1658d$. The residual deviance $9.90$ on $12$ degrees of freedom has $p=0.625$, and the plotted curve tracks the data, so there is no evidence of poor fit.

The fitted doubling time is $\log 2/0.1658=4.16$ days. A 95% interval for the growth coefficient is $0.1658\pm 1.96(0.0166)=(0.133,0.198)$, corresponding to doubling times $(3.50,5.21)$ days. Seven days, whose rate is about $0.099$, is unsupported.

The terms are logistic birth and crowding, $rn-r{n}^2/K$, linear predation mortality $-\delta n$, and diffusion $D{n}_{xx}$. The coast is reflecting, so $n_x(0)=0$; lethal habitat beyond $L$ gives the absorbing condition $n(L)=0$.

Linearizing at extinction gives $n_t=(r-\delta )n+D{n}_{xx}$. The principal eigenfunction for Neumann data at $0$ and Dirichlet data at $L$ is $\cos (\pi x/(2L))$, with growth rateA population is viable exactly when this is positive, requiring $r>\delta$ and $L>(\pi /2)\sqrt{D/(r-\delta )}$. Thus intrinsic growth must beat predation and the refuge must exceed the diffusion-dependent critical size.

A Riemann P-symbol specifies a second-order Fuchsian equation with regular singular points $a,b,c$ and the two local exponents shown beneath each point. The Fuchs relation is $\alpha +\alpha \prime +\beta +\beta \prime +\gamma +\gamma \prime =1$.

Set $z\prime =(1-z)/2$, sending $1,-1,\infty$ to $0,1,\infty$. Then rescale the dependent variable byThis shifts the exponent pairs to $(0,m)$ at zero and $(0,-m)$ at one, while leaving the exponents at infinity unchanged.

The hypergeometric exponent differences give $1-c=m$, $c-a-b=-m$, and exponents $a,b$ at infinity. Hence one may takeso a solution is ${}_2{F}_1(n,1-n;1-m;(1-z)/2)$, with the prefactor from part (i) when returning to the original dependent variable.

A Lagrange top is an axially symmetric rigid body with one point fixed, centre of mass a distance $l$ along its symmetry axis, principal moments $I_1=I_2,I_3$, mass $M$, and Euler angles $\theta ,\phi ,\psi$ in gravity $g$.

The cyclic coordinates give $p_{\psi }=I_3(\dot{\psi }+\dot{\phi }\cos \theta )$ and $p_{\phi }=I_1\dot{\phi }{\sin }^2\theta +p_{\psi }\cos \theta$; the energy $E$ is the third integral. Eliminating $\dot{\phi },\dot{\psi }$ from $E$ and setting $u=\cos \theta$, with $\dot{u}=-\dot{\theta }\sin \theta$, yields ${\dot{u}}^2=f(u)$ after multiplication by $1-u^2$; all denominators cancel and $f$ is cubic.

For $I=\frac{1}{2}\sum m_i|x_i{|}^2$, differentiation givesbecause the Newtonian potential is homogeneous of degree $-1$. Bounded positions and velocities imply $\overline{\ddot{I}}=0$, so the virial theorem gives $\overline{T}=-\overline{V}/2$.

Observed stellar velocities estimate $T$, while visible mass and size predict $V$. Galaxies and clusters often have far more kinetic energy than luminous matter can bind under the virial theorem. The additional gravitational potential is evidence for unseen dark matter.

Writing $\omega =e^{2\pi i/N}$, $|{\chi }_k⟩=N^{-1/2}{\sum }_j{\omega }^{-jk}|j⟩$. Therefore $S|{\chi }_k⟩={\omega }^k|{\chi }_k⟩$.

If $|vangle={\sum }_k{c}_k|{\chi }_{k}angle$, then QFT measurement has probabilities $|c_k{|}^2$. Applying $S$ multiplies $c_k$ by the phase ${\omega }^k$, so the probabilities are unchanged.

The offset state is $S^{x_0}$ applied to the offset-zero periodic state. Part (b) therefore makes its QFT output distribution independent of $x_0$. Explicitly, only outcomes divisible by $A=N/r$ occur, each with probability $1/r$; $x_0$ contributes only a phase.

$N$ is a Fermat pseudoprime to base $b$ when it is composite, coprime to $b$, and $b^{N-1}\equiv 1(\mathrm{mod}N)$. Here $N\mid b^k-1$ gives coprimality and $k\mid N-1$, so $b^{N-1}=(b^k{)}^{(N-1)/k}\equiv 1(\mathrm{mod}N)$.

Both $n$ and $m$ divide $b^{2p}-1$, hence so does $N=nm$ after checking $\gcd (n,m)=1$ under the hypothesis. Also $n\equiv p(\mathrm{mod}b-1)$ and the elementary factorization gives $N\equiv 1(\mathrm{mod}2p)$; part (a) with $k=2p$ applies. As odd primes $p$ grow, $N$ grows, yielding infinitely many examples.

By the Chinese remainder theorem, $b^{n-1}\equiv 1(\mathrm{mod}n)$ iff it holds modulo every $p_j$. Since $n-1=p_j{r}_j-1\equiv r_j-1(\mathrm{mod}{p}_j-1)$ and the order of $b$ modulo $p_j$ divides $p_j-1$, this is equivalent to ${\mathrm{ord}}_{p_j}(b)\mid r_j-1$ for every $j$.

For each prime $k\ge 5$, choose a prime divisor $p$ of $2^k-1$ and a prime divisor $q\ne 3$ of $2^k+1$. Their orders are $k$ and $2k$, respectively, so $p\equiv 1(\mathrm{mod}k)$, $q\equiv 1(\mathrm{mod}2k)$, and the criterion in part (c) shows $pq$ is a base-two pseudoprime. The supplied gcd fact makes examples from distinct prime $k$ distinct, so there are infinitely many.

Multiplying the matrices inductively gives columns $(p_n,q_n{)}^T$ and $(p_{n-1},q_{n-1}{)}^T$. Their determinant is $(-1{)}^{n-1}$, and writing $x=(p_n{x}_{n+1}+p_{n-1})/(q_n{x}_{n+1}+q_{n-1})$ givesIf $A{y}^2+By+C=0$, then for rationals $p/q$ near $y$, factorization against the conjugate root gives $|p/q-y|\ge M/q^2$; rationals away from $y$ are handled by reducing $M$. Finally $q_{n+1}\ge a_{n+1}{q}_n$, so the upper bound is at most $1/(a_{n+1}{q}_n^2)$. Unbounded partial quotients contradict the fixed lower bound for a quadratic irrational.

Differentiating the ridge objective gives $(X^{T}X+\lambda I)\hat{\beta }=X^{T}Y$, hence $\hat{\mu }=X(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y=H_{\lambda }Y$.

Since $Y-HY=(I-H)\mu +(I-H)\epsilon$, the cross term has mean zero and $H$ is symmetric. Thus the expectation is $\Vert (I-H)\mu {\Vert }^2+{\sigma }^2\mathrm{tr}(I-H{)}^2$, which expands to the stated expression.

Independence gives $\mathbb{E}\Vert Y^{\ast }-HY{\Vert }^2=\Vert (I-H)\mu {\Vert }^2+n{\sigma }^2+{\sigma }^2\mathrm{tr}{H}^2$. Comparing with part (b) shows the difference is $2{\sigma }^2\mathrm{tr}H$, proving unbiasedness.

Here $H=hI$, $h=(1+\lambda {)}^{-1}$, and prediction risk isIt decreases then increases, with $h^{\ast }=\Vert \mu {\Vert }^2/(\Vert \mu {\Vert }^2+n{\sigma }^2)$, equivalently ${\lambda }^{\ast }=n{\sigma }^2/\Vert \mu {\Vert }^2$. Its minimum is $n{\sigma }^2+n{\sigma }^2\Vert \mu {\Vert }^2/(\Vert \mu {\Vert }^2+n{\sigma }^2)$; the endpoint limits are $2n{\sigma }^2$ and $n{\sigma }^2+\Vert \mu {\Vert }^2$.

This bistable reaction-diffusion equation models an invading population with an Allee effect: densities below $r$ decline, while those above it grow toward carrying capacity one.

The homogeneous equilibria are $0,r,1$. Since $f\prime (0)=-r<0$, $f\prime (1)=r-1<0$, and $f\prime (r)=r(1-r)>0$, the first and last are linearly stable and the middle one unstable.

Multiplying $Dn\prime \prime +f(n)=0$ by $n\prime$ and using the endpoint conditions gives the logistic frontIt has $n_0(0)=1/2$ and direct differentiation verifies the equation for $r=1/2$.

With $\xi =x-ct$, the equation is $Du\prime \prime +cu\prime +f(u)=0$. Since $f_r(u)-f_{1/2}(u)=u(1-u)(1/2-r)$ and $n_0\prime =-n_0(1-n_0)/\sqrt{2D}$, the same profile works with

The speed is positive for $r<1/2$, zero at $1/2$, and negative for $r>1/2$. The state with the larger basin-weighted reaction potential invades the other; raising the Allee threshold favours extinction.

The Poisson bracket is $\{f,g\}={\sum }_i(f_{q_i}{g}_{p_i}-f_{p_i}{g}_{q_i})$. Canonical variables satisfy $\{Q_i,Q_j\}=\{P_i,P_j\}=0$ and $\{Q_i,P_j\}={\delta }_{ij}$.

To first order the conditions are ${\partial }_{p_j}\delta q_i-{\partial }_{p_i}\delta q_j=0$, ${\partial }_{q_j}\delta p_i-{\partial }_{q_i}\delta p_j=0$, and ${\partial }_{q_j}\delta q_i+{\partial }_{p_i}\delta p_j=0$. The choices $\delta q_i=\epsilon F_{p_i}$ and $\delta p_i=-\epsilon F_{q_i}$ satisfy them by equality of mixed partials.

Taylor expansion gives $\delta H=H_q\cdot \delta q+H_p\cdot \delta p=-\epsilon \{F,H\}$. Hamilton's equation gives $\dot{F}=\{F,H\}$, so $F$ is conserved exactly when the generated infinitesimal canonical transformation leaves $H$ invariant.

For a constant translation vector $a$, take $F=a\cdot {\sum }_i{p}_i$. Then $\delta r_i=\epsilon a$ and $\delta p_i=0$. The potential depends only on position differences and the kinetic energy only on momenta, so this is a symmetry and total momentum is conserved.

Axiom of foundation says every nonempty set $A$ contains $a$ with $a\cap A=\varnothing$. Define $T_0=x$, $T_{n+1}=\bigcup T_n$, and $\mathrm{TC}(x)={\bigcup }_{n<\omega }{T}_n$ (including $x$ if that convention is desired). Replacement and union form this set, and it is transitive; induction shows every transitive set containing $x$ contains it.

The principle of membership induction says that if $(\forall y\in xP(y))\Rightarrow P(x)$ for every $x$, then $P$ holds for every set. Otherwise Foundation applied to the set of counterexamples in a suitable transitive closure gives a minimal counterexample.

Apply induction to $P(x):F(x)=x$. If it holds for all $y\in x$, then extensionality and preservation plus surjectivity give $z\in F(x)$ iff $z=F(y)$ for some $y\in x$, iff $z\in x$. Hence $F(x)=x$.

Hall marriage theorem states that a bipartite graph with parts $A,B$ has a matching saturating $A$ iff $|N(S)|\ge |S|$ for every $S\subseteq A$. Starting with a maximum matching, an unmatched vertex and its alternating reachable set would violate Hall unless an augmenting path exists; flipping along that path increases the matching, proving sufficiency.

Every vertex cover meets each edge of a matching, so $\gamma \le \beta$. Endpoints of a maximal matching cover every edge, so $\beta \le 2\gamma$. A disjoint union of $k$ triangles has $(\gamma ,\beta )=(k,2k)$. For $T_3(30)$, $\gamma =15$ and $\beta =30-10=20$. In bipartite graphs the alternating-path proof constructs a cover of size equal to a maximum matching, giving König theorem.

The chromatic index is the minimum number of matchings partitioning the edges. Label vertices of $K_{2^r}$ by the vector space over ${\mathbb{F}}_2$; for each nonzero $a$, pair $x$ with $x+a$. These $2^r-1$ perfect matchings partition all edges, while degree gives the matching lower bound, so $\chi \prime =n-1$.

An action by field automorphisms is a homomorphism $Go\mathrm{Aut}(L)$. Elements fixed by every group element are closed under addition, multiplication, additive inverses, and inversion of nonzero elements, so $L^G$ is a subfield.

The orbit polynomial ${\prod }_{\beta \in G\alpha }(X-\beta )$ has coefficients fixed by $G$, lies in $K[X]$, and has distinct roots. Thus $\alpha$ is separable and its degree is the orbit size $|G:G_{\alpha }|$, which divides $|G|$. If $L=K(\alpha )$ and the action is faithful, only the identity fixes $\alpha$, so the degree is $|G|$.

The relations ${\sigma }^n={\tau }^2=1$ and $\tau \sigma \tau ={\sigma }^{-1}$ give the dihedral group; its $2n$ substitutions $z\mapsto {\zeta }_n^{j}z$ and $z\mapsto {\zeta }_n^j/z$ are distinct. The element $w=z^n+z^{-n}$ is fixed. Since $z$ satisfies $X^{2n}-w{X}^n+1=0$, the extension has degree at most $2n$, while the automorphism group gives degree at least $2n$. Hence $L^G=\mathbb{C}(w)$.