Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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

Authors: Alexander Lubotzky and Igor Pak
Journal: J. Amer. Math. Soc. 14 (2001), 347-363
MSC (2000): Primary 60B15; Secondary 05C25, 22D10, 60J10
Published electronically: October 18, 2000
MathSciNet review: 1815215
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

  • [An] S. Andreadakis, On the automorphisms of free groups and free nilpotent groups, Proc. London Math. Soc. (3) 15 (1965), 239-268. MR 32:5746
  • [Bb1] L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, in Proc $23^{rd}$ ACM STOC (1991), 164-174.
  • [Bb2] L. Babai, Randomization in group algorithms: Conceptual questions, in Groups and Computation II (L. Finkelstein, W.M. Kantor, eds.) DIMACS Workshops on Groups and Computation (1997). MR 98k:68092
  • [BP] L. Babai, I. Pak, Strong bias of group generators: an obstacle to the ``product replacement algorithm'', in Proc. $11^{\text{t}h}$ SODA (2000), 627-635. CMP 2000:12
  • [Bh] S. Bachmuth, Automorphisms of free metabelian groups, Trans. Amer. Math. Soc. 118 (1965), 93-104. MR 31:4831
  • [BMS] H. Bass, J. Milnor, J.-P. Serre, Solution of the congruence subgroup problem for $SL_{n}\,(n\ge 3)$and $Sp_{2n}\,(n\ge 2)$, Publ. Math. IHES 33 (1967), 59-137. MR 39:5574
  • [BCP] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system, in ``Computational algebra and number theory (London, 1993)", J. Symbolic Comput. 24 (1997), 235-265. MR 98f:68006
  • [Bu] M. Burger, Kazhdan constants for $SL(3,\mathbb{Z} )$, J. Reine Angew. Math. 413 (1991), 36-67. MR 92c:22013
  • [CLMNO] F. Celler, C.R. Leedham-Green, S. Murray, A. Niemeyer, and E.A. O'Brien, Generating random elements of a finite group, Comm. Alg. 23 (1995), 4931-4948. MR 96h:20115
  • [Ch] F.R.K. Chung, Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92), American Mathematical Society, Providence, RI, 1994. MR 97k:58183
  • [CG] F.R.K. Chung, R.L. Graham, Random walks on generating sets for finite groups, The Electronic J. of Comb. 4 No 2. (1997), #R7. MR 98c:60087
  • [DG] P. Diaconis, R. Graham, The graph of generating sets of an abelian group, Colloq. Math. 80 (1999), 31-38. MR 2000f:20124
  • [DS1] P. Diaconis, L. Saloff-Coste, Walks on generating sets of abelian groups, Prob. Th. Rel. Fields 105 (1996), 393-421. MR 98a:60093
  • [DS2] P. Diaconis, L. Saloff-Coste, Walks on generating sets of groups, Invent. Math. 134 (1998), 251-199. MR 2000e:60013
  • [Du1] M.J. Dunwoody, On T-systems of groups, J. Austral. Math. Soc. 3 (1963), 172-179. MR 27:3706
  • [Du2] M.J. Dunwoody, Nielsen Transformations, in Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (1970), 45-46. MR 41:5472
  • [Ge] S. M. Gersten, A presentation for the special automorphism group of a free group, J. Pure Appl. Algebra 33 (1984), 269-279. MR 86f:20041
  • [Gi] R. Gilman, Finite quotients of the automorphism group of a free group, Canad. J. Math. 29 (1977), 541-551. MR 55:8186
  • [Gr] K. W. Gruenberg, Relation modules of finite groups, CBMS Regional Conference Series in Mathematics, No. 25, American Mathematical Society, Providence, R.I., 1976. MR 56:15743
  • [H] P. Hall, The Edmonton notes on nilpotent groups, in The collected works of Philip Hall, Clarendon Press, Oxford, 1988. MR 90b:01108
  • [HRV] P. de la Harpe, A.G. Robertson, A. Valette, On the spectrum of the sum of generators for a finitely generated group, Israel J. Math. 81 (1993), 65-96. MR 94j:22007
  • [Ho] G. Hochschild, Introduction to affine algebraic groups, Holden-Day, San Francisco, 1971. MR 43:3268
  • [HM] R. Howe, C. Moore, Asymptotic properties of unitary representations, J. Funct. Anal. 32 (1979), 72-96. MR 80g:22017
  • [K] D. A. Kazhdan, On the connection of the dual space of a group with the structure of its closed subgroups (Russian), Funkcional. Anal. i Prilozhen. 1 (1967), 71-74.
  • [LG] C. Leedham-Green, personal communication.
  • [Lu1] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Birkhauser, Boston, 1994. MR 96g:22018
  • [Lu2] A. Lubotzky, Eigenvalues of the Laplacian, the first Betti number and the congruence subgroup problem, Ann. of Math. (2) 144 (1996), 441-452. MR 98h:22013
  • [MKS] W. Magnus, A. Karrass, D. Solitar, Combinatorial group theory. Presentations of groups in terms of generators and relations (Second edition), Dover, New York, 1976. MR 34:7617 (review of first edition)
  • [Mc] J. McCool, A faithful polynomial representation of $\text{Out}\,F_{3}$, Math. Proc. Cambridge Philos. Soc. 106 (1989), 207-213. MR 90j:20079
  • [Mo] S. Moses, On the congruence subgroup problem for tree lattices, in ``Lie groups and ergodic theory (Mumbai, 1996)", Tata Inst. Fund. Res., Bombay, 1998, pp. 143-149.
  • [P1] I. Pak, Generating random elements in solvable groups, preprint (1999).
  • [P2] I. Pak, On the graph of generating sets of a simple group, preprint (1999).
  • [P3] I. Pak, What do we know about the product replacement random walk?, to appear in Groups and Computations III.
  • [PB] I. Pak, S. Bratus, On sampling generating sets of finite groups and the product replacement algorithm, Proc. ISSAC'99, 1999, pp. 91-96.
  • [PZ] I. Pak, A. Zuk, in preparation, 2000.
  • [Sc] M. Schönert et al., GAP - Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, RWTH Aachen, Germany, 1995.
  • [Sh1] Y. Shalom, Explicit Kazhdan constants for representations of semisimple and arithmetic groups, Annales de L'Institut Fourier, to appear.
  • [Sh2] Y. Shalom, Bounded generation and Kazhdan's property (T), Publ. Math. IHES, to appear.
  • [Sh3] Y. Shalom, Invariant measures for algebraic actions, Zariski dense subgroups and Kazhdan's property (T), Trans. Amer. Math. Soc. 351 (1999), 3387-3412. MR 99m:22008
  • [W] S. P. Wang, On the Mautner phenomenon and groups with property (T), Amer. J. Math. 104 (1982), 1191-1210. MR 84g:22033
  • [Z] R. J. Zimmer, Ergodic theory and semisimple groups, in: Monographs in Mathematics, 81, Birkhauser, Boston, MA, 1984. MR 86j:22014

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 60B15, 05C25, 22D10, 60J10

Retrieve articles in all journals with MSC (2000): 60B15, 05C25, 22D10, 60J10

Additional Information

Alexander Lubotzky
Affiliation: Department of Mathematics, Hebrew University, Givat Ram, Jerusalem 91904, Israel

Igor Pak
Affiliation: Department of Mathematics, Yale University, New Haven, Connecticut 06520
Address at time of publication: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Keywords: Random walks on groups, Kazhdan's property (T), nilpotent groups
Received by editor(s): January 5, 2000
Received by editor(s) in revised form: August 23, 2000
Published electronically: October 18, 2000
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society