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

For $x\ge 2$, expand the finite Euler product as a product of geometric series:Every integer $1\le n\le x$ has all its prime factors at most $x$, soThe harmonic series diverges, and therefore

Suppose instead that ${\sum }_{p}1/p$ converged. For $0<t\le 1/2$,Since ${\sum }_{p}1/p^2$ converges, this would makeconverge to a finite limit, contradicting the divergence of $P(x)$. Hence the Euler proof that the sum of reciprocals of primes diverges gives

Assume for contradiction that $\pi =a/b$ with positive integers $a,b$. DefineandThe coefficient of $x^{n+j}$ in $F_n$ isConsequently every derivative $F_n^{(k)}(0)$ is an integer: it is zero unless $n\le k\le 2n$, and in that range the factor $k!/n!$ clears the denominator. Since $F_n(\pi -x)=F_n(x)$, every $F_n^{(k)}(\pi )$ is also an integer.

Repeated integration by parts, ending when derivatives above degree $2n$ vanish, givesThus $I_n$ is an integer. It is strictly positive because $F_n(x)\sin x>0$ for $0<x<\pi$.

On the other hand, $x(\pi -x)\le {\pi }^2/4$, soThe factorial-over-power series implies that the right-hand side tends to zero. For all sufficiently large $n$ this says that the positive integer $I_n$ is less than one, a contradiction. Therefore the Irrationality of pi is established:

In Diffie-Hellman key exchange, Alice and Bob publicly agree on a cyclic group $G=⟨g⟩$ in which the discrete logarithm problem is believed hard. Alice chooses a secret $a$ and sends $A=g^a$; Bob chooses a secret $b$ and sends $B=g^b$. They independently computeThusis their shared key. A passive eavesdropper sees $g,g^a,g^b$ but is believed unable to compute $g^{ab}$ efficiently; this is the computational Diffie--Hellman assumption. The basic protocol does not authenticate the participants and is therefore vulnerable to a man-in-the-middle attack unless the exchanged values are authenticated.

No. The procedure exposes a square-root oracle for the Rabin cryptosystem. The verifier chooses $m$, sends $r=m^2\mathrm{mod}N$, and receives another square root $m_1$. Ifthen the factorization from distinct square roots modulo a semiprime givesFor a product of two odd primes, a square normally has four roots, and a returned root lies outside the pair $\{\pm m\}$ with probability about $1/2$. Repeating chosen-square challenges therefore factors $N$ with overwhelming probability. The attacker can then compute square roots and impersonate Alice. This is the chosen-square attack on Rabin authentication, so the proposed protocol is insecure.

LetIntersect it with the regular languageEvery word of $R$ contains exactly two copies of $b$. If it is a proper power, its exponent must therefore be two and its root must contain one $b$. HenceThis language is not regular: if $p$ were a pumping length, pumping any nonempty substring among the first $p$ copies of $a$ in $a^{p}b{a}^{p}b$ would change only its first $a$-block. Since regular languages are closed under intersection,This is the proper-power language is not regular.

This language is recognized by the parity-counting deterministic finite automaton with four statesThe initial state is $(0,0)$ and the only accepting state is $(1,0)$. Reading $a$ leaves the state unchanged, reading $b$ toggles $p_b$, and reading $c$ toggles $p_c$. The state therefore records exactly the parities of the numbers of $b$'s and $c$'s. Thus

Use the bounded-run deterministic finite automaton with statesState $q_j$ records that the current suffix consists of exactly $j$ consecutive zeros. Every $q_0,\dots ,q_7$ is accepting; $q_{\mathrm{dead}}$ is rejecting. Reading $1$ sends every accepting state to $q_0$, while reading $0$ sends $q_j$ to $q_{j+1}$ for $j<7$ and sends $q_7$ to $q_{\mathrm{dead}}$. The dead state loops on both symbols. This finite automaton accepts exactly the words with no run of eight zeros, so

Let $K\subseteq \mathbb{N}$ be the undecidable set denoted $\mathbb{K}$ in the question. The language satisfies the pumping lemma for regular languages with pumping length one. For any nonempty $s\in L$, write $s=xyz$ with $x=\epsilon$, $y$ its first symbol, and $z$ the remaining suffix.

If $s\in b^{\ast }$, then $x{y}^{i}z\in b^{\ast }$ for every $i\ge 0$. Otherwise $s=wa{b}^n$ for some $n\in K$. If the chosen first symbol lies in $w$, pumping it preserves the same final suffix $a{b}^n$. If $w=\epsilon$, then $s=a{b}^n$: pumping down gives $b^n\in b^{\ast }$, while every positive pump gives $a^i{b}^n$ and all but its last $a$ can be absorbed into $w$. Thus every sufficiently long word has a valid pumping decomposition.

Nevertheless, if $L$ were regular language, closure under intersection would makeregular. A finite automaton deciding this unary language would decide whether $n\in K$ by running it on $a{b}^n$, contradicting the halting problem. ThereforeThis is a nonregular language satisfying the pumping lemma.

A $(1-\alpha )$ prediction interval is a pair of statistics $L(Y),U(Y)$ such that, for every $\beta$ and ${\sigma }^2>0$, an independent future response $Y^{\ast }$ at the specified input satisfies

In the normal linear model, assume $X$ has full column rank and writeFor a new observationindependent of the training sample, the prediction error isThe two terms on the right are independent centered normal random variables, whileConsequently, with the new-point regression leveragewe have

The assumption in the question givesThis variable is independent of $\hat{\beta }$; it is also independent of the new error ${\epsilon }^{\ast }$. Therefore it is independent of the standardized prediction error, and the defining normal-over-chi-square representation of Student's t-distribution givesIf $t_{n-p,1-\alpha /2}$ is the corresponding upper quantile, symmetry yieldsSolving these inequalities for $Y^{\ast }$ proves that the prediction interval in a normal linear model isIts center and endpoints depend only on the observed data and $x^{\ast }$, and the pivotal calculation proves the required coverage uniformly in the unknown $\beta$ and ${\sigma }^2$.

Put $x(t)=1+u(t)$. Retaining terms linear in $u$ givesThe exponential ansatz $u=e^{\lambda t}$ gives the characteristic equation of a delay differential equationAt $T=0$ its root is $\lambda =-\alpha$, and the remaining delay roots lie far in the left half-plane, so the equilibrium is stable for sufficiently small $T$.

A stability change can first occur when $\lambda =i\omega$. Separating real and imaginary parts givesFor the first positive crossing, $\omega T=\pi /3$ and $\omega =\sqrt{3}\alpha$. ThusAll positive-frequency crossings have $\omega T=\pi /3+2\pi k$, so there is no earlier imaginary-axis crossing. Implicit differentiation ofgives, with $q=\alpha T_c$,so the conjugate pair crosses into the right half-plane as $T$ increases. Therefore the stability threshold for delayed quadratic crowding is

Again put $x=1+u$. ThenThe linearized equation is thereforewhose sole characteristic exponent is $-\alpha <0$ and is independent of $T$. By delay-independent stability from an undelayed linearization,

Putand take the branch cut $[-1,1]$. On $\mathbb{C}\setminus [-1,1]$, choose the analytic branch of a square root whose upper boundary value isIts lower boundary value is $s(x-i0)=-\sqrt{1-x^2}$. This fixes the integrand to be $+1$ at $0^{+}$ as required.

For $0\le \arg z\le \pi$, start at $0^{+}$ and use any path to $z$ lying above the cut; path deformations within that region do not alter the integral by the Cauchy integral theorem. For $\pi <\arg z<2\pi$, start in the same way, continue counterclockwise around the branch point $-1$ from the upper bank to the lower bank, and then continue to $z$ through the lower half-plane. This second prescription is the continuation obtained as $argz$ increases through $\pi$.

Start with the germ $w=\mathrm{Arcsin}(z)$ selected in part (a) and continue it along paths in $\mathbb{C}\setminus \{-1,1\}$. At the two branch points,The monodromy reflection at a square-root branch point therefore shows that continuation once around $1$ sends $w$ to $\pi -w$, while continuation once around $-1$ sends it to $-\pi -w$. Composing these reflections produces every translation by an even multiple of $\pi$. Hence the branches of the complex inverse sine are

Let the argument of $z$ increase by $2\pi$ along a counterclockwise path enclosing both branch points. On a large circle, the branch chosen in part (a) satisfiesThe change in the primitive is consequentlyEquivalently, this is the composition of the two reflections described by the monodromy of the complex inverse sine. Thus, for this orientation,The reverse orientation gives $\mathrm{Arcsin}(z)+2\pi$. Both continued values invert the same $z$, so $\sin (w-2\pi )=\sin w$ on an open set of inverse values. The identity theorem extends this equality to every $w\in \mathbb{C}$, proving the periodicity of the complex sine:

Let $e_1,e_2,e_3$ be a principal body frame, let $I_1,I_2,I_3$ be the corresponding principal moments of inertia, and write the angular velocity as $\mathbf{\omega }={\sum }_i{\omega }_i{e}_i$. The body-frame components of the angular momentum areNo external torque acts, so $\mathbf{L}$ is constant in the fixed space frame. Since a body-fixed basis vector satisfies ${\dot{e}}_i=\mathbf{\omega }\times e_i$,Taking body-frame components gives the Euler equations for a torque-free rigid body:

Multiply the three Euler equations for a torque-free rigid body by ${\omega }_1,{\omega }_2,{\omega }_3$ and add. The cubic terms cancel, giving conservation of the rotational kinetic energyInstead multiply the equations by $I_1{\omega }_1,I_2{\omega }_2,I_3{\omega }_3$ and add. The cubic terms again cancel, givingthe squared magnitude of the conserved angular momentum. For an asymmetric body these two quadratic forms are not proportional, so the torque-free rigid-body invariants are independent.

First consider rotation predominantly about the third principal axis, writing ${\omega }_3=\Omega +O({\omega }_1^2+{\omega }_2^2)$. To first order the third Euler equation gives $\dot{\Omega }=0$, while the transverse components satisfyThereforeand the same equation holds for ${\omega }_2$.

Order the principal moments as $I_1<I_2<I_3$. The coefficient above is negative, so perturbations about axis three oscillate and remain bounded. Cyclically applying the same linear stability of principal-axis rotation calculation about axis one givesso that rotation is also stable. About axis two, however,which has an exponentially growing solution. Thus the intermediate axis theorem gives

For a relativistic species the supplied relation $P=ϵ/3$ makes its entropy density proportional to $T^3$. The fermion-to-boson thermal integral ratio gives the factor $7/8$ for each fermionic degree of freedom, so the electromagnetic plasma immediately before electron-positron annihilation in cosmology hasAfter annihilation only the two photon polarizations remain, so $g_{\ast s,\mathrm{after}}=2$.

The neutrinos have already undergone neutrino decoupling. They therefore receive none of the electron-positron entropy and cool as $T_{\nu }\propto a^{-1}$. In the still-coupled electromagnetic plasma, cosmological entropy conservation gives $g_{\ast s}{T}_{\gamma }^3{a}^3=\mathrm{constant}$. If $T_d$ and $a_d$ denote the common temperature and scale factor just before annihilation, then at a later scale factor $a$,Dividing gives the Cosmic neutrino background temperature ratio

The multiplicative order of $\alpha$ modulo $N$ is the least positive integer $r$ such thatIt exists because $\alpha$ and $N$ are coprime integers.

Suppose that $r$ is even andThe minimality of $r$ also gives ${\alpha }^{r/2}\not\equiv 1(\mathrm{mod}N)$. Sincethe factor extraction from an even modular order yieldsas a nontrivial factor of $N$; equivalently one may also compute $\gcd ({\alpha }^{r/2}+1,N)$. Thus the required conditions are that $r$ be even and that ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

Measure the second register. The order as the exact period of modular exponentiation implies that, conditional on the measured value, the first register is a normalized truncated periodic cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{QFT}}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log \log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,The supplied continued-fraction theorem, applied through continued-fraction recovery in quantum order finding, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying ${\alpha }^r\equiv 1(\mathrm{mod}N)$.

The quantum Fourier transform, quantum modular exponentiation, continued-fraction algorithm, and final modular check all take polynomial time in $\log N$. Since $r<N$, the successful event has probability of order $1/\log \log N$, as required.

Setand, for $n\ge 1$, defineWriting $M(a)=\left(\begin{array}{cc}a& 1\\ 1& 0\end{array}\right)$, these recurrences are equivalent to the continued-fraction matrix identityThe associated Möbius transformation sends a positive tail $\beta$ to the continued-fraction tail formula

Since $\det M(a_j)=-1$, taking determinants givesMoreover,whereasTheir signs are opposite, so ${\theta }_n$ lies between the two adjacent convergents. For $n=0$, the second endpoint is interpreted as $p_{-1}/q_{-1}=\infty$.

Let ${\beta }_{n+1}>0$ be the complete quotient after $a_n$. Part (a) writes the irrational number $\theta$ asso $\theta$ lies between the adjacent continued fraction convergents $p_n/q_n$ and $p_{n-1}/q_{n-1}$. Their separation isBecause all $a_j$ are positive integers, the recurrence $q_n=a_n{q}_{n-1}+q_{n-2}$ implies $q_n\to \infty$. Hence this separation tends to zero, and the squeeze theorem gives