The product replacement algorithm and Kazhdan’s property (T)

Lubotzky, Alexander¹ ; Pak, Igor^2, 3

¹ Department of Mathematics, Hebrew University, Givat Ram, Jerusalem 91904, Israel
² Department of Mathematics, Yale University, New Haven, Connecticut 06520
³ Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Journal of the American Mathematical Society, Tome 14 (2001) no. 2, pp. 347-363

Résumé

The “product replacement algorithm” is a commonly used heuristic to generate random group elements in a finite group $G$, by running a random walk on generating $k$-tuples of $G$. 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.

Détail

DOI : 10.1090/S0894-0347-00-00356-8

Bibliographie

[1] Andreadakis, S. On the automorphisms of free groups and free nilpotent groups Proc. London Math. Soc. (3) 1965 239 268

[2] Babai, Lã¡Szlã³ Randomization in group algorithms: conceptual questions 1997 1 17

[3] Bachmuth, S. Automorphisms of free metabelian groups Trans. Amer. Math. Soc. 1965 93 104

[4] Bass, H., Milnor, J., Serre, J.-P. Solution of the congruence subgroup problem for 𝑆𝐿_{𝑛}(𝑛≥3) and 𝑆𝑝_{2𝑛}(𝑛≥2) Inst. Hautes Études Sci. Publ. Math. 1967 59 137

[5] Computational algebra and number theory 1997 233 506

[6] Burger, M. Kazhdan constants for 𝑆𝐿(3,𝑍) J. Reine Angew. Math. 1991 36 67

[7] Celler, Frank, Leedham-Green, Charles R., Murray, Scott H., Niemeyer, Alice C., O’Brien, E. A. Generating random elements of a finite group Comm. Algebra 1995 4931 4948

[8] Chung, Fan R. K. Spectral graph theory 1997

[9] Chung, F. R. K., Graham, R. L. Random walks on generating sets for finite groups Electron. J. Combin. 1997

[10] Diaconis, Persi, Graham, Ronald The graph of generating sets of an abelian group Colloq. Math. 1999 31 38

[11] Diaconis, P., Saloff-Coste, L. Walks on generating sets of abelian groups Probab. Theory Related Fields 1996 393 421

[12] Diaconis, P., Saloff-Coste, L. Walks on generating sets of groups Invent. Math. 1998 251 299

[13] Dunwoody, M. J. On 𝑇-systems of groups J. Austral. Math. Soc. 1963 172 179

[14] Dunwoody, M. J. Nielsen transformations 1970 45 46

[15] Gersten, S. M. A presentation for the special automorphism group of a free group J. Pure Appl. Algebra 1984 269 279

[16] Gilman, Robert Finite quotients of the automorphism group of a free group Canadian J. Math. 1977 541 551

[17] Gruenberg, Karl W. Relation modules of finite groups 1976

[18] Hall, Philip The collected works of Philip Hall 1988

[19] De La Harpe, Pierre, Robertson, A. Guyan, Valette, Alain On the spectrum of the sum of generators for a finitely generated group Israel J. Math. 1993 65 96

[20] Hochschild, G. Introduction to affine algebraic groups 1971

[21] Howe, Roger E., Moore, Calvin C. Asymptotic properties of unitary representations J. Functional Analysis 1979 72 96

[22] Lubotzky, Alexander Discrete groups, expanding graphs and invariant measures 1994

[23] Lubotzky, Alexander Eigenvalues of the Laplacian, the first Betti number and the congruence subgroup problem Ann. of Math. (2) 1996 441 452

[24] Magnus, Wilhelm, Karrass, Abraham, Solitar, Donald Combinatorial group theory: Presentations of groups in terms of generators and relations 1966

[25] Mccool, James A faithful polynomial representation of 𝑂𝑢𝑡𝐹₃ Math. Proc. Cambridge Philos. Soc. 1989 207 213

[26] Shalom, Yehuda Invariant measures for algebraic actions, Zariski dense subgroups and Kazhdan’s property (T) Trans. Amer. Math. Soc. 1999 3387 3412

[27] Wang, S. P. On the Mautner phenomenon and groups with property (𝑇) Amer. J. Math. 1982 1191 1210

[28] Zimmer, Robert J. Ergodic theory and semisimple groups 1984