How fast a group grows

A wallpaper group can be written in four letters: a handful of generators and the relations they satisfy, with the plane thrown away entirely. What is left is an algebraic object, and the question this essay asks of it is one that seems to need the plane back and does not.

How many elements can be spelled in at most R letters?

An element’s word length is the shortest product of generators and their inverses that equals it. The elements of length at most R form a ball, and the sizes of those balls as R runs upwards are the group’s growth. No coordinates enter, no distances, nothing about a pattern; the input is a multiplication table.

The Cayley graph is a crystal net #

The construction above has a name in two subjects, and noticing that they are the same construction is the reason this essay sits beside the ones on crystal nets.

A Cayley graph joins each group element to each element one generator away. For a wallpaper group that graph is infinite, and the group’s own translations act on it freely with a finite quotient — which is, word for word, the definition of a periodic graph. So the Cayley graph of a wallpaper group is a crystal net, its quotient vertices are the cosets of the translation subgroup, and the voltage on an edge is the whole-cell part of the product.

The consequence is immediate and worth savouring. The number of elements at each word length is the number of vertices at each graph distance, which is a net’s coordination sequence — so the growth of a group and the shell counts of a crystal are one computation, done twice in two literatures.

The simplest case makes it plain. The group p1 is ℤ²; its Cayley graph against the two obvious generators is the square net; and its sphere sizes are 4, 8, 12, 16 — the square net’s coordination sequence, which is where this collection first met the numbers.

Every one of the seventeen grows quadratically #

Run the counting on all seventeen against the same kind of generating set — the two lattice translations together with whatever point-group generators the classification names — and the ball sizes come out as an exact quadratic in R.

The fitting is done the way this collection fits everything: a quadratic through three points of each residue class, required to be exact on every other point of that class, with a period reported only when the requirement is met. A fit that came from a tolerance would be worth nothing.

The degree of the growth is the dimension, and this is not a coincidence. A crystallographic group in d dimensions grows like R to the d, and the reason is that its ball of radius R contains roughly the lattice points inside a region of diameter proportional to R, which is a d-dimensional volume. The group knows how many dimensions it acts on, and it knows it from counting words.

That fact is the germ of a large theory. Gromov’s theorem, from 1981, says that a group grows polynomially exactly when it is virtually nilpotent — has a nilpotent subgroup of finite index — and a crystallographic group is virtually abelian, which is the easiest case. Growth is therefore one of the few properties of a group that can be read off a purely combinatorial count and that constrains its structure severely.

The coefficient is not an invariant #

The degree is a property of the group. The leading coefficient is not, and the demonstration is one line of measurement.

Add a third generator — the diagonal translation, which was always in the group and was previously spelled with two letters — and every word gets no longer and some get shorter. The balls grow, at every radius, in every group. The degree cannot change, because changing generators changes word lengths by at most a bounded factor and a bounded factor cannot turn a quadratic into a cubic.

And here the obvious sentence is wrong. The obvious sentence is the coefficient moves, because the ball is now a different shape, and it is what this essay said for a long time. Measured across all seventeen, the coefficient moves on twelve of them and does not move on the other five — p3, p3m1, p31m, p6 and p6m, which are exactly the groups whose lattice is hexagonal. p6m’s balls go from 8, 36, 107, 238 to 10, 44, 125, 270 and its leading coefficient stays at thirty-six.

The reason is worth having, because it says what the coefficient actually is. The coefficient is the area of the shape the balls converge to when they are scaled down by their own radius — the limit shape of the word metric — and adding a generator changes that shape only if the direction it points in was not already an extreme direction of it. On a square lattice the diagonal is not: the limit shape against the two axis translations is a diamond, the diagonal sticks out past its edge, and adding it clips two corners off and enlarges the area. On a hexagonal lattice the third short translation points along a direction the hexagonal limit shape already had, so the shape does not change and neither does its area. Everything below the leading term moves — which is why every ball size is larger — and the leading term does not.

So the honest statement has two halves. A growth coefficient quoted without a generating set means nothing, and every number in these essays carries one. But a generating set that grows every ball need not move the coefficient at all, and the five hexagonal groups are the cases in hand. It is the same discipline as quoting a cutoff with a net or a tolerance with a near-symmetry — the number is a property of a pair — with the extra warning that the dependence is not monotone in the size of the set.

What the coefficient does depend on #

Having said the coefficient is not an invariant, it is worth saying what it is, because the pattern in the table is not random.

Against the standard generating set the coefficient turns out to be the order of the point group multiplied by a factor that depends only on the shape of the lattice: two where the generators make a square-shaped ball, three where they make a hexagonal one. So p1 gives two, p2 and pm and pg and cm give four, the four groups of point-group order four give eight, p3 gives nine, and p6m gives thirty-six.

The reading is straightforward once seen. The elements of the group are the point-group elements times the translations; the translations of length at most R fill an area proportional to R², with the constant set by the shape of the generating set’s ball; and each of them is available in as many versions as the point group has elements. The coefficient is an area times an order, and the area is where the generating set gets in.

Why the counting is finite work #

There is an implementation point here that is worth an interruption, because it is the difference between a computation and a table copied from a paper.

A wallpaper group is infinite, so counting its elements of length at most thirty could be a search over a large number of things. It is not, because the Cayley graph is a net and a net is stored as a quotient: the search runs over pairs, a coset and a cell, and the cosets number at most twelve. Thirty terms of the largest of the seventeen is a few tens of thousands of vertices, which is nothing.

The representation had to be got right for that to work, and the wrong version failed instructively. An operation of a wallpaper group, as this collection stores one, is a coset: its translation part is reduced into the home cell, because that is what makes two descriptions of one coset equal. Reduce a lattice translation that way and it becomes the identity — so building a Cayley graph out of stored operations turns both generating translations into the identity, and produces a graph with one vertex, one loop of voltage zero, and a growth of nothing at all.

The fix is to carry an element as a pair: a coset, and the lattice vector by which this element differs from that coset’s representative. Composition then has to be written out rather than delegated, and the whole-cell part of each product has to be kept rather than discarded — which is exactly the voltage the quotient graph wants. The representation that makes the counting possible is the representation that makes it a net.

What growth cannot tell apart #

An invariant is worth what it decides, and this one decides less than it looks.

Four of the seventeen have identical ball sizes term for term against the standard generators: pmm, cmm and p4 share a sequence, and so do p3m1 and p31m. The last pair is the one that matters, because p3m1 and p31m are genuinely different groups — same point-group order, same kinds of operation, mirrors in different directions relative to the lattice — and no amount of counting words separates them.

That failure is instructive rather than embarrassing. Growth is a count, and a count cannot see orientation; distinguishing p3m1 from p31m requires knowing which way the mirrors lie with respect to the translations, which is exactly the information a ball size discards.

The series, and why it is rational #

There is a standard way of packaging a growth sequence, and it says something the sequence alone does not.

Form the growth series: the power series whose coefficients are the sphere sizes. For a crystallographic group that series is a rational function — a ratio of two polynomials — which is a strong statement, because it says the sequence satisfies a linear recurrence with constant coefficients and is therefore determined by finitely many of its terms plus a rule.

That claim is checkable here without any theory. A quasi-polynomial of degree two and period p satisfies the recurrence whose characteristic polynomial is (x^p − 1)³, so the coefficients of that recurrence can be formed from the measured period and applied to the measured sequence. If the sequence obeys it on every term of the tail, the series is rational in the way claimed; if it did not, the fit would be wrong.

It obeys it on every one of the seventeen. The check costs four multiplications per term and it is the difference between the growth looks quadratic and the growth satisfies an exact recurrence.

The same statement can be made without mentioning recurrences at all, and in that form it is a picture. Every period here is one, so the recurrence has characteristic polynomial (x − 1)³, and applying it to the ball sizes is the same as multiplying the whole series by (1 − x)³. If the series is N(x)/(1 − x)³ for a polynomial N, the product is N — a finite list of numbers followed by nothing. So the claim the series is rational with denominator (1 − x)³ is the claim that a certain column of arithmetic stops, and stopping is visible where satisfying a recurrence is not.

It stops between degree two and degree six across the seventeen. p1’s numerator is 1 + 2x + x², which is (1 + x)²; p2’s is (1 + x)³ and p4’s is (1 + x)⁴; p6m’s is 1 + 5x + 15x² + 22x³ + 17x⁴ + 9x⁵ + 3x⁶ and factors into nothing pleasant. There is no theorem here about which numerators are binomial — eight of the seventeen are and nine are not — and the pattern is a fact about the standard generating set rather than about the groups, in exactly the way the leading coefficient is.

What makes the row a measurement rather than a display is the last two columns. Sum the numerator at x = 1 and the answer is twice the leading coefficient of the quadratic fitted to the same sequence, on every one of the seventeen. That is not a coincidence and it is not a second copy of the same calculation: the coefficient of x^R in (1 − x)⁻³ is (R + 1)(R + 2)/2, which is asymptotically R²/2, so a series N(x)/(1 − x)³ has ball sizes approaching N(1)·R²/2 and its leading coefficient is N(1)/2. One number arrives from a fit on a tail of thirty terms and the other from adding up at most seven integers, and they agree exactly.

The domain, and where the generators came from #

One more identification closes the circle, and it is the subject of the companion essay.

The Cayley graph’s vertices are the group’s elements; the copies of a fundamental domain are also in one-to-one correspondence with the elements; and two copies share a wall exactly when the elements naming them differ by a wall-crossing. So the adjacency of the copies of a fundamental domain is a Cayley graph, against the generating set the walls supply.

That means the generating set — which the discussion above has been treating as an arbitrary choice — can be read off a picture, and the picture is one this collection already draws. It also means the growth of a group is the shell count of a tiling of the plane by copies of one region, which is about as geometric as a purely algebraic count could hope to become.

The shape of a ball #

One last thing the numbers say, which is easier to see in the drawings than in the table.

The ball of radius R in a Cayley graph, drawn in the plane, is not a disc. Against the two lattice translations it is a diamond, because word length is the sum of the absolute values of the coordinates — the metric a taxi driver uses, and the reason the square net’s shells are diamonds. Against three generators on a hexagonal lattice it is a hexagon.

So the leading coefficient is the area of the unit ball of the word metric, times the order of the point group. That is why adding a generator changes it: the ball is a different shape, so its area is different. And it is why the coefficient is never a property of the group alone — the shape belongs to the generating set, and a group has no preferred one.

The shapes also explain the periods. For these generating sets the ball’s corners land on lattice points at every R, so the counts are a plain polynomial and the period is one. A generating set whose ball had corners landing on lattice points only at every second R would produce period two, in exactly the way the kagome net’s shells do. Nothing in the seventeen produces one here, which is a fact about the standard generators rather than about the groups.

Three limits #

Growth is asymptotic. The early terms of a ball sequence are a boundary effect and obey no rule, which is why the fits here are made on a tail of a sequence run to thirty terms and checked there. Fitting the head produces coefficients that are artefacts of the head.

Growth does not see the plane. It cannot distinguish p3m1 from p31m, and it cannot tell a group from any group isomorphic to it — which is fine, because an isomorphism between two plane crystallographic groups is realised by an affine map, so isomorphic here means the same anyway. In other settings that would be a serious limitation.

Growth is a two-dimensional statement here only. The counting extends to any dimension and the degree is the dimension, but nothing in these figures has been run in three, and the periods that appear in higher-dimensional cases are not measured here.

Growth as a way of not needing a picture #

It is worth closing with what the exercise is for, because how many elements have length at most R is not a question anybody asks casually.

The point is that it is a question about a group which needs nothing but the group. A wallpaper group arrived here as a set of motions of a plane; the classification treats them as such throughout; and there is a persistent worry — this collection has raised it more than once — that the seventeen might be a classification of drawings rather than of algebra. Growth is one of the properties that could only have been defined algebraically, and it is a property the seventeen genuinely have.

It also gives a way of comparing a wallpaper group with objects that have no plane at all. A free group grows exponentially; a finite group’s growth stops; a crystallographic group grows polynomially with degree its dimension. Those are comparisons between things that could not otherwise be put on the same page, and they are the reason growth became a subject.

Where this goes #

Every wall names a generator makes the geometric half of this precise: the generators of a wallpaper group are read off the walls of a fundamental domain, and Poincaré’s theorem says the reading always works.

And the connection this essay opened — that a Cayley graph is a crystal net — runs the other way too. Everything the net ladder established about coordination sequences applies here: they are eventually quasi-polynomial, their periods are measurements, and two different objects can share one. A chemist counting shells around an atom and a group theorist counting words are doing the same arithmetic, and neither literature tends to mention the other.

The converse, which is a much larger statement #

That a crystallographic group grows polynomially is easy: it contains a lattice of finite index, and a lattice’s ball sizes are a volume. The converse is the deep statement, and it is worth writing down because it says what polynomial growth is a symptom of.

Gromov’s theorem, from 1981: a finitely generated group has polynomial growth if and only if it is virtually nilpotent — that is, it has a nilpotent subgroup of finite index.

The forward direction was known; the converse was not, and it is the surprise. A statement about counting words — an entirely combinatorial quantity, with no geometry and no algebra in it — turns out to force a structural property of the group. Nothing in the definition of the growth function mentions commutators, and the conclusion is about them.

For this collection the theorem is doing a specific job. The seventeen are virtually abelian — a lattice of finite index, and abelian is a special case of nilpotent — so their polynomial growth is an instance of the easy direction. What the converse says is that nothing else grows this way: a group whose ball sizes come out quadratic is, up to finite index, a lattice acting on something.

So the counting is a test for crystallinity, in a sense that needs no crystal. Hand over a group as generators and relations, count its balls, and a quadratic answer says the group has a ℤ² of finite index inside it — which by Bieberbach’s theorem means it acts on the plane as one of the seventeen.

The shape the balls converge to #

The leading coefficient is described as the area of a unit ball, and the object it is the area of deserves naming, because it is what the drawings converge to.

Scale the ball of radius R down by R and let R grow. The shapes converge to a fixed convex region — the limit shape of the word metric — and its area is the coefficient. For the lattice translations alone in p1 that region is a square rotated forty-five degrees, since the word metric is the sum of the absolute coordinates; adding the diagonal generators makes it an octagon; and for a hexagonal generating set it is a hexagon.

So the coefficient is a geometric quantity attached to the generating set, which is exactly why it can change when a generator is added while the degree cannot. And it is why it sometimes does not change: a generator whose direction already lies on the boundary of the limit shape adds no vertex to it and enlarges nothing. That is the whole of the hexagonal exception above, stated in the language the coefficient belongs to rather than as a list of four group names.

That also explains the periods in the ball sequences. A limit shape with corners is approximated by lattice points unevenly, and the unevenness recurs with a period set by how the corners sit relative to the lattice — the same phenomenon as the quasi-polynomial counts of a net’s shells and of lattice points in a scaled polygon, which are the same counting problem twice more.