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$
$\endgroup$
14
-
$\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$– WolfgangCommented Jan 5, 2019 at 17:23
-
$\begingroup$ 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! $\endgroup$– WolfgangCommented Jan 5, 2019 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 PasemanCommented Jan 5, 2019 at 17:41
-
$\begingroup$ @ChristianRemling: You are correct. I have modified the problem. $\endgroup$– Haoran ChenCommented Jan 6, 2019 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^2-4)(x^2-16)(x^2-36)(x^2-64)(x^6-80x^4+1684x^2-8040)$. Double check is very welcome... $\endgroup$– Ilya BogdanovCommented Jan 6, 2019 at 19:06
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
4
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_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)?
-
$\begingroup$ Yes asymptotically they differ by $\frac18\sqrt{2\pi n}\approx .31\sqrt{ n} $. $\endgroup$– WolfgangCommented Jan 6, 2019 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(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)$. $\endgroup$– WolfgangCommented Jan 7, 2019 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$ Commented Jan 7, 2019 at 9:45
-
$\begingroup$ 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. $\endgroup$– WolfgangCommented Jan 7, 2019 at 12:06