Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1

The Chinese remainder theorem says that if the positive integers $m_1,\dots ,m_r$ are pairwise coprime and $M={\prod }_i{m}_i$, then for arbitrary residue classes $a_i(\mathrm{mod}{m}_i)$ there is a unique residue class $x(\mathrm{mod}M)$ satisfyingEquivalently, reduction is a ring isomorphism

For existence, put $M_i=M/m_i$. Pairwise coprimality gives $\gcd (M_i,m_i)=1$, so Bézout's identity supplies an integer $u_i$ with $u_i{M}_i\equiv 1(\mathrm{mod}{m}_i)$. Thenhas the required residues, because every term except the $i$th is divisible by $m_i$. If $x$ and $y$ are two solutions, each $m_i$ divides $x-y$. Pairwise coprimality then implies that their product $M$ divides $x-y$, proving uniqueness modulo $M$.

An odd composite number $N$ with $\gcd (b,N)=1$ is a Fermat pseudoprime to base $b$ whenFor $N=35$, the Chinese remainder theorem for unit groups reduces this condition to congruences modulo $5$ and $7$. Modulo $5$, Fermat's little theorem givesso $b^{34}\equiv 1(\mathrm{mod}5)$ exactly when $b\equiv \pm 1(\mathrm{mod}5)$. Modulo $7$, the unit group has order $6$, soThe equation $b^4=1$ in the cyclic group $(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ has $\gcd (4,6)=2$ solutions, namely $b\equiv \pm 1(\mathrm{mod}7)$.

Combining the two independent sign choices by the Chinese remainder theorem givesand hence

The Chebyshev polynomial identity $T_m(\cos \theta )=\cos (m\theta )$ implies $|T_m(x)|\le 1$ on $[-1,1]$. Since ${\sum }_i{\gamma }_i<\infty$, the Weierstrass M-test shows thatconverges uniformly on $[-1,1]$. Every partial sum is continuous, so the uniform limit theorem makes $f$ a well-defined continuous function.

LetThen $-1=x_0<x_1<\cdots <x_{3^{n+1}}=1$. Since every $3^i$ is odd and, for $i\ge n+1$, $3^{i-n-1}$ is an odd integer,It follows thatThus the error has equal alternating extrema at $3^{n+1}+1$ ordered points. The Chebyshev alternation theorem shows that $P_n$ is a best uniform approximation among polynomials of degree at most $3^{n+1}-1$, and in particular

Now let $({\delta }_N)$ be the prescribed decreasing positive sequence. DefineThen $s_j$ decreases strictly to zero, so every ${\gamma }_j>0$, the series ${\sum }_j{\gamma }_j=s_0$ converges, andGiven $N\ge 1$, choose $j\ge 0$ with $3^j\le N\le 3^{j+1}-1$. Monotonicity of best-approximation errors and of ${\delta }_N$ givesHence this continuous $f$ satisfiesfor every polynomial $P$ of degree at most $N$. This is the polynomial form of Bernstein's lethargy theorem.

For finite-valued discrete random variables, the conditional entropy isThe chain rule for information entropy in two orders givesThereforeusing nonnegativity of conditional entropy and the fact that conditioning reduces entropy. This proves the required inequality.

For Fano's inequality, let $X$ take values in an alphabet of size $m$, let $\hat{X}=g(Y)$ be any estimator, and putBecause $E$ is determined by $(X,Y)$,Now $H(E\mid Y)\le H(E)=h_2(p_e)$. If $E=0$, $X$ is determined by $Y$; if $E=1$, at most $m-1$ values remain possible. HenceCombining the bounds yields

The pumping lemma for context-free languages states that for every context-free language $L$ there is a pumping length $p$ such that every $w\in L$ with $|w|\ge p$ can be writtenwith

This language is context-free. It is the language of even-length palindromes over $\{a,b\}$, generated by the context-free grammarEvery derivation adds matching outer symbols, and removing the matching first and last symbols gives the converse induction.

This language is not context-free. Suppose it had pumping length $N$, and choose a prime $p>N$. Apply the pumping lemma to $w=0^p{1}^p$. Let $\alpha$ and $\beta$ be the total numbers of zeros and ones in the pumped pieces $v$ and $y$. If $\alpha \ne \beta$, pumping with $i=0$ produces unequal block lengths and leaves the language. If $\alpha =\beta$, then $|vy|>0$ forces $\alpha =\beta =d>0$. Pumping with $i=p+1$ produces equal block lengthswhich are composite. Every possible pumping decomposition fails, proving the equal prime block language is not context-free.

The equations $3m=4l$ and $2n=5k$ are equivalent tofor nonnegative integers $r,s$. Hence the language iswhich is the nested two-pair count language generated byIt is therefore context-free.

Take context-free grammars $G_L,G_M$ for $L,M$ and rename their nonterminals so that they are disjoint. If their start symbols are $S_L,S_M$, add a new start symbol $S$ and the productionAll productions remain context-free. A derivation from $S$ produces a word from $L$ followed by a word from $M$, and every such concatenation has a derivation. Thus the new grammar generates $LM$, proving closure of context-free languages under concatenation.

An exponential dispersion family has densities of the formwhere $\theta$ is the canonical parameter, $\varphi >0$ is the dispersion parameter, and the support does not depend on $\theta$. Its mean and variance are

For the given Gamma distribution, setThengivesThus the gamma laws form the Gamma exponential dispersion family.

Directly integrating, or using the cumulant-generating function of a gamma distribution,soDifferentiation at zero yields

In this discrete age-structured population model, individuals of age $a\ge 1$ present during the breeding season each produce $b_a$ newborns, so the number entering age zero isAn age-$a$ individual survives the following winter with probability $1-{\mu }_a$ and is then age $a+1$ in the next year, givingTogether with the initial age distribution, these equations determine every later cohort.

Substitute $n_{a,t}=r_a{\gamma }^t$ into the survival equation. Thenand iteration givesThe birth equation becomesA nonzero population mode therefore requires the Discrete Euler-Lotka equation

For nonnegative vital rates with at least one surviving reproductive age and enough decay to make the series finite, $\varphi$ is continuous and strictly decreasing on $\gamma >0$, tends to infinity as $\gamma \downarrow 0$, and tends to zero as $\gamma \to \infty$. The intermediate value theorem gives one positive solution, and strict monotonicity makes it unique.

The value $\varphi (1)$ is the expected lifetime offspring count under these fixed rates. Since $\varphi$ decreases, $\varphi (1)>1$ places the root at $\gamma >1$ and the population grows geometrically; $\varphi (1)<1$ places it at $\gamma <1$ and the population shrinks. Equality gives replacement, $\gamma =1$.

With $u=x^4$, the change of variables formula givesThe beta--gamma identity, $\Gamma (1/2)=\sqrt{\pi }$, and the Gamma reflection formula giveTherefore

Use the suggested substitutionIt maps $[0,1]$ to itself and satisfiesHencewhere $K$ is the complete elliptic integral of the first kind. Part (a) and the Gamma function recurrence $\Gamma (5/4)=\Gamma (1/4)/4$ now give

Letbe the infinitesimal generator of the continuous symmetry, and letbe the canonical momentum. Noether theorem states that along every trajectory satisfying the Euler-Lagrange equations,is conserved.

Indeed, differentiate the invariance of $L$ with respect to $s$ at zero:On an Euler-Lagrange trajectory, $\partial L/\partial q_i=d{p}_i/dt$, soThis proves the Noether conserved quantity for a mechanical point symmetry.

In cylindrical coordinates,The screw transformationleaves $r$ and $\varphi -kz$ fixed, so it is the helical symmetry of a potential. Its infinitesimal generator has ${\xi }_z=1$ and ${\xi }_{\varphi }=k$. Noether's theorem therefore gives the conserved quantityThis is a linear combination of axial linear momentum and axial angular momentum.

For an infinitesimal test mass $\delta m$ on the surface of a homogeneous sphere, its Newtonian mechanical energy isThe spatially flat case corresponds to zero specific energy. Usingand dividing by $\delta m{R}^2/2$ givesSince $R$ is proportional to the scale factor $a$, this is the Newtonian derivation of the flat Friedmann equation

Now take $a(t_0)=1$ and $\rho ={\rho }_0{a}^{-4}$. PutThe contracting branch of the Friedmann equation isIntegrating $ada=-Cdt$ from $t_0$ givesThereforeon the contracting interval, reaching $a=0$ at $t=t_0+1/(2C)$.

Write $|\alpha ⟩=a|0⟩+b|1⟩$. Expanding in the orthonormal Bell basis of systems $CA$ gives the Bell-basis teleportation identityThus, uniformly for $x,z\in \{0,1\}$,The states are unique because the four Bell states are an orthonormal basis of the two-qubit space. In particular,

Alice performs a projective Bell-basis measurement on her qubits $C$ and $A$. Outcome $(x,z)$ occurs with probability $1/4$ and leaves Bob's qubit inAlice sends the two classical bits $(x,z)$ to Bob. He applies the inverse Pauli operationrecovering $|\alpha ⟩$ exactly, up to an irrelevant global phase. This is quantum teleportation: only local operations and classical communication are used, while the shared Bell pair supplies the entanglement resource.

No. Before any operation, Bob's reduced density matrix is $I/2$, independent of $|\alpha ⟩$. Any trace-preserving operation performed only by Alice leaves Bob's reduced state unchanged when her uncommunicated outcomes are averaged. This is the no-communication theorem, or quantum no-signalling.

If Bob received the unknown state, his reduced state would instead be the pure state $|\alpha ⟩⟨\alpha |$, which depends on Alice's input. That would let Alice signal by choosing different inputs, contradicting no-signalling. The two classical outcome bits are therefore essential.

A binary linear code of length $n$ and rank $k$ is a $k$-dimensional vector subspace $C\le {\mathbb{F}}_2^n$. Its minimum distance $d$ is the least Hamming weight of a nonzero codeword, equivalently the least Hamming distance between distinct codewords.

Delete any $d-1$ coordinates. The resulting puncturing mapis injective: if $\pi (x)=\pi (y)$ for distinct codewords, then the nonzero codeword $x-y$ is supported on at most $d-1$ coordinates, contradicting the minimum distance. Thuswhich is the Singleton bound

Let $S$ be the support of the weight-$d$ codeword $x$, and let ${\pi }_S$ delete all coordinates in $S$. Its kernel consists of codewords supported in $S$. If $0\ne y\in \ker {\pi }_S$, then $\mathrm{wt}(y)\ge d$ but $|S|=d$, so $y$ is nonzero in every coordinate of $S$. Over ${\mathbb{F}}_2$ this forces $y=x$. Hencehas dimension one, and the punctured code $C^{\prime }={\pi }_S(C)$ has length $n-d$ and rank $k-1$ by the rank-nullity theorem.

To bound its minimum distance, take $y\in C$ whose puncture $y^{\prime }$ is nonzero. If $y$ has $r$ nonzero coordinates in $S$, then $y+x$ has $d-r$ there, while both words have the same $\mathrm{wt}(y^{\prime })$ nonzero coordinates outside $S$. Both $y$ and $y+x$ are nonzero codewords, soAdding gives $2\mathrm{wt}(y^{\prime })\ge d$, and therefore

Apply part (b) repeatedly. After the first puncturing, the code has rank $k-1$, length $n-d$, and minimum distance at least $\lceil d/2\rceil$. Repeating with a minimum-weight codeword at each stage givesbecause nested ceilings obeyThuswhich is the binary Griesmer bound.