Probabilistic algorithms in group theory

A finite group G is commonly presented by a set of elements which generate G. We argue that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. We bound the expected number of random elements requied to generate a given group G. Our main results are probabilistic algorithms which take as inputs a random generator set of a fixed permutation group G ⊆Sn. We gave O(n³ logn) expected time sequential RAM algorithms for testing membership, group inclusion and equality. Our bounds hold for any (worse case) input groups; we average only over the random generators representing the groups. Our algorithms are two orders of magnitude faster than the best previous algorithms for these group theoretic problems, which required Ω(n⁵) time even if given random generators. Furthermore, we show that in the case the input group is a 2-group with a random presentation, than those group theoretic problems can be solved by a parallel RAM in O(log n)³ expected time using n^O(1) processors.

Duke Scholars

Author John H. Reif Computer Science