4
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Good question. I asked a related question in a special case (where the answer was negative): see mathoverflow.net/questions/151869/… $\endgroup$
    – Lucia
    Jan 31, 2014 at 11:24
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2014 at 11:28
  • 1
    $\begingroup$ 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? $\endgroup$
    – Wolfgang
    Jan 31, 2014 at 12:56

5 Answers 5

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2014 at 14:27
  • $\begingroup$ Thanks for the reference to Nathanson and Ruzsa, which I hadn't seen before. $\endgroup$
    – Lucia
    Jan 31, 2014 at 14:36
  • $\begingroup$ 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... $\endgroup$ Jan 31, 2014 at 15:38
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2014 at 0:35
3
$\begingroup$

The polytopes in the question are called Normal Polytopes.

$\endgroup$
1
  • $\begingroup$ ... or integrally closed or having the integer-decomposition property. A nice reference is arxiv.org/abs/1211.5755. $\endgroup$ Sep 6, 2017 at 4:27
2
+50
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ So, for example if the polytope happens to be a simplex, it is smooth? $\endgroup$ Jan 31, 2014 at 14:52
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2014 at 18:34
  • $\begingroup$ 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$? $\endgroup$ Jan 31, 2014 at 20:33
  • $\begingroup$ Yes. It is probably fairly easy to write them explicitly for GT polytopes -- these just might give smooth varieties (maybe some repeated projective bundles)? $\endgroup$ Jan 31, 2014 at 20:33
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$ Feb 20, 2014 at 11:17
  • $\begingroup$ 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). $\endgroup$ Feb 20, 2014 at 12:23
  • $\begingroup$ 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. $\endgroup$ Feb 20, 2014 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.