dc.contributor.author | Dick, Ian Gregor | |
dc.date.accessioned | 2015-09-30T18:13:34Z | |
dc.date.available | 2015-09-30T18:13:34Z | |
dc.date.issued | 2015-07 | |
dc.identifier.citation | Dick, I.G. 2015. Constructive recognition of black-box F4(q) in odd characteristic. Queen Mary University of London. | en_US |
dc.identifier.uri | http://qmro.qmul.ac.uk/xmlui/handle/123456789/9025 | |
dc.description | PhD | en_US |
dc.description.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. | en_US |
dc.description.sponsorship | This work was supported by the Engineering and Physical Sciences Research Council grant
number MTHA1F6R | en_US |
dc.language.iso | en | en_US |
dc.publisher | Queen Mary University of London | en_US |
dc.subject | Mathematics | en_US |
dc.title | Constructive recognition of black-box F4(q) in odd characteristic. | en_US |
dc.type | Thesis | en_US |
dc.rights.holder | The copyright of this thesis rests with the author and no quotation from it or information derived from it may be published without the prior written consent of the autho | |