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 -