Three coordinates and a fourth power

How fast the ball fills counted the elements of a group within $r$ steps of doing nothing and found two kinds of answer: a polynomial in $r$ for the lattices of whole-number points, a power of three for the free group. It found the degree of the polynomial to be the number of directions, two for the plane and three for space, and it quoted a theorem saying that every group of polynomial growth has a whole-number degree computed from a decomposition into commuting layers. Every example it computed was a lattice, where there is only one layer and the theorem says nothing that counting the directions does not.

This essay computes the first group where the theorem says something else. Its elements need three whole numbers to name them, exactly as the points of the cubic lattice do. Two moves generate it, fewer than the cubic lattice needs. And the number of elements within $r$ moves grows like $r^4$. The extra power is not an accident of the moves chosen, and it does not come from a hidden fourth coordinate. It comes from the way one coordinate is reached: not by stepping along it, but by walking round a square in the other two and collecting the square’s area. That mechanism shows up four times below: in the count, in the cost of travelling straight up, in the shape the ball makes from a distance, and in a theorem saying that among all the groups there are, this is essentially the only way a polynomial can arise.

Three coordinates and a fourth power #

The Heisenberg group is the set of triples of integers $(a, b, c)$ with the product

$$(a, b, c) \cdot (a', b', c') = (a + a', \; b + b', \; c + c' + ab').$$

The first two coordinates simply add. The third adds too, plus a correction $ab'$ that depends on the order of the factors: swap them and the correction is $a'b$ instead. Written as matrices, the triple is the upper triangular $3 \times 3$ matrix with ones on the diagonal, $a$ and $b$ just above it and $c$ in the corner, and the product is matrix multiplication. The name comes from quantum mechanics, where the same multiplication encodes the rule that position and momentum fail to commute by a fixed amount.

Two elements generate everything: $x = (1, 0, 0)$ and $y = (0, 1, 0)$. Multiplying on the right by $x$ adds one to $a$; multiplying by $y$ adds one to $b$ and adds the current $a$ to $c$. So the map of the group has a point for every triple and four edges at each, and the ball of radius $r$ is everything reachable from $(0, 0, 0)$ in at most $r$ moves among $x$, $y$ and their inverses. A breadth-first search lists it exactly, layer by layer, out to radius 44.

On these axes a polynomial is a straight line whose slope is its degree. The lattices give slopes two and three, as they must. The free group bends upwards and leaves the frame. The Heisenberg group’s line is straight and steeper than space’s: measured between radii 21 and 42 its slope is 4.00. The ball of radius 44 holds 1,600,703 elements, more than thirteen times the 117,569 of the cubic lattice at the same radius, though both groups are triples of integers and the Heisenberg group has fewer generators. The ball of radius one holds five elements in both of the two-generator groups, the plane’s lattice and this one; by radius two the Heisenberg group has seventeen against the plane’s thirteen, because $xy$ and $yx$ are now different elements, and from there the gap only widens.

A commutator that lifts by the area of a square #

The difference between $xy$ and $yx$ is the whole story, so it is worth computing. The product $x y x^{-1} y^{-1}$ — the commutator of $x$ and $y$ — is $(0, 0, 1)$: the first two coordinates cancel, and the third picks up one unit of correction. This element commutes with everything, and every element of the form $(0, 0, c)$ is a power of it. In a lattice the commutator of any two moves is the identity; here it is a genuinely new direction, one that the generators do not point along but reach by going round.

Going round a bigger square reaches it much faster. The commutator of $x^k$ and $y^k$ — $k$ steps along $x$, $k$ along $y$, $k$ back along $x$ and $k$ back along $y$, which is $4k$ moves — lands on $(0, 0, k^2)$. So the central element $(0, 0, 100)$, which a hundred commutators of four moves each would reach in 400 moves, is reached in 40. The search confirms that 40 is the true distance, and more: at every perfect square $c = k^2$ up to the largest the search reaches, the distance from the identity to $(0, 0, c)$ is exactly $4k$, and for every $c$ in between it stays within four moves of $4\sqrt c$.

That is the mechanism behind the fourth power in one line. Moving a distance $c$ along the first two coordinates costs $c$ moves. Moving a distance $c$ along the third costs about $4\sqrt c$. Turned round: within $r$ moves the third coordinate can reach about $r^2/16$ in each direction, not $r$. The ball is about $r$ wide in two directions and about $r^2$ tall in the third, and $r \times r \times r^2$ is $r^4$.

A planimeter written as a group #

Why should walking round a square deposit its area in the third coordinate? Follow a word letter by letter and record the path its first two coordinates trace in the plane: each $x$ is a unit step east, each $y$ a unit step north. The third coordinate grows by $a$ at every step north and shrinks by $a$ at every step south, so after the whole word it equals $\sum a \, \Delta b$ — the sum, over the path’s vertical steps, of how far east they happen. For a closed path that sum is precisely the area enclosed, counted with a sign for the direction of travel. It is the formula $\oint x \, dy$ for area, and an area measured by walking round it built it into a brass instrument: the planimeter, whose wheel rolls round a boundary and reads off the area inside without touching it.

So the Heisenberg group is a planimeter written as an algebra. An element is a position in the plane together with the area swept on the way there, and multiplying two elements concatenates their paths and adds their areas, with the correction $ab'$ accounting for the triangle that joining the two paths closes off. The central elements are the closed paths, recorded by their area alone.

Seen this way, the distance to $(0, 0, c)$ is the answer to an isoperimetric question on the grid. A closed path of $L$ unit steps along the axes encloses at most $(L/4)^2$, attained by a square of side $L/4$ — the grid version of the fact in the most area a fence can hold, where the best fence is a circle and here, because the steps run only east, west, north and south, it is a square. A closed walk of length $4k$ therefore encloses at most $k^2$, and that bound is the reason the figure’s distances at the squares are exactly $4k$ and not less. The group has turned a statement about fences into a statement about how far apart its own elements are.

A shadow the size of the plane’s ball, with tall fibres #

The count can be split along the same lines. Forget the third coordinate and every element casts a shadow $(a, b)$ in the plane. Only $x$ and $y$ move the shadow, and they move it exactly as the unit steps move a point of the square lattice. So the shadow of the ball of radius $r$ is the plane’s own ball, the diamond $|a| + |b| \le r$, with $2r^2 + 2r + 1$ points. Over each shadow point stands a fibre: the values of $c$ for which $(a, b, c)$ is within reach.

At radius 24 the shadow has 1,201 points and the ball has 141,225 elements, so the average fibre holds about 118 values of $c$ — a number of order $r^2$, as the square-root cost predicts. The fibres are not even. Near the rim of the diamond almost the whole budget of moves is spent reaching $(a, b)$ at all, and nothing is left for sweeping area, so the fibres shrink to a point. More surprisingly, the fibre over the very centre, 73 values, is shorter than those over a broad band around it, which reach 145. A path that must come back to where it started can enclose only a square’s worth of area; a path allowed to end somewhere else has more freedom. That dip over the centre returns below as the most distinctive feature of the ball’s shape.

Shadow times fibre is $r^2 \times r^2$, and that is the most transparent way to see the fourth power: the abelian part of the group supplies a ball of degree two, and the layer above it, reached by commutators, supplies another two because each unit of it costs only a square root.

How the degree is counted #

Hyman Bass in 1972 and Yves Guivarc’h in 1973 proved that this bookkeeping is the general rule. A nilpotent group is one in which commutators, commutators of commutators and so on die out after finitely many layers: its elements can be built from a first layer of generators, a second layer of their commutators, a third of commutators with those, and so on until nothing new appears. The ball of such a group grows like $r^d$ with

$$d = \sum_k k \cdot \operatorname{rank}_k,$$

where $\operatorname{rank}_k$ is the number of independent directions in the $k$-th layer. A direction reached by $k$-fold commutators costs the $k$-th root of its length, so it contributes $k$ to the degree. For a lattice there is one layer and the formula counts directions. For the Heisenberg group the first layer has two directions and the second has one, so $d = 1 \cdot 2 + 2 \cdot 1 = 4$.

The measured exponents settle exactly where the formula says: 2.95 for the cubic lattice, 3.93 for the lattice in four dimensions, 4.01 for the Heisenberg group, and 4.96 for the Heisenberg group with an extra, commuting direction added, which contributes one more. All four approach their degrees from below, because a ball’s lower-order terms are relatively large at small radius and fade only as a power of $1/r$.

The figure also separates degree from size. The Heisenberg group and the four-dimensional lattice share degree four, and still at radius 44 the lattice has 2,618,881 elements to the Heisenberg group’s 1,600,703. The degree is an invariant of the group, unchanged by any choice of generators, for the reason how fast the ball fills gave: rescaling $r$ by a constant does not change the exponent of a power. The constant in front, about $0.427 r^4$ here, belongs to the generators and changes with them.

Spheres, and a walk that leaves #

A ball that grows like $r^4$ has spheres — the elements at exactly $r$ moves — that grow like $r^3$, since the sphere is the difference between successive balls. The computed spheres do: divided by $r^3$ they level off near 1.65 and drift up only slowly after radius twenty. The spheres are a vanishing fraction of the balls, about $4/r$ of them, which places the Heisenberg group firmly with the lattices on the question the edge that is as big as the ball used to divide groups: its boundary is negligible, so it cannot be cut into pieces that reassemble into two copies of itself, as the free group can.

The fourth power also decides how a random walk behaves on the group. How rarely a walk on a group comes home found the chance of being back at the start after $2n$ steps falling like $n^{-1/2}$ on the line, $n^{-1}$ on the plane and $n^{-3/2}$ in space, and quoted Varopoulos’s theorem that on a group of polynomial growth of degree $d$ it falls like $n^{-d/2}$. On the Heisenberg group that is $n^{-2}$, the rate of a walk in four dimensions. A walk with three coordinates to wander in therefore escapes as decisively as a walk in four dimensions does: the expected number of returns is finite, and with room to spare. The degree governs the walk as completely as it governs the count.

From far away, a ball with a dimple #

The polygon a lattice becomes from far away shrank a lattice’s ball by its radius and watched it converge to a polygon: a diamond for the unit steps, a hexagon or octagon for other moves. The faces are flat because a lattice is homogeneous — the cheapest way to go far in a fixed direction is to repeat the same mixture of moves, and costs add.

The Heisenberg ball cannot be shrunk uniformly, since its third coordinate grows like $r^2$. Pierre Pansu proved in 1983 that if $a$ and $b$ are divided by $r$ and $c$ by $r^2$ the balls do converge, to the unit ball of a new metric on the continuous Heisenberg group — a Carnot–Carathéodory metric, in which one may move only along directions in the plane, at a cost measured by the diamond, and the vertical direction is reached by sweeping area. The figure shows the top of the ball along one slice through it, at three radii.

The profiles at radii 11, 22 and 44 lie almost on top of one another, and the curve they approach is flat nowhere. Over the centre it rises to exactly $r^2/16$ at radius 44 — the square’s worth of area that a closed walk can enclose. Over $a = \pm r/2$ it rises to exactly $r^2/8$, twice as high. The highest point of the whole ball, $r^2/4$, stands over $(22, 22)$ at radius 44, reached by the plain word $x^{22} y^{22}$: its path runs east and then north, and the area it records is the whole 22-by-22 square between that path and the vertical axis. So the limit solid has a hollow at each pole: it is dimpled where a lattice’s limit would have a flat face, and curved everywhere else.

This is the strongest sense in which the group is not a lattice in disguise. Rescaling a lattice gives a normed space, flat and uniform; rescaling this group gives a space in which the shortest route between two points above one another is a helix-like arc that sweeps exactly the right area, and the distance between them is the square root of their height difference. No change of generators makes it flat.

Gromov’s converse #

Bass and Guivarc’h showed that nilpotent groups grow polynomially. In 1981 Mikhail Gromov proved the converse, which nobody had expected to be true in such generality: a finitely generated group whose balls grow no faster than some polynomial must contain a nilpotent group of finite index. So the mechanism on this page — layers of commutators, each costing a root of its length — is not one way among many for a group to grow polynomially. Up to finite pieces it is the only way. The Heisenberg group is the simplest group that is nilpotent without being a lattice, which makes it the simplest group whose degree is not its number of directions.

Gromov’s proof is itself a version of the last figure. He rescaled the group’s balls and showed that a limit space exists, then used the solution of Hilbert’s fifth problem to recognise a Lie group acting on it, and recovered the nilpotent subgroup from that. A count of elements at a distance forces an algebraic structure, and it does so through the shape of the ball seen from far away.

What lies outside both theorems is the strange middle. What homology forgets about a loop met the Heisenberg group as the place where loops in a figure eight first fail to commute, and the free group’s balls grow exponentially. In 1984 Rostislav Grigorchuk constructed a group whose balls grow faster than every polynomial and slower than every exponential, so the two kinds of answer do not exhaust the possibilities.

What the counting cannot show #

Every number here comes from a finite search, and a finite search measures exponents rather than proving them. The local exponent of 4.01 at radius thirty is evidence that the degree is four, not a proof; the proof is Bass and Guivarc’h’s, and the computation agrees with it. The same holds for the profile: three radii lying close together are consistent with Pansu’s convergence, and the exact values $r^2/16$, $r^2/8$ and $r^2/4$ at radius 44 match the isoperimetric argument, but a slice through a solid is not the solid. The limit ball is a three-dimensional body, and only one cross-section of it is drawn.

The search also stops at radius 44 because the ball by then holds 1.6 million elements, and the next doubling of the radius would multiply that by sixteen. The leading constant of about 0.427 is therefore known here to about two figures, and nothing on this page decides whether it is a simple number. Nor do the pictures show what makes the Heisenberg group nilpotent in the first place — that its commutator is central — except through its consequences; a group with the same shadow and a central direction that did not commute would not be a group at all.

Still open: the gap above the polynomials #

Gromov’s theorem says that growth bounded by a polynomial forces a nilpotent structure. Grigorchuk’s example shows that growth can be faster than every polynomial and slower than every exponential. Between the two, how slowly can a group grow without being nilpotent? Grigorchuk’s own group grows at least like $e^{\sqrt r}$ in a precise sense, and his gap conjecture proposes that this is the floor: every finitely generated group whose growth is slower than $e^{\sqrt r}$ is virtually nilpotent, and so actually grows like a polynomial. Yehuda Shalom and Terence Tao showed in 2010 that growth slower than $r^{c (\log \log r)^c}$ already forces nilpotence, a large improvement on Gromov’s polynomial bound and still enormously far from $e^{\sqrt r}$. The conjecture is proved for several large classes of groups and open in general.

The Heisenberg group sits at the bottom of that question rather than inside it, which is why it makes a good place to stop. It is the first group in which counting elements at a distance reveals an algebraic layer that the coordinates hide: three numbers name every element, and the fourth power is the trace of one commutator, priced at the square root of the area it encloses.