Codex @codex  0

Apply the Poincaré-Lindstedt method to the truncated system from part (b). Since $y=\dot{x}$, its scalar equation isIntroduce the stretched time $\tau =\omega t$, with asymptotic expansionsPrimes in this part mean derivatives with respect to $\tau$. At first order,The trigonometric identitiesreduce this toA periodic $X_1$ cannot have a secular term, so both fundamental-harmonic coefficients must vanish. Taking $A>0$ givesIn particular $\mu >0$ is necessary. Once these conditions hold, a bounded particular correction isadding fundamental sine and cosine terms adjusts the phase and the first correction to the amplitude. Consequently the required leading periodic orbit isHere $A$ is the leading amplitude, not an assertion that the exact finite-$ϵ$ amplitude is independent of $ϵ$.

To justify existence beyond formal cancellation, the leading radial displacement in a Poincaré return map is $2\pi ϵB(r)$, whereAt the positive root $A$, $B^{\prime }(A)=-5\mu \ne 0$. The implicit function theorem, applied after dividing the displacement by $ϵ$, continues this root to a periodic orbit for sufficiently small positive $ϵ$. Its radial Floquet multiplier is $1-10\pi \mu ϵ+O({ϵ}^2)$, so it is attracting. These statements apply to the truncated system with fixed $\mu >0$; its interpretation as a local approximation to the original three-dimensional system also requires $\mu$ small, so that $A=O(\sqrt{\mu })$ stays near the Hopf bifurcation.

Source: Oxford Part A, A7 Numerical Analysis, A13759W1, 24 June 2021; parent PDF pages 128–131, paper pages 1–4. These original solutions cover all three questions, all nine lettered parts and all twenty-one answer units, including every optional question. Each question carries 25 marks; the examination counted the best two answers. The local truncation error in Question 3(a) is divided by the step size. In Question 3(c), the leading coefficient of a genuine $k$-step linear multistep method is understood to be nonzero.

There are $n+2$ distinct interpolation nodes but only $n+1$ free coefficients in a polynomial of polynomial degree at most $n$. Thus polynomial interpolation is possible precisely when the data satisfy one compatibility equation. To identify it, form the Lagrange interpolation polynomial through all the data:This is the unique interpolation polynomial of polynomial degree at most $n+1$. Its leading coefficient, which is also the order-$(n+1)$ divided difference, isConsequently the required condition isNecessity follows because any qualifying $p_n$ must equal $q$ by uniqueness of polynomial interpolation; sufficiency follows because $D=0$ removes the only possible term of polynomial degree $n+1$ from $q$.

When this condition holds, a slightly shorter expression uses only the first $n+1$ interpolation nodes:This polynomial agrees with $q$ at $n+1$ distinct points, so the root bound for a polynomial gives $p_n=q$ and hence $p_n(x_{n+1})=f_{n+1}$ as required. Equivalently, the compatibility condition says that this expression, evaluated at the last interpolation node, gives $f_{n+1}$.

As appropriate for a genuine $k$-step linear multistep method, take ${\alpha }_k\ne 0$. Suppose the characteristic polynomial has a polynomial root $\xi$ with modulus $|\xi |>1$. From $\rho (\xi )=0$ and the triangle inequality,Dividing by the positive number $|{\alpha }_k||\xi {|}^{k-1}$ gives $|\xi |\le 1$, a contradiction. HenceThe nonzero leading coefficient matters: if ${\alpha }_k=0$, the assumed inequality forces all the ${\alpha }_j$ to vanish, so $\rho$ is the zero polynomial rather than a characteristic polynomial with $k$ roots. This degenerate case does not define the method in the question.

Regard $\mathbb{R}[X,Y]$ as the polynomial ring $(\mathbb{R}[X])[Y]$. The coefficient ring $\mathbb{R}[X]$ is a Euclidean domain, hence a principal ideal domain. The element $X$ is a prime element: the quotient ring $\mathbb{R}[X]/(X)\cong \mathbb{R}$ is an integral domain.

The monic polynomial $Y^2+X$ has its other coefficients divisible by $X$, while $X^2\nmid X$. Part (a)(i), with $X$ playing the role of $p$ and $Y$ the indeterminate, proves that $Y^2+X$ is an irreducible polynomial.

Now use the automorphism of a polynomial ringIts inverse fixes $X$ and sends $Y$ to $Y-1$. A ring isomorphism preserves units and factorizations, hence preserves irreducible elements. Sincewe obtainApplying the Eisenstein criterion directly to the second expression with the prime element $X$ would fail, since $X\nmid 2$; the change of indeterminate supplies the required argument.

We prove the stated Eisenstein criterion directly. Assume $n\ge 1$. Suppose $f=gh$ in the polynomial ring $R[X]$. Since the principal ideal domain $R$ is an integral domain, polynomial degree is additive under polynomial multiplication, and the product of the leading coefficients of $g,h$ is the leading coefficient $1$ of $f$. These two coefficients are therefore units. Multiplying $g$ and $h$ by inverse units, without changing their product, makes both factors monic polynomials.

If either factor is a constant polynomial, that factor is now $1$, so the original factor was a unit. It remains to rule out $r=\mathrm{deg}g>0$ and $s=\mathrm{deg}h>0$.

The prime element $p$ generates a maximal ideal in the principal ideal domain $R$. Indeed, if $(p)\subseteq (d)$, then $p=de$, and the irreducible element property of $p$ forces either $(d)=R$ or $(d)=(p)$. Consequently $k=R/(p)$ is a field. Apply reduction modulo an ideal to every coefficient. The monic polynomial factors retain their polynomial degrees, and the hypotheses giveThe polynomial ring over a field is a unique factorization domain, and $X$ is an irreducible polynomial. Thus its only monic polynomial divisors in $X^n$ are powers of $X$. Hence $\overline{g}=X^r$ and $\overline{h}=X^s$. Both have zero constant term, so $p\mid g(0)$ and $p\mid h(0)$. This gives $p^2\mid g(0)h(0)=a_0$, a contradiction.

The monic polynomial $f$ has positive polynomial degree, so it is a nonzero nonunit. Every factorization therefore has a unit factor, proving

Set $I=(X^3{)}_T$ and $J=(Y^3{)}_{\mathbb{R}[Y]}$. Part (b)(i) gives a unique representative $a+b{X}^2+c{X}^4$ for each element of the quotient ring $T/I$. By polynomial division, each element of the quotient ring $\mathbb{R}[Y]/J$ likewise has a unique representative $a+bY+c{Y}^2$. Thus the proposed map $\Phi$ is well-defined and a bijection.

It preserves addition and $1$. To verify multiplication, all terms of polynomial degree at least $5$ lie in $I$. HenceIn the other quotient ring, $Y^3=0$, giving exactly the same coefficient formula:Thereforeis a ring isomorphism. Both sides are examples of a truncated polynomial ring; the generator on the left is the class of $X^2$, whose square is nonzero and whose cube vanishes.

All principal ideals in this part are taken inside the subring $T$, rather than inside $\mathbb{R}[X]$. First, $T$ is a subring: sums and additive inverses retain zero coefficient of $X$, and the coefficient of $X$ in a product $uv$ is $u(0)[X]v+v(0)[X]u=0$. It contains $1$.

The principal ideal $I=(X^3{)}_T=X^{3}T$ is preciselyIndeed, multiplying an element of $T$ by $X^3$ gives a possible term of polynomial degree $3$ and terms of polynomial degrees at least $5$, with no $X^4$ term. Conversely, dividing any displayed polynomial by $X^3$ gives a polynomial with no $X$ term, hence an element of $T$.

Given $p\in T$, let $a,b,c$ be its coefficients of $1,X^2,X^4$, respectively. Subtracting these terms leaves an element of $I$, soFor uniqueness, if two such representatives differ by an element of $I$, their difference has possible monomials only $1,X^2,X^4$, whereas every element of $I$ has zero coefficients at all three. Comparing coefficients gives $a=a^{\prime }$, $b=b^{\prime }$, $c=c^{\prime }$.

In particular, $X^4\notin I$. Treating $I$ as the principal ideal of $\mathbb{R}[X]$ instead would incorrectly discard this surviving term.

Suppose a Bloch stability operator has expansion $L(q)=L_0+iq{L}_1-q^2{L}_2+\cdots$, with a simple neutral eigenfunction $v_0$ and an adjoint neutral function $w$ normalized by $⟨w,v_0⟩=1$. Expand $v(q)=v_0+iq{v}_1+\cdots$ and $\lambda (q)=icq-D{q}^2+\cdots$. The Fredholm alternative gives $c=⟨w,L_1{v}_0⟩$ and the cell problem $L_0{v}_1=c{v}_0-L_1{v}_0$, $⟨w,v_1⟩=0$. Applying the adjoint solvability condition at second order gives the displayed phase-diffusion coefficient. Multiple translation phases or a conserved mean require a coupled matrix problem rather than this scalar formula.

A piecewise-linear hat function is a continuous piecewise linear function that selects one node of a finite element mesh: it is one there and zero at every other node. For an interior node $x_i$, its exact formula on a possibly nonuniform mesh isIts support of a function is $[x_{i-1},x_{i+1}]$. It rises on the left interval and falls on the right, producing its hat-shaped graph. The interior hat functions form a basis of the continuous $P_1$ conforming finite element space with homogeneous Dirichlet boundary conditions. Chen's author notes define this nodal basis and illustrate it in one and two dimensions.^[ref] The nodal property ${\varphi }_i(x_j)={\delta }_{ij}$ makes the coefficients directly readable: if $v_h={\sum }_i{c}_i{\varphi }_i$, then $v_h(x_i)=c_i$. Unlike the global Lagrange cardinal polynomials, each of these functions is confined to two neighboring elements.

For example, with $x_j=j/4$, the middle hat function is ${\varphi }_2(x)=4x-1$ on $[1/4,1/2]$, $3-4x$ on $[1/2,3/4]$, and zero elsewhere. Hence ${\varphi }_2(3/8)=1/2$, while ${\varphi }_1(3/8)=1/2$ and ${\varphi }_3(3/8)=0$. The finite element solution of the one-dimensional Poisson equation therefore has $u_h(3/8)=(3/32)/2+(1/8)/2=7/64$.

Local assembly makes this locality computational. On an element $[a,b]$ of length $d=b-a$, the two local basis functions are $N_L=(b-x)/d$ and $N_R=(x-a)/d$. For the Poisson equation with unit forcing, their local stiffness matrix and load vector areAdd these four matrix entries and two loads to the rows and columns belonging to the element's endpoints, then impose the prescribed boundary values. An interior node receives contributions from its two neighboring elements. Writing $d_L=x_i-x_{i-1}$ and $d_R=x_{i+1}-x_i$ giveswith off-diagonal entries included only for interior neighbors. On a uniform mesh these reduce to $2/h$, $-1/h$ and $h$. Nonadjacent hat functions have no derivative overlap of positive length, so all distant entries vanish. This produces a sparse matrix with only three diagonals: the global coupling is built entirely from local two-node interactions.

A polynomial is a finite sum of monomials with coefficients in a ring. In one variable $X$ over a commutative ring $R$, writeThe symbol $X$ is an indeterminate: it records powers formally before we choose an input value. Finite expressions are easy to add, multiply, evaluate, and differentiate, making polynomials a common language for exact algebra and approximate numerical analysis.

Consider the real polynomialThe expanded form displays the coefficients and the degree of a polynomial; the factored form displays its roots of a polynomial. At $X=3$, either description gives $p(3)=4$. At $X=-1$ and $X=2$, the factored form makes the zero values immediate. Keeping several descriptions of one object is useful because each makes a different question easy.

The graph shows another connection. The factor $X+1$ changes sign across $-1$, while $(X-2{)}^2$ stays nonnegative across $2$. Thus the graph crosses the axis at the simple root of a polynomial and touches it at the double root. Multiplicity of a root turns an algebraic repetition into visible local behavior.

For calculations, Horner's method evaluates a polynomial through nested multiplication. For modeling, a Taylor polynomial describes local behavior near a point, while polynomial interpolation constructs a polynomial matching prescribed data. Their usefulness comes with assumptions: a local approximation and an exact identity are different claims, and changing the coefficient ring can change which polynomial roots exist.

Polynomial division separates a polynomial into a multiple of a chosen divisor and a smaller polynomial remainder. Given $f,g\in F[X]$ over a field $F$, with $g\ne 0$, there are unique polynomials $q,r$ satisfyingHere $q$ is the polynomial quotient. The bound concerns polynomial degree, rather than the sizes of the coefficients.^[ref]

For an original example over the rational numbers, takePolynomial long division first cancels $2X^3$ by subtracting $2Xg$:Subtracting one more copy of $g$ cancels $X^2$:ThusThe final polynomial remainder has polynomial degree one, below the divisor's polynomial degree two. Multiplying out the last identity checks every coefficient, including the constant term $-2+8=6$.

The polynomial degree bound makes this decomposition useful: it replaces a potentially long polynomial with a short polynomial remainder whenever multiples of $g$ can be discarded. At any root of a polynomial of $g$, those multiples vanish under polynomial evaluation. Repeated polynomial division also drives the Euclidean algorithm for finding a greatest common divisor of polynomials.

The coefficient setting matters. Over a commutative ring, the same existence and uniqueness hold when the divisor's leading coefficient is a unit in a ring. A monic polynomial therefore works over the integers, even though they do not form a field; monic polynomial division over a ring explains why zero divisors cause no difficulty in that case.^[ref]

A nonzero divisor alone is insufficient over the integers. Dividing $X$ by $2X+1$ with an integer polynomial quotient and a constant polynomial remainder would require $1=2c$ for an integer $c$, which is impossible. Over the rational numbers the division instead givesThe obstruction is the nonunit leading coefficient $2$. This example separates existence from uniqueness: over an integral domain, the polynomial degree argument still makes any admissible pair unique, if it exists.

A polynomial function is the function obtained by evaluating a polynomial on a specified ring or field. Distinct polynomials can induce the same polynomial function over a finite field; for example, $x^p$ and $x$ agree on ${\mathbb{F}}_p$.

Over ${\mathbb{F}}_2$, the nonzero formal polynomial $X^2-X$ evaluates to zero at both possible inputs, zero and one. It therefore induces the same polynomial function as the zero polynomial, despite having different coefficients and polynomial degree. Over an infinite field, equality at every input forces equality of polynomials by the root bound for a polynomial. The distinction matters whenever a representation is supposed to identify the function uniquely.

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials $A,B$ amounts to testing $P=A-B$ for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer $n\ge 1$, ${\prod }_{i=1}^n(1+x_i)$ has $2^n$ distinct monomials, one for each subset of the $n$ variables. Its factored expression needs only $n$ additions and $n-1$ multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Work in the finite field ${\mathbb{F}}_5=\{0,1,2,3,4\}$, using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives $(x+1{)}^2=x^2+2x+1$, so all coefficients of $F$ cancel: $F$ is identically zero. In contrast, $G=x^2-3x+2=x^2+2x+2$ in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.

The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, $G(3)=(3-1)(3-2)=2$ is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that $G$ is nonzero. A random variable $a$ with a uniform distribution on a finite set ${\mathbb{F}}_5$ hits those two polynomial roots with probability $2/5$.

A crucial limit appears with $H(x)=x^5-x$. Its coefficients make it a nonzero polynomial of polynomial degree five in ${\mathbb{F}}_5[x]$, yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are $0,0,30,240,1020$, all divisible by five. Thus $H$ induces the same polynomial function as the zero polynomial. Any number of trials restricted to ${\mathbb{F}}_5$ will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is $5/5=1$, which gives no useful guarantee.

When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish $H$ from zero.^[ref]

For an odd integer $q\ge 3$ and positive summable coefficients $a_k$, the Weierstrass M-test makes $f(x)={\sum }_{k\ge 0}{a}_k\cos (q^{k}x)$ continuous. Its partial sum over $q^k\le n$ is the unique best uniform approximation by degree-at-most-$n$ trigonometric polynomials, for $n\ge 1$. If $Q$ is the first omitted frequency, at $x_j=j\pi /Q$ every omitted cosine equals $(-1{)}^j$ because all frequency ratios are odd. Thus the tail attains alternating extrema equal to its coefficient sum at $2Q\ge 2n+2$ points. The trigonometric Chebyshev alternation theorem proves the formula. For $a_k=r^{-k}$, $r>1$, the largest decay exponent is $\log r/\log q$.

A power series combines a sequence of coefficients with monomials in the displacement from a fixed centre:The variable $z$, centre $c$, and coefficients can be real numbers or complex numbers. Its degree-$N$ partial sum $P_N(z)={\sum }_{n=0}^N{a}_n(z-c{)}^n$ is a polynomial, so a convergent power series can turn a complicated function into increasingly accurate finite calculations. Convergence, and the error after stopping, are essential parts of that claim.

The geometric series supplies the simplest computed example:At $z=1/2$, stopping after degree ten gives $P_{10}(1/2)=1.9990234375$, differing from the exact value $2$ by $1/1024=0.0009765625$. At $z=0.99$, the same degree gives only about $10.4662$ instead of $100$. The same formula has very different practical accuracy at different points; the geometric power-series remainder quantifies it.

The structure is useful beyond numerical evaluation. Within its radius of convergence, termwise differentiation of a power series turns a question about a derivative into a question about coefficients. A Taylor series chooses $a_n=f^{(n)}(c)/n!$ when it represents the function locally. A formal power series instead uses the coefficients algebraically, without asserting numerical convergence; the existing generating function examples use that distinction to encode counting problems.

For prime $p$, a graph with $m>(p-1)n$ edges and maximum degree at most $2p-1$ contains a nonempty $p$-regular subgraph. Over ${\mathbb{F}}_p$, apply the Combinatorial Nullstellensatz on the Boolean edge-variable cube toIts full squarefree coefficient is nonzero because the first product has degree below $m$. A nonzero value cannot occur at the zero vector; at any other Boolean vector the second product vanishes, and the first forces all selected degrees to be multiples of $p$. The maximum-degree condition makes every positive selected degree exactly $p$.

Let $N$ be a nonnegative integer-valued random variable, and let $Y_1,Y_2,\dots$ be nonnegative integer-valued independent and identically distributed random variables, with common probability generating function $G_Y$. Require the whole sequence to be independent of $N$, so $N,Y_1,Y_2,\dots$ are jointly independent. Set the random sumwith the empty sum equal to zero. Given $N=n$, the probability generating function of an independent sum yields the conditional expectation $\mathbb{E}[s^S\mid N=n]=G_Y(s{)}^n$. By the law of total expectation,The composition is valid because $|G_Y(s)|\le 1$. Merely making the $Y_j$ independent of each other does not preserve their conditional laws when $N$ depends on them. This is the probability generating function version of transform composition for an independent random sum.

For a Poisson distribution count with mean $\lambda$, substitution into $G_N(u)=\exp (\lambda (u-1))$ gives a compound Poisson distribution withIf the jumps have finite second moment, conditioning also gives mean $\mathbb{E}[S]=\lambda \mathbb{E}[Y]$ and variance $\mathrm{Var}(S)=\lambda \mathbb{E}[Y^2]$. The extra spread comes from randomness in the count as well as randomness in the jumps.^[ref]

For an original example, choose $N\sim \mathrm{Poisson}(2)$ and jumps taking values one and two with equal probability. Keep the independence assumptions above. ThenHere $\mathbb{E}[Y]=3/2$, $\mathrm{Var}(Y)=1/4$, and $\mathbb{E}[Y^2]=5/2$. The law of total expectation and law of total variance giveThus the aggregate is not itself a Poisson distribution, whose mean and variance would coincide.

To recover the probability mass function $p_n=\mathbb{P}(S=n)$ without repeated differentiation, use $G_S^{\prime }(s)=(1+2s)G_S(s)$ and compare coefficients:For example, $(p_0,p_1,p_2,p_3)=e^{-2}(1,1,3/2,7/6)$. As an independent check, expanding $e^{s+s^2-2}=e^{-2}{e}^s{e}^{s^2}$ gives

The plotted probability masses stop at 20, although the support of a probability distribution is unbounded. The omitted tail probability isThis model has bounded jumps and an unbounded count. Its entire probability generating function does give a finite moment-generating function at every real argument, but the general random sum composition only guarantees the stated $|s|\le 1$ domain.

For nonnegative integer-valued independent random variables $X,Y$, factor the expected value of a product:The Cauchy product explains what this means for individual probability masses:Every way of splitting the total contributes once. This is convolution of independent random variables; multiplying probability generating functions performs the bookkeeping automatically.

For an original example, take independent $X\sim \mathrm{Bernoulli}(0.3)$ and $Y\sim \mathrm{Binomial}(2,0.5)$, using the Bernoulli distribution and binomial distribution. ThensoDirect enumeration of the six pairs $(x,y)$ gives the same probability masses. For example, total one collects $(0,1)$ and $(1,0)$, with contributions $0.7\cdot 0.5+0.3\cdot 0.25=0.425$. The coefficients sum to one. The expected value is $G_{X+Y}^{\prime }(1)=1.3$; since $G_{X+Y}^{\prime \prime }(1)=1.1$, the variance is $1.1+1.3-1.3^2=0.71$, agreeing with $0.3\cdot 0.7+2\cdot 0.5\cdot 0.5$.

Uncorrelated random variables are insufficient for the product identity. For a concrete counterexample, let $U$ be uniform on $\{-1,0,1\}$ and set $A=U+1$, $B=U^2$. Then $\mathrm{Cov}(A,B)=\mathbb{E}[U^3]=0$, but $\mathbb{P}(A+B=0)=0$, whereas $G_A(0)G_B(0)=1/9$. Zero covariance controls one mixed moment, not the full joint probability mass function.