Past exam of the mathematics course of the University of Cambridge / 2002

For a finite group $G$ acting on a set $X$, write $G_x=\{g\in G:gx=x\}$ for the stabilizer subgroup and $Gx=\{gx:g\in G\}$ for the orbit of $x$. The orbit-stabilizer theorem givesIndeed, $g{G}_x\mapsto gx$ is a bijection from the left cosets of $G_x$ onto $Gx$: two images agree precisely when $h^{-1}g\in G_x$. Each coset has $|G_x|$ elements, proving the formula.

Place the cube vertices at $(\pm 1,\pm 1,\pm 1)$. The four vertices whose coordinate product is $+1$ form $T$; those with product $-1$ form $T^{\prime }$. Within either set, two distinct vertices differ in exactly two coordinates, so every edge has length $2\sqrt{2}$ and each set is a regular tetrahedron.

A member of the cube rotation group is a signed permutation matrix of determinant one. There are $3!$ permutations of the coordinate axes and four choices of signs for each permutation that give determinant one, so $|G|=24$. Such a matrix maps a coordinate-product class to a coordinate-product class. Moreover, the rotation through a quarter-turn $(x,y,z)\mapsto (-y,x,z)$ interchanges the classes. Thus the orbit of $T$ consists of exactly $T,T^{\prime }$. By the orbit-stabilizer theorem, the tetrahedron stabilizer in the cube rotation group has order

The fundamental theorem of algebra says that every nonconstant polynomial with complex number coefficients has a root in the complex numbers. Repeated polynomial division by a factor of degree one therefore factors a degree-three polynomial with complex number coefficients into three factors of degree one, with algebraic multiplicities included.

For a matrix with complex number entries $A$ of size three, its characteristic polynomial is ${\chi }_A(t)=\det (tI-A)$, and its characteristic equation is ${\chi }_A(t)=0$. A complex number $\lambda$ is an eigenvalue exactly when $\lambda I-A$ is singular, equivalently when its null space contains a nonzero vector. Thus the three roots of the characteristic polynomial are the three eigenvalues counted with algebraic multiplicity.

For the specified matrix, expansion along the first row givesHence the eigenvalues are $1,1,-1$. Corresponding eigenvectors areThe matrix with these three columns has determinant $2i\ne 0$, so these eigenvectors are linearly independent. A repeated eigenvalue does not in general guarantee two independent eigenvectors; here they have been exhibited directly.

The limit of a sequence of real numbers is $a$ if, for every $\epsilon >0$, there is an integer $N$ such that $n\ge N$ implies $|a_n-a|<\epsilon$. It tends to positive infinity if, for every real $M$, there is an integer $N$ such that $n\ge N$ implies $a_n>M$.

If $a_n\to +\infty$, choose the latter threshold with $M=1/\epsilon$. Then $a_n>1/\epsilon >0$ eventually, so $|1/a_n|<\epsilon$. Thus $1/a_n\to 0$. The converse is false: $a_n=-n$ has reciprocal tending to zero and tends to negative infinity. The precise sign-free statement is given by reciprocal limits and escape in absolute value: $1/a_n\to 0$ is equivalent to $|a_n|\to \infty$.

If $a_n\to a\ne 0$, eventually $|a_n-a|<|a|/2$, and the triangle inequality gives $|a_n|>|a|/2$. ConsequentlyGiven $\epsilon >0$, take $N$ large enough that $|a_n-a|<\min (|a|/2,\epsilon |a{|}^2/2)$ for all $n\ge N$. This proves $1/a_n\to 1/a$ directly from the definition of the limit of a sequence.

Here is a nested-interval proof of the Bolzano-Weierstrass theorem. Put every term of the bounded real sequence in a closed interval $I_0=[-M,M]$, with $M>0$. Bisect this interval and choose a closed half containing infinitely many terms. Repeating gives nested closed intervals $I_j=[l_j,r_j]$, each containing infinitely many sequence terms, with length $2M/2^j$.

By the least-upper-bound property, $x_{\ast }={\sup }_j{l}_j$ exists. For each $j$, every lower endpoint lies at most $r_j$, while $l_j\le x_{\ast }$; hence $x_{\ast }\in I_j$. Choose increasing indices $n_j$ with $a_{n_j}\in I_j$, possible because each interval contains infinitely many terms. ThenThus every bounded real sequence has a convergent subsequence.

For a sequence with no convergent subsequence, take $a_n=n$: any subsequence has $n_j\ge j$, so its terms tend to positive infinity rather than to a finite limit of a sequence. For an unbounded sequence with a convergent subsequence, take $a_{2n}=0$ and $a_{2n-1}=n$. Its odd terms are unbounded, while its even subsequence converges to zero.

Take the scalene triangle vertex set $T=\{(0,0),(1,0),(0,2)\}$. Its edge lengths are $1,2,\sqrt{5}$. Each vertex has a different unordered pair of incident edge lengths. A Euclidean isometry preserving the set must preserve these pairs, and therefore fixes every vertex.

To justify rigidity of a scalene triangle fully, Euclidean distances from an arbitrary plane point to these three fixed points determine that point uniquely: subtracting its squared Euclidean distance to the origin from the other two squared Euclidean distances determines its two coordinates. Thus an isometry fixing the three vertices fixes every plane point. Only the identity preserves $T$.

For the general union of group translates, let $h\in G$. Left multiplication by $h$ permutes $G$, soTherefore $G\subseteq H$. This containment uses only the group action; the absence of symmetries of $T$ is not needed for the containment itself.

Use the same triangle and let $G$ consist of translations $x\mapsto x+m$ for $m\in {\mathbb{Z}}^2$. All its vertices have integer coordinates, and one vertex is the origin, soThe rotation through a quarter-turn $(x,y)\mapsto (-y,x)$ preserves this integer lattice, and hence belongs to $H$. It fixes the origin and is not the identity, whereas the only translation fixing the origin is the identity. It is therefore outside $G$, proving $G⊊H$. This is symmetry enlargement under group translates even though $T$ itself has trivial stabilizer subgroup.

Write a Möbius transformation as $g(z)=(az+b)/(cz+d)$, with $ad-bc\ne 0$, on the Riemann sphere. If $c\ne 0$, infinity is not fixed, and its finite fixed points solveThe pole $-d/c$ cannot solve this equation, since substitution gives $(ad-bc)/c\ne 0$. The quadratic has one or two distinct complex roots, so these give exactly one or two fixed points.

If $c=0$, then $a,d\ne 0$ and infinity is fixed. If $a\ne d$, there is one additional finite fixed point, namely $b/(d-a)$. If $a=d$ and $b\ne 0$, the transformation is a nonzero translation, with no finite fixed point. If $a=d$ and $b=0$, it is the identity and fixes the entire sphere.

Thus a nonidentity Möbius transformation has one or two fixed points; the identity has infinitely many. The examples $z\mapsto z+1$, $z\mapsto 2z$, and $z\mapsto z$ realize the three possibilities respectively.

Complex conjugation fixes $0,1,\infty$, but sends $i$ to $-i$, so it is not the identity. The preceding classification of fixed points of a Möbius transformation says that a nonidentity Möbius transformation has at most two fixed points. Since complex conjugation has at least three, it cannot be a Möbius transformation.

Take positive angles counterclockwise. The rotation sends the standard basis vectors to $(\cos \alpha ,\sin \alpha )$ and $(-\sin \alpha ,\cos \alpha )$. These images form the columns of its matrix, soThe columns are an orthonormal basis and the determinant is one, as required for a plane rotation.

Orient the axis towards $n=(3/5,4/5,0)$ and measure positive angles by the right-hand rule about $n$. The vectors $n$, $m=(-4/5,3/5,0)$ and $e_3=(0,0,1)$ form a positively oriented orthonormal basis, since $n\times m=e_3$. Its change-of-basis matrix isRelative to this basis, the rotation fixes the first coordinate and rotates the last two. Writing $c=\cos \alpha$ and $s=\sin \alpha$, its matrix in the standard basis is thereforeIn particular $Rn=n$, $Rm=cm+s{e}_3$, and $R{e}_3=-sm+c{e}_3$, verifying the axis and the direction of rotation. Reversing the chosen orientation of the axis replaces $\alpha$ by $-\alpha$.

A vector space over the real numbers is a set $V$ with an addition making it an abelian group and a scalar multiplication by $\mathbb{R}$ satisfying, for scalars $a,b$ and vectors $u,v$, the identities $a(u+v)=au+av$, $(a+b)v=av+bv$, $a(bv)=(ab)v$ and $1v=v$. A vector subspace is a nonempty subset closed under addition and scalar multiplication; a proper vector subspace is one unequal to $V$. A spanning set is a set whose finite linear combinations give every vector of $V$. A basis is a linearly independent spanning set. The dimension is the number of vectors in a basis, or its cardinality when the basis is infinite.

The sum of vector subspaces and their intersection of vector subspaces areBoth are vector subspaces: addition and scalar multiplication preserve the displayed forms or simultaneous membership. The intersection of vector subspaces is never empty because $0\in U\cap W$.

For the two given hyperplanes, adding and subtracting their defining equations gives $x_1=x_2$ and $x_3=x_4$. HenceThese two nonzero vectors are orthogonal, and consequently form an orthogonal basis of the intersection of vector subspaces. Put $u=(1,-1,-1,1)$ and $w=(1,-1,1,-1)$. Direct substitution gives $u\in U$, $w\in W$. Their dot products with $b_1,b_2$ vanish, and $u\cdot w=0$. Each defining equation of $U$ or $W$ is one nonzero linear constraint in four variables, so each vector subspace has dimension three. Thus each space has the indicated orthogonal basis:The last four vectors are nonzero and mutually orthogonal, so they are a basis of ${\mathbb{R}}^4$. They lie in $U+W$, proving $U+W=V$. The dimension identity is therefore verified numerically:

Use the least-upper-bound property as the least upper bound axiom: every nonempty set of real numbers bounded above has a least upper bound in $\mathbb{R}$. It implies convergence of a bounded increasing sequence: if $L$ is the supremum of its terms, then for every $\epsilon >0$ some term exceeds $L-\epsilon$, and all subsequent terms lie between that term and $L$. A bounded decreasing sequence converges by applying this argument to its negative.

The alternating series test states that if $b_n\ge 0$, $b_{n+1}\le b_n$, and $b_n\to 0$, then ${\sum }_{n\ge 1}(-1{)}^{n-1}{b}_n$ converges. To prove it, let $S_N$ denote its partial sums. The even partial sums are increasing because $S_{2m+2}-S_{2m}=b_{2m+1}-b_{2m+2}\ge 0$. The odd partial sums are decreasing because $S_{2m+3}-S_{2m+1}=-b_{2m+2}+b_{2m+3}\le 0$. Moreover,Completeness of the real numbers therefore gives a limit of a sequence for each subsequence, denoted $L_e,L_o$ respectively for the even and odd subsequences. Their difference is $S_{2m+1}-S_{2m}=b_{2m+1}\to 0$, so $L_e=L_o$. Every sufficiently late partial sum belongs to one of these two subsequences, proving convergence of the full sequence of partial sums. Multiplying the terms by $-1$ leaves convergence unchanged.

The positive terms $b_n=1/\log (n+1)$ decrease to zero. The alternating series test just proved therefore gives convergence of the signed series. It is conditional convergence: $\log (n+1)\le n$, so $b_n\ge 1/n$, and the absolute-value series dominates the divergent harmonic series.

The comparison test for series used here says that if $0\le c_n\le d_n$, convergence of $\sum d_n$ implies convergence of $\sum c_n$, while divergence of $\sum c_n$ implies divergence of $\sum d_n$. This follows by comparing increasing partial sums. For completeness, the harmonic series diverges because every block from $2^k$ to $2^{k+1}-1$ has sum at least $1/2$.

The absolute-value series can be grouped in pairs of nonnegative terms:Indeed, $1/n^2\le {\int }_{n-1}^n{x}^{-2}dx$ for $n\ge 2$, so these positive partial sums are bounded by two. Completeness of the real numbers proves their convergence. The triangle inequality bounds every late signed sum by the corresponding late absolute-value sum, so absolute convergence implies convergence. Thus the series converges absolutely.

Group three consecutive terms. Their block sum isSince $2n-1\ge n$ and $4n-1\ge 3n$ for $n\ge 1$, we have $|b_n|\le 1/(2n^2)$. The comparison test for series and the preceding proof of convergence of $\sum n^{-2}$ show that $\sum b_n$ converges absolutely.

This establishes convergence of the original partial sums at indices $3N$. Each intermediate partial sum differs from one of these by at most two of the original terms; those terms tend to zero. Thus all partial sums have the same limit of a sequence, which is the mechanism of convergence from fixed-length series blocks. The original series is not absolutely convergent, since its absolute-value series contains ${\sum }_n(2n-1{)}^{-1}\ge \frac{1}{2}{\sum }_n{n}^{-1}$. Therefore the original series converges conditionally.

Let $S_N={\sum }_{k=1}^N{a}_k$, with $S_0=0$. The indices in the $n$th dyadic block have one sign, soA convergent sequence of partial sums must be a Cauchy sequence: for every $\epsilon >0$, all sufficiently late pairs of partial sums differ by less than $\epsilon$. The displayed differences violate this necessary condition with $\epsilon =1/4$, at arbitrarily late endpoints. Thus the series diverges, even though its individual terms tend to zero. This dyadic-block alternation of reciprocal terms has growing block lengths; the fixed-length block argument of the previous part does not apply.

Let $f$ be continuous on a closed bounded interval $[a,b]$. First prove that $f$ is a bounded function. If it failed, we could choose $x_n\in [a,b]$ with $|f(x_n)|>n$. The Bolzano-Weierstrass theorem gives a subsequence $x_{n_j}\to x_{\ast }$. Because the interval is closed, $x_{\ast }\in [a,b]$. Continuity gives $f(x_{n_j})\to f(x_{\ast })$, contradicting $|f(x_{n_j})|>n_j\to \infty$.

Now let $M=\sup \{f(x):x\in [a,b]\}$, which exists by completeness of the real numbers and the bound just proved. Choose $y_n\in [a,b]$ with $f(y_n)>M-1/n$. A convergent subsequence has limit of a sequence $y_{\ast }\in [a,b]$, and continuity gives $f(y_{\ast })=M$. Applying the same argument to $-f$ gives attainment of the infimum. This proves the extreme value theorem: the maximum and minimum both exist and are attained. The argument also covers a one-point interval, where the conclusions are immediate.

Take $f_1(x)=1/x$. It is continuous on $(0,1)$ and unbounded as $x\to 0$ from the right.

Take $f_2(x)=x$. It is continuous and bounded on $(0,1)$, with infimum zero and supremum one, neither attained on this open interval.

Take the step functionIt is bounded between zero and one, and is discontinuous at $x=1/2$.

Use the reduced-denominator function unbounded on every interval:Every value is a finite real number. In any nondegenerate interval $[a,b]\subseteq [0,1]$, its interior contains infinitely many rational numbers, whereas there are only finitely many reduced fractions in $[0,1]$ with denominator at most any fixed $M$. Some rational number in $(a,b)$ therefore has denominator exceeding $M$. Hence the function is unbounded on every such interval. It reverses the positive values of the Thomae function rather than requiring an infinite value at any point.

The mean value theorem states that, if $f$ is continuous on $[a,b]$ and differentiable on $(a,b)$, with $a<b$, there is $c\in (a,b)$ such thatTo deduce it from Rolle's theorem, subtract the secant line: $k(t)=f(t)-f(a)-\frac{f(b)-f(a)}{b-a}(t-a)$. This function has the same continuity and differentiability properties and satisfies $k(a)=k(b)=0$. Rolle's theorem gives an interior point with $k^{\prime }(c)=0$, which is precisely the required equality.

If $h^{\prime }=0$ on $\mathbb{R}$, apply the mean value theorem on any $[x,y]$ with $x<y$. It gives $h(y)-h(x)=(y-x)h^{\prime }(c)=0$. Hence $h$ is constant.

For the differential equation, the product rule givesThe preceding result makes this product constant. Thus all solutions are $f(x)=C{e}^{ax}$, and differentiation verifies every such solution.

For the integral assertion, continuity ensures that $f$ is Riemann integrable on every finite closed interval. Use the usual orientation for an integral with negative upper endpoint. For $h\ne 0$, additivity of the integral givesThe absolute value of this expression is at most the supremum of $|f(t)-f(x)|$ on the segment joining $x$ and $x+h$. Continuity at $x$ makes this bound tend to zero for either sign of $h$. Consequently $F^{\prime }(x)=f(x)$, proving this form of the fundamental theorem of calculus.

Finally, a differentiable solution of the integral equation is continuous, so the fundamental theorem of calculus yields $g^{\prime }=g$; setting $x=0$ gives $g(0)=A$. The differential-equation calculation above now forcesConversely, $A+{\int }_0^{x}A{e}^{t}dt=A+A(e^x-1)=A{e}^x$, so this function satisfies the original integral equation. It is unique because every differentiable solution has already been forced to this form and this initial condition.

For a function with continuous derivatives through order $m+1$ on the interval between $0$ and $x$, the Taylor formula with integral remainder isThis is Taylor's theorem about zero; translation gives the formula about any other point. To prove it, the case $m=0$ is the fundamental theorem of calculus. For $m\ge 1$, integration by parts givesSubstitution into the formula at order $m-1$ proves the formula at order $m$ by induction. The integral estimate, valid also for negative $x$, isFor the smooth function satisfying $f^{(3)}=f$, each fixed derivative is continuous on $[-R,R]$ and hence is bounded there by the extreme value theorem. Thus a bound $M_j$ exists for every $j$. Differentiating the differential equation repeatedly gives $f^{(j+3)}=f^{(j)}$. Only the three functions $f,f^{\prime },f^{\prime \prime }$ are needed: take $M$ to be the maximum of their absolute-value bounds on $[-R,R]$. Then $|f^{(j)}(x)|\le M$ simultaneously for every $j\ge 0$ and $|x|\le R$.

At zero the derivatives consequently repeat the values $1,0,0$. Taylor's theorem therefore givesThe last limit of a sequence follows because the ratio of consecutive majorants is $R/(m+2)$, eventually less than $1/2$. Since $R$ is arbitrary, Taylor expansion from a periodic derivative equation provesThis proves convergence to the function using a remainder bound; it does not assume beforehand that a smooth function equals its Taylor series.

The characteristic equation of the homogeneous linear differential equation is $m^2+m-2=(m-1)(m+2)=0$, giving the homogeneous solution $A{e}^t+B{e}^{-2t}$. For the first forcing, a particular solution of the form $C{e}^{-t}$ gives $-2C=1$, soThe initial conditions impose $A+B=1/2$ and $A-2B=-1/2$, whence $A=1/6$, $B=1/3$. Thus the first solution isFor the second forcing, $e^t$ is already a homogeneous solution, so the usual exponential trial must be multiplied by $t$. Substitution of the particular solution $Ct{e}^t$ gives $3C{e}^t=e^t$, hence $C=1/3$. Now $y=A{e}^t+B{e}^{-2t}+t{e}^t/3$, and the initial conditions give $A+B=0$, $A-2B=-1/3$. Therefore the resonant solution isThe additional factor $t$ reflects resonance in a differential equation.

This is a separable differential equation. On the solution with $y<1$, integration from the initial condition givesThe right side lies in $[0,1)$, so taking its sine stays on the required branch. The solution isNear the origin, $1-\sqrt{1-x^2}=x^2/2+O(x^4)$, so $y=x^2/2+O(x^4)$ and the tangent line is horizontal. At the other end, $y\to \sin 1$, whileThus the curve has a vertical limiting tangent line as $x\uparrow 1$, even though $x=1$ is excluded from the domain.

For the direction field, the slope is nonnegative everywhere in the square. The segments are horizontal on $x=0$ and on $y=1$, become steeper as $x$ increases at fixed $y<1$, and become flatter as $y$ increases at fixed $x$. Near $x=1$ they are almost vertical unless $y$ is correspondingly close to one. The excluded corner $(1,1)$ has no single limiting slope: the ratio $(1-y^2)/(1-x^2)$ depends on the path of approach.

The indicator function $I_A$ equals one when the event $A$ occurs and zero otherwise. Its expected value is $\mathbb{E}{I}_A=\mathbb{P}(A)$. By linearity of expectation, no independence assumption is needed to obtainSince $I_i{I}_j=I_{A_i\cap A_j}$, including $p_{ii}=p_i$, the variance isIn particular, correlations between the events cannot simply be discarded.

Write $\mu =\mathbb{E}N$. If $\mu >0$, then $N=0$ implies $|N-\mu |\ge \mu$. Applying Chebyshev's inequality therefore givesEquivalently, the contribution of $N=0$ to $\mathbb{E}[(N-\mu {)}^2]$ is ${\mu }^2\mathbb{P}(N=0)$. A positive mean is necessary for the displayed ratio to be defined. If $\mu =0$, nonnegativity instead gives $N=0$ almost surely, and the printed ratio would be $0/0$.

After $n+1$ independent tosses, an even count arises in exactly two disjoint ways: an even count after $n$ tosses followed by a tail, or an odd count followed by a head. Independence of the last toss from the preceding ones therefore givesSubtracting the fixed point $1/2$ turns this into the linear recurrenceAs zero is even, ${\pi }_0=1$, so the probability isFor $p=1/2$ this is $1/2$ for every $n\ge 1$; for $p=0$ it is always one; for $p=1$ it alternates between one and zero according to the parity of $n$.

An integrating factor for a differential one-form is a nonzero function $\mu (x,y)$ for which $\mu (dy+fdx)$ is an exact differential, say $dF$. Then solutions lie on level sets $F=\text{constant}$. Locally, the compatibility condition is ${\partial }_x\mu ={\partial }_y(\mu f)$.

Here multiplication by $2y{e}^x$, which is nonzero for $y>0$, producesThe initial condition makes this first integral equal to $a^2$. Taking the positive branch yields the solutionon the connected interval containing zero where the radicand is positive. This domain restriction matters because the original differential equation is singular at $y=0$.

Completing the square gives $2x+x^2=(x+1{)}^2-1\ge -1$. As $y>0$, the differential equation consequently impliesAt $x=0$, $y^{\prime }=-a/2<0$. Thus, moving a little to the left from $y(0)=a\ge 1$, the curve rises above $a$. Throughout $y>1$ every segment of the direction field points downwards as $x$ increases, by the inequality above. Tracing backwards therefore makes $y$ rise further, so it cannot return to $y=1$. This graphical barrier argument proves $y>a\ge 1$ and $y^{\prime }<0$ for every $x<0$ on the solution. The explicit first integral also shows this branch extends throughout $x<0$: writing $t=-x>0$, the minimum of $e^t/t^2$ is $e^2/4>1$, so $a^2{e}^t-t^2>0$ for $a\ge 1$. Including the initial point, $y^{\prime }<0$ for all $x\le 0$.

For $a=1$ the curve is $y=\sqrt{e^{-x}-x^2}$ on $(-\infty ,b)$, where the strictly increasing function $x^2{e}^x$ has the unique positive root $x^2{e}^x=1$ at $b\simeq 0.703467$. The curve decreases through $(0,1)$ with slope $-1/2$ and reaches $(b,0)$ only as a limiting endpoint. Its derivative isAs $x\to -\infty$, $y\sim e^{-x/2}$ and $y^{\prime }\sim -\frac{1}{2}{e}^{-x/2}\to -\infty$. As $x\uparrow b$, the numerator tends to $-b^2-2b<0$ and the denominator to zero from above, so again $y^{\prime }\to -\infty$. More precisely, $y\sim \sqrt{b(b+2)(b-x)}$ at the endpoint. Both ends have the requested unbounded negative slope.

For the logistic differential equation, separate variables to obtain $\log |y/(1-ay)|=rt+C$ away from the constant solutions. Applying the positive initial condition givesThe formula also includes the constant solution $y_0=1/a$. Below $1/a$ positive solutions increase; above $1/a$ they decrease. They approach $1/a$ as $t\to \infty$. Equivalently, linearizing $F(y)=ry(1-ay)$ gives $F^{\prime }(0)=r>0$ and $F^{\prime }(1/a)=-r<0$. Thus zero is unstable and $1/a$ is asymptotically stable.