V.16 Gromov’s Polynomial-Growth Theorem

If G is a group and g₁, . . . , g_k are generators of G (meaning that every element of G can be expressed as a product of the g_i and their inverses), then we can define a Cayley graph by taking the elements of G as vertices and joining g to h if there is some i such that h is equal either to gg_i or to g

For each r, let _r be the number of elements that are at a distance of at most r from the identity: that is, the number of elements that can be written as a “word” of length at most r in the generators and their inverses. (For instance, if g = g₁g₂, then we know that g belongs to ₅.) It turns out that if G is an infinite group, then the rate of growth of the sizes of the sets _r can tell one a great deal about G; this is particularly true when the growth is less than exponential. (The growth is always bounded above by an exponential function, since there are at most exponentially many words of a given length in the generators g₁,. . . ,g_r.)

If G is an Abelian group generated by g₁,. . . , g_k, then every element of _r is of the form = 1^a_ig_i, where a₁, . . . ,a_k are integers such that = 1 |a_i| ≤ r. It follows easily that the size of ^r is at most (2r + 1)^k (and with a bit more effort one can improve this bound). Thus, as r tends to infinity, the growth rate of ^r is bounded above by a polynomial of degree k in r. If G is the FREE GROUP [IV.10 §2] generated by g₁,. . . , g_k, then all words of length r in the elements g_i (but not their inverses) give rise to distinct elements of G, so the size of ^r is at least k^r. Thus, in this case the growth rate is exponential. More generally, there will be an exponential growth rate whenever G contains a non-Abelian free subgroup.

These observations suggest that the growth rate is likely to be smaller if G is more like an Abelian group. Gromov’s theorem is a remarkably precise result along these lines. It states that the growth rate of the sets ^r is bounded above by a polynomial in r if and only if G has a nilpotent subgroup of finite index. This condition does indeed say that G is somewhat like an Abelian group, since nilpotent groups are “close to Abelian” and a subgroup of finite index is “close to the whole group.” For example, a typical nilpotent group is the Heisenberg group, which consists of all 3 × 3 matrices with 0s below the diagonal, 1s on the diagonal, and integers above the diagonal. Given any two such matrices X and Y, the products XY and YX differ only in the top right-hand corner, and the “error matrix” XV - YX commutes with everything in the group. In general, a nilpotent group is built out of Abelian groups in a controlled manner in a finite number of steps.

A fuller discussion of the theorem, including the exact definition of “nilpotent,” can be found in GEOMETRIC AND COMBINATORIAL GROUP THEORY [IV.10]. Here we highlight the fact that it is a beautiful example of a rigidity theorem: if a group behaves roughly in the way that a nilpotent group would (because the growth rate of the sets ^r is polynomial), then it must in fact be related to a nilpotent group in a very precise and algebraic way. (See MOSTOW’S STRONG RIGIDITY THEOREM [V.23] for another example of such a theorem.)