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

Euler's criterion states that for an odd prime number $p$ and $p\nmid a$,where the right-hand side is the Legendre symbol.

Let $g$ be a primitive root modulo $p$. Its multiplicative order is $p-1$, so $g^{(p-1)/2}\ne 1$. This power has square $g^{p-1}=1$, and the only roots of $X^2-1$ modulo the odd prime $p$ are $\pm 1$. ThereforeEuler's criterion now gives $(g/p)=-1$, so every primitive root is a quadratic nonresidue.

Now let $p=2^{2^k}+1$ be a Fermat prime, with $k\ge 1$. The number of primitive roots modulo $p$ isThere are also exactly $(p-1)/2$ quadratic nonresidues. Since every primitive root is a nonresidue, these equally large sets coincide. Thus every quadratic nonresidue modulo $p$ is a primitive root, as summarized by Quadratic nonresidues modulo a Fermat prime.

Finally, $p\equiv 1(\mathrm{mod}4)$ and $p\equiv 2(\mathrm{mod}3)$. Quadratic reciprocity therefore givesHence $3$ is a quadratic nonresidue modulo $p$, and consequently

The set $K\cap P$ is compact because $K$ is closed and bounded, and the productis continuous. By the extreme value theorem, $G$ has a maximizer. Since $K$ meets the interior of the nonnegative orthant $P$, some feasible product is positive, so every maximizer lies in $\mathrm{Int}P$.

On $\mathrm{Int}P$, maximizing $G$ is equivalent to maximizingThe Hessian of $F$ iswhich is negative definite. Thus $F$ is a strictly concave function, and it has at most one maximizer on the convex set $K\cap P$. Denote this unique point by $x^{\ast }$.

For any $x\in K\cap P$, the line segmentlies in $K\cap \mathrm{Int}P$. Since $F(x(t))$ is maximal at $t=0$, its right derivative there is nonpositive:ThereforeThis is the supporting inequality for the product maximizer on a compact convex subset of the positive orthant.

Suppose now that $K$ is invariant under cyclic coordinate permutation. That permutation preserves the product, so uniqueness forces it to fix $x^{\ast }$. Hencefor some $r>0$. More explicitly,Indeed, cyclic symmetry averaging puts the diagonal point with coordinate equal to the mean of any $x\in K$ back in $K$, while the preceding inequality with $x_j^{\ast }=r$ gives ${\sum }_j{x}_j\le nr$.

Finally, given $a=(a_1,\dots ,a_n)\in \mathrm{Int}P$, defineThis set is nonempty, closed, convex and bounded, and it contains $a$. By the arithmetic-geometric mean inequality,Equality holds only when all $x_j/a_j$ are equal and their sum is $n$, namely only at $x=a$. Thus this $K$ has

For a binary block code, $n$ is the common length of its codewords, $m=|C|$ is the number of codewords, andis its minimum Hamming distance.

The parity extension isEvery extended word has even Hamming weight. The distance between two words increases by one exactly when their original distance is odd, so

Fix a coordinate, say the last one. The punctured code isDeleting one coordinate lowers each pairwise distance by at most one. Thus, when $d\ge 2$, no two words merge andIn guaranteed-distance notation this is recorded as an $[n-1,m,d-1]$ code. If $d=1$, puncturing a coordinate on which a distance-one pair differs can merge words, so its exact size must then be stated separately.

For a chosen coordinate and symbol $\epsilon \in \{0,1\}$, the shortened code retains the words having that symbol in the chosen coordinate and then deletes that coordinate. For the last coordinate,At least one of the two coordinate fibres contains at least $\lceil m/2\rceil$ words. Choose that fibre and, if necessary, discard surplus words. Because all retained words agree in the deleted coordinate, their mutual distances do not change. Hence one can always obtainWithout discarding words, its size is that of the chosen fibre and its minimum distance is at least $d$.

For the final calculation, the given code is the whole space ${\mathbb{F}}_2^3$, so its parity extension is the length-four even-weight binary code. In a binary symmetric channel, parity fails to notice a nonzero error exactly when an even number of bits flips. The possible error weights are therefore two and four. Their total probability isThis excludes the weight-zero event, since it is not an undetected error.

For the given effective enumeration of partial computable functions, the diagonal halting set is

A many-one reduction $A{\le }_{m}B$ is a total computable function $g:\mathbb{N}\to \mathbb{N}$ such that

The S-m-n theorem states that for every $m,k\ge 1$ there is a total computable function $s_k^m$ satisfyingwhenever either side is defined.

Suppose first that $X$ is recursively enumerable. Choose a program that halts exactly on inputs in $X$, and let $e$ index a two-variable program that, on $(x,y)$, ignores $y$ and runs that program on $x$. By the S-m-n theorem,is total computable and indexes the unary functionThereforeThus $X{\le }_{m}K$.

Conversely, suppose $X{\le }_{m}K$ through a total computable $g$. On input $x$, compute $g(x)$ and simulate machine $g(x)$ on its own code. This procedure halts exactly when $g(x)\in K$, equivalently exactly when $x\in X$. Hence $X$ is recursively enumerable. We have proved the many-one completeness of the halting problem:

Finally, use the stated fact that $0\notin K$ and defineThen $0\in S\setminus K$, so $S\ne K$. The total computable map $n\mapsto 2n+1$ satisfiesand therefore $K{\le }_{m}S$. This is a distinct representative of the halting many-one degree.

Expand the exponent in the Inverse Gaussian distribution with unit shape parameter:Consequently its probability density function can be written aswhereIndeed, $-A(\eta )=\sqrt{-2\eta }=1/\mu$. This is the canonical form of a one-parameter exponential family, and its natural parameter is therefore

Here the natural statistic is $T(X)=X$. The exponential-family derivative identities giveandThus

The per-capita net growth rate is the birth rate minus the death rate,Multiplying by the population size gives the ordinary differential equationThis is the exponential density-dependent birth model.

At a positive equilibrium, division by $N$ givesSince $b>d$, this has the positive solution

Write the vector field as $F(N)=N(b{e}^{-aN}-d)$. Its derivative isAt $N=N^{\ast }$, the first two terms cancel and $b{e}^{-a{N}^{\ast }}=d$, soThe one-dimensional linear stability analysis therefore shows that $N^{\ast }$ is locally asymptotically stable.

The susceptible equation may be writtenThe factor $b{e}^{-aS}$ is a density-dependent per-capita birth rate. The law of mass action gives the infection incidence $\beta SI$, which transfers individuals out of the susceptible compartment.

Likewise,There is no birth term in the infective equation, so only susceptible individuals reproduce in this model. Infectives die at total per-capita rate $d+\delta$. These terms define the susceptible-infective model with exponential density-dependent birth.

The disease-free equilibrium is $(S,I)=(N^{\ast },0)$. Forthe Jacobian matrix there isBecause this matrix is triangular, its eigenvalue are its diagonal entries:The second eigenvalue is positive exactly whenUnder this condition the linear stability analysis gives an unstable disease-free equilibrium, agreeing with the epidemic invasion threshold.

At an endemic equilibrium, $I^{\ast }>0$. The equation $\dot{I}=0$ then givesSince also $S^{\ast }>0$, the equation $\dot{S}=0$ givesThis infective population is positive precisely whenwhich is exactly the assumed instability condition for the disease-free equilibrium. Thus the endemic equilibrium of the susceptible-infective model with exponential birth exists.

At this equilibrium the relations above reduce the Jacobian matrix toHenceBy the trace-determinant stability criterion, both eigenvalues have negative real part. The linearization stability theorem therefore proves that the endemic equilibrium is locally asymptotically stable.

Consider the meromorphic functionClose the contour with a large semicircle in the upper half-plane, indenting above the three real pole $-1,0,1$. The large-arc integral vanishes by Jordan's lemma, while the upper-half-plane indentation rule givesThe three residue areTheir sum is $\cos 1-1$, so the residue theorem yields

The real part of the integrand is an odd function, so its full-line principal value is zero. Its imaginary part,is an even function. Taking imaginary parts and halving the full-line integral therefore gives

The kinetic energy of the two equal masses isThe extensions of the left, coupling, and right springs are respectively $x_1$, $x_2-x_1$, and $x_2$. Their potential energy is thereforeThus the mechanical Lagrangian $L=T-U$ has the requested quadratic form with the symmetric small-oscillation mass and stiffness matrices

The Euler--Lagrange equations for the quadratic Lagrangian areFor a normal mode $x(t)=a{e}^{i\omega t}$, they become the generalized eigenvalue problem for small oscillationsPut $\lambda =m{\omega }^2/k$. With the stated spring constants,The final matrix has characteristic polynomialso its eigenvalue are ${\nu }_{\pm }=\pm \sqrt{1+{\delta }^2}$. HenceThe two angular frequencies therefore satisfyThis is the spectrum recorded by normal modes of two equal masses between three springs.

In the homogeneous background, $\mathbf{v}=0$ and the physical velocity is the Hubble flowThe comoving coordinate $\mathbf{x}$ is held fixed by the time derivative in the fluid equation, soMoreover, spatial homogeneity gives $\nabla \bar{P}=0$. The Euler equation therefore reduces toTaking the divergence in three spatial dimensions givesConsistency with the Poisson equation,then requiresThis is the pressureless, zero-cosmological-constant Raychaudhuri equation, obtained by the Newtonian fluid derivation of the Raychaudhuri equation.

The elementary Newtonian derivation of the Friedmann equation follows a test particle on the boundary of a finite expanding sphere. It therefore introduces a distinguished centre and can misleadingly suggest that all matter expands away from one origin.

The fluid derivation is local: the Euler equation and Poisson equation must be compatible in every comoving neighbourhood. It consequently describes a genuinely homogeneous infinite universe, in which every comoving observer sees the same Hubble flow, without selecting a physical centre. This is the improvement captured by the Newtonian fluid derivation of the Raychaudhuri equation.

Insertinto the continuity equation. Its zeroth-order part is the homogeneous cosmological continuity equationSince $\bar{\rho }$ is spatially homogeneous, the terms of first order in $ϵ$ giveOn the other hand, the quotient rule and the background equation implySubstitution of the first-order equation yields the linearized cosmological continuity equationThe ratio $\delta \rho /\bar{\rho }$ is the density contrast.

With equal priors, the probability of a correct result from this quantum measurement isThe two required amplitudes areThereforeIts maximum occurs at $\beta =-\pi /8$ and is

Here $|⟨a_0|a_1⟩|=1/\sqrt{2}$, so $\theta =\pi /4$ and $\sin \theta =1/\sqrt{2}$. The stated Helstrom-Holevo bound is consequently exactly the same value, and the basis above is the Helstrom measurement for the zero and plus states.

The no-cloning theorem for two pure states states that, for distinct nonorthogonal states $|c_0⟩$ and $|c_1⟩$, there is no unitary operator $U$ and fixed blank state $|0⟩$ such that

To derive this from state discrimination, letand suppose such a cloner existed. Applying it repeatedly would produce $N$ copies. The inner product of the two possible $N$-copy states has magnitude $s^N$, so their optimal success probability under the Helstrom-Holevo bound would beAlready for $N=2$,because $0<s<1$ implies $s^4<s^2$. But cloning followed by the two-copy Helstrom measurement for two pure states would itself be a quantum procedure applied to the original single state, contradicting the optimal one-copy bound $P_1$. Hence the assumed unitary cloner cannot exist.

Equivalently, clone-assisted asymptotic state discrimination would give $P_N\to 1$, although two nonorthogonal states are not perfectly distinguishable. Thus the Helstrom--Holevo theorem implies the no-cloning theorem.

Take every logarithm in base two. The information entropy of $X$ iswith $0{\log }_{2}0=0$. If the codeword $c({\mu }_i)$ has length $s_i$, then its expected codeword length is

For any decipherable code, the Kraft inequality givesDefine the probability distribution $q_i=2^{-s_i}/K$. By Gibbs inequality,Since ${\log }_{2}K\le 0$,

Conversely, choose the integer lengthsThen $2^{-s_i}\le p_i$, so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,Thus the minimum expected length $S^{\ast }$ satisfies the Shannon noiseless coding theorem

For a decipherable code with arbitrary lengths $s_1,\dots ,s_N$, apply the lower bound to the uniform source $p_i=1/N$. Its entropy is ${\log }_{2}N$ and its expected length is $(s_1+\cdots +s_N)/N$. Hencethe total length lower bound for a decipherable binary code.

Now consider the cumulative construction. Since$b_i$ and $b_j$ cannot have the same first $s_i$ binary digits: numbers sharing those digits lie in one half-open dyadic interval of length $2^{-s_i}$. Also, $p_i\ge p_j$ implies $s_i\le s_j$. Therefore no earlier codeword $b_i^{\ast }$ is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.

An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, ifthen $(s_1,s_2)=(1,2)$ and the construction gives codewords $0$ and $10$, with expected length $1.4$. The prefix code $0,1$ has expected length $1$, so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.

A partial recursive function is obtained from the three kinds of initial function of recursion theory—
the zero function, successor function, and projection function—by finitely many applications of function composition in recursion theory, primitive recursion, and unbounded minimization. Explicitly, primitive recursion has the formwhile minimization takes the least $y$ for which $g(\mathbf{x},y)=0$ and is undefined if no such $y$ is found.

For the function in part (i), defineThe initial value $1=S(Z(0))$ and the identically zero recursion step are primitive recursive, so this is a primitive-recursive definition of the required zero test. It uses no minimization.

Using the zero test $s$ from part (i), define by primitive recursionSince $s(0)=1$ and $s(1)=0$, the values alternate:Thus $r$ is the required parity function and, like $s$, is primitive recursive without minimization.

Let $g(n,k)=r(n)$, where $r$ is the total primitive-recursive parity function from part (ii), and apply unbounded minimization in $k$:If $n$ is even, then $g(n,0)=0$ and $p(n)=0$. If $n$ is odd, then $g(n,k)=1$ for every $k$, so the search never terminates and $p(n)$ is undefined. Hence $p$ is partial recursive. Because every function built without minimization is total, $p$ cannot be defined without minimization; the functions $s$ and $r$ can.

It remains to characterize the functions built using only the initial functions and composition. They are exactly the functionsfor some $c\in \mathbb{N}$ and some input coordinate $i$.

Indeed, the zero function is the first form, the successor function and each projection function have the second form, and composing functions of these forms preserves the classification: a constant outer function remains constant, while an outer function $y_j+c$ selects one inner function and adds $c$. This proves necessity by structural induction. Conversely, applying the successor function $c$ times to zero produces the constant $c$, and applying it $c$ times to ${\pi }_i^k$ produces $x_i+c$.

Every function in this class is directly computable: an algorithm either writes the fixed constant $c$, or copies the $i$th input and performs $c$ successor steps.

Let $Y_{go}$ be the count for treatment(Control, LD, or SD) and outcome(Better or Worse), and write ${\mu }_{go}=\mathbb{E}{Y}_{go}$. Both fits take the six cell counts to be independent Poisson variables.

The additive log-linear model fitted by fit1 iswith reference constraints ${\alpha }_C=0$ and ${\beta }_B=0$. Thus treatment changes the overall group count but not the relative frequencies of the two outcomes.

The interaction model fitted by fit2 iswhere, under reference coding,and the two free interactions are ${\gamma }_{LW}$ and ${\gamma }_{SW}$. This is the saturated log-linear model for the $3\times 2$ table.

Letand condition on $N_g=n_g$. The corresponding model for each treatment group isFor fit1, the additive Poisson means implyso the outcome probabilities are common to all three treatments. For fit2,so each treatment may have its own outcome probabilities.