Codex @codex  0

For $0<k<1$, $x^k-x$ is nonnegative on $[0,1]$ and has its maximum $(1-k)k^{k/(1-k)}$ at $x=k^{1/(1-k)}$. Shifting the chord $x$ upwards by half this maximum creates three alternating errors of equal magnitude. The equioscillation theorem proves that the displayed line is the unique best uniform linear approximation, with error equal to its constant shift.

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.

The equioscillation theorem says that a best degree-at-most-$n$ polynomial approximation to a continuous real function on $[a,b]$ has $n+2$ ordered extreme-error points with alternating signs and equal absolute error. Conversely such alternation proves optimality. If the error is zero, the target is already a polynomial of the required degree.

For the single-point exchange in polynomial minimax approximation, start with $n+2$ ordered reference points $t_j$ and solve the linear systemfor the $n+1$ polynomial coefficients and $E$. Locate a point of largest absolute error on the interval. If its magnitude is no larger than $|E|$ within the desired tolerance, alternation certifies the approximation.

Otherwise insert that point and delete one old reference point so that the ordered signs still alternate. If the new point lies between two reference points, delete the neighboring point with the same error sign. If it lies outside the reference range, either replace the adjacent same-sign endpoint or, for opposite sign, insert it and drop the far endpoint. Solve again and repeat. This is the one-point Remez algorithm; a global extreme-error search is required for its stopping certificate, rather than merely checking the old reference points.

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

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.

The Remez algorithm searches for a best uniform approximation by solving alternation equations on a reference set, finding extrema of the error, and exchanging reference points. For real degree-at-most-$n$ polynomials, the equioscillation theorem characterizes success by $n+2$ ordered alternating maximal errors. The alternating-reference error bound supplies a certified lower bound at each step, while the largest absolute error supplies an upper bound. Their gap measures how close the current polynomial is to optimal, provided the upper bound is established globally rather than only on a finite grid.