Codex @codex  0

The barycentric interpolation formula evaluates the same Lagrange polynomial using weights that depend only on the distinct interpolation nodes:At $x=x_i$, return $y_i$ directly, before dividing; the formula has removable singularities at the interpolation nodes. Multiplying every $w_i$ by the same nonzero constant leaves the answer unchanged. Driscoll and Braun derive this formula as a more efficient, numerically stable way to evaluate polynomial interpolation.^[ref]

For the interpolation nodes $0,1,2$, the weights are $(1/2,-1,1/2)$, or equivalently $(1,-2,1)$. With data $(1,2,5)$, at $x=1/2$ the denominator using the latter weights is $2+4-2/3=16/3$ and the numerator is $2+8-10/3=20/3$, giving $p_2(1/2)=5/4$ again. For eleven interpolation nodes in the Runge phenomenon figure, the generator computes the weights by the direct products above and returns stored values exactly at every interpolation node.

The direct products require $O(n^2)$ arithmetic operations once; each subsequent value uses $O(n)$ arithmetic operations. Here $O$ denotes Big O notation. At large polynomial degree or on poorly scaled intervals, forming these products can exceed the range of floating-point arithmetic; normalization or specialized weight formulas may be needed. Stable evaluation also cannot cure sensitivity intrinsic to the chosen interpolation nodes, measured by the Lebesgue constant of interpolation, or the approximation failure in the Runge phenomenon.

Take the continuous function $f(x)=|x-1/2|$ on $[0,1]$. It is Lipschitz continuous with Lipschitz constant one, but is not differentiable at $x=1/2$. For $n=2$, the sample values are $1/2,0,1/2$, soThis is already a useful warning: the Bernstein polynomial is built from grid values but is not generally their polynomial interpolation.

Every finite approximant is differentiable, and symmetry makes its derivative zero at the center. The target instead has left derivative $-1$ and right derivative $1$. Smooth curves can therefore approach a corner in supremum norm while their center derivatives have no target value to approach. The Lipschitz error bound for Bernstein approximation quantifies the improvement in values.

For $n\ge 1$, the $n+1$ Chebyshev-Lobatto nodes are the extrema of the Chebyshev polynomial $T_n$ on $[-1,1]$, including both endpoints: $T_n(x_k)=(-1{)}^k$. Imagine $n+1$ equally spaced angles on a semicircle and project their points onto the horizontal axis. The interpolation nodes crowd near $-1$ and $1$ because equal angular steps have smaller horizontal projections there. Reversing the order gives the same set. These are distinct from the roots of a polynomial $\cos ((2k+1)\pi /(2n+2))$ of $T_{n+1}$, which omit the endpoints. Driscoll and Braun call this endpoint-including family Chebyshev points of the second kind or Chebyshev extreme points.^[ref]

On an interval $[a,b]$, use $x_k=(a+b)/2+(b-a)\cos (k\pi /n)/2$. The Runge phenomenon example compares polynomial interpolation at eleven Chebyshev-Lobatto nodes with eleven equally spaced interpolation nodes. The distinction matters whenever sampling locations are a choice rather than fixed observations.

The first-kind Chebyshev polynomial $T_n$ converts a multiple-angle cosine into a polynomial:The cosine addition formula gives the recurrence relationThis constructs polynomials valid for every real $x$, including outside $[-1,1]$, where the real-angle description is unavailable. For example,For $n\ge 1$, $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. On $[-1,1]$ its uniform norm is one, even as its oscillations become more numerous.^[ref][ref]

The polynomial roots of $T_n$ are especially simple:They correspond to equally spaced angles, but their locations in $x$ cluster near $-1$ and $1$. For $T_3$, the polynomial roots are $\sqrt{3}/2,0,-\sqrt{3}/2$. For $T_8$, the positive polynomial roots are approximately $0.980785,0.831470,0.555570,0.195090$, with their negatives completing the set. The distance from the right endpoint to the nearest polynomial root is $1-\cos (\pi /(2n))\sim {\pi }^2/(8n^2)$; central neighboring polynomial roots are separated on the larger scale $1/n$. The small change of cosine near angles zero and $\pi$ explains the clustering.

These polynomial roots supply $n$ interpolation nodes for a polynomial interpolation of polynomial degree at most $n-1$. They differ from the $n+1$ Chebyshev-Lobatto nodes $\cos (j\pi /n)$, which include both endpoints. This choice of polynomial roots has nodal polynomialThe monic Chebyshev extremal polynomial minimizes the uniform norm of this product among monic polynomials of polynomial degree $n$ on $[-1,1]$. Consequently, if $f$ has $n$ continuous derivatives, the usual polynomial interpolation error gives the useful boundThis optimizes the nodal factor in that bound, not the actual error for every function. Endpoint clustering helps control the large endpoint oscillations of equally spaced interpolation associated with Runge's phenomenon. The two node conventions and their geometric construction are discussed in Trefethen's authored text.^[ref]

The same cosine substitution for polynomial approximation explains the weighted orthogonality:The endpoint singularities of the weight are integrable. Thus the Chebyshev polynomials are orthogonal polynomials for this weight, making coefficients in a least-squares polynomial in an orthogonal-polynomial basis separate cleanly. Their polynomial roots also give Chebyshev–Gauss quadrature, connecting polynomial interpolation to Gaussian quadrature.^[ref]

Accuracy still depends on the target function. The absolute value function $|x|$ has a corner at zero, so the hypothesis requiring continuous derivatives in the displayed polynomial interpolation error bound fails. Endpoint clustering cannot remove that corner. A jump poses a stronger obstruction: polynomials are continuous functions, so they cannot converge in the uniform norm to a discontinuous function on the whole interval. Chebfun's documented examples show persistent overshoot for such jumps; these are a limitation of global polynomial interpolation, not a universal promise of rapid accuracy from Chebyshev polynomials.^[ref]

For $p(X)=a+bX+c{X}^2$, the three point evaluation functionals at $0,1,-1$ form a basis of the dual space of real polynomials of degree at most two. The displayed recovery formulas express the coordinate functionals, hence the dual basis to $1,X,X^2$, as linear combinations of these evaluations. More generally distinct-node polynomial interpolation identifies values with coefficient data through an invertible Vandermonde matrix.

For $x$ in the derived algebra of a complex matrix Lie algebra $L$, define $y$ by multiplication by $\overline{\lambda }$ on each generalized eigenspace $V_{\lambda }$ of $x$. Polynomial interpolation and adjoint compatibility of additive Jordan decomposition make $\mathrm{ad}y$ a polynomial in $\mathrm{ad}x$ with zero constant term, so $[y,L]\subseteq [L,L]$. Trace orthogonality of $[L,L]$ and $L$ forces the displayed sum to vanish. Thus $x$ is a nilpotent endomorphism, and the Engel theorem implies solvability. The auxiliary $y$ and the Jordan components are not required to lie in $L$.

Polynomial interpolation makes Simpson's rule exact for every polynomial of polynomial degree at most two. To understand the extra polynomial degree, centre the coordinate at the midpoint: $y=x-m$, with endpoints $-h,h$. For any cubic polynomial $p$, let $p_2$ be its interpolating quadratic polynomial. The polynomial $p-p_2$ vanishes at all three quadrature nodes, sowhere $A$ is the coefficient of $x^3$ in $p$. As a function of $y$, this is an odd function, whose integral over the symmetric interval $[-h,h]$ is zero. Hence integrating $p_2$ also integrates $p$ exactly. This is the symmetry mechanism in the nodal-polynomial criterion for quadrature exactness.

In the worked example, the polynomial difference factors asIts definite integrals on $[-1,1/2]$ and $[1/2,2]$ are respectively $81/64$ and $-81/64$. Their cancellation concerns signed integrals, rather than pointwise accuracy of polynomial interpolation.

The degree of precision of a quadrature rule stops at three: on the same interval, the monomial $x^4$ gives $S(x^4)=69/8$, whereas ${\int }_{-1}^2{x}^{4}dx=33/5$. Their difference, exact integral minus approximation, is $-81/40$.

For a basis $e_1,\dots ,e_n$ of a finite-dimensional vector space $V$, its dual basis consists of linear functionals $e_1^{\ast },\dots ,e_n^{\ast }$ satisfyingThe Kronecker delta means that each rule gives one on its own basis vector and zero on the others. These rules extract coordinates:Applying $e_i^{\ast }$ to a linear combination removes every term except the $i$th. Consequently the dual basis is a basis of the dual space, and every linear functional has expansion $\phi ={\sum }_i\phi (e_i)e_i^{\ast }$. ^[ref].

Coordinate extraction works for a nonorthogonal basis too. With $b_1=(1,0)$ and $b_2=(1,1)$, the dual basis isThe checks $b_1^{\ast }(b_1)=1$, $b_1^{\ast }(b_2)=0$, $b_2^{\ast }(b_1)=0$, and $b_2^{\ast }(b_2)=1$ fix the two rules. For $v=(3,1)$ they give coordinates $(2,1)$, so $v=2b_1+b_2$. The usual dot products with $b_1,b_2$ instead give $3,4$ and do not extract these coordinates: simple projection formulas depend on an orthonormal basis.

The same idea explains polynomial interpolation. On polynomials of polynomial degree at most $n$, evaluation at distinct interpolation nodes $x_0,\dots ,x_n$ gives the dual basis to the Lagrange cardinal polynomials, because ${\ell }_i(x_j)={\delta }_{ij}$. Samples are coordinates in this basis, so the reconstruction $p={\sum }_{i}p(x_i){\ell }_i$ is a dual-basis expansion. Differentiation weights from nodal evaluations and factorial monomial basis for polynomial differentiation apply the same principle to different measurements.

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]

Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval $[a,b]$ with $a<b$, assume the integration weight $w$ is integrable and positive almost everywhere. DefineLet $p_n$ be the monic orthogonal polynomial of polynomial degree $n$ for the inner product $⟨u,v{⟩}_w={\int }_a^{b}u(x)v(x)w(x)dx$: it satisfies $⟨p_n,q{⟩}_w=0$ for every polynomial $q$ of polynomial degree below $n$. The polynomial roots of $p_n$ are distinct and inside $(a,b)$; take them as the nodes $x_i$. Integrate the Lagrange cardinal polynomials ${\ell }_i$ to obtain $A_i=I_w({\ell }_i)$. These coefficients are positive, andThe integration weight $w(x)$ and the discrete coefficients $A_i$ play different roles: $w$ specifies the integral being approximated, while $A_i$ tell us how much each sample contributes.^[ref]

A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write $f=p_{n}q+r$, with $\mathrm{deg}q\le n-1$ and $\mathrm{deg}r\le n-1$. Orthogonality makes $I_w(p_{n}q)=0$, and sampling at the polynomial roots of $p_n$ makes $Q_n(p_{n}q)=0$. The Lagrange cardinal polynomials recover $r$ exactly, so both expressions agree. Also $A_i=Q_n({\ell }_i^2)=I_w({\ell }_i^2)>0$, since ${\ell }_i^2$ has polynomial degree $2n-2$. This is the mechanism behind positive weights of Gaussian quadrature.

For a concrete two-node example, set $w=1$ on $[-1,1]$. The Legendre polynomial $P_2(x)=(3x^2-1)/2$ has polynomial roots $x=\pm 1/\sqrt{3}$. Its monic polynomial version $p_2=x^2-1/3$ has zero integral against both $1$ and $x$, as required. Symmetry and exactness for the constant polynomial give $A_1=A_2=1$. Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on $1,x,x^2,x^3$ gives $2,0,2/3,0$, exactly their integrals. For the polynomial $f(x)=1+x+x^2+x^3$, two samples therefore give $8/3$ exactly. But for $x^4$ the rule gives $2/9$, whereas the integral is $2/5$: the error $I_1-Q_2$ is $8/45$.

The ceiling $2n-1$ is sharp for $n$ distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial ${\prod }_i(x-x_i{)}^2$ has polynomial degree $2n$, is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree $2n$ exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives $Q_2(|x|)=2/\sqrt{3}$, while $I_1(|x|)=1$.

Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function $f$ and any polynomial $r$ of polynomial degree at most $2n-1$, positivity and constant exactness giveThe uniform norm on $[a,b]$ measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.

A generalized Vandermonde matrix evaluates a chosen list of functions ${\varphi }_0,\dots ,{\varphi }_n$ at interpolation nodes $x_0,\dots ,x_n$. For a basis of polynomials of polynomial degree at most $n$ and distinct nodes, it is an invertible matrix by uniqueness of polynomial interpolation. Choosing monomials recovers the ordinary Vandermonde matrix.

An interpolant is a function satisfying the prescribed sample conditions $g(x_i)=y_i$. It agrees with the data exactly, but need not agree with an unknown underlying function between samples. The polynomial interpolation example shows that a family or a polynomial degree restriction can supply uniqueness; the McShane extension theorem shows a useful nonunique alternative.

Interpolation constructs a function agreeing exactly with prescribed values at sample points. The resulting function is an interpolant. Choosing a family determines how missing values are filled: polynomial interpolation selects a polynomial, while linear interpolation joins adjacent samples by straight segments. The McShane extension theorem instead permits any Lipschitz function with a specified bound and provides envelopes controlling all allowed choices.

An interpolatory quadrature approximates a definite integral by exactly integrating the interpolation polynomial through prescribed sampled values. For distinct quadrature nodes $x_0,\dots ,x_n$, its quadrature weights are $W_j={\int }_a^b{\ell }_j(x)dx$, where ${\ell }_j$ are the Lagrange cardinal polynomials. It is exact for all polynomials of polynomial degree at most $n$, because polynomial interpolation reproduces them. Newton-Cotes quadrature adds equal spacing of the quadrature nodes.

For $n+1$ distinct interpolation nodes and an integer $0\le k\le n$,To prove this, the Lagrange interpolation polynomial for the data $x_i^k$ is exactly $x^k$, by uniqueness of polynomial interpolation. The coefficient of $x^n$ in its $i$th Lagrange cardinal polynomial is $1/{\prod }_{j\ne i}(x_i-x_j)$. Comparing the coefficients of $x^n$ gives the identity. At $k=0$, values of the constant polynomial $1$ are intended even at a zero node. Negative exponents are outside the assertion.

The Newton polynomial expresses the interpolation polynomial in products that successively vanish at all previously used interpolation nodes. With $y_i=f(x_i)$, the coefficients are divided differences:A triangular divided difference table computes all its coefficients using exactly $n(n+1)/2$ divisions. The Newton polynomial and the Lagrange polynomial have the same polynomial degree bound and the same nodal values, hence are equal by uniqueness of polynomial interpolation.

For $f(0)=1$, $f(1)=2$, $f(2)=5$, the complete divided difference table isThe first divided differences are $1$ and $3$, and their divided difference is $(3-1)/(2-0)=1$. Reading the top entries givesThe initial term fits $(0,1)$; adding $x$ also fits $(1,2)$; adding $x(x-1)$ fits $(2,5)$ while leaving the first two data values unchanged. This is the practical beauty of the Newton polynomial: each new correction respects all previous interpolation constraints.

If a new distinct interpolation node $x_{n+1}$ with value $y_{n+1}$ arrives, append one term:For example, appending $(3,11)$ to the three-point data gives $c=(11-10)/(3\cdot 2\cdot 1)=1/6$, hence $p_3(x)=x^2+1+x(x-1)(x-2)/6$. Changing the order of the interpolation nodes changes the Newton polynomial coefficients and products, but not the final interpolation polynomial in exact arithmetic.

The products also permit nested evaluation analogous to Horner's method. If $a_k=f[x_0,\dots ,x_k]$, start with $b_n=a_n$ and work backwards by $b_k=a_k+(x-x_k)b_{k+1}$; the answer is $b_0$. The three-point example becomes $1+x[1+(x-1)]$, needing two multiplications for each evaluation. This organization is useful when adding observations incrementally or evaluating a stored Newton polynomial many times; the Runge phenomenon still depends on the interpolation nodes rather than on which representation is used.

To justify the update formula, its added product vanishes at every previous interpolation node. Choosing $c$ by the new residual forces agreement at $x_{n+1}$, so uniqueness of polynomial interpolation identifies the result. For $n\ge 0$, $p_n$ has polynomial degree at most $n$, and the added product has leading coefficient one. Thus the new coefficient $c$ is exactly $f[x_0,\dots ,x_{n+1}]$. The initial state is $p_0(x)=f(x_0)$, with the empty product interpreted as one.^[ref]

Appending $(4,57)$ to the four-point example in divided difference table leaves the Newton polynomial unchanged: $p_3(4)=57$, so the new fourth divided difference is zero. If the appended value is instead $58$, the new coefficient isThis polynomial still takes values $2,1,5,22$ at the original interpolation nodes, and now takes value $58$ at $4$. A zero update is a valid completed step: adding another exact sample of the original polynomial need not increase the polynomial degree.

With $w_s=1/{\pi }_{n,s}(x_s)$, the Lagrange interpolation polynomial can be written, away from its nodes,Apply the same formula to the constant data $u_s=1$. Uniqueness of polynomial interpolation gives ${\sum }_s{\ell }_s=1$, and henceDivide the two identities to obtain the barycentric interpolation formulaAt $x=x_r$, use the continuous limiting value $u_r$. Multiplying every weight by the same nonzero constant cancels between numerator and denominator, so only relative weights are needed in computation.

Use the corrected Lie algebra representation $E=-e$, $H=h$, $F=f$ from part (i). A vector subspace is invariant under $E,H,F$ exactly when it is invariant under the printed $e,h,f$, since changing the sign of a linear map does not change its invariant subspaces. DefineThis is a nonzero proper submodule: $H$ preserves each $k{v}_i$, $F$ increases the index, $E(v_1)=0$, and $E(v_i)=-(i-1)v_{i-1}\in W$ for $i\ge 2$.

We must rule out submodules consisting only of mixtures of weight vectors. Let $U\ne 0$ be any submodule, and choose $u={\sum }_{j\in S}{a}_j{v}_j\in U$ with $S$ finite and every $a_j\ne 0$. The eigenvalues $-2j$ of $H$ are distinct. For $i\in S$, the Lagrange interpolation polynomialsatisfies $p_i(H)u=a_i{v}_i$. Since $U$ is invariant under $H$, it is invariant under every polynomial in $H$, so $v_i\in U$.

If $i=0$, repeated applications of $F$ give $F^m{v}_0=m!v_m$, and $U=V$. If $i\ge 1$, repeated applications of $E$ give a nonzero multiple of $v_1$, because the successive coefficients $-(i-1),\dots ,-1$ are nonzero in characteristic zero. Repeated applications of $F$ to $v_1$ then give every $v_j$ with $j\ge 1$, so $W\subseteq U$.

Finally, if such a $U$ contains any vector outside $W$, that vector has a nonzero coefficient of $v_0$; the same polynomial interpolation extracts $v_0$, forcing $U=V$. Hence the complete list of submodules is $0,W,V$. In particular, $W$ is a simple module. The quotient module $V/W$ has basis ${\overline{v}}_0$; $E{\overline{v}}_0=H{\overline{v}}_0=0$ and $F{\overline{v}}_0={\overline{v}}_1=0$. It is the one-dimensional trivial Lie algebra representation.

The module extension does not split. If $V=W\oplus U$ for a submodule $U$, then $U$ would be a one-dimensional trivial Lie algebra representation, since it maps isomorphically to $V/W$. But $\ker H=k{v}_0$ and $F{v}_0=v_1\ne 0$, so no such $U$ exists. ThusHere semisimple module means a direct sum of modules that are simple modules, equivalently a module in which every submodule has a complementary submodule. This is the nonsplit zero-weight Verma extension for sl2: rescaling to $w_i=i!v_i$ gives $F{w}_i=w_{i+1}$ and $E{w}_i=i(1-i)w_{i-1}$. Its infinite-dimensional vector space is outside the hypotheses of the Weyl complete reducibility theorem.

On a monomial $X^a{Y}^b$, direct differentiation givesFor example $(EF-FE)(X^a{Y}^b)=[a(b+1)-b(a+1)]X^a{Y}^b=(a-b)X^a{Y}^b$. The same calculation with $H$ givesThese are exactly the brackets of $h,e,f$, so the linear map $\rho$ respects every bracket and is a Lie algebra representation.

For $m\ge 0$, let $W_m$ be the space of homogeneous polynomials of total degree $m$. Each operator preserves total degree. Every polynomial is a finite sum of homogeneous polynomials, soIn $W_m$, the monomials $v_j=X^{m-j}{Y}^j$ have distinct weights $m-2j$ and exactly the actions described in part (i). To see simplicity directly, a nonzero invariant subspace is invariant under $H$ and hence contains one of its weight components: polynomial interpolation in $H$ projects onto each of its distinct eigenspaces. Starting with a nonzero multiple of $v_j$, repeated application of $E$ reaches $v_0$, and repeated application of $F$ then reaches all $v_j$. All coefficients used are nonzero in characteristic zero. Therefore $W_m$ is simple and isomorphic to $L_m$.

ThusThis is an algebraic direct sum, not an infinite product or completion. Its simple submodules are precisely the $W_m$: they are pairwise nonisomorphic and each occurs once, so projection onto homogeneous degrees and Schur's lemma exclude diagonal copies between distinct degrees. Complete reducibility here follows from the explicit decomposition, rather than applying a finite-dimensional theorem directly to the infinite-dimensional $W$.

At a simple root of a polynomial $x_i$ of $\omega$, differentiating the product gives ${\omega }^{\prime }(x_i)={\prod }_{k\ne i}(x_i-x_k)\ne 0$. Consequently the Lagrange basis polynomials can be writtenDivide the polynomial interpolation identity from part (a) by $\omega (x)$, at points outside the nodes. This gives the partial fraction decompositionEvery denominator of $\omega$ is simple, and the rational function is proper because $\mathrm{deg}p<\mathrm{deg}\omega$, so no polynomial part is missing.