Polynomials with prescribed points to match prescribed bounds Consider real polynomials on the interval $I=[-1,1]$. It is easy
to see that the smallest degree for a non-negative polynomial
with given zeros $x_1,\dots,x_s\in I^\circ$ is $n=2s$ (e.g.
$P(x) = \prod_{i=1}^s (x-x_i)^2$ works).

My question is:
What is the smallest degree for a polynomial such that it is
bounded by $\pm 1$ on $I$ and attains the value $1$ on a set
$x_1^+,\dots,x_s^+$ and the value $-1$ on a set
$x_1^-,\dots,x_r^-$?

Background: I know that the fact about nonnegative polynomials
with presribed zeros can be generalized to "generalized
polynomials" built from Tchebycheff-systems (due to a theorem by
Krein). I would love to see a similar theorem on bounded
generalized polynomials which attain the bounds at prescribed points.
Edit: In this question I leanerd from the answer of Gjergji Zaimi that there are bounds on the degree of increasing interpolating polyomials. How does the bounds change for monotone interpolation are described above? Are there (algebraical or numerical) methods to calculate the polynomial?
It seems to me that monotone interpolating polynomials are not treated in the current literature and are not subject of current research. Is that right, and if so is there a special reason for that?
 A: Let $D$ be the minimum distance between $x$'s, merging all the $x$'s into one list of length $N$.
Let $k$ be an integer $\ge \max(16\log(8/D^2),10N)\ /\ D^2$.
Then a polynomial of degree of $6(k+1)(N-1)$ suffices.
Proof:
Let $p(x) = \frac{1}{2}(3 q(x) - q^3(x))$, where $q(x) = \sum_i \pm \Pi_{j \neq i} r_{ij}(x)$ and
$$r_{ij}(x) = \left(1-\frac{(x-x_i)^2}{4}\right)^k \frac{(x-x_j)^2}{(x_i-x_j)^2}$$
Then $p$ is clearly of the specified degree, and has the specified values at the $x_i$'s.
The key is to show that $p$ is bounded by $\pm1$.
Small terms:  When $|x-x_i| > D/2$, $r_{ij}(x) \le (1-D^2/16)^k (4/D^2) < 
%(1-D^2/16)^{\large(16/D^2)\log(8/D^2)}(4/D^2) <
1/2$, so $\Pi_{j \neq i} r_{ij}(x) < 2^{-(N-1)}$.
Large terms:  When $|x-x_i| < D/2$,
$$r_{ij}(x)
\le
\left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 - \frac{x-x_i}{x_j-x_i}\right)^2
\le
\left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 + \frac{2|x-x_i|}{kD}\right)^k
$$
$$
\le
\left(1+ \frac{2|x-x_i|}{kD}-\frac{(x-x_i)^2}{4}\right)^k
\le
\left(1+\frac{4}{k^2D^2}\right)^k
\le
e^{\large 4/D^2k}
\le
e^{\large 4/10N}
\le
(3/2)^{\large 1/N}.
$$
So $\Pi_{j \neq i} r_{ij}(x) < 3/2$
Since each $x$ is within $D/2$ of at most one $x_i$, $q(x)$ is the sum of at most one
large term bounded by 3/2, and by $N-1$ small terms bounded by $2^{-(N-1)}$.   So $|q|\le2$,
and $|p|\le1$.
