# Lattice points in dilated polytopes and sumsets

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?

-
Good question. I asked a related question in a special case (where the answer was negative): see mathoverflow.net/questions/151869/… –  Lucia Jan 31 '14 at 11:24
Ah, yes, interesting! The polytopes I have in mind are GT-polytopes, which have a lot of oddities (nice ones thought), so this might be true for these particular polytopes. –  Per Alexandersson Jan 31 '14 at 11:28
The way you state it, it is not clear what you mean by "question 1 is true/false". Supposedly you mean "Do all such $P$'s guarantee...", don't you? –  Wolfgang Jan 31 '14 at 12:56

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

-
Ah, thank you, this put me into a nice track. I found a proof of eventual polynomiality here: www.emis.de/journals/JTNB/2002-2/NathansonRuzsa.ps‎. I have to read a bit more, but most results only give polynomiality for n large. –  Per Alexandersson Jan 31 '14 at 14:27
Thanks for the reference to Nathanson and Ruzsa, which I hadn't seen before. –  Lucia Jan 31 '14 at 14:36
You are welcome. Now, when I read the paper by Nathanson and Ruzsa, they define something which is called "height" of a point in $\mathbb{N}^d$, which is just the sum of the coordinates. They use this in an essential way, and the problem I am looking at has a nice property related to this. Maybe that can explain why I get polynomials for those... –  Per Alexandersson Jan 31 '14 at 15:38

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.

-
Why don't the results mentioned in my post earn the bounty? A sufficient condition for the condition is that $P = k P'$ where $k \geq d-1$. On the other hand, not even normality is enough to guarantee sufficiency. –  David Handelman Feb 23 '14 at 0:35

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

-
So, for example if the polytope happens to be a simplex, it is smooth? –  Per Alexandersson Jan 31 '14 at 14:52
No, smoothness is a very strenuous assumption. It means that if you write $q_i-q$ in a basis of the lattice, the determinant of the resulting matrix is $\pm 1$. It may however hold for the polytopes you are interested in. –  Lev Borisov Jan 31 '14 at 18:34
Ah, ok. Hm, so let me visualize, the $q_i$:s are the closest lattice points on edges going out of $q$, which are in the boundary of $P$? –  Per Alexandersson Jan 31 '14 at 20:33
Yes. It is probably fairly easy to write them explicitly for GT polytopes -- these just might give smooth varieties (maybe some repeated projective bundles)? –  Lev Borisov Jan 31 '14 at 20:33

The polytopes in the question are called Normal Polytopes.

-

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.

-
I can find the vertices explicitly. I checked the condition on all vertices having the same degree, but this is not true in general, so they are not smooth. Finding a triangulation in general is too hard in my case i believe; a priori, not even the number of vertices is easy to find (unless the polytope is integral, but then I can only do it by checking all vertices explicitly...) Can you give an explicit family of polytopes that satisfy your conditions, but not being too trivial (say, hypercubes)? –  Per Alexandersson Feb 20 '14 at 11:17
If you can't even find the points $p_i$, then you have little hope of finding a triangulation or of proving the normality of the semigroup ring (which is what you are asking about). –  Lev Borisov Feb 20 '14 at 12:23
I had that feeling: Only a couple of years ago, a proof was provided that some GT-polytopes have non-integral vertices, and there is no known characterization on which polytopes are integral. Hence, finding the vertices (in general), is hard. For a specific instance, one can do it, but it requires a lot of work. –  Per Alexandersson Feb 20 '14 at 19:31