Skip to main content
3 of 5
Fixes missing overline and wrong numbering
Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51

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 $\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 groupes 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", 2001.

Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51