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

HTML articles powered by AMS MathViewer

- by Alexander Lubotzky and Igor Pak
- J. Amer. Math. Soc.
**14**(2001), 347-363 - DOI: https://doi.org/10.1090/S0894-0347-00-00356-8
- Published electronically: October 18, 2000
- PDF | Request permission

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

- S. Andreadakis,
*On the automorphisms of free groups and free nilpotent groups*, Proc. London Math. Soc. (3)**15**(1965), 239–268. MR**188307**, DOI 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**, DOI 10.1090/dimacs/028/01
[BP]BP L. Babai, I. Pak, - S. Bachmuth,
*Automorphisms of free metabelian groups*, Trans. Amer. Math. Soc.**118**(1965), 93–104. MR**180597**, DOI 10.1090/S0002-9947-1965-0180597-3 - H. Bass, J. Milnor, and J.-P. Serre,
*Solution of the congruence subgroup problem for $\textrm {SL}_{n}\,(n\geq 3)$ and $\textrm {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 $\textrm {SL}(3,\textbf {Z})$*, J. Reine Angew. Math.**413**(1991), 36–67. MR**1089795**, DOI 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 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**, DOI 10.37236/1322 - 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 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 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 10.1007/s002220050265 - M. J. Dunwoody,
*On $T$-systems of groups*, J. Austral. Math. Soc.**3**(1963), 172–179. MR**0153745**, DOI 10.1017/S1446788700027919 - 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 10.1016/0022-4049(84)90062-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 10.4153/CJM-1977-056-3 - Karl W. Gruenberg,
*Relation modules of finite groups*, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 25, American Mathematical Society, Providence, R.I., 1976. MR**0457538**, DOI 10.1090/cbms/025 - 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 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 10.1016/0022-1236(79)90078-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**, DOI 10.1007/978-3-0346-0332-4 - 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 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], New York-London-Sydney, 1966. MR**0207802** - James McCool,
*A faithful polynomial representation of $\textrm {Out}\,F_3$*, Math. Proc. Cambridge Philos. Soc.**106**(1989), no. 2, 207–213. MR**1002533**, DOI 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 10.1090/S0002-9947-99-02363-6 - S. P. Wang,
*On the Mautner phenomenon and groups with property $(\textrm {T})$*, Amer. J. Math.**104**(1982), no. 6, 1191–1210. MR**681733**, DOI 10.2307/2374057 - Robert J. Zimmer,
*Ergodic theory and semisimple groups*, Monographs in Mathematics, vol. 81, Birkhäuser Verlag, Basel, 1984. MR**776417**, DOI 10.1007/978-1-4684-9488-4

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

## Bibliographic 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
- Received by editor(s): January 5, 2000
- Received by editor(s) in revised form: August 23, 2000
- Published electronically: October 18, 2000
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1815215