The Extrinsic Geometry of Subgroups and the Generalized Word Problem

Benson Farb Princeton University and UC Berkeley

5/10/93, appeared in Proc. London Math. Soc. (3) 68 (1994), pp. 577-593.

1 Introduction

Powerful new techniques have been developed in the last decade to study discrete groups from a geometric point of view. This is exemplified by the work of Gromov on hyperbolic groups ([AB, Gr1, GdlH, Gh, CDP]) and the work of Thurston and Epstein on automatic groups ([E et al., Fa]). One important thread has been the study of isoperimetric functions in groups, which were introduced by Gromov and have been studied extensively by Gersten and others ([Ge1, Ge2], also see [Ge4] for a survey). Isoperimetric (and isodiametric) functions provide a geometric context in which to study the word problem for groups, and give a quantitative measure of the complexity of this problem; in particular a finitely presented group has solvable word problem if and only if it has a recursive isoperimetric function ([Ge1]). Gromov has shown that a group is word-hyperbolic if and only if it has a linear isoperimetric function ([Gr1]); automatic groups have quadratic isoperimetric functions ([E et al.]). Isoperimetric and isodiamteric functions have also proven useful in the study of three-manifolds ([Ge2, Po, SG]).

In this paper we study the geometry of embeddings of discrete groups inside other discrete groups. We introduce distortion, generalized isoperimetric and generalized isodiametric functions in order to study the generalized word problem from a geometric point of view, and to provide quantitative measures of the complexity of this problem. We provide a convexity condition which gives concrete bounds on these functions; in fact this condition characterizes those subgroups for which the generalized word problem can be solved. We compute several examples, and give applications to isoperimetric and isodiametric functions; in particular we compute the isoperimetric function of a quotient G/H in terms of the isoperimetric function for G and the distortion of H in G.

This material is related to recent work of Gromov ([Gr2]); in particular Gromov studies distortion in Lie groups. We make use of several of his examples in this paper. This work was greatly influenced by ideas of S. Gersten and M. Gromov, whose papers have been useful and inspirational. I’d like to thank J. Stallings for helpful conversations, and S. Gersten for his comments and corrections.

2 The Generalized Word Problem and its Complexity

Let G be a finitely presented group with finite generating set S, and let H be a finitely generated subgroup of G. The generalized word problem, or GWP for H in G asks for an algorithm which takes as input an element of the free group on S (a so-called ‘word’), and as output tells whether or not this word represents an element of H. When H is the trivial group then this is simply the word problem for the group G. The group G is said to have solvable generalized word problem if the GWP is solvable for every finitely generated subgroup H in G.

The generalized word problem, also called the membership, occurrence or Magnus problem, was formulated by K. Mihailova in 1958 ([Mi]), but special cases had already been studied by Nielsen ([Ni]) and Magnus ([Ma]). The corresponding topological question is the following : Given a space X with fundamental group G, is there a way of determining when a closed loop in X lifts to a closed loop in X̃_{H} , the cover of X corresponding to the subgroup H of G? The GWP also arises, for example, as the question : given an incompressible surface N in a three-manifold M , can one determine when a loop in M can be homotoped (rel basepoint) into N ?

Let G be a group with finite presentation G =< X : R >, and let H < G be a finitely generated subgroup. Let A = X ∪ X^{−1} , and let A^{∗} denote the free monoid on A. Note that the only difference between A^{∗} and F (X) is the fact that elements of F (X) , the free group on X, are usually considered to be reduced. For a word w ∈ A^{∗}, we denote by \overline{w} the image of w under the natural map A^{∗} ⟶ G. We denote by ℓ(w) the length of w in A^{∗}. Choose a set of words Y = {y_{1}, …, y_{m}}, y_{i} ∈ A^{∗}, so that Y = Y^{−1} and so that H is generated by \overline{Y} = \{\overline{y_{1}}, …, \overline{y_{m}}\}. We define a metric, denoted d_{G}, on the group G by letting d_{G}(x, y) be the length of a shortest word representing x^{−1}y; this metric agrees with the metric obtained by letting each edge of the Cayley graph Γ_{X}(G) have length 1 and taking the induced path metric. We denote d_{G}(1, g) by ||g||_{G}.

We now introduce three functions which provide different quantitative measures of the complexity of the generalized word problem for a given group and subgroup. Given w ∈ A^{∗} with \overline{w} ∈ H, there exists an expression

w = y_{i_{1}} ⋯ y_{i_{k}} ∏_{j=1}^{N} z_{j}R_{j}z_{j}^{−1}, y_{i_{r}} ∈ Y, z_{j} ∈ F (X), R_{j} ∈ R ∪ R^{−1} (1)

with the equality in F (X) . Note that w may be expressed in this fashion in many possible ways, even for fixed generating sets for G and H.

Let N denote the natural numbers. We say that a function f : N ⟶ N is a distortion function for H in G if for every w ∈ F (X) with \overline{w} ∈ H we may write w as in (1) with

k ≤ f(||\overline{w}||_{G}).

This is equivalent to

||\overline{w}||_{H} ≤ f(||\overline{w}||_{G}).

In this case we also say that ‘ H has distortion f(n) in G ’. We should note that this notion of distortion differs from Gromov’s definition (as defined in [Gr2]) by a linear factor. Note that f(n) is constant if and only if H is finite; otherwise f is at least linear. Following Gersten ([Ge4]), the minimum distortion function will be called the rewrite function for H in G.

We say that functions g, h : N ⟶ N are generalized isoperimetric and generalized isodiametric functions, respectively, for H in G if for every w ∈ F (X) with \overline{w} ∈ H, we may write w as in (1) with

N ≤ g(ℓ(w))

and

ℓ(z_{j}) ≤ h(ℓ(w))

for each j. Such functions will also be called GIP and GID functions for H in G. Note that in the case when H is trivial, these functions are simply the standard isoperimetric and isodiametric functions for G.

There is a geometric interpretation of these three functions. Firstly, the distortion f(n) is simply a comparison of the intrinsic (word) metric in the subgroup H with the metric on H induced by the metric on G. Now writing w as in (1) is equivalent to finding a Dehn diagram ^{1} for (y_{i_{1}} ⋯ y_{i_{k}})^{−1}w whose faces are the R_{j}. The ‘combinatorial area’ of a Dehn diagram is simply the number of faces in the diagram, while the ‘combinatorial diameter’ of a Dehn diagram is the diameter of the 1-skeleton of the diagram considered as a graph each of whose edges has length 1. For any v ∈ F (X) we define Area_{X}(v) (resp. Diam_{X}(v) ) to be the minimal area (resp. diameter) of any Dehn diagram for w. The generalized isoperimetric and isodiametric functions g(n) and h(n) now have the following interpretation:

g(n) = max_{ℓ(w)≤n}min_{\{y∈Y^{∗}:\overline{w}=\overline{y}\}}Area_{X}(y^{−1}w)
h(n) = max_{ℓ(w)≤n}min_{\{y∈Y^{∗}:\overline{w}=\overline{y}\}}Diam_{X}(y^{−1}w).

The motivation for these definitions comes from differential geometry, where one measures the area and diameter of a minimal surface spanning a null-homotopic loop.

Remark: It may seem as if the study of generalized isoperimetric functions reduces to the study of isoperimetric functions, since with GIP functions we are looking at very special words representing 1 ∈ G, namely words of the form wv^{−1} , where w ∈ F (X), v ∈ Y^{∗}, and \overline{w} = \overline{v}. In particular, if H has distortion f(n) in G, and if G has isoperimetric function F (n) , then F (n + f(n)) is clearly a bound for the generalized isoperimetric function for H in G. However, this obvious bound can be awful (cf. Example 4 below), even in very simple cases; indeed, this is one of the reasons GIP functions are so interesting.

1For the notion of Dehn diagram, sometimes called van Kampen diagram or singular disc diagram, see [LS].

Henceforth we assume that the group G has solvable word problem. It is known ([Ge1]) that this is equivalent to G having a recursive isoperimetric function. The connection between the three functions defined above and the generalized word problem is given by the following

Proposition 2.1 Let G have solvable word problem, and let H be a finitely generated subgroup of G. Then the following are equivalent:

1. The generalized word problem for H in G is solvable.

2. The GIP function is recursive.

3. The GID function is recursive.

4. Some distortion function (for H in G) is recursive.

5. The rewrite function is recursive.

Proof: Recall our notation that Y = {y_{1}, …, y_{m}} is a set of words in F (X) such that \overline{Y} generates H, and f(n) is a distortion function for H in G. Suppose that f(n) is recursive, and let w ∈ F (X) with ℓ(w) = n be given. Then \overline{w} ∈ H if and only if \overline{w} can be written as a product of at most f(n) elements of \overline{Y}. If f(n) is recursive, then we can create a list of all possible products of at most f(n) elements of Y, and simply check whether or not w is in this list, which can be done since G has solvable word problem. Note that \overline{w} ∈ H if and only if w lies in this list.

Conversely, if H has solvable generalized word problem in G, then to compute f(n) one simply lists all words w ∈ F (x) of length n such that \overline{w} ∈ H (note that this list includes all such w with ||\overline{w}||_{G} = n). Each of the words on this (finite) list represents an element of H, so it is possible to write each word as a product of elements of Y. Then f(n) is the maximal number of elements needed in such a product.

In section 7 we show that a bound on one of the distortion, GIP or GID functions gives a bound on the other two. It is clear from this that the generalized word problem is solvable if and only if the GIP function is recursive, if and only if the GID function is recursive. The rest of the proposition follows easily. ⋄

Remark: The algorithm given in the proof of Proposition 2.1 is inefficient; its advantage is its universality.

The proof of Proposition 2.1 shows precisely how the distortion, GIP and GID functions measure the complexity of the generalized word problem. When the subgroup in question is trivial we are dealing with the standard isoperimetric and isodiametric functions. Much work has been done to compute these functions explicitly for many groups (see for example, [E et al., Ge1, Ge2, BP, BG]). In some cases the precise constants are important ([Po, SG]).

One of the goals of this paper is to compute the distortion, GIP and GID functions in several cases. Further motivation for the study of these functions comes from the fact that, together with an isoperimetric function for a group G, the distortion, GIP and GID functions provide bounds for the isoperimetric and isodiametric functions of the quotient G/H for normal subgroups H < G. Distortion, GIP and GID functions also provide another context in which to explore the geometry of groups.

3 Behavior Under Change of Generators and Presentations

The reader may notice that we really should have defined the distortion, GIP and GID functions of a presentation, not of a group. However, these functions are indeed dependent (up to a certain equivalence) only on the group and subgroup, not on the presentation or choice of generators for the subgroup, as the following propositions show.

Proposition 3.1 Let G =< X : R > be a finitely presented group, and let Y = {y_{1}, …, y_{m}}, y_{i} ∈ F (X) and Y′ = {y′_{1}, …, y′_{m}}, y′_{i} ∈ F (X) be such that both \overline{Y} and \overline{Y}′ generate H. If f(n), g(n) are distortion and GIP functions for H in G with respect to the generating set Y′, then there exist constants K, L > 0 such that Kf(n) is a distortion function and Lg(n) is a GIP function for H in G with respect to Y.

Proof: For each y_{i}, 1 ≤ i ≤ n, we can write

y′_{i} = y_{b_{1}} ⋯ y_{b_{k_{i}}} ∏_{j=1}^{M_{i}} d_{j}R_{j}d_{j}^{−1}, y_{b_{s}} ∈ Y, d_{j} ∈ F (X), R_{j} ∈ R ∪ R^{−1} (2)

with each b_{p} and d_{j} dependent on i. Let K = max_{i}k_{i}, M = max_{i}M_{i} and D = max_{i,j}ℓ(d_{j}) . Now given w ∈ F (X) with \overline{w} ∈ H, we may write

w = y′_{i_{1}} ⋯ y′_{i_{r}} ∏_{i=1}^{N} z_{j}R_{j}z_{j}^{−1}, y′ ∈ Y′, z_{j} ∈ F (X), R_{j} ∈ R ∪ R^{−1}

with r ≤ f(||\overline{w}||_{G}), N ≤ g(ℓ(w)), ℓ(z_{j}) ≤ h(ℓ(w)) . Now replace each y′_{i_{k}} in this equation by its representation in (2), obtaining an expression for w in terms of elements of Y. Note that if R_{j} is any relator and if u, v ∈ F (X) are any words, then

(uRu^{−1})v = v[(v^{−1}u)R(v^{−1}u)^{−1}]

so that we may move each (conjugate of a) relator completely to the right at the cost only of increasing the length of the conjugating element, while keeping the number of (conjugates of) relators fixed. After doing this, we obtain an expression which shows that \overline{w} can be written as a product of at most Kr ≤ Kf(||\overline{w}||_{G}) elements of \overline{Y}. This expression also shows that, as an element of F (X) , w differs from its expression as an element of Y^{∗} by a product of at most Mr + g(||\overline{w}||_{G}) (conjugates of) relators. By looking at Dehn diagrams one sees that there exists a constant M′ > 0 so that f(n) ≤ M′g(n) for all n (see equation 8 in Section 7). Hence

\begin{aligned}Mr & ≤ Mf(||\overline{w}||_{G}) \\ & ≤ MM′g(||\overline{w}||_{G}). \end{aligned}

This shows that MM′g(n) + g(n) = (MM′ + 1)g(n) is a GIP function for H in G with respect to Y. ⋄

If one follows the argument through in Proposition 3.1 then one sees that the bound on the GID function with respect to the new set of generators is equivalent to the maximum of the original GID function and the distortion of H in G; in particular it may change in a more than linear way. This phenomenon may simply be a function of the proof, although we see no other. This brings up the following

Question: Is the generalized isodiametric function for H in G independent of the choice of generating set for the subgroup H?

Proposition 3.2 If f(n), g(n) are distortion and GIP functions for a presentation P of a group G, then given any other presentation Q of G, there exist constants A, B, C > 0 such that Af(Bn) is a distortion function and Ag(Bn) + Cn is a GIP function for the presentation Q.

Proof:

It is quite easy to check that if G =< X : R > and if X′ is another choice of generators for G, then there are constants A, B > 0 such that the distortion of H in G is Af(Bn) with respect to the generators X′. The proof of this fact consists of rewriting words in F (X′) in terms of the X ’s (and vice versa), and is left as an exercise.

We now see how the GIP function for a presentation behaves under Tietze transformations; this follows along the lines of Gersten’s proof for isoperimetric function ([Ge1]), but we include the proof here for completeness. Let P =< X : R > be a finite presentation for the group G such that the subgroup H < G has GIP function g(n) for this presentation. Let w ∈ F (X) with ℓ(w) = n and \overline{w} ∈ H be given, and let v ∈ F (X) be any word in the generators of the subgroup with \overline{v} = \overline{w}.

Suppose that a presentation Q for G is obtained from P by adjoining a relator r ∈ F (X) , where r is a consequence of the relators in R. Then clearly Area_{P}(v^{−1}w) ≥ Area_{Q}(v^{−1}w) . Now r is the boundary some Dehn diagram in P, say with A faces. Given any Dehn diagram for v^{−1}w in Q, we may subdivide each face labelled r, thus obtaining a Dehn diagram in P, which shows that Area_{P}(v^{−1}w) ≤ A · Area_{Q}(v^{−1}w) .

Now suppose that Q is obtained from P by adjoining one free generator t ∉ X ∪ X^{−1} and adjoining one relator tr^{−1} , where r ∈ F (X) has length B. By Proposition 3.1 we may assume that H has the same set of generators in the two presentations; in particular t does not occur in any of the chosen representative for generators of H. Note that this assumption will only change g(n) by a linear factor. If w, v ∈ F (X) are as above then Area_{P}(v^{−1}w) = Area_{Q}(v^{−1}w) , since any minimal Dehn diagram cannot have an interior edge labelled t, for otherwise the diagram would not be reduced.

Now suppose that w is a word in the generators for Q, and v is as above. As noted above, the only occurrences of t in a Dehn diagram for v^{−1}w occur on the boundary. Since v contains no t ’s by our choice of generators for H, the only occurrences of t in a Dehn diagram for v^{−1}w occur on the part of the boundary containing w, so there are at most n such occurrences of t. We then replace each occurrence of t by the word r to obtain a word v^{−1}u in F (X) , with ℓ(u) ≤ Bn. Given a minimal P diagram for v^{−1}u, we obtain a minimal Q diagram for v^{−1}w by attaching at most n faces with label tr^{−1} along the boundary. Hence Area_{Q}(v^{−1}w) ≤ Area_{P}(v^{−1}u) + n, so that in this case the GIP function with respect to Q is ≤ g(Bn) + n.

It follows from these calculations and from Tietze’s theorem that if the GIP function for H in G is g(n) with respect to a presentation P, then the GIP function with respect to any other presentation is ≤ Ag(Bn) + Cn. ⋄

In view of these propositions we make the following definitions: for functions f, g : N ⟶ N we write f(n) ⪯ g(n) if there exist positive constants A, B, C, D, E such that f(n) ≤ Ag(Bn + C) + Dn + E, and we write f(n) ∼ g(n) if f(n) ⪯ g(n) and g(n) ⪯ f(n) . It is easily verified that this is an equivalence relation, and when speaking of a distortion, GIP or GID function we mean an equivalence class of functions, some member of which is an upper bound for the function in question. When speaking of the distortion or GIP or GID function of H in G, we shall really mean an equivalence class of functions which contains both upper and lower bounds for the actual function.

4 Examples and Constructions

In this section we give some examples of distortion, GIP and GID functions. Some of the proofs are left for later sections; in particular we use Theorem 6.1 repeatedly. Other computations of distortion can be found in [P].

Examples:

1. A subgroup H of a finitely generated free group G is free, and is quasiconvex (see below) if and only if H is finitely generated ([GS]). Hence such finitely generated subgroups H have linear rewrite function, linear GIP and linear GID functions in G. In fact it is not difficult to determine these functions exactly (including the constants); such an argument for the rewrite function is given in [Gr2].

2. For a fixed geodesic section of an abelian group of rank greater than one, there are always finitely generated subgroups which are not quasiconvex ([Br3]). However, for every finitely generated subgroup of a finitely generated abelian group, there exists a geodesic section such that, with respect to this section, the given subgroup is quasiconvex; hence the subgroup has linear rewrite function and quadratic GIP function.

3. Gromov ([Gr2]) claims that the distortion of any subgroup of a finitely generated nilpotent group is polynomial. It should also be true that the GIP and GID functions are polynomial in this case, but a proof of any of these facts seems not to have been written down as of yet. As an example let G =< a, b, c : [a, b] = c, [a, c] = [b, c] = 1 > be the 3-dimensional integral Heisenberg group, and let H = Z(G) =< c > be the center of G. Then c^{n^{2}} = [a^{n}, b^{n}] = a^{n}b^{n}a^{−n}b^{−n}, so it is clear that ||c^{n^{2}}||_{H} = n^{2} while ||c^{n^{2}}||_{G} ≤ 4n; hence H has rewrite function f(n) ∼ n^{2} in G.

4. Let G =< a, b : bab^{−1} = a^{2} >. Then the subgroup H =< a > which is generated by a ∈ G has both distortion and GIP function 2^{n}. However, since G has exponential isoperimetric function, the obvious bound for the GIP function would be 2^{2^{n}} , which is much worse than the actual GIP function. This example generalizes to the other Baumslag-Solitar groups.

5. Finitely generated subgroups of surface groups are quasiconvex ([P, Sw]), hence have linear distortion, GIP and GID functions.

6. It is well known that cyclic subgroups of a negatively curved group G are quasiconvex ([Gr1, GdlH]); hence such subgroups have linear rewrite and GIP functions. There are many examples of negatively curved groups, such as fundamental groups of compact, negatively curved manifolds.

7. Any nilpotent subgroup of the fundamental group of a finite volume negatively curved manifold has polynomial distortion, GIP and GID functions. This follows from the fact that such subgroups are virtually cyclic (hence quasiconvex) in the compact case, and are contained in maximal nilpotent subgroups in the noncompact case. In the latter case, a maximal nilpotent subgroup acts on some horosphere cocompactly, and is quasiconvex. This argument is contained in [Gr2].

As noted in example 4 above, the obvious bound for the GIP function for the subgroup H =< a > of the Baumslag-Solitar group G =< a, b : bab^{−1} = a^{2} > is g(n) ⪯ 22^{n} . We now show that the actual GIP function in this case is precisely g(n) ∼ 2^{n}.

Proposition 4.1 The subgroup H =< a > of the Baumslag-Solitar group G =< a, b : bab^{−1} = a^{2} > has precisely the generalized isoperimetric function g(n) ∼ 2^{n}.

Proof: Let w ∈ F (a, b) with ℓ(w) = n be given. We will put w in the form a^{n}b^{m}, and will keep track of how many (conjugates of) relators we need to do this. Note that ba = Ra^{2}b, where R = bab^{−1}a^{−2} is the basic relator of G. Hence we can move any single b to the right of any a at the cost of creating 2 more a ’s and a single relator. Also note that if u ∈ F (X) is any word, then Ru = u(u^{−1}Ru) , so that we may immediately move any relator completely to the right at the cost of increasing only the length of the conjugating element, not the number of (conjugates of) relators. We begin by moving the right-most b to the right of all of the a ’s. Since there are at most n a ’s to cross, this creates at most n new a ’s and n relators. Moving the next b to the right of the a ’s then creates at most 2n new a ’s and 2n new relators. It is easy to see that moving the i th b to the right of all the a ’s creates at most 2^{i} new a ’s and 2^{i} new relators. Since there are at most n b ’s to start with, we can put w in the form

w = a^{r}b^{s} ∏_{i=1}^{N} z_{j}Rz_{j}^{−1}, z_{j} ∈ F (X)

with N ≤ ∑_{i=0}^{n} 2^{i}n ≤ n^{2}2^{n} ∼ 2^{n}. Now \overline{w} ∈ H if and only if s = 0 , and we are done.

Let f(n) denote the distortion of H in G. Since f(n) ≤ Mg(n) for some constant M (see equation (8) in Section 7), it is clear that 2^{n}/M is a lower bound for g(n) since f(n) = 2^{n}. ⋄

Remark: The first half of proof of Proposition 4.1 also provides a simple proof of the well-known fact that G satisfies an exponential isoperimetric inequality. Both parts of the proof work for the Baumslag-Solitar groups G_{1,q} =< a, b : bab^{−1} = a^{q} >, with q > 1 .

As another way of obtaining examples we give the following proposition, whose proof is rather straightforward and is left as an exercise for the reader.

Proposition 4.2 Let K < H < G. Let f_{1}(n), g_{1}(n), h_{1}(n) (resp. f_{2}(n), g_{2}(n), h_{2}(n) ) be distortion, GIP and GID functions for K in H (resp. H in G). Then K < G has

distortion  f_{1} ∘ f_{2}(n)
GIP function g_{2}(n) + g_{1}(f_{2}(n))
GID function h_{2}(n) + h_{1}(f_{2}(n))

5 Lattices in Isom(H^{2}×H^{2}) and the Complexity of Mihailova’s Construction

The geometry of H^{2} × H^{2} is extremely interesting, and indeed this space is a basic example of a higher rank symmetric space. Certain lattices ^{2} in Isom(H^{2} × H^{2}) , namely uniform lattices which do not virtually split as a product of surface groups, are candidates (according to Thurston) for counterexamples to some of the major unsolved questions in the theory of automatic groups ([Fa]). Problems concerning products of free groups F_{n}×F_{n} are also of considerable interest because of their close connection with problems about 3-manifolds, including a group-theoretic statement concerning homomorphisms of hyperbolic surface groups onto products of free groups, which has been shown by Stallings and Jaco to be equivalent to the Poincaré conjecture (for this and other connections with 3-manifolds, see [LS], p.194-5). For these reasons we believe that the geometry of products of free groups, and more generally lattices in Isom(H^{2} ×H^{2}) , deserves to be better understood.

We now recall an example due to Mihailova which shows that the generalized word problem is unsolvable for certain (nonuniform) lattices in Isom(H^{2}× H^{2}) . This example, given by Mihailova in 1958 ([Mi]), was the first example of a group with solvable word problem but unsolvable generalized word problem; it can be used to construct many examples of distortion, GIP and GID functions. It should be noted that the statement made by Gromov in [Gr2] concerning the distortion of Mihailova’s example seems to be incorrect.

Let G =< x_{1}, …, x_{m} : R_{1}, …, R_{s} > be any finitely presented group, and let F_{m} denote the free group on {x_{1}, …, x_{m}}. There is a natural map π : F_{m} × F_{m} ⟶ G × G which is the product of the natural map F_{m} ⟶ G with itself. Let

H = π^{−1}({(g, g) : g ∈ G})

so that H < F_{m} × F_{m} and H is generated by {(x_{i}, x_{i})}_{i=1}^{m} ∪ {(1, R_{j})}_{j=1}^{s} (see [LS], Chap. IV). Note that (u, v) ∈ H if and only if \overline{u} = \overline{v} in G, so taking G to be a finitely presented group with unsolvable word problem shows that H has unsolvable generalized word problem in F_{m} × F_{m}. In other words, the distortion of the finitely generated subgroup H in F_{m} ×F_{m} is non-recursive.

2Recall that a lattice in a Lie group is a cofinite volume discrete subgroup; a uniform lattice is a cocompact lattice.

Proposition 5.1 (Mihailova’s Construction) Let G and H be groups as given above, and let F (n), H(n) be isoperimetric and isodiametric functions, respectively, for G. Then H < F_{m} × F_{m} has distortion f(n) ⪯ F (n)H(n) .

Proof: We take the set {(x_{1}, 1), …, (x_{m}, 1), (1, x_{1}), … (1, x_{m})} as a generating set for K = F_{m} ×F_{m}, and consider the natural map F_{2m} ⟶ F_{m} ×F_{m} denoted by w ⟼ \overline{w}. Given w ∈ F_{2m}, we may write \overline{w} = (u, v) with u, v ∈ F_{m}. Note that ||\overline{w}||_{K} = ℓ(u) + ℓ(v) , so in particular ℓ(u), ℓ(v) < ||\overline{w}||_{K} . Also note that \overline{w} ∈ H if and only if \overline{u} = \overline{v} in G; in this case we may write

u^{−1}v = ∏_{i=1}^{N} z_{j}R_{j}z_{j}^{−1}, z_{j} ∈ F_{m}, R_{j} ∈ R ∪ R^{−1}

with

N ≤ F (ℓ(uv^{−1})) ≤ F (||\overline{w}||_{K})

and

ℓ(z_{j}) ≤ H(ℓ(uv^{−1})) ≤ H(||\overline{w}||_{K}).

Now \overline{w} = (u, u) · (1, u^{−1}v) , and

(1, z_{j}R_{j}z_{j}^{−1}) = (z_{j}, z_{j})(1, R_{j})(z_{j}, z_{j})^{−1}.

By the choice of generating set for H, we see that \overline{w} may be written as a product of at most

ℓ(u) + N · (2H(||\overline{w}||_{K}) + 1) ≤ ||\overline{w}||_{K} + F (||\overline{w}||_{K})(2H(||\overline{w}||_{K}) + 1)

generators of H; hence f(n) ⪯ F (n)H(n) . ⋄ Remark: It is well known that every free group F_{n}, n > 1 can be realized as a lattice in Isom(H^{2}) , so that F_{n} × F_{n}, n > 1 can be realized as a lattice in Isom(H^{2} × H^{2}) .

Question: Do uniform lattices in Isom(H^{2} ×H^{2}) have solvable generalized word problem? How about lattices in Isom(H^{3}) ?

6 The Quasiconvexity Condition

In this section we introduce a geometric condition on subgroups which, if satisfied, gives bounds on the distortion, GIP and GID functions for that subgroup; indeed this condition characterizes those subgroups for which the generalized word problem can be solved.

Let σ : G ⟶ A^{∗} be a (perhaps multi-valued) section of the natural map from the free monoid A^{∗} onto G; hence σ can be viewed as a choice of paths from the identity to each vertex in the Cayley graph Γ_{X}(G) . Sometimes we will consider only the restriction of such sections to a subgroup H < G. We say that the section σ has length ψ(n) if ℓ(σ(g)) ≤ ψ(||g||_{G}) for all g ∈ G. Note that geodesic sections have length ψ(n) = n, and quasigeodesic sections have linear length.

If H < G is finitely generated, we say that q : N ⟶ N is a quasiconvexity function for (H, σ) if, for all h ∈ H, the path σ(h) in the Cayley graph Γ_{X}(G) lies in a q(||h||_{G}) -neighborhood of H. In this case we say that H is (σ, q(n)) -quasiconvex, or simply q(n) -quasiconvex when the section is understood. When σ is a section consisting of geodesics and when q(n) is constant, we simply say that H is quasiconvex. Quasiconvexity has been studied extensively (see [AB, CDP, GS, Sh], for example). We study quasiconvexity functions for general sections, and not just for geodesic sections, since the study of sections (which some authors call ‘combings’) with greater than linear length has proven to be necessary and useful ([Br1, Br2, BP]).

Remark: For a fixed subgroup H in G, the quasiconvexity function q(n) depends strongly on the section σ, even when considering different geodesic sections. For example, let H be the cylic subgroup generated by ab ∈ G, where G is the free abelian group of rank 2, G =< a, b : aba^{−1}b^{−1} >. Let σ, τ : G ⟶ {a, b, a^{−1}, b^{−1}}^{∗} be the sections defined by σ(a^{n}b^{m}) = (ab)^{n}b^{m−n} and τ(a^{n}b^{m}) = a^{n}b^{m}. Then (H, σ) has quasiconvexity function q(n) = 1 , while (H, τ) has quasiconvexity function q(n) = n/2 .

Two basic examples should be kept in mind :

Examples:

1. Suppose σ is any section consisting of geodesics. Then q(n) = n/2 is a quasiconvexity function for (H, σ) . This is clear since a path of length n which begins and ends in H can obviously only stray a distance of at most n/2 from H.

2. Let H < G with generating set \overline{Y}, where Y = \{y_{1}, …, y_{m}\}, y_{i} ∈ F (X) , have distortion f(n) , and let C = max_{i}ℓ(y_{i}) . Any h ∈ H is represented by a word w ∈ (Y ∪ Y^{−1})^{∗} with ℓ_{Y}(w) ≤ f(||h||_{G}) , by definition of distortion. Considered as a path in G, w has length at most Cf(||h||_{G}) . Hence there is a section of G which, restricted to H, has length at most Cf(n) , and which has quasiconvexity function q(n) = C/2 .

We have just seen that every group admits some section, in fact a geodesic section, so that any subgroup has quasiconvexity q(n) = n/2 . If we weaken this condition as little as possible by assuming that there exists some (perhaps incredibly long) section of G for which the subgroup H has quasiconvexity q(n) ≤ n/2 − 1 , then surprisingly much can be said; in particular H will be finitely generated and have solvable generalized word problem in H. More precisely we have the following:

Theorem 6.1 Let σ : G ⟶ A^{∗} be a section of length ψ(n) , and let F (n) be an isoperimetric function for G. If H < G has σ -quasiconvexity q(n) with q(n) ≤ n/2 − 1 for all n ≥ N for some N , then H is finitely generated. Furthermore in this case, if f(n) and g(m) are increasing functions satisfying

f(n) ≥ ψ(n)f(2q(n) + 1)  (3)
g(m) ≥ ψ(m)g(2q(m) + 1) + F (m + ψ(m))  (4)

then f(n) and g(m) are distortion and generalized isoperimetric functions, respectively, for H in G.

Proof: Suppose that q(n) ≤ n/2 − 1 for all n ≥ N . Let Y = \{w : \overline{w} ∈ H, ℓ(w) ≤ N\}; note that Y = Y^{−1} . We shall show that \overline{Y} generates H, and will compute f(n) and g(m) with respect to this generating set. Let any word w with \overline{w} ∈ H be given. The proof proceeds by induction on ||\overline{w}||_{G}.

If ||\overline{w}||_{G} = 1 then the only point that need be mentioned is the fact that g(ℓ(w)) ≤ F (ℓ(w)) as desired. So now suppose that the theorem holds for all w with \overline{w} ∈ H and ||\overline{w}||_{G} ≤ n − 1 .

Now suppose that v is a word with \overline{v} ∈ H and ||\overline{v}||_{G} = n. Let w = σ(v) , so that the path w stays within q(n) = n/2−1 of H and \overline{w} = \overline{v}. Note that v may not stay close to H, and that w has length at most ψ(n) , which may indeed be much greater than ||\overline{v}||_{G} = n. Write w = a_{1} ⋯ a_{r}, where each a_{i} one of the original (fixed) generators for G and r ≤ ψ(n) . For 1 ≤ i ≤ r−1 , let g_{i} be a path of minimal length from a_{1} ⋯ a_{i} to H (see figure 1); also set g_{0} = g_{r} = 1 . Let w_{i} = g_{i−1}^{−1}a_{i}g_{i}, so that w = ∏_{i=1}^{r} w_{i}. Since w_{i} is a path which begins and ends in H, we see that \overline{w_{i}} ∈ H. Further,

||\overline{w_{i}}||_{G} ≤ ℓ(w_{i})
≤ 2q(n) + 1
≤ 2(n/2 − 1) + 1
= n − 1.

By induction, since \overline{w_{i}} ∈ H with ||\overline{w_{i}}||_{G} ≤ n−1 , each w_{i} can be written in the form

w_{i} = y_{d_{1}} ⋯ y_{d_{k}} ∏_{j=1}^{N} z_{j}R_{j}z_{j}^{−1}, y_{d_{s}} ∈ Y, z_{j} ∈ F (X), R_{j} ∈ R.

with k ≤ f(||\overline{w_{i}}||_{G}) ≤ f(2q(n) + 1) and with N ≤ g(ℓ(w_{i})) ≤ g(2q(n) + 1) . Since w = ∏_{i=1}^{r} w_{i}, we see that \overline{w} can be written as a product of at most ψ(n)f(2q(n)+1) ≤ f(n) elements of \overline{Y}. If R_{i} is a conjugate of a relator and z is any word, then Rz = z(z^{−1}Rz) , so that, after writing w = ∏_{i=1}^{r} w_{i}, all relators may be moved all the way to the right at the cost of

Figure 1: A path with quasiconvexity q(n) ≤ n − 1 .

increasing only the length of the conjugating elements, while leaving the number of conjugates of relators and elements of Y fixed. From this observation it now follows that we may write w as in (1) with N ≤ ψ(n)g(2q(n)+1) conjugates of relators.

Now the originally given word v had \overline{v} = \overline{w} so that \overline{v} can be written as a product of at most f(n) elements of \overline{Y}; in particular \overline{Y} is finite and generates H. Further, since vw^{−1} represents 1 ∈ G, we may write vw^{−1} of a product of at most

\begin{aligned}F (ℓ(v) + ℓ(w)) & ≤ F (ℓ(v) + ψ(||\overline{v}||_{G})) \\ & ≤ F (ℓ(v) + ψ(ℓ(v))) \end{aligned}

relators and their conjugates, since F (n) is an isoperimetric function for G. Combining this with the above implies that we may write v as in (1) with

\begin{aligned}N & ≤ ψ(n)g(2q(n) + 1) + F (ℓ(v) + ψ(ℓ(v))) \\ & ≤ ψ(ℓ(v))g(2q(ℓ(v)) + 1) + F (ℓ(v) + ψ(ℓ(v))) \end{aligned}

and we are done, since g(m) is considered as a function of ℓ(v) , not of ||\overline{v}||_{G}. The point of replacing the word v by the word w is that we have some control on the behavior of the path w, while the path v is arbitrary. ⋄

Remark: The conclusion of Theorem 6.1 is the best possible, for there exist subgroups with q(n) = n/2 which are not finitely generated; for example the commutator subgroup of a free group of rank two is infinitely generated but has q(n) = n/2 for any geodesic section. There also exist cases where H < G is finitely generated but H has non-recursive distortion, even though q(n) = n/2 for any geodesic section (cf. Section 5)

To illustrate some explicit bounds which may be obtained from Theorem 6.1 we give the following corollary.

Corollary 6.2 Let σ : G ⟶ A be a section of length ψ(n) , and let q(n) be the quasiconvexity function for (H, σ) , where H is a finitely generated subgroup of G. Let f(n) denote the distortion of H in G. Then

1. If q(n) = n/2 − 1 then f(n) ⪯ 2^{ψ(n)logψ(n)} .

2. If q(n) = C then f(n) ≤ C′ψ(n) for some C′ > 0 .

3. If q(n) ⪯ n^{α}, 0 ≤ α < 1 and ψ(n) ∼ n^{d}, d ≥ 1 then f(n) ⪯ n^{d/(1−α)} .

4. If q(n) ⪯ (logn)^{r}, r ≥ 1 and ψ(n) ∼ n^{d}, d ≥ 1 then f(n) ⪯ n^{d}(logn)^{dr+1} .

Proof: It is not difficult to check that, in each case, the function f(n) satisfies the condition f(n) ≥ ψ(n)f(2q(n) + 1) . The result then follows from Theorem 6.1. ⋄

As another corollary we obtain the following characterization of those subgroups for which the generalized word problem can be solved.

Corollary 6.3 Let H be a finitely generated subgroup of a group G whose word problem is solvable. Then the generalized word problem for H in G is solvable if and only if there exists a section σ : G ⟶ A^{∗} with recursive length such that (H, σ) has quasiconvexity q(n) ≤ n/2 − 1 .

Proof: If the GWP is solvable for H in G, then the distortion f(n) is a recursive function by Proposition 2.1. The construction given in Example 2 on page 16 then gives a section σ of length Cf(n) such that q(n) = C/2 is a quasiconvexity function for (H, σ) . The converse implication follows immediately from Corollary 6.2(1) and the fact that if the distortion f(n) is recursive then H has solvable generalized word problem in G (Proposition 2.1). ⋄

7 The Relationship Between Distortion, GIP, and GID Functions

In this section we explore the relationship between the distortion, GIP and GID functions; in particular we shall see that a bound on any one of these functions gives a bound on the other two. We also give an extension of the Cohen-Gersten Double Exponential Theorem ([Ge3]).

Let F (n) (resp. H(n) ) be an isoperimetric (resp. isodiametric) function for a group G =< X : R >. Let H < G have distortion, GIP and GID functions f(n), g(n) and h(n) , respectively. Let M be the maximum length of an element of R, and let Y = \{y_{1}, … y_{m}\} be such that \overline{Y} generates H. Given a word w ∈ F (x) of length n with \overline{w} ∈ H, there exists v ∈ F (Y) with ||\overline{v}||_{H} ≤ f(||\overline{w}||_{G}) such that, when v is considered as an element of F (X) , \overline{w} = \overline{v}. Hence there is a Dehn diagram for the word wv^{−1} whose boundary has length at most ℓ(w) + ℓ(v) ≤ n + Cf(n) , where C > 0 is the maximal length (in F (X) ) of an element of Y. This Dehn diagram has at most F (n + Cf(n)) faces. It is clear then that

g(n) ≤ F (n + Cf(n)) ∼ F ∘ f(n)  (5)
h(n) ≤ H(n + Cf(n)) ∼ H ∘ f(n)  (6)

as long as both H and G are infinite (for otherwise f(n) or F (n) is constant and the statement is trivial). Since this Dehn diagram realizes wv^{−1} as a product of conjugates of relators, we see that each conjugating element has length at most M times the number of faces plus the length of the boundary; in other words

h(ℓ(w)) ≤ Mg(ℓ(w)) + (ℓ(w) + Cf(||\overline{w}||_{G}))  (7)

so that

h(n) ≤ Mg(n) + (Cf(n) + n) ∼ g(n) + f(n)

again assuming that H is infinite. Now each edge which is part of the word v on the boundary of the Dehn diagram is part of some face (i.e. relator), and any face contains at most M of these edges. It clearly follows that

f(n) ≤ Mg(n).  (8)

Equations 5,6,7 and 8, together with Proposition 7.1, show that any bound on one of f(n), g(n), h(n) gives bounds on the other two; in particular, since we are assuming that G has solvable word problem (so that both F (n) and H(n) are recursive) we see that if one of f(n), g(n), h(n) are recursive, then so are the other two. In this case the generalized word problem is solvable for H in G.

The following proposition is an extension of the Cohen-Gersten Double Exponential Theorem ([Ge3]).

Proposition 7.1 Let h(n) be a generalized isodiametric function for H in G. Then there exist constants a, b > 0 so that a^{bh(n)+n} is a generalized isoperimetric function for H in G.

Proof: The proof of Proposition 7.1 follows precisely along the lines of Gersten’s proof for the case H = 1 , which is given in [Ge3]. We provide a sketch of the proof of the general case here.

Let G =< X : R > be a finite presentation for G, denote by N the normal closure of the relators in F (X) , and let {y_{1}, …, y_{m}}, y_{i} ∈ F (X) be a set of representatives for a set of generators for H in G. Let N_{k} < N < F (X) denote the subgroup generated by all elements R_{i}^{u} = uR_{i}u^{−1} with R_{i} ∈ R, ℓ(u) ≤ k, together with the elements {y_{1}, …, y_{m}}. Let w ∈ F (X), ℓ(w) = n be given such that \overline{w} ∈ H. Note that \overline{w} ∈ H if and only if w ∈ N_{h(n)} , by definition.

If B = 2|X| is twice the number of generators of G, then the number of elements in the ball of radius r in the Cayley graph Γ_{X}(G) is at most B^{r}. Thus the number of generators of the subgroup N_{h(n)} is at most |R|B^{h(n)} + m. Let M be the maximum length of a generator for N_{h(n)} , so clearly there exist constants C, D > 0 such that M ≤ Ch(n) + D. Lemma 2.3 of [Ge3] analyzes Stallings’ folding algorithm for subgroups of free groups ([St]) to show that each so-called ‘Stallings basis element’ of N_{h(n)} is a product of at most 3^{(Ch(n)+D)(|R|B^{h(n)}+m)} of the original generators. Lemma 2.4 of [Ge3] shows that n is an upper bound for the number of Stallings basis elements needed in a factorization of w. Hence the total number of relators of G and their conjugates which are needed to represent w is

(# of Stall. elts.)(length of Stall. elt.) ≤ n3(Ch(n) + D)(|R|Bh(n) + m)
≤ abh(n) + n

for some constants a, b > 0 . In other words, g(n) ≤ abh(n) + n . ⋄

Question: Does there exist a constant a > 0 such that ah(n) is a GIP function for H in G, where h(n) is a GID function? In the case when H = 1 this seems to be known as the “Stallings conjecture”. This conjecture is best possible ([Ge3]).

8 Applications to Isoperimetric and Isodiametric Functions

In this section we give an application to isoperimetric and isodiametric functions in groups. Little is known about isoperimetric (or isodiametric) functions for quotients G/H. The only result along these lines is a theorem of Short ([Sh]) which states that if H is a quasiconvex, normal subgroup of a bicombable group G, then G/H satisfies a quadratic isoperimetric inequality. The results in this section extend Short’s result to a very general form; indeed they provide added motivation for the study of distortion and GIP functions.

Theorem 8.1 Let H be a finitely generated, normal subgroup of G with distortion f(n) , GIP function g(n) , and GID function h(n) . Then f(n) + g(n) is an isoperimetric function and h(n) is an isodiametric function for the group G/H.

Proof: Propositions 3.2 and 3.1 show that isoperimetric, distortion, and GIP functions are independent of the choice of presentation for G and choice of generators for H. Hence we assume that G has the presentation G =< X : R >=< h_{1}, …, h_{m}, x_{1}, … x_{n} : R_{1}, …, R_{k} >, where the generators Y = \{h_{1}, …, h_{m}\} are such that H is generated by \overline{Y} = \{\overline{h_{1}}, …, \overline{h_{m}}\} (we also assume, for simplicity, that Y = Y^{−1} ). Then G/H has a presentation

G/H =< h_{1}, …, h_{m}, x_{1}, …, x_{n} : R_{1}, … R_{k}, h_{1}, …, h_{m} >

Let a word w with \overline{w} = 1 ∈ G/H be given. Then the word w may also be considered as representing \overline{w} ∈ H < G, in which case we may write

w = h_{i_{1}} ⋯ h_{i_{r}} ∏_{j=1}^{N} z_{j}R_{u_{j}}z_{j}^{−1}, z_{j} ∈ F (X), R_{u_{j}} ∈ R ∪ R^{−1}

with r ≤ f(||\overline{w}||_{G}), N ≤ g(ℓ(w)) and ℓ(z_{j}) ≤ h(ℓ(w)) . Since each h_{i_{p}} and each R_{u_{j}} is a relator of G/H, we see that we have just written w as a product of at most f(||\overline{w}||_{G}) + g(ℓ(w)) ≤ f(ℓ(w)) + g(ℓ(w)) relators of G/H and their conjugates, with each conjugating element having length at most h(ℓ(w)) . ⋄

Theorem 8.1 can be applied to the case when we are given an isoperimetric function for G, and we want to determine an isoperimetric function for the quotient G/H. In the next two corollaries we fix a group G =< X : R >, a finitely generated subgroup H < G, and a set of words Y = \{y_{1}, …, y_{m}\}, y_{i} ∈ F (X) such that \overline{Y} generates H. Let C be the maximal length (in F (X) ) of an element of Y.

Corollary 8.2 Let H be a finitely generated, normal subgroup of G with distortion f(n) . If F (n) is an isoperimetric function for G then F ∘ f(n) is an isoperimetric function for the group G/H.

Proof: It is clear that g(n) ≤ F (n + Cf(n)) ∼ F ∘ f(n) ; the second implication follows from the fact that F (n) is at least linear (assuming G is infinite; otherwise both F (n) and f(n) are constant functions). The corollary now follows immediately from Theorem 8.1. ⋄

Theorem 8.1 may also be applied to determine the isodiametric function of the quotient G/H in terms of the isodiametric function of G.

Corollary 8.3 Let H be a finitely generated, normal subgroup of G with distortion f(n) . If H(n) is an isodiametric function for G then H ∘ f(n) is an isodiametric function for the group G/H.

Proof: It is clear that h(n) ≤ H(n + Cf(n)) ∼ H ∘ f(n) ; the second implication follows from the fact that f(n) is at least linear (assuming that H is infinite; for otherwise f(n) is constant and the statement is trivial). The corollary now follows immediately from Theorem 8.1. ⋄

As an important special case of Corollaries 8.2 and 8.3 we give the following

Corollary 8.4 Let H be a finitely generated normal subgroup of G which is quasiconvex with respect to some quasigeodesic section. Then any isoperimetric function for G is an isoperimetric function for G/H, and any isodiametric function for G is an isodiametric function for G/H.

Remark: Theorem 8.1 gives a better estimate than Corollaries 8.2 and 8.3 since, as we have seen, F (n + f(n)) and H(n + f(n)) are not always the best upper bounds for GIP and GID functions, respectively.

9 Some Open Questions

The extrinsic geometry of subgroups provides a new context in which to explore the geometry of groups. It allows for construction of a great number of examples, and a way of studying these and known examples in a more in-depth way. There are many questions to be explored, a few of which we list here.

1. Show that the generalized word problem is solvable for fundamental groups of surface bundles over the circle. Does the fundamental group of every Haken 3-manifold have solvable GWP? One may assume here that the manifold is irreducible. As a first step, show that GWP is solvable for surface groups inside Haken 3-manifold groups. Show that the fundamental group of a hyperbolic 3-manifold has solvable GWP. Note that there exist negatively curved groups with finitely generated normal subgroups which have unsolvable GWP ([Ri]). Note also that the generalized word problem is solvable for fundamental groups of closed 3-manifolds modelled on one of the geometries S^{3}, R^{3}, S^{2}×R, Nil, Sol.

2. Given a finitely presented group H with solvable word problem, can H be embedded in finitely presented group G so that G has solvable word problem but the generalized word problem is not solvable for H in G? Note that if U is a finitely presented group with unsolvable word problem then H has unsolvable GWP in H × U , but H × U itself has unsolvable word problem. Which triples (f(n), F (n), H(n)) can occur, where f(n) is the distortion of H in G and F (n) (resp. H(n) ) is an isoperimetric function for G (resp. H)?

3. Is the generalized word problem a geometric property; that is, if G has solvable generalized word problem and if G is quasi-isometric to H, does H have solvable GWP?

4. Do cocompact irreducible discrete subgroups of Isom(H^{2} × H^{2}) have solvable generalized word problem? Note that this is not the case for cofinite volume discrete subgroups of Isom(H^{2} × H^{2}) (cf. Section 5).

5. Let f(n) be the distortion of H in G, and let F (n) and H(n) be the isoperimetric and isodiametric functions, respectively, for G. We have seen that the obvious estimates F ∘ f(n) and H ∘ f(n) (cf. Section 7) are not nearly the best upper bounds for the GIP and GID functions for H in G. For which groups are these the best upper bounds?

References

[AB] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short, Notes on Word Hyperbolic Groups , in Group Theory from a Geometric Viewpoint, World Scientific, Singapore, 1991.

[Br1] M. Bridson, Combing the Fundamental Group of a Haken 3manifold, preprint, Princeton University.

[Br2] M. Bridson, The Geometry of Normal Forms in Discrete Groups, Proc. London Math. Soc., to appear.

[Br3] M. Bridson, Regular Combings, Nonpositive Curvature and the Quasiconvexity of Abelian Subgroups, preprint, Princeton University.

[BP] M. Bridson and Ch. Pittet, Isoperimetric Inequalities for the Fundamental Groups of Torus Bundles Over the Circle, preprint.

[BG] M. Bridson and S. Gersten, The Optimal Isoperimetric Inequality for Z ×_{A}Z, preprint, University of Utah, 1992.

[CDP] M. Coornaert, T. Delzant, A. Papadopoulos, Notes sur les groupes hyperboliques de Gromov, Springer Lecture Notes, vol. 1441.

[E et al.] D.B.A. Epstein, J. Cannon, D.F. Holt, S. Levy, M.S. Paterson and W.P. Thurston, Word Processing in Groups, Jones and Bartlett, 1992.

[Fa] B. Farb, Automatic Groups: a Guided Tour, L’Enseign. Math., Vol.38 (1992), p.291-313.

[Ge1] S.M. Gersten, Dehn Functions and ℓ_{1} -norms of finite presentations, in Proceedings of the Workshop on Algorithmic Problems, C.F. Miller III and G. Baumslag, ed., Springer MSRI series, Springer-Verlag, New York, 1992.

[Ge2] S.M. Gersten, Isodiametric and Isoperimetric Inequalities in Group Extensions, preprint.

[Ge3] S.M. Gersten, The Double Exponential Theorem for Isodiametric and Isoperimetric Functions, preprint, 1992.

[Ge4] S.M. Gersten, Isoperimetric and Isodiametric Functions in Finite presentations, preprint, 1992.

[GdlH] E. Ghys and P. de la Harpe, editors, Sur les groupes Hyperboliques d’aprés Mikhael Gromov, Progress in Mathematics, Vol. 83, Birkhaüser, 1990.

[Gh] E. Ghys, Les Groups Hyperboliques, Séminaire Bourbaki, march 1990.

[Gr1] M. Gromov, Hyperbolic groups, Essays in Group Theory, Springer Verlag, MSRI series Vol. 8, S.M. Gersten, ed., 1987, pp. 75-263.

[Gr2] M. Gromov, Asymptotic Invariants of Groups, preprint, 1992.

[GS] S.M. Gersten and H. Short, Rational Subgroups of Biautomatic Groups, Annals of Math., 134 (1991), 125-158.

[LS] R.C. Lyndon and P.E. Schupp, Combinatorial Group Theory, Berlin-Heidelberg-New York: Springer 1977.

[Ma] W. Magnus, Das Identitätsproblem für Gruppen mit einer definierenden Relation, Math. Annalen 106 (1932), p.295-307.

[Mi] K.A. Mihailova, The occurence problem for direct products of groups, Dokl. Akad. Nauk SSSR 119 (1958), p.1103-1105.

[Ni] J. Nielsen, Om Regning med ikke Kommutative Faktorer og dens Anvendelse i Gruppeteorien, Matematisk Tidsskrift B (1921), p.77-94. English translation: Math. Scientist 6, (1981), p.73-85.

[P] Ch. Pittet, Géométrie Des Groupes. Inégalités Isopérimétriques de Dimension 2 et Distortions., Thesis, Universite de Geneve, 1992.

[Po] V. Poenaru, Geometry “á la Gromov” for the fundamental group of a closed 3-manifold M^{3} and the simple connectivity at infinity of M̃^{3} , preprint, Université de Paris-Sud, Orsay, Nov. 1990.

[Ri] E. Rips, Subgroups of Small Cancellation Groups, Bull. London Math. Soc. 14 (1982), p.45-47.

[Sh] H. Short, Groups and combings, preprint, Ecole Normale Supérieure de LYON, July 1990.

[SG] J. Stallings and S.M. Gersten, Casson’s idea about 3-manifolds whose universal cover is R^{3} , Int. Jour. of Alg. and Comp., Vol.1, No.4 (1991), 395-406.

[St] J. Stallings, Topology of Finite Graphs, Invent. Math. 71 (1983), p.551-565.

[Sw] G. Swarup, Geometrical Finiteness and Rationality, preprint, 1990.

Math Department, Princeton University

Current Address: Math Department, Univ. of California, Berkeley

E-mail: farb@math.berkeley.edu