This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and earlier selections, see this post.
My choice for 2002 in Algebra is John S. Wilson’s construction of finitely generated groups which have exponential growth but fail to have uniform exponential growth. The result gives a negative answer to one of the central open questions in the theory of growth of groups, a question posed by Gromov in 1981 (Gromov 1981). Wilson’s theorem was proved in 2002 and published in 2004 (Wilson 2004).
The point of the theorem is that there are two rather different ways in which a finitely generated group can grow exponentially. The first is qualitative: balls in the Cayley graph grow exponentially fast for one, and hence for every, finite generating set. The second is quantitative and uniform: there is a single exponential lower bound which works independently of the choice of finite generating set. Gromov’s question asked whether the first phenomenon always forces the second. Wilson showed that it does not.
Recall that a generating set of a group is a subset such that every element can be written as a finite product of elements of and their inverses. The group is finitely generated if it admits a finite generating set. Given such a finite generating set , let Equivalently, is the size of the ball of radius around the identity in the Cayley graph .
The exponential growth rate of with respect to is The existence of this limit follows from submultiplicativity: the inequality implies that the limiting exponential rate is well-defined.
A finitely generated group is said to have exponential growth if for some finite generating set . This condition is independent of the choice of finite generating set: if and are two finite generating sets, then each element of has bounded word length with respect to , and conversely. Thus the two corresponding word metrics are quasi-isometric, and the property of having exponential growth does not depend on the chosen generators. In particular, if for one finite generating set , then for every finite generating set .
Uniform exponential growth is the stronger requirement that the exponential growth rate be bounded away from uniformly over all finite generating sets. That is, has uniform exponential growth if where the infimum is taken over all finite generating sets of . Thus a group has exponential growth but not uniform exponential growth precisely when every finite generating set gives exponential growth, but there are finite generating sets for which the growth rate is arbitrarily close to .
Gromov asked whether such behavior could occur. His question was natural partly because the known mechanisms producing exponential growth tended to produce it uniformly. For example, if a group contains a free semigroup on two generators with words of uniformly bounded length, then one obtains a uniform exponential lower bound. More generally, many classes of groups for which exponential growth was understood were eventually shown to have uniform exponential growth. A particularly important affirmative result is the case of finitely generated linear groups: if a finitely generated linear group has exponential growth, then it has uniform exponential growth. Results of this kind made Gromov’s question seem plausible for a long time.
Wilson’s theorem showed that the general picture is subtler.
In other words, Wilson constructed a finitely generated group such that for every finite generating set , but Thus grows exponentially no matter how one chooses generators, yet there are generating sets with respect to which the exponential growth is as slow as desired.