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

A reduced positive definite binary quadratic form $a{x}^2+bxy+c{y}^2$ satisfies $|b|\le a\le c$, with $b\ge 0$ when $|b|=a$ or $a=c$. These inequalities select representatives under proper equivalence of binary quadratic forms; the changes of variables have integer entries and determinant $1$.

For the first binary quadratic form, put $x=u-v$, $y=v$. For the second, put $x=-u-3v$, $y=u+2v$. Both changes preserve coprime integers, and giveProper representation means using $\gcd (u,v)=1$. For $f$, $|v|\ge 2$ gives a value greater than $5$, while $v=0$ forces $u=\pm 1$. For $|v|=1$, the smallest values are $4$ and $5$. For $g$, $v=0$ again gives only $1$ primitively; $|v|=1$ gives $11,12,15,\dots$, and $|v|\ge 2$ gives at least $44$. Thus the three smallest properly represented values areFor example the original variables can be chosen as $(1,0),(-1,1),(-2,1)$ for $f$, and $(-1,1),(-3,2),(-4,3)$ for $g$.

Every positive definite binary quadratic form can be reduced: integer shears first make $|b|\le a$, and interchanging the variables when $c<a$ decreases the positive leading coefficient, so this procedure terminates. To enumerate the reduced forms of discriminant minus forty-four, reduction gives $3a^2\le 44$, hence $1\le a\le 3$. Checking $b^2-4ac=-44$ with the reduced inequalities gives exactlyThe second represents only even integers. The last two have the same represented values, by $u\mapsto -u$. The first and third are the reduced versions of $g$ and $f$. Therefore every represented odd integer occurs in at least one of $f,g$, whether or not its original representation was primitive.

Let $\mathcal{A}$ be the closure of the polynomials in $C(K)$ for the uniform norm. It is a closed algebra, since products of uniformly convergent sequences converge uniformly on the compact set $K$.

Choose a point $W$ with $|W|>{\sup }_{z\in K}|z|$. The uniformly convergent geometric seriesshows that this reciprocal belongs to $\mathcal{A}$. Join $w$ to $W$ by a continuous path in $\mathbb{C}\setminus K$. Its image is compact and disjoint from $K$, so their distance $d$ is positive. Partition the path into finitely many steps shorter than $d/2$.

Suppose $1/(b-z)\in \mathcal{A}$ and $|a-b|<d/2$, with $b$ on the path. Thenconverges uniformly on $K$, since $|b-z|\ge d$. Every partial sum belongs to $\mathcal{A}$, by its algebra property, and so does the limit. Working backwards along the partition transfers the pole from $W$ to $w$. Thus $1/(w-z)\in \mathcal{A}$: a polynomial $P$ exists withThis pole-moving polynomial approximation is the elementary mechanism behind the polynomial Runge theorem.

Order the prescribed lengths as $l_1\le \cdots \le l_N$. Construct a prefix code on the binary tree. At depth $l_i$, previously assigned codewords exclude ${\sum }_{j<i}{2}^{l_i-l_j}$ of the $2^{l_i}$ vertices. The Kraft inequality impliesso an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required uniquely decodable code.

For completeness the same length inequality is necessary even for a uniquely decodable code which is not a prefix code. Write $K={\sum }_a{2}^{-l(a)}$ and $L={\max }_{a}l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. ThereforeTaking $r$th roots and letting $r\to \infty$ gives $K\le 1$. This is the McMillan inequality.

Set $q(a)=2^{-l(a)}/K$. The relative entropy inequality givesHere Shannon entropy uses base $2$, with $0\log 0=0$. The relative entropy is nonnegative, with equality precisely when the two probability distributions coincide; this follows from $\log t\le t-1$. Consequently equality holds exactly whenIn particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.

The command fits the simple linear regressionusing ordinary least squares. The fitted conditional mean is a straight line in time. The regression residuals are mainly positive at the beginning and end and negative in the middle, so the mean function needs curvature.

A direct improvement is polynomial regression of degree two:The nested-model F-test tests $H_0:{\beta }_2=0$ against a nonzero quadratic coefficient. If $N$ measurements were used, its statistic isA small reported $p$-value supports the quadratic term. The new regression residuals should then be checked for remaining systematic structure, changing variance and temporal dependence, because the F-test assumes independent errors of common variance. Radioactive decay also motivates an exponential mean, but the displayed curvature already justifies this simple nested comparison.

There are $k{x}_n$ seeds and their germinating proportion is $e^{-\gamma x_n}$, giving the survival-augmented Ricker map with zero survival. A positive equilibrium point satisfies $e^{-\gamma x_{\ast }}=1/k$, soIt exists when $k>1$ and is strictly linearly stable when $|1-\log k|<1$. Thus the usual strict linear-stability interval is $\boxed{1<k<e^2}$.

With winter survival, surviving adults and new plants add:Writing $L=\log [k/(1-s)]$, the linearization of a dynamical system has multiplier $1-(1-s)L$. Hence the strict linear-stability interval becomesIts lower endpoint is less than $1$. Its upper endpoint exceeds $e^2$: for $t=1-s\in (0,1)$, $\log t+2/t$ is decreasing in $t$ and equals $2$ at $t=1$.

The nonlinear stability at the Ricker flip threshold needs a separate check. The upper endpoints have multiplier $-1$, so the strict linear test alone does not decide stability there. They are in fact locally asymptotically stable, with algebraic rather than geometric convergence. To see this, put $u=\gamma (x-x_{\ast })$ at $L=2/(1-s)$. The local map isand its second iterate is $u-2(s^2-s/2+1/6)u^3+O(u^4)$. The cubic coefficient in parentheses is positive for every $s\in [0,1)$. Thus, if “stable” includes nonlinear endpoint stability, the upper inequalities can be replaced by $\le$; the lower endpoints have no positive equilibrium.

Use equal small excisions on the two sides of each real pole. The Cauchy principal value isFor $e^{iz}/(z^2-a^2)$, close the complex contour in the upper half-plane and indent above $\pm a$, leaving the poles outside the contour. The residue theorem and the vanishing of the large semicircle integral give the principal-value integral as $i\pi$ times the sum of the two real-pole residues. Each clockwise indentation contributes $-i\pi$ times its residue. Sincethe sum is $i\sin a/a$. Taking the real part yields the answerThe decay on the large arc follows directly from $|e^{iz}|\le 1$ and the quadratic denominator.

The Hamiltonian is $\boxed{H(q,p)=p^2/(2m)+V(q)}$. On a regular family of closed phase-space trajectories, action-angle variables are canonical coordinates $(\theta ,I)$ in which $\theta$ is periodic modulo $2\pi$ and $H=H(I)$. Hamilton's equations then give $\dot{I}=0$ and $\dot{\theta }=dH/dI$.

The action variable isThe orientation is that of the motion, so the integral is the positive enclosed phase-space area divided by $2\pi$.

A constant-energy phase-space trajectory of the harmonic oscillator is the ellipseIts area is $\pi \sqrt{2E/(m{\omega }^2)}\sqrt{2mE}=2\pi E/\omega$. Thus the action and slow energy change areThe action variable is an adiabatic invariant when $|\dot{\omega }|\ll {\omega }^2$, with $\omega$ staying positive. Averaging over many short oscillations therefore keeps $I$ approximately fixed; an increase in frequency increases the energy in the same proportion.

The Flatness problem is the extreme closeness to spatial flatness required in the early universe if ordinary decelerating expansion is to produce the observed near-flat universe. From the Friedmann equation, with $c=1$ and curvature constant $k$,During decelerating expansion $|\Omega -1|$ grows. The Friedmann acceleration equation gives $\ddot{a}/a=-4\pi G(\rho +3P)/3$. Thus $\rho +3P<0$ makes an expanding universe accelerate, increases $\dot{a}$ and suppresses $|\Omega -1|$: this is the inflationary solution of the flatness problem.

The slow-roll approximation neglects ${\dot{\varphi }}^2/2$ compared with $V$ and $\ddot{\varphi }$ compared with $3H\dot{\varphi }$. For the positive-field branch, taking $m>0$,Integrating the field equation and $\dot{a}/a=H$ gives the slow-roll solutionThe potential slow-roll parameters are ${ϵ}_V={\eta }_V=2/{\varphi }^2$. They cease to be small when $\varphi$ is of order $1$ in these units; the customary endpoint ${ϵ}_V=1$ is $\boxed{{\varphi }_{\mathrm{end}}\simeq \sqrt{2}}$. Equating the approximate kinetic and potential energies instead gives $\sqrt{2/3}$, another order-one indicator, not a precise endpoint of an approximation that is already failing.

For a simple continued fraction, defineMultiplying the matrices $\left(\begin{array}{cc}{a}_j& 1\\ 1& 0\end{array}\right)$ givesTheir determinants also give $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$. If the infinite tail is $\beta =[a_{n+1},a_{n+2},\dots ]>a_{n+1}$, the same formula impliesThe denominators of these continued fraction convergents tend to infinity, since $q_{n+2}\ge q_{n+1}+q_n$. Hence they converge to $\theta$.

The square-root algorithm for the periodic continued fraction of a quadratic irrational, using $M^{\prime }=Da-M$, $D^{\prime }=(53-M^{\prime 2})/D$ and $a^{\prime }=\lfloor (7+M^{\prime })/D^{\prime }\rfloor$, givesThe first four continued fraction convergents are $7/1,22/3,29/4,51/7$. Direct substitution gives positive solutions to the requested Pell-type equations:

Work in the complete Banach space $C([0,1])$ with the uniform norm. Each $E_m$ is closed. Indeed if $f_j\to f$ uniformly and $x_j$ witnesses membership in $E_m$, pass to a subsequence with $x_j\to x$. For each $y\in [0,1]$, uniform convergence and continuity giveThus $x$ witnesses membership for $f$.

Each $E_m$ has empty interior. Approximate an arbitrary $f$ uniformly by a piecewise-linear function $q$ on a uniform mesh, and let $D$ bound the absolute slopes of $q$. On a sufficiently fine uniform refinement of mesh $\delta$, add a triangular oscillation of fixed small amplitude $b$, alternating between $b$ and $-b$ at successive vertices. The resulting function $g$ is still as close to $f$ as desired, and every segment has absolute slope at least $2b/\delta -D$. For any $x$, choose the farther endpoint of a segment containing $x$. Its distance $h$ is between $\delta /2$ and $\delta$, sowhen $\delta$ is small. Therefore $g\notin E_m$.

By the Baire category theorem, the complement of ${\bigcup }_m{E}_m$ is dense and nonempty. If the local limsup in the question were finite at some $x$, its nearby differences would satisfy a finite bound. The remaining differences, with $|h|\ge \delta >0$, are bounded by $2\Vert f{\Vert }_{\infty }{\delta }^{-\alpha }$. Combining the bounds would put $f$ in some $E_m$, a contradiction. Hence the required limsup is infinite at every point, including one-sided approaches at the endpoints.

True. Apply the preceding Baire category theorem argument simultaneously to $\alpha =1/j$, $j\ge 1$. The union of all the corresponding $E_{m,j}$ is still a countable union of closed sets with empty interior, so its complement is nonempty. For any $\alpha >0$, choose $j$ with $1/j\le \alpha$. For $0<|h|\le 1$,The right-hand limsup is infinite at every $x$, proving the assertion for every positive exponent.

False. At $\alpha =0$, continuity givesat every $x$, so the requested infinite limsup is impossible.

Let $N=x+y$. Uninfected births and density limitation give $x(1-N)$, while horizontal transmission transfers individuals to the infected class at rate $\beta xy$. Infected births are infected by vertical transmission, and their net demographic growth is $y(1-N)-dy$. ConsequentlyThese give the stated equations. Adding them gives $\dot{N}=N(1-N)-dy$, displaying the additional mortality due to disease.

At the disease-free equilibrium point $(1,0)$, the linearization of a dynamical system of the infected equation is $\dot{y}=(\beta -d)y$. Thus exponential invasion occurs exactly when $\boxed{\beta >d}$. At equality there is no positive linear growth rate; the nonlinear boundary dynamics described below do not give sustained invasion.

Assume first $\beta >0$ and $d\ge 0$. The nonnegative equilibrium points areand, when both coordinates are nonnegative,The Jacobian matrix at $O$ has eigenvalues $1,1-d$, so $O$ cannot attract an initially positive uninfected population. At $U$ the eigenvalues are $-1,\beta -d$. At $I$, for $d<1$, they are $d(1+\beta )-\beta$ and $-(1-d)$. At an interior $C$, the equilibrium equations reduce the Jacobian matrix toThus the coexistence equilibrium is asymptotically stable precisely when $\beta /(1+\beta )<d<\beta$.

For positive initial populations these local results identify the global outcome. The relation $\dot{N}=N(1-N)-dy$ bounds all trajectories. With the Dulac function $1/(xy)$, the divergence of the rescaled vector field is $-1/y-1/x<0$, excluding interior periodic orbits. Boundary saddles cannot attract an interior trajectory except at the merging thresholds. The resulting long-term outcomes areAt $d=\beta /(1+\beta )$, $C$ merges into $I$; at $d=\beta$, it merges into $U$. The merged equilibria still attract interior trajectories, but convergence along the zero-eigenvalue direction is algebraic. For example at $d=\beta$, put $x=1+u$, $y=v$. The local centre manifold has $u=-(1+\beta )v+O(v^2)$, and $\dot{v}=-{\beta }^2{v}^2+O(v^3)$. At the other threshold, using $y=(1-d)+v$, $x=u$, gives $v=(\beta -1)u+O(u^2)$ and $\dot{u}=-{\beta }^2{u}^2+O(u^3)$.

The invariant axes also matter: $y=0$ leads to $U$ whenever $x(0)>0$; $x=0$ leads to $I$ for $d<1$ and to extinction for $d\ge 1$. At $d=1$, $I$ coincides with $O$. If $\beta =0$, disease declines for $d>0$ and any initially positive $x$ tends to $U$. If also $d=0$, every point $x+y=1$ is an equilibrium and the initial population proportions are preserved.

For $\beta >0$ and positive initial populations, summing the coordinates of the attracting equilibrium point gives the steady total populationIts minimum is $1/(1+\beta )$ at $d=\beta /(1+\beta )$. Small mortality leaves a fully infected population with only modest demographic loss. Raising mortality first reduces that population; after the threshold it suppresses infection sufficiently for the uninfected population to recover. Beyond the invasion threshold the disease cannot persist.

The terms in the Boltzmann equation respectively describe dilution by expansion, pair annihilation, and pair production from the thermal bath. The annihilation rate per volume is $⟨\sigma v⟩n\bar{n}$; $P(t)$ is the corresponding production rate. Antiparticles satisfy the same equation with $n$ replaced by $\bar{n}$. Subtracting givesInitial particle-antiparticle symmetry therefore persists. Detailed balance in the thermal bath gives $P=⟨\sigma v⟩n_{\mathrm{eq}}^2$, soDuring radiation domination, with fixed effective relativistic degrees of freedom, $T\propto a^{-1}$ and $H=H_m/x^2$. Thus $\dot{x}=Hx$ and the dilution terms cancel in $Y=n/T^3$:After cosmological particle freeze-out, neglect $Y_{\mathrm{eq}}$. For constant $\lambda$ the exact reduced solution isFor the post-freeze-out relic abundance, the familiar answer $Y_{\infty }\simeq x_f/\lambda$ additionally neglects $1/Y_f$ compared with $\lambda /x_f$. It is an approximation, not an exact consequence of the post-freeze-out equation without initial data. A smaller annihilation cross-section means smaller $\lambda$, earlier decoupling and less depletion, so weakly interacting particles normally have a larger relic abundance.

Zorn lemma states that a nonempty partially ordered set in which every chain in a partial order has an upper bound has a maximal element. Here is a proof from the axiom of choice and Hartogs theorem.

Suppose there is no maximal element. Every chain $C$ has a strict upper bound: choose an upper bound $b$ and then an element strictly greater than $b$. The family of sets of strict upper bounds is a set of nonempty subsets of the underlying set $P$. The axiom of choice is used here to choose, simultaneously for every chain $C$, one strict upper bound $b(C)$.

By Hartogs theorem there is an ordinal $\kappa$ admitting no injection into $P$. Transfinite recursion defines $x_{\alpha }$ for $\alpha <\kappa$ byAt each stage the previous elements form a chain, and $x_{\alpha }$ is strictly above every one of them. Hence $\alpha \mapsto x_{\alpha }$ is an injection $\kappa \to P$, a contradiction. Therefore a maximal element exists.

Replace the strict partial order by its reflexive closure $\le$. Partially order all partial orders on $X$ extending $\le$ by inclusion. A chain has an upper bound given by its union: transitivity and antisymmetry each concern finitely many pairs, which all lie in one member of the chain. By Zorn lemma there is a maximal extension $R$.

If $a,b$ are incomparable under $R$, defineThis adds $a{R}^{\prime }b$. It is transitive: composing an old pair with a new one stays in the added set; composing two new pairs would require $bRa$, which is impossible. It is antisymmetric: an added pair and a reverse old pair would again imply $bRa$, and two reverse added pairs would do the same. Thus $R^{\prime }$ is a larger partial order, contradicting maximality. Therefore $R$ is total, and removing its diagonal gives a total order extending the original strict order.

A well-founded relation has a minimal element in every nonempty subset; with the axiom of choice this is equivalent to having no infinite strictly descending sequence. If an extension is a well-order, its least element in any nonempty subset is minimal for the original relation, so the original order must be well-founded.

However not every total extension need be a well-order. Take the empty strict order on $\mathbb{N}$, which is well-founded. Its extension defined by $x\prec y$ if $x>y$ in the usual order is total and has no least element.

A Hamilton cycle is a cycle graph which visits every vertex of a finite graph exactly once, apart from returning to its starting vertex. A graph is Hamiltonian when it contains such a cycle.

Let $v_1\cdots v_k$ be a longest path. Every neighbour of either endpoint lies on it. Among the $k-1$ indices $i=1,\dots ,k-1$, mark those with $v_1{v}_{i+1}$ an edge and those with $v_i{v}_k$ an edge. Their total number isso some index has both marks. The edges at that index close the path into the cycle graphThe minimum-degree hypothesis also forces the graph to be a connected graph: each component would otherwise have at least $n/2+1$ vertices. If $k<n$, an edge from this cycle to an outside vertex would give a longer path by opening the cycle at its incident vertex. Hence $k=n$, proving the Dirac theorem and Hamiltonicity.

The bound is sharp. For $n=2m$, take two disjoint copies of $K_m$, with minimum degree $m-1$. For $n=2m+1$, take two copies of $K_{m+1}$ sharing exactly one vertex. The minimum degree is $m$, but the shared vertex is a cut vertex, which no Hamiltonian graph can have. Both constructions have

Add missing cross-edges to a hypothetical non-Hamiltonian balanced bipartite graph until it is maximal with that property. The complete bipartite graph is Hamiltonian for $n\ge 2$, so a missing cross-edge $uv$ remains. Adding it creates a Hamilton cycle, and removing it gives a Hamilton pathFor each $i$, consider the conditions $u{B}_i\in E$ and $A_{i}v\in E$. Since $\mathrm{deg}u+\mathrm{deg}v>n$, they hold together for some $i$. Following the path from $u$ to $A_i$, crossing to $v$, following the remaining path backwards to $B_i$, and crossing back to $u$ gives a Hamilton cycle already in the original maximal graph. This contradiction proves the stated Hamiltonicity criterion.

For $n=2m$, two disjoint copies of $K_{m,m}$ have $n$ vertices in each class and minimum degree $m$. For $n=2m+1$, the disjoint union $K_{m,m+1}\bigsqcup K_{m+1,m}$ has $n$ vertices in each class and minimum degree $m$. Both are disconnected and hence non-Hamiltonian. Thus the sharp counterexamples have $\boxed{\delta =\lfloor n/2\rfloor }$ for every $n\ge 2$.

For a finite group $G$, subgroups $H,K$, and a complex group representation $V$ of $H$, the Mackey restriction formula isChoose one representative $g$ of each double coset $KgH$. The conjugate subgroup representation ${}^{g}V$ is a representation of $gH{g}^{-1}$ on the same vector space, with $(gh{g}^{-1})v=hv$. Restriction of a representation keeps the vector space and restricts the acting subgroup. induced representation is $\mathbb{C}G{\otimes }_{\mathbb{C}H}V$, and analogously for each subgroup of $K$. The displayed isomorphism is an isomorphism of $K$-representations. These definitions specify every summand and its subgroup.

If $G$ is $n$-transitive, it is transitive by extending one-element tuples to $n$-tuples. Apply $n$-transitivity to tuples beginning with $\omega$ to see that the stabilizer subgroup $G_{\omega }$ is $(n-1)$-transitive on the remaining elements.

Conversely, given two ordered $n$-tuples of distinct elements, transitivity first supplies $g$ carrying their first entries to each other. Conjugating the given stabilizer hypothesis shows that the stabilizer of the target first entry is $(n-1)$-transitive. An element of that stabilizer then maps the remaining entries of the image tuple to their targets. Composing the two elements proves $n$-transitivity. For $n=1$, the condition on zero-tuples is vacuous.

For finite nonempty $\Omega$, let $e_{\omega }$ be the basis vectors of the permutation representation. PutThe line $\mathbb{C}u$ is fixed by $G$, and $V$ is the augmentation subrepresentation of a permutation representation. Since $|\Omega |\ne 0$ in $\mathbb{C}$, they have zero intersection and their dimensions add to $|\Omega |$. Hence $\boxed{\mathbb{C}\Omega \cong {\mathbb{C}}_G\oplus V}$.

The printed formulation does not explicitly require $\Omega$ to be finite. For an infinite nonempty $G$-set, interpret $\mathbb{C}\Omega$ as finite-support vectors. Choose one finite orbit $O$ (all orbits are finite because $G$ is finite), replace $u$ by ${\sum }_{\omega \in O}{e}_{\omega }$, and use the same augmentation kernel. This again splits off a trivial summand. The nonempty-set assumption is needed; the empty permutation module contains no trivial summand.

As printed, the equivalence needs a transitivity hypothesis. A group acting trivially on two points has $\mathbb{C}\Omega ={\mathbb{C}}_G\oplus {\mathbb{C}}_G$, so $V$ is one-dimensional and irreducible, although the action is not even transitive.

Here is the intended result for a transitive action. The set is then finite, and, for a point stabilizer $H$, its permutation character is $\chi ={\mathrm{Ind}}_H^{G}1$. Frobenius reciprocity givesThe last equality follows because an $H$-fixed vector has constant coefficients on each orbit. There is exactly one trivial constituent, since the action is transitive. Therefore, writing $\chi =1+\psi$ for the character of $V$,By character orthogonality, $V$ is irreducible exactly when this equals $1$. One stabilizer orbit is $\{\omega \}$, so this happens exactly when $H$ is transitive on $\Omega \setminus \{\omega \}$, equivalently when $G$ is two-transitive. Moreover $V$ is not trivial, since a transitive action has only one independent fixed vector in the whole permutation module.

The complete correction without assuming transitivity is also precise: $V$ is irreducible exactly for a two-transitive action or the exceptional action on two fixed points. Indeed for a finite set with $r$ orbits, the fixed subspace of $V$ has dimension $r-1$. If $r>1$ and $V$ is irreducible, $V$ must itself be a one-dimensional trivial module, forcing $|\Omega |=2$ and $r=2$. If $\Omega$ is infinite, $V$ is infinite-dimensional and cannot be irreducible: any nonzero vector generates a submodule of dimension at most $|G|$.