Editing Growth rate (group theory) (section)

==Definition==
Suppose ''G'' is a finitely generated group; and ''T'' is a finite ''symmetric'' set of [[Generating set of a group|generator]]s
(symmetric means that if <math> x \in T </math> then <math> x^{-1} \in T </math>).
Any element <math> x \in G </math> can be expressed as a [[string (computer science)#Formal theory|word]] in the ''T''-alphabet

:<math> x = a_1 \cdot a_2 \cdots a_k \text{ where } a_i\in T. </math>

Consider the subset of all elements of ''G'' that can be expressed by such a word of length &le;&nbsp;''n''

:<math>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\}.</math>

This set is just the [[Ball (mathematics)|closed ball]] of radius ''n'' in the [[word metric]] ''d'' on ''G'' with respect to the generating set ''T'':

:<math>B_n(G,T) = \{x\in G \mid d(x, e)\le n\}.</math>

More geometrically, <math>B_n(G,T)</math> 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 (<math>a\sim b</math>) if there is a constant ''C'' such that for all positive integers&nbsp;''n'',

:<math> a(n/ C) \leq b(n) \leq a(Cn),\, </math>

for example <math> p^n\sim q^n </math> if <math> p,q>1 </math>.

Then the growth rate of the group ''G'' can be defined as the corresponding [[equivalence class]] of the function
:<math>\#(n)=|B_n(G,T)|, </math>
where <math>|B_n(G,T)|</math> denotes the number of elements in the set <math>B_n(G,T)</math>. Although the function <math>\#(n)</math> 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 <math>B_n(G,T)</math> depend on the generating set ''T''.  However, any two such metrics are [[Lipschitz continuity#Lipschitz continuity in metric spaces|''bilipschitz'']] [[equivalence class|''equivalent'']] in the following sense:  for finite symmetric generating sets ''E'', ''F'', there is a positive constant ''C'' such that
:<math> {1\over C} \ d_F(x,y) \leq d_E(x,y) \leq C \ d_F(x,y). </math>
As an immediate corollary of this inequality we get that the growth rate does not depend on the choice of generating set.