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?

  • 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