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

Lubotzky, Alexander; Pak, Igor

doi:10.1090/S0894-0347-00-00356-8

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

Local expansion of vertex-transitive graphs and random generation in finite groups

in

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

Strong bias of group generators: an obstacle to the “product replacement algorithm”

in

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

On the connection of the dual space of a group with the structure of its closed subgroups (Russian)

1

personal communication

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

On the congruence subgroup problem for tree lattices, in “Lie groups and ergodic theory (Mumbai, 1996)"

Generating random elements in solvable groups

On the graph of generating sets of a simple group

What do we know about the product replacement random walk?

Groups and Computations III

On sampling generating sets of finite groups and the product replacement algorithm

in preparation

GAP – Groups, Algorithms, and Programming

Explicit Kazhdan constants for representations of semisimple and arithmetic groups

Bounded generation and Kazhdan’s property (T)

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