An elementary algorithm for computing the composition factors of a permutation group

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

1 Scopus citations

Abstract

A permutation group G may be concisely described by a set S of generators (\S\ need not be larger than log |G|). From such a short description, however, it is not immediately clear how to efficiently obtain various kinds of information about the group. Furst, Hopcroft, and Luks [FHL] showed that an algorithm of Sims [Si] for computing the order of G and performing membership tests runs in polynomial time. Sims's algorithm relies on combinatorial methods, and there is no deep group theory involved in the analysis. Polynomial time algorithms for determining various aspects of the structure of G are also known. However, it seems that algorithms which give us more information about G require increasing amounts of group theory for their analyses. An example is Luks's algorithm [Lu2] to find composition factors (the "building blocks" of G), which requires the classification of finite simple groups (CFSG) for its proof of correctness. Kantor's algorithm [Ka] for finding Sylow subgroups likewise requires CFSG. As the proof of CFSG is 15,000 manuscript pages long (according to Gorenstein [Go2]), it is reasonable to ask whether so much group theory is necessary to study the computational complexity of permutation group problems. We give a deterministic polynomial time algorithm to compute the composition factors of a permutation group, given by a set of generators. This is the first polynomial time algorithm for the composition factor problem with an analysis that does not depend on CFSG. In addition, we give a Monte Carlo version of our algorithm which runs in nearly linear (0(nlogcn)) time for the class of "small-base" permutation groups introduced by Babai, Cooperman, Finkelstein, and Seress [BCFS]. This algorithm is significantly less complicated than other algorithms for the same problem, and should be easier to implement efficiently.

Original languageEnglish (US)
Title of host publicationProceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993
EditorsManuel Bronstein
PublisherAssociation for Computing Machinery
Pages127-134
Number of pages8
ISBN (Electronic)0897916042
DOIs
StatePublished - Aug 1 1993
Event1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 - Kiev, Ukraine
Duration: Jul 6 1993Jul 8 1993

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993
Country/TerritoryUkraine
CityKiev
Period7/6/937/8/93

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'An elementary algorithm for computing the composition factors of a permutation group'. Together they form a unique fingerprint.

Cite this