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

Since $a=kp\ge 2$, we have $a^p\equiv 1(\mathrm{mod}{a}^p-1)$ and $\gcd (a,a^p-1)=1$. Its multiplicative order therefore divides the prime number $p$. It cannot be one, because $0<a-1<a^p-1$. Thus the order is exactly $p$.

To find the desired prime divisor, use the cyclotomic polynomialChoose a prime factor $q$ of this integer. Since $p\mid a$, we have ${\Phi }_p(a)\equiv 1(\mathrm{mod}p)$, so $q\ne p$. Also $q\nmid a$. If $a\equiv 1(\mathrm{mod}q)$, then ${\Phi }_p(a)\equiv p(\mathrm{mod}q)$, contradicting $q\ne p$. Consequently $a$ has multiplicative order $p$ in the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Lagrange theorem givesThis $q$ divides $a^p-1$ as required. Notice that order $p$ modulo a composite integer alone would not justify selecting an arbitrary prime divisor; the cyclotomic polynomial selects a suitable one.

If there were only finitely many such primes $q_1,\dots ,q_r$, choose $k=q_1\cdots q_r$, with the empty product interpreted as one. Each $q_i$ divides $a=kp$ and hence does not divide $a^p-1$. The preceding argument supplies a further prime $q\equiv 1(\mathrm{mod}p)$ dividing that integer, a contradiction. There are infinitely many primes in this residue class.

The fourth Chebyshev polynomial is $T_4(x)=8x^4-8x^2+1$. Therefore takeIndeed $x^4-p(x)=T_4(x)/8$, and $|T_4(x)|\le 1$ on $[-1,1]$, as follows from $T_4(\cos \theta )=\cos 4\theta$.

Here is a direct Chebyshev alternation theorem argument proving optimality, without assuming the theorem. At the five ordered pointsthe error $x^4-p(x)$ takes the alternating values $1/8,-1/8,1/8,-1/8,1/8$. If a polynomial $q$ of degree at most three had strictly smaller uniform error, then $q-p$ would have alternating strictly positive and strictly negative values at these points. The intermediate value theorem would give a distinct root in each of the four intervening intervals. A nonzero polynomial of degree at most three cannot have four distinct roots. This contradiction proves the required minimax inequality.

There are two conventions for loxodromic Möbius transformations. In the inclusive convention, a transformation conjugate to $z\mapsto \lambda z$ with $|\lambda |\ne 1$ is loxodromic, including a hyperbolic Möbius transformation with $\lambda >0$. Under that convention the assertion about discs is false: $z\mapsto 2z$ preserves the upper half-plane, and a Cayley conjugation gives an invariant ordinary disc.

The question uses the classification in which hyperbolic Möbius transformations and genuinely spiralling loxodromic Möbius transformations are separate. Thus here the multiplier satisfies $|\lambda |\ne 1$ and $\lambda \notin (0,\infty )$. Such a Möbius transformation has two distinct fixed points; after sending them to zero and infinity it acts by the stated dilation and rotation.

For a determinant-one representative, put $\tau =a+d$. Its eigenvalues are $\eta ,{\eta }^{-1}$, with $\eta +{\eta }^{-1}=\tau$, and the normalized multiplier is ${\eta }^2$ or its reciprocal. If $\tau$ is real, the eigenvalues are either real or conjugate unit-modulus numbers. These give the hyperbolic, elliptic, parabolic or identity cases, not a genuine spiral. Conversely, a real eigenvalue or a unit-modulus eigenvalue makes $\tau$ real. Hence the practical criterion in the question's convention isChanging the determinant-one representative by its sign does not affect this criterion.

Finally, conjugate an invariant disc to the upper half-plane. A Möbius transformation preserving that half-plane has a representative in $S{L}_2(\mathbb{R})$: preservation of the boundary gives real coefficients up to a common scalar, and preservation of the chosen side makes the real determinant positive, allowing normalization to one. Its trace is real. Trace is invariant under conjugacy, up to the harmless sign of the representative, so a disc-preserving transformation cannot be genuinely loxodromic. This proves the intended assertion while specifying its necessary terminology.

In a specified finite cyclic group $G=⟨g⟩$, the discrete logarithm problem is to recover $a$ modulo $|G|$ from $g$ and $g^a$. A common choice is a large prime-order subgroup of a multiplicative group of a finite field.

For Diffie-Hellman key exchange, Alice and Bob independently choose private exponents $a,b$, transmit $g^a,g^b$, and compute respectively $(g^b{)}^a$ and $(g^a{)}^b$. Both obtainSolving a discrete logarithm problem reveals a private exponent and breaks this exchange. The converse implication is not known in general: recovering $g^{ab}$ from $g^a,g^b$ is the computational Diffie–Hellman problem, rather than literally the same task as computing a logarithm.

The advantage is that parties without an already shared secret can establish a fresh session key, which can then be used with efficient symmetric encryption. A classical secret-key system requires an earlier secure key distribution; ordinary public-key encryption can instead transmit a chosen key, but ephemeral Diffie-Hellman key exchange also permits forward secrecy when private session exponents are erased and the exchange is authenticated. Authentication is essential: an unauthenticated exchange is vulnerable to a man-in-the-middle attack.

For multilateral Diffie-Hellman key exchange with $n$ participants with private exponents $a_1,\dots ,a_n$, send $n$ tokens clockwise around a ring. Participant $j$ starts the token $g^{a_j}$ and sends it to participant $j+1$. On each subsequent receipt, the receiver raises the token to their own private exponent and sends it onwards, until that token has made $n-1$ transmissions and reaches participant $j-1$. Its exponent then contains every exponent except $a_{j-1}$. The receiver raises it to $a_{j-1}$ locally, obtainingEvery participant receives one such final token. There are $n$ tokens with exactly $n-1$ transmitted group elements per token, giving $n(n-1)$ transmissions. No private exponent is transmitted.

Write $Y_i=\log ({\mathrm{price}}_i)$ and fit the normal linear modelThe basic linear regression analysis assumes centered independent normal random variables ${\epsilon }_i$ of a common variance ${\sigma }^2$, conditional on the predictors. Independence between makes does not by itself establish independence between different models of the same make; that stronger assumption should be checked, or within-make dependence modelled. The requested R fit is

fit <- lm(log(price) ~ mpg + psngr + length + width + weight, data = cars)

The estimate column contains the ordinary least squares coefficients. The standard error estimates the standard deviation of each coefficient estimator. The t value is its estimate divided by its standard error. The last column gives the two-sided p-value for a zero coefficient, using a Student t-distribution with $93-6=87$ residual degrees of freedom under the stated normal linear model; the stars summarize significance thresholds.

Conditional on the other predictors, passenger capacity and width have negative fitted coefficients, while length and weight have positive ones. All four are significant at the conventional 5% level; length is borderline. There is little evidence for an additional mpg effect once the others are included. These are conditional associations, not causal claims. For example, increasing weight by 100 pounds multiplies the fitted price by approximately $\exp (0.08373)$, about 1.087.

A reasonable candidate simplification removes mpg and compares the nested models by an F-test, rather than treating a nonsignificant coefficient as proof of no effect:

fit2 <- update(fit, . ~ . - mpg)
anova(fit2, fit)

Inspect regression residuals, normal quantiles, residual-versus-fitted plots, leverage and influential observations. The correlated size predictors may produce multicollinearity; missing make effects, nonlinear terms or unequal residual variances may also matter. A random make effect or a covariance adjustment addresses the possible dependence noted above.

Put $u=\epsilon v+O({\epsilon }^2)$. The linearization at the zero solution isThe appropriate Fourier sine series isOrthogonality of the modes givesThus each mode grows or decays exponentially with its own eigenvalue, and the largest growth rate is the $n=1$ value. Strict linear stability analysis, meaning decay of every mode, is equivalent toAt equality the first mode is neutral in the linearization; the nonlinear terms decide its subsequent behavior. Above this length the first mode grows, giving linear instability.

A useful version of the Poincaré-Bendixson theorem says that a forward orbit of a continuously differentiable planar autonomous vector field which stays in a compact set has a nonempty compact omega-limit set; if that omega-limit set contains no equilibrium, it is a periodic orbit.

Let $r^2=x^2+y^2$. Direct calculation givesFor $r>0$, $|xy|\le r^2/2$, so $-9/8\le \dot{\theta }\le -7/8$. In particular there is no equilibrium away from the origin.

On $r=1/2$, both coefficients in the radial expression are strictly positive, so the flow crosses outward. On $r=2$, both are strictly negative, so the flow crosses inward. Consequently the compact annulusis forward invariant. Any orbit starting there stays there, and its omega-limit set avoids the only equilibrium, the origin. The Poincaré-Bendixson theorem therefore supplies at least one periodic orbit in this annulus.

Choose $z=e^{it}$ on the right semicircle, with the continuous branch $\log z=it$. ThenHere the integral is along that semicircle. Since $|A|>1$, the pole lies outside the unit disc and the geometric series converges uniformly on the contour.

PutThe Euler integral for the hypergeometric function, initially for $\mathrm{Re}u>-1$, givesThe prefactor follows from $\Gamma (u+2)/\Gamma (u+1)=u+1$. Hence an antiderivative of the contour integrand before multiplication by $1/i$ isEvaluating at the endpoints with the chosen branch yieldsThis is first obtained where the individual expressions are defined. The original finite-interval integral is entire in $u$, so analytic continuation gives the result elsewhere, taking removable limits at the apparent exceptional negative integers. That convention matters: the two separate hypergeometric terms may be singular even though their combination is finite.

For an autonomous Lagrangian, the canonical momentum and energy areAlong a solution of the Euler-Lagrange equation,The absence of explicit time dependence is essential to this conservation law.

The classical action is $S_c(q_I,q_F,T)={\int }_0^{T}L(q_c,{\dot{q}}_c)dt$. If the final endpoint is moved along one fixed classical trajectory, while the initial endpoint is held fixed, the fundamental theorem of calculus givesThis total derivative is different from the partial derivative with fixed final position.

For a family of nearby classical trajectories, integration by parts gives the endpoint variationTo obtain the final term, the endpoint change in the variation at fixed parameter time is $\delta q(T)=\delta q_F-{\dot{q}}_F\delta T$, while the changing upper integration limit contributes $L_F\delta T$. The interior integral vanishes by the Euler-Lagrange equation. Therefore, on any smooth branch of classical boundary-value solutions,The chain rule along the endpoint trajectory now reads $d{S}_c/dT=p_F{\dot{q}}_F-E=L_F$, consistently with the direct calculation.

The Jeans wavenumber in physical coordinates is $k_J=\sqrt{4\pi G\rho }/c_s$. With wavelength defined as $2\pi /k$, the Jeans length isPressure opposes gravitational growth on physical wavelengths shorter than this; on longer wavelengths the gravitational term wins. Expansion also provides the damping term $2H\dot{\delta }$, so the actual growth is not generally the exponential growth of a static medium.

For the pressure-free, spatially flat matter solution, $H=2/(3t)$ and the Friedmann equation gives $\rho =1/(6\pi G{t}^2)$. The perturbation equation becomesSubstituting ${\delta }_k=t^{\nu }$ gives $3{\nu }^2+\nu -2=(3\nu -2)(\nu +1)=0$. ThusThe growing mode scales as $a(t)$ and permits the formation of structure; the decaying mode becomes negligible at late times. This is a linear result, valid while the density contrast remains small.

Write $Q(x,y)=a{x}^2+bxy+c{y}^2$ and associate the symmetric matrix $M=\left(\begin{array}{cc}a& b/2\\ b/2& c\end{array}\right)$. Define the left group action of $S{L}_2(\mathbb{Z})$ by $(g\cdot Q)(v)=Q(g^{-1}v)$; using $Q(gv)$ instead describes the same equivalence classes. The transformed matrix is $g^{-T}M{g}^{-1}$, so its determinant is unchanged. Hence the discriminant of a binary quadratic formis invariant under proper equivalence of binary quadratic forms.

A proper representation here means $Q(x,y)=n$ with $\gcd (x,y)=1$. Such a vector extends to the first column of an integer determinant-one matrix by Bezout identity. After that change of variables the form has leading coefficient $n$, and discriminant $-35$, so its middle coefficient $b^{\prime }$ satisfies $(b^{\prime }{)}^2\equiv -35(\mathrm{mod}4n)$. Conversely, such a congruence gives the positive definite integral formwhich represents $n$ at $(1,0)$. It is primitive: a common divisor of all three coefficients would have its square dividing the squarefree discriminant 35.

For clarity, enumerate all the proper equivalence classes at this discriminant. Substitutions $(x,y)\mapsto (x+my,y)$ first arrange $|b|\le a$; if $c<a$, the determinant-one substitution $(x,y)\mapsto (-y,x)$ makes the leading coefficient smaller. Repeating terminates because this coefficient is a positive integer. Thus every class has a reduced representative with $|b|\le a\le c$. From $4ac-b^2=35$ it follows that $3a^2\le 35$, giving $a\le 3$. Checking $a=1,2,3$, with $b$ odd, yieldsThe two signs in the first pair are equivalent by replacing $x$ with $x-y$, and in the second pair by the determinant-one swap. Thus the two forms in the question exhaust the classes.

The primitive representation criterion at discriminant minus thirty-five now follows. For odd $n$ prime to 35, the congruence modulo $4n$ is solvable exactly when $-35$ is a square modulo every prime divisor of $n$. Necessity is immediate. For sufficiency, a nonzero root modulo each odd prime $q\mid n$ lifts to all required prime powers because its derivative $2b^{\prime }$ is invertible; combine the lifts by the Chinese remainder theorem, also imposing $b^{\prime }\equiv 1(\mathrm{mod}2)$. This gives the modulus-four condition since $-35\equiv 1(\mathrm{mod}4)$. We concludeBy quadratic reciprocity, the symbol equals $(q/5)(q/7)$. In particular each prime divisor must be a quadratic residue at both 5 and 7, or a nonresidue at both. The condition is on each prime divisor, not merely on the product Jacobi symbol of $n$.

The Poincare ball model has ideal boundary the Riemann sphere. To construct the hyperbolic extension of a Möbius transformation, conjugate the ball to the upper half-space model with coordinates $(z,t)\in \mathbb{C}\times (0,\infty )$ and metric $(|dz{|}^2+d{t}^2)/t^2$. The generators of the Möbius group extend asandTranslations and similarities plainly preserve the metric; Euclidean inversion rescales both the squared Euclidean line element and $t^2$ by the same factor, proving the last case. Composition gives the unique orientation-preserving hyperbolic extension. Equivalently, for a determinant-one matrix its upper half-space formula is

An isometry fixing the ball origin acts on its tangent space by an orientation-preserving orthogonal transformation; radial geodesics then show that the whole map is that ordinary rotation. Conversely every rotation preserves the ball metric. On the sphere these are exactly the projective special-unitary mapsthe image of $SU(2)$ modulo its central signs.

A hyperbolic line is determined by its unordered pair of ideal endpoints. It is invariant precisely when that pair is preserved as a set. A nonidentity parabolic map has one fixed point, and its square also has one, so it cannot fix or interchange two distinct endpoints. Every nonparabolic nonidentity map has two fixed points, and their joining line is invariant.

More precisely, normalize the latter map to $z\mapsto \lambda z$. Unless $\lambda =-1$, any invariant pair must consist of zero and infinity: a swapped pair would be fixed pointwise by the square, whose only fixed points remain zero and infinity when ${\lambda }^2\ne 1$. This proves uniqueness for every nonidentity map except an elliptic half-turn. For $\lambda =-1$, every pair $\{z,-z\}$ is also invariant, giving infinitely many additional lines, besides the fixed-point axis. The identity preserves every line. ThusHere the uniqueness statement includes hyperbolic translations, genuine loxodromic maps and elliptic rotations through angles other than a half-turn.

A natural grouped-binomial logistic regression assumes independentwhere $B_i$ is beer intake and $W_i,R_i$ indicate Weird and Relaxed expressions. This uses the logit link. Independence of the individual throws conditional on the day's predictors gives the binomial sampling model; extra within-day dependence would instead produce overdispersion. The interactions let the beer slope depend on facial expression, rather than requiring one common slope. With the data frame named darts, R code is

darts$Expression <- relevel(factor(darts$Expression), ref = "Mad")
barney <- glm(cbind(BullsEye, 100 - BullsEye) ~ Beer * Expression, family = binomial, data = darts)

Mad is the baseline category. Its intercept and beer slope are already represented by the first two coefficients; including all three category indicators together with an intercept would make the design matrix rank deficient. For three beers and Weird expression,The fitted probability is $(1+e^{0.63430}{)}^{-1}$, approximately 0.347.

The Weird intercept and interaction are individually nonsignificant, suggesting that Mad and Weird might be combined. The Relaxed beer interaction is significant, so dropping all interactions would discard supported structure. A candidate reduced model retains only the Relaxed indicator and its interaction:

reduced <- glm(cbind(BullsEye, 100 - BullsEye) ~ Beer * I(Expression == "Relaxed"), family = binomial, data = darts)
anova(reduced, barney, test = "Chisq")

This fits without changing the data file. The joint likelihood-ratio test, rather than the two separate coefficient p-values alone, decides whether the simplification is supported. Also inspect regression residuals and the ratio of residual deviance to residual degrees of freedom for overdispersion or lack of fit; a quasibinomial analysis may be appropriate if the binomial variance is inadequate.

A fixed point is locally attracting when its multiplier satisfies $|F^{\prime }(x_{\ast })|<1$ and repelling when $|F^{\prime }(x_{\ast })|>1$. A multiplier crossing $+1$ can create or destroy fixed points in a fold bifurcation, or exchange their stability when branches cross, as in a transcritical bifurcation. A multiplier crossing $-1$ gives a flip, or period-doubling bifurcation, in which a two-cycle can emerge. These are the two multiplier mechanisms; additional symmetry can distinguish special cases at $+1$.

For the logistic map, the fixed points areThe second lies in $[0,1]$ only for $\mu \ge 1$. Their multipliers are $\mu$ and $2-\mu$. Thus zero attracts for $0<\mu <1$; the branches meet at $\mu =1$ and exchange stability, with the nonzero branch attracting for $1<\mu <3$. At $\mu =1$, positive orbits decrease to zero since $F(x)=x-x^2$. At $\mu =3$, put $x=2/3+z$. Then $z\mapsto -z-3z^2$ and its second iterate isso the fixed point is still weakly attracting at the bifurcation, although linear attraction has disappeared.

The supplied factorization gives the nonfixed two-cycle points for $\mu >3$:They are interchanged by $F$. Using their sum and product in $F^{\prime }(x_{+})F^{\prime }(x_{-})$ givesThe two-cycle is attracting exactly forIt is born from the fixed point at multiplier $+1$ for the second iterate, and at $\mu =1+\sqrt{6}$ its multiplier reaches $-1$, giving the next period doubling. The boundary cycles are nonhyperbolic; the strict multiplier test is not a proof of attraction there.

Beyond this threshold the logistic map undergoes further period doublings, with attracting cycles of periods $4,8,16,\dots$ and then chaotic parameter ranges, interspersed with periodic windows. It is not correct to say that every parameter above this threshold is chaotic. At $\mu =4$, the substitution $x={\sin }^2(\pi \theta )$ gives $F(x)={\sin }^2(2\pi \theta )$, illustrating its chaotic doubling-map behavior.

For a canonical coordinate and momentum, the Poisson bracket isThe chain rule and Hamilton equations $\dot{q}=H_p$, $\dot{p}=-H_q$ giveFor the stated complex variables, direct differentiation givesSince $H=\omega a{a}^{\ast }$, the product rule for the Poisson bracket yieldsThe linear change of variables is invertible, so treating $a,a^{\ast }$ as independent coordinates when differentiating givesIn particular $a(t)=a(0)e^{-i\omega t}$ and $a^{\ast }(t)=a^{\ast }(0)e^{i\omega t}$. On a continuously chosen branch along a nonzero trajectory,are constant. The logarithm is undefined at the zero-energy equilibrium, and a fixed principal branch need not be continuous across its cut; the branch qualification is necessary.

The completeness theorem for propositional logic states that $\Gamma \models \varphi$ implies $\Gamma ⊢\varphi$: every semantic consequence is formally derivable. Equivalently, every syntactically consistent set of formulas has a truth assignment satisfying it.

First prove the equivalent formulation. With countably many primitive propositions there are countably many formulas; enumerate them as ${\varphi }_1,{\varphi }_2,\dots$. Starting from a consistent $\Gamma$, construct increasing consistent sets ${\Gamma }_n$ by adjoining ${\varphi }_n$ if this remains consistent, and otherwise adjoining $\neg {\varphi }_n$. The second choice is consistent: if adjoining either choice were inconsistent, the deduction theorem for propositional logic would give both $\neg {\varphi }_n$ and $\neg \neg {\varphi }_n$ as consequences of ${\Gamma }_{n-1}$, contradicting consistency.

The union $\Delta ={\bigcup }_n{\Gamma }_n$ is consistent, since a finite proof of a contradiction would already use premises in one stage. It decides every formula. It is also deductively closed: if $\Delta ⊢\psi$ and $\psi \notin \Delta$, then $\neg \psi \in \Delta$, violating consistency.

Give an atomic proposition $P$ the truth value true exactly when $P\in \Delta$. Induction proves the truth lemma. For negation, exactly one of $\psi ,\neg \psi$ lies in $\Delta$. For implication, if $\psi \to \chi \in \Delta$ and $\psi \in \Delta$, modus ponens gives $\chi \in \Delta$. Conversely, if $\psi \notin \Delta$, then $\neg \psi \in \Delta$ entails $\psi \to \chi$ by a classical propositional tautology; if $\chi \in \Delta$, it too entails $\psi \to \chi$. Hence membership of an implication agrees with its truth table. Other connectives follow from their definitions or the corresponding tautologies. Thus the assignment satisfies $\Delta$, and therefore $\Gamma$.

Now if $\Gamma ⊬\varphi$, the set $\Gamma \cup \{\neg \varphi \}$ is consistent, by the deduction theorem for propositional logic and classical double-negation elimination. Its satisfying assignment is a model of $\Gamma$ in which $\varphi$ is false. Contraposition provesThe reverse implication is soundness theorem for propositional logic, proved by checking axioms and inference rules preserve truth.

For uncountably many primitive propositions, replace the enumeration by a maximal-consistent extension using Zorn lemma. The union of a chain of consistent extensions is consistent for the same finite-proof reason. Maximality then decides each formula: if adjoining $\psi$ creates inconsistency, the deduction argument gives $\neg \psi$ already in the extension. The same truth lemma applies with no change. Alternatively, well-order the formulas and run the same recursion with unions at limit stages. This modification uses a choice principle, unlike the countable enumeration argument.

For a connected plane drawing, Euler formula for a connected planar graph isFor a simple planar graph with $v\ge 3$, counting edge sides around faces gives $3f\le 2e$ and hence $e\le 3v-6$. Thus some vertex has degree at most five. A tree or a graph with bridges obeys the same bound; a face boundary is counted as a closed walk with edge multiplicity, and the small cases are immediate.

Induct on the number of vertices to prove the five colour theorem. Remove a vertex $v$ of degree at most five and five-colour the remainder. If fewer than five colors appear at its neighbours, extend the coloring. Otherwise it has five neighbours in their cyclic order, with colors $1,2,3,4,5$. If the color-1 neighbour is not connected to the color-3 neighbour by a path using only colors 1 and 3, swap these colors in the component containing the former, freeing color 1 at $v$. If they are connected, that path together with its two edges to $v$ is a simple closed curve. The colour-2 and colour-4 neighbours lie on opposite sides, so cannot be joined by a path using only colors 2 and 4, which would have to cross it. Swap colors in the component containing the colour-2 neighbour and give $v$ color 2. This establishes the induction without the four colour theorem.

For a triangle-free simple planar graph with $v\ge 3$, the analogous bound is $e\le 2v-4$, so some vertex has degree at most three. One can prove the bound for connected graphs with no bridges by $4f\le 2e$; bridges and isolated components are then joined or split off, with the small tree cases checked directly. Every subgraph is still triangle-free and planar. Successively remove a vertex of degree at most three, and color in reverse order with four colors. Thus triangle-free planar graphs have chromatic number at most four.

Finally, let $G$ be minimal 5-chromatic. Removing any vertex leaves a graph colorable with four colors. If its degree is at most three, that coloring extends immediately. If its degree is four, either a colour is unused at its neighbours, or all four appear once in cyclic order. The same two-path argument, now using opposite pairs 1,3 and 2,4, permits a Kempe chain interchange freeing one colour. Therefore a planar minimal 5-chromatic graph must satisfyWithout planarity only $\delta (G)\ge 4$ follows from the elementary extension argument. The complete graph $K_5$ is a counterexample to the stronger assertion: it is minimal 5-chromatic and every vertex has degree four. Deleting an edge allows its endpoints to share a color; deleting a vertex also reduces the required number of colors.

The irreducible cubic is separable, and its Galois group acts transitively on its three roots. The only transitive subgroups of $S_3$ areFor the cycle $\sigma :(\alpha ,\beta ,\gamma )\mapsto (\beta ,\gamma ,\alpha )$, the Lagrange resolvent for a cubic obeys $\sigma (x)={\zeta }^{2}x$. A transposition interchanging $\beta ,\gamma$ sends $x$ to $y=\alpha +\zeta \gamma +{\zeta }^2\beta$. Since $\zeta \in K$, these scalars are fixed by every automorphism. Thus the two possibilities for the image set areThese are descriptions of sets, so coincident values or a zero resolvent are not being asserted distinct.

The previous permutation calculation shows that every automorphism either preserves $x^3,y^3$ separately or interchanges them. Their sum and product are therefore fixed by the Galois group and belong to $K$, proving the quadratic assertion.

For the depressed cubic, $\alpha +\beta +\gamma =0$, $\alpha \beta +\alpha \gamma +\beta \gamma =b$, and $\alpha \beta \gamma =-c$. Using $1+\zeta +{\zeta }^2=0$ givesand henceAlso $x^3{y}^3=-27b^3$. The desired polynomial isIts discriminant is $729c^2+108b^3=-27D$, where $D=-4b^3-27c^2$. Here $-27$ is a square in $K$, since $[3(\zeta -{\zeta }^2){]}^2=-27$.

One can justify the group criterion directly even when one resolvent vanishes. The nonzero root-difference producthas $d^2=D$ and changes sign exactly under odd root permutations. It is fixed by the entire group exactly when the group is contained in $A_3$. If $D$ is a square in $K$, then $d$ equals one of its two square roots in $K$; conversely, a fixed $d$ lies in $K$. ThereforeSeparability ensures $D\ne 0$, and the characteristic hypotheses ensure that all divisions and the sign argument are valid.

The circle group is $U(1)=\{z\in \mathbb{C}:|z|=1\}$ under multiplication. For continuous finite-dimensional complex representations, its irreducibles are the one-dimensional charactersA group representation is a continuous homomorphism to the invertible linear maps; it is irreducible when it has no proper nonzero invariant subspace. Compactness permits an invariant Hermitian inner product by averaging. Since the resulting unitary operators commute for $U(1)$, simultaneous diagonalization reduces an irreducible to a character, and the continuous characters of the circle have the stated integer winding number.

The group $SU(2)$ consists of unitary two-by-two complex matrices of determinant one. Each has the unique formidentifying it homeomorphically with the unit 3-sphere in ${\mathbb{R}}^4$. This is the Spin group $\mathrm{Spin}(3)$. A unitary matrix is conjugate to $\mathrm{diag}(e^{i\theta },e^{-i\theta })$, and its conjugacy class is determined by $0\le \theta \le \pi$, or equivalently its trace $2\cos \theta$.

The irreducible representations of SU2 are $V_n={\mathrm{Sym}}^n({\mathbb{C}}^2)$ for integers $n\ge 0$, with dimension $n+1$. The symmetric power can be realized as homogeneous degree-$n$ polynomials in two variables, with the induced linear action. On the diagonal torus its eigenvalues are $e^{i(n-2j)\theta }$ for $j=0,\dots ,n$, so its character, the trace of the representing operator, isAt the endpoints use the continuous values ${\chi }_n(0)=n+1$ and ${\chi }_n(\pi )=(-1{)}^n(n+1)$. The highest-weight classification says this list is complete.

For the final action, multiplication of block matrices gives $(AB{)}_1=A_1{B}_1$, so conjugation is a linear group representation. Decompose the underlying three-dimensional space as $V_1\oplus V_0$. Its endomorphism space isThe two off-diagonal blocks are each $V_1$, since the invariant alternating form identifies $V_1^{\ast }$ with $V_1$. The scalar part of $\mathrm{End}(V_1)$ is $V_0$ and its traceless part is $V_2$: the same alternating form identifies traceless endomorphisms with symmetric tensors of degree two. The lower scalar block is a second $V_0$. ThusThe dimensions add to $2+4+3=9$, and its character is $2{\chi }_0+2{\chi }_1+{\chi }_2$.

A rational root of the monic cubic would be one of $\pm 1,\pm 3$, and substitution excludes all four. A reducible cubic over $\mathbb{Q}$ would have a rational root, so the polynomial is irreducible andIts polynomial discriminant is $-4(-1{)}^3-27(3{)}^2=-239$. The integer 239 is prime: it has no prime divisor among $2,3,5,7,11,13$, the primes not exceeding its square root.

The discriminant-index formula for an integral lattice for an integral primitive element isBoth discriminants are integers, and the left side is $-239$. Its squarefreeness forces the positive index to be one. Since $\alpha$ is an algebraic integer by its monic equation,

The Snake lemma applies to a commutative diagram of modules with exact rows $0\to A^{\prime }\stackrel{i^{\prime }}{\to }{B}^{\prime }\stackrel{j^{\prime }}{\to }{C}^{\prime }\to 0$ and $0\to A\stackrel{i}{\to }B\stackrel{j}{\to }C\to 0$, and vertical maps $f,g,h$. It supplies the exact sequenceFor $c^{\prime }\in \ker h$, choose $b^{\prime }$ with $j^{\prime }{b}^{\prime }=c^{\prime }$. Commutativity gives $jg{b}^{\prime }=0$, so $g{b}^{\prime }=i(a)$ for a unique $a\in A$. Define $\delta (c^{\prime })=[a]$ modulo $f(A^{\prime })$. Changing $b^{\prime }$ by $i^{\prime }(a^{\prime })$ changes $a$ by $f(a^{\prime })$, proving well-definedness. This construction is additive. Exactness follows by the same lift-and-chase: $\delta (c^{\prime })=0$ exactly when the lift can be adjusted into $\ker g$; a class in $\mathrm{coker}f$ maps to zero in $\mathrm{coker}g$ exactly when it is obtained from such a lift. The remaining kernel and cokernel positions follow directly from row exactness.

For an open cover $X=U\cup V$, use the short exact sequence of singular chain complexeswhere the last complex consists of chains whose simplices lie in one member of the cover. This is exact because a simplex present in both summands lies in their intersection. Barycentric subdivision and its chain homotopy to the identity show that this small-chain inclusion induces an isomorphism on homology: compactness of each simplex and a Lebesgue-number argument place sufficiently subdivided simplices inside the cover.