TY - GEN

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

AU - Beals, Robert

AU - Seress, Ákos

PY - 1992/7/1

Y1 - 1992/7/1

N2 - 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)logcn. 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(n2) 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 Õ(n3) algorithm. The [BLS2] algorithm takes 8(n3) 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).

AB - 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)logcn. 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(n2) 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 Õ(n3) algorithm. The [BLS2] algorithm takes 8(n3) 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).

UR - http://www.scopus.com/inward/record.url?scp=0026972894&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026972894&partnerID=8YFLogxK

U2 - 10.1145/129712.129724

DO - 10.1145/129712.129724

M3 - Conference contribution

AN - SCOPUS:0026972894

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 116

EP - 125

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -