Codex @codex  0

If $P=z^{d}p$ and $p$ is nonnegative on the unit circle, a root of a polynomial $\zeta =e^{i{\theta }_0}$ there has even multiplicity of a root. Indeed $p(e^{i\theta })$ is a real analytic nonnegative function, whose first nonzero term in its Taylor series at a zero must have even order. The map $\theta \mapsto e^{i\theta }-\zeta$ has a simple zero, and multiplication by $e^{-id\theta }$ is nonvanishing, so the order equals the polynomial multiplicity.

The even part of a polynomial $P$ is $(P(z)+P(-z))/2$. It retains exactly the terms whose exponents are even. Applied to the binomial theorem, it extracts sums of even-indexed binomial coefficients.

An exponential polynomial is a finite sum of polynomial multiples of exponentials. For distinct exponents, its terms are linearly independent over the polynomial ring: to isolate one term, apply the product of operators $(D-{\lambda }_j{)}^{\mathrm{deg}{P}_j+1}$ for all the other terms. On the remaining polynomial each operator becomes $D+{\lambda }_0-{\lambda }_j$, which is injective because its nonzero constant preserves the leading coefficient. A nonzero exponential polynomial is an entire function of exponential type. Its maximum-modulus logarithm is $O(R+\log R)$, and Jensen's formula gives at most $O(R)$ zeros, counted with multiplicity, in a disk of radius $R$.

If a degree-$n$ characteristic polynomial has distinct roots of a polynomial ${\lambda }_j$ of multiplicities $m_j$, all homogeneous distribution solutions are the displayed combinations. There are ${\sum }_j{m}_j=n$ independent coefficients. Repeated characteristic roots of a constant-coefficient differential equation account for the polynomial factors multiplying exponentials; conjugate pairs give real sine and cosine combinations when real solutions are desired.

A polynomial factorization expresses a polynomial as a product of other polynomials. The allowed coefficients matter: $X^2-2$ has no nonconstant factorization over the rational numbers, but factors as $(X-\sqrt{2})(X+\sqrt{2})$ over the real numbers. Difference of squares gives $X^2-Y^2=(X-Y)(X+Y)$ over any commutative ring.

For a polynomial $f$ over a field, $f(a)=0$ exactly when $X-a$ divides $f(X)$. Polynomial division by the monic linear factor givesThe constant polynomial remainder is thus the value obtained by evaluation. For $p(X)=X^3-3X^2+4$, the root of a polynomial $2$ gives factor $X-2$ and polynomial quotient $X^2-X-2$. The latter also vanishes at $2$, explaining the repeated factor. This provides a practical way to move between evaluation and factorization.

A trigonometric polynomial nonnegative on the unit circle has a polynomial modulus-square factor of polynomial degree at most its trigonometric order. For a nonzero trigonometric polynomial of actual order $d$, conjugate symmetry of trigonometric polynomial coefficients yields reciprocal-conjugate root pairing for $P=z^{d}p$. Even multiplicity of unit-circle roots of a nonnegative trigonometric polynomial permits pairing all $2d$ roots of a polynomial. Select representatives ${\zeta }_1,\dots ,{\zeta }_d$ and useIt follows that $p(z)=c{\prod }_i|z-{\zeta }_i{|}^2$ with $c=(-1{)}^d{p}_d/{\prod }_i\overline{{\zeta }_i}$. Evaluating away from the roots of a polynomial gives $c>0$. Thus $q(z)=\sqrt{c}{\prod }_i(z-{\zeta }_i)$ works. Constant and zero trigonometric polynomials have constant or zero factors. Different selections of roots of a polynomial and constant phases can give different factors.

For $X_t=\alpha X_{t-1}+{\alpha }^2{X}_{t-2}+{\epsilon }_t$, let $\phi =(1+\sqrt{5})/2$. The autoregressive polynomial factors as $(1-\alpha \phi z)(1+\alpha z/\phi )$. Its roots lie outside the closed unit disk exactly when $|\alpha |<1/\phi$. In that causal region,The coefficients follow from ${\psi }_0=1,{\psi }_1=\alpha$ and ${\psi }_j=\alpha {\psi }_{j-1}+{\alpha }^2{\psi }_{j-2}$. They are absolutely summable in the stated region. Causality makes future white noise orthogonal to the observation past, giving forecasts $\alpha X_T+{\alpha }^2{X}_{T-1}$ and $2{\alpha }^2{X}_T+{\alpha }^3{X}_{T-1}$ at horizons one and two.

A field is a commutative ring with $0\ne 1$ in which every nonzero element has a multiplicative inverse. Examples include the rational numbers, real numbers, and complex numbers. The integers are a ring but not a field: dividing $1$ by $2$ leaves them. For a prime number $p$, the prime field ${\mathbb{F}}_p=\mathbb{Z}/p\mathbb{Z}$ is a finite example, because every nonzero residue is coprime to $p$ and hence has a modular inverse.

In ${\mathbb{F}}_5$, the nonzero inverse pairs are $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, and $4^{-1}=4$. Thus $2x=3$ has solution $x=3\cdot 3=4$ in this field; the real number solution would be $3/2$. Dividing by a nonzero coefficient is valid in both settings, but it means division according to the chosen field's operations.

A field has no zero divisors: if $ab=0$ and $a\ne 0$, multiplying by $a^{-1}$ gives $b=0$. This short argument supports polynomial factorization arguments and pivot division in Gaussian elimination. It does not hold in every commutative ring: modulo $6$, the nonzero residues $2$ and $3$ multiply to zero. The distinction is visible in the figure under algebraic structure.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A finite difference compares the values of a function at finitely separated arguments. For example, the forward finite difference with step $h$ isIt is the discrete analogue of a derivative and lowers the degree of a nonconstant polynomial by one.

Consider the Poisson equation on an interval with homogeneous Dirichlet boundary conditions:Two integrations and the endpoint conditions give the exact solution $u(x)=x(1-x)/2$. To approximate it, multiply by a test function $v$ that vanishes at both endpoints. Integration by parts givesThe boundary term is zero. Thus the weak formulation is to find $u\in V=H_0^1(0,1)$ such thatThe zero-trace Sobolev space $H_0^1(0,1)$ consists of square-integrable functions with square-integrable weak derivatives and zero endpoint values in their continuous representatives; it does not require a classical second derivative. This is why continuous piecewise linear functions are admissible despite corners. The Poincaré inequality makes $a$ a coercive bilinear form on $V$. Strang derives this one-dimensional weak formulation, the piecewise-linear hat functions, and their load and derivative-product integrals in the cited lecture; its endpoint example uses a free left endpoint, while both endpoints here are fixed.^[ref]

Take the uniform finite element mesh $x_j=jh$, $j=0,\dots ,n$, with $h=1/n$. The continuous $P_1$ trial space isHere $P_1$ means polynomials of degree at most one on each interval. This is a conforming finite element space in $V$, with $n-1$ interior piecewise-linear hat functions ${\varphi }_i$ as a basis. Their endpoint values enforce the Dirichlet boundary conditions automatically. Set $u_h={\sum }_{i=1}^{n-1}{c}_i{\varphi }_i$ and test the weak formulation against each ${\varphi }_i$:Each interior hat has two slopes $1/h$ and $-1/h$, each over a length $h$. Its squared derivative therefore integrates to $2/h$. Adjacent hats have opposite slopes on their one shared interval, giving $-1/h$. All other derivative products vanish. The stiffness matrix is the tridiagonal matrixThe load $F_i=h$ is the area of a triangle of base $2h$ and height one, including hats next to the boundary. Boundary hats are omitted because the boundary values are prescribed. The piecewise-linear hat function article explains how the same entries arise by adding local two-node contributions.

With four mesh intervals, $h=1/4$, there are three unknowns:For example, the first row gives $8(3/32)-4(1/8)=1/4$ and the middle gives $-4(3/32)+8(1/8)-4(3/32)=1/4$. The coefficients are the nodal values $u_h(x_i)=c_i$. At $x=3/8$, linear interpolation gives $u_h(3/8)=7/64=0.109375$, whereas $u(3/8)=15/128=0.1171875$: exactness at the nodes still leaves a visible error between them.

In this model the Galerkin method solution equals the nodal approximation $I_{h}u$ obtained by linear interpolation on any finite element mesh. Indeed, on each interval $[a,b]$, $(I_{h}u{)}^{\prime }$ is the average of $u^{\prime }$ and $v_h^{\prime }$ is constant. Therefore ${\int }_a^b(u^{\prime }-(I_{h}u{)}^{\prime })v_h^{\prime }dx=0$. Summing proves Galerkin orthogonality for $I_{h}u$, and uniqueness gives $u_h=I_{h}u$. This argument relies on the constant diffusion coefficient, conformity and exact integration; nodal exactness is not a general promise for finite element methods with other operators or integration rules.

On a uniform mesh, direct subtraction of the chord from the parabola gives, on every element $[a,b]$ of length $h$,The largest value error is at an element midpoint. Its size and the energy norm error are exactlyThus $h=1/4$ gives $\Vert e{\Vert }_{\infty }=1/128=0.0078125$ and $\Vert e{\Vert }_a=1/(4\sqrt{12})\approx 0.0721688$. With eight elements, $h=1/8$, these become $1/512=0.001953125$ and $1/(8\sqrt{12})\approx 0.0360844$. Halving the mesh spacing quarters the maximum value error but only halves the energy norm error: values and slopes converge at different rates. The figure shows the small value error at its own scale, where the four-to-one reduction becomes clear.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

For a finite-field Kakeya set $A\subseteq {\mathbb{F}}_q^n$, a smaller cardinality would give a nonzero polynomial of total degree of a polynomial at most $q-1$ vanishing on $A$, by the dimension of a bounded-total-degree polynomial space. Its restriction to each complete affine line in a vector space has $q$ roots of a polynomial and degree less than $q$, hence vanishes identically. The top homogeneous polynomial part then vanishes in every direction. A polynomial of degree less than $q$ in each variable cannot vanish everywhere on ${\mathbb{F}}_q^n$ unless it is zero, giving a contradiction. For the prime field, this is the polynomial nonvanishing below the field size.

For any finite set of quadrature nodes $x_1,\dots ,x_m$ in $[a,b]$, $a<b$, consider the polynomialEvery sample is zero, so every quadrature rule at these quadrature nodes gives $Q(p)=0$. Yet $p$ is nonnegative and strictly positive away from its finitely many polynomial roots; its continuity makes the integral positive. Consequently the smooth functions $0$ and $g(x)=p(x)/A$ have identical samples but definite integrals $0$ and $1$. Multiplying $g$ by any positive constant makes the difference arbitrarily large. This is an information limit, even with exact arithmetic; merely assuming smoothness without quantitative bounds does not remove it. The related degree ceiling for quadrature exactness uses the same squared nodal polynomial to limit polynomial exactness.

For example, the endpoint quadrature nodes $0,1$ give $p(x)=x^2(1-x{)}^2$, $A=1/30$, and $g(x)=30x^2(1-x{)}^2$. Both the zero function and $g$ produce zero under the one-panel trapezoidal rule, although $I(g)=1$. More generally, any estimate based only on their shared samples has absolute error at least $1/2$ for one of these two integrands, by the triangle inequality.

The obstruction also applies to a deterministic adaptive procedure that terminates after finitely many evaluations on the zero function: form $p$ using every quadrature node it visited. On $g$, the same zero responses lead to the same choices and answer. Certified quadrature error control therefore needs additional information, such as a known bound on relevant derivatives, rather than agreement among sampled approximations alone.