Real polynomial bounded at inverse-integer points

Question

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

Answer 1

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.