Integer decomposition of dilated integral polytopes

Question

For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$.

Question: Given $d > n + 2$ is it true that

$$ dP \cap \mathbb{Z}^n \stackrel{?}{=} (n+2)P \cap \mathbb{Z}^n + (d-(n+2))P \cap \mathbb{Z}^n \ ? $$

That is for any integer point $u$ in the dilation $dP$ is there an integer point $v$ in the dilation $(n+2)P$ such that $u-v$ is an integer point of the dilation $(d-(n+2))P$? If so, is the construction explicit? If not are there conditions on $P$ where it does hold?

Answer 1

The answer is YES in the following stronger form:

Lemma 1: Let $d>n$ and let $p\in dP\cap \mathbb{Z}^n$. Then there is an $i\in\{1,\dots, n\}$ and points $p'\in iP\cap \mathbb{Z}^n$, $p_1,\dots, p_{d-i}\in P\cap \mathbb{Z}^n$ such that $$ p = p' + p_1 + \cdots + p_{d-i}. $$

For the proof I will (as is customary in this type of problems) work on the cone over $P$, defined as follows: $$ C_P := \operatorname{pos}(P\times \{1\}) \subset \mathbb{R}^{n+1}. $$ Observe that $dP$ can be identified with $C_P \cap \{x_{n+1}=d\}$. I call height of a point in $C_P$ the value of its last coordinate, so that integer points at height $d$ are identified with integer points in $dP$. Lemma 1 is equivalent to:

Lemma 2: Let $p\in C_P\cap \mathbb{Z}^{n+1}$ be an integer point at height $d> n$. Then, there is a point $p'\in C_P$ at a certain height $i\in \{1,\dots,n\}$ and integer points points $p_1,\dots, p_{d-i}$ such that $p=p' + p_1 + \cdots + p_{d-i}$.

Proof of Lemma 2: There is no loss of generality in assuming that $P$ is a simplex (if not, consider an integer triangulation of $P$ and apply the result to each individual simplex). So, let $v_1,\dots,v_{n+1}$ be the vertices of $P$, considered as points in $C_P$ at height one, and let $Z$ be the unit parallelepiped obtained as the Minkowski sum of the segments $Ov_i$.

The cone $C_P$ can be tiled by integer translations of $Z$; more precisely, it is tiled by all translations $v+Z$ where $v$ runs over the integer non-negative combinations of the $v_i$'s. Thus, $p$ can be decomposed as $p'+v$, where $p'$ is an integer point in $Z$ and $v$ is an integer non-negative combination of the $v_i$'s.

Except in the trivial cases where $p'=O$ or $p'$ is the sum of all the $v_i$'s, the integer point $p'$ in $Z$ has height between $1$ and $n$, which finishes the proof. QED

Answer 2

Somewhat belatedly (four years later), I noticed that the Shapley-Folkman lemma (https://en.wikipedia.org/wiki/Shapley%E2%80%93Folkman_lemma) yields a strong version of the result. SF says (as a special case) that if $S$ is a subset of $n$-dimensional Euclidean space, and we set $P$ to be its convex hull, then when $d > n$, for all $x$ in $dP$, there exists $y $ in $nP$ such that $x - y$ is a sum of $n-d$ elements of $S$.

So let $S = P \cap {\bf Z^n}$. For $x$ in $dP \cap {\bf Z^n}$, SF implies there is a decomposition $x = y + w$ where $w$ is a sum of $d-n$ elements of $S$ and $y \in dP$. Then $y = x-w$ is in ${\bf Z^n}$ (since $x$ and $w$ are). Hence $y \in nP \cap {\bf Z^n}$, yielding a stronger result: $dP \cap {\bf Z^n} = nP \cap {\bf Z^n} + ( S + \dots + S)$ with $d-n$ copies of $S$.