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.
Definition Suppose G is a finitely generated group; and T is a finite symmetric set of generators (symmetric means that if x ∈ T {\displaystyle x\in T} then x − 1 ∈ T {\displaystyle x^{-1}\in T} ). Any element x ∈ G {\displaystyle x\in G} can be expressed as a word in the T-alphabet
x = a 1 ⋅ a 2 ⋯ a k where a i ∈ T . {\displaystyle x=a_{1}\cdot a_{2}\cdots a_{k}{\text{ where }}a_{i}\in T.}
Consider the subset of all elements of G that can be expressed by such a word of length ≤ n
B n ( G , T ) = { x ∈ G ∣ x = a 1 ⋅ a 2 ⋯ a k where a i ∈ T and k ≤ 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\leq 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:
B n ( G , T ) = { x ∈ G ∣ d ( x , e ) ≤ n } . {\displaystyle B_{n}(G,T)=\{x\in G\mid d(x,e)\leq n\}.}
More geometrically, B n ( G , T ) {\displaystyle B_{n}(G,T)} 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 ( a ∼ b {\displaystyle a\sim b} ) if there is a constant C such that for all positive integers n,
a ( n / C ) ≤ b ( n ) ≤ a ( C n ) , {\displaystyle a(n/C)\leq b(n)\leq a(Cn),\,}
for example p n ∼ q n {\displaystyle p^{n}\sim q^{n}} if p , q > 1 {\displaystyle p,q>1} . Then the growth rate of the group G can be defined as the corresponding equivalence class of the function
# ( n ) = | B n ( G , T ) | , {\displaystyle \#(n)=|B_{n}(G,T)|,}
where | B n ( G , T ) | {\displaystyle |B_{n}(G,T)|} denotes the number of elements in the set B n ( G , T ) {\displaystyle B_{n}(G,T)} . Although the function # ( n ) {\displaystyle \#(n)} 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 ( G , T ) {\displaystyle B_{n}(G,T)} 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
1 C d F ( x , y ) ≤ d E ( x , y ) ≤ C d F ( x , y ) . {\displaystyle {1 \over C}\ d_{F}(x,y)\leq d_{E}(x,y)\leq 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.
Polynomial and exponential growth If
# ( n ) ≤ C ( n k + 1 ) {\displaystyle \#(n)\leq C(n^{k}+1)}
… excerpt ends here. Continue reading the full article.
