The following question arises in passing in a joint paper that I am working on. Let $K$ be a centrally symmetric convex body in an $n$-dimensional real vector space $V$ which contains a lattice $L$. $L$ yields a natural volume scale fon $V$, and Minkowski established a well-known lower bound on the number of points in $L$ contained in $K$, namely $N \ge (\text{Vol}\ K)/2^n$. You could view this as a primitive estimate, but actually it's often roughly correct, after you take an $n$th root for a fair comparison.

Is there a similar upper bound that (a) is invariant under the $\text{GL}(n,\mathbb{Z})$ stabilizer of $L$, (b) behaves reasonably if you dilate $K$, and (c) can be regarded as useful or simple? Without any further restrictions on $K$, you obviously can't just use its volume, because it could be a thin rod that contains many lattice points of $L$. An extra restriction that holds in our case is that $K$ is a lattice polytope, i.e., the convex hull of finitely many lattice points. What we currently do is ask for basis of $L$, or a lattice that contains $L$, relative to which $K$ is contained in the $\ell^\infty$ ball of radius $c$. Then of course you get $N \le (2c+1)^n$. Or more generally, you could use a lattice parallelepiped. This works in the cases that we need it, but I don't know when it's a good estimate, again with the allowance of an $n$th root. It's also only $\text{GL}(n,\mathbb{Z})$-invariant by fiat.

  • $\begingroup$ Here is a primitive bound for lattice polytopes (not necessarily centrally symmetric) that is already interesting. It looks like a lattice polytope can be triangulated by lattice simplices with no internal vertices. This yields $N \le (n+1)!(\text{Vol} K)$. This bound is apparently refined by a bound on Ehrhart coefficients due to Betke and McMullen. This estimate and the Betke-McMullen bound might already be what I'm looking for. I will leave the question open for now in case there are further ideas. $\endgroup$ – Greg Kuperberg Jan 21 '13 at 17:44

Oded Regev and I recently published a paper that partially answers this question: https://arxiv.org/abs/1611.05979. In particular, we obtain reasonably tight bounds for the case when $K$ is a Euclidean ball in terms of the quantity $\min_{L' \subseteq L} \det(L')^{1/\mathrm{rank}(L')}$:

Section 9 of Dadush and Regev (https://arxiv.org/abs/1606.06913) has some discussion about the case of general convex bodies (as well as possible strengthenings of the above). In particular, they show that a natural generalization of the above to arbitrary convex bodies fails unless $t \geq \Omega(n^{1/4})$, but it holds for $t = O(n)$.


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.