10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ In addition to Peter's comments, I don't quite understand the remark below the line. What does it mean to "guess volume approximately"? What is the converse and how is it different? To me this looks like a symmetric statement about how well the number of lattice points approximates volume. $\endgroup$ – Sasho Nikolov Oct 18 '17 at 22:39
  • 2
    $\begingroup$ For a convex body $K$ symmetric around the origin, a version of Minkowski's theorem provides a lower estimate on the number of lattice points in $K$ in terms of the volume of $K$ and the determinant of the lattice. A standard packing argument provides an upper estimate. If this is helpful I can write an answer. There is also the work related to the Gauss circle problem which provides estimates on the function $D_K(t) = tK \cap \mathbb{Z}^n - t^d \mathrm{vol}(K)$. $\endgroup$ – Sasho Nikolov Oct 18 '17 at 22:43
  • $\begingroup$ @SashoNikolov 'To me this looks like a symmetric statement about how well the number of lattice points approximates volume' so if this has been studied before is there a reference? $\endgroup$ – 1.. Oct 20 '17 at 8:50
  • $\begingroup$ @SashoNikolov please provide the estimates. $\endgroup$ – 1.. Oct 20 '17 at 8:50
  • 1
    $\begingroup$ @PeterHeinig I specify as linear half space inequalities and I mean polyhedron given by linear inequalities. $\endgroup$ – 1.. Oct 20 '17 at 8:51
5
$\begingroup$

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.

  1. 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So $|\mathcal L\cap K|$ refers to number of integer points in $K$. Then I have $$\frac{\mathrm{vol}(K)}{2^n\det({\cal L})}\le |{\cal L} \cap K| \le \frac{\mathrm{vol}(K + V)}{\det({\cal L})}$$ which is exponential gap in volume given number of lattice points. Does it give exponential gap in number of lattice points given volume (the $K+V$ is bothering me)? $\endgroup$ – 1.. Oct 25 '17 at 23:15
  • 1
    $\begingroup$ You could have a body $K$ of volume zero with an arbitrarily large number of lattice points: for example $K$ can live inside a lower dimensional subspace spanned by some subset of the basis vectors of $\cal L$. Both inequalities are tight for $\mathbb{Z}^n$ and an appropriate choice of $K$: e.g. take $K$ to be a tiny region around $0$ for the packing argument, and take $K = [-1+\varepsilon, 1-\varepsilon]^n$ for Minkowski's theorem. $\endgroup$ – Sasho Nikolov Oct 26 '17 at 0:06
  • $\begingroup$ sorry but I think this still does not clarify "Is there a randomized polytime algorithm for constant factor approximation for lattice point enumeration as well?". $\endgroup$ – 1.. Oct 27 '17 at 5:23
  • 1
    $\begingroup$ My answers addresses the comment under the line: "If you know the number of lattice points approximately then we can guess volume approximately." I have asked an expert and there is no known constant factor approximation to the number of lattice points in a convex body. There are exact algorithms in fixed dimension (due to Barvinok), and also constant factor approximation is possible in singly exponential time. $\endgroup$ – Sasho Nikolov Oct 27 '17 at 6:09
  • $\begingroup$ ok,,,,,, if we prove constant factor approximation gives some collapse would it be interesting? $\endgroup$ – 1.. Oct 27 '17 at 6:11
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ this is a question about counting lattice points and has no relation to SVP. Approximating SVP tells nothing about difficulty of counting lattice points approximately. $\endgroup$ – 1.. Oct 27 '17 at 5:21
  • 2
    $\begingroup$ Of course there is a relation to SVP: if the number of lattice points in $tK$ is at least $2$ iff the shortest nonzero vector has $K$-norm at most $t$. This gives hardness for a factor 2 approximation to the number of lattice points in a symmetric convex body. $\endgroup$ – Sasho Nikolov Oct 27 '17 at 6:32
  • $\begingroup$ @SashoNikolov Is there a reference for the "iff" fact or could this be seen directly? Is deciding $K$-norm in $P$ or is it $NP$ complete? Also I think "if the number of lattice.... iff the ..." should be "the number of lattice.... iff the ...". correct? $\endgroup$ – 1.. Oct 27 '17 at 7:16
  • $\begingroup$ @SashoNikolov Does $K$ have to be a convex body symmetric around $0$? So the second point is essentially the unique non-zero integer point if there are exactly two lattice points? $\endgroup$ – 1.. Oct 27 '17 at 7:24
  • 1
    $\begingroup$ The first if is a typo. Usually SVP is defined for norms, whose unit balls are convex bodies symmetric around 0; so, yes, $K = -K$. And, indeed, the second point is the unique nonzero integer point. $\endgroup$ – Sasho Nikolov Oct 27 '17 at 7:46
0
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Why is this knapsack? The special case where the polyhedron is a halfspace is the counting version of knapsack and for that there is an approximation scheme. But I don't see how to get the arbitrary polyhedron version from this. $\endgroup$ – Sasho Nikolov Oct 16 '17 at 4:27

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.