Lattice points in dilated polytopes and sumsets

Question

Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.

Let $p_1,\dots,p_m$ be all lattice points in $P$.

Question: What is the condition on $P$ that guarantees that every lattice point in the dilation $nP$ can be expressed as $k_1p_1 + k_2p_2 + \cdots + k_n p_n$, where the $k_i$ are non-negative integers? Here, $n \in \mathbb{N}$ and $k_1+k_2+\cdots+k_n = n$.

Note that not all $p_i$ need to be vertices of $P$. Clearly, all vertices of $nP$ are expressible in this manner, since they are dilations of the vertices in $P$.

Remark: The function $f(n)$ which counts lattice points in the dilation $nP$ is an (Erhart) polynomial and the $g(n)$ that counts the number of points that can be expressed as $k_1p_1 + k_2p_2 + \cdots + k_n p_n$ is eventually polynomial (Khovanskii).

Thus, we must impose some extra condition on the $p_i$s to have polynomiality all the way, and also equality.

Are there some non-trivial examples of such polytopes?

Answer 1

Your second question is known to be true by a theorem of Khovanskii: that is, $g(n)$ is eventually a polynomial for large $n$. Khovanskii also compares this number with the Erhart polynomial -- that is he shows that the $n$ fold sums are approximately contained in the $n$-th dilate of the polytope (this is not so hard). But I don't know of good conditions which guarantee that the Khovanskii polynomial is the same as the Erhart polynomial. For Khovanskii's work see Theorem 1 in his paper Newton polyhedron, Hilbert polynomial, and Sums of Finite sets; translation from Russian of his paper in Functional analysis & Applications 1992 (http://www.math.jussieu.fr/~chenhuayi/conferences/okounkov/khovanskii.pdf).

Answer 2

Toward the first question, there is a theorem (due mostly to Bruce Reznick) that says if $K$ is a lattice polytope in $R^d$ such that the group generated by $(K \cap Z^d) - (K \cap Z^d)$ is the standard copy of $Z^d$ (projectively faithful—referring to the corresponding product type action of the $d$-torus on the obvious UHF C*-algebra), then $(d-1)K$ has the property you mention, and $d-1$ is sharp in the sense that for every $d \geq 3$, there is a counter-example with anything less than $d-1$. Moreover, $nK$ has the property for every $n \geq d-1$ (this is relatively easy to obtain, once the $d-1$ result is available). Hence if your set $\{p_i \}$ is of the form $K \cap Z^d$ with $K$ projectively faithful, then you have the result with $n \geq d-1$. This is also the sharpest result if we restrict to simplices.

Some results of this type can be found in

DE Handelman (me), Positive polynomials and product type actions of compact groups, Mem AMS 320 (1985)

DE Handelman, Positive Polynomials, Convex Integral Polytopes, and a random walk problem, SLN 1282 (1987).

The $d-1$ and $n \geq d-1$ results are in one of these, but I can't locate the monographs at the moment, so I can't tell you which one of the references has them.

When $d \geq 5$ (and possibly with $d \geq 4$), weird things can happen wrt this kind of problem; see the examples in

D Handelman, Effectiveness of an affine invariant for indecomposable integral polytopes, J Pure and Applied Algebra 66 (1990) 165–184.

Answer 3

The polytopes in the question are called Normal Polytopes.

Answer 4

In general, $g(n)$ is strictly less than $f(n)$, although they have the same leading term. One sufficient condition to get $g(n)=f(n)$ is to require smoothness of the corresponding toric variety. Combinatorially, this means that at every vertex $q$ of $P$ there are exactly $\dim P$ edges coming out of it; moreover if you take $q_i$ to be the closest points to $q$ on these edges, the simplex with vertices $q,q_1,...,q_{\dim P}$ has minimum possible volume. I believe the statement is pretty much local near all the vertices: if you can generate all points in $kP$ that are close to any given vertex, then you will be able to eventually generate all points.

Edit: I made a mistake in claiming that $g$ and $f$ have the same leading term. This only happens if the differences of points in $P$ generate the whole lattice. A simple counterexample in dimension three is the convex hull of $(0,0,0),(1,1,0),(1,0,N),(0,1,N)$ for some $N$.

Answer 5

Since you have changed the formulation of the question slightly to now require identity for all $n$, not just for large ones (or maybe it was just me misreading the original post), let me offer a sufficient condition.

If you can find a triangulation of $P$ with vertices $p_i$, so that the number of maximum simplices equals the normalized volume of $P$, then you are done. If you can describe GT polytopes explicitly (I have a vague idea of what they are, but not working knowledge), then it might be possible to see if there is such a triangulation.