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

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.$


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.

Tags:

Gr.Group Theory

Finite Groups

Related

Higman's lemma and a manuscript of Erdős and Rado Process quicker than Fourier for squares of polynomials Maps between grassmannians with inclusion property On sums of independent random variables in Banach spaces Global integral model for unitary groups Every riemannian length structure on $\mathbb{R}^n$ is induced by a continuous function $f:\mathbb{R}^n\to \mathbb{E}^n$, to the euclidean space Why doesn't mathematics collapse even though humans quite often make mistakes in their proofs? Number of matrices with bounded products of rows and columns CG spaces from the perspective of sheaves over compact Hausdorff spaces Sums of binomial coefficients weighted by incomplete gamma Regular subsets of $\text{PSL}(2, q)$ Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?

Recent Posts