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

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

For a continuous closed path $\gamma :[0,1]\to \mathbb{C}\setminus \{0\}$, choose a continuous argument liftIts winding number of a continuous closed path about zero isFor a piecewise smooth path this equals $(2\pi i{)}^{-1}{\int }_{\gamma }dz/z$.

If $|\gamma (t)|>|\varphi (t)|$, thennever vanishes, since $|H(s,t)|\ge |\gamma (t)|-s|\varphi (t)|>0$. Thus $H$ is a homotopy through closed paths avoiding zero. By homotopy invariance of winding number, or directly by the dominated-perturbation lemma,

More generally, ${\gamma }_0$ and ${\gamma }_1$ are homotopic by paths in $\Gamma$ when there is a continuous functionwith $H(0,t)={\gamma }_0(t)$, $H(1,t)={\gamma }_1(t)$, and $H(s,0)=H(s,1)$ for every $s$. The winding-number theorem states that such a homotopy implies

For the Fundamental theorem of algebra, let $P(z)=a_n{z}^n+\cdots +a_0$ with $n\ge 1$. For sufficiently large $R$,for every $t$. The dominated-perturbation lemma shows that $t\mapsto P(R{e}^{2\pi it})$ has the same winding number as $t\mapsto a_n{R}^n{e}^{2\pi int}$, namely $n$. If $P$ had no zero, however,would be a homotopy in $\Gamma$ from that loop to the constant loop $P(0)$, whose winding number is zero. This contradiction proves that $P$ has a complex root. This is the winding-number proof of the fundamental theorem of algebra.

Finally suppose that a continuous retraction $r:D^2\to S^1$ existed. The boundary loop $\eta (t)=e^{2\pi it}$ has winding number one, while $(1-s)\eta (t)$ contracts it to zero inside the disc. Composing this contraction with $r$ gives a homotopy through loops in $S^1$ from $r\circ \eta =\eta$ to the constant loop $r(0)$. Their winding numbers are respectively one and zero, contradicting homotopy invariance. Hence there is no such retraction, as in the winding-number proof of the no-retraction theorem.

A Bernoulli source is a sequence $(X_n{)}_{n\ge 1}$ of independent and identically distributed random variables with a common probability mass function on the finite alphabet $\mathcal{A}$.

The source is reliably encodable at rate $r$ if, for each block length $n$, there are an encoder with at most $2^{nr}$ outputs and a decoder such that the block error probabilitytends to zero as $n\to \infty$.

Its information rate is the limiting information entropy per source symbol,when this limit exists.

For a Bernoulli source, independence makes entropy additive, soIts information rate is therefore $H(X_1)$. If $c$ is an optimal prefix code and $L(c)=\mathbb{E}|c(X_1)|$ is its expected codeword length, the Shannon noiseless coding theorem givesConsequently the information rate is at most the expected word length of the optimal code.

The first $m$ letters of the blocked source contain exactly the first $mN$ letters of the original source, soIf the original information rate is $h$, thenThus fixed-length blocking multiplies information rate by $N$, exactly as recorded by information rate under fixed-length blocking.

A subset $A\subseteq {\Sigma }^{\ast }$ is a computably enumerable set if there is a program, equivalently a register machine, that halts on input $w$ exactly when $w\in A$. It need not halt when $w\notin A$.

Statement (i) implies (ii) directly from the definition: if $A$ is computably enumerable, its semidecision program computes a partial computable function whose domain is exactly $A$; for example, return the empty word whenever the program halts.

Suppose $A=\mathrm{dom}f$ for a partial computable function $f$. Defineand leave $g(w)$ undefined otherwise. A program computes $g$ by running $f(w)$ and returning $w$ if that computation halts. Hence $g$ is partial computable andwhich proves (ii)$\Rightarrow$(iii).

Suppose $A=\mathrm{ran}f$ for a partial computable function $f$. Since $A\ne \varnothing$, fix $a_0\in A$. Decode each input $w$ as a pair $((w{)}_0,(w{)}_1)=(u,t)$. Using the truncated computation function, defineThis is a total computable function, and every output lies in $A$. Conversely, if $a=f(u)$, choosing $t$ at least the halting time gives an input $w$ with $h(w)=a$. Thus $\mathrm{ran}h=A$, proving (iii)$\Rightarrow$(iv).

Suppose $A=\mathrm{ran}h$ for a total computable function $h$. Effectively enumerate the words as $w_0,w_1,\dots$. On input $x$, computein order and halt as soon as one equals $x$. Every individual computation terminates because $h$ is total. The search halts exactly for $x\in \mathrm{ran}h=A$, so $A$ is computably enumerable. This proves (iv)$\Rightarrow$(i) and completes the equivalence recorded by the domain and range characterizations of a nonempty computably enumerable set.

The commands choose $n=100$ observations and $p=2$ predictors; generate a $100\times 2$ matrix $X$ of independent standard-normal values; generate independent binary random variables $Y_i$ with success probability $1/2$; and report the observed number of successes, ${\sum }_i{Y}_i=48$. The first glm call then fits the Bernoulli logistic-regression modelThe prediction command returns the fitted response probabilities ${\hat{p}}_i$ and sums them.

The likelihood isAt the maximum-likelihood estimator, the intercept component of the score function isThereforeexactly, by the fitted-mean balance for logistic regression with an intercept.

The second fit uses probit regression,where $\Phi$ is the standard normal distribution function. Its intercept score isa weighted residual equation. It does not imply ${\sum }_i{\hat{p}}_i=48$, so exact equality is not expected. The output should nevertheless be close to $48$: the data were generated with constant success probability $1/2$ independently of $X$, so the fitted slopes should be small, the linear predictors should cluster near a common intercept, and the score weights should be nearly constant.

This is the SIR model with waning immunity. The mass-action interaction term $\beta IS$ transfers people from the susceptible compartment to the infected compartment, $\nu I$ transfers infectives to the recovered compartment, and $fR$ returns recovered people to susceptibility as immunity wanes. Adding the equations givesso the total population $N$ is conserved.

When $f=0$ and infection is rare, $S\simeq N$ andThus $I$ initially decays if $\beta N<\nu$. Equivalently, the basic reproduction number is ${\mathcal{R}}_0=\beta N/\nu <1$, so the epidemic invasion threshold is not crossed and no epidemic occurs.

At a nontrivial equilibrium $I^{\ast }>0$, the equation $I^{\prime }=0$ givesThe equation $R^{\prime }=0$ gives $R^{\ast }=\nu I^{\ast }/f$, and conservation of population then yieldsThese values are positive precisely in the epidemic regime $\beta N>\nu$.

Eliminate $R=N-S-I$. The two-dimensional system isSet $a=\beta I^{\ast }=f(\beta N-\nu )/(f+\nu )>0$. The Jacobian matrix at the endemic equilibrium isso its eigenvalues satisfyTheir sum is $-(f+a)<0$ and their product is $a(f+\nu )>0$, proving local asymptotic stability.

The discriminant isWriting $r=\beta N-\nu >0$, we have $a=fr/(f+\nu )$. As $f\to 0^{+}$,whereas as $f\to \infty$,Hence sufficiently slow immunity loss gives a stable focus: $I(t)$ approaches $I^{\ast }$ through damped oscillations, corresponding to successively smaller epidemic waves. Sufficiently rapid immunity loss gives a stable node: small disturbances are sums of two decaying real modes and show no forced oscillation. These conclusions and the equilibrium formulas are collected in the Endemic equilibrium of the SIR model with waning immunity.

For $\Re s>1$, absolute convergence permits separation into odd and even terms:Using the defining integral of the Gamma function and the substitution $u=nt$ givesTermwise integration is justified by absolute convergence when $\Re s>1$, and the geometric sum isConsequently the Dirichlet eta function satisfies

Near zero the integrand is $O(t^{\Re s-1})$, while at infinity it decays exponentially. The integral therefore defines a holomorphic function for $\Re s>0$. Thusprovides the desired continuation wherever the displayed denominator is nonzero. At a nonreal zero of $1-2^{1-s}$, use insteadwith an integer $k$ for which $1-k^{1-s}\ne 0$; the bounded partial sums of $a_n$ give convergence for $\Re s>0$. This shows that those apparent singularities are removable and yields the Analytic continuation of the Riemann zeta function to the right half-plane.

At $s=1$,whereasHenceso $s=1$ is a simple pole and its residue is

A fixed space frame is an inertial orthonormal frame whose axes remain fixed in space. A principal body frame is attached to the rigid body and aligned with the principal axes of its inertia tensor, so that the tensor is diagonal with entries $I_1,I_2,I_3$.

If $e_i(t)$ are the body axes and $\omega$ is the angular velocity, then the derivative of a body-fixed basis vector isIn the principal frame,For torque-free motion, the angular momentum has zero space derivative. ThereforeTaking body-frame components gives the Euler equations for a torque-free rigid body:

For an axisymmetric body, put $I_1=I_2=I$ and let $e_3$ be its symmetry axis. Decompose $\omega ={\omega }_1{e}_1+{\omega }_2{e}_2+{\omega }_3{e}_3$. ThenThus $L$ is a linear combination of $\omega$ and $e_3$, proving that the angular momentum, angular velocity, and symmetry axis are always coplanar. This is the coplanarity in a torque-free axisymmetric rigid body.

The given formula is the integral of the Planck photon distribution. SetThenwhereEach photon of frequency $\nu$ has energy $h\nu$, so the energy density isThis is the temperature scaling of thermal photon number and energy densities.

After decoupling, cosmological redshift givesThe occupation number is conserved along the freely propagating photon trajectory. Its exponential argument at decoupling becomesThus the spectrum still has the Planck form ifFrequency and temperature redshift by the same factor, which is the redshift preservation of a thermal photon spectrum.

Expanding either Bell state and using $⟨0|1{⟩}_B=0$ removes the cross terms:Thus the two expectation values agree. Equivalently, both states have the same reduced density matrix $I/2$ on qubit $A$; the positivity of $Q$ makes it a possible measurement effect but is not needed for the algebraic equality.

Yes. The states $|{\Phi }^{+}⟩$ and $|{\Phi }^{-}⟩$ are orthogonal, sinceA joint projective measurement in the Bell basis therefore distinguishes them with certainty. Concretely, a controlled-NOT followed by a Hadamard gate converts the Bell basis into the computational basis before measurement.

No. Taking the partial trace over $B$ givesEvery measurement on $A$ alone therefore has identical outcome probabilities in the two cases. This is the local indistinguishability of Bell-state phase.

Yes. Alice and Bob both measure in the Hadamard basis $|+⟩,|-⟩$. The identitiesshow that their outcomes agree for $|{\Phi }^{+}⟩$ and differ for $|{\Phi }^{-}⟩$. After exchanging one classical bit they know which state they had. This is the LOCC discrimination of two Bell states.

No. In quantum dense coding, Alice's four encodings produce four different joint Bell states, but the qubit she transmits has reduced statein every case. Charlie intercepts only that qubit, so every measurement he can perform has the same probability distribution for messages $00,01,10,11$. He gains no information about the two-bit string.

The Baire category theorem states that every countable intersection of open dense subsets of a complete metric space is dense. Equivalently, no nonempty open subset of a complete metric space is a countable union of nowhere dense sets.

To prove the first form, let $G_1,G_2,\dots$ be open dense subsets of a complete metric space $X$, and let $V\subseteq X$ be nonempty and open. Choose a closed ballInductively, density and openness of $G_{n+1}$ allow a closed ballThe balls are nested and $d(x_m,x_n)<2^{-n}$ for $m>n$, so $(x_n)$ is Cauchy. Completeness gives $x_n\to x\in X$. For every $n$, all later centres lie in $\overline{B}(x_n,r_n)$; closedness gives $x\in \overline{B}(x_n,r_n)\subseteq G_n$. The first ball also lies in $V$, henceSince every nonempty open $V$ meets the intersection, that intersection is dense.

Every summand is at most $2^{-r}$, and ${\sum }_{r\ge 0}{2}^{-r}=2$, so $d(f,g)$ is finite and well defined. Nonnegativity and symmetry follow from the uniform norm. If $d(f,g)=0$, its $r=0$ summand gives $\Vert f-g{\Vert }_{\infty }=0$, hence $f=g$. Finally,and the triangle inequality for each uniform norm give the triangle inequality for $d$. Thus $d$ is a metric.