A CHARACTERISATION OF VIRTUALLY FREE GROUPS

ROBERT H. GILMAN, SUSAN HERMILLER, DEREK F. HOLT, AND SARAH REES

Abstract. We prove that a finitely generated group G is virtually free if and only if there exists a generating set for G and k > 0 such that all k-locally geodesic words with respect to that generating set are geodesic.

Keywords: Virtually free group; Dehn algorithm; word problem.

Mathematics Subject Classification: 20E06; Secondary 20F67.

1. Introduction

A group is called virtually free if it has a free subgroup of finite index.

In this article we characterise finitely generated virtually free groups by the property that a Dehn algorithm reduces any word to geodesic form. Equivalently, a group is virtually free precisely when the set of k-locally geodesic words and the set of geodesic words coincide for suitable k and appropriate generating set.

Let G be a group with finite generating set X. We shall assume throughout this article that all generating sets of groups are closed under the taking of inverses. For a word w = x_{1} ⋯ x_{n} over X, we define l(w) to be the length n of w as a string, and l_{G}(w) to be the length of the shortest word representing the same element as w in G. Then w is called a geodesic if l(w) = l_{G}(w), and a k-local geodesic if every subword of w of length at most k is geodesic.

Let R be a finite set of length-reducing rewrite rules for G; that is, a set of substitutions

u_{1} → v_{1}, u_{2} → v_{2}, …, u_{r} → v_{r},

where u_{i} =_{G} v_{i} and l(v_{i}) < l(u_{i}) for 1 ≤ i ≤ r. Then R is called a Dehn algorithm for G over X if repeated application of these rules reduces any representative of the identity to the empty word. It is well-known that a group has a Dehn algorithm if and only if it is word-hyperbolic [1].

More generally (that is, even outside of the group theoretical context), if L is any set of strings over an alphabet X (or, in other words, L is any language over X), we shall call L k-locally excluding if there exists a finite set F of strings of length at most k such that a string w over X is in L if and only if w contains no substring in F. It is clear that the set of k-local geodesics in a group is k-locally excluding, since we can choose F to be the set of all non-geodesic words of length at most k. We observe in passing that if a set of strings is k-locally excluding then, by definition, it is a k-locally testable and hence locally testable language (see [6]).

We shall say that the group G is k-locally excluding over a finite generating set X when the set of geodesics of G over X is k-locally excluding.

The purpose of this paper is to prove the following theorem.

Theorem 1. Let G be a finitely generated group. Then the following are equivalent.

(i) G is virtually free.

(ii) There exists a finite generating set X for G and a finite set of lengthreducing rewrite rules over X whose application reduces any word over X to a geodesic word; that is G has a Dehn algorithm that reduces all words to geodesics.

(iii) There exists a finite generating set X for G and an integer k such that every k-locally geodesic word over X is a geodesic; that is, G is k-locally excluding over X.

2. Proof of Theorem 1

The equivalence of (ii) and (iii) is straightforward. Assume (ii), and let R be a set of length-reducing rewrite rules with the specified property. Let k be the maximal length of a left hand side of a rule in R. Then a k-local geodesic over X cannot have the left hand side of any rule in R as a subword, and so it must be geodesic. Conversely, assume (iii) and let R be the set of all rules u → v in which l(v) < l(u) ≤ k and u =_{G} v. Then repeated application of rules in R reduces any word to a k-local geodesic which, by (iii), is a geodesic.

The main part of the proof consists in showing that (i) and (iii) are equivalent. We start with a useful lemma.

Lemma 1. Let G be a group with finite generating set X, let k > 0 be an integer, and suppose that G is k-locally excluding over X. Let w be a geodesic word over X, and let x ∈ X. Then

(i) l_{G}(wx) is equal to one of l(w) + 1, l(w), l(w) − 1. (ii) wx is geodesic (that is, l_{G}(wx) = l(w) + 1) if and only if vx is geodesic, where v is the suffix of w of length k − 1 (or the whole of w if l(w) < k − 1). (iii) l_{G}(wx) − l(w) = l_{G}(v′x) − l(v′), where v′ is the suffix of w of length 2k − 2 (or the whole of w if l(w) < 2k − 2).

Proof. The three possibilities for l_{G}(wx) follow from the fact that w is geodesic and x is a single generator. (ii) is an immediate consequence of G being k-locally excluding. (iii) follows from (ii) when wx is geodesic, so suppose not. Write w = uv with v as defined in (ii), and let z be a geodesic representative of vx. Since v is geodesic, l(z) is either l(v) or l(v) − 1. In the second case uz is geodesic, so l_{G}(wx) − l(w) = l_{G}(vx) − l(v) = l_{G}(v′x) − l(v′) = −1 and (iii) follows. In the first case (l(z) = l(v)) write w = u′v′′v with v′ = v′′v, so l(v′′) = k − 1 provided that u′ is non-empty. Now wx = u′v′′vx =_{G} u′v′′z where l(u′v′′z) = l(w), and either l_{G}(wx) = l(u′v′′z) = l(w) or l_{G}(wx) = l(u′v′′z) − 1 = l(w) − 1. So at most one length reduction occurs in the word u′v′′z, and since u′v′′ is geodesic, that length reduction must occur, if at all, within the subword v′′z =_{G} v′x. Part (iii) follows from this. □

We are now ready to prove that (iii) implies (i) in Theorem 1.

Proposition 1. Suppose that G is a group with finite generating set X and that the geodesics over X are k-locally excluding for some k > 0. Then G is virtually free.

Proof. We prove this result by demonstrating that the word problem for G can be solved on a pushdown automaton, and then using Muller and Schupp’s classification of groups with this property [5].

The automaton to solve the word problem operates as follows. Given an input word w, the automaton reads w from left to right. At any point, the word on the stack is a geodesic representative of the word read so far. Suppose at some point it has u on the stack and then reads a symbol x. It pops 2k−2 symbols off the stack (or the whole of u if l(u) < 2k−2), appends x to the end of the word so obtained, replaces it by a geodesic representative if necessary, and appends that reduced word to the stack. It follows from Lemma 1 that the word now on the stack is a geodesic representative of ux, and hence of the word read so far.

So w represents the identity in G if and only if the stack is empty once all the input has been read and processed, and it follows immediately from [5] that G is virtually free. □

It remains to prove that (i) implies (iii), namely that the set of geodesics of a virtually free group with an appropriate generating set is k-locally excluding for some k > 0.

It is proved in [7, Theorem 7.3] that a finitely generated group G is virtually free if and only if it arises as follows: G is the fundamental group of a graph of groups Γ with finite vertex groups G_{1}, … G_{n}, and finite edge groups G_{i,j} for certain pairs {i, j}.

There are various alternative and equivalent definitions of the fundamental group of a graph of groups, but the one that is most convenient for us is [2, Chapter 1, Definition 3.4]. As is pointed out in [2, Chapter 1, Example 3.5 (vi)], such a group G can be built up as a sequence of groups 1 = H_{1}, H_{2}, …, H_{r} = G, where each H_{i+1} is defined either as a free product with amalgamation (over an edge group) of H_{i} with one of the vertex groups G_{i}, or as an HNN extension of H_{i} with associated subgroups isomorphic to one of the edge groups G_{i,j}. The amalgamated free products are done first, building up along a maximal tree, and then the HNN extensions are done for the remaining edges in the graph.

So from now on we shall assume that our virtually free group G can be constructed in this way, where the groups G_{i} and G_{i,j} are all finite. Hence the result follows from repeated application of the following two lemmas, of which the proofs are very similar.

Notice that the generating set X over which G is k-locally excluding will contain all non-identity elements of each of the vertex groups, G_{i} and also certain other elements arising from the HNN extensions, which are specified in Lemma 3.

Lemma 2. Let H be a group which is k-locally excluding over a generating set X for some k ≥ 2, let K be a finite group, let A = H ∩ K, and suppose that A \ {1} ⊂ X.

Then G = H ∗_{A} K is k′-locally excluding over X′ := X ∪ (K \ A), where k′ = 3k − 2.

Lemma 3. Let H be a group which is k-locally excluding over a generating set X for some k ≥ 2, let A and B be isomorphic finite subgroups of H which satisfy A \ {1} ⊂ X and B \ {1} ⊂ X, and let G = ⟨H, t⟩ be the HNN extension in which tat^{−1} = ϕ(a) for all a ∈ A, where ϕ : A → B is an isomorphism.

Then G is k′-locally excluding over X′ := X ∪ {ta | a ∈ A}∪ {t^{−1}b | b ∈ B}, where k′ = 3k − 2. (Note that the elements of X′ in the set {t^{−1}b | b ∈ B} are the inverses of those in the set {ta | a ∈ A}.)

Proof of Lemma 2. Let w be a k′-local geodesic of G over X′. We want to prove that w is geodesic. Suppose not, and let w′ be a geodesic word that represents the same element of G. Note that, since A \ {1} ⊆ X′, we cannot have w ∈ A, because that would imply that l(w) ≤ 1.

We can write w = w_{0}k_{1}w_{1}k_{2} ⋯ k_{r}w_{r}, where each k_{i} ∈ K \ A and each w_{i} ∈ X^{∗}. Either w_{0} or w_{r} could be the empty word but, since K \ {1} ⊆ X′ and w is a k′-local geodesic with k′ > k ≥ 2, w_{i} must be non-empty for 0 < i < r. The 2-locally excluding condition also implies that no non-empty w_{i} is a word in A^{∗}. In fact, since H is by assumption k-locally excluding over X and k′ > k, the words w_{i} are geodesics as elements of H over X, and so the non-empty w_{i} represent elements of H \ A.

Similarly, write w′ = w′_{0}k′_{1}w′_{1}k′_{2} ⋯ k′_{r′}w′_{r′}.

Now the normal form theorem for free products with amalgamation (see [4, Thm 4.4] or the remark following [3, Chapter 4, Theorem 2.6]) states that, if C is a union of sets of distinct right coset representatives of A in H and in K, then any element of the amalgamated product can be written uniquely as a product of the form ac_{1} ⋯ c_{s}, where a ∈ A, each c_{i} ∈ C, and alternate c_{i}’s are in H \ A and K \ A.

Since each k_{i} ∈ K \ A and each non-empty w_{i} ∈ H \ A, the syllable length s of the group element represented by w is equal to the number of non-trivial words w_{0}, k_{1}, w_{1}, …, k_{r}, w_{r}, where c_{1} ∈ H \A if and only if w_{0} is non-trivial, and c_{s} ∈ H \ A if and only if w_{r} is non-trivial. The same applies to w′, and hence r = r′, w_{0} and w′_{0} are either both empty or both non-empty, and similarly for w_{r} and w′_{r}.

Furthermore, w_{r} and w′_{r} are in the same right coset of A in H, and so w′_{r} =_{H} a_{r}w_{r} for some a_{r} ∈ A. Then k_{r} and k′_{r}a_{r} are in the same right coset of A in K, and so k_{r} =_{K} b_{r−1}k′_{r}a_{r} for some b_{r−1} ∈ A. Carrying on in this manner, we can show that there exist a_{i}, b_{i} ∈ A (0 ≤ i ≤ r) such that w′_{i} =_{H} a_{i}w_{i}b_{i} and k′_{i} =_{K} b_{i−1}^{−1}k_{i}a_{i}^{−1}, where a_{0} = b_{r} = 1.

Since r = r′ and l(w′) < l(w), we must have l(w′_{i}) < l(w_{i}) for some i. So one of the words a_{i}w_{i}, w_{i}b_{i}, a_{i}w_{i}b_{i} must reduce (in H over X) to a word strictly shorter than w_{i}.

Suppose first that w_{i}b_{i} reduces to a word strictly shorter than w_{i}. Since b_{r} = 1, we have i < r and so k_{i+1} exists. Then, by Lemma 1, l_{H}(v′_{i}b_{i}) = l(v′_{i}) − 1, where v′_{i} is the suffix of w_{i} of length 2k − 2, or the whole of w_{i} if l(w_{i}) < 2k − 2. Now, since v′_{i}k_{i+1} =_{G} (v′_{i}b_{i})(b_{i}^{−1}k_{i+1}) with b_{i}^{−1}k_{i+1} ∈ K, we see that the suffix v′_{i}k_{i+1} of w_{i}k_{i+1}, which has length at most 2k − 1, is a non-geodesic word in G and, since 2k − 1 < k′, this contradicts the assumption that w is a k′-local geodesic.

The case in which a_{i}w_{i} reduces to a word of length less than w_{i} is similar (here we use a ‘mirror image’ of Lemma 1), and we find that i > 0 and a prefix of k_{i}w_{i} of length at most 2k − 1 is non-geodesic, again contradicting the assumption that w is a k′-local geodesic.

It remains to consider the case where the reduction (in H over X) of a_{i}w_{i}b_{i} is strictly shorter than w_{i}, but each of the reductions of a_{i}w_{i} and w_{i}b_{i} have the same length as w_{i}. Since neither a_{i} nor b_{i} can be trivial, we have 0 < i < r, and so k_{i} and k_{i+1} both exist. We claim that w_{i} has length at most 3k − 4. For if not, we write w_{i} = u′uv′, where l(u′) = l(v′) = k − 1 and l(u) ≥ k − 1, and deduce from Lemma 1 and its mirror image that a_{i}w_{i}b_{i} =_{H} yuz, where y, z ∈ X^{∗} and l(y) = l(z) = k − 1. Then since yuz reduces in H over X and H is k-locally excluding over X, some subword of length k must reduce. Such a subword must be a subword of either yu or uz, and so one of a_{i}w_{i} or w_{i}b_{i} does indeed reduce to a word shorter than w_{i}, contradicting our assumption. Hence l(w_{i}) ≤ 3k − 4 as claimed.

Now k_{i}w_{i}k_{i+1} has length 2+l(w_{i}) ≤ 3k−2, but k_{i}w_{i}k_{i+1} =_{G} (k_{i}a_{i}^{−1})w′_{i}(b_{i}^{−1}k_{i+1}) with k_{i}a_{i}^{−1}, b_{i}^{−1}k_{i+1} ∈ K, so k_{i}w_{i}k_{i+1} is not a geodesic in G over X′, and once again we contradict our assumption that w is a k′-local geodesic. This completes the proof of Lemma 2. □

Proof of Lemma 3. Let w be a k′-local geodesic of G over X′. We want to prove that w is geodesic. Suppose not, and let w′ be a geodesic word that represents the same element of G.

Write w = w_{0}t_{1}^{ϵ_{1}}w_{1}t_{2}^{ϵ_{2}}w_{2} ⋯ t_{r}^{ϵ_{r}}w_{r}, where each t_{i} is one of the generators of the form ta (a ∈ A), each ϵ_{i} is 1 or −1, and each w_{i} is a word over X. Since k′ > k, w is a k-local geodesic, so each word w_{i} is geodesic as an element of H. So if w_{i} represents a non-trivial element of A or of B, then w_{i} has length 1. Hence, if ϵ_{i} = 1 then we cannot have w_{i} ∈ A \ {1}, and if ϵ_{i} = −1 then we cannot have w_{i} ∈ B \ {1}, because in those cases t^{ϵ_{i}}w_{i} would be a non-geodesic subword of w of length 2. Also, if w_{i} is empty with 0 < i < r, then ϵ_{i} = ϵ_{i+1}.

Similarly, write w′ = w′_{0}(t′_{1})^{ϵ′_{1}}w′_{1}(t′_{2})^{ϵ′_{2}}w′_{2} ⋯ (t′_{r′})^{ϵ′_{r′}} w′_{r′}.

Now the normal form theorem for HNN extensions [3, Chapter 4, Theorem 2.1] states that if C is a union of sets H_{A} and H_{B} of distinct right coset representatives of A and of B in H, then any element of the HNN extension G can be written uniquely as a product of the form ht^{ε_{1}}c_{1} ⋯ t^{ε_{s}}c_{s}, where h ∈ H, each ε_{i} is 1 or −1, each c_{i} ∈ C, and c_{i} ∈ H_{A} or c_{i} ∈ H_{B} when ε_{i} = 1 or −1, respectively. Also, if c_{i} = 1 with 1 ≤ i < s, then ε_{i} = ε_{i+1}.

For the normal form of the element of G represented by both w and w′, it follows that r = r′ = s and ϵ_{i} = ϵ′_{i} = ε_{i} for each i. Furthermore, an inductive argument similar to the one in the proof of Lemma 2 shows that there are elements a_{i}, b_{i} ∈ A ∪ B (0 ≤ i ≤ r) such that w′_{i} =_{H} a_{i}w_{i}b_{i} and (t′_{i})^{ϵ_{i}} = b_{i−1}^{−1}(t_{i})^{ϵ_{i}}a_{i}^{−1}, where a_{0} = b_{r} = 1. We have a_{i} ∈ A or B when ϵ_{i} = 1 or −1, respectively, and b_{i} ∈ B or A when ϵ_{i+1} = 1 or −1, respectively.

Since r = r′ and l(w′) < l(w), we must have l(w′_{i}) < l(w_{i}) for some i. So one of the words a_{i}w_{i}, w_{i}b_{i}, a_{i}w_{i}b_{i} must reduce (in H over X) to a word strictly shorter than w_{i}.

Suppose first that w_{i}b_{i} reduces to a word strictly shorter than w_{i}. Since b_{r} = 1, we have i < r and so t_{i+1} exists. Then, by Lemma 1, l_{H}(v′_{i}b_{i}) = l(v′_{i}) − 1, where v′_{i} is the suffix of w_{i} of length 2k − 2, or the whole of w_{i} if l(w_{i}) < 2k − 2. Now, since v′_{i}t_{i+1}^{ϵ_{i+1}} =_{G} (v′_{i}b_{i})(b_{i}^{−1}t_{i+1}^{ϵ_{i+1}}) with b_{i}^{−1}t_{i+1}^{ϵ_{i+1}} ∈ X′, we see that the suffix v′_{i}t_{i+1}^{ϵ_{i+1}} of w_{i}t_{i+1}^{ϵ_{i+1}}, which has length at most 2k − 1, is a non-geodesic word in G and, since 2k − 1 < k′, this contradicts the assumption that w is a k′-local geodesic.

The case in which a_{i}w_{i} reduces to a word of length less than w_{i} is similar (using the mirror image of Lemma 1), and we find that i > 0 and a prefix of t_{i}^{ϵ_{i}}w_{i} of length at most 2k − 1 is non-geodesic, again contradicting the assumption that w is a k′-local geodesic.

It remains to consider the case where the reduction (in H over X) of a_{i}w_{i}b_{i} is strictly shorter than w_{i}, but each of the reductions of a_{i}w_{i} and w_{i}b_{i} have the same length as w_{i}. Since neither a_{i} nor b_{i} can be trivial, we have 0 < i < r, and so t_{i} and t_{i+1} both exist. We claim that w_{i} has length at most 3k − 4. For if not, we write w_{i} = u′uv′, where l(u′) = l(v′) = k − 1 and l(u) ≥ k − 1, and deduce from Lemma 1 and its mirror image that a_{i}w_{i}b_{i} =_{G} yuz, where y, z ∈ X^{∗} and l(y) = l(z) = k − 1. Then since yuz reduces in H over X and H is k-locally excluding over X, some subword of length k must reduce.

Such a subword must be a subword of either yu or uz, and so one of a_{i}w_{i} or w_{i}b_{i} does indeed reduce to a word shorter than w_{i}, contradicting our assumption. Hence l(w_{i}) ≤ 3k − 4 as claimed.

Now t_{i}^{ϵ_{i}}w_{i}t_{i+1}^{ϵ_{i+1}} has length 2+l(w_{i}) ≤ 3k−2, but t_{i}^{ϵ_{i}}w_{i}t_{i+1}^{ϵ_{i+1}} =_{G} (t_{i}^{ϵ_{i}}a_{i}^{−1})w′_{i}(b_{i}^{−1}t_{i+1}^{ϵ_{i+1}}) with l_{G}(t_{i}^{ϵ_{i}}a_{i}^{−1}) = l_{G}(b_{i}^{−1}t_{i+1}^{ϵ_{i+1}}) = 1, so t_{i}^{ϵ_{i}}w_{i}t_{i+1}^{ϵ_{i+1}} is not a geodesic in G over X′, and once again we contradict our assumption that w is a k′-local geodesic. This completes the proof of Lemma 3. □

References

[1] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short, Notes on word-hyperbolic groups, Proc. Conf. Group Theory from a Geometrical Viewpoint, eds. E. Ghys, A. Haefliger and A. Verjovsky, held in I.C.T.P., Trieste, March 1990, World Scientific, Singapore, 1991.

[2] W. Dicks and M.J. Dunwoody, Groups Acting on Graphs Cambridge studies in advanced mathematics 17, Cambridge University Press, 1989.

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

[4] W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory, Dover Publications Inc., New York, 1976.

[5] David Muller and Paul E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26, 1983, 295–310.

[6] J.E. Pin, Varieties of Formal Languages, Plenum Publishing Corp., New York, 1986.

[7] Peter Scott and Terry Wall, Topological methods in group theory. in Homological group theory (Proc. Sympos., Durham, 1977), ed. C.T.C. Wall, London Math. Soc. Lecture Note Ser., 36, Cambridge Univ. Press, Cambridge-New York, 1979, 137–203.

Department of Mathematics, Stevens Institute of Technology, Hoboken NJ 07030, USA

E-mail address: rgilman@stevens-tech.edu

Department of Mathematics, University of Nebraska, Lincoln NE 68588-0130, USA

E-mail address: smh@math.unl.edu

Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK

E-mail address: dfh@maths.warwick.ac.uk

School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK

E-mail address: Sarah.Rees@ncl.ac.uk