# Deg $n$ integral polynomial $P(x)$ with $n+1$ integer solutions to $0\leq P\leq d$

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?

• 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... – Wolfgang Jan 5 '19 at 17:23
• In fact we can do better sometimes. For $n=6$, take $P(x)=(1-x^2)(3-x^2)(9-x^2)$ then $d=27<36$. Fascinating problem! – Wolfgang Jan 5 '19 at 17:38
• 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. – Gerhard Paseman Jan 5 '19 at 17:41
• @ChristianRemling: You are correct. I have modified the problem. – Haoran Chen Jan 6 '19 at 2:01
• @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^2-4)(x^2-16)(x^2-36)(x^2-64)(x^6-80x^4+1684x^2-8040)$. Double check is very welcome... – Ilya Bogdanov Jan 6 '19 at 19:06

Let $$x_0<\dots 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_i-x_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^{n-1}$$. 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)?
• Yes asymptotically they differ by $\frac18\sqrt{2\pi n}\approx .31\sqrt{ n}$. – Wolfgang Jan 6 '19 at 8:06
• 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(n-1)=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^2-4)\cdots (x^2-16^2 )(x^{14} - 672x^{12} + 174200x^{10} - 22119856x^8 + 1443224772x^6 - 46275602672x^4 + 625295296152x^2 - 2334623374800)$. – Wolfgang Jan 7 '19 at 8:59
• Right, I neglected those. Empirically, if for $n=2^k$ the last factor is denoted $(a_{2^{k-1}} x^{2^k-2}+a_{2^{k-1}-1} x^{2^k-4}\cdots+a_2x^2+a_1)$, then the 2-valuations 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. – Wolfgang Jan 7 '19 at 12:06