6
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ You understand that the answer depends heavily on the location of the points and, thereby, is by no means as simple and clean as in the non-negative case, right? $\endgroup$
    – fedja
    Nov 3, 2011 at 13:17
  • $\begingroup$ That is pretty clear. I am willing to add more assumptions and not hoping for a very clean answer. $\endgroup$
    – Dirk
    Nov 3, 2011 at 13:35
  • $\begingroup$ @Dirk and @fedia: why does such a polynomial exist for every choice of $x^+, x^-$? Say, what is the polynomial if $x_1^+=1/5, x_2^+=1/4, x_1^-=1/3, x_2^-=1/2$? $\endgroup$
    – user6976
    Nov 3, 2011 at 22:13
  • $\begingroup$ Such a polynomial always exists: Take a Chebycheff polynomial $P$ of degree high enough (such that is attains the values 1 and -1 in the right order at point $t_i$. Then choose a monotone polynomial $Q$ which maps the points $t_i$ to the prescribed $x_i$ and take $P\circ Q$. Such monotone polynomial interpolants exit by a theorem of Young (ams.org/mathscinet-getitem?mr=0212455). $\endgroup$
    – Dirk
    Nov 4, 2011 at 7:58
  • $\begingroup$ Oh, there is a simpler argument: Since there are piecewise monotone interpolating polynomials we can use them directly to interpolate the $x^+$ and $x^-$ (and possibly adding zero interpolation points inbetween). $\endgroup$
    – Dirk
    Nov 4, 2011 at 8:56

1 Answer 1

4
+100
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ That looks very interesting! Christmas time prevents that I check the answer in detail right now and since I am not sure, if I am going to come back here in due time I check this answer as correct right now to cash the bounty. Maybe I'll come back with questions later. $\endgroup$
    – Dirk
    Dec 26, 2013 at 17:28
  • 1
    $\begingroup$ Dirk, happy to answer any questions. For what it's worth, you can check that, e.g. $p$ behaves appropriately in @Mark Sapir's example, with $k=51654$, $q=250000 \left(1-\frac{1}{4} \left(x-\frac{1}{5}\right)^2\right)^{3k} (x-1/2)^2(x-1/3)^2(x-1/4)^2+921600 \left(1-\frac{1}{4} \left(x-\frac{1}{4}\right)^2\right)^{3k} (x-1/2)^2(x-1/3)^2(x-1/5)^2-291600 \left(1-\frac{1}{4} \left(x-\frac{1}{3}\right)^2\right)^{3k}(x-1/2)^2(x-1/4)^2(x-1/5)^2-6400 \left(1-\frac{1}{4} \left(x-\frac{1}{2}\right)^2\right)^{3k} (x-1/3)^2 (x-1/4)^2 (x-1/5)^2$. $\endgroup$
    – user44143
    Dec 29, 2013 at 11:06
  • $\begingroup$ Hah, that is a pretty compelling example Matt F. $\endgroup$ Sep 17, 2017 at 18:13

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.