Past exam of the mathematics course of the University of Cambridge / 2007 / ii

The Prime number theorem says $\pi (x)\sim x/\log x$ as $x\to \infty$. Bertrand's postulate says that for every integer $n\ge 2$ there is a prime number strictly between $n$ and $2n$.

To count S-smooth numbers, split each prime exponent into its parity and an even part. This gives the unique expression $n=a{b}^2$, where $a$ is a squarefree product of a subset of $S$. There are $2^{|S|}$ possible $a$, while $b\le \sqrt{x}$ whenever $n\le x$. The squarefree-part bound for smooth numbers therefore gives $f_S(x)\le 2^{|S|}\lfloor \sqrt{x}\rfloor \le 2^{|S|}\sqrt{x}$.

For an integer $x\ge 1$, take $S$ to be all prime numbers at most $x$. Every positive integer at most $x$ is then S-smooth, so $x\le 2^{\pi (x)}\sqrt{x}$. Taking logarithms yields

True. Define the Chebyshev polynomials by $T_0(x)=1$, $T_1(x)=x$, and $T_{n+1}(x)=2x{T}_n(x)-T_{n-1}(x)$. The cosine addition identities give the same recurrence for $\cos (nt)$, so mathematical induction proves $T_n(\cos t)=\cos (nt)$. For $n\ge 1$, the leading coefficient is $2^{n-1}$, proving that its polynomial degree is exactly $n$.

True, with $R_n=T_n$. The hyperbolic cosine identity $\cosh ((n+1)t)=2\cosh t\cosh (nt)-\cosh ((n-1)t)$ and the initial values $1,\cosh t$ give $T_n(\cosh t)=\cosh (nt)$ by mathematical induction, using the same Chebyshev polynomial recurrence.

False. A function of $\cos t$ is even in $t$, whereas $\sin (nt)$ is odd. If the identity held, replacing $t$ by $-t$ would imply $\sin (nt)=0$ for every $t$, contradicted by $t=\pi /(2n)$. Thus no polynomial of any degree has the required property.

Put the cube's vertices at $(\pm 1,\pm 1,\pm 1)$. Squared distances between distinct vertices are $4,8,12$ according as one, two or three coordinates differ. Four mutually equidistant vertices cannot all differ in one coordinate, since the cube has no triangles, or in three coordinates, since each vertex has only one antipode. They must differ in two coordinates. The two regular tetrahedra are therefore precisely the sets $xyz=1$ and $xyz=-1$.

The full symmetry group $G$ consists of signed coordinate permutations, so $|G|=2^3\cdot 3!=48$. These maps permute the two tetrahedra. The stabilizer $H$ of the first has order $24$ and acts faithfully on its four vertices: a linear map fixing the tetrahedron fixes a spanning set. Thus $H\cong S_4$. Central inversion $-I$ swaps the tetrahedra and commutes with every element of $H$, giving the direct-product decomposition of the cube symmetry groupHere $H$ preserves one tetrahedron; it is not the subgroup consisting only of rotations.

A uniquely decodable code is a map whose extension by concatenation to finite strings is injective. Write ${\ell }_j$ for its codeword lengths and assume the target alphabet has size $a\ge 2$. The Kraft–McMillan inequality gives $K={\sum }_j{a}^{-{\ell }_j}\le 1$. The Gibbs inequality says $D(p\Vert q)={\sum }_j{p}_j\log (p_j/q_j)\ge 0$ for probability distributions $p,q$, with the usual convention for zero probabilities.

Set $q_j=a^{-{\ell }_j}/K$. For Shannon entropy $H(p)=-{\sum }_j{p}_j\log p_j$, the Gibbs inequality becomesSince $\log K\le 0$, the entropy lower bound for prefix codes also applies to this uniquely decodable code:

The command fits independent grouped binomial distributions $Y_j\sim \mathrm{Bin}(N_j,p_j)$, using the supplied totals as trial counts. The logistic regression has the additive linear predictorThe reference category is adult females. The age and gender coefficients are conditional log odds ratios: the fitted odds for a child are multiplied by $e^{-1.27079}\approx 0.281$, and those for a male by $e^{-0.37211}\approx 0.689$.

The coefficients are maximum-likelihood estimates, found by Newton's method or iteratively reweighted least squares. With design matrix $X$ and $W_{jj}=N_j{\hat{p}}_j(1-{\hat{p}}_j)$, the estimated covariance matrix is $(X^{T}WX{)}^{-1}$; the printed standard errors are square roots of its diagonal entries. Each Wald test compares a coefficient with zero using its estimate divided by its standard error, approximately a standard normal distribution under the null. The age and gender effects are strongly significant. The intercept test instead tests whether the reference probability is $1/2$.

The fitted probabilities are about $0.04476$ for adult females, $0.03128$ for adult males, $0.01298$ for female children, and $0.008981$ for male children. Adult females have the largest fitted probability, about 4.48%. The residual deviance is $0.06514$ on $4-3=1$ degree of freedom; comparison with a chi-squared distribution gives $p\approx 0.799$. There is no evidence here that an age–gender interaction is needed, under the assumed independent binomial distribution model.

Let $D=Q/V_0$ be the dilution rate. Population loss is $DN$, and nutrient loss by consumption is $NK(C)/V_0$, so mass conservation givesUse the dimensionless variables $\tau =Dt$, $c=C/K_0$, and $n=N{K}_{\max }/(Q{K}_0)$. Substitution into the Monod equation gives the stated system withFor a positive equilibrium, the first equation requires $\alpha c/(1+c)=1$. Hence $c_{\ast }=1/(\alpha -1)$ and $n_{\ast }=\alpha (\beta -c_{\ast })$, both positive exactly under the specified inequalities.

Writing $A=\alpha n_{\ast }/(1+c_{\ast }{)}^2>0$, the Jacobian matrix at this equilibrium isBoth eigenvalues are negative, so the state is locally asymptotically stable. The Monod chemostat equilibrium and relaxation also makes one decay rate transparent: $z=c+n/\alpha$ satisfies $z^{\prime }=\beta -z$, independently of the uptake kinetics.

Introduce the vector $x=(t,y,y^{\prime },\dots ,y^{(k-1)})\in {\mathbb{R}}^{k+1}$. Its autonomous ordinary differential equation iswhere the coordinate indices start at zero. Appending the clock removes the explicit time dependence.

For a vector field with local existence and uniqueness, its flow ${\varphi }_t(x)$ is the solution at elapsed time $t$ starting at $x$. The uniqueness theorem for ordinary differential equations gives ${\varphi }_s({\varphi }_t(x))={\varphi }_{s+t}(x)$ whenever both sides are defined. The orbit is $O(x)=\{{\varphi }_t(x):t\text{ lies in its maximal interval}\}$. For a forward-complete solution its omega-limit set isequivalently the set of limits along sequences $t_n\to \infty$. A homoclinic orbit is a nonconstant complete orbit approaching the same equilibrium as $t\to -\infty$ and $t\to \infty$. This last definition concerns a general autonomous system; the appended clock itself cannot approach an equilibrium.

Continuation around one positively oriented loop induces an invertible linear map $M$ on the two-dimensional solution space. Its inverse is continuation around the reversed loop. Over $\mathbb{C}$, choose an eigenvector with eigenvalue $\lambda \ne 0$, and let $w$ be the corresponding nonzero solution. After continuation it becomes $\lambda w$.

Choose $\sigma$ with $e^{2\pi i\sigma }=\lambda$. The product $h(z)=z^{-\sigma }w(z)$ has trivial monodromy, so it is single-valued and holomorphic on the punctured disc. Its Laurent series, convergent on compact subannuli, gives the Monodromy eigenfunction Laurent representationNo assumption of a regular singular point has been made, so the negative part need not terminate.

For variations $q_i+\epsilon {\eta }_i$ with ${\eta }_i(t_1)={\eta }_i(t_2)=0$, differentiation of the action and integration by parts giveThe fundamental lemma of the calculus of variations therefore yields the Euler-Lagrange equations $d{L}_{{\dot{q}}_i}/dt=L_{q_i}$. An ignorable coordinate has $L_{q_j}=0$, so its conjugate momentum $p_j=L_{{\dot{q}}_j}$ is constant.

For the sphere, $\phi$ is ignorable andThe Hamiltonian is the mechanical energy. Along solutions, $\dot{H}=-\partial L/\partial t=0$, because the Lagrangian has no explicit time dependence.

In a spatially flat FLRW metric, a radial null geodesic satisfies $d\chi /dt=\pm c/a(t)$. For a source and observer at fixed comoving separation, $\chi ={\int }_{t_e}^{t_0}cdt/a(t)$. Applying this to successive wave crests gives $d{t}_0/a(t_0)=d{t}_e/a(t_e)$ and therefore the cosmological redshift $1+z=a(t_0)/a(t_e)$.

Each photon's energy is reduced by $1+z$, and the arrival interval is increased by $1+z$. The received power crossing the observation sphere is consequently $L/(1+z{)}^2$. Its physical area is $4\pi a(t_0{)}^2|x{|}^2$, so the radiative flux isThis is the luminosity distance relation with $d_L=(1+z)a(t_0)|x|$. The Euclidean area formula presumes spatial flatness; in a curved FLRW metric the transverse comoving distance replaces $|x|$.

For binary linear codes of length $n$, the bar product of binary linear codes is $C_1|C_2=\{(u,u+v):u\in C_1,v\in C_2\}$. The parametrization is injective and linear, so its dimension is $k_1+k_2$. If $v=0$, a nonzero word has Hamming weight at least $2d_1$; if $v\ne 0$, $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)\ge d_2$. Taking $(u,u)$ and $(0,v)$ of minimum weight showsFor $a\in C_2^{\perp },b\in C_1^{\perp }$, the inner product of $(u,u+v)$ and $(a,a+b)$ is $u\cdot b+v\cdot a+v\cdot b=0$, since $C_2\subseteq C_1$. The spaces have complementary dimensions, proving $(C_1|C_2{)}^{\perp }=C_2^{\perp }|C_1^{\perp }$.

Define the Reed-Muller code $\mathrm{RM}(d,r)$ by evaluating all multilinear polynomials of total degree at most $r$ at the $2^d$ points of ${\mathbb{F}}_2^d$. The squarefree monomials are independent functions, giving dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{d}{j}\right)$. Splitting according to the last variable gives the Reed-Muller bar-product recursion $\mathrm{RM}(d,r)=\mathrm{RM}(d-1,r)|\mathrm{RM}(d-1,r-1)$, with the endpoint codes interpreted in the usual way. The distance recursion gives $2^{d-r}$.

To identify the Dual of a Reed-Muller code, multiply a monomial of degree at most $r$ by one of degree at most $d-r-1$. The product omits some variable, so its sum over ${\mathbb{F}}_2^d$ is even and its binary inner product is zero. The binomial dimension identity then gives

Using the diameter normalization, define ${\mathcal{H}}_{\delta }^d(E)=\inf \{{\sum }_j(\mathrm{diam}{U}_j{)}^d:E\subseteq {\bigcup }_j{U}_j,\mathrm{diam}{U}_j\le \delta \}$ and the Hausdorff measure ${\mathcal{H}}^d(E)={\lim }_{\delta \downarrow 0}{\mathcal{H}}_{\delta }^d(E)$. The Hausdorff dimension is $\inf \{d:{\mathcal{H}}^d(E)=0\}$, equivalently $\sup \{d:{\mathcal{H}}^d(E)=\infty \}$.

The Cantor set is the intersection of the sets left by successively removing open middle thirds from $[0,1]$. At level $k$ it has $2^k$ Cantor cylinders of diameter $3^{-k}$. For $s=\log 2/\log 3$, their total $s$-cost is $2^k{3}^{-ks}=1$, so ${\mathcal{H}}^s(C)\le 1$.

The random series $\xi ={\sum }_{n\ge 1}{X}_n{3}^{-n}$ converges absolutely, and its ternary digits are all zero or two. Thus $\xi \in C$ and its law is the Cantor Bernoulli measure. Each level-$k$ cylinder has probability $2^{-k}$. Distinct such intervals have separation at least $3^{-k}$; a set $U$ of smaller diameter meets at most one. If $3^{-(k+1)}\le \mathrm{diam}U<3^{-k}$, thenSets of diameter zero have probability zero, since the measure has no measure atoms; diameters at least one give the bound trivially. For arbitrary nonmeasurable sets use outer probability. Any countable cover of $C$ therefore satisfies $1\le {\sum }_j{\mathbb{P}}^{\ast }(\xi \in U_j)\le 2{\sum }_j(\mathrm{diam}{U}_j{)}^s$. HenceThe last implication follows by multiplying the $s$-costs by powers of the cover diameter: measures above $s$ vanish and those below $s$ are infinite.

The first command fits independent Poisson random variables with means ${\mu }_j$ and a log link. For concentration $x$ and strain indicator $s$, its fitted linear predictor isThe interaction allows different concentration slopes in the two strains. At $x=0$ the second strain's mean is multiplied by $e^{0.33667}$; its slope is $-1.47253-0.12534$. These are multiplicative changes in counts, not changes in probabilities.

The maximum-likelihood estimates use the Poisson regression likelihood. With design matrix $X$, estimated information $X^T\mathrm{diag}({\hat{\mu }}_j)X$ gives the inverse covariance matrix; diagonal square roots give the standard errors. The printed Wald tests use approximately standard-normal coefficient-to-error ratios. Fuel and strain effects are strong, whereas the interaction has $p=0.182$, suggesting a common slope.