This is a one-dimensional problem over $\mathbb{R}$. Given $y_0, y_1 \ge 0$ with $y_0 \neq y_1$, and closed intervals $I_0$ and $I_1$ with $I_0 \cap I_1 = \emptyset$, define a partial function $f(x) = y_i$ if $x \in I_i$ for $i \in \{0,1\}$. Given $\epsilon > 0$, what is the minimum degree (in terms of $\epsilon$) of a nonnegative polynomial that $\epsilon$-approximates $f$ uniformly? I.e., approximating polynomial should not differ by more than $\epsilon$ from $f$ where $f$ is defined, and on the rest of $\mathbb{R}$, it should just be nonnegative.

I am interested in both upper and lower bounds. In particular, is $O(\log(1/\epsilon))$ possible? If not, why not?

I apologize if I missed a classical theorem that gives the answer right away. My search online revealed Jackson-type theorems, but there are a few differences from the setting I am interested in - namely nonnegativity constraint and multiple compact sets, on which approximation should take place.


1 Answer 1


First, let us ignore the nonnegativity constraint on the approximating polynomial.

By linear transformation of the variable, one may suppose that $I_{0}=[-A,-1]$ and $I_{1}=[1,B]$ and by a linear transformation on the approximating polynomial $P_{n}$, one may suppose that $y_{0}=-1$ and $y_{1}=1$ (since $y_{0}\neq y_{1}$). Now, by Chebyshev's theorem, a best polynomial approximant $P_{n}(x)$ to $\text{sgn}(x)$ on $I=I_{0}\cup I_{1}$ exists and is unique. It has been proved in [1] that $$C_{1}n^{-1/2}e^{-\eta n}\leq\|P_{n}-\text{sgn}\|_{I,\infty}=\inf_{p\in\mathcal{P}_{n}}\|p-\text{sgn}\|_{I,\infty} \leq C_{2}n^{-1/2}e^{-\eta n},$$ where $C_{1}$ and $C_{2}$ are positive constants depending on $A$ and $B$, and $\eta$ is the critical value of the Green's function of the region $\mathbb{C}\setminus I$ with pole at infinity
(Ref. [1] seems difficult to find on the internet, but the above result is mentioned in Ref. [2] which is more accessible).

By the above inequality, one gets that, indeed, an $\epsilon$-approximation is achieved by a polynomial of degree $O(\log(1/\epsilon))$.

Concerning the nonnegativity constraint, obviously, it cannot be satisfied by odd approximating polynomials. For even degree $n$, it follows from the discussion on p.295 of [2] that the best approximant $P_{n}$ has at least $n-2$ critical points $x_{j}$, $j=1,\ldots,n-2$, which lie in $I$ and are alternating points for the error function, that is $|(P_{n}-\text{sign})(x_{j})|=\epsilon$. Hence, there is at most one critical point which is not an alternating point. This point is shown to belong to $\mathbb{R}\setminus[-A,B]$, and the corresponding critical value could, a priori, contradicts the nonnegativity constraint.


[1] W.H.J. Fuchs, On the degree of Chebyshev approximation on sets with several components, Izv. Akad. Nauk Armyan. SSR Ser. Mat. 13 (1978), 396-404, 541.

[2] A. Eremenko, P. Yuditskii, Polynomials of the best uniform approximation to sgn(x) on two intervals, J. Anal. Math. 114 (2011), 285-315.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.