Past exam of the short options course of the University of Oxford / 2015 (A13752W1, ASO)

The original cover dates this examination to 22 June 2015, 9.30–11.00am. The archive stores it under 2014/T/a13752w1.pdf; the cover determines the year. Source: released examination archive.

The intact copy in the Mathematics Part A release, member FOI-20210708-1 - Data/a13752w1 (4).pdf, restores the previously missing printed page 3 and supplies a complete readable counterpart. Questions 1–2 had already been recovered and answered; those answers and all answers to questions 5–8 are retained. The solutions now cover all eight questions and their 37 leaf subparts. The earlier source provenance above is unchanged.

The binomial theorem isolates the only terms that can survive reduction modulo the prime number $p$:For $1\le r\le p-1$, neither $r!$ nor $(p-r)!$ is divisible by $p$, whereas $p!$ is. Consequently $p\mid \left(\genfrac{}{}{0ex}{}{p}{r}\right)$, and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers $a,b$, including those divisible by $p$. It is the additive identity behind the Frobenius endomorphism in characteristic $p$.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

In Pollard's p-1 algorithm, a large exponent containing many small factors makes $a^M-1$ divisible by a prime factor whose predecessor divides $M$, by Fermat's little theorem. A greatest common divisor with the number being factored can then separate that prime factor from the others.

Choose base $a=2$ and build factorial exponents using modular exponentiation. The successive exponents $2!$, $3!$, and $4!$ giveThe first two greatest common divisors are $\gcd (3,1003)=\gcd (63,1003)=1$. At the next step the Euclidean algorithm givesHenceHere the element order of $2$ modulo $17$ is $8$, which divides $24$, even though $17-1=16$ does not divide $24$. The algorithm only needs the element order to divide the chosen exponent; divisibility by the full predecessor is a sufficient condition, not a necessary one.

First simplify the specified residue by modular exponentiation. Modulo the prime number $113$,Therefore $102^{70}\equiv 28\cdot 64\cdot 8\equiv 98$, so the required equation becomes $x^{37}\equiv 97(\mathrm{mod}113)$. Its right side is nonzero, so any solution is a unit modulo $113$.

By Fermat's little theorem, exponents of such units can be reduced modulo $112$. Sinceraising to the $109$th power is the inverse of raising to the $37$th power. There is therefore exactly one residue class of solutions:Now $97\equiv -16$ and $97^3\equiv -4096\equiv 85$. Since $4\cdot 85\equiv 1$, we obtainAs a direct check, $4^4\equiv 30$, $4^8\equiv 109$, $4^{16}\equiv 16$, and $4^{32}\equiv 30$, whence $4^{37}\equiv 30\cdot 30\cdot 4\equiv 97$.

The defining relation $yx=x^{4}y$ lets us move every occurrence of $y$ to the right of every occurrence of $x$. More generally, repeated conjugation givesNegative powers cause no problem because $x^{-1}=x^8$ and $y^{-1}=y^2$. Thus every word in the group presentation can be put in the required form, reducing powers using $x^9=y^3=e$:At this stage existence is proved; uniqueness will follow from the concrete semidirect product in part (b). Moving $x^r$ past $y^j$ gives the multiplication lawThe action is consistent with reduction of $j$ modulo $3$ because $4^3\equiv 1(\mathrm{mod}9)$.

For the given group homomorphism $\phi :H\to \mathrm{Aut}(N)$, the external semidirect product has underlying Cartesian product $N\times H$ and operationThe notation $\mathrm{Aut}(N)$ denotes the automorphism group of $N$. Closure follows because $\phi (h)$ is an automorphism of $N$. To check associativity, calculate both bracketings:They agree because $\phi (hk)=\phi (h)\phi (k)$. The identity is $(e_N,e_H)$, using $\phi (e_H)={\mathrm{id}}_N$, and the two-sided inverse isIndeed multiplication in either order gives the identity, using $\phi (h)\phi (h^{-1})={\mathrm{id}}_N$. This verifies the group axioms.

For the specified group presentation, take $N=C_9=⟨X⟩$ and $H=C_3=⟨Y⟩$. The rule $\alpha (X)=X^4$ defines an automorphism because $4$ is coprime to $9$. Furthermore $4^3\equiv 1(\mathrm{mod}9)$, so $Y\mapsto \alpha$ defines the required group homomorphism $C_3\to \mathrm{Aut}(C_9)$. In the resulting semidirect product $S$, the canonical generators satisfyConsequently the group presentation defines a surjective group homomorphism $G\to S$, sending $x$ to $X$ and $y$ to $Y$. The underlying Cartesian product gives $|S|=27$, whereas part (a) gives $|G|\le 27$. Surjectivity forces equality, so the map is an isomorphism:This also proves that the $27$ normal forms in part (a) are distinct and that $x$ has element order exactly $9$.

The cyclic subgroup $⟨x^3⟩$ is normal: conjugation by $y$ sends $x^3$ to $x^{12}=x^3$, and conjugation by $x$ fixes it. Modulo this subgroup, the relation $yx{y}^{-1}=x^4$ becomes $yx{y}^{-1}=x$, so the quotient group is Abelian. Thus the commutator subgroup $G^{\prime }$ is contained in $⟨x^3⟩$.

Conversely the displayed relation gives the commutator $yx{y}^{-1}{x}^{-1}=x^3$, so $⟨x^3⟩\subseteq G^{\prime }$. HenceSince $x$ has element order $9$, $x^3\ne e$, so the first commutator subgroup is nontrivial. ThereforeHere derived length counts the number of steps needed for the derived series to reach the trivial group.

The given unitriangular group of degree three over F3 has $27$ elements, just as $G$ does, so counting alone cannot distinguish them. Instead compare element orders.

Write an element as $I+U$, with $U$ strictly upper triangular of size $3$. Then $U^3=0$. Over the finite field ${\mathbb{F}}_3$, the binomial theorem for commuting matrices givesEvery nonidentity element of $H$ consequently has element order $3$. In contrast, $x\in G$ has element order $9$, by part (b). An isomorphism preserves element order, soEquivalently, the exponent of a finite group is $3$ for $H$ and $9$ for $G$.

Use the cross-ratio convention compatible with the permutation identities in this paper. Represent a projective point $P_i\in {\mathbb{CP}}^1$ by a nonzero vector $p_i\in {\mathbb{C}}^2$, and write $[p_i,p_j]=\det (p_i,p_j)$. DefineThe denominator is nonzero because the four projective points are distinct. Rescaling any one representative multiplies numerator and denominator by the same nonzero scalar, so the definition is independent of the chosen homogeneous coordinates. In finite affine coordinates it readswith the point at infinity of the complex projective line handled by the homogeneous formula.

A projective transformation is represented by an invertible matrix $A\in {\mathrm{GL}}_2(\mathbb{C})$. Since $[A{p}_i,A{p}_j]=\det (A)[p_i,p_j]$, the two factors of $\det (A)$ in the numerator cancel the two in the denominator. Therefore every projective transformation preserves this cross-ratio. This also shows that the formula descends from matrices to the projective linear group, whose representatives differ by a nonzero common scalar.

The needed general-position theorem is sharp triple transitivity of the projective linear group on the projective line: for any two ordered triples of distinct projective points, exactly one projective transformation takes the first triple to the second.

In particular, let $T_P$ take $(P_0,P_1,P_2)$ to $(\infty ,0,1)$. In these coordinates,so cross-ratio invariance gives $T_P(P_3)=\lambda$, where $\lambda =(P_0{P}_1:P_2{P}_3)$. Distinctness implies $\lambda \ne 0,1$ and $\lambda$ is finite. The entire ordered quadruple is thus normalized toFor a second quadruple $(Q_0,Q_1,Q_2,Q_3)$ with the same cross-ratio, its normalizing map $T_Q$ yields the same quadruple. ConsequentlyThis proves the equivalence. Uniqueness on the first three points also shows that the projectivity carrying one ordered quadruple to the other is unique. The cross-ratio normalization of four projective points therefore gives a complete invariant for this ordered classification.

Choose three distinct projective points $A,B,C$. Their images under the injective map $\tau$ are distinct. Sharp triple transitivity gives a projective transformation $S$ agreeing with $\tau$ on these three points. The map $\sigma =S^{-1}\circ \tau$ fixes $A,B,C$ and preserves their cross-ratios.

For any other projective point $P$, invariance givesLet $T$ normalize $(A,B,C)$ to $(\infty ,0,1)$. By part (b), the left side is $T(\sigma (P))$ and the right side is $T(P)$. Since $T$ is a bijection, $\sigma (P)=P$. It fixes the original three points too, so $\sigma$ is the identity map everywhere. ThereforeNo continuity or prior surjectivity assumption was needed. This is the rigidity assertion that cross-ratio preserving maps are projective.

By invariance under projective transformations and part (b), it is enough to calculate on the normalized quadruple $(\infty ,0,1,\lambda )$. Direct evaluation of the cross-ratio givesFor instance, $(0\infty :1\lambda )=(0-1)/(0-\lambda )=1/\lambda$, and $(\infty 1:0\lambda )=(1-\lambda )/(1-0)$. ThusAll denominators are legitimate because $\lambda \notin \{0,1\}$. The first identity explains why some distinct permutations always give the same cross-ratio.

The cross-ratio permutation orbit is generated by the two operations $\lambda \mapsto 1/\lambda$ and $\lambda \mapsto 1-\lambda$ from part (d). The full list isThese are all the possibilities: the four permutations generated by interchanging both pairs and by exchanging the two pairs leave the cross-ratio unchanged. They form the Klein four-group inside the symmetric group on four symbols, leaving at most $24/4=6$ different values; the displayed operations attain all six rational expressions.

There are fewer than six values exactly when a nonidentity operation in this six-element action fixes $\lambda$: if two operations give the same value, composing one with the inverse of the other gives such a fixed point. For real $\lambda \ne 0,1$, the fixed-point equations areThe other two equations reduce to ${\lambda }^2-\lambda +1=0$, which has no real root. HenceEach exceptional value has the same three-element orbit $\{-1,\frac{1}{2},2\}$. Every other permitted real value gives six different values.

For the geometric interpretation, put $P_0=[1:0]=\infty$ and $P_i=[x_i:1]$ for $i>0$. ThenThe three exceptional cases becomeThus the three finite points are collinear and equally spaced, with one their midpoint, even when the $x_i$ are viewed as points of the complex plane. Equivalently they form an arithmetic progression in some order. These are the harmonic conjugate points configurations with the fourth point equal to the point at infinity of the complex projective line.

A map $g$ is differentiable at $a$ when a linear map $D{g}_a:{\mathbb{R}}^n\to {\mathbb{R}}^k$ approximates its increment to first order:This Fréchet derivative is unique, and its matrix in the standard bases is the Jacobian matrix. Differentiability on a domain means differentiability at each point there.

A standard sufficient condition for a zero locus to be a submanifold is the regular level set theorem: if $g$ is $C^1$ on an open domain and $D{g}_a$ is surjective at every $a\in g^{-1}(0)$, thenFor smooth $g$, the submanifold is smooth. The full-rank condition is the relevant constraint qualification.

Under this regularity hypothesis, its tangent space isIndeed, if a differentiable curve $\gamma$ lies in $M$ and passes through $a$, the chain rule gives $D{g}_a({\gamma }^{\prime }(0))=0$. Thus all tangent velocities lie in the kernel of a linear map. The rank-nullity theorem makes this kernel $(n-k)$-dimensional, the same dimension as the tangent space, proving equality. In coordinates, solve the homogeneous linear equations given by the Jacobian matrix.

The regularity qualification matters: $g(x)=x^2$ has zero set $\{0\}$, a zero-dimensional submanifold, but $D{g}_0=0$. Its kernel is all of $\mathbb{R}$, whereas its tangent space is zero. This is the phenomenon that singular defining maps can overestimate tangent spaces.

At a constrained critical point, the directional derivative of $f$ vanishes along every admissible tangent velocity:For a regular zero locus, $T_{a}M=\ker D{g}_a$. A linear functional vanishing on this kernel lies in the row space of $D{g}_a$. Equivalently there are Lagrange multipliers ${\lambda }_1,\dots ,{\lambda }_k$ such thatGeometrically, $\nabla f$ is orthogonal to the tangent space, so it lies in its orthogonal complement, spanned by the independent constraint gradients. Thus the level set of $f$ has no first-order change in a tangent direction. The equations provide candidates for constrained extrema; they must still be classified and compared, and boundary or singular cases must be treated separately. The condition is necessary for a regular constrained extremum, not a guarantee of a maximum.

The feasible set is closed and contained in the rectangleIt is therefore compact, and the continuous function $xy$ attains a global maximum there by the extreme value theorem. At the two boundary endpoints where a coordinate is zero, the product is zero. Meanwhile $(1,1)$ is feasible because the conjugate exponents satisfy $1/p+1/q=1$, and its product is one. Hence every maximizer has $x,y>0$.

On that positive region the constraint is $C^1$ with nonzero gradient. The Lagrange multiplier equations areThe first two identities imply $xy=\lambda x^p=\lambda y^q$. Since $x,y>0$, the multiplier is nonzero, so $x^p=y^q=r$. The constraint now givesThus the sole interior candidate is $(1,1)$. Existence of a maximum and the boundary comparison prove the unique global resultThis conjugate-power constrained product maximum is valid for all real $p,q>1$ with $1/p+1/q=1$; no integrality of the exponents is needed.

Use a normalization proof of Young's inequality. For arbitrary $x,y\ge 0$, putIf $A=0$, both coordinates are zero and the desired inequality is equality. If $A>0$, defineThen $X^p/p+Y^q/q=1$. Part (c) gives $XY\le 1$, and the conjugate exponent identity gives $XY=xy/A$. Therefore Young's inequality for products isThe unique equality case in part (c) says $X=Y=1$. Translated back, and including the zero case, this gives the sharp conditionConversely, if both powers equal $r\ge 0$, then $xy=r^{1/p+1/q}=r$ and the right side is $r(1/p+1/q)=r$, directly verifying equality.

Use the unilateral Laplace transform convention $\overline{f}(p)={\int }_0^{\infty }{e}^{-px}f(x)dx$. The Laplace transform of a derivative isThe formula holds in the common Laplace convergence region under the usual endpoint and growth hypotheses. The initial value is the right-hand value at zero.

With the same unilateral Laplace transform convention, the standard sine formula is

The defining evaluation rule of the Dirac delta givesThe impulse lies strictly inside the integration domain, so there is no endpoint convention to settle. This Laplace transform exists for every complex $p$.

Let $K(p)=\mathcal{L}[k](p)$ and $F(p)=\mathcal{L}[f](p)$. Apply the Laplace transform of a derivative twice and use the two zero initial conditions. The differential equation becomesThe factor $1/(p^2+1)$ is the Laplace transform of $\sin x$. The convolution theorem for Laplace transforms therefore givesThis is a causal convolution: the value at $x$ uses only the forcing up to $x$. For ordinary continuous $k$, direct differentiation gives $f^{\prime }(x)={\int }_0^x\cos (x-t)k(t)dt$ and $f^{\prime \prime }(x)=k(x)-f(x)$, verifying both the differential equation and the initial conditions. For an impulsive $k$, the same formula is interpreted using distributions.

An impulse at $a$ shifts the causal sine response. Substituting the Dirac delta in the convolution from part (i), or using the Laplace transform time-shift rule, giveswhere $H$ is the Heaviside step function. The answer is continuous at $a$, while its first derivative jumps from $0$ to $1$. Consequently its second distributional derivative contains exactly one unit Dirac delta at $a$, giving $f^{\prime \prime }+f=\delta (x-a)$. Since $a>0$, both initial conditions vanish.

Put $G(p)=\mathcal{L}[J_0](p)$, initially for real $p>0$. Besides the Laplace transform of a derivative, use multiplication by the original variable in the formTransforming the Bessel differential equation, with its given initial conditions, yieldsThe constant terms cancel, leaving $(1+p^2)G^{\prime }+pG=0$. This first-order ordinary differential equation integrates toThe initial value theorem for Laplace transforms gives ${\lim }_{p\to \infty }pG(p)=J_0(0)=1$, so $C=1$. Thus the Laplace transform of the Bessel function J0 isFor complex $p$ with $\mathrm{Re}p>0$, choose the analytic square-root branch agreeing with the positive square root on the positive real axis.

For the forcing $k=J_0$, part (b) now gives $F(p)=(1+p^2{)}^{-3/2}$. On the other hand, the same multiplication rule givesTaking an integral from zero divides the Laplace transform by $p$. By uniqueness of the Laplace transform,A direct check also explains the cancellation. This expression has $f^{\prime }=x{J}_0$ and $f^{\prime \prime }=J_0+x{J}_0^{\prime }$. The Bessel differential equation says $(x{J}_0^{\prime }{)}^{\prime }=-x{J}_0$, so integration from zero gives $x{J}_0^{\prime }=-{\int }_0^{x}t{J}_0(t)dt=-f$. Hence $f^{\prime \prime }+f=J_0$, and both initial conditions hold.

Use the chain rule along a sufficiently smooth extremal of the functional. For $E=y^{\prime }{F}_{y^{\prime }}-F$,The bracket vanishes by the Euler-Lagrange equation. When $F$ has no explicit $x$ dependence, $F_x=0$, giving the Beltrami identity:

For the specified functional,Since $y>0$, the Beltrami identity gives $y\sqrt{1+y^{\prime 2}}=R$ for some $R>0$. This suggests a circular arc, but it is worth deriving its equation without dividing by $y^{\prime }$: such division would lose the point where the arc is horizontal.

Substitute the displayed partial derivative and $F_y=-\sqrt{1+y^{\prime 2}}/y^2$ in the full Euler-Lagrange equation. Combining terms over the common denominator givesThus $(y{y}^{\prime }{)}^{\prime }=-1$, so $y{y}^{\prime }=h-x$ and a second integration givesThis establishes the semicircular extremals of the hyperbolic length functional and excludes constant $y$, which would satisfy the first-order Beltrami identity for a suitable $R$ but not the full Euler-Lagrange equation.

The two prescribed endpoints giveSubtracting yields $4h=4(d^2-c^2)$. ThereforeIn particular the centre is $\boxed{(d^2-c^2,0)}$. Admissibility requires $c,d>0$, as the prescribed heights must lie in $y>0$. Under that condition the radicand is positive throughout $[-1,1]$: it is a concave quadratic polynomial whose two endpoint values are $4c^2$ and $4d^2$. The positive root consequently gives one smooth admissible arc, uniquely determined by the endpoints.

When an endpoint's horizontal coordinate is fixed but its height is free, the natural boundary conditions for a free endpoint require $F_{y^{\prime }}=0$ there. In this problem,Every admissible extremal is an upper circular arc with centre on $y=0$, by part (b). Its tangent is horizontal precisely above its centre. Thus imposing the natural boundary conditions for a free endpoint at $x=1$ forces $h=1$. The fixed height at $x=-1$ gives $R^2=4+4c^2$, soIts free endpoint height is $y(1)=2\sqrt{1+c^2}$. Positivity on the whole interval follows because the radicand is at least $4c^2$.

There can be no solution satisfying the natural boundary conditions for a free endpoint at both ends: an upper circular arc has only one point with a horizontal tangent, whereas the two endpoints have distinct horizontal coordinates. Therefore

A tree is a nonempty connected graph with no graph cycle. A leaf of a tree is a vertex of vertex degree one. As usual in this finite graph theory problem, trees are finite; the assertion would fail for a doubly infinite graph path.

Take a longest path $v_0,v_1,\dots ,v_m$ in a tree with at least two vertices. Connectedness gives $m\ge 1$. If $v_0$ had a neighbour outside this graph path, the path could be extended, contradicting maximal length. If it had a neighbour $v_j$ with $j\ge 2$, that edge together with the segment $v_0,v_1,\dots ,v_j$ would make a graph cycle. Thus its only neighbour is $v_1$, and it is a leaf of a tree. The same argument at the other end makes $v_m$ a second, distinct leaf of a tree. Hence

Deleting a vertex and its incident edge cannot create a graph cycle, so $T\setminus v$ is acyclic. It remains to establish connectedness and nonemptiness.

Since the leaf of a tree $v$ has one neighbour, $T$ has at least two vertices, so $T\setminus v$ is nonempty. For any two remaining vertices $a,b$, take their unique simple graph path in $T$. It cannot pass through $v$: an internal vertex on such a graph path has two incident edges, whereas $v$ has vertex degree one. Neither endpoint is $v$, so the entire graph path remains after deletion. The remaining graph is connected and acyclic, givingThis includes the two-vertex case, where deletion leaves the one-vertex tree.

Here each $T_i$ is a nonempty connected subgraph of a tree, rather than a descendant-closed data-structure subtree. We prove the Helly property for connected subgraphs of a tree by mathematical induction on the number of vertices of $T$.

For a one-vertex tree, every nonempty $T_i$ contains that vertex. For a larger tree, choose a leaf of a tree $v$ using part (i), and denote its unique neighbour by $w$. If some $T_i$ consists only of $v$, the assumed pairwise intersections force every $T_j$ to contain $v$, and we are done.

Otherwise, remove $v$ from every $T_i$ that contains it, leaving all other $T_i$ unchanged. Any affected $T_i$ has at least two vertices; connectedness forces it to contain $w$ and the edge $vw$. Thus $v$ is a leaf of a tree of $T_i$, and part (ii) shows that its deletion leaves a nonempty tree. All reduced $T_i$ are therefore nonempty connected subgraphs of a tree $T\setminus v$.

They still intersect pairwise. An original common vertex other than $v$ survives. If a pair had only $v$ in common, both members would also contain $w$, by the previous paragraph, contradicting that it was their only common vertex. The induction hypothesis now supplies a common vertex of the reduced family, which is also common to the original family. Consequently

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.