For each family of finite classical groups, and their associated simple quotients, we provide an explicit presentation on a specific generating set of size at most 8. Since there exist efficient algorithms to construct this generating set in any copy of the group, our presentations can be used to verify claimed isomorphisms between representations of the classical group. The presentations are available in Magma.
The conjecture was motivated by potential complexity applications to questions about matrix groups defined over finite fields (see @cite_21 for details); its proof also provided verification for the first constructive recognition algorithms for classical groups, developed by Kantor and Seress @cite_4 .
@cite_21 @cite_4
1980351200 1969754062
We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NPB. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NPB and thus in NPB ∩ NPB. Introduction Preliminaries Special linear groups: @math Orthogonal groups: @math Symplectic groups: @math Unitary groups: @math Proofs of Theorems 1.1 and 1.1, and of corollaries 1.2-1.4 Permutation group algorithms Concluding remarks References.