Options II course of the University of Oxford (AO2)

Source release: Oxford examination archive, member FOI-20210708-1 - Data/4304.pdf. The cover dates this examination to 20 June 2013, 9.30am–12.30pm. All source questions are answered in source order below.

A monic quadratic polynomial over a field is irreducible exactly when it has no root in that field. Testing the nine choices of its two coefficients in ${\mathbb{F}}_3$ givesFor clarity, a zero constant term gives a root at zero. Among constant term one, only the zero linear coefficient avoids roots at $1,2$. Among constant term two, precisely the linear coefficients one and two avoid roots. This exhausts all choices.

Put $f=x^4+x+2$. Its values at $0,1,2$ are respectively $2,1,2$, so it has no linear factor. If this quartic were reducible, absence of a linear factor would force a factorization into two irreducible quadratics. Division by the three candidates above gives remainders respectively $x,x+1,x+1$, all nonzero. Thus $f$ is an irreducible polynomial.

The quotient by an irreducible polynomial is a field consequently gives a field of $3^4=81$ elements. Its nonzero elements form a multiplicative group of a finite field of order $80$. In this field, $a^4=1+2a$. Successive squaring givesThe latter is not one: otherwise the nonzero polynomial $1+x+2x^3$ of degree below four would vanish at $a$, contradicting its minimal polynomial. By Lagrange's theorem, $(a^{16}{)}^5=a^{80}=1$. Since five is prime, its order is exactly five. Hence one answer isIts other nonidentity powers are the remaining primitive fifth roots. It is unnecessary to prove that $a$ itself generates the entire multiplicative group.

The orbit of $s$ is $O_s=\{gs:g\in G\}$, and its stabilizer is $G_s=\{g\in G:gs=s\}$. The identity fixes $s$; if $g,h$ fix it then $(gh)s=g(hs)=s$; and $gs=s$ implies $g^{-1}s=s$. Thus $G_s$ is a subgroup.

A group action is transitive when it has just one orbit: for every $s,t\in S$ there is $g\in G$ with $gs=t$.

On the set of left cosets $G/H$, define $g\cdot (xH)=(gx)H$. Given $xH$ and $yH$, the element $y{x}^{-1}$ sends the first to the second. Thus the coset action is transitive. In particular the orbit of $H$ is the entire coset space, and its stabilizer is $H$.

Two group actions on $S_1,S_2$ are equivalent if there is a bijection $\varphi :S_1\to S_2$ such that $\varphi (gs)=g\varphi (s)$ for all $g,s$. Such a bijection is equivariant.

The orbit-stabilizer theorem in this form says that the action on $O_s$ is equivalent to the left coset action on $G/G_s$, by $g{G}_s\mapsto gs$. This map is well-defined and injective because $gs=hs$ exactly when $h^{-1}g\in G_s$, and it is onto by the definition of the orbit. It is equivariant by multiplication.

Thus every transitive action is a coset action. Two such actions $G/H$ and $G/K$ are equivalent exactly when $H,K$ are conjugate: stabilizers at different points of one orbit are conjugate, and a conjugacy explicitly supplies a coset-action equivalence. This last classification is what makes counting by orbit types possible.

A cyclic group of order six has exactly one subgroup of each order $1,2,3,6$, and no others. Since it is abelian, these are also its four conjugacy classes of subgroups. Thus there is one transitive group action of each size $1,2,3,6$.

An action on six points is a disjoint union of its orbits. Its equivalence type is therefore determined by nonnegative integers satisfyingIf $n_6=1$ there is one possibility. If $n_6=0$, the possibilities $n_3=0,1,2$ allow respectively $4,2,1$ choices of $n_2$, with $n_1$ then fixed. HenceThis is counting finite group actions by transitive orbit types. Equivalently, a generator acts as a permutation whose cycles have lengths dividing six, and these are its eight possible cycle types on six points.

The symmetric group $S_3$ has subgroups of orders $1,2,3,6$. There is one trivial subgroup, three conjugate subgroups generated by transpositions, one order-three subgroup $A_3$, and the whole group. These are all subgroups by Lagrange's theorem. Thus again there is one conjugacy class for each index $6,3,2,1$.

The coset action classification in part (c) supplies exactly one transitive orbit type of each of these sizes. The same orbit-multiplicity equation as in part (i) applies, givingThe equality of the two counts comes from their identical lists of transitive orbit types, rather than from the groups being isomorphic.

For an odd prime $p$, the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue modulo $p$, and minus one if it is a quadratic nonresidue. ThusIt depends only on the congruence class of $a$ modulo $p$.

The first supplementary law for quadratic reciprocity isIt also follows immediately from Euler's criterion applied to $-1$.

The second supplementary law for quadratic reciprocity isThe exponent is an integer because every odd square is one modulo eight.

Multiplicativity of the Legendre symbol givesThis includes the case where $p$ divides a factor, when both sides are zero.

For distinct odd primes $p,q$, the quadratic reciprocity law isThus the two symbols have opposite signs exactly when both primes are three modulo four; otherwise they agree. Distinctness excludes zero symbols.

Factor $a={\prod }_i{q}_i$ and $b={\prod }_j{p}_j$, listing prime factors with repetitions. Coprimality ensures $q_i\ne p_j$. By the definition of the Jacobi symbol and multiplicativity of the Legendre symbol,For odd integers $r,s$,since the difference is $(r-1)(s-1)/2$, an even integer. Inductively the two sums in the exponent are congruent to $(a-1)/2$ and $(b-1)/2$ modulo two. HenceIf either number is one, the empty product convention proves the same identity. This extends the prime law to arbitrary coprime positive odd denominators.

Put $p=4272943$. Since $p\equiv 7(\mathrm{mod}8)$, the supplementary laws give $(-1/p)=-1$ and $(2/p)=1$. Therefore $(-286/p)=-(143/p)$.

Both $143$ and $p$ are three modulo four. Reciprocity for the Jacobi symbol, followed by the supplied remainder, givesAgain both denominators are three modulo four, soNow $103\equiv 7(\mathrm{mod}8)$ and $40=8\cdot 5$. Consequentlybecause the nonzero squares modulo five are one and four. Thus $(103/143)=1$, $(143/p)=-1$, and finallyThe congruence is soluble, with exactly two distinct solutions modulo this prime: a nonzero root and its negative. The computation uses a prime denominator in its final step; a positive Jacobi symbol with composite denominator would not by itself imply solubility.

The monotone convergence theorem states that if $0\le h_n\uparrow h$ pointwise for measurable functions, then $h$ is measurable and $\int h={\lim }_n\int h_n$, allowing infinity.

Apply it to the partial sums $S_N={\sum }_{n=0}^N{f}_n$. They are nonnegative, measurable, and increase pointwise to $f$. Finite additivity of the integral and monotone convergence yieldThe assumed finite sum of integrals makes $f$ integrable. This proves the series-integration rule needed below directly from the stated theorem, without assuming an additional interchange theorem.

For $\alpha >0$, integration by parts on $[0,R]$ givesThe exponential remainder tends to zero. Since the integrand is nonnegative, the monotone convergence theorem applied to truncations identifies the improper integral with the Lebesgue integral. ThereforeIts finite value proves integrability as well as evaluating it.

For $x>0$, the geometric series givesEvery summand is nonnegative and has integral $(n+\alpha {)}^{-2}$ by part (a). This numerical series converges by comparison with ${\sum }_{n\ge 1}{n}^{-2}$. The series-integration rule proved above therefore yieldsThe value at the single endpoint zero does not affect this Lebesgue integral.

On $0<x<1$, the geometric expansion gives summands $h_n(x)=x^{n+\beta -1}-x^{n-\beta }$. Their integrals areBoth powers are integrable because $0<\beta <1$. If $\beta <1/2$, each $h_n$ is nonnegative, since its first exponent is smaller. Their integrals form a convergent nonnegative series: the $n=0$ term is finite and subsequent terms are bounded by a constant times $n^{-2}$. The proved series-integration rule applies.

If $\beta >1/2$, apply precisely that rule to $-h_n$, which are nonnegative, and negate the result. At $\beta =1/2$ all summands and the integrand are zero. Thus in every case the integral is absolutely integrable andThe common sign of the summands is the reason no unproved theorem for integrating arbitrary signed series is needed.

A null set $E\subseteq \mathbb{R}$ has Lebesgue outer measure zero. Equivalently, for every $ϵ>0$ it can be covered by countably many open intervals whose total length is less than $ϵ$. This definition also applies before assuming $E$ measurable; every such set is Lebesgue measurable with measure zero.

A property holds almost everywhere when its exceptional set, where the property fails, is a null set. The exceptional set need not be empty or countable.

Given $ϵ>0$, cover $E_1$ by open intervals of total length less than $ϵ/2$, and cover $E_2$ similarly. Combining the two countable covers gives a cover of their union of total length less than $ϵ$. Thus $E_1\cup E_2$ is a null set.

For each $n\ge 1$, choose a countable interval cover of $E_n$ of total length below $ϵ/2^n$. The union of these covers is countable and covers ${\bigcup }_n{E}_n$, with total length less than ${\sum }_nϵ/2^n=ϵ$. As $ϵ$ is arbitrary, a countable union of null sets is null.

The relation is reflexive because the exceptional set for $f=f$ is empty, and symmetric because the exceptional sets for $f=g$ and $g=f$ agree. If $f=g$ off a null set $N_1$ and $g=h$ off a null set $N_2$, then $f=h$ off $N_1\cup N_2$, which is null by part (b). Hence it is transitive as well, so equality almost everywhere is an equivalence relation.

For each $n$, let $N_n$ be the null set where $f_n\ne g_n$. Their union $N$ is null. At any $x\notin N$, the two sequences agree term by term, so their pointwise limits are equal: $f(x)=g(x)$. Therefore $f\sim g$. Taking the countable union first is essential: it produces one exceptional set outside which all equalities hold simultaneously.

Exactly those integrable functions that vanish almost everywhere:Thus this expression is a seminorm on actual functions, becoming a norm after the quotient in part (ii).

Let $N$ be the vector subspace of integrable functions that vanish almost everywhere. The Lebesgue space is the quotient vector space $L^1(\mathbb{R})={\mathcal{L}}^1(\mathbb{R})/N$: its elements are equivalence classes of functions equal almost everywhere. Addition and scalar multiplication are $[f]+[g]=[f+g]$ and $c[f]=[cf]$.

Set $\Vert [f]{\Vert }_1=\int |f|$. This is well-defined because replacing $f$ by an equal-almost-everywhere representative does not change the integral. It is nonnegative, homogeneous, and obeys the triangle inequality by $|f+g|\le |f|+|g|$. Part (i) says its only zero element is the zero class. Hence it is a norm on $L^1$.

For each integer $m\ge 1$, list the $m^2$ functionsin increasing $j$, and concatenate the blocks in increasing $m$. Each function has $L^1$ norm $1/m$, so the resulting sequence has norm tending to zero. Every $x\in (0,1)$ lies in exactly one interval of each block, where the function takes value $m$. ThereforeThis unbounded typewriter sequence with vanishing L1 norm is a moving-spike construction: the support shrinks fast enough to beat the increasing height.

No such sequence exists. By Fatou's lemma on $(0,1)$,But the proposed nonnegative measurable integrand is positive at every point of $(0,1)$, so its integral cannot be zero. Explicitly, the sets where it is at least $1/k$ cover $(0,1)$; at least one has positive measure, forcing a positive integral. This contradicts the displayed bound.

If $A$ is closed and $a_n\in A$ converges to $x\in X$, then $x$ cannot lie in the open complement: an open ball about such an $x$ would eventually contain all $a_n$ while missing $A$. Thus $x\in A$.

Conversely, suppose $A$ contains every limit of a sequence in $A$. If $x\in \overline{A}$, every ball $B(x,1/n)$ meets $A$; choose $a_n$ in that intersection. Then $a_n\to x$, so $x\in A$. Hence $\overline{A}=A$, proving that a subset of a metric space is a closed set exactly when it is sequentially closed.

A metric space is complete when every Cauchy sequence in it converges to a point of that space. A sequence is Cauchy when, for each $ϵ>0$, there is $N$ such that $d(x_m,x_n)<ϵ$ whenever $m,n\ge N$. The requirement that the limit lie in the space distinguishes completeness from having limits only in a larger ambient space.

If $A$ is closed in the complete ambient metric space, any Cauchy sequence in $A$ converges in $X$ by completeness, and its limit belongs to $A$ by part (i). Thus $A$ is complete with its restricted metric.

Conversely, suppose $A$ is complete and a sequence $a_n\in A$ converges in $X$ to $x$. A convergent sequence is Cauchy, also in the restricted metric, so completeness of $A$ gives $a_n\to a$ for some $a\in A$. Uniqueness of a metric limit gives $x=a\in A$. Part (i) now makes $A$ closed. Hence

Let $a^{(m)}=(1,1/2,\dots ,1/m,0,0,\dots )$. Each has finite support, and in the supremum norm metric it converges to $a=(1,1/2,1/3,\dots )$, because $d(a^{(m)},a)=1/(m+1)$.

The limit is bounded but does not have finite support. Thus the finite-support subspace is not closed in $X$, and by part (a)(iii) it is not complete. Equivalently, the displayed sequence is Cauchy in that subspace but has no limit there.

Show that the subspace $C$ of convergent real sequences is closed in $X$. Suppose $a^{(m)}\in C$ converges uniformly in the coordinate index to $a\in X$. Given $ϵ>0$, choose $m$ so ${\sup }_j|a_j-a_j^{(m)}|<ϵ/3$. Since the fixed sequence $a^{(m)}$ converges, it is Cauchy, so for sufficiently large $j,k$ its coordinate difference is below $ϵ/3$. ThenThus $a$ is a Cauchy sequence of real numbers and converges by completeness of $\mathbb{R}$. Hence $a\in C$, so $C$ is closed. Part (a)(iii) proves the convergent-sequence subspace is complete.

A topological space is compact if every open cover of it has a finite subcover. That is, if $X={\bigcup }_{i\in I}{U}_i$ with all $U_i$ open, finitely many of those same open sets already cover $X$.

If the intersection were empty, the open complements $X\setminus F_i$ would cover the compact space. A finite subcover would give an empty finite intersection of the corresponding $F_i$. But the sets are nested, so any finite intersection is the set with largest index, which is nonempty. This contradiction provesThis is the nested-closed-set form of the finite intersection property for compact spaces.

Suppose no $F_N$ is contained in $U$. Then $K_i=F_i\cap (X\setminus U)$ are nested nonempty closed subsets of the compact space. Part (ii) gives a point in their intersection. Such a point lies both in ${\bigcap }_i{F}_i$ and outside $U$, contradicting the hypothesis. Thus some $F_N\subseteq U$, and nesting givesCompactness upgrades containment of the limiting intersection to eventual containment of the whole nested sets.

For each $b\in B$, use the supplied Hausdorff condition fact to choose disjoint open sets $U_b,V_b$ with $A\subseteq U_b$ and $b\in V_b$. Compactness of $B$ gives finitely many $b_1,\dots ,b_r$ whose $V_{b_j}$ cover $B$. SetBoth are open; $U$ contains $A$ and $V$ contains $B$. They are disjoint because membership in $U\cap V$ would put a point in some $U_{b_j}\cap V_{b_j}$. If one compact set is empty, use the empty set and $X$ directly. Thus disjoint compact subspaces of a Hausdorff space admit disjoint open neighborhoods.

A topological space is connected if it cannot be written as the union of two disjoint nonempty open subsets. Equivalently, its only subsets that are both open and closed are the empty set and the whole space. Under this definition the empty space is connected.

If $A$ is disconnected, a separation writes it as $A=A_1\cup A_2$ with $A_1,A_2$ disjoint, nonempty and open in its subspace topology. By definition there are ambient open sets $U,V$ with $A_1=U\cap A$ and $A_2=V\cap A$. These give exactly the four conditions stated.

Conversely, those conditions make $U\cap A,V\cap A$ two nonempty disjoint relatively open sets whose union is $A$. They are therefore a separation. This proves the equivalence. The ambient sets may overlap outside $A$, which is why the condition here is $U\cap V\cap A=\varnothing$.

If $A$ is disconnected, take a separation $A=A_1\cup A_2$. Each piece is also relatively closed, being the complement of the other. They are compact as closed subsets of the compact space $A$.

Part (b), using the ambient Hausdorff property, gives disjoint ambient open neighborhoods of $A_1$ and $A_2$. They meet $A$, cover it, and are disjoint everywhere, as required. Conversely, such ambient open sets give a separation on intersecting with $A$, by part (ii). Hence compactness and the Hausdorff property permit fully disjoint ambient neighborhoods.

Put $K={\bigcap }_i{F}_i$. If some $F_i$ is empty, so is $K$, which is connected. Otherwise the compact sets are closed in the Hausdorff ambient space, and can all be considered as nested nonempty closed subsets of the compact space $F_0$. Part (a)(ii) gives $K\ne \varnothing$, and $K$ is compact.

Suppose $K$ were disconnected. Part (c)(iii) gives disjoint ambient open sets $U,V$ covering $K$, both meeting it. Part (a)(iii), applied within $F_0$ to $U\cup V$, gives $F_N\subseteq U\cup V$ for some $N$. Both $U$ and $V$ meet $F_N$ because they meet $K\subseteq F_N$. Their intersections with $F_N$ would therefore disconnect $F_N$, a contradiction. Thus