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

DOI:
https://doi.org/10.1090/S0894-0347-00-00356-8

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 , 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.

**[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 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. 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**and*, 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*, 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*, 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*,*, Birkhauser, Boston, MA, 1984. MR**81****86j:22014**

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

Email:
alexlub@math.huji.ac.il

**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

DOI:
https://doi.org/10.1090/S0894-0347-00-00356-8

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