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

Choose an integer $b$ whose reduction is a primitive root modulo $p$. At least one of $b,b+p$ satisfies $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$, because the binomial theorem givesand the added coefficient is nonzero modulo $p$. Both choices still generate the multiplicative group modulo $p$. Choose such a $g$ and write $g^{p-1}=1+up$ with $p\nmid u$.

For $k\ge 1$ and $p\nmid v$, another binomial expansion showsThe intermediate binomial coefficients are divisible by $p$, and the final term also has valuation at least $k+2$ because $p$ is odd. Induction therefore givesThus $g^{p-1}$ has order exactly $p^{n-1}$ modulo $p^n$. The order of $g$ itself is divisible by $p-1$, by reduction modulo $p$, and divides the number $p^{n-1}(p-1)$ of invertible residue classes. Its order must consequently be precisely that number. This proves the lifting a primitive root to odd prime powers result andFor the requested example choose $g=2$. Modulo $11$, $2^5\equiv -1$ and $2^2\not\equiv 1$, excluding the proper divisors $1,2,5$ of ten, so its order is ten. Also $2^{10}-1=1023=11\cdot 93$, which is not divisible by $11^2$. Hence

The polynomial Runge theorem states that, for a compact set $K\subset \mathbb{C}$ with connected complement and a function $f$ holomorphic on a neighborhood of $K$, for every $\epsilon >0$ there is a polynomial $P$ such thatThe connected-complement hypothesis permits polynomial approximation rather than approximation by rational functions with poles in bounded complementary components.

Use the Runge exhaustion of a slit disk, with the principal argument $-\pi <\arg z<\pi$:These are nested compact subsets of $\Omega$. Their complements are connected: the inner disk and exterior region join through the omitted sector around the negative real radius. Every compact subset of $\Omega$ has positive distance from zero, the unit circle and the slit, so it is contained in $K_m$ for all sufficiently large $m$.

Since $f$ is holomorphic on $\Omega$, it is holomorphic on a neighborhood of each $K_m$. The polynomial Runge theorem gives $P_m$ with ${\sup }_{K_m}|P_m-f|<1/m$. Given any compact $K\subset \Omega$, eventually $K\subseteq K_m$, so the same estimate holds on $K$. ThereforeThe nested exhaustion makes this one sequence work simultaneously on all compact subsets.

On the unit three-ball $B^3$, the distance in the Poincare ball model is the infimum of the lengthsover piecewise smooth paths joining the two points. Equivalently the hyperbolic metric as a metric-space distance isIt has curvature-minus-one normalization; in particular $d(0,x)=2\mathrm{artanh}|x|$.

For a nonempty finite set $p_1,\dots ,p_m$, define $R(x)={\max }_{j}d(x,p_j)$. The triangle inequality gives $|R(x)-R(y)|\le d(x,y)$, so $R$ is continuous. Take $R_0=R(p_1)$. Any improving center satisfies $d(x,p_1)\le R(x)\le R_0$, and thus lies in the closed hyperbolic ball $K=\overline{B}(p_1,R_0)$.

This ball is compact: an isometry sending $p_1$ to the origin identifies it with the Euclidean closed ball of radius $\tanh (R_0/2)<1$, and the Euclidean and hyperbolic topologies agree inside $B^3$. The continuous function $R$ attains a minimum on $K$. Centers outside $K$ have $R>R_0$, so this is also the global minimum. Its associated closed ball proves a minimum enclosing ball in hyperbolic space exists. For the empty finite set, any center and radius zero suffice.

A binary cyclic code is a linear subspace of ${\mathbb{F}}_2^N$ invariant under cyclic coordinate shift. Associate a word $(c_0,\dots ,c_{N-1})$ to $\sum c_j{X}^j$ in ${\mathbb{F}}_2[X]/(X^N-1)$. Cyclic shift is multiplication by $X$, so linearity and shift invariance make the code an ideal of this quotient.

Its inverse image in ${\mathbb{F}}_2[X]$ is an ideal containing $(X^N-1)$. Since a polynomial ring over a field is a principal ideal domain, that inverse image is $(g)$ for a unique monic polynomial $g$. Containment gives $X^N-1=gh$ for some polynomial $h$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code $g$ is also its monic word polynomial of smallest degree. For the zero code use $g=X^N-1$, whose residue is zero. Conversely every monic divisor defines a cyclic code, proving the full correspondence.

Over ${\mathbb{F}}_2$,The quartic factor has no root in ${\mathbb{F}}_2$. The only monic irreducible quadratic over this field is $X^2+X+1$, and division leaves remainder $X+1$, so the quartic is not divisible by it. A reducible quartic with no linear factor would have two irreducible quadratic factors; hence this quartic is irreducible. There are exactly four binary cyclic codes of length five, given by the generator polynomials of a cyclic codeThey are respectively the full space, the even-weight code, the repetition code and the zero code, with dimensions $5,4,1,0$.

These are nested Poisson regression models with independent counts and the default log link function. If $x_i$ is biomass and $g_i$ is the three-level pH group, model 1 specifies $\log {\mu }_i=\alpha +\beta x_i$: one common intercept and slope. Model 2 specifies $\log {\mu }_i={\alpha }_{g_i}+\beta x_i$: three group-specific intercepts and a common slope. Model 3 specifies $\log {\mu }_i={\alpha }_{g_i}+{\beta }_{g_i}{x}_i$: three intercepts and three slopes, because the multiplication syntax includes both main effects and their interaction. The parameter counts are therefore $2,4,6$.

The analysis of deviance compares model 1 against model 2 by testing equality of the three intercepts, conditional on a common biomass slope. The likelihood-ratio test statistic is $407.67-99.24=308.43$ with two additional parameters, giving the reported tiny p-value. The next test compares model 2 against model 3 by testing equality of their three slopes. Its statistic is $99.24-83.20=16.04$, again with two degrees of freedom and reported $p=3.288\times 10^{-4}$. Both restrictions are rejected. Thus model 3 is the supported choice: both baseline richness and its biomass dependence vary with pH. Under the Poisson assumptions, residual deviance $83.20$ on $84$ residual degrees of freedom is also consistent with a satisfactory fit, although these nested tests themselves establish improvement rather than every possible aspect of model adequacy.

The prediction from model 2 is on its linear-predictor scale. Exponentiating gives its fitted means. The final expression is twice the saturated log likelihood minus the model-2 log likelihood, i.e. the Poisson deviance of model 2. ConsequentlyIn the saturated model each mean equals the corresponding observed count, with the usual continuous convention for a zero count.

Balancing the viscous and bending terms gives $\zeta \omega h\sim Ah/{\ell }^4$, so the elastohydrodynamic penetration length isInserting $h=h_0\mathrm{Re}[e^{i\omega t}F(x/\ell )]$ into the linear equation yields $F^{\prime \prime \prime \prime }=-iF$, with $F(0)=1$, $F^{\prime \prime }(0)=0$ and decay at infinity. Write $C=\cos (\pi /8)$, $S=\sin (\pi /8)$. Of the four roots of ${\lambda }^4=-i$, precisely two have negative real part:The two decaying solutions are $e^{{\lambda }_L\eta }$ and $e^{{\lambda }_R\eta }$, and the general decaying response is their linear combination. Both coefficients are nonzero: if one vanished, $F^{\prime \prime }(0)=0$ would force the other to vanish, contradicting $F(0)=1$.

Their real parts in the time-dependent response are proportional toConstant phases move respectively with velocities $-\omega \ell /S$ and $\omega \ell /C$, so these are damped travelling waves moving left and right. Since $S<C$, the right-going wave has the longer attenuation length and dominates at large $x$. Thus the less strongly damped, outward-moving wave dominates the far-field response. This is the oscillatory bending of a moment-free semi-infinite filament; the two boundary conditions determine its amplitudes without needing them explicitly here.

In Glendinning chaos, a continuous interval map is chaotic when some positive iterate has a horseshoe for an interval map. In the interval version, one may take an open interval $J$ containing two disjoint open intervals $K_0,K_1$ with $F^m(K_0)=F^m(K_1)=J$.

Let a three-cycle be ordered $a<b<c$. There are only two possible cyclic orderings; reflection of the coordinate interchanges them, so assume $F(a)=b$, $F(b)=c$, $F(c)=a$. ThenAlso $F(b)=c$ and $F(c)=a$, so the intermediate value theorem gives $d\in (b,c)$ with $F(d)=b$, whence $F^2(d)=c$. Both $[a,b]$ and $[b,d]$ therefore map across $[a,c]$ under $F^2$.

To obtain exact open-interval images, use the following elementary first-passage observation. A continuous function on $[r,s]$ with endpoint values $a,c$ has a subinterval on which its endpoint values are $a,c$ and all interior values lie strictly between them: take the first hit of the second level, then the last hit of the first level before it. The intermediate value theorem makes its interior image exactly $(a,c)$. Apply this to the two intervals, reversing endpoint order on the first. Their selected interiors $K_0\subset (a,b)$ and $K_1\subset (b,d)$ are disjoint and lie in $J=(a,c)$, withThis proves the three-cycle forces a two-iterate interval horseshoe result and establishes the required horseshoe for $F^2$.

Consider $G(z)=(e^{iz}-1)/(iz)$, extending it at zero by $G(0)=1$. It is holomorphic in the upper half-plane and on its boundary, and on large upper semicircles $G(z)=O(1/|z|)$ because $|e^{iz}|\le 1$. For real $t$, indent the upper-half-plane contour above the pole of $G(z)/(z-t)$. The clockwise indentation contributes $-i\pi G(t)$, while the large semicircle contributes zero in the limit. The Cauchy integral theorem givesWith the stated Hilbert transform convention this is $\mathcal{H}G(t)=-iG(t)$. ButTaking real parts yields the Hilbert transform of the sinc function:At $t=0$ the right side has limit zero; the same value follows by oddness of the principal-value integrand. The apparent singularity of $G$ at zero is removable, so the contour calculation is valid there too.

Take the sheet to lie in the $x_1{x}_2$ plane, with lengths $a,b$ in those directions. Its surface density is $M/(ab)$. Reflection symmetry about the coordinate axes makes the off-diagonal entries of the inertia tensor zero. Its principal moments of inertia areand similarly $I_2=M{a}^2/12$. Since $I_3$ integrates $x_1^2+x_2^2$, the perpendicular axis theorem gives

Set ${\omega }_1=u$, ${\omega }_2=\Omega +v$, ${\omega }_3=w$ and retain terms linear in the perturbations in Euler equations for a torque-free rigid body. Using $I_3=I_1+I_2$ givesConsequently $\ddot{u}={\beta }^2{\Omega }^{2}u$, where $\beta =\sqrt{(a^2-b^2)/(a^2+b^2)}>0$. For $\Omega >0$ the growing solution isThere is also a decaying mode with the opposite exponent. For negative $\Omega$, select the exponent $+\beta |\Omega |$ as the growing one. This is the intermediate axis theorem: steady rotation about the intermediate principal inertia axis is unstable whenever $\Omega \ne 0$.

With a prime denoting conformal-time differentiation, $a^{\prime }=a\dot{a}$ and $\mathcal{H}=a^{\prime }/a=\dot{a}$. Multiplying the Friedmann equation by $a^2$ gives ${\mathcal{H}}^2+k{c}^2=8\pi G\rho a^2/3$, and henceThe Friedmann acceleration equation and $P=w\rho c^2$ giveDifferentiate $\Omega -1=k{c}^2/{\mathcal{H}}^2$ and substitute this expression:For $k=0$, $\Omega =1$ identically and the same equation holds directly. The relations assume $\mathcal{H}\ne 0$, as is true on the expanding branch in the question.

For pressureless matter, $w=0$, the cosmological density parameter flow points away from $\Omega =1$: initial $\Omega >1$ increases, while $0<\Omega <1$ decreases. In the closed case the expanding branch can end at a turnaround, where $\mathcal{H}=0$ and this density parameter diverges. For vacuum domination, $w=-1$, the sign reverses: values above one decrease and positive values below one increase toward one. The plotted curves are representative conformal-time solutions with $c=1$ and separately chosen origins; inflationary future infinity occurs at a finite conformal time.

In a decelerating matter or radiation era, small deviations from flatness grow: near one, $d\log |\Omega -1|/d\log a\simeq 1+3w>0$. Observed near-flatness therefore requires extremely small earlier deviations, the flatness problem. During accelerated expansion with $w<-1/3$, this exponent is negative and curvature is driven toward negligible relative size. For $w=-1$, $|\Omega -1|$ decays approximately as $a^{-2}$. Sufficiently long cosmic inflation supplies the inflationary solution of the flatness problem before ordinary decelerating evolution resumes.

Put $\alpha =\sqrt{N}$ and use conventional convergent indexing starting at zero; the same argument covers all the printed positive indices. The continued fraction complete quotients satisfy ${\alpha }_{j+1}=1/({\alpha }_j-a_j)$, $a_j=\lfloor {\alpha }_j\rfloor$. After the first step they exceed one, while their algebraic conjugates lie in $(-1,0)$. Indeed ${\alpha }_1^{\prime }=1/(-\sqrt{N}-a_0)\in (-1,0)$, and if ${\alpha }_j^{\prime }\in (-1,0)$ with $a_j\ge 1$, then $1/({\alpha }_j^{\prime }-a_j)\in (-1,0)$.

Write ${\alpha }_{k+1}=(\sqrt{N}+m)/d$, where $m,d$ are integers and $d>0$. This form follows by rationalization at each step: $m_{j+1}=a_j{d}_j-m_j$ and $d_{j+1}=(N-m_{j+1}^2)/d_j$, starting from $m_0=0,d_0=1$. The two conjugate inequalities giveso $d<2\sqrt{N}$. The standard convergent recursions also giveSubstitute the displayed form of ${\alpha }_{k+1}$ and compare rational and irrational coefficients. This yields $p_k=m{q}_k+d{q}_{k-1}$ and $N{q}_k=m{p}_k+d{p}_{k-1}$. Therefore the small norm residues from square-root continued fractions obeyThe initial convergent satisfies the same relation with the usual $p_{-1}=1,q_{-1}=0$. This avoids the insufficient estimate obtained by merely replacing the convergent error with $1/q_k^2$.

For integer factorization, choose a factor base of small primes for which $N$ is a quadratic residue, together with $-1$ to record negative residues; a prime dividing $N$ already supplies a factor. Test the small nonzero integers $r_k=p_k^2-N{q}_k^2$ for being B-numbers. Complete factorization over the base records each prime exponent modulo two. Once enough relations are collected, linear algebra over ${\mathbb{F}}_2$ can choose a nonempty subcollection whose exponent sum is even, including the sign. ThenIf $X\not\equiv \pm Y(\mathrm{mod}N)$, one of $\gcd (X-Y,N)$ or $\gcd (X+Y,N)$ can yield a nontrivial factor. Relations with a noninvertible $p_k$ may already give a factor through its gcd. The small-residue bound makes smoothness more likely; it does not guarantee that any one dependency gives a nontrivial factor.

A subgroup of the Möbius group ${\mathrm{PSL}}_2(\mathbb{C})$ is a discrete subgroup when the identity is isolated in its induced topology, equivalently every group element is isolated. We prove the compact-set criterion for a properly discontinuous group action: for every compact $K\subset {\mathbb{H}}^3$, only finitely many $g\in G$ satisfy $gK\cap K\ne \varnothing$.

Fix an origin $o$ and take $K\subseteq \overline{B}(o,R)$. If $x\in K$ and $gx\in K$, the triangle inequality and invariance of hyperbolic distance giveThe set of Möbius isometries with $d(o,go)\le 2R$ is compact. To see this explicitly, represent an isometry by a determinant-one complex matrix and use singular-value decomposition:The compact factors fix $o$, and the diagonal factor moves it hyperbolic distance $s$, as seen from the vertical dilation by $e^s$ in upper half-space. Thus the bounded-displacement set is the continuous image of $\mathrm{SU}(2)\times [0,2R]\times \mathrm{SU}(2)$, modulo central signs.

By the allowed closedness fact, its intersection with $G$ is a closed discrete subset of a compact space, hence finite. Otherwise an infinite sequence would accumulate in that intersection, contradicting isolation of its limit point. This proves every discrete Möbius subgroup acts properly discontinuously on hyperbolic three-space. Finite stabilizers are allowed; discreteness alone does not imply a free action.

Write ${\theta }_i=\theta ({\mu }_i)$ and ${\eta }_i=x_i^T\beta =g({\mu }_i)$. Differentiating ${\mu }_i=K^{\prime }({\theta }_i)$ gives $d{\mu }_i/d{\theta }_i=V({\mu }_i)$, soIn the independent exponential dispersion family, only $[y_i{\theta }_i-K({\theta }_i)]/{\sigma }_i^2$ depends on $\beta$. Its derivative therefore gives the score functionThe residuals are independent, have mean zero and variance ${\sigma }_i^{2}V({\mu }_i)$. Consequently their score covariance is the Fisher information matrix:This also equals minus the expected likelihood Hessian under the usual regularity conditions.

For the canonical link function, $g(\mu )=\theta (\mu )$ and $g^{\prime }=1/V$, soTo obtain the maximum-likelihood estimate, solve $U(\hat{\beta })=0$, for example with Fisher scoring iterations ${\beta }^{new}=\beta +\mathcal{I}(\beta {)}^{-1}U(\beta )$. Equivalently use iteratively reweighted least squares, with weights $[{\sigma }_i^{2}V({\mu }_i)g^{\prime }({\mu }_i{)}^2{]}^{-1}$ and working response ${\eta }_i+(y_i-{\mu }_i)g^{\prime }({\mu }_i)$. Since ${\sigma }_i^2={\sigma }^2{a}_i$, the common dispersion scale cancels from this update for $\beta$. A nonsingular information matrix and a finite interior likelihood maximum are needed; iteration does not assert those for every possible dataset.

For a flow, a hyperbolic fixed point has no eigenvalue of its linearization with zero real part; a nonhyperbolic fixed point has at least one such eigenvalue. At $(\mu ,0)$ the eigenvalues are $-\mu ,1-\mu$, while at $(0,\pm 1)$ they are $\mu +1,-2$. Thus nonhyperbolicity occurs at the two stated parameters. The following centre manifold reductions show the associated actual bifurcations.

Near $(1,0)$ put $X=x-\mu$, $Y=y$, $\nu =\mu -1$. The transformed equations areAt $\nu =0$, the non-extended stable subspace is the $X$ axis and the centre subspace is the $Y$ axis. In the extended centre manifold, write $X=h(Y,\nu )$, with $h(0,\nu )=0$. The symmetry $Y\mapsto -Y$ allows an even graph. At quadratic order its invariance equation has left side of degree at least three and right side $-h+Y^2$, so $h=Y^2+O(\nu Y^2,Y^4)$. Substitution givesThis is a supercritical pitchfork bifurcation in parameter $-\nu =1-\mu$. The central branch is stable for $\mu >1$ and unstable for $\mu <1$ near one; the two nonzero branches for $\mu <1$ are stable. At the bifurcation itself the cubic term attracts on the centre manifold.

Near $(0,1)$ put $X=x$, $Y=y-1$, $\nu =\mu +1$. ThenAt $\nu =0$, the stable subspace is $X=0$ and the centre line is $Y=-X/2$. Thus the leading extended centre graph is $Y=-X/2+O(X^2,\nu X)$, and the reduced flow isThis is a transcritical bifurcation: $X=0$ is stable for $\nu <0$, while the branch $X=\nu /2+\cdots$ is stable for $\nu >0$; the opposite branches are unstable. At the critical point the quadratic term is only one-sided attracting.

The exact additional branch in $y>0$ isIt meets $(\mu ,0)$ at $\mu =1$ and $(0,1)$ at $\mu =-1$, displaying the connecting pitchfork and transcritical branches in a quadratic-product flow. Its Jacobian has determinant $1-{\mu }^2$ and trace $(\mu -3)/2$. Hence it is stable for $-1<\mu <1$ and a saddle for $\mu <-1$. The negative-$y$ companion is needed for the pitchfork sketch near $(1,0)$; no separate analysis of $(0,-1)$ is required.

With Hamilton's equations ${\dot{q}}_j=H_{p_j}$ and ${\dot{p}}_j=-H_{q_j}$, the chain rule givesFor the vortex problem, combine the two ordered terms for each unordered pair, writing $D_{ij}=(p_i-p_j{)}^2+(q_i-q_j{)}^2$ and $H=-(\kappa /2){\sum }_{i<j}\log D_{ij}$. Since $F_{q_j}=2q_j$, $F_{p_j}=2p_j$, its pairwise contribution to the Poisson bracket isEvery pair cancels, so $[F,H]=0$ and ${\sum }_j(q_j^2+p_j^2)$ is conserved along any collision-free solution. The logarithmic Hamiltonian is undefined at coinciding vortices, so the derivation applies on its natural domain.

For a regular periodic energy orbit, differentiate the action integral with respect to its energy. On a branch $H(p,q)=E$, implicit differentiation gives $\partial p/\partial E=1/H_p=1/\dot{q}$. ThusThe integral follows the entire orbit, with its orientation; at turning points this formula is interpreted by the limiting integral from each branch. It is valid for a smooth family of nonseparatrix periodic orbits.

An adiabatic invariant means that the action variable remains constant to leading order when the external parameter changes on a timescale much longer than the orbital period. Denote that parameter by $\lambda$. With $H(0,\lambda )=0$, the displayed identity integrates toIf the parameter change decreases $T(J,\lambda )$ for every intervening action $J$, this integrand increases pointwise. At the adiabatically fixed positive $I$, the energy increases. This uses the phrase “with any $I$” as a statement about the family of orbits, not merely a period decrease at a single selected action; that weaker premise alone would not determine the integral.

For Hartogs theorem, collect all well-order relations on all subsets of a set $x$. They form a set, since the relations belong to the power set of $x\times x$. Replacement collects their ordinal order types in a set $T$. DefineIf there were an injection $\alpha \to x$, transfer the well-order of $\alpha$ to its image. Its type would put $\alpha$ in $T$, giving $\alpha +1\le \alpha$, impossible. Thus some ordinal does not inject into $x$, without using choice.

Assume the axiom of choice and let a nonempty partially ordered set $P$ have an upper bound for every chain. Suppose it has no maximal element. Choose, from every subset of $P$ with a nonempty set of strict upper bounds, one such strict upper bound. Every chain has a strict upper bound: first take an upper bound and then a strictly larger element, using the absence of maximal elements. Take a Hartogs ordinal $\alpha$ for $P$. Transfinite recursion chooses $p_{\beta }$, for each $\beta <\alpha$, strictly above all previously chosen elements. Their predecessors form a chain at every stage, so this recursion is defined and strictly increasing. It gives an injection $\alpha \to P$, contradicting the choice of $\alpha$. Hence $P$ has a maximal element, proving Zorn's lemma.

For the well-ordering theorem, take a choice function on the nonempty subsets of $x$ and recursively choose an element of $x$ not previously selected. If this process had not exhausted $x$ at any stage below its Hartogs ordinal $\alpha$, it would define an injection $\alpha \to x$, again impossible. Therefore it exhausts $x$ at some ordinal stage $\beta <\alpha$. Order each element by its unique selection index; this transfers the ordinal well-order to all of $x$. The empty set is already well-ordered. These proofs use transfinite recursion, not an unstated fixed-point theorem.

Define the multicolour graph Ramsey number $R_k(s_1,\dots ,s_k)$ as the least $n$ such that every colouring of the edges of the complete graph $K_n$ with $k$ colours contains, for some $i$, a complete subgraph on $s_i$ vertices all of whose edges have colour $i$.

Prove finiteness by induction on ${\sum }_i{s}_i$, temporarily allowing $s_i=1$. If some $s_i=1$, a single vertex supplies the required vacuous monochromatic clique, so the Ramsey number is one. Otherwise put $N_i=R_k(s_1,\dots ,s_i-1,\dots ,s_k)$, which is finite by induction, and takeFix a vertex $v$ and partition its other $n-1$ vertices according to the colour of their edge to $v$. Some colour-$i$ class has at least $N_i$ vertices: if every class had at most $N_i-1$, their total would be at most ${\sum }_i{N}_i-k=n-2$. In that class the inductive property either gives a colour-$j$ clique of size $s_j$ with $j\ne i$, or a colour-$i$ clique of size $s_i-1$. In the latter case add $v$. ThusIn particular the requested two-colour diagonal number is $R(s)=R_2(s,s)$, so it exists for every $s\ge 2$.

Now colour each positive integer by its partition class, say there are $k$ classes, and take $m=R_k(3,\dots ,3)$. Colour the edge $ij$, $1\le i<j\le m$, by the class of $j-i$. There is a monochromatic triangle $a<b<c$. Its three differences $x=b-a$, $y=c-b$, $z=c-a$ are positive integers in one class, andThis is the finite-Ramsey proof of the partition conclusion. The statement does not require $x$ and $y$ to be distinct.

The automorphisms satisfy ${\sigma }^n={\tau }^2=1$ and $\tau \sigma \tau ={\sigma }^{-1}$. The $n$ rotations $z\mapsto {\zeta }_n^{j}z$ and $n$ inversion maps $z\mapsto {\zeta }_n^j/z$ are all distinct, so the dihedral group $G$ has order $2n$, including the case $n=1$ when it has order two. The invariantis fixed by both generators.