This post is less about mathematics in TCS as it is about mathematics around TCS–specifically spectral graph theory and the structure of finite groups. Earlier this year at an IPAM conference on expander graphs, Terry Tao presented Bruce Kleiner’s new proof of Gromov’s theorem. After the talk, Luca Trevisan asked whether there exists an analog of certain steps in the proof for finite groups. Recently, Yury Makarychev and I gave a partial answer to Luca’s question in our paper Eigenvalue multiplicity and volume growth.
Gromov’s theorem
Let 
be an infinite, finitely-generated group with a finite, symmetric generating set 
. One defines the Cayley graph 
as an undirected 
-regular graph with vertex set , and which has an edge 
whenever 
for some 
.
We let 
denote the set of all elements in that can be written as a product of at most 
generators ( is a ball radius about the identity, in the word metric). is said to have polynomial growth if there exists a number 
such that
as 
. Polynomial growth is a property of the group, and does not depend on the choice of finite generating set 
(because one can express any two fixed generating sets in terms of each other with words of length 
).
It is straightforward, for instance, that every finitely generated abelian group has polynomial growth, since 
, where 
. Wolf proved a generalization of this: In fact, it holds for every nilpotent group. On the other hand, the free group on two generators does not have polynomial growth, since 
.
Notice also that every finite group has polynomial growth trivially. This fact extends a bit: If is an arbitrary group and 
is a subgroup of index , then polynomial growth for implies polynomial growth for . Combining this with the result of Wolf, we see that: A group has polynomial growth if it has a nilpotent subgroup of finite index. In a stunning work, Gromov proved the conjecture of Milnor that this sufficient condition is also necessary: Every finitely generated group of polynomial growth has a nilpotent subgroup of finite index.
Gromov’s proof
Imagine starting with the integer lattice 
, and slowly zooming out so that the gaps in the grid become smaller and smaller. As you move far enough away, the grid seems to morph into the continuum 
. Gromov defines this process abstractly, and shows that every group of polynomial growth “converges” to a finite-dimensional limit object on which the group acts by isometries (just as acts on by translation). Finally, the Gleason-Montgomery-Zippin-Yamabe structure theory of locally compact groups is used to classify the limit object. The jump from geometry (polynomial growth of balls) to algebra is encapsulated in the following result.
Theorem 1: If is a finitely generated infinite group of polynomial growth, then either
1. There exists a sequence of finite-dimensional linear representations 
with 
, or
2. There exists a single finite-dimensional linear representation 
, with 
infinite.
Here, 
is the general linear group. (Kleiner’s proof, which I’ll discuss momentarily, shows that actually (2) always holds.)
From Theorem 1, and work of Jordan and Tits, Gromov is able to conclude the following.
Theorem 2: Let be a finitely generated infinite group of polynomial growth. Then has a finite index subgroup which admits a homomorphism onto 
.
From this fact, and a theorem of Milnor on solvable groups, an induction on the degree of growth finishes the argument (see Tits’ appendix in Gromov’s paper for a 2-page version of this argument).
What about finite groups?
Luca’s question concerned a (quantitative) version of Theorem 1 for finite groups. In this case, it’s not even clear how one defines “polynomial growth.” A possible definition is that there exists a generating set such that in , one has 
for some numbers 
. Unfortunately, this property seems quite unwieldy in the finite case. We make a stronger assumption, using the doubling constant
.
Observe that in the infinite case, 
implies polynomial growth. It turns out (though it requires Gromov’s theorem to prove!) that if an infinite Cayley graph has polynomial growth, then it also has , in fact it must satisfy 
for some 
. It is unclear whether a similar phenomenon holds in the finite case.
We prove the following quantitative analogs of Theorems 1 and 2 above, for finite groups.
Theorem 1 (finite): Let be a finite group with symmetric generating set . Then there exist constants 
and 
, depending only on the doubling constant 
, such that has a linear representation 
with 
.
Theorem 2 (finite): Let be a finite group with symmetric generating set . Then there exist constants 
and 
, depending only on the doubling constant , such that has a normal subgroup having index at most , and admits a homomorphism onto the cyclic group 
, where 
.
In fact, if 
, then one can take 
and 
in the first theorem, and 
and 
in the second.
Eigenvalue multiplicity and the Laplacian
It seems hopeless to use Gromov’s approach for finite groups; indeed, quite literally, zooming out from a finite group converges to a single point. Kleiner’s remarkable new proof is discussed in detail in Terry Tao’s blog entry. He completely avoids Gromov’s limiting process, and the difficult classification of the resulting limit objects. Instead, his proof is based on estimating the dimension of the space of harmonic functions of fixed polynomial growth on the Cayley graph of . Kleiner’s approach is inspired by similar work of Colding and Minicozzi in the setting of non-negatively curved manifolds.
Define the discrete Laplacian on functions 
by
A harmonic function 
on is one for which 
. It is straightforward to verify that every harmonic function on a connected, finite graph is constant, so again we seem stuck for finite groups.
Fortunately, though, the Laplacian is very nice on finite graphs. In particular, it is a self-adjoint operator on the 
-dimensional space of functions 
, with eigenvalues 
. The second eigenspace of 
is the subspace 
given by 
, and the (geometric) multiplicity of 
is defined to be 
. In some sense, 
contains the most “harmonic-like” functions on which are orthogonal to the constant functions. The basis of our strategy is the following theorem, which is proved by “scaling down” the approach of Colding-Minicozzi and Kleiner. In order to prove that these functions are “harmonic enough,” we need precise bounds on in terms of , which we obtain in the paper. This yields the following theorem.
Theorem: For finite, the multiplicity of the 2nd eigenvalue of the Laplacian on is at most 
.
(In fact, we prove more general bounds on the multiplicity of higher eigenvalues, and more general graphs than Cayley graphs.)
To pass from this to Theorem 1 (finite) above, we use the fact that acts on 
via the action 
. It is easy to see that this action commutes with the Laplacian, i.e. 
, so that in fact acts by linear transformations on the second eigenspace . Thus in order to finish the proof of Theorem 1 (finite), we need only show that is large.
It turns out that if is too small, then we can pass to a small quotient group, and every second eigenfunction pushes down to an eigenfunction on the quotient. This allows us to bound on the quotient group in terms of on . But on a small, connected graph cannot be too close to zero by the discrete Cheeger inequality. In this way, we arrive at a contradiction if the image of the action is too small. Theorem 2 (finite) is then a simple corollary of Theorem 1 (finite), using a theorem of Jordan on finite linear groups.
Finally, note that the ideal algebraic conclusion of such a study is a statement of the form: There exists a normal subgroup 
of index , and such that is an -step nilpotent group, where the notation hides a constant that depends only on the growth data of . It is not clear that such a strong property can hold under only an assumption on for some fixed generating set . One might need to make assumptions on every generating set of , or even geometric assumptions on families of subgroups in . Defining a simple condition on and its generators that can achieve the full algebraic conclusion is an intriguing open problem.
