Available in electronic format
Available in print format		 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN: 1088-6834(e) ISSN: 0894-0347(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

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

Author(s): Alexander Lubotzky; Igor Pak
Journal: J. Amer. Math. Soc. 14 (2001), 347-363.
MSC (2000): Primary 60B15; Secondary 05C25, 22D10, 60J10
Posted: October 18, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

References:

[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 $23^{rd}$ 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. $11^{\text{t}h}$ 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 $SL_{n}\,(n\ge 3)$and $Sp_{2n}\,(n\ge 2)$, 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 $SL(3,\mathbb{Z} )$, 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 $\text{Out}\,F_{3}$, 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, 81, Birkhauser, Boston, MA, 1984. MR 86j:22014

Similar Articles:

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: 10.1090/S0894-0347-00-00356-8
PII: S 0894-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
Posted: October 18, 2000
Copyright of article: Copyright 2000, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google