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

Apply the continued-fraction algorithm. Since $3<\sqrt{11}<4$,The successive complete quotients areandTaking one more reciprocal returns to $x_1$, so the continued fraction of the square root of eleven is

WriteThe first convergents are $p_0/q_0=3$ and $p_1/q_1=10/3$, whenceThe continued fraction convergent recurrence iswhere $a_{n+1}=3$ for even $n$ and $a_{n+1}=6$ for odd $n$.

SetIf $n$ is even and $z_{n+1}=\beta z_n$, thenbecause ${\beta }^{-1}=\sqrt{11}-3$. If $n$ is odd and $z_{n+1}=\alpha z_n$, thenbecause ${\alpha }^{-1}=(\sqrt{11}-3)/2$. The base case and induction prove the alternating multiplier recurrence for convergents of the square root of eleven:

LetThe function $h$ is continuous, withThe intermediate value theorem gives $c\in [0,1]$ such that $h(c)=0$, and hence $f(c)=c$. This proves the fixed-point property of a closed interval.

Now suppose $0,1\in f([0,1])$. For any $y\in [0,1]$, choose $a,b\in [0,1]$ with $f(a)=0$ and $f(b)=1$. Applying the intermediate value theorem to $f$ on the interval with endpoints $a,b$ gives a point $x$ with $f(x)=y$. Thus $f$ is a surjective function.

Let $h:A\to B$ be a homeomorphism, and let $f:B\to B$ be continuous. The conjugate mapis continuous. By hypothesis it has a fixed point $a\in A$. Thereforeand applying $h$ gives $f(h(a))=h(a)$. Hence every continuous self-map of $B$ has a fixed point. This is the homeomorphism invariance of the fixed-point property.

The Brouwer fixed-point theorem for the closed unit disc $\overline{D}\subset {\mathbb{R}}^2$ states that every continuous maphas a fixed point.

The closed unit disc has the fixed-point property by the Brouwer fixed-point theorem. The annulus admits the fixed-point-free rotation of an annulus, for examplewhich is continuous, maps the annulus to itself, and has no fixed point because the origin is not in the annulus. If the disc and annulus were homeomorphic, the homeomorphism invariance of the fixed-point property would give the annulus the fixed-point property, a contradiction. Therefore they are not homeomorphic.

No. TakeIt contains more than one point and has the fixed-point property of a closed interval, but it is not homeomorphic to the closed unit disc. Indeed, deleting any point $(t,0)$ with $0<t<1$ disconnects $B$, so such a point is a cut point. Deleting one point from a two-dimensional closed disc leaves a path-connected space. Since being a cut point is preserved by homeomorphisms, the two spaces cannot be homeomorphic. This gives the required counterexample.

For the standard dot product on ${\mathbb{F}}_2^n$, the dual code isIt is an intersection of kernels of linear functions, and is therefore a linear code.

Let $\sigma$ denote cyclic right shift. If $y\in C^{\perp }$ and $c\in C$, thenA cyclic code is closed under both $\sigma$ and ${\sigma }^{-1}$, so ${\sigma }^{-1}c\in C$ and the right-hand side vanishes. Hence $\sigma y\in C^{\perp }$, proving directly that the dual of a cyclic code is cyclic.

Identify words with polynomials in ${\mathbb{F}}_2[X]/(X^n-1)$. If the generator polynomial of a cyclic code is the monic divisor $g(X)$ andthen the generator polynomial of $C^{\perp }$ is the monic reciprocalEquivalently, the parity-check polynomial of one code becomes, after reversal, the generator polynomial of its dual.

Over ${\mathbb{F}}_2$, subtraction equals addition. The polynomial $X^7-1$ has the factorizationThe two cubic factors have no root in ${\mathbb{F}}_2$, so they are irreducible, and they are reciprocal to one another. PutEvery cyclic code corresponds to one monic divisor of $X^7-1$. The complete list isThus the two cubic generators give the two cyclic coordinate orientations of Hamming's $[7,4,3]$ code. Their duals have generators $(X+1)f$ and $(X+1)f^{\ast }$ and are the $[7,3,4]$ simplex codes. The remaining four are the familiar whole-space, even-weight, repetition, and zero codes. This is the complete classification of binary cyclic codes of length seven.

A grammar $G=(\Sigma ,V,P,S)$ is a right-linear regular grammar when every production has one of the formswhere $A,B\in V$ and $w\in {\Sigma }^{\ast }$. Thus a production has at most one variable on its right-hand side, and that variable is at the right end.

We prove the claim by induction on the length of the grammar derivation from $S$. At length zero the sentential form is $S=ϵS$, which has the required form.

Suppose the current sentential form is $wA$. Because $w$ is terminal, the only symbol to which a production can apply is $A$. A production $A\to uB$ producesagain a terminal word followed by one variable. A production $A\to u$ produces the terminal word $wu$. Once a completely terminal word is reached, no further production can apply. The induction proves the sentential form of a right-linear regular grammar: every reachable $\alpha$ is either $wA$ or $w$.

In every derivation beginning at $wA$, the terminal prefix $w$ remains unchanged because no production has a terminal on its left-hand side. By the sentential-form result, each step rewrites the sole variable at the right and appends terminals immediately before its successor variable. Henceforces $v=wu$ for some $u\in {\Sigma }^{\ast }$. Removing the inert prefix $w$ from every sentential form in the derivation gives

An accepting derivation in a right-linear grammar has the formwith one active variable until the final terminal production.

If no variable repeated on any accepting derivation, an accepting derivation could contain at most $|V|$ variable occurrences. Since the production set is finite, only finitely many such derivations and hence finitely many terminal words would exist. The hypothesis that $\mathcal{L}(G)$ is infinite therefore supplies an accepting derivation in which some variable $A$ occurs twice.

Split this derivation at the two occurrences:where $u,v,z\in {\Sigma }^{\ast }$. The first segment makes $A$ an accessible variable of a regular grammar, the middle segment makes it a looping variable of a regular grammar, and the last makes it a terminable variable of a regular grammar. Thus $A$ has all three properties, proving the accessible looping terminable variable criterion.

Use the R linear-model formula with only its implicit intercept:

This models every log-price by one common mean plus an error term.

The other quantitative columns are mpg, psngr, length, width, and weight, so use

This is a normal linear model with an intercept and five slopes.

Treat make as a categorical predictor, converting it to a factor explicitly if necessary:

The models are nested. The first nested-model F-test compares fit2 with the intercept-only fit1. Adding the five quantitative predictors reduces the residual sum of squares from $8584.0$ to $3349.1$, withThere is overwhelming evidence that these quantitative car properties jointly improve the model.

The second test compares fit3 with fit2. Adding make reduces the residual sum of squares further to $840.8$, withThus manufacturer has a highly significant effect even after adjusting for the five quantitative properties, and fit3 is preferred among these nested models.

There are $93$ observations because the intercept-only model has $92=93-1$ residual degrees of freedom. The make term uses $31$ additional degrees of freedom. By the degrees of freedom of a factor predictor, a factor with $m$ represented levels contributes $m-1$ degrees of freedom when an intercept is present. Henceunique manufacturers occur in the dataset.

Put $a=f^{\prime }(0)>0$. Linearizing the morphogen reaction-diffusion equation at $C=0$ givesSeek separated modes $C(x,t)=X(x)e^{\lambda t}$. ThenThe mixed Dirichlet-Neumann modes on an interval areIndeed, the Dirichlet condition selects sine functions, while the Neumann condition requires $\cos (k_{n}L)=0$. Their growth rates areThe largest growth rate is the lowest mode,Linear stability requires ${\lambda }_0<0$, after which all higher modes also decay. Therefore the critical length for a linearly growing morphogen isEquality gives a neutral lowest mode, while a larger domain is linearly unstable.

The Papperitz symbolspecifies a second-order Fuchsian differential equation. The first row lists its three distinct regular singular points $0,1,\infty$; $z$ is the independent variable. The two entries below each singular point are its characteristic exponents. Thus local solutions have leading behaviorsand, with the usual convention at infinity,When an exponent difference is an integer, a logarithmic second solution may replace the naive second Frobenius power. The entries obey the Fuchs relationFor a second-order equation with exactly three regular singular points, these exponent data determine the equation up to multiplication by a nonzero function; there is no accessory parameter. The symbol is therefore the one for the Gauss hypergeometric equation. Its distinguished solution $F(a,b;c;z)$ is the exponent-zero solution analytic at zero and normalized to one there. For the ordinary power-series definition one assumes $c\notin \{0,-1,-2,\dots \}$, with exceptional parameter values handled separately or by continuation.

Now putThe hypergeometric equation in $u$ has exponent pairsThe Möbius transformation of a Papperitz symbol sendsso $Y$ has symbol

On the other hand, $F(a,b;c;z)$ has exponent pairsat $0,1,\infty$. Multiplication by $(1-z{)}^a$ applies the dependent-variable rescaling of a Papperitz symbol: it adds $a$ to both exponents at $z=1$ and subtracts $a$ from both at infinity. Hencehas exactly the same three exponent pairs as $Y$.

Both functions are analytic near $z=0$ and equal one at $z=0$, so uniqueness of the normalized exponent-zero hypergeometric solution gives the Pfaff transformationThe identity first holds near zero with the branch of $(1-z{)}^a$ equal to one there, and then extends by analytic continuation on any domain where compatible branches are chosen.

An adiabatic invariant remains constant to leading order when a system parameter changes on a timescale much longer than one period. For a periodic one-degree-of-freedom system, the adiabatic invariance of the action supplies such an invariant.

The momentum magnitude between collisions is $p_0=\sqrt{2mE}$. A complete orbit crosses the gap once in each direction, so the unnormalized action used in the question isConsequentlybecause the speed is $\sqrt{2E/m}$ and the round-trip distance is $2L$.

When $L(t)$ varies adiabatically, conservation of the adiabatic particle between moving parallel walls action givesA moving wall does work at each collision: an approaching wall raises the particle's energy and a receding wall lowers it. Elasticity holds in the instantaneous rest frame of the wall.

The Flatness problem is that the observed cosmological density parameter is close to $\Omega =1$, although in an ordinary decelerating universe any departure from one grows with time. Extrapolation backward therefore requires implausibly precise early cancellation of the curvature term.

The cosmological perfect-fluid continuity equation isConsequentlyFor an expanding universe $H>0$. Ifthen $\rho a^2$ increases. The Friedmann equation impliesIt therefore decreases during this period, driving $\Omega$ toward one. By the Friedmann acceleration equation, the same condition gives $\ddot{a}>0$ when the cosmological constant is included in the effective fluid. This is the inflationary solution of the flatness problem.

For the scalar field, the slow-roll approximation meansThe equations reduce toTaking the positive-field branch gives $H\simeq m\varphi /\sqrt{3}$, and thereforeWith $\varphi (0)={\varphi }_i$,Now integrate $H=\dot{a}/a\simeq m\varphi /\sqrt{3}$:Thus the quadratic-potential slow-roll solution isFinally,so equivalently

Let the unknown qubit be $|\alpha ⟩=a|0⟩+b|1⟩$. Alice holds this qubit and her half of the shared Bell state $|{\Psi }^{+}⟩$, while Bob holds the other half.

Alice performs a measurement of her two qubits in the Bell basis and sends the two-bit outcome to Bob through the classical channel. For the shared state $|{\Psi }^{+}⟩$, the teleportation with the psi-plus Bell state correction table isup to physically irrelevant global phases. Here $X$ and $Z$ are the Pauli X gate and Pauli Z gate. After the indicated correction, Bob's qubit is $|\alpha ⟩$. This is quantum teleportation; no physical copy of the unknown qubit is sent.

Let $D$ denote Alice's unknown input qubit and $A$ her GHZ qubit. Expanding the four-qubit state in the Bell basis of $D,A$ giveswhere a global sign in the last term is immaterial.

For outcomes ${\Phi }^{+}$ and ${\Phi }^{-}$, Bob and Charlie already haveFor either $\Psi$ outcome, both apply the Pauli X gate. Since $X\otimes X$ exchanges $|00⟩$ and $|11⟩$, the ${\Psi }^{+}$ branch becomes $|{\varphi }_1⟩$ and the ${\Psi }^{-}$ branch becomes $|{\varphi }_2⟩$, up to a global phase. This proves the Bell measurement on one qubit and one leg of a GHZ state result.

Finally, tracing out Charlie givesfor either sign. This reduced state has rank two exactly when $a\ne 0$ and $b\ne 0$. By the entanglement criterion for a two-term correlated state,

For an odd prime $p$, the Legendre symbol isEuler criterion states thatIf $p\mid a$, both sides vanish. Otherwise choose a primitive root $g$ and write $a\equiv g^m$. Since $g^{(p-1)/2}\equiv -1$,The power $g^m$ is a square exactly when $m$ is even, proving the criterion. Taking $a=-1$ gives the first supplementary law for quadratic reciprocity

Because $I$ and $A$ commute, the matrix binomial theorem givesFor prime $p$, every intermediate coefficient $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ is divisible by $p$, proving the prime-power binomial congruence for a matrix

Forone has $(I+A{)}^2=2A$ and $(I+A{)}^4=-4I$. If $p=4k+1$, thenso $(-4{)}^k\equiv 1(\mathrm{mod}p)$. If $p=4k-1$, then $A^p=-A$ andso $(-4{)}^k\equiv 2(\mathrm{mod}p)$.

By Euler criterion, $(\frac{2}{p})\equiv 2^{(p-1)/2}(\mathrm{mod}p)$. In either case the preceding congruence gives $(\frac{2}{p})=(-1{)}^k$. Since $(p^2-1)/8$ has the same parity as $k$ for $p=4k\pm 1$, this is the second supplementary law for quadratic reciprocity

Write $\chi (a)=(\frac{a}{p})$. When $p\equiv 1(\mathrm{mod}4)$, the first supplementary law for quadratic reciprocity gives $\chi (-1)=1$, so $\chi (p-a)=\chi (a)$. Pairing $a$ with $p-a$ givesThe sum of the nontrivial character $\chi$ over all nonzero residue classes is zero. Because its two half-sums are equal when $\chi (-1)=1$,Hence