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

Write $N={\prod }_i{p}_i^{e_i}$ with odd primes $p_i$. The Jacobi symbol iswhere each factor on the right is a Legendre symbol. The supplementary law isFor coprime positive odd $m,n$, quadratic reciprocity givesApplying this with $m=3$ givesFinally, factor $d=2^{e}m$ with $m$ odd. The supplementary laws for $-1$ and $2$, followed by reciprocity on every odd prime factor of $m$, express $(-d/a)$ solely in terms of the residue class of the positive odd integer $a$ modulo $d$ when $d\equiv 0$ or $3(\mathrm{mod}4)$. If $a\equiv b(\mathrm{mod}d)$, all those factors, including the zero cases, agree; hence

Fix $z_0\notin \Gamma$ and put $\delta =\mathrm{dist}(z_0,\Gamma )>0$. If $|z-z_0|<\delta /2$, thenuniformly for $w\in \Gamma$. Multiplication by the bounded continuous function $f$ and integration therefore prove continuity of $F$ at $z_0$.

Take $\Gamma$ to be the positively oriented unit circle and $f\equiv 1$. By the Cauchy integral formula, $F(z)=1$ inside the circle and $F(z)=0$ outside it, so no continuous extension across $\Gamma$ exists.

For the final assertion, cover $K$ by finitely many sufficiently small closed axis-parallel squares whose slightly enlarged squares lie in $\Omega$, choosing the grid so that no boundary meets $K$. Apply the square Cauchy formula to $f$ on every selected square and add the results. Integrals over shared edges cancel with opposite orientations. The remaining finitely many oriented boundary polygons can be split into contours ${\Gamma }_j\subset \Omega \setminus K$, and their sum isfor every $z\in K$.

The Reed-Muller code is spanned by the evaluation vectors of the square-free monomialsform a basis: every Boolean function has a unique algebraic normal form, so the monomials remain independent after evaluation on ${\mathbb{F}}_2^d$. ThusInduction using the decomposition $(u,u+v)$, with $u\in \mathrm{RM}(d-1,r)$ and $v\in \mathrm{RM}(d-1,r-1)$, gives the lower bound $2^{d-r}$ for every nonzero weight. The monomial $x_1\cdots x_r$ attains it, so the minimum distance is

The Mariner code is $\mathrm{RM}(5,1)$ with parameters $[32,6,16]$. Its information rate is $6/32=3/16$, and it correctserrors, a proportion $7/32$ of a codeword. The binary Hamming code of length $31$ has parameters $[31,26,3]$: its rate $26/31$ is much higher, but it corrects only one error, a proportion $1/31$.

A word of $\mathrm{RM}(d,1)$ is the evaluation of an affine Boolean functionIf $a=0$, the two constants have weights $0$ and $2^d$. If $a\ne 0$, choose $v$ with $a\cdot v=1$. Translation $x\mapsto x+v$ pairs every input where $f=0$ with one where $f=1$. Hence every one of the other codewords has weight $2^{d-1}$.

Let $\Sigma =\{a,b\}$, $V=\{S\}$, andThen $\mathcal{L}(G)=\{a^{n}b{a}^n:n\ge 0\}$. Adding $S\to \epsilon$ also produces $a^{2n}$; for example $aa$ is generated but lies in neither $\mathcal{L}(G)$ nor $\{\epsilon \}$. Thus the proposed equality can fail because the new erasing rule may be used on a noninitial occurrence of $S$.

After the first rule $S\to S^{\ast }$, every sentential form is obtained from a sentential form of $G$ by uniformly renaming $S$ as $S^{\ast }$. Each rule of $P$ has exactly the corresponding renamed rule in $P^{\ast }$, and conversely. Terminal words contain neither symbol, so this bijection of derivations proves

In $H^{+}$ the unstarred $S$ occurs only as the initial symbol and has precisely the alternativesThe first produces only $\epsilon$. After the second, the renamed-derivation argument from part (b) produces exactly $\mathcal{L}(G)$. Therefore

In a linear model containing an intercept, the normal equations make the residual vector $e$ orthogonal to every design column. In particular $e\perp 1$, soup to floating-point rounding.

The second design matrix has $49$ random Gaussian columns plus the intercept, hence is a random $50\times 50$ matrix. It has full rank with probability one because the determinant vanishes only on a measure-zero algebraic set. Its column space is then all of ${\mathbb{R}}^{50}$, so the fitted vector equals $Y$, the residual sum of squares is zero, and $R^2=1$.

The transition rates of this birth-death process are $q_{n,n+1}=\lambda n$ and $q_{n,n-1}=n(\gamma +\beta n)$. Thus, with $p_{-1}=0$,Multiplying by $n$, summing, and shifting indices givesAt a finite-moment steady state with positive mean and $\lambda >\gamma$,Since $\mathbb{E}(N^2)\ge (\mathbb{E}N{)}^2$, this impliesIf $\lambda \le \gamma$, both terms in the mean equation are nonpositive, and stationarity forces $\mathbb{E}N=0$. Thus the population is extinct almost surely in any such steady state.

For any $n$ with $\mathrm{Re}z>-n$, defineThe definitions agree on overlaps by the recurrence, giving a meromorphic continuation to $\mathbb{C}$. Its only singularities are simple poles at $0,-1,-2,\dots$. Since $F(1)=1$, repeated use of the recurrence givesThese residues are nonzero, so all the listed singularities really are simple poles.

The meromorphic continuations of $F$ and the gamma function have the same recurrence and the same value at $1$. Hence their residues at every nonpositive integer are the same. Their difference $f=F-\Gamma$ therefore has removable singularities there and is analytic elsewhere, so it extends to an entire function. Equivalently, $f(z+1)=zf(z)$ and $f(1)=0$ show inductively that the apparent quotient singularities are removable.

The product $S(z)=f(z)f(1-z)$ is entire. From $f(z+1)=zf(z)$ and $f(1-z)=-zf(-z)$,Its modulus is therefore periodic with period one. The assumed bound for $f$ on $0\le \mathrm{Re}z\le 1$, together with the reflected bound for $f(1-z)$, bounds $S$ on that strip and hence on all of $\mathbb{C}$. By Liouville's theorem $S$ is constant, while $S(z+1)=-S(z)$ forces that constant to be zero.

If $f$ were nonzero at one point, it would be nonzero on a neighborhood, so $f(1-z)=0$ on an open set; the identity theorem would then give $f\equiv 0$, a contradiction to that choice. Therefore $f\equiv 0$ and $F=\Gamma$.

In Hamiltonian mechanics, the canonical momenta areHence

Because $H$ is independent of $\varphi$, Hamilton's equation gives ${\dot{p}}_{\varphi }=0$. PutUsingone obtains $d{L}^2/dt=0$. Physically, $p_{\varphi }=L_z$ is the component of angular momentum along the polar axis, while $L^2$ is the squared magnitude of the angular momentum.

The orbital plane has normal parallel to the conserved angular momentum. If its inclination to the equatorial plane is $\psi$, then $L_z=L\cos \psi$. ThereforesoIt vanishes when $\sin \theta =|\cos \psi |$, equivalently at the greatest northern and southern latitudes reached by the inclined orbit. These are the turning points of the polar motion.

The Friedmann equation immediately givesUsing $P=w\rho$ in the acceleration equation and eliminating $\rho a^2$ with Friedmann givesDifferentiate $\Omega -1=k{c}^2{\mathcal{H}}^{-2}$ and substitute this equation:where ${\mathcal{H}}^2+k{c}^2=\Omega {\mathcal{H}}^2$ was used in the last step.

For an expanding universe with $0\le w\le 1$, the coefficient $(1+3w)\mathcal{H}$ is positive. Thus $\Omega =1$ is unstable toward the future: an initial $0<\Omega <1$ decreases away from one toward zero, whereas an initial $\Omega >1$ increases and eventually corresponds to recollapse. In radiation domination, $w=1/3$ andso a phase-line sketch has arrows away from the fixed point $1$ on both sides. Consequently the observed near-flatness today requires extremely fine tuning of the early value of $\Omega$.

During inflation $w\simeq -1$, so $1+3w\simeq -2$. For expansion,and the arrows point toward $\Omega =1$. Equivalently, accelerated expansion makes the curvature contribution $|k{c}^2|/{\mathcal{H}}^2$ rapidly decay. A sufficiently long inflationary epoch therefore drives a broad range of initial conditions extremely close to spatial flatness.

If the Schmidt rank is one, the decomposition is $|\psi ⟩=|\alpha ⟩|\beta ⟩$ after absorbing its sole coefficient, so the state is a product. Conversely, a product state has coefficient matrix $X=a{b}^T$, which has rank one. Therefore a bipartite pure state is entangled exactly when its Schmidt rank is at least two.

The state is alreadyIt therefore has Schmidt rank one across each of $A|BC$, $B|AC$, and $C|AB$.

Across $A|BC$ the state is the product $|0{⟩}_A\otimes |{\varphi }^{+}{⟩}_{BC}$, so its Schmidt rank is one. Across $B|AC$ it isand the two states on each side are orthonormal, so the Schmidt rank is two. The same argument with $B$ and $C$ exchanged handles $C|AB$. This is precisely the entanglement of the Bell state shared by $B$ and $C$.

Across $A|BC$, the GHZ state has the Schmidt decompositionof rank two. Symmetry gives the same rank-two decomposition across $B|AC$ and $C|AB$, so the state is entangled across every bipartition.

Projecting the GHZ state onto Charlie's outcome $0$ leaves the unnormalised state $|00{⟩}_{AB}/\sqrt{2}$. After normalization Alice and Bob have $|00⟩$, a product state.

Projecting the three-qubit $W$ state onto Charlie's outcome $0$ leavesAfter normalization this is $(|01⟩+|10⟩)/\sqrt{2}$, a Bell state and hence an entangled state of Alice and Bob.

The reduction map sends $H_k$ onto $H_{k-1}$ with kernel of order $p$, so $|H_k|=p^{k-1}$. More explicitly, the lifting-the-exponent calculationshows that $1+p$ has order $p^{k-1}$ modulo $p^k$. Hence $H_k=⟨1+p⟩$ is cyclic of that order.

For the matrix claim, suppose $A\ne I$ and choose $m$ maximal such that $A=I+p^{m}B$, so some entry of $B$ is nonzero modulo $p$. Replacing $A$ by a suitable power, we may assume its order is a prime $q$. If $q\ne p$, binomial expansion modulo $p^{m+1}$ givesIf $q=p$, expansion modulo $p^{m+2}$ givesbecause $p$ is odd. Both contradict $A^q=I$, so $A=I$.

For $p=2$, $r=1$ fails because $-I=I+2(-I)$ has order two. If $r=2$, the same argument works; in the order-two case, for maximal $m\ge 2$,since the parenthesis is nonzero modulo two. Thus the smallest value is $r=2$.

A language $L$ satisfies the regular pumping lemma if there is an integer $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with

Let a deterministic automaton for $L$ have $p$ states. During the first $p$ input symbols of an accepted word $w$ of length at least $p$, the run visits $p+1$ states, so two coincide. Write $w=xyz$ so that $y$ labels the nonempty loop between those visits and $|xy|\le p$. Traversing that loop any number of times leaves the remainder of the accepting run unchanged, giving $x{y}^{i}z\in L$ for every $i\ge 0$.

If an automaton with at most $100$ states accepted a word $w\in L$ of length $100$, the preceding loop argument would produce $x{y}^{i}z\in L$ for every $i\ge 0$, with $y\ne \epsilon$. These words have unbounded lengths and are distinct, contradicting the finiteness of $L$.

Take pumping length $p=1$. If a nonempty word $w\in \{0,1{\}}^{\ast }$, pump its first symbol; every pumped word remains in $\{0,1{\}}^{\ast }$. Otherwise write $w=u2v$ with $v\in L$. If $u\ne \epsilon$, pump the first symbol of $u$, leaving a word of the same form. If $u=\epsilon$, pump the initial $2$: deleting it leaves $v\in \{0,1{\}}^{\ast }$, while retaining one or more copies lets the last pumped $2$ serve as the separator. Thus every required pumped word belongs to $\hat{L}$.

Choose a language $L\subseteq \{0,1{\}}^{\ast }$ that is not recursively enumerable; such a language exists because there are uncountably many languages but only countably many algorithms. Form $\hat{L}$ as in part (d), which satisfies the pumping lemma.

If a grammar generated $\hat{L}$, enumerate its terminal derivations and retain precisely words of the form $2v$ with $v\in \{0,1{\}}^{\ast }$. Since such a word contains only one separator,This would enumerate $L$, a contradiction. Hence $\hat{L}$ is the required language.

Open ends impose $C(0,t)=C(L,t)=0$. By separation of variables,Expanding the initial constant gives $b_n=2C_0(1-(-1{)}^n)/(n\pi )$, hence

The diffusive flux is $j=-D{C}_x$. The total outward flux through both ends is thereforeIt diverges as $t\downarrow 0$: the initially uniform profile is incompatible with the suddenly imposed zero boundary values, creating an idealized infinite initial gradient.

At late times the first sine mode dominates, with growth exponentThusand the population grows precisely when $\mu >{\mu }_c$. Faster diffusion carries organisms to the lethal ends more quickly and raises the threshold; a longer channel lowers the principal diffusion eigenvalue and therefore lowers the threshold.

Immediately after $t=0$, thin boundary layers enforce zero concentration at both ends while the interior remains close to $C_0$. The profile is symmetric about $L/2$. Higher sine modes then decay rapidly and the shape approachesFor $\mu <{\mu }_c$ successive late-time curves have the same sine shape and decreasing height; for $\mu >{\mu }_c$ they have that shape and increasing height. Those features determine the two requested sketches.

The boundary conditions are now $C(0,t)=0$ and $C_x(L,t)=0$. Their wave numbers areThe principal growth rate is $\mu -D{\pi }^2/(4L^2)$, so long-term growth occurs whenClosing one end reduces the critical growth rate by a factor of four because there is only one absorbing escape boundary.

Each spatial mode acquires the factorThe oscillatory factor $e^{{\mu }_1\sin t}$ is bounded and does not affect the long-term exponential rate. With two open ends, growth therefore occurs exactly whenOnly the time average of this spatially uniform fluctuating growth rate controls the asymptotic threshold.

Since $P=P(\rho )$ and $\rho =\bar{\rho }(1+\delta )$,To first order, continuity and the divergence of Euler giveEliminating $\theta$ and using $\nabla \mapsto i\mathbf{k}/a$ yieldsThe second term is Hubble damping, gravity drives growth, and pressure produces oscillatory restoration. Their balance definesModes longer than the Jeans length are gravitationally unstable; shorter modes are pressure supported.

HereSince $\bar{\rho }\propto t^{-2}$ and $a\propto t^{2/3}$, $c_s^2/a^2=L_0^2/t^2$ for a constant $L_0^2$. With $\dot{a}/a=2/(3t)$ and $4\pi G\bar{\rho }/c^2=2/(3t^2)$, substitution of $\delta =t^n$ givessoFor $k\ll {\tilde{k}}_J=5/(6L_0)$, the modes approach $t^{2/3}$ and $t^{-1}$. For $k\gg {\tilde{k}}_J$, the exponents are complex with real part $-1/6$, giving logarithmic oscillations with decaying envelope $t^{-1/6}$. Taking $L_0\simeq 50\mathrm{Mpc}$ would pressure-suppress structure on enormous, cosmologically important scales and is incompatible with the observed growth of smaller-scale structure.