Math. Struct. in Comp. Science (), vol. 11, pp. 1–000 Copyright \begin{matrix}c \\ ◯ \end{matrix} Cambridge University Press

String Rewriting and Homology of Monoids

Daniel E. Cohen

Received 25 January 0

Results of Anick (1986), Squier (1987), Kobayashi (1990), Brown (1992b), and others, show that a monoid with a finite convergent rewriting sytem satisfies a homological condition known as F P_{∞}. In this paper we give a simplified version of Brown’s proof, which is conceptual whereas the other proofs are computational. We also collect together a large number of results and examples of monoids and groups which satisfy F P_{∞} and others which do not. These may provide techniques for showing that various monoids do not have finite convergent rewriting systems, as well as explicit examples on which methods can be tested.

1. Introduction

Kapur & Narendran (1985) showed that the rewriting system {(aba, bab)} has no equivalent finite convergent rewriting system. However the monoid it presents can also be presented by the finite convergent rewriting system {(ab, c), (ca, bc), (bcb, cc), (ccb, acc)} on three generators a, b, c.

It is therefore natural to ask what conditions a monoid must satisfy if it can be presented on some generating set by a finite convergent rewriting system.

An obvious necessary condition is that the monoid has solvable word problem. Squier (1987) showed that such a monoid must satisfy the condition F P_{3}, which is well-known in homology theory. It was later realised that results of Anick (1986) contained, in a different language and with some conditions which can be weakened, the stronger result that such monoids satisfy the homological condition F P_{∞}. These conditions, and the related conditions F P_{n} for all n, will be defined in section 6.

Anick proved his result by showing that any convergent rewriting system, not necessarily finite, gives rise to a resolution for the monoid. A proof by Kobayashi (1990), very similar to Anick’s, is rather easier to follow. Another proof was given by Groves (1991); see also (Farkas 1992). A version of Squier’s argument is also given in (Lafont & Prouté 1991); that argument is closer to ours than the other cited proofs, and is a useful introduction to our method.

All these proofs are computational, and so provide no insight as to why they work. By contrast, a proof due to Brown (1992b) is conceptual, and helps to explain what is happening. Also Brown’s method enables us to compute certain important homomorphisms, called boundary operators. The other proofs in principle allow these boundary operators to be computed, but do so only by a complicated inductive definition which is likely to be troublesome in practice.

Brown’s proof, however, requires some detailed knowledge of topology and homology theory to understand it. It therefore seems worthwhile to give a proof of Anick’s theorem using the essential ideas of Brown’s method in a form which does not require detailed topological or homological knowledge. I gave a version of the proof in (Cohen 1993), but the algebra can be simplified further by slightly weakening Brown’s conclusion, and we look at the simpler version here.

Squier also proved (the result was published after his death in (Squier, Otto & Kobayashi 1994); see also (Lafont 1994)) that a monoid with a finite convergent rewriting system satisfies a stronger condition, which he referred to as having finite derivation type. He showed that there was a monoid which did not have finite derivation type but is F P_{∞}. Recently, Cremans & Otto (1994) showed that a group has finite derivation type iff it is F P_{3}.

Much recent work in group theory has a very geometric flavour, and Hermiller & Meier (1994b) have shown a connection between groups with finite convergent rewriting systems and certain geometric properties. Precisely, they show that such a group has the geometric property known as a tame 1-combing. It is known that any group with a tame 1-combing is F P_{∞}, so we have another proof of Anick’s Theorem, but only for groups. The weaker property known as a bounded combing is discussed in (Alonso 1992), where groups with this property are shown to be F P_{∞}. Many groups with tame 1-combings are known, some of which have additional properties. It would be of interest to know whether such groups must have a finite convergent rewriting system.

Hermiller & Meier (1994b) also show that if the finite convergent rewriting system has additional properties (for instance, if it is length-reducing) then further geometric properties of the group can be obtained.

The relevant properties of rewriting systems are recalled in section 2. Sections 4 and 5 contain the homological results needed to discuss the F P_{n} and F P_{∞} properties, with their topological bakground sketched in Section 2. Section 6 lists all the results I know of about these properties. This is intended as a source of information which can be used in conjunction with Anick’s theorem to obtain interesting monoids or groups which have no finite convergent rewriting system (or as examples for which one may want to look for such a system). Section 7 contains the proof of Brown’s theorem, and section 8 compares the different approaches..

2. String Rewriting

A rewriting system on a set X is a set R of pairs of elements of the free monoid X^{∗}. We define a relation → on X^{∗} by ulv → urv for any pair (l, r) ∈ R and any (possibly empty) words u and v of X^{∗}, and we then say that ulv rewrites to urv. We denote by →^{+} and →^{∗} the transitive closure and the reflexive transitive closure of →. The monoid presented by ⟨X; R⟩ is defined to be the quotient of X^{∗} by the equivalence relation generated by →.

We say that a word w is reducible if there is some word z with w → z; if there is no such z we call w irreducible.

An arbitrary relation ≻ on a set S is called noetherian (or well-founded) if any sequence s_{1} ≻ s_{2} ≻ … ≻ s_{n} ≻ s_{n+1} ≻ … is finite. In particular, if → is noetherian, we see that any sequence of rewritings must eventually stop with an irreducible word.

We say that R is convergent (also called canonical or complete) if it is noetherian and there is only one irreducible word in each equivalence class. Results of Newman (1943) and others give conditions equivalent to this. In particular, if a finite system is noetherian (for instance, if r is shorter than l for all (l, r) ∈ R) then one can decide whether or not it is convergent. For general properties of rewriting systems see the books by Jantzen (1988) and Book & Otto (1993).

Two rewriting systems on the same set are called equivalent if the equivalence relations they define are the same. Knuth & Bendix (1970) proved that to every rewriting system there is an equivalent convergent rewriting system (which may, however, be infinite even if the original system is finite).

We say that the convergent rewriting system R is minimal if, for each (l, r) ∈ R, r is irreducible with respect to R and l is irreducible with respect to R − {(l, r)}. It is well-known (see (Kapur & Narendran 1985) or Theorem 2.4 of (Squier 1987)) that to every convergent rewriting system there is an equivalent minimal convergent rewriting system, which is finite if the original system is finite. Indeed, as shown in the references cited, the most obvious modification of R is suitable. That is, we begin by replacing each pair (l, r) by (l, r̂) where r̂ is the irreducible word obtained from r by repeated reduction. We then omit any pair (l_{1}, r_{1}) for which there is a pair (l, r) and words u and v with l_{1} = ulv. Finally, for each l we omit all but one pair with left side l. If R is not convergent, however, the resulting system need not be equivalent to R .

We say that R is strongly minimal if it is minimal and each element of X is irreducible. Any minimal convergent rewriting system R on X can be modified to a strongly minimal convergent rewriting system presenting the same monoid. We define X_{2} to be {x ∈ X; there is a pair (x, r_{x}) ∈ R}, and let X_{1} = X − X_{2}. Since R is minimal, no member of X_{2} occurs on the right-hand side of any member of R. Also the only member of R which has the element x of X_{2} occurring in its left-hand side is (x, r_{x}). It follows that the monoid presented by ⟨X; R⟩ is also presented by ⟨X_{1}; R_{1}⟩, where R_{1} = R − {(x, r_{x}); x ∈ X_{2}}. This latter system is easily seen to be convergent and strongly minimal. The two systems will not be equivalent, since they are defined over different generating sets.

We conclude this section by proving some results about noetherian relations which will be used in section 6.

Let ≻ be a relation on a set S. We define the height of an element s as the supremum of all k for which there is a sequence s ≻ s_{1} ≻ … ≻ s_{k}. This height is either a non-negative integer or is infinite.

There are two reasons why s may have infinite height. The first is that there is an infinite sequence s ≻ s_{1} ≻ … ≻ s_{n} ≻ . . .. The second is that there is no such infinite sequence, but, for all n there is a finite sequence s ≻ s_{n1} ≻ … ≻ s_{nn}. The following result is well-known, and its proof is easy. We make explicit use of it in the proof of Brown’s theorem. It is needed in Anick’s proof, and in all the other proofs, but its use there is implicit, and readers have to look closely to see that it plays a crucial role in the performance of an inductive process.

Lemma 1. (König’s Lemma) Suppose that for each s there are only finitely many t with s ≻ t. Then an element s has infinite height only if there is an infinite sequence s ≻ s_{1} ≻ … ≻ s_{n} ≻ . . .. In particular, if, in addition, ≻ is noetherian then every element has finite height.

Lemma 2. Let ≫ and ⇒ be noetherian relations on a set S such that whenever u ⇒ v ≫ w there is some z with u ≫ z ⇒ w. Define ≻ by u ≻ v if either u ≫ v or u ⇒ v. Then ≻ is noetherian.

Proof. Let ⇒^{∗} be the reflexive transitive closure of ⇒. An easy induction shows that if u ⇒^{∗} v ≫ w then there is some z such that u ≫ z ⇒^{∗} w. Suppose we have an infinite sequence v_{1} ⪰ v_{2} ⪰ . . .. We want to show that this sequence is ultimately constant. It will be enough to find elements u_{i} such that, for all i, u_{i} ⇒^{∗} v_{i} and either u_{i} ≫ u_{i+1} or u_{i} = u_{i+1} and one of v_{i} ⇒ v_{i+1} and v_{i} = v_{i+1} holds. For, as ≫ is noetherian, the sequence {u_{i}} will be ultimately constant. Once this constancy is achieved, the sequence {v_{i}} will also be ultimately constant, since ⇒ is also noetherian. We begin by defining u_{1} = v_{1}, and suppose that we have defined u_{i} for all i ≤ k. If v_{k} ⇒ v_{k+1} or v_{k} = v_{k+1}, we let u_{k+1} = u_{k}. If v_{k} ≫ v_{k+1}, the first paragraph of the proof shows that there is a suitable u_{k+1}.

3. The Topological Background

Our algebraic constructions and results first occurred in a topological setting, and closely mimic the corresponding topological constructions and results. It may therefore be helpful to begin with an account of the topological material. Because this is just for background, I leave many of the terms undefined, with the related algebraic concepts precisely defined later. Also, I omit technical conditions necessary for some of the results to hold (for instance, there is usually a need for the spaces considered to be reasonably well-behaved).

Let G be a group. Let X and Y be spaces, both of which have trivial higher homotopy groups and have fundamental group G. Then X is homotopy equivalent to Y. Consequently, these spaces have the same homology groups (and cohomology groups). It is natural to refer to these groups (which, for spaces with a geometric or combinatorial structure, are easily defined in terms of the geometry) as the homology groups of the group G.

This result was proved in 1935, but it was not until about ten years later that an explicit construction for the homology groups was made. This construction, and the earlier result, are the sources from which the wide river of homological algebra sprung.

For a simplicial complex (that is, a space made up of simplexes — triangles in dimension 2, tetrahedra in dimension 3, and so on), the homology groups are fairly easy to describe. The chain group in dimension n is defined to be the free abelian group with basis the n-simplexes. A boundary operator from the n-chains to the (n − 1)-chains is defined by requiring the boundary of a simplex to be the signed sum of its faces. The homology groups then measure how much the subgroup of all n-chains with zero boundary differs from the subgroup of all boundaries of (n + 1)-chains. For general spaces, we have a related construction, but the chain groups are much harder to describe.

How can we find such a space X? We can start with a contractible space C on which G acts nicely, and define X to be the quotient C/G.

We then want to obtain the homology groups of X. Because G acts on C it will also act on the chain groups of C, and the quotient of these chain groups by the action of G gives us the chain groups of X. Because C is contractible, the chain groups of C form a resolution of G (this algebraic notion is defined in the next section). Then the construction of the homology groups of X from the chain groups of X, and the construction of these chain groups from those of C, is exactly the algebraic construction of the homology groups of G given in the next section.

We still have to construct a suitable space C. We build C out of simplexes (we can regard the constructed object either as something abstract and combinatorial or as a topological space). We take one n-simplex [y_{1}, …, y_{n+1}] to each (n + 1)-tuple y_{1}, …, y_{n+1} of elements of G. This simplex has n+1 (n−1)-dimensional faces, each obtained by omitting one of the y_{i}. Also G acts on C by the obvious rule [y_{1}, …, y_{n+1}]z = [y_{1}z, …, y_{n+1}z]. It is not difficult to show that C is contractible.

This construction defines the simplexes in what may be called a homogeneous fashion. There is an alternative approach which may be called non-homogeneous. For this we take one n-simplex, denoted by (x_{1}, …, x_{n})x_{n+1} to each (n + 1)-tuple of elements of G. We have an obvious action of G on these simplexes, and we have a bijection between the simplexes in the two constructions under which (x_{1}, …, x_{n})x_{n+1} corresponds to [y_{1}, …, y_{n+1}] if y_{i} = x_{i} … x_{n+1} for 1 ≤ i ≤ n + 1; equivalently, x_{n+1} = y_{n+1} and x_{i} = y_{i}y_{i+1}^{−1} for 1 ≤ i ≤ n.

In this construction, the non-homogeneous (n−1)-dimensional simplexes corresponding to the faces of [y_{1}, …, y_{n+1}] are easily seen to be (x_{2}, …, x_{n})x_{n+1} for the first face, (x_{1}, …, x_{n−1})x_{n}x_{n+1} for the last face, and (x_{1}, …, x_{i−2}, x_{i−1}x_{i}, x_{i+2}, …, x_{n})x_{n+1} for the i-th face.

This description of the faces explains the definition of the bar resolution in a later section. When we are dealing with a group G, the homogeneous definition is simpler. But for an arbitrary monoid M, rather than a group, we no longer get a bijection between the homogeneous simplexes and the non-homogeneous ones, and the complex constructed using the homogeneous simplexes does not provide a resolution of M; also, the action of the monoid on the homogeneous simplexes is no longer free.

4. Complexes and Resolutions

Let M be a monoid. Let ZM be the monoid ring of M. This is defined to be the set of all finite formal sums ∑ n_{u}u, where u runs over all elements of M, n_{u} ∈ Z and n_{u} = 0 for all but finitely many u. Addition and multiplication are defined by (∑ n_{u}u)+(∑ p_{u}u) = ∑(n_{u} +p_{u})u and (∑ n_{u}u)(∑ p_{u}u) = ∑ q_{u}u where q_{u} = ∑_{vw=u} n_{v}p_{w}. It is easy to check that this makes ZM a ring. We do not use any special properties of Z, and the whole theory would be identical if we chose an arbitrary commutative ring for coefficients. However, Z is the most important case, so we do not use the more general notation.

A free chain complex over M consists of a sequence of free right ZM -modules P_{n} for all n ≥ 0 and homomorphisms ∂_{n} : P_{n} → P_{n−1} for all n > 0 such that ∂_{n}∂_{n+1} = 0 for n > 0. We shall usually just refer to a complex, since we do not consider other kinds of complex. We can just as well work with left modules, but choose right modules so as to be consistent with Brown’s notation (and Anick’s notation, but not Squier’s).

We say that a complex is augmented if there is also a homomorphism ϵ : P_{0} → Z such that ϵ∂_{1} = 0. Here, Z is regarded as a module on which M acts trivially.

An augmented complex is called a resolution of M if we have im ∂_{n+1} = ker ∂_{n} for n > 0, and im ∂_{1} = ker ϵ and ϵP_{0} = Z. Note that for any complex the left-hand side is contained in the right-hand side. Strictly speaking, we should refer to a free resolution of Z, but this is the only kind we shall consider.

Every monoid has a resolution. For suppose we have a partial resolution; that is, the modules and corresponding homomorphisms are defined only for n ≤ k. Every module is the quotient of a free module. So we can find a free module P_{k+1} which has a homomorphism onto ker ∂_{k}, and define ∂_{k+1} to be this homomorphism. Inductively, we can extend any partial resolution to a resolution. To start the induction, we may choose P_{0} to be ZM and ϵ(∑ n_{u}u) = ∑ n_{u}. Resolutions constructed like this are too big to be useful, but a smaller resolution will be constructed in the next section, and an even smaller resolution is obtained by Anick’s and Brown’s theorems. Theorem 1. (Anick’s Theorem) Any strongly minimal convergent rewriting system on a monoid M gives rise to a resolution of M. This resolution will be finitely generated in each dimension if the rewriting system is finite.

This will be proved using Brown’s method in section 6.

Given a sequence of modules and homomorphisms, it is usually straightforward to see that it forms an (augmented) complex. A direct proof that it is a resolution may be quite hard. Fortunately, to show that a complex is a resolution it is enough to prove the existence of other homomorphisms satisfying certain conditions.

Suppose we have an augmented complex with modules P_{n} and homomorphisms ∂_{n}. A contracting homotopy consists of a sequence of homomorphisms of abelian groups (not of modules) σ_{n} : P_{n} → P_{n+1} and η : Z → P_{0} such that, for n > 0 and x ∈ P_{n} we have ∂_{n+1}σ_{n}x + σ_{n−1}∂_{n}x = x, and for x ∈ P_{0} and r ∈ Z we also have ∂_{1}σ_{0}x + ηϵx = x and ϵηr = r. In examples we usually have P_{0} = ZM with ϵ(∑ n_{u}u) = ∑ n_{u}, and we then take η to be given by ηr = r1, where 1 is the identity element of M. Lemma 3. An augmented complex with a contracting homotopy is a resolution.

Proof. Let x be in P_{n}, where n > 0 (the other cases are similar but simpler). Then (omitting subscripts for ease of notation) x = ∂σx + σ∂x, so if ∂x = 0 we have, as required, x = ∂(σx).

It is not hard to see that every resolution has a contracting homotopy, which is defined inductively using the fact that the modules are free abelian groups. Since we do not need this result, the proof is left to the reader.

Let P be a free ZM-module with basis S. We denote by P̃ the free abelian group with basis S. Let Q be another free module with basis T, and let ϕ : P → Q be a homomorphism. Then, for all s ∈ S, we can write ϕs = ∑ tc_{st}, where c_{st} ∈ ZM and, for each s, c_{st} = 0 for all but finitely many t. We define ϕ̃: P̃ → Q̃ by ϕ̃s = ∑ t(ϵc_{st}), where ϵ(∑ n_{u}u) = ∑ n_{u}. The modules and homomorphism can be defined without mention of a basis. Specifically, we can define P̃ to be P ⊗ZM Z, where ⊗ denotes the tensor product. This is in principle a better approach, but it requires knowledge of tensor products which readers may not have and do not need for the properties that concern us.

It is easy to see that ĩm ϕ = im ϕ̃ and that k̃er ϕ ⊆ ker ϕ̃. In general this inclusion is not an equality.

Suppose we have a resolution with modules P_{n} and homomorphisms ∂_{n}. Then we have the corresponding abelian groups P̃_{n} and homomorphisms of abelian groups ˜∂_{n}. Since ∂_{n}∂_{n+1} = 0, the previous paragraph tells us that im ˜∂_{n+1} ⊆ ker ˜∂_{n}. The quotient group ker ˜∂_{n}/ im ˜∂_{n+1} is called the nth homology group of M.

These homology groups appear to depend on the choice of resolution. But it is wellknown (see (Hilton & Stammbach 1971), (MacLane 1963), or (Lafont & Prouté 1991)) that in fact they only depend on M. This is, of course, a key result, without which homology theory would be impossible. Also, these groups are the homology groups with integer coefficients. It is possible to use other coefficients, and also to define cohomology groups. Any of these groups can be used to check if Anick’s condition holds.

5. The Bar Resolution

Let M be a monoid. We will construct two resolutions of M, the unnormalised bar resolution and the normalised bar resolution.

An n-tuple of elements of M will be called an n-cell or a cell of dimension n. Let B_{n} be the free right ZM -module with basis the n-cells. In particular, B_{0} has a single generator (), and we usually identify B_{0} with ZM and () with 1_{M}, where 1_{M} is the identity of M (which we usually denote just by 1). We then define ϵ : B_{0} → Z by ϵ ∑ n_{u}u = ∑ n_{u}. We also define η : Z → ZM by ηn = n1_{M},

We define homomorphisms ∂_{ni} : B_{n} → B_{n−1} for n > 0 and 0 ≤ i ≤ n by

∂_{nn}(u_{1}, …, u_{n}) = (u_{1}, …, u_{n−1})u_{n},
∂_{n0}(u_{1}, …, u_{n}) = (u_{2}, …, u_{n}),

and, for 0 < i < n,

∂_{ni}(u_{1}, …, u_{n}) = (u_{1}, …, u_{i−1}, u_{i}u_{i+1}, u_{i+2}, …, u_{n}).

We then define ∂_{n} to be ∑_{0}^{n}(−1)^{n−i}∂_{ni}. In particular, ∂_{1}(u) = u − 1 (identifying B_{0} with ZM and () with 1), ∂_{2}(u, v) = (v)−(uv)+(u)v, and ∂_{3}(u, v, w) = −(v, w)+(uv, w)− (u, vw) + (u, v)w. Plainly ϵ∂_{1} = 0.

It is easy to check that ∂_{ni}∂_{n+1,j} = ∂_{n,j−1}∂_{n+1,i} for 0 ≤ i < j ≤ n + 1, from which we see that ∂_{n}∂_{n+1} = 0 for all n. Thus we have a complex.

We may define a homomorphism σ_{n} of abelian groups from B_{n} to B_{n+1} which sends (u_{1}, …, u_{n})u_{n+1} to (u_{1}, …, u_{n}, u_{n+1}). It is easy to check that this is a contracting homotopy.

Thus our complex is a resolution, which we call the unnormalised bar resolution.

We call the cell (u_{1}, …, u_{n}) degenerate if u_{i} = 1 for some i, and we let D_{n} be the submodule of B_{n} with basis the set of degenerate n-cells. Plainly, ∂_{n} maps D_{n} into D_{n−1} and σ_{n} maps D_{n} into D_{n+1}. It follows that ∂_{n} induces a homomorphism of modules from B_{n}/D_{n} to B_{n−1}/D_{n−1} and σ_{n} induces a homomorphism of abelian groups from B_{n}/D_{n} to B_{n+1}/D_{n+1}. Thus the modules B_{n}/D_{n}, which are plainly free with basis the non-degenerate n-cells, together with the homomorphisms induced by ∂_{n} also form a resolution.

We call this the normalised bar resolution. For notational reasons, we usually think of it as generated by all n-cells (u_{1}, …, u_{n}) with the relations (u_{1}, …, u_{n}) = 0 if u_{i} = 1 for some i. We shall usually call this resolution the bar resolution, since we shall not need the unnormalised resolution.

6. The F P_{∞} Property

We say that a monoid is F P_{∞} if it has a free resolution which is finitely generated in all dimensions. More generally, we say that it is F P_{n} if it has a free resolution which is finitely generated in all dimensions ≤ n.

We have seen that any partial resolution can be extended to a resolution. Thus M will be F P_{n} if it has a partial resolution which is defined in dimensions ≤ n and finitely generated in each dimension ≤ n.

The theorem of Anick, Brown, and Kobayashi tells us that a monoid with a finite convergent rewriting system will be F P_{∞}. Thus it is of interest to give examples of monoids and groups which satisfy this condition and other examples which do not satisfy it. I give here most of the results I am aware of concerning this property, so as to provide a resource for anyone interested in examples. As one of the major references (Bieri 1976) may not be widely available (having been published in a departmental lecture notes series), it seems worthwhile to record many of the results given there. Readers wanting to look at particular examples which cannot be treated by the methods discussed here will probably need to ask assistance from an expert in homology theory. The explicit presentations given (or obtainable) for some of these groups provide a source of examples to test.

As remarked in the introduction, in the rapidly developing field of geometric group theory, important classes of groups are F P_{∞}, and also satisfy the stronger necessary condition given in (Hermiller & Meier 1994b). I do not give examples of such groups; the interested reader should check the book by (Epstein, Cannon, Holt, Levy, Paterson & Thurston 1992).

Let M be a monoid which is F P_{∞} with a resolution by free modules P_{n} which are finitely generated for all n. Let P̃_{n} be the corresponding free abelian group discussed in Section 3; this is finitely generated. Since every subgroup of a finitely generated free abelian group is finitely generated, ker ˜∂_{n} will be finitely generated. Thus the homology group H_{n}(M), being a quotient of this, will also be finitely generated. So we have seen that a monoid which is F P_{∞} will have finitely generated homology groups in all dimensions. We can use any resolution to evaluate the homology groups. The bar resolution is too large for efficient calculation of these groups. However, Brown’s theorem gives us a smaller resolution from any convergent rewriting system, even an infinite one. So we may be able to show, using this smaller resolution, that some homology group is not finitely generated; it will then follow that the monoid is not F P_{∞}, and so cannot be given by any finite convergent rewriting system. (More generally, we could use coefficients other than Z, and we could use the cohomology groups rather than the homology groups.) Here Brown’s theorem is of more use than Anick’s and Kobayashi’s theorems, as it gives the boundary operators by a simple formula (of geometric origin), whereas they only give the boundary operators by a complicated inductive formula.

Squier (1987) cites several examples of finitely generated groups with solvable word problem which are not F P_{3}, and hence cannot be presented by any finite convergent rewriting system. These examples belong to families of finitely presented groups with solvable word problems, such that each family contains, for every n ≥ 2, a group which is F P_{n} but not F P_{n+1}. These examples, which will be given later, satisfy Squier’s condition if n > 2, but do not satisfy Anick’s condition.

Squier (1987) also gives explicitly a family of monoids S_{k} for all k ≥ 0, and proves the following facts. Each S_{k} is given by an infinite convergent rewriting system in a form from which one can easily see that the monoid has solvable word problem. S_{0} is not F P_{2}, and so (as remarked below) cannot be presented by any finite rewriting system, even one which is not convergent. For k ≥ 1, S_{k} can be presented by a finite rewriting system (but this system is not convergent). For k ≥ 2, S_{k} is not F P_{3} (this is shown by using the infinite convergent rewriting system to calculate the homology groups), and so S_{k} cannot be presented by any finite convergent rewriting system. The monoid S_{1} is F P_{∞}, but Squier showed in a later paper (published after his death as (Squier et al. 1994); see also (Lafont 1994)) that S_{1} cannot be presented by any finite convergent rewriting system.

It is shown in (Squier 1987) (and also in (Lafont & Prouté 1991); the result was known much earlier than Squier’s paper) that any finitely generated monoid is F P_{1} and any finitely presented monoid is F P_{2}. It is shown in (Bieri 1976) (and elsewhere) that a group which is F P_{1} is finitely generated. This does not hold for monoids, since a monoid which is right F P_{∞} but not left F P_{1} cannot be finitely generated. I do not know if there is a monoid which is both left and right F P_{1} but is not finitely generated. For groups the property F P_{2} is equivalent, as shown in (Bieri 1976), to a property known as almost finitely presented.

6.1. Monoids and Groups; differences and similarities

Our definitions and proofs have been given in terms of right modules, so, strictly speaking, we should refer to to the property of being right F P_{∞}. There will be a similar concept of left F P_{∞}. A monoid with a finite convergent rewriting system will be both right F P_{∞} and left F P_{∞}.

For a group G, any left G-module can be regarded as a right G-module, and conversely, by defining ug = g^{−1}u for any g ∈ G and any u in the module. Thus a group is right F P_{∞} if and only if it is left F P_{∞}, and the same holds for F P_{n}. For monoids the two concepts can differ. It is shown in (Cohen 1992) that there is a monoid which is right F P_{∞} but not even left F P_{1}.

Most of the results on the F P_{∞} and F P_{n} properties hold only for groups. We begin with some results relating the monoid M with presentation ⟨X; R⟩ to the group G with the same presentation. There is a homomorphism i from M to G induced by the inclusion of X^{∗} into F, the free group on X. More precisely, there are, by definition of monoid and group presentations, homomorphisms π : X^{∗} → M and ρ : F → G, and there is a natural inclusion j from X^{∗} to F; we shall sometimes regard j as inclusion, so that it need not be explicitly mentioned. Because the relations of M hold in G, we can define i by iπ = ρj. However, i need not be an inclusion, as is seen by taking X = {a} and R = {(a^{2}, a)}. Lemma 4. Suppose that for any u_{1} and u_{2} in M there are v_{1} and v_{2} in M such that u_{1}v_{1} = u_{2}v_{2}. Then G = (iM)(iM)^{−1}.

Proof. Since G is generated by iX, it is enough to show that (iM)(iM)^{−1} is a subgroup. It is plainly closed under taking inverses. So look at a product (iw_{1})(iu_{1})^{−1}(iw_{2})(iu_{2})^{−1}. By hypothesis, we can find p and q in M such that u_{1}p = w_{2}q. Let u = u_{1}p, v = w_{1}p, and z = u_{2}q. Then the product we are looking at equals (iv)(iu)^{−1}(iu)(iz)^{−1} = (iv)(iz)^{−1}, as required. Lemma 5. To any homomorphism α from M into a group H there is a homomorphism β from G into H such that α = βi. If there is a one-one homomorphism from M into some group, then i is one-one. If α is one-one and M satisfies the conditions of the previous lemma, then β is one-one.

Proof. Define a homomorphism β̂ : F → H by β̂x = απx. For any (l, r) ∈ R, we have πl = πr, and so β̂l = β̂r. It follows that there is a homomorphism β : G → H such that β̂ = βρ. Then βiπ = βϕj = β̂j = απ, and the first part of the lemma follows, as π maps onto M. When α is one-one, we see at once from α = βi that i is one-one. Suppose the condition of Lemma 4 holds. Then to any g ∈ G there are u and v in G such that g = (iu)(iv)^{−1}. Then βg = (αu)(αv)^{−1}. If βg = 1 we get αu = αv. Thus, if α is one-one, then ker β = {1}, and so β is one-one. Lemma 6. Suppose the condition of Lemma 4 holds. Then i is one-one if and only if, for all u, v, w ∈ M, uw = vw implies u = v.

Proof. Let i be one-one, and suppose that uw = vw. Then (iu)(iw) = (iv)(iw). Since G is a group, this implies that iu = iv, and so u = v. Conversely, let M be a monoid satisfying the condition of Lemma 4. Define a relation ∼ on M ×M by (u, v) ∼ (u_{1}, v_{1}) if there are w and w_{1} such that uw = u_{1}w_{1} and vw = v_{1}w_{1}. Then ∼ is obviously reflexive and symmetric, and it is easy to check, using the condition, that it is transitive. Further, to any two equivalence classes A and B there are u, v, w such that A and B are the equivalence classes of (u, v) and (v, w) respectively. Also the class of (u, w) depends only on A and B, not on the choices of u, v, w. Thus we have a multiplication on the set of equivalence classes which (it is easy to see) makes it into a group. This group is isomorphic to G, but we do not need this fact. There is a homomorphism from M into this group which sends u into the class of (u, 1). If u and v have the same image there is some w such that uw = vw. Thus our second hypothesis tells us that this homomorphism is one-one, and so, by the previous lemma, i is one-one.

Lemma 7. Let i be one-one. Then M has solvable word problem if G has solvable word problem. Also, if in addition M satisfies the condition of Lemma 4 then G has solvable word problem if M has solvable word problem.

Proof. Let u and v be in X^{∗}. Then πu = πv iff iπu = iπv iff ρu = ρv. If G has solvable word problem, we can decide whether or not this holds, and so M has solvable word problem. Conversely, suppose that the condition of Lemma 4 holds, and that M has solvable word problem. By the condition, to any a and b in X^{∗} there are c and d in X^{∗} such that π(ac) = π(bd). Since M has solvable word problem, such c and d can be computed from a and b (by testing all pairs until a suitable pair is found). Evidently, we then have ρ(a^{−1}b) = ρ(cd^{−1}). Iterating this procedure, for any w in the free group F we can compute y and z in X^{∗} such that ρw = ρ(yz^{−1}). Thus ρw = 1 iff ρy = ρz, that is, iff iπy = iπz. Since i is one-one, this holds iff πy = πz, and we can decide whether or not this holds, since M has solvable word problem.

The proof of the next lemma is rather complicated, because it is a special case of a general homological result. Readers may prefer to note the statement, but omit its proof.

Lemma 8. Let i be one-one, and let the condition of Lemma 4 hold. If M is F P_{m} for some m with 1 ≤ m ≤ ∞ then G is F P_{m}.

Proof. For convenience of notation, we shall regard i as inclusion, so that we can omit mention of it. An easy induction shows that, for any k and any u_{1}, …, u_{k} ∈ M there are v_{1}, …, v_{k} ∈ M such that u_{1}v_{1} = … = u_{k}v_{k}. It then follows that, for any k and any g_{1}, …, g_{k} ∈ G there are w_{1}, …, w_{k} ∈ M and t ∈ M such that g_{i} = w_{i}t^{−1} for all i. It is then easy to see that any element of ZG can be written as cu^{−1} for some c ∈ ZM and u ∈ M, and, finally, that, for any k, any k elements of ZG can be written as c_{i}u^{−1} for some u ∈ M and c_{1}, …, c_{k} ∈ ZM. Let P be a free ZM -module with basis S. The previous paragraph shows that any element of the free ZG-module with basis S can be written as pu^{−1} for some p ∈ P and u ∈ M. We therefore denote this free ZG-module by P M^{−1}. Let Q be another free ZM -module with basis T, and let ϕ : P → Q be a homomorphism. Then there are elements c_{st} of ZM such that, for all s, ϕs = ∑ tc_{st}, and for each s there are only finitely many t with c_{st} ≠ 0. We may define a ZG-homomorphism ϕM^{−1} : P M^{−1} → QM^{−1} by (ϕM^{−1})s = ∑ tc_{st}. Also, if ϵ is a ZM -homomorphism from P to the trivial module Z, we have integers k_{s} such that ϵs = k_{s}, and again we define ϵM^{−1} to be the ZG-homomorphism from P M^{−1} to the trivial module Z which sends s to k_{s}. It is possible to define P M^{−1} and ϕM^{−1} without reference to a basis, but for our purposes it seems easier to use this definition. It is easy to check that im(ϕM^{−1}) = (im ϕ)M^{−1} and that ker(ϕM^{−1}) = (ker ϕ)M^{−1}, with similar results for ϵ. It follows that any resolution of M by modules P_{n} and homomorphisms ∂_{n} gives rise to a resolution of G by modules P_{n}M^{−1} and homomorphisms ∂_{n}M^{−1}. The lemma is now immediate.

6.2. Examples of Monoids and Groups which are F P_{∞}

6.2.1. Some Easy Examples The simplest case is that of finite monoids. The bar resolution shows at once that any finite monoid is F P_{∞}.

Let M be the free monoid on X. Let P_{0} = ZM and let P_{1} be free on a basis {t_{x}} bijective with X. Define ∂_{1} : P_{1} → P_{0} by ∂_{1}t_{x} = x − 1 and define ϵ as usual. Plainly ϵ∂_{1} = 0. Let 0 ≠ p ∈ P_{1}. We can write p = ∑ t_{x}u_{x}, where u_{x} ∈ ZM and u_{x} = 0 for all but finitely many x. Each u_{x} is a finite sum ∑ n_{xi}m_{xi} with n_{xi} ∈ Z and m_{xi} ∈ M, where i runs over some index set depending on x. Let m_{yj} have the maximum length among all the elements m_{xi} for all x and all associated i. Then ∂_{1}p ≠ 0, since it contains the term n_{yj}ym_{yj}, which cannot cancel against any other term.

Thus M has a resolution with P_{0} and P_{1} as above, with P_{n} = 0 for n > 1. Plainly, then, M is F P_{∞} if X is finite.

A similar, but more complicated, analysis of elements of maximum length can be applied to the free group G on X. It gives a resolution with P_{0} being ZG, P_{1} the free ZG-module with basis {t_{x}}, and P_{n} = 0 for n > 1. Thus the free group on a finite set X is F P_{∞}.

Alternatively, we can regard the free group on X as the monoid with presentation ⟨X∪X̄; (xx̄, 1), (x̄x, 1) for all x⟩. This rewriting system is convergent, so Brown’s theorem tells us that the group is F P_{∞} when X is finite. However, this approach does not show that we can take P_{n} = 0 for n > 1.

The free abelian monoid on {x_{1}, …, x_{n}} is presented by the convergent rewriting system {(x_{j}x_{i}, x_{i}x_{j})} for all j > i. Brown’s theorem tells us that this monoid has a resolution for which P_{k} has basis the set of all k-tuples (x_{j_{1}}, …, x_{j_{k}}) with j_{1} > … > j_{k}. In particular, this monoid is F P_{∞} (and even has P_{k} = 0 for k > n).

By Lemma 8, the free abelian group on a finite set is also F P_{∞}.

Lyndon (1950) shows that a finitely generated group with a single defining relation is F P_{∞}. (Note that here we are looking at group presentations, not monoid presentations, when we say that there is a single defining relation.)

6.2.2. Some Simple Constructions We now look at how various group-theoretic constructions behave with regard to the F P_{n} properties. We will find that various results about F P_{∞} have parallel results about convergent rewriting systems.

The next two results are shown in (Bieri 1976).

Let H be a subgroup of the group G, and let H have finite index in G. Then, for 1 ≤ n ≤ ∞, G is F P_{n} iff H is F P_{n}.

Let K be a normal subgroup of the group G, and let K be F P_{∞}. Then, for 1 ≤ n ≤ ∞, G is F P_{n} iff G/K is F P_{n}. In particular, the direct product of F P_{∞} groups is F P_{∞}.

The following analogues of these for rewriting systems are found in the unpublished paper (Groves & Smith 1989); some of these results are published in (Groves & Smith 1993).

Let H be a subgroup of the group G, and let H have finite index in G. If H has a finite convergent rewriting system then so does G. However, it is not known if H must have a finite convergent rewriting system when G has a finite convergent rewriting system.

Let K be a normal subgroup of the group G. If both K and G/K have finite convergent rewriting systems then so does G. In particular, the direct product of groups with finite convergent rewriting systems has a finite convergent rewriting system.

The following results are immediate from those above. Let G_{0} = {1}, and, for 1 ≤ i ≤ k, let G_{i} be a group containing G_{i−1}. Suppose that, for 1 ≤ i ≤ k, either G_{i−1} has finite index in G_{i} or G_{i−1} is a normal subgroup of G_{i} with G_{i}/G_{i−1} finitely generated and either free or free abelian or with one defining relation. Then G_{k} is F P_{∞}. If the last case is omitted then G_{k} has a finite convergent rewriting system.

The following criterion can be found in (Bieri 1980).

Let G be a finitely presented group which is isomorphic to a subgroup of GL_{n}(Q), the group of invertible n × n matrices with rational coefficients. If G is F P_{∞} then the centre of G, which is defined to be {g ∈ G; gh = hg for all h ∈ G}, is finitely generated.

6.2.3. Further Constructions Two constructions of importance in group theory are the amalgamated free product and the HNN extension. The former constructs a group A∗_{C} B from two groups A and B and a group C which is a subgroup of both. In particular, if C is trivial we get the free product A ∗ B; this has presentation ⟨X ∪ Y; R ∪ S⟩ when A and B have presentations ⟨X; R⟩ and ⟨Y; S⟩ with X and Y disjoint. The latter constructs a group from a group A, a subgroup C and a one-one homomorphism ϕ : C → A.

The following results are found in (Bieri 1976). Here we have 1 ≤ n ≤ ∞, with n − 1 denoting ∞ if n = ∞.

Let G be the amalgamated free product A ∗_{C} B. If A and B are F P_{n} and C is F P_{n−1} then G is F P_{n}. If G and C are F P_{n} then so are A and B. If G is F P_{n} and A and B are F P_{n−1} then C is F P_{n−1}.

Let G be the HNN extension ⟨A, t; t^{−1}Ct = ϕC⟩. If A is F P_{n} and C is F P_{n−1} then G is F P_{n}. If G and C are F P_{n} then so is A. If G is F P_{n} and A is F P_{n−1} then C is F P_{n−1}.

Baumslag & Bieri (1976) define the class of constructible groups to be the smallest class C closed under isomorphisms and such that:

— {1} ∈ C,

— G ∈ C if G has a subgroup H of finite index with H ∈ C,

— an amalgamated free product A ∗_{C} B is in C if A, B, and C are in C,

— an HNN extension ⟨A, t; t^{−1}Ct = ϕC⟩ is in C if A and C are in C.

From the previous discussions, it is immediate that all constructible groups are F P_{∞}. Those constructible groups which are solvable (also called soluble; this means that some term of the derived series is trivial, and it has no connection with having a solvable word problem) are characterised in (Baumslag & Bieri 1976). It is shown in (Groves & Smith 1989) that all constructible solvable groups have finite convergent rewriting systems. This paper also gives sufficient conditions for an amalgamated free product or an HNN extension to have a finite convergent rewriting system.

Let Γ be a finite graph, and suppose that, for each vertex i ∈ Γ, we have a group G_{i} with presentation ⟨X_{i}; R_{i}⟩. The graph product of the groups is defined to be the group with presentation ⟨⋃ X_{i}; ⋃ R_{i} ∪ S⟩, where S = {xyx^{−1}y^{−1} for all x ∈ X_{i}, y ∈ X_{j} and i adjacent to j}. This can be shown to depend only on the graph and the groups, not on the presentations chosen. The similar construction for monoids is called a partially commutative monoid.

The graph product can be constructed from direct products and amalgamated free products in a simple way, giving the next result (Cohen 1995).

The graph product of F P_{∞} groups is F P_{∞}. It is shown in (Hermiller & Meier 1994a) that convergent rewriting systems on the vertex groups (or monoids) give rise, in a natural way, to a convergent rewriting system on the graph product, and this is finite if the original rewriting systems are finite.

6.3. Examples of Groups which are not F P_{∞}

6.3.1. Bieri’s groups A_{n} and B_{n} We need to begin with the notion of the split extension of one group by another. We define an action of the group G on the group H as a function from G × H to H, denoted by ·, such that

— g · (hh_{1}) = (g · h)(g · h_{1}) for all g ∈ G and h, h_{1} ∈ H,

— (gg_{1}) · h = g · (g_{1} · h) for all g, g_{1} ∈ G and h ∈ H,

— g · 1_{H} = 1_{H} for all g ∈ G, where 1_{H} is the identity element of H,

— 1_{G} · h = h for all h ∈ H, where 1_{G} is the identity element of G. Equivalently, an action of G on H is a homomorphism from G to the group of automorphisms of H.

Given an action of G on H, the split extension of H by G is the group whose underlying set is H × G with the multiplication defined by (h, g)(h_{1}, g_{1}) = (h(g · h_{1}), gg_{1}). It is easy to see that this multiplication makes H × G a group, and that this group contains a subgroup isomorphic to G and a normal subgroup isomorphic to H. The intersection of these subgroups is trivial and their product is the whole group.

We now apply this construction. Let D_{n} = ⟨x_{1}, y_{1}⟩×…×⟨x_{n}, y_{n}⟩, the direct product of n free groups of rank 2. Let F be the free group of countable rank with basis {a_{k}; k ∈ Z, and let Z[1/d], where d is an integer greater than 1, be the set of rational numbers of the form r/d^{s} for some r ∈ Z and s ∈ N. We may specify an action of D_{n} on either of these groups by specifying how the generators act, and any action of these generators extends to an action of D_{n} if it respects the relations. In particular, we have an action of D_{n} on F given by x_{i} · a_{k} = a_{k+1} = y_{i} · a_{k} for all k ∈ Z and 1 ≤ i ≤ n and an action of D_{n} on Z[1/d] by x_{i} · q = dq = y_{i} · q for all q ∈ Z[1/d] and 1 ≤ i ≤ n. Let A_{n} and B_{n} be the corresponding split extensions.

Then A_{n} and B_{n} have normal subgroups isomorphic to F and Z[1/d] respectively, the quotient groups being D_{n} in each case. It is then easy to see that both A_{n} and B_{n} have solvable word problem. It is also easy to check that (for instance), for any j, the relation x_{2} · a_{j} = a_{j+1} can be derived from the relations x_{2} · a_{0} = a_{1}, x_{2}x_{1} = x_{1}x_{2}, and, for all k, x_{1} · a_{k} = a_{k+1}. As a result, we find that A_{n} has a finite presentation with generators x_{1}, y_{1}, …, x_{n}, y_{n} and a with the relations x_{i}x_{j} = x_{j}x_{i}, y_{i}y_{j} = y_{j}y_{i}, x_{i}y_{j} = y_{j}x_{i} for 1 ≤ i < j ≤ n, and x_{i}ax_{i}^{−1} = x_{1}ax_{1}^{−1}, y_{i}ay_{i}^{−1} = x_{1}ax_{1}^{−1} for 1 ≤ i ≤ n. Similarly B_{n} has a finite presentation with the same generators as A_{n}, and with the relations of A_{n} and one additional relation z_{1}ax_{1}^{−1} = a^{d}. It is shown in (Bieri 1976) that both A_{n} and B_{n} are F P_{n} but not F P_{n+1}. It is these examples that Squier uses.

6.3.2. Abels’ group G_{n} Let p be a prime, and let Z1/p be the ring consisting of all rational numbers of form r/p^{n}.

The group GL_{n}(Z[1/p]) consists of those n × n matrices with entries in Z[1/p] which have an inverse of the same form. Let G_{n} be the subgroup of GL_{n+1}(Z[1/p]) which consists of those matrices A = (a_{ij}) with a_{11} = 1 = a_{n+1,n+1} and a_{ij} = 0 for i > j. As a matrix group, A has solvable word problem. Brown shows that, for n > 2, G_{n} is finitely presented and F P_{n−1} but not F P_{n}.

We can find an explicit finite presentation of G_{n}. It is a split extension of the group T of unitriangular matrices (that is, matrices with a_{ii} = 1 for all i and a_{ij} = 0 for i > j) by the group of those diagonal matrices which are in G_{n} (that is, a_{ij} = 0 for i ≠ j and a_{11} = 1 = a_{n+1,n+1}). For 1 ≤ k ≤ n, let T_{k} be the subgroup of T consisting of those matrices in T such that a_{ij} = 0 for 1 ≤ j − i ≤ k. Then T_{k+1} is a normal subgroup of T_{k} such that the quotient T_{k}/T_{k+1} is the direct sum of n + 1 − k copies of Z[1/p], regarded as a group under addition.

Now, if P is a group with a normal subgroup Q it is easy to find a presentation of P from presentations of Q and P/Q. Thus we can find inductively an (infinite) presentation of each T_{k}. This leads to an infinite presentation of T, and then of G_{n}. A finite presentation of G_{n} can be found from its infinite presentation by routine but tedious manipulations. Details are left to the reader. Abels (1979), who first discussed the group G_{3}, gives a group presentation (not a monoid presentation) of G_{3} with five generators and thirteen relations.

6.3.3. Brown’s group H_{n} Brown (1987) gives conditions under which a group acting on a space is F P_{∞}, and under which it is F P_{n} but not F P_{n+1}. In (Brown 1984) he discusses circumstances under which such a group is finitely presented. When the action is given in sufficient detail, a finite presentation can be explicitly determined, but it is often quite complicated to do so. The proofs of his results require a considerable knowledge of homological methods. The statements, however, are not difficult to understand. In particular, the statements of Corollary 3.3 of (Brown 1987) and Theorem 3 of (Brown 1984) require very little technical knowledge. His examples include the following ones.

Let H_{n} be the group of those permutations α of N × {0, …, n − 1} for which there are integers m_{0}, …, m_{n−1} such that, for 0 ≤ i ≤ n − 1 and all sufficiently large x ∈ N, we have α(x, i) = (x + m_{i}, i). It is easy to see that the function sending α to (m_{0}, …, m_{n−1}) is a homomorphism. The kernel of this homomorphism is isomorphic (by means of the bijection from N × {0, …, n − 1} to N which sends (k, i) to kn + i) to the group of those permutations of N which fix all but finitely many elements.

Given α, choose k so that α(x.i) = (x + m_{i}, i) for x > k and 0 ≤ i ≤ n − 1. Since α is a permutation, it maps ⋃_{i}{(x, i); x ≤ k} bijectively onto ⋃_{i}{(x, i); x ≤ k + m_{i}}. Hence the image of the homomorphism is contained in {(m_{0}, …, m_{n−1}; ∑ m_{i} = 0}. That the image is precisely this set is easily seen, using the permutations α_{i} for which

α_{i}(x, 0) = (x + 1, 0), α_{i}(0, i) = (0, 0), α_{i}(x + 1, i) = (x, i), α_{i}(x, j) = (x, j) for all i ≠ 0, i.

From this we can easily see that H_{n} has solvable word problem. It is shown in (Brown 1987) that, for n > 2, H_{n} is finitely presented and is F P_{n−1} but not F P_{n}. In principle, Brown’s results could be used to find an explicit finite presentation of H_{n}, but it may be easier to use the technique sketched below.

We begin with presentations ⟨X_{k}; R_{k}⟩ of the finite symmetric groups S_{k} (for instance, that in 6.28(1) of (Coxeter & Moser 1958), or one of the other presentations given in (Coxeter & Moser 1958)). If these are chosen so that X_{k} ⊆ X_{k+1} and R_{k} ⊆ R_{k+1}, then ⟨⋃ X_{k}; ⋃ R_{k}⟩ is an infinite presentation of the group of all permutations of N which move only finitely many elements. This a normal subgroup of H_{n}, and we have described the quotient group, which has an obvious presentation. As in the discussion of Abels’ group, this leads easily to an infinite presentation of H_{n}, and routine but complicated calculations enable us (with the aid of the permutations α_{i} defined above) to replace this by a finite presentation. The details are left to the reader.

6.4. Further Monoids and Groups which are F P_{∞}

The first of these is the monoid M presented on X = {x_{i}, all i ∈ N} by the rewriting system {(x_{j}x_{i}, x_{i}x_{j+1}) for all i, j with i < j}, and the group F with the same presentation. The history of this group is discussed in (Brown 1987) and (Brown 1992b). The rewriting system is evidently convergent, and so M has solvable word problem. It is easy to check that the irreducible words of X^{∗} are exactly the words x_{i_{1}} … x_{i_{k}} for all k and all i_{1}, …, i_{k} with i_{1} ≤ … ≤ i_{k}. We can then see easily that M satisfies both hypotheses of Lemma 6. It follows, by Lemma 7, that F also has solvable word problem. Brown shows by topological methods in (Brown 1987) that F is F P_{∞}, and he indicates how the topological proof can be turned into an algebraic one. A slightly different proof is given in (Brown & Geoghegan 1984). Further discussion in (Brown 1992b) makes it clear (though this is not stated explicitly) that M is F P_{∞}; the proof in (Brown 1992b) that F is F P_{∞} is that of Lemma 8, stated in a more abstract homological version.

We will show that F can be finitely presented. This result is stated in the references cited, but the proof is left to the reader. As it is slightly messy, but still managable by hand, I give the details here. By contrast, M is right F P_{∞} but is shown in (Cohen 1993) not to be left F P_{1} so it is not even finitely generated.

For k > 0 let r_{k} be the relation x_{0}^{−1}x_{k}x_{0} = x_{k+1}, for k > 1 let s_{k} be the relation x_{1}^{−1}x_{k}x_{1} = x_{k+1}, and for k ≥ 0 let t_{k} be the relations x_{k}^{−1}x_{k+1}x_{k} = x_{k+2}; in particular, r_{1} is the same as t_{0} and s_{2} is the same as t_{1}.

It is easy to see that, for 0 < i < j, the relation x_{i+1}^{−1}x_{j+1}x_{i+1} = x_{j+2} can be derived from r_{i}, r_{j}, r_{j+1} and the relation x_{i}^{−1}x_{j}x_{i} = x_{j+1}. It follows that all the relations can be derived from {r_{k}; k > 0} ∪ {s_{k}; k > 1}. It is also clear that, for k > 0, r_{k+2} can be derived from r_{k}, r_{k+1}, t_{k} and t_{k+1}, and that, for k > 1, s_{k+2} can be derived from s_{k}, s_{k+1}, t_{k} and t_{k+1}. Thus we may take for the defining relations of F the relations t_{k} for all k ≥ 0 together with the relations r_{2} and s_{3}. The relations t_{k} for k > 2 can be used to eliminate the generators x_{k} for k > 4. We get a finite presentation of F with generators x_{i} for 0 ≤ i ≤ 4 and relations r_{2}, s_{3}, t_{0}, t_{1} and t_{2}. If we prefer, the relation s_{3} can be replaced by the relation x_{1}^{−1}x_{3}x_{1} = x_{0}^{−1}x_{3}x_{0}. Each of these finite presentations can easily be replaced by presentations on the two generators x_{0}, x_{1}.

Guba & Sapir (1995) show that this group, regarded as a monoid on the generators x_{0}, x_{1}, x̄_{0}, x̄_{1} can be given by a convergent rewriting system which is regular (it is still unknown whether it has a finite convergent rewriting system).

There is a family of groups, which arise as groups of homeomorphisms or as automorphism groups, all of which are finitely presented infinite simple groups which are F P_{∞}. Some of the properties of these groups are obtained in (Brown 1992b). In (Brown 1992a) one of these groups is exhibited explicitly in a way from which a finite presentation can easily be derived.

Brown (1992a) defines a triangle of groups to consist of three groups G_{i} for i = 1, 2, 3 together with a subgroup G_{ij} of G_{i} for i ≠ j and isomorphism from G_{ij} to G_{ji} for 1 ≤ i < j ≤ 3. Let G_{i} have presentation ⟨X_{i}; R_{i}⟩, where X_{i} ∩ X_{j} = ∅ for i ≠ j. Let Y_{ij} be a subset of the free group on X_{i} whose image in G_{i} generates G_{ij}, and let these sets be chosen so that the isomorphism from G_{ij} to G_{ji} is induced by a bijection from Y_{ij} to Y_{ji}. Brown defines the triangle product in a way that depends on the groups but not on their presentations. However, it is easy to see from his definition that this triangle product has presentation ⟨X_{1} ∪ X_{2} ∪ X_{3}; R_{1} ∪ R_{2} ∪ R_{3} ∪ S⟩, where S consists of all y_{ij}y_{ji}^{−1} where i < j, y_{ij} ∈ Y_{ij}, and y_{ji} corresponds to y_{ij} in the bijection between Y_{ij} and Y_{ji}.

The triangle product is defined in a similar way to the amalgamated free product (which uses two groups rather than three, with the obvious modifications). But they behave very differently. The amalgamated free product always contains copies of the original groups, whereas the triangle product of non-trivial groups can be trivial.

Brown shows that one of the groups he considered can be described as a triangle product of symmetric groups of degrees 5, 6, and 7 in the following way. Let G_{1} be the group of all permutations of the set {a, b, c, d, e}, let G_{2} be the group of all permutations of {a, b, c, d, e_{0}, e_{1}}, and let G_{3} be the group of all permutations of {a, b, c, d_{0}, d_{1}, e_{0}, e_{1}}. Let G_{12} be the subgroup of G_{1} fixing e, G_{21} the subgroup of G_{2} fixing both e_{0} and e_{1}, G_{23} the subgroup of G_{2} fixing d, and G_{32} the subgroup of G_{3} fixing both d_{0} and d_{1}, the isomorphisms being the obvious ones. Let G_{13} be the subgroup of G_{1} which preserves the sets {a, b, c} and {d, e}. Thus G_{13} is the direct product of the group of permutations of {a, b, c} by a cyclic group of order 2 whose non-trivial element is the permutation (d e). Finally, G_{31} is to be the direct product of the group of permutations of {a, b, c} by the cyclic group of order 2 whose non-trivial element is (d_{0} e_{0})(d_{1} e_{1}).

From this description, it is routine to obtain a presentation of the triangle product. We could use various presentations of the symmetric group to get a number of presentations of the triangle product.

7. Brown’s Theorem

Brown showed that, in circumstances to be given shortly, a complex (either in the algebraic sense of this paper or in a topological sense) can be replaced by a smaller complex which is equivalent, in a suitable sense, to the original complex. In particular, in the algebraic setting, if the original complex is a resolution then so is the smaller complex. Brown proved his result in a topological setting. A translation of his proof to the algebraic setting was given in (Cohen 1993). If we are content to prove the result for resolutions, which will be enough to obtain Anick’s result, then the algebraic proof can be further simplified, and this simplified proof will be given in this section.

7.1. The Topological Background

Let T be a triangle (edges and interior), let T_{1} be the union of two of its edges, and let T_{2} be the third edge. It is easy to see that T can be deformed (pushed down, collapsed) into T_{1}, by moving each point in a direction perpendicular to T_{2}.

Let X be a space and let Y be the space obtained by attaching T to X along T_{1}. More precisely, let f : T_{1} → X be a map, and let Y be obtained from the disjoint union of X and T by identifying t with ft for all t ∈ T_{1}. Then the collapsing of T into T_{1} can be extended to a collapsing of Y into X. Thus Y and X are homotopy equivalent, and so have the same homology. We call T_{2} a redundant edge with corresponding collapsible triangle T.

This can obviously be extended to higher dimensions; T could be a tetrahedron, T_{2} one of its faces, and T_{1} the union of its other faces, or, more generally, T could be a cell (simplex) of arbitrary dimension and T_{1} the union of all but one of its faces. Further, there is no need to add just one cell (simplex); we can add an arbitrary number of cells (possibly infinite) at once, and Y will still collapse into X.

We can proceed further, attaching new collapsible and redundant cells to Y (by means of maps into Y which are not maps into X), and so on. We get a sequence of spaces,

X = Y_{0} ⊆ Y_{1} ⊆ Y_{2} ⊆ …,

where each Y_{n} is obtained by adding collapsible and redundant cells to Y_{n−1}.

Then, as before, each Y_{n} collapses into Y_{n−1}, and, inductively, Y_{n} collapses into X. Let Y_{∞} = ⋃ Y_{n}. A subtler argument shows that Y_{∞} is homotopy equivalent to X.

A further generalisation is now needed. We are often given a space Y, which we want to regard as coming from a simpler space X by adding cells in various stages. That is, we have a sequence

X = Y_{0} ⊆ Y_{1} ⊆ Y_{2} ⊆ …,

where each Y_{n} is obtained by adding cells to Y_{n−1}, and Y = ⋃ Y_{n}. In this situation, we will not expect that all the cells added to Y_{n−1} to form Y_{n} will be collapsible or redundant; we call the remaining cells essential. Brown’s topological theorem states that Y is homotopy equivalent to a space Z obtained from X by adding, for each k, one k-cell for each essential k-cell occurring somewhere in the sequence (and, further, the attaching map can be constructed).

This topological idea translates to the algebraic notion of a collapsing scheme which will shortly be defined. All our proofs are given in the algebraic setting.

7.2. Collapsing Schemes and Resolutions

Let P be an augmented free chain complex. We specify a basis for each P_{n}, and we call the elements of this basis n-cells. A collapsing scheme for P consists of the following:

(1) a division of the cells into three disjoint classes, called the essential, redundant, and collapsible cells, with all 0-cells being essential, and all 1-cells being either essential or redundant,

(2) a function, called height, from the set of all redundant cells into N,

(3) a bijection between the set of redundant n-cells and the set of collapsible (n + 1)-cells such that, when c is the collapsible cell corresponding to the redundant cell r, for one of the two choices of sign any redundant cell occurring in r ± ∂c has smaller height than r. A collapsing scheme on a resolution (not on an arbitrary complex) is called strong if

it satisfies the following extra condition:

(4) there is a contracting homotopy σ such that, for any collapsible chain x and any m ∈ M the chain σ(xm) is collapsible. We shall see later how this notion arises in the bar resolution. Usually the height function is given implicitly and not explicitly. That is, we replace

conditions (2) and (3) by (2′) for each n, a noetherian relation > on the set of redundant n-cells, (3′) a bijection between the set of redundant n-cells and the set of collapsible (n+1)-cells

such that, when c is the collapsible cell corresponding to the redundant cell r, for one of the two choices of sign any redundant cell r′ occurring in r ± ∂c has r > r′. For the rest of the theory we will assume that the sign in ± is always −. This can be

achieved simply by replacing c by −c for some collapsible cells to get a new basis. In the explicit construction given later, however, it is preferable to use ± because there is a natural choice of the cells.

König’s Lemma and its preceding remarks, applied to the relation ≻ given by r ≻ r′ if r′ occurs in r −∂c, show that, when (1), (2′) and (3′) hold, there will be a height function satisfying (2) and (3). Note that we only need to compare redundant cells of the same dimension. Theorem 2. (Brown’s Theorem) If a free resolution has a (strong) collapsing scheme, then there is a free resolution which in dimension n has as basis the essential n-cells; also the boundary operator in dimension n is determined by the original boundary operator in dimension n and the collapsing scheme in dimensions n − 1 and n. Every strongly minimal convergent rewriting system ⟨X; R⟩ gives rise to a strong collapsing scheme for the normalised bar resolution of the monoid presented by the rewriting system in such a way that the essential 1-cells and 2-cells are bijective with X and R respectively, and there are only finitely many essential cells in each dimension if the rewriting system is finite.

The theorem is true for any collapsing scheme, but the proof for a strong collapsing scheme is slightly easier, and is all that we need, so we will only prove this case. The proof of the theorem will take the rest of this section.

Let P be a resolution with a collapsing scheme. We call a chain essential, redundant or collapsible if all its cells are essential, redundant or collapsible, respectively. We denote by E_{n} the set of all essential n-chains. The resolution we construct will have E_{n} as its set of n-chains, but it will take some work to define the boundary operators.

We begin by defining a homomorphism θ_{n} : P_{n} → P_{n}. For a redundant cell r with corresponding collapsible cell c we let θr = r − ∂c (as usual, we omit subscripts wherever this does not cause confusion), we let θe = e for any essential cell e, and we let θc′ = 0 for any collapsible cell c′.

We define the height of a chain to be −1 if the chain has no redundant cells, and to be the maximum height of its redundant cells if it has any such cells. It is easy to see that if x is a chain of height k ≥ 0 then θx has height less than k. It follows that (even if k = −1) θ^{k+1}x has no redundant cells, θ^{k+2}x is essential, and θ^{m}x = θ^{k+2}x for m ≥ k + 2.

We define ϕx to be θ^{m}x for any m ≥ k + 2. Then ϕ_{n} can be regarded either as a homomorphism from P_{n} to itself or as a homomorphism from P_{n} to E_{n}; we rely on the context to determine which is meant.

We define δ_{n} : E_{n} → E_{n−1} by δ_{n} = ϕ_{n−1}∂_{n}. Proposition 1. The modules E_{n} and homomorphisms δ_{n} form an augmented free chain complex.

Proof. Observe first that to any n-chain x there is a collapsible n-chain y and a collapsible (n + 1)-chain z such that x − θx = ∂y + z. For this holds for all chains if it holds for all cells. However, if x is essential we may take y = 0 and z = 0, if x is redundant we may take z = 0 and y the collapsible cell corresponding to x, while if x is collapsible we take y = 0 and z = x. Since ϕx = θ^{m}x for some m, it is immediate that for each x

x − ϕx = ∂y + z for some collapsible y, z  (†)

Since z is collapsible, there will be a redundant u such that ∂z = u − θu. Hence ϕ∂(∂y + z) = ϕ∂z = ϕ(u − θu) = 0, since ∂∂ = 0, and, by definition of ϕ, ϕθ = ϕ. It follows that

ϕ∂x = ϕ∂ϕx.  (‡)

Since all 0-cells are essential, ϕ_{0} is the identity, and ϵδ_{0} = ϵ∂_{0} = 0. Also, by the above, δδ = ϕ∂ϕ∂ = ϕ∂∂ = 0, as required.

The first part of Brown’s theorem is completed by the following proposition. Proposition 2. Suppose that the collapsing scheme is strong. Define τ_{n} : E_{n} → E_{n+1} by τ = ϕσ. Then τ is a contracting homotopy for the complex of essential chains, and so this complex is a resolution.

Proof. We begin by showing that ϕσϕ = ϕσ. So take any chain u. By † there are collapsible chains y and z such that u − ϕu = ∂y + z. Thus ϕσu−ϕσϕu = ϕσ(∂y +z). By hypothesis, σz is a collapsible chain, and so ϕσz = 0. Because σ is a contracting homotopy, we have ϕσ∂y = ϕy − ϕ∂σy. Now ϕy = 0, because y is collapsible. By hypothesis, σy is a collapsible chain, and so there is a redundant chain w with ∂σy = w − θw. As ϕθ = ϕ, we see that ϕσu − ϕσϕu = 0, as required.

Now, for any essential chain x, (τδ + δτ)x = (ϕσϕ∂ + ϕ∂ϕσ)x, by definition, and this, by the result just shown and ‡, equals (ϕσ∂ + ϕ∂σ)x = ϕx, because σ is a contracting homotopy. Since x is essential, we have ϕx = x, which shows that τ is a contracting homotopy.

It is not difficult to prove the result for all collapsing schemes. Since we do not need it, the details will be left to the reader. One needs to use (†), and to begin by proving that for a non-zero collapsible chain x the chain ∂x is non-zero.

7.3. Rewriting Systems and Collapsing Schemes

Let R be a strongly minimal convergent rewriting system on the set X. Let M be the monoid with presentation ⟨X; R⟩. Brown shows how to obtain from R a collapsing scheme on the normalised bar resolution of M. We shall follow the account in (Brown 1992b). The details are given here only to make the current paper self-contained.

Even when R is infinite, the collapsing scheme may be simple enough to enable calculations to be made in the resolution by essential cells. We may then be able to prove that M has an infinitely generated homology group in some dimension, and so cannot be F P_{∞}, and therefore cannot be given by any finite convergent rewriting system.

We will regard the elements of M as the irreducible elements of X^{∗}. If u and v are in M the product uv may be reducible. We will denote by u × v the irreducible element obtained from uv; thus u × v is the product in M of u and v.

The construction is somewhat complicated, so we will look explicitly at the lowdimensional cases first.

Let v ∈ M − X. Then in X^{∗} we have v = xu for some x ∈ X and u ∈ M. As indicated in the topological bachground material, we are thinking of the cells as being added in stages. Since u is simpler than v, it is natural to expect that u will already be present when we want to add v.The 2-cell (x, u) has boundary (x)u − (x × u) + (u). Since xu is irreducible, v = x × u, and the second term in the boundary is the 1-cell (v), while the third term is (u), which is already present. We therefore say that (v) is a redundant cell whose corresponding collapsible cell is (x, u). The essential 1-cells will be the cells (x) for x ∈ X.

By analogy with the 1-dimensional case, with v as above and any w, the 2-cell (v, w) is to be redundant, with corresponding collapsible 3-cell (x, u, w). The boundary of this cell is (x, u)w − (x, u × w) + (x × u, w) − (u, w). Here the third term is our 2-cell (v, w), while (x, u) is collapsible. The other two terms may be collapsible, essential, or redundant (or zero, since we are working in the normalised bar resolution, if u × w = 1). We will have to define the partial ordering on redundant cells so that these two precede (u, v) if they are redundant.

We still have to consider 2-cells of the form (x, w). Such a cell will, by our earlier discussion, be collapsible if xw is irreducible.

Suppose that xw is reducible. If no proper subword is reducible (equivalently, if xw is the left side of an element of R), then there is no natural way of associating a 3-cell with (x, w), and we therefore call this cell essential.

Now suppose that some proper subword of xw is reducible. Since w is irreducible, we can write w = pq, where xp is the left-hand side of an element of R. We now define (x, w) to be redundant, with corresponding collapsible 3-cell (x, p, q). Its boundary is (x, p)q − (x, p × q) + (x × p, q) − (p, q). Here the second term is our redundant cell (x, w), while (x, p) is essential. The other two terms can be of any type. We must define our partial ordering so that they precede (x, w) if they are redundant.

We now look at arbitrary dimensions. Recall that the n-cells are the n-tuples (u_{1}, …, u_{n}) with u_{i} ∈ M − {1} for all i, and that, if u_{i} = 1 for some i then (u_{1}, …, u_{n}) denotes 0.

The cell (u_{1}, …, u_{n}) is defined to be essential if

i) u_{1} ∈ X, ii) for all i < n, u_{i}u_{i+1} is reducible, iii) for all i < n, no proper prefix of u_{i}u_{i+1} is reducible.

It is obvious that there are only finitely many essential cells in each dimension if R is finite, and so Brown’s analysis provides a proof that a monoid with a finite convergent rewriting system is F P_{∞}.

Let u_{1} ∉ X, and write u_{1} = xv for some x ∈ X. Then the cell (u_{1}, …, u_{n}) is to be redundant, with corresponding collapsible cell (x, v, u_{2}, …, u_{n}). We say that the level of this redundant cell is 1.

Now let u_{1} ∈ X. We say that (u_{1}, …, u_{n}) has level i if i is as large as possible subject to (u_{1}, …, u_{i−1}) being essential; note that i > 1. Thus an essential cell has level n + 1, and a non-essential cell has level at most n. If the cell is not essential, (u_{1}, …, u_{i−1}) is essential but (u_{1}, …, u_{i}) is not, and so either u_{i−1}u_{i} is irreducible or some prefix of it is reducible. In the first case we call the cell collapsible, in the second case we call it redundant.

Suppose that (u_{1}, …, u_{n}) is redundant of level i. Write u_{i} as vw, where v is as short as possible subject to u_{i−1}v being reducible. Then the cell (u_{1}, …, u_{i−1}, v) is essential, and so (u_{1}, …, u_{i−1}, v, w, u_{i+1}, …, u_{n}) is easily seen to be collapsible. We define a function from redundant cells to collapsible cells by letting this collapsible cell correspond to the redundant cell (u_{1}, …, u_{n}).

It is easy to see that this is a bijection between the set of redundant n-cells and the set of collapsible (n+1)-cells, and that every collapsible cell comes from a redundant cell of one level lower.

We still need to define a relation >_{n} on the n-cells (it is convenient to define >_{n} on all n-cells, though we only need it on the redundant ones) and show that (3′) holds.

In X^{∗}, we say that v is a subword of w, and write w ⇒ v, if w = pvq for some words p and q which are not both empty (though one may be). We define w > v to mean that either w →^{+} v (in the sense of the rewriting system) or w ⇒ v. Since R is noetherian, and ⇒ is obviously noetherian, Lemma 2 tells us that > is noetherian.

When b denotes the cell (u_{1}, …, u_{n}), we let W (b) be the element u_{1} … u_{n} of X^{∗}, and we let i(b) be the level of b.

Let b and b′ be n-cells. We say that b >_{n} b′ if either W (b) > W (b′) or W (b) = W (b′) and i(b) < i(b′). Since > is noetherian, and i(b) and i(b′) are at most n + 1, we see easily that >_{n} is also noetherian.

Let c = (u_{1}, …, u_{n}) be a collapsible n-cell of level i + 1 with corresponding redundant (n − 1)-cell r of level i. We have ∂_{n0}c = (u_{2}, …, u_{n}) and ∂_{nn}c = bu_{n}, where b = (u_{1}, …, u_{n−1}). Both W (∂_{n0}c) and W (b) are subwords of W (c).

For 0 < j < n, ∂_{nj}c = (u_{1}, …, u_{j−1}, u_{j} ×u_{j+1}, …, u_{n}). By the definition of level and of essential, u_{i}u_{i+1} is irreducible, while u_{j}u_{j+1} is reducible for 0 < j < i. In particular, we have W (r) = W (c). Since u_{j}u_{j+1} reduces to u_{j} ×u_{j+1}, we see that if u_{j}u_{j+1} is reducible, then W (c) →^{+} W (∂_{nj}c); in particular, this holds for 0 < j < i, and may hold for some j > i. When j > i and u_{j}u_{j+1} is irreducible, we have W (c) = W (∂_{nj}c). Also, for j > i, ∂_{nj}c begins with u_{1}, …, u_{i} as does c itself, and so its level is at least i + 1.

Thus ∂c has one entry ±r, while all its other cells (whether redundant or not) are <_{n} r, and we have the final condition (3′) for a collapsing scheme.

Brown goes on to discuss methods of calculating the boundary maps, giving several examples. This material is easy to follow, now that we have made the general algebraic construction; readers are strongly recommended to look at these examples in (Brown 1992b).

Brown & Geoghegan (1984) discuss the monoid M presented on generators {x_{n}; n ∈ N} by the convergent rewriting system {(x_{j}x_{i}, x_{i}x_{j+1}); all i, j with i < j}. The general analysis of the collapsing scheme associated with a convergent rewriting system shows that M has a resolution whose basis in dimension n is the set of all cells (x_{j_{1}}, …, x_{j_{n}}). They show that there is a further collapsing scheme on this resolution for which there are exactly two essential cells in each dimension. Thus M is F P_{∞}, as previously remarked.

7.4. An Alternative Ordering

There is a variation of the definitions and proofs, which will be useful in the next section.

When b is an n-cell, and u ∈ M, we call bu an n-term. We call a term redundant, essential, or collapsible if the corresponding cell is redundant, essential, or collapsible. We modify the definition of a collapsing scheme to allow for a height function, or a partial ordering, on terms rather than cells. Precisely, we replace (2′) and (3′) by (2′′) for each n, a noetherian relation > on the set of redundant n-terms, (3′′) a bijection between the set of redundant n-cells and the set of collapsible (n + 1)-

cells such that, when c is the collapsible cell corresponding to the redundant cell r, for one of the two choices of sign any redundant term r′u′ occurring in ru ± ∂cu has ru > r′u′. It is easy to check that, with this variant definition, all the previous results apply, and

once again a collapsing scheme gives rise to a resolution whose chains have as basis the essential cells.

We now associate with a convergent rewriting system a collapsing scheme in this new sense.

We change the definition of ⇒, and now define w ⇒ v if w = vq for some non-empty q. As before, we define w > v to mean that either w →^{+} v (in the sense of the rewriting system) or w ⇒ v, using this new sense of ⇒. Then > will be noetherian. Let ≫ be the transitive closure of >.

Fo a term bu, we define W (bu) and i(bu) to be W (b)u and i(b). We get a noetherian relation >_{n} on the n-terms by bu >_{n} b′u′ if either W (bu) > W (b′u′) or W (bu) = W (b′u′) and i(bu) < i(b′u′).

As before, let c = (u_{1}, …, u_{n}) be a collapsible n-cell of level i + 1 with corresponding redundant (n − 1)-cell r of level i; let u ∈ M. With our new definition, we still have ∂_{ni}(cu) = ru and W (ru) = W (cu), and we have ru >_{n−1} ∂_{nj}(cu) for 0 < j < n and j ≠ i. If u_{n}u is reducible, we have W (cu) > W (∂_{nn}(cu)), while if u_{n}u is irreducible, then we have W (cu) = W (∂_{nn}(cu)) and i(∂_{nn}(cu)) ≥ i + 1 > i(ru), so we also have ru >_{n−1} ∂_{nn}(cu). Thus we have a collapsing scheme in the new sense.

We also note that any term t, of whatever kind, occurring in θ(ru) satisfies W (ru) ≫ W (t) or W (ru) = W (t).

It is then immediate that, for any term t and any term t′ occurring in ϕt we have either W (t) ≫ W (t′) or W (t) = W (t′).

We now consider an essential n-term eu, where e = (u_{1}, …, u_{n}). Suppose that v = u_{n}u is irreducible, and let e′ = (u_{1}, …, u_{n−1}), which is an essential cell. Then e′v = ∂_{nn}(cu), and W (e′v) = W (eu). Also, because e is essential, u_{j}u_{j+1} is reducible for 0 < j < n, and we see that W (eu) > W (∂_{nj}(eu)). Also, W (eu) ⇒ W (∂_{n0}(eu)). Hence W (e′v) > W (∂_{nj}(eu)) for 0 ≤ j < n.

Since δ = ϕ∂, we see, from the remarks previously made about ϕ, that δ(eu) = e′v + q, where any term t in q satisfies W (e′v) ≫ W (t), and W (e′v) = W (eu).

Now suppose that u_{n}u is reducible. Then ∂_{nn}(eu) = (u_{1}, …, u_{n−1})w, where w = u_{n}×u. Thus W (eu) > W (∂_{nn}(eu)). So any term t in ∂(eu) has W (eu) > W (t). As before, it follows that any term t′ in δ(ey) has W (eu) ≫ W (t′).

We shall need these results in the next section.

8. Comparison with Other Approaches

In this section, we shall show that our approach leads to the same resolutions as the ones found by Kobayashi, Anick, and (up to dimension 3) by Squier. Note that we will use brackets [ and ] as a means of grouping expressions together, because we are using the parentheses ( and ) in the notation for essential cells; this will be done except for a few occasions when we need several levels of grouping. We need a notation because some of our functions are homomorphisms of abelian groups, not of modules; if f is such a function and e is a cell, we need to distinguish between f(eu) and (fe)u.

8.1. Kobayashi’s Method

Kobayashi’s definition uses as basis for the chains what we have called the essential cells. However, he uses an inductive definition for the boundary operator d_{n} and the contracting homotopy t_{n}. (Our notation is slightly different from his, in order to be consistent with that of section 6.) We shall use the definition of > given in subsection 6.3. He defines

d_{1}(x) = x − 1

and, when u = x_{1} … x_{n},

t_{0}u = ∑(x_{i})x_{i+1} … x_{n}.

Suppose that d_{i} has been defined for i ≤ n and t_{i} has been defined for i < n. He then defines

d_{n+1}(u_{1}, …, u_{n+1}) = (u_{1}, …, u_{n})u_{n+1} − t_{n−1}d_{n}[(u_{1}, …, u_{n})u_{n+1}].

Let (u_{1}, …, u_{n}) be an essential n-cell, and let u ∈ M. When u_{n}u is irreducible (in particular, when u = 1), he defines t_{n}[(u_{1}, …, u_{n})u] = 0.

When u_{n}u is reducible, we can write u = vw where v is as short as possible with u_{n}v reducible. Then (u_{1}, …, u_{n}, v) is an essential cell. He then defines

t_{n}[(u_{1}, …, u_{n})u] = (u_{1}, …, u_{n}, v)w + t_{n}[(t_{n−1}d_{n}[(u_{1}, …, u_{n})v])w].

This last is shown to be a valid definition by noetherian induction, using other properties of the d_{i} and t_{i} which are themselves proved inductively. We want to identify his boundary operators and contracting homotopy with ours. For this we need to know that t_{n} satisfies the stated formula, but we do not have to show that this formula provides a definition of t_{n}.

Note that this approach (and also Anick’s) requires that we know both d_{n} and t_{n−1} in order to compute d_{n+1}. In turn, d_{n} requires knowledge of d_{n−1} and t_{n−2}. Thus we cannot use either Kobayashi’s formula or Anick’s to compute d_{n+1} until we have computed the boundary operators and contracting homotopy in all lower dimensions.

By contrast, our method starts with the bar resolution, in which the boundary operators and contracting homotopies are given by simple formulas. The division of the cells into essential, collapsible, and redundant cells is also fairly simple, and the boundary operator for our resolution in dimension n + 1 is determined using only these data in dimensions n + 1 and n; there is no need to look at lower dimensions.

Let u = x_{1} … x_{n}, and, if n > 1, let v = x_{2} … x_{n}. We have σ_{0}1 = 0, since we are regarding degenerate cells as zero. We have σ_{0}u = (u). If n > 1 the cell (u) is redundant, with corresponding collapsible 2-cell (x, v). We have ∂(x, v) = (x)v − (xv) + (v) and so θ(u) = (x)v + v; similarly if n > 2 we obtain θv. Hence

τ_{0}u = ϕσ_{0}u = ∑(x_{i})x_{i+1} … x_{n} = t_{0}u.

Plainly, d_{1} = δ_{1}.

Now suppose that d_{i} = δ_{i} for i ≤ n and t_{i} = τ_{i} for i < n. To show that d_{n+1} = δ_{n+1}, it is evidently enough to show that

δ_{n+1}(u_{1}, …, u_{n+1}) = (u_{1}, …, u_{n})u_{n+1} − τ_{n−1}δ_{n}[(u_{1}, …, u_{n})u_{n+1}].

However,

τ_{n−1}δ_{n}[(u_{1}, …, u_{n})u_{n+1}] = (u_{1}, …, u_{n})u_{n+1} − δ_{n+1}τ_{n}[(u_{1}, …, u_{n})u_{n+1}],

and σ_{n}[(u_{1}, …, u_{n})u_{n+1}] = (u_{1}, …, u_{n}, u_{n+1}). As this is essential, we have τ_{n}[(u_{1}, …, u_{n})u_{n+1}] = (u_{1}, …, u_{n})u_{n+1}, so we have the required formula.

To show that t_{n} = τ_{n}, we use noetherian induction on W [(u_{1}, …, u_{n})u]. If u = 1 then σ_{n}[(u_{1}, …, u_{n})u] = 0, by definition, so τ_{n}[(u_{1}, …, u_{n})u] = 0. If u_{n}u is irreducible, then σ_{n}[(u_{1}, …, u_{n})u] is collapsible, and so τ_{n}[(u_{1}, …, u_{n})u] = 0. Thus t_{n} = τ_{n} on terms of these kinds.

Now suppose that u_{n}u is reducible, and write u = vw as before. We have

τ_{n−1}δ_{n}[(u_{1}, …, u_{n})v] = (u_{1}, …, u_{n})v − δ_{n+1}τ_{n}[(u_{1}, …, u_{n})v].

Also, σ_{n}[(u_{1}, …, u_{n})v] = (u_{1}, …, u_{n}, v), which is essential, and so τ_{n}[(u_{1}, …, u_{n})v] = (u_{1}, …, u_{n}, v). It then follows that

τ_{n}[(τ_{n−1}[δ_{n}(u_{1}, …, u_{n})v])w] = τ_{n}[(u_{1}, …, u_{n})u] − τ_{n}δ_{n+1}[(u_{1}, …, u_{n}, v)w].

However,

τ_{n}δ_{n+1}[(u_{1}, …, u_{n}, v)w] = (u_{1}, …, u_{n}, v)w − δ_{n+2}τ_{n+1}[(u_{1}, …, u_{n}, v)w].

As already remarked, because vw is irreducible, τ_{n+1}[(u_{1}, …, u_{n}, v)w] = 0. That is, we have

τ_{n}[(τ_{n−1}[δ_{n}(u_{1}, …, u_{n})v])w] = τ_{n}[(u_{1}, …, u_{n})u] − (u_{1}, …, u_{n}, v)w.

This formula is obtained from that for t_{n}, replacing t by τ and d by δ.

Inductively, we assume that d_{i} = δ_{i} for i ≤ n and that t_{i} = τ_{i} for i < n. As a subsidiary noetherian induction, we assume that t_{n}[e′u′] = τ_{n}[e′u′] for any term e′u′ with W [(u_{1}, …, u_{n})u] ≫ W [e′u′], and we want to prove that t_{n}[(u_{1}, …, u_{n})u] = τ_{n}[(u_{1}, …, u_{n})u]. By the discussion of the previous paragraphs, we may assume that u_{n}u is reducible, write u = vw, and we need only show that in [τ_{n−1}[δ_{n}(u_{1}, …, u_{n})v]]w any term e′u′ has W [(u_{1}, …, u_{n})u] ≫ W [e′u′].

Now, for any essential cell e′′ and any m ∈ M, we plainly have W [e′′m] = W [σ[e′′m]]. By the discussion in subsection 6.3, it follows that for any term e′u′ in τ[e′′m] we have W [e′′m] ≫ W [e′u′)] or W [e′′m] = W [e′u′]. Because u_{n}v is reducible, we know that W [(u_{1}, …, u_{n})v] ≫ W [e′′m] for any term e′′m in δ_{n}[(u_{1}, …, u_{n})v]. Hence, by the previous paragraph, in τ_{n−1}[δ_{n}(u_{1}, …, u_{n})v] any term e′u′ has W [(u_{1}, …, u_{n})v] ≫ W [e′u′]. Since the relation ≫ is preserved by multiplication on the right, we have the required property.

Thus we have identified Kobayashi’s boundary operators and contracting homotopy with ours.

Kobayashi states his result in a more general from, involving a second rewriting system S, for which we can rewrite lv to rv, but cannot rewrite ulv to urv if u ≠ 1. Brown’s method generalises to this situation. We begin by changing the definition of ∂_{n0} in the unnormalised bar resolution to ∂_{n0}(u_{1}, …, u_{n}) = (û_{1}u_{2}, …, u_{n}), where û_{1} is the normal form of u_{1}, leaving ∂_{ni} unchanged for n > 0. We then define a cell to be degenerate is either u_{1} is irreducible or u_{i} = 1 for some i > 1, and get a normalised resolution (in a slightly more general sense) by factoring out the degenerate cells. The details of the collapsing scheme are left to the reader.

8.2. Anick’s Method

Anick’s account is both more and less general than ours. It is more general, because he works with an associative algebra rather than a monoid; we shall not make this generalisation. It is less general, because on the free monoid he takes a well-ordering compatible with multiplication and assumes that any (l, r) ∈ R has r less than l. It is possible to modify his approach, using a noetherian partial ordering as before, and using noetherian induction rather than transfinite induction. Since we already have a better proof, we shall not do this. However, we will show that his resolution is also the same as ours.

Anick’s definition of the elements which form a basis for the chains is very different from ours, and the main work is in showing that there is a natural bijection between his basis and the essential cells. We will leave this till later, and for the moment assume that they are the same.

We denote his boundary operator in dimension n (but with the essential cells as basis using the bijection) by β_{n}. He does not define a contracting homotopy, but only defines a homomorphism of abelian groups α_{n} from ker β_{n} to the group of (n + 1)-chains such that β_{n+1}α_{n}c = c when β_{n}c = 0.

With the notation of the previous subsection, he defines β_{1} = d_{1} and α_{0}(u − 1) = t_{0}u. Thus we have β_{1} = δ_{1} and α_{0} = τ_{0} on ker ϵ.

Suppose we have defined β_{i} for i ≤ n and α_{i} for i < n, and that β_{i} = δ_{i} for i ≤ n and α_{i} = τ_{i} on ker β_{i} for i < n.

He defines

β_{n+1}(u_{1}, …, u_{n+1}) = (u_{1}, …, u_{n})u_{n+1} − α_{n−1}[β_{n}(u_{1}, …, u_{n})u_{n+1}].

As in Kobayshi’s approach, we find that β_{n+1} = δ_{n+1}.

Before defining α_{n} we need a lemma.

Lemma 9. Let (u_{1}, …, u_{n}) and (v_{1}, …, v_{n}) be essential cells, and let u and v be in M. If W [(u_{1}, …, u_{n})u] = W [(v_{1}, …, v_{n})v] then u_{i} = v_{i} for all i and u = v.

Proof. Since u_{1} … u_{n}u = v_{1} … v_{n}v and both u_{1} and v_{1} are in the generating set X, we have u_{1} = v_{1}. Suppose we have u_{i} = v_{i} for i ≤ r and let r + 1 ≤ n. Since u_{r}u_{r+1} and v_{r}v_{r+1} are prefixes of the same word, either one is a prefix of the other or they are equal. By the definition of an essential cell, both u_{r}u_{r+1} and v_{r}v_{r+1} are reducible but neither has a reducible prefix. Thus they must be equal. As u_{r} = v_{r}, we see that u_{r+1} = v_{r+1}. So, inductively u_{i} = v_{i} for all i, and then u = v.

We define a quasi-ordering of essential terms which may have different dimensions by saying that the essential term eu is higher than the essential term e′u′ if W [eu] is higher than W [e′u′]. From the lemma, this is a well-ordering on essential terms of a fixed dimension. From the way the well-ordering is defined, eu is higher in this well-ordering than e′u′ if eu ≫ e′u′.

Now consider an essential n-chain c with δ_{n}c = 0. Let (u_{1}, …, u_{n})u be its highest term, so that c = k(u_{1}, …, u_{n})u + c′, where k ∈ Z and the terms in c′ are lower than (u_{1}, …, u_{n})u. Then, by our analysis in subsection 6.3, all the terms in δ_{n}c′ will be lower than (u_{1}, …, u_{n})u, as will all but one of the terms in δ_{n}(u_{1}, …, u_{n})u. If u_{n}u is irreducible, the remaining term is (u_{1}, …, u_{n−1})U with U = u_{n}u, and W [(u_{1}, …, u_{n−1})U] = W [(u_{1}, …, u_{n})u], so that this term is higher than all the other terms of δ_{n}c. This is impossible because δ_{n}c = 0.

Thus u_{n}u is reducible, and, as usual, we write u = vw. We have β_{n+1}(u_{1}, …, u_{n}, v)w = δ_{n+1}(u_{1}, …, u_{n}, v)w = (u_{1}, …, u_{n})u + c′, where, as before, all terms in c′ are lower than (u_{1}, …, u_{n}, v)w and so lower than (u_{1}, …, u_{n})u. It follows that c−kβ_{n+1}(u_{1}, …, u_{n}, v)w is a chain in ker β_{n} all of whose terms are lower than (u_{1}, …, u_{n})u; we denote it by c′′.

Anick now defines

α_{n}c = k(u_{1}, …, u_{n}, v)w + α_{n}c′′,

a definition by transfinite induction.

Since β_{n+1} = δ_{n+1} and, as shown in the previous subsection, τ_{n}δ_{n+1}[(u_{1}, …, u_{n}, v)w] = (u_{1}, …, u_{n}, v)w, we also have

τ_{n}c = k(u_{1}, …, u_{n}, v)w + τ_{n}c′′.

Thus we have proved by transfinite induction that α_{n} = τ_{n} on kerβ_{n}. We now proceed to give Anick’s account of the basis elements. We shall define n-overlaps and leftmost n-overlaps. (These correspond to Anick’s notion of n-prechains and n-chains. His names do not indicate what the objects are; also, we need the word chain to refer to the elements of our complex.) His resolution has as basis in dimension n the leftmost (n − 1)-overlaps.

Let L be the set of left-hand sides of elements of R. When l_{i} ∈ L, we denote by r_{i} the word such that (l_{i}, r_{i}) ∈ R. We call the elements of X 0-overlaps and the elements of L 1-overlaps. Every member of X or L is to be a leftmost overlap.

An n-overlap is defined to be a word x_{1} … x_{k} for some k and some x_{i} ∈ X together with integers i_{r} and j_{r} for 1 ≤ r ≤ n such that

1 = i_{1} < i_{2} ≤ j_{1} < i_{3} ≤ j_{2} < … < i_{n} ≤ j_{n−1} < j_{n} = k

and x_{i_{r}} … x_{j_{r}} ∈ L for 1 ≤ r ≤ n. Less formally, an n-overlap consists of a word w and words l_{1}, …, l_{n} ∈ L such that

— l_{1} is a prefix of w, l_{n} is a suffix of w, and l_{r} is a subword of w for 1 < r < n,

— for i < n the subword l_{i+1} of w overlaps the subword l_{i} and starts later than the start of l_{i} (it will also end later than the end of l_{i}, because R is reduced; conversely, any subword which is in L which ends later than the end of l_{i} must start later than the start of l_{i}),

— the subword l_{i+2} does not overlap the subword l_{i}.

A 2-overlap is often referred to as an overlap ambiguity, which gives rise to a critical pair (since R is reduced, there are no inclusion ambiguities).

We sometimes refer to the word w as an n-overlap, without explicit mention of the corresponding integers. Strictly speaking, this is incorrect, as there may be more than one way of assigning the integers so as to get an n-overlap. Because R is reduced, this cannot happen if n = 2. But suppose that {abc, bcd, cde, def } ⊆ L. Then the word abcdef is a 3-overlap in two ways. one using the subwords abc, cde, and def, and the other using abc, bcd, and def. Note that the word abcde, in which the subwords abc and bcd overlap and the subwords bcd and cde also overlap, is not a 3-overlap, as the subwords abc and cde overlap, which is forbidden by our definition. In this example, the second expression as an overlap is further to the left than the first, in an obvious sense. More precisely, the first expression gives rise to a 2-overlap of abc and cde in the word abcde and the second expression gives rise to a 2-overlap of abc and bcd in the word abcd; the second word is a prefix of the first. This explains the notion of a leftmost overlap, given in the next paragraph.

To each n-overlap and m < n there is a corresponding m-overlap given by the word x_{1} … x_{j_{m}} and the integers i_{r} and j_{r} for r ≤ m. We say that an n-overlap is leftmost if, for all m ≤ n and all r < j_{m} the word x_{1} … x_{r} is not an m-overlap.

It is easy to see that, although some words may be n-overlaps in more than one way, a word can be a leftmost n-overlap in at most one way. For suppose it had two such expressions, corresponding to integers i_{r} and j_{r} for one and i′_{r} and j′_{r} for the other. Because each corresponding m-overlap is leftmost for each expression, we must have j′_{m} = j_{m} for all m. Because R is reduced, this requires that we also have i′_{m} = i_{m}.

Note that a word which can be expressed as an n-overlap may not have an expression as a leftmost n-overlap. For instance, let L = {abc, bcd, cde, efg}. Then the word abcdefg is expressed as a 3-overlap using the subwords abc, cde, and efg. The corresponding 2overlap is abcde, which has the 2-overlap abcd as prefix. So this expression is not leftmost. But if we try to find an expression which is further to the left, we must use the subwords abc, bcd, and efg, which express our word as the product of a 2-overlap and a 1-overlap, not as a 3-overlap.

Anick constructs his resolution using the leftmost (n − 1)-overlaps as the basis for the chains in dimension n. We shall show how to obtain a bijection between essential n-cells and leftmost (n − 1)-overlaps.

The leftmost 0-overlaps are the elements of X, and the essential cell corresponding to x is (x). The leftmost 1-overlaps are the elements of L. Since R is strongly reduced, any l ∈ L can be written l = xu for some non-empty word u, and the corresponding essential 2-cell is (x, u).

Now let x_{1} … x_{k} be a word which is a leftmost (n − 1)-overlap, for n > 1. We define words u_{1}, …, u_{n} inductively, by setting u_{1} = x_{1} and u_{1} … u_{r+1} = x_{1} … x_{j_{r}} for 0 < r < n. By definition of an n-overlap, u_{m}u_{m+1} is reducible for 0 < m < n. Because our overlap is leftmost, no prefix of u_{m}u_{m+1} is reducible. Hence the n-cell (u_{1}, …, u_{n}) is essential.

Conversely, take an essential n-cell (u_{1}, …, u_{n}), and write u_{1} … u_{n} = x_{1} … x_{k} with x_{i} ∈ X for all i. Define j_{r} for 0 < r < n by u_{1} … u_{r+1} = x_{1} … x_{j_{r}}. Because u_{r}u_{r+1} is reducible but no prefix of it is reducible, there will be a suffix of u_{r}u_{r+1} in L; this suffix will be unique, since R is reduced. We define i_{r} by requiring x_{i_{r}} … x_{j_{r}} ∈ L. This expresses x_{1} … x_{k} as an (n − 1)-overlap. If it is not leftmost, take the smallest value of m such that the corresponding m-overlap has a prefix which is also an m-overlap. We would then find that u_{m}u_{m+1} had a reducible prefix, contrary to hypothesis.

So we have the required bijection, and we have identified Anick’s resolution with ours. As already remarked, the boundary operator is much easier to calculate using our approach. However, in some cases the structure of the overlaps is more transparent than that of the essential cells, so Anick’s method may be better if we do not need to compute the boundary operators.

8.3. Squier’s Method

We conclude the detailed comparison by comsidering Squier’s method. Squier works with left modules, while we use right ones. As already remarked, we can use either, and we will look at the right module version of Squier’s result. We begin by defining a function D_{x} : X^{∗} → ZX^{∗} for each x ∈ X. Let u = x_{1} … x_{n}, Then we define D_{x}u = ∑ x_{r+1} … x_{n}, the sum being taken over those r for which x_{r} = x. For example, if u = xyxyxz then D_{x}u = yxyxz +yxz +z, D_{y}u = xyxz +xz, D_{z}u = 1. We extend D_{x} to ZX^{∗} linearly. It is easy to see that, for any u, v ∈ X^{∗}, we have D_{x}[uv] = [D_{x}u]v + D_{x}v and ∑[x − 1]D_{x}u = u − 1.

From our previous description, we see that τ_{0}u = ∑(x)D_{x}u. We already know that ϕ_{1}(u) = τ_{0}u.

For any w ∈ X^{∗}, let πw be the irreducible word equivalent to w; we extend π linearly to ZX^{∗}.

Let l ∈ L. For any u and v, we have D_{x}[ulv − urv] = [D_{x}u][lv − rv] + [D_{x}l − D_{x}r]v, and so πD_{x}[ulv − urv] = π[[D_{x}l − D_{x}r]v].

Write l as xu. Then there is a corresponding essential 2-cell (x, u). To focus attention on l, we will also denote this cell by ⟨l⟩.

Now ∂_{2}(x, u) = (x)u + (u) − (π[xu]). From our discussion of ϕ_{1} and τ_{0}, we have δ_{2}⟨l⟩ = ∑(x)D_{x}[l − r]. This identifies our δ_{2} with Squier’s. Note that we also have δ_{2}[⟨l⟩w] = ∑(x)πD_{x}[[l − r]w]; the formula of the previous sentence does not need π because the elements involved are irreducible. Further, we have already seen that πD_{x}[[l− r]w] = π[[D_{x}l − D_{x}r]w]. For each w ∈ X^{∗}, choose (arbitrarily) a sequence w = w_{1} → w_{2} … → w_{n} = πw. For i < n, let w_{i} = u_{i}l_{i}v_{i} and w_{i+1} = u_{i}r_{i}v_{i}, where l_{i} ∈ L with corresponding right-hand side r_{i}. Denote this sequence by F, and define ⟨F ⟩ = ∑⟨l_{i}⟩v_{i}. From our previous remarks, we see that δ_{2}⟨F ⟩ = ∑(x)πD_{x}[w − πw].

In particular, if we always make the rightmost reduction possible, the resulting function will be denoted by ρ. Note that ρw = ⟨l_{1}⟩v_{1} + ρw_{2}. Also, ρ[ww′] = ρw′ + ρ[wz], where z = πw′.

We now show that ϕ_{2}(u, v) = ρ[uv] for any 2-cell (u, v). To do this, we use noetherian induction on >_{2}, defined as in subsection 6.3. First suppose that u = xt for some x ∈ X and non-empty t. Then (u, v) is redundant, and, looking at the boundary of the corresponding collapsible cell, we have ϕ_{2}(u, v) = ϕ_{2}(t, v)+ϕ_{2}(x, π[tv]) = ρ[tv]+ρ[x[π[tv]], inductively, and this equals ρ[xtv], as required.

Next suppose that u = x. If xv is irreducible, then (x, v) is collapsible and so ϕ_{2}(x, v) = 0, and also ρ[xv] = 0. Otherwise we can write v = pq with xp = l ∈ L. Note that xp is the only subword of xpq which is in L. Then π[xp] = r. We have ϕ_{2}(x, v) = ⟨l⟩q + ϕ_{2}(r, q) = ⟨l⟩q + ρ[rq], inductively, and this equals ρ[xpq], as required.

We see that τ_{1}[(x)u] = ρ[xu], since σ_{1}[(x)u] = (x, u).

In dimension 3, Squier’s module differs from ours. Before discussing it, we look at some results on 3-cells. Consider a 3-cell (u, v, w) with uv irreducible. If u ∈ X this cell is collapsible, and ϕ_{3}(u, v, w) = 0. Otherwise this cell is redundant, and, looking at the boundary of the corresponding collapsible 4-cell, we easily see that ϕ_{3}(u, v, w) = 0, by induction on the length of u. From this we then see that if uv ∈ L and u = xt we have ϕ_{3}(u, v, w) = ϕ_{3}(x, tv, w).

Squier takes a module S with basis the cells (u, v, w) where uv = l_{1} and vw = l_{2} are in L. We consider the boundary δ_{3} = ϕ_{2}∂_{3} on S. We know that δ_{2}δ_{3} = 0, and that ϕ_{2}∂_{3}ϕ_{3} = ϕ_{2}∂_{3}. So, by the previous paragraph, δ_{3}S = δ_{3}S′, where S′ has as basis the cells (x, tv, w), with u, v, w as before and u = xt. These cells include all essential cells, so we have ker δ_{2} ⊆ δ_{3}S′, as required.

Now ∂_{3}(u, v, w) = (u, v)w−(u, r_{2})+(r_{1}, w)−(v, w), by definition. Using the connection between ϕ_{2} and ρ previously found, and noting that ρ[uv] = ⟨l_{1}⟩ and ρ[vw] = ⟨l_{2}⟩, we obtain

δ_{3}(u, v, w) = ⟨l_{1}⟩w − ⟨l_{2}⟩ + ρ[r_{1}w] − ρ[ur_{2}].

Allowing for the fact that we are using right modules and Squier is using left ones, this is exactly Squier’s definition of his boundary operator. Thus Squier’s module in dimension 3 is larger than it needs to be, which leads to the difficulties in extending the resolution further. Comparing with Anick’s approach, we find that the the bijection between essential 3-cells and leftmost 2-overlaps extends to a bijection between the cells of S′ and all 2-overlaps.

Squier extends his theory further by using the function α obtained by using an arbitrary choice of reductions, rather than ρ which was obtained using the rightmost possible reduction at each step. That is, taking the same set S, he defines

Δ_{3}(u, v, w) = ⟨l_{1}⟩w − ⟨l_{2}⟩ + α[r_{1}w] − α[ur_{2}].

He then proves that ker δ_{2} = Δ_{3}S.

We have

Δ_{3}(u, v, w) − δ_{3}(u, v, w) = α[r_{1}w] − ρ[r_{1}w] − α[ur_{2}] + ρ[ur_{2}].

So δ_{2}Δ_{3} = δ_{2}δ_{3} = 0 if δ_{2}αz = δ_{2}ρz for all z. But we have already remarked that both these expressions equal ∑(x)D_{x}[z − πz]. If we show that αz − ρz ∈ Δ_{3}S for any z, it will be immediate that δ_{3}(u, v, w) ∈ Δ_{3}S. The next lemma proves a stronger property. We first need to obtain a simple formula. Let F be a sequence of rewritings from w to πw, and let u and v be any words. Let H be a sequence of rewritings from u[πw]v to π[uwv]. Let the obvious sequence from uwv to u[πw]v, and let G consist of uF v followed by H. It is easy to check (noting that the product in M of πv_{i} and πv is π[v_{i}v]) that ⟨G⟩ = ⟨F ⟩πv + ⟨H⟩. Lemma 10. Let F and G be sequences of rewritings from a word z to πz. Then ⟨F ⟩ − ⟨G⟩ ∈ Δ_{3}S.

Proof. We prove the result by noetherian induction. Let F_{1} and G_{1} be the sequences obtained from F and G by omitting the first rewriting. If the first rewriting in F is the same as the first in G, then ⟨F ⟩ − ⟨G⟩ = ⟨F_{1}⟩ − ⟨G_{1}⟩, and the result holds by induction. Otherwise we have the usual two possibilities. The first is that z = al_{1}bl_{2}c, where the first rewriting of F replaces l_{1} by r_{1}, and the first rewriting of G replaces l_{2} by r_{2}. Let H be any sequence of rewritings from ar_{1}br_{2}c to π[ar_{1}br_{2}c]. Then ⟨F ⟩ = ⟨l_{1}⟩π[bl_{2}c] + ⟨F_{1}⟩. Inductively, ⟨l_{2}⟩πc + ⟨H⟩ − ⟨F_{1}⟩ ∈ Δ_{3}S. Using the similar formulae concerning G and G_{1}, the result is immediate. The second case is that z = auvwb with uv = l_{1} and vw = l_{2}; we will have u, v, w irreducible and non-empty, and so w = πw. Then ⟨F ⟩ = ⟨l_{1}⟩π[wb] + ⟨F_{1}⟩. Let A be that sequence of rewritings from r_{1}w to π[r_{1}w] = π[uvw] which defines α[r_{1}w], and let H be any sequence of rewritings from aπ[uvw]b to π[auvwb]. Then we have the sequence aAb followed by H from ar_{1}wb and also the sequence F_{1} from the same word. Inductively, using the formula before the lemma, α[r_{1}w]πb+⟨H⟩−⟨F_{1}⟩ ∈ Δ_{3}S. Similarly, ⟨G⟩ = ⟨l_{2}⟩πb + ⟨G_{1}⟩, and α[ur_{2}]πb + ⟨H⟩ − ⟨G_{1}⟩ ∈ Δ_{3}S. So it is enough to show that ⟨l_{1}⟩π[wb] + α[r_{1}w]πb − ⟨l_{2}⟩πb − α[ur_{2}]πb ∈ Δ_{3}S. But this is precisely Δ_{3}(u, v, w)πb.

A closer look at the proof shows that we have ⟨F ⟩ − ⟨G⟩ = Δ_{3}q, where any term t in the chain q has either z ≫ W [t] or z = W [t]. The same will hold for δ_{3}, which is just a special case of Δ_{3}. It then follows that for any chain p there is a chain q such that Δ_{3}p = δ_{3}[p + q] and p + q ≠ 0 if q ≠ 0 . In particular, Δ_{3} has trivial kernel if δ_{3} has trivial kernel.

Here we are looking at δ_{3} as a homomorphism from S. If (in the notation used in the previous section) all overlaps are leftmost, then ϕ_{3} is plainly a bijection from the basis of S to the set of essential 3-cells. Since δ_{3}ϕ_{3} = δ_{3}, we see that δ_{3} has trivial kernel on S if it has trivial kernel on the set of essential 3-chains. By Brown’s Theorem, this will certainly hold if there are no 3-overlaps. We have therefore shown the following result, which is exactly Theorem 3.2 of (Squier 1987).

Proposition 3. Suppose that all 2-overlaps are leftmost and that there are no 3-overlaps. Then ker Δ_{3} = 0.

8.4. Groves’s Method

Groves (1991) gives yet another proof of Anick’s theorem. This differs in significant details from the approaches we have discussed, because it is based on cubes rather than simplexes (which, for some situations such as free and direct products of groups, is more convenient). Nevertheless, readers who have followed our approach this far will probably feel, on looking at Groves’s work, that it can be fitted into our account of collapsing schemes. The notations and concepts he uses seem to me rather complicated, and I have not been able to simplify them enough to give a detailed account. I therefore make just a few comments on his work.

Groves starts with our usual strongly minimal convergent rewriting system ⟨X; R⟩, presenting the monoid M. He then defines a directed graph Γ, with vertex set X^{∗} and with one edge starting at u for each application of a rewrite rule to u. He then defines what he calls cubes and stars of Γ, and obtains a resolution whose basis consists of certain stars.

We note that Γ is disconnected, with one component for each element of M. Also, each component has a terminal vertex; that is, a vertex which can be reached from any other String Rewriting and Homology of Monoids 33

vertex in the component by a directed path. These vertices are precisely the irreducible words. Because of this, it is easy to construct a resolution

… C_{2} → C_{1} → C_{0} → ZM → 0

of the abelian group ZM by free abelian groups (note that we do not define a module structure yet). The basis of C_{n} will consist of all n-cubes except that certain cubes are equated to zero.

In the low dimensions it is not too difficult to see what we want the redundant and collapsible cells to be, and we should be able to extend this to a collapsing scheme. It is then necessary to factor out further subgroups, as indicated by Groves, in order to get an action of M. The boundary operators map each such subgroup into the next one down, and so we get a complex. This will satisfy the condition for a resolution, except in low dimensions, because the contracting homotopies will map each subgroup in the next one up. In low dimensions, we need to make explicit definitions slightly different from the original ones, and check that the required properties hold.

References

Abels, H. (1979), An example of a finitely presented solvable group, in C. J. C. Wall, ed., ‘Homological group theory’, number 36 in ‘London Mathematical Society Lecture Notes’, Cambridge University Press, Cambridge.

Alonso, J. (1992), Combings of groups, in G. Baumslag, F. Cannonito & C. F. Miller, eds, ‘Proceedings of the workshop on algorithms, word problems, and classification in combinatorial group theory’, number 23 in ‘MSRI Publications’, Springer, New York, pp. 165–178.

Anick, D. J. (1986), ‘On the homology of associative algebras’, Transactions of the American

Mathematical Society 296, 641–659. Baumslag, G. & Bieri, R. (1976), ‘Constructible solvable groups’, Mathematische Zeitschrift

151, 249–257. Bieri, R. (1976), Homological dimension of discrete groups, Queen Mary College Mathematics

Notes, Queen Mary College, London. Bieri, R. (1980), ‘A connection between the integral homology and the centre of a rational linear

group’, Mathematische Zeitschrift 170, 263–266. Book, R. V. & Otto, F. (1993), String-Rewriting Systems, Springer, New York. Brown, K. S. (1984), ‘Presentations for groups acting on simply-connected complexes’, Journal

of Pure and Applied Algebra 32, 1–10. Brown, K. S. (1987), ‘Finiteness properties of groups’, Journal of Pure and Applied Algebra

44, 45–75. Brown, K. S. (1992a), The geometry of finitely presented infinite simple groups, in G. Baumslag,

F. Cannonito & C. F. Miller, eds, ‘Proceedings of the workshop on algorithms, word problems, and classification in combinatorial group theory’, number 23 in ‘MSRI Publications’, Springer, New York, pp. 121–136.

Brown, K. S. (1992b), The geometry of rewriting systems; a proof of the Anick-Groves-Squier theorem, in G. Baumslag, F. Cannonito & C. F. Miller, eds, ‘Proceedings of the workshop on algorithms, word problems, and classification in combinatorial group theory’, number 23 in ‘MSRI Publications’, Springer, New York, pp. 137–164.

Brown, K. S. & Geoghegan, R. (1984), ‘An infinite-dimensional torsion-free F P_{∞} group’, Inventiones Mathematicae 77, 367–381.

Daniel E. Cohen 34

Cohen, D. E. (1992), ‘A monoid which is right F P_{∞} but not left F P_{1}’, Bulletin of the London

Mathematical Society 24, 340–342. Cohen, D. E. (1993), String rewriting; a survey for group theorists, in G. Niblo & M. Roller, eds,

‘Proceedings of the conference on Geometric Group Theory, Isle of Thorns 1991’, number 181 in ‘London Mathematical Society Lecture Notes’, Cambridge University Press.

Cohen, D. E. (1995), ‘Projective resolutions for graph products’, Proceedings of the Edinburgh

Mathematical Society 38, 185–188. Coxeter, H. S. M. & Moser, W. O. J. (1958), Generators and relations for discrete groups,

number 14 in ‘Ergebnisse Mathematik’, Springer, Berlin. Cremans, R. & Otto, F. (1994), For groups the property of having finite derivation type is equiv-

alent to the homological finiteness condition F P_{3}, Mathematische Schrift Kassel, preprint 8/94.

Epstein, D. B. A., Cannon, J. W., Holt, D. F., Levy, S. V. F., Paterson, M. S. & Thurston, W. P.

(1992), Word Processing in Groups, Jones and Bartlett, Boston. Farkas, D. R. (1992), ‘The Anick resolution’, Journal of Pure and Applied Algebra 79, 159–168. Groves, J. R. J. (1991), Rewriting systems and homology of groups, in L. G. Kovacs, ed., ‘Groups

— Canberra 1989’, number 1456 in ‘Lecture notes in mathematics’, Berlin, pp. 114–141. Groves, J. R. J. & Smith, G. S. (1989), Rewriting systems and soluble groups, Bath computer

science technical report 89-19. Groves, J. R. J. & Smith, G. S. (1993), ‘Soluble groups with a finite rewriting system’, Proceedings

of the Edinburgh Mathematical Society 36, 283–288. Guba, V. S. & Sapir, M. V. (1995), The Dehn function and a regular set of normal forms for

R. Thompson’s group F, preprint. Hermiller, S. & Meier, J. (1994a), Algorithms and geometry for graph products of groups, to

appear. Hermiller, S. & Meier, J. (1994b), Tame combings, almost convexity and rewriting systems for

groups, to appear. Hilton, P. J. & Stammbach, U. (1971), A course in homological algebra, Springer, New York. Jantzen, M. (1988), Confluent string rewriting, number 14 in ‘European association for theoretical

computer science’, Springer, Berlin. Kapur, D. & Narendran, P. (1985), ‘A finite Thue system with a decidable word problem and

without an equivalent finite canonical system’, Theoretical Computer Science 35, 337–344. Knuth, D. & Bendix, P. (1970), Simple word problems in universal algebra, in J. Leech, ed.,

‘Computational problems in abstract algebra’, Pergamon, Oxford. Kobayashi, Y. (1990), ‘Complete rewriting systems and homology of monoid algebras’, Journal

of Pure and Applied Algebra 65, 263–275. Lafont, Y. (1994), A new finiteness condition for monoids presented by complete rewriting sys-

tems (after Craig C. Squier), Journal of Pure and Applied Algebra (to appear). Lafont, Y. & Prouté, A. (1991), ‘Church-Rosser property and homology of monoids’, Mathemat-

ical structures in computer science 1, 297–326. Lyndon, R. C. (1950), ‘Cohomology theory of groups with a single defining relation’, Annals of

Mathematics 52, 650–665. MacLane, S. (1963), Homology, Springer, Berlin. Newman, M. H. A. (1943), ‘On theories with a combinatorial definition of equivalence’, Annals

of Mathematics 43, 223–243. Squier, C. C. (1987), ‘Word problems and a homological finiteness condition for monoids’, Journal

of Pure and Applied Algebra 49, 201–217. Squier, C. C., Otto, F. & Kobayashi, Y. (1994), ‘A finiteness condition for rewriting systems’,

Theoretical Computer Science 131, 271–294.