How many points a shape holds

Almost every count in this collection is a lattice-point count wearing a disguise. How many reflections lie inside a resolution sphere; how many sublattices have a given index; how many atoms a supercell holds; how many vertices of a net lie within a given distance. In each case the question is how many points of a lattice lie in a region, and the region grows.

There is a theorem about that, it is exact, and it is far stronger than the approximation a reader would expect.

Pick’s theorem, which is the first coefficient #

Draw a polygon whose corners are lattice points. Let I be the number of lattice points strictly inside it and B the number on its boundary. Then its area is

$$A = I + \tfrac{B}{2} - 1$$

exactly, for every such polygon, convex or not, however many corners it has.

The statement is startling on first meeting because area is a continuous quantity and the right-hand side is made of integers and a half. What makes it work is that a lattice polygon’s area is forced to be a multiple of a half — twice the area is the shoelace sum of integer cross-products, which is an integer — so both sides live in the same small set and there is room for an identity.

The check is correspondingly clean: twice the area against 2I + B − 2, both integers, no tolerance. Something either holds or it does not.

Scaling, and the polynomial that appears #

Now take the same polygon and scale it by a whole number t, and count again. Write L(t) for the number of lattice points in the scaled copy, boundary included.

The counts are a polynomial in t:

$$L(t) = A\,t^{2} + \tfrac{B}{2}\,t + 1$$

with A the area of the original and B its boundary count. Not asymptotically, not approximately — from t = 1 onwards, exactly.

Three things about that polynomial are worth separating.

The leading coefficient is the area, which is the statement that the number of lattice points in a large region is its area, made exact rather than asymptotic.

The middle coefficient is half the boundary count, which is a correction for the points sitting on the edge, each of which is shared.

The constant term is one, for every polygon there is, whatever its shape. It is the Euler characteristic of a disc, and its being a topological invariant is the reason it does not vary.

At t = 1 the polynomial is A + B/2 + 1, which is I + B, which rearranges to Pick’s theorem. Pick’s theorem is the first coefficient of an infinite family, and the family is Ehrhart’s.

It is worth pausing on how much stronger the polynomial statement is than the one a reader would have guessed. The natural expectation for “how many lattice points are in a region of area A” is approximately A, with an error nobody can pin down — which is exactly the situation for a circle, and the last section of this essay puts a number on how bad it gets. For a lattice polygon there is no error term at all. Three numbers determine every count, for every t, for ever; and two of the three are already visible in the unscaled polygon, so the entire infinite sequence of counts is decided by a single drawing with its points marked.

That is also why the fit is worth distrusting until it is checked. Any three counts determine a quadratic, so a routine that measures L(1), L(2), L(3) and reports a quadratic has reported nothing. What makes the polynomial a claim is that it predicts L(4) and every count after it, and the check this collection makes is exactly that: the coefficients are fitted on the first few and then compared against every term they were not fitted to. A polygon whose counts disagreed at any later t would stop the figure, and a polygon whose corners are not lattice points does disagree — which is the next section.

The corners that are not lattice points #

Now break the assumption. Take a polygon whose corners are at half-integers — the midpoints of lattice edges, say — and run the same experiment.

The counts are no longer a polynomial. They are a quasi-polynomial: one quadratic for even t, a different quadratic for odd t, alternating for ever. The leading coefficient is the same in both, because the area is the area; the lower coefficients differ.

The reason is visible in the picture. Scaling by an even t puts the corners back on lattice points; scaling by an odd t leaves them halfway. The boundary meets the lattice differently in the two cases and the count is correspondingly different, and there is no t large enough to make the difference go away.

The same shape, two subjects away #

A quasi-polynomial count is exactly what the coordination sequences of this collection’s nets turn out to be — the kagome net’s period two, the star net’s period four — and the two are the same phenomenon rather than an analogy.

In both cases a growing region is being counted; in both cases the region’s boundary meets the underlying discrete structure the same way only at every p-th step; and in both cases the result is a polynomial plus a periodic correction that never dies away. The literature on lattice-point counting and the literature on crystal nets do not usually cite one another, and the object in the middle is the same object.

The same shape appears a third time in the growth of a wallpaper group, where the ball sizes are a quadratic quasi-polynomial for the same reason: the word-metric ball is a polygon, and its corners land on lattice points only at some radii.

Why the count is a polynomial at all #

The result is easier to trust after seeing where the polynomial comes from, and the argument is short enough to give.

Cut the polygon into triangles whose corners are lattice points, in any way at all. The count for the whole is the sum of the counts for the pieces, minus the points on the cuts, which are counted twice — and the points on a cut are themselves a one-dimensional lattice-point count, which is linear in t. So if each triangle’s count is a quadratic, the whole is a quadratic.

For a triangle the count can be got by cutting again into primitive triangles: triangles with no interior points and no boundary points except their three corners. A primitive triangle has area a half — that is Pick’s theorem applied to it — and a lattice can be sheared so that any primitive triangle becomes the standard one with corners at the origin and the two basis vectors, since a shear of determinant one is a symmetry of the lattice. Count the standard one directly and the general case follows by a change of basis.

The change of basis is doing the real work, and it is the same fact that underlies most of this collection: a lattice has no preferred basis, so any statement invariant under a determinant-one integer change of coordinates need only be proved in one convenient basis. Ehrhart’s theorem is invariant that way, because a lattice-point count does not know which basis it was asked in.

Reciprocity, which has no right to be true #

There is a further identity, and it is the one that persuades people that the polynomial is a real object rather than a curve fit.

The polynomial L(t) was defined for positive whole t, where it counts something. Evaluate it at a negative argument, where it counts nothing, and it turns out to give — up to a sign that is plus in two dimensions — the number of lattice points strictly inside the polygon scaled by |t|.

$$L(-t) = \text{the interior points of } tP$$

That is Ehrhart reciprocity. Nothing about the definition suggests it: one side is a count of a region including its boundary, the other is a count of a region excluding it, and the bridge between them is a polynomial evaluated where no polygon exists.

It is checked here term by term on every lattice polygon in the collection, and it holds on all of them.

The constant term, and why it is one #

Of the three coefficients, the constant is the strangest, and it repays a paragraph.

It is one for every polygon: a triangle, a hexagon, an L-shape with a notch, a polygon with a thousand corners. Nothing about the polygon’s size or shape enters. The reason is that the constant term of an Ehrhart polynomial is the Euler characteristic of the region, and every polygon — being a disc with some corners — has Euler characteristic one.

That makes the three coefficients a small hierarchy: the leading one is the area, which is geometry; the middle one is half the boundary count, which is geometry of one dimension less; and the constant is topology, which does not vary at all. The pattern continues upward in higher dimensions, and it is one of the reasons the subject is thought of as a bridge between combinatorics and topology rather than as a curiosity about counting.

It also gives a check with teeth. A polygon with a hole in it — an annulus rather than a disc — has Euler characteristic zero, and its Ehrhart polynomial’s constant term is zero rather than one. Any implementation that reports one for such a region has counted the hole’s boundary wrongly.

What this is for, in a collection about symmetry #

Three uses, and the third is the one that recurs.

Counting reflections. How many reflections there are inside a resolution sphere is a lattice-point count in a growing region, so it is a polynomial in the radius with the volume of reciprocal space as its leading coefficient. Crystallographers quote the leading term and call it an estimate; it is the leading term of an exact polynomial.

Counting sublattices and supercells. A supercell of index n holds n times as many lattice points per cell, which is a lattice-point count with a linear answer; and the number of sublattices of a given index is a different count that happens to be arithmetic rather than geometric.

Counting anything that grows. Whenever a count in this collection is a function of a size — the shells of a net, the balls of a group, the atoms in a growing crystallite — the right expectation is polynomial with a periodic correction, and the right first question is what the period is.

How it is computed here #

The arithmetic is integer throughout and it is worth saying how, because the natural implementation is floating-point and would be wrong at exactly the interesting points.

A polygon is stored as integer coordinates together with a denominator: a triangle on half-integers is written as integers over two. Scaling by t multiplies the integer coordinates by t, and asking whether a lattice point (x, y) lies inside is asking whether (qx, qy) lies inside the integer-coordinate polygon — so the rational case is the integer case asked on a coarser grid, and no arithmetic changes.

Testing whether a point is inside is a crossing count with every comparison done as a cross-product of integers, and boundary points are tested first and counted separately. That last part is not fastidiousness: Pick’s theorem needs the boundary points counted apart from the interior ones, and a point-in-polygon routine that reports boundary points as inside will produce a count that is wrong by exactly the amount the theorem is about.

Who found it, and when #

Georg Pick published his theorem in 1899 in Prague, in a paper that attracted almost no attention for half a century; it became widely known only after Steinhaus put it in Mathematical Snapshots in the 1960s, and it is now the sort of result that turns up in school competitions.

Eugène Ehrhart’s generalisation came much later, in the 1960s, and the circumstances are worth recording: he was a schoolteacher in Strasbourg, working alone, and completed his doctorate at sixty. The theorem — that the count for a rational polytope is a quasi-polynomial, with the period the denominator — is now one of the load-bearing results of geometric combinatorics, with applications to counting solutions of integer programs and to the algebra of toric varieties.

Reciprocity was proved by Macdonald in 1971, and it is the part of the subject that most looks like magic and most repays being checked rather than admired.

What it does not settle #

It is two-dimensional here. Ehrhart’s theorem holds in every dimension, with degree the dimension and the leading coefficient the volume — but the middle coefficients in three dimensions are genuinely harder, and the second one is not simply half the surface count. Nothing in this collection computes them.

It is about lattice polygons, not about regions. A circle scaled by t contains a number of lattice points that is not a polynomial in t; the error term is a famous open problem. What makes polygons tractable is that their boundaries are flat, and flatness is what lets the count be exact. Flatness alone is not enough either: a polygon with one corner at an irrational point has no period at all, so its counts are neither a polynomial nor a quasi-polynomial, and nothing in the theorem covers it.

And the theorem says nothing about which polygon. Two polygons with the same area and the same boundary count have the same Ehrhart polynomial and can be entirely different shapes — which puts this invariant in the same class as the coordination sequence and the theta series: a good fingerprint, not an identification.

The generating function, which carries all of it at once #

The three coefficients and the reciprocity identity look like three separate facts about L(t). They are one fact about a single power series, and packaging them that way is what makes the theorem generalise.

Form the series whose coefficients are the counts:

$$1 + L(1)x + L(2)x^2 + L(3)x^3 + \cdots$$

Because L is a quadratic polynomial, that series is a rational function with (1 − x)³ underneath, and the numerator is a polynomial of degree at most two. Computing it for a lattice polygon gives

$$h^*(x) = 1 + (I + B - 3)\,x + I\,x^{2},$$

with I and B the interior and boundary counts of the original polygon.

Three things fall out of that shape and each is a statement already made above, now visible as one. The coefficients are non-negative integers — which is Stanley’s theorem in general and a small check here, since a polygon has at least three boundary points. The last coefficient is the interior count, which is Ehrhart reciprocity: the reversal of the numerator is what the negative arguments compute. And the first coefficient is one, which is the constant term of L and the same statement that a polygon has one point when it is not scaled at all.

The packaging is what survives to higher dimensions. In three dimensions the polynomial’s middle coefficients are awkward and the numerator’s coefficients are still non-negative integers, so the series is where the structure lives and the coefficient-by-coefficient reading is where it stops.

The count that is not a polynomial, and how badly #

The limit about circles is worth putting a number on, because the contrast with the exactness above is the whole reason lattice polygons are special.

Count the lattice points inside a circle of radius t. The leading term is the area, πt², exactly as Ehrhart’s leading term is the area — and the error is where everything is different. It is not a polynomial correction; it is a genuinely irregular quantity, and how large it can be is one of the older open problems in the subject.

Gauss showed the error is at most of order t, by the obvious argument that the discrepancy lives in a boundary annulus. Sharpening that is the Gauss circle problem: the error is known to be $O(t^{2/3})$ and a little better, it is known not to be $O(t^{1/2})$, and the truth is conjectured to sit just above the square root. A century and a half of work has moved the exponent from 1 to about 0.63.

The contrast is sharper still when the two are put in the same units. A lattice polygon of area 100 has its count known exactly for every scale from three numbers. A circle of the same area has its count known to within something of order t^0.63, which at t = 1000 is a couple of hundred points that nobody can predict — against a total of some three hundred million, so the relative error is tiny and the absolute error is an open problem. Both readings are true and the second is the interesting one, because the question a lattice-point count is usually asked is not “roughly how many” but “exactly how many, and does the answer have structure”.

The reason for the difference is not that a circle is curved but that its boundary contains no lattice points to organise the count. Every argument on this page went through a decomposition into primitive triangles whose corners are lattice points, and a circle admits no such decomposition — so the count has no polynomial to be, and the residual is an arithmetic object rather than a geometric one.

Where this goes #

The next essay in this field takes a different count of the same lattice — the sublattices, arranged as a tree rather than merely counted — and finds a structure where this one finds a polynomial.

And the connection to run forward is the one this essay has made three times: quasi-polynomial counting is a single phenomenon appearing in lattice-point counts, in net coordination sequences and in group growth, and the period is always the same kind of thing — how often the growing boundary meets the discrete structure the same way.

The two sections sit either side of one line. On one side are regions whose boundaries are built out of the lattice, where the count is a polynomial, every coefficient means something, and an identity relates the closed count to the open one. On the other are regions whose boundaries ignore the lattice, where the leading term survives and everything after it becomes a question nobody has answered. What decides which side a region falls on is not its smoothness or its convexity but whether its corners are lattice points.