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

Use the reduction algorithm for a positive definite binary quadratic form. A determinant-one shear $(x,y)\mapsto (x+ky,y)$ puts the middle coefficient in $[-a,a]$. If the resulting last coefficient is smaller than $a$, the determinant-one substitution $(x,y)\mapsto (-y,x)$ decreases the positive integer leading coefficient. Repeating terminates with a reduced positive definite binary quadratic form satisfying $|b|\le a\le c$. These substitutions preserve proper equivalence of binary quadratic forms and the discriminant of a binary quadratic form.

The enumeration of reduced binary quadratic forms givesSince $b^2\equiv -163\equiv 1(\mathrm{mod}4)$, $b$ is odd. For $|b|=1,3,5,7$, the possible values of $(b^2+163)/4$ are respectively $41,43,47,53$. Each is a prime number greater than seven. But $ac=(b^2+163)/4$, so its positive divisor $a\le 7$ must be one. Then $|b|\le a$ forces $b=\pm 1$ and $c=41$. The two signs are properly equivalent: substituting $x\mapsto x-y$ in $x^2+xy+41y^2$ gives $x^2-xy+41y^2$. Thus every form in question is properly equivalent to

The closed-set version of the Baire category theorem says that if a nonempty complete metric space $X$ is a countable union $X={\bigcup }_{n=1}^{\infty }{F}_n$ of closed sets, then at least one $F_n$ has nonempty interior. Equivalently, a nonempty complete metric space cannot be a countable union of closed nowhere dense sets.

For each integer $n\ge 0$, put $Z_n=\{z:f^{(n)}(z)=0\}$. Every derivative $f^{(n)}$ is an entire function and cannot be identically zero: otherwise repeated integration would make $f$ a polynomial. By the identity theorem for holomorphic functions, its zero set has empty interior, and continuity makes $Z_n$ a closed set. Thus $Z_n$ is nowhere dense.

The complex plane with its usual metric is a complete metric space, so the Baire category theorem gives $z_0\notin {\bigcup }_{n\ge 0}{Z}_n$. The Taylor series there has coefficients

Each nonidentity element of the special orthogonal group $\mathrm{SO}(3)$ is a rotation fixing exactly the two unit vectors along its axis. Since $G$ is a finite group, $\Omega$ is finite. If $v\in \Omega$ is fixed by $g\ne 1$ and $h\in G$, then $hv$ is fixed by $hg{h}^{-1}\ne 1$. Hence $G$ acts on $\Omega$ by a group action.

Let $N=|G|>1$, let $r$ be the number of orbits of a group action, and choose representatives with stabilizer subgroups of orders $n_1,\dots ,n_r$, each at least two. Count pairs $(g,v)$ with $g\ne 1$ and $gv=v$. Counting by $g$ gives $2(N-1)$. Counting by group orbits and using the orbit-stabilizer theorem givesEvery summand is at least $1/2$, so $r<4$: there are at most three orbits. For the trivial group, $\Omega$ is empty and the assertion also holds.

For the rotation group of a regular dodecahedron, $N=60$. The three group orbits are the unit vectors towards the 12 face centres, 20 vertices and 30 edge midpoints, whose stabilizer subgroup orders are respectively $5,3,2$. Rotations about these axes exhaust the nonidentity rotations. Consequently the orbit sizes are

Use binary search: maintain the interval of possible integers and ask whether $n$ is at least the first integer in its upper half. Each answer reduces the number of possibilities to at most its previous number divided by two, rounded up. After $q$ questions at most $\lceil 10^6/2^q\rceil$ possibilities remain. Since $2^{20}=1048576>10^6$, twenty questions suffice.

A yes/no decision tree of depth twenty has at most $2^{20}$ leaves, whereas the possible finishing orders number $15!=1307674368000$. Thus twenty questions cannot identify the finishing order of fifteen horses, assuming no ties. With unrestricted yes/no questions, the exact minimum for $n$ horses is $\lceil {\log }_2(n!)\rceil$: the leaf count is a lower bound, and repeatedly partitioning the remaining permutations into two nearly equal sets attains it. In particular fifteen horses require 41 questions.

By Stirling's formula,so the leading number of questions is $n{\log }_{2}n$. These questions may ask about whole sets of possible orders; restricting them to pairwise comparisons is a different model.

Write $u(y,\theta )={\partial }_{\theta }\log f(y,\theta )$ for the single-observation score function. Differentiating the normalization of the probability density function givesFor discrete observations, use a sum instead. The allowed interchange of differentiation and integration is the usual regular-model assumption with common support. Adding these identities gives ${\mathbb{E}}_{\theta }{U}_n=0$.

Let $p_{\theta }$ be the joint density. Because $T$ is an unbiased estimator with no explicit dependence on the parameter, differentiating ${\mathbb{E}}_{\theta }T=\theta$ givesThe scores are independent random variables with mean zero, so variance additivity for independent random variables gives ${\mathrm{Var}}_{\theta }(U_n)=n{\mathrm{Var}}_{\theta }(U_1)$. The Cauchy-Schwarz inequality applied to the centred estimator and the score now gives the Cramér-Rao lower bound:The denominator is the sample Fisher information. This bound concerns regular models with positive finite information; the preceding covariance identity explains why a small estimator variance requires a sufficiently informative score.

The equation is a conservation law $n_t+J_x=0$ with diffusive flux $J=-D(n_0/n)n_x$. For positive density, insects move down the density gradient, with effective diffusion coefficient $D{n}_0/n$: dispersal is stronger in low-density regions. This is logarithmic diffusion, since the equation is $n_t=D{n}_0(\log n{)}_{xx}$.

Put $\tau =Dt$ and $\xi =x/{\tau }^{\beta }$. A self-similar solution $n=n_0{\tau }^{-\beta }g(\xi )$ conserves total number when ${\int }_{\mathbb{R}}g=1$. Its width shrinks to zero as $t\downarrow 0$; for an integrable nonnegative $g$, changing variables in the integral against a bounded continuous function proves convergence to $n_0$ times the Dirac delta distribution at the origin.

Substitution givesMatching powers for a nonstationary profile forces $\beta =1$. The profile equation integrates to $g^{\prime }/g=-\xi g+C$. For a centred even profile, $C=0$, and integration of $g^{\prime }=-\xi g^2$ gives $g=2/({\xi }^2+a^2)$. Normalization requires $2\pi /a=1$, henceThis is $n_0$ times a Cauchy distribution density with scale $2\pi Dt$. It is positive, has total mass $n_0$, and directly satisfies the nonlinear diffusion equation for $t>0$.

The fixed points are $(0,0)$ and $(\pm |\mu |,{\mu }^2)$. The Jacobian matrix isAt the origin its eigenvalues are ${\mu }^2$ and $-1$, so it is a saddle equilibrium for every allowed $\mu$. At either nonzero fixed point the characteristic polynomial is ${\lambda }^2+\lambda +2{\mu }^2$, givingThus both are stable nodes for $0<|\mu |<1/(2\sqrt{2})$ and stable focuses for $|\mu |>1/(2\sqrt{2})$. At equality the repeated eigenvalue is $-1/2$ and the matrix is not scalar, so there is only one independent eigenvector: the fixed point is a stable improper node.

The stable manifold of the origin is $x=0$, exactly: there $\dot{y}=-y$. Conversely, a trajectory converging to the origin with $x\ne 0$ would eventually have $\dot{x}/x={\mu }^2-y>{\mu }^2/2$, which precludes convergence of $x$ to zero.

For the local unstable manifold, write $y=h(x)=a{x}^2+b{x}^4+O(x^6)$. Reflection symmetry makes $h$ even, and the invariance equation for a graph requiresComparing quadratic and quartic terms gives $2a{\mu }^2=1-a$ and $4b{\mu }^2-2a^2=-b$. Therefore

At $x=0$, both denominators are nonzero because $a\notin 2\pi \mathbb{Z}$; they remain nonzero for every real $x\ge 0$. The integrand is therefore bounded on each finite interval. At infinity its terms decay respectively as $O(e^{-(1+b)x})$ and $O(e^{-(1-b)x})$, so $0<b<1$ gives absolute convergence.

Set $t=e^{-x}$. The two integrals becomeBy the Euler integral for the hypergeometric function and the Gamma function recurrence, ${\int }_0^1{t}^{s-1}/(1-zt)dt={}_2{F}_1(1,s;s+1;z)/s$ for $s>0$ and the indicated unit-circle values $z\ne 1$. HenceThe Gauss hypergeometric functions here use their continuation from the Euler integral, so no pole crosses the integration interval.

The canonical momentum is $p_i=\partial L/\partial {\dot{x}}_i=m{\dot{x}}_i+q{A}_i$. Its time derivative contains the total derivative along the trajectory: ${\dot{p}}_i=m{\ddot{x}}_i+q{\partial }_t{A}_i+q{\dot{x}}_j{\partial }_j{A}_i$. The Euler-Lagrange equation therefore givesThe magnetic field is $\mathbf{B}=\nabla \times \mathbf{A}$, so the last term is $(\dot{\mathbf{x}}\times \mathbf{B}{)}_i$. With the electric field $\mathbf{E}=-\nabla \varphi -{\partial }_t\mathbf{A}$, this is precisely the Lorentz force law:

The specified vector potential gives $\mathbf{B}=(0,0,B)$. Put $\omega =qB/m$, retaining its sign. The Lorentz force law yields $\ddot{x}=\omega \dot{y}$, $\ddot{y}=-\omega \dot{x}$ and $\ddot{z}=0$. For initial velocities $(u,v,w)$ and $\omega \ne 0$, integration givesThe transverse motion is a circle centred at $(x_0+v/\omega ,y_0-u/\omega )$ with radius $\sqrt{u^2+v^2}/|\omega |$. Thus the full orbit is a helix around a line parallel to the magnetic field, with period $2\pi /|\omega |$ and signed axial advance $2\pi w/|\omega |$ per turn. The charge sign determines the sense of rotation. If $w=0$ it is a circle, if $u=v=0$ it is a straight line parallel to the field, and if $qB=0$ all motion is uniform rectilinear motion.

For neighbouring comoving observers separated by a small physical distance $d\ell$, the recession velocity is $H(t)d\ell$, where $H=\dot{a}/a$ is the Hubble parameter. During the photon's travel time $dt=d\ell /c$, the local Doppler effect gives $d\lambda /\lambda =Hdt$. Integrating along the ray gives the cosmological wavelength-redshift relation:The same ratio stretches the arrival interval of successive wave crests and of successive emitted pulses: $d{t}_0=(1+z)d{t}_e$. Each photon loses a factor $1+z$ in energy because $E=hc/\lambda$. Thus energy arriving through the sphere per unit observer time has one factor from cosmological redshift and one from time dilation:This is the total power crossing the sphere; division by its area would give the observed flux.

Identify the Möbius group with ${\mathrm{PSL}}_2(\mathbb{C})$, the orientation-preserving isometry group of three-dimensional hyperbolic space. Here a properly discontinuous group action permits finite stabilizers: for each compact set $K$, only finitely many $g$ satisfy $gK\cap K\ne \varnothing$.

Fix $o\in {\mathbb{H}}^3$. The set of isometries with $d(o,go)\le R$ is compact. To see this, an orientation-preserving isometry is uniquely determined by the image of an oriented orthonormal frame at $o$. The image point lies in a compact closed hyperbolic ball and its frame lies in a compact rotation-group fiber. These choices parametrize the indicated set of isometries continuously.

A discrete subgroup of a topological group is closed: otherwise distinct subgroup elements accumulating at the same point would have quotients tending to the identity, contradicting isolation of the identity. Its intersection with a compact set is therefore finite. If $K\subseteq B(o,R)$ and $gK\cap K\ne \varnothing$, choosing $x,gx\in K$ gives $d(o,go)\le d(o,gx)+d(gx,go)\le 2R$. Hence discreteness implies a properly discontinuous group action. Conversely, if the subgroup is not discrete, distinct $g_n$ tend to the identity. For a compact ball $K$ with $o$ in its interior, eventually $g_{n}o\in K$, so infinitely many $g_{n}K$ meet $K$, contradicting proper discontinuity. This proves the equivalence.

Matrices of determinant one over the Gaussian integers are closed under multiplication and inversion, with inverse $\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$. Quotienting by $\{\pm I\}$ gives the specified group of Möbius transformations. The Gaussian integers form a discrete set in the complex plane, so these matrices form a discrete subgroup of ${\mathrm{SL}}_2(\mathbb{C})$, and the finite quotient remains discrete. Thus this group acts properly discontinuously on ${\mathbb{H}}^3$.

Explicit representatives of all four types areThe first is $z\mapsto -1/z$ and has order two; the second is the nonidentity translation $z\mapsto z+1$. The third has positive real reciprocal eigenvalues $(3\pm \sqrt{5})/2$, giving translation along an axis without rotation. For the last, a nonreal trace excludes both unit-modulus and real eigenvalues. Its multiplier therefore has modulus different from one and a nonzero rotation angle: it is a loxodromic Möbius transformation.

Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes $p,q\equiv 3(\mathrm{mod}4)$, keep them secret, and publish $N=pq$. A message block $m\in \{0,\dots ,N-1\}$ is encrypted asUsually require $\gcd (m,N)=1$; otherwise the message itself reveals a factor. For a quadratic residue $c$ modulo $p$, Euler criterion gives $c^{(p-1)/2}=1$, so $c^{(p+1)/4}$ is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo $N$. Message redundancy identifies the intended root; squaring alone does not identify it uniquely.

To reduce integer factorization to recovery of square roots, choose $x$ uniformly from $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$, compute $c=x^2$, and ask the alleged decoder for any root $y$ of $c$. Conditional on $c$, the secret $x$ is uniform among its four roots, even if the decoder deterministically chooses $y$. With probability $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$. Then the signs agree modulo one prime and disagree modulo the other. Sincethe greatest common divisor factors $N$. Independent trials require an expected two successful oracle calls. If a trial's chosen $x$ is not a unit, $\gcd (x,N)$ already factors $N$. This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.

For coin flipping by telephone, Alice publishes $N$ with its factorization secret. Bob chooses uniformly a unit $x$ with $0<x<N/2$ and sends $c=x^2\mathrm{mod}N$. Alice computes the two roots $r_1,r_2$ in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's $x$. Bob reveals $x$; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals $p,q$, so Bob verifies the primes, product, and differing digit.