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

Suppose first that a simple continued fraction is eventually periodic. Its periodic tail $\xi$ is fixed by the Möbius transformation represented by the continued-fraction matrix of one full period:ThusThe infinite tail is not rational, since a rational simple continued fraction terminates. Hence $\xi$ is a quadratic irrational, and the finite initial block expresses the original number as another rational Möbius transform of $\xi$. Therefore every eventually periodic simple continued fraction represents a quadratic irrational.

For the purely periodic fraction $x=[7,7,7,\dots ]$,so $x^2-7x-1=0$. Positivity selects

Apply the continued-fraction algorithm to $\sqrt{23}$:The complete quotient then repeats, givingThe convergents through one term before the final $8$ areThe last of these satisfies the Pell equationso a positive solution is

LetAssume for a contradiction that $S=a/b$ is rational. For every $N\ge b$, both $N!S$ andare integers, because the $m_n$ are integers. Their positive differencemust therefore be a positive integer.

On the other hand, concavity of $x^{\alpha }$ for $0\le \alpha <1$ gives $(N+k{)}^{\alpha }\le N^{\alpha }+k^{\alpha }\le N^{\alpha }+k$. Since $(N+1)\cdots (N+k)\ge (N+1{)}^k$,Eventually $0<R_N<1$, contradicting its integrality. Hence

The integrality assumption is essential. For example, take $\alpha =0$, $A=2$, andThen $1<m_n<2$, but the exponential series givesThus the result does not remain true for arbitrary real $m_n$.

A binary linear-feedback shift register of length $L$ stores $L$ bits. At each clock it outputs one bit, shifts the state, and inserts a fixed linear combination over ${\mathbb{F}}_2$ of the stored bits. Equivalently, its output obeys a recurrence

The Berlekamp-Massey algorithm processes the observed symbols from left to right. It maintains the shortest current connection polynomial $C(D)$, its degree $L$, and a saved polynomial from the most recent degree increase. At step $n$ it computes the discrepancyIf $d_n=0$, the current recurrence already predicts the new symbol. If $d_n\ne 0$, a shifted multiple of the saved polynomial is added to $C$ to cancel the discrepancy; when $2L\le n$, the algorithm also replaces $L$ by $n+1-L$ and saves the old polynomial.

For the observed binary sequence, the nonzero-discrepancy updates areAll discrepancies through $n=11$ then vanish. Thus the shortest recurrence isor, equivalently, $s_{n+4}=s_{n+1}+s_n$. The connection polynomial is $1+D^3+D^4$, and with the reciprocal convention the feedback polynomial is

Fix an effective enumeration $f_{e,n}$ of the $n$-ary partial recursive functions.

The S-m-n theorem says that program inputs can be compiled into an index: for every $m,n\ge 1$ there is a total recursive $s_n^m$ such thatHere $\simeq$ means that either both sides are undefined or both are defined and equal.

The recursion theorem says that every total recursive transformation $h$ of program indices has a semantic fixed point: some $e$ satisfies

The Rice theorem says that every nontrivial extensional property of programs computed by partial recursive functions is undecidable.

By the S-m-n theorem, there is a total recursive function $h$ such thatfor all $x,y$. Apply the recursion theorem to $h$. It supplies an index $e$ for whichConsequently

Apply part (b) toThere is an index $m$ such that $f_{m,1}(y)\simeq g(m,y)$. Its domain of a partial function is exactlyTherefore

No. The propertyis extensional: it depends only on the partial function computed, not on its program index. It is nontrivial, since some partial recursive functions have a nine-element domain and others do not. The Rice theorem therefore implies that its index setis undecidable. Hence

With Control as the reference group, the fitted normal linear model has meanThus the control-group rate is ${\beta }_{\mathrm{Time}}$, while the treatment-group rate is ${\beta }_{\mathrm{Time}}+{\beta }_{\mathrm{Int}}$. The estimates areandweight units per day. The control slope has $t=-0.477$ and $p=0.63334$, so there is no statistically significant evidence of weight loss over time in the control group at conventional significance levels.

The plotted regression residuals for each mouse form smooth time patterns rather than an unstructured cloud: nearby observations on the same mouse have similar residuals, and the mice also show persistent individual offsets. This is strong evidence of autocorrelation and omitted mouse-level variation. The ordinary linear model treats all 400 measurements as independent after accounting for cage, so it commits pseudoreplication and will generally underestimate the coefficient standard errors. The reported $t$-tests and $p$-values should therefore not be trusted. A random-intercept linear mixed model with a within-mouse correlation structure would respect the repeated-measures design.

LetAt low density, $F(N)/N\to r$, so $r$ is the density-independent per-generation multiplication factor. The parameter $b$ has units of inverse population and sets the density scale at which crowding suppresses recruitment.

The fixed points satisfy $N=F(N)$. Besides extinction $N=0$, for $r>1$ there is the positive fixed pointSinceits multiplier isFor every $r>1$, $-1<F^{\prime }(N_{\ast })<1$, so fixed point stability for an iteration proves that $N_{\ast }$ is locally asymptotically stable.

Scale the population by $x_{\tau }=b{N}_{\tau }$. ThenThe map increases on $0<x<1$, decreases on $x>1$, and has global maximum $f(1)=r/4$. Starting from $x_1=1$ therefore givesFor $r>4$, writing $s=\sqrt{r}>2$ givesThus $1<L<N_{\ast }b=s-1<U$. Since $f$ decreases on $[L,U]$, $f(U)=L$ and $f(L)>f(s-1)=s-1>L$, while the global maximum gives $f(L)\le U$. Hence $f([L,U])\subseteq [L,U]$. The cobweb plot consequently remains in this invariant interval after the first iterate, and both endpoints are attained at $\tau =2,3$:The printed bound cannot include $\tau =1$, because $N_1=1/b<L/b$ when $r>4$.

Fora finite point $z_0$ is a regular singular point when $(z-z_0)P(z)$ and $(z-z_0{)}^{2}Q(z)$ extend holomorphically to $z_0$. A singularity at infinity is classified by applying this criterion after the change of variable $w=1/z$.

For the displayed Bessel differential equation,At $z=0$, the functions $zP(z)=1$ and $z^{2}Q(z)=z^2-1/4$ are holomorphic, so zero is regular singular. To inspect infinity, write $Y(w)=y(1/w)$. The equation becomesHere $w^{2}Q(w)=w^{-2}-1/4$ is not holomorphic at zero, so infinity is an irregular singular point. Thus

Set $y=z^{-1/2}f$. Direct differentiation makes every lower-order term cancel:Hence $f^{\prime \prime }+f=0$, and on any domain carrying a branch of $\sqrt{z}$ two linearly independent solutions areNear the regular singular point, these behave as $z^{-1/2}$ and $z^{1/2}$, the two Frobenius exponents. At infinity their combinations are $z^{-1/2}{e}^{\pm iz}$; after $w=1/z$ these contain $e^{\pm i/w}$, the exponential behavior characteristic of an irregular singular point.

Let a one-parameter infinitesimal transformation be $\delta q_i=ϵX_i(q,t)$ and suppose its change in the Lagrangian is a total derivative,With canonical momentum $p_i=\partial \mathcal{L}/\partial {\dot{q}}_i$, the chain rule and the Euler-Lagrange equations give, along a motion,Comparison with the assumed total derivative proves Noether theorem:

The given Lagrangian has no explicit time dependence, so its energy function is conserved:It is also invariant under the dilation $(x,y)\mapsto (e^{ϵ}x,e^{ϵ}y)$: the velocities and $y$ all scale by the same factor, while $x/y$ is unchanged. The generator is $(X_x,X_y)=(x,y)$ and $F=0$. SinceNoether's theorem supplies the second first integralThe integrals $E$ and $D$ are independent on an open dense subset of phase space.

For small $\theta$,Put $u=(6t/B{)}^{1/3}$. Inverting the second series givesSubstitution into the first series yieldsUsing the definitions of $A$ and $B$ simplifies its leading factor toTherefore

The homogeneous sphere containing the same mass has radius $\bar{R}=R_0{\Omega }_{m,0}^{1/3}a(t)$. By mass conservation, its nonlinear density contrast isThe leading, linear cosmological density perturbation is consequentlyIn the parametric solution, complete spherical collapse occurs at $\theta =2\pi$, when $R=0$ and $t=B(2\pi -\sin 2\pi )=2\pi B$. Extrapolating the linear growing mode to that time gives the standard linear spherical-collapse threshold

Let $P=|\psi ⟩⟨\psi |$. Since $|\psi ⟩$ is normalized, $P^2=P=P^{†}$. Hence the Householder reflectionis Hermitian andTherefore $A$ is unitary.

The marked-state phase oracle changes only the amplitude of $|x_0⟩$. Since that amplitude in $|\psi ⟩$ is $1/2$,Also,It follows that $A|\psi ⟩=-|\psi ⟩$ and $A|x_0⟩=|x_0⟩-|\psi ⟩$, soThe global minus sign has no observable effect. Prepare $|\psi ⟩=H^{\otimes 2}|00⟩$, query $I_{x_0}$ once, apply the fixed operator $A$, and perform a quantum measurement in the computational basis. The outcome is $x_0$ with probability one. This is exact Grover search on four entries.

No classical one-query algorithm can determine $x_0$ with certainty. If it queries a string $x$ and receives $1$, then it knows $x_0=x$. But if it receives $0$, each of the other three strings remains compatible with the response. Randomization cannot remove this ambiguity when certainty is required. ThusIndeed, three adaptive classical queries are necessary and sufficient in the worst case: after three negative answers, the unqueried fourth string must be $x_0$.

The Fermat-Euler theorem states thatIndeed, if $r_1,\dots ,r_{\phi (n)}$ are the reduced residue classes modulo $n$, multiplication by $a$ permutes them. ThereforeThe product ${\prod }_i{r}_i$ is invertible modulo $n$, so cancellation gives the theorem.

Now let $p$ be prime. If $k\equiv 1(\mathrm{mod}p-1)$, then for $p\nmid b$, Fermat little theorem gives $b^{k-1}\equiv 1(\mathrm{mod}p)$, while $p\mid b$ makes $b^k\equiv b\equiv 0$. Thus $b^k\equiv b$ for every integer $b$.

Conversely, assume this congruence holds for every $b$. Choose a primitive root $g$ modulo $p$. Then $g^{k-1}\equiv 1(\mathrm{mod}p)$. Since $g$ has order $p-1$, one has $p-1\mid k-1$. Hence

An odd composite $N$ coprime to $b$ is a Fermat pseudoprime to base $b$ when $b^{N-1}\equiv 1(\mathrm{mod}N)$. It is a Carmichael number when this congruence holds for every $b$ coprime to $N$.

Suppose a Carmichael number has $p^a\Vert N$ with $a\ge 2$. The group $(\mathbb{Z}/p^a\mathbb{Z}{)}^{\ast }$ is cyclic, so choose a residue of orderBy the Chinese remainder theorem, extend it to an integer $b$ that is congruent to $1$ modulo every other prime-power factor of $N$. Then $\gcd (b,N)=1$, and the Carmichael congruence forces the order of $b$ modulo $p^a$ to divide $N-1$. In particular $p\mid N-1$, contradicting $p\mid N$. Therefore every Carmichael number is square-free.

Now assume $N$ is square-free. If $p-1\mid N-1$ for every $p\mid N$, then for every $b$ coprime to $N$, Fermat little theorem givesfor each $p\mid N$. The Chinese remainder theorem then gives the congruence modulo $N$, so $N$ is Carmichael.

Conversely, if $N$ is Carmichael, fix $p\mid N$. Choose a primitive root $g$ modulo $p$ and use the Chinese remainder theorem to choose $b\equiv g(\mathrm{mod}p)$ and $b\equiv 1(\mathrm{mod}N/p)$. Then $b^{N-1}\equiv 1(\mathrm{mod}p)$, so the order $p-1$ of $g$ divides $N-1$. This proves the Korselt criterion in the required form:

A Carmichael number cannot have one prime factor because it is composite. If $N=pq$ with distinct primes $p<q$, the condition $q-1\mid pq-1$ implies $q-1\mid p-1$, which is impossible. Hence every Carmichael number has at least three prime factors.

The converted source omits $r$ from the product; the PDF asks about $N=pqr$. Fix the odd prime $r$, and suppose $pqr$ is Carmichael. Its three prime factors are distinct by the Korselt criterion. Relabel $p,q$ so that $p<q$.

The divisibility conditions includeWritefor a positive integer $b$. Since $p<q$,so $1\le b<r$. Moreover,Multiplying the second divisibility by $b$ and reducing modulo $p-1$ givesThe positive integer on the right is at most $(r-1)(2r-1)$. ConsequentlyThere are only finitely many possible primes $p$ and integers $b\in \{1,\dots ,r-1\}$, and each pair determines at most one $q=(pr+b-1)/b$. Therefore

The set $K$ is compact, and its complement is connected: two disjoint closed disks do not enclose any bounded complementary component. Since $f$ is holomorphic on the open neighbourhood $\Omega$ of $K$, the polynomial Runge theorem gives, for each $n$, a polynomial $p_n$ such thatHence

Define a function on the disconnected open set $\Omega$ byIt is holomorphic on $\Omega$. Applying the first part produces polynomials $P_n$ with

For an obstruction, takeThese are disjoint nonempty bounded closed sets. If polynomials $Q_n$ converged uniformly to zero on $K_1$, the maximum modulus principle on a bounded domain would giveThey therefore cannot also satisfy $Q_n(0)\to 1$. Thus this pair $K_1,K_2$ has the requested non-approximation property.

No intercept should be included unless the ordering of the two teams has an external meaning such as home advantage. Ifthen reversing the teams gives ${\eta }_{k\ell ,ij}=-{\eta }_{ij,k\ell }$, so the logistic model automatically givesAn intercept would not change sign when the teams are swapped and would violate this required symmetry. Thus an intercept does not make sense in the stated model.

Whenever players 1 and 2 occur, the linear predictor contains their parameters only throughFor any constants $a,b$, replacingleaves every fitted probability and hence the likelihood function unchanged. The parameterization is therefore nonidentifiable: at most ${\gamma }_{12}$ can be estimated uniquely. Hence there is no unique maximum-likelihood estimate of the three separate parameters.

Let $x$ be the parameter-contrast vector for the specified game: it has entries $+1$ for ${\beta }_i,{\beta }_j,{\beta }_{\{i,j\}}$, entries $-1$ for ${\beta }_k,{\beta }_{\ell },{\beta }_{\{k,\ell \}}$, and zero elsewhere. PutUnder the stated regularity assumptions, asymptotic normality of a maximum likelihood estimator giveswhere $i_N(\beta )/N\to I(\beta )$. Since $g^{\prime }(\eta )=p(1-p)$, the delta method givesEquivalently, for large $N$,with $p=e^{x^T\beta }/(1+e^{x^T\beta })$.