0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Every finite simple group can be generated by two elements, see mathoverflow.net/questions/59213/… $\endgroup$ – Francesco Polizzi Aug 22 '16 at 21:02
  • $\begingroup$ 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. $\endgroup$ – khers Aug 22 '16 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Aug 22 '16 at 21:32
  • $\begingroup$ By minimal generating subsets, I mean irredundant (no proper subset of it can generate the group). Thanks $\endgroup$ – khers Aug 22 '16 at 21:59
  • $\begingroup$ 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. $\endgroup$ – Geoff Robinson Aug 23 '16 at 4:36
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note that, by "minimal", the OP means "irredundant" so, even in finite simple groups, some minimal generating sets might have cardinality larger than two. $\endgroup$ – verret Aug 23 '16 at 0:41
  • $\begingroup$ @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).$ $\endgroup$ – Igor Rivin Aug 23 '16 at 1:13
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.