How fast the ball fills

The group drawn as a map turns a group into a metric object and then says what the finite pictures cannot carry: “growth — how the number of elements within distance r behaves as r increases — is the fundamental invariant of the infinite theory, and it is invisible in any finite picture.”

It is not invisible in a finite count. Take an infinite group, pick a generating set, and count the elements reachable in at most $r$ steps. That is a finite number for every $r$, and the sequence of them is the invariant.

What the counts are, and where they come from #

The counts are produced by a search rather than a formula, which matters for what they are evidence of. Start at the identity, apply each of the generators, keep what is new, repeat. That is a breadth-first walk on the Cayley graph, and the number of elements at distance exactly $k$ is the $k$-th shell.

For the integers generated by $\pm 1$ the shells are $1, 2, 2, 2, \ldots$ and the ball is $2r+1$. For the integers squared generated by the four unit steps the shells are $1, 4, 8, 12, \ldots$ — each shell is a diamond of perimeter $4k$ — and the ball is $2r^2 + 2r + 1$. For the free group on two generators every element has four neighbours and exactly one of them is closer to the identity, so each element has three children and the shells are $1, 4, 12, 36, \ldots$, giving $2 \cdot 3^r - 1$.

Those three formulas are checked against the search at every radius the figures draw, which is the discipline that makes a count of a few hundred elements say something about an infinite group: the search knows only the group’s multiplication, and a formula disagreeing with it would be reported.

Two shapes, and the whole distinction #

Put the two drawings side by side and the arithmetic is visible as geometry. A ball in the lattice is a flat region whose shells are perimeters: each shell grows by a constant, so the total grows like a square. A ball in the free group is a tree whose shells triple: each shell is larger than everything inside it put together.

That second sentence is worth stating exactly, because it is the tree’s defining oddity. The ball of radius $r$ in $F_2$ has $2 \cdot 3^r - 1$ elements and its outermost shell has $4 \cdot 3^{r-1}$, which is two thirds of the whole. Most of a tree is its leaves, at every size, and no amount of growing changes the proportion.

In the lattice the proportion falls. The ball of radius $r$ has about $2r^2$ elements and its shell about $4r$, so the shell’s share is about $2/r$ and goes to nothing. The difference between those two behaviours is the subject of the edge as big as the ball, and here it is the reason the growth rates are what they are.

The lattice in three dimensions, and the pattern of the degrees #

The lattice in $d$ dimensions has a ball whose size is a polynomial in $r$ of degree exactly $d$, and the reason is the obvious one: the ball is the set of integer points with $|x_1| + \cdots + |x_d| \le r$, which is a solid region of diameter proportional to $r$ in $d$ dimensions, so it holds about $r^d$ points. The leading coefficient is $2^d/d!$, from the volume of the region, and the lower-order terms are the boundary corrections.

So the degrees of polynomial growth available to the abelian groups are exactly the ranks. That is not surprising, and it is worth having on the page because the theorem quoted below says something much stronger: every group of polynomial growth has a whole-number degree, not only the lattices, and the degree is computed from a decomposition into commuting layers. A group of growth degree five need not be $\mathbb{Z}^5$ and it has to be built from layers whose ranks add up in the right way.

The three rows also show where the counting stops being cheap in the other direction: the ball of radius six in the integers cubed already has 377 elements against the integers’ 13, and the search grows like the answer. Polynomial growth is slow only relative to exponential.

Why the distinction survives a change of generators #

The group drawn as a map is emphatic that a Cayley graph is an invariant of a group with a choice, and that the diameter, the degree and the planarity are properties of the presentation rather than of the group. So it needs saying why growth is not.

Change the generating set from $S$ to $T$. Each generator of $T$ is a word of some length in $S$, so let $C$ be the largest such length; then a $T$-word of length $k$ is an $S$-word of length at most $Ck$, and so $B_T(r) \subseteq B_S(Cr)$. Symmetrically with the roles swapped. So the two counting functions bound each other up to a constant factor in the radius:

$$\beta_T(r) \le \beta_S(Cr), \qquad \beta_S(r) \le \beta_T(C'r).$$

That is not equality and it does not need to be. Whether a function grows like a polynomial of degree $d$ is unchanged by rescaling its argument, since $(Cr)^d = C^d r^d$; whether it grows exponentially is unchanged for the same reason. The growth type survives and the growth function does not, which is exactly the distinction that earlier essay sets up when it says the large-scale features are the group’s and the fine detail is the presentation’s.

The integers generated by $\{1\}$ have $\beta(r) = 2r+1$; generated by $\{2, 3\}$ they have a different function with the same linear type. Neither is more correct and the type is the thing to quote.

Two groups, one growth type #

Growth does not determine the group, and the cheapest example is worth having in the table. Take two reflections $s$ and $t$ of a line, at different points. Their composition is a translation, and the group they generate — the infinite dihedral group — is every word alternating $s$ and $t$. Its ball of radius $r$ has $2r+1$ elements, exactly as the integers’ does.

The two groups are not isomorphic: one is commutative and the other is not, and one has elements of order two and the other has none. So linear growth is compatible with two genuinely different groups, and the invariant is coarse.

Coarse is what it is for. The whole programme the map of a group describes takes the Cayley graph as the group up to a notion of equivalence that ignores bounded detail, and under that equivalence these two groups are the same — each contains the other with finite index, which is the relation the growth cannot see past. What growth measures is exactly the part that survives, and asking it to distinguish more is asking it for the wrong thing.

Which growth types occur #

The natural next question is what is possible, and the answer is a theorem nobody expected followed by an example nobody expected either.

Polynomial growth is very restrictive. Gromov proved in 1981 that a finitely generated group whose ball grows like a polynomial is virtually nilpotent — it contains a finite-index subgroup built out of commuting layers, of which the integers to a power is the simplest case. That is a startling statement: a condition counting elements at a distance forces an algebraic structure, with no hypothesis about what the group is made of. And the degree is then a whole number, computed from the layers.

So a group cannot grow like $r^{1.5}$. The polynomial degrees available are exactly the whole numbers, which is not something the counting suggests.

And between polynomial and exponential there is room. Milnor asked in 1968 whether every group grows either polynomially or exponentially, and Grigorchuk answered it in 1984 by constructing a group that does neither — its ball grows faster than every polynomial and slower than every exponential. The construction is a group of automorphisms of an infinite binary tree, it is generated by four elements, and nothing about it is a modification of a familiar group.

That answer is the reason the classification is a subject rather than a dichotomy. The growth of a group is a function and the possible functions are constrained in ways that are understood at the two ends and not in the middle.

Where growth already appeared in this collection #

Two of the groups above have been drawn here before under different names, and noticing it is the quickest way to see that the invariant is about the picture rather than about the algebra.

The cyclic group of order $n$ is the roots of unity and its Cayley graph with one generator is a ring. It is finite, so its growth stops — the ball reaches the whole group at radius $n-1$ and stays there. A finite group’s growth function is eventually constant, which is the degenerate case of polynomial growth and is why the invariant says nothing about finite groups at all.

The free group’s tree is the shape a subgroup cuts a group into seen from the other side: a subgroup of finite index in the free group has cosets that are a finite partition of an infinite tree, and each coset is itself a copy of the tree’s coarse shape. That is why passing to a finite-index subgroup leaves the growth type alone, which is the invariance the section above needs and which the coset picture makes obvious — the cosets have equal size and there are finitely many, so the ball in the subgroup and the ball in the group differ by a bounded factor.

So the two invariances have the same source. Changing the generating set rescales the radius; passing to a finite-index subgroup rescales the count. Growth type is insensitive to both, and the two together are most of what the coarse equivalence that map names allows.

What the counts cost, and where they stop #

A ball of radius eight in the free group has thirteen thousand elements, and one of radius twenty has more than ten billion. So the search is feasible for small radii only, and every figure here stops where the exponential case becomes impractical. For the polynomial groups the ball grows slowly enough to go much further, which is itself a small demonstration of the distinction.

The normal form is what makes a search possible at all. A group given by generators and relations has no algorithm for deciding when two words are equal, and the search above depends on being able to tell. Every group drawn here has a normal form that a few lines compute — reduce a word, add a vector, alternate two letters — and the groups that do not are exactly the ones this apparatus cannot reach.

And the counting answers nothing about the group’s structure by itself. Gromov’s theorem is the statement that it answers a great deal, and the proof is not a counting argument: it passes to a limit of rescaled Cayley graphs and finds a space with enough structure to build the algebra from. A growth rate is a piece of evidence and the theorem is what makes it a conclusion.

What the pictures cannot show #

Every drawing here is a ball of radius four or five, and the groups are infinite. What the drawings show is the mechanism — shells that grow by a constant, shells that triple — and the mechanism is what the formulas prove and the counting checks.

The tree’s layout is a drawing choice with no content, exactly as the earlier map’s layout was. The angular splitting that makes the free group’s ball legible is not part of the group, and a different layout of the same graph would look unrelated; what is real is which elements are adjacent.

And nothing here shows a growth rate. A rate is a statement about a limit, the counts stop at radius six or seven, and the ratio of consecutive balls at radius six is not the limit of that ratio. The figures report the ratio and say what it is; the type is read off it under the arithmetic above, and a group whose behaviour changed after radius twenty would be invisible.

Still open: the gap in the middle #

Grigorchuk’s group grows between the polynomial and the exponential, and how much room there is in that gap is not known. The known constructions produce growth functions of the form $\exp(r^{\alpha})$ for various $\alpha$ strictly between nought and one, and a range of $\alpha$ is now known to be achievable — but the set of achievable ones is not determined, and whether every value in some interval occurs is open.

There is a lower bound on how slowly a group can grow without being polynomial, and it is a genuine gap: Grigorchuk’s group grows at least as fast as $\exp(\sqrt{r})$, and no group is known to grow more slowly than that without growing polynomially. Whether that is a theorem — whether there is a gap immediately above polynomial growth — is the standing open question in the subject and has been since the first example was built.

The other open direction concerns which functions are growth functions at all. A growth function is increasing, submultiplicative and defined on the whole numbers; those conditions are necessary and nowhere near sufficient, and no characterisation is known.

The one thing the shells say that the balls do not #

A ball’s size is a running total and the shells are the increments, and the increments are where the mechanism is legible.

For the lattice in $d$ dimensions the shell at radius $k$ has about $c\,k^{d-1}$ elements: the boundary of a $d$-dimensional region. So the shells grow polynomially with degree one less than the balls, and the ball is a sum of the shells — which is the discrete version of a volume being an integral of surface areas.

For the free group the shell at radius $k$ has $4 \cdot 3^{k-1}$ elements and the ball has $2 \cdot 3^k - 1$, so the shell is a fixed fraction of the ball rather than a smaller-order term. That is the arithmetic signature of exponential growth and it is the thing to look at when the closed form is unknown: a shell that is a constant share of its ball means exponential, and one that is a vanishing share means subexponential.

The shell-to-ball ratio is therefore a better instrument than the ball count itself, because it converges rather than diverging. At radius six the free group’s ratio is already 0.667 and the lattice’s is 0.282, and extending the radius sharpens the first and drives the second towards nothing. A ratio that settles at a positive number and a ratio that falls to nought are distinguishable in a way that two increasing sequences of counts are not, and that observation is the whole of the argument about edges.

What one number a radius buys #

A group is an algebraic object and counting is not an algebraic operation. What this essay adds is that one arithmetic sequence — how many elements are near the identity — carries enough information to force algebraic structure, and the forcing is a deep theorem rather than a definition.

The reason it can is that the count is about the group and not about the presentation, and the argument for that is three lines: each generating set’s words bound the other’s in length, so the counting functions bound each other after rescaling, and the growth type is rescaling-invariant. Everything after that is the mathematics of which types occur.

Which leaves a habit worth carrying past this page. When a construction depends on a choice, the useful question is not how to avoid the choice but which of the answers survive it — and the answer is usually a coarser quantity than the one first computed. Here the choice is the generating set, the surviving quantity is the growth type, and it turned out to be enough to classify the polynomial case completely.