The product replacement algorithm and Kazhdan's property (T) (Q2701703)

An important problem in ``computational group theory'' is to generate (nearly) uniformly distributed random elements in a finite group \(G\). Starting from a given set of generators, repeating certain algorithms, find group structures with efficient mixing time. The ``product replacement algorithm'' by Leedham-Green and Soicher, Celler et al. is a practically prominent algorithm. However, its theoretical study is not so satisfactory. In the present paper, it is proved that \(\Aut(F_k)\) has ``Kazhdan's property (T)'', where \(F_k\) is the free group with \(k\) generators. Then the mixing time of the lazy random walk on a connected component of \(\Gamma_k(G)\) is of order \(\log|G|\), where \(\Gamma_k(G)\) is the set of generating \(k\)-tuples of the finite group \(G\). (See Theorem 1). For ``Kazhdan's property(T)'', see Definition 2.3 and Section 4.