Algorithms for the minimum generating set problem

Abstract

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.