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

The binomial theorem givesThe central binomial coefficient is the largest of these $2n+1$ nonnegative binomial coefficients, so

For the upper bound, fix a prime number $p\le 2n$. By Legendre formula,Each summand is either zero or one. Hence the P-adic valuation satisfiesIf $p\le \sqrt{2n}$, this impliesThere are at most $\sqrt{2n}$ such prime numbers. If instead $p>\sqrt{2n}$, then $p^2>2n$, so the P-adic valuation is at most one. Multiplying the prime-power contributions therefore yields

Write the Chebyshev theta function asTaking natural logarithms in part a givesand henceBecause $\sqrt{n}\log n/n\to 0$, the right-hand side is at least $n/2$ for every sufficiently large integer $n$.

Now let $x$ be sufficiently large and set $n=\lfloor x/2\rfloor$ using the floor function. Then $2n\le x$ and $n\ge x/3$, so the monotonicity of $\vartheta$ gives

Suppose that the positive integer $n$ is a decisive number. For every prime number $p<\sqrt{n}$, the composite number $p^2$ satisfies $1<p^2<n$. It therefore cannot be coprime to $n$, so $p\mid n$.

The product of all prime numbers below $\sqrt{n}$ consequently divides $n$. Taking natural logarithms givesChanging the strict endpoint can remove at most one prime term. By part b, for every sufficiently large $n$ the right-hand side is at least, for example, $\sqrt{n}/13$. This is impossible for sufficiently large $n$, sinceThus every decisive number lies below one fixed bound, and only finitely many integers can do so.

The polynomial form of Runge theorem says that if $K\subset \mathbb{C}$ is compact, $\mathbb{C}\setminus K$ is connected, and $f$ is holomorphic on a neighbourhood of $K$, then for every $\epsilon >0$ there is a polynomial $P$ such that

Statement (i) is false. Take the entire function $f(z)=e^{-z}$. It is bounded on the closed first quadrant $E$. If polynomials $P_n$ converged uniformly to $f$ on $E$, then each sufficiently late $P_n$ would be bounded on the positive real axis. A polynomial bounded on that ray must be constant. No sequence of constants converges uniformly to $e^{-x}$ on $[0,\infty )$, since its values at zero and near infinity differ by one.

Statement (ii) is true. LetEach $K_n$ is compact and has connected complement. By the polynomial Runge theorem, choose a polynomial $P_n$ withEvery fixed $z\in E$ belongs to $K_n$ for all sufficiently large $n$, so $P_n(z)\to f(z)$. Thus the convergence is pointwise on $E$.

Statement (iii) is false. Let $\Omega$ be a thin open annulus about the unit circle, let $f(z)=1/z$, and split the circle into two proper closed arcs $K_1,K_2$ whose union is the whole circle. Each arc has connected complement, so polynomial approximation of the reciprocal on a proper circular arc gives uniform polynomial approximations to $f$ on each $K_j$ separately.

If polynomials $P_n$ converged uniformly to $1/z$ on $K_1\cup K_2$, then uniform convergence on the unit circle and the Cauchy integral theorem would givea contradiction.

Statement (iv) is true. Apply the Weierstrass approximation theorem separately to the real and imaginary parts of the continuous function $f$ on the compact interval $[0,1]$. Combining the two real polynomial sequences gives complex polynomials converging uniformly to $f$ on $I$.

Write $1_n$ for the all-one column vector. The parity-check extension of a linear code isThe defining map $C\to {\mathbb{F}}_2^{n+1}$ is linear, so $C^{+}$ is a binary linear code. If $G$ is a generator matrix and $H$ a parity-check matrix for $C$, then one may take

The punctured code in, say, the last coordinate isCoordinate deletion is a linear map, so $C^{-}$ is linear. Its generator matrix $G^{-}$ is obtained by deleting the last column of $G$. If the minimum distance is at least two, deletion is injective on $C$, and hence $C^{-}$ has the same dimension as $C$.

For its parity-check matrix, first use invertible row operations on $H$ to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to $C$, contrary to $d\ge 2$. Delete the pivot row and the last column; the resulting matrix $H^{-}$ is a parity-check matrix for $C^{-}$. Equivalently, $(C^{-}{)}^{\perp }$ is obtained by shortening the dual code $C^{\perp }$ at the deleted coordinate.

Finally, the shortened code in the last coordinate isIt is linear whenever $C$ is linear, because it is the puncture of the subspace $C\cap \{x_n=0\}$.

For the formal grammar $G=(\Sigma ,V,P,S)$,Thus $L(G)$ contains exactly the finite terminal words reachable from the start symbol by a finite grammar derivation.

Two formal grammars over the same terminal alphabet are equivalent when they generate the same language:

Two formal grammars over the same terminal alphabet are isomorphic when there is a bijection $\varphi :V_0\to V_1$ between their nonterminals such that $\varphi (S_0)=S_1$ andwhere $\varphi$ is extended to words by fixing each terminal and acting symbol by symbol.

The grammars are isomorphic. The bijectionmaps every production of $P_0$ to the corresponding production of $P_1$. They are therefore equivalent. Notice that $B$ in the first grammar and $C$ in the second are unreachable; the isomorphism also preserves this irrelevant component.

The grammars are non-equivalent. In the first grammar, terminal derivations without $AB\to c$ giveAfter applying $B\to Bb$ any number of times while $A$ and $B$ remain adjacent, the production $AB\to c$ also givesHence, in particular, $ab\in L(G_0)$ and $c\in L(G_0)$.

In the second grammar, the fixed terminals $ab$ in $XabY$ prevent $X$ and $Y$ from ever becoming adjacent, so $XY\to c$ can never be used. The remaining productions give exactlyThus $ab,c\notin L(G_1)$, proving that the generated languages differ.

The first grammar generatesbecause $A\to bAb$ adds two $b$'s and $A\to b$ terminates the derivation.

In the second grammar, $Z$ is a nonproductive nonterminal: every right-hand side of a $Z$-production still contains a $Z$. Consequently the branch $Y\to ZZ$ never yields a terminal word. Every terminal derivation from $Y$ instead uses $Y\to bYb$ repeatedly and ends with $Y\to b$, soThe grammars are therefore equivalent, although they are not isomorphic.

A one-parameter exponential family with natural statistic $Y$ has density or probability mass functionwhere $\theta$ is the natural parameter of an exponential family and $K$ is the cumulant function of an exponential family. Its mean parameter is

The exponential-family deviance from ${\theta }_1$ to ${\theta }_2$ is twice the Kullback-Leibler divergence:The carrier $h(Y)$ cancels from the likelihood ratio, so, with ${\mu }_1={\mathbb{E}}_{{\theta }_1}Y$,

For the Poisson distribution with mean $\mu$,ThereforeWriting ${\mu }_2={\mu }_1+\delta$ and applying the Taylor series of $\log (1+\delta /{\mu }_1)$ givesso the second-order approximation is

With $s=0$, the equilibria satisfyBesides $g=0$, the two positive equilibria arewhere $g_{-}{g}_{+}=1$. Sincethe nonzero equilibrium relation $k=(1+g^2)/g$ givesThe fixed point stability for an autonomous differential equation therefore shows that $g=0$ and $g_{+}$ are stable, while $g_{-}$ is unstable. The graph of $f(g,0)$ starts at zero with negative slope, crosses upward at $g_{-}$, crosses downward at $g_{+}$, and tends to $-\infty$ as $g\to \infty$.

For a constant input $s$, write the equilibrium equation asThe low stable equilibrium and the intervening unstable equilibrium coalesce in a saddle-node bifurcation. More precisely, let $g_c$ be the first positive solution ofand defineEquivalently, $f(g_c,s_c)=0$ and ${\partial }_{g}f(g_c,s_c)=0$, with $g_c$ on the low-concentration branch. If $s_1>s_c(k)$, that branch no longer exists. Holding the input long enough carries the trajectory into the basin of attraction of the high state. When the input returns to zero, the concentration converges toThis is the saturating autocatalytic switch.

For $k\gg 1$, the threshold occurs at $g=O(k^{-1})$, soThe approximate double-root conditions areThus $g_c\simeq 1/(2k)$ andHence the constant in $s_c(k)\simeq C{k}^{-1}$ is $\boxed{C=1/4}$, as recorded by the strong-autocatalysis switching threshold.

Fora finite point $z_0$ is an ordinary point exactly when $p$ and $q$ are holomorphic there. It is a regular singular point exactly whenare holomorphic at $z_0$.

Put $\zeta =1/z$ and $W(\zeta )=w(1/\zeta )$. Direct differentiation givesso the transformed equation isConsequently $z=\infty$ is ordinary precisely whenare holomorphic at $\zeta =0$. It is a regular singular point at infinity precisely when $zp(z)$ and $z^{2}q(z)$ are holomorphic functions of $1/z$ near infinity.

If zero and infinity are regular singular and every nonzero finite point is ordinary, the Laurent series of $p$ and $q$ can contain only the terms compatible with both endpoint bounds. Hencefor constants $a,b$. The equation is a Cauchy-Euler differential equation. Its indicial equation isFor distinct roots ${\lambda }_1,{\lambda }_2$, the general solution on a domain with a chosen logarithm branch isFor a repeated root $\lambda$, the general solution of an Euler-Cauchy equation is

Finally require infinity to be ordinary. In the transformed equation its coefficients becomeBoth are holomorphic at zero exactly when $a=2$ and $b=0$. Thus the further restriction is

For smooth functions $f,g$ on the six-dimensional phase space with canonical coordinates $(q_i,p_i)$, the Poisson bracket is

Hamilton's equations and the multivariable chain rule giveThus the Hamiltonian conservation law gives

For the phase-space dilation generator $D=q\cdot p$,Therefore the condition $\{f,D\}=0$ is the first-order equation

If $f(\lambda q,{\lambda }^{-1}p)=f(q,p)$ for every positive real $\lambda$, differentiate with respect to $\lambda$ at $\lambda =1$. The chain rule gives exactlyso every smooth scale-invariant $f$ satisfies the constraint. The same conclusion for negative $\lambda$ follows wherever the stated invariance is defined; differentiation only needs the positive component containing $\lambda =1$.

In the nonrelativistic regime,The assumption $E-\mu \gg k_{B}T$ puts the Fermi-Dirac distribution in its Maxwell-Boltzmann limit, soTherefore the nonrelativistic Maxwell--Boltzmann number density is

For $p+e^{-}\leftrightarrow H+\gamma$, chemical equilibrium and the vanishing photon chemical potential implyApplying the number-density formula to each massive species and eliminating the chemical potentials givesUse charge neutrality, $n_p\simeq n_e$, the mass approximation $m_H\simeq m_p$, and the convention in the question that suppresses the order-one internal-degeneracy ratio $g_e{g}_p/g_H$. With the Hydrogen binding energywe obtain the Saha ionization equationThe assumptions are thermal equilibrium and chemical equilibrium before cosmological recombination, a nonrelativistic nondegenerate gas, zero photon chemical potential, charge neutrality, negligible proton-electron mass correction in the translational prefactor, and the stated degeneracy-factor approximation.

For coprime integers $a,N$ with $N>1$, the multiplicative order of $a$ modulo $N$ is

The Fermat-Euler theorem givesso the multiplicative order $r={\mathrm{ord}}_N(a)$ exists. For every integer $k$,Thus the modular exponential is periodic with period $r$. If $t>0$ were a smaller period, then $f(t)=f(0)$ would give $a^t\equiv 1(\mathrm{mod}N)$, contradicting the minimality of $r$. Hence $r$ is its least positive period.

Modulo $33$,so ${\mathrm{ord}}_{33}(10)=2$. This order is even andThe factor extraction from an even modular order therefore givesThus

The quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives