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 '19 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$ – Wolfgang Jan 5 '19 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 '19 at 17:41
  • $\begingroup$ @ChristianRemling: You are correct. I have modified the problem. $\endgroup$ – Haoran Chen Jan 6 '19 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 Bogdanov Jan 6 '19 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_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)?

| cite | improve this answer | |
  • $\begingroup$ Yes asymptotically they differ by $\frac18\sqrt{2\pi n}\approx .31\sqrt{ n} $. $\endgroup$ – Wolfgang Jan 6 '19 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$ – Wolfgang Jan 7 '19 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 '19 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$ – Wolfgang Jan 7 '19 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.