ALGEBRAIC, COMPUTATIONAL, AND GEOMETRIC PROPERTIES OF RANDOM GROUPS

Professor Schupp is studying the algebraic and geometric properties of random group-theoretic objects and the generic-case behavior of group-theoretic algorithms, with the goal of extending these ideas to other types of mathematical structures.

The theme of genericity in the context of finitely generated groups is the subject of much active research and has occupied Professor Schupp and his collaborators for several years. They have developed new techniques and ideas of independent interest and beauty that combine nontrivial algebraic and probabilistic methods. During his Center appointment, Professor Schupp will continue his exploration of these areas.

First, standard “worst-case” measures of computational difficulty often do not give a good overall picture of a particular problem or algorithm. It turns out that in many interesting cases the famous traditional group-theoretic decision problems, such as the word, conjugacy, and isomorphism problems, have provably very low generic-case complexity.

Also, it turns out that “random” groups have very strong properties. Professor Schupp and his colleagues discovered that a strong Mostow-type isomorphism rigidity holds for two classes of groups: random one-relator groups and random quotients of the modular group. Two random groups from one of these two classes are isomorphic (an algebraic concept) if and only if their associated geometric structures (Cayley graphs) are isometric. These ideas suggest approaches to questions about subgroups of random groups, particularly subgroups of finite index.

Rigidity allows using Kolmogorov complexity to conclude that random presentations from the above-mentioned classes are “essentially incompressible,” that is, the given group does not possess any finite presentation at all that is substantially shorter than the given one. This phenomenon of essential incompressibility should be extendable to other classes of structures. In particular, it seems feasible to show that random finite automation (defined by random transition graphs) are essentially incompressible in terms of extended regular expressions.