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

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

The polynomial Runge theorem says that if $K\subset \mathbb{C}$ is compact, $\mathbb{C}\setminus K$ is connected, and $f$ is holomorphic on a neighbourhood of $K$, then for every $\epsilon >0$ there is a polynomial $p$ such that ${\sup }_{z\in K}|p(z)-f(z)|<\epsilon$.

For an explicit approximation on the left semicircle $K=\{z:|z|=1,\mathrm{Re}z\le 0\}$, defineThe two power-series expansionsproduce this formula. The first is a geometric series whose ratio has modulus at most $4/\sqrt{17}<1$ on $K$. The second converges uniformly on the whole unit circle; the elementary bound $\left(\genfrac{}{}{0ex}{}{j+k}{k}\right)\le 2^{j+k}$ shows that truncating it at $k=n^2$ gives a total error tending to zero even after summing over $0\le j\le n$. Consequently $p_n\to 1/z$ uniformly on $K$. This is an explicit polynomial approximation of the reciprocal on the left semicircle.

No such sequence exists on the punctured unit circle $S=\{z:|z|=1,z\ne 1\}$. If polynomials $p_n$ converged uniformly there, they would be Uniformly Cauchy. Continuity givesso they would converge uniformly on the entire unit circle. The uniform limit theorem would force the value at the missing point to be $1$, and hence the limit would be $1/z$ on the full circle. But the Cauchy integral theorem gives $\oint p_n(z)dz=0$ for every $n$, while uniform convergence and contour integration would implya contradiction. This is the polynomial approximation obstruction on a punctured circle.

Use Shamir's secret sharing over the finite field ${\mathbb{F}}_p$. The Chair independently chooses $a_1,\dots ,a_{r-1}$ from the uniform distribution on a finite set ${\mathbb{F}}_p$ and forms the random polynomialChoose distinct nonzero $x_1,\dots ,x_s\in {\mathbb{F}}_p$, with $s$ equal to the number of discs to be issued, and inscribe $(x_i,f(x_i))$ on disc $i$.

Any $r$ discs give $r$ distinct values of a polynomial of degree at most $r-1$. Their Vandermonde determinant is nonzero, so polynomial interpolation recovers $f$ uniquely and hence recovers the secret as $N=f(0)$.

Conversely, fix any $r-1$ observed discs and any candidate secret $n\in {\mathbb{F}}_p$. Interpolating through those $r-1$ points and $(0,n)$ gives exactly one polynomial of degree at most $r-1$. Thus every candidate $n$ is compatible with the observed discs in exactly the same number of ways. Because the coefficients were chosen uniformly, the conditional distribution of the secret is unchanged after seeing any $r-1$ discs. This proves the Perfect secrecy of Shamir's threshold scheme.

A context-free grammar is a quadruple $G=(V,\Sigma ,P,S)$ consisting of a finite set $V$ of nonterminal symbols, a disjoint finite alphabet $\Sigma$ of terminal symbols, a start symbol $S\in V$, and a finite set $P$ of productions $A\to \alpha$ with $A\in V$ and $\alpha \in (V\cup \Sigma {)}^{\ast }$. A sentence is a terminal word over an alphabet $w\in {\Sigma }^{\ast }$ with $S{\Rightarrow }^{\ast }w$, and the generated formal language is $\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

The first language is context-free. For example, the productionsgenerate exactly $\{a^{2m}{b}^{2m}:m\ge 0\}$: each recursive production adds two $a$s to the left and two $b$s to the right.

The language $L=\{a^{m^2}{b}^{m^2}:m\ge 0\}$ is not context-free. Suppose it had pumping length $p$ in the pumping lemma for context-free languages, and apply the lemma to $w=a^{p^2}{b}^{p^2}$. Write $w=uvxyz$ with $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z\in L$ for every $i\ge 0$.

Let $\alpha$ and $\beta$ be the respective numbers of $a$s and $b$s in $vy$. If $\alpha \ne \beta$, pumping with $i=0$ or $i=2$ destroys equality of the two block lengths. Hence a valid decomposition would require $\alpha =\beta =d>0$. Pumping with $i=2$ would then produce $a^{p^2+d}{b}^{p^2+d}$, where $1\le d\le p$. Butso $p^2+d$ is not a square number. This contradiction proves the square-count language is not context-free.

Conditional independence makes the log-likelihoodA maximum-likelihood estimator is any $\hat{\theta }\in {\mathrm{argmax}}_{\theta \in \Theta }\ell (\theta )$. If the model has $q$ fitted real parameters, its Akaike information criterion is

For the normal linear model, the Gaussian likelihood givesMaximization over $\beta$ gives the ordinary least squares estimator $\hat{\beta }$, and maximization over the variance givesAt this value the quadratic term in $-2\ell$ is $n$. There are $p$ regression coefficients and one variance parameter, so substitution into the Akaike information criterion yields

The hat matrix $P$ is an orthogonal projection of rank $p$, so $I-P$ is an orthogonal projection of rank $n-p$. Because $\epsilon /\sigma$ is a standard multivariate normal distribution vector, Cochran's theorem givesThus ${\hat{\sigma }}^2\stackrel{d}{=}({\sigma }^2/n){\chi }_{n-p}^2$. Substituting this into the preceding formula gives the Distribution of the Akaike information criterion in a normal linear model:

Adding the three equations of the SIR model with waning immunity givesHence conservation of population holds: $N=S+I+R$ is an integral of motion.

At an endemic equilibrium, $I^{\ast }>0$, so $0=\dot{I}=I^{\ast }(\beta S^{\ast }-\gamma )$ forcesThe equation $\dot{R}=0$ gives $R^{\ast }=\gamma I^{\ast }/\alpha$. The conservation law $S^{\ast }+I^{\ast }+R^{\ast }=N$ therefore yieldsA positive endemic state exists exactly when $\beta N>\gamma$, equivalently when the basic reproduction number ${\mathcal{R}}_0=\beta N/\gamma$ exceeds one.

Eliminate $R=N-S-I$ to obtain the two-dimensional autonomous differential equationIts Jacobian matrix at the endemic equilibrium isSince $I^{\ast }>0$,The trace-determinant stability criterion shows that both eigenvalues have negative real part. The Endemic equilibrium of the SIR model with waning immunity is therefore locally asymptotically stable.

For each nonzero period lattice point $\omega$, the binomial series givesPairing $\omega$ with $-\omega$ cancels every odd power. Hence the Laurent series of the Weierstrass elliptic function iswhich is the stated coefficient formula.

SetThis is an elliptic function. Write $a=g_2/20$ and $b=g_3/28$ in the expansion from part (i). At a lattice point, the coefficient of $z^{-2}$ in $F$ is $g_2-20a=0$, and its constant coefficient is $g_3-28b=0$; there are no other singular terms. Every apparent pole is therefore a removable singularity, and $F$ extends to an entire elliptic function with value zero at the lattice points.

An entire elliptic function is bounded on a fundamental parallelogram and hence everywhere. By Liouville theorem it is constant, and its value at zero is zero. Thus $F\equiv 0$, proving the Weierstrass elliptic differential equation

The repulsive force is $\mathbf{F}=k\mathbf{r}/r^3=-\nabla (k/r)$, so the Hamiltonian isThe Hamilton's equations give $\dot{\mathbf{r}}=\mathbf{p}/m$ and $\dot{\mathbf{p}}=k\mathbf{r}/r^3$. Consequentlyso the angular momentum is conserved. Moreover,It follows that the Laplace-Runge-Lenz vector $\mathbf{A}=\mathbf{p}\times \mathbf{L}+mk\hat{\mathbf{r}}$ is conserved. By the Hamiltonian conservation law, these time derivatives are exactly $\{\mathbf{L},H\}$ and $\{\mathbf{A},H\}$, so both Poisson brackets vanish.

The integrals of motion are the energy $H$, the components of $\mathbf{L}$, and the components of $\mathbf{A}$, subject toTaking the dot product of $\mathbf{A}$ with $\hat{\mathbf{r}}$ givesTherefore the polar equation of a repulsive inverse-square orbit iswhere $\lambda =L^2/(mk)\ge 0$ and $e=A/(mk)\ge 0$. For a nonradial physical scattering orbit $H>0$, the identity above gives $e>1$, as expected for a hyperbolic Kepler orbit.

For equal internal degeneracy, the number density of an isotropic ultrarelativistic species is proportional toWith $x=\beta pc$, compare the Fermi-Dirac distribution and Bose-Einstein distribution usingFor $s>0$, a change of variables in the second term gives the fermion-to-boson thermal integral ratioParticle number has $s=2$, so $n_f=(1-2^{-2})n_b=3n_b/4$. The energy density contains one further factor $E=pc$, so it has $s=3$ and

The selective phase rotation $R_g^{\varphi }$ multiplies the component parallel to $|g⟩$ by $e^{i\varphi }$ and fixes its orthogonal complement. Therefore

Conjugating the reflection operator by a unitary operator reflects about the conjugated state:Thus one may take $|\psi ⟩=|{\psi }_{\mathrm{in}}⟩=U|00⟩$.

For $p=1/4$, put $|{\psi }_{\mathrm{in}}⟩=\frac{1}{2}|g⟩+\frac{\sqrt{3}}{2}|b⟩$. After the first phase rotation the state isSince $U{R}_{00}^{\pi }{U}^{†}=I-2|{\psi }_{\mathrm{in}}⟩⟨{\psi }_{\mathrm{in}}|$, the requested state isIt is proportional to $|g⟩$ exactly when $e^{i\varphi }=-1$, hence when $\varphi =\pi$. The state is then $-|g⟩$, whose global phase has no physical effect.

Choose $U$ to prepare the uniform superposition, so the marked-state probability is $p=1/4$. Apply the marked-state phase oracle $R_g^{\pi }$, followed by the reflection $U{R}_{00}^{\pi }{U}^{†}$ about the prepared state. Part (iii) shows that this single Grover iteration produces $-|g⟩$. A projective measurement in the four-item basis therefore returns the marked element with probability one. This is exact Grover search on four entries.

For an odd prime number $p$, the Legendre symbol isIf $p\nmid x$, multiplicativity of the Legendre symbol givesBoth factors belong to $\{1,-1\}$, so they are equal. Thus $(x^{-1}/p)=(x/p)$.

Gauss lemma states that if $p\nmid a$ and $m$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^m$.

To prove it, replace each residue exceeding $p/2$ by its negative, obtaining numbers $r_1,\dots ,r_{(p-1)/2}$ in $\{1,\dots ,(p-1)/2\}$. No two of them are equal modulo $p$: such an equality would give $ia\equiv \pm ja(\mathrm{mod}p)$, hence $i=j$ in the allowed range. They therefore permute $1,\dots ,(p-1)/2$, and multiplication givesCancel the nonzero factorial and apply Euler's criterion to obtain the lemma.

For $a=-1$, all $(p-1)/2$ least positive residues $p-1,p-2,\dots ,(p+1)/2$ exceed $p/2$. Hence the first supplementary law for quadratic reciprocity is

Write $\chi (x)=(x/p)$. Choose a quadratic nonresidue $a$. Multiplication by $a$ permutes ${\mathbb{F}}_p$, while multiplicativity of the Legendre symbol gives $\chi (ax)=-\chi (x)$. Thereforeso the complete Legendre-symbol sum is zero.

Since $4x(x+1)=(2x+1{)}^2-1$ and $\chi (4)=1$, the bijection $x\mapsto 2x+1$ reduces the next sum to ${\sum }_y\chi (y^2-1)$. Count pairs $(y,t)\in {\mathbb{F}}_p^2$ satisfying $t^2=y^2-1$. On one hand their number isOn the other hand $(y-t)(y+t)=1$, and every $u\in {\mathbb{F}}_p^{\times }$ gives exactly one pair by $y-t=u$, $y+t=u^{-1}$. There are therefore $p-1$ pairs, proving the quadratic Legendre-symbol correlation

For $1\le z\le p-2$, the indicator that both $z$ and $z+1$ are quadratic residues is $(1+\chi (z))(1+\chi (z+1))/4$. Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime

A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ with finite state set $Q$, finite input alphabet $\Sigma$, transition function $\delta :Q\times \Sigma \to Q$, initial state $q_0$, and accepting-state set $F\subseteq Q$. It accepts a word when the extended transition function of a deterministic finite automaton carries $q_0$ to a state in $F$. A regular language is a language accepted by some deterministic finite automaton.

The pumping lemma for regular languages says that if a regular language is accepted by an automaton with $N$ states, every accepted word $w$ of length at least $N$ has a decomposition $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{i}z$ in the language for every $i\ge 0$. Indeed, among the $N+1$ states visited before and after the first $N$ symbols, two are equal by the pigeonhole principle. The intervening nonempty word $y$ labels a loop, which may be traversed any number of times without changing the final accepting state.

In base two, the powers of two have representations $10^n$, so their language is the regular expression $10^{\ast }$ and is regular.

Suppose instead that their base-ten representations formed a regular language. Apply the pumping lemma to a sufficiently long decimal power of two $xyz$, and put $d=|y|>0$. Pumping gives decimal integers $a_i$ represented by $x{y}^{i}z$, all powers of two. A direct place-value calculation shows thatfor a constant $C$ independent of $i$. The lengths, and hence the exponents in $a_i=2^{n_i}$, tend to infinity. Dividing by $a_i$ givesFor large $i$, the right side has absolute value less than one while the left side is an integer, so it must vanish. This would make a power of two equal to $10^d=2^d{5}^d$, impossible for $d>0$ by unique prime factorization. Thus the decimal powers of two are not a regular language.

Removing the death term with $u(x,t)=e^{\mu t}n(x,t)$ gives the heat equation $u_t=D{u}_{xx}$ with initial data $N\delta (x)$. The heat kernel therefore yieldsFor each fixed $x$, the exponential mortality factor and diffusive prefactor show that $n(x,t)\to 0$ as $t\to \infty$. Its spatial integral is $N{e}^{-\mu t}$, the expected number of surviving larvae.

Because $e(x,0)=0$, the egg density is the accumulated depositionIt is convenient to use the Fourier transform. The larval equation givesApplying the stated inverse-transform integral with $\alpha =\sqrt{\mu /D}$ gives the remnant density from diffusion with mortality and deposition

Each larva undergoes diffusion over its exponentially distributed lifetime of mean $1/\mu$ and deposits eggs at rate $\lambda$ wherever it is found. The characteristic diffusion length before death is $\sqrt{D/\mu }$, which explains the exponential spatial decay. Integrating the remnant over space givesThis is also immediate physically: each of the $N$ larvae lives for mean time $1/\mu$ and therefore lays an expected $\lambda /\mu$ eggs. The eggs remain as a stationary record because they neither die nor diffuse.

Expand the density contrast in Fourier modes, $\delta (\mathbf{x},t)=\int {\delta }_{\mathbf{k}}(t)e^{i\mathbf{k}\cdot \mathbf{x}}{d}^{3}k$. In the static universe each mode satisfiesFor $k>k_J$ there are sound wavesFor $k<k_J$, Jeans instability gives growing and decaying exponentials with rate $c_s\sqrt{k_J^2-k^2}$. At the Jeans wavenumber the two solutions are constant and linear in time.