]> 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:

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:

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 $k≥1$ 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 $x∈intK$ be an interior point of K. The coefficient of asymmetry is defined by $σ(K,x) = max y≠0 max{λ∣ x+λy∈K} max{λ∣ x-λy∈K}$ 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:

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 $K⊂ℝd$ 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 $K⊂ℝd$ 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$, $0≤i≤d$, 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.

You can already see that $K⊆Ri$. 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.