New bounds in the discrete analogue of Minkowski’s second theorem

New bounds in the discrete analogue of Minkowski’s second theorem, Discrete Analysis 2024:7, 6 pp.

Minkowski’s first theorem in the geometry of numbers states that if a closed centrally symmetric body $K$ in $\mathbb R^n$ has volume at least $2^n$, then it contains a non-zero point in $\mathbb Z^n$. The proof is simple: if $K$ does not contain such a point, then all translates of $K/2$ by a vector with integer coordinates are disjoint (since if $x+K/2$ intersects with $y+K/2$, then $x-y\in K$). But the volume of $K/2$ is $2^{-n}$ times the volume of $K$, and also equal to the density of the union of all the integer translates of $K/2$, and therefore at most 1.

More generally (but equivalently), if $\Lambda$ is any lattice in $\mathbb R^n$ and $K$ is a closed centrally symmetric body of volume at least $2^n\det\Lambda$, then $K$ contains a non-zero point of $\Lambda$. (The determinant of a lattice is the volume of a fundamental parallelepiped.)

It is easy to see that the bound given by Minkowski’s first theorem can be very far from sharp. For instance, if $K$ is a very thin cylinder about the first coordinate axis that does not quite touch the points $(\pm 1,0,0,\dots,0)$, then the theorem implies that $K$ has volume at most $2^n$, when in fact it can be arbitrarily small. On the other hand, if $K$ is the cube $[-t,t]^n$ for $t$ very close to 1, then $K$ has volume very close to $2^n$, so the result cannot be improved without more refined assumptions about $K$.

Minkowski’s second theorem relates the volume of $K$ to quantities known as successive minima. If $\lambda$ increases from zero, then the convex body $\lambda K$ will at first contain no non-zero points of $\Lambda$. The first successive minimum $\lambda_1$ is the minimal $\lambda$ such that $\lambda$ contains a non-zero point of $\Lambda$, which exists by Minkowski’s first theorem, and in general the $k$th successive minimum is the minimal $\lambda$ such that $\lambda K$ contains at least $k$ linearly independent points of $\Lambda$.

If $\Lambda=\mathbb Z^n$ and $K$ is the cuboid $\prod_{i=1}^n[-t_i,t_i]$ with $t_1\geq t_2\geq\dots\geq t_n$, then $\lambda_i=1/t_i$, so the volume of $K$ is $2^n/\prod_i\lambda_i$. Minkowski’s second theorem states that this is an upper bound for a general symmetric convex body and a general lattice, except that one must of course again introduce the normalizing factor $\det\Lambda$. That is, $\mathop{\text{vol}} K\leq 2^n\det\Lambda/\prod_i\lambda_i$.

This paper, as is clear from its title, is about a discrete version of Minkowski’s second theorem. What makes it discrete is that the quantity being bounded above is no longer the volume of $K$ but the number of lattice points that $K$ contains. Note that in this instance we no longer expect $\det\Lambda$ to appear in the bound. It was conjectured by Betke, Henk and Wills that one should have the upper bound
$$|K\cap\Lambda|\leq\prod_{i=1}^n\lfloor 2/\lambda_i+1\rfloor.$$
Later Malikiosis conjectured that the same bound should apply even if one drops the assumption that $K$ is centrally symmetric, where one defines the successive minima of a non-symmetric convex body $K$ to be those of the symmetric convex body $(K-K)/2$.

Malikiosis proved that the conjecture is correct up to an explicit factor that grows exponentially with $n$ (which is quite reasonable given that scaling an $n$-dimensional convex body up by $\lambda$ increases its volume by a factor $\lambda^n$), and Freyer and Lucas proved an upper bound of $\prod_{i=1}^n(2/\lambda_i+d)$, which is correct up to a factor $1+o(1)$ when all the $\lambda_i$ converge to zero, reflecting the fact that the discrete problem is a better and better approximation to the continuous one when the successive minima get smaller and smaller.

This paper gives a new bound that improves the bounds of Malikiosis, and in some cases improves the bound of Freyer and Lucas as well. If the successive minima are $\lambda_1\leq\dots\leq\lambda_n$, then the upper bound obtained in the paper is
$$2^k(1+\lambda_k/2)^k/\lambda_1\dots\lambda_k,$$
where $k$ is maximal such that $\lambda_k\leq 1$. (In fact, the paper proves a slightly better bound than this that is more complicated to define.) Note that when the successive minima are all small, then $k=n$, and the bound is close to $2^k/\lambda_1\dots\lambda_n$, so like the result of Freyer and Lucas this argument approximates the continuous one for bodies that are small in every direction. In fact, both bounds straightforwardly imply Minkowski’s second theorem, as one can see by applying them to the convex body $rK$ and letting $r$ tend to infinity.

The proof is closely modelled on a proof by Tao and Vu of Minkowski’s second theorem, with a twist at the end.