⭕Geometric Group Theory Unit 5 – Growth Functions of Groups

Growth functions in geometric group theory quantify how quickly a group expands as you multiply generators. They provide insights into group structure and complexity, ranging from polynomial to exponential growth. Understanding growth functions helps classify groups and analyze their geometric properties. Key concepts include generating sets, word metrics, and Cayley graphs. Different growth types characterize various group structures, such as polynomial growth for abelian groups and exponential growth for free groups. Calculating and analyzing growth functions reveals fundamental properties of groups and their relationships.

Study Guides for Unit 5

5.1

Definition and basic properties of growth functions

4 min read

5.2

Growth types and classification

3 min read

5.3

Polynomial and exponential growth

3 min read

5.4

Gromov's theorem on groups of polynomial growth

3 min read

Key Concepts and Definitions

Growth function $\gamma(n)$ $γ (n)$ counts the number of elements in a group $G$ $G$ that can be expressed as a product of at most $n$ $n$ generators and their inverses
- Provides a quantitative measure of the size and complexity of the group
- Depends on the choice of generating set for the group
Generating set $S$ is a subset of a group $G$ such that every element of $G$ can be expressed as a finite product of elements from $S$ and their inverses
Word metric $d_S(g,h)$ $d_{S} (g, h)$ is the minimum number of generators from $S$ $S$ needed to express $g^{-1}h$ $g^{- 1} h$ in $G$ $G$
- Induces a metric space structure on the group
Cayley graph $\Gamma(G,S)$ $Γ (G, S)$ is a graph with vertices corresponding to elements of $G$ $G$ and edges connecting elements that differ by a generator from $S$ $S$
- Provides a geometric representation of the group and its growth

Types of Growth Functions

Polynomial growth: $\gamma(n)$ $γ (n)$ is bounded above by a polynomial function $Cn^d$ $C n^{d}$ for some constants $C>0$ $C > 0$ and $d\geq0$ $d \geq 0$
- Characterizes groups with a relatively simple structure (abelian groups, nilpotent groups)
Exponential growth: $\gamma(n)$ $γ (n)$ is bounded below by an exponential function $a^n$ $a^{n}$ for some constant $a>1$ $a > 1$
- Indicates a more complex group structure (free groups, hyperbolic groups)
Intermediate growth: $\gamma(n)$ $γ (n)$ grows faster than any polynomial but slower than any exponential function
- Grigorchuk group is a notable example of a group with intermediate growth
Subexponential growth: $\gamma(n)$ $γ (n)$ grows faster than any polynomial but is not necessarily exponential
- Includes groups with intermediate growth as a special case
Superpolynomial growth: $\gamma(n)$ $γ (n)$ grows faster than any polynomial function
- Encompasses both exponential and intermediate growth

Calculating Growth Functions

Direct counting: For small groups or specific generating sets, $\gamma(n)$ can be calculated by directly counting elements
Recurrence relations: In some cases, $\gamma(n)$ $γ (n)$ satisfies a recurrence relation that allows for efficient computation
- Example: For the free group on $k$ generators, $\gamma(n)=1+2k\sum_{i=0}^{n-1}\gamma(i)$
Generating functions: The growth function can be encoded as the coefficients of a formal power series $\sum_{n=0}^\infty\gamma(n)x^n$ $\sum_{n = 0}^{\infty} γ (n) x^{n}$
- Algebraic properties of the generating function provide insights into the growth behavior
Asymptotic estimates: For large $n$ $n$ , the growth function can be approximated using asymptotic techniques
- Example: Gromov's theorem states that a group has polynomial growth if and only if it is virtually nilpotent
Computational methods: For finitely presented groups, growth functions can be estimated using computer algorithms
- Example: The Todd-Coxeter algorithm can be used to enumerate cosets and estimate growth

Properties of Growth Functions

Invariance under change of generating set: The growth type (polynomial, exponential, etc.) is independent of the choice of generating set
- Different generating sets may yield different constants in the growth estimates
Submultiplicativity: For any two positive integers $m$ $m$ and $n$ $n$ , $\gamma(m+n)\leq\gamma(m)\gamma(n)$ $γ (m + n) \leq γ (m) γ (n)$
- Follows from the fact that any product of $m+n$ generators can be split into a product of $m$ generators and a product of $n$ generators
Monotonicity: The growth function is non-decreasing, i.e., $\gamma(n)\leq\gamma(n+1)$ for all $n$
Subadditivity: For any positive integer $n$ $n$ , $\gamma(n)\leq\sum_{i=0}^{n-1}\gamma(i)$ $γ (n) \leq \sum_{i = 0}^{n - 1} γ (i)$
- Consequence of the triangle inequality in the word metric
Relation to amenability: A finitely generated group is amenable if and only if its growth function satisfies a certain averaging property
- Følner's criterion: For every $\varepsilon>0$ , there exists a finite subset $F\subseteq G$ such that $|SF|<(1+\varepsilon)|F|$ , where $|SF|$ denotes the number of elements in the set $SF=\{sf:s\in S,f\in F\}$

Growth Functions and Group Structure

Abelian groups: All finitely generated abelian groups have polynomial growth
- The degree of the polynomial is equal to the rank of the group (number of independent generators)
Nilpotent groups: All finitely generated nilpotent groups have polynomial growth
- The degree of the polynomial is related to the nilpotency class of the group
Free groups: The free group on $k$ generators has exponential growth with $\gamma(n)=2k(2k-1)^{n-1}+1$ for $n\geq1$
Hyperbolic groups: Hyperbolic groups, which include free groups as a special case, have exponential growth
- The growth rate is related to the hyperbolicity constant of the group
Solvable groups: Solvable groups can have either polynomial or exponential growth
- The growth type depends on the derived series of the group
Amenable groups: Groups with subexponential growth are amenable, but the converse is not true
- There exist amenable groups with exponential growth, such as the lamplighter group

Applications in Geometric Group Theory

Classification of groups: Growth functions provide a way to distinguish between different classes of groups
- Example: Polynomial growth characterizes virtually nilpotent groups (Gromov's theorem)
Quasi-isometry invariance: The growth type is preserved under quasi-isometries between groups
- Allows for the study of geometric properties of groups up to quasi-isometry
Amenability and paradoxical decompositions: Growth functions are related to the amenability of groups and the existence of paradoxical decompositions
- Groups with subexponential growth do not admit paradoxical decompositions
Asymptotic dimension: The growth function can be used to estimate the asymptotic dimension of a group
- Groups with polynomial growth have finite asymptotic dimension
Random walks on groups: The growth function influences the behavior of random walks on the Cayley graph of a group
- Faster growth typically implies faster mixing times for random walks

Notable Examples and Case Studies

Integer lattice $\mathbb{Z}^d$ : The growth function is polynomial with $\gamma(n)\sim Cn^d$ for some constant $C>0$
Heisenberg group: A nilpotent group with polynomial growth of degree 4
Baumslag-Solitar groups $BS(m,n)=\langle a,b|ba^mb^{-1}=a^n\rangle$ : Have exponential growth unless $m=\pm n$
Grigorchuk group: The first example of a group with intermediate growth, answering the Milnor problem
Lamplighter group $\mathbb{Z}_2\wr\mathbb{Z}$ : An amenable group with exponential growth
Thompson's group $F$ : A finitely presented group with subexponential growth, conjectured to have intermediate growth
Automatic groups: A class of groups with efficiently computable growth functions using finite state automata
- Includes hyperbolic groups, braid groups, and Coxeter groups

Advanced Topics and Open Problems

Isoperimetric inequalities: Relate the growth of the boundary of a set to the growth of the set itself
- Can be used to estimate the growth function of a group
Entropy and growth: The growth rate of a group is related to the entropy of its action on its Cayley graph
- Provides a connection between growth functions and dynamical systems
Growth of subgroups: The growth of a subgroup can be different from the growth of the ambient group
- Example: The Grigorchuk group contains a subgroup isomorphic to the infinite dihedral group, which has linear growth
Growth of quotient groups: The growth of a quotient group $G/N$ $G / N$ is related to the growth of $G$ $G$ and the growth of $N$ $N$
- If $N$ has polynomial growth, then $G/N$ has the same growth type as $G$
Growth of group extensions: The growth of a group extension depends on the growth of the base group and the growth of the extending group
- Example: The wreath product of two groups with polynomial growth has polynomial growth
Algorithmic problems: Determining the growth type of a finitely presented group is algorithmically undecidable
- There is no general algorithm to compute the growth function of a given group
Gap conjecture: There is a gap between polynomial and exponential growth, i.e., there are no groups with growth functions of the form $e^{n^\alpha}$ $e^{n^{α}}$ for $0<\alpha<1$ $0 < α < 1$
- Remains an open problem in geometric group theory
Amenability and growth: The relationship between amenability and growth is not fully understood
- It is unknown whether there exist non-amenable groups with subexponential growth