11
$\begingroup$

Let $p$ be a real polynomial and $N$ be a positive integer. Suppose I tell you that $|p(\frac{1}{k})| \le 1$ for all $k\in\{1,\ldots,N\}$, and also that $p(\frac{1}{N})\le -\frac{1}{2}$ while $p(\frac{2}{N})\ge \frac{1}{2}$. What bounds can you give me on the minimal possible degree $\deg(p)$?

An upper bound of $O(\sqrt{N})$ follows by considering the Chebyshev polynomials (which indeed are bounded everywhere in $[0,1]$, not just at the inverse-integer points).

On the other hand, the best lower bound I could show was $\deg(p)=\Omega(N^{1/4})$. This follows by restricting our attention to the interval $[\frac{1}{N},\frac{1}{\sqrt{N}}]$, which has no point more than about $1/N$ away from an inverse-integer point, and where (by assumption) $p$ also attains a large first derivative somewhere. We then apply standard results from approximation theory about polynomials bounded at discrete points, due to, e.g., Ehlich, Zeller, Coppersmith, Rivlin, and Cheney. Unfortunately the original papers seem to be paywalled, but the idea here is just to say that either $|p(x)|=O(1)$ in the entire interval $[\frac{1}{N},\frac{1}{\sqrt{N}}]$, in which case we can directly use Markov's inequality to lower-bound its degree, or else $p$ goes on some crazy excursion in between two of the discrete points at which it's bounded (say $\frac{1}{k}$ and $\frac{1}{k-1}$), in which case it attains a proportionately larger derivative there, so Markov's inequality can again be applied.

My question is whether there are any fancier tools from approximation theory that yield a better lower bound on the degree, like $\Omega(N^{1/3})$ or conceivably even $\Omega(\sqrt{N})$.

In case it helps: I already tried ransacking the approximation theory literature, but while I found many papers about polynomials bounded at evenly-spaced points, I found next to nothing about unevenly-spaced points (maybe I didn't know the right search terms). I also tried using Bernstein's inequality, which often yields better lower bounds on degree than Markov's inequality. But the trouble is that Bernstein's inequality is only useful if our polynomial attains a large first derivative far away from the endpoints of the interval where we're studying it (i.e., towards the center of the interval). And it seems that that can't be guaranteed here, basically because the interval $[0,1]$ has precious few inverse-integer points that are anywhere close to its endpoint of $1$.

$\endgroup$
  • $\begingroup$ Yes, that's what I meant (edited to clarify). $\endgroup$ – Scott Aaronson Jun 5 '18 at 20:10
  • $\begingroup$ I don't understand the "paywalled" comment. Surely your university subscribes?! $\endgroup$ – Igor Rivin Jun 5 '18 at 20:11
  • 4
    $\begingroup$ Yes, I was able to access some by proxy server. Others my university library did not have. In any case, I prefer to link to stuff that anyone reading my question can see. In that spirit, the following paper by Nisan and Szegedy has a nice self-contained proof of the "Ehlich-Zeller-Rivlin-Cheney theorem": hebuntu.cs.huji.ac.il/~noam/degree.ps It also, of course, has the bibliographic references. $\endgroup$ – Scott Aaronson Jun 5 '18 at 20:22
  • $\begingroup$ $N^{1/3}$ seems to be the right answer (up to a constant factor, of course), but that is just a back of envelope computation with no warranty attached to it. $\endgroup$ – fedja Jun 6 '18 at 3:25
  • $\begingroup$ I also did a back-of-the-envelope calculation last night that led me to wonder whether $N^{1/3}$ was the right answer -- but I could prove it neither as an upper bound nor as a lower bound. $\endgroup$ – Scott Aaronson Jun 6 '18 at 5:17
18
$\begingroup$

Part I: $CN^{1/3}$ is enough.

Start with $P(x)=\prod_{k\le N^{1/3}}(1-k^2x^2)$. Notice that it vanishes at $1/k$ with $k\le N^{1/3}$, is bounded by $1$ on $[0,N^{-1/3}]$, the degree of $P$ is $2N^{1/3}$ and on the interval $[0,2N^{-1}]$ we have $\log P\ge -2\sum_{k\le N^{1/3}}\frac{4k^2}{N^2}=o(1)$. Now just take the Chebyshev polynomial $Q$ of degree $N^{1/3}$ adjusted to the interval $[0,N^{-1/3}]$. It will jump as you requested between $N^{-1}$ and $2N^{-1}$ and stay below $1$ on $[0,N^{-1/3}]$. The product $P(x)Q(x)$ will then satisfy all your conditions.

Part 2: $n<cN^{1/3}$ is insufficient

One thing that is written in every decent textbook addressing such inequalities is that, in principle, you need no fancy tools for them. Everything can be derived directly from the Lagrange interpolation formula if you can guess the right nodes to use. This is just the general linear programming mumbo-jumbo.

So, the question is how to get the right nodes in your setting. If you do not care about constant factors, then the canonical set of nodes for human consumption is just $\{k^2:k=0,1,\dots,n\}$. Let's recall how it works. Suppose you know the values $P(0),P(1),P(4),\dots,P(n^2)$ of a polynomial of degree $N$ and want to estimate $P'(-y), 0<y<1$ or something like that. You just write $$ P(x)=\sum_{k=0}^n P(k)L_k(x) $$ where $$ L_k(x)=\frac {\prod_{m:\ne k}(x-m^2)}{\prod_{m:m\ne k}(k^2-m^2)} $$ and estimate $$ |P'(-y)|\le\max_k|P(k^2)|\sum_k |L'_k(-y)| $$ Now let us estimate $|L'_k(-y)|$. It is just $$ |L_k(-y)|\sum_{m:m\ne k}\frac 1{y+m^2} $$ Now, $$ |L_k(y)|=\frac{\prod_{m:m\ne k}(y+m^2)}{\prod_{m:m\ne k}(|m-k|(m+k))} $$ If $k=0$, then the numerator is $\le (n!)^2\prod_{m=1}^n(1+\frac y{m^2})\le C(n!)^2$ while the denominator is exactly $(n!)^2$. Thus $|L_0(-y)|\le C$ whence $$ |L_0'(-y)|\le C\sum_{m=1}^n\frac 1{y+m^2}\le C\,. $$ If $k>0$, then the numerator in $L_k(-y)$ is at most $Cy\frac 1{k^2}(n!)^2$ (the same count except now $y=|-y-0|$ is present and $y+k^2=|-y-k^2|$ is missing) while the denominator is $$ \frac{k!(n-k)!(n+k)!}{2k(k-1)!}=\frac{(n-k)!(n+k)!}{2} $$ whence $$ |L_k'(-y)|\le \left(\frac 1y+\sum_{m\ge 1}\frac 1{y+m^2}\right)|L_k(-y)|\le \frac C{k^2}\frac{(n!)^2}{(n-k)!(n+k)!}\le \frac C{k^2}e^{-k^2/n}\,. $$ Thus we can easily derive from here that $$ |P'(-y)|\le C\sum_{k=0}^n |P(k^2)|\frac 1{k^2+1}e^{-k^2/n}\,. $$

Now choose an integer $M$ such that $n^3<c M\le c^2N$ where $c>0$ is some small constant. Consider the nodes $x_k=\frac 1M+\frac{k^2}{M}, k=0,1,\dots,n$. If they were available, that would be the end of the story (we would get an estimate $CM$ for the derivative on $[0, M^{-1}]$). Unfortunately only $\frac 1M$ is surely there and the rest have to be approximated. Note that for any $x\in[0,1]$, the nearest to $x$ inverse integer is within $x^2$ from $x$. So, if we choose $z_k$ to be the closest inverse integers to $x_k$, we'll have $|x_k-z_k|\le x_k^2\le 4\frac{k^4}{M^2}$ for $k>0$. Note that the distance from $x_k$ to any neighboring node is about $\frac kM$, so the shift $4\frac{k^4}{M^2}\le 4\frac{n^3}M\frac kM\le 4c\frac kM$ is small compared to it and we, indeed, get $n+1$ different nodes.

Let us now look at how different the corresponding elementary Lagrange polynomials $$ \widetilde L_k(x)=\frac{\prod_{m:m\ne k}(x-z_m)}{\prod_{m:m\ne k}(z_k-z_m)} $$ are from the polynomials $L_k(x)$ built on the canonical nodes $x_k$ on the interval $[0,\frac 1M]$.

The numerator:

We have $\frac {|x-z_m|}{|x-x_m|}\le 1+\frac {4m^2}{M}$, so the numerator can grow at most $\prod_{m=1}^n (1+\frac {4m^2}{M})\le e^{4n^3/M}\le 2$ times.

The denominator:

If $k=0$, then we have $\frac{z_m}{x_m}\ge 1-\frac {4m^2}{M}$, so, as above, we see that it can drop at most twice.

If $k>0$, then $$ \frac {|z_k-z_m|}{|x_k-x_m|}\ge 1-\frac {4(m^4+k^4)}{M|k^2-m^2|}\ge 1-\frac {4(m^3+k^3)}{M|k-m|} $$ We also have $$ \sum_{m:0\le m\le 2k,m\ne k}\frac {4(m^3+k^3)}{M|k-m|}\le C\frac{k^3}M(1+\log k) $$ and $$ \sum_{m:2k\le m\le n}\frac {4(m^3+k^3)}{M|k-m|}\le C\sum_{m:2k\le m\le n}\frac {m^2}{M}\le C\frac {n^3}{M}<1 $$ Thus, the ratio of the denominators we can have against us is at most $Ck^{Ck^3/M}$. That is played against the decay $k^{-2}e^{-k^2/n}$ and it is clear that the decay wins (say, because the power on $k$ in the growth factor is always below $1/2$; we have plenty of leeway here).

For the transition from the value to the derivative, we can change the distances $x-x_m$ even twice without changing the corresponding factor too much, so we are done.

$\endgroup$
  • 7
    $\begingroup$ I love your line "One thing that is written in every decent textbook ...," when, obviously, this is the first time this piece of wisdom has been shared in print. $\endgroup$ – Christian Remling Jun 7 '18 at 2:46
  • $\begingroup$ This is awesome!! I also had the idea of multiplying a Chebyshev polynomial on $[0,N^{-1/3}]$ by a polynomial of degree ~$N^{1/3}$ that would simply zero out the remaining points, but I didn't see why doing so would preserve boundedness. $\endgroup$ – Scott Aaronson Jun 7 '18 at 4:46
  • $\begingroup$ I'd like to add a note to a paper to the effect, "while it's not automatic, it seems likely that the degree lower bound from this MO post could be used to improve this complexity lower bound from $\Omega(N^{1/4})$ to $\Omega(N^{1/3})$, closer to the upper bound of $O(\sqrt{N})$." If I do so, should I acknowledge you as "fedja" or should I use a full name? Thanks! $\endgroup$ – Scott Aaronson Jun 7 '18 at 4:49
  • $\begingroup$ On further thought, I think I can get a modest improvement to my complexity lower bound already from this. fedja, would you like to be added as a coauthor of a quantum algorithms paper, with me doing almost all the work, or would you prefer just a prominent acknowledgment? Shoot me an email at aaronson@cs.utexas.edu if you'd like to discuss. $\endgroup$ – Scott Aaronson Jun 7 '18 at 8:30
  • 1
    $\begingroup$ @ScottAaronson Mentioning MO is more than sufficient as far as I am concerned, but I'm glad my 2 cents helped :-) $\endgroup$ – fedja Jun 7 '18 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.