Degree necessary of a polynomial?

Question

Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that will suffice?

What is degree as function of $a,b$ that is necessary and sufficient using chebyshev polynomials?

Is $O(1)$ degree sufficient?

Quadratic will not work. Min of quadratic goes below $[a,b]$ at some point in middle of $[b^2,a^2]$. Example take $b=−1/9,a=−1/3$. Quadratic is $3x(−13+81x)/4$ which takes min value at $x=13/162\in[1/81,1/9]$ with value $-169/432<-1/3$. Although $-((111 x)/10) + (729 x^2)/4 - (19683 x^3)/20$ seems to work. Is answer cubic always?

I think theory of Tchebyshev polynomials or Jackson's theorem in approximation theory should be useful here.

The question is about finding a polynomial that hits zero one place, and then is squeezed in a rectangle in some other region with rectangle $\mathsf{Height} = |a-b|$ here while $\mathsf{Width}=|a^2-b^2|=|(a-b)(a+b)|\leq |a-b|=\mathsf{Height}$ if $a+b\leq1$, $\mathsf{Width}=|a^2-b^2|=|(a-b)(a+b)|\geq |a-b|=\mathsf{Height}$ if $a+b\geq1$.

Answer 1

Update: The solution has been edited in order to answer a more general question.

We can always rescale to obtain the following problem: find a polynomial $f(x)$ of minimal degree such that $f(0)=0$ and $f([\beta,1])\subseteq [\alpha,1]$. Here $1>\alpha=\sqrt\beta=b/a>0$ in the original problem.

Suppose we have a polynomial $f_0(x)$ satisfying $f([\beta,1])\subseteq [\alpha,1]$, but $f_0(0)\leq 0$. Then it is possible to construct a solution to the original problem of degree $\deg f_0$ by the formula $$f(x)=\beta(f_0(x)),\quad \beta(y)=\frac{y-1}{1-f_0(0)}+1,$$ since $\beta([\alpha,1])\subseteq[\alpha,1]$.

Therefore the following is true

Lemma: The problem can be solved with a polynomial of degree $n$ if and only if $\inf_{f\in P_n} f(0)\leq 0$, where $P_n$ is the space of polynomials $f$ of degree $n$ having the property $f([\beta,1])\subseteq [\alpha,1]$.

Now, this $\inf$ is known and given by Chebyshev polynomials. Indeed, let $Q_n$ denote the space of polynomials $g$ of degree $n$ satisfying $g([-1,1])\in [-1,1]$. Then we have $$ g\in Q_n\Longrightarrow 1-(1-\alpha)\frac{g\left(1-2\frac{x-\beta}{1-\beta}\right)+1}{2}\in P_n $$ and this correspondence is bijective. Therefore, the $\inf$ in question is given by $$ \inf_{f\in P_n} f(0)=1-(1-\alpha)\frac{1+\sup_{g\in Q_n} g\left(\frac{1+\beta}{1-\beta}\right)}{2}, $$ and since $\frac{1+\beta}{1-\beta}>1$, we have $$ \sup_{g\in Q_n} g\left(\frac{1+\beta}{1-\beta}\right)=T_n\left(\frac{1+\beta}{1-\beta}\right). $$

Therefore we get the following statement

The problem can be solved in degree $n$ if and only if $T_n\left(\frac{1+\beta}{1-\beta}\right)\geq\frac{1+\alpha}{1-\alpha}$, where $0<\alpha,\beta<1$, and in the original problem $\alpha=\sqrt\beta=b/a$

Alternatively, defining $\gamma=\frac{1+\sqrt\beta}{1-\sqrt\beta}=\frac{a+b}{a-b}$, $\delta=\frac{1+\alpha}{1-\alpha}$ we get the inequality $$ \cosh (n\log\gamma)\geq\delta. $$ Looking for the threshold value, replace this by equality and obtain $$ n=\left\lceil \frac{\cosh^{-1}\delta}{\log\gamma}\right\rceil=\left\lceil \sqrt{\frac{a}{b}}\left(1+\frac{1}{3}\frac{b}{a}+O(b^2/a^2)\right)\right\rceil, $$ where the last equality sign is for the original problem. Keeping just the leading term gives a pretty good approximation.

Answer 2

Version 2

Here is some experimental evidence. Like most people here I'm using $-f(x)$ and assuming $0<b<a<1$. Consider $b=1/100$ and $a=i/100$.

For $2\le i\le 3$, there is a quadratic polynomial.
For $4\le i\le 8$, the least degree is 3.
For $9\le i\le 15$, the least degree is 4.
For $16\le i\le 24$, the least degree is 5.
For $24\le i\le 35$, the least degree is 6. - corrected as per Peter K
For $36\le i\le 48$, the least degree is 7.
For $49\le i\le 63$, the least degree is 8.
For $64\le i\le 80$, the least degree is 9.
For $81\le i\le 99$, the least degree is 10.

Turbo noticed that these cutoffs are close to squares.

Next consider $a=1-\frac1n$, $b=\frac1n$. We find:

For $3\le n\le 4$, there is a quadratic poynomial.
For $5\le n\le 9$, the least degree is 3.
For $10\le n\le 16$, the least degree is 4.
For $17\le n\le 25$, the least degree is 5.
For $26\le n\le 36$, the least degree is 6.
For $37\le n\le 49$, the least degree is 7.
For $50\le n\le 64$, the least degree is 8.
For $65\le n\le 81$, the least degree is 9.
For $82\le n\le 100$, the least degree is 10.
For $101\le n\le 121$, the least degree is 11.
For $122\le n\le 144$, the least degree is 12.

Turbo's square-root conjecture is looking pretty good, and I see PeterKravchuk has proved it. The solutions look very much like scaled-and-shifted Chebyshev polynomials inside the box and surely that is the place to look for an analytic upper bound on the degree.

Here is my method. We are looking for $c_1,\ldots,c_d$ such that $f(x)=c_1x+\cdots +c_dx^d$ has the desired properties. Let $X$ be some finite subset of $[b^2,a^2]$ including the two endpoints. Initially I take $X$ to consist of $2d+1$ points uniformly spaced.

Make a linear program whose variables are $m,c_1,\ldots,c_d$ and whose constraints are $f(x)\in[b+m,a-m]$ for $x\in X$ and $m\ge 0$. Maximize $m$. If the constraints are infeasible, we have proved that no good polynomial of degree at most $d$ exists. If there is a solution, let $f(x)$ be that polynomial. Check if $f(x)$ is good by finding its turning points and evaluating $f(x)$ there. (Alternatively, use Sturm sequences to prove this in rational arithmetic.) If $f(x)$ is good, we are done; if not, add (an accurate rational approximation of) the turning points of $f(x)$ to $X$ and repeat.

This method won't work if there are only solutions which hit the bounds exactly, but I didn't find any other case when it doesn't work. Usually only 2 or 3 iterations are needed.

Maple worksheets: version 16, older version (not tested).

Answer 3

The requirement that $f(0)=0$ and that $f(x)$ is a polynomial allows us to rewrite the problem: What polynomial $g(x)$ is there so that $f(x)=xg(x)$ meets the desired restrictions? We can now ignore $x=0$ and ask what polynomial fits between the two hyperbolas $y= b^2/x$ and $y=a^2/x$ in the interval $[a,b] \subset [-1,0]$?

I first picture the target endpoints which are vertical lines with ordinates between $b^2/a$ and $a$ at abcissa $a$, and the other with ordinates between $b$ and $a^2/b$ at abcissa $b$ . (In case I have the terms wrong, draw your own picture.) What makes the problem interesting is that the coordinates depend only on two parameters $b$ and $a$; for four parameters $c$ and $d$ replacing $a^2$ and $b^2$, it should be easy to generate examples which require polynomials of arbitrarily high degree.

I have not put pencil to paper on this, but my mental picture tells me that for both $a$ and $b$ greater than -1/2, or both less than -1/2, a linear function $g(x)$ will thread both needles simultaneously, and that it gets more challenging when $a$ and $b$ are further apart on both sides of 1/2. Even then, I imagine a low degree polynomial is needed for these cases.

I suspect $g(x)$ of the form $K\cdot$Cheybshev$/x$ will yield to a similar analysis.

Gerhard "Coffee First; Opinion Change Later" Paseman, 2015.05.05