On the Number of Integer Points in Translated and Expanded Polyhedra

NEW

Problem: Reconstructed statement: for a fixed integer $n$, the decision problem

is NP-hard, where $\Delta\subset\mathbb R^n$ is a full-dimensional rational simplex, $v\in\mathbb Q^n$, and all rationals are binary encoded. This matches Nguyen–Pak’s definition of Polytope Translation, restricted to simplices.

Result: The conjecture is true.

Use Nguyen–Pak’s theorem: Polytope Translation is NP-hard for rational polytopes $P\subset\mathbb R^6$ with at most $64$ vertices, translating in direction $e_1$. Such polytopes have at most a fixed number $M$ of facets; for example $M=\binom{64}{6}$ suffices for full-dimensional $6$-polytopes. Pad the facet description by repeated inequalities so that

It is enough to show that every such fixed-facet polytope instance reduces to a simplex instance in $\mathbb R^M$.

Let $A$ have rank $6$, choose six independent rows $A_I$, and choose a rational matrix $B\in\mathbb Q^{(M-6)\times M}$ with

For $T>\max_{x\in P}\sum_i(b_i-A_i x)$, let

the standard rational $M$-simplex. Define an affine isomorphism

Its linear part is invertible: if $B h=0$, then $h=Az$, and if also $-A_I^{-1}h_I=0$, then $z=0$.

Thus $\Delta_0:=\Phi(\Sigma)$ is a rational simplex. Its intersection with the coordinate subspace $H=\mathbb R^6\times\{0\}$ is exactly

Indeed, $x\in P$ gives $u=b-Ax\in\Sigma$ and $\Phi(u)=(x,0)$; conversely, if $\Phi(u)=(x,0)$, then $u=b-Ax$, hence $Ax\le b$.

Now scale only the last $M-6$ coordinates by a small rational $\varepsilon>0$ so that the resulting simplex $\Delta$ has all nonzero-coordinate projections contained in $(-1/2,1/2)$. Then every lattice point of $\Delta+\lambda(e_1,0)$ has last $M-6$ coordinates equal to $0$. Therefore, for every $\lambda$,

Thus $(P,k)$ is a yes-instance iff $(\Delta,(e_1,0),k)$ is a yes-instance. The construction is polynomial-time because $M$ is fixed and all linear algebra is over rationals of polynomial bit length.

Therefore Polytope Translation for rational simplices in the fixed dimension $n=M$ is NP-hard.

Citation: Uses Nguyen–Pak’s NP-hardness theorem for rational $6$-polytopes with at most $64$ vertices: Danny Nguyen and Igor Pak, On the number of integer points in translated and expanded polyhedra, arXiv:1805.03685.