turkmath.org

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 the recognition problem for the black box groups PSL_2 over fields of odd characteristic. Our approach to this problem involves the construction of a black box projective plane and its coordinatization by using the geometry of involutions (elements of order 2). This construction produces the best possible recognition for these groups and also produces a solution to a long standing open problem in computational group theory, that is, construction of a unipotent element in black box groups of Lie type. This is a joint work with Alexandre Borovik.