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

Let $p_1,\dots ,p_a$ be the primes not exceeding $\sqrt{x}$, where $a=\pi (\sqrt{x})$, and let $\Phi (x,a)$ count integers $1\le n\le x$ divisible by none of these primes. Every surviving integer other than $1$ is prime: a composite integer at most $x$ has a prime factor at most its square root. Conversely, the surviving primes are exactly those between $\sqrt{x}$ and $x$. Thus the Legendre prime-counting formula isBy inclusion-exclusion,where the empty product is one. To cover literally every positive real $x$, replace the subtraction of $1$ by $1_{\{x\ge 1\}}$: for $0<x<1$, both counts are zero and there is no surviving integer $1$.

For $x=48$, the sieving primes are $2,3,5$. The surviving count is $48-(24+16+9)+(8+4+3)-1=13$. Consequently

The two-dimensional Brouwer fixed-point theorem states that every continuous map from a closed filled triangle to itself has a fixed point. Use the triangle $\Delta =\{x\in {\mathbb{R}}^3:x_i\ge 0,{\sum }_i{x}_i=1\}$, which lies in a two-dimensional affine plane. Strict positivity of the matrix entries ensures $(Ax{)}_i>0$ for every $x\in \Delta$. Thereforeis a continuous self-map of $\Delta$, in fact into its interior. Its fixed point $x$ satisfies $Ax=\lambda x$, where $\lambda ={\sum }_i(Ax{)}_i>0$. Since $x=T(x)$ lies in the interior, $A$ has an eigenvector all of whose entries are strictly positive. This is positive matrix eigenvector from simplex normalization; it uses strict positivity, not merely nonnegative entries.

For a Euclidean circle with centre $c$ and radius $r$, two distinct finite points are inverse when they lie on the same ray from $c$ and their distances from $c$ have product $r^2$. Points on the circle are fixed, and $c$ and infinity are inverse to each other. In complex coordinates this uniquely defines inversion in a circle byUniqueness follows from the ray and product conditions, including the specified centre–infinity pair; the formula also gives $I_{\Gamma }^2=\mathrm{id}$. A circle through infinity is a straight line in the complex plane; its inversion is reflection in that line, fixing infinity. For a line through $c$ with direction angle $\theta$, its formula is $c+e^{2i\theta }\overline{z-c}$.

Thus every inversion is an anti-Möbius transformation, of the form $(a\overline{z}+b)/(c\overline{z}+d)$ with nonzero determinant. If $J(z)=\overline{z}$, write such an inversion as $M\circ J$ with $M$ a Möbius transformation. Since $J\circ M\circ J$ is the Möbius transformation with conjugated coefficients, the product of two inversions is $M_1\circ (J\circ M_2\circ J)$, hence Möbius. Pairing consecutive inversions proves every composition of an even number of inversions is a Möbius transformation.

A binary linear-feedback shift register stores $L$ bits, shifts them at each clock step, and inserts a fixed linear combination over ${\mathbb{F}}_2$ of the stored bits. Its output obeys a recurrence $s_n+c_1{s}_{n-1}+\cdots +c_L{s}_{n-L}=0$. Write its connection polynomial as $C(D)=1+c_{1}D+\cdots +c_L{D}^L$; the corresponding monic feedback polynomial is $z^{L}C(z^{-1})$.

The Berlekamp-Massey algorithm maintains the shortest recurrence fitting the observed prefix. Initialize $C=B=1$, length $L=0$, displacement $m=1$, and previous nonzero discrepancy $b=1$. At symbol $n$, calculate $d=s_n+{\sum }_{j=1}^L{c}_j{s}_{n-j}$. If $d=0$, increase $m$. If $d\ne 0$, save $T=C$ and replace $C$ by $C-(d/b)D^{m}B$. If $2L\le n$, replace $L$ by $n+1-L$, $B$ by $T$, $b$ by $d$, and $m$ by $1$; otherwise only increase $m$. In the binary field subtraction equals addition. The shifted previous discrepancy polynomial cancels the current discrepancy while preserving earlier equations. A failed recurrence of length $L$ at position $n$ requires a corrected length at least $n+1-L$ when this exceeds $L$, explaining the length update. Thus the algorithm recovers the shortest compatible register; a known bound $L$ and at least $2L$ output symbols suffice to identify its minimal recurrence.

For the printed twelve-bit prefix, the nonzero discrepancies occur at positions $n=0,1,2,5,6,7$ (indexing from zero). The successive updated pairs $(L,C)$ areAll remaining discrepancies vanish. ThereforeThe first four observed bits are the fill. Length four is necessary: a length-three recurrence would need to hold already at $n=3$ and no such recurrence fits the prefix. Indeed the equations at $n=3,4,5$ force $c_2=1$, $c_1+c_3=0$, $c_1+c_3=1$, a contradiction. Finite observations cannot rule out longer nonminimal registers.

The normal-model log-likelihood is $-\frac{n}{2}\log {\sigma }^2-\Vert Y-X\beta {\Vert }^2/(2{\sigma }^2)$ up to a constant. Differentiating gives the maximum-likelihood estimatorsLet $P=X(X^{T}X{)}^{-1}{X}^T$. The fitted component $P\epsilon$ and residual $(I-P)\epsilon$ are orthogonal jointly normal projections and hence independent. ThereforeThe prediction error $\tilde{y}-y^{\ast }=x^{\ast T}(\hat{\beta }-\beta )-{\epsilon }^{\ast }$ is normal with mean zero and variance ${\sigma }^2{\tau }^2$, and is independent of the residual variance estimate. Dividing by the independent estimated standard deviation yieldsThus the prediction interval in a normal linear model isThe extra $1$ includes the new observation's independent noise; omitting it would give a confidence interval for its conditional mean instead.

The terms $u$ and $\alpha v$ represent intrinsic exponential population growth. The losses $-uv$ and $-\alpha uv$ describe competition between the species; $-{ϵ}_1{u}^2$ and $-\alpha {ϵ}_2{v}^2$ describe crowding within each species. The positive constant $\alpha$ sets the relative time scale of the second population.

The four equilibrium points in the nonnegative quadrant areThe last follows by solving ${ϵ}_{1}u+v=1$ and $u+{ϵ}_{2}v=1$ and is strictly positive under the assumptions. The Jacobian matrix isAt the origin its eigenvalues are $1,\alpha >0$, so it is unstable. At the first single-species equilibrium they are $-1$ and $\alpha (1-1/{ϵ}_1)<0$; at the second they are $1-1/{ϵ}_2<0$ and $-\alpha$. Both are asymptotically stable. At coexistence,Thus coexistence is a saddle; either species-only equilibrium is stable, and extinction is unstable. The saddle's stable manifold separates the competing basins of attraction.

Choose binary expansions $x=0.b_1{b}_2\dots$ that do not end in an infinite string of ones. The doubling map deletes the first digit: $F(x)=0.b_2{b}_3\dots$. Given $x$ and any neighbourhood of it, choose $N$ sufficiently large that its binary cylinder of length $N$ is small enough, and choose a point $y$ sharing that prefix but with a prescribed tail. After $N$ shifts, the tail of $y$ may be chosen arbitrarily in $[0,1)$. Choose it close to zero or close to one, whichever is at distance more than $1/3$ from $F^N(x)$. Then $|x-y|\le 2^{-N}$ but $|F^N(x)-F^N(y)|>1/3$. Hence the map has sensitive dependence on initial conditions, with a uniform separation constant. At dyadic endpoints the cylinder sharing the chosen terminating expansion still contains points arbitrarily close to the endpoint.

Every nonempty relatively open interval contains a binary cylinder whose points share a finite prefix. Given nonempty open sets $U,V$, choose such a cylinder $C\subset U$ of length $N$. After $N$ binary shifts, $F^N(C)$ contains $[0,1)$ with the usual half-open cylinder convention. In particular, some point of $C$ maps into $V$. Thus $F$ is topologically transitive: $F^N(U)\cap V\ne \varnothing$. Equivalently, concatenate a prefix placing the point in $U$ with a tail placing its $N$th iterate in $V$.

Given a binary cylinder with finite prefix $b_1\dots b_N$, repeat a finite block beginning with that prefix indefinitely. The resulting binary sequence is periodic under the shift and represents a periodic point of an interval map of $F$ in the cylinder. If the given prefix consists entirely of ones, append a zero to the block so that its value is less than one; this still preserves the prefix. Since cylinders can be taken inside any nonempty open interval, periodic points are dense.

A point fixed by $F^4$ satisfies $(2^4-1)x\in \mathbb{Z}$, so $x=j/15$ for $0\le j\le 14$. The points with period dividing two are $0,1/3,2/3$, corresponding to $j=0,5,10$. All other twelve points have least period four. Multiplication by two modulo fifteen groups them into the three cyclesThis exhausts the requested four-cycles. The displayed order is the dynamical order, and cyclic changes of the starting point describe the same cycle.

For the Euler integral to converge directly, assume $\mathrm{Re}b>0$ and $\mathrm{Re}(c-b)>0$. At zero it is the beta function $B(b,c-b)=\Gamma (b)\Gamma (c-b)/\Gamma (c)$. The normalization is thereforeOutside these initial parameter conditions the hypergeometric function is defined by analytic continuation wherever the parameters permit it.

For $|z|<1$, differentiation under the convergent Euler integral giveswhere $(a{)}_n=a(a+1)\cdots (a+n-1)$ and $(a{)}_0=1$ are Pochhammer symbols. Thus its Taylor series iswhich is symmetric in $a,b$. In the common region of parameter convergence for the two Euler integrals, this proves equality near zero. The identity theorem extends it throughout their common principal slit domain, and parameter continuation gives the usual identity wherever both sides are defined:

Assume the spheroid is homogeneous, as implicit in the stated moments. Put $s=\sqrt{1-e^2}$ and map a uniform solid sphere by $(X_1,X_2,X_3)\mapsto (X_1,X_2,s{X}_3)$, preserving total mass by adjusting density. For the sphere, symmetry and its moment $2M{a}^2/5$ give $\int X_i^{2}dm=M{a}^2/5$ for each coordinate. The transformed squared-coordinate integrals are consequently $M{a}^2/5,M{a}^2/5,s^{2}M{a}^2/5$. Reflection symmetry makes the off-diagonal inertia entries vanish. ThusThe original PDF gives the correct solid-sphere factor $2/5$, rather than the converted TeX's $2/3$.

Put $I=I_1=I_2$. The third of the Euler equations for a torque-free rigid body gives ${\dot{\omega }}_3=0$. The first two become ${\dot{\omega }}_1=-\Omega {\omega }_2$, ${\dot{\omega }}_2=\Omega {\omega }_1$, whereTherefore ${\omega }_1+i{\omega }_2=C{e}^{i\Omega t}$. In body coordinates, $L_1+i{L}_2=IC{e}^{i\Omega t}$ and $L_3=I_3{\omega }_3$ is constant. The angular momentum precesses about the body symmetry axis, with periodFor positive ${\omega }_3$ this is the printed expression. In the inertial frame the torque-free angular momentum is constant; the precession here is its changing representation in the rotating body frame. If $e=0$ or ${\omega }_3=0$, this body-frame precession rate is zero.

Here $H=\dot{a}/a=2/(3t)$, so the perturbation equation becomes $\ddot{\delta }+(4/3t)\dot{\delta }-(2/3t^2)\delta =0$. A trial $t^s$ gives $s(s-1)+(4/3)s-2/3=0$, with roots $2/3,-1$. ThusThe pure growing mode obeys ${\delta }_k(t)/{\delta }_k(t_i)=a(t)/a(t_i)$; for generic data the decaying component eventually becomes negligible, though the growing-mode normalization must be determined from both initial data.

With $a(t_0)=1$, the physical wavelength is $2\pi a(t)/k$. Equating it to the Hubble radius $c/H=3ct/2$, and using $k_0=2\pi H_0/c$, givesGrowing-mode evolution from crossing to today multiplies the perturbation amplitude by $(t_0/t_k{)}^{2/3}=(k/k_0{)}^2$. Hence the supplied horizon-crossing variance givesThis conclusion uses the stated matter-dominated growing-mode approximation over the relevant evolution, rather than an additional radiation-era transfer function.

Reduce the polynomial modulo $p$, obtaining a nonzero degree-$d$ polynomial over the field ${\mathbb{F}}_p$. If $a$ is a root, polynomial division gives $\bar{f}(X)=(X-a)h(X)$. Any different root $b$ is a root of $h$, because $b-a\ne 0$ is invertible. Induction on degree therefore proves there are at most $d$ distinct roots modulo $p$.

Every nonzero residue is a root of $X^{p-1}-1$ by Fermat's little theorem. The difference between this monic polynomial and the product over all its $p-1$ nonzero roots has degree at most $p-2$, yet has $p-1$ roots. The root bound forces it to vanish identically over ${\mathbb{F}}_p$. Thus all coefficients of the corresponding integer polynomial are divisible by $p$.

For the requested failure modulo $p^2$, take $p=7$: $6!+1=721=7\cdot 103$, and $103$ is not divisible by seven. Hence the prime-square strengthening fails, even though some special primes do satisfy it.

Compare constant terms in the polynomial identity proved above. The constant term of $X^{p-1}-1$ is $-1$, while that of the product is $(-1{)}^{p-1}(p-1)!$. For odd $p$, this gives $(p-1)!\equiv -1(\mathrm{mod}p)$. For $p=2$, the same conclusion holds because $1\equiv -1(\mathrm{mod}2)$. Thus Wilson's theorem follows:

For odd $p$, pair the terms with denominators $j$ and $p-j$. Since both denominators are coprime to $p$,has numerator divisible by $p$ and denominator not divisible by $p$. Summing these $(p-1)/2$ pairs over a common denominator coprime to $p$ gives a numerator divisible by $p$. Cancelling common factors cannot remove a factor $p$, since none occurs in the denominator. Therefore the numerator of $u_p$ in lowest terms is divisible by $p$. Equivalently, inversion permutes the nonzero residues and ${\sum }_{j=1}^{p-1}{j}^{-1}\equiv {\sum }_{j=1}^{p-1}j\equiv 0(\mathrm{mod}p)$.

A Kleinian group is a discrete subgroup of ${\mathrm{PSL}}_2(\mathbb{C})$, acting as orientation-preserving hyperbolic isometries of ${\mathbb{H}}^3$ and as Möbius transformations of its boundary sphere. Its limit set consists of the accumulation points on the boundary of an orbit $Gx$ with $x\in {\mathbb{H}}^3$; it is independent of that interior base point and is closed. A nonidentity parabolic transformation is conjugate to $z\mapsto z+c$, $c\ne 0$. Its iterates on the upper half-space tend to its unique fixed boundary point, infinity in these coordinates. Consequently every parabolic fixed point belongs to the limit set.

The displayed matrix has determinant one, trace two, and is not the identity because $a\ne 0$. Its fixed-point equation is $a(z-w{)}^2=0$, so it has exactly the double fixed point $w$. It is therefore parabolic, and its fixed point is $w$.

The determinant-one Gaussian-integer matrices form a subgroup of ${\mathrm{SL}}_2(\mathbb{C})$. They are discrete because their entries lie in a discrete lattice: a matrix sufficiently near the identity has every entry equal to the corresponding identity entry. Passing through the quotient by $\{\pm I\}$ preserves discreteness, so their Möbius transformations form a Kleinian group.

For $w=n/r$, $n=p+iq$ and $r\ne 0$, set $a=r^2$. This gives the Gaussian-integer parabolic constructionAll entries lie in $\mathbb{Z}[i]$, the determinant is one, and its parabolic fixed point is $n/r=w$. The points with nonzero $p,q,r$ are dense in the finite complex plane, and their closure on the sphere includes infinity. Since the limit set is closed and contains all these parabolic fixed points, the limit set is the whole Riemann sphere.

Use the exponential dispersion family convention $f(y)=\exp \{[y\theta -b(\theta )]/\varphi +c(y,\varphi )\}$. For the Gamma distribution, takeSubstitution reproduces the gamma density exactly. Differentiating its normalization with respect to $\theta$ yields $\mathbb{E}Y=b^{\prime }(\theta )$ and $\mathrm{Var}Y=\varphi b^{\prime \prime }(\theta )$: the first identity follows from zero mean score, and differentiation again gives the variance. ThereforeThe canonical link function is $g(\mu )=\theta =-1/\mu$. Some conventions reverse the sign and call $1/\mu$ the reciprocal link; this only reverses the regression coefficients. We retain the genuine natural parameter $\theta =-1/\mu$.

In the Gamma regression with canonical link, ${\eta }_i=x_i^T\beta <0$ and ${\mu }_i=-1/{\eta }_i$. Differentiating the independent-observation log-likelihood givesHere $d{\mu }_i/d{\eta }_i={\mu }_i^2$, so the negative Hessian equals this information matrix. Fisher scoring or Newton iteration iswith the means and information recalculated at each iteration; damping can preserve $X\beta <0$ and increase the likelihood. Full column rank makes the information positive definite for positive means.

The saturated model has mean $y_i$. Subtracting fitted from saturated log-likelihood yields the unscaled devianceTwice the actual log-likelihood ratio is $D/\varphi$. In particular, the printed parenthetical $\hat{\mu }=X\hat{\beta }$ is incorrect for this nonidentity link: $X\hat{\beta }$ estimates $\eta$, and ${\hat{\mu }}_i=-1/(x_i^T\hat{\beta })$.

The fixed-point equation is $x[a{x}^2+bx+\mu -1]=0$. Thuswhen the discriminant is nonnegative. At zero the multiplier is $F^{\prime }(0)=\mu$, so it is linearly stable for $-1<\mu <1$ and unstable for $|\mu |>1$. At a nonzero fixed point, eliminate $\mu$ to obtain the branch and its multiplier:The branch is stable precisely when $-2<x(b+2ax)<0$. These formulas specify stability throughout the diagram, including any extra flip points outside the region requested.

If $b=0$ and $a>0$, the two nonzero branches $x=\pm \sqrt{(1-\mu )/a}$ exist for $\mu <1$ and have multiplier $3-2\mu >1$. Thus $\mu =1$ is a subcritical pitchfork bifurcation. If $b\ne 0$, the branch through zero has $x\sim (1-\mu )/b$ and $M\sim 2-\mu$; its stability exchanges with zero at $\mu =1$, a transcritical bifurcation. The two nonzero roots meet atwhere $M=1$. The graph of $\mu (x)$ has nonzero second derivative $-2a$, proving a saddle-node bifurcation. At zero and $\mu =-1$, the multiplier is $-1$, indicating a period-doubling bifurcation; generically its nondegeneracy coefficient is $a+b^2$. If $a+b^2=0$, necessarily $b\ne 0$ here, composition at $\mu =-1$ instead gives $F^2(x)-x=4b^4{x}^5+O(x^6)$. For $\delta =\mu +1>0$ small, the leading return equation is $-2\delta x+4b^4{x}^5=0$, producing a two-cycle with leading amplitudes $x\sim \pm [\delta /(2b^4){]}^{1/4}$. Its return multiplier is $1+8\delta +o(\delta )>1$. Thus this special case still has a flip bifurcation, but it is degenerate and subcritical rather than the generic cubic normal form.

For $a,b>0$, the fold lies above $\mu =1$. Between it and the transcritical point, the branch $-b/(2a)<x<0$ is stable provided its multiplier remains above $-1$, while the other branch is unstable. For $a,b<0$, the fold lies below $\mu =1$: immediately above it the branch $x<-b/(2a)$ is stable and the branch between $-b/(2a)$ and zero is unstable; the branch crossing zero becomes stable for $\mu >1$. All these statements are subject to the displayed exact multiplier criterion if the diagram is extended. The sketch uses representative parameter values and stops before additional flips, as stipulated.

Separate fixed points from roots of $F^2(x)=x$. Fixed points are zero, and $\pm \sqrt{\mu -1}$ for $\mu \ge 1$. The remaining factors in the given factorization yield first $x^2=\mu +1$. For $\mu >-1$ these form the symmetric two-cycle $\{\sqrt{\mu +1},-\sqrt{\mu +1}\}$ because $F(x)=-x$. Its multiplier is $(-2\mu -3{)}^2>1$, so this cycle is always unstable.

The quartic factor gives $s^2-\mu s+1=0$ for $s=x^2$, hence $s_{\pm }=(\mu \pm \sqrt{{\mu }^2-4})/2$. Positive roots require $\mu \ge 2$. At $\mu =2$ they give the fixed points $\pm 1$, not genuine cycles. For $\mu >2$, $s_{+}{s}_{-}=1$ and $F(\sqrt{s_{+}})=\sqrt{s_{-}}$, giving exactly two additional cycles:There are therefore at most three two-cycles. For either of the latter two, its multiplier isThus they are stable for $2<\mu <\sqrt{5}$ and unstable for $\mu >\sqrt{5}$, with a flip at $\sqrt{5}$. The nonzero fixed points have multiplier $3-2\mu$, hence are stable for $1<\mu <2$. Zero is stable for $-1<\mu <1$. At $\mu =1$ there is a supercritical pitchfork; at $\mu =2$ both nonzero fixed points lose stability to these two-cycles. The symmetric unstable cycle terminates at zero at the subcritical flip $\mu =-1$. These are the cubic map period-two branches.

Beyond $\sqrt{5}$ one expects period-four branches and further period doublings, potentially a cascade toward chaotic behaviour. This local argument does not claim that every larger parameter is chaotic; periodic windows and escape may also occur.

The Hamilton equations are $\dot{q}=p/m$ and $\dot{p}=-V_q$. Applying the chain rule to $H(q,p,\lambda (t))$, their two phase-space contributions cancel, giving $\dot{H}=V_{\lambda }\dot{\lambda }=H_{\lambda }\dot{\lambda }$.

For fixed $\lambda$, a closed periodic orbit of energy $E$ has $p=\pm \sqrt{2m(E-V)}$. Thus its action variable isThe sign matches the direction on each half of the orbit, making the enclosed phase-plane area positive. Since $dq=\dot{q}dt=pdt/m$, differentiating under the integral givesFor slowly varying $\lambda$, the exact energy equation averaged over a nearly frozen cycle gives $d⟨H⟩/dt=⟨V_{\lambda }⟩\dot{\lambda }$ to the retained adiabatic order. Using $E=⟨H⟩$, the two chain-rule terms therefore cancel:Here the angle brackets differentiate the explicit parameter dependence along the frozen cycle, not an independently chosen family of energies. The action is an adiabatic invariant, with errors beyond the slow-cycle approximation.

For $V=\lambda q^{2n}$, scale $q=(E/\lambda {)}^{1/(2n)}s$. ThenThe integral is a positive constant depending only on $n$. Constancy of $I$ gives $E^{n+1}/\lambda$ constant, hence

A binary relation $R$ on a set is a well-founded relation if every nonempty subset has an $R$-minimal member, that is, a member with no predecessor inside that subset. Here write $xRy$ when $x\in f(y)$.

Suppose $R$ is well-founded and fix any $g:\mathcal{P}(b)\to b$. Call a partial function $h:D\to b$ consistent if $D$ is downward closed under $R$ and $h(y)=g(\{h(x):x\in f(y)\})$ for $y\in D$. Two consistent partial functions agree on their common domain: otherwise the set of points where they disagree has a minimal member, all of whose predecessors are in both domains and agree, so applying $g$ gives agreement at that member as well, a contradiction. Thus the union of all consistent partial functions is itself a function $h:D\to b$, on a downward-closed domain, and remains consistent. This union is a set, because every such graph is a subset of $a\times b$.

If $D\ne a$, choose a minimal member $y$ of $a\setminus D$. All predecessors of $y$ lie in $D$, so extend $h$ to $y$ by the prescribed value $g(\{h(x):x\in f(y)\})$. The enlarged domain remains downward closed and consistent, contradicting the union's maximality. Hence $D=a$. The same minimal-disagreement argument proves uniqueness. This establishes the required recursion directly, without invoking an unproved well-founded recursion theorem.

Conversely, if $R$ is not well-founded, choose a nonempty $S\subset a$ such that each $y\in S$ has a predecessor in $S$. Let $T$ be all points reachable from $S$ by a finite chain of upward $R$ steps, including $S$. ThenFor a point reached by a nonempty chain, its preceding point is in $T$; for a point of $S$, use its predecessor in $S$. The converse follows by appending the final step to a chain. Choose $b=\{0,1\}$ and $g(B)=1$ if $1\in B$, zero otherwise. Both $h_0\equiv 0$ and $h_1=1_T$ satisfy the required recursion, and they differ because $S\ne \varnothing$. This contradicts recursiveness. Therefore $f$ is recursive exactly when its predecessor relation is well-founded, the characterization of a recursive powerset mapping.

Let $d_v$ be the vertex degrees and let $r_{ij}$ count common neighbours of distinct vertices. Count unoriented length-two paths by their centre or endpoints:If no four-cycle occurs, $r_{ij}\le 1$, so $P_2\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$. By Cauchy-Schwarz inequality, $P_2\ge \frac{1}{2}[(2m{)}^2/n-2m]$. Solving $4m^2-2nm\le n^2(n-1)$ givesIf $m\ge n(n-1)/4$, the same bound and monotonicity of $2m^2/n-m$ in this range give $P_2\ge n(n-1)(n-3)/8$ (the small $n$ cases are immediate). Every pair of common neighbours supplies a four-cycle, counted twice through its two opposite vertex pairs, so four-cycle counting by common neighbours givesLet $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $\bar{r}=P_2/N\ge (n-3)/4$. Convexity of $r(r-1)/2$ gives $C_4\ge (N/2)\left(\genfrac{}{}{0ex}{}{\bar{r}}{2}\right)$. For $n\ge 7$, this function is increasing on the needed range, givingFor $3\le n\le 6$ the printed right-hand side is nonpositive and the conclusion is trivial. At $n=2$ the printed cycle bound is false: a single edge meets the edge hypothesis but has no four-cycles, while the right-hand side is $5/64>0$. Thus this particular bound needs the intended $n\ge 3$ restriction; the other counting statements above do not have this defect.

On four chosen vertices there are three distinct cycle subgraphs, each present with probability $2^{-4}$ in the stated random graph. Extra edges do not destroy these subgraphs. ThereforeFor positive expectation, Markov inequality giveswhen $0<ϵ<1/2$. If $n<4$, the cycle count is identically zero and the requested event has probability one.