Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3

An arithmetic function $f$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime integers. If $g(n)={\sum }_{d\mid n}f(d)$ and $(m,n)=1$, every positive integer divisor of $mn$ is uniquely $d_1{d}_2$ with $d_1\mid m$ and $d_2\mid n$. Henceso $g$ is multiplicative.

The Möbius function is defined by $\mu (1)=1$, $\mu (n)=0$ if the square of a prime number divides $n$, and $\mu (n)=(-1{)}^r$ if $n$ is a product of $r$ distinct prime numbers. Coprime integers have disjoint sets of prime factors, so this definition immediately gives $\mu (mn)=\mu (m)\mu (n)$ when $(m,n)=1$.

For $n=p_1^{a_1}\cdots p_r^{a_r}>1$, only the square-free divisors contribute, and thereforeFor $n=1$ the sum is $1$. Thus $1\ast \mu =\epsilon$ in the language of Dirichlet convolution. Convolving $g=1\ast f$ with $\mu$ gives the Möbius inversion formula

If $f(n)=n$, its divisor sum is the sum-of-divisors function. Conversely, if $g(n)=n$, Möbius inversion givesusing the standard divisor identity for the Euler totient function. Therefore the two requested answers are

One form of the Baire category theorem says that a nonempty complete metric space cannot be a countable union of closed nowhere dense sets.

For each nonnegative integer $n$, putBecause $f$ is an entire function, every derivative $f^{(n)}$ is continuous and $Z_n$ is closed. No $f^{(n)}$ is identically zero: if $f^{(n)}\equiv 0$ for some $n$, repeated integration shows that $f$ is a polynomial. By the identity theorem, the zero set of the nonzero holomorphic function $f^{(n)}$ has empty interior. Thus each $Z_n$ is nowhere dense.

The complex plane is complete, so the Baire category theorem givesChoose $z_0$ outside this union. Then $f^{(n)}(z_0)\ne 0$ for every $n$, and hence every coefficient $f^{(n)}(z_0)/n!$ in the Taylor series about $z_0$ is nonzero. Such a point $z_0$ therefore exists.

The relation $g(X)h(X)=X^7-1$ makes this a length-seven binary cyclic code. Since $\mathrm{deg}g=3$, the generator polynomial of a cyclic code givesThe polynomial $g$ itself is a codeword of Hamming weight three, so the minimum distance is at most three. A nonzero word of weight one cannot vanish at the nonzero element $\alpha$. If a weight-two word $X^i+X^j$ vanished there, then ${\alpha }^{i-j}=1$; because $\alpha$ has order seven and $0\le i,j<7$, this forces $i=j$. Hence there are no nonzero words of weight below three, and

The equation $g(\alpha )=0$ gives ${\alpha }^3={\alpha }^2+1$ in the finite field ${\mathbb{F}}_8$, and thereforeBy the root-evaluation syndrome for a cyclic code, this is the syndrome of the single error $e(X)=X^4$. Since $d(C)=3$, minimum-distance decoding uniquely corrects one error. Subtracting and adding agree over ${\mathbb{F}}_2$, so the decoded codeword is

A context-free grammar is in Chomsky normal form when every production rule has one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. If the language contains the empty word, one may additionally permit $S_0\to ϵ$, with the start symbol $S_0$ absent from all right-hand sides.

The standard conversion of a context-free grammar to Chomsky normal form proceeds as follows:

Add a fresh start symbol $S_0$ with $S_0\to S$.
Find the nullable nonterminals, add the variants obtained by omitting nullable occurrences, and remove all epsilon productions. Omit $S_0\to ϵ$ as well because the requested language excludes $ϵ$.
Remove every unit production $A\to B$ by copying the non-unit productions reachable from $B$ to $A$.
Remove nonterminals that are unreachable from $S_0$ or cannot derive a terminal word.
In every right-hand side of length at least two, replace a terminal $a$ by a fresh nonterminal $T_a$ with $T_a\to a$.
Replace each right-hand side of length greater than two by a chain of binary productions using fresh nonterminals.

Each remaining production is of the required binary or terminal form, and these transformations preserve every nonempty generated word. Thus $\mathcal{L}(G_{\mathrm{Chom}})=\mathcal{L}(G)\setminus \{ϵ\}$.

The original grammar generatesbecause each use of $S\to ASc$ adds one $a$ on the left and one $c$ on the right, and $S\to B\to b$ terminates the derivation.

Introduce nonterminals $S_0,X,C$ and useEvery production is in Chomsky normal form. The production $X\to SC$ completes one matched $a,c$ pair, while either start-like symbol terminates with $b$, so the grammar generates exactly the same language. These productions are a valid $G_{\mathrm{Chom}}$.

Treat the cell counts as independent Poisson random variables. Under independence of Month and Hospital, the independence log-linear model for a two-way contingency table iswith no Month–Hospital interaction. Compare its Poisson deviance with the appropriate upper quantile of a chi-squared distribution. This is the likelihood-ratio test of independence in a contingency table.

The approximation assumes independent counts with correctly specified Poisson means, identifiable parameters, and sufficiently large fitted cell means for the asymptotic chi-squared law to be accurate. Equivalently, one may condition on the margins and use the corresponding multinomial sampling formulation.

For the $12\times 3$ month table there are $36$ cells and $1+11+2=14$ independent model parameters, so the residual degrees of freedom areSincemodel 1 does not reject Month–Hospital independence at the $1\%$ level.

After combining months into four quarters, the table is $4\times 3$, givingdegrees of freedom. Nowso model 2 rejects Quarter–Hospital independence at the $1\%$ level.

There is no contradiction. Relabelling twelve months as four quarters aggregates the contingency table, changes the null hypothesis, and reduces the degrees of freedom. The quarter-level hospital pattern is coherent enough to cross the much lower six-degree-of-freedom threshold even though the more detailed month-level omnibus test does not. This is an instance of how aggregation can change a contingency-table independence test.

For a radial function, the equation isTherefore, assuming the population density and radial flux decay at infinity and are regular at the origin,Thus $N$ is conserved; it is the total population obtained by integrating density over the plane. This is the global form of the equation's conservation law.

SetThenwhile the radial diffusion term has the same prefactor and equalsEquating them and multiplying by $x$ givesso the proposed ansatz is a similarity solution.

Regularity at $x=0$ makes the constant of integration zero. Wherever $f>0$,for some $x_0>0$. The nonnegative weak solution continues as $f=0$ once this parabola reaches zero:This is the two-dimensional Barenblatt profile for quadratic porous-medium diffusion; its degenerate diffusivity permits compact support.

Indeed, conservation requiresso $x_0=(16/\pi {)}^{1/4}$ if desired. At time $t$ the populated disk has radius $x_0(NDt{)}^{1/4}$ and hence area

On the slit plane $\mathbb{C}\setminus [-a,a]$, chooseso that $F(z)\sim z$ as $z\to \infty$. This branch cut gives, for $-a<x<a$, the boundary values

Integrate $F$ over the boundary of a large disk with a thin slit removed. The upper bank is traversed from $-a$ to $a$ and the lower bank from $a$ to $-a$, so together they contributeAt infinity the Laurent series isand hence the counterclockwise large-circle integral tends to $-\pi i{a}^2$. By the Cauchy integral theorem, the large-circle and slit-boundary contributions sum to zero. Thereforewhich yields

The kinetic energy of the three unit masses is $\frac{1}{2}{\sum }_i{\dot{x}}_i^2$. Expanding the potential givesThus the small-oscillation mass and stiffness matrices arewhere $J$ is the all-ones matrix.

The vector $(1,1,1{)}^T$ is an eigenvector of the stiffness matrix with eigenvalue $1$. Every vector orthogonal to it has coordinate sum zero and is an eigenvector with eigenvalue $4$. Since $T=I$, the generalized eigenvalue problem for small oscillations gives ${\omega }^2$ equal to these eigenvalues. One orthonormal choice of normal modes isThe last two may be replaced by any orthonormal basis of the sum-zero plane because the frequency is degenerate. Hence the normal frequencies are $\boxed{1,2,2}$.

In the very early universe, assume species $i$ is in thermal equilibrium, is ultrarelativistic so that $kT\gg m_i{c}^2$ and $E(p)\simeq pc$, and has negligible chemical potential, ${\mu }_i\simeq 0$. Its occupation factor is then the Bose-Einstein distribution for a boson or the Fermi-Dirac distribution for a fermion.

Substitute $E=pc$ and set $y=pc/(kT)$. Since $p=(kT/c)y$ and $dp=(kT/c)dy$,

For a bosonic degree of freedom, the supplied integral givesFor a fermionic degree of freedom, useChanging variable $u=2y$ in the second integral givesThis is the energy-density case of the fermion-to-boson thermal integral ratio.

Summing the result of part (a) over all particle species therefore giveswhere the effective number of relativistic energy degrees of freedom is

Apply a Pauli X gate and then a Hadamard gate to the third qubit, and apply Hadamard gates to the first two. This preparesOne application of the Boolean quantum oracle now gives, by quantum phase kickback,The answer qubit is unentangled and may be ignored. If all three qubits must be restored to the displayed register form, applying $H$ and then $X$ to the answer qubit maps $|-⟩$ back to $|0⟩$. Thus the first register is exactly $|f⟩$ after one use of $U_f$.

If $f$ is constant, thenThe sign is a physically irrelevant global phase.

If $f(b_1{b}_2)=b_1\oplus b_2$, thenso

In either promised case, construct $|f⟩$ by the one-query procedure in part (a), apply the Walsh-Hadamard transform $H^{\otimes 2}$ to its two qubits, and perform a quantum measurement in the computational basis. The outcome is certainly $00$ for case (i) and certainly $11$ for case (ii). ThereforeThis is a two-bit instance of Bernstein-Vazirani phase kickback, and also a promised Deutsch-Jozsa test.

Write an integral binary quadratic form as $[a,b,c]=a{x}^2+bxy+c{y}^2$, with discriminant of a binary quadratic form $D=b^2-4ac$. It is positive definite when $a>0$ and $D<0$. Two forms are equivalent if one is obtained from the other by an integral linear change of variables whose matrix lies in ${\mathrm{SL}}_2(\mathbb{Z})$. A positive definite form is reduced whenwith $b\ge 0$ when $|b|=a$ or $a=c$.

To reduce a form, apply a unimodular shear $x\mapsto x+ny$ with $n$ chosen so that the new middle coefficient has $|b^{\prime }|\le a$. If the new final coefficient $c^{\prime }$ is smaller than $a$, exchange the variables, using a determinant-one rotation, so that the positive leading coefficient decreases from $a$ to $c^{\prime }$. Repeating must stop because a positive integer cannot decrease indefinitely. At termination $|b|\le a\le c$, and elementary sign changes impose the boundary convention. This is the reduction algorithm for a positive definite binary quadratic form, and proves that every positive definite form is equivalent to a reduced one.

The displayed forms have discriminant $1-36=-35$, so the intended discriminant is $-35$. For any reduced form of this discriminant, enumeration of reduced binary quadratic forms givesThe boundary convention and direct checking of $a=1,2,3$ leave only

Suppose first that a prime $p>7$ is represented by $f_1$. The identityshows modulo both $5$ and $7$ that $4p$ is a nonzero square. HenceSimilarly,Modulo $5$, this says $2p$ is a square, while modulo $7$ it says $5p$ is a square. Since $(2/5)=(5/7)=-1$, the multiplicativity of the Legendre symbol gives

Conversely, suppose the two displayed Legendre symbols have the same sign. By quadratic reciprocity,Choose an odd integer $B$ satisfying $B^2\equiv -35(\mathrm{mod}p)$. Since $B$ is odd, $B^2+35$ is also divisible by $4$, sois a positive definite integral form of discriminant $-35$ that represents $p$. Reducing $F$ yields either $f_1$ or $f_2$, and equivalence preserves represented integers. The necessary symbol calculation above determines which one: the positive pair selects $f_1$, and the negative pair selects $f_2$. Therefore

The pumping lemma for regular languages states that for every regular language $L$ there is an integer $N$ such that every $w\in L$ with $|w|\ge N$ can be writtenwith

To prove it, let a deterministic finite automaton with $N$ states recognize $L$. During the reading of the first $N$ symbols of an accepted word $w$, the automaton visits $N+1$ states, including the initial state. By the pigeonhole principle, two of them agree, say $q_i=q_j$ with $0\le i<j\le N$. Let $x$ be the first $i$ symbols, $y$ the next $j-i$ symbols, and $z$ the remaining suffix. Reading $y$ is a nonempty closed path from $q_i$ to itself. Traversing this path any number $r\ge 0$ of times and then reading $z$ therefore reaches the same accept state. This proves all three assertions.

Because $D$ is minimal, every state is accessible. Choose a word $u$ taking the initial state to $p$, and let the nonempty word $v$ label the closed path $\gamma$. If a word $w$ took $p$ to an accept state, thenThese words have strictly increasing lengths because $v\ne ϵ$, contradicting the assumption that $\mathcal{L}(D)$ is finite. Hence no accept state is reachable from $p$.

Suppose a path took $p$ to a state $q$. Part (i) implies that no accept state is reachable from either $p$ or $q$. Thus every possible continuation is rejected from both states, so $p$ and $q$ are indistinguishable states of a deterministic finite automaton. Distinct indistinguishable states cannot occur in a minimal deterministic finite automaton. Therefore $q=p$, and there is no path from $p$ to any other state.

Equivalently, a cycle state in a minimal deterministic finite automaton for a finite language is the unique rejecting sink.

Define the Multivariate Fokker-Planck probability current byThenso the Fokker-Planck equation is exactly the continuity equation ${\partial }_{t}P+\nabla \cdot \mathbf{J}=0$.

Integrating the continuity equation over state space and applying the divergence theorem givesAssume the probability density function and its derivatives decay sufficiently rapidly at infinity, or impose a zero-flux boundary condition. The boundary integral then vanishes, so $\int PdV$ is constant. Since it is initially one, the distribution remains normalized for all time.

Assume again that all boundary terms vanish. Multiplying the Fokker-Planck equation by $x_k$ and integrating by parts givesThe diffusion term vanishes after the second integration by parts.

Similarly, ${\partial }_i(x_k{x}_l)={\delta }_{ik}{x}_l+{\delta }_{il}{x}_k$ andBecause $B$ is symmetric,These are the First two moments of a multivariate Fokker-Planck equation.

With $A_i=a_{ij}{x}_j$ and constant $B_{ij}=b_{ij}$, the Fokker-Planck probability current becomesIn the stationary state we impose the stronger zero-current condition $J_i=0$, corresponding to detailed balance.

Forwith symmetric $D$,Substitution into the current from part (d) yieldsIt vanishes for all $\mathbf{x}$ exactly whenThus the stated multivariate normal distribution is a stationary solution whenever the zero-current assumption makes $D$ symmetric positive definite. This is the Stationary Gaussian density for a linear Fokker-Planck equation.

Comparison with the multivariate normal density shows that $D$ is its precision matrix. Since the mean is zero,