How many minimum generating sets are there in a finite group?

Question

Let $G$ be a finite group of order $n$.

A generating set in $G$ is said to be minimum if it has minimal size.

Is there a known lower bound on number of minimum generating sets in a group of order $n$? For cyclic groups I know the answer.

Answer 1

For the sake of simplicity of exposition, let $G$ be a non-cyclic finite group which can be generated by two elements. Let us first consider whether an element $x \in G$ can be a member of two-element generating set. In the contrary case, we have $\langle x, y \rangle < G$ for any $y \in G$. Continuing the contrary case, if we set $\mathcal{M}(x)$ to be the union of the maximal subgroups containing $x$, we see that $\langle x,y \rangle \leq \mathcal{M}(x)$ for each $y \in G$, so that in particular $G = \mathcal{M}(x).$

On the other hand, if $\mathcal{M}(x) = G$, then we do have $\langle x, y \rangle < G$ for each $y \in G$. Hence $x \in G$ is a member of a two-element generating set for $G$ if and only if $\mathcal{M}(x) < G.$ To make more explicit, if $y \in G \backslash \mathcal{M}(x)$, we see that $\langle x,y \rangle$ is not contained in any maximal subgroup $H$ of $G$ ( for that maximal subgroup $H$ would contain $x$ and $y$, so would be a subset of $\mathcal{M}(x)$, which it isn't as even $y \not \in \mathcal{M}(x)$).

So it is actually (in principle) possible to give a precise count of the number of (different in the sense of the question) two element generating sets of $G$.

First, determine those $x$ for which $\mathcal{M}(x) < G$ (assuming $G$ is two-generated, there will be some such $x$). Let $\mathcal{G}$ be the set of such $x$. Then the number of different generating pairs for $G$ is $$\frac{\sum_{x \in \mathcal{G}}|G \backslash \mathcal{M}(x)|}{2},$$ since we obtain each generating pair $\{x,y\}$ twice, once from $y \in G \backslash \mathcal{M}(x)$ and once from $x \in G \backslash \mathcal{M}(y).$

The idea to generalize this to groups which are $k$-generated, but not $k-1$-generated should be clear. Given $k-1$ elements $x_{1},x_{2}, \ldots, x_{k-1}$, it can be extended to a $k$-element generating set if and only if $\mathcal{M}(\langle x_{1}, x_{2}, \ldots , x_{k-1} \rangle) < G,$ where $\mathcal{M}(\langle x_{1}, x_{2}, \ldots , x_{k-1} \rangle)$ is the union of those maximal subgroups of $G$ which contain $\langle x_{1},x_{2}, \ldots, x_{k-1} \rangle.$

Answer 2

Some fairly general lower bounds are given in Igor Pak's "What do we know about the product placement algorithm" [2].

Let $d(G)$ denote the minimal number of generators of $G$. By $\varphi_{k}(G)$ we denote the number of generating $k$-tuples of $G$. The function $\varphi_k$ is usually referred to as the $k$-th Eulerian function of the group $G$ [1].

OP's Question. Let $d = d(G)$. Is there a non-trivial lower bound for $\frac{\varphi_{d}(G)}{d!}$ given as a function of the cardinal $\vert G \vert$ of $G$?

The probability that $k \ge d(G)$ uniformly and independently chosen elements in $G$ generate the whole group is:

$$\overline{\varphi}_k(G) \Doteq \frac{\varphi_k(G)}{{\vert G \vert}^k}.$$

Here is the most general (and the weakest) lower bound extracted from [2]:

[2, Theorem 1.1.7]. Let $G$ be a finite group, let $m \Doteq \lceil\log_2(\vert G \vert)\rceil$ and let $k \ge d(G)$. Let $0 < \epsilon < 1$. Then we have:

• $\overline{\varphi}_k(G) \ge \overline{\varphi}_k((\mathbb{Z}/2 \mathbb{Z})^m)$.
• $\overline{\varphi}_k(G) > 1 - \varepsilon$ if $k \ge m + 2 + \log_2(1/\epsilon)$.

There are also interesting general bounds for nilpotent groups.

[2, Proposition 1.1.4]. Let $G$ be a finite $p$-group with $p$ a prime number and let $d = d(G)$. Then we have $$\overline{\varphi}_d(G) \ge 1 -\frac{1}{p} - \frac{1}{p^2}.$$

For an arbitrary finite nilpotent group, we have:

[2, Proposition 1.1.4] Let $G$ be a finite nilpotent group and let $d = d(G)$. Then we have $$ \overline{\varphi}_d(G) > \frac{1}{5 \log(\log(G))}. $$

If $(G_n)$ is sequence of pairwise non-isomorphic finite simple groups then $\overline{\varphi}_2(G_n)$ tends to $1$ as $n$ tends to infinity [2, Theorem 1.1.1]. More detailed asymptotics are known for several specific sequences [2, Theorem 1.1.2].

---

[1] P. Hall, "The Eulerian functions of a group", Quarterly Journal of Mathematics 7 (1936), 134–151.
[2] I. Pak, "What do we know about the product replacement algorithm", 2000.