Approximate volume computation and lattice point enumeration - hardness

Question

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?

Answer 1

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.

Answer 2

Sasho basically answered everything, but I'll add a bit.

1. Counting the number of lattice points in a symmetric convex body is strictly harder than telling whether there exists a non-zero lattice point inside a convex body, which is the Shortest Vector Problem and is NP-hard (under randomized reductions), even when the body is a Euclidean ball (or any $\ell_p$ ball), and even for any constant-factor approximation [1].

   In fact, SVP is widely believed to be hard (but not NP-hard) to approximate even to within any polynomial approximation factor, and a lot of cryptography is based on this assumption. (Some cryptography is based on the presumed hardness for even superpolynomial approximation factors.) The best-known polynomial-time approximation factor is $2^{C n \log \log n/\log n}$ for any constant $C > 0$, which follows from a long line of work. (This algorithm is in the Euclidean norm, so to extend even this to arbitrary norms, you must be able to calculate a not-too-terrible approximating ellipsoid.) It would be a major breakthrough to improve this.

2. Finding the parity of the number of lattice points in a shifted Euclidean ball (or any $\ell_p$ ball) is in fact as hard as finding the parity of the number of solutions to a $2$-SAT instance. (For centrally symmetric bodies, the parity is always odd, so the problem is only interesting for shifted bodies or asymmetric bodies.) This follows from the simple reduction from Max-2-SAT in [2] with Bennett and Golovnev, which preserves the number of solutions, as we mention at the end of Section 6. There is probably an earlier reduction that also has this property.

Finally, there are many of upper bounds on the number of lattice points in a convex body based on certain geometric parameters of the body. For example, Henk's bound [3]. The one that Sasho described is probably the easiest to work with.

[1] Khot, Subhash, Hardness of approximating the shortest vector problem in lattices, J. ACM 52, No. 5, 789-808 (2005). ZBL1323.68301.

[2] https://arxiv.org/abs/1704.03928

[3] Henk, Martin, Successive minima and lattice points, Schneider, Rolf (ed.) et al., IV international conference on “Stochastic geometry, convex bodies, empirical measures and applications to engineering science”, Tropea, Italy, September 24--29, 2001. Vol. I. Palermo: Circolo Matematico di Palermo. Suppl. Rend. Circ. Mat. Palermo, II. Ser. 70, 377-384 (2002). ZBL1126.11034.

Answer 3

This is basically the knapsack problem for which fully polynomial approximation schemes are known (see the link). As for parity, I am guessing it is hopeless in general, but for centrally symmetric polytopes, the number of lattice points is always odd (every point that is not zero has a friend, and zero is its own friend).