Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1

The linear Diophantine equation solvability criterion says that $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. The Euclidean algorithm givesThus $\gcd (1007,2314)=1$, which divides $37$. Therefore

Applying the Euclidean algorithm,Hence $\gcd (2508,3211)=19$. Since $19$ does not divide $55$, the linear Diophantine equation solvability criterion gives

The quadratic form factors as a sum of two squares:The change of variableshas determinant $-1$, so its matrix is a unimodular matrix and it maps ${\mathbb{Z}}^2$ bijectively to itself. The original equation is therefore equivalent toThe sum of two squares theorem also decides this systematically: $365=5\cdot 73$, and every prime factor congruent to $3$ modulo $4$ occurs to an even power, vacuously here. Thus $365$ is a sum of two integer squares. Explicitly,Inverting the change of variables gives, for example, $(x,y)=(32,-15)$. ConsequentlyThis is the unimodular reduction of a discriminant-minus-four form to two squares.

The Liouville approximation theorem states that if $\alpha$ is an irrational algebraic number of degree $d\ge 2$, then there is a constant $c(\alpha )>0$ such that every reduced rational $p/q$ satisfies

Let $P\in \mathbb{Z}[X]$ be the minimal polynomial of $\alpha$, of degree $d$. Since $P$ is irreducible of degree greater than one, $P(p/q)\ne 0$. Moreover,and henceOn the compact interval $I=[\alpha -1,\alpha +1]$, putIf $p/q\in I$, the mean value theorem gives a point $\xi$ between $\alpha$ and $p/q$ such thatThus $|\alpha -p/q|\ge M^{-1}{q}^{-d}$. If $p/q\notin I$, then $|\alpha -p/q|>1\ge q^{-d}$. Taking anyproves the stated strict inequality.

Because both fractions are reduced and $q>v$, they are distinct. Their difference isThe numerator is a nonzero integer, so its absolute value is at least one. Thereforewhere the strict inequality uses $v<q$. This is the separation of distinct reduced fractions.

Since the positive series converges, $a_n\to 0$. We construct the subsequence recursively. Choose $n(1)$ arbitrarily. Once $n(1)<\cdots <n(k-1)$ have been chosen, write the reduced partial sums asChoose $n(k)>n(k-1)$ so far out thatThis is possible because $a_n\to 0$.

LetFor every fixed $j$, each later choice includes $q_j^{-j}$ in its minimum, so

First, $\alpha$ is irrational. If $\alpha =u/v$ were reduced and rational, the strictly increasing rational sequence $s_j\to \alpha$ would have unbounded denominators $q_j$; only finitely many reduced fractions in a bounded interval have bounded denominator. Choose $j>2$ with $q_j>v$. Part (b) would givecontrary to $|\alpha -s_j|<2^{-j}{q}_j^{-j}<q_j^{-2}$.

If $\alpha$ were algebraic of degree $d$, part (a) would give a constant $c>0$ withFor $j>d$ our construction instead giveswhich contradicts the lower bound once $2^{-j}<c$. Hence $\alpha$ is transcendental. This proves the transcendental subseries of a positive rational convergent series construction.

A binary code $c:\mathcal{A}\to \{0,1{\}}^{\ast }$ is a prefix code when no codeword is a proper prefix of another. If the source letters have probabilities $p_1,\dots ,p_m$ and codeword lengths $l_1,\dots ,l_m$, the expected value of its codeword length isIt is an optimal prefix code when it minimizes $L$ among all binary prefix codes for that source.

Suppose $p_i>p_j$ but $l_i>l_j$. Exchanging the codewords assigned to ${\mu }_i$ and ${\mu }_j$ leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length iscontradicting optimality. Thuswhich is the probability monotonicity of optimal prefix-code lengths.

Represent the code by its binary prefix tree and choose a codeword $wb$ of maximal length, where $b\in \{0,1\}$. Its sibling is $w(1-b)$. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than $wb$. Replacing $wb$ by $w$ would then preserve prefix-freeness and strictly reduce $L$. This is impossible for an optimal code, so $w(1-b)$ is also a maximal-length codeword. The pair differs only in its last digit, proving the deepest sibling property of an optimal prefix code.

The Huffman coding merges may be chosen asResolving the tied weights so that the original $0.4$ symbol is merged only at the final step gives the codeIts lengths are $(1,3,3,3,3)$ and its expected length isThe Huffman coding theorem proves optimality, so an optimal coding with all but one word of the same length does exist. This is an instance of a nonunique optimal prefix code: a different resolution of the ties also gives the optimal profile $(2,2,2,3,3)$.

An optimal code cannot have five distinct lengths. By the deepest sibling property of an optimal prefix code, at least two maximal-length codewords have the same length. Thus the answers are respectively

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. The conventional exceptional production $S\to ϵ$ may be allowed when the language contains the empty word, with $S$ excluded from right-hand sides.

The length isIndeed, the parse tree has $n$ terminal-production nodes and, as a full binary tree with $n$ leaves, $n-1$ binary-production nodes. This is the Chomsky-normal-form derivation length.

One parse tree can be recorded unambiguously by the nested expressionEvery internal node uses one of the given productions, and the leaves read from left to right areEquivalently, the corresponding leftmost grammar derivation isHence the required word is generated by the grammar.

TakewhereThis grammar is in Weak Chomsky normal form. In the original grammar, $C$ occurs only in $S\to AC$ and has the sole production $C\to BA$. Thus every use ofis replaced in $G^{\prime }$ by $S\to ABA$, while every later production is unchanged. Conversely, the ternary production can always be expanded into those two original steps. Therefore $G^{\prime }$ is equivalent to $G$ in the sense of an equivalent grammar.

The compressed initial production gives the leftmost derivationIt has $12$ steps, whereas part (b) gives $2\cdot 7-1=13$ for every derivation in Chomsky normal form. The Weak Chomsky normal form ternary rule has compressed exactly one pair of binary productions, so the derivation is strictly shorter as required.

For $X=x$, the last flip must be the $r$th head. Among the preceding $x+r-1$ flips, exactly $x$ are tails and $r-1$ are heads. There are $\left(\genfrac{}{}{0ex}{}{x+r-1}{x}\right)$ choices for their positions, and every resulting sequence has probability $(1-p{)}^x{p}^r$. The negative binomial stopping argument therefore givesso $X$ has the failures-before-the-$r$th-success negative binomial distribution.

To put the mass function into exponential family form, setSince $p=1-e^{\theta }$,whereThus the natural parameter of an exponential family is $\theta$, and the Fisher-Neyman factorization theorem shows that $T(X)=X$ is a sufficient statistic. This is the negative binomial exponential family.

The exponential-family derivative identities now giveand

With population $n$, the transition diagram has the two outgoing arrowsThus this is a batch-birth linear-death process. If $P_n(t)=\mathbb{P}(N_t=n)$ and $P_j=0$ for $j<0$, probability enters state $n$ from $n-3$ by a birth and from $n+1$ by a death. Hence the master equation is

The Markov jump-process generator isFor $f(n)=n$, this gives $Ln=3\lambda -\beta n$. Therefore the expected value $m(t)=\mathbb{E}[N_t]$ satisfiesso

For $f(n)=n^2$,Writing $s=\mathbb{E}[N_t^2]$ and using the generator identity givesThe variance $v=s-m^2$ consequently obeysIf $v(0)=v_0<\infty$, substitution of the formula for $m$ yieldsAll transient terms vanish, and the moments of a batch-birth linear-death process therefore give

Taking reciprocals in the finite product defining the gamma function givesLet $H_n={\sum }_{k=1}^n{k}^{-1}$. Sinceand $H_n-\log n\to \gamma$, where $\gamma$ is the Euler--Mascheroni constant, passage to the limit gives the Weierstrass product for the reciprocal gamma function

The logarithmic derivative of this identity isSince $k^{-1}-(z+k{)}^{-1}=z/[k(z+k)]$, the digamma function therefore satisfies

For real $z>0$, termwise differentiation gives the trigamma functionThus $\psi$ is strictly increasing on the positive real axis. At the two positive integers needed here, telescoping givesThe intermediate value theorem supplies a zero in $(1,2)$, and strict increase makes it unique. This is the positive zero of the digamma function.

Under the stated gauge transformation, the charged-particle electromagnetic Lagrangian becomesThusThe action changes only by $q[f(t_2)-f(t_1)]$, whose variation vanishes for fixed endpoints. By total-time-derivative invariance of a Lagrangian, the Euler-Lagrange equation is unchanged.

In Cartesian components,andThe Euler-Lagrange equation therefore givesUsingand $[\dot{r}\times B{]}_i={\dot{r}}_j({\partial }_i{A}_j-{\partial }_j{A}_i)$, this becomes the Lorentz force

Let $\hat{b}=B/|B|$. For a constant uniform magnetic field, choose the symmetric gaugewhich has $\nabla \times A=B$ and $A\cdot \hat{b}=0$. With $E=0$, one may take $\varphi =0$. The coordinate $r_{\parallel }=r\cdot \hat{b}$ is then absent from the Lagrangian, so it is an ignorable coordinate. Its generalized momentumis conserved. Hencewhich is the canonical momentum parallel to a uniform magnetic field in this gauge.

For a comoving region, $E=\rho V$ and $V=a^3{V}_0$. The work law givesso differentiation with respect to time yieldsSince $\dot{V}/V=3\dot{a}/a$, division by $V$ gives the cosmological perfect-fluid continuity equation

Put $K=8\pi G/(3c^2)$. Differentiating $Q=K\rho a^2-{\dot{a}}^2$ givesThe continuity equation and the Friedmann acceleration equation implyandThese terms cancel, soThis is the First integral of the Friedmann acceleration equation.

For the barotropic equation of state $P=w\rho$, the continuity equation separates asSince $a(t_0)=1$,which is the constant-equation-of-state density scaling.

When $Q=0$, the expanding branch satisfieswhere $H_0=\dot{a}(t_0)>0$. Because $w>-1$, integration givesand hence the flat constant-equation-of-state scale factorIt vanishes atas $|w|<1$ ensures $1+w>0$.