Abstract

If a black box simple group is known to be isomorphic to a classical group over a field of known characteristic, a Las Vegas algorithm is used to produce an explicit isomorphism. This is used to upgrade all nearly linear time Monte Carlo permutation group algorithms to Las Vegas algorithms when the input group has no composition factor isomorphic to an exceptional group of Lie type or a 3–dimensional unitary group.

Key words and phrases: computational group theory, black box groups, classical groups, matrix group recognition

1991 Mathematics Subject Classification: Primary 20B40, 20G40; Secondary: 20P05, 68Q25, 68Q40

Introduction

There is a large library of nearly linear time permutation group algorithms [BCFS, BS, CF, LS, Mo, Ra, SchS, Ser]. Most of these are Monte Carlo (which means that the algorithm can return an incorrect answer, although the probability of that can be made as small as desired). The main result of this note is that Monte Carlo can be upgraded to Las Vegas (which means that the output is always correct, but the algorithm may also report failure, although the probability of that can be made as small as desired), whenever there are suitable recognition algorithms for the simple groups occurring as composition factors.

There is a growing literature of recognition algorithms for quasisimple groups of Lie type. The first of these, due to Neumann and Praeger [NP], solved the following problem: given a group G ≤ GL(d, q) by a set of generating matrices, decide whether G contains SL(d, q).