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

For an odd prime $p$, the Legendre symbol $(a/p)$ is zero if $p\mid a$, one if $a$ is a nonzero square modulo $p$, and minus one otherwise. By Gauss lemma, $(2/p)=(-1{)}^N$, where $N$ counts those least positive residues of $2,4,\dots ,p-1$ which exceed $p/2$. They correspond to integers $j>p/4$ among $1\le j\le (p-1)/2$, henceFor $p\equiv 1,3,5,7(\mathrm{mod}8)$, its parity is respectively $0,1,1,0$, the same as that of $(p^2-1)/8$. ThereforeUse multiplicativity and quadratic reciprocity for the requested composite numerator. Since $91=7\cdot 13$,The first reciprocity sign is negative because both primes are $3(\mathrm{mod}4)$; the subsequent signs are positive because one prime is $1(\mathrm{mod}4)$. Thus $(91/167)=-1$.

The hyperbolic cosine has the absolutely convergent expansion $\cosh (1/2)={\sum }_{k\ge 0}1/[4^k(2k)!]$. Suppose its value were a rational $a/b$, with $b>0$. For sufficiently large $N$, $b\mid (2N)!$. Multiplying by $4^N(2N)!$ makes the assumed value an integer, and every term of the partial sum through $k=N$ is also an integer. Their difference is the positive remainderLet $q=[4(2N+1)(2N+2){]}^{-1}$. Every new pair of factorial factors is at least $(2N+1)(2N+2)$, so $0<R_N\le {\sum }_{j\ge 1}{q}^j=q/(1-q)<1$ for $N\ge 1$. No integer lies strictly between zero and one. This contradiction proves $\cosh (1/2)$ is irrational. The argument uses a finite integer partial sum and a controlled tail; it does not infer irrationality merely from an infinite expansion.

A discrete subgroup of the Euclidean isometry group has the identity isolated in the group topology. Equivalently, no sequence of distinct group elements converges to the identity; translating neighbourhoods then isolates every element. Such a subgroup is closed, and its intersection with any compact subset is finite: otherwise two elements of a convergent sequence would have quotient tending to the identity.

Write each Euclidean isometry uniquely as $x\mapsto Qx+b$, $Q\in O(2)$. Its linear part gives the group homomorphism $G\to O(2)$, since the linear part of a composite is the product of the linear parts. Its kernel is exactly the translation subgroup $G_T$. The translation vectors form a discrete additive subgroup $L\subset {\mathbb{R}}^2$.

If $L\ne \{0\}$, choose a shortest nonzero vector $a$, possible by discreteness and finiteness in compact balls. On its line, Euclidean division of a scalar coefficient by one proves $L\cap \mathbb{R}a=\mathbb{Z}a$: a nonzero remainder would be shorter than $a$. If all vectors are collinear, this finishes the proof. Otherwise orient the perpendicular coordinate so some vector has positive height. Reduce every vector's component along $a$ modulo $a$ into a bounded interval. Among vectors with positive height at most that of a chosen vector, these reduced representatives lie in a compact rectangle and are finite. Choose $b$ with the smallest such positive height. Subtracting an integer multiple of $b$ from any vector of $L$ reduces its height into $[0,b_{\perp })$; minimality makes the remainder's height zero, so it is an integer multiple of $a$. ThusThis derives the rank-at-most-two translation lattice rather than assuming every discrete subgroup of the plane is a full lattice.

Two examples with $G_T\cong \mathbb{Z}$ are the group generated by $T(x,y)=(x+1,y)$ alone, and the infinite dihedral group generated by $T$ together with $R(x,y)=(-x,y)$. The latter has $RTR=T^{-1}$; its elements are translations $T^k$ and reflections $T^{k}R$, whose mirror lines are $x=k/2$. The first group preserves the orientation of every translated motif; the second also reverses it across these mirrors.

Shannon-Fano coding orders symbols by decreasing probability and recursively splits each consecutive block into two groups with probability totals as close as possible, appending bits zero and one. Huffman coding instead repeatedly merges the two least probable nodes, constructs a binary tree upwards, and then assigns the branch bits. Both yield prefix codes, so a concatenation can be decoded without separators; Huffman coding minimizes expected length among binary prefix codes.

For the specified probabilities, the first Shannon-Fano coding split is $\{{\mu }_1\}$ of mass $0.45$ versus the remaining mass $0.55$. Split the latter into $\{{\mu }_2\}$ of mass $0.25$ and $\{{\mu }_3,{\mu }_4,{\mu }_5\}$ of mass $0.30$, and then split off ${\mu }_3$. One resulting code isIts expected word length is $0.45+2(0.25)+3(0.20)+4(0.05+0.05)=\boxed{1.95\text{ bits}}$.

The Huffman coding merges are $0.05+0.05=0.10$, $0.10+0.20=0.30$, $0.25+0.30=0.55$, and $0.45+0.55=1$. Reading the resulting tree gives the same code lengths $1,2,3,4,4$, and it may give exactly the displayed code if the branch bits are chosen accordingly. Its expected length is also $1.95$ bits. The methods agree here; their agreement on this particular distribution is not a claim that the two procedures always coincide.

Differentiate the normalization of the exponential family density with respect to ${\theta }_i$, assuming the regularity that permits differentiation under its integral. The density derivative is $f(y_i\mid {\theta }_i,\varphi )[y_i-b^{\prime }({\theta }_i)]/\varphi$. ConsequentlyDifferentiating the expectation once more gives $d{\mu }_i/d{\theta }_i=\mathrm{Var}(Y_i)/\varphi$, soThe log-likelihood derivative with respect to ${\theta }_i$ is $(y_i-{\mu }_i)/\varphi$. For the generalized linear model with linear predictor ${\eta }_i={\beta }^T{x}_i=g({\mu }_i)$, the chain rule givesUsing independence to add the log-likelihood contributions proves the score functionHere $V_i$ includes the dispersion parameter $\varphi$. Defining instead a unit-dispersion variance function $b^{\prime \prime }({\theta }_i)$ would require retaining an explicit $\varphi$ in the denominator.

The nullclines are $x=f(y)$ and $y=g(x)$, both decreasing curves in the positive quadrant. To their left/right the horizontal velocity is respectively positive/negative; below/above the second nullcline the vertical velocity is positive/negative. Bounded positive synthesis functions give an inward-pointing sufficiently large rectangle, while the axes point into the quadrant. More directly, put $H(x)=f(g(x))-x$: $H(0)>0$, and $H(x)<0$ for large enough $x$. Continuity therefore gives a positive equilibrium.

At an equilibrium, the Jacobian matrix is $J=\left(\begin{array}{cc}-1& f^{\prime }(y_{\ast })\\ g^{\prime }(x_{\ast })& -1\end{array}\right)$, with eigenvalues $-1\pm \sqrt{f^{\prime }(y_{\ast })g^{\prime }(x_{\ast })}$. Its logarithmic-slope product isbecause $f(y_{\ast })=x_{\ast }$ and $g(x_{\ast })=y_{\ast }$. Thus a product exceeding one makes this equilibrium a saddle and gives $H^{\prime }(x_{\ast })>0$. Immediately on its left $H<0$, and immediately on its right $H>0$. Since $H(0)>0$ and $H$ is eventually negative, there must be other roots on both sides, crossing in the attracting direction. For simple roots those have $H^{\prime }<0$, hence two negative Jacobian eigenvalues: the saddle separates at least two stable steady-state alternatives. The divergence is $-2$, so periodic attractors cannot replace these equilibria in a bounded planar region. Nongeneric flat crossings or intervals of equilibria require a nonlinear stability interpretation; the strict saddle inequality alone does not guarantee that every other root is hyperbolic. This is the usual mutual repression stability criterion behind bistability.

The conclusion also has a nonlinear trapping justification. Choose $l<u$ on the left of the saddle with $H(l)>0>H(u)$; such endpoints exist by the signs just proved. The rectangle $[l,u]\times [g(u),g(l)]$ is forward invariant: on the vertical edges, $f(y)-l\ge f(g(l))-l>0$ and $f(y)-u\le f(g(u))-u<0$, while the horizontal-edge velocities point inward or are tangent. The same construction on the right of the saddle gives a second disjoint trapping rectangle. Each contains a nonempty compact attracting invariant set, obtained by intersecting its nested forward images; strict vertical inwardness also rules out invariant boundary trajectories. If a downward crossing is isolated, endpoints can be taken arbitrarily close to it, proving nonlinear stability, and the absence of periodic orbits makes nearby trajectories converge to that equilibrium. Intervals of equilibria instead give attracting alternatives consisting of families, so bounded monotone functions without nondegeneracy do not necessarily produce two isolated hyperbolic attractors.

At a positive equilibrium of the bounded Hill model, the mutual repression stability criterion becomesThus $mn>1$ is necessary. Because the same $\lambda$ is imposed in both synthesis functions, it is not sufficient for arbitrary unequal positive exponents. The additional equilibrium constraint isHere is an exact criterion for all the printed exponent choices, including nonintegers. If $m>1$ and $n>1$, multistability is possible: for large $\lambda$ the intermediate equilibrium satisfies $x\sim {\lambda }^{(m-1)/(mn-1)}$, $y\sim {\lambda }^{(n-1)/(mn-1)}$, so both increase without bound and $K\to mn>1$. These asymptotics follow by balancing $x{y}^m\sim \lambda$ and $y{x}^n\sim \lambda$; the limiting two algebraic equations have a nonsingular log-Jacobian when $mn\ne 1$, so a nearby exact equilibrium exists for large $\lambda$. If both exponents are at most one, $K<1$ everywhere and multistability is impossible.

For the remaining case, interchange $x,y$ if necessary so $0<m\le 1<n$. For each $x>0$, let $Y(x)>0$ be the unique solution ofwhich exists because the left side is strictly decreasing; for $m=1$ the right side always exceeds one. DefineThen the exact answer for this remaining range isThis is a one-variable test depending only on $m,n$, with no unknown $\lambda$. To prove it, parameterize all equilibria by $\lambda (x)=x(1+Y(x{)}^m)$. Implicit differentiation givesThe denominator is positive, and $\lambda (x)$ goes from zero to infinity as $x$ goes from zero to infinity. A negative-slope portion therefore forces two folds and an interval of three equilibria, with two attracting branches. If $K\le 1$ everywhere, $\lambda$ is strictly increasing apart from possible isolated stationary points, so there is only one equilibrium for each $\lambda$. This is the common-strength Hill repression criterion.

For illustration and a closed test on the boundary $m=1$, $Y=x/(1+x^n-x)$ andobtained at $x^n=(n+1)/(n-1)$. In particular $(m,n)=(1,2)$ has $mn>1$ but maximum $3\sqrt{3}/8<1$, so it cannot be multistable. For positive integer exponents the allowed choices simplify to both exponents at least two, or one equal to one and the other at least four. For arbitrary real exponents the preceding exact criterion is needed; replacing it by $mn>1$ would discard the common-strength constraint.

The unbounded power laws behave differently. Combining their equilibrium equations gives $x^{1-mn}={\lambda }^{1-m}$. If $mn\ne 1$, there is exactly one positive equilibrium,Its slope product is exactly $mn$, so it is attracting if $mn<1$ and a saddle if $mn>1$, but there are never two isolated attracting equilibria. If $mn=1$, equilibria exist only when ${\lambda }^{1-m}=1$; when this holds there is a whole curve of equilibria, with a zero tangent eigenvalue and transverse eigenvalue $-2$. This includes $m=n=1$, $xy=\lambda$, for every $\lambda$. A neutrally degenerate continuum is not bistability between isolated attractors. Thus these power laws do not generate ordinary multistability; boundedness was essential to the outer-root argument in part (a).

The Bendixson-Dulac criterion says that if a $C^1$ planar field admits a $C^1$ multiplier $B$ on a simply connected region such that $\nabla \cdot (Bf)$ has one strict sign there, no nonconstant periodic orbit lies wholly in that region. The Poincaré-Bendixson theorem says that a nonempty compact omega-limit set of a planar $C^1$ flow which contains no equilibria is a periodic orbit.

For $\mu <0$, the divergence of the given field is $\mu -2x^2-3y^2<0$ throughout the plane. Taking $B=1$ proves there are no periodic orbits.

For $\mu >0$, use $E=(x^2+y^2)/2$. Along trajectories,On a circle $r=r_{-}$ with $2r_{-}^2<\mu$ the radial flow is outward or tangent, and on a circle $r=r_{+}$ with $r_{+}^2>\mu$ it is inward or tangent. Their intervening closed annulus is positively invariant. At the tangent points $y=0$, the field has $\dot{y}=-x\ne 0$, so no equilibrium sits on its boundaries. Indeed the only equilibrium is the origin, excluded from the annulus. Every forward trajectory in the annulus has a nonempty compact omega-limit set without equilibria. The Poincaré-Bendixson theorem consequently proves at least one periodic orbit exists for every $\mu >0$. No claim of uniqueness follows from this trapping argument.

A Papperitz symbol records the three regular singular points of a second-order Fuchsian differential equation and the two local exponents at each. Exponents at infinity refer to solutions behaving as $z^{-\gamma }$, that is, to powers of the local coordinate $1/z$. Their sum satisfies the Fuchs relation: the six exponents add to one. The symbol represents the two-dimensional solution space, not one normalized solution by itself.

The specified exponents give the Gauss hypergeometric equationSet $d=c-a-b$ and let $v=F(c-a,c-b;c;z)$. Its equation isFor $u=(1-z{)}^{d}v$, differentiation gives $u^{\prime }=(1-z{)}^d[v^{\prime }-dv/(1-z)]$ and $u^{\prime \prime }=(1-z{)}^d[v^{\prime \prime }-2d{v}^{\prime }/(1-z)+d(d-1)v/(1-z{)}^2]$. Substitution into the first equation leaves $(1-z{)}^d$ times exactly the second equation: its $v^{\prime }$ coefficient is $c-(a+b+1+2d)z$, and its $v$ coefficient simplifies to $-(c-a)(c-b)$. Hence $u$ solves the same equation as $F(a,b;c;z)$.

The symbol gives the same check geometrically: multiplication by $(1-z{)}^d$ shifts the exponents at one from $\{0,-d\}$ to $\{d,0\}$ and those at infinity from $\{c-a,c-b\}$ to $\{b,a\}$; it does not change the exponents at zero. Choose the branch with $(1-0{)}^d=1$. Then $u$ is analytic at zero and $u(0)=1$. For $c\notin \{0,-1,-2,\dots \}$ the analytic recurrence uniquely determines this normalized solution, provingThe identity continues wherever both sides are defined with compatible branches. At exceptional parameters where the stated normalization does not uniquely define an analytic function, a parameter-continuation convention is needed; the generic proof does not silently assume uniqueness there. This is Euler's hypergeometric transformation.