# How do I find the minimum size of a generating set of a group?

For example, obviously all the integer points in a $\mathbb{R}^n$ space have a minimum generating set with a size of $n$, that is, $\{(1,0,...,0),(0,1,...,0),...,(0,0,...,1)\}$.

I came across this because I was thinking what should be the generating set of the Symmetric Group $S_4$, and I thought $\{(12),(23),(34)\}$ would be reasonable, and it was shocking when I realized a smaller set $\{(12),(1234)\}$ can do the job. So is there any way I can find the minimum size of a generating set of a group? Or can I easily tell if my former guessing is wrong?

-
This is a very hard question in general. It is however known that the minimal generating set for any symmetric group is size 2, and is not that hard to prove (the hard part is finding the right generators!). It is also true for all finite simple groups, but this is incredibly difficult and requires the classification. Some classes of groups (p-groups, abelian groups) are not too hard; others (solvable groups) can be extremely difficult. –  user641 Nov 10 '11 at 6:52
In fact, $S_n$ can be generated by $(1,2)$ and $(1,2,\ldots,n)$; the minimal number is straightforward for finitely generated abelian groups (it equals the number of invariant factors) and finitely generated nilpotent groups (same as their abelianization). –  Arturo Magidin Nov 10 '11 at 7:05
In the case of $p$-groups we have the following. Let $\Phi(G)$ be the Frattini-subgroup of a $p$-group $G$, and let $G'$ be the commutator subgroup. Then $\Phi(G)\cong G' G^p$ und so $G/\Phi(G) \cong C_p^n$ is an n-dimensional vector space. Any minimal generating set of $G$ has $\dim_{\mathbb{F}_p}(G/\Phi(G))$ elements. This result is known as Burnside's basis theorem. –  Oliver Braun Nov 10 '11 at 7:12
For solvable groups an algorithm is implemented in GAP. I believe the technical details for doing it for general finite groups are known, but not implemented due to missing infrastructure. For solvable groups, I believe the result is due to P. Hall. If you want an exposition of the finite case, I can do that. Here is a puzzle: It takes 2 generators for S4, so how many generators does S4×S4 take? –  Jack Schmidt Nov 10 '11 at 14:10
@JackSchmidt: I vote for an exposition of the finite case! –  user641 Nov 10 '11 at 17:52

Computing the size of the minimum generating set of a finite group can be performed by an algorithm that uses at most $O(\log^2 n)$ space. A brief description of the algorithm is given in Proposition 3 of The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem, by Arvind and Toran, 2006. It essentially enumerates all subsets of the group of size $\log k$ and determines if all elements of the group are reachable on the Cayley graph induced by edges labelled by elements of S.
Algorithms which use $O(\log^2 n)$ space are not quite polynomial time algorithms, but there may yet be a polynomial time algorithm out there for this computational problem.