Conjugacy in Artin groups of extra-large type

Derek F. Holt and Sarah Rees

7th April 2015

Abstract

We describe a constructive, cubic time solution to the conjugacy problem in Artin groups of extra-large type, which was proved soluble in those groups in [2]. We use results from [7, 6] that characterise geodesic words in those groups, as well as the description of conjugacy between elements involving three or more generators that is given in [2].

1 Introduction

In [2], Appel and Schupp used arguments from small cancellation theory to prove that Artin groups of extra-large type have soluble conjugacy problem, and this result was extended to Artin groups of large type in [3]. In neither case was any analysis of the complexity of the solution attempted. In this paper, we address the complexity question in the extra-large case, and prove the following result.

Theorem 1.1 The conjugacy of two elements represented as words of length at most ℓ in an n-generator Artin group of extra-large type can be decided constructively in time O(ℓ) when n = 2 and O(nℓ^{3}) when n > 2.

An Artin group is defined by a presentation

⟨x_{1}, …, x_{n} | _{m_{ij}}(x_{i}, x_{j}) = _{m_{ij}}(x_{j}, x_{i}) for each i ≠ j⟩,

where (m_{ij}) is a Coxeter matrix (a symmetric n × n matrix with entries in ℕ∪{∞}, m_{ii} = 1, m_{ij} ≥ 2, ∀i ≠ j), and where for generators a, a′ and m ∈ ℕ we define _{m}(a, a′) to be the word that is the product of m alternating as and a′s and that starts with a. When m_{ij} is infinite, there is no relation between x_{i} and x_{j}. The set X = {x_{1}, ….x_{n}} is called the standard generating set; an element of X ∪X^{−1} is called a letter, and a finite string of letters is called a word over X. It is common to represent the Coxeter matrix graphically using a Coxeter graph Γ with n vertices, 1, …, n and an edge labelled m_{ij} joining i, j. We use the notation G(Γ) to denote the Artin group defined by the Coxeter graph Γ.

An Artin group has large type if all the integers m_{ij} are at least 3, and extra-large type if they are all at least 4. Peifer proved in [11] that Artin groups of extra-large type are biautomatic, and it is proved in [7] that Artin groups of large type are automatic, which implies that their word problem is soluble in quadratic time. Our proof of Theorem 1.1 will use Peifer’s result, and also make use of many of the techniques that we developed in [7].

Let G be an Artin group of extra-large type, with generating set X. To prove Theorem 1.1 we describe a cubic time algorithm that, given words u, v representing elements g, h ∈ G as input, determines whether or not g, h are conjugate, and if so produces a specific conjugating element. The algorithm varies depending on whether u, v involve one, two, or at least three generators, and the remaining sections of this article are organised accordingly. In many situations the conjugacy problem reduces to the conjugacy problem within a dihedral Artin group, and so we study that first, in Section 3. Then Section 4 examines the structure of conjugates of powers of a generator. Section 5 proves that when one of the input words is written over two generators and is not a power of a generator, conjugacy can be determined using the algorithm for the appropriate dihedral Artin groups. Section 6 analyses the complexity of the complete algorithm.

We use a number of results from [7, 6] describing the structure of geodesic words in Artin groups of dihedral or large type, and the reduction of words to that form; a word w is geodesic if its length |w| is minimal over all words over X that represent the same element of G as w. Section 2 summarises what we need from [7, 6].

In our algorithm we shall need both words and elements to be cyclically reduced. As is standard, we call a word w over X cyclically reduced if it is freely reduced and does not have the form aua^{−1}, for any letter a. We call an element g ∈ G cyclically reduced if all geodesic words representing g are cyclically reduced or, equivalently, if the geodesic length |aga^{−1}| of aga^{−1} is no shorter than that of g, for any letter a. (This equivalence follows from the fact that all relators of G have even length, and so |aga^{−1}| < |g| implies |aga^{−1}| = |g| − 2.)

The analysis of the complexity of our algorithm makes use of the fact, proved in [11], that Artin groups of extra-large type are biautomatic with geodesic normal form. In any such group, words over the generators can be reduced to normal form in quadratic time and, if w is already in normal form and a is a letter, then aw and wa (and hence also awa^{−1}) can be reduced to normal form in linear time.

We also use [2, Theorem 4′′]:

Theorem 1.2 (Appel, Schupp, 1983) Let G be an Artin group of extralarge type. Then G has soluble conjugacy problem. Furthermore, if u and v are specially cyclically reduced words involving at least three generators then u and v are conjugate in G if and only if there are cyclic permutations u^{∗} and v^{∗} of u and v, respectively, a generator x_{i} occurring in both u and v, and an exponent n such that u^{∗} = x_{i}^{n}v^{∗}x_{i}^{−n} in G.

A word is defined in [2] to be specially cyclically reduced if none of its cyclic conjugates can be reduced in length in G using a certain type of substitution. So, in particular, if all cyclic conjugates of the word are geodesics, then it is specially cyclically reduced.

Proof of Theorem 1.1: The case n = 2 is proved as Proposition 3.1. So from now on we assume that n > 2.

The theorem is proved by the description of the algorithm, and analysis of its correctness and complexity. Here we describe the basic steps of the algorithm. The details are given, with justification, in the sections that follow this one. Complexity is analysed in Proposition 6.1.

Suppose that we are given words u, v representing the elements g, h for which we want to test conjugacy.

First we replace u, v by normal form representatives, and check whether the geodesic lengths of the elements represented by aua^{−1} and ava^{−1}, for a ∈ X ∪ X^{−1}, are less than |u| and |v|; if they are, then we replace g, h by appropriate conjugates and repeat this process as necessary. Now g, h are ensured cyclically reduced, and u, v are in normal form.

Now we check to see if either u or v is a power of a single generator. If so, then g and h can only be conjugate if u and v have the form x^{k} and y^{k} for some integer k and generators x, y linked by a path in the Coxeter graph on which all edges have odd labels. This is justified in Proposition 4.2.

Suppose next that one of u, v involves just two generators. In that case g and h can only be conjugate if u and v involve the same two generators x, y, and if g, h are conjugate in the subgroup of G generated by x, y; this is justified by Proposition 5.1. So in this case we can use the algorithm for dihedral Artin groups, and apply Proposition 3.1.

Finally suppose that both u and v involve at least three generators. We need to reduce to the situation where the conditions of Theorem 1.2 are satisfied. So we check that all cyclic conjugates of the words u, v are geodesic, by reducing each to normal form. If not, then we replace g, h by appropriate conjugates, and repeat as necessary. At the end of this process, we have either landed in the one or two generator case (and can use the methods referred to above) or we can assume that u, v satisfy the hypotheses of Theorem 1.2. That theorem together with Proposition 6.2 ensures that a complete test for conjugacy is provided by computing and comparing the normal forms of all elements represented by v^{∗} and a^{n}u^{∗}a^{−n}, where u^{∗} is a cyclic conjugate of u, v^{∗} is a cyclic conjugate of v, a ∈ X ∪X^{−1}, and n ≤ |u|. □

In a forthcoming paper [5] we shall use some of the results proved in this paper to show that, in an Artin group of extra-large type, the set of conjugacy geodesics is regular. We define a word to be a conjugacy geodesic if its length is minimal among representatives of elements in its conjugacy class.

2 Background on Artin groups

In this section we give some background on Artin groups, reproducing results already proved in [7, 6] that we shall need in this article. Almost all of those results are valid for all Artin groups of large type.

Suppose first that G is any n-generator Artin group, given in its standard presentation, and that X is its standard generating set. A non-empty word over X is called positive if it involves only positive powers of generators, and negative if it involves only negative powers; otherwise it is called unsigned. We write f[w], l[w] to denote the first and last letters of a word w. Where a is a letter, we call the corresponding generator (a or a^{−1}) the name of a. For letters a, b we extend the notation already used in the Artin group presentations and define _{k}(a, b) to be the product of k alternating as and bs that starts with a, and (a, b)_{k} to be the product of k alternating as and bs that ends with b.

For elements g_{1}, …, g_{k} ∈ G, we say that the product g_{1} ⋯ g_{k} is geodesic if the element g it represents has length equal to the sum of the lengths |g_{i}|; equivalently g_{1} ⋯ g_{k} is a geodesic factorisation of g. In this situation, g_{1} is called a left divisor of g, and g_{k} a right divisor of g.

Now, for an integer m, let G(m) denote the dihedral Artin group

⟨x_{1}, x_{2} | _{m}(x_{1}, x_{2}) = _{m}(x_{2}, x_{1})⟩.

For i, j ∈ {1, …, n} with i ≠ j, G(i, j) will denote the subgroup of G generated by x_{i}, x_{j}; by [8] G(i, j) is isomorphic to the dihedral Artin group G(m_{ij}).

Geodesics in dihedral Artin groups are recognised using a criterion described in [10]. Let w be a freely reduced word over the generating set {x_{1}, x_{2}} of the dihedral Artin group G(m). Then we define p(w) to be the minimum of m and the length of the longest subword of w of alternating x_{1}’s and x_{2}’s (that is, the length of the longest subword of w of the form _{r}(x_{1}, x_{2}) or r(x_{2}, x_{1})). Similarly, we define n(w) to be the minimum of m and the length of the longest subword of w of alternating x_{1}^{−1}’s and x_{2}^{−1}’s. The following is proved in [10, Proposition 4.3]:

Proposition 2.1 The word w is geodesic in G(m) if and only if p(w) + n(w) ≤ m. If p(w)+n(w) < m, then w is the unique geodesic representative of the group element it defines, but if p(w) + n(w) = m then there are other representatives.

A freely reduced, unsigned word w over {x_{1}, x_{2}} with p(w) + n(w) = m is defined to be critical if it is has either of the forms

p(x, y)ξ(z^{−1}, t^{−1})_{n} or _{n}(x^{−1}, y^{−1})ξ(z, t)_{p}.

with p = p(w), n = n(w) and {x, y} = {z, t} = {x_{1}, x_{2}}. (Obviously these conditions put some restrictions on the subword ξ.) We define a positive geodesic word w to be critical if it has either of the forms_{m}(x, y)ξ or ξ(x, y)_{m}, and only the one positive alternating subword of length m. Similarly we define a negative geodesic word w to be critical it is has either of the forms m(x^{−1}, y^{−1})ξ or ξ(x^{−1}, y^{−1})_{m}, and only the one negative alternating subword of length m.

The element Δ represented by the geodesic words (x_{1}, x_{2})_{m} and (x_{2}, x_{1})_{m} conjugates x_{1} to x_{2}, and x_{2} to x_{1} when m is odd, and is central when m is even. For a word ξ, we denote by δ(ξ) the image of ξ under the map that maps each generator to its conjugate under Δ.

Now we define an involution τ on the set of critical words by

τ(_{p}(x, y) ξ (z^{−1}, t^{−1})_{n}) := _{n}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{p},  (p, n > 0)
τ(_{n}(x^{−1}, y^{−1}) ξ (z, t)_{p}) := _{p}(y, x) δ(ξ) (t^{−1}, z^{−1})_{n},  (p, n > 0)
τ(_{m}(x, y)) := _{m}(y, x),
τ(_{m}(x^{−1}, y^{−1})) := _{m}(y^{−1}, x^{−1}),
τ(_{m}(x, y) ξ) := δ(ξ) (z, t)_{m}, where z = l[ξ], {x, y} = {z, t},
τ(ξ (x, y)_{m}) := _{m}(t, z) δ(ξ), where z = f[ξ], {x, y} = {z, t},
τ(_{m}(x^{−1}, y^{−1}) ξ) := δ(ξ) (z^{−1}, t^{−1})_{m}, where z = l[ξ]^{−1}, {x, y} = {z, t},
τ(ξ (x^{−1}, y^{−1})_{m}) := _{m}(t^{−1}, z^{−1}) δ(ξ), where z = f[ξ]^{−1}, {x, y} = {z, t}.

In all cases, a critical word and its image under τ represent the same group element; this is easily verified using equations such as _{p}(x, y) = _{n}(y^{−1}, x^{−1})Δ.

A freely reduced non-geodesic word in a dihedral Artin group must contain a critical subword whose replacement by its image under τ will produce a word admitting a free reduction [7, Lemma 2.3].

We define a word w to be over-critical if p(w) + n(w) > m. We can extend our definition of τ to over-critical words via

τ(_{p}(x, y) ξ (z^{−1}, t^{−1})_{n}) := _{m−p}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{m−n},
τ(_{n}(x^{−1}, y^{−1}) ξ (z, t)_{p}) := _{m−n}(y, x) δ(ξ) (t^{−1}, z^{−1})_{m−p}.

An over-critical word and its image under τ represent the same group element, but the image under τ is shorter.

Now, and for the remainder of this section, suppose that G = G(Γ) is an Artin group of large type with generating set X.

We can extend the definition of critical and over-critical words to words defined over any two of the generators of X in the obvious way. Again, critical words give us a criterion for recognising geodesics; a non-geodesic word must contain a critical subword, and admit a sequence of τ-moves to overlapping subwords the last of which provokes a free reduction [7]. We call such a sequence a reducing sequence. The sequence is rightward if each τmove is applied to the right of its predecessor. Such a sequence of reductions to a word w corresponds to a critical factorisation of w as αu_{1} ⋯ u_{k}β, where each of u_{1}, l[τ(u_{1})]u_{2}, …, l[τ(u_{k−1}]u_{k} is critical, and where the last letter of τ(u_{k}) freely cancels with the first letter of β.

We need some results from [7, 6] about geodesics words in G. Proofs are supplied in [7, 6].

Proposition 2.2 [7, Proposition 4.5] Suppose that v, w are any two geodesic words representing the same group element, and that l[v] ≠ l[w]. Then (1) l[v] and l[w] have different names;

(2) The maximal 2-generator suffixes of v and w involve generators with names equal to those of l[v] and l[w];

(3) Any geodesic word equal in G to v must end in l[v] or in l[w].

Corresponding results apply if f[v] ≠ f[w].

Corollary 2.3 [6, Corollary 7.2] If wa is a geodesic word for some a ∈ A, then wa^{k} is a geodesic word for all k > 1.

Proposition 2.4 [6, Proposition 7.5]

(1) Let v, w be two geodesic words representing the same group element g, with l[v] ≠ l[w]. Then a single rightward critical sequence can be applied to v to yield a word ending in l[w].

(2) Let v be a freely reduced non-geodesic word with v = wa, with a ∈ A and w geodesic. Then v admits a rightward length reducing sequence.

Proposition 2.5 [6, Proposition 7.3] Let g ∈ G and x_{i}, x_{j} ∈ X with i ≠ j. Then g has a unique left divisor LD_{ij}(g) ∈ G(i, j) of maximal length. Furthermore, if w is any geodesic word representing g, and u is the maximal {x_{i}, x_{j}}-prefix of w, then LD_{ij}(g) =_{G} ua^{r} for some r ≥ 0 with a ∈ {x_{i}^{±1}, x_{j}^{±1}} and |LD_{ij}(g)| = |u| + r.

Similarly, g has a unique right divisor RD_{ij}(g) ∈ G(i, j) of maximal length, to which the corresponding results apply.

The following two lemmas are stated and proved in [6] in a specific setting defined in that article. But it is clear that the proofs of [6] are valid more generally, and so can be applied in this article. So we do not reprove the results as stated here.

Lemma 2.6 [6, Lemma 7.11] Suppose that g = g_{1}g_{2}g_{3}, with g_{2} ∈ G(i, j) not a power of a generator, and RD_{ij}(g_{1}) = LD_{ij}(g_{3}) = 1. Suppose also that g_{1}g_{2}g_{3} is not a geodesic factorisation of g. Then g_{2} = a^{s}b^{t} for some s, t > 0 where a, b ∈ {x_{i}^{±1}, x_{j}^{±1}}.

Lemma 2.7 [6, Lemma 7.12] Let G = G(Γ) be an Artin group of extralarge type. Suppose that g = g_{1}g_{2}g_{3}, with g_{2} = a^{s}b^{t} with a = x_{i}^{±1}, b = x_{j}^{±1} i ≠ j, s, t > 0 and RD_{ij}(g_{1}) = LD_{ij}(g_{3}) = 1, and that g_{1}g_{2}g_{3} is not a geodesic factorisation of g.

Then there exists a letter c = x_{i′}^{±1} for i′ ≠ i, j, q > 0, and elements e_{1}, e_{2} of G, such that g_{1}a^{s} =_{G} e_{1}c^{q} and b^{t}g_{3} =_{G} c^{−q}e_{2}, where e_{1}c^{q}, c^{−q}e_{2} and e_{1}e_{2} are all geodesic factorisations.

3 Conjugacy in dihedral Artin groups

We recall that G(m) denotes the dihedral Artin group

⟨x_{1}, x_{2} | _{m}(x_{1}, x_{2}) = _{m}(x_{2}, x_{1})⟩.

This section is devoted to the proof of the case n = 2 of Theorem 1.1; that is, where G = G(m).

Proposition 3.1 The conjugacy of two elements represented as words of length at most ℓ in the dihedral Artin group G(m) group of large type can be decided constructively in time O(ℓ).

Proof: For m even,

G(m) ≅ ⟨y_{1}, y_{2} | y_{1}y_{2}^{m/2} = y_{2}^{m/2}y_{1}⟩.

with y_{1} = x_{1}, y_{2} = x_{1}x_{2}. So, the quotient of G(m) by its central subgroup ⟨z := y_{2}^{m/2}⟩ is a free product C_{m/2} ⋆ C_{∞}. Since that free product has trivial centre, we see that Z := ⟨z⟩ is the centre of G(m).

For m odd,

G(m) ≅ ⟨y_{1}, y_{2} | y_{1}^{2} = y_{2}^{m}⟩

with y_{1} = _{m}(x_{1}, x_{2}), y_{2} = x_{1}x_{2}. So, now the quotient of G(m) by the central subgroup ⟨z := y_{2}^{m}⟩ is a free product C_{2} ⋆ C_{m}, and again Z := ⟨z⟩ is the centre of G(m).

In either case, and also when m is infinite (and so Z = 1), G(m)/Z is a free product of two cyclic groups and so, for g ∉ Z, C_{G(m)/Z}(gZ) is cyclic. So the inverse image of C_{G(m)/Z}(gZ) in G(m) is abelian; this means in particular that g cannot be conjugate within G(m) to any other element of gZ.

Conjugacy testing in free products is straightforward, by [9, Theorem 4.2]: in the case of a free product of two cyclic groups, two elements are conjugate if and only if the normal form of one is (essentially) a cyclic conjugate of that of the other. Suppose g, h ∈ G(m) are given. If g and h are conjugate, then so are the elements gZ and hZ of G/Z, and in that case, for any element xZ with gZ = hZ^{xZ}, by the final statement in the preceding paragraph, we must have g = h^{x}. Hence, to test for conjugacy of g and h, we first test for conjugacy of gZ and hZ; then, having found some x with gZ = hZ^{xZ}, we check whether h^{x} = g. If gZ and hZ are non-conjugate, or otherwise if for x as above h^{x} ≠ g, then g and h are proved non-conjugate.

The steps in this process are

1. conversion of input words written over the standard generating set {x_{1}, x_{2}} to words over {y_{1}, y_{2}};

2. collection of the resulting words into a free product normal form modulo Z, followed by a power of z;

3. checking whether the free product normal form of one of the words is a cyclic conjugate of the other and the powers of z are the same.

4. writing down a conjugator as a word over {y_{1}, y_{2}}, and then rewriting it as a word over {x_{1}, x_{2}}.

Each of these four steps can be done in linear time □

4 Conjugates of powers of a generator

This section is devoted to the first case considered in the proof of Theorem 1.1 for which n > 2, where one of the two input elements is a power of a generator. The conjugates of powers of a generator are easy to recognise in dihedral Artin groups.

Proposition 4.1 Suppose that h is cyclically reduced, and conjugate to g := x_{1}^{k} in G(m), for some k ≠ 0. If h ≠ g, then m is odd and h = x_{2}^{k}.

Proof: Recall that if m is odd, then the element Δ = _{m}(x_{1}, x_{2}) conjugates x_{1} to x_{2}; if m is even, then Δ is central.

Let f^{−1}gf = h. The proof is by induction on |f|. The case |f| = 0 is clear, so assume |f| > 0. We may assume that g = x_{1}^{k} with k ≠ 0. Now f does not have x_{1}^{±1} as a left divisor, or else we could find a shorter conjugator, so gf and f^{−1}g are geodesic factorisations. But f^{−1}gf cannot be a geodesic factorisation, or else h would not be cyclically reduced.

Let u be a geodesic word for f. Then f[u] = x_{2}^{±1}, so u^{−1}x_{1}^{k}u is freely reduced. Let p := p(u), n := n(u), as defined in Section 2. We have p, n < m, since otherwise f has Δ^{±1} as a left divisor, and hence also x_{1}^{±1}.

Now if p > 0, then u^{−1}x_{1}^{k}u contains a subword w = _{p}(x^{−1}, y^{−1})ξ(z, t)_{p}, where {x, y} = {z, t} = {x_{1}, x_{2}}, and the subword x_{1}^{k} representing g is within ξ. This is equal in G to the word w′ = _{m−p}(y, x)δ(ξ)(t^{−1}, z^{−1})_{m−p},

If p > m/2 then w′ is shorter than w, and so we can find a representative of h of the form u^{′−1}δ(x_{1}^{k})u′ that has w′ as a subword and for which u′ is shorter than u. So h = f^{′−1}g′f′ with |f′| < |f| and g′ = δ(g) conjugate to g. The result then follows by the inductive hypothesis. Similarly the result follows when n > m/2.

Since u^{−1}x_{1}^{k}u is non-geodesic, we have p(u^{−1}x_{1}^{k}u) + n(u^{−1}x_{1}^{k}u) > m. This inequality cannot hold if both p < m/2 and n < m/2. Hence to complete the proof it remains to consider the cases where m is even and either p = l or n = l, where l = m/2.

Assume that k > 0 (the case k < 0 is similar). Then p(u^{−1}x_{1}^{k}u)+n(u^{−1}x_{1}^{k}u) > m is only possible if p = l and u has a prefix _{l}(x_{2}, x_{1}) or _{l}(x_{2}^{−1}, x_{1}^{−1}). In the former case, we have

l(x_{2}, x_{1})^{−1} x_{1}^{k} _{l}(x_{2}, x_{1}) = (x_{1}^{−1}, x_{2}^{−1})_{l} x_{1}^{k−1} _{l+1}(x_{1}, x_{2})

The right hand side is an over-critical word and so can be reduced as described in Section 2. When l is even we express the right hand side as l(x_{1}^{−1}, x_{2}^{−1}) x_{1}^{k−1} (x_{2}, x_{1})_{l+1} and see that

l(x_{1}^{−1}, x_{2}^{−1}) x_{1}^{k−1} (x_{2}, x_{1})_{l+1} =_{G} _{l}(x_{2}, x_{1}) x_{1}^{k−1} (x_{1}^{−1}, x_{2}^{−1})_{l−1}
= _{l}(x_{2}, x_{1}) x_{1}^{k−1} _{l−1}(x_{2}, x_{1})^{−1}
= _{l−1}(x_{2}, x_{1}) x_{1}^{k} _{l−1}(x_{2}, x_{1})^{−1},

while if l is odd we express the right hand side as _{l}(x_{2}^{−1}, x_{1}^{−1}) x_{1}^{k−1} (x_{1}, x_{2})_{l+1} and see that

l(x_{2}^{−1}, x_{1}^{−1}) x_{1}^{k−1} (x_{1}, x_{2})_{l+1} =_{G} _{l}(x_{1}, x_{2}) x_{1}^{k−1} (x_{2}^{−1}, x_{1}^{−1})_{l−1}
= _{l}(x_{1}, x_{2}) x_{1}^{k−1} _{l−1}(x_{1}, x_{2})^{−1}
= _{l−1}(x_{1}, x_{2}) x_{1}^{k} _{l−1}(x_{1}, x_{2})^{−1}.

In either case, we have replaced f by a shorter element, and the result follows by the inductive hypothesis. A similar argument applies when u has the prefix _{l}(x_{2}^{−1}, x_{1}^{−1}). □

Note that when n ≥ 3, two generators x_{i}, x_{j} of G can be conjugate even when m_{ij} is even. This happens if there is a sequence of generators x_{i} = x_{i_{1}}, x_{i_{2}}, …, x_{i_{k}} = x_{j} with each m_{i_{t},i_{t+1}} odd (and so Δ_{i_{t}i_{t+1}} := (x_{i_{t}}, x_{i_{t+1}})_{m_{i_{t}i_{t+1}}} conjugates x_{i_{t}} to x_{i_{t+1}}). In that case, we say that x_{i}^{k} and x_{j}^{k} are generator conjugate.

The following proposition generalises Proposition 4.1 to show that, in groups of large type, the conjugates of powers of a generator are straightforward to recognise. We recall the definition of LD_{ij}(g) and RD_{ij}(g) from Section 2 as the longest left and right divisors of g in G(i, j) respectively, where G(i, j) := ⟨x_{i}, x_{j}⟩ < G.

Proposition 4.2 Suppose that G has large type, and that h is cyclically reduced, and conjugate to g := x_{i}^{k} in G, for some k ≠ 0. If h ≠ g, then h = x_{j}^{k} for some j, and g and h are generator conjugate.

Proof: Choose an element f such that f^{−1}gf = h. The proof is by induction on |f|. The case |f| = 0 is clear, so assume |f| > 0. We may assume that g = x_{j}^{k} with k ≠ 0.

The result is clear if f is a power of a generator so suppose not, and let u be a geodesic representative of f.

Suppose that neither of the first two generators occurring in any geodesic representative of f is x_{i}. By Proposition 2.4 (ii), the word u^{−1}gu must admit a rightward reducing sequence that starts either in u^{−1} or in g. But our assumption ensures that u^{−1}gu can contain no critical subword that intersects g. So the sequence must start wholly within u^{−1}, and in that case some word u^{′−1}gu, for which u′ is a geodesic representative of f, must contain a critical subword intersecting g and u^{′−1}. Again our assumptions forbid that.

So now (if necessary replacing u by another geodesic representative) we may assume that one of the first two generators of u is x_{i}. Let x_{j} be the other one, and let f = de with d := LD_{ij}(f). If g′ := d^{−1}gd is a power of a generator, then g and g′ are generator conjugate by Proposition 4.1. We then have h = e^{−1}g′e and the result follows by the inductive hypothesis, since |e| < |f|.

So d^{−1}gd is not a power of a generator and hence, by Proposition 4.1, it cannot be cyclically reduced, and so it has a geodesic representative (of the form ava^{−1}) with at least three syllables. Any other geodesic representative can be transformed to this by a sequence of τ-moves, so must contain a critical subword and hence also at least three syllables. But then, by Lemma 2.6, f^{−1}gf is a geodesic factorisation, contradicting the fact that h is cyclically reduced. □

5 Conjugacy of words involving two generators

Proposition 5.1 Let G = ⟨x_{1}, x_{2}, …, x_{n}⟩ be an Artin group of extra-large type. Let g, h be cyclically reduced and conjugate in G with g ∈ G(i, j) for some i, j, where g is not a power of a generator. Then h ∈ G(i, j) and g, h are conjugate in G(i, j).

Proof: Let h = f^{−1}gf where f ∉ G(i, j).

Let f = de with d := LD_{ij}(f). So e ≠ 1. Then, since g is not a power of a generator, by Lemma 4.1 g′ := d^{−1}gd cannot be a power of a generator, so it has at least two syllables. Now by Lemmas 2.6 and 2.7, applied with g_{1} = e^{−1}, g_{2} = g′, g_{3} = e, either

(i) e^{−1}g′e is a geodesic factorisation; or (ii) g′ =_{G} a^{s}b^{t} with (without loss of generality) a = x_{i}^{±1}, b = x_{j}^{±1} and

s, t > 0. Furthermore, for some letter c with name x_{k} ≠ x_{i}, x_{j}, we have e^{−1}a^{s} =_{G} e_{1}c^{q} and b^{t}e =_{G} c^{−q}e_{2}, where e_{1}c^{q}, c^{−q}e_{2} and e_{1}e_{2} are geodesic factorisations.

In Case (i), h is not cyclically reduced, contrary to assumption.

In Case (ii), let g′′ be the group element b^{t}e. Then LD_{jk}(g′′) has both b^{t} and c^{−q} as left divisors, and so by Lemma 2.1 for any geodesic representative w of LD_{jk}(g′′) we have p(w) + n(w) = m ≥ 4, and so w has at least four syllables. Then any representative of LD_{jk}(e) has at least three syllables, the first of which must be a power of x_{k} (recall that by construction no power of x_{i} or x_{j} can be a left divisor of e). Similarly, considering the group element a^{−s}e =_{G} c^{−q}e_{1}^{−1}, we deduce that LD_{ik}(e) has at least three syllables, the first of those also a power of x_{k}. Now for some r, x_{k}^{r}e has distinct geodesic representatives with distinct first letters, one of which starts with a word over x_{i}, x_{k} and the other with a word over x_{j}, x_{k}. This contradicts Proposition 2.2. □

6 Complexity and correctness

We need to analyse the complexity of our algorithm in the case n ≥ 3, and to justify the fact that we only need consider conjugates a^{n}u^{∗}a^{−n} with n ≤ |u| in the final step of the algorithm. We carry out the complexity analysis in Proposition 6.1 and justify the restriction on n in Proposition 6.2. Recall that any Artin group of extra-large type has a geodesic normal form arising from its biautomatic structure.

Proposition 6.1 When n ≥ 3 the algorithm described in the proof of Theorem 1.1 decides conjugacy between two words of length at most ℓ in an n-generator Artin group of extra-large type in time O(nℓ^{3}).

Proof: Let u, v be words of length at most ℓ. We analyse each step of the algorithm.

1. Reducing u and v to normal form takes time O(ℓ^{2}).

2. We reduce all cyclic conjugates of u and v to normal form. If u = a_{1}a_{2} ⋯ a_{t} with t ≤ ℓ and, for 1 ≤ k ≤ t, u_{k} is the cyclic conjugate a_{k}a_{k+1} ⋯ a_{t}a_{1} ⋯ a_{k−1} of u and we have computed the normal form u′_{k} of u_{k}, then we can compute u′_{k+1} as the normal form of a_{k}^{−1}u′_{k}a_{k} which, by biautomaticity, can be done in time O(ℓ). So the total time for this step is O(ℓ^{2}).

3. We check that the cyclic conjugates of u and v are all cyclically reduced as group elements, by checking |au′_{k}a^{−1}| ≥ |u′_{k}| and |av′_{k}a^{−1}| ≥ |v′_{k}| for all k and all a ∈ X ∪X^{−1} involved in u and v. This takes time O(nℓ^{2}).

4. If any of the normal form words for u′_{k} (or v′_{k}) or any of their conjugates under a ∈ X ∪ X^{−1} in Steps 2 or 3 is shorter than u (or v), then we replace u (or v) by this shorter word and restart. Since this can happen at most ℓ times, the total time so far is O(nℓ^{3}).

At this stage u and v are both specially cyclically reduced, and |u′_{k}| = |u|, |v′_{k}| = |v| for all k.

5. If one of u is a power x_{i}^{k}, then we can check in time O(ℓ) whether v is also a k-th power x_{j}^{k} of a generator. In that case u and v are conjugate if i and j are in the same component of the graph formed from the Coxeter graph by deleting even-labelled edges; those components can be computed in time O(n^{2}) in pre-processing time before the algorithm takes input.

6. If u, v ∈ G(i, j) for some i, j, then we are in the 2-generator case, and we proved in Section 3 that we can test u and v for conjugacy in time O(ℓ).

Otherwise, by Theorem 1.2, if u and v are conjugate, then they must both involve the same set of at least three generators. If not, then we return false.

At this stage we can apply Theorem 1.2 and Proposition 6.2, which is stated and proved below. In fact Proposition 6.2 implies that if u and v are conjugate then |u| = |v|, so we return false if not.

7. We initialise an automaton for string searching for one of the normal forms v′_{k} of the cyclic conjugates v_{k} of v. By [1, 4], this takes time O(ℓ^{2}).

8. For each letter a ∈ X ∪ X^{−1} that is involved in u, each normal form u′_{k} of the cyclic conjugate u_{k} of u, and each j with 1 ≤ j ≤ |u|, we compute the normal form of a^{j}u′_{k}a^{−j}, and use the automaton to check whether this equals any of the normal forms v′_{k} of the cyclic conjugates of v. By biautomaticity, computing each of these normal forms takes time O(ℓ) as does the search for equality with v_{k}, so the total time for this step is O(nℓ^{3}).

(Note that we have already computed these normal forms when j = 1 in Step 3, so we could avoid that repetition.)

□

Proposition 6.2 Suppose that g, h are cyclically reduced elements in G, an Artin group of extra-large type, and suppose that, for some generator a ∈ X ∪ X^{−1} and some N ∈ ℕ, a^{N}ga^{−N} = h. Then |g| = |h|, and either g = h or N ≤ |g|.

Proof: Let g = a^{r}g_{0}a^{s} with r, s ∈ ℤ be a geodesic factorisation of g, where g_{0} has neither a nor a^{−1} as left or right divisor. Since g is cyclically reduced, r and s cannot have opposite signs, and we assume without loss of generality that r, s ≥ 0. If N ≤ s then N ≤ |g|, and h = a^{r+N}g_{0}a^{s−N} is a geodesic factorisation of h, so |g| = |h| and we are done. So assume that N − s > 0.

Then h = a^{N+r}g_{0}a^{−N+s} = a^{N−s}a^{r+s}g_{0}a^{−(N−s)}. This last product cannot be geodesic, since h is cyclically reduced; hence neither is the product ag_{0}a^{−1}, by Corollary 2.3. Since, by assumption, g_{0} has neither a nor a^{−1} as left or right divisor, the products ag_{0} and g_{0}a^{−1} are geodesic, and so |g_{1}| = |g_{0}|, where g_{1} = ag_{0}a^{−1}.

We claim that g_{1} cannot have a or a^{−1} as left or right divisor. If g_{1} has a as left divisor, then we get |a^{−1}g_{1}| < |g_{1}|, but a^{−1}g_{1} = g_{0}a^{−1}, so this contradicts |g_{0}a^{−1}| = |g_{0}| + 1 = |g_{1}| + 1. If g_{1} has a^{−1} as left divisor, then g_{1}a has a geodesic representative beginning with a^{−1} and another one (arising from g_{1}a = ag_{0}) beginning with a, which is impossible by Proposition 2.2. The proof for right divisors is similar.

Continuing in this way, we find a sequence g_{0}, g_{1}, …, g_{N−s} of elements, all of length |g_{0}|, such that ag_{i}a^{−1} = g_{i+1} for 0 ≤ i < N − s, where none of the g_{i} has a or a^{−1} as left or right divisor. Since h = a^{r+s}g_{N−s}, we have |g| = |h|.

In fact, since ag_{i} and g_{i}a^{−1} are geodesic factorisations but ag_{i}a^{−1} is not, each ag_{i} must admit a rightward critical factorisation (aw_{1}^{(i)})w_{2}^{(i)} ⋯ w_{k}^{(i)}, as defined in Section 2 (with u_{1} = aw_{1}^{(i)}, u_{2} = w_{2}^{(i)}, …), which the associated rightward sequence of τ-moves transforms to g_{i+1}a = w_{1}^{(i+1)}w_{2}^{(i+1)} ⋯ w_{k}^{(i+1)}a. For each j, all of the words w_{j}^{(i)} involve the same pair of generators. Setting

a_{0} := a, a_{1} := l[τ(aw_{1}^{0})] and, for each j, a_{j} := l[τ(a_{j−1}w_{j}^{(0)})], we see that

also, for each i < N − s, a_{1} = l[τ(aw_{1}^{(i)})] and, for each j, a_{j} = l[τ(a_{j−1}w_{j}^{(i)})]. For each j with 1 ≤ j ≤ k, we apply Lemma 6.3 below to the sequence w_{j}^{(0)}, w_{j}^{(1)}, …, w_{j}^{(N−s)}, with a := a_{j−1}, b := a_{j}.

If for some j, N − s ≤ |w_{j}^{(i)}|, then certainly N − s ≤ |g_{i}| = |g_{0}|, and so N ≤ |g_{0}| + r + s = |g|. Otherwise Lemma 6.3 ensures that for each i, j, w_{j}^{(i)} = w_{j}^{(i+1)}, and so g_{i} = g_{i+1} = g_{0}; in that case g = aga^{−1} = h. □

Lemma 6.3 Let w = w^{(0)}, w^{(1)}, …, w^{(N)} be a sequence of words in the dihedral Artin group G(m), and let a, b ∈ {x_{1}, x_{2}}^{±1} such that for each i with 0 ≤ i < N, aw^{(i)} is critical and τ(aw^{(i)}) = w^{(i+1)}b. Then either w^{(i)} = w^{(i+1)} for all i or N ≤ |w|/(m − 1).

Proof: Since aw^{(i)} is critical and hence has length at least m, the result is immediate if N ≤ 1. So we assume that N > 1.

We consider the various possibilities for w = w^{(0)}. Without loss of generality we assume that a is a generator, rather than the inverse of one. From the definition of critical words in [7, Section 2], we see that there are two possibilities for aw and τ(aw) where, in both cases, {a, c} = {b, d} = {x_{1}, x_{2}} is the generating set.

Case 1. aw = _{p}(a, c) ξ (b^{−1}, d^{−1})_{n} with p, n > 0 and p + n = m; τ(aw) = n(c^{−1}, a^{−1}) δ(ξ) (d, b)_{p}.

Case 2. aw = _{m}(a, c) ξ with ξ a positive word and l[ξ] = d; τ(aw) = δ(ξ) (d, b)_{m}.

We restrict the possibilities for w by using the fact that pre[τ(aw)] is the maximal suffix of the critical word aw^{(1)}.

Suppose first that we are in Case 1. The fact that aw^{(1)} must start with a positive alternating subword of length p forces p = 1, and so n = m − 1. If ξ is non-empty then, since aw^{(1)} must end with a negative alternating subword of length m−1 that ends in d^{−1}, so must δ(ξ); and so ξ has a suffix equal to δ((b^{−1}, d^{−1})_{m−1}). We factorise ξ as η ∏_{j=0}^{J−1}(δ^{J−j}((b^{−1}, d^{−1})_{m−1})), for some word η, where J > 0 is as large as possible. If ξ is empty then we define η to be the empty word and J = 0.

Then

aw = aη ∏_{j=0}^{J}(δ^{J−j}((b^{−1}, d^{−1})_{m−1}),

aw^{(1)} = a_{m−1}(c^{−1}, a^{−1}) δ(η) ∏_{j=0}^{J−1}(δ^{J−1−j}((b^{−1}, d^{−1})_{m−1}).

If η is empty then, since aw is freely reduced, we see that its second letter must be c^{−1} rather than a^{−1}, and so δ^{J}(b^{−1}, d^{−1})_{m−1}) = _{m−1}(c^{−1}, a^{−1}), and we have aw = aw^{(1)} and then w = w^{(i)} for all i.

Otherwise, we see that

aw^{(J)} = a ∏_{j=0}^{J−1} δ^{j}(_{m−1}(c^{−1}, a^{−1}))δ^{J}(η)((b^{−1}, d^{−1})_{m−1})),

τ(aw^{(J)}) = ∏_{j=0}^{J} δ^{j}(_{m−1}(c^{−1}, a^{−1}))δ^{J+1}(η)b,

aw^{(J+1)} = a ∏_{j=0}^{J} δ^{j}(_{m−1}(c^{−1}, a^{−1}))δ^{J+1}(η).

Now, since we chose J to be maximal, δ^{J+1}(η) does not have an alternating negative subword of length m − 1 as a suffix. So if aw^{(J+1)} had such a suffix, then it would overlap the subword ∏_{j=0}^{J} δ^{j}(_{m−1}(c^{−1}, a^{−1})). But then aw^{(J+1)} would contain an alternating negative subword of length at least m, and would be be non-geodesic. Hence, in this case we see that aw^{(J+1)} is not critical, and the sequence ends with aw^{(J+1)}. So N ≤ J +1 ≤ |w^{(0)}|/(m−1).

Suppose now that we are in Case 2. If ξ is empty then τ(aw) = _{m}(c, a), and w^{(i)} = _{m−1}(c, a) for all i. So we may assume that ξ is non-empty.

We write ξ = ∏_{j=0}^{J−1} δ^{j+1}(_{m−1}(c, a)) η, with J ≥ 0 as large as possible. Then

aw = _{m}(a, c) ∏_{j=0}^{J−1} δ^{j+1}(_{m−1}(c, a)) η,

aw^{(1)} = _{m}(a, c) ∏_{j=0}^{J−2} δ^{j+1}(_{m−1}(c, a)) δ(η) (b, d)_{m−1}.

If η is empty then, since l[w] = l[w^{(1)}] = d, we see that aw = aw^{(1)} and so w = w^{(i)} for all i.

So suppose that η is non-empty. If m is even, then δ(η) = η, so l[δ(η)] = l[η] = d = f[(b, d)_{m−1}]. If m is odd, then l[δ(η)] ≠ l[η], so l[δ(η)] = b = f[(b, d)_{m−1}]. So l[δ(η)] = f[(b, d)_{m−1}] in either case. We have

aw^{(J)} = _{m}(a, c)δ^{J}(η) ∏_{j=1}^{J} δ^{J−j}((b, d)_{m−1}),

τ(aw^{(J)}) = δ^{J+1}(η) ∏_{j=1}^{J} δ^{J+1−j}((b, d)_{m−1})(d, b)_{m},

aw^{(J+1)} = aδ^{J+1}(η) ∏_{j=1}^{J+1} δ^{J+1−j}((b, d)_{m−1}).

Now, since we chose J to be maximal, aδ^{J+1}(η) does not have an alternating postive subword of length m as a prefix and, since l[δ(η)] = f[(b, d)_{m−1}], neither does aw^{(J+1)}. So aw^{(J+1)} is not critical, the sequence ends with aw^{(J+1)}, and again we have N ≤ J + 1 ≤ |w^{(0)}|/(m − 1). □

References

[1] A. V. Aho and M. J. Corasick, Efficient string searching; an aid to bibliographic search, Comm. ACM 18 (1975) 333–340.

[2] K.I.Appel and P.E.Schupp, Artin groups and infinite Coxeter groups. Invent. Math. 72 (1983) 201–220.

[3] K.I. Appel, On Artin groups and Coxeter groups of large type. Contributions to group theory, 5078, Contemp. Math., 33, Amer. Math. Soc., Providence, RI, 1984.

[4] B.S. Boyer and J.S. Moore, A fast string searching algorithm, Comm. ACM 20 (1977) 762–772.

[5] L. Ciobanu, S. Hermiller, D.F. Holt and S. Rees, Conjugacy Languages in Groups, to appear in Israel J. Math.

[6] L. Ciobanu, D.F. Holt and S. Rees, Rapid decay and Baum-Connes for large type Artin groups, to appear in Trans. Amer. Math. Soc.

[7] D.F. Holt and S. Rees, Artin groups of large type are shortlex automatic with regular geodesics, Proc. Lond. Math. Soc. 104 (2012), 486–512.

[8] H. van der Lek, The homotopy type of complex hyperplane complements, PhD Thesis, University of Nijmegen, 1983.

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

[10] J. Mairesse and F. Mathéus, Growth series for Artin groups of dihedral type, Int. J. Alg. Comp. 16 (2006) 1087–1107.

[11] D. Peifer, Artin groups of extra-large type are biautomatic, J. Pure Appl. Alg. 110 (1996) 15–56.

Derek F. Holt Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK. dfh@maths.warwick.ac.uk

Sarah Rees, School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK. Sarah.Rees@ncl.ac.uk