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

The simple continued fraction algorithm for $\sqrt{29}$ begins with $a_0=5$. Its complete quotients repeat afterThus

The convergents through one period areThe last one gives the negative Pell equation solutionTherefore

For $t<1/2$, the number $f(t)$ is negative real, so the proposed identity would forceContinuity on the connected interval $[0,1/2)$ makes $\varphi$ equal to one fixed odd multiple of $\pi$ there. For $t>1/2$, the number $f(t)$ is positive real, so $\varphi$ must instead equal one fixed even multiple of $\pi$. These two constants cannot agree, and their one-sided limits at $1/2$ therefore contradict continuity. The fact that $f(1/2)=0$ removes the phase condition at that one point but does not repair the discontinuity.

Now let $g:[0,1]\to \mathbb{C}\setminus \{0\}$ and put $h=g/|g|$. This is a continuous path in the unit circle. The exponential map $\theta \mapsto e^{i\theta }$ is a covering map, so the path lifting theorem supplies a continuous lift $\theta :[0,1]\to \mathbb{R}$ after one value of $\theta (0)$ is chosen. HenceOne can obtain the same lift directly from the allowed special case: by uniform continuity, subdivide $[0,1]$ so that on each subinterval $h(t)/h(t_j)$ lies in the right half-plane, choose its continuous local argument there, and add a multiple of $2\pi$ to match the preceding endpoint.

If $\theta$ and $\tilde{\theta }$ are two such phases, thenThis integer-valued function is continuous and hence constant. Thereforedoes not depend on the chosen lift.

For $u(t)=g(t^2)$, the phase $\theta (t^2)$ givesFor $v(t)=g(t{)}^2$, the phase $2\theta (t)$ gives

Finally, takeThey have the same two endpoints, but $r(g_1)=0$ and $r(g_2)=2\pi$. This endpoint discrepancy records the winding number of the closed path.

A general binary feedback shift register of length $d$ has stateand a feedback function $F:{\mathbb{F}}_2^d\to {\mathbb{F}}_2$. One update outputs the oldest bit, shifts the state, and insertsThe initial fill is $(x_0,\dots ,x_{d-1})$. It is a linear-feedback shift register whenfor fixed $c_i\in {\mathbb{F}}_2$.

The Berlekamp-Massey algorithm reads an intercepted sequence from left to right while maintaining the shortest connection polynomial that reproduces the prefix. At each new symbol it computes the discrepancy between the observed bit and that predicted by the current recurrence. A zero discrepancy leaves the polynomial unchanged; a nonzero discrepancy adds a suitably shifted copy of the connection polynomial saved at the previous increase in linear complexity. After at least twice the unknown register length, it recovers the shortest recurrence, after which the entire keystream can be predicted.

Applying those discrepancy updates toreturns the connection polynomialEquivalently, the sequence obeysIndeed this predicts successively $0,1,0,1,1$. No recurrence of length one or two fits the prefix, so its linear complexity is three.

A context-free grammar is in Chomsky normal form when every production has one of the formswhere $A,B,C$ are nonterminals and $a$ is a terminal. One may additionally allow $S\to ϵ$ when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.

An $ϵ$-production has the form $A\to ϵ$. A unit production has the form $A\to B$ for nonterminals $A,B$.

In $G_1$, the productions for $T$ giveConsequentlyIn $G_2$, $X$ and $Y$ generate $a$ and $b$, while $T\to TX\mid TY\mid c$ again givesSince $Z\to TX$, the two start productions $S\to XZ\mid YZ$ generate exactlyThusEvery production of $G_2$ has the required binary-nonterminal or single-terminal form, so $G_2$ is the Chomsky-normal-form grammar for the nonempty part of $L(G_1)$.

Writing $Y_i={\mathrm{medv}}_i$, $L_i={\mathrm{lstat}}_i$, and $A_i={\mathrm{age}}_i$, the fitted normal linear model isThe R formula lstat * age includes both main effects and their interaction term.

Three notable features are:

The first reaction is reversible, with reverse rate $k_{-1}{c}_1$. Applying the law of mass action to each reaction givesEach term has the sign dictated by whether the corresponding species is consumed or produced.

Adding the equations for the free enzyme and its two complexes givesThusThis conservation law says that the enzyme is neither created nor destroyed: each enzyme molecule is either free, bound in $C_1$, or bound in $C_2$.

Use enzyme conservation to writeSince $\tau =k_1{e}_{0}t$, $u=s/s_0$, $v_i=c_i/e_0$, and $ϵ=e_0/s_0$, substitution into the mass-action equations givesandwhereThe factors of $ϵ$ multiplying $d{v}_i/d\tau$ identify the complex concentrations as fast variables in a singular perturbation.

On times $\tau \gg ϵ$, the quasi-steady-state approximation setsThe second equation givesIn the first equation the terms $-\beta u{v}_1+\gamma v_2$ then cancel, leavingSolving these two equations givesSince $\dot{p}=k_3{c}_2=k_3{e}_0{v}_2$,

At small substrate concentration this allosteric rate is quadratic, $dp/dt\sim (A/\alpha )u^2$, so its graph leaves the origin with zero slope. At large $u$ it saturates at $A\gamma /\beta =k_3{e}_0$. A Michaelis-Menten equation also saturates, but its rate $V_{\max }u/(K_M+u)$ is linear near the origin. The allosteric curve is therefore more sigmoidal:This is the quasi-steady rate law for a two-substrate allosteric enzyme.

The Papperitz symboldescribes the two-dimensional solution space of a second-order homogeneous Fuchsian differential equation on the Riemann sphere with exactly three regular singular points $z_1,z_2,z_3$. Near $z_i$, its two independent Frobenius behaviours are locallysubject to logarithmic modifications in resonant cases. The six characteristic exponents obey the Fuchs relation

For the Gauss hypergeometric equation, the exponents at infinity are $a$ and $b$. Put $w=z^{-1}$. Transforming the Papperitz symbol from $z$ to $w$ shows thatandare local solutions near $z=\infty$, with respective leading behaviours $z^{-a}$ and $z^{-b}$. When $a-b\notin \mathbb{Z}$, these behaviours are distinct and the two solutions are linearly independent. They therefore form a basis of the solution space on any simply connected common domain with compatible branch choices.

The solution $F(a,b;c;z)$ normalized at zero can be analytically continued into that domain. Since it solves the same second-order equation, it must be a constant linear combination of the basis at infinity:The constants depend on $a,b,c$ and the branch convention, but not on $z$. This is the hypergeometric connection formula at infinity.

Taking downward distance as positive, the Lagrangian is

At equilibrium the lower spring supports only the lower mass, while the upper spring supports both masses:Hence

Let $q_i=z_i-z_i^{(0)}$. The linear terms cancel by the equilibrium equations, and the quadratic Lagrangian iswith the small-oscillation mass and stiffness matrices

The generalized eigenvalue problem for small oscillations isIts characteristic equation issoCorresponding displacement eigenvectors are

They are not orthogonal in the ordinary Euclidean inner product. They are orthogonal in the kinetic-energy, or mass-matrix, inner product:This is mass-matrix orthogonality of normal modes.

The constant $R$ is the curvature radius of the closed spatial slices when $a=1$; at general scale factor their curvature radius is $Ra$ and their scalar curvature is $6/(R^2{a}^2)$.

The cosmological perfect-fluid continuity equation isDuring expansion, $\dot{a}>0$, and thereforeIf $C=\rho (t_0)a(t_0{)}^3$, then throughout the later expanding phaseMultiplying the Friedmann equation by $a^2$ givesThe right-hand side is negative oncewhich is impossible because ${\dot{a}}^2\ge 0$. Thus the scale factor cannot grow without bound.

In fact the expanding phase ends in finite time. Combining the Friedmann and continuity equations yields the Friedmann acceleration equationThe curvature term in the first Friedmann equation also impliesWhile $a$ remains below the finite bound just found, $\ddot{a}$ is bounded above by a strictly negative constant. Hence $\dot{a}$ reaches zero after finite time: the closed universe attains a maximum size and cannot expand forever. This is recollapse of a closed Friedmann universe with nonnegative pressure.

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

Use $n$ controlled-NOT gates in parallel. For each $j=1,\dots ,n$, the $j$th input qubit is the control and the $j$th output-register qubit is the target. Their combined action iswhich is exactly

The known circuit from part (b) lets us apply $U_{\mathcal{I}}$ without querying the faulty oracle. Their composition satisfiesBecause $a=00\cdots 01$, only the last answer qubit is flipped in the exceptional case.

Prepare the answer register asSince $X|-⟩=-|-⟩$, quantum phase kickback gives, for an arbitrary search-register state,The answer register is unchanged and factors out. The induced operation on the first register is thereforeThis is the marked-state phase oracle from a single faulty identity-oracle query.

Use the construction in part (c) for the marked-state phase reflection in each Grover search algorithm iteration. Every such reflection costs one query to $U_f$; the identity-oracle circuit, Hadamard gates, and $I_0$ are independent of $f$.

Starting from $|s⟩$, after $r$ iterations the success probability isby the Grover rotation angle. Choose an integerThen $(2r+1)\theta$ differs from $\pi /2$ by at most $\theta$, soFor every sufficiently large $N$ this is greater than $1/2$, whileThus measuring the search register determines the faulty input with the required constant success probability using $O(\sqrt{N})$ oracle queries.

For an odd prime $p$, the Legendre symbol isEuler criterion states that

The Gauss lemma says that, for $p\nmid a$, if $m$ of the least positive residues oflie in $(p/2,p)$, thenTo prove it, replace every residue above $p/2$ by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation ofMultiplying the congruences givesCancel the nonzero factorial and apply Euler's criterion.

For $a=2$, the residues are $2,4,\dots ,p-1$. The number above $p/2$ iswhose parity gives the second supplementary law for quadratic reciprocityConsequently, for odd primes,The congruence is also soluble for $p=2$.

Suppose only finitely many primes $q_1,\dots ,q_r$ are congruent to $7$ modulo $8$, and setThenIf an odd prime $q$ divides $M$, then $n^2\equiv 2(\mathrm{mod}q)$, so part (a) givesSince their product $M$ is $7$ modulo $8$, at least one prime divisor $q$ is $7$ modulo $8$ to an odd power. Yet no listed $q_i$ divides $M$, because $n\equiv 0(\mathrm{mod}{q}_i)$ givesThis produces a new prime congruent to $7$ modulo $8$, a contradiction. HenceThis is the Euclid proof for infinitely many primes congruent to seven modulo eight.

Let $N=\lfloor \sqrt{x}\rfloor$ and formFor sufficiently large $x$, every factor is positive and at most $x$. Every odd prime divisor $p$ of $P$ makes $2$ a quadratic residue modulo $p$, so part (a) gives $p\equiv 1$ or $7(\mathrm{mod}8)$.

For an odd prime power $p^a$, the congruence $n^2\equiv 2(\mathrm{mod}{p}^a)$ has at most two residue classes, because each root modulo $p$ is simple and lifts uniquely. ThereforeSince $\log p/(p-1)\le \log 3/2$ for odd $p$,The prime $2$ contributes at most $N\log 2$, because $v_2(n^2-2)\le 1$. Ifthen, for all sufficiently large $x$, $2\log x\le N\log 3/2$ and hence