Steinberg presentations of black box classical groups in small characteristics

arXiv1302.3059MaRDI QIDQ6239592FDOQ6239592

Authors: Alexandre V. Borovik, Şükrü Yalçınkaya 

Publication date: 13 February 2013

Abstract: The main component of (constructive) recognition algorithms for black box groups of Lie type in computational group theory is the construction of unipotent elements. In the existing algorithms unipotent elements are found by random search and therefore the running time of these algorithms is polynomial in the underlying field size $q$ which makes them unfeasible for most practical applications cite{guralnick01.169}. Meanwhile, the input size of recognition algorithms involves only $logq$. The present paper introduces a new approach to construction of unipotent elements in which the running time of the algorithm is quadratic in characteristic $p$ of the underlying field and is polynomial in $logq$; for small values of $p$ (which make a vast and practically important class of problems), the complexity of these algorithms is polynomial in the input size. For $ps{l}_2(q)$, $qpone$, we present a Monte-Carlo algorithm which constructs a root subgroup $U$, the maximal torus $T$ normalizing $U$ and a Weyl group element $w$ which conjugates $U$ to its opposite. Moreover, we extend this result and construct Steinberg generators for the black box untwisted classical groups defined over a field of odd size $q=p^k$ where $qpone$. Our algorithms run in time quadratic in characteristic $p$ of the underlying field and polynomial in $logq$ and the Lie rank $n$ of the group. The case $qmone$ requires the use of additional tools and is treated separately in our next paper cite{suko12B}. Further, and much stronger results can be found in cite{suko12E,suko12F}.

This page was built for publication: Steinberg presentations of black box classical groups in small characteristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239592)