Algorithms for the minimum generating set problem

For a finite group G, the size of a minimum generating set of G is denoted by d(G). Given a finite group G and an integer k, deciding if d(G)?k is known as the minimum generating set (MIN-GEN) problem. A group G of order n has generating set of size logpn? where p is the smallest prime dividing n=|G|. This fact is used to design an nlogpn+O(1)-time algorithm for the group isomorphism problem of groups specified by their Cayley tables (attributed to Tarjan by Miller, 1978). The same fact can be used to give an nlogpn+O(1)-time algorithm for the MIN-GEN problem. We show that the MIN-GEN problem can be solved in time n(1/4)logpn+O(1) for general groups given by their Cayley tables. This runtime incidentally matches with the runtime of the best known algorithm for the group isomorphism problem. We show that if a group G, given by its Cayley table, is the product of simple groups then a minimum generating set of G can be computed in time polynomial in |G|. Given groups Gi along with d(Gi) for i?[r] the problem of computing d(?i?[r]Gi) is nontrivial. As a consequence of our result for products of simple groups we show that this problem also can be solved in polynomial time for Cayley table representation. For the MIN-GEN problem for permutation groups, to the best of our knowledge, no significantly better algorithm than the brute force algorithm is known. For an input group G?Sn, the brute force algorithm runs in time |G|O(n) which can be 2?(n2). We show that if G?Sn is a primitive permutation group then the MIN-GEN problem can be solved in time quasi-polynomial in n. We also design a DTIME(2n) algorithm for computing a minimum generating set of permutation groups all of whose non-abelian chief factors have bounded orders.