Let $\Delta=\{(x_1,\cdots,x_n)\in\mathbb{R}^n_{\ge 0}\,|\,a_1 x_1 + \cdots + a_n x_n \le 1\}$ (all the $a_i$'s are positive) be an $n$-simplex such that $(1,1,\cdots,1)$ is contained in the interior of $\Delta$. What is the smallest possible value of $\#(\Delta\cap\mathbb{Z}^2)$? Is it true that the number of lattices points in $\Delta$ is at least $\binom{2n}{n}$? Clearly the equality can be achieved when all the $a_i$ are sufficiently close to (but less than) $\frac{1}{n}$.

  • 1
    $\begingroup$ Volume bound gives the lower estimate $n^n/n!$, which is essentially worse but at least shows that the answer grows exponentially in $n$. $\endgroup$ – Fedor Petrov Jan 17 '18 at 10:05
  • 1
    $\begingroup$ Actually, generalizing this idea, for any dimension $n$, I think it is possible to find such a $\Delta$, whose number of lattices points is exactly $\binom{2n}{n} - 1 - (n-1) - (n-2)^2 - \ldots - 2^{n-2}$. So for example, for $n = 3$, $.33x+.33y+.339z \leq 1$ should give $17$. You can even do $16$ with $.33x+.332y+.337z$. $\endgroup$ – Jeremy Jan 17 '18 at 14:15
  • 1
    $\begingroup$ @Jeremy do you subtract also $(n/2)^{n/2}$? This is much greater than $\binom{2n} {n} $. $\endgroup$ – Fedor Petrov Jan 17 '18 at 18:18
  • 2
    $\begingroup$ Since we're counting points in the closed simplex, it doesn't matter if $(1,\dots,1)$ is allowed to be on the boundary. $\endgroup$ – MTyson Jan 17 '18 at 19:12
  • 2
    $\begingroup$ For each point $(x_1,\dots,x_n)\in\mathbb{Z}_{\ge 0}^n$ s.t. $\bar x=\sum x_i/n\le 1$, at least one of its cyclic permutations $(x_{1+i},\dots,x_{n+i})$ must be in $\Delta$. This is because their average is $(\bar x,\dots,\bar x)\in\Delta$ and $\mathbb{R}_{\ge 0}^n\setminus\Delta$ is convex. For prime $n$ this gives a lower bound of $({2n \choose n}-2)/n+2$. For composite $n$, one could use Polya enumeration or Mobius inversion to get a similar bound. $\endgroup$ – MTyson Jan 18 '18 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.