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 Free Access

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**0188307**, https://doi.org/10.1112/plms/s3-15.1.239**[Bb1]**L. Babai,*Local expansion of vertex-transitive graphs and random generation in finite groups*, in Proc ACM STOC (1991), 164-174.**[Bb2]**László Babai,*Randomization in group algorithms: conceptual questions*, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 1–17. MR**1444127****[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**0180597**, https://doi.org/10.1090/S0002-9947-1965-0180597-3**[BMS]**H. Bass, J. Milnor, and J.-P. Serre,*Solution of the congruence subgroup problem for 𝑆𝐿_{𝑛}(𝑛≥3) and 𝑆𝑝_{2𝑛}(𝑛≥2)*, Inst. Hautes Études Sci. Publ. Math.**33**(1967), 59–137. MR**0244257****[BCP]**John Cannon and Derek Holt (eds.),*Computational algebra and number theory*, Elsevier Ltd, Oxford, 1997. J. Symbolic Comput. 24 (1997), no. 3-4. MR**1484477****[Bu]**M. Burger,*Kazhdan constants for 𝑆𝐿(3,𝑍)*, J. Reine Angew. Math.**413**(1991), 36–67. MR**1089795**, https://doi.org/10.1515/crll.1991.413.36**[CLMNO]**Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E. A. O’Brien,*Generating random elements of a finite group*, Comm. Algebra**23**(1995), no. 13, 4931–4948. MR**1356111**, https://doi.org/10.1080/00927879508825509**[Ch]**Fan R. K. Chung,*Spectral graph theory*, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. MR**1421568****[CG]**F. R. K. Chung and R. L. Graham,*Random walks on generating sets for finite groups*, Electron. J. Combin.**4**(1997), no. 2, Research Paper 7, approx. 14. The Wilf Festschrift (Philadelphia, PA, 1996). MR**1444154****[DG]**Persi Diaconis and Ronald Graham,*The graph of generating sets of an abelian group*, Colloq. Math.**80**(1999), no. 1, 31–38. MR**1684568****[DS1]**P. Diaconis and L. Saloff-Coste,*Walks on generating sets of abelian groups*, Probab. Theory Related Fields**105**(1996), no. 3, 393–421. MR**1425868**, https://doi.org/10.1007/BF01192214**[DS2]**P. Diaconis and L. Saloff-Coste,*Walks on generating sets of groups*, Invent. Math.**134**(1998), no. 2, 251–299. MR**1650316**, https://doi.org/10.1007/s002220050265**[Du1]**M. J. Dunwoody,*On 𝑇-systems of groups*, J. Austral. Math. Soc.**3**(1963), 172–179. MR**0153745****[Du2]**M. J. Dunwoody,*Nielsen transformations*, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 45–46. MR**0260852****[Ge]**S. M. Gersten,*A presentation for the special automorphism group of a free group*, J. Pure Appl. Algebra**33**(1984), no. 3, 269–279. MR**761633**, https://doi.org/10.1016/0022-4049(84)90062-8**[Gi]**Robert Gilman,*Finite quotients of the automorphism group of a free group*, Canad. J. Math.**29**(1977), no. 3, 541–551. MR**0435226**, https://doi.org/10.4153/CJM-1977-056-3**[Gr]**Karl W. Gruenberg,*Relation modules of finite groups*, American Mathematical Society, Providence, R.I., 1976. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 25. MR**0457538****[H]**Philip Hall,*The collected works of Philip Hall*, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1988. Compiled and with a preface by K. W. Gruenberg and J. E. Roseblade; With an obituary by Roseblade. MR**986732****[HRV]**Pierre de la Harpe, A. Guyan Robertson, and Alain Valette,*On the spectrum of the sum of generators for a finitely generated group*, Israel J. Math.**81**(1993), no. 1-2, 65–96. MR**1231179**, https://doi.org/10.1007/BF02761298**[Ho]**G. Hochschild,*Introduction to affine algebraic groups*, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1971. MR**0277535****[HM]**Roger E. Howe and Calvin C. Moore,*Asymptotic properties of unitary representations*, J. Funct. Anal.**32**(1979), no. 1, 72–96. MR**533220**, https://doi.org/10.1016/0022-1236(79)90078-8**[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]**Alexander Lubotzky,*Discrete groups, expanding graphs and invariant measures*, Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel, 1994. With an appendix by Jonathan D. Rogawski. MR**1308046****[Lu2]**Alexander Lubotzky,*Eigenvalues of the Laplacian, the first Betti number and the congruence subgroup problem*, Ann. of Math. (2)**144**(1996), no. 2, 441–452. MR**1418904**, https://doi.org/10.2307/2118597**[MKS]**Wilhelm Magnus, Abraham Karrass, and Donald Solitar,*Combinatorial group theory: Presentations of groups in terms of generators and relations*, Interscience Publishers [John Wiley & Sons, Inc.], New York-London-Sydney, 1966. MR**0207802****[Mc]**James McCool,*A faithful polynomial representation of 𝑂𝑢𝑡𝐹₃*, Math. Proc. Cambridge Philos. Soc.**106**(1989), no. 2, 207–213. MR**1002533**, https://doi.org/10.1017/S0305004100078026**[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]**Yehuda Shalom,*Invariant measures for algebraic actions, Zariski dense subgroups and Kazhdan’s property (T)*, Trans. Amer. Math. Soc.**351**(1999), no. 8, 3387–3412. MR**1615966**, https://doi.org/10.1090/S0002-9947-99-02363-6**[W]**S. P. Wang,*On the Mautner phenomenon and groups with property (𝑇)*, Amer. J. Math.**104**(1982), no. 6, 1191–1210. MR**681733**, https://doi.org/10.2307/2374057**[Z]**Robert J. Zimmer,*Ergodic theory and semisimple groups*, Monographs in Mathematics, vol. 81, Birkhäuser Verlag, Basel, 1984. MR**776417**

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