# Growth rate (group theory)

Growth rate (group theory)

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".

Definition

Suppose "G" is a finitely generated group; and "T" is a finite "symmetric" set of generators(symmetric means that if $x in T$ then $x^\left\{-1\right\} in T$). Any element $x in G$ can be expressed as a word in the "T"-alphabet

:$x = a_1 cdot a_2 cdots a_k mbox\left\{ where \right\} a_iin T$

Let us consider the subset of all elements of "G" which can be presented by such a word of length &le; "n"

:$B_n\left(G,T\right) = \left\{xin G | x = a_1 cdot a_2 cdots a_k mbox\left\{ where \right\} a_iin T mbox\left\{ and \right\} kle n\right\}$

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

:$B_n\left(G,T\right) = \left\{xin G | d\left(x, e\right)le n\right\}$

More geometrically, $B_n\left(G,T\right)$ 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 thatthey are equivalent ($asim b$) if there is a constant "C" such that

:$a\left(n/ C\right) leq b\left(n\right) leq a\left(Cn\right),,$

for example $p^nsim q^n$ if $p,q>1$.

Then the growth rate of the group "G" can be defined as the corresponding equivalence class of the function :$#\left(n\right)=|B_n\left(G,T\right)|,$where $|B_n\left(G,T\right)|$ denotes the number of elements in the set $B_n\left(G,T\right)$.Although the function $#\left(n\right)$ 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 $B_n\left(G,T\right)$ 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 :$\left\{1over C\right\} d_F\left(x,y\right) leq d_\left\{E\right\}\left(x,y\right) leq C d_F\left(x,y\right).$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

:$#\left(n\right)le C\left(n^k+1\right)$

for some polynomial growth rate.The infimum $k_0$ of such "ks is called the order of polynomial growth"'.According to Gromov's theorem, a group of polynomial growth is almost nilpotent, i.e. it has a nilpotent subgroup of finite index. In particular, the order of polynomial growth $k_0$ has to be a natural number and in fact $#\left(n\right)sim n^\left\{k_0\right\}$.

If $#\left(n\right)ge a^n$ for some $a>1$ we say that "G" has an exponential growth rate. Every finitely generated "G" has at most exponential growth, i.e. for some $b>1$ we have $#\left(n\right)le b^n$.

If $#\left(n\right)$ grows more slowly than any exponential function, "G" has a subexponential growth rate. Any such group is amenable.

Examples

* A free group with a finite rank "k" > 1 has an exponential growth rate.

* If "M" is a closed negatively curved Riemannian manifold then its fundamental group $pi_1\left(M\right)$ has exponential growth rate. Milnor proved this using the fact that the word metric on $pi_1\left(M\right)$ is quasi-isometric to the universal cover of "M".

* Z"d" has a polynomial growth rate of order "d".

* The discrete Heisenberg group "H"3 has a polynomial growth rate of order 4. This fact is a special case of the general theorem of Bass that is discussed in the article on Gromov's theorem.

* The lamplighter group has an exponential growth. This is a rare example of a solvable group with exponential growth.

* The existence of groups with intermediate growth, i.e. subexponential but not polynomial was open for many years. It was asked by Milnor in 1968 and was finally answered in the positive by 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.

ee also

Connections to isoperimetric inequalities

References

* J. Milnor, "A note on curvature and fundamental group", J. Differential Geometry 2 (1968), 1&ndash;7.
* R. I. Grigorchuk, "Degrees of growth of finitely generated groups and the theory of invariant means.", Izv. Akad. Nauk SSSR Ser. Mat. 48:5 (1984), 939&ndash;985 (Russian).
*cite web |author=Rostislav Grigorchuk and Igor Pak |title=Groups of Intermediate Growth: an Introduction for Beginners |year=2006 |publisher=arXiv |url=http://arxiv.org/abs/math.GR/0607384

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Growth rate — may refer to:*Exponential growth, a growth rate classification *Compound annual growth rate or CAGR, a measure of financial growth *Economic growth, the increase in value of the goods and services produced by an economy *Growth rate (group… …   Wikipedia

• 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 groups act (that is, when the… …   Wikipedia

• List of group theory topics — Contents 1 Structures and operations 2 Basic properties of groups 2.1 Group homomorphisms 3 Basic types of groups …   Wikipedia

• Lamplighter group — In mathematics, the lamplighter group L of group theory is the wreath product Z/2Z ≀ Z. The base group B of L is :igoplus {( infty, +infty)} mathbb{Z}/2mathbb{Z}, and so L / B is isomorphic to Z. The standard presentation for the lamplighter… …   Wikipedia

• Iterated monodromy group — In geometric group theory and dynamical systems the iterated monodromy group of a covering map is a group describing the monodromy action of the fundamental group on all iterations of the covering. It encodes the combinatorics and symbolic… …   Wikipedia

• Growth-share matrix — The BCG matrix (aka B.C.G. analysis, BCG matrix, Boston Box, Boston Matrix, Boston Consulting Group analysis) is a chart that had been created by Bruce Henderson for the Boston Consulting Group in 1970 to help corporations with analyzing their… …   Wikipedia

• Theory of Constraints — (TOC) is an overall management philosophy. Dr. Eliyahu M. Goldratt introduced the Theory of constraints in his 1984 book titled The Goal . It is based on the application of scientific principles and logic reasoning to guide human based… …   Wikipedia

• Theory of religious economy — The theory of religious economy is the application of rational choice theory as a theory of religion. The Theory of Religious Economy argues that the economic model of supply and demand has a significant role in the development and success of… …   Wikipedia

• Bacterial growth — Growth is shown as L = log(numbers) where numbers is the number of colony forming units per ml, versus T (time.) Bacterial growth is the division of one bacterium into two daughter cells in a process called binary fission. Providing no mutational …   Wikipedia

• theory — A reasoned explanation of known facts or phenomena that serves as a basis of investigation by which to seek the truth. SEE ALSO: hypothesis, postulate. [G. theoria, a beholding, speculation, t., fr. theoros, a beholder] adsorption t. of narcosis… …   Medical dictionary