This week there is a conference here at IPAM on expanders in pure and applied mathematics. I was an invited speaker, but I don’t actually work in expanders per se (though I am certainly interested in them). So I spoke instead about the recent simplified proof by Kleiner of the celebrated theorem of Gromov on groups of polynomial growth. (This proof does not directly mention expanders, but the argument nevertheless hinges on the absence of expansion in the Cayley graph of a group of polynomial growth, which is exhibited through the smoothness properties of harmonic functions on such graphs.)

— Gromov’s theorem —

Let G be an at most countable group generated by a finite set S of generators, which we can take to be symmetric (i.e. s^{-1} \in S whenever s \in S). Then we can form the Cayley graph \Gamma, whose vertices are the elements of G, and with g and gs connected by an edge for every g \in G and s \in S. This is a connected regular graph, with a transitive left-action of G. For any vertex x and R>0, one can define the ball B(x,R) in \Gamma to be the set of all vertices connected to x by a path of length at most R. We say that G has polynomial growth if we have the bound |B(x,R)| = O( R^{O(1)} ) as R \to \infty; one can easily show that the left-hand side is independent of x, and that the polynomial growth property does not depend on the choice of generating set S.

Examples of finitely generated groups of polynomial growth include

  1. Finite groups;
  2. Abelian groups (e.g. {\Bbb Z}^d);
  3. Nilpotent groups (a generalisation of 2);
  4. Virtually nilpotent groups, i.e. it has a nilpotent subgroup of finite index (a combination of 1 and 3).

In 1981, Gromov proved that these are the only examples:

Theorem 1. (Gromov’s theorem). Let G be a finitely generated group of polynomial growth. Then G is virtually nilpotent.

Gromov’s original argument used a number of deep tools, including the Montgomery-Zippin-Yamabe structure theory of locally compact groups (related to Hilbert’s fifth problem), as well as various earlier partial results on the problem. Several proofs have subsequently been found. Recently, Kleiner obtained a proof which was significantly more elementary, although it still relies on some non-trivial partial versions of Gromov’s theorem. Specifically, it needs the following result proven by Wolf and by Milnor:

Theorem 2. (Gromov’s theorem for virtually solvable groups) Let G be a finitely generated group of polynomial growth which is virtually solvable (i.e. it has a solvable subgroup of finite index). Then it is virtually nilpotent.

The argument also needs a related result:

Theorem 3. Let G be a finitely generated amenable group which is linear, thus G \subset GL_n({\Bbb C}) for some n. Then G is virtually solvable.

This theorem is an immediate consequence of the Tits alternative, but also has a short elementary proof, due to Shalom. An easy application of the pigeonhole principle to the sequence |B(x,R)| for R = 1,2,\ldots shows that every group of polynomial growth is amenable. Thus Theorem 2 and Theorem 3 already give Gromov’s theorem for linear groups.

Other than Theorem 2 and Theorem 3, Kleiner’s proof of Theorem 1 is essentially self contained. The argument also extends to groups of weakly polynomial growth, which means that |B(x,R)| = O( R^{O(1)} ) for some sequence of radii R going to infinity. (This extension of Gromov’s theorem was first established by van der Dries and Wilkie.) But for simplicity we only discuss the polynomial growth case here.

— Reductions —

The first few reductions follow the lines of Gromov’s original argument. The first observation is that it suffices to exhibit an infinite abelianisation of G, or more specifically to prove:

Proposition 1. (Existence of infinite abelian representation) Let G be an infinite finitely generated group of polynomial growth. Then there exists a subgroup G’ of finite index whose abelianisation G'/[G',G'] is infinite.

Indeed, if G’ has infinite abelianisation, then one can find a non-trivial homomorphism \alpha: G' \to {\Bbb Z}. The kernel K of this homomorphism is a normal subgroup of G’. Using the polynomial growth hypothesis, one can show that K is also finitely generated; furthermore, it is polynomial growth of one lower order (i.e. the exponent in the O(R^{O(1)}) bound for |B(x,R)| is reduced by 1). An induction hypothesis then gives that K is virtually nilpotent, which easily implies that G’ (and thus G) is virtually solvable. Gromov’s theorem for infinite G then follows from Theorem 2. (The theorem is of course trivial for finite G.)

[Note: the above argument not only shows that G is virtually solvable, but moreover that G’ is the semidirect product K \rtimes_\phi {\Bbb Z} of a virtually nilpotent group K and the integers, which acts on K by some automorphism \phi. So it seems to me that one does not actually need the full strength of Theorem 2 here, but only the special case of semidirect products of the above form, which might be doable “by hand”, for instance by inducting on the step of K. This might make Kleiner’s proof even more elementary, though I have not fully checked the details.]

To show Proposition 1, it suffices to show

Proposition 2. (Existence of infinite linear representation) Let G be an infinite finitely generated group of polynomial growth. Then there exists a finite-dimensional representation \rho: G \to GL_n({\Bbb C}) whose image \rho(G) is infinite.

Indeed, the image \rho(G) \subset GL_n({\Bbb C}) is also finitely generated with polynomial growth, and hence by Theorem 3 and Theorem 2 is virtually nilpotent (actually, for this argument we don’t need Theorem 2 and would be content with virtual solvability). If the abelianisation of \rho(G) is finite, one can easily pass to a subgroup G’ of finite index and reduce the (virtual) step of \rho(G') by 1, so one can quickly reduce to the case when the abelianisation is infinite, at which point Proposition 1 follows.

So all we need to do now is to prove Proposition 2.

— Harmonic functions on Cayley graphs —

Kleiner’s approach to Proposition 2 relies on the notion of a (possibly vector-valued) harmonic function on the Cayley graph \Gamma. This is a function f: G \to H taking values in a Hilbert space H such that f(g) = \frac{1}{|S|} \sum_{s \in S} f(gs) for all g \in G. Formally, harmonic functions are local minimisers of the energy functional

E(f) := \frac{1}{2} \sum_{g \in G} |\nabla f(g)|^2

where

|\nabla f(g)|^2 := \frac{1}{|S|} \sum_{s \in S} \| f(gs) - f(g)\|_H^2

though of course with the caveat that E(f) is often infinite. (This property is also equivalent to a certain graph Laplacian of f vanishing.)

Of course, every constant function is harmonic. But there are other harmonic functions too: for instance, on {\Bbb Z}^d, any linear function is harmonic (regardless of the actual choice of generators). Kleiner’s proof of Proposition 2 follows by combining the following two results:

Proposition 3. Let G be an infinite finitely generated group of polynomial growth. Then there exists an (affine-) isometric (left-)action of G on a Hilbert space H with no fixed points, and a harmonic map f: G \to H which is G-equivariant (thus f(gh) = g f(h) for all g, h \in G). (Note that by equivariance and the absence of fixed points, this harmonic map is necessarily non-constant.)

Proposition 4. Let G be an finitely generated group of polynomial growth, and let d \geq 0. Then the linear space of harmonic functions u: G \to {\Bbb R} which grow of order at most d (thus u(g) = O(R^d) on B(\hbox{id},R)) is finite-dimensional.

Indeed, if f is the vector-valued map given by Proposition 3, then from the G-equivariance it is easy to see that f is of polynomial growth (indeed it is Lipschitz). But the linear projections \{ f \cdot v: v \in H \} of f to scalar-valued harmonic maps lie in a finite-dimensional space, by Proposition 4. This implies that the range f(G) of f lies in a finite-dimensional space V. On the other hand, the obvious action of G on V has no fixed points (being a restriction of the action of G on H), and so the image of G in GL_n(V) must be infinite, and Proposition 2 follows.

It remains to prove Proposition 3 and Proposition 4. Proposition 3 follows by some more general results of Korevaar-Schoen and Mok, though Kleiner provided an elementary proof which we sketch below. Proposition 4 was initially proven by Colding and Minicozzi (for finitely presented groups, at least) using Gromov’s theorem; Kleiner’s key new observation was that Proposition 4 can be proven directly by an elementary argument based on a Poincaré inequalities.

— A non-constant equivariant harmonic function —

We now sketch the proof of Proposition 2. The first step is to just get the action on a Hilbert space with no fixed points:

Lemma 1. Let G be a countably infinite amenable group. Then there exists an action of G on a Hilbert space H with no fixed points.

This is essentially the well-known assertion that countably infinite amenable groups do not obey Property (T), but we can give an explicit proof as follows. Using amenability, one can construct a nested Følner sequence F_1 \subset F_2 \subset \ldots \subset \bigcup_n F_n = G of finite sets with the property that |(F_{n-1} \cdot F_n) \Delta F_n| \leq 2^{-n} |F_n| (say). (In the case of groups of polynomial growth, one can take F_n = B(\hbox{id}, R_n) for some rapidly growing, randomly chosen sequence of radii R_n.) We then look at H := l^2({\Bbb N}; l^2(G)), the Hilbert space of sequences f_1, f_2, \ldots \in l^2(G) with \sum_n \|f_n\|_{l^2(G)}^2 < \infty. This space has the obvious unitary action of G, defined as g: (f_n(\cdot))_{n \in {\Bbb N}} \to (f_n(g \cdot))_{n \in {\Bbb N}}. This action has a fixed point of 0, but we can delete this fixed point by considering instead the affine-isometric action f \mapsto gf + gh - h, where h is the sequence h = (\frac{1}{|F_n|^{1/2}} 1_{F_n})_{n \in {\Bbb N}}. This sequence h does not directly lie in H, but observe that gh-h lies in H for every g. One can then easily show that this action obeys the conclusions of Lemma 1.

Another way of asserting that an action of G on H has no fixed point is to say that the energy functional E: H \to {\Bbb R}^+ defined by E(v) := \frac{1}{2} \sum_{s \in S} \| sv - v \|_H^2 is always strictly positive. So Lemma 1 concludes that there exists an action of G on a Hilbert space on which E is strictly positive. It is possible to then conclude that there exists another action of G on another Hilbert space on which the energy E is not only strictly positive, but actually attains its minimum at some vector v. This observation follows from more general results of Fisher and Margulis, but one can also argue directly as follows. For every 0 < \lambda < 1 and A > 0 , there must exist a vector v which almost minimises E in the sense that E(v') \geq \lambda E(v) whenever \| v-v' \| \leq A E(v)^{1/2}, since otherwise one could iterate and sum a Neumann-type series to obtain a fixed point of v. But then by shifting v to the origin, and taking an ultrafilter limit (!) as \lambda \to 1 and A \to \infty, we obtain the claim.

Some elementary calculus of variations then shows that if v is the energy minimiser, the map f: g \mapsto gv is a harmonic G-equivariant function from G to H, and Proposition 2 follows.

— Poincaré’s inequality, and the complexity of harmonic functions —

Now we turn to the proof of Proposition 4, which is the main new ingredient in Kleiner’s argument. To simplify the exposition, let us cheat and suppose that the polynomial growth condition |B(x,R)| = O( R^{O(1)} ) is replaced by the slightly stronger doubling condition |B(x,2R)| = O( |B(x,R)| ). (In practice, one can use pigeonholing arguments to show that polynomial growth implies doubling on large ranges of scales, which turns out to suffice.) Similarly, to simplify the argument, let us pretend that the harmonic functions u: G \to {\Bbb R} are not only of polynomial growth, but also obey a doubling condition \sum_{x \in B(\hbox{id},2R)} u(x)^2 = O( \sum_{x \in B(\hbox{id},R)} u(x)^2 ).

The key point is to exploit the fact that harmonic functions are fairly smooth. For instance, a simple “integration by parts” argument shows that if u is harmonic, then

\sum_{x \in B(\hbox{id},R)} |\nabla u(x)|^2\ dx = O( R^{-2} \sum_{x \in B(\hbox{id},2R)} |u(x)|^2\ dx ) (1);

this estimate can be established by the usual trick of replacing the summation over B(\hbox{id},R) with a smoother cutoff function and then expanding out the gradient square.

To use this gradient control, Kleiner established the Poincaré inequality

\sum_{x \in B(x_0,R)} \sum_{y \in B(x_0,R)} |u(x)-u(y)|^2

= O( R^2 |B( x_0, R)| \sum_{x \in B(x_0,3R)} |\nabla u(x)|^2 ) (2)

assuming the doubling condition on balls. This inequality (a variant of a similar inequality of Coulhon and Saloff-Coste) is actually quite easy to prove. Observe that if x, y \in B(x_0,R), then x=yg for some g \in B(0,2R). Thus it suffices to show that

\sum_{x \in B(x_0,R)} |u(x)-u(xg)|^2 = O( R^2 \sum_{x \in B(x_0,3R)} |\nabla u(x)|^2 )

for each such g. But by expanding g as a product of at most 2R generators, splitting u(x)-u(xg) as a telescoping series, and using Cauchy-Schwarz, the result follows easily.

Combining (1) and (2), one sees that a harmonic function which is controlled on a large ball B(0,R), becomes nearly constant on small balls B(x,\varepsilon R) (morally speaking, we have |u(x)-u(y)| \ll \varepsilon |u(x)| “on the average” on such small balls). In particular, given any 0 < \varepsilon < 1, one can now obtain an inequality of the form

\sum_{x \in B(\hbox{id},R)} |u(x)|^2 \leq

O( \frac{1}{|B(\hbox{id},\varepsilon R)|} \sum_j |\sum_{x \in B_j} u(x)|^2 + \varepsilon^2 \sum_{x \in B(\hbox{id},16 R)} |u(x)|^2)

where B_j ranges over a cover of B(\hbox{id},R) by balls B_j of radius \varepsilon R (the number of such balls can be chosen to be polynomially bounded in 1/\varepsilon, by the doubling condition). As a consequence, we see that if a harmonic function u obeys a doubling condition, and has zero average on each ball B_j, then it vanishes identically. Morally speaking, this shows that the space of functions that obeys the doubling condition has finite dimension (bounded by the number of such balls), yielding Proposition 4 in the doubling case. It requires a small amount of combinatorial trickery to obtain this conclusion in the case when u and the balls B(\hbox{id},R) exhibit polynomial growth rather than doubling, but the general idea is still the same.

[Update, Feb 17: some discrepancies in the order of group multiplication (e.g. left actions vs. right actions) fixed (I think…).]