Small lattice polytopes have few vertices

2026

Read Small lattice polytopes have few vertices (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30856.txt.

Introduction

Travis Dillon gives a new presentation of a classic theorem about lattice polytopes. A polytope is a shape whose corners sit on integer grid points. Andrews' theorem says a lattice polytope with many vertices must have large volume. The vertex count is bounded by a constant times a fractional power of the volume. The constant depends only on the dimension. The result is sharp up to that constant. It also separates vertices from lattice points, since the point count can grow in direct proportion to volume.

Dillon retells the proof by Konyagin and Sevast'yanov. His aim is to expose its strategy and foreground the geometry the original hides. He calls their route a forced march through a concrete hallway. He re-plots the journey with guiding signs, so the conclusion arrives as an appealing, satisfying walk.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30856

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Small lattice polytopes have few vertices Abstract \usetikzlibrary calc, math, cd, arrows.meta, braids, decorations.pathreplacing, decorations.markings, decorations.pathmorphing, bending, shapes \tikzset vertex/.style=draw, shape=circle, inner sep=1.5pt, minimum size=4pt \tikzset <->/.tip=Latex \tikzset shorten > = 2pt, shorten <=2pt \tikzset smallnode/.style=every node/.style=draw, fill=black, shape=circle, inner sep=0pt, minimum size=4pt, scale=0.7 \tikzset drawnode/.style=fill,shape=circle,inner sep=0pt, minimum size=3pt small lattice polytopes have few vertices A proof of Andrew’s theorem Travis Dillon The purpose of this paper is to prove that a lattice polytope (that is, a polytope whose vertices are lattice points) with many vertices must also have large volume (or, the other way around, a lattice polytope with small volume does not have many vertices). Theorem 1 . For any lattice polytope P in \mathbb{R}^{d} , |\operatorname{vert}(P)|\leq c_{d}\Vol(P)^{\frac{d-1}{d+1}}. The constant c_{d} depends only on the dimension d . In comparison, |\mathbb{Z}^{d}\cap P|\leq c_{d}^{\prime}\Vol(P) is the best possible inequality comparing the volume of a lattice polytope to the number of lattice points it contains (see Lemma 2 ). As Imre Bárány’s notes in his paper Random points and lattice points in convex bodies [ 1 ] , the original proof of G. E. Andrews in 1963 is “not easy” and while “there are several other proofs available, . . . none of them is simple . ’’ 1 1 1 See the citations after Theorem 13.1 in [ 1 ] for references to other proofs. That’s a shame, because this is a very nice theorem: It’s tight up to a constant (see Section A.2 ), and it shows a fundamental difference between the number of lattice points contained in a lattice polytope and the number of vertices of a lattice polytope. This note is a retelling of Konyagin and Sevast’yanov’s proof from [ 2 ] . My intention is to make their strategy more evident and foreground the underlying geometry. Reading their proof is like being grabbed firmly by the arms and marched steadily and unyieldingly through a formidable concrete hallway until you stumble over the conclusion you were trying to reach. It’s there, sure enough, but you have to wonder why you took such an odd journey to get there, and why in the middle of the march you were told to scratch your toes, and, now that you think about it, why you walked backwards rather than forwards. That said, if you dismiss the guide, re-plot the journey, and post a few guiding signs, it’s an appealing and satisfying journey. Let’s get to it. 1 . The strategy In broadest terms, the strategy is simple: Induction on the dimension. The case d=1 is easy, since any polytope in \mathbb{R}^{1} has at most two vertices. Now we move up. Suppose P\subseteq\mathbb{R}^{d} has m vertices and k facets, which we’ll call F_{1},\dots,F_{k} ; suppose that F_{i} has m_{i} vertices. The hyperplane containing F_{i} intersects \mathbb{Z}^{d} in an affine sublattice of dimension d-1 ; let \Pi_{i} be its fundamental parallelotope. Theorem 1 applied to F_{i} in this sublattice tells us that m_{i}\leq c_{d-1}\Big(\frac{\Vol_{d-1}(F_{i})}{\Vol_{d-1}(\Pi_{i})}\Big)^{\frac{d-2}{d}}. ( \ast ) To use induction, we bound m by \sum_{i=1}^{k}m_{i} and then use the previous inequality to bound each term in this sum by some function of the (d-1) -dimensional volume of the facets. But then we can’t make the next step: it’s impossible to upper bound the surface measure by any function of the volume. As an example, take the usual unit hypercube \conv(\{0,1\}^{d}) and shear the top facet far away from the bottom facet. (For example, so that the vertices are \{0,1\}^{d-1}\times\{0\} and \{a,a+1\}\times\{0,1\}^{d-2}\times\{1\} for some a\in\mathbb{Z} .) The volume of this polytope is always 1, but the surface measure tends toward infinity. Luckily, there is a fix, called the reverse isoperimetric inequality : (see Section A.1 for a proof 2 2 2 To focus on the main ideas of the proof, proofs of various lemmas and tangential statements have been moved to Appendix A . ) Lemma 1 . For any convex body C in \mathbb{R}^{d} , there is a volume-preserving linear transformation A so that \Vol_{d-1}\!\big(\partial A(C)\big)\leq c_{d}\Vol\!\big(A(C)\big)^{\frac{d-1}{d}}. Our new strategy is to use the bound m_{i}\leq c_{d-1}\Big(\frac{\Vol_{d-1}\!\big(A(F_{i})\big)}{\Vol_{d-1}\!\big(A(\Pi_{i})\big)}\Big)^{\frac{d-2}{d}}, which follows from ( ∗ ‣ 1 ) simply because the ratio of two volumes is invariant under linear transformation (even though the actual quantity \Vol_{d-1}\!\big(A(F_{i})\big) is likely different). The outline of the proof is then: 1. Calculate a lower bound on \Vol_{d-1}\!\big(A(\Pi_{i})\big) to obtain an upper bound for m_{i} in terms of \Vol_{d-1}\!\big(A(F_{i})\big) . 2. Use the reverse isoperimetric inequality to convert this into a bound on volume. That’s it! Now it’s time to follow through. 2 . The calculations 2.1 . Volume bound on fundamental parallelotopes Instead of estimating \Vol_{d-1}\!\big(A(\Pi_{i})\big) , let’s start with the easier task of estimating \Vol_{d-1}(\Pi_{i}) . The strategy is the same for both cases, but the latter is less ornate and therefore easier to understand. To do find a lower bound for \Vol_{d-1}(\Pi_{i}) , we’ll introduce the vector h_{i} , which is a normal vector to \Pi_{i} of length |h_{i}|=\Vol_{d-1}(\Pi_{i}) . The excellently convenient fact about this vector is that it has integer coordinates. There are two ways to see this, one by matrix manipulation and the other geometrically; both can be found in Section A.3 . Either way, now comes the clever bit. Order the indices so that |h_{1}|\leq\cdots\leq|h_{k}| (in other words, so that the volumes of \Pi_{i} form a nondecreasing sequence). For any \ell , we have \Vol\!\big(\!\conv(0,h_{1},\dots,h_{\ell})\big)\leq\Vol(B^{d})|h_{\ell}|^{d}, since all the vectors h_{1},\dots,h_{\ell} are contained inside the ball of radius |h_{\ell}| . ( B^{d} is the unit ball.) But we can also get a lower bound for the volume based only on the fact that it contains at least \ell integer points: the points h_{1},\dots,h_{\ell} themselves. Lemma 2 . If X\subseteq\mathbb{Z}^{d} does not lie in a single hyperplane, then \Vol\!\big(\!\conv(X)\big)\geq\frac{|X|-d}{d!}. For a proof, see Section A.4 . At this point, it would be nice to say that \frac{\ell-d}{d!}\leq\Vol(B^{d})|h_{\ell}|^{d}, and since d! and \Vol(B^{d}) are both constants in d , we have that \Vol_{d-1}(\Pi_{\ell})=|h_{\ell}|\gtrsim(\ell-d)^{1/d} for every \ell . (The symbol \gtrsim means that the inequality is true up to a constant that depends only on the dimension.) But this is only true if h_{1},\dots,h_{\ell} span \mathbb{R}^{d} . If this condition holds, combining this lower bound for \Vol_{d-1}(\Pi_{\ell}) with ( ∗ ‣ 1 ) tells us that m_{\ell}^{d/(d-2)}(\ell-d)^{1/d}\lesssim\Vol_{d-1}(F_{i}). Even though this inequality is only true for some \ell , we’re still able to find an upper bound for m : Lemma 3 . If t is the largest index such that h_{1},\dots,h_{t} is contained in a proper subspace of \mathbb{R}^{d} , then m\leq\sum_{i=t+1}^{k}m_{i} . Proof . Let w be any vector orthogonal to the (d-1) -dimensional subspace containing h_{1},\dots,h_{t} . Each vertex of P is contained in a facet whose normal vector is not perpendicular to w (in other words, a facet that is not parallel to w ), so m\leq\sum_{\langle h_{i},w\rangle\neq 0}m_{i}\leq\sum_{i=t+1}^{k}m_{i}.\qed So it will be enough to work with m_{i} for i\geq t+1 . Now we want to transfer this proof scheme to obtain a lower bound for \Vol_{d-1}\!\big(A(\Pi_{i})\big) . Here’s how. Let A^{-\top} denote (A^{-1})^{\top}=(A^{\top})^{-1} . The vector A^{-\top}(h_{i}) is perpendicular to A(\Pi) , and |A^{-\top}h_{i}|=\Vol_{d-1}\!\big(A(\Pi_{i})\big) . (Verifying this is straightforward linear algebra; see Section A.5 .) Now we can repeat everything from above,

Read the complete text