Return to Answer

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$ This works with $V$ replaced by any other set that tiles space with respect to $\cal L$, e.g. any fundamental parallelepiped.

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{n-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.

Below the line I address the question after "Update" about the relationship between volume and the number of lattice points. Since OP asks about conditions under which we can count the number of lattice points in $K$, let me point to a recent chapter by Barvinok, which has a lot of relevant information. Here are three special cases in which a positive result is known:

1. The problem (= computing $|\mathcal{L} \cap P|$ for a convex polytope $P$) is solvable exactly in fixed dimension. The running time as a function of the dimension is $n^{O(n)}$.

2. The problem is solvable exactly for a totally unimodular polytope $P$.

3. Kannan and Vempala have shown that if $P$ is a polytope in $\mathbb{R}^n$ with $m$ facets containing a Euclidean ball of radius $\Omega(n\sqrt{\log m})$, then the volume of $P$ gives a constant factor approximation to $|\mathbb{Z}^n \cap P|$. They also show how to approximately sample from $\mathbb{Z}^n \cap P$ under the same condition.

Volumetric bounds

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$ This works with $V$ replaced by any other set that tiles space with respect to $\cal L$, e.g. any fundamental parallelepiped.

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

Both bounds are in general tight.

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{n-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$ This works with $V$ replaced by any other set that tiles space with respect to $\cal L$, e.g. any fundamental parallelepiped.

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{d-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$ This works with $V$ replaced by any other set that tiles space with respect to $\cal L$, e.g. any fundamental parallelepiped.

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{n-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{d-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.

Let $\cal L$ be a full-dimensional lattice in $\mathbb{R}^n$ with determinant $\det({\cal L})$. Let $V$ be the Voronoi cell of $\cal L$, i.e. the set of all points in $\mathbb{R}^n$ which are closer to $0$ (in Euclidean distance) than to any other point of $\cal L$. Let $K$ be a convex body symmetric around $0$. We have the following volumetric bounds on $|{\cal L} \cap K|$.

1. Because $({\cal L} \cap K) + V \subseteq K + V$ and ${\cal L} + V$ is a packing (i.e. for any two distinct lattice points $x$ and $y$ $(x + V) \cap (y + V) = \emptyset$), we have

$$ |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\mathrm{vol}(V)} = \frac{\mathrm{vol}(K + V)}{\det({\cal L})}. $$ This works with $V$ replaced by any other set that tiles space with respect to $\cal L$, e.g. any fundamental parallelepiped.

2. An easy extension of Minkowski's convex body theorem shows that

$$ |{\cal L} \cap K| \ge \frac{\mathrm{vol}(K)}{2^n\det({\cal L})}. $$

This problem is also studied in a setting analogous to the Gauss circle problem. Let's just look at the case ${\cal L} = \mathbb{Z}^n$ (you can always reduce to this case by applying a linear transformation to both $K$ and $\cal L$). Define the discrepancy function $D_K(t) = |tK \cap \mathbb{Z}^n| - t^n \mathrm{vol}(K)$. It's a long standing open problem to find the smallest $c$ so that $|D_K(t)| = O(t^{d-2 + c})$. Here the constant in the asymptotic notation could depend on $K$. Check this thesis by Guo for references.