Both volume computation and lattice point enumeration of convex polyhedron are $\#P$ hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation.


1. Is there a randomized polytime algorithm for constant factor approximation for lattice point enumeration as well?
2. Is it $\oplus P$ complete to decide if a convex body has odd number of integer points?


If the polytope is convex and also centrally symmetric then what is the situation for 1., 2. and approximate volume computation?




---


**Update** If you know the number of lattice points approximately then we can guess volume approximately. 


The converse is not true. What additional assumptions could give a healthy converse?



Approximate volume computation and lattice point enumeration - hardness
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](https://www.csun.edu/~ctoth/Handbook/chap7.pdf) 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](https://dl.acm.org/citation.cfm?id=258665) 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](https://en.wikipedia.org/wiki/Minkowski%27s_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](https://en.wikipedia.org/wiki/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](https://search.proquest.com/docview/911048762) by Guo for references.


