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

The Lagrange theorem for polynomial congruences says that if $p$ is prime and $f\in \mathbb{Z}[X]$ has degree $d$ with at least one coefficient not divisible by $p$, thenhas at most $d$ incongruent solutions modulo $p$.

The Chinese remainder theorem states that for pairwise coprime $m_1,\dots ,m_r$, every systemhas exactly one solution modulo $M={\prod }_i{m}_i$. For two moduli, choose $u,v$ with $um+vn=1$ by Bezout identity. Thenis congruent to $a$ modulo $m$ and to $b$ modulo $n$. If $x,y$ are two solutions, both $m$ and $n$ divide $x-y$; coprimality makes $mn$ divide $x-y$. This proves existence and uniqueness for two factors, and induction proves the general statement.

Nowand $12^3+1=1729$, so $x=12$ is a solution. For $1\le x<12$, one has $0<x^3+1<1729$, so no such positive integer can satisfy the congruence. Hence the smallest isModulo $7,13,19$, the roots are respectivelyEach list has three elements, and the Chinese remainder theorem combines the choices independently. Therefore the number of solutions with $1\le x\le 1729$ is

Because $\overline{\Omega }$ is compact, $\varphi$ attains a maximum. If a maximizer lay in $\Omega$, its Hessian matrix would be negative semidefinite, so its trace would satisfy $\Delta \varphi \le 0$, contradicting $\Delta \varphi >0$. Hence every strictly subharmonic function under the stated hypotheses attains a maximum on $\partial \Omega$.

Statement (i) is true. For $ϵ>0$, the functionhas $\Delta {\varphi }_{ϵ}=4ϵ>0$, soLetting $ϵ\downarrow 0$ givesThis is the maximum principle for harmonic functions.

Statement (ii) is true. Since $\Delta (-\varphi )=0$, applying the maximum principle to $-\varphi$ gives

Statement (iii) is false. On the unit disc, takeThe function $f$ is continuous on the closed disc, but $\varphi$ has its strict maximum $1$ at the interior point $(0,0)$ and equals zero on the boundary.

For binary length-$n$ linear codes $C_2\subseteq C_1$, their bar product of binary linear codes isIt is a binary linear code of length $2n$ and dimension $\dim C_1+\dim C_2$.

The code $\mathrm{RM}(d,0)$ is the binary repetition code of length $2^d$, whileis the full binary code. For $0<r<d$, the Reed-Muller bar-product recursion isThus its rank $k(d,r)$ satisfies Pascal's recursionwith the stated boundary values. Therefore

A square-free monomial in $d$ variables of degree $j\le d-1$ evaluates to one at exactly $2^{d-j}$ points of ${\mathbb{F}}_2^d$, an even number. Since parity of Hamming weight is a linear functional over ${\mathbb{F}}_2$, every sum of such evaluation words also has even weight. Hence every word in $\mathrm{RM}(d,d-1)$ has even weight.

If $f$ and $g$ have degrees at most $r$ and $d-r-1$, then $fg$ has degree at most $d-1$. The binary inner product of their evaluation words is the parity of the weight of the evaluation of $fg$, and is therefore zero. ThusFinally, binomial symmetry givesso the inclusion has equal dimensions andThis is the Dual of a Reed-Muller code.

A context-free grammar is a quadruple $(V,\Sigma ,P,S)$ consisting of finite nonterminal and terminal alphabets, a set of productions $A\to \alpha$ with one nonterminal $A$ on the left, and a start symbol $S$. A context-free language is a language generated by such a grammar.

The pumping lemma for context-free languages says that there is a pumping length $p$ such that every $w$ in the language with $|w|\ge p$ can be writtenwith $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z$ in the language for every integer $i\ge 0$.

The language in (i) is not context-free. If it were, pumpThe substring $vxy$, having length at most $p$, cannot meet both the $a$- and $c$-blocks. If pumping changes the number of $a$'s or $c$'s, those two counts cease to agree. If it changes neither, it changes the number of $b$'s while the outer counts remain $p$, so the middle count ceases to be $2p$. Every permitted decomposition therefore fails, contradicting the pumping lemma.

The language in (ii) is context-free. The grammargenerates exactlyThe recursive uses of the first rule match the numbers of $a$'s and $c$'s, while $B$ independently generates any even number of $b$'s.

The log density isIts kink occurs at the unknown location $\mu$, so its parameter dependence cannot be separated into a fixed finite-dimensional statistic of $y$ and the smooth canonical form required of an exponential dispersion family. Thus the two-parameter location-scale Laplace distribution is not such a family.

For independent observations, the log-likelihood isFor every fixed $\sigma >0$, maximizing this expression in $\beta$ is equivalent to minimizing $S(\beta )$. Hencethe least absolute deviations estimator. At this value,so, in the nondegenerate case $S(\hat{\beta })>0$,

Probability enters state $n$ through a birth from $n-1$ or a pair-death event from $n+2$, and leaves through either event at state $n$. Thus the Kramers-Moyal master equation iswith probabilities and impossible transition rates taken as zero outside the nonnegative states.

A birth changes $n$ by $+1$, while a death event changes it by $-2$. Applying these increments to the first moment givesConsequently every steady state must satisfy

Taylor-expand the gain terms:and, writing $Q(n)=\beta n^{2}P(n)$,After cancellation of the loss terms, the second-order Kramers-Moyal expansion isHence the constant-birth pair-annihilation process has

The deterministic drift vanishes at the positive stable pointWhen $n_{\ast }$ is large, fluctuations sample only a narrow range around it, so the linear noise approximation replacesThe resulting Ornstein-Uhlenbeck stationary density is the stated normal distribution withand

For the Gaussian approximation,The extra term reflects the subleading error made by centring the linear approximation at the deterministic fixed point. It is smaller than ${\mu }^2$ by relative order $1/\mu$, so the exact steady-state condition from part (a) is recovered at leading order. A higher-order expansion shifts the mean and restores the moment balance more accurately.

The approximation is reliable whenThus one needs $\lambda /\beta \gg 1$: births must support a large typical population, with jumps of one or two individuals small compared with the population scale.

Taking the Laplace transform in $t$ and using the zero initial condition givesThe solution bounded as $x\to \infty$ isThe transformed boundary condition isso this is the sinusoidally forced heat equation on a half-line. Integrating in $x$ gives

Use the principal square root, with a branch cut along the negative real axis. The Bromwich contour is a vertical line to the right of $p=\pm i\omega$ and the branch point $p=0$. For $t>0$, close it in the left half-plane, indent around the cut, and let the large semicircle recede. The simple poles at $p=\pm i\omega$ contributeHence

On the upper and lower sides of the cut, put $p=-s$; the two values of $\sqrt{p}$ are $i\sqrt{s}$ and $-i\sqrt{s}$. Their jump and the opposite contour orientations combine to giveThis is precisely Bromwich inversion with a square-root branch cut: the residues produce the permanent periodic response, while the cut integral is the transient that decays with time.

The generalized momenta conjugate to the two ignorable coordinates areandSince the Lagrangian contains neither $\varphi$ nor $\psi$, both momenta are constant in time.

Eliminating the two angular velocities givesConservation of energy then yields the heavy symmetric top reductionwhere

As $\theta \to 0$, the first term diverges unlessWriting their common value as $p$, the small-angle expansion isBy the effective potential stability criterion, the vertical state is stable exactly whenAt the vertical state $p=I_3(\dot{\psi }+\dot{\varphi })$, so this is the gyroscopic stabilization of an inverted symmetric top by sufficiently rapid spin.

Differentiate the Friedmann equationand use the cosmological perfect-fluid continuity equationAfter dividing by $2H$,Since $\ddot{a}/a=\dot{H}+H^2$, eliminating the curvature term gives the Friedmann acceleration equation

Under the strong energy condition in a Friedmann universe, $\rho +3P\ge 0$, so $\ddot{a}/a\le 0$. Thereforeand wherever $H\ne 0$,

If $H(t_0)>0$, integrating the inequality backward shows that $H^{-1}$ reaches zero no later than $t_0-H(t_0{)}^{-1}$. Thus $H\to +\infty$ and $a\to 0$ at a finite time in the past. If $H(t_0)<0$, the same argument forward in time makes $H\to -\infty$ and $a\to 0$ at a finite future time. The sign of $H$ distinguishes an expanding universe with a past Big Bang from a contracting universe ending in a Big Crunch. Hence a Friedmann universe obeying the strong energy condition cannot remain nonsingular for unlimited proper time in both directions.

Use the available unitaries to preparein the first register andin the answer qubit. The quantum phase kickback identity givesChoose a unitary $F$ with $F|0⟩=|s⟩$, apply $F^{-1}$ to the first register, and measure it. Its amplitude at $|0⟩$ isThis equals $+1$ or $-1$ for a constant string and zero for a balanced string. Thus outcome $0$ means constant, while every other outcome means balanced, with certainty after one oracle query. This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary.

With the restricted operations, begin in $|0⟩|0⟩$ and apply $F$ to the first register:Now applyFor every basis state this compute-phase-uncompute construction acts asThe first register is therefore the same phase state used in part (a). Apply $F^{-1}$ and measure. Again, outcome $0$ occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to $O_x$ and only the permitted operations.

An integer $b$ is a primitive root modulo $n$ when it is coprime to $n$ and its residue class generates the multiplicative group of integers modulo n. Equivalently,

We prove that (i) implies (ii). Since $b$ is primitive modulo $p$, writeBeing primitive modulo $p^2$ is equivalent to $p\nmid c$. The binomial theorem then gives inductivelyIt follows that the order modulo $p^m$ is exactlyso $b$ is primitive modulo every $p^m$. This is lifting a primitive root to odd prime powers. The implication (ii)$\Rightarrow$(i) is immediate by taking $m=2$.

This implication is already contained in part (i): being primitive modulo every $p^m$ plainly includes being primitive modulo $p^2$, while primitivity modulo $p^2$ lifts to every higher power by the valuation calculation there.

Suppose first that $b$ is not primitive modulo $p^2$. Since it is primitive modulo $p$, its order modulo $p^2$ is then $p-1$, soBecause $p-1$ divides $p^2-1$, the composite number $p^2$ satisfiesit is a Fermat pseudoprime to base $b$ and is divisible by $p^2$. Thus (iii) fails.

Conversely, suppose $b$ is primitive modulo $p^2$ and a base-$b$ pseudoprime $N$ is divisible by $p^a$ with $a\ge 2$. By part (i),The pseudoprime congruence forces this order to divide $N-1$, so in particular $p\mid N-1$. But $p\mid N$, a contradiction. Hence no such pseudoprime exists. This proves (i)$\iff$(iii), and all three statements are equivalent.

By lifting a primitive root to odd prime powers, it is enough to test primitivity modulo $25$. The positive integers below eight either fail to be units or have orderswhereasTherefore the three smallest required integers are

By the primitive-root modulus classification, $P(n)>0$ only forwith $p$ an odd prime, and thenFix $k\ge 1$. The finite fibres of the Euler totient function imply that there are only finitely many possible values $m=\phi (n)$ satisfying $\phi (m)=k$. For each such $m$, the same result gives only finitely many $n$ satisfying $\phi (n)=m$. The union of these finitely many finite sets is finite, proving the claim.

A state $q$ is accessible whenfor some word $w\in {\Sigma }^{\ast }$. States $p$ and $q$ are equivalent, or indistinguishable, whenfor every continuation $w$.

This equivalence is preserved by transitions: if $p\sim q$, then $\delta (p,a)\sim \delta (q,a)$. Hence define $D/\sim$ with states $[q]$, initial state $[q_0]$, transitionand accepting classes $[q]$ with $q\in F$. Induction on word length givesso $D$ and its quotient deterministic finite automaton by indistinguishable states accept the same language. If two quotient states were equivalent, their representatives would be equivalent in $D$, so the classes would be equal. Thus no two distinct quotient states are equivalent.

For the unary alphabet, accessibility means that all states occur on the orbitFiniteness makes this orbit a directed tail entering a directed cycle. The quotient retains exactly one accepting state and merges precisely those positions having the same future acceptance pattern.

More explicitly, if the unique accepting state lies before the cycle, every state after it can never reach acceptance and these states collapse to one rejecting sink. The minimal diagram is then a directed chain from the initial state through the unique accepting state and onward to that sink, which has a self-loop.

If the accepting state lies on the cycle, all cycle states are distinct because their next visits to the accepting state occur in different residue classes modulo the cycle length. Any remaining tail is a chain feeding the cycle. In a minimal diagram with a nonempty tail, the accepting state is the cycle vertex immediately preceding the entry vertex; otherwise the final tail state has the same future acceptance sequence as a cycle state and would be merged. A pure cycle with one accepting vertex is also possible. These are exactly the minimal accessible unary DFAs with one accepting state.

Fick's first law gives the diffusive fluxLocal conservation says $C_t+\nabla \cdot \mathbf{J}=0$, and therefore

For $D(C)=kC$, conservation of the deposited amount requiresThe dimensions satisfy $[M]=[C]L^2$ and $[k]=L^2/([C]T)$. Thus $Mkt$ has dimension $L^4$, so the similarity length is $(Mkt{)}^{1/4}$. Requiring the concentration scale to have dimension $[C]$ givesHence

In polar coordinates, substitution into
$C_t=k{r}^{-1}(rC{C}_r{)}_r$ givesMultiplying by $\xi$ and integrating once, with regularity and zero radial flux at the origin, yieldsWhere $F>0$, this reduces to $F^{\prime }=-\xi /4$, soNonnegativity and zero flux at the moving front give the compactly supported profileThe normalization givesand hence $A=1/\sqrt{2}$ and ${\xi }_0^4=32$. This is the Two-dimensional Barenblatt solution with diffusivity proportional to concentration, and its support radius isso $N=32$.