Speaker: Jennifer Chubb, University of San Francisco

Title: Detecting properties from descriptions of groups.

Abstract: The complexity of the word, conjugacy, and isomorphism problems of finitely presented groups have long been of interest in combinatorial group theory, logic, and algebra in general. Motivating questions are whether (and ideally, how) the presentation of a group in terms of generators and relators can shed any light on the existence of algorithms that solve these problems, or whether the groups exhibit other properties of interest. These questions are usually formulated as what we'll call detection problems, questions of the form "Does presentation P yield a group which exhibits property X?"

We consider detection problems in two classes of descriptions of groups. The first is the class of recursive presentations of groups, in which we are given an algorithm that identifies the generators and relators in the presentation. The second is from the point of view of computable structure theory, from which we consider another type of algorithmic description of a group, its computable atomic diagram.

From either perspective we are asking whether, given a simple, finite description of a group in the form of an algorithm, it is possible to effectively determine whether or not the group has some specified property. When there is such an effective procedure, we say the property s recursively recognizable within some class of descriptions. When there is not, we ask how algorithmically complex detection would be.

We were originally motivated by a desire to determine from a recursive presentation or atomic diagram whether or not a group is orderable. While we see results in that context, we will begin by considering a much more general class of properties, Markov properties, which include having a solvable word problem, being torsion-free, trivial, nilpotent, abelian, orderable, etc., We will see precise characterizations of the algorithmic complexity of the detection problems for many of these properties.

This work is joint with Iva Bilanovic and Sam Roven.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491