Can we say anything about a minimal generating set of a finite group based on its normal subgroups? For example, can we bound their order, or say whether they come from the same conjugacy class?
An easy example is that when $G$ is cyclic, if $x$ generates $G$ then $x$ does not generate any (normal) subgroup of $G$.
If it isn't possible in general to relate a minimal set of generators of a finite group to its normal subgroups, can we do this when $G$ is generated by only 2 or 3 elements?
Best Answer
The arXiv paper The Minimum Generating Set Problem by Lucchini and Thakkar (to be published in Journal of Algebra) describes an algorithm for finding a smallest-sized generating set of (a finite group) $G$ starting from a chief series $G = N_u > N_{u-1} > \dotsb N_1 > N_0= \{1\}$ of $G$.
The idea is to successively find smallest-sized generating sets of the quotients $G/N_{u-1}, G/N_{u-2},\dotsc,G/N_1,G/N_0 \cong G$. The top factor is simple and either cyclic with one generator, or nonabelian simple with two generators, which can quickly found by a random search.
Defining $d(G)$ to be the smallest size of a generating set of $G$, there is a useful result that, for a minimal normal subgroup $N$ of $G$, we always have $d(G/N) \le d(G) \le d(G/N)+1$ and, furthermore, if $d(G/N) = d$ with $G/N = \langle g_1N,\ldots,g_dN\rangle$, then either $d(G) = d(G/N)$ and there exist $n_1,\dotsc,n_d \in N$ with $G = \langle g_1n_1,\dotsc,g_dn_d \rangle$; or $d(G) = d(G/N)+1$ and there exist $n_1,\dotsc,n_d,n_{d+1} \in N$ with $G = \langle g_1n_1,\dotsc,g_dn_d,n_{d+1} \rangle$.
The bulk of the paper is describing methods to decide which of the two cases we are in when moving from $G/N_i$ to $G/N_{i-1}$ without recourse to too many exhaustive searches through all $d$- or ($d+1$)-tuples of elements of $N$. Implementations run very fast in practice.