Moderate growth and random walk on finite groups (Q1326533): Difference between revisions

Let \(G\) be a finite group with a symmetric generating set \(E \subset G\) containing the identity. Let \(q\) be the probability measure on \(G\) which is uniformly distributed on \(E\). The authors study the rate of convergence of the distributions \(q^{(n)}\) \((n \geq 1)\) of the associated symmetric random walk to the uniform distribution \(u\) of \(G\) with respect to the total variation norm. This problem is interesting in particular for families of finite groups with a similar structure where the sizes \(| G |\) tend to \(\infty\), and where \(E\) or at least the size of \(E\) does not change. The authors define the volume growth \(V(n):=| E^ n |\) and the diameter \(\gamma:=\min \{n:V(n)=| G |\}\) of \(G\) with respect to \(E\). Then \(G\) is called \((A,d)\)-moderate growing with respect to \(E\), if \[ V(n)/V(\gamma) \geq A^{-1} \cdot (n/ \gamma)^ d \quad \text{ for } 1 \leq n \leq \gamma. \] The main result of this paper states that \((A,d)\)- moderate growth implies that for all \(c>0\) \[ \| q^{(n)}-u \| \leq B \cdot e^{-c} \quad \text{for } n=(1+c) | E | \gamma^ 2,\;B=A^{1/2} 2^{d(d+3)/4} \] and \[ \| q^{(n)}-u \| \geq e^{-c}/2 \quad \text{ for } n=c \gamma^ 2/(2^{4d+2} A^ 2). \] Therefore, for finite groups with moderate growth one needs roughly \(\gamma^ 2\) steps to get close to the uniform distribution. Examples of families of groups with moderate growth are given by nilpotent groups (with fixed degree of nilpotency), and, in particular, by finite Heisenberg groups and \(p\)- groups. At the end of this paper, a version of Gromov's theorem is used to show that \((A,d)\)-polynomial growth of \(G\) (i.e. \(V(n) \leq An^ d\) for \(n \in \mathbb{N})\) yields that \(G\) has \((\tilde A, \tilde d)\)-moderate growth where \(\tilde A, \tilde d\) depend on \(A,d\) only.