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

Write $n=2^{r}m$ with $m$ odd. If $m>1$, the polynomial factor of $X^m+1$ by $X+1$, evaluated at $X=10^{2^r}$, supplies a proper divisor. Therefore $n$ must be a power of two. Conversely this is only a necessary condition for primality testing.

For a prime factor $p$ of the number, $p$ is odd and does not divide $10$. Its multiplicative order $d$ satisfies $d\mid 2n$ but $d\nmid n$, since $10^n\equiv -1(\mathrm{mod}p)$. When $n$ is a power of two, every proper divisor of $2n$ divides $n$, so $d=2n$. By Lagrange theorem in the multiplicative group of a finite field, $2n\mid p-1$. Thus $\boxed{p\equiv 1(\mathrm{mod}2n)}$.

The Fermat factorization method searches for a difference of two squares: starting at $a=\lceil \sqrt{N}\rceil$, increase $a$ until $a^2-N=b^2$, and return $(a-b)(a+b)$. Every factorization of an odd integer has this form, with $a=(d+e)/2$ and $b=(e-d)/2$. For $N=10001$, the successive differences at $a=101,102,103,104,105$ are $200,403,608,815,1024$. The last is $32^2$, giving $\boxed{10001=73\cdot 137}$. Trial division by the primes up to their respective square roots confirms that both factors are prime.

For nonempty compact sets, define the distance from a point to a closed set by $d(x,B)={\min }_{b\in B}|x-b|$ and the Hausdorff distance byThe minima and suprema exist: the sets are nonempty and compact, and the distance function is Lipschitz continuous. The Hausdorff distance is finite, nonnegative and symmetric. If it is zero, every point of $A$ belongs to the closed set $B$ and conversely, so $A=B$; the converse is immediate.

For $a\in A$, choose $b\in B$ attaining $d(a,B)$ and then $c\in C$ attaining $d(b,C)$. The triangle inequality gives $d(a,C)\le d(a,B)+d_H(B,C)$. Taking the supremum over $a$, and doing the same with $A,C$ exchanged, proves $d_H(A,C)\le d_H(A,B)+d_H(B,C)$. Hence this is a metric.

The nested compact sets have the finite intersection property inside $K_1$, so $K=\bigcap K_n$ is nonempty. It is a closed subset of $K_1$ and therefore compact. Because $K\subseteq K_n$, only ${\sup }_{x\in K_n}d(x,K)$ contributes to the Hausdorff distance. If this did not tend to zero, some increasing indices $n_j$ and $x_j\in K_{n_j}$ would satisfy $d(x_j,K)\ge ϵ>0$. A convergent subsequence in $K_1$ has limit $x$. For each fixed $m$, its tail belongs to the closed set $K_m$, so $x\in K$. But then $d(x_j,K)\le |x_j-x|\to 0$, a contradiction. Thus $\boxed{d_H(K_n,K)\to 0}$.

Work over the finite field ${\mathbb{F}}_2$. Reduce polynomials modulo $X_i^2-X_i$, so their monomials are square-free. The binary Reed-Muller code $\mathrm{RM}(r,m)$ consists of the evaluation vectors of polynomials of degree at most $r$ at all $2^m$ points of ${\mathbb{F}}_2^m$, in a fixed order. This is a linear code of length $2^m$ and dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{m}{j}\right)$, for $0\le r\le m$. Square-free monomials give independent evaluation functions, as follows inductively by splitting according to the last variable.

The minimum Hamming distance of a linear code equals its least nonzero Hamming weight. The result isHere $r=0$ is the repetition code, while $r=m$ is the full binary vector space and has distance one. For the induction step, write $f(x,t)=u(x)+tv(x)$, where $\mathrm{deg}u\le r$ and $\mathrm{deg}v\le r-1$. Its evaluation vector is $(u,u+v)$, the Reed-Muller bar-product recursion. If $v=0$, its nonzero Hamming weight is at least $2d(r,m-1)=2^{m-r}$, with the full-space endpoint treated as above. If $v\ne 0$, every position where $v=1$ contributes exactly one to the sum of the two weights; hence the weight is at least $\mathrm{wt}(v)\ge 2^{(m-1)-(r-1)}=2^{m-r}$. The monomial $X_1\cdots X_r$ is one exactly on $2^{m-r}$ points, attaining the bound. Degrees greater than $m$ give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.

This is a generalized linear model with independent Bernoulli distributions for the responses and the logit link. Under treatment coding with colour one as the reference level, the linear predictor isColour is a categorical variable, not a numerical trend. Width has the same slope for every colour, since no interaction term is fitted. The parameters are estimated by maximum likelihood estimation.

The approximate Wald confidence interval for the width coefficient is $\boxed{0.46\pm 1.96(0.106)}$, or approximately $(0.2522,0.6678)$. This uses the approximate normal distribution of the maximum-likelihood estimator, rather than a confidence interval for an individual binary response.

For the requested crab, the fitted linear predictor is $\hat{\eta }=-11.38-0.22+0.46(20)=-2.40$. Applying the inverse logit link gives $\boxed{\hat{p}=(1+e^{2.40}{)}^{-1}\simeq 0.0832}$. The rounded displayed coefficients need not reproduce the reported test statistics exactly.

Put $x=1+y$ and retain linear terms. The delay differential equation is $\dot{y}(t)=-\alpha y(t-T)$, with characteristic equation of a delay differential equation $\lambda +\alpha e^{-\lambda T}=0$. Write $z=\lambda T$ and $q=\alpha T$. If a root has $\mathrm{Re}z\ge 0$, then $|z|=q{e}^{-\mathrm{Re}z}\le q$. Writing $z=a+ib$ gives $a=-q{e}^{-a}\cos b$. For $q<\pi /2$, $|b|<\pi /2$ and the right side is negative, contradicting $a\ge 0$. All characteristic roots therefore lie in the left half-plane.

An imaginary root $z=ib$ requires $\cos b=0$ and $b=q\sin b$. The first crossing is $q=\pi /2$, $z=\pm i\pi /2$. Implicit differentiation gives $dz/dq=-e^{-z}/(1+z)$, whose real part at the positive crossing is $(\pi /2)/(1+{\pi }^2/4)>0$. The later imaginary crossings occur at $q=\pi /2+2\pi k$ and also enter the right half-plane. Thus the equilibrium is locally exponentially asymptotically stable whenand unstable when $\alpha T>\pi /2$. At equality the linearized equation has neutral oscillatory modes; it is the Hopf bifurcation threshold. If stability is meant for the nonlinear equation itself, the borderline can also be resolved. In dimensionless time $s=t/T$, let $q_0=\pi /2$. A small center oscillation has the form $y=R\cos \theta +R^2(\cos 2\theta /5+\sin 2\theta /10)+O(R^3)$. Substitution at quadratic order gives these second-harmonic coefficients. At cubic order the fundamental forcing is $q_0{R}^3(\cos \theta /20+3\sin \theta /20)$. Projection onto the center mode divides the complex forcing by the characteristic derivative $1+i{q}_0$, yielding the Hopf normal form amplitude equationIts cubic coefficient is negative, so the equilibrium at equality is locally asymptotically stable, with algebraic rather than exponential decay. Thus the usual strictly decaying linear condition is $\alpha T<\pi /2$, while nonlinear local asymptotic stability includes $\alpha T=\pi /2$. The purely imaginary linear modes alone would not justify that borderline conclusion.

The delayed positive term models recruitment depending on the population a time $T$ earlier; the quadratic negative term represents instantaneous density-dependent losses. Thus this delay differential equation delays recruitment rather than the strength of crowding acting on the present population.

With $x=1+y$, the linearized equation is $\dot{y}=\alpha y(t-T)-2\alpha y(t)$. Its characteristic equation of a delay differential equation is $\lambda +2\alpha =\alpha e^{-\lambda T}$. A root with nonnegative real part would satisfy $|\lambda +2\alpha |\ge 2\alpha$, whereas $|\alpha e^{-\lambda T}|\le \alpha$. This is impossible. Consequently the equilibrium is locally exponentially asymptotically stable for every $\alpha >0$ and $T>0$. There is no upper bound on $\alpha T$ in this model.

The Papperitz symbol describes a homogeneous second-order Fuchsian differential equation on the Riemann sphere, with three regular singular points and the two indicial exponents at each. At a finite point $z_j$, an exponent $r$ corresponds locally to a factor $(z-z_j{)}^r$; at infinity it corresponds to $z^{-r}$. Repeated or resonant exponents can require logarithms. The six exponents obey the Fuchs relation that their sum is one. With three singularities there is no independent accessory parameter, so these data determine the normalized equation.

A Möbius transformation of a Papperitz symbol moves the singular points without changing their exponents. Multiplication of the dependent variable by a local power shifts the two exponents by that power, using the reciprocal local coordinate at infinity.

Set $w=z/(z-1)$ and $v(w)=F(a,c-b,c;w)$. At $w=0,1,\infty$, the exponent pairs for $v$ are respectively $(0,1-c)$, $(0,b-a)$, and $(a,c-b)$. The Möbius transformation sends $z=0,1,\infty$ to $w=0,\infty ,1$. Before rescaling, $v(w(z))$ therefore has exponent pairs $(0,1-c)$ at zero, $(a,c-b)$ at one, and $(0,b-a)$ at infinity. Multiplication by $(1-z{)}^{-a}$ subtracts $a$ at one and adds $a$ at infinity. The resulting pairs areexactly those of the original Gauss hypergeometric equation. Near zero choose the branch with $(1-z{)}^{-a}=1$ at zero. The resulting solution is analytic there and has value one. Uniqueness of the normalized analytic solution yieldsThis is the Pfaff transformation. The normalization presupposes the usual admissible parameters, in particular $c\notin \{0,-1,-2,\dots \}$. Elsewhere the identity holds by analytic continuation with compatible branches, or by parameter limits wherever those are defined.

Let $x_1,x_2,x_3$ be longitudinal displacements from equilibrium. The original diagram has masses $m,2m,m$, and no attachments to fixed walls. The Lagrangian isThe Euler-Lagrange equations giveThe forces sum to zero, consistent with momentum conservation for an isolated molecule.

For a normal mode write $x_j=A_j{e}^{i\omega t}$. The generalized eigenvalue problem isThe three independent eigenvectors and corresponding squared frequencies areThe last two have zero mass-weighted displacement and are orthogonal in the mass inner product. The lowest frequency is zero: it represents a rigid translation with both springs unchanged. Its general motion includes uniform centre-of-mass velocity, not just a constant displacement. Superpositions of the two oscillatory normal modes and this translation give the general solution.

The effective number of relativistic energy degrees of freedom count two photon polarizations, four electron/positron spin states, and six neutrino/antineutrino states, with the Fermi-Dirac distribution factor $7/8$ for fermions. Treating these species as relativistic and at a common temperature gives $\boxed{g_{\ast }=2+(7/8)(4+6)=10.75}$.

The mass-equivalent radiation mass density is $\rho =({\pi }^2/30)g_{\ast }(k_{B}T{)}^4/({\hslash }^3{c}^5)$. Therefore the Friedmann equation givesAt $T_0=10^{10}\mathrm{K}$, $H_0\simeq 0.503{\mathrm{s}}^{-1}$. Equating the specified weak interaction rate to $H_0(T/T_0{)}^2$ gives $(T_{\ast }/T_0{)}^3=H_0/(1{\mathrm{s}}^{-1})$ and henceThe approximate equilibrium neutron-to-proton ratio, neglecting chemical potentials, is $r_{\ast }\simeq \exp [-(m_n-m_p)c^2/(k_B{T}_{\ast })]$, about $0.152$ using the mass difference $1.293\mathrm{MeV}$. This is a freeze-out estimate rather than a detailed reaction-network computation.

After weak cosmological weak freeze-out, free neutrons undergo beta-minus decay; neutrinos decouple, and electron-positron annihilation heats the photons relative to the neutrinos. Initially the abundant energetic photons destroy deuterium almost as soon as it forms. Once the deuterium bottleneck ends, nuclear reactions rapidly pass through deuterium, tritium and helium-three to helium-4. Reactions eventually become too slow compared with cosmic expansion; nearly all surviving neutrons are bound in helium-four. Its mass fraction is approximately $Y_4=2r/(1+r)$, where $r$ is evaluated when nuclear assembly begins.

Increasing $g_{\ast }$ increases the Hubble parameter, raises $T_{\ast }$, increases the freeze-out neutron-to-proton ratio, and leaves less time for free-neutron decay after freeze-out. Both effects increase $Y_4$; decreasing $g_{\ast }$ reverses them. Most deuterium is only an intermediate product and is burned into helium, so its residual abundance and its absolute change are tiny compared with the helium mass fraction. This does not imply a negligible fractional change in residual deuterium. Faster expansion also shortens the time available to burn it, and its relative abundance can be appreciably sensitive to extra radiation. The distinction matters when interpreting the final wording of the question; joint deuterium and helium abundances constrain extra relativistic species, as discussed in the Particle Data Group nucleosynthesis review.

The Chinese remainder theorem says that for pairwise coprime positive moduli $n_i$, arbitrary residue classes modulo each $n_i$ specify one residue class modulo ${\prod }_i{n}_i$. For an odd positive integer $N=\prod p_i^{e_i}$, the Jacobi symbol is $(a/N)={\prod }_i(a/p_i{)}^{e_i}$, where each factor is a Legendre symbol; for $N=1$ the empty product is one. The Jacobi symbol is multiplicative in $a$, and is zero exactly when $a$ and $N$ have a common prime factor.

False. The Jacobi symbol $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, yet $2$ is not a quadratic residue modulo three. A solution modulo fifteen would give one modulo three, which is impossible. A positive Jacobi symbol need not indicate a square modulo a composite modulus.

True. Since $N$ is not a square, some exponent $e_i$ is odd. Choose a quadratic nonresidue modulo that $p_i$ and choose residue one at every other prime. The Chinese remainder theorem produces a unit $b$ modulo $N$ with $(b/N)=-1$. Multiplication by $b$ permutes the residue classes modulo $N$. Thus, by multiplicativity of the Jacobi symbol,The sum is therefore $\boxed{0}$. Nonunits contribute zero, so the permutation argument covers every term.

False. The Carmichael number $561=3\cdot 11\cdot 17$ supplies a counterexample. For every $a$ coprime to $561$, the Fermat little theorem gives $a^{560}\equiv 1$ modulo each of these primes, since $2,10,16$ all divide $560$. The Chinese remainder theorem then gives $a^{560}\equiv 1(\mathrm{mod}561)$. Thus the proposed Fermat primality test can fail to detect a composite for every coprime base.

True. First suppose $p^e\mid N$ with $e\ge 2$ maximal. By the Chinese remainder theorem, choose $a\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $a\equiv 1$ modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For $m=(N-1)/2$, the binomial theorem givesbecause $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.

If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a quadratic nonresidue at one prime $p$ and one at every other prime, again using the Chinese remainder theorem. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv 1\not\equiv -1(\mathrm{mod}q)$. These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.

Write $R_j=I-P_{-j}$. Minimizing the residual sum of squares first over the coefficients of $X_{-j}$ reduces the problem to minimizing $\Vert R_{j}Y-b{R}_j{X}_j{\Vert }^2$. Full column rank ensures $R_j{X}_j\ne 0$. Thus the partial regression formula and its variance areThis uses $R_j^T=R_j=R_j^2$ and the isotropic error covariance matrix ${\sigma }^{2}I$.

Since the span of $X_k$ is contained in the column space of $X_{-j}$, orthogonal projection onto the latter removes at least as much squared norm. Consequentlyand inversion proves the requested lower bound. Full rank makes the denominator positive.

Adding $c{1}_n$ to column $j\ge 2$ leaves the column space unchanged. Every old fitted vector is reproduced by keeping all slopes unchanged and replacing the regression intercept by ${\hat{\beta }}_1-c{\hat{\beta }}_j$. Uniqueness of the ordinary least squares estimators then proves that slope $j$ is unchanged. In particular all columns can be centered by such changes. Applying the previous projection argument to the centered design proves the bound with $X_j-{\bar{X}}_j{1}_n$ and $X_k-{\bar{X}}_k{1}_n$; the normalized inner product is now the usual sample correlation.

Each reported coefficient test is the two-sided Student's t-test of $H_0:{\beta }_j=0$ against $H_1:{\beta }_j\ne 0$, conditional on the other predictors. Under the null, ${\hat{\beta }}_j/(\hat{\sigma }\sqrt{(X^{T}X{)}_{jj}^{-1}})$ has a Student's t-distribution with $100-3=97$ degrees of freedom. At five percent the intercept is significant, but neither individual test slope is. The final F-test compares the full model against an intercept-only model: $H_0:{\beta }_{\mathrm{Maths}}={\beta }_{\mathrm{Stats}}=0$. It has $(2,97)$ degrees of freedom and rejects at five percent, since its $p$-value is $0.003166$. Thus the predictors jointly explain variation, without strong evidence separating their individual conditional effects.

The two test predictors have sample correlation $0.9371630$, although each has only moderate correlation with the final exam response. The variance inflation factor is $1/(1-0.9371630^2)\simeq 8.22$. Their nearly shared direction produces substantial multicollinearity, inflating the individual slope standard errors. The joint F-test can detect this common predictive direction even though either coefficient, given the other, has a large $p$-value.

For a smooth test function $f$, integration by parts in the Fokker-Planck equation givesWe use the decay and absence of boundary flux intended in the question, sufficiently strong to remove the moment-weighted boundary terms. For $f=x_k$, only ${\partial }_{i}f={\delta }_{ik}$ survives, giving $d⟨x_k⟩/dt=⟨A_k⟩$. For $f=x_k{x}_l$, the first derivative is ${\delta }_{ik}{x}_l+{\delta }_{il}{x}_k$ and the second is ${\delta }_{ik}{\delta }_{jl}+{\delta }_{il}{\delta }_{jk}$. The Fokker-Planck diffusion matrix is symmetric, soThe factor one-half cancels the two equal diffusion contributions, including when $k=l$.

Let $\xi =x-⟨x⟩$ and $C_{ij}=⟨{\xi }_i{\xi }_j⟩$. In the linear noise approximation, $A_i=a_{ik}{\xi }_k$ and $B_{ij}=b_{ij}$. At the stationary mean, the preceding moment identity gives ${\dot{C}}_{ij}=a_{ik}{C}_{kj}+a_{jk}{C}_{ik}+b_{ij}$. Hence the stationary covariance matrix solves the Continuous Lyapunov equationwhich is precisely the requested component formula because $C$ is symmetric.

The three jump vectors and their rates are $(1,0)$ at rate $\lambda$, $(-1,1)$ at rate $\gamma x_1$, and $(0,-1)$ at rate $\beta x_2$. Summing rate times jump gives the Fokker-Planck drift vector, while summing rate times the outer product of the jump gives the Fokker-Planck diffusion matrix:The maturation event simultaneously decreases larvae and increases adults; this accounts for the negative off-diagonal entries. Since $A$ is affine, its expectation is its value at the mean. Setting both mean derivatives to zero yields $\boxed{⟨x_1⟩=\lambda /\gamma ,⟨x_2⟩=\lambda /\beta }$.

At the stationary mean,The $(1,1)$ entry of the Continuous Lyapunov equation gives $-2\gamma C_{11}+2\lambda =0$, so $C_{11}=\lambda /\gamma$. Its $(1,2)$ entry gives $\gamma C_{11}-(\gamma +\beta )C_{12}-\lambda =0$, hence $C_{12}=0$. Finally $(2,2)$ gives $2\gamma C_{12}-2\beta C_{22}+2\lambda =0$. ThusBoth variances equal their means; the absence of stationary covariance does not mean that the maturation jumps are independent events in the two populations.

In a frame centered at the fixed point or centre of mass, a rotating material point has velocity $\dot{r}=\omega \times r$. The identity $|\omega \times r{|}^2=|\omega {|}^2|r{|}^2-(\omega \cdot r{)}^2$ converts the rotational kinetic energy into $T=\frac{1}{2}{\omega }_i{I}_{ij}{\omega }_j$, where the inertia tensor isLikewise integrating $r\times (\omega \times r)$ gives the angular momentum $\boxed{L=I\omega }$. These expressions refer to rotational motion about the chosen origin.

In principal axes, $2E=\sum I_i{\omega }_i^2$ and $L^2=\sum I_i^2{\omega }_i^2$. Substitute the Euler equations for a torque-free rigid body:For the squared angular momentum,Thus both $E$ and $L^2$ are conserved, even though the body-frame components of $L$ generally change.

Place the origin at the centre and the axes along the edges. Symmetry makes the off-diagonal entries of the inertia tensor zero. Uniform density gives $⟨x^2⟩=a^2/12$, $⟨y^2⟩=b^2/12$, $⟨z^2⟩=c^2/12$. Consequently the principal moments of inertia areFor example $I_1=\rho \int (y^2+z^2)dxdydz$ gives the first expression directly.

Here $(I_1,I_2,I_3)=(20,17,5)M{a}^2/12$, so $I_1>I_2>I_3$ and $e_2$ is the intermediate axis. Eliminating the other components from $L^2=2I_{2}E$ and the conservation of energy relation gives, with $J=2E-I_2{\omega }_2^2$,Thus the second Euler equations for a torque-free rigid body reduces toThe sign is minus the sign of ${\omega }_1{\omega }_3$; it is constant along a nontrivial branch. Let $\Omega =\sqrt{24E/(17M{a}^2)}$. Since ${\omega }_2(0)=0$, integration yields ${\omega }_2(t)=\pm \Omega \tanh (3\Omega t/5)$, with the same sign as in the scalar equation. The remaining components areTheir initial squares are fixed by the preceding algebraic formulas with $J=2E$; their initial signs determine the branch. Hence $\boxed{\omega (t)⟶\pm \Omega e_2}$ as $t\to \infty$. This trajectory is an intermediate-axis separatrix: approaching intermediate-axis rotation on this special conserved-energy level does not make that rotation stable to generic perturbations. If $E=0$, all components vanish identically.

The Axiom of foundation states that every nonempty set $A$ has a member $a$ with $a\cap A=\varnothing$. The principle of epsilon induction states that a formula $\varphi$ satisfying $\forall x[(\forall y\in x\varphi (y))\Rightarrow \varphi (x)]$ holds for every set $x$.

Assume Axiom of foundation and suppose a progressive formula has a counterexample $a$. In the transitive closure of $\{a\}$, use axiom schema of separation to collect the counterexamples into a nonempty set $B$. Foundation supplies $b\in B$ having no member in $B$. Since the closure is transitive, every member of $b$ satisfies $\varphi$, contradicting progressiveness. Conversely, if a nonempty set $A$ had no foundation-minimal member, every $x\in A$ would have a member $y\in x\cap A$. The formula $x\notin A$ is then progressive: if every member of $x$ lies outside $A$, $x$ cannot belong to $A$. Epsilon induction would make $A$ empty, a contradiction. This proves equivalence in the presence of the other Zermelo–Fraenkel set theory.

To obtain the cumulative hierarchy, perform epsilon induction on the assertion that $x$ belongs to some $V_{\alpha }$. If this holds for each member $y$, Axiom schema of replacement collects their least such ordinals into a set. Choose an ordinal $\beta$ above them all. Then $x\subseteq V_{\beta }$ and $x\in V_{\beta +1}$. Thus every set occurs in the hierarchy. Use the rank of a set convention $\mathrm{rk}(x)={\sup }_{y\in x}(\mathrm{rk}(y)+1)$, equivalently the least $\alpha$ with $x\subseteq V_{\alpha }$.

An ordinal has rank equal to itself. Thus the rank of a set here is $\sup \{\omega +2,\omega +3,\omega +4\}=\boxed{\omega +4}$.

Use the Kuratowski ordered pair $(m,n)=\{\{m\},\{m,n\}\}$. Its rank of a set is $\max (m,n)+2$. Every pair in the Cartesian product has finite rank, but those ranks are unbounded in $\omega$. Therefore $\mathrm{rk}(\omega \times \omega )={\sup }_{m,n<\omega }(\max (m,n)+3)=\boxed{\omega }$.

Represent a function by its graph of Kuratowski ordered pairs. For $f:\omega \to {\omega }^2$,The bound is attained by $f(n)=\omega n$, which is a cofinal function into ${\omega }^2$. Taking the rank of the set of all such functions adds one at this attained maximum. Thus $\boxed{\mathrm{rk}(({\omega }^2{)}^{\omega })={\omega }^2+1}$. The extra successor is essential: unlike the previous product, this set actually contains a member of rank ${\omega }^2$.

A matching in a graph from $X$ to $Y$ is a collection of edges with disjoint endpoints covering every vertex of $X$; equivalently it chooses a distinct neighbour in $Y$ for each $x\in X$. For a finite bipartite graph, the Hall marriage theorem says this exists exactly when $|N(A)|\ge |A|$ for every $A\subseteq X$. Necessity follows by counting the distinct matched neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ is tight, $|N(A)|=|A|$, Hall's condition holds on $(A,N(A))$. It also holds on $(X\setminus A,Y\setminus N(A))$: for $B\subseteq X\setminus A$, the original condition applied to $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$. Induction provides two disjoint matching in a graph whose union covers $X$. If no nonempty proper subset is tight, choose an edge $xy$, possible by Hall's condition. Delete its endpoints. Each nonempty subset of $X\setminus \{x\}$ had at least one extra neighbour, so deleting $y$ leaves Hall's condition intact. Induction and then the edge $xy$ finish the proof. The single-vertex case is immediate.

For the degree condition, fix $A\subseteq X$ and double-count with weights:Every denominator is nonzero; the last inequality uses $d(y)\le d(x)$ along each edge. The Hall marriage theorem therefore proves the required matching exists. Finiteness, as in the usual course version of the theorem, is understood; the same proof covers a finite $X$ with arbitrary $Y$ and finite degrees.