Constructive recognition of black-box F4(q) in odd characteristic.

Abstract

Let G be a group, and let b G be a group isomorphic to G. The constructive recognition problem for G with respect to b G is to find an isomorphism Á from G to b G such that the images under Á and Á¡1 of arbitrary elements may be computed efficiently. If the representation of b G is well-understood, then the representation of G becomes likewise by means of the action of Á. The problem is of foundational importance to the computational matrix group project in its ambitious desire to find an algorithmto construct a composition series for an arbitrarymatrix group over a finite field. This requires algorithms for the constructive recognition of all finite simple groups, which exist in the literature in varying degrees of practicality. Those for the exceptional groups of Lie type admit of improvement, and it is with these that we concern ourselves. Kantor and Magaard in [31] give Monte Carlo algorithms for the constructive recognition of black-box (i.e. opaque-representation) exceptional groups other than 2F4(22nÅ1). These run in time exponential in the length of the input at several stages. We specialise to the case of F4(q) for odd q, and in so doing develop a polynomial-time alternative to the preprocessing stage of the Kantor–Magaard algorithm; we then modify the procedure for the computation of images under the recognising isomorphisms to reduce this to polynomial running time also. We provide a prototype of an implementation of the resulting algorithm in MAGMA [10]. Fundamental to our method is the construction of involution centralisers using Bray’s algorithm [11]. Our work is complementary to that of Liebeck and O’Brien [40] which also uses involution centralisers; we make a comparison of the two approaches.