Sixteen polygons with one dot inside

Pick’s theorem prices a lattice polygon’s area in two counts: the dots strictly inside, and the dots on the edge. Fix the first at one and the question becomes a classification. Which lattice polygons have exactly one dot inside them?

There are infinitely many, because a polygon can be moved, and stretched by any integer matrix that preserves the lattice. Count those as the same polygon and the answer becomes finite. It is sixteen.

Why the list is finite at all #

A search only terminates if there is something to bound it, and here the bound is one inequality that has nothing obviously to do with the question.

Scott’s inequality: a convex lattice polygon with $I \ge 1$ interior points has at most $2I + 7$ boundary points.

With $I = 1$ that caps the boundary at nine. Pick’s theorem then caps the area: with one interior point and at most nine on the edge, the area is at most $1 + 9/2 - 1$, which is four and a half. A convex region of area at most four and a half containing a lattice point can be moved so that the point is the origin and then transformed so that it fits in a small box, and a small box holds finitely many lattice points. The search is over.

The last step in that chain is the one worth doubting, and it has a name: a convex body of small area that contains a lattice point in its interior cannot be long and thin in every direction at once, because a long thin body of that area would contain no lattice point at all. Squeezing it into a box is the same fact that makes lattice reduction work, and it is what turns “finitely many up to equivalence” from a hope into a bounded computation.

The column at zero is the reason the inequality carries its hypothesis, and it is worth dwelling on because the hypothesis looks like a technicality and is not. A triangle with corners at the origin, at $(n, 0)$ and at $(0, 1)$ has no interior point at all and $n + 2$ points on its edge, so the boundary count is unbounded with nothing inside. Every polygon in the classification is finite because it has something inside it, which is the opposite of the intuition that an interior point is an extra thing to accommodate.

What “the same polygon” means #

The classification is up to translation and up to the integer matrices of determinant $\pm 1$ — the maps that send the lattice onto itself. There are infinitely many of those, and a search can only try finitely many, which puts a hole in any count a program produces.

The hole is real and the figure walks into it deliberately. Classifying with matrices whose entries are at most two gives seventeen classes; at most three gives sixteen; and four, five and beyond give sixteen again. Two of the seventeen were the same polygon in disguise, and the disguise needed an entry of three to see through.

So the reported number is an upper bound that has stopped moving, which is the strongest thing a finite search can say about an infinite group. It is not a proof, and a reader entitled to one should note that the classification is a theorem with a proof of its own; what the search adds is the pictures and the confidence that they are all of them.

Every edge one step from the middle #

There is a second description of these polygons that makes no reference to counting, and the two descriptions turning out to be the same is why the objects have a name.

Put the interior point at the origin. Each edge of the polygon lies on a line, and every line through lattice points has an equation $ax + by = c$ with $a$, $b$ and $c$ whole and $a$, $b$ sharing no factor. For these sixteen polygons, every edge has $c = -1$: each edge is exactly one lattice step away from the origin, in the sense that the lattice planes parallel to it are numbered and the edge sits on number one.

That is checked on all sixteen, and it is a strong condition — most polygons containing the origin have some edge two or three lines out. A polygon meeting it is called reflexive, and the equivalence of the two definitions in the plane is the reason the search above and the classification below describe the same list.

Reading the list #

The sixteen are not a shapeless collection, and sorting them by boundary count shows the structure.

One has three boundary points and three corners: the triangle with corners at $(1,0)$, $(0,1)$ and $(-1,-1)$, the smallest reflexive polygon there is, of area three halves. One has nine, the largest possible, and it is a triangle too — the one with corners at $(-1,-1)$, $(2,-1)$ and $(-1,2)$, area four and a half, which is Scott’s bound attained.

Between them the counts run 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, and the corner counts run from three to six. No reflexive polygon has seven corners, which is not obvious and comes out of the search: a heptagon with one interior point would need its seven edges each one step from the middle, and seven lines at lattice distance one cut out too little area to contain a point with room to spare.

Reading corners against boundary points together shows what the individual pictures hide. The five triangles run 3, 4, 6, 8 and 9 boundary points — the whole range — while the three pentagons sit at 5, 6 and 7 and the hexagon at 6. A polygon with many corners is squeezed to the middle of the range, because many corners means many short edges, a short edge carries few lattice points, and the area is capped either way.

The five triangles, seven quadrilaterals, three pentagons and one hexagon fill out the whole list, and the hexagon is the one with the most symmetry: the hull of the six units of the triangular lattice, which is self-dual and sits at six boundary points, the middle of the range.

The extremes are both triangles and that is not an accident. The smallest area and the largest are attained by the shape with the fewest edges, because the constraint that every edge sit one step from the middle binds hardest when there are many edges to place. Three edges can be pushed far out or pulled in tight; six cannot.

The dual, and the twelve #

The reflexive condition has a consequence that is startling the first time and remains startling.

Take the sixteen edge-normals — the vectors $(a, b)$ from the edge equations — and form their convex hull. The result is another lattice polygon, called the polar dual, and for a reflexive polygon it is again reflexive: it is another of the sixteen.

Twelve. Every polygon’s boundary count plus its dual’s, for all sixteen, without exception, and there is no elementary reason visible in the picture.

The identity is genuine and it is not a coincidence of small numbers; it is the two-dimensional shadow of a fact that appears in several unrelated places at once. The same twelve counts the singular fibres of a rational elliptic surface, appears as the weight of the first modular form of level one, and is the reason the Euler characteristic of a K3 surface is twenty-four. A statement about counting dots on the edge of a triangle is, read correctly, a statement about modular forms, and nothing in the derivation gives any hint of that.

What the figure can honestly say is that the identity holds on all sixteen and that it was measured rather than assumed. The explanation is a rung on somebody else’s ladder.

Why this is the natural next question #

The rung below asks whether Pick’s theorem generalises to three dimensions and answers no, because the two counts do not determine the volume. That is a negative result about a formula. This rung is what remains positive, and the two are the same discovery seen from opposite ends.

In three dimensions the reflexive polytopes are also finite in number, and the number is 4,319. In four dimensions it is 473,800,776, computed by Kreuzer and Skarke in 2000 and by nobody since, and the list is a standard object in string theory, where each polytope specifies a candidate geometry. The two-dimensional case being sixteen is the smallest case of a hierarchy whose fourth term took a supercomputer.

Whether the five-dimensional list is finite is known — it is, in every dimension — and whether anybody will ever have it is not.

The growth is the striking part and it is worth stating as a sequence: 16, then 4,319, then 473,800,776. Each step multiplies by a few hundred and then by a hundred thousand, and no formula predicts any of the three. This is a classification problem that is finite at every stage, solved at three stages, and hopeless at the fourth — which is an unusual combination and is why the numbers get quoted.

The reason string theory cares is worth one sentence, since it explains why anybody computed the four-dimensional list at all. A reflexive polytope specifies a pair of geometries that are mirror to one another, with the polytope and its dual giving the two members of the pair — and the duality drawn above is, in four dimensions, that mirror symmetry. The sixteen polygons are the toy case of a construction that produced hundreds of millions of candidate universes.

What the interior point is doing #

One more reading, because it explains why the count is small and the objects are rigid.

A single interior point is a very tight constraint because area and interior points grow together. Pick’s theorem says the area is $I + B/2 - 1$: with $I$ fixed at one, the area is entirely determined by the boundary count, and the boundary count is capped. So the sixteen polygons are exactly the sixteen possible areas-and-shapes at the smallest non-trivial value of a quantity that otherwise grows without bound.

Ask the same question at $I = 2$ and Scott’s bound permits eleven boundary points, an area up to five and a half — and the answer is a larger but still finite list. At $I = 3$ larger again. The classification exists at every $I$ and only the first case is small enough to draw, which is the usual situation and is why $I = 1$ is the case with a name.

An equivalence that is not obvious #

One more thing the search settles that the two definitions do not.

A polygon is reflexive when every edge sits one lattice step from the interior point. A polygon has one interior point when a count comes out at one. Those are different sentences about different things, and in the plane they describe the same sixteen polygons — which the figures check, edge by edge, on every one of them.

In three dimensions they are not the same. A lattice polytope with exactly one interior point need not be reflexive; the Reeve tetrahedra of the rung below are the standard family showing it, since they have one interior point at every height and their faces sit at lattice distances that grow. The plane’s coincidence is a two-dimensional accident, of the same kind as Pick’s theorem itself.

That is worth stating because it changes what the word means. In dimension two, reflexive and one interior point are interchangeable and the second is the easier description. In every higher dimension the first is the definition and the second is a consequence, and the counts quoted above — 4,319 and 473,800,776 — are counts of reflexive polytopes, not of polytopes with one interior point. The larger and less tractable class is the one with the simpler description, which is the reverse of the usual arrangement and is why the plane case misleads.

What the pictures cannot show #

The search runs over lattice points in a box of side four and takes hulls of at most six of them. Both limits are justified — a reflexive polygon has at most six corners and has a representative in that box — and neither is proved here. A reader wanting the classification rather than the pictures should treat the figures as an exhibition of a known list.

The identification up to unimodular equivalence is by matrices of bounded size, and the stability of the count is evidence rather than proof. That the answer at bound two differs from the answer at bound three is the useful part, because it shows the check has content.

And the twelve is checked and not explained. Nothing here derives it, and the derivations that exist go through objects — modular forms, toric surfaces — that no figure on this site draws.

Where the ladder goes next #

Named here as debts. The classification at two interior points, which is a larger finite list nobody draws and which would say whether sixteen is special or merely first. And the three-dimensional list, whose 4,319 entries are the reason the plane case is quoted so often.

Sideways, the formula being specialised is Pick’s, its failure in space is the rung below, the bound that makes a convex region swallow a lattice point is Minkowski’s, and the lattice these polygons live on is the one a quadratic form measures.

Where the search spends its time #

The computation behind the hero figure is worth describing, because the expensive step is not the one it looks like.

Hulling every subset of at most six of the twenty-five lattice points in the box is a quarter of a million convex hulls, and that is cheap: a hull of six points is a few comparisons, and testing whether the interior holds exactly one point is a scan over a small grid. The result is a few hundred polygons — the ones with a single interior point, before any identification.

The expensive step is the identification. Deciding whether two polygons are the same means transforming one by every unimodular matrix in the search range and comparing canonical forms, and the number of such matrices grows with the cube of the bound: 104 at entries up to two, 232 at three, 360 at four. Every polygon is transformed by every matrix, and the polygons in the raw list number in the hundreds.

That ordering — a cheap enumeration and an expensive classification — is typical of this kind of problem and it is why the answer arrived late historically. Producing candidates is easy; deciding which of them are genuinely different is where the mathematics is, and it is also where a search can silently be wrong. A classification is a statement that a list has no repeats, and that is the half a program is worst at. The stability check in the figure exists for exactly that reason, and it caught the bound-of-two answer being seventeen.

What is worth carrying away #

Fixing a parameter at its smallest interesting value often turns a formula into a finite list, and the list is usually more informative than the formula.

Pick’s theorem is a statement about all lattice polygons and says nothing about any of them in particular. Setting the interior count to one produces sixteen specific objects, each with a dual among the others, and an identity connecting them that the theorem never suggested.

The habit worth taking is to ask which of a formula’s inputs can be pinned. A formula with two inputs is a surface; pinning one gives a curve, and pinning it at an extreme value often gives a finite set — at which point the objects can be looked at rather than reasoned about, and looking at them is how the twelve was found.

The corollary is about trusting a search. A classification produced by a program is an upper bound on the number of classes, always, because a program identifies objects using the transformations it thought to try. The honest report is the sequence of answers as the transformations widen, and a count that has stopped moving is worth more than a count with no such sequence beside it.