How many elements are needed to generate a finite group with good probability?
type: Item
instance of: scholarly article
title: How many elements are needed to generate a finite group with good probability?
zbMATH Open document ID: 1042.20046
DOI: 10.1007/BF02784504
author: Eloisa Detomi
author: Andrea Lucchini
author: Fiorenza Morini
published in: Israel Journal of Mathematics
publication date: 2002-01-01T00:00:00Z
review text: For a finite group \(G\), let \(d(G)\) denote the least number of elements required to generate \(G\), and \(\lambda(G)\) be the length of a composition series of \(G\). For each real \(\alpha\) with \(0<\alpha<1\), the authors define \(d_\alpha(G)\) to be the least integer \(t\) such that \(t\) elements chosen at random from \(G\) generate \(G\) with probability at least \(\alpha\). Examples show that \(d_\alpha(G)\) cannot be bounded by a function depending only on \(d(G)\). The authors prove that for each \(\alpha\) there exists a constant \(c_\alpha\) such that \[ d_\alpha(G)\leq d(G)+c_\alpha\log\lambda(G)\log\log\lambda(G)\leq d(G)+c_\alpha\log\log|G|\log\log\log|G| \] whenever \(\lambda(G)\geq 4\) (all logarithms are base 2). For \(\lambda(G)<4\) the corresponding bound is \(d(G)+c_\alpha\). As they note, this bound is close to one conjectured by I. Pak (unpublished). As a corollary they prove: if \(\beta>\tfrac 12\) and \(0<\alpha<1\) then there exists \(n_0\) such that \(d_\alpha(G)\leq\beta n\) for every permutation group \(G\) of degree \(n\geq n_0\). A similar result (with \(\beta>\tfrac 32\)) is proved for completely reducible linear groups of degree \(n\). Since this paper was published, stronger theorems proving the full conjecture of Pak have been obtained by \textit{A. Lubotzky} [J. Algebra 257, No. 2, 452-459 (2002; Zbl 1042.20047)].
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 20P05
Mathematics Subject Classification ID: 20F05
Mathematics Subject Classification ID: 20B35
Mathematics Subject Classification ID: 20G40
Mathematics Subject Classification ID: 11N45
zbMATH DE Number: 1874386
zbMATH Keywords: numbers of generators
zbMATH Keywords: finite groups
zbMATH Keywords: randomly chosen elements
zbMATH Keywords: permutation groups
zbMATH Keywords: completely reducible linear groups
MaRDI profile type: Publication
cites work: Some applications of the first cohomology group
cites work: Chains of subgroups in symmetric groups
cites work: Zu einem von B. H. und H. Neumann gestellten Problem
cites work: Die Eulersche Funktion endlicher auflösbarer Gruppen
cites work: The probability of generating a finite classical group
cites work: Generating Finite Completely Reducible Linear Groups
cites work: On the number of generators and composition length of finite linear groups
full work available at URL: https://doi.org/10.1007/bf02784504
OpenAlex ID: W1992076965
Recommended article: Minimal and random generation of permutation and matrix groups.
Recommended article: The probability of generating a permutation group.
Recommended article: Minimal generation of transitive permutation groups
Recommended article: Bounding the composition length of primitive permutation groups and completely reducible linear groups
Recommended article: Invariable generation of permutation and linear groups
Recommended article: Generation and random generation: from simple groups to maximal subgroups.
Recommended article: On the orders of doubly transitive permutation groups, elementary estimates
Recommended article: The expected number of elements to generate a finite group with \(d\)-generated Sylow subgroups
Recommended article: The expected number of random elements to generate a finite group.
description: scientific article; zbMATH DE number 1874386