Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 2

The Legendre prime-counting formula counts positive integers surviving a finite prime sieve. For $x\ge 2$, put $a=\pi (\sqrt{x})$ and let $p_1,\dots ,p_a$ be the primes at most $\sqrt{x}$. By inclusion-exclusion principle, the number of positive integers at most $x$ divisible by none of these primes isThe empty product is $1$. Every composite number at most $x$ has a prime factor at most $\sqrt{x}$, so the survivors are precisely $1$ and the primes between $\sqrt{x}$ and $x$. ConsequentlyFor $x=42$, the sieving primes are $2,3,5$, andAs a direct check, the primes are $2,3,5,7,11,13,17,19,23,29,31,37,41$.

False. If uniform convergence held, some polynomial $P_n$ would satisfy ${\sup }_{t\in \mathbb{R}}|P_n(t)-\sin t|<1$. Such a polynomial would be bounded on $\mathbb{R}$, hence constant: a nonconstant polynomial grows without bound in absolute value along a real half-line. For any constant $c$, however,a contradiction.

True. By the Weierstrass approximation theorem, choose a polynomial $Q_n$ with ${\sup }_{|t|\le n}|Q_n(t)-f(t)|<1/n$. For each fixed $t$, this bound applies once $n\ge |t|$, so $Q_n(t)\to f(t)$. This proves pointwise convergence; the same construction even gives uniform convergence on every closed interval.

True. Define $h(u)=g(1/u)$ for $0<u\le 1$ and $h(0)=0$. The hypothesis at infinity makes $h$ continuous on $[0,1]$. The Weierstrass approximation theorem gives polynomials $R_n$ with ${\sup }_{0\le u\le 1}|R_n(u)-h(u)|\to 0$. Since $t\mapsto 1/t$ maps $[1,\infty )$ onto $(0,1]$,

Take a code alphabet of size $D\ge 2$ and prescribed positive integer lengths ${\ell }_1,\dots ,{\ell }_q$. A decipherable code means that concatenation of codewords determines the entire finite sequence of codewords uniquely. First prove the necessary Kraft inequality. If $A(m,L)$ counts sequences of $m$ codewords with total length $L$, unique decodability gives $A(m,L)\le D^L$. ThereforeTaking $m$th roots and letting $m\to \infty$ gives $K\le 1$.

Conversely, order the lengths increasingly and construct a prefix code in the rooted $D$-ary tree. At depth ${\ell }_j$, previously selected codewords forbid exactly ${\sum }_{i<j}{D}^{{\ell }_j-{\ell }_i}$ vertices. The partial Kraft inequality impliesso an available vertex exists. Select it as the next codeword. Earlier lengths are no greater, so this preserves the prefix code property. A prefix code has unique decodability: in two purported parsings, the first unequal codewords would force one to be a prefix of the other. This proves the equivalence of decipherable and prefix code lengths: the two existence conditions are equivalent.

For a one-symbol alphabet, at most one positive-length codeword can be decipherable: two different unary codewords commute under concatenation. At most one is also exactly the prefix-code condition, so the equivalence still holds. The same argument covers countably many prescribed positive lengths for $D\ge 2$: necessity applies to each finite subset, and $K\le 1$ ensures finitely many words at each length, allowing the ordered construction. Empty codewords are excluded, as required for unique decodability of arbitrary sequences.

Use $L=\{a^n{b}^n:n\ge 0\}$. The context-free grammar $S\to aSb\mid \epsilon$ generates exactly $L$, so it is a context-free language. It is not a regular language: if $p$ is a pumping length, any allowed decomposition of $a^p{b}^p$ has a nonempty pumped segment consisting only of $a$'s. Pumping down leaves fewer $a$'s than $b$'s, contradicting the pumping lemma for regular languages. Thus $L$ is a context-free language but not a regular language.

Use $L=\{a^n{b}^n{c}^n:n\ge 0\}$. A halting algorithm checks that a word consists of three consecutive blocks in the correct order and compares their lengths, so $L$ is a decidable language. If it were a context-free language, apply the pumping lemma for context-free languages to $a^p{b}^p{c}^p$. The segment containing both pumped pieces has length at most $p$, so it cannot meet both the $a$ and $c$ blocks. Pumping down therefore changes at least one block count but leaves another equal to $p$, or destroys the required block order. Either way the resulting word is not in $L$, a contradiction. Thus $L$ is a decidable language but not a context-free language.

Fix an effective numbering of Turing machines and use the diagonal halting setIt is computably enumerable: dovetail all the computations and output each index when its computation halts. It is not a recursive set. Otherwise a machine could, on input $e$, loop if the alleged decider says $e\in H$ and halt otherwise. Applying this machine to its own index contradicts either answer. Hence $H$ is computably enumerable but not a recursive set.

With the diagonal halting set $H$, defineIf $A$ were computably enumerable, its odd-index inverse image would make $\mathbb{N}\setminus H$ computably enumerable. If $\mathbb{N}\setminus A$ were computably enumerable, its even-index inverse image would do the same. But a set and its complement being computably enumerable would make the set a recursive set: run the two enumerations in parallel until the input appears in one. This contradicts the undecidability of $H$. Thus neither $A$ nor its complement is computably enumerable.

Use the usual normal linear model $Y=X\beta +\epsilon$, with fixed full-column-rank design $X\in {\mathbb{R}}^{n\times p}$, $n>p$, and $\epsilon \sim N(0,{\sigma }^2{I}_n)$. These Gaussian distribution and constant-variance hypotheses are necessary for an exact finite-sample Student's t-test. Put $V=(X^{T}X{)}^{-1}$ and $\nu =n-p$. The vector of ordinary least squares estimators satisfiesWith $s^2=\Vert Y-X\hat{\beta }{\Vert }^2/\nu$, the test statistic isUnder the null hypothesis, $T$ has Student's t-distribution with $\nu$ degrees of freedom. A two-sided level-$5\%$ Student's t-test rejects when $|T|>t_{\nu ,0.975}$. If the intended test is one-sided against ${\beta }_0>0$, it rejects when $T>t_{\nu ,0.95}$; the statistical power conclusion below holds for either convention.

The orthogonal projections of the Gaussian noise onto the column space of $X$ and its orthogonal complement are independent. Consequently ${\hat{\beta }}_0$ and the residual sum of squares are independent, andThus under the alternative,This is the noncentral t-distribution. The rejection region is fixed by the design, $\nu$ and the chosen level, while this probability distribution depends on $\beta$ only through ${\beta }_0$. Therefore the statistical power does not depend on the other regression coefficients, with the design and $\sigma$ fixed.

For this chemical reaction network, the law of mass action gives the reaction rates are $k_1{s}^{2}e$, $k_{2}c$ and $k_{3}c$. Their stoichiometry givesHere the convention for $k_1$ absorbs any combinatorial factor for two identical reactants. Direct differentiation gives the two conservation lawsEliminating $e$ and $p$ leavesFor positive $s_0,e_0,k_1$, use the dimensionless variables $u=s/s_0$, $v=c/e_0$ and $\tau =k_1{e}_0{s}_{0}t$. With prime marks denoting differentiation in $\tau$, this becomeswhere

The given Euler product for the gamma function has the finite approximantsaway from the poles. Split the denominator of ${\Gamma }_{2m+1}(2z)$ into even and odd factors. The resulting exact identity isThe right side does not depend on $z$, so its limit is a constant $C$. Evaluate the ratio at $z=1/2$: $\Gamma (1)=1$, and the gamma reflection formula, together with positivity on the positive real axis, gives $\Gamma (1/2)=\sqrt{\pi }$. HenceThis is the gamma duplication formula. The argument first applies where the factors are finite; the identity then holds as an identity of meromorphic functions, with values at poles interpreted accordingly.

For variations vanishing at both endpoints, differentiating the action and using integration by parts givesThe fundamental lemma of the calculus of variations therefore yields the Euler-Lagrange equationsFor the specified Lagrangian, the gauge transformation changes it byFor arbitrary $F$, it is a total derivative precisely when $\boxed{\alpha =-1}$. The corresponding change in action is then an endpoint term whose variation is zero. In general time-dependent notation, the equations areThe electric field $-\nabla \varphi -{\partial }_t\mathbf{A}$ and magnetic field $\nabla \times \mathbf{A}$ are unchanged by the gauge transformation with $\alpha =-1$. Although the original potentials have no time dependence, their transformed versions generally do; allowing this is essential to the stated invariance.

Differentiation of the Hubble parameter gives $\dot{H}+H^2=\ddot{a}/a$. The strong energy condition and the acceleration equation therefore implyAssume the present universe is expanding, $H_0>0$, and normalize the scale factor by $a(t_0)=1$. Since $\ddot{a}\le 0$, the past expanding branch has $\dot{a}(t)\ge \dot{a}(t_0)>0$. On this branch,Integrating from a past time $t$ to $t_0$ gives $H(t{)}^{-1}\le H_0^{-1}+t-t_0$. Thus, where the denominator is positive,The printed inequality needs this past-time qualification: for future times with $H>0$, the inequality reverses. Independently, a concave function lies below its tangent, soPositivity of $a$ prevents the past branch extending before the zero of this tangent. If $t_B$ is the beginning of the expanding universe, its age satisfies $\boxed{t_0-t_B\le H_0^{-1}}$. Without the normalization $a(t_0)=1$, the tangent bound instead reads $a(t)\le a(t_0)[1+H_0(t-t_0)]$.

The Baire category theorem says that in a nonempty complete metric space, every countable intersection of open dense sets is dense. To prove it, start in an arbitrary nonempty open set $O$ and let $G_n$ be open dense. Inductively choose closed balls $\overline{B}(x_n,r_n)$ with $0<r_n\le 2^{-n}$, contained in $G_n$ and in the interior of the previous ball, with the first also contained in $O$. Density provides a point at each stage, and openness permits the smaller closed ball. The centers are a Cauchy sequence; completeness supplies a limit lying in every closed ball, hence in $O\cap {\bigcap }_n{G}_n$. The proof also works at isolated points, where sufficiently small balls are singletons.

The incomplete metric space $\mathbb{Q}$ is a counterexample: it is the countable union of its closed nowhere dense singletons, so the complements are open dense with empty intersection.

For the sequence in the problem, putEach $E_N$ is closed by continuity. Pointwise convergence makes each point's values a Cauchy sequence, so $[0,1]={\bigcup }_N{E}_N$. By the Baire category theorem, one $E_N$ has nonempty relative interior, which contains a nonempty open interval $J$ in $(0,1)$. This proves the required common tail bound.

If continuous $g_n$ converged pointwise to the rationality indicator, take $ϵ=1/4$ and let $m\to \infty$ in this bound. On $J$, $|g_n-g|\le 1/4$ for $n\ge N$. Hence a fixed continuous $g_N$ is at least $3/4$ at every rational point and at most $1/4$ at every irrational point of $J$. The density of both sets contradicts continuity. Thus the rationality indicator is not a pointwise limit of continuous functions.

Nevertheless $h_n(x)=x^n$ are continuous and converge pointwise to $h(x)=0$ for $x<1$, $h(1)=1$. This limit is discontinuous at $1$: a pointwise limit of continuous functions can be discontinuous.

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.

Choose a branch of $t=1-z$ with $|\arg t|<\pi$ and write $d=c-a-b\notin \mathbb{Z}$. The Gauss hypergeometric equation isChanging to $t$ turns this into the same equation with third parameter $a+b+1-c=1-d$. Its solution regular at $t=0$ is $y_1=F(a,b,1-d;t)$. Substitution of $y=t^{d}v$ gives the Gauss hypergeometric equation for $v$ with parameters $c-a,c-b,1+d$. Thus $y_2=t^{d}F(c-a,c-b,1+d;t)$ is also a solution. Their distinct nonintegrally separated characteristic exponents at a regular singular point $0,d$ imply linear independence near $z=1$, soThis also follows from the exponent transformation in the Papperitz symbol.

Initially assume $\Re c>\Re b>0$, so the Euler integral for the hypergeometric function applies. If $\Re d>0$, taking $z\to 1$ gives an integral evaluated by the beta function and determinesIndeed $y_1\to 1$ and $y_2\to 0$ there. To find $B$, instead work in the nonempty parameter region $\Re d<0$, put $z=1-ϵ$ and scale the integration variable by $1-s=ϵu$. The singular contribution isThe defining integral of the beta function evaluates this integral to $\Gamma (c-b)\Gamma (-d)/\Gamma (a)$. Since ${ϵ}^{-d}{y}_1\to 0$ and ${ϵ}^{-d}{y}_2\to 1$, it determines $B$. Analytic continuation in the parameters then yields the hypergeometric connection formulaThe usual power-series definition requires $c\notin \{0,-1,-2,\dots \}$; exceptional parameters need a separately specified analytic limit. Reciprocal gamma functions make vanishing coefficients at denominator poles meaningful. The branch must remain fixed when continuing in $z$.

Let $\mathbf{r}$ be position relative to the center of mass, and let the new origin have vector $\mathbf{c}$ relative to it. The inertia tensor about this origin isExpanding and using $\int \mathbf{r}dm=0$ proves the tensor form of the parallel axis theorem:For a uniform cube of side $L$ and mass $M$, centered coordinate integrals give $I_0=(M{L}^2/6)I$. The displacement to a vertex is $(L/2,L/2,L/2)$ up to signs. Using axes along its incident edges givesThe principal moments of inertia are $\boxed{M{L}^2/6,11M{L}^2/12,11M{L}^2/12}$. The first principal axis is the body diagonal through the vertex; every direction perpendicular to it has the repeated moment.

For ordinals, the inductive definition of ordinal addition isThe synthetic definition takes a well-order of type $\alpha$, followed by a disjoint well-order of type $\beta$, with every point of the first preceding the second. They agree by transfinite induction on $\beta$: the empty second order does nothing; adding its last point takes the successor; at a limit ordinal, the concatenated order is the union of its initial concatenations, whose types have the displayed supremum.

The first assertion is false: $\boxed{1+\omega =\omega <\omega +1}$. Thus ordinal addition is not commutative.

False. Put $\alpha =\beta =1$ and $\gamma =\omega$. ThenThe two ordinals differ. The order of the factors matters in the distributive law for ordinal multiplication.

True. The valid distributive law for ordinal multiplication isThe synthetic definition of ordinal multiplication takes a sequence of copies of the left factor, indexed by the right factor. A sequence indexed first by $\beta$ and then by $\gamma$ is exactly the concatenation of the two corresponding sequences. Taking order types gives the identity. Equivalently, use transfinite induction on $\gamma$, with the successor rule and the supremum rule at limit ordinals.

True. If $\alpha \beta =\beta \alpha$, repeated use of associativity givesNo unlicensed commutativity of ordinal multiplication is being used: only the assumed commuting pair is swapped.

True. A useful fact is that squaring is strictly increasing on ordinals. If $A<B$, monotonicity in both arguments gives $A^2\le BA$, and strict increase in the right argument for the positive left factor $B$ gives $BA<B^2$. Hence $A^2<B^2$.

Suppose, for a contradiction, that $\alpha \beta <\beta \alpha$. Again using monotonicity and associativity of ordinal multiplication,This contradicts the hypothesized equality of the outer terms. Reversing the roles excludes $\beta \alpha <\alpha \beta$. If either factor is zero, they already commute. Therefore the commuting squares of ordinals property isThe proof uses monotonicity, which follows directly from the ordered-copy definition; it does not assume a cancellation law for ordinals.

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.

A finite field extension $L/K$ is a separable field extension if every element of $L$ has a minimal polynomial over $K$ with distinct roots in an algebraic closure. The primitive element theorem says that a finite separable field extension $L/K$ is $K(\alpha )$ for some $\alpha \in L$.

If $K$ is finite, then so is $L$. The multiplicative group of a finite field is cyclic, so a generator of $L^{\times }$ generates $L$ as a field. To justify the group fact, a finite subgroup of a field's multiplicative group is cyclic: in a finite abelian group its exponent is attained as an element order, while the polynomial root bound forces its size to be at most that exponent.

If $K$ is infinite, first consider $L=K(a,b)$. The minimal polynomials of $a$ and $b$ have distinct roots $a_i,b_j$ in an algebraic closure. Choose $c\in K$, $c\ne 0$, avoiding the finitely many values for which $a_i+c{b}_j=a+cb$ for a pair other than $(a,b)$. Set $\alpha =a+cb$. Over $K(\alpha )$, the polynomials $f(T)$ and $g((\alpha -T)/c)$ have precisely one common root, $a$. Their monic greatest common divisor is therefore $T-a$, so $a\in K(\alpha )$ and $b=(\alpha -a)/c\in K(\alpha )$. Thus $K(a,b)=K(\alpha )$. Induct over finitely many generators of the finite separable field extension. This proves every finite separable extension is simple.

Put $a=\sqrt{p}$, $b=\sqrt{-q}$ and $\alpha =a+b$. Since $a^2-b^2=p+q$, the identity $(a+b)(a-b)=p+q$ givesThus $\mathbb{Q}(\alpha )=\mathbb{Q}(\sqrt{p},\sqrt{-q})$. The latter has degree $4$: $p$ is not a square and $\mathbb{Q}(\sqrt{p})$ is real, whereas $\sqrt{-q}$ is not real. Squaring ${\alpha }^2=p-q+2\sqrt{-pq}$ gives its monic degree-$4$ minimal polynomial

In characteristic $p$, let $K={\mathbb{F}}_p(s,t)$ and $L={\mathbb{F}}_p(s^{1/p},t^{1/p})$, with $s,t$ having algebraic independence. The monomials $s^{i/p}{t}^{j/p}$, $0\le i,j<p$, form a $K$-basis, so $[L:K]=p^2$. Their independence follows by grouping polynomial monomials according to their exponents modulo $p$, after clearing rational-function denominators.

Every $\alpha \in L$ has ${\alpha }^p\in K$, so its minimal polynomial divides $T^p-{\alpha }^p$ and $[K(\alpha ):K]\le p$. Thus this finite purely inseparable extension has no primitive element. It demonstrates why the separable field extension hypothesis cannot simply be removed.