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

For every odd prime $p$ and $n\ge 1$, the group of units modulo an integer $(\mathbb{Z}/p^n\mathbb{Z}{)}^{\times }$ is a cyclic group, of order $\phi (p^n)=p^{n-1}(p-1)$; a generator is a primitive root.

Modulo seven, $3,3^2,\dots ,3^6$ are $3,2,6,4,5,1$, so three has order six. Moreover $3^6-1=728=7\cdot 104$ is divisible by seven exactly once. We prove the lifting needed here. If $u=1+7^{r}v$ with $r\ge 1$ and $7\nmid v$, the binomial expansion gives $u^7=1+7^{r+1}v+O(7^{r+2})$, so $v_7(u^7-1)=r+1$. Induction therefore givesAny exponent giving one modulo $7^n$ is divisible by six. The order also divides $6\cdot 7^{n-1}$ by Lagrange theorem, while the displayed valuation rules out each proper divisor of this form. Consequently three is a primitive root modulo every $7^n$.

Since $2^3=1(\mathrm{mod}7)$ and two is not one, its order modulo seven is three. A generator modulo $7^n$ would reduce to a generator modulo seven, because reduction is a surjective group homomorphism. Thus two is never a primitive root modulo $7^n$. Finally every unit modulo eight is odd, and $(2k+1{)}^2=1+4k(k+1)\equiv 1(\mathrm{mod}8)$. All unit orders are at most two, whereas the unit group has four elements. There is no primitive root modulo eight.

The Brouwer fixed-point theorem says that every continuous map from a closed Euclidean ball to itself has a fixed point. For the closed disc $D\subset {\mathbb{R}}^2$ its equivalent no-retraction theorem says that there is no continuous $r:D\to \partial D$ satisfying $r(z)=z$ on $\partial D$.

Assume the fixed-point theorem and suppose such a retraction exists. Then $F(x)=-r(x)$ maps $D$ continuously into itself. A fixed point must lie on the boundary, where $r(x)=x$, giving $x=-x$, impossible on the unit circle.

Conversely suppose $F:D\to D$ is continuous and has no fixed point. From $F(x)$ draw the ray through $x$ and let $r(x)$ be its exit point on the circle. To check continuity rather than merely relying on the picture, put $v=x-F(x)\ne 0$. The exit point is $F(x)+t(x)v$, whereThis is continuous, lies on the circle and has $t(x)\ge 1$. On the boundary the exit point is $x$, so $r$ is a retraction, contradicting the assumed theorem. Hence the two disc formulations are equivalent; the same argument works for a ball in any dimension.

Under the open set condition there is a nonempty bounded open set $O$ such that the sets $S_i(O)$ are pairwise disjoint and all contained in $O$. The Hausdorff dimension of the nonempty compact invariant set is the unique $s\ge 0$ satisfyingFor the carpet here the 24 retained sub-squares give Euclidean similarities $S_{ij}(x,y)=((x+i)/5,(y+j)/5)$ for $0\le i,j\le 4$, $(i,j)\ne (2,2)$. Their images of $O=(0,1{)}^2$ are disjoint and lie in $O$, so the condition holds even though some closed images share boundary points. All contraction factors are $1/5$. Thus

A binary linear-feedback shift register of length $L$ keeps $L$ bits and produces a sequence satisfying a recurrenceAfter each output it shifts its stored bits and inserts the feedback bit. Its connection polynomial is $C(z)=1+c_{1}z+\cdots +c_L{z}^L$. This convention reverses the usual characteristic polynomial $z^L+c_1{z}^{L-1}+\cdots +c_L$.

The Berlekamp-Massey algorithm recovers the shortest recurrence compatible with observed bits. Maintain the current $C$, length $L$, an earlier polynomial $B$ that last caused a length increase, and the offset $m$ since that increase. Initially $C=B=1,L=0,m=1$. At position $n$ calculate the discrepancy $d=s_n+{\sum }_{j=1}^L{c}_j{s}_{n-j}$. If $d=0$, advance $m$. If $d=1$, save $T=C$ and replace $C$ by $C+z^{m}B$. If also $2L\le n$, replace $L$ by $n+1-L$, $B$ by $T$ and $m$ by one; otherwise increase $m$. Over a general field the correction is $(d/b)z^{m}B$, where $b$ is the saved nonzero discrepancy. The correction cancels the failed equation while retaining the previous successful ones; when it forces a length increase the smallest possible new length is $n+1-L$.

Here, indexing the first bit by zero, the nonzero discrepancies occur at positions $1,4,6$. The corresponding updates areEvery subsequent supplied discrepancy is zero. ThusEquivalently the characteristic feedback polynomial is $z^4+z+1$. No length-three recurrence works: positions $3,4,5$ force $c_2=1,c_1=0,c_3=1$, but position six then has nonzero discrepancy. The recovered length is therefore minimal. Observing at least twice the true linear complexity ordinarily identifies the recurrence, after which a known consecutive block determines all future key bits. This is why a bare register is unsuitable as a cryptographic keystream generator; a finite prefix alone does not exclude a longer generator that later diverges.

Put $\hat{\beta }=(X^{T}X{)}^{-1}{X}^{T}Y$, ${\hat{\sigma }}^2=\Vert Y-X\hat{\beta }{\Vert }^2/(n-p)$. Orthogonal projections of the Gaussian error give independent variablesHence the exact $(1-\alpha )$ confidence set is the ellipsoidHere $F_{p,n-p}(q)$ denotes the $q$ quantile of the F-distribution.

Let ${\hat{\beta }}_{(-i)}$ be the fit with observation $i$ removed, when that reduced design retains full rank. Cook's distance iswhere $e_i$ is its residual and $h_{ii}=x_i^T(X^{T}X{)}^{-1}{x}_i$ is its leverage. Thus $D_i$ measures the deleted estimate's distance from the full estimate in exactly the metric of the confidence ellipsoids. The deleted estimate lies on the confidence contour whose $F$ quantile equals $D_i$; this is a geometric influence diagnostic, not an assertion that $D_i$ itself has an $F$ law.

For $p=2,n=50$, $0.70<1.3<2.42$, so deletion moves the estimate outside the 50% confidence ellipsoid but inside the 90% one. The observation warrants investigation for influence: the shift is substantial, though the supplied figures do not justify calling it outside the 90% region. The reciprocal $F_{48,2}$ and the approximate chi-square figures are unnecessary.

The probability generating function encodes the population distribution in one analytic function. Its coefficients and derivative recoverprovided the mean is finite. Higher derivatives at one give factorial moments, and normalization says $\varphi (1,t)=1$.

Interpret the supplied birth and death expressions as transition rates: over a small time $dt$ their probabilities are $(\alpha +\beta n)dt+o(dt)$ and $\gamma ndt+o(dt)$. Incoming probability from $n-1$ and $n+1$, minus both outgoing rates, giveswith $P(-1,t)=0$. Multiplying by $s^n$ and summing yieldsAt stationarity, ${\varphi }_s/\varphi =\alpha /(\gamma -\beta s)$, so integration and normalization giveAlternatively differentiating the evolution equation at one gives $m^{\prime }=\alpha -(\gamma -\beta )m$, so $m(t)=\alpha /(\gamma -\beta )+[m(0)-\alpha /(\gamma -\beta )]e^{-(\gamma -\beta )t}$. If $\beta =0$, the displayed power expression is understood in its limit: $\varphi (s)=e^{(\alpha /\gamma )(s-1)}$, a Poisson distribution with mean $\alpha /\gamma$.

Solving the two factors in each equation gives $(0,0),(3,0),(0,3),(1,1)$. The Jacobian isAt the three boundary equilibria its eigenvalues are $3,-3$. These equilibria are hyperbolic fixed points; the Hartman-Grobman theorem gives local topological conjugacy to their saddle linearizations. At $(1,1)$ the matrix is $\left(\begin{array}{cc}1& 2\\ -2& -1\end{array}\right)$, with eigenvalues $\pm i\sqrt{3}$. The linearization is a centre, but the hyperbolic theorem does not apply there.

The nonlinear classification follows from the actual HamiltonianAlong solutions $\dot{H}=H_x{H}_y-H_y{H}_x=0$. At $(1,1)$, $H=-1$ and its Hessian is $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$, which is positive definite. Nearby regular level curves are closed ovals around this strict minimum. Their vector field is nonzero and tangent, so each is a periodic orbit. The nonlinear equilibrium is a centre.

The separatrix level $H=0$ consists of $x=0$, $y=0$, and $x+y=3$. Within the triangle they connect the saddles as $(3,0)\to (0,0)\to (0,3)\to (3,0)$. The interior levels $-1<H<0$ are nested clockwise periodic orbits; outside the triangle the remaining level branches are unbounded. On $y=0$, flow is left for $0<x<3$ and right for $x<0$ or $x>3$; on $x=0$, it is up for $0<y<3$ and down otherwise. These directions and the invariant levels determine the full phase portrait.

Use the one-sided Laplace transform $F(s)={\int }_0^{\infty }{e}^{-st}f(t)dt$. Since $f=0$ on $[0,1)$, substitution gives $\mathcal{L}[f(t+1)](s)=e^{s}F(s)$. ThusIts poles are $s=0$ and $s_n=-\log 2+2\pi in$, with residues of $e^{st}F(s)$ respectively two and $2e^{s_{n}t}/s_n$. For $t>1$ close the Bromwich inversion formula to the left, using horizontal heights avoiding those poles. The left-side integrand decays like $e^{st}/s$, and on the right-side horizontal ends like $e^{s(t-1)}/s$, so the added integrals vanish with the usual symmetric limiting contour. The residue theorem giveswhere the series is summed symmetrically and at jumps has the midpoint value.

For $t<1$ the vanishing can be checked directly in the inversion integral, rather than inferred from the recurrence. On any vertical line $\Re s=c>0$ expand the denominator geometrically, uniformly there:Each inversion term is $2^{1-j}(2\pi i{)}^{-1}{\int }_{c-i\infty }^{c+i\infty }{e}^{s(t-j-1)}ds/s$. If $t<1$, close this contour to the right: the exponential decays, and the pole at zero is outside, so every term is zero. Equivalently the geometric expansion bounds the full closing contour by the same decaying factors. Thus $f(t)=0$ for $t<1$.

The same integral gives $f(t)=2{\sum }_{j\ge 0}{2}^{-j}H(t-j-1)$ elsewhere. For $m<t<m+1$ with integer $m\ge 1$, this is $4(1-2^{-m})$, which directly verifies the difference equation. Neither a Laplace transform nor a Fourier series determines values at isolated jumps; the printed series fixes the standard convention $H(0)=1/2$, including $f(1)=1$.

Let $M_{ij}=\partial y_i/\partial x_j$ be the Jacobian of an invertible change of phase coordinates, and set $K(y,t)=H(x(y),t)$. The chain rule gives ${\nabla }_{x}H=M^T{\nabla }_{y}K$, whenceTherefore the necessary and sufficient condition to retain Hamilton's equations for arbitrary Hamiltonians isequivalently $M^{T}JM=J$. In one degree of freedom this is the Poisson bracket condition $\{Q,P\}=Q_q{P}_p-Q_p{P}_q=1$.

Put $D=p^2+{\alpha }^2{q}^2$. On a smooth branch of the angular coordinate,Consequently $Q_q{P}_p-Q_p{P}_q=(p^2+{\alpha }^2{q}^2)/D=1$. The transformation is canonical for every real $\alpha \ne 0$ on each angular-coordinate chart. The origin is excluded and a single-valued arctangent cannot give a global chart on the punctured plane; using an angle modulo $2\pi$ accounts for the usual branch qualification.

A comoving coordinate $\mathbf{\chi }$ labels a galaxy carried by the homogeneous cosmological flow. Its physical separation at time $t$ is $\mathbf{r}(t)=a(t)\mathbf{\chi }$, where $a$ is the scale factor. Thus $\mathbf{v}=\dot{a}\mathbf{\chi }=(\dot{a}/a)\mathbf{r}$, the Hubble law, apart from peculiar velocities relative to this flow. In particular

Assume the present universe is expanding, $\dot{a}(t_0)>0$. The stated energy inequality and the Raychaudhuri equation imply $\ddot{a}\le 0$ wherever $a>0$. Therefore for $t<t_0$ in that positive branch, $\dot{a}(t)\ge \dot{a}(t_0)$, andNonnegativity of $a(t)$ forces $t_0-t\le a(t_0)/\dot{a}(t_0)=H_0^{-1}$. If the solution remains valid towards the past, its positive branch must thus end in $a=0$ within that time; a positive scale factor extending further would contradict the inequality. HenceThis argument presumes an expanding branch and the stated energy condition throughout it, rather than proving either assumption.

There are two relevant failures of the naive numerical bound. The supplied ten-billion-year Hubble time is an approximate observational input: a smaller inferred present expansion rate gives a larger Hubble time, and comparison with stellar ages must include these uncertainties. More decisively, a positive cosmological constant, or other dark energy with sufficiently negative pressure, has $\rho +3P/c^2<0$ and permits accelerated expansion, so the concavity assumption fails. Observations of acceleration therefore remove this particular upper-bound argument. This is a discussion of the supplied historical estimate, not an assertion that its numerical value is a current measurement.

Parametrize the circle by $z=e^{it}$, $0\le t\le 2\pi$. Choose a continuous argument $\vartheta (t)$ of $\varphi (e^{it})$, so $\varphi (e^{it})=|\varphi (e^{it})|e^{i\vartheta (t)}$. Its winding number about zero isThe two facts proved below determine the requested calculation without needing differentiability or contour integration. Put $P(z)=(3z-2)(z-3)(2z+1)$. On $|z|=1$, $|P(z)|\ge 1\cdot 2\cdot 1=2$, so adding one does not change its winding. The first and third factors have winding one, since their constant terms have modulus smaller than their linear terms; the second has winding zero, since its $z$ term has modulus smaller than its constant term. Nonzero constants have winding zero and $z$ has winding one. Thus

Choose continuous arguments ${\vartheta }_1,{\vartheta }_2$ along the parametrized circle. Their sum is a continuous argument of the product, because multiplication multiplies moduli and adds arguments. Subtracting endpoint values gives

Factor $\varphi +\psi =\varphi (1+\psi /\varphi )$. The second factor has positive real part, since $|\psi /\varphi |<1$. It therefore has the continuous single-valued argument $\arctan (\Im (1+\psi /\varphi )/\Re (1+\psi /\varphi ))$ taking values in $(-\pi /2,\pi /2)$. Its values agree at the two ends of the parametrized circle, so its winding number is zero. Part (i) gives

In curvature-minus-one polar coordinates the hyperbolic metric is $d{s}^2=d{r}^2+{\sinh }^{2}rd{\theta }^2$. Thus the area element is $\sinh rdrd\theta$, givingIt is asymptotic to $\pi e^r$.

For a usual locally finite tessellation with compact congruent tiles of nonempty interior, let their diameter be at most $D$ and choose in each a congruently placed interior ball of radius $r_0>0$. These balls have disjoint interiors. The number of tiles meeting a geodesic segment of length one is uniformly bounded: their ball centres lie in a ball of radius $D+1$, and the disjoint $r_0$-balls lie in the larger ball of radius $D+1+r_0$. Comparing areas supplies a constant $K$. A path of length $R$, divided into at most $\lceil R\rceil$ such segments, therefore crosses at most $K(\lceil R\rceil +1)$ tiles. A small generic perturbation avoids vertices if steps are defined by crossing sides.

Consequently the union of tiles at most $n$ steps from the initial tile contains a metric ball of radius $cn-C$ for fixed $c>0,C$. If $A$ is tile area, their number $N(n)$ is at least $\mathrm{Area}B(cn-C)/A$, an exponential lower bound. Conversely any chain of $n$ adjacent tiles lies in $B(D(n+1))$ about a point in the initial tile; the interiors are disjoint, so $AN(n)\le \mathrm{Area}B(D(n+1))$. Thus $N(n)$ is bounded above and below by positive exponential functions of $n$. No precise common growth exponent is claimed.

An explicit example is the regular right-angled pentagon tiling $\{5,4\}$: reflect a regular hyperbolic pentagon with all angles $\pi /2$ in its sides. Four pentagons meet at each vertex, and their interiors tile the plane. Its tiles have area $3\pi -5\pi /2=\pi$ by the hyperbolic polygon area formula. The compactness and ordinary local finiteness assumptions exclude pathological decompositions with degenerate tiles.

The fitted grouped-binomial logistic regression generalized linear model treats seasonal hits $H_i$ as independent $\mathrm{Bin}(n_i,p_i)$ variables, with $n_i={\mathrm{AB}}_i$ andThus the response supplied to glm is a proportion, and weights=AB supplies its binomial denominator; it is not a regression with equally precise seasonal averages. I(Age^2) forms the numerical square rather than using a formula operator. The estimates maximize $\ell (\beta )={\sum }_i[H_i{\eta }_i-n_i\log (1+e^{{\eta }_i})]$ up to a constant, where ${\eta }_i=x_i^T\beta$, $x_i=(1,a_i,a_i^2{)}^T$.

The observed negative Hessian is $X^{T}WX$, $W_{ii}=n_i{\hat{p}}_i(1-{\hat{p}}_i)$. Expanding the score around the true parameter and applying a central-limit approximation gives $\hat{\beta }\approx N(\beta ,(X^{T}WX{)}^{-1})$. The reported standard errors are square roots of the diagonal entries of this inverse; the binomial dispersion is fixed at one. Each z value divides the coefficient estimate by its standard error, and the reported two-sided Wald test uses a standard normal approximation under the corresponding zero-coefficient hypothesis.

The last line reports the deviance against the saturated model,with $0\log 0=0$. There are 22 seasonal observations and three fitted parameters, so 19 degrees of freedom. Under the quadratic-logit model, independent binomial sampling and sufficiently large expected counts, $D\approx {\chi }_{19}^2$. The value 23.345 gives an upper-tail probability about 0.22, no evidence of lack of fit at conventional levels. This approximation and the independence assumption should not be confused with an exact test of a player's ability.

The final commands recover the coefficients, apply the inverse logit $p=(1+e^{-\eta }{)}^{-1}$, plot the observed averages against age, and join the fitted probabilities at the observed ages. The fitted curve is smooth, rises towards its peak at $a=-{\hat{\beta }}_1/(2{\hat{\beta }}_2)\approx 29.95$, then falls. Its maximum is about 0.373; the early and late observed points include markedly lower averages. The plot uses equally sized points even though their binomial precisions differ.

Linearizing about the orbit gives $\dot{\eta }=A(t)\eta$, where $A(t)=Df(X(t))$. The fundamental matrix therefore satisfiesThe Floquet multipliers are the eigenvalues of the monodromy matrix $\Phi (T)$. Differentiating the orbit equation shows that its tangent $\dot{X}(t)$ solves the variational equation. Since $\dot{X}(T)=\dot{X}(0)\ne 0$, one multiplier is one.

For an invertible fundamental matrix, differentiating the determinant gives $(\det \Phi {)}^{\prime }=\mathrm{tr}({\Phi }^{-1}\dot{\Phi })\det \Phi =\mathrm{tr}A\det \Phi$. Integration from the identity yields $\det \Phi (T)=\exp ({\int }_0^T\mathrm{tr}A(t)dt)$. The determinant is the product of the two multipliers, so the other is

Write $y=\dot{x}$ and $E=(x^2+y^2)/2$. Along a trajectory,Use the unperturbed orbit $x=R\sin t,y=R\cos t$ to compute the leading energy change over one period:Zero averaged energy change gives the nonzero amplitudeThe supplied sign condition makes this real and nonzero. The averaged amplitude equation is $\dot{R}=ϵ[\gamma R/2-(\alpha +3\beta )R^3/8]+O({ϵ}^2)$, whose derivative at that root is $-ϵ\gamma +O({ϵ}^2)$. Its nonzero derivative also makes the root persist as an isolated periodic orbit for sufficiently small positive $ϵ$.

Directly, the planar divergence is $-ϵ(\alpha x^2+3\beta y^2-\gamma )$. On the leading orbit its integral over $2\pi$ is $-ϵ[\pi R^2(\alpha +3\beta )-2\pi \gamma ]=-2\pi ϵ\gamma$. ThusThe cycle is attracting for $\gamma >0$ and repelling for $\gamma <0$. Both sign possibilities are allowed by $(\alpha +3\beta )\gamma >0$.

Vary $q_a$ and $p_a$ independently, fixing the endpoint positions. Integration by parts givesThe boundary term vanishes, so arbitrary interior variations implyIn the Lagrangian principle only $q$ is varied independently, and $\delta \dot{q}=d(\delta q)/dt$; here positions and momenta are independent paths in phase space. The extremality condition is stationarity of the action, not necessarily a minimum. Along Hamiltonian motion,so an explicitly time-independent Hamiltonian is conserved.

The invariant is phase-space volume, or area $dqdp$ for one degree of freedom. It does not require an autonomous Hamiltonian. The flow vector $v=(H_p,-H_q)$ has divergence ${\partial }_q{H}_p-{\partial }_p{H}_q=0$ whenever the mixed derivatives agree. If $M(t)$ is the Jacobian of the flow with respect to initial coordinates, then $\dot{M}=DvM$. Differentiating its determinant givesThus the change-of-variables formula shows that any region carried by the flow retains its area. This proves Liouville theorem in Hamiltonian mechanics even when $H=H(q,p,t)$ depends on time.

Between collisions the momentum is $p_0=\sqrt{2mE}$ or $-p_0$. In phase space the cycle runs right along the upper horizontal segment from $q=0$ to $q=b$, jumps vertically to $-p_0$ at the right wall, runs left along the lower segment, and jumps back at the left wall. The jumps have $dq=0$. ThereforeDifferentiation gives $dI/dE=2bm/\sqrt{2mE}=2b/v$, exactly the out-and-back period. Under slow wall motion the action $I$ is the adiabatic invariant; a convention using $I/(2\pi )$ is equivalent. HenceCompression raises the energy and expansion lowers it, provided the wall speed is small compared with the particle speed and the change per cycle is small.

A chain-complete partially ordered set has a supremum for each chain (and a least element if the empty chain is included). The weaker condition needed for Zorn lemma is that every chain have an upper bound; some terminology also calls this chain-complete. Zorn's lemma says that a nonempty partially ordered set with this upper-bound property has a maximal element. We verify that exact hypothesis below.

Consider the lattice ideals containing $a$ but not $b$, ordered by inclusion. The principal ideal $\downarrow a$ belongs to this family because $b\nleqq a$. The union of a nonempty chain of such ideals is an ideal: two of its elements lie together in one member of the chain, which contains their join and everything below it. The union still avoids $b$. The empty chain has the initial principal ideal as an upper bound. Zorn supplies a maximal such ideal $I$.

We prove that $I$ is a prime lattice ideal. If $x,y\notin I$, maximality says that the ideals generated by adjoining $x$ and by adjoining $y$ both contain $b$. Thus $b\le i\vee x$ and $b\le j\vee y$ for some $i,j\in I$: the first generated ideal consists of elements below $i\vee x$, and similarly for $y$. If $x\wedge y\in I$, distributivity givesa contradiction. Consequently $x\wedge y\in I$ implies $x\in I$ or $y\in I$.

Define $f(x)=0$ on $I$ and one elsewhere. An ideal contains $x\vee y$ exactly when it contains both $x$ and $y$, and its primeness says that it contains $x\wedge y$ exactly when it contains at least one of them. Thus $f$ preserves both joins and meets, and $f(a)=0,f(b)=1$ as required.

For completeness, take the Lindenbaum algebra of classical propositional formulae modulo provable equivalence, including any given premises as axioms. It is a Boolean, hence distributive, lattice; provable implication is its order. If a formula $P$ is not provable from the premises, then $1\nleqq [P]$. The separation just proved, with $a=[P],b=1$, gives a homomorphism of lattices sending $P$ to zero and one to one. It also sends zero to zero, since $0\le [P]$, and preserves complements because their meet is zero and join is one. Its values on atomic propositions form a Boolean valuation satisfying all premises and falsifying $P$. Thus semantic consequence implies provability, the completeness theorem for propositional logic.

For a finite connected plane graph, with $v$ vertices, $e$ edges and $f$ faces including the unbounded face, Euler formula for a connected planar graph isIf the graph is a tree, $e=v-1$ and $f=1$. Otherwise remove an edge on a cycle. This preserves connectivity and joins the two faces on its sides, so both $e$ and $f$ decrease by one. Repeating reaches a tree, preserving $v-e+f$ throughout and proving the formula.

For a simple connected graph with $v\ge 3$, each face boundary walk has length at least three, with bridges counted twice in the walk; the sum of lengths is $2e$. Hence $3f\le 2e$, which with Euler gives $e\le 3v-6$. If it has no triangles in a graph, no face boundary walk can have length three, and every boundary length is at least four. Thus $4f\le 2e$, givingFor a disconnected graph, add noncrossing bridges between its components; this preserves simplicity and creates no triangles, reducing to the connected bound.

Every triangle-free planar graph with at least three vertices has average degree $2e/v<4$, and therefore a vertex of degree at most three. Remove one such vertex. Its remaining graph is again triangle-free and planar. Induction, with graphs on at most two vertices as the base cases, provides a graph colouring with four colours of the remainder. At most three colours appear on the removed vertex's neighbours, so a fourth colour extends the graph colouring. This proves four-colourability without using the four-colour theorem.

Let $L$ be the splitting field of the separable polynomial. Its Galois group is $G={\mathrm{Aut}}_K(L)$, acting faithfully on its $n$ distinct roots, hence as a subgroup of $S_n$. An automorphism preserves each root's minimal polynomial. Conversely an isomorphism $K(\alpha )\to K(\beta )$ for roots of the same irreducible factor extends to an embedding of $L$ in an algebraic closure, and normality of the splitting field makes the image $L$ itself. Thus the root orbits are precisely the irreducible factors' root sets. The action is transitive exactly when the polynomial is irreducible.

If $n=p$ is prime, a transitive action has $p\mid |G|$ by orbit-stabilizer, so Cauchy theorem for groups supplies an element of order $p$. Its permutation must be a $p$-cycle. Conversely a $p$-cycle already acts transitively on all $p$ roots. This proves the stated equivalence for prime degree.

The factorization theorem modulo a good prime says that if an integer polynomial retains its degree and has square-free reduction modulo $p$, and that reduction's irreducible factor degrees are $d_1,\dots ,d_r$, its Galois group over $\mathbb{Q}$ contains a permutation with disjoint cycle lengths $d_1,\dots ,d_r$. Equivalently the finite-field Galois group, generated by Frobenius on the roots, occurs as an unramified decomposition subgroup. The degree-retention qualification matters for nonmonic polynomials.

For the given quintic, Eisenstein criterion at three proves irreducibility. Modulo two it factors asNeither factor has a root in ${\mathbb{F}}_2$, so both are irreducible, and they are distinct; the reduction is separable. Thus $G$ contains an element of cycle type $(2)(3)$, whose cube is a transposition. It is also transitive of degree five.

To prove that this forces the full symmetric group here, form the graph on the five roots with an edge for each conjugate in $G$ of that transposition. The graph is $G$-invariant, and transitivity makes its connected components all the same size. That size divides five; there is an edge, so the size cannot be one. Hence the graph is connected. Transpositions along the edges of a connected graph generate all transpositions (move along a path and conjugate successive swaps), and hence generate $S_5$. They all belong to $G$, giving