A nearly linear algorithm for Sylow subgroups of small-base permutation group

Let G be a permutation group acting on a finite set $Omega$ and assume that no composition factor of G is an exceptional group of Lie type. Let p be a prime. New Monte Carlo algorithms are presented for the construction and conjugation of Sylow p-subgroups of G. The running time of the algorithms is $O(sn/ logsp{c} vert Gvert)$ for some explicitly computable constant c where n is the size of $Omega$ and s the number of generators for G. This running time is nearly linear for small-base groups.;The method employs a reduction to the case of permutation representations of finite simple groups. This reduction starts with a series of normal subgroups and faithful permutation representations of the factors which are direct products of isomorphic simple groups. We show how to solve the problems of finding and conjugating Sylow subgroups for the given group once we solve these problems for these factors.;This reduces the problem to finding and conjugating Sylow subgroups of finite simple groups. We invoke the Classification of finite simple groups. The cyclic groups of prime order are easy to handle while the sporadic simple groups can be handled by brute force. We solve these problems for the alternating simple groups and the classical simple groups. We use detailed information about the alternating and classical simple groups: their automorphism groups, their combinatorial and geometric properties and their subgroup structure.;An implementation of the algorithm is expected to be practical even for input groups of very large degree.