Geometric notions of space complexity for the word problem
by
Tim Riley
Cornell
Coauthors: Martin Bridson

A word w represents the identity element in a finitely presented group if and only if it can be reduced to the empty word by applying relations and inserting or deleting inverse pairs of letters. The minimal length FL(n) such that every word w of length at most n that represents the identity can be reduced to the empty word whilst encountering words no longer than FL(n) en route, is a (naive) measure of the space complexity of the word problem. This function is called filling length and has a geometric interpretation in terms of null-homotopies of loops; its qualitative behaviour gives a quasi-isometry invariant. I will show that relaxing the definition in natural ways (such as allowing conjugation when reducing) can radically change the invariant.

Date received: March 6, 2006