Generating sets of finite groups
HTML articles powered by AMS MathViewer
- by Peter J. Cameron, Andrea Lucchini and Colva M. Roney-Dougal PDF
- Trans. Amer. Math. Soc. 370 (2018), 6751-6770 Request permission
Abstract:
We investigate the extent to which the exchange relation holds in finite groups $G$. We define a new equivalence relation $\equiv _{\mathrm {m}}$, where two elements are equivalent if each can be substituted for the other in any generating set for $G$. We then refine this to a new sequence $\equiv _{\mathrm {m}}^{(r)}$ of equivalence relations by saying that $x \equiv _{\mathrm {m}}^{(r)}y$ if each can be substituted for the other in any $r$-element generating set. The relations $\equiv _{\mathrm {m}}^{(r)}$ become finer as $r$ increases, and we define a new group invariant $\psi (G)$ to be the value of $r$ at which they stabilise to $\equiv _{\mathrm {m}}$.
Remarkably, we are able to prove that if $G$ is soluble, then $\psi (G) \in \{d(G),$ $d(G) +1\}$, where $d(G)$ is the minimum number of generators of $G$, and to classify the finite soluble groups $G$ for which $\psi (G) = d(G)$. For insoluble $G$, we show that $d(G) \leq \psi (G) \leq d(G) + 5$. However, we know of no examples of groups $G$ for which $\psi (G) > d(G) + 1$.
As an application, we look at the generating graph $\Gamma (G)$ of $G$, whose vertices are the elements of $G$, the edges being the $2$-element generating sets. Our relation $\equiv _{\mathrm {m}}^{(2)}$ enables us to calculate $\mathrm {Aut}(\Gamma (G))$ for all soluble groups $G$ of nonzero spread and to give detailed structural information about $\mathrm {Aut}(\Gamma (G))$ in the insoluble case.
References
- Adolfo Ballester-Bolinches and Luis M. Ezquerro, Classes of finite groups, Mathematics and Its Applications (Springer), vol. 584, Springer, Dordrecht, 2006. MR 2241927
- Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
- J. R. Britnell, A. Evseev, R. M. Guralnick, P. E. Holmes, and A. Maróti, Sets of elements that pairwise generate a linear group, J. Combin. Theory Ser. A 115 (2008), no. 3, 442–465. MR 2402604, DOI 10.1016/j.jcta.2007.07.002
- Timothy C. Burness, Martin W. Liebeck, and Aner Shalev, Generation and random generation: from simple groups to maximal subgroups, Adv. Math. 248 (2013), 59–95. MR 3107507, DOI 10.1016/j.aim.2013.07.009
- T. Breuer, R. M. Guralnick, A. Lucchini, A. Maróti, and G. P. Nagy, Hamiltonian cycles in the generating graphs of finite groups, Bull. Lond. Math. Soc. 42 (2010), no. 4, 621–633. MR 2669683, DOI 10.1112/blms/bdq017
- Eleonora Crestani and Andrea Lucchini, The generating graph of finite soluble groups, Israel J. Math. 198 (2013), no. 1, 63–74. MR 3096630, DOI 10.1007/s11856-012-0190-1
- Eleonora Crestani and Andrea Lucchini, Bias of group generators in the solvable case, Israel J. Math. 207 (2015), no. 2, 739–761. MR 3359716, DOI 10.1007/s11856-015-1159-7
- Francesca Dalla Volta and Andrea Lucchini, Finite groups that need more generators than any proper quotient, J. Austral. Math. Soc. Ser. A 64 (1998), no. 1, 82–91. MR 1490148, DOI 10.1017/S1446788700001312
- 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
- Wolfgang Gaschütz, Zu einem von B. H. und H. Neumann gestellten Problem, Math. Nachr. 14 (1955), 249–252 (1956) (German). MR 83993, DOI 10.1002/mana.19550140406
- Robert Guralnick and Gunter Malle, Simple groups admit Beauville structures, J. Lond. Math. Soc. (2) 85 (2012), no. 3, 694–721. MR 2927804, DOI 10.1112/jlms/jdr062
- Robert M. Guralnick and William M. Kantor, Probabilistic generation of finite simple groups, J. Algebra 234 (2000), no. 2, 743–792. Special issue in honor of Helmut Wielandt. MR 1800754, DOI 10.1006/jabr.2000.8357
- J. I. Hall, Classifying copolar spaces and graphs, Quart. J. Math. Oxford Ser. (2) 33 (1982), no. 132, 421–449. MR 679813, DOI 10.1093/qmath/33.4.421
- Sebastian Jambor, The minimal generating sets of $\textrm {PSL}(2,p)$ of size four, LMS J. Comput. Math. 16 (2013), 419–423. MR 3124163, DOI 10.1112/S1461157013000193
- W. M. Kantor, A. Lubotzky, and A. Shalev, Invariable generation and the Chebotarev invariant of a finite group, J. Algebra 348 (2011), 302–314. MR 2852243, DOI 10.1016/j.jalgebra.2011.09.022
- Martin W. Liebeck and Aner Shalev, Simple groups, probabilistic methods, and a conjecture of Kantor and Lubotzky, J. Algebra 184 (1996), no. 1, 31–57. MR 1402569, DOI 10.1006/jabr.1996.0248
- Andrea Lucchini, The largest size of a minimal generating set of a finite group, Arch. Math. (Basel) 101 (2013), no. 1, 1–8. MR 3073659, DOI 10.1007/s00013-013-0527-y
- Andrea Lucchini and Attila Maróti, On the clique number of the generating graph of a finite group, Proc. Amer. Math. Soc. 137 (2009), no. 10, 3207–3217. MR 2515391, DOI 10.1090/S0002-9939-09-09992-4
- Andrea Lucchini and Attila Maróti, Some results and questions related to the generating graph of a finite group, Ischia group theory 2008, World Sci. Publ., Hackensack, NJ, 2009, pp. 183–208. MR 2816431, DOI 10.1142/9789814277808_{0}014
- Andrea Lucchini, Attila Maróti, and Colva M. Roney-Dougal, On the generating graph of a simple group, J. Aust. Math. Soc. 103 (2017), no. 1, 91–103. MR 3679018, DOI 10.1017/S1446788716000458
- Tomasz Łuczak and László Pyber, On random generation of the symmetric group, Combin. Probab. Comput. 2 (1993), no. 4, 505–512. MR 1264722, DOI 10.1017/S0963548300000869
- The On-Line Encyclopedia of Integer Sequences, https://oeis.org/
- Attila Maróti, Covering the symmetric groups with proper subgroups, J. Combin. Theory Ser. A 110 (2005), no. 1, 97–111. MR 2128968, DOI 10.1016/j.jcta.2004.10.003
- Derek John Scott Robinson, A course in the theory of groups, Graduate Texts in Mathematics, vol. 80, Springer-Verlag, New York-Berlin, 1982. MR 648604, DOI 10.1007/978-1-4684-0128-8
- Alexander Stein, $1\frac 12$-generation of finite simple groups, Beiträge Algebra Geom. 39 (1998), no. 2, 349–358. MR 1642676
- Aner Shalev, A theorem on random matrices and some applications, J. Algebra 199 (1998), no. 1, 124–141. MR 1489358, DOI 10.1006/jabr.1997.7167
- Julius Whiston, Maximal independent generating sets of the symmetric group, J. Algebra 232 (2000), no. 1, 255–268. MR 1783924, DOI 10.1006/jabr.2000.8399
Additional Information
- Peter J. Cameron
- Affiliation: Mathematical Institute, University of St Andrews, St Andrews, Fife KY16 9SS, Scotland
- MR Author ID: 44560
- ORCID: 0000-0003-3130-9505
- Email: pjc20@st-andrews.ac.uk
- Andrea Lucchini
- Affiliation: Dipartimento di Matematica, Università degli studi di Padova, Via Trieste 63, 35121 Padova, Italy
- MR Author ID: 233594
- Email: lucchini@math.unipd.it
- Colva M. Roney-Dougal
- Affiliation: Mathematical Institute, University of St Andrews, St Andrews, Fife KY16 9SS, Scotland
- Email: colva.roney-dougal@st-andrews.ac.uk
- Received by editor(s): September 19, 2016
- Received by editor(s) in revised form: January 9, 2017
- Published electronically: April 4, 2018
- Additional Notes: The second and third authors were supported by Università di Padova (Progetto di Ricerca di Ateneo: Invariable generation of groups).
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 370 (2018), 6751-6770
- MSC (2010): Primary 20D60; Secondary 20D10, 20D05
- DOI: https://doi.org/10.1090/tran/7248
- MathSciNet review: 3814347