The polygon a lattice becomes from far away

How fast the ball fills establishes that the number of group elements within $r$ steps of the identity grows like a power of $r$ in the integers squared, that the power is two, and that the two does not depend on which generators are used to take the steps. It leaves the rest of the count alone. The ball under axis steps holds $2r^2 + 2r + 1$ points; under a king’s moves it holds $(2r + 1)^2$. The power is the same and the constant in front of it is not, and nothing so far says where that constant comes from.

It comes from a shape. Draw the ball of radius $r$ for a given set of moves and it fills a region of the plane, and the region, scaled down by $r$, settles onto a polygon — the polygon spanned by the moves themselves. The constant in the count is that polygon’s area. Every generating set of the same group gives a different polygon, so the group has no shape of its own at large scales, only a shape for each way of walking it; but every one of those shapes is a polygon, and that is a fact about the group.

Three sets of moves, three polygons #

The first figure draws the ball of radius five in the integers squared under three generating sets: a step along either axis; axis steps together with one diagonal, $(1, 1)$; and all eight of a king’s moves.

The three balls are a diamond, a hexagon and a square, and in each case the shape is the polygon whose corners are the moves and their reverses, blown up by the radius. For axis steps the moves are $(\pm 1, 0)$ and $(0, \pm 1)$, whose convex hull is a diamond. Adding $\pm(1, 1)$ adds two corners and makes a hexagon. A king’s eight moves span the square with corners $(\pm 1, \pm 1)$.

Half of the reason is a one-line argument, and it holds for every set of moves in every dimension. Call the polygon $P$: the smallest convex region containing every move and its reverse. A point reached in $r$ moves is a sum of $r$ points of $P$, and a sum of $r$ points of a convex region lies in the region scaled by $r$ — divide the sum by $r$ and it is an average of points of $P$, which is inside $P$ because averaging never leaves a convex set. So every point of the ball of radius $r$ lies in $rP$, whatever the moves. The figure checks this point by point, and no dot anywhere falls outside its outline.

The other half — that the ball fills $rP$ rather than merely sitting inside it — is where the three sets of moves above are special, and the knight below is not.

The count is the polygon’s area, and its dots #

Counting the balls at several radii gives the table.

Axis steps give $5, 13, 25, 41, \dots$, which is $2r^2 + 2r + 1$. The hexagon gives $3r^2 + 3r + 1$ and the king gives $4r^2 + 4r + 1$. Divided by $r^2$ they head for 2, 3 and 4, and those are the areas of the diamond, the hexagon and the square. The polygon’s area is the constant in front of $r^2$.

The exact counts have a second meaning that makes the agreement less of a coincidence. For these three sets of moves the ball of radius $r$ is precisely the set of lattice points inside $rP$, and counting lattice points inside a scaled lattice polygon is what Pick’s theorem and its dilations do: Eugène Ehrhart showed in 1962 that the number of lattice points in $rP$ is a polynomial in $r$, and for a polygon it is

$$\text{area}(P)\, r^2 + \tfrac{1}{2}\,(\text{boundary points of } P)\, r + 1.$$

The diamond has area 2 and four boundary points, giving $2r^2 + 2r + 1$. The hexagon has area 3 and six, giving $3r^2 + 3r + 1$; the square area 4 and eight. The growth of the group under these moves is the Ehrhart polynomial of the polygon they span — a formula about dots in shapes, found in a count of words in a group.

A knight cannot step one square sideways #

A knight’s eight moves, $(\pm 1, \pm 2)$ and $(\pm 2, \pm 1)$, also generate the whole grid, and their polygon is an octagon with area 14. Its Ehrhart polynomial is $14r^2 + 6r + 1$, which would put 21 points in the ball of radius one and 145 in the ball of radius three. The ball of radius one has nine points — the knight’s square and its eight moves — and the ball of radius three has 109.

The knight’s ball is full of holes, and the holes are the familiar awkwardness of the piece on a chessboard. Every knight move changes the colour of the square it stands on, so a square of the starting colour can only be reached in an even number of moves and a square of the other colour only in an odd number. The square next door, $(1, 0)$, is inside the octagon scaled by one half — near, in the polygon’s sense — and needs three moves, because it has the other colour and one move always lands too far. The square $(2, 2)$ needs four. And near the edge of every octagon $rP$ there are points that $r$ moves would reach if the colour allowed it, and that need one move more because it does not: at radius three that is most of the ringed points, among them $(6, 0)$, which sits on the edge of the octagon scaled by three and has the starting colour, so it needs four.

So the knight’s ball does not fill its polygon, and the count is not the Ehrhart polynomial. It is still, in the long run, the polygon’s area times $r^2$: the table’s last row reaches 1,949 at radius twelve, which is 13.5 times $r^2$ against an area of 14, and the ratio is still climbing.

Why the diamond has no holes and the octagon has many #

Whether a ball fills its polygon is decided at the polygon’s corners, by a determinant. Take two neighbouring corners of $P$, say the moves $g_1$ and $g_2$, and the wedge of the plane between them. A lattice point in that wedge is a combination $\alpha g_1 + \beta g_2$ with $\alpha, \beta \ge 0$, and its norm is $\alpha + \beta$. If $\alpha$ and $\beta$ are always whole numbers, the point is reached in exactly $\alpha + \beta$ moves and the ball fills the wedge with no holes at all.

They are always whole exactly when the two moves span a parallelogram of area one — when $\det(g_1, g_2) = \pm 1$. Then $g_1$ and $g_2$ are a basis of the lattice, every lattice point has whole coordinates in that basis, and the determinant measures how much of the lattice the pair reaches: all of it. Axis steps have $\det\bigl((1, 0), (0, 1)\bigr) = 1$ at every corner of the diamond. The hexagon’s corners $(1, 0)$ and $(1, 1)$ give one, and so do $(1, 1)$ and $(0, 1)$. The king’s square has corners $(1, 1)$ and $(1, -1)$ with determinant two — but the king also has the axis moves, which sit in the middle of each side of the square and cut each wedge into two of determinant one. So all three balls are exactly the lattice points of $rP$, which is why their counts are Ehrhart polynomials.

The knight’s neighbouring corners $(2, 1)$ and $(1, 2)$ span a parallelogram of area $4 - 1 = 3$. Only one lattice point in three has whole coordinates in that basis, and the other two need a detour — a step back and forth through some other move — to be reached at all. Every one of the octagon’s eight wedges has determinant three, and that is where the holes live: they are the lattice points whose coordinates in the corner basis are not whole, and their extra cost is the price of the fractional parts. The same determinant is behind the bounded gap below.

The holes are a band of fixed width #

Shrinking each ball by its radius puts all of them on the same octagon and shows where the holes go.

At radius two the missed points are scattered through the octagon. By radius four they have moved outward, and at eight and sixteen they form a thin rim along the boundary with nothing missing inside it. The figure measures how deep that rim is — how far inside the edge, in units of the polygon’s own scale, the deepest missed point lies — and at every radius it is at most one and a half. The holes are a band of fixed depth, and scaling down by $r$ makes a band of fixed depth thinner and thinner until it is invisible. That is exactly what it means for the rescaled balls to converge to the octagon.

The share reached climbs like $1 - c/r$, since a band of fixed depth round a polygon of size $r$ holds about $r$ times as many points as the polygon’s perimeter and the polygon holds $r^2$ times its area. It never reaches one. Every ball of every radius misses a rim, and the convergence is a statement about shapes, not about any single ball.

Every point within three moves of its straight-line count #

The same fact can be read point by point instead of shape by shape. The polygon defines a way of measuring every point — the norm $\|v\|_P$, the smallest $\lambda$ for which $v$ lies in $\lambda P$ — and the word length $|v|$ is the number of moves the knight actually needs. The argument above says $|v| \ge \|v\|_P$ always. The next figure measures how much larger it can be.

Across 625 points the largest gap is $2\tfrac{2}{3}$, at $(\pm 2, \pm 2)$, whose norm is $1\tfrac{1}{3}$ and whose distance is four moves. The squares next door come second, at two and a half. Everywhere else the knight needs at most two moves more than the octagon says, and far from the start the gap does not grow.

The reason it cannot grow is short. A point $v$ on the boundary of $\|v\|_P \cdot P$ lies on some edge, and so it is a combination $v = \alpha g_1 + \beta g_2$ of the two moves at that edge’s corners, with $\alpha, \beta \ge 0$ and $\alpha + \beta = \|v\|_P$. Take $\lfloor \alpha \rfloor$ copies of the first move and $\lfloor \beta \rfloor$ of the second. What is left over, $v - \lfloor \alpha \rfloor g_1 - \lfloor \beta \rfloor g_2$, is a lattice point of the form $\{\alpha\} g_1 + \{\beta\} g_2$ with fractional parts below one — so it lies in a fixed bounded region, which holds finitely many lattice points, each with some fixed move count. The largest of those counts bounds the gap everywhere. It is the same argument in every dimension and for every generating set of $\mathbb{Z}^d$: the word length and the polygon’s norm differ by at most a constant.

What a change of generators keeps #

The three pictures in the first figure are three different geometries on one group. The diamond’s norm is the taxicab distance and the king’s is the largest of the two coordinate differences, the pair that the circles that are diamonds and squares draw as unit balls of two different formulas. They disagree about which points are nearest: under axis steps $(1, 1)$ is two moves away and $(2, 0)$ is two; under the king’s moves the first is one and the second two. But they never disagree by more than a factor of two, and any two generating sets of the same group disagree by at most some fixed factor.

A property that survives every such change is a property of the group rather than of the picture. The power of $r$ in the growth survives, and so do the number of ends and whether balls can have negligible edges. The polygon does not survive, and neither does the constant in the count. Maps that distort distances by at most a fixed factor and a fixed amount are called quasi-isometries, and the geometric theory of groups is the study of what they preserve; the answer for the integers squared is that from far away the group is a plane with some polygonal norm on it, and which polygon is a choice.

For groups that are not commutative the picture changes in kind. Pierre Pansu showed in 1983 that for the nilpotent groups — the next simplest after the lattices, of which the smallest interesting one is generated by two moves whose commutator commutes with both — the shrunken balls still converge, and the limit is not a normed plane at all but a curved space in which some directions can only be travelled by zigzagging in others. The constant in front of the growth is still the volume of the limiting ball. The lattice is the case where the limit is flat and the shape is a polygon; it is not the general case.

The same question with random moves #

There is a version of this question whose answer nobody can compute, and it is the reason the lattice case is worth having exactly. Instead of counting moves, give every edge of the square grid a random travel time — independent, all with the same distribution — and let the ball of radius $r$ be every point reachable from the origin within time $r$. This is first-passage percolation, introduced by John Hammersley and Dominic Welsh in 1965 as a model of fluid seeping through a porous rock.

The ball is now random and ragged, and the theorem is that it has a shape anyway: J. Theodore Cox and Richard Durrett proved in 1981 that the rescaled balls converge, with probability one, to a fixed convex set determined by the distribution of the travel times. It is the same statement as the one proved above for the knight — a ragged ball, a band of irregularity that shrinks away under rescaling, a convex limit — with the randomness averaged out by a law of large numbers along every direction. It is also the same kind of statement as the one the shape a random partition takes makes about a random staircase: a random object, rescaled, is almost surely one particular curve.

But in the random case the shape is unknown. For the knight the limit is an octagon with corners at its moves, found by convexity in a line. For random travel times it is known to be convex and symmetric under the grid’s own symmetries, and for most distributions almost nothing else is known — not its boundary, not its area, and not whether it has any flat sides.

What the pictures cannot show #

Every figure here is a ball of some finite radius, and the claim is about a limit. The shrinking figure shows four radii and a rim of missed points no deeper than one and a half; it cannot show that the rim stays that thin at radius a million, and the proof that it does is the leftover argument, which works for every radius at once because the leftover region does not depend on the radius. The gap figure is exhaustive inside its box and says nothing outside it; the bound of two and two thirds is a fact about 625 points, and the argument gives some bound everywhere without claiming it is that one.

The figures also show only the integers squared. The statement that every finitely generated commutative group has a polygonal shape from far away, and Pansu’s statement about the curved limits of nilpotent groups, are quoted rather than drawn. And the counts are of balls, not of the space between them: the figures say nothing about how the far-away parts of the lattice are connected, which is the question of ends and has a different answer.

Still open: the shape of a random ball #

The question that the lattice settles and the random model does not is whether the limit shape has flat pieces. A polygon is all flat pieces. The Cox–Durrett shape is convex, and convex sets can be round, polygonal or anything between.

Richard Durrett and Thomas Liggett showed in 1981 that flat pieces do occur for special distributions — when a travel time of exactly the smallest possible value is common enough that long straight runs of fastest edges percolate along the diagonal, the shape picks up a flat facet there. For the natural distributions, where travel times are continuous and no value is special, the shape is conjectured to be strictly convex, with no flat piece anywhere, and to have a boundary curved enough that the fluctuations of the random ball about it follow the laws that govern the random matrices and growing interfaces of the Kardar–Parisi–Zhang universality class. Neither strict convexity nor those fluctuations has been proved for any continuous distribution on the square grid. The lattice’s own shape is a polygon found in one line; the shape of a lattice with a little randomness added is, at present, not known to be anything more specific than convex.