\titleofpresentation{From proofs about finite groups to probabilistic
algorithms for black box groups} 

\presenter{\c{S}\"{u}kr\"{u} Yal\c{c}\i nkaya}  

The main purpose of this talk is to develop an analogy between the
methods for recognizing a black box group and the classification of
the finite simple groups. Following this talk, Alexandre Borovik will
talk about the relations between black box groups and groups of finite
Morley rank. 

A \textit{black box group} $G$ is a finite group whose elements are
encoded as 0-1 strings of uniform length and the group operations are
performed by an oracle (`black box'). Given strings representing $g,h
\in G$, the black box can compute the strings representing $g \cdot
h$, $g^{-1}$ and decide whether $g=h$. In problems naturally arising
in computational group theory, some additional information is usually
available, for example, the group can be given as a group of matrices
over a finite field; another natural assumption is that we have an
\textit{order oracle} which determines the orders of elements. 

In this context, a natural task  is to find a probabilistic algorithm
which determines the isomorphism type of a group within given
(arbitrarily small) probability of error. Under various mild
assumptions, there are positive answers to this question in class of
finite simple groups; for example, one can determine the isomorphism
type of a finite simple group of Lie type with an order oracle
\cite{Sukru2}.  

In this talk, we propose a uniform approach for recognizing simple
groups of Lie type which follows the computational version of the
classification of the finite simple groups. Similar to the inductive
argument on centralizers of involutions which plays a crucial role in
the classification project, our approach is based on a recursive
construction of the centralizers of involutions in black box groups
\cite{sukru4, sukru5}. We present an algorithm which constructs a long
root ${\rm SL}_2(q)$-subgroup in a finite simple group of Lie type of
odd characteristic. Following this construction, we take the
Aschbacher's ``Classical Involution Theorem'' \cite{Sukru1} as a model
in the final recognition algorithm and we construct all root ${\rm
SL}_2(q)$-subgroups corresponding to the nodes in the  extended Dynkin
diagram, that is, we construct the extended Curtis - Phan - Tits
\cite{sukru6, sukru7, sukru8} presentation of the finite simple groups
of Lie type of odd characteristic. In particular, we construct all
subsystem subgroups which can be read from the extended Dynkin
diagram. With this approach it is also possible to determine whether
the $p$-core (or ``unipotent radical'') $O_p(G)$ of a black box group
$G$ is trivial or not where $G/O_p(G)$ is a finite simple group of Lie
type of odd characteristic $p$ answering a well-known question of
Babai and Shalev \cite{sukru3}. 






\begin{ourbiblio}{99} 

\bibitem{Sukru1}
M.~Aschbacher, \emph{A characterization of Chevalley groups over fields of odd order I, II}, Ann. of Math. \textbf{106} (1977), 353--468.

\bibitem{Sukru2} L.~Babai, W.~M.~Kantor, P.~P.~Palfy, A.~Seress, \textit{Black-box recognition of finite simple groups of Lie type by statistics of element orders}, J. Group Theory 5, 2002, 383–401.

\bibitem{sukru3}
L.~Babai and A.~Shalev, \emph{Recognizing simplicity of black-box groups and the frequency of $p$-singular elements in affine groups}, in Groups and Computation III (W.~Kantor and A.~Seress, eds.), de Gruyter, Berlin (2001), 39--62.

\bibitem{sukru4}
A.~V. Borovik, \emph{Centralisers of involutions in black-box groups}, Contemp. Math. \textbf{298} (2002), 7--20.

\bibitem{sukru5}
J.~N. Bray, \emph{An improved method of finding the centralizer of an involution}, Arch. Math. (Basel) \textbf{74} (2000), 241--245.

\bibitem{sukru6}
C.~Curtis, \emph{Central extensions of groups of Lie type}, J. Reine Angew. Math. \textbf{220} (1965), 174--185.
  
\bibitem{sukru7}
K.~W. Phan, \emph{On groups generated by three-dimensional special unitary groups I, II}, J. Austral. Math. Soc. Ser. A \textbf{23} (1977).

\bibitem{sukru8}
J.~Tits, \emph{Groupes semi-simples isotropes}, Colloque sur la th\'{e}orie des groupes alg\'{e}briques, Bruxelles (1962), 137--146.
\end{ourbiblio}



\presenteraddress{Middle East Technical University}  % The name of a university is fine.

\email{sukru@math.metu.edu.tr}

