Clearly every finite group has a minimal generating subset.
Is there any formula for the number of minimal generating subsets of a finite group?
Is it known which groups have a unique minimal generating subset?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ Every finite simple group can be generated by two elements, see mathoverflow.net/questions/59213/… $\endgroup$– Francesco PolizziCommented Aug 22, 2016 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$– khersCommented Aug 22, 2016 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 PasemanCommented Aug 22, 2016 at 21:32
-
$\begingroup$ By minimal generating subsets, I mean irredundant (no proper subset of it can generate the group). Thanks $\endgroup$– khersCommented Aug 22, 2016 at 21:59
-
1$\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 RobinsonCommented Aug 23, 2016 at 4:36
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
answered Aug 22, 2016 at 23:43
-
$\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$– verretCommented Aug 23, 2016 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$ Commented Aug 23, 2016 at 1:13