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

Document Type : Ischia Group Theory 2014


Dipartimento di Matematica Universita; di Padova


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.


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
Volume 4, Issue 2 - Serial Number 2
Proceedings of the Ischia Group Theory 2014-Part II.
June 2015
Pages 49-67
  • Receive Date: 11 October 2014
  • Revise Date: 18 June 2015
  • Accept Date: 19 June 2015
  • Published Online: 01 June 2015