Past exam of the options I course of the University of Oxford / 2006 (AO1, XMAT 4303)

Options I, Honour School of Mathematics; Friday 23 June 2006, 9.30am–12.30pm. The complete nine-page source was supplied in the disclosed past-papers archive, member “FOI-20210708-1 - Data/4303 (6).pdf”, through the original request. The full source is privately transcribed. No exact worked-answer advertisement was found in the bounded availability check.

Write the group action as $(\omega ,g)\mapsto \omega g$. A right group action satisfies $\omega 1=\omega$ and $(\omega g)h=\omega (gh)$. Its orbit and stabilizer areThe identity belongs to $H$. If $g,h\in H$, then $\omega gh=(\omega g)h=\omega$, so $gh\in H$. Also $\omega g=\omega$ implies $\omega =(\omega g)g^{-1}=\omega g^{-1}$, so $g^{-1}\in H$. Thus $H$ is a subgroup.

For the orbit-stabilizer theorem, the map $G\to \mathrm{Orb}(\omega )$, $g\mapsto \omega g$, is onto, andIts fibers are precisely the right cosets $Hh$, each containing $|H|$ elements. Counting these disjoint fibers givesFor the symmetric group $S_3$, the six subgroups areThe group action $H\mapsto g^{-1}Hg$ has four orbits: each of $\{1\}$, $A_3$, and $S_3$ is fixed, while the three order-two subgroups form one orbit. Here an orbit is a collection of subgroups, rather than a collection of individual permutations.

A field extension $K/F$ is finite when $K$, regarded as a vector space over $F$, has finite dimension. Its degree of a field extension isThus a finite basis $u_1,\dots ,u_m$ means that every $k\in K$ is uniquely expressible as ${\sum }_i{c}_i{u}_i$ with coefficients $c_i\in F$.

Since $K$ is an $F$-vector subspace of the finite-dimensional vector space $L$, it has a finite $F$-basis $u_1,\dots ,u_m$. Any finite $F$-spanning set for $L$ also spans $L$ over $K$, so choose a finite $K$-basis $v_1,\dots ,v_r$ of $L$.

Every $\ell \in L$ can be expanded first in the $v_j$ and then in the $u_i$, showing that the products $u_i{v}_j$ span $L$ over $F$. If ${\sum }_{i,j}{c}_{ij}{u}_i{v}_j=0$ with $c_{ij}\in F$, independence of the $v_j$ over $K$ gives ${\sum }_i{c}_{ij}{u}_i=0$ for every $j$; independence of the $u_i$ then gives every $c_{ij}=0$. The products form an $F$-basis, proving the tower law for field extensions:

Put $E=F(a,b)$. The tower law for field extensions shows that both $m$ and $n$ divide $[E:F]$. Since $m,n$ are coprime, their product divides $[E:F]$, so $[E:F]\ge mn$.

The minimal polynomial of $b$ over $F$ has degree $n$ and is still an annihilating polynomial over $F(a)$. The minimal polynomial over $F(a)$ divides it, soThe upper and lower bounds agree:Coprimality is the step forcing the lower bound to equal the product; without it the two generated fields can overlap substantially.

Use the agreed text encoding to split the plaintext into integer blocks $m_j\in \{0,\dots ,1072\}$. RSA encrypts each block by modular exponentiation:Because $1073=29\cdot 37$ is a product of distinct primes, its Euler totient function is $\phi (1073)=28\cdot 36=1008$. The inverse exponent follows fromThus a decryption exponent is 275, and the three recovered blocks areTo check every block, including blocks not coprime to the modulus, reduce modulo each prime. If $m_j$ is nonzero modulo 29, Fermat's little theorem gives $m_j^{3025}=m_j$ because $28\mid 3024$; if it is zero the equality is immediate. The same argument works modulo 37 because $36\mid 3024$. The Chinese remainder theorem then gives the equality modulo 1073. Finally reverse the agreed text encoding. The symbols $r_1,r_2,r_3$ are unspecified, so there are no numerical message blocks to evaluate further.

The Gaussian function is continuous and hence Lebesgue measurable. For $|x|\ge 2$, $x^2/2\ge |x|$, and thereforeThe right side has finite Lebesgue integral: its first term has integral 4 and the second is Lebesgue integrable by hypothesis. The comparison principle for the Lebesgue integral says that a measurable nonnegative function dominated by an integrable function has finite integral. Consequently the Gaussian function is Lebesgue integrable.

A real measurable function is Lebesgue integrable precisely when the integral of its absolute value is finite. For every integer $k\ge 1$, on $I_k=[k+1/6,k+5/6]$ one has $|\sin \pi x|\ge 1/2$ and $x\le k+1$. ConsequentlyThe intervals have disjoint interiors. Countable additivity of the nonnegative Lebesgue integral, or the monotone convergence theorem applied to their finite unions, givesThe harmonic series diverges, so the function is not Lebesgue integrable. Cancellation between adjacent oscillations cannot give absolute integrability.

The annulus is open and hence Lebesgue measurable; multiplying its indicator by the continuous Gaussian gives a measurable function. It is bounded by the indicator of $[-b,b{]}^2$, whose Lebesgue integral is $4b^2$. Thus it is Lebesgue integrable by comparison.

Use the change of variables formula with polar coordinates $x=r\cos \theta$, $y=r\sin \theta$. Removing one radial cut makes this a smooth one-to-one coordinate map; the cut is a null set and does not affect the integral. The absolute Jacobian determinant is $r$. By Fubini theorem,The antiderivative is $-e^{-r^2/2}$, which also makes the sign of the answer transparent.

In a metric space, a Cauchy sequence has arbitrarily small distances between all sufficiently late terms:This condition compares terms to each other and does not assume that a limit exists in the space.

A sequence converges to $x\in X$ whenThe phrase convergent sequence requires the limit to belong to the stated metric space; convergence in a larger ambient space alone does not suffice.

A complete metric space is a metric space in which every Cauchy sequence converges to a point of that space.

If $x_n\to x$, choose $N$ so that $d(x_n,x)<\epsilon /2$ for all $n\ge N$. The triangle inequality gives $d(x_m,x_n)\le d(x_m,x)+d(x,x_n)<\epsilon$, proving the Cauchy sequence property.

Now let $A$ be complete in the induced metric. If $x\in \overline{A}$, choose $a_n\in A$ with $d(a_n,x)<1/n$. The sequence converges to $x$ in $X$, so is a Cauchy sequence. Completeness of $A$ supplies a limit $a\in A$. Uniqueness of limits in a metric space gives $a=x$, hence $\overline{A}\subseteq A$. Therefore a complete metric subspace is closed.

Completeness does not imply sequential compactness. In the complete space $\mathbb{R}$, the sequence $x_n=n$ has no convergent subsequence: a subsequence has strictly increasing indices $n_k\ge k$, so $x_{n_k}\to +\infty$ and is unbounded, whereas every convergent real sequence is bounded.

A topological space is connected when it cannot be written as the union of two disjoint nonempty open sets. Equivalently, the only subsets that are simultaneously open and closed are the empty set and the whole space. For a subset, connectedness refers to its subspace topology.

True. Suppose $A\cup B=U\bigsqcup V$ were a separation into nonempty relatively open sets. Intersecting with $A$ gives a separation unless all of the connected set $A$ lies on one side; similarly all of $B$ lies on one side. A point of $A\cap B$ forces both to lie on the same side. The other side would then be empty, a contradiction. Hence $A\cup B$ is connected.

False. Take $X=\mathbb{R}$ and $A=B=\{0\}$. Both complements are disconnected: their negative and positive halves form a separation. Butis path-connected, hence connected. To see path connectedness directly, move any nonzero point radially to its normalization on the unit circle; join the two normalized points by a circular arc; then reverse the radial path for the second point. Every segment of this path avoids the origin. Thus disconnected coordinate complements do not force a disconnected complement of their product.

False. In $X=\mathbb{R}$, takeThen $A\cap B=\{2\}$ and $A\cup B=[0,2]$ are connected. Nevertheless $A$ is disconnected: $[0,1)$ and $\{2\}$ are disjoint nonempty relatively open sets partitioning $A$. For instance, intersecting $A$ with $(-1,3/2)$ and $(3/2,3)$ produces this separation. The endpoint missing from $[0,1)$ is supplied by $B$, so the union becomes connected without forcing $A$ itself to be connected.

The rows of the Jacobian matrix $Dg(a)$ are $\nabla g_1(a{)}^T,\dots ,\nabla g_k(a{)}^T$. Rank $k$ means precisely that these $k$ gradients are linearly independent. The Lagrange multiplier condition is that real numbers ${\lambda }_1,\dots ,{\lambda }_k$ exist withGeometrically, $\nabla f(a)$ is perpendicular to the tangent space of the constraint level set, whose tangent vectors form $\ker Dg(a)$. The full-rank hypothesis ensures this level set is a smooth local constraint manifold.

The constraint set $S^1\times S^2$ is compact, so the continuous objective attains a maximum and minimum. The two constraint gradients are nonzero and supported on separate coordinates, so they are linearly independent everywhere on it. The Lagrange multiplier equations areBoth positive and negative values occur. At a maximizing or minimizing point the objective is therefore nonzero, so $x_1\ne 0$, $y_2-y_3\ne 0$, and both $\lambda ,\mu$ are nonzero. The equations imply $x_2=0$, $y_1=0$, and $y_3=-y_2$. The constraints then give $x_1=\pm 1$, $y_2=\pm 1/\sqrt{2}$.

Consequently, writing $s=\pm 1$, the complete list of extrema isFor an independent global check, Cauchy-Schwarz inequality gives $|x_1(y_2-y_3)|\le |x_1|\sqrt{2(y_2^2+y_3^2)}\le \sqrt{2}$, with equality exactly at the displayed points.

Let $\eta$ be a smooth variation with $\eta (a)=\eta (b)=0$. Assuming the usual continuous second derivatives of $F$, stationarity of the functional under $y+t\eta$ gives its first variationIntegration by parts removes the derivative of $\eta$; its boundary term vanishes because the endpoint values are fixed. Thusfor every such variation. The fundamental lemma of the calculus of variations implies the Euler-Lagrange equation $F_y=(d/dx)F_{y^{\prime }}$.

For arc length, $F=\sqrt{1+(y^{\prime }{)}^2}$, soThe function $s\mapsto s/\sqrt{1+s^2}$ is strictly increasing; hence $y^{\prime }$ is constant. With endpoints $(a,A)$ and $(b,B)$, $a<b$, the extremal isIt is also the global shortest curve: integrating the unit displacement vector dotted with the curve velocity gives the endpoint distance, which is at most the integrated speed by Cauchy-Schwarz inequality; the straight segment attains equality. A vertical segment is described parametrically or after rotating axes, since it cannot be represented by $y(x)$ on a nontrivial horizontal interval.

For a holonomic conservative system the Lagrangian is $L(q,\dot{q},t)=T-V$, the difference between kinetic energy and potential energy. The Euler-Lagrange equations areIf $\partial L/\partial q_j=0$, this gives $d{p}_j/dt=0$ for the generalized momentum $p_j=\partial L/\partial {\dot{q}}_j$. Such a coordinate is a cyclic coordinate.

In cylindrical coordinates the squared speed is ${\dot{r}}^2+r^2{\dot{\theta }}^2+{\dot{z}}^2$. The holonomic constraint $z=r^2/a$ gives $\dot{z}=2r\dot{r}/a$, while gravity has potential energy $V=mgz$. ThereforeThere is no explicit $\theta$ dependence, so $\theta$ is a cyclic coordinate andThis is angular momentum about the vertical symmetry axis. At $r=0$ the polar angle is singular, but the Cartesian angular momentum $m(x\dot{y}-y\dot{x})$ remains well defined and has the same conserved value.

In SI units, Gauss's law for a closed surface with outward unit normal vector isSpherical symmetry and the absence of an imposed external field make the electric field radial, $\mathbf{E}=E_r(r){\mathbf{e}}_r$. For $0\le r\le a$ (with the physical radius $a>0$),Outside the charge distribution this becomes $Q(a)=8\pi K{a}^5/15$. Applying Gauss's law on spheres givesBoth formulas agree at $r=a$, and the first tends to zero at the origin. Thus the total charge is $8\pi K{a}^5/15$. Negative $K$ reverses the field direction. If the radius is zero the distribution vanishes; a negative value of $a$ gives no nonnegative-radius support under the printed piecewise inequalities and likewise gives the zero distribution.

For a twice continuously differentiable stream function, equality of mixed derivatives givesThis is the incompressible flow condition in two dimensions. A streamline is a curve whose tangent at each regular point is parallel to the instantaneous velocity field. Parameterize it by ${\gamma }^{\prime }(s)=c(s)(u,v)$. The chain rule yieldsTherefore the stream function is constant on each streamline. This proof includes arbitrary regular parametrizations; at a stagnation point the velocity vanishes and the usual tangent direction is not determined.

The complex potential of a two-dimensional potential flow is $w=\varphi +i\psi$, soFor $\mu \ne 0$, a nonzero level $\psi =c$ isThus the streamlines are circles tangent to the horizontal axis at the excluded singular origin, with centers on the vertical axis. Each circle has the origin removed. The zero level is the horizontal axis without the origin, whose positive and negative rays are separate streamlines. Since $w^{\prime }=-\mu /z^2$ is nonzero away from the origin, no other stagnation points intervene. For $\mu =0$ the flow vanishes everywhere off the origin, so the circle description is replaced by the degenerate zero-velocity field.

The stream function gives $u=2\alpha xy$ and $v=-\alpha y^2$. Its scalar vorticity isFor $\alpha \ne 0$ this does not vanish on any nonempty open region of the plane. A holomorphic complex potential of a two-dimensional potential flow would produce an irrotational flow there. Equivalently, its imaginary part would be a harmonic function, whereas $\Delta \psi =2\alpha x$. Thus no complex potential exists on any nonempty open region for this flow; vanishing vorticity only along the vertical line does not provide a two-dimensional domain.

Start from the uniform-flow complex potential of a two-dimensional potential flow $Uz$. Milne-Thomson's circle theorem adds the image doublet $U{a}^2/z$, yielding constant stream function on $|z|=a$. Add a line vortex with positive counterclockwise circulation $\Gamma$:Indeed, on $z=a{e}^{i\theta }$ the uniform-flow and doublet terms sum to the real number $2Ua\cos \theta$, while the vortex has imaginary part $-\Gamma \log a/(2\pi )$, also constant. Thus the cylinder is a streamline and satisfies the impermeability condition. The vortex velocity is $\Gamma /(2\pi r)$ in the counterclockwise direction. Although the potential is multivalued when $\Gamma \ne 0$, its velocity is single-valued.

Differentiate and locate the coefficient of $z^{-1}$ in the square:For the counterclockwise contour in the printed Blasius force theorem, the residue theorem gives ${\oint }_C(w^{\prime }{)}^{2}dz=2U\Gamma$. ConsequentlyThese are force components per unit cylinder length; with the stated circulation convention the lift is downward for positive $U\Gamma$.

Convergence in probability means that for every $\epsilon >0$, $\mathbb{P}(|X_n-X|\ge \epsilon )\to 0$. The use of $>$ instead of $\ge$ gives the equivalent definition by replacing $\epsilon$ with a smaller positive number.

For $Y\ge 0$, the pointwise inequality $Y\ge a{1}_{\{Y\ge a\}}$ gives, on taking expected values, Markov's inequalityThis also holds if the expectation is infinite, though the resulting bound is then uninformative. Apply it to $Y=(X-\mu {)}^2$ with threshold ${\epsilon }^2$ to obtain Chebyshev's inequality:Set $S_n=n^{-1}{\sum }_{i=1}^n(Z_i-\mathbb{E}{Z}_i)$. Its mean is zero. Independence eliminates cross covariances, and boundedness gives $\mathrm{Var}(Z_i)\le \mathbb{E}{Z}_i^2\le 1$. HenceThus $\boxed{S_n\to 0\text{ in probability}}$. Identical distributions were never needed.

Two states lie in the same communicating class when each is reachable from the other by transitions of positive probability. Inspecting the directed transitions gives three classes:State 1 has no incoming transition from another state and can leave, so its singleton class is open and transient. More explicitly, the probability of returning to 1 after time zero is only $0.1$, since a departure can never be reversed.

States $2,3,6,7$ communicate: $2\to 3\to 7\to 2$ and $2\to 6\to 7$ are positive-probability paths. The class is open because, for example, $2\to 8$ and $6\to 4$ leave it; no transition from the class $\{4,5,8\}$ returns to it. Every state of $\{2,3,6,7\}$ is transient. One can see eventual exit directly: from each of its four states there is a positive-probability path of at most three steps to 8; the minimum of these four path probabilities is positive, so survival through repeated three-step blocks has a geometrically decreasing upper bound.

Finally $4\to 8\to 5\to 4$ shows that $\{4,5,8\}$ communicates, and every outgoing transition stays inside it. It is a closed finite irreducible class, so all its states are positive recurrent. Therefore the first two classes are open and transient; the last is closed and recurrent.

A stationary distribution is a nonnegative row vector $\pi$ with $\pi P=\pi$ and ${\sum }_i{\pi }_i=1$. The balance equations giveThe first yields ${\pi }_1={\pi }_4$. Substitution into the middle pair yields ${\pi }_2=3{\pi }_4/4$ and ${\pi }_3={\pi }_4$; the fourth equation is then satisfied. Normalization gives $15{\pi }_4/4=1$, henceAll states communicate, so this is the unique stationary distribution. The self-loop at state 1 additionally makes this finite Markov chain aperiodic, although aperiodicity is not required for the balance calculation.

For independent daily counts $X_1,\dots ,X_N$ modeled by a Poisson distribution, the log-likelihood isDifferentiating gives the maximum-likelihood estimator $\hat{\mu }=\overline{X}$. Here the observed frequencies sum to $N=1096$, and the expected frequencies are consistent with $\hat{\mu }\approx 2.157$ (their ratio $E_1/E_0$ estimates the same parameter). The final class is open-ended: its single observation is only reported as at least 9, so its exact contribution to the sample total cannot be recovered from this grouped table alone. The underlying ungrouped daily observations determine the exact sample mean.

Fit the Poisson distribution using the estimated daily mean. For $k=0,\dots ,8$, its expected frequency isand $E_{\ge 9}=N\left(1-{\sum }_{k=0}^8{e}^{-\hat{\mu }}{\hat{\mu }}^k/k!\right)$. Each row's contribution to the Pearson chi-squared statistic is $(O_k-E_k{)}^2/E_k$. For example the zero-count class contributes $(162-126.784{)}^2/126.784\approx 9.781$. Summing the class contributions gives the test statistic; expected frequencies depend on the fitted model, while observed frequencies come directly from counting days.

The expected counts in the final two separate classes are too small for a reliable chi-squared asymptotic approximation. Pooling the last three classes gives the tail class $\ge 7$, with observed frequency $8+3+1=12$ and expected frequency $5.464+1.473+0.447=7.384$. This exceeds the usual expected-count guideline of 5. Pooling only the last two would leave an expected count of $1.920$, still too small. Pooling requires recomputing the contribution from the pooled totals, rather than adding the old separate contributions.

After pooling, there are eight categories: $0,1,\dots ,6,\ge 7$. Their frequencies have one constraint because they sum to $N$, and one model parameter was fitted. Thus the reference chi-squared distribution hasdegrees of freedom. The reported statistic satisfies $25.914>22.46$, the stated upper $0.001$ cutoff for six degrees of freedom. Therefore reject the Poisson model at the 0.1% significance level under the independence and common-mean assumptions. The discrepancy is especially pronounced in the zero-count class, but the test assesses the whole fitted distribution. The conclusion uses the approximate Pearson chi-squared goodness-of-fit test, not an exact finite-sample tail probability.

Assume each sampled response is truthful, card selection is independent of the student's status, and responses follow the usual independent sampling model. In randomized response, a yes answer occurs either for a user receiving the first question or for a nonuser receiving the complementary question. Its probability isConsequently $Y\sim \mathrm{Bin}(n,q)$, and the likelihood isFor $x\ne 1/2$, first maximize the binomial likelihood in the unrestricted probability $q$: its maximum occurs at $Y/n$. Inverting the affine relation givesFor an interior value $0<Y<n$, the same result follows from the scoreThe endpoint cases follow by monotonicity. This estimator has expected value $p$ and varianceThese identities follow immediately from $\mathbb{E}Y=nq$ and $\mathrm{Var}(Y)=nq(1-q)$.

The printed claim needs a parameter-space qualification. The admissible yes probabilities lie in $[\min (x,1-x),\max (x,1-x)]$, which may exclude $Y/n$. The constrained maximum-likelihood estimator isThe displayed untrimmed estimator is the maximum-likelihood estimator only when it already lies in $[0,1]$. Its unbiased estimator property does not carry over to the clipped estimator in general. For example, if $n=1$, $x=3/4$ and $p=0$, the clipped estimate equals 1 exactly when the answer is yes, so its expectation is $1/4$, not zero. At $x=1/2$, $q=1/2$ for every $p$: the parameter is unidentifiable and the printed quotient is undefined. Thus the unbiased formula requires $x\ne 1/2$, and the constrained likelihood assertion requires the stated clipping.

The Lagrange interpolation polynomial constructs existence explicitly:Distinct nodes make every denominator nonzero, and ${\ell }_j(x_k)={\delta }_{jk}$, so $p(x_k)=f_k$ and $p$ has degree at most $n$. If two such polynomials existed, their difference would have degree at most $n$ but at least $n+1$ distinct roots. The root bound for a nonzero polynomial forces that difference to vanish. Thus the interpolating polynomial exists and is unique.

The polynomial $p(x)=x^2-2x$ already has degree at most three and gives the specified data at every node. Uniqueness of polynomial interpolation therefore gives

Let $f(x)=x^4-6x^3+11x^2-5x$. The node polynomial isIt vanishes at all four nodes, so subtracting it leaves the data unchanged. Since $f(x)-\omega (x)=x$, uniqueness of polynomial interpolation gives

The form is symmetric and bilinear by the corresponding properties of finite real sums. Its squared norm is $⟨p,p⟩={\sum }_{i}p(x_i{)}^2\ge 0$. Equality means $p$ vanishes at all $n+1$ distinct nodes. A nonzero polynomial of degree at most $n$ has at most $n$ roots, so equality forces $p=0$. Thus this is an inner product on ${\Pi }_n$.

On ${\Pi }_{n+1}$ it is only positive semidefinite: the nonzero node polynomial $\omega (x)={\prod }_{i=0}^n(x-x_i)$ satisfies $⟨\omega ,\omega ⟩=0$. Hence it is not an inner product on ${\Pi }_{n+1}$. The finite-evaluation inner product on polynomials works exactly when the evaluation map is injective on the chosen space.

Finally, if $q\ne 0$, positivity applied to $p-tq$ and the choice $t=⟨p,q⟩/⟨q,q⟩$ giveRearranging proves Cauchy-Schwarz inequality in its required form:If $q=0$ both sides of the asserted inequality are zero. Equality holds exactly when $p,q$ are linearly dependent, since in the nonzero case the minimizing $p-tq$ must have zero norm.