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

If the positive odd integer $n$ has prime factorizationits Jacobi symbol iswhere each factor is a Legendre symbol; by convention $(a/1)=1$. Thus the symbol is zero exactly when $\gcd (a,n)>1$.

The quadratic reciprocity law for the Jacobi symbol says that for coprime positive odd integers $m,n$,To prove it, write $m={\prod }_i{p}_i^{e_i}$ and $n={\prod }_j{q}_j^{f_j}$. The quadratic reciprocity law for distinct odd primes statesMultiplying this identity over $i,j$ with multiplicities $e_i{f}_j$ gives the required product of Jacobi symbols. Its sign exponent modulo two isbecause multiplication of odd integers adds the quantities $(r-1)/2$ modulo two. This proves the law.

For the requested value, two applications of reciprocity givesince $2019\equiv 7(\mathrm{mod}503)$, $503\equiv 6(\mathrm{mod}7)$, and $6$ is a quadratic nonresidue modulo $7$.

The sum is nonempty because $A$ and $B$ are nonempty. It is a bounded set: if $|a|\le M_A$ and $|b|\le M_B$, then $|a+b|\le M_A+M_B$.

To prove that it is a closed set, let $x_j=a_j+b_j\in A+B$ be a convergent sequence with $x_j\to x$. By the Heine-Borel theorem, $A$ is a compact set, so $(a_j)$ has a convergent subsequence $a_{j_r}\to a\in A$. ThenSince $B$ is closed, $x-a\in B$, and hence $x=a+(x-a)\in A+B$. Therefore $A+B$ is nonempty, closed and bounded, so $A+B\in \mathcal{K}$.

Every $K_n$ is contained in the bounded set $K_1$, so the intersection $K={\bigcap }_{n\ge 1}{K}_n$ is bounded. It is closed because an arbitrary intersection of closed sets is closed.

It remains to prove that $K$ is nonempty. Choose $x_n\in K_n$. The set $K_1$ is a compact set, so some subsequence $x_{n_j}$ converges to a point $x\in K_1$. For each fixed $m$, all sufficiently late terms satisfy $n_j\ge m$ and hence $x_{n_j}\in K_{n_j}\subseteq K_m$. Since $K_m$ is closed, $x\in K_m$. This holds for every $m$, so $x\in K$. Thus $K\in \mathcal{K}$.

Because $K\subseteq K_n$, one of the two directed terms in the given Hausdorff distance vanishes, andSuppose this does not tend to zero. Then some $\epsilon >0$, a strictly increasing sequence $(n_j)$ and points $x_j\in K_{n_j}$ satisfyAll $x_j$ lie in the compact set $K_1$, so after passing to a subsequence, $x_j\to x$. For every fixed $m$, eventually $n_j\ge m$, so $x_j\in K_m$ and the closedness of $K_m$ gives $x\in K_m$. Hence $x\in K$, contradicting $|x_j-x|\to 0$. Therefore $\rho (K_n,K)\to 0$.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight

A recursive set $E\subseteq {\mathbb{N}}_0$ has an indicator function computed by a register machine that halts on every input. A recursively enumerable set is the exact halting set of some register machine; equivalently, it is the domain of a partial computable function.

If $E$ is recursive, its decider immediately gives machines that halt exactly on $E$ and on ${\mathbb{N}}_0\setminus E$, so both sets are recursively enumerable. Conversely, suppose machines $M_E$ and $M_{E^c}$ recognize the two sets. On input $x$, use dovetailing to run one step of $M_E(x)$ and one step of $M_{E^c}(x)$ alternately. Exactly one must eventually halt. Return one if $M_E$ halts first and zero if $M_{E^c}$ halts first. This is a total decider for $E$, so $E$ is recursive.

Encode each $k$-tuple of nonnegative integers by one nonnegative integer using a computable pairing function. Define a unary partial procedure $P$ on input $m$ as follows: use dovetailing on the computations of $f_{n,k}$ over all encoded $k$-tuples, and halt as soon as one of them halts with output $m$. ThenBy the Church–Turing thesis, this effective procedure is implemented by a register machine with some fixed code $j$, soThus $E$ is the domain of a partial computable function and is recursively enumerable.

The function is the predecessor function. It has the primitive recursion definitionThe initial function is the zero function and the recursion step is a projection function, both of which are primitive recursive functions. Closure under primitive recursion therefore proves that $f$ is primitive recursive.

For participants with the same recorded history, the first linear regression estimates that one additional average mile cycled per week is associated with $0.04917$ fewer asthma episodes. The corresponding $p$-value is $0.00761$, giving evidence against a zero conditional association.

The second model estimates that, among participants with the same history, receiving the incentive is associated with $0.91387$ more episodes. The third estimates that receiving the incentive is associated with $1.73282$ more miles cycled per week. Both incentive coefficients have very small p-values. Because the incentive was assigned in a randomized controlled trial, these last two comparisons estimate a causal effect of the incentive.

The first model alone would suggest that more cycling is beneficial, but cycling was not randomized in that model: its coefficient can be distorted by confounding or reverse causality. The randomized incentive both substantially increased cycling and substantially increased asthma episodes.

If the incentive affects asthma only through cycling, it is an instrumental variable, and the corresponding Wald estimator of the effect per additional weekly mile isadditional episodes. Under that exclusion assumption the evidence therefore advises against cycling to work more often for this population. Without the exclusion assumption, the experiment establishes the harmful effect of the incentive itself but cannot by itself distinguish an effect of cycling from a direct effect of the monetary incentive.

At a positive spatially homogeneous equilibrium,soThe Jacobian matrix of the reaction terms there isThe linear stability analysis of a two-dimensional system requires negative trace and positive determinant. Since $a>0$, the homogeneous equilibrium is stable exactly when

For a spatial Fourier mode proportional to $\cos (kx)$, put $q=k^2$. The linearized matrix isIts trace is still negative when $0<a<1$, whileA Turing instability occurs for some $q>0$ exactly when this quadratic has a negative minimum. This requiresWriting $d=\sqrt{D}$, the second inequality reduces to $d<a(\sqrt{2}-1)$. Hence, for continuously available wave numbers, the condition isOn a bounded spatial domain, one additionally requires an allowed wave number $k$ for which $\det J_{k^2}<0$.

Apply the residue theorem to the upper-half-plane semicircle, with a small semicircular indentation above the pole at $z=0$. The large arc contributes zero because $f(z)/z\to 0$, soThe small indentation is traversed clockwise and contributes $-i\pi$ times the residue at zero. The only pole strictly inside the indented contour is $z=ia$. ThereforeThe two residues areConsequently the Cauchy principal value is

For canonical position and momentum coordinates $(q_i,p_i)$, Hamilton's equations are

The Poisson bracket of two phase-space functions is

The canonical Poisson-bracket relations are

By the multivariable chain rule and Hamilton's equations,The sum is the Poisson bracket $\{f,H\}$, giving

Let $f$ and $g$ be conserved quantities, allowing explicit time dependence. ThenUsing bilinearity of the Poisson bracket, commutation of partial differentiation with it, and the Jacobi identity for the Poisson bracket,Thus $\{f,g\}$ is also conserved.

Differentiate the Friedmann equation $H^2=8\pi G\rho /3$ and use the continuity equation $\dot{\rho }=-3H(\rho +P)$:so $\dot{H}=-4\pi G(\rho +P)$. Since $H=\dot{a}/a$,Hence the Raychaudhuri equation is

For the equation of state $P=w\rho$ with positive energy density,The expansion is accelerated for $w<-1/3$, coasting for $w=-1/3$, and decelerated for $w>-1/3$.

At equality, let ${\rho }_{\mathrm{cc}}={\rho }_{\mathrm{dust}}={\rho }_{\ast }$. The cosmological constant has $P_{\mathrm{cc}}=-{\rho }_{\ast }$, while nonrelativistic matter has $P_{\mathrm{dust}}=0$. ThereforeThe scale factor consequently has $\ddot{a}>0$: the expansion is accelerated at $a=a_{\mathrm{eq}}$.

The cosmological constant energy is constant, whereas the matter density scales as $a^{-3}$. HenceThe transition occurs when $\rho +3P={\rho }_{\mathrm{dust}}-2{\rho }_{\mathrm{cc}}=0$, so

For each position $i$, Alice uses $y_i$ to choose a basis and $x_i$ to choose a vector in that basis. Explicitly, she sends the qubitThus $y_i=0$ uses the computational basis $\{|0⟩,|1⟩\}$, while $y_i=1$ uses the Hadamard basis $\{|+⟩,|-⟩\}$.

Alice sends the $m$ conjugate-coded qubits through the noiseless quantum channel. Bob independently chooses a uniformly random basis bit $y_i^{\prime }$ for each qubit and performs a projective measurement in the computational basis when $y_i^{\prime }=0$ or the Hadamard basis when $y_i^{\prime }=1$.

After all measurements, Alice and Bob publicly reveal $Y$ and $Y^{\prime }$ but keep the data bits secret. They discard every position with $y_i\ne y_i^{\prime }$ and retain the measured bits at positions where the bases agree. In the ideal channel those retained bits equal Alice's $x_i$ with certainty. Each pair of bases agrees with probability $1/2$, so the shared secret key has expected length $m/2$.

Condition on a position retained after basis reconciliation, so Bob used Alice's basis. If Eve does not intercept, no error occurs. If she intercepts, her uniformly chosen basis agrees with Alice's with probability $1/2$, again causing no error. With probability $1/2$ she uses the conjugate basis; her measurement and resent state then make Bob's bit uniformly random, giving an error with probability $1/2$.

Therefore the bit error rate in the retained key is

Read the $2n+1$ colours from left to right. If every neighbouring pair had the same colour, mathematical induction would make every point the same colour as $-1$, contradicting the different colour of $1$. Therefore at least one adjacent pair has different colours.

Suppose for a contradiction that $A\cap B=\varnothing$. Each grid point then belongs to exactly one of $A$ and $B$; colour it red in $A$ and green in $B$. By part (a), there are adjacent points $a_n\in A$ and $b_n\in B$, in either order, withThe interval $I$ is a compact set, so a subsequence of $(a_n)$ converges to some $x\in I$. Along the same subsequence $b_n\to x$. Since $A$ and $B$ are closed sets, $x\in A\cap B$, a contradiction. Hence $A\cap B\ne \varnothing$.

If such a continuous function existed, the inverse imageswould be closed, would cover $I$, and would contain $-1$ and $1$ respectively. Part (b) gives a point in $A\cap B$, which is impossible.

Suppose that the continuous function $f:I\to I$ has no fixed point. Then $g(x)=f(x)-x$ is continuous and never zero, sois a continuous function from $I$ to $\{-1,1\}$. Since $f(-1)\ge -1$ and equality would be a fixed point, $h(-1)=1$. Similarly $h(1)=-1$. Multiplying $h$ by $-1$ contradicts part (c). Thus $f$ has a fixed point.

Conversely, suppose a continuous $f:I\to \{-1,1\}$ satisfies $f(-1)=-1$ and $f(1)=1$. The function $g=-f:I\to I$ is continuous, so part (d) gives $x=g(x)=-f(x)$. If $f(x)=1$, this forces $x=-1$, contradicting $f(-1)=-1$; if $f(x)=-1$, it forces $x=1$, contradicting $f(1)=1$. Hence no such $f$ exists.

Suppose $I=A\cup B$, where $A$ and $B$ are disjoint closed sets with $-1\in A$ and $1\in B$. Since each is the complement of the other, both are also open in $I$. Define $f=-1$ on $A$ and $f=1$ on $B$. This locally constant function is continuous and contradicts part (c). Therefore $A\cap B\ne \varnothing$.

The conclusions of (b) and (c) remain true. Indeed, the unit circle is a path-connected space, and the upper semicircle supplies a path from $-1$ to $1$; restricting the proposed closed cover or two-valued continuous function to that path reduces either claim to the corresponding result on $I$.

The fixed-point conclusion (d) fails. For example, any nontrivial spatial rotation $f(z)=e^{i\theta }z$ of the unit circle has no fixed point when $e^{i\theta }\ne 1$; the antipodal map $f(z)=-z$ is the simplest example.

The binary Huffman coding algorithm repeatedly merges the two currently least probable symbols into one meta-symbol whose probability is their sum. After recursively constructing a code for the smaller alphabet, append $0$ and $1$ to the meta-symbol's codeword to obtain codewords for the merged pair. The result is a binary prefix code.

To prove optimality, begin with an optimal prefix-code tree. It may be taken to be full, since an internal vertex with one child can be suppressed and all codewords below it shortened. Two leaves of maximum depth are siblings. By exchanging labels, without changing lengths, assign two least probable symbols to such a sibling pair: moving a smaller probability to a no-shorter codeword cannot increase the expected length. Contracting this pair to one leaf replaces their contribution $p_i{\ell }_i+p_j{\ell }_j$ by $(p_i+p_j)({\ell }_i-1)$ plus the constant $p_i+p_j$. If the contracted code were not optimal for the reduced alphabet, replacing it by a better one and then expanding the merged leaf would improve the original code. Mathematical induction on the number of symbols now proves that the Huffman construction minimizes expected word length.

False. For probabilities $(0.4,0.2,0.2,0.1,0.1)$, first merge the two $0.1$ symbols. Subsequent ties allow Huffman trees with length multisets $(2,2,2,3,3)$ and $(1,3,3,3,3)$, both of expected length $2.2$.

False. For probabilities $(0.30,0.25,0.25,0.20)$, every length-two code is optimal. A code in which the $0.30$ and $0.20$ symbols are sibling leaves is optimal, but no Huffman construction produces that labelled tree, because its first merge must pair $0.20$ with a $0.25$ symbol.

True. The Huffman tree is a full binary tree, so its leaves form a complete prefix code. The Kraft inequality is therefore an equality:

Take the Hankel contour about the negative real axis: it starts at $-\infty$ just below the cut, circles the origin counterclockwise, and returns to $-\infty$ just above the cut. The notation $(0+)$ records this return side of the branch point. Choose the branch $-\pi <\arg t<\pi$ for $t^{z-1}$.

For $\mathrm{Re}z>1$, collapse the contour onto the two banks of the cut. Their phase difference is determined byand the resulting sine factor, together with the Gamma reflection formula $\Gamma (z)\Gamma (1-z)=\pi /\sin (\pi z)$, recovers the integral representation (‡). The Hankel integral converges exponentially at its unbounded end and, after the standard local subtraction of the singular part at zero, depends holomorphically on $z$. The apparent poles of $\Gamma (1-z)$ are cancelled by zeros of the contour integral except at $z=1$. It therefore gives the analytic continuation of the Riemann zeta function to $\mathbb{C}\setminus \{1\}$.

For $n\ne 0$, the denominator has derivativeHence the simple-pole residue is

Apply the Hankel representation with $z$ replaced by $1-z$:Enlarge $H$ to a modified Hankel contour that encloses the simple poles $t=2\pi in$, $n\in \mathbb{Z}\setminus \{0\}$. In a strip where the deformation and residue sum converge, the outer pieces vanish and the orientation gives the Hankel integral as minus $2\pi i$ times the sum of the enclosed residues. Part (b) givesSubstitution therefore yieldsBoth sides are meromorphic functions of $z$, so the identity theorem extends the equality from the initial strip to every point where either side is defined.