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

The Möbius function isMöbius inversion says thatNowis the sum of $(-1{)}^{|S|}$ over subsets of the primes whose $k$th powers divide $n$. It is one if there are no such primes and zero otherwise, proving the power-free criterion.

LetGrouping all $n$th roots of unity by their exact order givesMöbius inversion therefore yields $c_n=\mu (n)$.

For each degree and coefficient bound there are finitely many integer polynomials. Hence $\mathbb{Z}[x]$ is countable. Every nonzero polynomial has finitely many roots, and every algebraic number is a root of one of these polynomials. A countable union of finite sets is countable.

Choose a subsequence $a_{n_j}$ so sparse thatfor every $j$; this is possible because the tails of the convergent positive series tend to zero. Distinct binary sequences $({\epsilon }_j)$ then have distinct sums ${\sum }_j{\epsilon }_j{a}_{n_j}$: at their first disagreement, the corresponding term exceeds the entire remaining tail. Thus these subsums form an uncountable set. The algebraic numbers are countable, so at least one subsum is transcendental. Set ${\theta }_{n_j}={\epsilon }_j$ and all other ${\theta }_n=0$.

Letand suppose $x=p/q$. Choose $n\ge \max (q,2)$ such that some ${\theta }_j=1$ for $j>n$. Then $n!x$ is an integer, while its first $n$ terms also sum to an integer. Their difference is strictly positive and satisfiesThis cannot be the difference of two integers, so $x$ is irrational.

Because decryption determines $M$ from $(C,K)$,The chain rule and monotonicity give

The unicity distance is the least ciphertext length for which the key is determined, or in the usual approximation the length at which the expected number of spurious keys falls to about zero. Assume equiprobable keys, a stationary plaintext source of information entropy rate $H_E$, and ciphertext symbols that are approximately uniform on $A$. The language redundancy per symbol isThe key equivocation is then approximated byHence the classical closed-form estimate is

Entropy is nonnegative. Gibbs' inequality also givesDivide by $n$ and pass to the assumed limit to obtain

A homomorphism $f:D\to D^{\prime }$ is a map $f:Q\to Q^{\prime }$ satisfyingfor every state $q$ and symbol $a$, together with

Induction on word length givesThe final-state condition then says that the state reached by $D$ is accepting exactly when the state reached by $D^{\prime }$ is accepting. Therefore $w\in \mathcal{L}(D)$ exactly when $w\in \mathcal{L}(D^{\prime })$, and the languages are equal.

False. Given any $D$, adjoin arbitrarily many unreachable states whose transitions remain among those new states, choosing their accepting status consistently away from the embedded copy. This produces infinitely many pairwise nonisomorphic finite deterministic automata $D^{\prime }$ containing an injective homomorphic copy of $D$.

True. In fact any fixed finite $D$ works. If $D^{\prime }\le D$, then $D^{\prime }$ has at most $|Q|$ states. For a fixed finite alphabet, there are only finitely many transition tables, initial states, and accepting subsets on at most $|Q|$ labelled states, hence only finitely many isomorphism classes.

Conditionally on $x_i$,Thus this is a probit regression with linear predictorFit $(\alpha ,\gamma )$ by maximum likelihood for Bernoulli observations, then recover

Write ${\tilde{x}}_{\ast }=(1,x_{\ast }^T{)}^T$, $\hat{\vartheta }=(\hat{\alpha },{\hat{\gamma }}^T{)}^T$, and let $\hat{V}$ estimate the asymptotic covariance of $\hat{\vartheta }$. ThenAn asymptotic confidence interval for the mean binary response $p_{\ast }=\Phi ({\eta }_{\ast })$ is

Of the $a_t$ immature cells, a fraction $\lambda$ leaves by maturation and the rest remains immature. Of the $b_t$ mature cells, a fraction $\mu$ divides and is replaced by four immature cells, while a fraction $k$ dies; the remainder stays mature. These contributions give exactly

Once a cell is mature, its eventual competing outcomes are division and death. Conditional on one of them occurring, division has probability $\mu /(\mu +k)$ and creates four immature offspring. Thus the expected lifetime offspring number isassuming maturation eventually occurs.

Let $N_t=a_t+b_t$. Adding the two recurrences givesSince $b_t\ge 0$, total population can increase only if $3\mu >k$. This is exactlyso the population-growth and offspring criteria agree.

For $t\ge T$, set $\lambda =0$. Mature cells then decay geometrically:while their divisions add $4\mu b_{T+j}$ to the permanently immature population. If $\mu +k>0$, mature cells disappear andIf $\mu =k=0$, no further change occurs and the limit is $a_T+b_T$.

For $w^{\prime \prime }+P(z)w^{\prime }+Q(z)w=0$, a finite point $z_0$ is regular singular whenextend analytically to $z_0$. Inspection shows that $a,b,c$ satisfy these conditions. There are no other finite singularities; with the Fuchs relation on the six exponents, the point at infinity is ordinary in the corresponding sphere description.

At $z=a$, insert $w\sim (z-a{)}^r$. The coefficient of the most singular power gives the indicial equationThus the two local exponents are $\alpha ,{\alpha }^{\prime }$. Cyclically, the exponents at $b$ are $\beta ,{\beta }^{\prime }$ and those at $c$ are $\gamma ,{\gamma }^{\prime }$. The assumed nonintegral exponent differences give two independent Frobenius solutions without logarithmic resonance at each point.

The Papperitz symbol isIt records the three regular singular points and the two characteristic exponents at each.

Set $a=0$, $b=1$, $c=\infty$, $\alpha =\beta =0$. Comparing the $w^{\prime }$ coefficient givesand comparison of the $w$ coefficient gives the exponents $A,B$ at infinity. Hence

The phase space of an $n$-degree-of-freedom mechanical system is the $2n$-dimensional space of canonical positions and momenta $(q_1,\dots ,q_n,p_1,\dots ,p_n)$, geometrically the cotangent bundle of configuration space. A point specifies a complete instantaneous state.

For the canonical Poisson bracket,Hamilton's equations areMore generally $\dot{f}=\{f,H\}+\partial f/\partial t$.

With $H=p_j{p}_j/(2m)$, the stated brackets giveandThus $m\ddot{\mathbf{q}}=e\dot{\mathbf{q}}\times \mathbf{B}$, the Lorentz-force equation with zero electric field. The magnetic interaction has been moved from the Hamiltonian into the noncanonical symplectic structure.

From $E=\rho V$, $P=\rho /3$, and $dE=T,dS-P,dV$,Using $\rho =4\sigma T^4/c$ givesThereforeup to an irrelevant additive entropy constant.

When $\Gamma \gg H$, reactions maintain thermal and chemical equilibrium, so the expansion is quasistatic and adiabatic. With no change in the equilibrium degrees of freedom, comoving entropy and photon number are conserved. Sinceone gets $T^3{a}^3=\text{constant}$ and hence $T\propto a^{-1}$.

Before electron-positron annihilation, the electromagnetic plasma haswhereas afterward only the two photon polarizations remain, so $g_{\ast s}=2$. Entropy conservation in the decoupled electromagnetic sector givesNeutrinos receive none of this entropy and continue cooling as $T_{\nu }\propto a^{-1}$. Therefore

Write $|{\Phi }^{+}⟩=2^{-1/2}{\sum }_{j=0}^1|j⟩|j⟩$. Then

Sinceapplication of $X$ gives $\cos \theta |0⟩-\sin \theta |1⟩$, and subsequent application of $Z$ givesThus $ZX|{\psi }_2⟩=|{\psi }_1⟩$.

The matrix $U_{\theta }$ is real orthogonal. Part (a) givesExpanding the left side in the computational basis yields

Using the decomposition from part (ii), $U_{\theta }^{-1}$ maps Alice's $|{\psi }_1⟩$ to $|0⟩$ and $|{\psi }_2⟩$ to $|1⟩$. Alice obtains $0$ or $1$, each with probability $1/2$. Conditional on outcome $0$, Bob has $|{\psi }_1⟩$; conditional on outcome $1$, Bob has $|{\psi }_2⟩$.

Alice performs the operation and measurement from part (iii) and sends the one-bit outcome to Bob. If the bit is $0$, Bob does nothing. If it is $1$, Bob applies $ZX$, which maps $|{\psi }_2⟩$ to $|{\psi }_1⟩$ by part (i). In either case Bob finishes with the known target state $|{\psi }_1⟩$, using one shared Bell pair and one classical bit.

Setand recursivelyThen $p_n/q_n=[a_0,ldots,a_n]$. The determinant identityfollows by induction. Writing the remaining complete quotient as ${\theta }_{n+1}>1$ givesso $\theta$ lies strictly between consecutive convergents and their order alternates. For odd $n$,Moreover $|\theta -p_n/q_n|<1/(q_n{q}_{n+1})$, and $q_n\to \infty$, proving convergence.

The continued-fraction algorithm gives

The convergents beginSincea strictly positive solution is $(x,y)=(8,3)$.

Reducing $x^2-7y^2=-1$ modulo seven gives $x^2\equiv -1\equiv 6(\mathrm{mod}7)$. The quadratic residues modulo seven are $0,1,2,4$, so no solution exists.

Reducing $x^2-7y^2=5$ modulo seven gives $x^2\equiv 5(\mathrm{mod}7)$, again impossible because five is not a quadratic residue modulo seven.

The denominators of the convergents areThey increase strictly from $q_2$ onward, and none equals $13$. Equivalently, $34/13=[2;1,1,1,1,2]$, which ceases to agree with $[2;\overline{1,1,1,4}]$ after the third partial quotient. Hence there is no positive index $x$ with $p_x/q_x=34/13$.

Moving from $A_1$ to $A_n$, the colour changes an odd number of times because the endpoints have opposite colours: every change toggles the current colour, while every nonchange preserves it. Formally, encode red and green by zero and one; the sum modulo two of adjacent differences is the endpoint difference, which is one.

Count red-green segments modulo two. On $DE$, part (a) says their number is odd; the other two outer sides contain no red-green segment. Every interior segment belongs to two small triangles and therefore contributes zero modulo two, while each boundary segment belongs to one. Thus the sum, over all small triangles, of their numbers of red-green edges is odd.

A triangle with all three colours has exactly one red-green edge. A triangle using only red and green has zero or two, and any other nontrichromatic triangle has zero red-green edges. Hence the parity sum counts precisely the trichromatic triangles modulo two, proving that their number is odd.

Not necessarily, once the subdivision has at least two segments per side. Colour $D,E,F$ red, green, blue respectively and colour every other grid vertex red. No small triangle contains both exceptional vertices $E$ and $F$, and every small triangle therefore uses at most two colours. For the unsubdivided triangle the assertion is of course true.

False. The constant map to $E$ satisfies it: $E\in I$ and also $E\in J\subset J\cup K$.

True. At the vertices the side conditions forceOn each side, $g$ remains in that same side, so the boundary restriction is homotopic within the boundary to the identity and has degree one. If it extended continuously over the filled triangle with image in the boundary circle, that degree-one boundary map would be null-homotopic, which is impossible. Equivalently, a sufficiently fine simplicial approximation would contradict the parity form of Sperner's lemma proved in part (b).