Growth rate (group theory)
Encyclopedia
In group theory
, the growth rate of a group
with respect to a symmetric generating set
describes the size of balls in the group. 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.
s
(symmetric means that if
then 
).
Any element
can be expressed as a word in the T-alphabet
Let us consider the subset of all elements of G which can be presented 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 which 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.
for some
we say that G has a polynomial growth rate.
The infimum
of such ks is called the order of polynomial growth.
According to Gromov's theorem
, a group of polynomial growth is virtually nilpotent, 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
.
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, the growth rate of a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
with respect to a symmetric generating set
Generating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
describes the size of balls in the group. 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.
Definition
Suppose G is a finitely generated group; and T is a finite symmetric set of generatorGenerating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
s
(symmetric means that if
then ).Any element
can be expressed as a word in the T-alphabetLet us consider the subset of all elements of G which can be presented by such a word of length ≤ n
This set is just the closed ball
Ball (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open 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 graphCayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
with respect to T which 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 thatfor 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 ofgrowth does not (see below) and therefore the rate of growth gives an invariant of a group.
The word metric d and therefore sets
dependon 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
Iffor some
we say that G has a polynomial growth rate.The infimum
of such ks is called the order of polynomial growth.According to Gromov's theorem
Gromov's theorem on groups of polynomial growth
In geometric group theory, Gromov's theorem on groups of polynomial growth, named for Mikhail Gromov, characterizes finitely generated groups of polynomial growth, as those groups which have nilpotent subgroups of finite index....
, a group of polynomial growth is virtually nilpotent, i.e. it has a nilpotent
Nilpotent group
In mathematics, more specifically in the field of group theory, a nilpotent group is a group that is "almost abelian". This idea is motivated by the fact that nilpotent groups are solvable, and for finite nilpotent groups, two elements having relatively prime orders must commute...
subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of finite index
Index of a subgroup
In mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" of H that fill up G. For example, if H has index 2 in G, then intuitively "half" of the elements of G lie in H...
. 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 growthExponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
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 amenableAmenable group
In mathematics, an amenable group is a locally compact topological group G carrying a kind of averaging operation on bounded functions that is invariant under translation by group elements...
.
Examples
- A free groupFree groupIn mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
with a finite rank k > 1 has an exponential growth rate.
- A finite groupFinite groupIn mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
has constant growth – polynomial growth of order 0 – and includes fundamental groups of manifolds whose universal cover is compact.
- If M is a closed negatively curved Riemannian manifoldRiemannian manifoldIn Riemannian geometry and the differential geometry of surfaces, a Riemannian manifold or Riemannian space is a real differentiable manifold M in which each tangent space is equipped with an inner product g, a Riemannian metric, which varies smoothly from point to point...
then its fundamental groupFundamental groupIn mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...
has exponential growth rate. MilnorJohn MilnorJohn Willard Milnor is an American mathematician known for his work in differential topology, K-theory and dynamical systems. He won the Fields Medal in 1962, the Wolf Prize in 1989, and the Abel Prize in 2011. Milnor is a distinguished professor at Stony Brook University...
proved this using the fact that the word metric on
is quasi-isometric to the universal coverCovering mapIn mathematics, more specifically algebraic topology, a covering map is a continuous surjective function p from a topological space, C, to a topological space, X, such that each point in X has a neighbourhood evenly covered by p...
of M.
- Zd has a polynomial growth rate of order d.
- The discrete Heisenberg group H3 has a polynomial growth rate of order 4. This fact is a special case of the general theorem of BassHyman BassHyman Bass is an American mathematician, known for work in algebra and in mathematics education. From 1959-1998 he was Professor in the Mathematics Department at Columbia University, where he is now professor emeritus...
and Guivarch that is discussed in the article on Gromov's theoremGromov's theorem on groups of polynomial growthIn geometric group theory, Gromov's theorem on groups of polynomial growth, named for Mikhail Gromov, characterizes finitely generated groups of polynomial growth, as those groups which have nilpotent subgroups of finite index....
.
- The lamplighter group has an exponential growth.
- The existence of groups with intermediate growth, i.e. subexponential but not polynomial was open for many years. It was asked by MilnorJohn MilnorJohn Willard Milnor is an American mathematician known for his work in differential topology, K-theory and dynamical systems. He won the Fields Medal in 1962, the Wolf Prize in 1989, and the Abel Prize in 2011. Milnor is a distinguished professor at Stony Brook University...
in 1968 and was finally answered in the positive by GrigorchukRostislav GrigorchukRostislav Ivanovich Grigorchuk is a Soviet and Ukrainian mathematician working in the area of group theory. He holds the rank of Distinguished Professor in the Mathematics Department of Texas A&M University...
in 1984. There are still open questions in this area and a complete picture of which orders of growth are possible and which are not is missing.
- The triangle groupTriangle groupIn mathematics, a triangle group is a group that can be realized geometrically by sequences of reflections across the sides of a triangle. The triangle can be an ordinary Euclidean triangle, a triangle on the sphere, or a hyperbolic triangle...
s include 3 finite groups (the spherical ones, corresponding to sphere), 3 groups of quadratic growth (the Euclidean ones, corresponding to Euclidean plane), and infinitely many groups of exponential growth (the hyperbolic ones, corresponding to the hyperbolic plane).
See also
- Connections to isoperimetric inequalities