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

Robert Beals, Ákos Seress

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

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-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).

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
PublisherAssociation for Computing Machinery
Pages116-125
Number of pages10
ISBN (Electronic)0897915119
DOIs
StatePublished - Jul 1 1992
Externally publishedYes
Event24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada
Duration: May 4 1992May 6 1992

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129722
ISSN (Print)0737-8017

Other

Other24th Annual ACM Symposium on Theory of Computing, STOC 1992
CountryCanada
CityVictoria
Period5/4/925/6/92

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Structure forest and composition factors for small base groups in nearly linear time'. Together they form a unique fingerprint.

Cite this