Stephen J. Pride

University of Glasgow

1. Introduction

Combinatorial group theory is concerned with groups which are given by means of presentations. A rich and fruitful method of studying groups given this way is to use geometric and topological techniques. Such ideas were employed by Dehn in the early development of the subject, and there has been an explosion in the use of such techniques over the last 30 years.

Group theorists of course work with group presentations, that is, ordered pairs

(1) P*=<X;R>

where X is a set and R is a set of words on X and X' (where X' is set disjoint from X and in one-to-one correspondence with it [where x' corresponds to x]). The group defined by the presentation is then specified as follows. An elementary reduction of a word W on X and X' is the deletion of a subword which belongs to R, or the deletion of an "inverse pair" xx', x'x. An elementary insertion is the opposite of an elementary reduction. Two words are said to be equivalent if one can be obtained from the other by a finite sequence of elementary reductions and insertions. The group G defined by P* then consists of the equivalence classes W, with multiplication given by [V][W] = [VW].

Now if we consider the rewriting system

(2) P=[X,X'; r=1 (r in R),xx'=1, x'x=1 (x in X)]

(where 1 denotes the empty word), then the elementary reductions constitute the one step reduction relation corresponding to this rewriting system, and G is nothing more than the monoid defined by P (the quotient of the free monoid on X and X' by the congruence generated by the one-step reduction relation). Thus, a group presentation really encodes a rewriting system with some of the data suppressed. The geometric techniques for dealing with group presentations are tailor made so that one does not have to bother about this suppressed information. Nevertheless, people do think about rewriting systems for groups. Indeed quite a lot of work has been done on the question of which groups have finite complete rewriting systems. In investigating this question one is really treating the group as a monoid.

Just as it is fruitful to consider the real numbers as part of the complex world, it may thus be fruitful to consider groups as part of the monoid world. As such I am interested in developing geometric techniques for general rewriting systems, which extend the existing techniques for dealing with group presentations. This should have benefit to group theory, monoid theory, and the theory of rewriting systems.

2. Group-theoretic background

Given a group presentation as in (1), there is an important module associated with P* called the second homotopy module. The elements of this module can be represented by means of geometric objects called spherical pictures. (We remark that one can consider pictures which are not spherical; these too are useful.)

Much work has been done on finding a "basis" for the spherical pictures over a given presentation P* - that is, finding a collection of spherical pictures from which all other pictures can be derived (in a well-specified sense). If one can find such a basis then it can often be used to obtain information about the group G defined by P*. Finding a basis is a geometric problem. By experimention one first tries to find a collection D of "obvious" spherical pictures over P*. One then tries to argue that any other spherical picture can be derived from these obvious ones.

If D turns out to be a basis then one can associate with the pair P*, D a function h(P*,D) which gives a measure of how efficiently the spherical pictures over P* can be derived from those in D.

A nice situation is when the presentation P* is finite (ie., X and R are finite) and there is a finite basis D for the spherical pictures over P*. A group with such a presentation is said to be of type F_3. In this case the function h(P*,D) turns out to be a group invariant (up to a certain standard equivalence) called the second order Dehn function of G.

The above is the analogue one dimension higher, of what one does in finding a presentation for a group. Given a set of generators of a group one looks for a collection R of "obvious" relations amongst these generators. One then tries to show that these obvious relations are a "basis" for all the relations, that is, any other relation is derivable from those in R. When this is the case we have a presentation P* of the group, and an associated function f(P*) which measures how efficiently the relations can be derived from R. In the case when the group is finitely presented (that is, of type F_2) the function f(P*) then becomes a group invariant called the first order Dehn function of G.

We remark that under suitable finiteness conditions one can obtain an n-th order Dehn function for any dimension n.

3. Extension to rewriting systems

Let P be an arbitrary rewriting system (not necessarily as in (2)). It is possible to define the concept of a picture over P. Indeed one can define a certain 2-dimensional complex K=K(P) associated with P, where the 1-cells in K are "atomic pictures" over P, and where paths in K are then pictures over P. Spherical pictures over P are closed paths in K.

One can then consider finding a basis for the spherical pictures over P. Again this means a set of spherical pictures from which all others can be derived. But now there are two different notions of derivability depending on whether one works homotopically or homologically in K. If D is a homotopic basis then we get an associated function h'(P,D) measuring how effficient this basis is. Similarly, if we have a homological basis E then we obtain a function h(P,E).

A monoid M which has a finite rewriting system P with a finite homotopic basis D for the spherical pictures is said to be of finite derivation type (FDT). For such a monoid h'(P,D) is essentially a monoid invariant, called the second order homotopical Dehn function of M. A monoid which has a finite rewriting system with a finite homological basis for the spherical pictures is said to be of finite homological type (FHT). For such a monoid one then obtains a monoid invariant called the second order homological Dehn function. It turns out that if the monoid is a group then this homological second order Dehn function agrees with the function h already defined for groups.

We remark that there is a first order Dehn function for general finite rewriting systems which is essentially a monoid invariant and which agrees with the first order Dehn function for finitely presented groups. We would ultimately want to define and compute nth order Dehn functions for monoids in all dimensions n, which agree with the already defined functions for groups.

4. Papers

Listed below are some relevant papers by myself and others.

J.M. Alonso, W.A. Bogley, R.M. Burton, S.J. Pride and X. Wang, Second order Dehn functions of groups, Quart, J. Math. Oxford (2), 49 (1998), 1-30.

J.M. Alonso, S.J. Pride and X. Wang, Higher dimensional isoperimetric (or Dehn) functions of groups, Journal of Group Theory, 2 (1999), 81-112.

Y.G. Baik, J. Harlander and S.J. Pride, The geometry of group extensions, J. Group Theory 1 (1998), 395-416.

W.A. Bogley and S.J. Pride, Calculating generators of pi_2; in: Low-Dimensional Homotopy Theory and Combinatorial Group Theory, C. Hog-Angeloni, W. Metzler, A. Sieradski (eds.), Cambridge University Press, 1993, 157-188.

V. Guba and M. Sapir, Diagram groups, Memoirs Amer. Math. Soc. 130 (1997), Number 620.

V. Guba and S.J. Pride, On the left and right cohomological dimension of monoids, Bull. London Math. Soc. 30 (1998), 391-396.

S.J. Pride, Low dimensional homotopy theory for monoids, Intern. J. Alg. Comput. 5 (1995), 631-649.

S.J. Pride, Geometric methods in combinatorial semigroup theory, in: Semigroups, Formal Languages and Groups (J. Fountain, ed.), 1995, Kluwer Publishers, 215-232.

S.J. Pride, Low dimensional homotopy theory for monoids II: groups, Glasgow Math. J., 41 (1999), 1-11.

S.J. Pride and Jing Wang, Subgroups of finite index in groups with finite complete rewriting systems, Proc. Edin. Math. Soc., to appear.

S.J. Pride and Jing Wang, Rewriting systems, finiteness conditions, and associated functions, to appear in Proceedings Lincoln Conference 1998.

S.J. Pride and Xiaofeng Wang, Second order Dehn functions of groups and monoids, Internat. J. Alg. Comput., to appear.

S.J. Pride and Xiaofeng Wang, Second order Dehn functions and HNN-extensions, J. Austral. Math. Soc., 67 (1999), 272-288.

Jing Wang, Finite derivation type for semi-direct products of monoids, Theoretical Computer Science 191 (1998), 219-228.

Jing Wang, Finite complete rewriting systems and finite derivation type for small extensions of monoids, Journal of Algebra 204 (1998), 493-503.

Xiaofeng Wang, Mappings of groups and quasi-retractions, Journal of Group Theory, 2 (1999), 435-446.