Growth rate (group theory)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In the mathematical subject of geometric group theory, the growth rate of a group with respect to a symmetric generating set describes how fast a group grows. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length n.


Suppose G is a finitely generated group; and T is a finite symmetric set of generators (symmetric means that if then ). Any element can be expressed as a word in the T-alphabet

Consider the subset of all elements of G that can be expressed by such a word of length ≤ n

This set is just the closed ball of radius n in the word metric d on G with respect to the generating set T:

More geometrically, is the set of vertices in the Cayley graph with respect to T that are within distance n of the identity.

Given two nondecreasing positive functions a and b one can say that they are equivalent () if there is a constant C such that

for example if .

Then the growth rate of the group G can be defined as the corresponding equivalence class of the function

where denotes the number of elements in the set . Although the function depends on the set of generators T its rate of growth does not (see below) and therefore the rate of growth gives an invariant of a group.

The word metric d and therefore sets depend on the generating set T. However, any two such metrics are bilipschitz equivalent in the following sense: for finite symmetric generating sets E, F, there is a positive constant C such that

As an immediate corollary of this inequality we get that the growth rate does not depend on the choice of generating set.

Polynomial and exponential growth[edit]


for some we say that G has a polynomial growth rate. The infimum of such k's is called the order of polynomial growth. According to Gromov's theorem, a group of polynomial growth is a virtually nilpotent group, i.e. it has a nilpotent subgroup of finite index. In particular, the order of polynomial growth has to be a natural number and in fact .

If for some we say that G has an exponential growth rate. Every finitely generated G has at most exponential growth, i.e. for some we have .

If grows more slowly than any exponential function, G has a subexponential growth rate. Any such group is amenable.


See also[edit]


  • Milnor J. (1968). "A note on curvature and fundamental group". Journal of Differential Geometry. 2: 1–7. doi:10.4310/jdg/1214501132.
  • Grigorchuk R. I. (1984). "Degrees of growth of finitely generated groups and the theory of invariant means". Izv. Akad. Nauk SSSR Ser. Mat. (in Russian). 48 (5): 939–985.

Further reading[edit]