Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3

Starting with ${\theta }_0=\theta$, definewhile the denominator is nonzero. This gives the simple continued fractionA finite expansion is rational by evaluating it from the bottom. Conversely, for rational $\theta$, these steps are the Euclidean algorithm applied to numerator and denominator, so the remainders eventually vanish.

Define convergents byThe recurrence givesso induction yieldsIn particular,Since an irrational $\theta$ lies strictly between these convergents, the two approximation errors sum to this distance. If both displayed bounds in the question failed, their sum would be at leastby the arithmetic-geometric mean inequality, contradicting strict betweenness. Thus at least one bound holds.

Runge approximation theorem in its polynomial form says that if $K\subset \mathbb{C}$ is compact with connected complement and $f$ is holomorphic on a neighborhood of $K$, then polynomials approximate $f$ uniformly on $K$.

True when “uniform” means on all of the unbounded quadrant $\Omega$. A uniformly convergent sequence $(P_n)$ is uniformly Cauchy. For sufficiently large $m,n$, the polynomial $P_n-P_m$ is bounded on $\Omega$. Every nonconstant polynomial is unbounded along some ray contained in $\Omega$, so $P_n-P_m$ is constant. Fixing one large $m$, the limit is therefore $P_m$ plus the limit of constants, hence is a polynomial.

True. Exhaust the quadrant by compact sets $K_n$ with connected complements and with every compact subset of $\Omega$ eventually contained in the interior of $K_n$. Runge's theorem gives a polynomial $P_n$ satisfyingThus $P_n\to f$ locally uniformly. For a fixed $z\in \Omega$, choose a small circle about $z$ eventually contained in every $K_n$. The Cauchy integral formula for derivatives applied to $P_n-f$ givesfor every $r\ge 0$.

Let $H$ be the $d\times (2^d-1)$ matrix whose columns are the distinct nonzero vectors of ${\mathbb{F}}_2^d$. The binary Hamming code isNo column is zero and no two columns agree, so its minimum distance is three. A radius-one Hamming ball containswords, while $|C|=2^{2^d-1-d}$. The radius-one balls about codewords are disjoint and their total size is $2^{2^d-1}$, so they partition the ambient space. Hence $C$ is a perfect code.

Let the received word be all ones except in the last coordinate. The sum of all nonzero vectors of ${\mathbb{F}}_2^d$ is zero for $d\ge 2$, so its syndrome is the last column of $H$. Minimum-distance decoding therefore flips the last bit and returns the all-one word. A Hamming code corrects every single error because each nonzero syndrome identifies its unique erroneous coordinate.

A regular expression is built from $\varnothing$, $ϵ$, and alphabet symbols using union, concatenation, and Kleene star; its language is defined by applying the corresponding set operations recursively. A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ and acceptsKleene theorem says that the languages denoted by regular expressions are exactly those accepted by finite automata.

Regular languages are closed under finite union, using a product automaton or nondeterministic choice, and under finite intersection, using the product automaton with accepting set $F_L\times F_M$.

They are not closed under countable unions or intersections. Every language over a finite alphabet is a countable union of singleton languages, each regular, so a nonregular language such as $\{a^n{b}^n:n\ge 0\}$ is a counterexample. It is alsoa countable intersection of regular languages, giving the second counterexample.

Assume $X$ has full column rank. The log-likelihood, up to constants, isThe ordinary least squares normal equations giveand maximizing over the variance gives the maximum-likelihood estimatorBecause $I-H$ is an orthogonal projection of rank $n-p$,Writing ${\chi }_{\nu ,q}^2$ for the $q$-quantile, a confidence interval of level $1-\alpha$ is

The boundary condition says that all newborn individuals enter at age zero, and that their influx equals the total birth rate obtained by summing the age-specific births $b(a)n(a,t)$ over the population.

Put $n(a,t)=A(a)T(t)$. Separation givesfor a constant $r$. Hence

Substitution into the renewal boundary condition and cancellation of $A_{0}T(t)$ gives the Euler-Lotka equationThis is the necessary condition selecting the growth exponent $r$.

For $b(a)=\beta e^{-\lambda a}$ and constant death rate $d$,ThusA separable solution exists with this exponent, and it grows precisely when

The substitution $t\mapsto 1-t$ gives $B(p,q)=B(q,p)$. Direct integration gives

Integration by parts, or the identities obtained by splitting $1=t+(1-t)$, givesTherefore

For any $z\notin \{0,-1,-2,\dots \}$, choose $N$ with $\mathrm{Re}(z+N)>0$ and defineThe recurrence makes this independent of $N$ and agrees with the original integral where $\mathrm{Re}z>0$. It is the desired analytic continuation away from the listed points.

Usingwe see that $z=-n$ is generally a simple pole, inherited from $\Gamma (z)$. A cancellation occurs exactly when $p-n$ is a nonpositive integer. Thus $z=0$ is always a simple pole; for $n\ge 1$, $z=-n$ is removable when $p$ is one of $1,2,\dots ,n$, and otherwise is a simple pole.

The scalar and vector potentials satisfyThe canonical momentum and Hamiltonian areFor the uniform fields choosewhich produces the stated Hamiltonian. Since it is time independent and $y,z$ are cyclic coordinates, three independent conserved quantities are

InsertMatching powers of $t$ requires $\lambda \alpha =2$, so $\alpha =2/\lambda$. Writing $\overline{V}=V_0{e}^{-\lambda {\varphi }_0}$, the scalar equation and Friedmann equation giveThusExistence with positive potential requires $\gamma >1/3$, or ${\lambda }^2<48\pi G$. Accelerated expansion requires $\gamma >1$, hence

Multiplying the inflaton equation by $\dot{\varphi }$ givesComparison with $\dot{\rho }+3H(\rho +P)=0$ yields $\rho +P={\dot{\varphi }}^2$, and therefore

The acceleration equation requires $\rho +3P<0$, so $w=P/\rho <-1/3$. A canonical scalar field with nonnegative potential obeys $P\ge -\rho$. Hence inflation occurs for

Without Alice's operation, Bob obtains outcome $b$ with probabilityIf Alice applies $U$ and then measures, but her outcome is not communicated, Bob's probability isbecause ${\sum }_a{\Pi }_a=I_A$. Equivalently, a trace-preserving local operation leaves Bob's reduced density matrix unchanged. This is the no-communication theorem: local operations cannot signal without communication of their outcomes.

Two integral binary quadratic forms are properly equivalent when one is obtained from the other by a change of variables in $S{L}_2(\mathbb{Z})$. For a negative discriminant $d\equiv 0,1(\mathrm{mod}4)$, the class number of binary quadratic forms $h(d)$ is the number of proper equivalence classes of primitive positive-definite forms of discriminant $d$.

If $f$ properly represents $m$, then $f(r,s)=m$ for coprime $r,s$. Extend $(r,s{)}^T$ to a matrix in $S{L}_2(\mathbb{Z})$; after the associated variable change, the coefficient of $x^2$ is $m$, so the transformed form isThe converse follows by evaluating this form at $(1,0)$.

Such a form has discriminant $d$ precisely whenso it exists exactly when $b^2\equiv d(\mathrm{mod}4m)$. Thus $m$ is properly represented by some form of discriminant $d$ exactly when $d$ is a square modulo $4m$.

Now let $d=1-4A$. If $n^2+n+A$ is composite for $0\le n\le A-2$, it has a prime divisor $p<A$, andConversely, if $d$ is a square modulo $4p$ for a prime $p<A$, choose an odd square root $2n+1$ with $0\le n<p$. Then $p\mid n^2+n+A$ and $n\le A-2$, so that value is composite.

Finally, reduction theory says that every nonprincipal positive-definite class of discriminant $1-4A$ has a reduced representative whose leading coefficient has a prime divisor $p<A$ for which $d$ is a square modulo $4p$. Conversely such a prime produces a represented form not equivalent to the principal form $x^2+xy+A{y}^2$. Combining this with the preceding equivalence gives

A parse tree has the start variable at its root; the ordered children of a variable spell the right side of the production used at that occurrence, and its leaves, read left to right, spell the derived word.

For a grammar in Chomsky normal form with $r$ variables, take pumping length $p=2^r$. A parse tree for a word of length at least $p$ has a root-to-leaf path containing one variable twice. The yield can therefore be writtenwhere $|vxy|\le p$, $|vy|>0$, and replacing the subtree between the repeated variables zero, one, or several times provesThis is the pumping lemma for context-free languages. Without Chomsky normal form but with no epsilon or unit productions, use the maximum production length to choose a larger exponential $p$; bounded branching and the same repeated-variable argument apply.

The language $\{a^i{b}^i{a}^i:i\ge 0\}$ is not context free. A pumped window of bounded length cannot alter all three long blocks equally, so pumping breaks one of the required equalities.

The language $\{a^i{b}^j:i\ge j\ge 0\}$ is context free. For example the grammargenerates $a^{j+k}{b}^j$ with $j,k\ge 0$, and every required word has this form.

The language $\{wabw:w\in \{a,b{\}}^{\ast }\}$ is not context free. Intersecting with a suitable regular language that forces both copies into long homogeneous blocks reduces to a marked copy language; the context-free pumping lemma then places the two pumped pieces within only finitely many local blocks and cannot change the two copies identically. Equivalently, the standard copy-language proof applies with the fixed marker $ab$.

The term ${\lambda }_i{S}_i$ moves susceptible people in group $i$ into its infective class, while $\gamma I_i$ moves infectives into recovery. In$C_{ij}$ is the contact rate of a person in group $i$ with group $j$, and $I_j/N_j$ is the infectious fraction there. The reciprocity condition $N_i{C}_{ij}=N_j{C}_{ji}$ says that the total number of $i$--$j$ contacts agrees when counted from either group. Common $\beta$ and $\gamma$ mean age-independent transmission per infectious contact and recovery rate. There is no transmission between distinct age groups exactly when

With $S_i\simeq N_i$, the infective equations becomewhere reciprocity was used. For a column vector $\mathbf{I}$,Therefore

Since $C$ and $C^T$ have the same eigenvalues, an exponentially growing mode exists precisely when $L$ has an eigenvalue with real part greater than one. For the nonnegative contact matrix this iswhere $\rho (C)$ is the spectral radius.

Substituting $P=\rho /3$ into the continuity equation givessoThree powers arise from dilution of photon number in physical volume and one from the cosmological redshift of each photon's energy.

The positive-curvature term identifies $R$ as the curvature radius of the spatial three-sphere when the dimensionless scale factor is $a=1$; the physical curvature radius is $Ra(t)$.

Put $a=\alpha \tilde{a}$ withThenFor $y={\tilde{a}}^2$ this becomesThe expanding big-bang branch hasDifferentiation givesThus, with $\omega =\sqrt{4\Lambda /3}$,where the initial derivative givesFor $\lambda >1$, $\tilde{a}$ expands forever and becomes asymptotically exponential. For $\lambda <1$, it reaches a maximum and recollapses to zero. At $\lambda =1$, $y$ increases monotonically to $3/(2\Lambda )$, the limiting static radius.

Writewhere $|\beta ⟩$ is the normalized component orthogonal to $|x_0⟩$. On this real plane, $I_{x_0}$ is reflection in the line perpendicular to $|x_0⟩$, whileis reflection in the line spanned by $|{\psi }_0⟩$. Their product $Q=-J{I}_{x_0}$ is a rotation through $2\theta =\pi /3$ toward $|x_0⟩$. This is the geometric core of Grover search.

Prepare $|{\psi }_0⟩=H^{\otimes 2}|00⟩$. One query to $U_f$, with phase kickback, implements $I_{x_0}$. The reflection $-J$ is independent of $f$ and can be implemented by conjugating the phase flip of $|00⟩$ with $H^{\otimes 2}$. Since $|{\psi }_0⟩$ begins at angle $\theta =\pi /6$ from the unmarked direction, one Grover iterate rotates it by $2\theta$ and givesA computational-basis measurement therefore determines $x_0$ with certainty after one oracle query.

Let $a=\Vert {\Pi }_A\xi \Vert$ and $b=\Vert {\Pi }_{A^{\perp }}\xi \Vert$. Since $a^2+b^2=1$, choose $\theta \in [0,\pi /2]$ with $a=\sin \theta$, $b=\cos \theta$. Normalizing the two nonzero projections givesAt an endpoint, the unused normalized vector may be chosen arbitrarily in its subspace.

Since $I_A|\alpha ⟩=-|\alpha ⟩$,Substituting the decomposition of $|\xi ⟩$ and using the double-angle identities gives

The two stated formulas show that $Q$ rotates the $(|\beta ⟩,|\alpha ⟩)$ plane by $2\theta$. Starting from $|\xi ⟩$, whose angle from $|\beta ⟩$ is $\theta$, two iterations give angleHence $Q^2|\xi ⟩=|\alpha ⟩$. The reflection about $|\xi ⟩$ is implementable asThus apply $U$ to $|0\cdots 0⟩$, followed by two applications of $-I_{\xi }{I}_A$. This prepares $|\alpha ⟩$ exactly and deterministically.

For cardinals, $\kappa <\lambda$ means that there is an injection $\kappa \to \lambda$ but no bijection. Under the axiom of choice, every set is well-orderable, so every infinite cardinal is the initial ordinal ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$. Cantor theorem givesand minimality of the successor cardinal givesThe strict inequality ${\aleph }_{\alpha +1}<2^{{\aleph }_{\alpha }}$ printed in the conversion is not provable and can be false under the generalized continuum hypothesis; the intended symbol must be $\le$.

The map $a\mapsto \{a\}$ injects $x$ into $\mathcal{P}(x)$. Cantor's diagonal argument shows that no map $x\to \mathcal{P}(x)$ is surjective: for $f:x\to \mathcal{P}(x)$, the set $D=\{a:a\notin f(a)\}$ differs from every $f(a)$. Hence $\kappa <2^{\kappa }$.

If $f:x\to y$ is surjective, inverse image gives an injectionFor every infinite initial ordinal ${\omega }_{\alpha }$, transfinite recursion constructs a pairing of ${\omega }_{\alpha }\times {\omega }_{\alpha }$ with ${\omega }_{\alpha }$: at each stage fewer than ${\aleph }_{\alpha }$ earlier pairs have been used. Thuswithout invoking choice for arbitrary families.

Every ordinal below ${\omega }_{\alpha +1}$ has cardinal at most ${\aleph }_{\alpha }$ and can be coded by a well-ordering relation on a subset of ${\omega }_{\alpha }$. Sending such a relation to its order type, and all non-well-orders to zero, gives a surjectionUsing the pairing above to code relations as subsets of ${\omega }_{\alpha }$ yieldsAgain, strictness beyond this is independent of the usual axioms.

The diagonal Ramsey number $R(k)$ is the least $n$ such that every red-blue coloring of $K_n$ contains a monochromatic $K_k$. The standard recursiongivesThus the converted $k^4$ is a superscript-order error; that bound is false for large $k$.