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

If $m$ and $n$ are coprime, every divisor of $mn$ is uniquely $ab$ with $a\mid m$ and $b\mid n$. Hence, for a multiplicative arithmetic function $f$,

The Möbius function is $\mu (n)=0$ if a prime square divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct primes. The Euler totient function $\varphi (n)$ counts residues modulo $n$ coprime to $n$. From the prime factorizations,Both sides of the second identity are multiplicative, and at a prime power $p^a$,Therefore

Directly,Thus take $\alpha =aC+A$, $\beta =aD+B$, $\gamma =C$, and $\delta =D$. They are nonnegative and

Each finite block of a continued fraction acts by a fractional linear transformation with an integral matrix of determinant $\pm 1$. If the block $a_1,\dots ,a_N$ repeats, removing one period leaves the same tail $x$, sofor integers $A,B,C,D$. Hence $C{x}^2+(D-A)x-B=0$, with the linear case allowed when $C=0$.

For period $(a,b)$,soThe continued fraction is positive, so it is the positive rootwhile the other root is negative.

For a $q$-ary code with codeword lengths $l_1,\dots ,l_m$, Kraft inequality isChoose an infinite random $q$-ary string with independent uniform symbols. The event that it begins with codeword $i$ has probability $q^{-l_i}$. For a prefix-free code, these events are disjoint, so their probabilities sum to at most one. This proves necessity.

If one comma codeword were a prefix of another, its terminal comma would occur inside the longer codeword, contrary to the definition. Thus every comma code is prefix-free. Directly, the disjoint cylinder sets of infinite strings beginning with the respective comma-terminated words have measures $q^{-l_i}$, so their total measure gives Kraft's inequality.

Kraft's inequality does not imply unique decipherability. Over the binary alphabet,has Kraft sum $1/2+1/4+1/4=1$, butThus it is not uniquely decipherable.

Fix an effective enumeration of register-machine programs. The $n$th register machine is $P_n$, and its domainis the $n$th recursively enumerable set. A many-one reduction $A{\le }_{m}B$ is a total computable function $h$ satisfying $x\in A⟺h(x)\in B$. Rice theorem says that every nontrivial property depending only on the computed partial function, or equivalently on an r.e. set in its extensional form, has an undecidable index set.

There is no total equality algorithm: it would decide whether $W_n$ is empty by comparing it with a fixed index for the empty set, contradicting Rice's theorem.

There is no partial algorithm that halts exactly when $W_m=W_n$ either. Given $e$, effectively construct an index $h(e)$ whose machine enumerates nothing unless $P_e(e)$ halts, after which it enumerates $0$. ThenA semialgorithm for equality with a fixed empty index would enumerate the complement of the halting problem $K$. Since $K$ is r.e., both it and its complement would then be r.e., making $K$ recursive, a contradiction.

For $Y_{\mu }\sim \mathrm{Poisson}(\mu )$, the delta method with $g(y)=2\sqrt{y}$ givesThus the transformation stabilizes variance at large $\mu$.

A Gaussian linear model for $\sqrt{Y}$ treats the transformed observations as having additive constant-variance errors and models $\mathbb{E}(\sqrt{Y}\mid X)$ as linear. A Poisson regression with square-root link retains the Poisson likelihood and modelsThe two procedures therefore have different likelihoods, fitted means, and constraints; transforming the response is not the same as transforming its conditional mean.

The positive fixed point satisfies $x_{\ast }=x_{\ast }{e}^{r(1-x_{\ast })}$, hence $x_{\ast }=1$. Put $x_n=1+u_n$ and retain first-order terms:Thuswith characteristic polynomial ${\lambda }^2-\lambda +r$.

The Jury stability criterion for ${\lambda }^2-\lambda +r$ gives both roots inside the unit disc exactly whenThe decay is monotone when both roots are real and positive. Since the discriminant is $1-4r$, this occurs for

For $1/4<r<1$, the roots are a complex-conjugate pair with modulus $\sqrt{r}<1$. The perturbation therefore changes sign or phase while its envelope decays:

At the stability boundary $r_{\ast }=1$, the characteristic roots areThey lie on the unit circle and satisfy ${\lambda }^6=1$, with no smaller positive common period. Hence

Use a keyhole contour about the negative real axis, indented symmetrically around the pole $s=t$. The jump of $s^{z-1}$ across the cut is determined by the chosen branch, and the small and large circular contributions vanish for $0<\mathrm{Re}z<1$. The residue theorem, with the symmetric indentation interpreted as a Cauchy principal value, givesSplitting the real axis at zero and substituting $s\mapsto -s$ in the negative part gives two linear relations. Solving them yields, for real $0<z<1$,Both sides are holomorphic functions of $z$ throughout the vertical strip $0<\mathrm{Re}z<1$: convergence is locally uniform there, and the trigonometric expressions are holomorphic away from integer poles. The identity theorem therefore extends the identities from real $z$ to the whole strip.

For a type-two generating function, comparewithThe coefficients give the canonical-transformation equations

Hamilton's equations givesoUseThenand $P_2=p_2-(n_2/n_1)p_1$ is the conserved combination. The transformed Hamiltonian depends on $Q_1$ but not $Q_2$. Thus $H$ and $P_2$ are two independent first integrals in involution for two degrees of freedom, proving Liouville integrability.

Chemical equilibrium for $p+e\leftrightarrow H$ givesand charge neutrality gives $n_p=n_e$. Insert the nonrelativistic Maxwell-Boltzmann number densities, use $m_H{c}^2=m_p{c}^2+m_e{c}^2-E_{\mathrm{bind}}$, and neglect the proton correction in the reduced mass. The spin degeneracies cancel in the ground-state approximation. One obtains Saha equationEquivalently, its reciprocal is the ionization ratio. The exponential favors neutral hydrogen as the temperature falls, while the translational phase-space factor favors ionization at high temperature.

The no-signalling theorem states that any trace-preserving quantum operation performed locally by Bob leaves Alice's reduced density matrix unchanged when Bob's outcome is not communicated:Thus Bob's choice cannot change the statistics of any measurement made by Alice.

A unitary cloner with blank state $|0⟩$ would satisfyfor every $|\psi ⟩\in S$. For $|\psi ⟩,|\varphi ⟩\in S$, preservation of inner products givesHence every pair is either orthogonal or represents the same state. Conversely, an orthonormal set can be cloned by defining the map on its basis states and extending it to a unitary. Therefore the no-cloning theorem says that a set of pure states is unitarily clonable exactly when its distinct members are mutually orthogonal.

Let Alice and Bob share the Bell stateAlice may measure in the computational basis, remotely preparing Bob's ensemble $\{|0⟩,|1⟩\}$, or in the Hadamard basis, preparing $\{|+⟩,|-⟩\}$. Without her outcome, both ensembles have density matrix $I/2$, as no-signalling requires.

If Bob could clone all four states, the resulting two-qubit ensembles would beandThey are distinguishable: a $Z\otimes Z$ measurement is perfectly correlated for the first and only equally likely correlated or anticorrelated for the second. Bob could infer Alice's basis choice instantaneously, violating no-signalling. Thus no-signalling implies no-cloning for this set.

A binary cyclic code of odd length $n$ is an ideal of ${\mathbb{F}}_2[X]/(X^n-1)$. For a primitive $n$th root $\alpha$, its defining set is the set of powers ${\alpha }^i$ at which every code polynomial vanishes. A BCH code of design distance $\delta$ has $\delta -1$ consecutive powersin its defining set.

If a nonzero codeword had weight $w<\delta$, write it as $c(X)={\sum }_{j=1}^w{c}_j{X}^{i_j}$. Evaluation at $w$ consecutive defining roots gives a homogeneous Vandermonde system in the nonzero values $c_j{\alpha }^{b{i}_j}$. Its determinant is nonzero because the support elements ${\alpha }^{i_j}$ are distinct. Thus every $c_j$ would vanish, a contradiction. This proves the BCH bound

The defining roots are $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$. Frobenius conjugacy gives the two binary cyclotomic classesHencewhile ${\alpha }^3$ has order five andThe generator is their least common multiple:

For received polynomial $r$, define the syndromes $S_j=r({\alpha }^j)$. If the error positions are $i_1,\dots ,i_{\nu }$, the error locator polynomial isIts roots are ${\alpha }^{-i_h}$, and its coefficients satisfy the Newton syndrome recurrences. For this design-distance-five code, bounded-distance decoding seeks degree at most two.

For $r(X)=1+X+X^7$, reduction using ${\alpha }^4=\alpha +1$ givesThe degree-two syndrome recurrence yieldsChecking the fifteen nonzero field elements shows that this polynomial has no root in ${\mathbb{F}}_{16}$. It therefore cannot be expressed as $(1-{\alpha }^{i}Z)(1-{\alpha }^{j}Z)$ for error positions $i,j$. The received word lies outside the code's two-error decoding radius, so the error positions cannot be determined uniquely by this decoder.

The primitive recursive functions are the smallest class containing zero, successor, and projections and closed under composition and primitive recursion. Addition is defined byand multiplication byThus both are primitive recursive directly from the definition. Inductively,is primitive recursive. For fixed $a$,so $E_a(n)=a^n$ is primitive recursive.

Encode $(x_0,\dots ,x_{k-1})$ by $2^{x_0}{3}^{x_1}\cdots p_k^{x_{k-1}}$. The exponent functions $M_{p_i}$ decode the coordinates. Thereforeis a primitive recursive one-number encoding of $F$; the finite product is built from the primitive recursive multiplication and exponentiation just established.

The Fibonacci function is primitive recursive. Encode the pair $(B(n),B(n+1))$ byStarting with $C(0)=3$, primitive recursion usingconstructs $C$, and $B(n)=M_2(C(n))$.

There is no universal exponential bound of the stated form. The primitive recursive functionexceeds $R^n$ for every fixed $R>0$ once $n$ is sufficiently large.

The first command counts missing values in every column: there are $177$ missing ages and $687$ missing cabin entries, with none in the other variables. The next command deletes Cabin. The final command replaces every missing age by the mean of the observed ages, using na.rm = TRUE so missing entries do not contaminate that mean.

The code fits a Bernoulli logistic-regression model. Conditionally on the covariates, the responses are independent withwhere the design includes the displayed numerical predictors and indicator columns for factor levels. It maximizesAkaike information criterion iswhere $k$ is the number of fitted parameters. Backward stepwise selection starts from the full model, tentatively removes each eligible term, chooses the removal producing the lowest AIC, and repeats while AIC decreases. It balances fit against model size rather than testing every coefficient at a fixed significance threshold.

The residual deviance per residual degree of freedom isreasonably close to one. The first and third quartiles of the deviance residuals, $-0.591$ and $0.621$, are also fairly close to the standard-normal quartiles $\pm 0.674$. There is mild evidence of underdispersion, but nothing in this summary makes the binomial value one plainly unreasonable.

A standard moment estimator is the Pearson dispersion estimatorFor Bernoulli data, $V(\mu )=\mu (1-\mu )$. The deviance divided by its residual degrees of freedom is a common alternative.

For fixed $s$, the factor $n^{-s}$ grows at most polynomially in $n$, whereas $|z{|}^n$ decays exponentially when $|z|<1$. The defining series for the polylogarithm therefore converges absolutely and locally uniformly for every complex $s$ and $|z|<1$. It is holomorphic in $z$ on the unit disc and entire in $s$ there.

For $|z|<1$ on the negative-real portions of the Hankel contour, expandLocal uniform convergence permits termwise integration. The reciprocal Hankel formula givesso $I(z,s)={\sum }_{n\ge 1}{z}^n/n^s={\mathrm{Li}}_s(z)$ initially on the disc.

For $z\notin [1,\infty )$, choose the contour around the negative axis so that it passes between zero and every pole satisfying $e^{-t}=z$. On compact subsets of the slit $z$-plane it can be chosen uniformly, and differentiation under the integral proves holomorphy. Deforming without crossing a pole gives a single-valued analytic continuation. Near the cut, the pole $t=-\log z$ lies on opposite sides of the two admissible contours; this is why the contour must pass it consistently.

When $s$ is a nonpositive integer, $t^{s-1}$ is meromorphic and the Hankel contour may be shrunk to a small circle about zero. The integral is then computed by the residue at zero. This givesThese also follow by repeatedly applying $zd/dz$ to the geometric series.

For real $s>0$, collapse the Hankel contour onto the negative axis and use the jump in the argument of $t^{s-1}$. The reflection formula for the gamma function yieldsso $K(z,s,t)=z{t}^{s-1}/[\Gamma (s)(e^t-z)]$. At positive integer $s$, the original Hankel expression is interpreted by analytic continuation: the pole of $\Gamma (1-s)$ cancels the corresponding zero of the contour integral.

When $z$ crosses the slit at $x>1$, the pole of the real-integral kernel at $t=\log x$ crosses the integration path. The two boundary values differ by $2\pi i$ times its residue. Since $d(e^t-z)/dt=x$ there, that residue is $(\log x{)}^{s-1}/\Gamma (s)$, giving the jump

The homogeneous part of the continuity equation gives $\dot{\bar{n}}+3H\bar{n}=0$. At first order,For the density contrast $\delta =\delta n/\bar{n}$, the background equation cancels the expansion terms, leaving

The homogeneous Euler equation removes the background force. Products of perturbations are second order, while differentiating the peculiar velocity inside the expanding flow produces the Hubble drag term. The first-order equation is therefore

Take the divergence of the linear Euler equation, use $\delta P=c_s^{2}m\bar{n}\delta$, and differentiate the continuity equation. Eliminating $\nabla \cdot \delta \mathbf{v}$ givesThe perturbed Poisson equation isThusHere $k_J$ is the comoving Jeans wavenumber.

Neglecting the pressure and self-gravity bracket leavesDuring radiation domination, $a(t)\propto t^{1/2}$ and $H=1/(2t)$, soConsequentlyMatter perturbations therefore grow only logarithmically while radiation dominates.

The Knaster-Tarski theorem says that the fixed points of a monotone self-map of a complete lattice form a complete lattice. In particular,For the first formula, let $a$ be the displayed meet. Monotonicity gives $f(a)\le f(x)\le x$ for every prefixed point $x$, hence $f(a)\le a$. Then $f(f(a))\le f(a)$, so $f(a)$ is itself prefixed; minimality of $a$ gives $a\le f(a)$. Thus $f(a)=a$. The dual argument gives the greatest fixed point. Applying the same construction above the join of any family of fixed points, and dually below its meet, supplies joins and meets within the fixed-point set.

A down-set contains every element below any of its members. Arbitrary unions and intersections of down-sets are down-sets. Thus the down-sets of $X$, ordered by inclusion, have joins given by unions and meets by intersections, so they form a complete lattice.

For the requested counterexample, takewith their usual orders. The set $X$ is a down-set in $Y$, while $Y$ is order-isomorphic to the down-set $[0,1/2]$ of $X$. They are not isomorphic because $Y$ has a greatest element and $X$ does not.

Let $f:X\to A\subseteq Y$ be an order isomorphism onto a down-set, and let $g:Y\to U=X\setminus B$ be an order isomorphism onto the complement of a down-set $B$. Define increasing down-setsThe order assumptions ensure inductively that each $D_n$ is a down-set. DefineThe usual Cantor-Schröder-Bernstein theorem orbit argument shows that these two pieces partition both domain and codomain bijectively: points generated from $B$ move forward through $f$, while every remaining point lies in $U$ and moves backward through $g$. Each branch preserves order. If $x\in D$ and $x^{\prime }<x$ then $x^{\prime }\in D$; hence the only mixed case has $x\notin D<x^{\prime }\in D$, and the initial/final-segment hypotheses put $h(x)<h(x^{\prime })$. Thus $h$ is an order isomorphism and

A proper $k$-coloring assigns one of $k$ colors to each vertex so adjacent vertices receive different colors. The chromatic number $\chi (G)$ is the least such $k$. Order the vertices arbitrarily and color greedily. At most $\Delta (G)$ colors are forbidden by previously colored neighbors, soEquality occurs for every possible maximum degree: use $K_1$ for $\Delta =0$, $K_2$ for $\Delta =1$, an odd cycle for $\Delta =2$, and $K_{\Delta +1}$ for every $\Delta \ge 3$.

A graph is $k$-connected when it has more than $k$ vertices and remains connected after deletion of fewer than $k$ vertices. In a noncomplete 3-connected graph, choose a vertex $v$ with two nonadjacent neighbors $a,b$. Since $G-\{a,b\}$ is connected, take a spanning tree rooted at $v$ and order its vertices so every vertex other than $v$ has a later tree neighbor. Color $a$ and $b$ first with the same color, then greedily color the other vertices in reverse tree order, leaving $v$ last. Every nonfinal vertex has one uncolored neighbor and therefore sees at most $\Delta -1$ colors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta -1$ colors occur. HenceThis is the relevant 3-connected case of Brooks' theorem.

Euler's formula for a connected plane graph is $|V|-|E|+|F|=2$. If the graph is triangle-free, every face has boundary length at least four, soEuler's formula then gives $|E|\le 2|V|-4$, so the average degree is less than four. There is a vertex of degree at most three. Delete it, color the remaining graph inductively with four colors, and restore it using a color absent from its at most three neighbors. Thus

The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colors in a proper coloring of edges, where incident edges receive distinct colors. Hall marriage theorem says a bipartite graph has a matching saturating one side exactly when $|N(S)|\ge |S|$ for every subset $S$ of that side.

In a 4-regular bipartite graph, the $4|S|$ edges leaving $S$ all enter $N(S)$, whose vertices can receive at most $4|N(S)|$ such edges. Hence Hall's condition holds and there is a perfect matching. Remove it and repeat in the resulting 3-, 2-, and 1-regular bipartite graphs. The four perfect matchings give a four-edge-coloring, while every vertex requires four distinct colors. Therefore

For roots $r_1,r_2,r_3$, the discriminant isand for $f=X^3+pX+q$,If $f$ is irreducible, its Galois group is transitive in $S_3$: it is $A_3\cong C_3$ when $\Delta$ is a square in $K$, and $S_3$ otherwise. If $f$ has one root in $K$ and an irreducible quadratic factor, the group is $C_2$; if it splits, it is trivial. A repeated-root depressed cubic already has all roots in $K$, so adds no case.

For $X^3+3X+1$, the rational-root test proves irreducibility andis not a rational square. Thus $G\cong S_3$. By the fundamental theorem of Galois theory, the complete subfield list iswhere the three cubic fields fix the three order-two subgroups and the quadratic field fixes $A_3$.

If $L/K$ is Galois, form the norm polynomialThe Galois group permutes the factors, so $F\in K[X]$. Since the identity factor is $f$, taking $g=F/f\in L[X]$ proves the claim.

If $L/K$ is merely finite separable, place it in a finite Galois closure $M/K$ and use the same product over $\mathrm{Gal}(M/K)$. It gives $F\in K[X]$ divisible by $f$ in $M[X]$. Polynomial division of $F$ by $f$ uses only coefficients in $L$, and the remainder is zero, so the quotient $g=F/f$ actually lies in $L[X]$. It is nonzero and satisfies $fg=F\in K[X]$.