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

Let $p_1,\dots ,p_a$ be the first $a$ primes, and let $\varphi (x,a)$ count positive integers at most $x$ not divisible by any of them. The inclusion-exclusion principle givesFor $a=\pi (\sqrt{x})$, every composite at most $x$ is removed, so the survivors are one and the primes larger than $\sqrt{x}$. Thus the Legendre prime-counting formula is $\boxed{\pi (x)=\varphi (x,\pi (\sqrt{x}))+\pi (\sqrt{x})-1}$. This is the prime-counting formula, distinct from the factorial-valuation formula of the same name.

Fix $y\ge 2$ and put $a=\pi (y)$. Every prime exceeding $y$ is among the unsieved integers. Replacing each floor in the finite sum by its argument makes an error bounded by $2^a$, givingTake $x\to \infty$ with $y$ fixed. The supplied product estimate gives $0\le \mathrm{limsup}\pi (x)/x\le 1/\log y$. Since $y$ can be arbitrarily large, $\boxed{\underset{x\to \infty }{\lim }\pi (x)/x=0}$. The order of these limits avoids treating the growing inclusion-exclusion error as negligible.

For each node define its Lagrange interpolation cardinal polynomial ${\ell }_i(t)={\prod }_{j\ne i}(t-x_j)/(x_i-x_j)$. Its square has degree $2n-2<2n$ and nodal values ${\ell }_i(x_j{)}^2={\delta }_{ij}$. Exactness therefore gives $a_i={\int }_{-1}^1{\ell }_i(t{)}^{2}dt$. The polynomial is nonzero, so continuity makes this integral strictly positive. Thus $\boxed{a_i>0}$ for every node.

Apply exactness to the constant polynomial one. Its integral is two and its value at every node is one, so $\boxed{\sum _{i=1}^n{a}_i=2}$.

Put $P(t)={\prod }_i(t-x_i)$. For every polynomial $q$ of degree at most $n-1$, $Pq$ has degree at most $2n-1$ and vanishes at all nodes; thus ${\int }_{-1}^{1}Pq=0$. The monic degree-$n$ orthogonal polynomial for this integral is unique: the difference of two such monic polynomials has degree below $n$ and is orthogonal to itself, hence is zero. Consequently $P$ is the monic normalization of the degree-$n$ Legendre polynomial, proving the given nodes are exactly its roots. Together the three results characterize this Gaussian quadrature rule.

A nonidentity Möbius transformation has either two distinct fixed points on the Riemann sphere or one double fixed point. With two fixed points, conjugate them to zero and infinity. A Möbius map fixing both is $z\mapsto kz$ with $k\ne 0$. With one fixed point, conjugate it to infinity; the resulting map is affine, $z\mapsto az+b$. If $a\ne 1$ it would have another fixed point, so $a=1$ and $b\ne 0$. Scaling the coordinate makes it $z\mapsto z+1$. The identity is already the case $k=1$.

Define ${\mathrm{tr}}^2(g)$ using a determinant-one representing matrix; the two possible lifts differ by sign, so its square is well defined and invariant under conjugation. For $z\mapsto kz$ it is $k+2+k^{-1}$, while for a nontrivial translation it is four. If two nonidentity dilations have equal trace-square, their multipliers satisfy the same quadratic and are either equal or reciprocal. Inversion $z\mapsto 1/z$ conjugates one reciprocal multiplier to the other. Trace-square four forces the dilation multiplier to be one, which is the excluded identity; thus every nonidentity map with that invariant is in the translation class. This proves $\boxed{g\sim h⟺{\mathrm{tr}}^2(g)={\mathrm{tr}}^2(h)}$ for the stated nonidentity maps.

Not every such map fixes an interior point of hyperbolic three-space. In its upper-half-space extension, $z\mapsto z+1$ translates the horizontal coordinate and has no fixed point at positive height. A dilation extends as $(z,t)\mapsto (kz,|k|t)$, so it fixes the vertical axis only when $|k|=1$; if $|k|\ne 1$, the height changes. Boundary fixed points therefore do not imply an interior fixed point.

A digital signature lets a holder of a private key authenticate a message while anyone with the public key verifies it. Signing a message digest ties the signature to the message and detects alterations; it does not conceal the message. Authentication also requires a trustworthy association of the public key with its owner.

For the ElGamal signature scheme, choose a large prime $p$ and a generator $g$ of ${\mathbb{F}}_p^{\times }$. The secret is $x$, and the public key is $(p,g,y)$ with $y=g^x\mathrm{mod}p$. To sign a message whose hash is represented by $m\mathrm{mod}(p-1)$, choose a fresh secret nonce $k$ coprime to $p-1$ and setTransmit $(r,s)$ with the message. Verification checks the permitted ranges and $\boxed{g^m\equiv y^r{r}^s(\mathrm{mod}p)}$. Correctness follows from $xr+ks\equiv m(\mathrm{mod}p-1)$. The secret exponent prevents an outsider from directly constructing this relation for an arbitrary hashed message; nonce reuse can expose the exponent through the repeated linear congruences. Hashing is part of the signature scheme, rather than signing arbitrary raw exponents with no message encoding.

The least-squares estimator minimizes $\Vert Y-Xb{\Vert }^2$. Differentiating in $b$ gives $-2X^T(Y-Xb)=0$, hence $\boxed{X^{T}X\hat{\beta }=X^{T}Y}$. Full column rank makes $X^{T}X$ positive definite, soThis is a linear transformation of a multivariate normal distribution. Its mean is $\beta$ and its covariance is ${\sigma }^2(X^{T}X{)}^{-1}$. Therefore $\boxed{\hat{\beta }\sim N_p(\beta ,{\sigma }^2(X^{T}X{)}^{-1})}$.

Define the hat matrix $H=X(X^{T}X{)}^{-1}{X}^T$. It is symmetric and idempotent, the orthogonal projection onto the column space of $X$. Since $HX=X$,The covariance is ${\sigma }^{2}H{H}^T={\sigma }^{2}H$. This normal distribution can be singular when $p<n$, since all fitted vectors lie in the $p$-dimensional model subspace.

The probability of an exact copy is $Q=q^L$. Incorrect copies contribute mutants at rate $a(1-Q)x$, giving $\boxed{\dot{y}=by+a(1-Q)x}$. For $y>0$, differentiating the ratio givesThis is a logistic-type equation for relative concentration; the absolute concentrations need not have a stationary value.

For $0<q<1$, a finite positive equilibrium exists exactly when $a{q}^L>b$, and thenThe derivative of the ratio's vector field at $z_{\ast }$ is $-(a{q}^L-b)<0$, so this equilibrium is locally asymptotically stable; every positive initial ratio tends to it. The critical real length is $L_c=\log (b/a)/\log q$, and the admissible integer lengths satisfy $L<L_c$. Thus the largest positive integer length, if one exists, is $\boxed{L_{\max }=\lceil L_c\rceil -1}$. At equality the equilibrium is zero, so rounding down without accounting for the strict inequality can be wrong. If $q=1$, mutants are never produced from masters and the ratio grows without a finite positive equilibrium; the finite threshold formula concerns imperfect copying.

Write $ϵ=1-q$ and $b/a=1-s$. Then $\log (1-s)=-s+O(s^2)$ and $\log q=-ϵ+O({ϵ}^2)$, givingThe largest permitted integer is still selected by the strict inequality from part (b). This says that longer master sequences need a proportionately larger selective advantage or smaller per-digit copying error.

At a hyperbolic saddle, the stable invariant subspace of $Df(0)$ is the sum of its generalized eigenspaces with negative real parts; the unstable subspace uses positive real parts. The stable manifold theorem gives invariant local manifolds tangent to these subspaces at the equilibrium, with the corresponding dimensions and the appropriate forward or backward convergence to the equilibrium.

Here the Jacobian is $\mathrm{diag}(1,-1)$, so the unstable tangent is the $x$ axis and the stable tangent the $y$ axis. For the stable graph write $x=h(y)=A{y}^2+B{y}^3+O(y^4)$. Invariance requires $h^{\prime }(y)(-y+3h(y{)}^2)=h+h^2+2hy+3y^2$. Comparing quadratic and cubic terms gives $-2A=A+3$ and $-3B=B+2A$, so $A=-1,B=1/2$.

For the unstable graph $y=g(x)=C{x}^2+D{x}^3+O(x^4)$, invariance is $g^{\prime }(x)(x+x^2+2xg+3g^2)=-g+3x^2$. Coefficients give $2C=3-C$ and $2C+3D=-D$, so $C=1,D=-1/2$. Thus the cubic graph expansion of a saddle invariant manifold isThese describe the local manifolds to cubic order, not exact global polynomial curves.

Assume the Laplace integrals converge absolutely in a common right half-plane. The Fubini theorem and the substitution $t=u-v$ on $u\ge v\ge 0$ give the convolution theorem for Laplace transforms:For the specified inverse-square-root function, the supplied identity says $f\ast f=\pi$ on $t>0$. Consequently $\hat{f}(p{)}^2=\pi /p$. For real $p>0$ the defining integral is positive, fixing the positive square root; analytic continuation into $\mathrm{Re}p>0$ giveswith the branch positive on the positive real axis. The square identity alone would not select the sign.

The Poisson bracket is $\{f,g\}={\sum }_a(f_{q_a}{g}_{p_a}-f_{p_a}{g}_{q_a})$. For a function with no explicit time dependence, the chain rule and Hamilton equations giveWith $L_b={ϵ}_{bcd}{x}_c{p}_d$, direct differentiation givesApply the product rule to $L_a={ϵ}_{acd}{x}_c{p}_d$ and substitute these two brackets. Contracting the epsilon symbols yields $\boxed{\{L_a,L_b\}={ϵ}_{abc}{L}_c}$. Equivalently, the two product terms are precisely the infinitesimal rotation of the vector $x\times p$ about the $b$ axis, with the same bracket convention as the position and momentum vectors.

For a homogeneous isotropic metric, radial light propagation covers comoving distance $\int cdt/a(t)$. The physical particle horizon is $d_p(t)=a(t){\int }_{t_i}^{t}cd{t}^{\prime }/a(t^{\prime })$, when this is finite. A future event horizon exists when $d_e(t)=a(t){\int }_t^{t_f}cd{t}^{\prime }/a(t^{\prime })$ is finite. The Hubble radius is the instantaneous scale $c/H$, with $H=\dot{a}/a$; it is not generally the same as either causal horizon.

For an Einstein-de Sitter universe, $H=2/(3t)$, so $c/H=3ct/2$, while $d_p=3ct$ from a beginning at zero. The future integral diverges, so there is no event horizon. For an eternal-past de Sitter spacetime, $H$ is constant and the particle-horizon integral from $-\infty$ diverges. Its event horizon and Hubble radius both equal $c/H$. Thus a Hubble radius is not automatically a particle horizon, even in these simple isotropic models.

For an expanding decelerating power law $a\propto t^{\alpha }$ with $0<\alpha <1$, the particle horizon is $ct/(1-\alpha )$, and the comoving Hubble radius is $c/(aH)\propto t^{1-\alpha }$. It increases with time, so regions that are mutually visible today can have been out of causal contact at early times. The nearly uniform early thermal conditions inferred across such regions give the horizon problem.

During cosmic inflation, accelerated expansion makes the comoving Hubble radius decrease. A patch initially within one causal communication scale can expand into the region now observed, after which its separated parts are temporarily outside the Hubble radius and later re-enter during deceleration. Sufficient duration before the hot radiation era permits a common causal origin; accelerated expansion is not itself a claim that signals propagate faster than light locally.

For the radiation-era law beginning at $t_r$, the present particle-horizon estimate isRescale this present physical distance back to $t_r$ using $a(t_r)/a(t_0)=\sqrt{t_r/t_0}$. Its physical size was $2c\sqrt{t_r{t}_0}\simeq 0.6\mathrm{m}$, of order one metre as required. The matched inflationary Hubble rate is $H=1/(2t_r)\simeq 5\times 10^{34}{\mathrm{s}}^{-1}$, with Hubble radius $c/H\simeq 6\times 10^{-27}\mathrm{m}$.

If inflation produces $N$ e-folds before $t_r$, this patch began with size $0.6e^{-N}$ metres. It fits within one Hubble radius ifThis estimate uses the idealized radiation-only history stated in the question; substituting the actual matter-dominated history would change the numerical estimate.

Write a reduced positive definite binary quadratic form as $[a,b,c]=a{x}^2+bxy+c{y}^2$, with $|b|\le a\le c$ and $b\ge 0$ on the reduction boundaries. Since $4ac-b^2=20$, reduction gives $3a^2\le 20$, so $a=1$ or two. The middle coefficient is even. For $a=1$, only $b=0$ is possible, yielding $c=5$. For $a=2$, $b=0$ would give a noninteger $c$, while $b=\pm 2$ gives $c=3$; the boundary convention selects $b=2$. Thus the two reduced forms are

A positive odd integer $n$ is properly represented by some integer form of discriminant $d$ exactly when $b^2\equiv d(\mathrm{mod}4n)$ has a solution. For a specified proper equivalence class, the more precise criterion is that $[n,b,(b^2-d)/(4n)]$ belong to that class for some such $b$. Indeed, a primitive representing vector extends to an $S{L}_2(\mathbb{Z})$ basis change, making the leading coefficient $n$; conversely that form represents $n$ at the primitive vector $(1,0)$.

For primes $p\nmid 10$, the existence criterion is $(-20/p)=1$, because the congruence modulo four is compatible with an even middle coefficient. Quadratic reciprocity gives $(-20/p)=(-1/p)(p/5)$, so the split possibilities are $p\equiv 1,3,7,9(\mathrm{mod}20)$. Any proper representing form reduces to one of the two listed forms. Odd values of $x^2+5y^2$ are one modulo four; odd values of $2x^2+2xy+3y^2$ require odd $y$ and are three modulo four. These distinguish the two classes. ConsequentlyA representation of a prime is automatically proper: a common divisor of $x,y$ would have its square divide $p$.

A linear length-$n$ cyclic code is a subspace closed under cyclic coordinate shifts. Identify a word with its polynomial modulo $X^n-1$; multiplying by $X$ performs the shift. Thus a cyclic code is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. Its preimage in the polynomial ring is an ideal containing $X^n-1$, so the Euclidean algorithm gives a unique monic generator $g$ dividing $X^n-1$. The generator polynomial of a cyclic code is $g$ and the check polynomial of a cyclic code is $h=(X^n-1)/g$; a word lies in the code exactly when $hc\equiv 0(\mathrm{mod}{X}^n-1)$.

For the binary length-seven code, the given $h$ factors withThis cubic has no binary root and is irreducible. Let $\alpha$ be its root in ${\mathbb{F}}_8$. Since the nonzero multiplicative group has prime order seven and $\alpha \ne 1$, its seven powers enumerate all nonzero elements. The condition $c(\alpha )=0$ gives a three-row binary parity-check matrix whose columns are precisely the seven nonzero vectors of ${\mathbb{F}}_2^3$. This is Hamming's code in a cyclic coordinate order. It has dimension four, and minimum distance three: no one or two distinct nonzero columns sum to zero, while $g$ itself has weight three. Its sixteen radius-one balls have total size $16(1+7)=128$, confirming the original perfect Hamming code.

It actually contains its dual code in this coordinate order. Each parity-check row has four ones, and any two distinct rows have two simultaneous ones, so $H{H}^T=0$ over ${\mathbb{F}}_2$. The row space $C^{\perp }$ therefore lies in $\ker H=C$. Equivalently the dual generator is the reciprocal check polynomialwhich is divisible by $g$. Hence there is a three-dimensional subcode equal to the dual, and in any other coordinate order it is equivalent to that dual.

Let $m_i=⟨x_i⟩$. The mean equations give $m_1={\lambda }_1/{\beta }_1$ and $m_2={\lambda }_2{m}_1/{\beta }_2$. For relative deviations, the drift Jacobian and normalized reaction-noise covariance areThe normalized stationary fluctuation-dissipation relation for a reaction network is $A\eta +\eta A^T+D=0$ with this negative-drift convention. Its entries successively giveThe birth and death channels act on one species at a time, so the diffusion matrix is diagonal even though the stationary covariance is not.

If RNA concentration does not fluctuate, protein synthesis is an immigration-death process, so its intrinsic normalized variance is $\boxed{1/m_2}$. If protein birth/death noise is suppressed and protein responds deterministically to the fluctuating RNA input, the remaining normalized variance isWriting ${\tau }_i=1/{\beta }_i$, its factor is ${\tau }_1/({\tau }_1+{\tau }_2)$. Slow environmental changes are followed almost fully; rapid environmental fluctuations are averaged over the longer protein response time. Thus extrinsic noise is the magnitude of relative RNA fluctuations multiplied by a dynamical averaging factor.

At the deterministic feedback equilibrium use ${\lambda }_2{m}_{1}f(m_2)={\beta }_2{m}_2$. The indicated elasticity isThe normalized drift becomes $A=\left(\begin{array}{cc}-{\beta }_1& 0\\ {\beta }_2& -{\beta }_{2}H\end{array}\right)$; equal mean birth and death rates still give $D=\mathrm{diag}(2{\beta }_1/m_1,2{\beta }_2/m_2)$. Solving the same covariance equation yields the feedback attenuation of gene-expression noise:For $f(x_2)=k/x_2$, $h=1,H=2$, soThe inverse-feedback expression is interpreted near a positive equilibrium; a microscopic birth rate singular at zero needs a separate regularization there.

Factor the extrinsic term asThe first factor is environmental relative variance. The second is static susceptibility squared: differentiating the equilibrium relation gives $\delta \log m_2=H^{-1}\delta \log m_1$. The last is the time-averaging factor with effective protein response time $1/({\beta }_{2}H)$. Feedback makes response faster, which by itself weakens averaging, but simultaneously reduces the static gain. These are distinct effects and both must be retained.

For the constitutive system, every propensity is affine in the copy numbers. The exact first- and second-moment equations therefore close: expectations of drift are determined by the means, and covariance drift by the covariance. The stationary fluctuation-dissipation calculation is consequently exact, even though the full joint stationary distribution need not be Gaussian.

For feedback, expectations such as $E[x_{1}f(x_2)]$ involve nonlinear moments and correlations. Replacing them by a linear expansion about the mean is a linear noise approximation, so the covariance formula is approximate. It works well around a stable single equilibrium when relative fluctuations are small and the rates vary smoothly over their typical range, generally at sufficiently large molecule numbers. Low counts, strong nonlinearities, multiple attractors and proximity to instability can invalidate it.

With response rates and elasticity effectively fixed, changing ${\lambda }_2$ changes $m_2$ and hence intrinsic noise but not the environmental term. Observation (i) therefore indicates extrinsic noise dominates, making the mean-dependent intrinsic contribution negligible. For a general feedback law whose elasticity changes substantially with the mean, compensation between terms is another possibility; independence from ${\lambda }_2$ alone would then not logically identify the dominant term.

Observation (ii) measures the local relaxation rate ${\beta }_{2}H$, which is larger under negative feedback. Observation (iii) is not explained by faster adjustment alone. At fixed susceptibility, increasing the response rate increases ${\beta }_{2}H/({\beta }_1+{\beta }_{2}H)$, reducing time averaging and increasing transmitted environmental noise. Feedback lowers variance primarily by reducing susceptibility and the intrinsic term. Thus rapid adjustment and low noise share a feedback mechanism but are not a direct causal equivalence.

Differentiate under the contour integral, with one consistent branch and convergent endpoint behavior. ThenThe stated zero boundary term therefore makes the integral a solution. On a closed contour this means returning to the same branch; on an open contour it requires the endpoint values to cancel or vanish.

For $\mathrm{Re}k>0$, choose the straight path from $-i$ to $i$ and put $t=is$, $-1\le s\le 1$. Choose the power of $1-s^2$ continuously, positive for real positive $k$. The boundary factor vanishes at both endpoints. At zero,using the symmetric beta function integral. This choice also gives a nonzero solution.

For positive integers $n$, the finite open segment from part (i) works because $k=n/2>0$. For $n\le 0$, take a finite closed contour enclosing both branch points $i,-i$, with the integrand analytic in the exterior of the joining cut. Near infinity choose $(t^2+1{)}^{n/2-1}=t^{n-2}(1+t^{-2}{)}^{n/2-1}$. Since $n$ is integral, a circuit around both branch points returns to the initial branch, and the endpoint boundary term cancels. Thus this is an admissible finite contour, including $n=0$.

For $n\le -1$, at $z=0$ that exterior branch is $O(t^{n-2})=O(t^{-3})$. Deforming the contour to a large circle makes its integral tend to zero; equivalently its Laurent series has no $t^{-1}$ coefficient. Hence $\boxed{w(0)=0(n\le -1)}$. An individual loop around one branch point would not generally return to the same branch when $n$ is odd, which is why both are enclosed.

The action variable for a regular periodic one-degree-of-freedom Hamiltonian orbit is $I(E)=(2\pi {)}^{-1}\oint pdq$, with orientation along the motion. Along its energy curve, implicit differentiation gives $\partial p/\partial E=1/H_p=1/\dot{q}$. Differentiating the loop integral branchwise givesAt simple turning points the two momentum branches join and their endpoint contributions cancel, so the integrable turning-point singularities do not spoil this differentiation. The formula concerns regular periodic levels, not a separatrix of infinite period.

The energy equation rearranges to $p^2+(E+1)q^2=E{\mu }^2$, an ellipse with semiaxes $p_0=\mu \sqrt{E}$ and $q_0=\mu \sqrt{E/(E+1)}$. At low energy it is nearly circular with both radii $\mu \sqrt{E}$; at high energy it is tall and thin, with $q_0\to \mu$ while $p_0$ grows. The area enclosed is $\pi p_0{q}_0$, soConsequently $T\sim \pi {\mu }^2/(2\sqrt{E})=\boxed{\pi {\mu }^3/(2p_0)}$ at high energy.

The Axiom of foundation states that every nonempty set $A$ has a member $a$ disjoint from $A$. The principle of membership induction states that a property $P$ satisfying $\forall x[(\forall y\in xP(y))\Rightarrow P(x)]$ holds for every set.

Assume Foundation and suppose a progressive property fails at a set $x$. In the transitive closure of $\{x\}$, form the nonempty set of counterexamples by Separation. Foundation selects a counterexample $a$ with no counterexample among its members. Transitivity makes those members belong to the closure, so each satisfies $P$, and progressiveness gives $P(a)$, a contradiction. Conversely, if a nonempty $A$ had no member disjoint from it, the property $P(x):x\notin A$ would be progressive: a member of $A$ necessarily has a member in $A$. Membership induction would then say no set belongs to $A$, a contradiction. Thus Foundation and membership induction are equivalent.

Apply induction to the property that a set belongs to some stage of the cumulative hierarchy. For each member $y$ of $x$, choose its least stage ordinal. Replacement collects these ordinals into a set; take an ordinal $\gamma$ large enough that all members lie in $V_{\gamma }$. Then $x\subseteq V_{\gamma }$ and $x\in V_{\gamma +1}$. This proves every set appears in the hierarchy.

For finite stages let $a_n=|V_n|$. Then $\boxed{a_0=0,a_{n+1}=2^{a_n}}$, giving $0,1,2,4,16,65536,\dots$. The stage $V_{\omega }$ is countably infinite, as the union of the finite stages. Thus $|V_{\omega +1}|=2^{{\aleph }_0}=|\mathbb{R}|$. Cantor's theorem makes $|V_{\omega +2}|$ strictly larger, and every later stage contains it. Earlier stages have at most countable size. Therefore $\boxed{|V_{\alpha }|=|\mathbb{R}|⟺\alpha =\omega +1}$.

For fixed $k$-element subsets $U,V$, their rectangle is empty with probability $(1-p{)}^{k^2}$. A union bound over at most $n^{2k}$ choices gives $P(A)\le n^{2k}(1-p{)}^{k^2}$. For a specified vertex and a specified $(n-k)$-subset, the chance of no edges is $(1-p{)}^{n-k}$. There are at most $n\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le n^{k+1}$ choices on each side, givingFor $n\ge 6$, $k=\lceil \sqrt{n}\rceil \le n/2$ and $k^2\ge n$. Hence $P(A\cup B\cup C)<3n^{2k}(1-p{)}^{n/2}$. The logarithm of this bound is $\log 3+2k\log n+(n/2)\log (1-p)$, which tends to $-\infty$ because $\sqrt{n}\log n=o(n)$. Thus the bad-event probability tends to zero.

The printed phrase “almost surely” must mean asymptotically almost surely as $n\to \infty$. At any fixed $n$, the empty graph has positive probability $(1-p{)}^{n^2}$, so the literal probability-one assertion is false.

When no bad event occurs, verify Hall's marriage theorem. If $0<|U|\le k$, each vertex has more than $k$ neighbors because event $B$ is absent, so $|N(U)|\ge |U|$. If $k<|U|\le n-k$, a failure would leave at least $k$ vertices outside $N(U)$, producing a forbidden empty $k$-square. If $|U|>n-k$, every vertex in $Y$ meets $U$ because event $C$ is absent; hence $N(U)=Y$. The empty set also satisfies Hall. Therefore the graph has a perfect matching whenever the three events are absent, proving the random bipartite matching from empty-rectangle exclusion result with probability tending to one.

Modulo two the quartic has no root, and the only irreducible monic quadratic is $x^2+x+1$. Reducing the quartic modulo that quadratic gives remainder one. Hence the quartic is irreducible over ${\mathbb{F}}_2$. Its splitting field is ${\mathbb{F}}_{16}$, and $\boxed{{\mathrm{Gal}}_{{\mathbb{F}}_2}\cong C_4}$, generated by Frobenius.

Modulo three it factors as $(x-1)(x^3+x^2+x+2)$. The cubic has no root at zero, one or two and is irreducible, so its splitting field is ${\mathbb{F}}_{27}$ and $\boxed{{\mathrm{Gal}}_{{\mathbb{F}}_3}\cong C_3}$. Both reductions are square-free. Irreducibility modulo two makes the rational quartic irreducible, and its rational Galois group is transitive on four roots. The unramified factorization theorem supplies a four-cycle from the modulo-two reduction and a three-cycle from the modulo-three reduction. Its order is divisible by twelve and divides twenty-four. An order-twelve subgroup would have index two and equal $A_4$, which has no four-cycle. Thus $\boxed{{\mathrm{Gal}}_{\mathbb{Q}}\cong S_4}$.

Every group element has a unique form $a^r{b}^s$, with $r\mathrm{mod}7$ and $s\mathrm{mod}3$. Conjugation by $b$ doubles the exponent of $a$, giving the two orbits $\{1,2,4\}$ and $\{3,6,5\}$. Conjugation by powers of $a$ runs through all seven elements of each nonidentity coset of $⟨a⟩$. The classes are thereforeTheir sizes $1,3,3,7,7$ sum to twenty-one.