Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 4

Expand the finite Euler product into geometric series. By unique prime factorization, it is the sum of $1/n$ over positive integers whose prime factors do not exceed $x$, and hence contains every term up to $m=\lfloor x\rfloor$. The harmonic sum satisfiesThe last inequality uses $m+1>x$, including when $x$ is an integer. For each prime number $p$,The telescoping series over all integers $n\ge 2$ bounds the sum of these remainders by $\frac{1}{2}{\sum }_{n\ge 2}[n(n-1){]}^{-1}=1/2$. Taking logarithms of the product bound therefore givesThis explicit constant suffices; no asymptotic theorem about the distribution of prime numbers is needed.

For $x>0$, $N(x)=\lfloor 1/x\rfloor$ and $T(x)=1/x-\lfloor 1/x\rfloor$. Iterating this Gauss continued-fraction map on an irrational number never reaches zero, and its continued fraction isThe branches $T:(1/(n+1),1/n)\to (0,1)$ have inverse $x_n(y)=1/(n+y)$, for $n\ge 1$. The change of variables formula for a probability density function gives, almost everywhere,The endpoints of these branches are a countable set of probability zero. Thus $T(X)$ and $X$ have the same distribution; this Gauss measure is an invariant measure for the Gauss continued-fraction map.

In the RSA cryptosystem, choose distinct large prime numbers $p,q$, set $N=pq$, and choose $e$ coprime to $\phi (N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. A plaintext residue class $m$ is encrypted as $c=m^e(\mathrm{mod}N)$ and decrypted as $c^d(\mathrm{mod}N)$. Fermat's little theorem modulo $p$ and $q$, followed by the Chinese remainder theorem, proves correctness even when $m$ is not coprime to $N$.

Textbook RSA cryptosystem is multiplicative: $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$. For a chosen-ciphertext attack, multiply an intercepted $c$ by $r^e$ for a known invertible $r$. A decryption oracle returns $mr$, from which multiplication by $r^{-1}$ recovers $m$. Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring $N$.

For an ElGamal signature, choose a prime $p$, a primitive root $g$ modulo $p$, a private exponent $a$, and public $y=g^a$. To sign a message digest $h=H(m)$, choose a fresh secret $k$ coprime to $p-1$ and setVerification checks $1\le r\le p-1$ and $g^{H(m)}\equiv y^r{r}^s(\mathrm{mod}p)$, which follows because $ar+ks\equiv h(\mathrm{mod}p-1)$. Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.

Use state elimination for finite automata on a generalized finite automaton, whose directed edges are labelled by regular expressions. Add a fresh initial state $s$ with an $\epsilon$-edge to the old initial state and a fresh final state $f$ with $\epsilon$-edges from all old accepting states. Every missing edge has label $\varnothing$, the empty language; parallel edges are merged by union. The label $\epsilon$ denotes the language containing just the empty word.

When eliminating a state $k$, replace the label on each surviving edge $i\to j$ byHere juxtaposition means concatenation of formal languages, and the Kleene star allows zero or more traversals of the loop at $k$. Then delete $k$ and its incident edges. Eliminate every original state; the remaining $s\to f$ label is a regular expression for exactly the accepted formal language. The update accounts for paths avoiding $k$ and paths entering $k$, looping there any number of times, and leaving it.

Let $K$ be the diagonal halting set, which is undecidable. The pumping argument below actually holds for every subset $K\subseteq \mathbb{N}$; nonregularity needs the stated convention, or at least a set of exponents whose unary language is nonregular.

The pumping lemma for regular languages holds with pumping length one. For an accepted nonempty word, pump its first symbol. A word containing only $1$s remains in $1^{\ast }$ even if that symbol is deleted. If there is a zero and a nonempty prefix before its last zero, pumping the first symbol leaves the last zero and its following $n\in K$ ones unchanged. If the word is $01^n$, pumping its initial zero produces $0^i{1}^n$; this is accepted for $i\ge 1$, and for $i=0$ it belongs to $1^{\ast }$. In every case the pumped substring is nonempty and lies in the first position.

If $L$ were a regular language, closure under intersection would makeregular. A finite-state automaton for this intersection would decide membership of $n$ in the diagonal halting set by reading $01^n$, a contradiction. Thus $L$ satisfies the pumping lemma but is not regular, under the usual meaning of $\mathbb{K}$. If $K$ were arbitrary, the printed conclusion would be false, for example for $K=\mathbb{N}$.

This is the appropriate command for the full contingency table. It fits a log-linear model to the nine cell counts, with logarithmic link function and no interaction:With baseline constraints on $g_i,d_j$, there are five parameters. The factorized means express independence of treatment group and damage category. The maximum-likelihood estimates areAlthough the experiment fixes each row total at 30, conditioning these independent Poisson random variables on those totals produces the appropriate row-wise multinomial distribution. The Poisson trick therefore gives the correct likelihood inference for this independence log-linear model for a two-way contingency table; the margins are nuisance parameters. It tests whether treatment changes the distribution of damage, rather than modelling a binary outcome.

This is not a valid ordinary R glm family specification. A multinomial distribution is natural for the three damage counts conditional on the row total, but base R's generalized linear model interface does not supply a family named multinomial. Furthermore, the written response is one cell count, not a three-category response or grouped multinomial vector. A properly specified multinomial logistic regression could model category probabilities by group, but it is not the model fit by this command. The independent-count log-linear model in part (a), conditional on the margins, is the appropriate supplied alternative.

This does not model the full three-category response. A binomial distribution has two outcome classes, whereas the observed damage factor has three. In base R, a factor response to a binomial generalized linear model is coded as first level versus all other levels; this would silently collapse the categories. It would also treat the nine table rows as nine individual observations, ignoring the frequencies. A deliberate binary analysis would require specifying the collapse and retaining the counts, but cannot recover the full damage distribution.

The count weights correct the loss of frequencies for a deliberately coarsened binary response, but do not supply a third outcome category. Thus this remains inappropriate for the full contingency table. With the base R factor convention, it could fit the chosen first damage level versus the other two combined, using a logistic regression and the frequencies as weights. That is a different scientific question. The supplied log-linear model retains all three categories and their counts without this information loss.

At an endemic equilibrium, $I_{\ast }>0$, so $\beta S_{\ast }=\mu +\nu$. Substitution into the susceptible equation givesThese values are physically positive exactly when $R_0>1$. The Jacobian matrix at this equilibrium isBoth eigenvalues have negative real parts, so the endemic equilibrium is locally asymptotically stable. Its decay exponents areThe regime $\nu \gg \mu$ means recovery is rapid compared with demographic replacement. For fixed $R_0>1$ away from the threshold, the exponents form a complex conjugate pair with frequency approximately $\sqrt{\mu \nu (R_0-1)}$. HenceStrictly, oscillations require $\mu (\mu +\nu )(R_0-1)>{\mu }^2{R}_0^2/4$; $\nu \gg \mu$ alone does not ensure this uniformly for every $R_0$ arbitrarily close to one or arbitrarily large.

Vaccinating a fraction $v$ of newborns replaces the susceptible input by $\mu N(1-v)$. The effective basic reproduction number is $R_v=(1-v)R_0$, and the same calculation replaces $R_0$ by $R_v$. Provided $R_v>1$ and the oscillatory approximation remains applicable, vaccination lengthens the oscillation period, because $R_v-1$ is smaller. Extremely near eradication the exponents become real and there is no oscillation period to extrapolate indefinitely.

Substitute the Laplace contour-integral method for a linear differential equation into the differential equation and use $z{e}^{zt}={\partial }_t{e}^{zt}$. Integration by parts around a closed contour avoiding singularities givesIt suffices to solve $(1+t^2)f^{\prime }+4tf=0$, givingNonzero contour integrals arise by enclosing one or both double poles $t=\pm i$. At $t=i$, the residue isThe conjugate pole gives the conjugate expression for real $z$. Taking real and imaginary linear combinations yields the real solutionsTheir derivatives are $y_1^{\prime }=z\sin z$, $y_2^{\prime }=z\cos z$, and their Wronskian is $-z^2$, so they are linearly independent on every interval avoiding zero. Both extend analytically across zero and remain independent as functions; the vanishing Wronskian at zero reflects the singular leading coefficient of the printed differential equation there.

The Poisson bracket is $\{f,g\}=\mathbf{r}\cdot (\nabla f\times \nabla g)$. Since $\nabla {\rho }^2=2\mathbf{r}$, the scalar triple product vanishes, andEquivalently, check the identity on $x,y,z$ and extend to every polynomial using the Leibniz rule. Thus ${\rho }^2$ is a Casimir function of a Poisson manifold of this rotational Lie-Poisson structure on R3.

The Hamilton's equations areLinearization about $(1,0,0)$ gives $\dot{\alpha }=0$, $\dot{\beta }=(C-A)\gamma$, $\dot{\gamma }=(A-B)\beta$. The two nonzero exponents satisfy ${\lambda }^2=(C-A)(A-B)$. ConsequentlyWhen $A$ is outside this interval the transverse motion is oscillatory. At equality the linearization is nonhyperbolic; if just one transverse coupling vanishes, the other permits secular linear growth, rather than an exponential instability. This is the familiar intermediate-axis instability described by the Euler equations for a torque-free rigid body.

For a thin spherical shell, the radial pressure force per unit volume is $-dP/dr$. By the shell theorem, the inward gravitational acceleration is $GM(r)/r^2$, because exterior spherical shells contribute no force. Balancing force densities in hydrostatic equilibrium givesThe second equation is mass conservation; it closes the pressure-support equation once an equation of state is supplied.

Regularity at the centre requires finite ${\rho }_c,P_c$ and $M(0)=0$. Then $M(r)=4\pi {\rho }_c{r}^3/3+o(r^3)$, so $P^{\prime }(0)=0$. At a free stellar surface, $P(R)=0$; more generally it matches the external pressure. For $P=K{\rho }^2$ with $K>0$ and vacuum outside, this also gives $\rho (R)=0$.

Inside the star, cancel positive $\rho$ to obtain $2K{\rho }^{\prime }=-GM/r^2$. Differentiate and use mass conservation:Thus the Lane-Emden equation of polytropic index one isFor example, the regular solution is $\rho ={\rho }_c\sin x/x$, with its central value interpreted by continuity, and the first vacuum surface is at $x=\pi$. This also verifies the stated central and surface boundary conditions.

Dirichlet theorem on primes in arithmetic progressions states that if positive integer $q$ and integer $a$ satisfy $\gcd (a,q)=1$, then infinitely many prime numbers satisfyThe coprimality hypothesis is essential: if $a$ and $q$ have a common factor greater than one, a prime in the progression must divide that factor, giving at most finitely many possibilities.

Write an integral binary quadratic form as $Q(u,v)=A{u}^2+Buv+C{v}^2$, with discriminant of a binary quadratic form $d=B^2-4AC$. If $Q(u,v)=p$ is prime, then $\gcd (u,v)=1$: any common divisor would have its square dividing $p$. Complete $(u,v)$ to a matrix in ${\mathrm{SL}}_2(\mathbb{Z})$ using Bezout identity. After the associated integral change of variables, the properly equivalent form has leading coefficient $p$, say $[p,b,c]$. Its discriminant of a binary quadratic form gives $d=b^2-4pc$, hence $b^2\equiv d(\mathrm{mod}p)$.

Conversely suppose $b_0^2\equiv d(\mathrm{mod}p)$. Since $d$ is an integral-form discriminant of a binary quadratic form, $d\equiv 0$ or $1(\mathrm{mod}4)$. Choose $b\equiv b_0(\mathrm{mod}p)$ with even integer parity for $d\equiv 0(\mathrm{mod}4)$ and odd integer parity for $d\equiv 1(\mathrm{mod}4)$. This is possible because $p$ is odd. Then $b^2-d$ is divisible by $4p$, andis an integral form of discriminant of a binary quadratic form $d$ representing $p=Q(1,0)$. This proves the discriminant criterion for prime representation by a binary quadratic form, including the case $p\mid d$; no assumption that $d$ is a fundamental discriminant was used.

Both forms have discriminant of a binary quadratic form $-60$. The reduction algorithm for a positive definite binary quadratic form gives $|b|\le a\le c$ and $a\le \sqrt{60/3}<5$ for a reduced positive definite representative. Enumerating $a=1,2,3,4$ givesThe second and fourth forms are imprimitive and represent only even integers. Every odd prime represented by a form of discriminant of a binary quadratic form $-60$ must therefore be represented by $f$ or $g$.

For a prime $p\nmid 30$, quadratic reciprocity givesEvery prime $p\equiv 1(\mathrm{mod}15)$ has this symbol equal to one and hence is represented by one of the two primitive forms, by part (b). But an odd prime represented by $g$ and different from three is $2(\mathrm{mod}3)$, so these primes must be represented by $f$. Similarly, primes $p\equiv 2(\mathrm{mod}15)$ have both symbols equal to $-1$, and are represented by $g$, since a prime represented by $f$ is $1(\mathrm{mod}3)$. Both residue classes are coprime to 15, so Dirichlet theorem on primes in arithmetic progressions proves each form represents infinitely many primes.

The same modulo-three distinction excludes every prime other than three from being represented by both. The form $f$ does not represent three; $g$ represents three and five but neither is represented by $f$, and two is represented by neither. Therefore there are no primes represented by both forms.

Let $u(t)=\gamma (t)/|\gamma (t)|$, a continuous map into the unit circle. By uniform continuity, partition $[0,1]$ so finely that on each interval beginning at $t_j$, $|u(t)/u(t_j)-1|<1$. This ratio lies in the right half-plane and has a continuous complex argument with value zero at $t_j$. Starting from ${\theta }_0$, add these local arguments successively, matching endpoint values. This constructs a continuous real lift with $u(t)=e^{i\theta (t)}$.

Any two such lifts with the same initial value differ by a continuous function taking values in $2\pi \mathbb{Z}$, and hence coincide. Since the curve closes, $e^{i(\theta (1)-\theta (0))}=1$. Define its winding number byChanging the chosen initial argument adds a constant multiple of $2\pi$ to the whole lift, so the winding number is independent of that choice. No differentiability of the curve is required.

For each integer $m$, take ${\gamma }_m(t)=e^{2\pi imt}$. It is a continuous closed curve avoiding zero and has the continuous argument $2\pi mt$. ConsequentlyPositive and negative integers correspond to opposite senses of traversal, and the constant curve gives zero.

Choose continuous argument lifts ${\theta }_1,{\theta }_2$ for the two curves. Their sum is a lift for their pointwise product, becauseSubtract its initial value from its final value to obtainIn particular, winding numbers subtract under pointwise division of curves avoiding zero.

The continuous closed curve $q(t)={\gamma }_2(t)/{\gamma }_1(t)$ satisfies $|q(t)-1|<1$. It lies in the right half-plane, which admits a single continuous complex argument in $(-\pi /2,\pi /2)$. Since $q$ closes, this argument has equal endpoint values, giving $w(q)=0$. Additivity under multiplication then yieldsThe strict inequality ensures that the quotient stays in a region avoiding zero and admitting a single argument branch.

The appropriate homotopy invariance of winding number is: if $H:[0,1{]}^2\to \mathbb{C}\setminus \{0\}$ is continuous and $H(s,0)=H(s,1)$ for each $s$, then all loops $t\mapsto H(s,t)$ have the same winding number. The basepoint may move; every intermediate curve must close and avoid zero.

Compactness gives $m={\min }_{s,t}|H(s,t)|>0$. Uniform continuity gives $\delta >0$ such that $|s-s^{\prime }|<\delta$ implies $|H(s,t)-H(s^{\prime },t)|<m$ for every $t$. Part (d) then makes the winding numbers equal for nearby $s,s^{\prime }$. Subdivide $[0,1]$ into steps smaller than $\delta$ and chain these equalities. ThereforeThis proves the theorem directly for continuous loops, without requiring an integral formula or smooth homotopy.

The Poisson deviance tests overall fit against the saturated Poisson regression, not whether the single slope is zero. Under fit.1, its large-count approximation is ${\chi }_{60-2}^2={\chi }_{58}^2$. The observed value is 261.72, far above the one-percent upper critical value (about 85.95); its upper-tail probability is about $1.14\times 10^{-27}$. Thus reject fit.1 at the one-percent level. The slope's reported $p$-value 0.421 only compares this inadequate log-linear trend with an intercept-only model; it is not a goodness-of-fit test.

The two design matrices span the same six-dimensional space of arbitrary log means for the six periods. Fit.2 uses the first period as a baseline, whereas fit.3 uses cumulative indicator steps. If $a_j$ is the log mean for period $j$, fit.3 has intercept $a_1$ and jump coefficients $a_{j+1}-a_j$. Thus both fits give identical fitted means and identical maximized likelihood functions. ThereforeDifferent coefficient tests arise because they test different contrasts, not because one full fit explains the observations better.

Use fit.3 if backward selection is intended to combine adjacent periods. Each cumulative indicator is a separate model term; deleting its coefficient enforces equality of the two adjacent period means separated by that boundary. This offers an interpretable reduced stepwise profile. Fit.2 treats the entire factor as one term, so ordinary term-wise backward selection retains all five contrasts or removes period altogether. Removing selected baseline contrasts by hand would instead privilege period one, rather than grouping neighbouring periods. If the scientific objective were simply whether any period effect exists, retaining or deleting the whole factor in fit.2 would be the appropriate different procedure.

Under fit.2, observations in each period are independent Poisson random variables with a common mean, so each sample variance should fluctuate around its sample mean. The plot instead has variances roughly 130–300 for means roughly 80–120, well above the line variance equals mean. This is overdispersion.

Day-to-day traffic variation can produce a Poisson mixture: a random daily intensity increases the marginal variance and can correlate observations from the same day. A useful replacement is a negative binomial regression, with variance $\mu +{\mu }^2/\kappa$, or a Poisson generalized linear mixed model with a day random intercept. A day-factor effect can also be included if inference is restricted to the observed days. A Quasi-Poisson regression estimates a dispersion multiplier for uncertainty, but does not itself explain the shared-day dependence and has no ordinary likelihood-based AIC. The means can retain the period-factor or selected jump structure.

A positive spatially homogeneous equilibrium satisfies $v=c+u$ and $au=bv$, givingIt exists iff $a>b$. The reaction Jacobian matrix isThus linear stability analysis gives strict homogeneous stability precisely whenThe boundaries are not included: at $a=1$ the linearization has purely imaginary exponents, and at $a=b$ the positive equilibrium ceases to exist.

For a mode $\cos (kx)$, put $q=k^2$. The perturbation matrix is $J-\mathrm{diag}(q,dq)$. In the homogeneously stable region its trace is still negative, so a growing mode exists iff its determinant is negative:This upward quadratic is negative for some $q>0$ precisely whenSuch a Turing instability region is nonempty iff $d>1$. The unstable band isFor a finite domain only the admissible boundary-condition wavenumbers in this band grow. The region shown below describes a continuous wavenumber spectrum.

At onset the minimum of $D$ is zero and $q_c=u_{\ast }(d-a)/(2d)$. On the threshold $b=4d{a}^2/(d+a{)}^2$, substitution gives $u_{\ast }=4dac/(d-a{)}^2$. HenceThis last expression is the threshold wavenumber; away from onset the fastest-growing mode need not coincide with the minimum of the determinant.

The Euler-Lagrange equations for the kinetic Lagrangian areExpanding and multiplying by the inverse metric gives the geodesic equationThe kinetic variational principle uses an affine parameter; the energy $g_{ab}{\dot{x}}^a{\dot{x}}^b/2$ is constant along its solutions. Constant curves are also geodesics.

For the Poincare half-plane model, translation in $x$ gives the conserved quantity $p=\dot{x}/y^2$, and the energy is $E=({\dot{x}}^2+{\dot{y}}^2)/(2y^2)$. If $p=0$, the nonconstant geodesics are vertical lines, with $y=y_0{e}^{\pm \sqrt{2E}t}$. If $p\ne 0$,Writing $R^2=2E/p^2$ and integrating $dx/dy=\pm y/\sqrt{R^2-y^2}$ yields $(x-x_0{)}^2+y^2=R^2$. Thus nonconstant geodesic images are vertical lines or upper semicircles meeting the real axis orthogonally.

For the two specified points, the circle centre is $(6,0)$ and the radius is five:For example, an affine unit-speed parametrization is $x=6+5\tanh t$, $y=5\mathrm{sech}t$. The endpoints on the real axis are $(1,0)$ and $(11,0)$, outside the hyperbolic surface.

Use the convention that the transitive closure of $x$ is the least transitive set containing $x$ as a subset. Define $x_0=x$ and $x_{n+1}=\bigcup x_n$. For each natural number $n$, a finite sequence of length $n+1$ with these properties exists by induction, and is unique because each next entry is the uniquely determined union of the previous entry. Thus the relation sending $n$ to its last entry is a definable function-class, not just a putative recursive specification. The Axiom schema of replacement applied to $\omega$ gives the set of all $x_n$. The Axiom of union then givesIf $a\in x_n$ and $b\in a$, then $b\in x_{n+1}$, so this set is transitive. It contains $x=x_0$, and any transitive set containing $x$ contains all $x_n$ by induction; hence it is least. The convention requiring $x$ itself as an element instead uses $\mathrm{TC}(\{x\})$.

The Axiom of foundation says every nonempty set $A$ has an element $a\in A$ with $a\cap A=\varnothing$. Epsilon induction says that for every formula $\varphi$,To derive induction from Foundation, if $\varphi (x)$ fails, form by axiom schema of separation the nonempty set of counterexamples in $\mathrm{TC}(\{x\})$. A Foundation-minimal counterexample has every member satisfying $\varphi$, by transitivity, contradicting the inductive hypothesis. Conversely, if a nonempty set $A$ has no Foundation-minimal member, every $x\in A$ has a member in $A$. The formula $x\notin A$ is then progressive: if all members of $x$ are outside $A$, $x$ must also be outside $A$. Epsilon induction makes $A$ empty, a contradiction. Thus the two principles are equivalent given the other axioms.

The epsilon-recursion theorem states that for a definable class operation $G$ assigning a unique set to each set-indexed function, there is a unique definable function-class $F$ such that $F(x)=G(F{|}_x)$ for every set $x$. A version with explicit $x$ in the argument is equivalent. Foundation gives well-foundedness and Replacement makes each restriction set-sized. Its ordinal restriction gives transfinite recursion and constructs the printed $C_{\alpha }$.

Here “countable” means at most countable, including finite sets and the empty set. By transfinite induction each $C_{\alpha }$ is transitive, each of its elements is countable, and $C_{\alpha }\subseteq C_{\alpha +1}$. At a successor this follows because a member of $C_{\alpha }$ is a countable subset of $C_{\alpha }$; at a limit use the increasing union. Let ${\omega }_1$ be the first uncountable ordinal. Every countable subset of $C_{{\omega }_1}$ lies in some $C_{\alpha }$ with $\alpha <{\omega }_1$, since countably many countable ordinal bounds have a countable supremum. It therefore belongs to $C_{\alpha +1}$. ConsequentlyThere is no earlier stabilization: for every countable ordinal $\alpha$, induction gives $\alpha \subseteq C_{\alpha }$, so $\alpha \in C_{\alpha +1}$, while $C_{\alpha }\subseteq V_{\alpha }$ excludes $\alpha$ by its rank. Thus ${\omega }_1$ is the first such stage. The fixed set is the set of hereditarily countable sets.

Let $A$ be the adjacency matrix of a graph and $Av=\lambda v$ with $v\ne 0$. Choose a vertex $i$ maximizing $|v_i|>0$. ThenDividing givesThis argument works even with a complex eigenvector; for a finite undirected graph the matrix is real symmetric and all eigenvalues are real.