MODERATE GROWTH AND RANDOM-WALK ON FINITE-GROUPS

We study the rate of convergence of symmetric random walks on finite groups to the uniform distribution. A notion of moderate growth is introduced that combines with eigenvalue techniques to give sharp results. Roughly, for finite groups of moderate growth, a random walk supported on a set of generators such that the diameter of the group is gamma requires order gamma2 steps to get close to the uniform distribution. This result holds for nilpotent groups with constants depending only on the number of generators and the class. Using Gromov's theorem we show that groups with polynomial growth have moderate growth.