Bias of group generators in finite and profinite groups: known results and open problems

Document Type: Research Paper

Authors

Dipartimento di Matematica Universita; di Padova

Abstract

We analyze some properties of the distribution $Q_{G,k}$ of the first component in a $k$-tuple chosen uniformly in the set of all the $k$-tuples generating a finite group $G$ (the limiting distribution of the product replacement algorithm). In particular, we concentrate our attention on the study of the variation distance $\beta_k(G)$ between $Q_{G,k}$ and the uniform distribution. We review some known results, analyze several examples and propose some intriguing open questions.

Keywords

Main Subjects


L. Babai and I. Pak (2000). Strong bias of group generators: an obstacle to the "product replacement algorithm". Pro ceed-ings of the Eleventh Annual ACM-SIAM Symp osium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York. , 627-635
F. Celler, C. R. Leedham-Green, S. Murray, A. Niemeyer and E. A. OBrien (1995). Generating random elements of a finite group. Comm. Algebra. 23, 4931-4948
E. Crestani and A. Lucchini Bias of group generators in the solvable case. Israel J. Math., to app ear, DOI: 10.1007/s11856-015-1159-7.
E. Crestani, G. De Franceschi and A. Lucchini Probability and bias in generating supersoluble groups. Proc. Edinb. Math. Soc , to appear.
J. D. Dixon (1969). The probability of generating the symmetric group. Math. Z.. 110, 199-205
M. D. Fried and M. Jarden (1986). Field Arithmetic. Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, New York. 11
P. Hall (1936). The Eulerian functions of a group. Quart. J. Math.. 7, 134-151
W. M. Kantor and A. Lubotzky (1990). The probability of generating a finite classical group. Geom. Dedicata. 36 (1), 67-87
M. W. Liebeck and A. Shalev (1995). The probability of generating a finite simple group. Geom. Dedicata. 56 (1), 103-113
A. Lucchini (2005). The X-Dirichlet polynomial of a finite group. J. Group Theory. 8 (2), 171-188
A. Lucchini, F. Menegazzo and M. Morigi (2006). On the probability of generating prosoluble groups. Israel J. Math.. 155, 93-115
A. Lubotzky and I. Pak (2001). The pro duct replacement algorithm and Kazhdan's property (T). J. Amer. Math. Soc.. 14 (2), 347-363
M. Morigi (2006). On the probability of generating free prosoluble groups of small rank. Israel J. Math.. 155, 177-123
A. Mann (1996). Positively finitely generated groups. Forum. Math.. 8 (4), 429-459
A. Mann and A. Shalev (1996). Simple groups, maximal subgroups, and probabilistic aspects of profinite groups. Israel J. Math.. 96 part B, 449-468
N. E. Menezes, M. Quick and C. M. Roney-Dougal (2013). The probability of generating a nite simple group. Israel J. Math.. 198 (1), 371-392
I. Pak (2001). What do we know about the product replacement algorithm. in Groups and computation, I I I, de Gruyter, Berlin. , 301-347
M. Pinter (2010). The existence of an inverse limit of an inverse system of measure spaces - a purely measurable case. Acta Math. Hungar.. 126 (1-2), 65-77