Colloquium-Detecting properties from descriptions of groups

Title: Detecting properties from descriptions of groups

Speaker:  Jennifer Chubb, University of San Francisco and GWU

Date and Time: Friday, March 23, 1:00-2:00pm
Place: Rome 204

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 P?"  

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 is in the Kleene hierarchy of unsolvability.

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 will see results in that vein, we will begin by considering a much broader class of properties, and see precise characterizations of the algorithmic complexity of the detection problems for many of them.
This work is joint with Iva Bilanovic and Sam Roven.
Bio: Jennifer Chubb received her PhD from George Washington University in 2009, where she studied mathematical logic and computability theory.  Her main interests are in  computable structure theory, and the algorithmically accessible content of mathematics in general.  In a previous life, she studied physics, applied math, and non-linear dynamics at George Mason University.  Jennifer is an Associate Professor at the University of San Francisco's Department of Mathematics in California, and visiting scholar at George Washington University.