On polytope lattice points

Question

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.

Denote $\mathcal P(a,c)$ to be the set of convex polytopes in $\Bbb R^n$ presented by $O(n^a)$ linear inequalities with $e/d=O(n^c)$.

1. Is it $\#P$ complete to find number of integer points in such polytopes?

2. Is it $NP$ complete to decide existence of integer points in such polytopes?

I am essentially asking if the polytope is reasonably round what is the difficulty of counting and decision problems. Here for quantifying roundedness I use width and max distance (but may be some other quantification which I do not know may be appropriate).

I think some strange partition of 0/1 cube with convex faces might suffice for 1.

Answer 1

Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints

1. $0\le x_i \le 1$ for all $i$,
2. clause constraints for any clause $C$ of $\phi$: for example if $C = x_i \vee \bar{x}_j \vee x_k$ put the constraint $x_i + 1-x_j + x_k \ge 1$. (I trust you can figure out the general rule.)

Clearly $P$ has an integer point if and only if $\phi$ is satisfiable. Also the number of integer points in $P$ equals the number of solutions of $\phi$. So as long as the ratio between the diameter and the width of $P$ is polynomial, this answers both your questions.

Let us then compute its diameter and width. $P \subseteq [0,1]^n$, so the diameter of $P$ is at most $\sqrt{n}$. By width, I am assuming you mean the standard

$$ \min_{\theta: \|\theta\|_2 = 1} \max_{x, y \in P} \langle \theta, x-y\rangle, $$

i.e. the smallest distance between two parallel hyperplanes that sandwich $P$. Notice that any $x$ which satisfies $\frac13 \le x_i \le \frac23$ for all $i$ is in $P$. So, for a $\theta$, pick $x_i$ to be $\frac23$ if $\theta_i > 0$ and $\frac13$ otherwise, and pick $y_i$ to be $\frac13$ if $\theta_i > 0$ and $\frac23$ otherwise. Then:

$$ \langle \theta, x - y \rangle = \sum_{i = 1}^n \frac{|\theta_i|}{3} = \frac13 \|\theta\|_1 \ge \frac13 \|\theta\|_2. $$

So the width is at least $\frac13$.