Gromov's theorem on groups of polynomial growth

The growth rate of a group is a well-defined notion from asymptotic analysis. To say that a finitely generated group has polynomial growth means the number of elements of length at most n (relative to a symmetric generating set) is bounded above by a polynomial function p(n). The order of growth is then the least degree of any such polynomial function p. A nilpotent group G is a group with a lower central series terminating in the identity subgroup. Gromov's theorem states that a finitely generated group has polynomial growth if and only if it has a nilpotent subgroup that is of finite index. ==Growth rates of nilpotent groups==

There is a vast literature on growth rates, leading up to Gromov's theorem. An earlier result of Joseph A. Wolf showed that if G is a finitely generated nilpotent group, then the group has polynomial growth. Yves Guivarc'h and independently Hyman Bass (with different proofs) computed the exact order of polynomial growth. Let G be a finitely generated nilpotent group with lower central series : G = G_1 \supseteq G_2 \supseteq \cdots. In particular, the quotient group Gk/Gk+1 is a finitely generated abelian group. The '''Bass–Guivarc'h formula' states that the order of polynomial growth of G'' is : d(G) = \sum_{k \geq 1} k \operatorname{rank}(G_k/G_{k+1}) where: :rank denotes the rank of an abelian group, i.e. the largest number of independent and torsion-free elements of the abelian group. In particular, Gromov's theorem and the Bass–Guivarc'h formula imply that the order of polynomial growth of a finitely generated group is always either an integer or infinity (excluding for example, fractional powers). Another nice application of Gromov's theorem and the Bass–Guivarch formula is to the quasi-isometric rigidity of finitely generated abelian groups: any group which is quasi-isometric to a finitely generated abelian group contains a free abelian group of finite index. ==Proofs of Gromov's theorem==

In order to prove this theorem Gromov introduced a convergence for metric spaces. This convergence, now called the Gromov–Hausdorff convergence, is currently widely used in geometry. A relatively simple proof of the theorem was found by Bruce Kleiner. Later, Terence Tao and Yehuda Shalom modified Kleiner's proof to make an essentially elementary proof as well as a version of the theorem with explicit bounds. Gromov's theorem also follows from the classification of approximate groups obtained by Breuillard, Green and Tao. A simple and concise proof based on functional analytic methods is given by Ozawa. == The gap conjecture ==

Beyond Gromov's theorem one can ask whether there exists a gap in the growth spectrum for finitely generated group just above polynomial growth, separating virtually nilpotent groups from others. Formally, this means that there would exist a function f: \mathbb N \to \mathbb N such that a finitely generated group is virtually nilpotent if and only if its growth function is an O(f(n)). Such a theorem was obtained by Shalom and Tao, with an explicit function n^{\log\log(n)^c} for some c > 0. All known groups with intermediate growth (i.e. both superpolynomial and subexponential) are essentially generalizations of Grigorchuk's group, and have faster growth functions; so all known groups have growth faster than e^{n^\alpha}, with \alpha = \log(2)/\log(2/\eta ) \approx 0.767, where \eta is the real root of the polynomial x^3+x^2+x-2. It is conjectured that the true lower bound on growth rates of groups with intermediate growth is e^{\sqrt n}. This is known as the Gap conjecture. == See also ==