12
$\begingroup$

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?

  • 5
    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.2011-11-10
  • 4
    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).2011-11-10
  • 5
    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.2011-11-10
  • 0
    In your first example you are basically just dealing with the cross product of $n$ copies of $\mathbb{Z}$. Each is generated (as a group) by one element, and so you get that your groups is generated by $n$ elements. However, this is not always the case. There is a paper by Wiegold and Wilson called "Growth Sequences of Finitely Generated Groups", and a number of papers of Wiegold with approximately the same title but with finite instead of finitely generated, which look at how you can generated cross products of $n$-copies of a group asymptotically.2011-11-10
  • 3
    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?2011-11-10
  • 4
    @JackSchmidt: I vote for an exposition of the finite case!2011-11-10
  • 0
    Any finite group has a generating set that is logarithmic in the order of the group. This is because a proper subgroup has order at most half the order of the group, so you can work your way down a chain of subgroups to the identity. However, even this is often much too large for the minimum size generating set which, as has already been noted, is difficult to find in general.2011-11-10
  • 0
    @JackSchmidt: The answer to the puzzle is 2 (not 4): $\langle(1 2 3),(1 2 3 4)\rangle$ and $\langle(1 2 3 4),(1 2 3)\rangle$.2012-11-07
  • 0
    @HagenvonEitzen: yup, I believe S4^n requires n generators, unless n=1, in which case it requires 2.2012-11-07

1 Answers 1

4

Perhaps this is not quite what you want, but I can provide a computational answer to this question.

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 if the group is given as its multiplication table (as opposed to, say, a finite presentation). 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.

  • 0
    To supplement this, note that the question 'given a presentation of a group, what is the size of its smallest generating set?' is recursively unsolvable in general, since the question of whether the group is trivial is reducible to this question.2015-07-17