Codex @codex  0

Let a polynomial $q$ of degree at most $n$ have errors $f(x_j)-q(x_j)=(-1{)}^{j}h$ at $n+2$ ordered distinct points. Then $|h|$ bounds below the error $E_n(f)$ of the best uniform approximation. Otherwise an improved polynomial $p$ with error strictly below $|h|$ would make $p-q$ alternate strictly in sign at all those points, giving at least $n+1$ distinct roots of a polynomial by the intermediate value theorem. Its degree is at most $n$, a contradiction. Moreover, if $q$ is not optimal, $|h|<E_n(f)$. In the equality case, an optimal $p$ gives weak alternating signs of $p-q$; its vanishing order-$(n+1)$ divided difference has same-sign summands, forcing every nodal value to vanish and hence $p=q$.

Given $f$ in a normed vector space and a vector subspace $U$, an element $p_{\ast }\in U$ is a best approximation if $\Vert f-p_{\ast }\Vert ={\inf }_{p\in U}\Vert f-p\Vert$. Existence is automatic for a finite-dimensional vector subspace: a minimizing sequence can be bounded by the triangle inequality, and a subsequence converges by compactness in finite dimension. An arbitrary infinite-dimensional vector subspace need not contain a minimizer. The norm matters: best uniform approximation uses the supremum norm, while $L^1$ approximation minimizes integrated absolute error.

For a real continuous function on a compact interval, choose its best uniform approximation $p_n^{\ast }$ of polynomial degree at most $n$. If its error is nonzero, the Chebyshev alternation theorem supplies $n+2$ ordered alternating extrema. The intermediate value theorem gives a zero of $f-p_n^{\ast }$ in each intervening interval. At these $n+1$ distinct points, the polynomial interpolant is exactly $p_n^{\ast }$. If the best error is zero, arbitrary distinct nodes suffice. The Weierstrass approximation theorem shows that these function-dependent interpolants converge uniformly. The nodes depend on the target function; the conclusion does not provide one universal node sequence for every continuous target.

The equioscillation theorem says that $p_n\in P_n$ is the unique best uniform approximation to a real continuous function $u$ on $[-1,1]$ exactly when its error attains alternating values $\pm E_n$ at $n+2$ ordered distinct points. If $E_n=0$, the error vanishes everywhere and the conclusion is immediate.

For the exponential function, write the candidate line as $p_1(x)=ax+b$. Its error $r(x)=e^x-ax-b$ is strictly convex. Equal endpoint errors require $a=(e-e^{-1})/2=\sinh 1$, and the interior minimum is at $c=\log a$, because $r^{\prime }(c)=e^c-a=0$. Equating the endpoint error to the negative interior error givesIndeed $r(-1)=r(1)=E_1$ and $r(c)=-E_1$; convexity puts every other error value between these extremes. The equioscillation theorem proves optimality.

For the reference-point assertions, put $M=\Vert u-q_a{\Vert }_{\infty }$. The alternating-reference error bound gives $|h_a|\le E_n$. In fact this inequality is strict here. To see the equality obstruction explicitly, let $p_n$ be optimal, $d=p_n-q_a$, andSince $d$ has polynomial degree at most $n$, its order-$(n+1)$ divided difference vanishes: ${\sum }_r{\omega }_{r}d(x_r)=0$. If $E_n=|h_a|>0$, change the overall sign to take $h_a>0$. The error bound for $p_n$ implies $(-1{)}^{r}d(x_r)\ge 0$. The signs of the weights are $(-1{)}^{n+1-r}$, so every term in this sum has the same weak sign. Every term must vanish; $d$ then has $n+2$ distinct zeros, forcing $d=0$. This contradicts $M>E_n$. If $h_a=E_n=0$, $u=p_n$ and the same zero-count argument again forces $q_a=p_n$, also a contradiction. ThusAt every old reference point the absolute error is only $|h_a|$, so a maximizer $\eta$ cannot be one of those points. The printed same-sign choice of $k$ additionally presumes $h_a\ne 0$; when $h_a=0$, none of the reference errors has the nonzero sign of the maximal error.

The printed replacement rule needs an endpoint qualification. For an interior $\eta \in (x_0,x_{n+1})$ and nonzero $h_a$, replacing the adjacent endpoint of its containing reference interval with the same error sign preserves spatial order and alternating signs. The single-point exchange in polynomial minimax approximation then gives the requested strict increase. On an irregular grid, the globally nearest same-sign reference point need not be that adjacent endpoint, so adjacency must be specified. More generally, for any correctly ordered replacement set $z_0<\cdots <z_{n+1}$ on which the old error alternates in sign, let $w_r={\prod }_{s\ne r}(z_r-z_s{)}^{-1}$. The vanished divided difference of $q_a$ and the new alternation equations showThis is a strict weighted average because all the weights are positive in absolute value and $M>|h_a|$.

For an exterior $\eta$ whose error sign is opposite that at the nearest endpoint, merely replacing the nearest same-sign point, as printed, need not preserve alternation. A concrete counterexample uses $n=2$, $q_a=0$, $h_a=1$, and reference pointsLet $u$ be the piecewise linear function through $(-1,-2),(0,1),(1/5,-1),(2/5,1),(3/5,-1),(1,-1)$. Then $M=2$ at $\eta =-1$, and $1<E_2\le 3/2<2$: the upper bound is achieved by the trial constant $-1/2$, while equality at the lower bound is excluded by the preceding zero-count argument. The printed rule selects $k=1$ and hence $z=(0,-1,2/5,3/5)$. Neverthelesssatisfy every printed new alternation equation, with $\boxed{|h_b|=61/64<1=|h_a|}$. Direct substitution at the four points checks this failure; reordering those points would destroy their assigned alternating signs.

The corrected exterior rule inserts $\eta$ as the new extreme reference point and drops the farthest endpoint when its sign is opposite the nearest endpoint. If its sign agrees with the nearest endpoint, replace that endpoint. Interior exchanges replace the adjacent reference point with the same sign. These rules preserve an ordered alternating set, so the strict-increase formula applies in every case.

The resulting Remez algorithm solves the $n+2$ linear alternation equations for the polynomial coefficients and reference height, locates a global maximum of the error, and performs a valid exchange unless $M=|h_a|$. The interval $|h_a|\le E_n\le M$ is an explicit optimality certificate; a small gap $M-|h_a|$ gives a stopping test. Strict increase of bounded reference heights alone does not prove convergence, so that stronger conclusion needs the additional analysis of the chosen exchange algorithm.

By definition, a best uniform approximation $p^{\ast }\in P_n$ minimizes $\Vert u-p{\Vert }_{\infty }$ over $p\in P_n$. Write $E=\Vert u-p^{\ast }{\Vert }_{\infty }$. The equioscillation theorem says that, if $E>0$, optimality is equivalent to the existence of $n+2$ ordered points with signed errorsThe absolute-value bars on the left of the printed formula must be omitted for this alternating-sign statement. A nonnegative absolute value cannot equal a negative $-E$.

For sufficiency, suppose a polynomial $p$ had strictly smaller error. At the alternating points, $p-p^{\ast }$ must have the same sign as $u-p^{\ast }$, since otherwise the new error would have magnitude at least $E$. The difference polynomial therefore changes sign in all $n+1$ successive gaps and has at least $n+1$ distinct roots, impossible for a nonzero element of $P_n$.

For necessity, suppose that no $n+2$ alternating extremal points exist. On the compact extremal set $K=\{x:|u(x)-p^{\ast }(x)|=E\}$, group the signs of the error into consecutive blocks. The positive and negative extremal sets are disjoint compact sets, so sign changes are separated by positive distances; the number of blocks is finite. The absence of an $n+2$ alternating selection means there are at most $n+1$ blocks. Place a root in each gap between successive blocks and choose the overall sign of their product $q$ to agree with the error on $K$. Then $\mathrm{deg}q\le n$ and $q$ is nonzero throughout $K$.

By compactness and continuity, on a neighborhood of $K$ the signs still agree and $|q|$ is bounded below. A sufficiently small positive $\eta$ reduces the error there when $p^{\ast }$ is replaced by $p^{\ast }+\eta q$. On the compact complement of this neighborhood the old error is below $E$ by a fixed positive margin, and choosing $\eta$ smaller preserves that margin. This gives a strictly better approximation, a contradiction. If $E=0$, the target already lies in $P_n$ and optimality is immediate.

For $u(x)=x^{1/3}$, the chord is $x$. Concavity gives $x^{1/3}-x\ge 0$, with maximum at $x_{\ast }=1/(3\sqrt{3})$ and maximum value $2/(3\sqrt{3})$. Shift the chord up by half that amount. The errors at $0,x_{\ast },1$ are respectively $-E,+E,-E$, so

Put $m={\min }_r|u(x_r)-q(x_r)|$ and $M={\max }_r|u(x_r)-q(x_r)|$. If the best uniform approximation had error below $m$, the values of $p_n^{\ast }-q$ would strictly alternate in sign at all $n+2$ reference points. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial of degree at most $n$, a contradiction. If $m=0$ the lower bound is immediate.

At least one reference point attains the global error maximum of $q$, so $M=\Vert u-q{\Vert }_{\infty }$. Optimality of $p_n^{\ast }$ gives the upper bound, and thereforeThis is the unequal-height version of the alternating-reference error bound.

For a line $p(x)=ax+b$, the error $e^x-ax-b$ is strictly convex. Its two endpoint maxima must agree, giving $a=e-1$. Its unique interior minimum is at $c=\log a\in (0,1)$. Equating its magnitude to the endpoint error givesThe errors at $0,c,1$ are respectively $E_1,-E_1,E_1$. The equioscillation theorem therefore certifies this best uniform approximation directly.

For degree above one, subtracting a general polynomial does not preserve convexity of the error. The required $n+2$ alternating extreme points include additional unknown interior points, and their derivative and equal-height equations form a coupled nonlinear problem. The simple endpoint-and-single-minimum calculation therefore does not extend as a direct higher-degree recipe.

For real continuous $f$, the Chebyshev alternation theorem says that $p\in {\mathcal{P}}_n$ is the unique best uniform approximation to $f$ precisely when there are $n+2$ ordered points $0\le x_0<\cdots <x_{n+1}\le 1$ and a sign $\sigma \in \{-1,1\}$ such thatHere ${\mathcal{P}}_n$ means degree at most $n$. Best approximants exist: a minimizing sequence is bounded in the finite-dimensional polynomial space, and finite-dimensional equivalence of norms gives a convergent coefficient subsequence. When $f=p$, the zero error is treated separately; the derivative-sign hypothesis below excludes that case.

Let $p_n$ be a best degree-at-most-$n$ approximant and suppose for contradiction that $E_n(f)=E_{n+1}(f)$. Since $f^{(n+1)}>0$, $f$ is not a degree-at-most-$n$ polynomial and its error is nonzero. The same $p_n$ would be best in ${\mathcal{P}}_{n+1}$, so the Chebyshev alternation theorem at that degree supplies $n+3$ alternating error extrema. The intermediate value theorem gives at least $n+2$ distinct zeros of $e=f-p_n$, one between each consecutive pair of extrema.

Repeated Rolle's theorem then forces a zero of $e^{(n+1)}$. But $p_n^{(n+1)}=0$, whereas $e^{(n+1)}=f^{(n+1)}>0$ everywhere. This contradiction provesThe argument proves strict decrease of best polynomial approximation under a derivative sign; an everywhere negative $(n+1)$st derivative gives the same strict conclusion after replacing $f$ by $-f$.

For any trigonometric polynomial $t_n$ of degree at most $n$, reproduction from (a) and the operator norm bound from (b) implyTaking the infimum over $t_n$ givesThis is the polynomial reproduction error bound with $\Vert v_n\Vert \le 3$; attaining the best uniform approximation is not needed for this inequality.

Let $p\in A$, $r=f-p$, $E=\Vert r{\Vert }_{\infty }$ and $M=\{x\in [0,1]:|r(x)|=E\}$. The Kolmogorov criterion for uniform approximation saysIf $E=0$, $p=f$ is already best and the criterion holds. Suppose $E>0$. If $q=p+h$ were strictly better, then $|r(x)-h(x)|<|r(x)|=E$ on $M$, which forces $r(x)h(x)>0$ there. Conversely, if a direction $h$ has $rh>0$ everywhere on $M$, compactness gives a positive lower bound on this product. On a sufficiently small neighborhood of $M$, $r$ and $h$ therefore have matching signs with $|h|$ bounded away from zero and $|r|$ bounded away from zero. On its compact complement, $|r|\le E-\delta$ for some $\delta >0$. Choose $\epsilon >0$ so small that $\epsilon \Vert h{\Vert }_{\infty }<\delta$ and that subtracting $\epsilon h$ does not cross zero on that neighborhood. Then $\Vert r-\epsilon h{\Vert }_{\infty }<E$, so $p$ is not a best uniform approximation. This proves both directions.

The Chebyshev alternation theorem states that $p\in {\mathcal{P}}_n$ is a best uniform approximation to real $f$ precisely when there are $n+2$ increasingly ordered points $x_0<\cdots <x_{n+1}$ withFor sufficiency, an improving polynomial direction $h$ would have to share these alternating signs, by the Kolmogorov criterion for uniform approximation. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial between consecutive points. A nonzero polynomial of degree at most $n$ cannot do that. If $E=0$, no improvement is possible anyway.

For necessity, suppose $E>0$ and the active set $M$ has no alternating sequence of length $n+2$. Its positive-error and negative-error subsets are disjoint compact sets, hence separated by a positive distance. Reading them from left to right splits $M$ into finitely many consecutive sign blocks. If there are $L$ blocks, choosing one point per block gives an alternating sequence, so $L\le n+1$. Choose $z_j$ in the gap between each consecutive pair of blocks. The polynomial $h(x)=C{\prod }_{j=1}^{L-1}(x-z_j)$ has degree at most $n$; choose the sign of $C$ to match the error on the first block. Its sign then matches the error on every block, and it is nonzero throughout $M$. Thus $rh>0$ on $M$, contradicting the Kolmogorov criterion for uniform approximation. There must therefore be $n+2$ alternating extrema.

Choose a best uniform approximation $p_n\in {\mathcal{P}}_n$. It exists because this vector subspace is a finite-dimensional vector space and a minimizing sequence $q_j$ is bounded: $\Vert q_j{\Vert }_{\infty }\le \Vert f{\Vert }_{\infty }+\Vert f-q_j{\Vert }_{\infty }$. Finite-dimensional equivalence of norms then supplies a convergent subsequence of coefficients. If $E_n(f)>0$, the Chebyshev alternation theorem gives $n+2$ alternating error extrema. The intermediate value theorem supplies a zero $x_{n,k}$ of $f-p_n$ in each of the $n+1$ intervening open intervals. These interpolation nodes are distinct, and uniqueness of polynomial interpolation givesThe convergence follows from the Weierstrass approximation theorem. If $E_n(f)=0$, choose any $n+1$ distinct nodes: the polynomial interpolant is still $f=p_n$. This constructs interpolation nodes from best uniform approximation; the nodes depend on $f$, and no universal node system for all continuous functions is asserted.

For a real continuous $2\pi$-periodic function $f$, the trigonometric Chebyshev alternation theorem says that $t^{\ast }\in {\mathcal{T}}_n$ is its best uniform approximation if and only if there are $2n+2$ distinct cyclically ordered points in one period,and a sign $\epsilon \in \{1,-1\}$ such thatThe best approximant exists and is unique. Alternation is cyclic: the last and first displayed extrema also have opposite signs across the closing interval. If the error is zero, $f=t^{\ast }$ and the characterization holds trivially.

The sufficiency can be seen from zero counting. A strictly improving trigonometric polynomial would have a difference from $t^{\ast }$ with the alternating nonzero signs at these points, forcing at least $2n+2$ zeros on the circle. A nonzero member of ${\mathcal{T}}_n$ has at most $2n$ zeros: multiplying its Laurent expression by $e^{inx}$ gives an ordinary polynomial of degree at most $2n$ in $e^{ix}$. This contradiction is the alternation mechanism used in the next part.

For real-valued $f\in C[-1,1]$, there is a unique best uniform approximation $p_{\ast }\in {\mathcal{P}}_n$, where ${\mathcal{P}}_n$ means degree at most $n$. If $E=\Vert f-p_{\ast }{\Vert }_{\infty }>0$, the Chebyshev alternation theorem characterizes it by the existence of $n+2$ ordered pointsand a sign $\epsilon \in \{-1,1\}$ such thatConversely, a polynomial in ${\mathcal{P}}_n$ whose error has this alternation is the best one. If the best error is zero, $f$ itself is the exact polynomial approximant. The real-valued qualification matters: this sign-alternation formulation is not the corresponding criterion for arbitrary complex-valued approximation.

The obstruction to a strict improvement is concrete. If $q$ had smaller error at every alternation point, $q-p_{\ast }$ would have alternating strict signs there. The intermediate value theorem would give at least $n+1$ distinct zeros, impossible for a nonzero polynomial of degree at most $n$.

The Chebyshev alternation theorem says that a polynomial $p$ of degree at most $n$ is a best uniform approximation to a real continuous function $f$ on a compact interval if and only if there are $n+2$ ordered points at which $f-p$ attains its uniform norm with alternating signs. For nonzero error these are equal-magnitude alternating extrema; the zero-error case is understood separately. The best approximating polynomial is unique.

Let $p$ be the best uniform approximation to the exponential function from the degree-at-most-$n-1$ polynomial space. Suppose that $E_{n-1}(e^x)=E_n(e^x)$. Then the same $p$ is best in the larger space. Its error $g(x)=e^x-p(x)$ is nonzero, since the exponential is not a polynomial. The Chebyshev alternation theorem supplies $n+2$ ordered points where $g$ has alternating signs. By the intermediate value theorem, $g$ has at least one zero in each of the $n+1$ intervening intervals, hence at least $n+1$ distinct zeros.

Applying Rolle's theorem successively $n$ times forces a zero of $g^{(n)}$. But $\mathrm{deg}p\le n-1$, soeverywhere. This is a contradiction. Together with the automatic non-increase of best errors, it provesThe argument is an instance of strict polynomial error decrease from nonvanishing derivatives.

For each $n$, choose the best uniform approximation $p_n^{\ast }$. If its error is nonzero, take its $n+2$ alternating extrema. The intermediate value theorem supplies a point $y_j$ strictly between the $j$th and $(j+1)$st extrema such that $f(y_j)=p_n^{\ast }(y_j)$, for $0\le j\le n$. These $n+1$ points are distinct. The polynomial interpolation problem at them has a unique solution of degree at most $n$, so its solution is exactly $p_n^{\ast }$. This constructs the interpolation nodes from best uniform approximation.

If $E_n(f)=0$, then $f$ itself belongs to the polynomial space, and any $n+1$ distinct nodes give the same conclusion. In either case, take $x_{n,j}=y_j$ or the arbitrary nodes just described. ThenThe Weierstrass approximation theorem gives $E_n(f)\to 0$; alternatively, the bound derived in part 4(b), combined with uniform continuity, gives this convergence directly. ThereforeThe nodes may depend on $f$ and on $n$. The conclusion does not assert a universal sequence of interpolation grids working for every continuous target.

For a real continuous function on $[-1,1]$, the Chebyshev alternation theorem gives a unique best uniform approximation $p_n^{\ast }$ from the space of polynomials of degree at most $n$. If $f$ is not already in that space, a candidate $p$ is best if and only if there exist ordered points $x_0<\cdots <x_{n+1}$ and a sign $\sigma \in \{1,-1\}$ withThus a nonzero best error has at least $n+2$ alternating extrema of equal magnitude. If $f$ is already a polynomial of degree at most $n$, the unique best approximant is $f$ itself with zero error.

Existence does not require assuming that the infimum is attained: a minimizing sequence has uniformly bounded polynomial norms, and evaluation at $n+1$ fixed distinct nodes bounds its coefficients through an invertible interpolation matrix. A convergent coefficient subsequence then attains the infimum. The alternation criterion characterizes that minimum and gives uniqueness. In the following parts, $n\ge 1$ whenever $E_{n-1}$ occurs.

Let $u\in \mathcal{U}$, $r=f-u$, $M=\Vert r{\Vert }_{\infty }$, and $E=\{x\in [0,1]:|r(x)|=M\}$. The Kolmogorov criterion for uniform approximation saysEquivalently, no available perturbation $v$ has strictly the same sign as the nonzero residual at every extremal point. This statement concerns a candidate $u$ in the linear subspace; it does not assume every subspace has an attained best approximation. If $M=0$, $u=f$ is already exact and the criterion is automatic.

To see sufficiency, for any competitor $u+v$, the criterion supplies an $x\in E$ with $r(x)v(x)\le 0$. Then $|f(x)-u(x)-v(x)|\ge |r(x)|=M$, so the competitor cannot have smaller supremum norm error.

For necessity, suppose $M>0$ and some $v\in \mathcal{U}$ has $r(x)v(x)>0$ on $E$. Since $E$ is compact, this product has a positive minimum there. By continuity, a neighborhood $O$ of $E$ has $rv\ge \eta >0$. For sufficiently small $\epsilon >0$,On the compact complement of $O$, $|r|$ has a strict gap below $M$, and taking $\epsilon \Vert v{\Vert }_{\infty }$ smaller than this gap preserves it. Hence $u+\epsilon v$ improves the uniform error everywhere, contradicting best uniform approximation.

For a real continuous function $f$, the Chebyshev alternation theorem asserts that a polynomial $p\in {\mathcal{P}}_n$ is a best uniform approximation exactly when either it is exact or its residual $r=f-p$ has $n+2$ ordered alternating extrema:Here ${\mathcal{P}}_n$ means degree at most $n$, as required for a linear subspace.

For sufficiency, if a polynomial perturbation $v\in {\mathcal{P}}_n$ violated the Kolmogorov criterion for uniform approximation, then $r(x_j)v(x_j)>0$ at every displayed point. Thus $v(x_j)$ would alternate signs, forcing a distinct zero in each of the $n+1$ intervals $(x_j,x_{j+1})$ by the intermediate value theorem. A nonzero polynomial of degree at most $n$ cannot have that many zeros; the zero polynomial does not violate the criterion either.

For necessity, assume $M=\Vert r{\Vert }_{\infty }>0$ and no such alternating sequence exists. The two compact sets $E_{+}=\{r=M\}$ and $E_{-}=\{r=-M\}$ are disjoint and, when both are nonempty, have positive separation. Hence the extremal set has finitely many successive sign runs: infinitely many alternations would contradict that separation on the bounded interval. If there are $m$ changes of sign between those runs, then selecting one point from each run gives an alternating sequence of length $m+1$, so $m\le n$. Choose a point $z_j$ in the gap between each pair of consecutive opposite-sign runs, and setChoose the sign of $C$ so that $v$ agrees with $r$ on the first run. The roots lie outside the extremal set and each changes the sign, so $rv>0$ at every extremal point. Since $\mathrm{deg}v=m\le n$, this contradicts the Kolmogorov criterion for uniform approximation. Therefore a best polynomial must have the required alternation.

Existence also holds: a minimizing sequence has bounded supremum norms, hence bounded coefficients by evaluating at $n+1$ fixed distinct points and inverting the resulting Vandermonde matrix. A convergent subsequence of coefficients yields a minimizer. Finally, if $p$ and $q$ are both best, their average is best; at its alternating extrema both individual residuals must equal the same extremal value. Consequently $p-q$ has at least $n+2$ zeros and is identically zero. The best polynomial exists, is unique, and is characterized by alternation.