9
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ The answer to the first paragraph is 2: it's easy to see that 1 isn't sufficient, but on the other hand the unique quadratic going through the origin, $(b^2, b)$, and $(a^2, a)$ has the desired property. I don't think this is appropriate for MO. $\endgroup$ May 5, 2015 at 12:06
  • $\begingroup$ Yes, draw the picture. $\endgroup$ May 5, 2015 at 12:08
  • 2
    $\begingroup$ I think this is actually a reasonable question. The question is about finding a polynomial that hits zero one place, and then is squeezed in a rectangle in some other region. Intuitively, I would expect the required degree to go up as the rectangle gets longer. $\endgroup$ May 5, 2015 at 14:06
  • 2
    $\begingroup$ Although bounds have been given, I think it is still worth noting a simple argument that no constant degree suffices. You can rescale the problem to say that you restrict the polynomial to take values between $-1$ and $1$ on the interval $[-1,1]$, and ask for the polynomial to take the value $y_0$ at the point $x_0$. The set of polynomials of a fixed degree satisfying the condition on the interval is compact, so for any $x_0$, the set of values taken by the polynomials is compact, hence not all of $\mathbb R$. $\endgroup$ May 6, 2015 at 11:42
  • 1
    $\begingroup$ Doug is rescaling and shifting so that the $x$ window changes from $[b^2,a^2]$ to $[-1,1]$ and the $y$ window changes from $[a,b]$ to $[-1,1]$. After the rescaling $x_0$ and $y_0$ will both be varying. $\endgroup$ May 6, 2015 at 21:24

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ @Turbo, yes, it is just one of their extremal properties. I should have probably stated this more explicitly. $\endgroup$ May 6, 2015 at 6:39
  • $\begingroup$ @Turbo I believe the same strategy applies. You just have to shift and rescale the Chebyshev polynomial to the new box and check if the result is non-positive at 0. $\endgroup$ May 6, 2015 at 6:42
  • $\begingroup$ @Turbo, Oh sorry I misread your first question. The statement follows because since we computed the $\inf$ using this $\sup$, we can just plug it into the lemma. $\endgroup$ May 6, 2015 at 6:47
  • $\begingroup$ @Turbo, my final formula does not apply to your new problem. You will have to modify the solution a little. If you understand this one, then it should be no problem. The answer should be like $\alpha(T_n(\beta(0)))\geq 0$, where $\alpha$ maps $[-1,1]$ linearly onto $[a,b]$ and $\beta$ maps $[c,d]$ linearly onto $[-1,1]$. $\endgroup$ May 6, 2015 at 6:48
  • $\begingroup$ How did you get "The problem can be solved in degree $n$ if and only if $T_n\left(\frac{1+\alpha}{1-\alpha}\right)\geq\frac{1+\sqrt\alpha}{1-\sqrt\alpha}$, $\alpha=b^2/a^2$"? I mean why does $\geq \frac{1+\sqrt\alpha}{1-\sqrt\alpha}$ hold? $\endgroup$
    – Turbo
    May 8, 2015 at 1:56
4
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Just curious. How did you convert this to linear programming problem? $\endgroup$
    – Turbo
    May 6, 2015 at 3:46
  • $\begingroup$ Are you guessing truth is close to $\mathsf{degree}\approx 1+\sqrt{\frac{a}b}$ if $a+b<1$? $\endgroup$
    – Turbo
    May 6, 2015 at 3:49
  • $\begingroup$ @Turbo: I'll add this in a few hours. $\endgroup$ May 6, 2015 at 4:16
  • $\begingroup$ @BrendanMcKay, I might be disagreeing with you in some borderline cases. E.g. I think $i=35$ should be possible with $n=6$. $\endgroup$ May 6, 2015 at 5:29
  • 1
    $\begingroup$ @Turbo: I added links. $\endgroup$ May 6, 2015 at 9:03
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I see the example with both a and b greater than -1/2. I guess that will be the problematic section. Gerhard "Time To Get A Pencil" Paseman, 2015.05.05 $\endgroup$ May 5, 2015 at 16:50
  • $\begingroup$ What is degree of Tchebyshev Polynomial that is needed? $\endgroup$
    – Turbo
    May 6, 2015 at 2:58

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.