This post continues my series on favourite theorems of the twenty-first century. My choice for 2006 in Algebra is a theorem of Emmanuel Breuillard and Tsachik Gelander on the growth of linear groups (Breuillard and Gelander 2008). Their paper first appeared as a preprint in 2006 and was published in Inventiones Mathematicae in 2008.
The theorem provides a remarkably strong answer to the following question: how quickly must the number of distinct products of generators of a group grow?
Let us begin with some definitions.
A group is a set equipped with an associative multiplication operation, an identity element, and inverses. For example, the invertible matrices with real entries form a group under matrix multiplication, denoted by .
A group is called finitely generated if there exists a finite subset such that every element of can be written as a product of elements of and their inverses.
For example, the group of integers is generated by the single element , since every integer is a sum of copies of or .
Given a finite generating set , let denote the number of elements of that can be expressed as products of at most elements of . Here
The function is called the growth function of the group relative to .
For example, if and , then because the integers that can be reached using at most additions or subtractions of are exactly .
Thus, the growth is linear.
Other groups may grow much faster.
Consider a group freely generated by two elements and . This means that distinct reduced words in the symbols represent distinct group elements, where a word is reduced if it has no adjacent pair of mutually inverse symbols.
For example, are all different elements.
In particular, there are distinct products of length using only and , without their inverses. Therefore, for .
A group with such rapidly growing numbers of elements is said to have exponential growth.
More precisely, a finitely generated group has exponential growth if, for some (and hence every) finite generating set ,
The existence of this limit follows from the elementary inequality
Although the qualitative distinction between exponential and subexponential growth does not depend on the choice of generators, the number generally does.
This raises a natural question: can we choose different generating sets for the same group so that its exponential growth rate becomes arbitrarily close to ?
A group is said to have uniform exponential growth if where the infimum is taken over all finite generating sets of .
Thus, uniform exponential growth means that there is a single exponential lower bound valid for every choice of generators.
In 1981, Gromov (Gromov 1981) asked whether every finitely generated group of exponential growth necessarily has uniform exponential growth.
This seemed plausible, since many of the familiar mechanisms producing exponential growth also give a uniform lower bound.
However, in 2004, Wilson (Wilson 2004) constructed a finitely generated group of exponential growth that does not have uniform exponential growth.
I discussed Wilson’s theorem in an earlier blog post.
Thus, Gromov’s question has a negative answer for general groups. But perhaps the answer is positive for more structured groups?
An important example is the class of linear groups: groups that can be represented as groups of invertible matrices over some field , that is, as subgroups of for some positive integer .
Linear groups have a much more rigid algebraic structure than arbitrary groups, and their growth has been extensively studied.
A fundamental result is Tits’ alternative, proved by Jacques Tits (Tits 1972) in 1972. It states that every finitely generated linear group either contains a nonabelian free subgroup or has a solvable subgroup of finite index.
The first possibility means that the group contains two elements satisfying no nontrivial relation. In particular, all reduced words in and are distinct.
The second possibility means that the group is virtually solvable, a structural condition saying that it contains a subgroup of finite index that can be reduced to abelian groups by a finite sequence of normal-subgroup quotients.
Thus, Tits’ alternative shows that linear groups which are not virtually solvable always contain a nonabelian free subgroup.
Consequently, they have exponential growth.
However, Tits’ theorem by itself does not imply uniform exponential growth. The free generators might require extremely long products of the elements of a chosen generating set .
In principle, changing could make the free subgroup increasingly difficult to reach.
In 2005, Eskin, Mozes, and Oh (Eskin et al. 2005) established uniform exponential growth for finitely generated linear groups over fields of characteristic zero.
Breuillard and Gelander’s work provides a stronger quantitative result, allowing arbitrary fields and, importantly, generating sets that are not required to contain inverses.
To formulate their theorem, let denote the set of all elements of expressible as products of at most elements of , without requiring that inverses belong to .
The most important feature is that depends only on the group , and not on the choice of generators .
Thus, no matter how we generate , the number of distinct products grows exponentially at a rate bounded away from .
The theorem is stronger than ordinary uniform exponential growth in two ways.
First, the set need not be symmetric: we do not assume that whenever .
Second, the lower bound includes the factor . Thus, choosing a larger generating set cannot make the guaranteed lower bound weaker.
Since the theorem immediately implies that has uniform exponential growth.
Let us explain the main idea behind the proof.
The authors establish a remarkable strengthening of Tits’ alternative.
They show that there exists an integer such that, for every finite generating set , one can find two elements , each expressible as a product of at most elements of , which freely generate a nonabelian free subgroup.
This is called uniform independence.
The distinction from Tits’ original theorem is crucial. Tits proved that such a pair exists somewhere in the group. Breuillard and Gelander show that it can always be found within a bounded distance of the identity, where the bound does not depend on the generating set.
Once such a pair is available, exponential growth follows immediately.
Indeed, the positive words of length in and are all distinct. Each is a product of at most elements of . Therefore, which gives the uniform exponential lower bound
This simple argument explains the connection between uniform independence and uniform exponential growth.
The sharper inequality in the theorem, including the factor and allowing nonsymmetric generating sets, follows from additional expansion estimates established in the paper.
But how do the authors find these two free generators at uniformly bounded distance?
Their proof uses the classical ping-pong method.
The idea is to make group elements act on a geometric space so that different transformations move points into disjoint regions.
For example, matrices act naturally on projective space, whose points correspond to one-dimensional subspaces of a vector space.
If two transformations have sufficiently strong attracting behaviour in appropriately separated regions, then different reduced words in these transformations have different effects on points. This allows one to prove that the transformations generate a free group.
The difficulty is not merely to find such transformations, but to find them as short products of an arbitrary generating set.
Breuillard and Gelander combine the ping-pong method with estimates on eigenvalues, matrix norms, and the geometry of linear groups over different fields. These estimates ensure that the required attracting transformations can always be constructed using a bounded number of generators.
Thus, a question about the number of group elements that can be reached in a given number of steps is reduced to a problem about the geometric action of matrices.
The theorem is a beautiful example of how algebraic structure can enforce a strong quantitative conclusion.
Wilson’s example shows that exponential growth need not be uniform for general finitely generated groups. Breuillard and Gelander show that, for linear groups containing a nonabelian free subgroup, such behaviour is impossible.
No matter how we change the generators, free behaviour appears within a bounded number of steps, and the group is forced to grow exponentially at a uniform rate.