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

- S. Andreadakis,
*On the automorphisms of free groups and free nilpotent groups*, Proc. London Math. Soc. (3)**15**(1965), 239–268. MR**188307**, DOI https://doi.org/10.1112/plms/s3-15.1.239
[Bb1]Bb1 L. Babai, - 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]BP L. Babai, I. Pak, - S. Bachmuth,
*Automorphisms of free metabelian groups*, Trans. Amer. Math. Soc.**118**(1965), 93-104. MR**180597**, DOI https://doi.org/10.1090/S0002-9947-1965-0180597-3 - H. Bass, J. Milnor, and J.-P. Serre,
*Solution of the congruence subgroup problem for ${\rm SL}_{n}\,(n\geq 3)$ and ${\rm Sp}_{2n}\,(n\geq 2)$*, Inst. Hautes Études Sci. Publ. Math.**33**(1967), 59–137. MR**244257** - 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** - M. Burger,
*Kazhdan constants for ${\rm SL}(3,{\bf Z})$*, J. Reine Angew. Math.**413**(1991), 36–67. MR**1089795**, DOI https://doi.org/10.1515/crll.1991.413.36 - 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**, DOI https://doi.org/10.1080/00927879508825509 - 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** - 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** - Persi Diaconis and Ronald Graham,
*The graph of generating sets of an abelian group*, Colloq. Math.**80**(1999), no. 1, 31–38. MR**1684568**, DOI https://doi.org/10.4064/cm-80-1-31-38 - 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**, DOI https://doi.org/10.1007/BF01192214 - P. Diaconis and L. Saloff-Coste,
*Walks on generating sets of groups*, Invent. Math.**134**(1998), no. 2, 251–299. MR**1650316**, DOI https://doi.org/10.1007/s002220050265 - M. J. Dunwoody,
*On $T$-systems of groups*, J. Austral. Math. Soc.**3**(1963), 172–179. MR**0153745** - M. J. Dunwoody,
*Nielsen transformations*, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 45–46. MR**0260852** - 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**, DOI https://doi.org/10.1016/0022-4049%2884%2990062-8 - Robert Gilman,
*Finite quotients of the automorphism group of a free group*, Canadian J. Math.**29**(1977), no. 3, 541–551. MR**435226**, DOI https://doi.org/10.4153/CJM-1977-056-3 - 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** - 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** - 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**, DOI https://doi.org/10.1007/BF02761298 - G. Hochschild,
*Introduction to affine algebraic groups*, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1971. MR**0277535** - Roger E. Howe and Calvin C. Moore,
*Asymptotic properties of unitary representations*, J. Functional Analysis**32**(1979), no. 1, 72–96. MR**533220**, DOI https://doi.org/10.1016/0022-1236%2879%2990078-8
[K]K D. A. Kazhdan, - 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** - 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**, DOI https://doi.org/10.2307/2118597 - 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** - James McCool,
*A faithful polynomial representation of ${\rm Out}\,F_3$*, Math. Proc. Cambridge Philos. Soc.**106**(1989), no. 2, 207–213. MR**1002533**, DOI https://doi.org/10.1017/S0305004100078026
[Mo]Mo S. Moses, - 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**, DOI https://doi.org/10.1090/S0002-9947-99-02363-6 - S. P. Wang,
*On the Mautner phenomenon and groups with property $({\rm T})$*, Amer. J. Math.**104**(1982), no. 6, 1191–1210. MR**681733**, DOI https://doi.org/10.2307/2374057 - Robert J. Zimmer,
*Ergodic theory and semisimple groups*, Monographs in Mathematics, vol. 81, Birkhäuser Verlag, Basel, 1984. MR**776417**

*Local expansion of vertex-transitive graphs and random generation in finite groups*, in Proc $23^{rd}$ ACM STOC (1991), 164–174.

*Strong bias of group generators: an obstacle to the “product replacement algorithm”*, in Proc. $11^{\text {t}h}$ SODA (2000), 627–635.

*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]LG C. Leedham–Green, personal communication.

*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]P1 I. Pak,

*Generating random elements in solvable groups*, preprint (1999). [P2]P2 I. Pak,

*On the graph of generating sets of a simple group*, preprint (1999). [P3]P3 I. Pak,

*What do we know about the product replacement random walk?*, to appear in

*Groups and Computations III*. [PB]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]PZ I. Pak, A. Żuk,

*in preparation*, 2000. [Sc]Sc M. Schönert et al.,

*GAP – Groups, Algorithms, and Programming*, Lehrstuhl D für Mathematik, RWTH Aachen, Germany, 1995. [Sh1]Sh1 Y. Shalom,

*Explicit Kazhdan constants for representations of semisimple and arithmetic groups*, Annales de L’Institut Fourier, to appear. [Sh2]Sh2 Y. Shalom,

*Bounded generation and Kazhdan’s property (T)*, Publ. Math. IHES, to appear.

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

MR Author ID:
116480

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

MR Author ID:
293184

ORCID:
0000-0001-8579-7239

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