 Solution

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.