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

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