Let consider a binary word $x\_1 \ldots x\_n$ (finite sequence of elements of $\{0,1\}$.


I want to construct a polynomial $P$ that interpolates the points $(i, x\_i)$ for $i \in \{1\ldots n\}$ , such that:


* $P(x) \neq 0,1 $ for all $x \in [0,n]$ and $x \neq 1,\ldots n$
* $P(x) \in [0,1]$ for all $x \in [0,n]$
* $\deg P = \mathcal{O} (e^n)$


In a word, P interpolates the word and is contained in $(0,1)$ at the non-integers points (and can of course do anything outside $[0,n]$).


I was thinking to approximate a $C^\infty$ function that does the job - and of course interpolate the considered points, but I've not managed to control the polynomial in order not to get greater than 1 (or lower than 0).


It seems possible to do it with splines but I am looking for a polynomial. 



Polynomial interpolation of binary word signal
There was a related question:
[Finite interpolation by a nondecreasing polynomial](https://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial) with a satisfactory answer. The last two papers cited there allow to find the required polynomial.


The results of the first paper


[E. Passow, L. Raymon, "The degree of piecewise monotone interpolation"](http://www.jstor.org/stable/2040274)


allow to obtain a polynomial of exponential degree (although the base of the exponent seems to be larger than $e$, when we apply it directly). I do not provide the details, in view of what follows. **EDIT.** The results of this paper, however, may also be applied in what follows; see next edit.


The second paper,


[G.L Iliev, "Exact estimates for monotone interpolation"](http://www.sciencedirect.com/science/article/pii/0021904580900829#),


seems to allow even polynomial bound for the degree in your special case. It suffices to apply the following trick.


Take the Chebyshev polynomial, say $T\_{1000n}(x)$. It alternately attains the values $\pm1$ at known points. The polynomial $Q(x)=(T\_{1000n}(x)+1)/2$ alternatively attains $0$ and $1$, and its values are in $[0,1]$. Now choose some points $0=a\_0<a\_1<\dots<a\_n<1$ with $Q(a\_i)=x\_i$ ($i=1,2,\dots,n$), so that $A=\max|a\_i-a\_{i-1}|$ and $B=\min|a\_i-a\_{i-1}|$ differ by factor of less than, say, 1000. It is clearly possible, if we choose them in a greedy way. As a result, $Q(a\_i)=x\_i$, and the values of $Q$ on $[a\_0,a\_n]$ lie in $[0,1]$.


Now we have two problems: (1) the points $a\_i$ are not distributed uniformly, and (2) there are other points on $[a\_0,a\_n]$ where $Q$ attains $0$ or $1$. We start with (2), then resolving (1).


(2) is easily curable in the following way: we may add to $Q$ a polynomial of the form 
$$
 \delta Q(x)=\varepsilon\prod\_{i=1}^n(x-a\_i)^2\cdot \prod\_j(x-b\_j),
$$ 
where $b\_j$ are chosen so that $\delta Q(x)$ is positive around $a\_i$ if $x\_i=0$ and negative if $x\_i=1$. If $b\_j$ are chosen appropriately, and $\varepsilon$ is small enough, then the values of $R(x)=Q(x)+\delta Q(x)$ on $[a\_0,a\_n]$ are still on $[0,1]$, but $R$ attains the values $0,1$ exactly at $a\_1,\dots,a\_n$. 


We are left with (1). Now, we apply the result of the aforementioned paper by Iliev in order to find a polynomial $S(x)$ which is monotonous on $[0,1]$ and satisfies $S(i/n)=a\_i$. Its degree is bounded as
$$
 \deg S\leq cn\ln\left(e+A/B\right)
$$
for some absolute constant $c$, thus by a linear function in $n$. **EDIT.** As Iliev claims, the first cited paper also provides linear degree of a polynomial in the monotonic case, namely $\leq c'nA/B$; sorry, I haven't checked this yet.


Finally, the polynomial $R(S(nx))$ does the job.


