Characters and random walks on finite classical groups (Q1362167): Difference between revisions

The upper-bound lemma of Diaconis and Shashahani yields that upper bounds for the order of convergence of conjugation-invariant random walks on a finite group \(G\) can be obtained from upper bounds of the character ratios \(|\chi (x)|/ \chi(1)\) where \(\chi\) is a character of \(G\), and where \(x\in G\) belongs to a certain conjugation-invariant subset of \(G\). In this way, the convergence problem for some basic random walks was settled for the symmetric groups \(S_n\) by Diaconis and Shashahani, and for \(SL_n (F_q)\) by Hildebrand. The purpose of this paper is to derive upper bounds of the type \(|\chi (x)|/ \chi(1) \leq\chi (1)^{-\gamma/n}\) for characters \(\chi\) of a large class of ``classical'' augmented finite groups \(G\) which in particular includes the classical groups over \(GF(q)\). In this estimation, \(n\) is the rank of \(G\), and \(\gamma\) is a small positive constant depending on \(q\) and datas concerning the conjugacy class of \(x\). The proof of this result uses a heavy amount of algebra and is based on an induction argument. Using this result and estimations for the number of conjugacy classes of \(G\), the author finally obtains that roughly \(O(n)\) steps are needed to achieve near-uniformity for certain random walks.