Past exam of the short options course of the University of Oxford / 2014 (ASO, 4319)

Source release: Oxford examination archive, member FOI-20210708-1 - Data/4319.pdf. The cover dates this examination to 23 June 2014, 9.30–11.00am. All seven questions and their 34 leaf subparts are answered below.

For an odd prime $p$, the Legendre symbol isIt depends only on the congruence class of the integer $a$. The values $1$ and $-1$ distinguish a nonzero quadratic residue from a quadratic nonresidue; zero is a separate case.

Euler's criterion states, for an odd prime $p$,Apply it to $a=-1$. The integer $(-1{)}^{(p-1)/2}$ is $1$ when $p\equiv 1(\mathrm{mod}4)$ and $-1$ when $p\equiv 3(\mathrm{mod}4)$. Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:This is the first supplementary law for quadratic reciprocity.

Gauss's lemma states that, for $p\nmid a$, if $N$ of the least positive residues of $a,2a,\dots ,((p-1)/2)a$ exceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, with no reduction needed. Write $m=(p-1)/2$. A term $2j$ exceeds $p/2$ exactly when $j>p/4$, soIf $p$ is congruent to $1,3,5,7$ modulo eight, the parity of this count is respectively even, odd, odd, even. Gauss's lemma therefore givesThis proves the second supplementary law for quadratic reciprocity, rather than merely applying it.

Because $p$ is odd, $x$ must be odd. Every odd square is $1$ modulo eight. If $y$ is even, $2y^2$ is zero modulo eight; if $y$ is odd, it is two modulo eight. ThusMore precisely, the first case has even $y$ and the second has odd $y$. These are necessary conditions on the congruence class, as requested; the elementary calculation alone does not prove their sufficiency.

Equivalently, reduction modulo $p$ makes $-2$ a quadratic residue: $p$ cannot divide $y$, since that would also force $p\mid x$ and hence $p^2\mid p$. The two supplementary laws and multiplicativity of the Legendre symbol give the same two allowed classes.

Writing $a=21r$, the second condition becomes $r\equiv 4(\mathrm{mod}5)$. Writing $b=15s$, its second condition becomes $s\equiv 6(\mathrm{mod}7)$. Consequentlygives an infinite set of positive integer solutions. Conversely these are the positive solutions in the indicated congruence classes, by the Chinese remainder theorem.

Choose any pair $(a,b)$ from part (i), and put $A=2^a{3}^b$. The divisibilities of the exponents makepositive integers. Their powers areThus $x^3+y^5=z^7$, with all three powers nonzero and distinct. For example, take $a=84+105t$, $b=90+105t$ for every nonnegative integer $t$. Then $A$ strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity $A+2A=3A$ into three prescribed perfect powers.

A simple group is a nontrivial group whose only normal subgroups are itself and the trivial subgroup.

A composition series is a chain $G=G_0▹G_1▹\cdots ▹G_r=1$ in which each $G_{i+1}$ is a normal subgroup of $G_i$ and each quotient group $G_i/G_{i+1}$ is simple and nontrivial. Its length is $r$, and these quotients are its composition factors. The individual terms need not all be normal in $G$.

A solvable group is a group whose derived series reaches the trivial group: starting with $G^{(0)}=G$, define $G^{(i+1)}=[G^{(i)},G^{(i)}]$. For finite groups this is equivalent to having a composition series whose factors are all cyclic groups of prime order.

Let $1◃N◃G$ be the given length-two composition series. Thus $N$ and $G/N$ are simple groups. Let $M$ be any proper nontrivial normal subgroup of $G$, such as the penultimate term of another composition series.

If $M=N$, its two factors are already the given ones. Suppose $M\ne N$. Since $M\cap N$ is normal in the simple group $N$, it is either $1$ or $N$. The latter would mean $N\subseteq M$, but then $M/N$ would be a proper nontrivial normal subgroup of $G/N$, impossible. Thus $M\cap N=1$.

Also $M$ cannot be contained in $N$, since it would then be a nontrivial normal subgroup of $N$ distinct from $N$. The product $MN$ is a normal subgroup of $G$, strictly containing $N$. Simplicity of $G/N$ therefore forces $MN=G$. The second isomorphism theorem for groups givesIn particular $M$ is simple. Every other composition series has such an $M$ as its last proper term, and no nontrivial refinement inside a simple $M$ is possible. Hence every composition series has length two.

The general Jordan–Hölder theorem states that any two composition series of a finite group have the same length and the same composition factors up to group isomorphism and permutation. The argument above proves both assertions in this length-two case: another series either uses $N$ itself or has factors isomorphic to the original pair in the opposite order. No general uniqueness theorem was used to prove this special case.

Factor the group order as $588=2^2\cdot 3\cdot 7^2$. The Sylow theorems say that the number of Sylow subgroups for the prime seven divides $12$ and is congruent to one modulo seven. Among $1,2,3,4,6,12$, only one qualifies. Thus there is a unique normal subgroup $N$ of order $49$.

Every group of prime-square order is Abelian. Indeed its center of a group is nontrivial, and a cyclic quotient by the center of a group forces the whole group to be abelian. Consequently $N$ is either $C_{49}$ or $C_7\times C_7$, and in either case it has two composition factors, both $C_7$.

It remains to consider $Q=H/N$, of order twelve. Its number of Sylow subgroups for the prime three is either one or four:

Lift the composition series of $Q$ to $H$ using the subgroup correspondence theorem, and join it to a composition series inside $N$. This givesas the multiset of composition factors. The Jordan–Hölder theorem makes this independent of the chosen series. In particular every group of order $588$ is a solvable group, with composition length five; that is a statement about composition length, not necessarily its derived length.

The required general linear position condition is that every $n+1$ of the $n+2$ representing vectors are linearly independent. Such an ordered configuration is a projective frame.

Choose representatives $p_0,\dots ,p_n$ of the first $n+1$ projective points; they form a basis. Write a representative of the last point as $p_{n+1}={\sum }_i{a}_i{p}_i$. Every $a_i$ is nonzero: otherwise the last point together with the other $n$ basis points would fail the independence condition. Rescale the basis representatives to ${\tilde{p}}_i=a_i{p}_i$, so that $p_{n+1}={\sum }_i{\tilde{p}}_i$.

Do the same for the target configuration, obtaining representatives ${\tilde{q}}_i$ with $q_{n+1}={\sum }_i{\tilde{q}}_i$. The unique linear map sending the basis ${\tilde{p}}_i$ to ${\tilde{q}}_i$ is invertible and also sends $p_{n+1}$ to $q_{n+1}$. Its induced projective transformation sends every point to its prescribed partner. Thus any two ordered projective frames are projectively equivalent.

A projective quadric is the zero locus of a nonzero homogeneous quadratic polynomial $q(v)=v^{T}Bv$, with $B$ symmetric over a field of characteristic different from two. A projective point on it is singular when all first partial derivatives vanish. Since $\nabla q(v)=2Bv$, the quadric is nonsingular exactly when $B$ is invertible.

Over the complex numbers, a nonzero quadratic form in three variables can be diagonalized by an invertible change of basis. Its rank classifies a projective conic:

The zero polynomial is excluded from the definition of a conic. Thus these last two cases are precisely the singular conics.

Use part (a) to put the four projective points atA quadratic polynomial vanishing at the first three has no square terms, and vanishing at the fourth givesThese form a two-dimensional vector space. Choose the two membersTheir coefficient triples are independent and both satisfy the relation. Their symmetric bilinear form matrices are of the formFor $(A,B,C)=(1,1,-2)$ and $(1,-2,1)$, both determinants are $-1/2$, so both selected conics are nonsingular. Any coefficient triple with zero sum is uniquely a linear combination of these two. Hence every conic through the four points has matrixUndoing the projective transformation carries the entire family back to the original four points, preserving nonsingularity. This is a pencil of conics through four points.

For the explicit basis in part (c), $q_0+t{q}_1$ has coefficients $(1+t,1-2t,t-2)$. ThusAt these values the conics factor, up to nonzero constants, asGeometrically these are exactly the three pairings of the four base points into two pairs, with a projective line joining each pair. No double line can contain four points in general linear position.

The numerical parameter values depend on the selected basis, but the three distinct singular members do not. Another pair of independent nonsingular basis conics gives an invertible projective change of pencil parameter. Its parameter infinity is nonsingular because the second basis form is nonsingular. Therefore all three singular members again occur at three distinct finite values of $t$. This proves the claimed count for any such basis.

The Fréchet derivative at a point $a$ is the unique linear map $D{f}_a:{\mathbb{R}}^n\to {\mathbb{R}}^m$ such thatThe error divided by $\Vert h\Vert$ tends to zero as $h\to 0$. In standard coordinates this linear map is represented by the Jacobian matrix, but the derivative itself is the map acting on increments, not merely a list of directional rates.

Factor $A+H=A(I+A^{-1}H)$. The determinant expansion near the identity isthe linear terms in the permutation formula come from choosing one diagonal increment and all remaining identity entries. ThereforeThe required Fréchet derivative is the linear functionalThe quadratic remainder proves full differentiability, rather than only the existence of each directional derivative. This is the derivative of the determinant.

The regular level set theorem says that a $C^1$ map $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ with surjective derivative at every point of $f^{-1}(0)$ has a zero set that is an embedded $C^1$ submanifold of dimension $n-m$. At each point $a$ of that zero set,For a smooth map the submanifold is smooth. The full-rank hypothesis is essential for this kernel description when using a particular defining map.

Apply the regular level set theorem to $F(A)=\det A-1$ on the $n^2$-dimensional vector space of real matrices. At a point with determinant one, part (b) gives $D{F}_A(H)=\mathrm{tr}(A^{-1}H)$. Choosing $H=A/n$ gives $D{F}_A(H)=1$, so this derivative is surjective.

Hence the special linear group $\mathrm{SL}(n,\mathbb{R})$ is a smooth submanifold of dimension $n^2-1$. At the identity,This is the special linear Lie algebra. When $n=1$, the group is a single point and the tangent space is zero, consistent with the same formula.

Use the six-dimensional vector space of real symmetric $3\times 3$ matrices as the target, rather than all nine matrix entries independently. DefineIts derivative isThe given $J$ is symmetric with $J^2=I$. Every $A\in G$ is invertible, since taking determinants of $A^{T}JA=J$ gives $(\det A{)}^2=1$. For any symmetric target $S$, chooseThen $A^{T}JH=\frac{1}{2}JJS=S/2$, and its transpose is also $S/2$. Thus $D{F}_A(H)=S$ and the derivative is surjective at every point of $G$.

The regular level set theorem now givesIt also proves smooth embeddedness in the entire ambient vector space of matrices. The target symmetry is what gives the correct codimension.

The tangent space at the identity is the kernel of a linear map from part (i):This says precisely that $JH$ is skew-symmetric. Since $J^{-1}=J$, multiplication by $J$ identifies this tangent space with the three-dimensional space of skew-symmetric $3\times 3$ matrices. In entries it isSubstitution verifies the equation directly and displays its three independent parameters.

Take a smooth variation $y_{\epsilon }=y+\epsilon \eta$. Differentiating the functional at zero gives the first variationIntegrate the second term once and the third term twice by integration by parts:Choose variations supported away from the endpoints. Stationarity and the fundamental lemma of the calculus of variations forceThis is the Euler-Lagrange equation for a second-derivative functional. With the interior equation imposed, the remaining boundary expression must vanish for every admissible variation.

At each endpoint, a freely varying value $y$ requires $\boxed{F_{y^{\prime }}-(F_{y^{\prime \prime }}{)}^{\prime }=0}$, and a freely varying slope $y^{\prime }$ requires $\boxed{F_{y^{\prime \prime }}=0}$. A fixed value or slope instead makes its corresponding variation zero and supplies no natural condition for that variable. These are the natural boundary conditions for second-derivative functionals, with the value and slope variations treated independently.

Here $F_y=\rho g$, $F_{y^{\prime }}=0$, and $F_{y^{\prime \prime }}=K{y}^{\prime \prime }$. The Euler-Lagrange equation for a second-derivative functional is thereforeWrite $q=\rho g/K>0$. After imposing the clamped conditions at zero, the general solution isFree right endpoint. Both endpoint variations are free, so the natural boundary conditions for second-derivative functionals give $y^{\prime \prime }(L)=y^{\prime \prime \prime }(L)=0$. Since $y^{\prime \prime \prime }=-qx+A$ and $y^{\prime \prime }=-q{x}^2/2+Ax+B$, they give $A=qL$, $B=-q{L}^2/2$. HenceRight endpoint with fixed height and free slope. Now $y(L)=0$ is imposed, while the free slope gives $y^{\prime \prime }(L)=0$. These equations yield $A=5qL/8$ and $B=-q{L}^2/8$, soBoth endpoints clamped. The right conditions are $y(L)=y^{\prime }(L)=0$, giving $A=qL/2$, $B=-q{L}^2/12$. ThusEach formula has fourth derivative $-\rho g/K$ and satisfies all four boundary conditions of its case. The three endpoint choices therefore change the integration constants, not the interior differential equation.

The sets of admissible functions are nested:All impose the same left conditions; the right height adds a restriction, and the right slope adds another. Minimizing the same functional over a smaller set cannot lower its minimum. ThereforeThe doubly clamped beam has the greatest minimum energy, and the free-ended beam the smallest. No energy integrals are needed. In fact the inequalities are strict: the positive quadratic bending term makes the minimizer unique on the left-clamped space, and the three solutions in part (b) are different. The relevant principle is monotonicity of a constrained minimum under added constraints.

A Hamilton cycle is a cycle visiting every vertex of a finite graph exactly once before returning to its starting point. A Hamilton path is a path visiting every vertex exactly once, with no requirement to return or to have its endpoints adjacent. Both conditions concern visiting vertices, rather than traversing every edge.

Let $v_1\dots v_k$ be a longest path in the finite simple graph. Every neighbor of either endpoint lies on this path, since an outside neighbor would extend it. Define two subsets of $\{1,\dots ,k-1\}$:Their sizes are $d(v_1)$ and $d(v_k)$. The degree hypothesis gives $|I|+|J|\ge n\ge k$, but there are only $k-1$ possible indices. Hence some $i$ belongs to both. The edges at that index close a cycle through every vertex of the path:The graph is connected: any component has at least $n/2+1$ vertices by the minimum degree, so two components would exceed $n$ vertices. If $k<n$, connectedness gives an edge from this cycle to an outside vertex. Starting at that vertex and traversing the cycle without its closing edge gives a path with $k+1$ vertices, a contradiction.

Thus $k=n$ and the cycle is a Hamilton cycle, proving Dirac's theorem. The overlap-of-indices argument is why the degree threshold is half the number of vertices.

Take the complete bipartite graph $\boxed{K_{3,4}}$. Its seven vertices have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.

Every cycle in a bipartite graph alternates between its two parts, using equal numbers of vertices from each. A Hamilton cycle here would have to use three vertices from one part and four from the other, which is impossible. Thus three-vertex connectivity and minimum degree three do not suffice for Hamiltonicity in this seven-vertex example.

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore

Put $A=R(k-1,\ell )$, $B=R(k,\ell -1)$ and consider any coloring of $K_{A+B}$. Choose a vertex $v$. Among its $A+B-1$ neighbors, either at least $A$ are joined to it by red edges, or at least $B$ by blue edges.

In the red case, the induced complete graph on those neighbors contains either a red $K_{k-1}$, which joins with $v$ to make a red $K_k$, or a blue $K_{\ell }$. The blue case similarly gives a red $K_k$ or a blue $K_{\ell -1}$ which extends with $v$ to a blue $K_{\ell }$. Hence every coloring has the required configuration, andThis is the Ramsey number recursion.

Fix $w\in W$. It has five incident edges, so three of them have the same color by the pigeonhole principle. Suppose they are red, with other endpoints $a,b,c$. Any existing edge among $a,b,c$ must be blue, or it would complete a red triangle with $w$.

If all three edges among $a,b,c$ existed, they would therefore form a blue triangle. Thus their triple must contain the unique missing edge $uv$. In particular, both $u$ and $v$ belong to the three red neighbors, so $wu$ and $wv$ are both red. The identical argument works if the chosen three edges are blue.

Therefore $wu$ and $wv$ have the same color for every $w\in W$. The missing edge is crucial: it is the only way the monochromatic neighbor triangle can fail to be present.

Use the Minkowski metric with signature $(+---)$ and write $U=(U^0,\mathbf{u})$, $V=(V^0,\mathbf{v})$. Future-pointing timelike means $U^0>\Vert \mathbf{u}\Vert$ and $V^0>\Vert \mathbf{v}\Vert$. Thusso $U+V$ is again future-pointing timelike.

Let $a=\sqrt{g(U,U)}>0$ and $b=\sqrt{g(V,V)}>0$. In a Lorentz frame where $U=(a,0,0,0)$, the future-pointing vector $V$ has $V^0\ge b$. Consequently $g(U,V)=a{V}^0\ge ab$, with equality exactly when $V$ has no spatial component in that frame. HenceTaking positive square roots provesEquality holds exactly when $U,V$ are positive scalar multiples of each other. This is the reverse triangle inequality for future timelike vectors, not the Euclidean triangle inequality.

Take spacetime coordinates $X=(ct,x,y,z)$. Differentiating the initial segment gives the four-velocityThe identity ${\cosh }^{2}r-{\sinh }^{2}r=1$ gives $g(U,U)=c^2$, and $dt/ds=\cosh \omega s>0$. The proper time element therefore satisfies $d{\tau }^2=g(dX,dX)/c^2=d{s}^2$, with the future orientation selecting $d\tau =ds$. Thus $s$ is proper time along this path.

Since $s$ is proper time, the four-acceleration isIts Minkowski norm squared is $g(A,A)=-c^2{\omega }^2$, so the invariant magnitude of proper acceleration isThe vector is spacelike, which accounts for the minus sign under the square root.

Differentiate each segment and express the four-velocity using a continuous rapidity:At $T$ both rapidities are $\omega T$; at $3T$ both are $-\omega T$. Hence the four-velocity is continuous at both junctions. This expression also gives $g(U,U)=c^2$ everywhere, so the parameter remains proper time on the later segments.

Away from the junctions,with ${\theta }^{\prime }$ successively $+\omega ,-\omega ,+\omega$. The rapidity is continuous but its slope reverses. Thus the four-acceleration has a finite jump to its negative at each junction, while its magnitude stays $c\omega$ on either side. There is no velocity jump; the idealized path is continuously differentiable but not twice differentiable at the switching events.

At $s=0$ and $s=4T$, the mission is at the planet's position $x=c/\omega$. The final coordinate time from the last segment isThe planet is at rest in these coordinates, so its proper time elapsed equals this coordinate-time difference. The astronauts' proper time is the parameter interval, $4T$. ThereforeFor proper acceleration $c\omega =10\mathrm{m}{\mathrm{s}}^{-2}$ and $c=3\times 10^8\mathrm{m}{\mathrm{s}}^{-1}$, ${\omega }^{-1}=3\times 10^7$ seconds, approximately one year. Thus $\omega T=16$ and $e^{16}\approx 3000^2=9\times 10^6$. Neglecting $e^{-16}$ in the hyperbolic sine,The clocks compare two different timelike paths between the same departure and reunion events.

Put $a=\omega T$. At emission, $s=2T$, the middle segment givesThe planet is at $x_p=c/\omega$, so the inward light signal takes coordinate timeIts arrival time on the planet is therefore $t_r=2(e^a-1)/\omega$. Subtract this from the mission's return time $4\sinh a/\omega$:For large $T$ at fixed acceleration this tends to $2/\omega =2c/(c\omega )$. With the Earth-gravity value above, the wait is approximately two years, despite the millions of planet-years elapsed since departure in part (i).