Short options course of the University of Oxford (ASO)

Source: released examination PDF, pages 28–38. Solutions follow the numbering of the 21 June 2023 Short Options paper.

The multiplicative group ${\mathbb{F}}_p^{\times }$ is a cyclic group of order $p-1$, so choose a primitive root $g$. Every nonzero residue is uniquely $g^j$, with $j$ taken modulo $p-1$. The condition becomes $(p-1)\mid kj$. Writing $d=\gcd (k,p-1)$, its solutions are $j=0,(p-1)/d,\dots ,(d-1)(p-1)/d$. Zero is not a solution. Therefore the number isThis includes $p=2$. The cyclic group argument gives the exact count, whereas the bound of $k$ roots for a nonzero degree-$k$ polynomial over a field would only give an upper bound.

If $p\mid n$, the field property forces $x=0$, giving exactly one solution. Otherwise, if $x_0$ is any solution, multiplication by $x_0$ is a bijection from the solutions of $z^k=1$ to those of $x^k=n$. Part (i) therefore givesThe two possibilities in the second line distinguish an empty fiber from a coset of the kernel of the power group homomorphism on ${\mathbb{F}}_p^{\times }$.

For $p>3$, quadratic reciprocity givesThe second Legendre symbol is $1$ when $p\equiv 1(\mathrm{mod}3)$ and $-1$ when $p\equiv 2(\mathrm{mod}3)$. Combining it with the sign determined by $p(\mathrm{mod}4)$ shows that a quadratic residue occurs precisely for

For odd $p\ne 5$, quadratic reciprocity has no sign factor because $5\equiv 1(\mathrm{mod}4)$:The nonzero squares modulo $5$ are $1,4$, so the answer for odd primes is $p\equiv 1,4(\mathrm{mod}5)$. The excluded-prime wording also allows $p=2$, where $5\equiv 1$ has a square root. Thus the full answer is

The primes $2,5$ both work, with the zero residue as a solution. For every other prime, multiplicativity of the Legendre symbol and quadratic reciprocity giveThe first factor is positive for $p\equiv 1,7(\mathrm{mod}8)$; the second is positive for $p\equiv 1,4(\mathrm{mod}5)$. They must have the same sign. The Chinese remainder theorem therefore yields

Let $a$ be a root modulo $p^j$. Every lift to a residue modulo $p^{j+1}$ is uniquely $a+t{p}^j$ with $t(\mathrm{mod}p)$. The polynomial expansion givesBecause $a(\mathrm{mod}p)$ is a root and there are no common roots of $f$ and $f^{\prime }$, $f^{\prime }(a)$ is nonzero modulo $p$. Thus precisely one $t$ solvesEvery root at one level therefore has exactly one lift, and every root at the next level reduces to a root at the previous level. Induction proves equality of the counts from $p$ to $p^l$. This is simple-root Hensel lifting by successive residues at finite precision; completeness is unnecessary for this finite-level assertion.

For $f(x)=x^2-n$, a root modulo the odd prime $p$ is nonzero because $p\nmid n$. Its derivative $2x$ is therefore nonzero modulo $p$. Part (i) gives exactly one lift of each root. A nonzero quadratic residue modulo an odd prime has two distinct roots, $x$ and $-x$; a nonresidue has none. Hence

A group presentation $⟨X\mid R⟩$ denotes the quotient $F(X)/⟨⟨R⟩⟩$ of the free group on the generator symbols by the normal closure of the relator words. The symbols generate the quotient, and each relator becomes the identity. The phrase also asserts that no additional relations are imposed except consequences of these relators and the group axioms. Equivalently, an assignment of the generators to a group extends to a group homomorphism from the presented group exactly when all relators evaluate to the identity; this is the universal property of a group presentation.

Multiplication, followed by induction and inversion for negative powers, givesIf $c\ne 0$, apply Euclidean division to write $a=q|c|+r$ with $0\le r<|c|$. Choose $n=-q\mathrm{sgn}(c)$, so $a+nc=r$. This is one step of the Euclidean algorithm implemented by a determinant-one row operation.

After the reduction in part (b), multiply by $S$. The new bottom-left entry is $r$, whose absolute value is strictly smaller than the previous $|c|$:Repeated Euclidean division must terminate because the nonnegative integers $|c|$ decrease strictly until zero. Thus a word $W$ in $S,T$ and their inverses gives a matrix with bottom-left entry zero. Its determinant is one, so the diagonal entries are equal and are either both $1$ or both $-1$:Since $S^2=-I$, this final matrix belongs to $⟨S,T⟩$. So does $W^{-1}$, proving

The identity $T=S^{-1}(ST)$ shows that $S,ST$ generate the same group. Direct multiplication givesConsequently their images $\bar{S},\overline{ST}$ in the quotient group $PSL(2,\mathbb{Z})$ satisfy ${\bar{S}}^2=1$ and ${\overline{ST}}^3=1$. The universal property of a group presentation gives a group homomorphism taking $u\mapsto \bar{S}$, $v\mapsto \overline{ST}$ from the stated presentation. It is surjective because these images generate the target. Injectivity is not needed here.

Suppose $N$ were a normal subgroup of index $m$ and put $Q=SL(2,{\mathbb{F}}_p)/N$. The supplied reduction map and part (c) show that $Q$ is generated by the images $s,t$ of $S,ST$. Their orders divide $4$ and $6$, respectively, because $S^4=I$ and $(ST{)}^6=I$. By Lagrange's theorem, their orders also divide $|Q|=m$. Since $\gcd (m,6)=1$, both $\gcd (m,4)$ and $\gcd (m,6)$ equal one. Thus $s=t=1$, forcing $Q$ to be trivial and $m=1$, a contradiction. No such normal subgroup exists for $m>1$.

A projective conic in ${\mathbb{P}}^2(\mathbb{C})$ is the zero locus of a nonzero homogeneous quadratic polynomial, up to nonzero scaling of that polynomial. Under an invertible linear change of homogeneous coordinates, its symmetric matrix has rank $3$, $2$, or $1$. Over $\mathbb{C}$, the corresponding forms are a nonsingular conic such as $XZ-Y^2=0$, two distinct lines such as $XY=0$, or a double line $X^2=0$. In the last case the repeated factor records multiplicity, even though the underlying point set is one line.

A projective line is the projectivization of a two-dimensional linear subspace of ${\mathbb{C}}^3$, equivalently the zero locus of one nonzero linear form. For two such subspaces $U,W$, the dimension formula for a sum of subspaces gives $\dim (U\cap W)\ge 2+2-3=1$. A nonzero vector in the intersection therefore supplies a common projective point. Distinct lines have exactly one such point.

Use coefficient coordinates $[a:b:c]$ on $\mathbb{P}(V)$. A nonzero binary quadratic has a repeated linear factor precisely when its discriminant vanishes, soIts gradient is $(-4c,2b,-4a)$, which cannot vanish at a projective point. Therefore $C$ is a nonsingular projective conic. The parametrization $[\alpha :\beta ]\mapsto [{\alpha }^2:2\alpha \beta :{\beta }^2]$ identifies it as a degree-two Veronese map.

Assume $L\ne 0$. The quadratics divisible by $L$ form $L\cdot \mathrm{span}\{x,y\}$, a two-dimensional linear subspace; their projectivization is a projective line. Evaluating at the projective zero $[-\beta :\alpha ]$ of $L$ gives its equationAt the point $[L^2]=[{\alpha }^2:2\alpha \beta :{\beta }^2]$ of $C$, the tangent equation obtained from the gradient of $b^2-4ac$ is $-4{\beta }^{2}a+4\alpha \beta b-4{\alpha }^{2}c=0$. It is exactly the same line, establishing tangency.

The fundamental theorem of algebra factors $q(x,1)$ into linear factors over $\mathbb{C}$; homogenizing supplies factors of $y$ if the degree is less than three. Thus every nonzero homogeneous cubic is $c{L}_1{L}_2{L}_3$ for linear forms $L_i$, with $c\ne 0$ absorbed into one factor.

For pairwise nonproportional factors, part (c) assigns three distinct tangent lines ${\ell }_i=\mathbb{P}(L_i\cdot \mathrm{span}\{x,y\})$ to $C$. Their pairwise intersections are $[L_1{L}_2]$, $[L_1{L}_3]$, and $[L_2{L}_3]$. There cannot be a common point of all three: a nonzero quadratic cannot be divisible by three pairwise nonproportional linear factors, by unique factorization. Hence the three lines form a triangle circumscribed about $C$.

For the operator norm, submultiplicativity bounds the remainder of the matrix exponential byTherefore $\Vert \exp A-\exp 0-A\Vert /\Vert A\Vert \to 0$. This is precisely Fréchet differentiability at zero, with

The curve-based tangent space at $x$ consists of velocities ${\gamma }^{\prime }(0)$ of smooth curves $\gamma :(-\epsilon ,\epsilon )\to M$ satisfying $\gamma (0)=x$. For an arbitrary subset these velocities need not form a vector space; for a smooth submanifold they do, and this is its usual tangent space. This definition suffices for the direct computation at the identity.

If $Q(t)$ is a smooth curve of orthogonal matrices with $Q(0)=I$, differentiating $Q(t{)}^{T}Q(t)=I$ gives $Q^{\prime }(0{)}^T+Q^{\prime }(0)=0$. Thus each tangent velocity is a skew-symmetric matrix.

Conversely, if $A^T=-A$, the curve $Q(t)=\exp (tA)$ satisfiesusing commutation of $-tA$ and $tA$. By part (a), $Q^{\prime }(0)=A$. Both inclusions prove

The matrix exponential is smooth, and part (a) identifies its derivative at zero as the identity. The inverse function theorem therefore gives a local diffeomorphism from an open neighborhood $U_0$ of zero onto a neighborhood of $I$. Choose a sufficiently small operator norm ball $U\subset U_0$ and let $V=\exp U$. This is again a diffeomorphism onto an open set, since it is a restriction of the original one.

The ball $U$ is preserved by $A\mapsto A^T$ and $A\mapsto -A$. Since $(\exp A{)}^T=\exp (A^T)$ and $(\exp A{)}^{-1}=\exp (-A)$, $V$ is preserved by adjoint and inversion. For its local inverse $L$, injectivity also gives

Part (b) already shows $\exp (U\cap \mathcal{A})\subset V\cap O(n)$. Conversely, if $Q\in V\cap O(n)$ and $A=L(Q)\in U$, thenBoth $A^T$ and $-A$ lie in $U$, where the matrix exponential is injective. Therefore $A^T=-A$, proving the reverse inclusion. The restricted map is a bijection, indeed a diffeomorphism between these local sets.

The linear map $\pi (A)=(A+A^T)/2$ is the projection onto the space $\mathcal{S}$ of symmetric matrices, with kernel $\mathcal{A}$. Define $F=\pi \circ L$ on $V$. Since $DL$ is invertible everywhere on $V$ and $\pi$ is onto, $DF$ is onto everywhere. By part (ii),The regular level set theorem makes this a submanifold of codimension $\dim \mathcal{S}=n(n+1)/2$, and henceThis neighborhood is $V$ around $I$; the source's final occurrence of $U$ in this step is a neighborhood-label slip. For any $Q\in O(n)$, left multiplication by $Q$ is an invertible linear map of the ambient matrix space and carries $V\cap O(n)$ onto $QV\cap O(n)$. These translated charts establish the submanifold property at every group element.

The distributional derivative is defined by $⟨F^{\prime },\varphi ⟩=-⟨F,{\varphi }^{\prime }⟩$ for every test function. For the Heaviside function, compact support givesThus ${\mathcal{H}}^{\prime }=\delta$. Splitting the integral for $|x|$ at zero and using integration by parts gives its first derivative as the sign function. The jump of that function at zero is two, soas distributions. The value assigned to the sign function at the single point zero does not affect its associated distribution.

For real $p>0$, substitute $t=px$ in the Laplace transform:The Gamma function integral is finite because $a>0$. For complex $p$, absolute convergence holds exactly when $\mathrm{Re}p>0$: the modulus of the integrand is $x^{a-1}{e}^{-(\mathrm{Re}p)x}$. On this half-plane the same answer holds with the branch $p^{-a}=\exp (-a\mathrm{Log}p)$ whose logarithm is real on the positive axis, by holomorphic continuation of the two sides.

If “exists” permits conditionally convergent ordinary improper integrals, there are additional boundary points when $0<a<1$: for $p=i\omega \ne 0$, the Dirichlet test gives convergence, with value $\Gamma (a)|\omega {|}^{-a}{e}^{-i\mathrm{sgn}(\omega )\pi a/2}$. For $a\ge 1$ these boundary integrals do not converge in that sense. At $p=0$, and for $\mathrm{Re}p<0$, the integral diverges. Thus $\mathrm{Re}p>0$ is the region of absolute convergence of a Laplace transform, with the stated conditional boundary qualification.

The integral $I$ is the convolution of the positive-half-line kernels $x^{a-1}$ and $x^{b-1}$. The convolution theorem for Laplace transforms therefore gives, for $p>0$,On the other hand, the substitution $t=xu$ gives $I(x)=x^{a+b-1}B(a,b)$, where $B(a,b)={\int }_0^1{u}^{a-1}(1-u{)}^{b-1}du$ is the beta function. Applying part (i) again yields $\mathcal{L}I(p)=B(a,b)\Gamma (a+b)p^{-(a+b)}$. Comparing the two expressions provesAll integrands used in the real-$p$ convolution argument are nonnegative, so Tonelli's theorem justifies the interchange; the endpoint singularities are integrable because $a,b>0$.

Use the Fourier transform convention $\hat{f}(s)={\int }_{\mathbb{R}}{e}^{-isx}f(x)dx$. First observe that $f(x)=(2\pi {)}^{-1/2}{e}^{-x^2/2}$ satisfies the differential equation, decay, and normalization, using the Gaussian integral. The uniqueness allowed in the question identifies it with $f$. In particular it is a Schwartz function, so the derivative and multiplication rules below are justified.

Taking the Fourier transform of the differential equation givesThe Riemann-Lebesgue lemma gives decay of $\hat{f}$. Every decaying solution $h$ of this equation is proportional to $e^{-s^2/2}$: setting $w=h^{\prime }+sh$ gives $w^{\prime }=sw$, and integration yieldsThe term with $C\ne 0$ grows like $C{e}^{s^2/2}/(2s)$ as $s\to +\infty$, so decay forces $C=0$. Thus $\hat{f}=\lambda f$ for a scalar $\lambda$. This establishes proportionality before using Fourier inversion to calculate the scalar.

At zero, the Fourier transform is $\hat{f}(0)=\int f=1$, so $\lambda f(0)=1$. In particular $\lambda \ne 0$ and $f(0)=1/\lambda$. The Fourier inversion theorem at zero also givesEquating the two values yields $\boxed{{\lambda }^2=2\pi }$. Since the explicit normalized Gaussian function in part (i) has $f(0)>0$, here $\lambda =\sqrt{2\pi }$.

In the space of tempered distributions, this Fourier transform convention gives $\hat{1}=2\pi \delta$ and $\hat{\delta }=1$. ThereforeThe constant distribution and the Dirac delta distribution are linearly independent: testing away from zero first determines the constant coefficient, and then testing at zero determines the delta coefficient. Hence $c=\lambda$ and $\lambda c=2\pi$, giving

Let $y$ be a smooth constrained minimizer. For any smooth variation $h$ vanishing at the endpoints, use the normalized admissible curve $y_{\epsilon }=(y+\epsilon h)/\sqrt{J[y+\epsilon h]}$. Since $J[y]=1$, differentiating at zero givesIn particular this holds for every compactly supported test function $h$ in $(0,1)$. Integration by parts and the fundamental lemma of the calculus of variations givewhich is the required Bessel differential equation with $\boxed{\lambda =I[y]}$. The lemma used here says that a continuous function whose integral against every compactly supported smooth test function is zero must itself vanish. No multiplier-existence theorem is needed: the explicit normalization produces the variation directly.

The endpoint $0$ causes no divergent energy for these variations: smoothness and $y(0)=h(0)=0$ imply $y,h=O(x)$. Also $J[v]>0$ for every nonzero admissible $v$, and $v/\sqrt{J[v]}$ has unit $J$ and energy $I[v]/J[v]$. Thus minimizing $I$ with $J=1$ is equivalent to minimizing the scale-invariant Rayleigh quotient $I/J$. The zero function is excluded whenever this quotient is written.

Set $t=\sqrt{\lambda }x$ and $w(t)=y(t/\sqrt{\lambda })$. The chain rule turns the equation into the parameter-one Bessel differential equation. By the regular-at-zero solution property supplied in the paper,For a nonzero solution, $c\ne 0$, so $y(1)=0$ forces $J_k(\sqrt{\lambda })=0$. Conversely, every positive zero $z$ supplies the admissible eigenfunction $J_k(zx)$ with eigenvalue $z^2$.

Here is a direct justification of the infimum characterization that does not assume a minimizer exists. Let $u(x)=J_k(z_{k,1}x)$ and choose its sign so that $u>0$ on $(0,1)$. The first positive zero exists by the oscillatory large-argument behavior of the Bessel function of the first kind. At zero, its Frobenius series for Bessel functions gives $u(x)=C{x}^k(1+O(x^2))$. At one, its zero is simple by uniqueness for a regular second-order ordinary differential equation. Expanding $y=u(y/u)$ and using the equation for $u$ gives the Ground-state representation of a Sturm-Liouville energy:For completeness, apply the identity first on $[\epsilon ,1-\epsilon ]$. The discarded boundary term is $[x{u}^{\prime }{y}^2/u]$. It tends to zero at both ends: $x{u}^{\prime }/u\to k$ and $y=O(x)$ at zero, while $u^{\prime }/u=O((1-x{)}^{-1})$ and $y=O(1-x)$ at one. Taking $y=u$ achieves equality, soThe infimum is over the stated smooth admissible functions with finite energy; the equality also proves attainment by a multiple of $u$.

The trial function $y=x(1-x)$ givesIts Rayleigh quotient is $5k^2+10$, yielding the upper bound. Conversely, $1/x\ge x$ on $(0,1)$ and the derivative energy is nonnegative, so $I[y]\ge k^{2}J[y]$ for every admissible $y$. Part (b) therefore gives

A spanning tree of the connected graph $G$ is a subgraph containing every vertex, connected and without cycles in a graph. Equivalently, between every pair of vertices it has exactly one graph path. For a finite graph with $v$ vertices, it has $v-1$ edges.

A shortest-path tree rooted at $x$ is a spanning tree $T$ such that, for every vertex $v$, the unique $xv$ graph path in $T$ has minimum total edge length among all $xv$ graph paths in $G$. The objective is the sum of the lengths along each route, not the sum of all the tree's edge lengths.

For Dijkstra's algorithm, initialize $d(x)=0$ and $d(v)=\infty$ for other vertices, with no predecessor initially. Repeatedly select an unfinalized vertex $u$ of least tentative distance, finalize it, and relax each edge $uv$: if $d(u)+\ell (uv)<d(v)$, replace $d(v)$ by that value and set the predecessor of $v$ to $u$. Continue until all vertices are finalized. The predecessor edges form the shortest-path tree.

To justify finalization, consider a supposedly shorter route to the next selected vertex. Its first unfinalized vertex is preceded by a finalized one, whose relaxation would already have offered a tentative distance no greater than the length of that route's prefix. Nonnegative remaining lengths would contradict the selected vertex's minimal tentative label. Thus final labels are the true shortest distances. Strictly positive lengths also make predecessors have smaller distances, ruling out predecessor cycles in a graph.