The product replacement algorithm and Kazhdan's property (T) |
| |
| Authors: | Alexander Lubotzky Igor Pak |
| |
| Affiliation: | Department of Mathematics, Hebrew University, Givat Ram, Jerusalem 91904, Israel ; Department of Mathematics, Yale University, New Haven, Connecticut 06520 |
| |
| Abstract: | The ``product replacement algorithm' is a commonly used heuristic to generate random group elements in a finite group  , by running a random walk on generating  -tuples of  . While experiments showed outstanding performance, the theoretical explanation remained mysterious. In this paper we propose a new approach to the study of the algorithm, by using Kazhdan's property (T) from representation theory of Lie groups. |
| |
| Keywords: | Random walks on groups Kazhdan's property (T) nilpotent groups |
|
| 点击此处可从《Journal of the American Mathematical Society》浏览原始摘要信息 |
|
点击此处可从《Journal of the American Mathematical Society》下载全文 |
