Place: MDBF G029

Abstract: A black box group is a black box (or an oracle, or a device, or an algorithm) operating with binary strings of uniform length which encrypt (not necessarily in a unique way) elements of some finite group. Group operations, taking inverses and deciding whether two strings represent the same group elements are done by the black box. 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, constructive recognition algorithms, are the ones producing an isomorphism between a black box copy of a finite group and its natural copy. 

In this talk, I will discuss characterizations of the groups PSL2 and PSL3 over fields of odd characteristic via geometry of involutions (elements of order 2) in the context of black box groups. Starting with the black box groups encrypting PSL2 and PSL3,  I will discuss a construction of the black box projective plane and its coordinatization which will yield a solution to a recognition problem for these groups. 

I will also discuss a solution of a twenty year old problem in the computational group theory, that is, a construction of a unipotent element in a black box group encrypting PSL2.

This is a joint work with Alexandre Borovik.