Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1

For an odd composite $N$ and a unit $b$ modulo $N$, $N$ is a Fermat pseudoprime to base $b$ whenIt is an Euler pseudoprime to base $b$ whenwhere the right side is the Jacobi symbol.

By the Chinese remainder theorem,and $\phi (105)=2\cdot 4\cdot 6=48$. The condition $b^{104}=1$ is automatic modulo $3$ and $5$. Modulo $7$ it hassolutions. Thus there are $2\cdot 4\cdot 2=16$ Fermat bases, giving proportion

For the Euler condition, $b^{52}=1$ modulo $3$, so the Jacobi symbol must be $+1$. The power condition is automatic modulo $5$, while modulo $7$ it again restricts $b$ to the two solutions of $b^2=1$. For each of those two residues, exactly half of the $2\cdot 4$ choices modulo $3$ and $5$ have Jacobi symbol $+1$. Hence there are $2\cdot 4=8$ Euler bases and proportion

The $n$th Chebyshev polynomial is defined on $[-1,1]$ byThe cosine addition formula givesInduction therefore shows that every $T_n$ is a polynomial. Its defining cosine formula also gives

The assertion is clear for $T_1=x$. If $T_n$ has degree $n$ and leading coefficient $2^{n-1}$, the recurrence shows that the leading term of $T_{n+1}$ isthe lower-degree polynomial $T_{n-1}$ cannot cancel it. Hence

For $x=\cos \theta \in [-1,1]$,Both sides are polynomials in $x$. Since they agree on an interval, the polynomial identity theorem extends the equality to every real $x$. Thus $T_n$ is even for even $n$ and odd for odd $n$.

The $n$ roots of $T_n$ are distinct and lie in $(-1,1)$. Repeated use of Rolle's theorem shows that every root of $T_n^{(k)}$, for $0\le k<n$, also lies in $(-1,1)$. Its leading coefficient is positive, soTaking $k=r+1$ shows thatfor $0\le r\le n-1$; when $r=n-1$, the derivative is the positive constant $T_n^{(n)}$. This is the positivity of Chebyshev derivatives beyond the unit interval.

Writing $x=\cos \theta$ and taking the limit as $\theta \to 0$ givesPart (d), with $r=1$, shows that $T_n^{\prime }$ is increasing on $[1,\infty )$, soSince $T_n(1)=1$ and $n^2\ge n$,

Binary Huffman coding repeatedly merges the two least probable current symbols, assigns opposite bits to the two children of every merge, and reads each original symbol's codeword from the root. The resulting prefix code minimizes expected word length.

The merge weights here may be chosen asOne corresponding code isIts expected word length is

Take the productionsand the word $w=aa$. There is only one parse tree: its root uses $S\to AA$ and each child uses $A\to a$. There are nevertheless exactly two derivations,andaccording as the left or right occurrence of $A$ is replaced first. This illustrates that derivations record replacement order while a context-free grammar parse tree does not.

The first displayed tree supplies the productions $S\Rightarrow AS$ and $S\Rightarrow AA$, as well as an $A$-parse tree producing $ab$. By assumption there is also an $A$-parse tree producing $baba$. Substitute these trees as follows:The resulting yield is

The displayed trees provide $A$-parse trees producing $ab$, $bb$, and $aa$, together with the same root productions as above. Thereforewhose yield is

Assume that $L$ is context-free and let $p$ be its pumping length. Apply the pumping lemma for context-free languages toWrite $w=uvxyz$, with $|vxy|\le p$ and $|vy|>0$. The substring $vxy$ meets at most two of the three constant-letter blocks.

If $v$ and $y$ affect only the first block, only the middle block, or only the last block, pumping down immediately makes the final block length differ from the minimum of the first two lengths. If they meet the first and second blocks, pumping down decreases at least one of those block lengths while leaving the final length $p$, again violating the defining minimum.

It remains that they meet the second and third blocks. Let pumping change their lengths by $s$ and $t$, respectively. Pumping down fails unless $s=t$. If $s=t>0$, pumping up gives lengthswhose last entry is not $\min (p,p+s)=p$. Thus some pumping exponent always leaves $L$, contradicting the lemma. Hence

A generalized linear model has three components:

Write the exponential-dispersion density asWith the canonical link, ${\theta }_i={\eta }_i=x_i^T\beta$. ThereforeKnown prior weights replace $\varphi$ by $\varphi /w_i$.

In the Poisson GLM the responses are independent andThe Poisson canonical link is logarithmic, so

For $F(n)=\alpha n-\beta n^3$, the nonnegative equilibria areSincethe zero equilibrium is unstable and $K$ is asymptotically stable.

For $0<n<K$, $F(n)>0$, so solutions increase monotonically toward $K$. For $n>K$, $F(n)<0$, so they decrease monotonically toward $K$. The solution $n=0$ remains at zero. Thus a phase-line sketch has arrows away from $0$ and toward $K$; a time-series sketch has all positive curves tending to the same horizontal asymptote $K$. This is the cubic saturation population model.

With the same low-density rate and carrying capacity, the two per-capita growth rates arefor the cubic model andfor logistic growth. The logistic correction is linear in a small population, whereas the cubic correction is quadratic. Consequently the cubic trajectory initially follows pure exponential growth more closely and lies above the logistic trajectory before both approach $K$. Plotting measured per-capita growth against $n$ distinguishes a linear decline from a curve with zero slope at the origin.

For singularities $a<c_1<\cdots <c_N<b$, the Cauchy principal value iswhere the assumed tail integrals make the two unbounded pieces meaningful. Equivalently, remove a symmetric interval of radius $\epsilon$ about each $c_j$ and take the limit of the remaining integral.

Using the convention adopted here, the Hilbert transform isThe convention with denominator $x-y$ differs by a minus sign.

For $f(x)=1/(x^2+1)$, contour integration or partial fractions givesunder the convention in part (b). Therefore

Let $\theta$ be the angle from the downward vertical to the hoop's centre, measured at the suspension point, and let $\varphi$ be the absolute angle from the downward vertical to the bead's radius from the hoop centre. The bead position is the sum of two vectors of length $a$. Including the hoop's moment of inertia about the pivot giveswhileThus one suitable Lagrangian is

To quadratic order about $\theta =\varphi =0$,andFor a normal mode, put $c={\omega }^{2}a/g$. The characteristic equation isso $c=1/2$ or $2$. The small oscillations of a hoop with a sliding bead therefore have

The slow-roll equations implyFor $V=\lambda {\varphi }^n/n$, $V/V^{\prime }=\varphi /n$. Integrating from ${\varphi }_i$ and using $a({\varphi }_i)=1$ gives

From $3H\dot{\varphi }=-c^2{V}^{\prime }$ and $H^2=8\pi GV/(3c^2)$,The slow-roll approximation fails when this kinetic contribution is comparable with $V$, giving

The number of e-folds isUsing the estimate above,For $n=6$ and the roughly $60$ e-folds needed for the flatness problem,This is the monomial slow-roll e-fold count.

Let $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. After the Hadamards and the oracle, Bernstein-Vazirani phase kickback gives

The Walsh-Hadamard identityand $H|-⟩=|1⟩$ give

A final oracle call evaluates $f$ on the definite input $a$:Since $a\cdot a$ modulo two is the parity of the Hamming weight of $a$, this form also determines the last-qubit measurement.

The first register of $|{\Phi }_3⟩$ is exactly $|a⟩$, so the probability of observing the string $a$ is

Measuring the first register does not disturb the product-state last register. Its state is

If $a$ has odd Hamming weight, then $a\cdot a=1$ and the final bit is $b$, so the probability is $1$. If $a$ has even Hamming weight, then $a\cdot a=0$ and the final bit is $1\oplus b$, so the probability is $0$. Thus

For a received word $y$, the ideal-observer rule chooses a message $i$ maximizing the posterior probabilityMaximum-likelihood decoding chooses $i$ maximizingand minimum-distance decoding chooses a codeword minimizing its Hamming distance from $y$.

Bayes' formula givesEqual message priors therefore make ideal-observer and maximum-likelihood decoding identical. On a binary symmetric channel, if $d=d_H(y,c_i)$, thenFor $p<1/2$, this strictly decreases with $d$, so maximum likelihood and minimum distance agree.

Choose $\delta$ withA greedy packing construction gives binary length-$n$ codes of minimum distance greater than $2\delta n$ and size at leastTheir asymptotic rate is at leastwhere $h_2$ is binary Binary entropy. Minimum-distance decoding corrects every error pattern of weight at most $\delta n$. Since a channel error count is $\mathrm{Bin}(n,p)$, the law of large numbers givesThus a fixed positive rate is achievable with error tending to zero, proving that the operational capacity is nonzero. This is the positive-rate coding bound below one-quarter crossover.

Shannon second coding theorem states that the operational capacity of a discrete memoryless channel equalsevery rate below $C$ is achievable with error probability tending to zero, while rates above $C$ are not.

Put $d=b-a$. If $d=0$, then $Y=X+a$, so $X$ is recovered exactly and $C=1$ bit. If $|d|\ge 2$, the two output supportsare disjoint, so again $Y$ determines $X$ and $C=1$.

If $|d|=1$, one output value is common to both inputs and occurs with probability $1/2$ independently of the input, while either of the other two values reveals the input. The channel is therefore a binary erasure channel with erasure probability $1/2$, whose capacity is $1/2$ bit. Hence

The upper register index is the largest register number occurring in an instruction of $P$, with value zero if only register $0$ is used. A configuration records the current state and the contents of every register up to that index.

For input $\vec{w}$, let $C(0,M,\vec{w})$ be the initial configuration: the designated initial state, the words of $\vec{w}$ in the input registers, and the empty word in every remaining register. Recursively, if $C(t,M,\vec{w})$ is halting, keep it fixed; otherwise let $C(t+1,M,\vec{w})$ be the unique configuration into which $M$ transforms it. The resulting sequenceis the computation sequence.

Choose an input word $w$ of length at least $n+1$. The final value $f_{M,1}(w)={\chi }_L(w)$ has length at most one. Every symbol initially in register $0$ must either be deleted or transferred elsewhere, and either action begins with a remove instructionNo other instruction can lower the length of register $0$. Consequently at leastsuch remove instructions occur in this computation. Since words of arbitrary length exist, the assertion follows.

Two registers suffice. Use register $0$ for the input and register $1$ as a stack of markers.

The finite control first rejects the empty word. While the next input symbol is $a$, remove it from register $0$ and append one marker to register $1$. On seeing the first $b$, enter a second phase. For every $b$ removed from register $0$, remove one marker from register $1$; reject if a marker is unavailable or if an $a$ is encountered in this phase. Accept exactly when both registers become empty simultaneously.

The first phase stores precisely the number of $a$'s, and the second compares it with the number of $b$'s. Register $1$ is the only scratch register, so the construction is a one-register-machine computation in the question's terminology. Therefore

Consider computations while a terminal block of $b$'s is removed from register $0$. Until that block has disappeared, the available instruction and next state depend on the current state and on the visible $b$, not on the untouched prefix $x$.

Take a block longer than $|Q|$. Record the state after each successive $b$ has been removed. Two records have the same state $q$, by the pigeonhole principle. If the corresponding removed tail lengths are $k\ne \ell$, the same finite instruction sequences work in front of every prefix $x$. Thus there are fixed times $t,t^{\prime }$ such thatfor every word $x$.