Structure forest and composition factors for small base groups in nearly linear time

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-0 notation introduced by [BLS1]: for two functions f(n),g(n), we write f(n) = Õ(g(n)) if for some constants c, C > 0, we have f(n) ≥ Cg(n)log^cn. We address the problems of finding structure trees and composition factors for permutation groups with small (Õ(1) size) bases. For general permutation groups, a method of Atkinson will find a structure tree in O(n²) time. We give an Õ(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 Õ(n³) algorithm. The [BLS2] algorithm takes 8(n³) time even in the small base case. We overcome several quadratic and cubic bottlenecks in the [BLS2] algorithm to give an Õ(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 0(n).