This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Growth rate" group theory – news ·newspapers ·books ·scholar ·JSTOR(March 2011) (Learn how and when to remove this message)

In the mathematical subject ofgeometric group theory, thegrowth rate of agroup with respect to a symmetricgenerating 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 lengthn.

SupposeG is a finitely generated group; andT is a finitesymmetric set ofgenerators(symmetric means that if${\displaystyle x\in T}$ then${\displaystyle x^{-1}\in T}$).Any element${\displaystyle x\in G}$ can be expressed as aword in theT-alphabet

${\displaystyle x=a_1\cdot a_2\cdots a_k\text{ where }{a}_i\in T.}$

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

${\displaystyle B_n(G,T)=\{x\in G\mid x=a_1\cdot a_2\cdots a_k\text{ where }{a}_i\in T\text{ and }k\le n\}.}$

This set is just theclosed ball of radiusn in theword metricd onG with respect to the generating setT:

${\displaystyle B_n(G,T)=\{x\in G\mid d(x,e)\le n\}.}$

More geometrically,${\displaystyle B_n(G,T)}$ is the set of vertices in theCayley graph with respect toT that are within distancen of the identity.

Given two nondecreasing positive functionsa andb one can say that they are equivalent (${\displaystyle a\sim b}$) if there is a constantC such that for all positive integers n,

${\displaystyle a(n/C)\le b(n)\le a(Cn),}$

for example${\displaystyle p^n\sim q^n}$ if${\displaystyle p,q>1}$.

Then the growth rate of the groupG can be defined as the correspondingequivalence class of the function

${\displaystyle \mathrm{\#}(n)=|B_n(G,T)|,}$

where${\displaystyle |B_n(G,T)|}$ denotes the number of elements in the set${\displaystyle B_n(G,T)}$. Although the function${\displaystyle \mathrm{\#}(n)}$ depends on the set of generatorsT its rate of growth does not (see below) and therefore the rate of growth gives an invariant of a group.

The word metricd and therefore sets${\displaystyle B_n(G,T)}$ depend on the generating setT. However, any two such metrics arebilipschitzequivalent in the following sense: for finite symmetric generating setsE,F, there is a positive constantC such that

${\displaystyle \frac{1}{C}{d}_F(x,y)\le d_E(x,y)\le C{d}_F(x,y).}$

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

If

${\displaystyle \mathrm{\#}(n)\le C(n^k+1)}$

for some we say thatG has apolynomial growth rate.The infimum${\displaystyle k_0}$ of suchk's is called theorder of polynomial growth.According toGromov's theorem, a group of polynomial growth is avirtuallynilpotent group, i.e. it has anilpotentsubgroup of finiteindex. In particular, the order of polynomial growth${\displaystyle k_0}$ has to be anatural number and in fact${\displaystyle \mathrm{\#}(n)\sim n^{k_0}}$.

If${\displaystyle \mathrm{\#}(n)\ge a^n}$ for some${\displaystyle a>1}$ we say thatG has anexponential growth rate.Everyfinitely generatedG has at most exponential growth, i.e. for some${\displaystyle b>1}$ we have${\displaystyle \mathrm{\#}(n)\le b^n}$.

If${\displaystyle \mathrm{\#}(n)}$ growsmore slowly than any exponential function,G has asubexponential growth rate. Any such group isamenable.

• Afree group of finite rank${\displaystyle k>1}$ has exponential growth rate.
• Afinite group has constant growth—that is, polynomial growth of order 0—and this includesfundamental groups ofmanifolds whoseuniversal cover iscompact.
• IfM is aclosednegatively curvedRiemannian manifold then itsfundamental group${\displaystyle {\pi }_1(M)}$ has exponential growth rate.John Milnor proved this using the fact that theword metric on${\displaystyle {\pi }_1(M)}$ isquasi-isometric to theuniversal cover ofM.
• Thefree abelian group${\displaystyle {\mathbb{Z}}^d}$ has a polynomial growth rate of orderd.
• Thediscrete Heisenberg group${\displaystyle H_3}$ has a polynomial growth rate of order 4. This fact is a special case of the general theorem ofHyman Bass andYves Guivarch that is discussed in the article onGromov's theorem.
• Thelamplighter group has an exponential growth.
• The existence of groups withintermediate 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 byRostislav 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.
• Thetriangle groups 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).

• Connections to isoperimetric inequalities

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

• Rostislav Grigorchuk andIgor Pak (2006). "Groups of Intermediate Growth: an Introduction for Beginners".arXiv:math.GR/0607384.

• Infinite group theory
• Cayley graphs
• Metric geometry

• Articles needing additional references from March 2011
• All articles needing additional references
• CS1 Russian-language sources (ru)