In the mathematical subject of
geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these group ...
, the growth rate of a
group with respect to a symmetric
generating set
In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied to ...
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''.
Definition
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
A word is a basic element of language that carries semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguist ...
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
In mathematics, a ball is the solid figure bounded by a ''sphere''; it is also called a solid sphere. It may be a closed ball (including the boundary points that constitute the sphere) or an open ball (excluding them).
These concepts are defin ...
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
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...
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 all positive integers ''n'',
:
for example
if
.
Then the growth rate of the group ''G'' can be defined as the corresponding
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
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
If
:
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 a
virtually nilpotent group
In mathematics, specifically group theory, a nilpotent group ''G'' is a group that has an upper central series that terminates with ''G''. Equivalently, it has a central series of finite length or its lower central series terminates with .
I ...
, i.e. it has a
nilpotent
In mathematics, an element x of a ring (mathematics), ring R is called nilpotent if there exists some positive integer n, called the index (or sometimes the degree), such that x^n=0.
The term, along with its sister Idempotent (ring theory), idem ...
subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
Formally, given a group (mathematics), group under a binary operation  ...
of finite
index
Index (: indexes or indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on the Halo Array in the ...
. In particular, the order of polynomial growth
has to be a
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
and in fact
.
If
for some
we say that ''G'' has an
exponential growth
Exponential growth occurs when a quantity grows as an exponential function of time. The quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast ...
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.
Examples
* A
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''− ...
of finite rank
has exponential growth rate.
* A
finite group
In abstract algebra, a finite group is a group whose underlying set is finite. Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving tra ...
has constant growth—that is, polynomial growth of order 0—and this includes
fundamental group
In the mathematics, mathematical field of algebraic topology, the fundamental group of a topological space is the group (mathematics), group of the equivalence classes under homotopy of the Loop (topology), loops contained in the space. It record ...
s of
manifold
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
s whose
universal cover
In topology, a covering or covering projection is a map between topological spaces that, intuitively, locally acts like a projection of multiple copies of a space onto itself. In particular, coverings are special types of local homeomorphism ...
is
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact, a type of agreement used by U.S. states
* Blood compact, an ancient ritual of the Philippines
* Compact government, a t ...
.
* If ''M'' is a
closed negatively curved Riemannian manifold
In differential geometry, a Riemannian manifold is a geometric space on which many geometric notions such as distance, angles, length, volume, and curvature are defined. Euclidean space, the N-sphere, n-sphere, hyperbolic space, and smooth surf ...
then its
fundamental group
In the mathematics, mathematical field of algebraic topology, the fundamental group of a topological space is the group (mathematics), group of the equivalence classes under homotopy of the Loop (topology), loops contained in the space. It record ...
has exponential growth rate.
John Milnor
John Willard Milnor (born February 20, 1931) is an American mathematician known for his work in differential topology, algebraic K-theory and low-dimensional holomorphic dynamical systems. Milnor is a distinguished professor at Stony Brook Uni ...
proved this using the fact that the
word metric on
is
quasi-isometric to the
universal cover
In topology, a covering or covering projection is a map between topological spaces that, intuitively, locally acts like a projection of multiple copies of a space onto itself. In particular, coverings are special types of local homeomorphism ...
of ''M''.
* The
free abelian group
In mathematics, a free abelian group is an abelian group with a Free module, basis. Being an abelian group means that it is a Set (mathematics), set with an addition operation (mathematics), operation that is associative, commutative, and inverti ...
has a polynomial growth rate of order ''d''.
* The
discrete Heisenberg group has a polynomial growth rate of order 4. This fact is a special case of the general theorem of
Hyman Bass and
Yves Guivarch that is discussed in the article on
Gromov's theorem.
* 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. The question was asked by Milnor in 1968 and was finally answered in the positive by
Rostislav Grigorchuk 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 group
In 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 triang ...
s include infinitely many finite groups (the spherical ones, corresponding to sphere), three 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
References
*
*
Further reading
*{{cite arXiv , author=Rostislav Grigorchuk and
Igor Pak , title=Groups of Intermediate Growth: an Introduction for Beginners , year=2006 , eprint=math.GR/0607384
Infinite group theory
Cayley graphs
Metric geometry