Polynomial interpolation of binary word signal

Question

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.

Answer 1

There was a related question: 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"

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",

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.