Past exam of the mathematics course of the University of Cambridge / 2025 / ii

Starting at $r=\lceil \sqrt{14351}\rceil =120$, one immediately findsTherefore

Since $N=3p$, its nontrivial difference-of-squares representation isAs $p$ is prime, every earlier square difference would give another nontrivial factorization, which is impossible. Thus the first successful value is $r=(p+3)/2$, and

Liouville approximation theorem states that if an irrational algebraic number $\alpha$ has degree $d\ge 2$, then some $C(\alpha )>0$ satisfiesfor every rational $p/q$ with $q>0$.

The omitted $n=0$ term is rational and does not affect transcendence. LetThe decimal expansion has ones at the increasingly separated positions $n^n$ and zeros elsewhere, so it is not eventually periodic and $\xi$ is irrational. Moreover,For every fixed $d$, the exponent $(N+1{)}^{N+1}$ eventually exceeds $d{N}^N$ by an arbitrarily large amount, so this upper bound is smaller than $C{q}_N^{-d}$. Liouville's theorem therefore rules out every finite algebraic degree, proving that $\xi$ is transcendental.

There are only countably many integer polynomials and each has finitely many roots, so the algebraic numbers are countable. Since $\mathbb{R}$ is uncountable, its complement, the set of transcendental numbers, is uncountable.

For a binary prefix code with word lengths $l_1,\dots ,l_m$, choose $L\ge \max l_i$. Each codeword is the prefix of exactly $2^{L-l_i}$ words of length $L$, and these descendant sets are disjoint. HenceThis is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

For Shannon--Fano coding, order symbols by probability and assignKraft's inequality applies because $2^{-l_i}\le p_i$ and therefore ${\sum }_i{2}^{-l_i}\le 1$. Thus codewords of those lengths exist. Sincethe expected length obeys

The closure table is

For the context-free intersection failure, takeBoth are context-free, but $L_1\cap L_2=\{a^n{b}^n{c}^n:n\ge 0\}$ is not. If context-free languages were also closed under complement, their closure under union and De Morgan's law would imply closure under intersection, so complement closure also fails. Finally, the halting set is computably enumerable but its complement is not, disproving complement closure for computably enumerable languages.

The change of variable $x=(y/\lambda {)}^k$ has derivative $kx/y$, soFor fixed $k$ this isThus the sample's sufficient statistic is $T={\sum }_i{Y}_i^k$.

Since $(Y/\lambda {)}^k\sim \mathrm{Exp}(1)$,The log likelihood, up to constants, is $-kn\log \lambda -T/{\lambda }^k$. Differentiating gives the unique maximum

The $\beta YN$ interaction converts supporters into opponents. The $\alpha YN$ interaction converts opponents into undecided people, while $\zeta U$ converts undecided people into opponents. Summing the three equations gives $(Y+N+U{)}^{\prime }=0$, as required for a fixed population.

Let the conserved population be $S>0$. At equilibrium $Y^{\prime }=-\beta YN=0$, so $Y$ and $N$ cannot both be positive. The other equations then force $U=0$. The only equilibria are

Near $E_Y$, using $(N,U)$ as coordinates gives the linearizationIts determinant is $-\beta S\zeta <0$, so $E_Y$ is a saddle and is unstable. Near $E_N$, coordinates $(Y,U)$ give the triangular linearization with eigenvalues $-\beta S$ and $-\zeta$. Hence $E_N$ is asymptotically stable.

No positive parameter choices can make everyone eventually favour the proposition for every initial condition. The all-opposed state $E_N$ is itself an equilibrium, and part (b) shows that an entire neighborhood is attracted to it. Thus initial conditions in that neighborhood cannot converge to $E_Y$.

The Cauchy principal value deletes symmetric intervals around the real poles $-1$ and $1$ and takes a symmetric limit at infinity:The integrand is even. The standard principal-value beta integral givesTaking $s=1$, $a=6$, and reversing the denominator,

The Lagrangian isWriting $T=2m+M$, the center of mass isAll internal forces cancel, so $\ddot{Y}=-g$ andIf the molecule is released from rest, the middle term vanishes.

Since $y_1=(Q_s+Q_a)/2$, $y_3=(Q_s-Q_a)/2$, elimination of the middle coordinate by the center of mass givesAfter substitution,The antisymmetric coordinate is decoupled. Its Euler--Lagrange equation is

Successive radial wave crests travel the same fixed comoving distance, soTo first order, $\delta t_0/a(t_0)=\delta t_e/a(t_e)$. Since wavelength is proportional to the period,

Each photon loses a factor $(1+z{)}^{-1}$ in energy, and cosmological time dilation reduces the photon arrival rate by another factor $(1+z{)}^{-1}$. Henceso $n=2$. The physical area of the sphere today is $4\pi a(t_0{)}^2{x}^2$, giving flux

Immediately before the final Hadamard, the state isThe outcome-one component after that Hadamard is $(|\psi ⟩+iU|\psi ⟩)/2$. Thus, with $z=⟨\psi |U|\psi ⟩$,

For every product vector,Product vectors span the two-register state space, so the single $A\otimes B$ gate equals parallel application of $A$ to the first register and $B$ to the second. Unitarity guarantees that both descriptions are valid quantum circuits.

Both $Z\otimes Z$ and $X\otimes I$ are unitary and Hermitian, so their expectations are real. Run the real-part Hadamard test twice, once with controlled $Z\otimes Z$ and once with controlled $X\otimes I$. If the respective ancilla outcome-one probabilities are $p_{ZZ}$ and $p_{XI}$, thenThe identity in part (b) implements each controlled tensor product by gates on its two target wires with the common control. By linearity,

Huffman's algorithm repeatedly merges the two least probable current symbols, labels the two new edges $0,1$, and replaces the pair by a compound symbol whose probability is their sum. Reading paths from the final root gives a prefix code.

For optimality, first observe that in some optimal full binary tree the two least probable symbols are sibling leaves at maximum depth: exchange them with any deepest sibling pair, putting the smaller probabilities at no smaller depths, without increasing expected length. Contract that sibling pair to one symbol of combined probability. The original expected length equals the contracted tree's expected length plus the pair's combined probability. Induction on the alphabet size now proves that choosing the two least probabilities and recursing is optimal, which is precisely Huffman's algorithm.

If a symbol has length one, it must be $a_1$. At the three-weight stage, the other two weights $x,y$ must be merged while $p_1$ survives, so $x,y\le p_1$. Thus $1-p_1=x+y\le 2p_1$, proving $p_1\ge 1/3$. Therefore $p_1<1/3$ forces every length to be at least two.

For the other bound, suppose $p_1$ is first merged at the three-weight stage, with weights $p_1,q,r$, where $q\le p_1\le r$. The preceding merge created $r=x+y$ from two weights no larger than the surviving $q$, so $r\le 2q$. Since also $r\ge p_1$, we have $q\ge p_1/2$, and henceThus this can happen only when $p_1\le 2/5$. If $p_1>2/5$, it survives until the final merge and receives a length-one word. At equality, ties can support either tree shape.

For code (a), takeHuffman merging produces lengths $(1,2,3,3)$ and expected length $2$.

For the same distribution $(2/5,1/5,1/5,1/5)$, the balanced code has every length equal to two and hence expected length $2$. Part (a) exhibited a Huffman code with that same expected length, so the balanced code is also optimal. Thus both listed codes are optimal for this distribution, after assigning their words in nondecreasing length order to nonincreasing probabilities.

For $C,D\subseteq \mathbb{B}$, one writes $C{\le }_{m}D$ if there is a total computable function $f:\mathbb{B}\to \mathbb{B}$ such thatfor every $x$. This is a computable many-one reduction.

One writes $C{\equiv }_{m}D$ when both $C{\le }_{m}D$ and $D{\le }_{m}C$.

Fix an effective coding of machines and write $W_w$ for the computably enumerable language recognized by code $w$. A set $I$ of codes is an index set when membership depends only on the recognized language:It is nontrivial when it is neither empty nor all of $\mathbb{B}$.

Let $K=\{w:w\in W_w\}$ and let $e_{\varnothing }$ be any index for the empty language. The proof of Rice theorem givesIn either case choose a language on the opposite side of the nontrivial property and switch from the empty enumerator to its enumerator if the simulated diagonal computation halts.

The empty language belongs to $\mathbf{Emp}$, so the second case applies:It does not belong to $\mathbf{Inf}$, so the first case applies:

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.

Since the empty language does not lie inRice's construction gives $K{\le }_m\mathbf{Two}$. Conversely, $\mathbf{Two}$ is computably enumerable: dovetail the enumerator for $W_w$ until two distinct words appear, then accept. The diagonal halting set $K$ is many-one complete for computably enumerable sets, so $\mathbf{Two}{\le }_{m}K$. Therefore

For $K{\le }_m\mathbf{Cof}$, map $x$ to a machine that initially enumerates nothing and, if the simulation establishing $x\in K$ halts, enumerates every word. Its language is cofinite exactly when $x\in K$.

For $\mathbb{B}\setminus K{\le }_m\mathbf{Cof}$, map $x$ to a machine that enumerates successively longer finite initial segments of $\mathbb{B}$ while simulating $x$. If the simulation never halts, every word is eventually enumerated; if it halts, enumeration stops with a finite language and therefore an infinite complement. Thus the constructed language is cofinite exactly when $x\notin K$.

The parameter theorem makes both code transformations total and computable.

Conditionally on $X$, the log likelihood differs fromonly by terms independent of $\beta$. Differentiation gives the weighted normal equationsand therefore

Dividing row $i$ of both $Y$ and $X$ by $\sqrt{v(X_i)}$ transforms the model to one with covariance ${\sigma }^{2}I$. Ordinary least squares without an intercept on these transformed data is exactly the estimator in part (a). In R, the unweighted estimator is returned by

R
fit2 <- lm(Y ~ X - 1)
fit2$coefficients

Write $Y_i=X_i^T\beta +{\epsilon }_i$, where conditionally $\mathbb{E}({\epsilon }_i|X_i)=0$ and $\mathrm{Var}({\epsilon }_i|X_i)={\sigma }^{2}v(X_i)$. ThenThe law of large numbers sends the matrix towhile the vector tends to zero, proving consistency. The central limit theorem and Slutsky's theorem give

Similarly, with $B=\mathbb{E}(X{X}^T)$ and $C=\mathbb{E}(v(X)X{X}^T)$,These conclusions require the displayed matrices to be finite and nonsingular.

For $p=1$, part (c) givesConsequently

Weighted least squares uses the known conditional variances and should be at least as efficient, so $\rho \le 1$. Indeed, apply Cauchy--Schwarz toIt giveswhich is exactly $\rho \le 1$. Equality holds precisely when $v(X_1)$ is constant on the part of the support where $X_1\ne 0$, up to null sets.

Use the Hankel contour about the negative real axis: it starts at $-\infty$ below the cut, circles the origin counterclockwise, and returns to $-\infty$ above the cut. Take $-\pi <\arg t<\pi$. For $\mathrm{Re}s>0$, the small circle vanishes and the two banks giveThe gamma reflection formula then gives

Near zero,Subtracting any desired number of these terms makes the local contour integral converge in successively larger left half-planes. The resulting apparent singularities are removable after multiplication by $\Gamma (1-s)$, so the Hankel formula analytically continues $\beta$ to all $s\in \mathbb{C}$.

At a nonpositive integer, the branch disappears and the collapsed Hankel contour extracts the residue at zero. For $s=0$,For $s=-2$, the coefficient of $t^{-1}$ inis $-1/4$; multiplication by $\Gamma (3)=2$ givesWhen $s=-2n-1$, the integrand is $t^{-2n-2}$ times an even power series, so it has no $t^{-1}$ coefficient. Hence

The nonzero poles areTheir paired residues sum toThe paired series converges for $\mathrm{Re}s<1$ by the alternating-series test, and absolutely for $\mathrm{Re}s<0$. ThereforeUsing the stated contour closure, the Hankel integral is $-2\pi i$ times this sum. Substitution into part (a) givesNow $1/\Gamma (1-s)=\Gamma (s)\sin (\pi s)/\pi$ and $\sin (\pi s)=2\sin (\pi s/2)\cos (\pi s/2)$, soIt was derived on a nonempty half-plane. Both sides have analytic continuations, with the apparent gamma poles cancelled by the sine factor or the trivial zeros from part (b); the identity theorem therefore extends it to every $s\in \mathbb{C}$.

At fixed time and angles, proper radial distance isThusThese are respectively flat Euclidean, positively curved spherical, and negatively curved hyperbolic spatial geometries.

Define conformal time by $d\tau =dt/a(t)$. The radial coordinate and the angular-radius function areSubstitution yields the stated conformal metric. A radial null ray satisfiesso $d\chi /d\tau =\pm c$ and $\chi ={\chi }_0\pm c(\tau -{\tau }_0)$.

With $P=-2\rho /3$, the continuity equation becomeshence $\rho a$ is constant. Since $a(t_0)=1$, one has $\rho ={\rho }_0/a$. The Friedmann equation is thereforewhere

The expanding branch obeysIntegrating from $a=0$ at $t=0$ givesSolving for $a$,

Setting $a(t_0)=1$ givesAt the present epoch,soFor $\beta \gg \gamma$, this tends to $1$, giving $t_0\sim H_0^{-1}$. For $\gamma \gg \beta$, it tends to $2$, giving $t_0\sim 2H_0^{-1}$.

From the explicit solution, $\ddot{a}=\gamma /2$. Since $a(t_0)=1$ and $\dot{a}(t_0{)}^2=\beta +\gamma$,Because an open universe has $\beta >0$, this is strictly greater than $-1/2$. It approaches $-1/2$ only in the zero-curvature limit, so this model cannot attain $q_0\le -0.5$ for the permitted parameters and therefore cannot reproduce $q_0\approx -0.55$.

For a well-order $(A,r)$, define recursivelyTransfinite recursion makes $F$ an isomorphism from $(A,r)$ onto a transitive set of transitive sets, hence onto an ordinal. If two ordinals were isomorphic, the first point where the isomorphism differed from the identity would contradict preservation of their initial segments. Thus this ordinal is unique.