# the number of minimal generating subsets of a group

Clearly every finite group has a minimal generating subset.

1. Is there any formula for the number of minimal generating subsets of a finite group?

2. Is it known which groups have a unique minimal generating subset?

• Every finite simple group can be generated by two elements, see mathoverflow.net/questions/59213/… – Francesco Polizzi Aug 22 '16 at 21:02
• Thanks for your guidance, I will read it and it is truely very intersting. But I did not ask about the minimum number of elements in a generating subset. I try to find an upper bound on the number of generating subsets which are minimal. Not their cardinality. I need the cardinality of the collection of minimal generating subsets. Again thanks for your help. – khers Aug 22 '16 at 21:03
• With perhaps small exceptions among 2-groups, no group has a unique minimal such set, since one can substitute an element for its inverse, and for 2-groups there are certain things like conjugates that can be used for the substitution. For a finite product of copies of the two element group, there are lots of such sets, and a weak lower bound can be had by counting invertible 0-1 matrices over the two element field. The weak lower bound is like $O(n^{\log n})$, and this can doubtless be improved. Gerhard "Assuming My Memory Still Works" Paseman, 2016.08.22. – Gerhard Paseman Aug 22 '16 at 21:32
• By minimal generating subsets, I mean irredundant (no proper subset of it can generate the group). Thanks – khers Aug 22 '16 at 21:59
• Since a minimal generating set is sent to a minimal generating set by any automorphism, in the second question, it might be better to ask for groups $G$ such that their automorphism groups transitively permute minimal generating sets. – Geoff Robinson Aug 23 '16 at 4:36

1.No, this is a hard question in general. It could maybe be done for special classes of groups, say nilpotent groups.

2.The only (finitely-generated) groups which have a unique minimal generating subset are the trivial group and the cyclic group of order 2.

Let $G$ be a group with a unique minimal generating subset $S$. As Gerhard Paseman said in the comments, we can replace a non-involution by its inverse, so we can assume that every element in $S$ is an involution. Now, let $s$ and $t$ be distinct elements of $S$ and let $S^*=(S\setminus\{t\})\cup \{st\}$. Clearly, $S^*$ generates $G$. Since $G$ has a unique minimal generating set and $|S|=|S^*|$, $S^*$ must be minimal (otherwise we'd get a smaller generating set) and thus $st$ is an involution and $s$ and $t$ commute. Since $s$ and $t$ were arbitrary elements of $S$, $G$ is an elementary abelian $2$-group and it is easily seen that it must have order at most $2$.

In finite simple groups, most pairs of elements generate, so (at least asymptotically), the number of generating pairs is $\asymp |G|^2.$ See, for example:

Robert M. Guralnick, Martin W. Liebeck, Jan Saxl, and Aner Shalev, MR 1707675 Random generation of finite simple groups, J. Algebra 219 (1999), no. 1, 345--355.

• Note that, by "minimal", the OP means "irredundant" so, even in finite simple groups, some minimal generating sets might have cardinality larger than two. – verret Aug 23 '16 at 0:41
• @verret Yes, I do understand that (notice that I make no statement about this in my answer). However, if I wanted to go out on a limb (a fairly thick one), I would conjecture that the number of minimal generating sets for a finite simple group is $\Theta(|G|^2).$ – Igor Rivin Aug 23 '16 at 1:13

If $G$ is a p-group and the Frattini quotient $G/\phi(G)$ has order $p^r$ (it's an elementary abelian group) then the number of minimal generating sets equals the number of bases of $\mathbb{F}_p^r$: $\frac{(p^r-1)(p^r-p)\cdots(p^r-p^{r-1})}{n!}$.

More generally: If $G$ is nilpotent, each gnerating set of $G/[G,G]$ lifts to a generating set of $G$ and the cardinality of a minimal generating set equals the rank of $G/[G,G]$. Hence, counting the minimal generating sets boils down to counting the minimal generating sets of an abelian group. But I don't know a formula for this number by heart.