# Polynomial interpolation of binary word signal

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.

• If $i\in \{1,\dots,n\}$ and $$x_j:=\begin{cases} 1 & j=i\\ 0 & \text{otherwise}\end{cases}$$ an ansatz is $$P(x)=\prod_{j\neq i} \left(\frac{x-j}{i-j} \right)^2\left(2- \frac{x-j}{i-j} \right)^2.$$ At least this function has the property that it interpolates and it is local minima or maxima at integers. The other case can maybe done by superposition and different exponents. – user35593 Aug 7 '15 at 12:32
• More generally you can choose $$P(x):=\prod_{j\neq i} p\left(\frac{x-j}{i-j}\right)$$ where $p$ is any polynomial with $p(0)=0$, $p(1)=1$, $p'(0)=0$ $p'(1)=0$ and $p(x)\in [-1,1]$ for all $x\in [-n,n]$. – user35593 Aug 7 '15 at 12:39
• @user35593: I do not think that $p(x)=x^2(2-x)^2$ satisfies your conditions if $n$ is large... – Ilya Bogdanov Aug 27 '15 at 10:04
• Yes, you are correct. This was just an idea. I think for every $n$ it should be possible to find a polynomial which satisfies the conditions above. However I don't have an explicit expression for such a polynomial nor do I no how to control the degree... – user35593 Aug 27 '15 at 14:17
• Yes you can recover what is needed by tweaking these kind of polynomials. – user70925 Oct 12 '15 at 9:04

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,

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.