Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2

The Möbius function is defined by $\mu (1)=1$ and, for $n>1$,It is a multiplicative arithmetic function: $\mu (mn)=\mu (m)\mu (n)$ whenever $m$ and $n$ are coprime.

The summand $\mu (d{)}^2/\varphi (d)$ is multiplicative, so its divisor sum is multiplicative. For a prime power $p^a$ with $a\ge 1$, only $d=1,p$ contribute andMultiplying these local identities over the prime divisors of $n$ gives

For the final claim, choose distinct primes $p_0,\dots ,p_k$. The moduli $p_j^2$ are pairwise coprime, so the Chinese remainder theorem gives an integer $a$ satisfyingEvery positive integer $n\equiv a(\mathrm{mod}{\prod }_j{p}_j^2)$ then has $p_j^2\mid n+j$. HenceThere are infinitely many positive representatives of this congruence class.

True. Continuity and compactness give a maximum of $\varphi$ on $\overline{\Omega }$. At an interior maximum the Hessian matrix is negative semidefinite, so its trace satisfies $\Delta \varphi \le 0$, contradicting $\Delta \varphi >0$. The maximum must therefore occur on $\partial \Omega$. This is the strict form of the maximum principle for subharmonic functions.

False. On the open unit disk, letThen $\Delta \varphi =-4<0$, but the unique maximum is $phi(0,0)=0$, whereas $phi=-1$ on the boundary.

False. On the open unit disk take, for $0<\epsilon <1$,Its relevant fourth derivatives satisfyNevertheless, since $x^4+y^4\le (x^2+y^2{)}^2$, every point with $0<x^2+y^2\le 1$ hasThus the maximum lies strictly inside $\Omega$.

True. This follows from the maximum principle for harmonic functions. A direct reduction to part (i) is also possible: for $\epsilon >0$, setThen $\Delta {\varphi }_{\epsilon }=4\epsilon >0$, soBecause $\Omega$ is bounded, ${\varphi }_{\epsilon }\to \varphi$ uniformly as $\epsilon \downarrow 0$. Taking the limit yields

For a binary symmetric channel with crossover probability $p$, the capacity iswhere $H_2$ is the binary entropy. Shannon second coding theorem says that for every transmission rate $R<C$ and every $ϵ>0$, sufficiently long block codes exist with rate at least $R$ and decoding-error probability below $ϵ$; conversely, a sequence of codes whose error tends to zero cannot have limiting rate above $C$.

For the general channel let $X$ and $Y$ be its input and output. Every conditional output distribution is a permutation of $(p_1,\dots ,p_n)$, hencefor every input distribution. Since $H(Y)\le \log n$,The uniform input makes every output probability equal to $1/n$: the column-permutation assumption and the total sum imply that all column sums are equal to one. It therefore attains $H(Y)=\log n$, proving

In the displayed four-output channel each row is a permutation ofWith base-two logarithms,

For a deterministic finite automaton the extended transition function of a deterministic finite automaton is recursivelyThe accepted language isFor a nondeterministic finite automaton, $\hat{\delta }(q,w)$ is the set of all states reachable from $q$ while reading $w$; recursively,Thus

The powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transitionand accepting states $\{S\subseteq Q:S\cap F\ne \varnothing \}$. Induction on $|w|$ givesso the two automata accept exactly the same language. If $|Q|=m$ and $F$ has one state, exactly $2^{m-1}$ of the $2^m$ subset states contain it and are accepting, including states that may be unreachable.

A generalized linear model assumes that the independent responses $Y_i$ have distributions in an exponential family, with means ${\mu }_i$, and thatThe invertible function $g$ is the link function; it connects the mean to the linear predictor.

For binomial regression, write $Y_i\sim \mathrm{Bin}(m_i,p_i)$ independently, so ${\mu }_i=m_i{p}_i$. The logistic regression link iswhile probit regression useswhere $\Phi$ is the standard-normal distribution function. The logit is the canonical link function for the binomial family.

The birth-death master equation must include jumps of size two on death. For $n\ge 2$,At the boundary states it is

Differentiate $⟨f(n)⟩={\sum }_{n\ge 0}{f}_n{p}_n$ and substitute the three master equations. Reindexing every gain term by its source state gives one contribution per possible transition:This is the generator identity for a continuous-time Markov chain applied to the test function $f$.

Set $f_n=n$. A birth changes $f$ by $1$, an ordinary pair death by $-2$, and singleton death by $-1$. HenceWhen $D=2d$ this closes toso the stationary mean is ${\mu }_{\ast }=b/(2d)$.

For $f_n=n^2$, the birth increment is $2n+1$, whileWith $D=2d$, the generator identity givesAt stationarity $\mu =b/(2d)$, and solving this equation for the variance yieldsFor $b,d>0$ the chain is irreducible on the nonnegative integers, so its stationary distribution has $0<p_1<1$. Therefore

The point $z_0$ is an ordinary point when both $p$ and $q$ are holomorphic at $z_0$.

The point $z_0$ is a regular singular point when it is singular butextend holomorphically to $z_0$.

A singular point which is not regular singular is an irregular singular point: at least one of $(z-z_0)p(z)$ and $(z-z_0{)}^{2}q(z)$ fails to extend holomorphically to $z_0$.

Put $t=1/z$ and $y(t)=w(1/t)$. Sincethe transformed equation is

By the transformed equation, infinity is ordinary precisely whenare holomorphic at $t=0$. Equivalently, as convergent Laurent expansions near infinity,

By the regular singular point at infinity criterion, infinity is regular singular precisely whenare holomorphic at $t=0$, but the ordinary-point conditions fail. Equivalently,with convergent expansions in $1/z$, excluding the ordinary case.

Infinity is irregular singular when at least one offails to be holomorphic as a function of $1/z$ at $1/z=0$.

Suppose there were no singular point in the Riemann sphere. Then every finite point would be ordinary, so $p$ and $q$ would be entire functions. Ordinary behavior at infinity would force $p(z)=2/z+O(z^{-2})$ and $q(z)=O(z^{-4})$. In particular $p(z)\to 0$, so Liouville theorem would give $p\equiv 0$, contradicting the required leading term $2/z$. Thus infinity cannot also be ordinary, and every such differential equation has at least one singular point in $\overline{\mathbb{C}}$.

Let $R$ be the center of mass and $g$ the uniform gravitational acceleration. The gravitational torque about $R$ is

Choose body-fixed principal axes of inertia. The inertial derivative of the angular momentum isFor torque-free motion $N=0$ and $L_i=I_i{\omega }_i$, giving the Euler equations for a torque-free rigid body

For a symmetric top, let $I_1=I_2=I$ and let $I_3$ be the axial moment. Then ${\omega }_3$ is constant andThus ${\omega }_1^2+{\omega }_2^2$ is constant and the transverse angular-velocity vector rotates uniformly about the body symmetry axis. Its rate is $|\Omega |$; it precesses in the positive axial sense when $(I_3-I){\omega }_3>0$ and in the opposite sense when this product is negative.

For bosons the occupation number is $n_{\mathbf{p}}=0,1,2,\dots$. Summing the geometric series for the single-mode grand canonical ensemble gives the Bose-Einstein distribution

For fermions the Pauli exclusion principle permits only $n_{\mathbf{p}}=0,1$. The two-term partition sum gives the Fermi-Dirac distribution

Write $n_b=n_e+n_H\simeq \eta n_{\gamma }$. Charge neutrality gives $n_p=n_e$, and thereforeSubstitution into the Saha ionization equation yieldsUsing the given photon density,

The baryon-to-photon ratio is extremely small. Even when $k_{B}T\ll I$, the high-energy tail of the enormous photon population contains enough ionizing photons per baryon to delay cosmological recombination. The exponential factor must become large enough to overcome both $\eta \sim 10^{-9}$ and the phase-space factor, which occurs near $k_{B}T\simeq 0.3\mathrm{eV}$ rather than near $I$.

Apply a Hadamard gate to every qubit. The amplitude of $|0^n⟩$ becomesIt equals $1$ in case (I) and $0$ in case (II). A computational-basis measurement therefore returns $0^n$ with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice preparesusing one query to her quantum oracle, and sends these $n$ qubits to Bob. Bob applies his phase oracle, producingThe function $h=f_A\oplus f_B$ is constant zero in case (1) and balanced in case (2). Bob applies $H^{\otimes n}$ and measures as above: outcome $0^n$ identifies case (1), while every other outcome identifies case (2), with certainty.

Bilinearity and symmetry are immediate. Since $r\ge 0$, $⟨u,u⟩\ge 0$. If this is zero, continuity of $u^{2}r$ makes it identically zero. The points where $r>0$ are dense because only finitely many are excluded, so $u$ vanishes on a dense set and hence everywhere. Thus the form is an inner product.

Apply the Gram-Schmidt process to $1,x,\dots ,x^n$. The last resulting vector $P_n$ is nonzero, has degree exactly $n$, and is orthogonal to every polynomial in $\mathrm{span}(1,x,\dots ,x^{n-1})$.

Let $x_1,\dots ,x_k$ be the distinct zeros in $(-1,1)$ at which $P_n$ changes sign, and put $Q(x)={\prod }_{j=1}^k(x-x_j)$. Then $P_{n}Q$ has constant sign and is nonzero except at finitely many points, soIf $k<n$, this contradicts the orthogonality of $P_n$ to the lower-degree polynomial $Q$. Hence $k\ge n$; degree $n$ forces exactly $n$ distinct, simple roots, all in $(-1,1)$.

Let ${\ell }_j$ be the Lagrange interpolation polynomial for the roots ${\omega }_j$, and defineFor $\mathrm{deg}Q\le 2n-1$, polynomial division gives $Q=S{P}_n+R$ with $\mathrm{deg}S,\mathrm{deg}R<n$. Orthogonality kills the first term, while interpolation gives $R={\sum }_{j}R({\omega }_j){\ell }_j$. ThereforeTaking $Q={\ell }_j$ proves uniqueness. Taking $Q={\ell }_j^2$ also showsThis is Gaussian quadrature.

Given $ϵ>0$, the Weierstrass approximation theorem supplies a polynomial $Q$ with $\Vert f-Q{\Vert }_{\infty }<ϵ$. For all sufficiently large $n$, the quadrature is exact on $Q$. Positivity of the weights and ${\sum }_j{A}_j=\int r$ then giveLetting $ϵ\downarrow 0$ proves convergence.

Write $f=Q_{2n-1}+E_n$, where $Q_{2n-1}$ contains the terms through degree $2n-1$. On $[-1,1]$,The quadrature error of $Q_{2n-1}$ is zero. Bounding the integral and quadrature errors of $E_n$ separately, using positive weights with total $\int r$, gives exactly

With $x=\cos \theta$, the weight becomes ${\sin }^2\theta d\theta$. Sincethe sine orthogonality relations show that $P_n$ is a scalar multiple of the Chebyshev polynomial of the second kind $U_n$. Its roots areThe printed normalization $P_n(0)=1$ is possible only for even $n$; then $U_n(0)=(-1{)}^{n/2}$ andFor odd $n$, every such orthogonal polynomial is odd and vanishes at zero, so that normalization is inconsistent.

A binary cyclic code is a linear subspace $C\le {\mathbb{F}}_2^n$ invariant under cyclic coordinate shift. Identify a word $(c_0,\dots ,c_{n-1})$ with $c_0+c_{1}X+\cdots +c_{n-1}{X}^{n-1}$ inCyclic shift is multiplication by $X$, so cyclic codes are exactly ideals of this quotient. Since ${\mathbb{F}}_2[X]$ is a principal ideal domain, each is generated by a unique monic divisor $g\mid X^n-1$, giving the required bijection.

A linear-feedback shift register is a linear mapFor the stated matrix $H$, a word $c=(c_0,\dots ,c_{k-1})$ lies in $C$ exactly when ${\sum }_j{c}_j{M}^{j}x=0$. If $\sigma c$ is its cyclic shift, periodicity $M^{k}x=x$ givesThus $\ker H$ is shift-invariant and is a binary cyclic code.