Yehuda Shalom and I have just uploaded to the arXiv our paper “A finitary version of Gromov’s polynomial growth theorem“, to be submitted to Geom. Func. Anal..  The purpose of this paper is to establish a quantitative version of Gromov’s polynomial growth theorem which, among other things, is meaningful for finite groups.   Here is a statement of Gromov’s theorem:

Gromov’s theorem. Let G be a group generated by a finite (symmetric) set S, and suppose that one has the polynomial growth condition

|B_S(R)| \leq R^d (1)

for all sufficiently large R and some fixed d, where B_S(R) is the ball of radius R generated by S (i.e. the set of all words in S of length at most d, evaluated in G).  Then G is virtually nilpotent, i.e. it has a finite index subgroup H which is nilpotent of some finite step s.

As currently stated, Gromov’s theorem is qualitative rather than quantitative; it does not specify any relationship between the input data (the growth exponent d and the range of scales R for which one has (1)), and the output parameters (in particular, the index |G/H| of the nilpotent subgroup H of G, and the step s of that subgroup).  However, a compactness argument (sketched in this previous blog post) shows that some such relationship must exist; indeed, if one has (1) for all R_0 \leq R \leq C( R_0, d ) for some sufficiently large C(R_0,d), then one can ensure H has index at most C'(R_0,d) and step at most C''(R_0,d) for some quantities C'(R_0,d), C''(R_0,d); thus Gromov’s theorem is inherently a “local” result which only requires one to multiply the generator set S a finite number C(R_0,d) of times before one sees the virtual nilpotency of the group.  However, the compactness argument does not give an explicit value to the quantities C(R_0,d), C'(R_0,d), C''(R_0,d), and the nature of Gromov’s proof (using, in particular, the deep Montgomery-Zippin-Yamabe theory on Hilbert’s fifth problem) does not easily allow such an explicit value to be extracted.

Another point is that the original formulation of Gromov’s theorem required the polynomial bound (1) at all sufficiently large scales R.  A later proof of this theorem by van den Dries and Wilkie relaxed this hypothesis to requiring (1) just for infinitely many scales R; the later proof by Kleiner (which I blogged about here) also has this relaxed hypothesis.

Our main result reduces the hypothesis (1) to a single large scale, and makes most of the qualitative dependencies in the theorem quantitative:

Theorem 1. If (1) holds for some R > \exp(\exp(C d^C)) for some sufficiently large absolute constant C, then G contains a finite index subgroup H which is nilpotent of step at most C^d.

The argument does in principle provide a bound on the index of H in G, but it is very poor (of Ackermann type).  If instead one is willing to relax “nilpotent” to “polycyclic“, the bounds on the index are somewhat better (of tower exponential type), though still far from ideal.

There is a related finitary analogue of Gromov’s theorem by Makarychev and Lee, which asserts that any finite group of uniformly polynomial growth has a subgroup with a large abelianisation.  The quantitative bounds in that result are quite strong, but on the other hand the hypothesis is also strong (it requires upper and lower bounds of the form (1) at all scales) and the conclusion is a bit weaker than virtual nilpotency.  The argument is based on a modification of Kleiner’s proof.

Our argument also proceeds by modifying Kleiner’s proof of Gromov’s theorem (a significant fraction of which was already quantitative), and carefully removing all of the steps which require one to take an asymptotic limit.  To ease this task, we look for the most elementary arguments available for each step of the proof (thus consciously avoiding powerful tools such as the Tits alternative).  A key technical issue is that because there is only a single scale R for which one has polynomial growth, one has to work at scales significantly less than R in order to have any chance of keeping control of the various groups and other objects being generated.

Below the fold, I discuss a stripped down version of Kleiner’s argument, and then how we convert it to a fully finitary argument.

– A modification of Kleiner’s argument –

Here is a variant of Kleiner’s argument, suitable for finitisation.  The starting point is to study the scalar Lipschitz harmonic functions on G, defined as those functions f: G \to {\Bbb R} which obey the harmonicity condition

f(g) = \frac{1}{|S|} \sum_{s \in S} f(gs) (2)

for all g \in G, as well as the Lipschitz condition

\sup_{g \in G, s \in S} |f(gs) - f(g)| < \infty. (3)

The space V of Lipschitz harmonic functions is a vector space which contains the constant functions.  If G is finite, a simple application of the maximum principle shows that the constant functions are the only harmonic functions.  However, for infinite G, non-constant harmonic functions exist:

Lemma 2. If G is infinite and generated by S, then there exists a non-constant Lipschitz harmonic function.

Proof (informal sketch only).  We give a proof which is more susceptible to finitisation than some of the more traditional proofs (e.g. the argument of Mok for the non-amenable case, and the argument of Lyons and Sullivan in the amenable case).   What we will do is find some Lipschitz almost-harmonic functions (in which (2) holds approximately rather than exactly) f which are uniformly non-constant near the identity; taking a limit of such functions we will obtain the claim.

There are two cases: the “non-amenable” case in which the Laplacian has a spectral gap (i.e. a  Poincaré inequality), and the amenable case in which no spectral gap exists.  In the amenable case, one has non-trivial low-frequency functions, and one can use these to generate the desired non-constant Lipschitz harmonic function.  For instance, if G = {\Bbb Z} with generators S = \{-1,+1\}, one can use the low-frequency function \sin (2\pi x / N ) to create the non-constant Lipschitz almost harmonic function N \sin(2\pi x/N), which in the limit N \to \infty yields the non-constant Lipschitz harmonic function 2 \pi x.

In the non-amenable case, one takes a long random walk on G using S as the steps (and using, say, an exponential distribution for the length of the walk).   By construction, the probability distribution of this walk will have a small Laplacian; but by the spectral gap, it will have a large derivative.  Manipulating this function a bit (using convolution and normalisation) one can again obtain a non-constant Lipschitz almost harmonic function. \Box

The next result is the heart of Kleiner’s argument, and is based on an earlier argument by Colding and Minicozzi:

Proposition 2. If G has polynomial growth, then V is finite dimensional.

Proof. See my previous blog post; the main tool is a certain local Poincaré inequality exploiting the polynomial growth hypothesis which asserts, roughly speaking, that harmonic functions on a large ball do not fluctuate much on smaller balls.  The argument gives an explicit upper bound D on the dimension of V in terms of the growth order d.  When one is assuming only polynomial growth at a single scale R, the argument yields that any D+1 Lipschitz harmonic (or almost harmonic) functions will have a “determinant” which is extremely small, where the determinant is taken with respect to a suitable quadratic form on V (defined using a scale slightly smaller than R). \Box

The group G acts on V by left translations, in a manner which preserves the Lipschitz norm, which becomes a genuine norm on the finite-dimensional space V after quotienting out the constants.  From Lemma 1 and Proposition 2, one thus obtains a non-trivial finite-dimensional isometric representation of G.  (The precise formulation of “non-trivial” is “infinite image”, which comes from the basic fact that non-constant harmonic functions must have infinite image, thanks to the maximum principle.)  Since G has polynomial growth, the image of G in the isometry group also has polynomial growth.

At this point one could apply the Tits alternative and conclude that the image of G is virtually solvable, but we wish to avoid the use of this alternative.  Instead, we use the basic observation (also used, for instance, in the proof of the Solovay-Kitaev theorem) that if two linear transformations are very close to the identity, then their commutator is even closer still to the identity.  If we take a few transformations in the image of G that are close to the identity and take a few commutators, we either end up at the identity, or we end up with a lot of transformations at widely differing distances from the identity.  The latter case contradicts the polynomial growth hypothesis, so we can conclude that the transformations near the identity form a solvable group.  Since the isometry group of a finite-dimensional space is compact, this implies that the image is virtually solvable.  Since the image is also infinite, we conclude that the image has a finite index subgroup with an infinite abelianisation, and thus G has a finite index subgroup with an infinite abelianisation.

An elementary splitting argument of Gromov then tells us that the kernel of that abelianisation has one order less growth (at least) than G itself.  Applying Gromov’s theorem as an induction hypothesis, this kernel is itself virtually nilpotent.  After passing to a finite index subgroup to get rid of the “virtually” adjective, we conclude that G contains a finite index subgroup whose kernel of the abelianisation is nilpotent; in particular, G is virtually solvable.

To conclude, one uses an elementary result of Milnor and Wolf that establishes Gromov’s theorem in the solvable case.  (Ultimately, things boil down to showing that the only linear transformations on the lattice {\Bbb Z}^d which exhibit polynomial growth are virtually unipotent; this in turn boils down to a classical result of Kronecker that the only algebraic integers whose Galois conjugates all lie on the unit circle are the roots of unity.)  This completes the proof sketch of Gromov’s theorem.

It turns out that all of the above steps can be finitised.  Instead of working with Lipschitz harmonic functions on infinite groups, one works instead with Lipschitz almost harmonic functions on very large groups.  One is then not working with a finite dimensional vector space V, but instead with a class of functions which is closely approximated by a finite-dimensional space.  Applying a Gram-Schmidt type procedure, we now get an approximate finite-dimensional representation of the group G (in which the homomorphism property contains small errors), but the elementary Solovay-Kitaev type argument can handle this sort of noise, and one soon finds that the image of G in this representation behaves as if it is virtually solvable; unpacking what this means, it implies that approximately Lipschitz harmonic functions on G are approximately constant in some iterated commutator of a subgroup of G.  (It is instructive to work this type of phenomenon out by hand for, say, the Heisenberg group.)  One can then quotient out this direction to reduce the order of growth.  The only remaining task is to finitise the Milnor-Wolf theory, but this is relatively straightforward (for instance, instead of Kronecker’s theorem, one uses lower bounds on Mahler measure, such as the bound due to Dobrowolski).