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)$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

The statement is 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$.

Solved by gpt-5.6-sol high.

The statement is 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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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}$.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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⟩$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.

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$.

Solved by gpt-5.6-sol high.

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.

Solved by gpt-5.6-sol high.