On polytope lattice points

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.

• What is $n$? Dimension? Nov 5, 2017 at 1:39
• Also, what is width? I would've thought it was defined as the maximum distance between any two points in the polytope, but apparently it means something different... Nov 20, 2017 at 0:15
• width smallest gap of two linear functionals enclosing the polytope and this is right measure and it influences Lenstra's result as well. Nov 20, 2017 at 0:43

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

• Is the natural polytope from cnf convex? Nov 5, 2017 at 3:22
• Yes, it is convex, because it is the intersection of halfspaces. Nov 5, 2017 at 3:50