Abstract
A base of a permutation group G is a subset B of the permutation domain such that only the identity of G fixes B pointwise. The permutation representations of important classes of groups, including all finite simple groups other than the alternating groups, admit O (log n ) size bases, where n is the size of the permutation domain. Groups with very small bases dominate the work on permutation groups within computational group theory.
We use the "soft" version of the big-O notation introduced by [BLSI]: for two functions f ( n ), g ( n ), we write f ( n )= O ˜( g ( n )) if for some constants c, C > 0, we have f ( n ) ≤ Cg ( n ) log c n .
We address the problems of finding structure trees and composition factors for permutation groups with small ( O ˜(1) size) bases. For general permutation groups, a method of Atkinson will find a structure tree in O ( n 2 ) time. We give an O ˜( n ) algorithm for the small base case. The composition factor problem was first shown to have a polynomial time solution by Luks [Lu], and recently Babai, Luks, Seress [BLS2] gave an O ˜( n 3 ) algorithm. The [BLS2] algorithm takes ( n 3 ) time even in the small base case. We overcome several quadratic and cubic bottlenecks in the [BLS2] algorithm to give an O ˜( n ) Monte Carlo algorithm for the small base case. In addition, we show that the center of a small base group can be found in time O ˜( n ).