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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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}$.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

In Hamiltonian mechanics, the canonical momenta areHence

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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}$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.