Groups with Context-Free Conjugacy Problems

Derek F. Holt, Sarah Rees, Claas E. Röver

September 30th 2009, Newcastle

Abstract

The conjugacy problem and the inverse conjugacy problem of a finitely generated group are defined, from a language theoretic point of view, as sets of pairs of words. An automaton might be obliged to read the two input words synchronously, or could have the option to read asynchronously. Hence each class of languages gives rise to four classes of groups; groups whose (inverse) conjugacy problem is an (a)synchronous language in the given class. For regular languages all these classes are identical with the class of finite groups. We show that finitely generated groups with asynchronously context-free inverse conjugacy problem are precisely the virtually free groups. Moreover, the other three classes arising from context-free languages are shown all to coincide with the class of virtually cyclic groups, which is precisely the class of groups with synchronously one-counter (inverse) conjugacy problem. It is also proved that for a δ-hyperbolic group the intersection of the inverse conjugacy problem with the set of pairs of quasi-geodesics is context-free.

1 Introduction

The relationship between the complexity of the word problem of a group as a formal language and the algebraic characteristics of the group has been well studied; it is well known that the word problem of a group is regular precisely when the group is finite [3] and context-free precisely when the group is virtually-free [9]; and in fact when the word problem is context-free it is even deterministic context-free. The purpose of this article is to investigate the relationship between the complexity of the conjugacy problem of a group as a formal language and the algebraic characteristics of the group.

Throughout this paper we assume that all group generating sets are finite and symmetric; that is, they are closed under taking inverses. For a group G generated by a set X, we define the conjugacy problem of G to be the set of ordered pairs of words (u, v) such that u and v are conjugate in G.

We will consider machines that read pairs of words synchronously as strings over an alphabet X ×X as well as machines that read inputs asynchronously from two strings. For synchronous reading, in any reading move of the machine (as opposed to a non-reading or ε-move), a single symbol from each of the two input words is read, where the shorter of the two words is padded at the end with a padding symbol that maps onto the identity element of the group. For asynchronous reading, in each move of the machine, zero or one symbols from each of the two input words may be read, so there are four types of moves altogether. Observe that synchronous reading is a special case of asynchronous reading.

Using additional states as necessary, we can clearly assume that a 2-variable asynchronous machine M never reads from both input strings in a single move. . This allows us to define a corresponding one variable machine M_{1} with alphabet the union X^{L} ∪ X^{R} of two disjoint copies of X. Define ρ_{L} : X^{L}∪X^{R} → X^{∗} by ρ_{L}(x^{L}) = x where x^{L} is the element of X^{L} corresponding to x ∈ X and ρ_{L}(x^{R}) = ε for all x^{R} ∈ X^{R}, and extend ρ_{L} to (X^{L} ∪ X^{R})^{∗}. Define ρ_{R} similarly. Then, the automaton M_{1} that simulates M should accept w precisely when M accepts (ρ_{L}(w), ρ_{R}(w)) by reading the inputs in the order encoded in w. Such an M_{1} can obviously be constructed.

We will call a language of pairs of strings synchronously or asynchronously regular if it is accepted by a finite state automaton reading the two input words synchronously or asynchronously. We define synchronously and asynchronously context-free similarly, with finite state automaton replaced by pushdown automaton. If the pushdown automaton has only one work symbol besides the bottom of stack marker, then it and the accepted language are called synchronously or asynchronously one-counter.

Note that the word problem for G is the restriction of the conjugacy problem to pairs (u, ε), where ε is the empty string, and hence the conjugacy problem is never easier than the word problem.

It is straightforward to prove that the conjugacy problem for G is regular if and only if G is finite, and we include a proof in Section 2. Our first main result classifies groups whose conjugacy problem is context-free.

Theorem A Let G be a finitely generated group. The following are equivalent.

(i) The conjugacy problem of G is synchronously one-counter.

(ii) The conjugacy problem of G is asynchronously context-free.

(iii) G is virtually cyclic.

Theorem A is proved in Section 3, where it is broken down into Theorems 5, 8 and 10.

By reversing the order of one of the input words we can deal with a wider class of groups, but only with asynchronous automata. We call the set of all pairs of words (u, v) for which u and v^{−1} are conjugate in G, the inverse conjugacy problem for G. Our second main result classifies groups whose inverse conjugacy problem is context-free.

Theorem B Let G be a finitely generated group. Then the inverse conjugacy problem of G is

(i) synchronously context-free if and only if G is virtually cyclic;

(ii) asynchronously context-free if and only if G is virtually free.

Theorem B is broken down into Theorems 5, 8, 18 and 19, and is the subject of Section 4. Theorem 19 is of independent interest, showing that, for any λ ≥ 1 and ϵ ≥ 0 the restriction of the inverse conjugacy problem of a word hyperbolic group to pairs of (λ, ϵ)-quasi-geodesics is asynchronously context-free.

In Section 5 we sketch the following result which implies that with respect to conjugacy problems indexed languages are more powerful than context-free languages.

Theorem C The conjugacy problem of a finitely generated virtually free group is asynchronously indexed.

This should be compared to the still open problems of whether indexed languages lead to larger classes of groups than context-free languages in the realms of word and coword problems; see [6].

2 Preliminaries

Let us begin by showing that the choice of generating set makes no difference and hence that we are dealing with group theoretic properties. In a way this justifies our terminology introduced and used before.

Theorem 1 If the conjugacy problem or inverse conjugacy problem for a group is synchronously or asynchronously context-free with respect to one generating set then the same is true with respect to any other generating set.

Proof: Suppose first that the conjugacy or inverse conjugacy problem for the group G is asynchronously context-free with respect to X. Given another generating set Y, for each y ∈ Y, we choose a word w_{y} in X^{∗} that represents the element y, and hence define a homomorphism from Y^{∗} to X^{∗}. Given any pair of input words (u, v) over Y, the automaton to solve the (inverse) conjugacy problem first rewrites over X using that homomorphism and then operates as the machine solving the (inverse) conjugacy problem over X.

This part of the argument works for any class of languages closed under inverse homomorphisms.

Now suppose that the (inverse) conjugacy problem for G is synchronously context-free with respect to X. Given another generating set Y, define the words w_{y} just as above. If the words w_{y} all had the same length, we could proceed as above. Otherwise by padding as necessary, as we rewrite, with words of the form xx^{−1} we can ensure that the rewrites of the prefixes of u, v which we have read so far differ in length by at most 1 at any stage. Hence using some additional memory to deal with that small shift we can adapt our solution to the problem over X to give a solution over Y.

This part of the argument has made some small assumptions about the power of the machine, and hence it is not immediately clear that it works for any class of language closed under inverse homomorphism. □

We include the following elementary result for completeness.

Theorem 2 A group has asynchronously regular conjugacy problem if and only if it is finite, in which case the problem is synchronously regular.

Proof: If the conjugacy problem is (synchronously or asynchronously) regular, then so is the word problem as the intersection of the conjugacy problem with the regular set X^{∗} ×{ε}, and hence a group with regular conjugacy problem must be finite.

Conversely suppose that G is finite, in which case we may store the conjugacy classes of its elements. Using a finite state automaton based on the Cayley graph for G×G, we can identify the elements of G represented by two input words u, v and hence decide their conjugacy. □

Of course the same result holds for the inverse conjugacy problem.

3 Conjugacy Problems

In this section we begin by solving the conjugacy and inverse conjugacy problem for virtually cyclic groups on a one-counter automaton Then we show that these are the only groups with synchronously context-free conjugacy or inverse conjugacy problem. This is an application of the classical pumping lemma for context-free languages.

Lemma 3 (Pumping Lemma [5, Lemma 6.1]) Add exact lemma reference Let L be a context-free language. Then there exists a constant N > 0 such that if w ∈ L with |w| > N, then w = υϕχψω where |ϕχψ| ≤ N, |ϕψ| ≥ 1, and υϕ^{n}χψ^{n}ω ∈ L for all n ≥ 0.

Finally we prove that groups with asynchronous context-free conjugacy problem must also be virtually cyclic, making use of Ogden’s generalisation of the pumping lemma.

Lemma 4 (Ogden’s Lemma [5, Lemma 6.2]) Let L be a context-free language. Then there exists a constant N > 0 such that if w ∈ L, with at least N letters in w marked, then w = υϕχψω where at most N letters in ϕχψ are marked, and at least one in ϕψ, and υϕ^{n}χψ^{n}ω ∈ L for all n ≥ 0.

3.1 Virtually Infinite Cyclic Groups

Theorem 5 Every virtually cyclic group has synchronously one-counter conjugacy problem, and synchronously one-counter inverse conjugacy problem.

Proof: Since regular languages are also one-counter, we may and will assume that G = ⟨X⟩ is virtually infinite cyclic. Let z be a generator of a normal cyclic subgroup of finite index in G, and let T be a set of coset representatives for ⟨z⟩ in G. Then every element of G is uniquely representable by a word z^{k}t for k ∈ ℤ, t ∈ T, and we refer to this word as its normal form.

Since T and X are finite we may assume that the machine knows the normal forms for all r^{t}, r^{−1} and rx, for r, t ∈ T and x ∈ X.

First we consider the conjugacy problem. The conjugate of z^{i}r by z^{k}t, (z^{k}t)^{−1}z^{i}rz^{k}t, can take one of four forms:

(a) z^{i}r^{t},  when r, t both centralise z
(b) z^{−i}r^{t}, when r centralises but t inverts z
(c) z^{i−2k}r^{t}, when t centralises but r inverts z
(d) z^{2k−i}r^{t}, when r, t both invert z.

We are now ready to describe the operation of our machine.

Suppose words u, v over X are input, and that u and v have normal forms z^{i}r and z^{j}s with r, s ∈ T. Before starting to read, the machine will guess one of the four cases above as well as a specific choice of t, and attempt to verify that v is a conjugate of u of that type. On a one-counter automaton, one can rewrite a single input word into normal form using the states to store the coset representative and the stack to store the exponent of z. But for a pair of words we cannot compute both exponents using a single stack. In fact, we compute both coset representatives r, s using the states. In addition we compute either i − j in case (a), i + j in case (b), or the parity of i − j in cases (c) or (d); we only need to use the stack in the first two cases.

After reading u and v, the machine knows r and s. It checks that r^{t} and s are in the same coset of ⟨z⟩, and also whether each of r, t centralise or invert z, as specified by the selected case (a), (b), (c) or (d). If either of these checks fails then the computation is abandoned.

Otherwise, r^{t} = z^{l}s, for some l ∈ ℤ. It remains to check the value of l against the information we have computed for i and j. To verify that u, v are conjugate by an element of the form z^{k}t, we check in case (a) that i − j = −l, in case (b) that i + j = l and in cases (c) and (d) that the parity of i − j matches that of l.

The machine recognising the inverse conjugacy problem operates very similarly. We assume as above that u, v are on the two tapes, and that u and v have normal forms z^{i}r and z^{j}s. We aim to verify that u is conjugate to v^{−1}. We have v^{−1} = z^{−ϵj}s^{−1}, where ϵ is −1 or 1 depending on whether or not conjugation by s inverts z. Let s^{−1} = z^{m}s′, where s′ ∈ T. Note that if u and v^{−1} are indeed conjugate, then r, s, s′ either all centralise or all invert z. So ϵ is equal to 1 in cases (a) and (b), and −1 in cases (c) and (d).

In all cases r^{t} and s^{−1} must be in the same coset of ⟨z⟩; otherwise we abandon the computation. This time we check in case (a) that i + j = m − l, in case (b) that j −i = m−l and in cases (c) and (d) that the parity of i−j matches that of m − l. □

3.2 Cancellation Lemmas and Transversals

We recall that a reduced word x_{1}x_{2} ⋯ x_{r} is said to be cyclically reduced if x_{1} ≠ x_{r}^{−1}. So the free reduction of any word has the form α^{−1}βα with β cyclically reduced, and we shall call β the cyclic reduction of the original word. By [8, Theorem 1.3] two words over a free generating set of a free group are conjugate in the group if and only if their cyclic reductions are cyclic conjugates of each other.

For the remainder of the article, u ≡ v will mean that u and v are equal as words, and u =_{G} v means that u and v are G-equivalent; that is, they represent the same element of the group G. We denote the length of a word w by |w|.

Lemma 6 Let u and v be cyclically reduced words over a free generating set of a free group, such that u ≠ v^{−1} and neither u nor v is a proper power. Let m = max(|u|, |v|). Then, for k, l ≥ 1, the cancelled suffix of u^{k} and prefix of v^{l} in the free reduction of the product u^{k}v^{l} each have length less than 2m, and hence the freely reduced length of u^{k}v^{l} is greater than k|u| + l|v| − 4m.

Proof: Suppose without loss of generality that m = |v| ≥ |u|. The result is clear if l = 1, so suppose that l > 1 and assume for a contradiction that the prefix v^{2} of v^{l} is cancelled in the product u^{k}v^{l}. Then v ≡ u^{−r}w for some r ≥ 1 with |w| < |u| and, since v ≠ u^{−1} and v is not a proper power, we have |w| > 0. But now, v^{2} ≡ u^{−r}wu^{−r}w, and since its subwords wu^{−r} and v have equal length and each is completely cancelled when multiplied on the left by u^{k+r}, we must have wu^{−r} ≡ v. So v is a nontrivial cyclic conjugate of itself, and hence must be a proper power, which is a contradiction. □

We use the following technical lemma in the proofs of both Theorem 8 and Theorem 10.

Lemma 7 Suppose that G has a non-abelian free normal subgroup F of finite index, and that a, b are part of a free basis Y for F. Then there exists a transversal T for F in G such that for each t ∈ T

(i) the word over Y for a^{t} := t^{−1}at is a cyclically reduced word α,

(ii) the word over Y for b^{t} has the form ρ^{−1}βρ where β is cyclically reduced, and |ρ| is as small as possible.

For all such t there is no cancellation in the products αρ^{−1} or ρα.

Proof: Each coset F t contains representatives for which (i) is satisfied. For if a^{t} is not cyclically reduced, then it has the form σ^{−1}ασ with α cyclically reduced, σ ∈ F, and tσ^{−1} satisfies (i). From amongst all those representatives of F t satisfying (i) we choose one satisfying (ii).

Now if there were cancellation in forming either of the products αρ^{−1} or ρα, then we could replace α by a cyclic conjugate and reduce the length of ρ. □

3.3 Synchronous (Inverse) Conjugacy Problems

Theorem 8 A finitely generated group with synchronously context-free conjugacy problem or inverse conjugacy problem is virtually cyclic.

Proof: First suppose that the group G has synchronously context-free conjugacy problem. Then the word problem for G is context-free, and hence G is virtually free [9]. Suppose that G is not virtually cyclic. Then G has a finite index free normal subgroup F of rank at least 2. Let a, b be part of a free generating set Y for F, and let A = a^{−1}, B = b^{−1}. We choose a generating set X for G that contains Y. So, by Theorem 1, the conjugacy problem of G is synchronously context-free with this generating set.

We choose a transversal T for F in G satisfying the conditions of Lemma 7.

Now, for some suitably large k, let u = a^{k}b^{k}a^{k}B^{k} and v = b^{k}a^{k}B^{k}a^{k}. Then u and v are conjugate in F, and so w = (a, b)^{k}(b, a)^{k}(a, B)^{k}(B, a)^{k} is in the conjugacy problem. According to the pumping lemma (Lemma 3), we can write w in the form υϕχψω where |ϕχψ| ≤ N, |ϕψ| ≥ 1, and for all n ≥ 0, (u_{n}, v_{n}) := υϕ^{n}χψ^{n}ω is in the language, and hence must also represent a conjugate pair in G. In particular this is true of (u_{0}, v_{0}) := υχω. Our aim is to establish a contradiction by showing that u_{0} and v_{0} are not conjugate.

Provided that k > N, the subword ϕχψ must be contained within one of the three subwords (a, b)^{k}(b, a)^{k}, (b, a)^{k}(a, B)^{k} or (a, B)^{k}(B, a)^{k} of w. We shall only deal with the first of these three possibilities; the arguments dealing with the other two cases are similar.

In this first case we have u_{0} ≡ a^{k−r}b^{k−s}a^{k}B^{k}, v_{0} ≡ b^{k−r}a^{k−s}B^{k}a^{k}, where at least one of r, s is greater than 0, and r + s ≤ N < k. It is clear that u_{0} and v_{0} are not cyclically conjugate, and hence are not conjugate within F; we still need to verify that they are not conjugate within the larger group G.

Suppose g ∈ G with g^{−1}u_{0}g = v_{0}. Then g = tx for some t ∈ T and x ∈ F, so the cyclically reduced length of t^{−1}u_{0}t is equal to |v_{0}| = |u_{0}|. By choice of the transversal T, we have t^{−1}at =_{G} α and t^{−1}bt =_{G} ρ^{−1}βρ, as described in Lemma 7. If ρ is nonempty then, since there is no cancellation in the products αρ^{−1} and ρα, t^{−1}u_{0}t =_{G} α^{k−r}ρ^{−1}β^{k−s}ρα^{k}ρ^{−1}β^{−k}ρ is clearly cyclically reduced, with length greater than |u_{0}|. Hence ρ is empty and α =_{G} t^{−1}at and β =_{G} t^{−1}bt are both cyclically reduced words. Furthermore, since α and β form part of a free basis of F, we cannot have α = β^{±1} and neither α nor β is a proper power.

Now by Lemma 6 at most 4 max{|α|, |β|} generators cancel in any product α^{i}β^{j} or β^{j}α^{i}, and hence the length of the cyclic reduction of t^{−1}u_{0}t =_{G} α^{k−r}β^{k−s}α^{k}β^{−k} is at least (2k − r)|α| + (2k − s)|β| − 16 max{|α|, |β|}. Provided that k is sufficiently large, this can only be equal to |v_{0}| = 4k − r − s if |α| = |β| = 1. In that case, t^{−1}u_{0}t is a cyclic conjugate in F of v_{0}, so we must have α, β ∈ {a, b, A, B}. (We can calculate how large k needs to be for this purpose after the choice of the transversal T, which determines all the words α and β that can arise.)

But it is easily seen that no word formed by substituting any of a, b, A, B for a and b in u_{0} is a cyclic conjugate of v_{0}. So u_{0} is not conjugate to v_{0} and we have our contradiction. Once the other two cases have been similarly dealt with we conclude that G must be virtually cyclic.

The proof of the fact that groups with synchronously context-free inverse conjugacy problem are virtually free is very similar. We suppose that G has context-free inverse conjugacy problem, and that F is a free finite index normal subgroup of rank at least two with generators a, b, . . .. But now we choose u = a^{k}b^{k}a^{k}B^{k} and v = A^{k}b^{k}A^{k}B^{k}. Then u and v^{−1} are conjugate in F, so (u, v) is in the inverse conjugacy problem. From then on the argument is the same. □

3.4 Asynchronous Conjugacy Problems

We now proceed to generalise Theorem 8 to groups with asynchronously context-free conjugacy problem. The proof is similar to that of Theorem 8, but considerably more difficult technically. In particular, we need a further lemma along the lines of Lemma 6.

Lemma 9 Let u and v be cyclically reduced words over a free generating set Y of a free group F, such that neither u nor v is a proper power. Let m = max(|u|, |v|), and let w be any freely reduced word over Y. Let k, l ≥ 1. Suppose that either

(a) u is not a cyclic conjugate of v^{−1}, or

(b) u =_{F} v^{−1} and w is not a power of u.

Then the freely reduced length of u^{k}wv^{l} is greater than k|u|+l|v|−|w|−4m.

Proof: If the whole of the word w is not cancelled in the product u^{k}wv^{l}, then the reduced length of the product is at least k|u| + l|v| − |w|.

Otherwise, after cancelling just w, the resulting word has length k|u| + l|v| − |w| and is of the form u^{k′}u_{1}v_{2}v^{l′} where 0 ≤ k′ ≤ k, 0 ≤ l′ ≤ l, u = u_{1}u_{2}, v = v_{1}v_{2}. But this word can also be written as u_{1}(u′)^{k′}(v′)^{l′}v_{2}, where u′ = u_{2}u_{1} and v′ = v_{2}v_{1} are cyclic conjugates of u and v. In this case, we observe that w =_{F} u^{−k+k′+1}u_{2}^{−1}v_{1}^{−1}v^{−l+l′+1}.

Now the result clearly follows from Lemma 6 if u′v′ ≠_{F} 1.

In case (a) we certainly have u′v′ ≠_{F} 1.

In case (b), we have uv =_{F} 1. Suppose that we also have u′v′ =_{F} 1, with u′, v′ as above. Then u_{2}^{−1}v_{1}^{−1} centralises u and so is a power of u, and it follows that w a power of u, contradicting our assumption. Hence also in this case u′v′ ≠_{F} 1, and the result follows. □

Theorem 10 If a group has asynchronously context-free conjugacy problem then it is virtually cyclic.

Proof: Let G have asynchronously context-free conjugacy problem. As in Theorem 8, G is virtually free. Suppose that G is not virtually cyclic. Then G has a finite index free normal subgroup F of rank at least three. Let a, b, c be part of a free generating set Y for F, and let A = a^{−1}, B = b^{−1}, C = c^{−1}. Again, we choose a generating set X for G that contains Y.

This time, we use Lemma 7 to choose two transversals T_{b} and T_{c} of F in G, such that:

(i) for all t ∈ T_{b} ∪ T_{c}, the reduced word α over Y for t^{−1}at is cyclically reduced;

(ii) for all t ∈ T_{b}, the reduced word over Y for t^{−1}bt has the form ρ^{−1}βρ with β cyclically reduced and |ρ| as small as possible; and

(iii) for all t ∈ T_{c}, the reduced word over Y for t^{−1}ct has the form τ^{−1}γτ with τ cyclically reduced and |τ| as small as possible.

(iv) there is no cancellation in the words ρα or αρ^{−1} for t ∈ T_{b} or in the words τα or ατ^{−1} for t ∈ T_{c}.

From our earlier discussion on page 2, there is a context-free language L_{1} with alphabet X^{L} ∪ X^{R} of two disjoint copies of X such that two words u and v are conjugate in G if and only if there is a word w ∈ L_{1} with ρ_{L}(w) = u and ρ_{R}(w) = v.

We choose some suitably large k and l with k ≠ l and put

ζ = b^{k}a^{l}b^{k}a^{l}B^{k}, η = c^{l}a^{k}c^{l}a^{k}C^{l}, u = ζη, v = ηζ.

Then u, v are conjugate in F (hence in G), and we let w ∈ L_{1} be as above. In other words, w is a shuffle of u^{L} and v^{R}, copies of u and v over X^{L} respectively X^{R}. It is clear that either all of ζ^{L} occurs before ζ^{R} or all of η^{R} occurs entirely before η^{L}.

We shall suppose that the first of these possibilities occurs. We omit the other case, for which the argument is similar, the main difference being that where we use the transversal T_{b} in the arguments below, we use T_{c} in the other case.

So w ≡ w_{1}w_{2}, where ζ^{L} occurs in w_{1} and ζ^{R} within w_{2}.

We now apply Ogden’s Lemma, stated as Lemma 4, to w. We shall assume that k and l have been chosen to be larger than the constant N of the lemma. We mark all the symbols of ζ^{L} in w_{1} and all the symbols of ζ^{R} in w_{2}, and no other symbols. (In the case we are omitting, η plays the role of ζ here.)

We conclude that we can write w ≡ υϕχψω, where ϕχψ has at most N marked symbols, ϕψ has at least 1 marked symbol, and υϕ^{n}χψ^{n}ω ∈ L_{1} for all n ≥ 0. In particular, putting n = 0, we have υχω ∈ L_{1}, which means that u_{0} = ρ_{L}(υχω) and v_{0} = ρ_{R}(υχω) must be conjugate in G. Our aim is to establish a contradiction by showing that u_{0} and v_{0} are not conjugate in G.

The situation is more complicated than in Theorem 8, because we have no information about how many of the unmarked symbols are involved in ϕ and ψ. We distinguish between two cases, the first of which splits into two (similar) subcases.

Case 1a. The substring ϕχψ ends before the final marked symbol in w_{1}. Then, since k, l > N and ϕχψ has at most N marked symbols, ρ_{L}(ϕχψ) can only involve letters from within 2 neighbouring blocks of the prefix ζ of u, and hence

u_{0} ≡ \{ \begin{matrix}b^{k−r}a^{l−s}b^{k}a^{l}B^{k}η, & or \\ b^{k}a^{l−r}b^{k−s}a^{l}B^{k}η, & or \\ b^{k}a^{l}b^{k−r}a^{l−s}B^{k}η, & or \\ b^{k}a^{l}b^{k}a^{l−r}B^{k−s}η, \end{matrix}

and

v_{0} ≡ c^{l_{1}}a^{k_{1}}c^{l_{2}}a^{k_{2}}C^{l_{3}}ζ,

where 0 < r + s ≤ N, and 0 ≤ k_{i} ≤ k, 0 ≤ l_{i} ≤ l for the relevant i.

Case 1b. The substring ϕχψ begins after the first marked symbol in w_{2}. This is similar to Case 1a, after inverting u_{0} and v_{0} and interchanging their rôles, which we are allowed to do, as we only need to show that they are not conjugate.

Case 2. The substring ϕχψ includes the final marked symbol in w_{1} or the first marked symbol in w_{2} or both. Then

u_{0} ≡ b^{k}a^{l}b^{k}a^{l}B^{k−r}c^{l_{4}}a^{k_{3}}c^{l_{5}}a^{k_{4}}C^{l_{6}} and v_{0} ≡ c^{l_{1}}a^{k_{1}}c^{l_{2}}a^{k_{2}}C^{l_{3}}b^{k−s}a^{l}b^{k}a^{l}B^{k}

where again 0 < r + s ≤ N and 0 ≤ k_{i} ≤ k, 0 ≤ l_{i} ≤ l for the relevant i.

Case 2 is the more difficult, and we shall discuss it first. Let v′_{0} be the cyclic reduction of the word v_{0}. Then

v′_{0} ≡ \{ \begin{matrix}v_{0} & provided k_{2} ≠ 0 \\ c^{l_{1}}a^{k_{1}}c^{l_{2}−l_{3}}b^{k−s}a^{l}b^{k}a^{l}B^{k} & if k_{2} = 0, k_{1} ≠ 0 \\ c^{l_{1}+l_{2}−l_{3}}b^{k−s}a^{l}b^{k}a^{l}B^{k} & if k_{1} = k_{2} = 0, l_{1} + l_{2} ≠ l_{3} \\ a^{l}b^{k}a^{l}B^{s} & if k_{1} = k_{2} = 0, l_{1} + l_{2} = l_{3}. \end{matrix}

Let g ∈ G with g^{−1}u_{0}g =_{G} v_{0}. Then g =_{G} tx for some t ∈ T_{b} and x ∈ F, and t^{−1}u_{0}t is conjugate to v′_{0} within F. So the cyclic reduction u′_{0} of t^{−1}u_{0}t must be a cyclic conjugate of v′_{0}. We proceed to show that this is impossible.

Let the reduced word in F for t^{−1}ct be σ^{−1}γσ with γ cyclically reduced.

Then

t^{−1}u_{0}t ≡ \underline{ρ^{−1}β_{1}^{k}ρα_{1}^{l}ρ^{−1}β_{2}^{k}ρα_{2}^{l}ρ^{−1}β_{3}^{−(k−r)}ρ}σ^{−1}γ^{l_{4}}σα^{k_{3}}σ^{−1}γ^{l_{5}}σα^{k_{4}}σ^{−1}γ^{−l_{6}}σ,

with α_{1} ≡ α_{2} ≡ α and β_{1} ≡ β_{2} ≡ β_{3} ≡ β; The subscripts are there to enable us to refer unambiguously to the subwords. Note that property (iv) of the transversal T_{b} ensures that the underlined prefix is freely reduced. We call the non-underlined part θ.

First note that, since α, β and γ are conjugates of the images of the free generators a, b and c, none of them is a cyclic conjugate of any of the others or their inverses. And, for the same reason, none of them is a proper power. Hence any two of them satisfy the conditions of Lemma 9. We shall also use the fact that β cannot be in the normal closure of ⟨α, γ⟩.

The free reduction of θ either involves some high powers of some or all of α, γ or γ^{−1}, or can be considered to be short.

In the first case, we apply case (a) of Lemma 9 twice to show that there can be only limited cancellation between β_{3}^{−(k−r)} and whatever is the first high power surviving in the free reduction of θ, and between whatever is the last high power surviving in the free reduction of θ and β_{1}^{k}.

In the second case, we first note that the fact that β cannot be in the normal closure of ⟨α, γ⟩ excludes the possibility that ρθρ^{−1} is a non-trivial power of β. If ρθρ^{−1} is non-trivial, then we apply case (b) of Lemma 9 to see that there can be only limited cancellation involving β_{3}^{−(k−r)} and β_{1}^{k}.

Therefore, precisely one of the following holds.

(A) The free reduction of ρθρ^{−1} is empty; or

(B) Only a small fraction of β_{1}^{k} and β_{3}^{−(k−r)} are cancelled.

Since the underlined prefix of t^{−1}u_{0}t is freely reduced, in either situation the powers α_{1}^{l}, β_{2}^{k} and α_{2}^{l} survive in their entirety in u′_{0}.

Now we can deduce that |α| = |β| = 1 as follows. First, as part of a free basis of F neither α nor β can be a proper power. Then if either has length greater than 1, the number of syllables in u′_{0} must be at least min{2l, 2k}, which is larger than 10, the number of syllables in v′_{0}, so long as k and l are sufficiently large. This contradicts the fact that u′_{0} is a cyclic conjugate of v′_{0}.

In Situation (A), u′_{0} ≡ β^{r}ρα^{l}ρ^{−1}β^{k}ρα^{l}ρ^{−1} (or α^{l}ρ^{−1}β^{k}ρα^{l} if r = 0) and so u′_{0} contains only three high powers of generators. Clearly, this means that v′_{0} ≡ a^{l}b^{k}a^{l}B^{s}, in which case ρ must be empty and, since r + s > 0, we find that there are no possibilities for α and β that make u′_{0} and v′_{0} cyclic conjugates.

So it remains to consider Situation (B). Since the underlined subword is freely reduced, in this case ρ and ρ^{−1} each appear twice in u′_{0}. But the only negative powers of generators that occur in v′_{0} occur as a unique power of C and a unique power of B, so ρ must be empty. Hence

t^{−1}u_{0}t =_{G} β^{k}α^{l}β^{k}α^{l}β^{−(k−r)}θ

and u′_{0} must contain a subword of the form β^{k′}α^{l}β^{k}α^{l}β^{−k′′}, where k′, k′′ > 0.

We now consider the possibilities for α and β, assuming that u′_{0} is a cyclic conjugate of v′_{0}. Since both β and β^{−1} occur in u′_{0} and A does not occur in v_{0}, β cannot be a or A. Since there are unique powers of B and of C in v′_{0} but two disjoint powers of β in u′_{0}, we cannot have β = C or β = B. If β = c, then we would necessarily have α = a and α^{l}β^{k}α^{l} ≡ a^{k_{1}}c^{l_{2}}a^{k_{3}} and hence k_{1} = k_{3} = l, l_{2} = k, which is impossible, since k_{1} ≤ k, l_{2} ≤ l and k ≠ l. So the only possibility is that β = b which implies immediately that α = a.

Now the subwords a^{l}b^{k}a^{l} of u′_{0} and v′_{0} must correspond, so we have

a^{l}b^{k}a^{l}B^{k}c^{l_{1}}a^{k_{1}}c^{l_{2}}a^{k_{2}}C^{l_{3}}b^{k−s} =_{F} a^{l}b^{k}a^{l}B^{(k−r)}θb^{k}  (1)

and hence

c^{l_{1}}a^{k_{1}}c^{l_{2}}a^{k_{2}}C^{l_{3}} =_{F} b^{r}θb^{s} =_{F} b^{r}σ^{−1}γ^{l_{4}}σa^{k_{3}}σ^{−1}γ^{l_{5}}σa^{k_{4}}σ^{−1}γ^{−l_{6}}σb^{s}.

Now, working modulo [F, F], we have

a^{k_{1}+k_{2}}c^{l_{1}+l_{2}−l_{3}} =_{F/[F,F]} a^{k_{3}+k_{4}}b^{r+s}γ^{l_{4}+l_{5}−l_{6}}.

Since the exponent of b on the right hand side must be zero, but r+s > 0, we must have l_{4} + l_{5} − l_{6} ≠ 0. So modulo [F, F], γ must be a product of powers of a, b and c. But the automorphism of F/[F, F] induced by conjugation by t has finite order and fixes a and b, and this is only possible if γ =_{F/[F,F]} c^{±1}, and hence the exponent of b on the right hand side is non-zero. So Situation (A) is also impossible and hence Case 2 cannot occur.

Case 1 can be ruled out by similar reasoning, which we shall now describe briefly. In Case 1a, we have

u_{0} ≡ b^{k−r_{1}}a^{l−s_{1}}b^{k−r_{2}}a^{l−s_{2}}B^{k−r_{3}}η

where 0 < r_{1} + s_{1} + r_{2} + s_{2} + r_{3} ≤ N, and either just one term, or two adjacent terms of the sequence r_{1}, s_{1}, r_{2}, s_{2}, r_{3} are nonzero. As in Case 2, we let v′_{0} be the cyclic reduction of v_{0}, and we can find t ∈ T_{b} such that the cyclic reduction u′_{0} of t^{−1}u_{0}t is a cyclic conjugate of v′_{0}. Again as in Case 2, we can use a syllable count to show that |α| = |β| = 1 and then that ρ must be empty.

It follows as before that β cannot be a, A, C or B. If β = c, then we get α = a and α^{l−s_{1}}β^{k−r_{2}}α^{l−s_{2}} ≡ a^{k_{1}}c^{l_{2}}a^{k_{3}}, so l−s_{1} = k_{1}, k−r_{2} = l_{2}, l−s_{2} = k_{3}, with k_{i} ≤ k and l_{i} ≤ l. This is impossible provided that |k − l| > N, and we can assume that k and l have been chosen with this property. So, as in Case 2, we must have α = a, β = b.

Still proceeding as before, Equation (1) above becomes

a^{l}b^{k}a^{l}B^{k}c^{l_{1}}a^{k_{1}}c^{l_{2}}a^{k_{2}}C^{l_{3}}b^{k} =_{F}
a^{l−s_{1}}b^{k−r_{2}}a^{l−s_{2}}B^{k−r_{3}}σ^{−1}γ^{l}σa^{k}σ^{−1}γ^{l}σa^{k}σ^{−1}γ^{−l}σb^{k−r_{1}}

This implies immediately that s_{1} = r_{2} = s_{2} = 0, so exactly one of r_{1} and r_{3} must be nonzero, in which case we get the same contradiction as in Case 2 by working modulo [F, F]. □

4 Inverse Conjugacy Problems

We turn now to the inverse conjugacy problem. The following theorem is a special case of the later result Theorem 18, but we include it here because its proof is more straightforward, and gives an indication of the proof of Theorem 18.

Theorem 11 A finitely generated free group has asynchronously contextfree inverse conjugacy problem.

Proof: We use a free generating set for the free group. Then, by [8, Theorem 1.3], the inverse conjugacy problem consists of all pairs of words (u, v) for which the cyclic reduction of u has the form αβ while the cyclic reduction of v has the form α^{−1}β^{−1}. That is, the free reduction of u has the form γαβγ^{−1}, while the free reduction of v has the form δα^{−1}β^{−1}δ^{−1}. In other words u itself can be written as a concatenation of (not necessarily freely reduced) subwords u_{1}u_{2}u_{3}u_{4}, and v as a concatenation of subwords v_{1}v_{2}v_{3}v_{4}, where each of u_{1}u_{4}, v_{1}v_{4}, u_{2}v_{2} and u_{3}v_{3} freely reduces to the empty word.

We can recognise a pair of words of this form non-deterministically on a machine with a single stack which guesses the endpoints of each of the subwords. We read the subwords in the order u_{1}, v_{1}, u_{2}, v_{2}, u_{3}, v_{3}, v_{4}, u_{4}. We use the stack to freely reduce and so put onto it the free reduction of u_{1}, followed by a marker, then the free reduction of v_{1}, followed by a marker. Then we use the stack above this to verify that u_{2}v_{2} freely reduces to the empty word (and otherwise abort the computation), and then that u_{3}v_{3} freely reduces to the empty word (and otherwise abort). At this point, if the calculation has not been aborted, then the stack contains the free reduction of u_{1}, followed by a marker, and then the free reduction of v_{1} followed by a marker. Deleting those markers as we read on we can check first whether or not v_{1}v_{4} reduces freely to the empty word, and second whether or not u_{1}u_{4} reduces to the empty word. □

Our main aim in this section is to prove that the inverse conjugacy problem of a virtually free group is asynchronously context-free. The method employed will be basically similar to that used in the proof of Theorem 11, but will involve several additional complications.

We need to start by reviewing some basic material from geometric group theory, particularly from the theory of (word-)hyperbolic groups. The following definition and discussion is from [4, Definition I.8.14].

A (λ, ϵ)-quasi-isometric embedding with λ ≥ 1 and ϵ ≥ 0 is a map ϕ : (X_{1}, d_{1}) → (X_{2}, d_{2}) between two metric spaces such that, for all x, y ∈ X_{1}, we have

\frac{d_{1}(x, y)}{λ} − ϵ ≤ d_{2}(f(x), f(y)) ≤ λd_{1}(x, y) + ϵ.

The map ϕ is called a quasi-isometry if, in addition, there is a constant C ≥ 0 such that for all y ∈ X_{2} there exists x ∈ X_{1} with d_{2}(y, f(x)) ≤ C. The two spaces are called quasi-isometric if there is a quasi-isometry between them; being quasi-isometric is an equivalence relation on metric spaces.

The Cayley graphs of a finitely generated group G with respect to different finite generating sets are quasi-isometric. So we can unambiguously define two finitely generated groups to be quasi-isometric if their Cayley graphs are quasi-isometric. Furthermore, it is easily seen that if H has finite index in G then the embedding of the Cayley graph of H into that of G, using a finite generating set of G that contains one of H, is a quasi-isometry, and hence G and H are quasi-isometric.

For a word w over X with G = ⟨X⟩, |w|_{G} will denote the geodesic length of w as an element of G; that is, the length of a shortest word v over X with v =_{G} w. We say that w is a geodesic word in G if |w| = |w|_{G}.

A (λ, ϵ)-quasigeodesic in a metric space (X , d) is a (λ, ϵ)-quasi-isometric embedding c : I → X from a (bounded or unbounded) interval I of the real line to X. In particular, a path of length n in the Cayley graph Γ_{X} of a group G = ⟨X⟩ is a (λ, ϵ)-quasigeodesic if the standard mapping from the interval [0, n] to the path is, and a word x_{1}x_{2} ⋯ x_{n} over X is a (λ, ϵ)-quasigeodesic word in G if the path that it labels is. Assuming that λ ≥ 1 and ϵ ≥ 0, this is equivalent to the property that any subword of length k has geodesic length at least k/λ − ϵ.

To simplify some of the technicalities, we shall assume when convenient that λ and ϵ are both integers.

Lemma 12 Let ϕ: G → H be a (λ′, ϵ′)-quasi-isometry (with respect to some word metrics on G and H) and C, κ ≥ 1 constants. Let g_{0}, g_{1}, …, g_{n} ∈ G and, for 0 ≤ i ≤ n, let h_{i} ∈ H with |h_{i}^{−1}ϕ(g_{i})|_{H} ≤ C. Suppose that h_{i} ≠ h_{i+1} for 0 ≤ i < n and that there exists a (λ′′, ϵ′′)-quasigeodesic in H through h_{0}, h_{1}, …, h_{n} (in that order). Then every path u = ξ_{1} ⋯ ξ_{n} in G through g_{0}, g_{1}, …, g_{n} in which each segment ξ_{i} from g_{i−1} to g_{i} satisfies |ξ_{i}| ≤ κ is a (λ, ϵ)-quasigeodesic in G, where λ = κλ′λ′′ and ϵ = (ϵ′ +ϵ′′ +2C +2/λ′′)/λ′ + 2κ.

Proof: There is nothing to show if there is no such path u. Otherwise, let v be a subword of u and g_{j}, g_{j+1}, …, g_{j+k} be the g_{i} on v. Since |ξ_{i}| ≤ κ, we have

k ≥ |v|/κ − 2 and |v|_{G} ≥ |ξ_{j+1} ⋯ ξ_{j+k}|_{G} − 2κ.

The hypotheses h_{i} ≠ h_{i+1} and |h_{i}^{−1}ϕ(g_{i})|_{H} ≤ C together with the existence of a (λ′′, ϵ′′)-quasigeodesic through h_{j}, …, h_{j+k} (which must have length at least k) imply that

|ϕ(g_{j})^{−1}ϕ(g_{j+k})|_{H} + 2C ≥ |h_{j}^{−1}h_{j+k}|_{H} ≥ k/λ′′ − ϵ′′.

Finally, the fact that ϕ is a (λ′, ϵ′)-quasi-isometry guarantees that

|ϕ(g_{j})^{−1}ϕ(g_{j+k})|_{H}/λ′ − ϵ′/λ′ ≤ |g_{j}^{−1}g_{j+k}|_{G} = |ξ_{j} ⋯ ξ_{j+k}|_{G}.

These four inequalities immediately imply |v|/λ − ϵ ≤ |v|_{G}, whence u is a (λ, ϵ)-quasigeodesic by the remark above. □

Theorem 13 Let G = ⟨X⟩ be a finitely generated virtually free group. Then there exist constants λ ≥ 1, ϵ, κ ≥ 0 with the following property: for any word w = x_{1}x_{2} ⋯ x_{n} over X, there is a G-equivalent (λ, ϵ)-quasigeodesic word w′, obtained from w by replacing some of its subwords by G-equivalent words of length at most κ.

Proof: By assumption, G has a subgroup H of finite index that is free on some generating set Y and, by the remarks above, for some λ′ ≥ 1, ϵ′ ≥ 0, there is a (λ′, ϵ′)-quasi-isometry ϕ from G to H with respect to the word metrics |.|_{G} and |.|_{H} induced by X and Y respectively. Let w = x_{1}x_{2} ⋯ x_{n} be a word over X, and let 1 = g_{0}, g_{1}, …, g_{n} =_{G} w be the vertices on the path from the identity vertex in Γ_{X} that is labelled by w, with x_{i} labelling the edge joining g_{i−1} to g_{i}.

Since ϕ is a (λ′, ϵ′)-quasi-isometry, |ϕ(g_{i−1})^{−1}ϕ(g_{i})|_{H} ≤ λ′ +ϵ′ for each i. Let ξ_{i} be the (unique) freely reduced word over Y that labels the geodesic from ϕ(g_{i−1}) to ϕ(g_{i}); so |ξ_{i}| ≤ λ′ + ϵ′. The free reduction ξ̄ of ξ := ξ_{1}ξ_{2} ⋯ ξ_{n} is the geodesic from ϕ(g_{0}) to ϕ(g_{n}) in H. There may be more than one way of freely reducing ξ by cancelling inverse pairs of generators, but we choose one such method arbitrarily. Then we define ξ̄_{i} to be the subsequence of those letters of ξ_{i} which remain in ξ̄; this is well defined since a free reduction is simply deletion of a subword.

Let I = { i | ξ̄_{i} ≢ ε} = {i_{1}, i_{2}, …, i_{k}}, and put i_{0} = 0. Then ξ̄ ≡ ξ̄_{i_{1}} ξ̄_{i_{2}} ⋯ ξ̄_{i_{k}} and ξ_{i} ≡ ξ′_{i}ξ̄_{i}ξ′′_{i}, as ξ_{i} is freely reduced. Put h_{0} = ϕ(g_{0}) and h_{j} = h_{0}ξ̄_{i_{1}} ξ̄_{i_{2}} ⋯ ξ̄_{i_{j}} and observe that h_{k} =_{H} ϕ(g_{n}). For ease of notation, let us redefine i_{k} to be n without changing h_{k}.

Since the ξ_{i} have length at most C := λ′ + ϵ′ and ϕ(g_{i_{j}}) =_{H} h_{0}ξ̄_{i_{1}} ξ̄_{i_{2}} ⋯ ξ̄_{i_{j}}ξ′′_{i_{j}} for 1 ≤ j ≤ k − 1, we have |h_{j}^{−1}h_{j+1}|_{H} ≤ C and |ϕ(g_{i_{j}})^{−1}ϕ(g_{i_{j+1}})|_{H} ≤ 2C for 0 ≤ j < k and |h_{j}^{−1}ϕ(g_{i_{j}})|_{H} ≤ C for 0 ≤ j ≤ k. Since ϕ is a (λ′, ϵ′)-quasi-isometry, it now follows that |g_{i_{j}}^{−1}g_{i_{j+1}}|_{G} ≤ κ := 2Cλ′ + λ′ϵ′.

Consequently, it is possible to replace each subword x_{i_{j}+1} ⋯ x_{i_{j+1}} of w (which labels the segment between g_{i_{j}} and g_{i_{j+1}}) by a G-equivalent word of length at most κ and the result is a (λ, ϵ)-quasigeodesic, by Lemma 12; h_{j−1} ≠ h_{j} because ξ̄_{j} ≠ ε, and λ′′ = 1, ϵ′′ = 0 as ξ̄ is a geodesic. □

A geodesic metric space is δ-hyperbolic if all of its geodesic triangles are δ-thin; see [4, Definition III.H.1.16]. We recall that a triangle with sides A, B, C is δ-thin if there are three points, one on each of the three sides, called the meeting points, with the properties that the two meeting points on the sides adjacent to any of the three vertices of the triangle are equidistant from that vertex, and two points moving synchronously between a vertex and the two meeting points on the sides through it remain a distance at most δ apart. The group G = ⟨X⟩ is defined to be δ-hyperbolic if its Cayley graph Γ_{X} is.

Lemma 14 (Proposition 3.1 in [7]) If u, v are words in a δ-hyperbolic group G = ⟨X⟩ with u =_{G} v, u a geodesic, and v a (λ, ϵ)-quasigeodesic for some λ, ϵ, then u and v boundedly asynchronously K-fellow-travel for some constant K and some asynchronicity bound M, where K and M depend only on λ, ϵ and δ.

To simplify some of the technicalities, we shall assume that δ, M, K are all integers with δ ≥ 1, and that each vertex on u or v is at distance at most K from a vertex on v or u, respectively.

A word w over X with G = ⟨X⟩ is said to be fully reduced if w and all of its cyclic conjugates are geodesic words in G. Lemma III.Γ.2.9 of [4] says that if the group G is δ-hyperbolic and the fully reduced words u and v represent conjugate elements of G, then either max(|u|, |v|) ≤ 8δ + 1 or there exist cyclic conjugates u′ and v′ of u and v and a word α over X with αu′α^{−1} =_{G} v′ and |α| ≤ 2δ + 1.

Define w to be (λ, ϵ)-quasi fully reduced if w and all of its cyclic conjugates are (λ, ϵ)-quasigeodesic words in G. We can use a similar argument to that employed in the proof of Lemma III.Γ.2.9 of [4] to show (assuming for simplicity that λ and ϵ are integers):

Lemma 15 If u and v are (λ, ϵ)-quasi fully reduced words representing conjugate elements of a δ-hyperbolic group, then either max(|u|, |v|) ≤ λ(8δ + 2K + ϵ + 1) or there exist cyclic conjugates u′ and v′ of u and v and a word α over X with αu′α^{−1} =_{G} v′ and |α| ≤ 2(δ + K), where K is the constant of Lemma 14.

Proof: Suppose that max(|u|, |v|) > λ(8δ +2K +ϵ+1), and without loss of generality assume that |u| > λ(8δ + 2K + ϵ + 1). Choose a word α that is as short as possible such that there exist cyclic conjugates u′ and v′ of u and v with αu′α^{−1} =_{G} v′. Let u′′ and v′′ denote geodesic words with u′′ =_{G} u′ and v′′ =_{G} v′. Then, since u′ and v′ are by assumption (λ, ϵ)-quasigeodesics, by Lemma 14 they are at a uniform distance at most K from u′′ and v′′, and |u′′| > 8δ + 2K + 1.

Consider a geodesic quadrilateral Q in the Cayley graph of G whose sides, read in order from a vertex, trace out edge paths labelled α, u′′, α^{−1}, (v′′)^{−1}. We shall refer to the sides of Q that are labelled α^{±1} as the vertical sides and to the sides labelled u′′ and (v′′)^{−1} as the top and the bottom sides, respectively. We also adjoin paths labelled u′ and (v′)^{−1} to Q having the same first and last vertices as the top and bottom sides of Q. Since |u′′| ≥ 8δ +2K +2, we can choose a vertex p on the top side of Q (labelled u′′) that is at distance at least 4δ + K + 1 from both ends of this side. Then p is at a distance at most 2δ from a vertex on one of the other three sides of Q. If it were within 2δ of a point p′ on the bottom side (labelled (v′′)^{−1}), then there would be vertices q, q′ on the paths labelled u′ and v′ with d(q, q′) ≤ 2δ+2K. But then, if α′ is a word labelling a geodesic path from q′ to q, α′ conjugates a cyclic conjugate of u to a cyclic conjugate of v and hence, by choice of α, we have |α| ≤ |α′| ≤ 2(δ + K), as required.

So suppose that p is within a distance 2δ from one of the vertical sides of Q. Let x and y be respectively the top and bottom vertices of the side containing q. Then the choice of α implies that |α| ≤ d(p, y)+K, and clearly d(p, y) ≤ 2δ +d(q, y) with |α| = d(q, x)+d(q, y), so we have d(q, x) ≤ 2δ +K and therefore d(p, x) ≤ d(p, x) + d(q, x) ≤ 4δ + K, contrary to the choice of p. □

In the second case of this lemma (|α| ≤ 2(δ + K)), by considering the quadrilateral with sides labelled α, u′, α^{−1}, (v′)^{−1}, we see that every vertex p′ on u′ is either at distance at most 2(δ + K) from a vertex on the side labelled v′^{−1}, or it is at distance at most 2δ + K from a vertex on a side labelled α or α^{−1}. So it is in any case at distance at most 4δ + 3K from a vertex on the side labelled v′^{−1}. By choosing the vertex on u′ to correspond to the beginning of the original word u, we conclude that there exists a word β with |β| ≤ 4δ + 3K and β^{−1}uβ = v′′ for some cyclic conjugate v′′ of v.

By a similar argument applied to the quadrilateral with sides labelled β, u, β^{−1} and (v′′)^{−1}, we find that the vertex on the side labelled (v′′)^{−1} that corresponds to the beginning of the word v^{−1} is at distance at most 6δ +4K from the side labelled u. Hence (see diagram below) we have the following result.

[figure: β; γ; β; u_{1}; u_{2}; v_{2}; v_{1}; u; v′′]

Proposition 16 Suppose that u and v are (λ, ϵ)-quasi fully reduced words representing conjugate elements of a δ-hyperbolic group G. Then either max(|u|, |v|) ≤ λ(8δ + 2K + ϵ + 1), or we have u ≡ u_{1}u_{2} and v ≡ v_{1}v_{2} where there exist β, γ ∈ X^{∗} with |β| ≤ 4δ + 3K, |γ| ≤ 6δ + 4K, βu_{1}γ^{−1} =_{G} v_{2} and γu_{2}β^{−1} =_{G} v_{1}.

Proposition 17 Let u be a geodesic word in a δ-hyperbolic group G with δ ≥ 1. Then we have u ≡ u_{1}u_{2}u_{3}, where u_{3}u_{1} =_{G} α for some word α with |α| ≤ δ, and u_{2}α is (1, 3δ + 1)-quasi fully reduced. In other words, the word u′ ≡ u_{1}u_{2}αα^{−1}u_{3} obtained by insertion of αα^{−1} into u, can be split as u′_{1}u′_{2}u′_{3} such that u′_{3}u′_{1} =_{G} 1 and u′_{2} ≡ u_{2}α is (1, 3δ+1)- quasi fully reduced.

Proof: Let w be a geodesic word representing u^{2}, and consider the geodesic triangle with sides A, B and C, labelled by u, u, and w^{−1}, respectively. For simplicity, we shall assume that the meeting points of this triangle coincide with vertices in the Cayley graph. The argument in the other case, in which the meeting points lie midway between two vertices, is similar, and gives rise to the 3δ + 1 rather than 3δ in the proposition statement.

Let u_{3} be the suffix of u that labels the part of the side A after the meeting point of the triangle on A, and let u_{1} be the prefix of u that labels the part of the side B before the meeting point of the triangle on B. See diagram below.

[figure: w; α; u_{3}; u_{1}; u_{1}u_{2}; u_{2}u_{3}; A; B; C; a; a′; b; b′; u_{s}; u_{p}]

By definition of meeting points, we have |u_{1}| = |u_{3}|. By δ-hyperbolicity, we have u_{3}u_{1} =_{G} α with |α| ≤ δ. Suppose first that |u_{1}| ≥ |u|/2. Then we replace u_{1} and u_{3} respectively by the prefix and suffix of u of length |u|/2 or (|u| − 1)/2, and we still have u_{3}u_{1} =_{G} α with |α| ≤ δ, and also u ≡ u_{1}u_{2}u_{3} with |u_{2}| ≤ 1. Since δ ≥ 1, we have |u_{2}α| ≤ 3δ, so u_{2}α is (1, 3δ)-quasi fully reduced.

Hence we assume that |u_{1}| < |u|/2, and we can write u ≡ u_{1}u_{2}u_{3} with |u_{2}| > 0, and we need to show that u_{2}α is (1, 3δ)-quasi fully reduced. To do this, we must show that the length of any subword σ of any cyclic conjugate of u_{2}α exceeds the geodesic length |σ|_{G} of σ in G by at most 3δ. We shall denote prefixes and suffixes of α and of u_{2} by α_{p}, α_{s}, u_{p}, u_{s}, respectively. If σ has one of the forms α_{s}u_{p}, u_{s}α_{p}, or α_{s}u_{2}α_{p} then, since u_{2} (as a subword of u) is geodesic and |α_{s}| + |α_{p}| ≤ |α| ≤ δ, we see that |σ|_{G} ≥ |σ| − 2δ. Otherwise, we have σ ≡ u_{s}αu_{p} with |u_{s}|, |u_{p}| > 0. Referring again to the diagram above, by δ-hyperbolicity, the first point a on the path labelled u_{s} on A is at distance at most δ from the point a′ on C at distance |u_{s}| from the meeting point on C and coming before the meeting point on C. Similarly, the last point b on the path labelled u_{p} on B is at distance at most δ from the point b′ on C at distance |u_{p}| from the meeting point on C and coming after that meeting point. So the geodesic distance between a′ and b′ is |u_{s}| + |u_{p}| and hence |u_{s}| + |u_{p}| ≤ 2δ + |σ|_{G}, and so

|σ| = |u_{s}| + |u_{p}| + |α| ≤ |u_{s}| + |u_{p}| + δ ≤ |σ|_{G} + 3δ,

as required. □

Following these preparations, we are now ready to embark upon the proof that virtually free groups have asynchronously context-free inverse conjugacy problem. We start by describing some aspects of the proof. The pushdown automaton will be non-deterministic, it will never return a negative answer, and will only return a positive answer when it has verified that the two input words are conjugate in G; so it cannot return an incorrect answer.

It will perform various transformations on the input words as it reads them. For example it may insert words of bounded length at various points, or it may replace an input symbol that it has read by a word of bounded length. It can do these things by using its states as memory. Similarly it can read ahead a bounded number of symbols and memorise the result. The purpose of doing this is to replace the input words by other words that satisfy various desirable properties. The automaton will not in general attempt to verify that these replacement words really do have these properties. But provided that we know theoretically that such replacements are possible, together with the fact that the automaton is non-deterministic and will never return an incorrect answer, we can effectively assume that these properties really are satisfied, and we shall do that during the proof.

Here is a summary of the proof. We suppose that words u, v are given as input.

1. Modify u, v to get (λ, ϵ)-quasigeodesics, for some fixed λ, ϵ.

2. Modify u, v to get geodesics.

3. Modify u, v as in Proposition 17, inserting into each a short word of the form αα^{−1}, so that u ≡ u_{1}u_{2}u_{3}, v ≡ v_{1}v_{2}v_{1} where u_{1}u_{3} =_{G} v_{1}v_{3} =_{G} 1 and u_{2}, v_{2} are (1, 3δ + 1)-quasi fully reduced words for some fixed δ.

4. Using Proposition 16 verify that u_{2} and v_{2}^{−1} are conjugate in G.

5. Verify that u_{1}u_{3} =_{G} v_{1}v_{3} =_{G} 1.

We emphasise that these are the steps in the proof of the theorem. In reality, the modifications of the input words described in the first three steps all take place together as the input words are read by the pushdown automaton. The reader will need to convince themselves that this is possible after studying the details of how these steps are carried out.

The constants λ, ϵ, δ depend only on G and its generating set X, so we may assume that they are known to the pushdown automaton. Only the first step in this proof makes use of the fact that the group is virtually free, rather than just being δ-hyperbolic for some δ, so we shall restate the remaining steps as a separate result that says essentially that the inverse conjugacy problem is solvable for hyperbolic groups on the assumption that the input words are (λ, ϵ)-quasigeodesics, for some fixed λ and ϵ.

Theorem 18 The inverse conjugacy problem for a virtually free group is asynchronously context-free.

Proof: Let G = ⟨X⟩ be a virtually free group. We first demonstrate that Theorem 13 allows us to assume that, for some fixed λ ≥ 1 and ϵ ≥ 0, our two input words are (λ, ϵ)-geodesics. Let w be one of the input words u, v^{−1}. By Theorem 13, we can replace certain subwords w_{1}, … w_{k} of w by Gequivalent words α_{1}, α_{2}, …, α_{k} of length at most K, such that the resulting word is a (λ, ϵ)-quasigeodesic. The pushdown automaton M guesses nondeterministically which subwords should be replaced by which short words α_{i}. When it reaches the beginning of a subword w_{i} that is to be replaced by α_{i}, then it puts a marker on the stack followed by α_{i}^{−1}. It then reads w_{i} and behaves like a pushdown automaton that accepts the word problem for G by empty stack. If, after reading w_{i}, the marker is at the top of the stack, then it has verified that w_{i} =_{G} α_{i}; otherwise it aborts. If the verification is successful, then M behaves as though it had read the input α_{i} which, since |α_{i}| is bounded, is possible by using states of M as memory.

This completes the first step of the summary of the proof presented above, and the result follows from the next theorem, which handles the remaining steps in the more general context of hyperbolic groups for which the input words are assumed to be quasigeodesics. It is a standard (and elementary) result that every virtually free group is δ-hyperbolic for some δ. □

Theorem 19 Let G = ⟨X⟩ be a δ-hyperbolic group and let λ ≥ 1 and ϵ ≥ 0 be fixed. Then there is an asynchronous 2-variable pushdown automaton M over X that satisfies

{ (u, v) | u, v (λ, ϵ)-quasigeodesics, u, v^{−1} conjugate in G } ⊆ L(M)
⊆ { (u, v) | u, v^{−1} conjugate in G }.

Proof: The pushdown automaton M to be constructed attempts to replace the input words u and v by G-equivalent geodesic words. Let K and M be the constants from Lemma 14, such that a (λ, ϵ)-geodesic u and a geodesic w with u =_{G} w asynchronously K-fellow-travel with asynchronicity bound M. Now, M will maintain (by means of its states) a group element g of geodesic length at most K with g =_{G} (u′)^{−1}w′, where u′ is the prefix of u read so far, and w′ is the prefix of the word w with which it is being replaced. On reading the next input letter x of u, M replaces x by a random word α of length at most M, and replaces g by x^{−1}gα if that group element has length at most K; otherwise the computation is aborted. If g =_{G} 1 after reading all of u, then we know that u =_{G} w; otherwise the computation is aborted. So, by means of this replacement, we can assume that the input word u is geodesic. The other input word v is similarly replaced by an equivalent word, which we shall assume to be geodesic.

From now on we shall use u and v to denote the equivalent words with which the actual input words have been replaced, and assume that they are geodesics. So this completes the second step of the proof summary above.

By Proposition 17, we have u ≡ u_{1}u_{2}u_{3} where u_{3}u_{1} =_{G} α (and hence u_{1}α^{−1}u_{3} =_{G} 1) with |α| ≤ δ, and u_{2}α is (1, 3δ + 1)-quasi fully reduced. Our automaton M splits the input word non-deterministically into three parts u_{1}, u_{2}, u_{3}. It also replaces u_{2} by u_{2}α and u_{3} by α^{−1}u_{3} for some arbitrarily chosen word α with |α| ≤ δ. So Proposition 17 says that it is possible to do this such that the replaced word u_{2} is (1, 3δ + 1)-quasi fully reduced, and u_{1}u_{3} =_{G} 1.

The input word v will be similarly split up and modified into v_{1}v_{2}v_{3}, where we know that it is possible to do this such that v_{2} is (1, 3δ + 1)-quasi fully reduced, and v_{1}v_{3} =_{G} 1. This completes the third step of the proof summary.

As in the proof of Theorem 11, M starts by putting u_{1} on the stack followed by a marker μ_{1}, and then it puts v_{1} on the stack followed by a marker μ_{2}. Now if u and v^{−1} are conjugate in G then so are u_{2} and v_{2}^{−1}, and if our constructions of u_{1}, u_{2}, u_{3}, v_{1}, v_{2}, v_{3} were successful, then u_{2}, v_{2} and v_{2}^{−1} are (1, 3δ + 1)-quasi fully reduced words. So in that case we can apply Proposition 16 to u_{2} and v_{2}^{−1}. Note that the constant K in the statement of Proposition 16 depends only on δ.

Since λ(8δ +2K +ϵ+1) = 11δ +2K +2 is a constant, M can read ahead and memorise up to 11δ +2K +2 symbols of u_{2} and v_{2} and thereby test whether max(|u_{2}|, |v_{2}|) ≤ 11δ + 2K + 2. As there are only finitely many pairs of words satisfying this condition, we can assume that M knows already which of the pairs (u_{2}, v_{2}^{−1}) represent conjugate elements of G. If it finds that max(|u_{2}|, |v_{2}|) ≤ 11δ + 2K + 2 with u_{2} and v_{2}^{−1} conjugate, then it removes the marker μ_{2} from the top of the stack and reads v_{3} to verify (by empty stack) that v_{1}v_{3} =_{G} 1. If so, then the marker μ_{1} is now at the top of the stack, and M removes it and reads u_{3} to verify that u_{1}u_{3} =_{G} 1. If so, then it has proved that the two input words are conjugate and can return true. If any of these verifications fail, then the computation is aborted.

So assume that max(|u_{2}|, |v_{2}|) > 11δ + 2K + 2, and we are in the second case of Proposition 16. The automaton M now guesses words β, γ with |β| ≤ 4δ + 3K and |γ| ≤ 6δ + 4K. As M reads the words u_{2} and v_{2} it splits them arbitrarily into two subwords u_{2} ≡ u_{21}u_{22}, v_{2} ≡ v_{21}v_{22}. It first reads u_{21}, but puts βu_{21}γ^{−1} on the stack. It then reads v_{21} and tests (by empty stack) whether βu_{21}γ^{−1}v_{21} =_{G} 1. If so, then it reads u_{22}, but puts γu_{22}β^{−1} on the stack. Then it reads v_{22} and tests whether γu_{22}β^{−1}v_{22} =_{G} 1. If so, then βu_{2}β^{−1} =_{G} v_{21}^{−1}v_{22}^{−1}, which is conjugate in G to v_{2}^{−1} ≡ v_{22}^{−1}v_{21}^{−1}, so M has verified that u_{2} and v_{2}^{−1} are conjugate in G. Furthermore, the marker μ_{2} is now at the top of the stack, and M proceeds to verify that v_{1}v_{3} =_{G} 1 and that u_{1}u_{3} =_{G} 1, in the same way as above. □

5 Indexed Languages are Richer

Here we shall only give the crucial idea for the proof of Theorem C, leaving the details to the reader.

Recall that an indexed language is accepted by a nested stack automaton which is a generalisation of a pushdown automaton, introduced by Aho in [1, 2]. More precisely, such a machine may move through the stack in read only mode and at any point it can open a nested stack. The top part of the previous (outer) stack is not accessible until this new stack is empty again. This enables checking whether two input words u and v define the same element of a free group as follows. The free reduction of u is read onto the stack and then the read-write head is moved down to the beginning of u (which is marked). The read-write head then moves back up through the stack letter by letter as v is read and freely reduced, comparing the free reduction of v with the freely reduced word that is on the stack. The reduction of v, as it is being read, is achieved on nested stacks that are inserted next to the symbol currently being read on the main stack. Since such a nested stack will necessarily be empty after verifying that a subword reduces freely to the empty word, the computation will continue as if this subword was missing. Using additional states this procedure also works in a virtually free group. Hence, for a virtually free group, one can adapt the strategy of the previous Section, after observing that all necessary replacements can be justified before they are carried out on a nested stack which will be empty after an affirmative check.

References

[1] A.V. Aho, ‘Indexed grammars-an extension of context-free grammars’, J. Assoc. Comp. Mach. 15 (1968) 647–671.

[2] A.V. Aho, ‘Nested stack automata’, J. Assoc. Comp. Mach. 16 (1969) 383–406.

[3] V.A. Anisimov, ‘The group languages’, Kibernetika 4 (1971) 18–24.

[4] M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature, Springer, 1999.

[5] J.E. Hopcroft and J.D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979.

[6] D.F. Holt and C.E. Röver, ‘Groups with indexed co-word Problem’, Internat. J. Algebra Comput. 26 (2006), 985–1014.

[7] D.F. Holt and S. Rees, ‘Regularity of quasigeodesics in a hyperbolic group’, Internat. J. Algebra Comput. 12 (2002), 747–754.

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

[9] D.E. Muller and P.E. Schupp, ‘Groups, the theory of ends, and contextfree languages’, J. Comp. System Sci. 26 (1983), 295–310.

Addresses

D. F. Holt Mathematics Institute University of Warwick Coventry CV4 7AL email: D.F.Holt@warwick.ac.uk

S. Rees School of Mathematics and Statistics University of Newcastle Newcastle NE1 7RU email: sarah.rees@newcastle.ac.uk

C. E. Röver School of Mathematics, Statistics and Applied Mathematics National University of Ireland, Galway University Road Galway Ireland email: class.roever@nuigalway.ie