Let $d\in\mathbf{N}$ be as follows: there exists a polynomial $P(x)$ with degree $n>1$ and integer coefficients, such that $P$ has $n+1$ integer solutions to \begin{equation*} 0\leq P(x) \leq d \end{equation*} What is the minimum possible value of $d$? What if $P$ has $n+2$ integer solutions?

$\begingroup$ Note that a trivial upper bound for $n+1$ solutions is $k!^2$ for even $n=2k$ and $k!(k+1)!$ for $n=2k+1$. I wouldn't be too surprised if those bounds are sharp... $\endgroup$ – Wolfgang Jan 5 at 17:23

$\begingroup$ In fact we can do better sometimes. For $n=6$, take $P(x)=(1x^2)(3x^2)(9x^2)$ then $d=27<36$. Fascinating problem! $\endgroup$ – Wolfgang Jan 5 at 17:38

$\begingroup$ For any such polynomial P, you can scale it with a large integer K. Then KP has fewer integer solutions to the given inequalities. Gerhard "Just Stretch The Axis Some" Paseman, 2019.01.05. $\endgroup$ – Gerhard Paseman Jan 5 at 17:41

$\begingroup$ @ChristianRemling: You are correct. I have modified the problem. $\endgroup$ – Haoran Chen Jan 6 at 2:01

1$\begingroup$ @Wolfgang: Thanks, I got that luck! For $n=16$ we have the minimal $d=16!/2^{!5}=638\,512\,875$ with a polynomial $P_{16}(x)=x^2(x^24)(x^216)(x^236)(x^264)(x^680x^4+1684x^28040)$. Double check is very welcome... $\endgroup$ – Ilya Bogdanov Jan 6 at 19:06
Let $x_0<\dots<x_n$ be the points where small values $y_0,\dots,y_n$ are attained. By Lagrange's interpolation formula, the number $$ \sum_{i=0}^n y_i\cdot\left(\prod_{j\neq i} (x_ix_j)\right)^{1} \qquad(*) $$ is a nonzero integer $p$, as it is the leading coefficient of $P$. This yields an easy lower bound for the maximum of the $y_i$, as the inverse to the sum of a half of the coefficients in $(*)$ (even or odd ones, depending on the sign of $p$).
This bound is minimal when $x_i=i$, and in this case both bounds equal $ n!/2^{n1}$. Hence this is a total lower bound. It seems to differ from the upper bound mentioned by @Wolfgang in the comment by a factor of $\Theta(\sqrt n)$.
On the other hand, perhaps, this bound may even be (almost) achieved, especially when it is integral (which happens when $n$ is a power of 2)?

$\begingroup$ Yes asymptotically they differ by $\frac18\sqrt{2\pi n}\approx .31\sqrt{ n} $. $\endgroup$ – Wolfgang Jan 6 at 8:06

$\begingroup$ You may want to add the construction you found, as it generalizes indeed for $n=2^k$, just by Lagrange interpolation for the odd values $P(n+1)=P(n+3)=\cdots=P(n1)=d$ between the even ones $P(n)=P(n+2)=\cdots=P(n)=0$. It is easy to see from the factors of $d$ that the coefficients must be integers. E.g. for $n=32$, it is $ x^2(x^24)\cdots (x^216^2 )(x^{14}  672x^{12} + 174200x^{10}  22119856x^8 + 1443224772x^6  46275602672x^4 + 625295296152x^2  2334623374800)$. $\endgroup$ – Wolfgang Jan 7 at 8:59

$\begingroup$ @Wolfgang: I've learned from Maple that the coefficients are integer, but I'm still thinking on how to prove that... My trouble is with powers of 2 only. $\endgroup$ – Ilya Bogdanov Jan 7 at 9:45

$\begingroup$ Right, I neglected those. Empirically, if for $n=2^k$ the last factor is denoted $(a_{2^{k1}} x^{2^k2}+a_{2^{k1}1} x^{2^k4}\cdots+a_2x^2+a_1)$, then the 2valuations of the coefficients seem to be $\nu_2(a_i)=k\nu_2(i)$ for all except the leading and the next one. Thus an even stronger conjecture (checked till $k=8$), but I don't know if that helps. $\endgroup$ – Wolfgang Jan 7 at 12:06