]> Math reading #1: Volume bounds for lattice polytopes with interior lattice points

Back to the blog entry

Technical remark: This text makes heavy use of MathML and SVG, using the compound XHTML+MathML+SVG DTD. Firefox should render it just fine, Safari renders the SVG but chokes on the MathML; I don't know about other browsers. This page will not validate because of some insane non-symmetry in how the svg tag and/or namespace are treated. I have no idea who is responsible for that mess, and since the math tag works in the expected and logical way, I refuse to fix this page to pander to the insanity that the W3 validator requires. See this website on the compound DTD for some background information.

Volume bounds for lattice polytopes with interior lattice points

I want to give a quick overview of what I have learned from reading the paper Bounds for Lattice Polytopes containing a fixed number of Interior Points in a Sublattice by Lagarias and Ziegler (1991), Canadian Journal of Mathematics Vol. 43(5).

In general, the results apply to polytopes whose vertices are lattice points of a lattice Λd and that has interior integral points. To simplify the discussion a little, I will only talk about the case Λ=d here, that is, the vertices of the polytopes in question are integers.

Let us first take a step back and notice that integer polytopes without interior integer points can have arbitrarily large volume:

Polygons without interior integer points can have arbitrarily large volume

This rectangle has integer points on its boundary, but not in its interior, and by making it wider and wider you can increase its volume arbitrarily. On the other hand, if you want a polygon to have exactly one interior integer point, for example, there appears to be a hard limit on how large its volume can be:

The volume of lattice polygons with interior lattice points is bounded

This square has volume 4 and contains exactly one interior integral point. It turns out that the maximum volume of an integer polygon with exactly one integer point in the interior is 4.5. Can you find such a polygon?

Lagarias and Ziegler improve an earlier result of Hensley, who was the first to show that this volume bound is a general phenomenon: given a dimension d and a number of interior integral points k, there exists a finite upper bound V(d,k) on the volume of all d-dimensional integer polytopes with k1 interior integral points. In fact, their result was later improved by Pikhurko (thanks to Günter Ziegler for pointing this out), whose paper I have not read yet, so I will only sketch a very rough outline of the proof.

Let K be a convex body and let xintK be an interior point of K. The coefficient of asymmetry is defined by σ(K,x) = max y0 max{λ x+λyK} max{λ x-λyK} which looks scarier than it really is. To understand the quotient, let us pick an arbitrary direction y and consider the line through x in that direction:

Illustration of the coefficient of asymmetry x x

The line intersects the convex body on both sides of x, and the quotient in the definition above is equal to the ratio of the lengths of these segments. So if x is the center of a centrally symmetric body, then σ(K,x)=1 because the length of these segments is always the same on both sides. The crucial theorem (which is stated slightly differently as Theorem 2.5 in the paper, but the idea is the same) is the following:

Let Kd be a convex body and x d intK such that σ(K,x) 1-δ δ . Then the number of interior integral points of K is at least δdVol(K).

This theorem can be understood as a generalization of Minkowski's theorem. To more or less recover Minkowski's theorem, observe that a convex set which is symmetric with respect to the origin has σ(K,0)=1= 1-1212 and so if the volume of K is strictly greater than 2d then the theorem cited above states that K contains stricly more than 1 interior integral point. One of those points will be 0, but there will also be at least one non-zero point. Considering this, it is not surprising that the proof is a relatively straightforward application of Blichfeldt's theorem very much in the spirit of how you use Blichfeldt's theorem to prove Minkowski's.

The theorem gives a lower bound on the number of interior integer points in terms of the volume, which can obviously be translated into an upper bound on the volume in terms of the number of interior integer points. The "only" remaining problem (which is actually the hard part!) is to bound the coefficient of asymmetry so that δ can be bounded from below.

Using a variant of Diophantine approximation, Lagarias and Ziegler show that every interior integral point has a bounded coefficient of asymmetry. This is quite interesting, but it results in a non-optimal upper bound because clearly points which are close to the boundary of a polytope will have a quite large coefficient of asymmetry no matter how clever the rest of your proof is. The crucial change that Pikhurko made is to show that there exists an interior integral point with low coefficient of asymmetry, which is enough to apply the theorem above. This might be the topic of a future Math reading entry.

Sandwiching a convex body using a simplex

The volume bounds are actually only the first half of the paper of Lagarias and Ziegler. In the second half, which has a decidedly different flavor, they apply their volume bound to argue that the number of equivalence classes modulo unimodular transformations and translations of lattice polytopes with a non-zero fixed number of interior integer points is bounded. To show this, they sandwich polytopes using simplices, which I think is also a rather nice and fundamentally interesting result. Here is the theorem:

Let Kd be a convex body and let Δ be a simplex of maximal volume contained in K and assume that the centroid of Δ is at the origin. Then K-dΔ and K(d+2)Δ .

The centroid condition is only there to make the formulas a bit nicer. If the centroid were non-zero, we could just translate everything to make it zero. Intuitively, all this is saying is that we can sandwich the convex body between a simplex and a scalar multiple of that same simplex.

The proof of this sandwiching theorem is quite elementary. It mostly uses the following observation: if we fix d vertices of the simplex Δ, then the volume of Δ is linear in the distance of the last vertex to the plane spanned by the d fixed vertices.

Let xi, 0id, be the vertices of Δ. For every i, let Hi be the plane through the points xj excluding xi. Let Hi+ be the plane parallel to Hi that passes through xi, and let Hi- be the plane parallel to Hi with the same distance on the other side. The region between the hyperplanes Hi- and Hi+ is called Ri. Here's a picture of the situation, with Ri shaded in a light gray.

Illustration of the coefficient of asymmetry x1 x1 x2 x2 x0 x0 H0 H0 H0- H0- H0+ H0+

You can already see that KRi. Otherwise (as in the picture), we could replace xi by a different point from K and thereby increase the volume of the simplex, contradicting the fact that the simplex had maximal volume. In the picture, we could replace x0 by the right-most vertex of the polygon to obtain a simplex of greater volume.

So we have K iRi . Using a simple but somewhat tedious calculation one can show that iRi= -dΔ(d+2)Δ , which concludes the proof.

Note that if K is a polytope, there exists a maximal volume simplex whose vertices are vertices of the polytope: as long as one vertex of Δ is not a vertex of K, we fix the other d vertices of Δ and find the point in K of maximum distance from the plane spanned by the fixed vertices. This is simply a linear programming problem (or actually two LP problems, one in each direction), so we can find an optimal solution which is a vertex of the polytope, and because of the linear relationship between the distance of the point to the plane and the volume of Δ, we can use this optimal solution as a vertex of Δ without decreasing its volume. Then we can iterate this process until all vertices of Δ are vertices of K. Since there are only finitely many vertices of K, the iteration stops after finitely many steps.