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

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.

Let $\hat{\delta }$ be the extended transition function of a deterministic finite automaton. States $p,q\in Q$ are equivalent, or indistinguishable, whenThe quotient deterministic finite automaton by indistinguishable states $D/\sim$ has state set $Q/\sim$, initial state $[q_0]$, accepting states $\{[q]:q\in F\}$, and transitionRight invariance of $\sim$ makes this well-defined, and the quotient accepts $L(D)$.

To prove minimality, choose for each state $q$ of the accessible automaton $D$ a word $w_q$ with ${\hat{\delta }}_D(q_0,w_q)=q$. Run the same word in any DFA $A$ accepting $L(D)$, and assign the class $[q]$ the reached state of $A$. If two distinct classes $[p]\ne [q]$ reached the same state of $A$, every continuation $u$ would have the same acceptance result after $w_p$ and $w_q$. Since $A$ and $D$ accept the same language, this would make $p$ and $q$ indistinguishable in $D$, a contradiction. Thus $A$ has at least one distinct state for every class in $D/\sim$, proving that the quotient is the minimal deterministic finite automaton.

For divisibility by seven, take states $Q=\{0,1,\dots ,6\}$, initial state $0$, accepting set $F=\{0\}$, and transitionsAfter reading a word, the state is its binary value modulo seven, so this binary divisibility automaton accepts exactly the multiples of seven, with leading zeros allowed. Every state is accessible: the three-bit words representing $0,1,\dots ,6$ reach the corresponding residues.

For distinct residues $p,q$, let $w_p$ be the three-bit representation of $-p(\mathrm{mod}7)$, chosen in $\{0,\dots ,6\}$. Since $2^3\equiv 1(\mathrm{mod}7)$, reading $w_p$ from state $p$ ends atwhereas reading it from $q$ ends at $q-p\ne 0$. Thus $w_p$ distinguishes $p$ from $q$. All seven states are pairwise distinguishable, so the DFA is minimal by the Myhill-Nerode theorem.

Let $Y_{ij}$ be the number of ice creams in price category $i\in \{\mathrm{high},\mathrm{low},\mathrm{medium}\}$ and score category $j\in \{\mathrm{excellent},\mathrm{good},\mathrm{poor}\}$. The fitted Poisson regression assumes that the nine counts are independent random variables withwhere the logarithmic link function is used and excellent is the reference level in a regression factor, so ${\beta }_{\mathrm{excellent}}=0$. Equivalently,This is the independence log-linear model for a two-way contingency table: price and score have main effects but no interaction.

Write $y_{i+}={\sum }_j{y}_{ij}$ and ${\mu }_{i+}={\sum }_j{\mu }_{ij}$. Under the model in part (a),and $p_j$ is independent of the price category $i$. The Poisson-multinomial conditioning identity givesMore explicitly, the likelihood function for row $i$ factors asThe first factor is the likelihood of the row total and the second is the conditional multinomial likelihood. The free price effect ${\alpha }_i$ makes the first factor maximal at ${\hat{\mu }}_{i+}=y_{i+}$, while maximizing the remaining factors givesConsequently both fits have the same maximum-likelihood fitted valueHere every row total is $30$, the column totals are $31,28,31$, and $y_{++}=90$, so every fitted row isThis factorization is the Poisson trick.

The null hypothesis is that price and score are independent, equivalently that the independence log-linear model for a two-way contingency table is correct. Against the saturated alternative, the reported Poisson deviance is the likelihood-ratio test statisticUnder the null and the usual large-sample regularity assumptions, Wilks theorem givesThe observations must be independent, the cell probabilities must not lie on the boundary of the parameter space, and the expected counts must be large enough for the chi-squared asymptotic approximation. The fitted counts are either $31/3$ or $28/3$, so the customary expected-count check is comfortably satisfied. Since(equivalently, the p-value is about $0.329$), we do not reject the null at the $1\%$ significance level. The data provide no significant lack of fit for independence.

Both variables are ordinal categorical variables, and the proposed alternative is directional: higher scores should tend to occur at higher prices. Assign increasing numerical scores to low, medium, high price and to poor, good, excellent quality, and use a one-sided linear-by-linear association test. Its statistic is based on the sample covariance, or equivalently the correlation, of those scores under the fixed margins.

This test uses one degree of freedom and directs its rejection region toward positive association. The four-degree-of-freedom likelihood-ratio test of independence in a contingency table spends power on every possible departure from independence, including unordered and negative patterns, so the ordered one-sided test is more powerful when the stated alternative is credible.

The Papperitz symbolrepresents the two-dimensional solution space of a homogeneous linear differential equation for a second-order Fuchsian differential equation on the Riemann sphere. Its only singularities are the three regular singular points $a,b,c$. The two entries beneath each point are its characteristic exponents at a regular singular point: for example, in the nonresonant case a local basis near $a$ has leading behaviours $(z-a{)}^{\alpha }$ and $(z-a{)}^{{\alpha }^{\prime }}$. If one of the points is infinity, exponent $\rho$ conventionally means behaviour $z^{-\rho }$ there.

The six exponents obey the Fuchs relationSubject to this relation, the symbol determines the corresponding Riemann differential equation; resonant differences between exponents may produce Logarithmic Frobenius solutions without changing the exponent data recorded by the symbol.

Let $\omega$ solve the equation represented by the original symbol and define a dependent-variable rescaling of a Papperitz symbolwith a consistent local choice of branch. Near $a$, the multiplier is a nonzero analytic factor times $(z-a{)}^{\delta }$, so both exponents at $a$ increase by $\delta$. Near $b$, it is a nonzero analytic factor times $(z-b{)}^{-\delta }$, so both exponents at $b$ decrease by $\delta$. It is analytic and nonzero near $c$, so the exponents there are unchanged. Therefore the transformed equation has symbolThe opposite shifts also preserve the Fuchs relation.