Continuously many quasiisometry classes of 2-generator groups B. H. Bowditch Faculty of Mathematical Studies, University of Southampton, Highfield, Southampton SO17 1BJ, Great Britain. bhb@maths.soton.ac.uk [First draft: July 1996. Revised: October 1997]

In the course of his construction of groups of intermediate growth, Grigorchuk [Gri] showed that there are continuously many quasiiometry classes of 2-generator groups. In this paper, we describe another class of groups exhibiting the latter phenomenon, and for which the demonstration is elementary. Unlike those of Grigorchuk, our groups have exponential growth, and can be taken to be torsion free. In fact, they can be exhibited explicitly as small cancellation groups as follows.

Let P(N) be the set of subsets of the natural numbers, N. Given F, F′ ∈ P(N), we write F ∼ F′ if the symmetric difference of F and F′ is finite. This defines an equivalence relation on P(N) with every equivalence class countable. There are thus continuously many equivalence classes.

Given F ∈ P(N), let S(F) = {2^{2^{n}} | n ∈ F }. Given p ∈ N, let w_{p}(a, b) = (a^{p}b^{p})^{7} be the (cyclic) word in two letters, a and b. Given S ⊆ N, let Γ(S) be the group with presentation ⟨a, b | (w_{p}(a, b))_{p∈S}⟩. We show:

Proposition 1 : If F, F′ ∈ P(N) are such that Γ(S(F)) and Γ(S(F′)) are quasiisometric, then F ∼ F′.

We chose the words (a^{p}b^{p})^{7} for simplicity. The groups thus defined have 7-torsion. If we want torsion-free groups, we could for example use the words a(a^{p}b^{p})^{12} instead.

This construction is clearly quite arbitrary. Its essential features may be summarised as follows. We chose the cyclic words w_{p} so as to satisfy the C′(1/6) cancellation property (see, for example [LS]). This means that if w′ is a common (linear) subword of w_{p} and w_{q}, then either p = q or 6L(w′) < min{L(w_{p}), L(w_{q})}. Here, L denotes the length of a word. Note that L(w_{p}) = 14p, so in the presentation of one of our groups, the lengths of relators grow superexponentially. Any construction retaining these features should serve for our purposes. Note that if we were to use the words a(a^{p}b^{p})^{12}, then the resulting groups would be torsion-free — in a small cancellation group, any torsion must show up in the cyclic symmetry of one of the relators, see [LS]. (The examples described by Grigorchuk are torsion groups.)

One obvious corollary of the above proposition is the result of B. H. Neumann [N] that there are continuously many finitely generated groups up to isomorphism. There are now many proofs of this around, though most of these arguments seem to be essentially algebraic in nature and in particular tend to make some use of torsion.

Quasiisometry classes

The quasiisometry invariant that distinguishes Grigorchuk’s groups is the growth function. Indeed, the main objective of that paper was to construct groups of superpolynomial but subexponential growth. In contrast, our groups are all non-amenable. In fact, they all contain non-cyclic free subgroups. Consider, for example, the elements a^{5}b^{6} and a^{7}b^{8}. The existence of a Dehn algorithm for C′(1/6) groups shows that no non-trivial reduced word in these elements can represent the trivial element in the group. They therefore generate a free group.

Our quasiisometry invariant, though in principle applicable to any finitely generated group, is tailored to our particular examples. It would be interesting to search for other kinds of quasiisometry invariants (for example among those suggested in [Gro]) that are capable of distinguishing continuously many quasiisometry classes while remaining reasonably amenable to computation.

The idea of the proof of Proposition 1 is very simple. In a small cancellation group, the lengths of the relators determine the sizes of the “holes” in the Cayley graph, and so give rise to a geometrically defined subset of the natural numbers. This subset can change only by a linearly bounded amount under quasiisometry. By arranging that it grows superexponentially, we can recover, up to finite ambiguity, the original set of natural numbers used for our presentation. To do this properly, we need a few definitions.

Let X be a connected graph with vertex set V (X). Let d_{X} be the combinatorial distance function defined on V (X). If Y is another graph, and k ∈ N, we say that a map ϕ : V (X) ⟶ V (Y) is k-lipschitz if for all x, y ∈ X, we have d_{Y} (ϕ(x), ϕ(y)) ≤ kd_{X}(x, y). Note that a 1-lipschitz map ϕ : V (X) ⟶ V (Y) extends to a map ϕ : X ⟶ Y in which every edge of X is either mapped homeomorphically to an edge of Y or is collapsed to a vertex of Y. We say that two graphs X and Y are k-quasiisometric if there are k-lipschitz maps ϕ : V (X) ⟶ V (Y) and ψ : V (Y) ⟶ V (X) such that d_{X}(x, ψ ∘ ϕ(x)) ≤ k for all x ∈ X and d_{Y} (y, ϕ ∘ ψ(y)) ≤ k for all y ∈ Y.

A cycle, β, is a graph homeomorphic to a circle. We write L(β) for the number of vertices (or edges) of β. A net, σ, is the 1-skeleton of a cellulation of the topological disc (i.e. a presentation of the disc as a CW-complex in which every closed 2-cell is embedded). We imagine σ as coming equipped with certain preferred subcycles, namely, its boundary, ∂σ, and the set, C(σ), of boundaries of 2-cells. Let M(σ) = max{L(γ) | γ ∈ C(σ)}.

Let X be a graph. A loop in X consists of a 1-lipschitz map, f : β ⟶ X from a cycle, β, into X. A spanning disc for the loop, (β, f) consists of a 1-lipschitz map, f : σ ⟶ X of a net, σ, into X, where we have identified β with ∂σ in such a way that f|∂σ agrees with f as already defined on β. Let H(β, f) be the minimum value of M(σ) as σ ranges over all nets which give rise to spanning discs for (β, f) in this way. Clearly, H(β, f) ≤ L(β).

Definition : A loop, (β, f) is taut if L(β) = H(β, f).

We write H(X) ⊆ N for the set of values taken by H(β, f) as (β, f) ranges over all taut loops in X.

Lemma 2 : If f : β ⟶ X is a loop, then H(β, f) ∈ H(X).

Proof : Let L = H(β, f). Suppose, for contradiction, that L ∉ H(X). Let f : σ ⟶ X be a spanning disc for (β, f) with M(σ) = L. Suppose γ ∈ C(σ) with L(γ) = L. Now (γ, f_{γ}) is a loop in X, where f_{γ} denotes the restriction of f to γ. Since L ∉ H(X), this loop is not taut, so we can find a spanning disc, f_{γ} : σ_{γ} ⟶ X for (γ, f_{γ}) with M(σ_{γ}) < L. Note that ∂σ_{γ} is identified with γ, and so the net σ_{γ} gives rise to a subdivision of the 2-cell bounded by γ in the cellulation of the disc given by σ.

We perform this construction for each such loop γ, and, in this way, obtain a net, σ′, with σ a subgraph of σ′ and with ∂σ = ∂σ′. Note that M(σ′) < L. Moreover, the maps f_{γ} allow us to extend f to a spanning disc f : σ′ ⟶ X for (β, f). This gives the contradiction that L = H(β, f) ≤ M(σ′) < L. We conclude that L ∈ H(X). ♢

Definition : Given k ∈ N, we say that two subsets, H, H′ ⊆ N are k-related if given any L ∈ H with L > k^{2} + 2k + 1 there is some L′ ∈ H′ with L/k ≤ L′ ≤ kL, and conversely, swapping H and H′.

The artificial constant k^{2} + 2k + 1 arises from the following lemma:

Lemma 3 : Suppose that the connected graphs X and Y are k-quasiisometric, then the sets H(X) and H(Y) are k-related.

Proof : Let ϕ : X ⟶ Y and ψ : Y ⟶ X be the maps given by the hypothesis. Suppose that L ∈ H(X) with L > k^{2} + 2k + 1. Let f : β ⟶ X be a taut loop with L(β) = L. Now, ϕ ∘ f : V (β) ⟶ V (Y) is a k-lipschitz map. We can subdivide β to give a loop β′, with V (β) ⊆ V (β′) and L(β′) ≤ kL, so that ϕ ∘ f|V (β) extends to a loop g : β′ ⟶ Y. Let L′ = H(β′, g). By Lemma 2, we have L′ ∈ H(Y). Note that L′ ≤ L(β′) ≤ kL. We extend g to a spanning disc g : σ ⟶ Y with ∂σ = β, and with M(σ) = L′. Now ψ ∘g : V (σ) ⟶ X is a k-lipschitz map. We subdivide σ (as a graph) to obtain a (homeomorphic) net, σ′, and extend ψ ∘ g|V (σ) to a 1-lipschitz map, h : σ′ ⟶ X. Note that M(σ′) ≤ kL′. Also, ∂σ′ is a subdivision of β in which each edge has been subdivided into at most k^{2} edges. Note that V (β) ⊆ V (∂σ′), and from the construction, h(x) = ψ ∘ ϕ ∘ f(x) for x ∈ V (β). Thus d_{X}(f(x), h(x)) ≤ k.

Now construct an annulus by gluing together a set of L squares cyclically along their “vertical” edges. We identify the “top” boundary circle with β, and identify the the “bottom” boundary circle, after subdivision, with ∂σ′. After subdividing each of the L vertical edges into at most k edges, we can find a 1-lipschitz map, i, of the 1-skeleton of this annulus into X, such that i|β = f and i|∂σ′ = h|∂σ′. (Note that the length of the boundary of each 2-cell in this annulus is at most k^{2} + 2k + 1.) We now formally glue this 1-skeleton to the net σ′ along the common circle, ∂σ′, to obtain a net σ′′ with ∂σ′′ = β. The maps h and i combine to give us a 1-lipschitz map j : σ′′ ⟶ X with j|∂σ′′ = f. Thus, (σ′′, j) is a spanning disc for (β, f). Moreover, M(σ′′) ≤ max{M(σ′), k^{2} + 2k + 1} ≤ max{kL′, k^{2} +2k +1}. Since β is taut, we have M(σ′′) ≥ L(β) = L. Since, by assumption, L > k^{2} + 2k + 1, it follows that L ≤ kL′. We see that L/k ≤ L′ ≤ kL as required.

The converse follows by symmetry. ♢

To relate this to the groups we have constructed, we need the following observation. Given S ⊆ N and q ∈ N, let qS = {qn | n ∈ S}. Recall that if F, F′ ⊆ N, we write F ∼ F′ to mean that the symmetric difference is finite.

Lemma 4 : Suppose that F, F′ ⊆ N, and that qS(F) and qS(F′) are k-related for some k ∈ N. Then, F ∼ F′.

Proof : If F ≁ F′ then, without loss of generality, we can find some n ∈ F \ F′ with q2^{2^{n−1}} > k^{2} + 2k + 1 > k. Now q2^{2^{n}} ∈ F, so there is some m ∈ F′ with q2^{2^{n}}/k ≤ q2^{2^{m}} ≤ kq2^{2^{n}}. Thus 2^{2^{n−1}} < 2^{2^{n}}/k ≤ 2^{2^{m}} ≤ k2^{2^{n}} < 2^{2^{n+1}}, and so m = n, giving the contradiction that n ∈ F′. ♢

To relate this to small cancellation groups, we need the following observation. Suppose that A is a finite alphabet, and (w_{i})_{i∈I} is a collection of cyclically reduced words of letters in A and their formal inverses, indexed by a set I, and satisfying the C′(1/6) cancellation condition pairwise (i.e. if i ≠ j, then the largest common subword of w_{i} and w_{j} (or w_{j}^{−1}) has length less than (1/6) min{L(w_{i}), L(w_{j})}). We have:

Lemma 5 : Let X be the Cayley graph of the presentation ⟨A | (w_{i})_{i∈I}⟩. Then, H(X) = {L(w_{i}) | i ∈ I}.

Proof : This follows more or less from the existence of a Dehn algorithm for C′(1/6) groups. Suppose, first, that w is a cyclically reduced word representing the identity, which we can think of as a loop in X. If w is not equal to a relator or its inverse, then we can find some relator w_{i} (or w_{i}^{−1}) with L(w_{i}) < L(w), and which has a common subword of length more than (1/2)L(w_{i}) with w. This allows us to shorten w, and continuing inductively, we can reduce w to the identity using only relators of length less than L(w). In particular, this gives us a spanning disc, σ, for w, with M(σ) < L(w). Thus, w is not taut.

Conversely, suppose w is not taut. There is a spanning disc, σ, for w, with M(σ) < L(w). Applying the construction of the last paragraph to each 2-cell of σ, we obtain another spanning disc for w, this time with each 2-cell corresponding to a conjugate of a relator (of length less than L(w)). At least one of these 2-cells, corresponding to a conjugate of w_{i}, say, has a common subword of length more than (1/2)L(w_{i}) with L(w). This shows that w cannot itself be a relator.

We have shown that the taut loops in X are precisely conjugates of relators and their inverses. This gives the result. ♢

Finally, we return to the examples given at the beginning. Note that if X is the Cayley graph of Γ(S(F)), then, by Lemma 5, we have H(X) = 14S(F). By Lemma 3, we see that if Γ(S(F)) is k-quasiisometric to Γ(S(F′)) then 14S(F) is k-related to 14S(F′). By Lemma 4, it follows that F ∼ F′. This proves Proposition 1.

Acknowledgement.

This paper was written at the University of Melbourne. I would particularly like to thank Walter Neumann and Craig Hodgson for the invitation to take part in the Special Year in geometric group theory. The paper was revised in the light of informative comments by the referee.

References.

[Gri] R.I.Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means : (Russian) Izv. Acad. Nauk SSSR, Ser. Mat. 48 (1984) No. 5, 939–985; (English translation) Math. U.S.S.R. Izv. 25 (1985) No. 2, 259–300.

[Gro] M.Gromov, Asymptotic invariants of infinite groups : “Geometric group theory, Volume 2” (ed. G.A.Niblo, M.Roller) London Math. Soc. Lecture Notes Series No. 182, Cambridge University Press (1993).

[LS] R.C.Lyndon, P.E.Schupp, Combinatorial group theory : Springer Verlag (1977).

[N] B.H.Neumann, Some remarks on infinite groups : J. London Math. Soc. 12 (1937) 120–127.