turkmath.org

Black box groups are introduced as an idealised setting for randomised algorithms for solving permutation and matrix group problems in computational group theory. A 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 gh, $g^{-1}$ and decide whether $g = h$. 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. More desirable algorithms, called constructive recognition algorithms, are the ones producing an isomorphism between a black box copy of a finite group and its natural copy.
A simple observation on the recognition algorithms in black box group theory is that procedures are based on checking whether some first order formulae satisfied by the given black box group. I will focus on this observation and discuss constructive recognition of black box groups of Lie type. Along the way, I will explain how we define a standard Frobenius automorphism in a black box group isomorphic to $(P)SL(2, q)$ and construct (or interpret) of a black box field in black box groups using only black box group operations. If time permits, I will talk about the interpretation of inverse transpose map and graph automorphisms, and the corresponding constructions in the black box groups of Lie type.
This is a joint work with Alexandre Borovik.