Rapid decay and Baum-Connes for large type Artin groups

Laura Ciobanu, Derek F. Holt and Sarah Rees

Abstract We prove that many Artin groups of large type satisfy the rapid decay property, including all those of extra-large type. For many of these, including all 3-generator groups of extra-large type, a result of Lafforgue applies to show that the groups satisfy the Baum-Connes conjecture without coefficients.

Our proof of rapid decay combines elementary analysis with combinatorial techniques, and relies on properties of geodesic words in Artin groups of large type that were observed in [17] by two of the authors of this current article.

2000 Mathematics Subject Classification: 20E06, 43A15, 46L99.

Key words: rapid decay, Artin groups

1 Introduction

An Artin group G is defined to be a finitely generated group with presentation

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

where the integers m_{ij} are the entries in a Coxeter matrix (a symmetric n × n matrix over ℕ ∪ {∞}, with m_{ii} = 1, and m_{ij} ≥ 2 for all i ≠ j), and, for generators x, y and m ∈ ℕ, the word _{m}(x, y) is defined to be the product of m alternating x’s and y’s that starts with x. The associated Coxeter group is defined by adding the relations x_{i}^{2} = 1 for all i.

A Coxeter matrix can be specified using an undirected labelled graph Γ with n vertices and an edge labelled m_{ij} between distinct vertices i and j whenever m_{ij} < ∞, but no edge between i and j if m_{ij} is infinite. (We note that an alternative and widely used convention deletes instead edges labelled 2 and leaves those with infinite labels.) We denote the Artin group defined in this way by G(Γ).

The Artin group G is said to be of large type if m_{ij} ≥ 3 for all i ≠ j, and of extra-large type if m_{ij} ≥ 4 for all i ≠ j. The concepts of large and extralarge type for Artin groups were introduced by Appel and Schupp [2, 1], who used small cancellation arguments to prove solubility of the word and conjugacy problems, the embedding of parabolic subgroups, the freeness of the subgroups ⟨x_{i}^{2} | 1 ≤ i ≤ n⟩, and more, for these groups. An Artin group is said to be of dihedral type if 2-generated, of spherical type if the associated Coxeter group is finite, or of right-angled type if m_{ij} ∈ {2, ∞} for all i, j.

The purpose of this paper is to prove the following two results.

Theorem 1.1. Let G = G(Γ) be an Artin group of large type for which Γ has no triangles with edge labels 3, 3, m with 3 ≤ m < ∞. Then G satisfies the rapid decay property. In particular, all Artin groups of extra-large type satisfy this property.

Corollary 1.2. Let G = G(Γ) be an Artin group satisfying the hypotheses of Theorem 1.1. Then G satisfies the Baum-Connes conjecture without coefficients whenever one of the following holds.

1. G is 3-generated.

2. Γ is triangle-free.

3. The edges of Γ can be oriented in such a way that the oriented graph contains no subgraph of either of the two types shown.

[figure]

In particular, any large type Artin group G(Γ) for which Γ is triangle-free satisfies the Baum-Connes conjecture without coefficients.

Following Jolissaint [18], we say that a finitely generated group G has the rapid decay property (RD) if the operator norm ||.||_{∗} for the group algebra ℂG is bounded by a constant multiple of the Sobolev norm ||.||_{s,r,ℓ}, a norm that is a variant of the l^{2} norm weighted by a length function for the group.

More precisely, rapid decay holds for G if there are constants C, r and a length function ℓ on G such that for any ϕ, ψ ∈ ℂG,

||ϕ||_{∗} := sup_{ψ∈ℂG} \frac{||ϕ ∗ ψ||_{2}}{||ψ||_{2}} ≤ C||ϕ||_{2,r,ℓ}.

Here, ϕ ∗ ψ denotes the convolution of ϕ and ψ, ||.||_{2} is the standard l^{2} norm, and ||.||_{2,r,ℓ} the Sobolev norm of order r, with respect to the length function ℓ, that is

ϕ ∗ ψ(g) = ∑_{h∈G} ϕ(h)ψ(h^{−1}g),

||ψ||_{2} = \sqrt{∑_{g∈G} |ψ(g)|^{2}}

||ϕ||_{2,r,ℓ} = \sqrt{∑_{g∈G} |ϕ(g)|^{2}(1 + ℓ(g))^{2r}}.

We call a function ℓ : G → ℝ a length function for G if it satisfies

ℓ(1_{G}) = 0, ℓ(g^{−1}) = ℓ(g), ℓ(gh) ≤ ℓ(g) + ℓ(h), ∀g, h ∈ G.

An account of the rapid decay property is given in [8].

The main interest in the rapid decay property for a group G stems from Lafforgue’s result [19] that the combination of rapid decay with an appropriate action of G implies that the Baum-Connes conjecture without coefficients holds for G. That conjecture relates the K-theory of the reduced C^{∗}-algebra C_{r}^{∗}(G) to the K^{G}-homology of the classifying space \underline{E}G for proper G-actions, claiming that the assembly maps

μ_{i}^{G} : RK_{i}^{G}(\underline{E}G) → K_{i}(C_{r}^{∗}(G)), i = 0, 1,

are isomorphisms. This in turn implies the Novikov conjecture and (when G is torsion-free) the Kaplansky-Kadison idempotent conjecture; see [24].

The conjecture as stated above is commonly referred to as the Baum-Connes conjecture ‘without coefficients’ in order to distinguish it from a more general conjecture, with coefficients from a C^{∗}-algebra admitting an action of G, to which counter-examples were claimed in [16].

Braid groups (Artin groups of type A_{n}) are shown to satisfy rapid decay in [5], where the result is proved for mapping class groups; braid groups are proved to satisfy Baum-Connes in [23, Corollary 14]. We note that since Artin groups of type B_{n} and D_{n} are split extensions of free groups by braid groups [11], it follows immediately from [23, Corollary 14] that those spherical type Artin groups also satisfy Baum-Connes (but we do not know if the result holds for the remaining spherical type groups). Right-angled Artin groups are proved to satisfy both rapid decay and Baum-Connes through their action on CAT(0) cube complexes [8]; alternative proofs of their rapid decay follow from their small cancellation properties [22], or the fact that they are graph products of infinite cyclic groups [10]. Dihedral Artin groups are easily proved to satisfy rapid decay since they are virtually direct products of free and cyclic groups. For the same reason they satisfy the Haagerup property (see [9]), which implies Baum-Connes [15]. We are not aware of any other classes of Artin groups known to satisfy either rapid decay or Baum-Connes prior to our results.

We shall call the hypothesis in Theorem 1.1 that there no triangles in Γ with edge labels 3, 3, m the (3, 3, m)-hypothesis. We shall prove rapid decay for Artin groups of large type that satisfy this hypothesis, using as our length function the word length metric over the standard generating set; that is, for each element g we shall define ℓ(g) to be the length of the shortest word over the standard generators that represents g.

Our proof makes critical use of the results and techniques developed in the earlier paper [17] by the second and third authors, in which the sets of geodesics and shortlex minimal geodesics of Artin groups of large type in their standard presentations are studied. It is proved there that those sets of geodesics are regular, and that the groups are shortlex automatic. Furthermore, a method was developed for rewriting arbitary words in the group generators to their shortlex normal forms. In Sections 6 and 7 of this paper, we shall recall some of these results and techniques, and develop them further, proving that certain conditions hold for factorisations of geodesics. In particular, our proof of Theorem 1.1 depends essentially on Proposition 7.5, which turns out to be false in all Artin groups of large type that do not satisfy the (3, 3, m)-hypothesis, so we are currently unable to dispense with this hypothesis.

We shall prove that certain conditions hold for the factorisation of geodesics, and derive rapid decay in groups for which these conditions hold. For many of those groups we can build on work of [6] to construct an action of the group that allows the application of Lafforgue’s result to deduce Baum-Connes.

Our strategy to prove rapid decay by examining the factorisation of geodesics was also used by Jolissaint [18] and de la Harpe [14] to prove rapid decay for word hyperbolic groups, extending Haagerup’s proof for free groups [13]; Drutu and Sapir used similar techniques to prove rapid decay for a group hyperbolic relative to a family of subgroups with the property [12]. Other authors have used more geometric techniques [7, 8].

In Section 2 we explain how Corollary 1.2 can be deduced from Theorem 1.1. Then Section 3 shows how rapid decay can be deduced from a pair of combinatorial conditions D1 and D2 relating to the factorisation of geodesics in the group. Section 5 introduces the notation we need for the remainder of the article. Section 6 examines dihedral Artin groups, first recalling from [17] some technical results on the structure of geodesics, and then using these to deduce the conditions D1 and D2 for these groups. Section 7 extends the results of Section 6 to deduce the same conditions for the large type groups considered in Theorem 1.1.

2 Deducing Baum-Connes from rapid decay

Any discrete group that acts continuously, isometrically, properly and co-compactly on a CAT(0) metric space is in the class C′ defined by Lafforgue in [19]; hence by [19, Corollary 0.4], for such a group the Baum-Connes conjecture is a consequence of rapid decay.

We shall deduce Corollary 1.2 from Theorem 1.1 using results of [6] to construct an appropriate CAT(0) action for a large class of Artin groups of large type.

A CAT(0) space is defined to be a metric space in which distances across a triangle with geodesic sides of lengths p, q, r are always bounded above by distances between equivalent points in a Euclidean triangle with the same side lengths. A space is locally-CAT(0) or equivalently non-positively curved if any point has a neighbourhood that is CAT(0). By the Cartan-Hadamard theorem of [4], a simply connected locally-CAT(0) space is actually CAT(0).

Brady and McCammond define non-positively curved presentation complexes for non-standard presentations of 3-generator Artin groups of large type (and some others) in [6]. We shall see that the actions of the groups on the universal covers of these complexes satisfy the conditions we need.

Theorems 4, 6 and 7 of that paper consider the three cases of our theorem. In each of the three cases we define a complex K_{Γ}, the presentation complex for a presentation I_{Γ} of the Artin group G(Γ) in which all relators have length 3, formed from the standard presentation by the addition of some generators. The presentation complex K_{Γ} has a single 0-cell v_{0}, a 1-cell for each generator of I_{Γ}, and a triangular 2-cell for each relator of I_{Γ}. We define L_{Γ} to be the link of v_{0}; this is the intersection with the surrounding complex of a small sphere centred on v_{0}, and can be viewed as a graph to which each edge of K contributes two vertices, and each corner of a 2-cell contributes an edge. K̃_{Γ} is the universal cover of K_{Γ}; this is simply connected, and also has L_{Γ} as the link of each 0-cell.

In each of the three cases of our theorem, it is proved in [6] that some specification of edge lengths of the triangles which are the 2-cells of K_{Γ} extends to a piecewise Euclidean metric on K_{Γ}; in the first and third cases of the theorem all triangles are made equilateral with side length 1, and in the second case all triangles are made isosceles and right-angled with their shorter sides of length 1. The piecewise Euclidean metric induces a metric on the link L_{Γ} of v_{0}, where the length of each edge is equal to the angle at the corner through v_{0} of the corresponding 2-cell. The metric can also be lifted to the cover K̃_{Γ}.

An action of G by isometries on K̃_{Γ} is inherited from the left regular action of G on its Cayley graph (the 1-skeleton of K̃_{Γ}), in which the vertex h is mapped by g to the vertex gh. The action is free, so clearly it is both proper and continuous. The quotient, K_{Γ}, of K̃_{Γ} by G is certainly compact. In order to apply Lafforgue’s result, we need simply to verify that K̃_{Γ} equipped with this metric is CAT(0).

That K_{Γ} is non-positively curved (locally-CAT(0)) is proved in [6]. In each of the three cases the length of a closed path in the link of a vertex is seen to be at least 2π; hence [3, Theorem 15] applies to show that K_{Γ} is non-positively curved. Exactly the same argument can be applied to the link of a vertex in K̃_{Γ} to deduce that the simply connected cover K̃_{Γ} is also non-positively curved, and hence by the Cartan-Hadamard theorem of [4], K̃_{Γ} is CAT(0). Baum-Connes in each of these cases now follows by [19, Corollary 0.4].

3 Reformulation of the rapid decay condition

Let ℓ be a length function on a group G. Given k ∈ ℕ, we define C_{k} to be the set of elements of G with ℓ(g) = k. We write χ_{k} for the characteristic function on C_{k}, and for ϕ ∈ ℂG, we write ϕ_{k} for the pointwise product ϕ.χ_{k}. (Generally, in this article we use a subscript k to indicate that a function has support on C_{k}.)

It is proved by Jolissaint [18, Proposition 1.2.6] that rapid decay for G is equivalent to the following condition (∗):

∀ϕ, ψ ∈ ℂG, k, l, m ∈ ℕ,
|k − l| ≤ m ≤ k + l, ⇒ ||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} ≤ ||ϕ_{k}||_{2,r,ℓ}||ψ_{l}||_{2},
otherwise  ||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} = 0

We observe that it follows from the properties of a length function that the norm ||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} is zero for m outside the range [|k − l|, k + l]. Hence we shall verify rapid decay by verifying the following condition (∗∗):

there exists a polynomial P (x) such that:

∀ϕ, ψ ∈ ℂG, k, l, m ∈ ℕ,

|k − l| ≤ m ≤ k + l, ⇒ ||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} ≤ P (k)||ϕ_{k}||_{2}||ψ_{l}||_{2}.

We can clearly assume that the coefficients of such a polynomial P are nonnegative, and hence that P is an increasing function of x, and we shall assume throughout this paper that all polynomials that arise have this property.

4 Geodesic factorisation

For g ∈ G we call a decomposition of g as a product g_{1} ⋯ g_{k} a geodesic factorisation of g if ∑ ℓ(g_{i}) = ℓ(g), and call the elements g_{i} divisors of g. In particular g_{1} is called a left divisor and g_{k} is called a right divisor. Given g ∈ C_{k+l} we define

Fact_{k,l}(g) := {(g_{1}, g_{2}) : g_{1} ∈ C_{k}, g_{2} ∈ C_{l} : g_{1}g_{2} =_{G} g}
F_{k,l} := sup_{g∈C_{k+l}} |Fact_{k,l}(g)|

Let P be a subset of G^{2} and, for g ∈ G, let P(g) = {(g_{1}, g_{2}) ∈ P : g_{1}g_{2} = g}. We shall refer to the factorisations of g in P(g) as the permissible factorisations of g. We define

Fact_{P,k,l}(g) := {(g_{1}, g_{2}) : g_{1} ∈ C_{k}, g_{2} ∈ C_{l}, (g_{1}, g_{2}) ∈ P(g)}
F_{P,k,l} := sup_{g∈C_{k+l}} |Fact_{P,k,l}(g)|

We shall verify the condition (∗∗) above for Artin groups satisfying the hypotheses of Theorem 1.1, and hence verify rapid decay, by finding a suitable set P of permissible factorisations for which the size of both Fact_{P,k,l}(g) and a related set are polynomially bounded.

We define two conditions D1, D2 that we shall require to hold on a suitable subset P of G^{2}.

D1 F_{P,k,l} is bounded above by P_{1}(min(k, l)) for some polynomial P_{1}(x).

D2 For each g ∈ G, each k, l ≥ 0, there is a subset S(g, k, l) of G^{3} as follows.

For each decomposition of g as a product g_{1}g_{2} with g_{1} ∈ C_{k}, g_{2} ∈ C_{l}, S(g, k, l) contains a triple (f_{1}, ĝ, f_{2}), for which g = f_{1}ĝf_{2}, and ĝ = h_{1}h_{2}, where (f_{1}, h_{1}) ∈ Fact_{P,k−p_{1},p_{1}}(g_{1}) and (h_{2}, f_{2}) ∈ Fact_{P,p_{2},l−p_{2}}(g_{2}), for some p_{1}, p_{2} ≤ K min(k, l), for some global constant K.

Furthermore, there are polynomials P_{2}(x), P_{3}(x) such that

(a) for all g, k, l, |S(g, k, l)| ≤ P_{2}(min(k, l)),

(b) |T (k, l)| ≤ P_{3}(min(k, l)), where T (k, l) := {ĝ : ∃g, (f_{1}, ĝ, f_{2}) ∈ S(g, k, l)}.

Figure 1 illustrates the condition D2.

Theorem 4.1. Let G be a group and P a subset of G^{2} for which the conditions D1 and D2 hold. Then G satisfies rapid decay with respect to the word length metric.

Before launching into the proof of Theorem 4.1 we prove a few technical results. Suppose first that ϕ_{k} is a function with support on C_{k}. Then for any p ≥ 0, we can define functions ϕ_{P,k−p}^{(p)} and ^{(p)}ϕ_{P,k−p} with support on C_{k−p} by

ϕ_{P,k−p}^{(p)}(g) = \sqrt{∑_{h∈C_{p},(g,h)∈P} |ϕ_{k}(gh)|^{2}}, if g ∈ C_{k−p}
= 0 otherwise
(p)ϕ_{P,k−p}(g) = \sqrt{∑_{h∈C_{p},(h,g)∈P} |ϕ_{k}(hg)|^{2}}, if g ∈ C_{k−p}
= 0 otherwise.

[figure: g; g_{1}; g_{2}; f_{1}; f_{2}; ĝ; h_{1}; h_{2}]

Figure 1: Condition D2

Lemma 4.2.

||ϕ_{P,k−p}^{(p)}||_{2}^{2} ≤ F_{P,k−p,p}||ϕ_{k}||_{2}^{2}
||^{(p)}ϕ_{P,k−p}||_{2}^{2} ≤ F_{P,p,k−p}||ϕ_{k}||_{2}^{2}

Proof.

||ϕ_{P,k−p}^{(p)}||_{2}^{2} = ∑_{g∈C_{k−p}} ∑_{h∈C_{p},(g,h)∈P} |ϕ_{k}(gh)|^{2}
≤ F_{P,k−p,p} ∑_{g_{1}∈C_{k}} |ϕ_{k}(g_{1})|^{2}
= F_{P,k−p,p}||ϕ_{k}||_{2}^{2}

The second inequality follows similarly.

We shall make frequent use of the following, which is an easy application of the Cauchy-Schwarz inequality.

Lemma 4.3. For a_{i} ∈ ℂ, n ∈ ℕ,

| ∑_{i=1}^{n} a_{i}|^{2} ≤ n ∑_{i=1}^{n} |a_{i}|^{2}

We are now ready to prove the theorem. Proof of Theorem 4.1: Suppose that D1 and D2 hold, and let K, P_{1}(x), P_{2}(x), P_{3}(x) and the sets P, S(g, k, l) and T (k, l) be as specified by those conditions.

Choose k, l, m such that |k − l| ≤ m ≤ k + l, and define k̂ := min(k, l). Let g ∈ G with ℓ(g) = m. Then

|(ϕ_{k} ∗ ψ_{l})(g)| = | ∑_{\begin{matrix}g_{1} ∈ C_{k}, g_{2} ∈ C_{l} \\ g = g_{1}g_{2} \end{matrix}} ϕ_{k}(g_{1})ψ_{l}(g_{2})| ≤ ∑_{\begin{matrix}g_{1} ∈ C_{k}, g_{2} ∈ C_{l} \\ g = g_{1}g_{2} \end{matrix}} |ϕ_{k}(g_{1})ψ_{l}(g_{2})|

Now the condition D2 defines an injection from Fact_{k,l}(g) to G^{5} ×ℕ^{2} that maps (g_{1}, g_{2}) to (f_{1}, ĝ, f_{2}, h_{1}, h_{2}, p_{1}, p_{2}), where h_{1} ∈ C_{p_{1}}, h_{2} ∈ C_{p_{2}}, (f_{1}, h_{1}), (h_{2}, f_{2}) ∈ P and h_{1}h_{2} = ĝ. We define

H(f_{1}, ĝ, f_{2}, p_{1}, p_{2}) := {h_{1} ∈ C_{p_{1}} : h_{2} := h_{1}^{−1}ĝ ∈ C_{p_{2}}, (f_{1}, h_{1}), (h_{2}, f_{2}) ∈ P}.

So the right hand side of the above inequality is bounded above by:

∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} ∑_{\begin{matrix}h_{1} ∈ H(f_{1}, ĝ, f_{2}, p_{1}, p_{2}) \\ h_{2} := h_{1}^{−1}ĝ \end{matrix}} |ϕ_{k}(f_{1}h_{1})ψ_{l}(h_{2}f_{2})|

Note that this summation is over a set that is possibly larger than the image of that injection, and hence we have an upper bound rather than equality.

Now by the Cauchy-Schwartz inequality, this sum is at most

∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} \sqrt{∑_{\begin{matrix}h_{1} ∈ C_{p_{1}} \\ (f_{1}, h_{1}) ∈ P \end{matrix}} |ϕ_{k}(f_{1}h_{1})|^{2}}\sqrt{∑_{\begin{matrix}h_{2} ∈ C_{p_{2}} \\ (h_{2}, f_{2}) ∈ P \end{matrix}} |ψ_{l}(h_{2}f_{2})|^{2}}

= ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})

where ϕ_{P,k−p}^{(p)} and ^{(p)}ψ_{P,l−p} are as defined above.

So now, we have

||(ϕ_{k} ∗ ψ_{l})_{m}||_{2}^{2} = ∑_{g∈C_{m}} |ϕ_{k} ∗ ψ_{l}(g)|^{2}

≤ ∑_{g∈C_{m}} | ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2}

Using Lemma 4.3 twice we see that

∑_{g∈C_{m}} | ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2}

≤ (Kk̂ + 1)^{2} ∑_{g∈C_{m}} ∑_{p_{1},p_{2}=0}^{Kk̂} | ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2}

≤ (Kk̂ + 1)^{2} ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{g∈C_{m}} |S(g, k, l)| ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} |ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2}

≤ (Kk̂ + 1)^{2}P_{2}(k̂) ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{g∈C_{m}} ∑_{(f_{1},ĝ,f_{2})∈S(g,k,l)} |ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1}) ^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2}

The last sum is bounded above by

(Kk̂+1)^{2}P_{2}(k̂) ∑_{p_{1},p_{2}=0}^{Kk̂} ∑_{ĝ∈T (k,l)} ( ∑_{f_{1}∈C_{k−p_{1}}} |ϕ_{P,k−p_{1}}^{(p_{1})}(f_{1})|^{2} ∑_{f_{2}∈C_{l−p_{2}}} |^{(p_{2})}ψ_{P,l−p_{2}}(f_{2})|^{2})

which is a sum of the same terms but over a possibly larger set. We bound the last sum above by

(Kk̂ + 1)^{2}P_{2}(k̂)P_{3}(k̂) ∑_{p_{1},p_{2}=0}^{Kk̂} |ϕ_{P,k−p_{1}}^{(p_{1})}||_{2}^{2}||^{(p_{2})}ψ_{P,l−p_{2}}||_{2}^{2}

≤ (Kk̂ + 1)^{2}P_{2}(k̂)P_{3}(k̂) ∑_{p_{1},p_{2}=0}^{Kk̂} F_{P,k−p_{1},p_{1}}F_{P,p_{2},l−p_{2}}||ϕ_{k}||_{2}^{2}||ψ_{l}||_{2}^{2}

≤ (Kk̂ + 1)^{2}P_{2}(k̂)P_{3}(k̂) ∑_{p_{1},p_{2}=0}^{Kk̂} P_{1}(min(k − p_{1}, p_{1}))P_{1}(min(p_{2}, l − p_{2}))||ϕ_{k}||_{2}^{2}||ψ_{l}||_{2}^{2},

using Lemma 4.2 to relate the l^{2}-norms. Since min(k−p_{1}, p_{1}) and min(p_{2}, l−p_{2}) above are bounded by Kk̂, condition (∗∗) now follows easily. □

5 Notation for Artin groups

Our Artin groups will be defined in their standard presentations

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

We prove rapid decay for Artin groups satisfying the hypotheses of Theorem 1.1 with respect to the word length metric, by verifying the conditions D1 and D2 above. In order to do that we need to examine the structure of geodesics in these groups; we build on the results of [17].

Given an Artin group G as before we let X be the set of generators in the standard presentation and let A be the set X ∪ X^{−1}; we call the elements of A letters. We shall generally use symbols like x, y, z, t for generators in X and a, b for letters in A. A letter is positive if it is a generator, negative otherwise. For each x ∈ X, we define x to be the name of the two letters x and x^{−1}. We say that a word w ∈ A^{∗} involves the generator x if w contains a letter with name x, and we call w a 2-generator word if it involves exactly two of the generators. Words in A^{∗} will be denoted by u, v, w (possibly with subscripts) or α, β, γ, η, ξ. (Roughly speaking, the difference is that u, v, w will be used for interesting subwords of a specified word, and the Greek letters for subwords in which we are not interested.) A positive word is one in X^{∗} and a negative word one in (X^{−1})^{∗}; otherwise it is unsigned. For u, v ∈ A^{∗}, u = v denotes equality as words, whereas u =_{G} v denotes equality within the Artin group. The length of the word w is denoted by |w|, while as above |w|_{G} denotes the length of a geodesic representative and, for g ∈ G, |g| denotes the length of a geodesic word representing g. A syllable in a word is a subword that is a power of a single generator, and is not a subword of a higher power.

For any distinct letters a and b and a positive integer r, we define alternating products_{r}(a, b) and (b, a)_{r}. The product_{r}(a, b), is defined, as it was earlier (over generators), to be the word of length r of alternating a’s and b’s starting with a, while (b, a)_{r} is defined to be the word of length r of alternating a’s and b’s ending with a. For example, _{6}(a, b) = ababab = (a, b)_{6}, _{5}(a, b) = ababa = (b, a)_{5}. We define both _{0}(a, b) and (b, a)_{0} to be the empty word. For any nonempty word w, we define f[w] and l[w] to be respectively the first and last letter of w, and pre[w] and suf[w] to be the maximal proper prefix and suffix of w. So w = pre[w]l[w] = f[w]suf[w].

6 Dihedral Artin groups

In this section, we prove that dihedral Artin groups of large type satisfy RD by verifying the properties D1 and D2 in these groups. As mentioned in the introduction, the fact that these groups satisfy RD can be deduced immediately from results already in the literature, but the techniques that we develop here are needed in the proof of Theorem 1.1 in Section 7.

6.1 The structure of geodesics in dihedral Artin groups

We need some results on the structure of geodesics from [21, 17]. We summarise what we need, and refer to those articles for details.

Let

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

be a 2-generator (dihedral) Artin group with 2 ≤ m < ∞. Conjugation by the Garside element

Δ := _{m}(x_{1}, x_{2}) =_{DA(m)} _{m}(x_{2}, x_{1})

induces a permutation δ of order 2 or 1 (depending on the parity of m) on the letters in A, and hence an automorphism δ of order 2 or 1 of the free monoid A^{∗}.

Let w be a freely reduced word over A = {x_{1}, x_{2}, x_{1}^{−1}, x_{2}^{−1}}. 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. It is proved in [21, Proposition 4.3] that w is geodesic in DA(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. Note that a non-geodesic word is always unsigned.

For example, suppose that m = 3, so DA(m) = ⟨x_{1}, x_{2} | x_{1}x_{2}x_{1} = x_{2}x_{1}x_{2}⟩. Then w := x_{1}x_{2}x_{1} and w′ := x_{2}x_{1}x_{2} are two geodesic representatives of the same element with p(w) = p(w′) = 3, n(w) = n(w′) = 0, and w = x_{1}x_{2}^{2}x_{1}^{−1} and w′ = x_{2}^{−1}x_{1}^{2}x_{2} are two geodesic representatives of the same element with p(w) = p(w′) = 2, n(w) = n(w′) = 1. In fact all four words are examples of critical words, as defined in [17].

As in [17], we define a freely reduced word w with p(w) + n(w) = m to be critical if one of the following holds, where ξ is a subword with the obvious restrictions.

(i) w is unsigned of one of the two forms_{p}(x, y)ξ(z^{−1}, t^{−1})_{n} or_{n}(x^{−1}, y^{−1})ξ(z, t)_{p}, with {x, y} = {z, t} = {x_{1}, x_{2}},

(ii) w is positive of one of the two forms _{m}(x, y)ξ or ξ(x, y)_{m}, and only the one positive alternating subword of length m,

(iii) w is negative of one of the two forms _{m}(x^{−1}, y^{−1})ξ or ξ(x^{−1}, y^{−1})_{m}, and only the one negative alternating subword of length m.

An involution τ on the set of critical words swaps critical words that represent the same element. We define τ by

p(x, y) ξ (z^{−1}, t^{−1})_{n} ↔^{τ} _{n}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{p},
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},
m(x^{−1}, y^{−1}) ξ ↔^{τ} δ(ξ) (z^{−1}, t^{−1})_{m}, where z = l[ξ]^{−1}, {x, y} = {z, t}.

Where a critical word w′ occurs as a subword of a word w, we call the substitution of the subword w′ by τ(w′) a τ-move on w.

The following lemma is proved in [17, Lemma 2.3].

Lemma 6.1. Suppose that w ∈ A^{∗} is geodesic and a ∈ A. If wa is non-geodesic, then either l[w] = a^{−1} or w has a critical suffix v such that l[τ(v)] = a^{−1}. Similarly, if aw is non-geodesic, then either f[w] = a^{−1} or w has a critical prefix v such that f[τ(v)] = a^{−1}.

It is proved in [17] that, whenever w is a freely reduced word that is not minimal under the shortlex ordering, w has a factorisation as w_{1}w_{2}w_{3}, where w_{2} is critical and either w_{1}τ(w_{2})w_{3} <_{lex} w or w_{1}τ(w_{2})w_{3} is not freely reduced. In that case, we call the τ-move on w that replaces w_{2} by τ(w_{2}) together with any subsequent free reduction within w_{1}τ(w_{2})w_{3} a critical reduction of w. It follows from [17, Theorem 2.4] that a succession of critical reductions reduces any word to its shortlex minimal representative. Further, any two geodesic representatives are related by a sequence of τ-moves. In particular this implies that two representatives of the same group element must either both be signed or both unsigned.

In order to deal with the reduction of non-geodesic words, we extend the concept of τ-moves.

A freely reduced subword u of a word w is said to be over-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, n ≤ m, p + n > m and {x, y} = {z, t} = {x_{1}, x_{2}}, and the extra condition that, if p < m, then _{p}(x, y) or (z, t)_{p} is a maximal positive alternating subword of w and if n < m then (z^{−1}, t^{−1})_{n} or_{n}(x^{−1}, y^{−1}) is a maximal negative alternating subword of w.

Note that we do not require that p = p(w) or n = n(w). But since the conditions on p, n force p(w) + n(w) > m, over-critical words are necessarily non-geodesic.

We define τ on over-critical words by

τ(_{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}.

We refer to these as length reducing τ-moves. Note that any such move can also be achieved by an ordinary τ-move followed by free reduction. So it follows from Lemma 6.1 that any word can be reduced to a geodesic by a sequence of length reducing τ-moves and free reduction. We call the move positive if p = m, negative if n = m and unsigned otherwise. (So if p = n = m it is both positive and negative, but we won’t need to use that case.)

Lemma 6.2. Let w be freely reduced with 0 < p(w), n(w) < m. Then w can be reduced to a geodesic using a sequence of unsigned length reducing τ-moves alone (i.e. with no free reduction).

Proof. This follows from lemma 6.1 together with the fact that applying an unsigned length reducing τ-move to w results in a freely reduced word, and does not increase p(w) or n(w).

We shall also need the following lemma when we come to verify D2 for Artin groups of extra large type.

Lemma 6.3. Let g, h ∈ DA(m). If gh ∈ ⟨x_{i}⟩, then g and h have geodesic factorisations x_{i}^{s}w and w^{−1}x_{i}^{t}, for some element w and integers s, t.

Proof. The result is trivial if either g or h (and hence both) is in ⟨x_{i}⟩, so we suppose not.

Suppose that g = a^{k}h^{−1} with a = x_{i}^{±1} and k ≥ 0. Suppose first that |ah^{−1}| = 1 + |h|. Then |g| = k + |h| and the result is clear. Otherwise, by Lemma 6.1, a^{−1} is a left divisor of h^{−1}. Let l be maximal such that a^{−l} is a left divisor of h^{−1}, and let h^{−1} = a^{−l}w. Then a^{k−l}w is a geodesic factorisation of g, and the result follows.

6.2 Verifying D1 and D2 for dihedral Artin groups

Our aim in this section is to verify that the properties D1 and D2 hold in any dihedral Artin group G. In fact, it can be shown that the kernel of the natural homomorphism of DA(m) onto the dihedral group of order 2m in which the images of x_{1} and x_{2} have order 2 is a direct product of an infinite cyclic group and a free group of rank m − 1. The fact that DA(m) has rapid decay then follows from [18, Propositions 2.1.5, 2.1.9], so we do not need to verify D1 and D2 in order to prove rapid decay in these groups. However we need the properties here in order to prove that corresponding properties hold for Artin groups satisfying the hypotheses of Theorem 1.1.

We shall assume throughout this section that m ≥ 3. We assume also that k ≤ l, and deduce D1 and D2 in that case; the case k ≥ l then follows immediately by symmetry.

We first need to define our set P of permissible geodesic factorisations of elements g ∈ G. For unsigned elements g, we define P(g) to be the set all geodesic factorisations of g; that is,

P(g) := {(g_{1}, g_{2}) ∈ G^{2} : g_{1}g_{2} = g, |g_{1}| + |g_{2}| = |g|}.

If m is infinite (that is, the 2-generator group is free) then for any element g we define P(g) to be its set of geodesic factorisations. From now on we shall assume that m < ∞.

Unfortunately, for m < ∞, if we adopt the above definition of P(g) for signed elements g, then D1 does not hold, so we are forced to use a more restrictive definition, which significantly increases the technical complications in the proofs.

For a positive (respectively negative) element g, we define d(g) to be the maximal k such that Δ^{k} (respectively Δ^{−k}) is a divisor of g. Then we call a geodesic factorisation g_{1}g_{2} = g of g Δ-decreasing if d(g_{1}) + d(g_{2}) < d(g). We define P(g) := P^{1}(g) ∪ P^{2}(g), where P^{1}(g) is the set of factorisations g_{1}g_{2} for which at least one of g_{1}, g_{2} is represented by geodesic words with at most two syllables (i.e. either g_{1} or g_{2} equals a^{s}b^{t} with a, b ∈ A, s, t ≥ 0), and P^{2}(g) is the set of geodesic factorisations of g that are not Δ-decreasing. That is,

P^{2}(g) := {(g_{1}, g_{2}) ∈ G^{2} : g_{1}g_{2} = g, |g_{1}| + |g_{2}| = |g|, d(g_{1}) + d(g_{2}) = d(g)}.

(In fact we could omit the factorisations in P^{1} and still obtain D1 and D2 in the dihedral case, but we will need them in the next section in order to prove the conditions when there are more than two generators; that proof is easier if we include those factorisations already for the dihedral case.) We say that a left (respectively right) divisor h of g lies in P_{l}^{i}(g) (respectively P_{r}^{i}(g)) for i = 1 or 2 if (h, h^{−1}g) ∈ P^{i}(g) (respectively (gh^{−1}, h) ∈ P^{i}(g)), and let P_{l}(g) := P_{l}^{1}(g) ∪ P_{l}^{2}(g) and P_{r}(g) := P_{r}^{1}(g) ∪ P_{r}^{2}(g).

Our first aim is to prove Property D1. In order to do that we need to examine the set of geodesic words representing a given element. Let w be a geodesic word with p(w) + n(w) = m; we write p := p(w), n := n(w). We have seen that w can be reduced to its shortlex normal form by a sequence of lex-reducing critical reductions. It follows that if w′ is another geodesic word with w =_{G} w′, then w can be transformed to w′ by a sequence of τ-moves.

First suppose that p, n > 0. The word w has the form η_{0}w_{1}η_{1} ⋯ w_{s}η_{s}, where each w_{i} has the form (x, y)_{p} or (x^{−1}, y^{−1})_{m} with {x, y} = {x_{1}, x_{2}}, and p(η_{i}) < p, m(η_{i}) < m for all i. A τ-move has the effect of changing the signs of w_{i}, w_{j} for some i < j for which w_{i}, w_{j} have opposite signs, and replacing the subword between them by its image under δ. Denote this τ-move by (i, j). So w′ = η′_{0}w′_{1}η′_{1} ⋯ w′_{s}η′_{s}, where each η′_{r} = η_{r} or δ(η_{r}), and all of the subwords w_{r}, w′_{r} are maximal alternating. But note that although |η′_{r}| = |η_{r}|, it is not necessarily true that |w_{r}| = |w′_{r}|.

Lemma 6.4. Let w, w′ be geodesic words as above. If, for some r with 1 ≤ r ≤ s, the number of positive w_{i} with 1 ≤ i ≤ r is equal to the number of positive w′_{i} with 1 ≤ r ≤ s, then η′_{0}w′_{1}η′_{1} ⋯ w′_{r} =_{G} η_{0}w_{1}η_{1} ⋯ w_{r} and η_{r} = η′_{r}.

Proof. This is by induction on r. Since none of the τ-moves changes η_{0}, we have η_{0} = η′_{0}, and so the result is true for r = 0.

So suppose that r ≥ 1. Since w_{1} can only be changed by a transformation (1, i) with 1 < i, there are only two possible w′_{1}, one of which is w_{1} and the other a word of opposite sign to w_{1}. So if Sign(w_{1}) = Sign(w′_{1}), then w_{1} = w′_{1} and the result follows by induction. Otherwise, we have {w_{1}, w′_{1}} = {_{p}(x, y), _{m}(y^{−1}, x^{−1})}. From the hypothesis, there must be both positive and negative w_{i} with i ≤ r, so there is a w′_{i} with 2 ≤ i ≤ r and Sign(w′_{i}) = −Sign(w′_{1}). We can do the move (1, i) to w′ giving w′′. Such a move does not change the group element η′_{0}w′_{1}η′_{1} ⋯ w′_{r} or η′_{r}, but it does change w′_{1} back to w_{1}, so the result follows by induction applied to w, w′′.

For a positive element g (the negative case is similar), let r = d(g). Then, for a geodesic factorisation g = g_{1}g_{2} in P^{2}(g), we have d(g_{1}) = s and d(g_{2}) = r − s for some 0 ≤ s ≤ r, and then g_{1} has Δ^{s} as a left divisor and g_{2} has Δ^{r−s} as a right divisor.

Lemma 6.5. Let w, w′ be positive geodesic words representing g ∈ G such that w and w′ both have Δ^{s} as a prefix and Δ^{r−s} as suffix for some s, where r = d(g). Then w = w′.

Proof. We have w = Δ^{s}ηΔ^{r−s}, w′ = Δ^{s}η′Δ^{r−s} with η =_{G} η′. Since d(g) = r, we have d(η) = d(η′) = 0 so by [21, Proposition 4.3] η_{G} has a unique geodesic representative, and hence η = η′ and w = w′.

Lemma 6.6. Let g ∈ G be a positive element and let l ≥ 0. Then, for a, b ∈ A with {a, b} = {x_{1}, x_{2}}, the number of right divisors of g of the form a^{s}b^{t} with s + t = l is at most d(g) + 1.

Proof. The proof is by induction on l, the case l = 0 being trivial. We may suppose that a^{l} is a right divisor of g, since otherwise all right divisors of g of the required form end in b, and the result follows from the case l − 1 applied to gb^{−1}. Similarly, we may assume that b^{l} is a right divisor of g, since otherwise the suffixes of the required form all begin with a, and the result follows from the case l − 1 applied to g.

Let d = d(g). We may assume that d > 0, since otherwise g has a unique geodesic representative. It is straightforward to prove by induction on t that, for any t > 0, the group element g_{a,t} := Δ^{t}a^{−t} is positive with d(g_{a,t}) = 0 and l[g_{a,t}] = b (that is, the unique geodesic representative ends in b); in fact the unique geodesic representative is a concatenation of positive alternating words each of length m − 1. Similarly g_{b,t} = Δ^{t}b^{−t} has d(g_{b,t}) = 0 with l[g_{b,t}] = a and, since g_{b,t} is obtained from g_{a,t} by interchanging a and b, we have f[g_{a,t}] ≠ f[g_{b,t}]. We write g = g′Δ^{d} with d(g′) = 0, and observe that the element g′g_{a,d} = ga^{−d} is divisible by Δ if and only if g′ ends in a positive letter other than f[g_{a,t}], and similarly for the element g′g_{b,d} = gb^{−d}; hence exactly one of the two group elements g′g_{a,d} and g′g_{b,d} is not divisible by Δ. If g′g_{a,d} = ga^{−d} is not divisible by Δ, then its unique geodesic representative ends in l[g_{a,d}] = b; ga^{−d} cannot have a as a right divisor, and g cannot have a^{d+1} as a right divisor; Similarly we see that if g′g_{b,d} is not divisible by Δ, then g cannot have b^{d+1} as a right divisor. Hence g cannot have both a^{d+1} and b^{d+1} as right divisors. It now follows from the preceding paragraph that l ≤ d, and then the result follows immediately, by counting the number of pairs (s, t) with s + t = l.

We can now prove D1, which we can express as follows:

Corollary 6.7. There is a polynomial P (x) with the following property: for any g ∈ G the number of left divisors of g of length k in P_{l}(g) is bounded above by P (k).

Proof. Suppose that g ∈ G has length k + l. We need to bound the number of group elements u_{G} for which w = uv is a geodesic word representing g, with |u| = k, |v| = l and (u_{G}, v_{G}) ∈ P.

First suppose that w = uv is unsigned, of the form η_{0}w_{1}η_{1} ⋯ w_{s}η_{s}, as above. If one of the subwords w_{i} of w intersects both u and v, then let u_{1} be the prefix of w that ends at the end of w_{i}; otherwise let u_{1} = u.

Suppose that u_{1} contains r_{p} positive subwords w_{i} and r_{n} negative subwords w_{i}. The group element (u_{1})_{G} is determined by those two parameters by Lemma 6.4. Since each of r_{p}, r_{n} must be in the range [0, k], there are at most k^{2} choices for (u_{1})_{G} corresponding to unsigned geodesics w. Since u differs from u_{1} by an alternating subword of length less than m (and there are less than 4m such words), there are at most 4mk^{2} choices for u_{G} that correspond to unsigned geodesic representatives w.

Now suppose that w = uv is signed. Suppose first that (u, v) ∈ P^{1}, so that either u or v has at most 2 syllables. There are at most 2(k + 1) possible words u with at most two syllables. By Lemma 6.6, there are at most 2(d(g) + 1) possible words v with at most two syllables. If the signed element g has the geodesic factorisation g = g′a^{s}b^{t} then, by collecting powers of Δ that divide g to the left, we see that at least m − 2 of the letters in each occurrence of Δ in g must come from g′, and hence |g′| ≥ (m − 2)d(g) ≥ d(g). So, if there are factorisations in which v has two syllables, then k ≥ d(g). So there are at most 4(k + 1) such pairs (u, v).

Now assume that (u, v) ∈ P^{2}. Then u =_{G} Δ^{s}u′ and v =_{G} v′Δ^{d(g)−s} for some s, where u′v′ is not divisible by δ, and by Lemma 6.5 u′v′ is completely determined by g, s. Further u′v′ is the unique geodesic representative of (u′v′)_{G}. Hence (given g, k), (u_{G}) is completely determined by s ∈ [0, k]. The number of such factorisations is therefore at most k + 1.

In order to verify the condition D2, we first describe a process that we call merging, which we can use to define the set S(g, k, l) that appears in that condition.

Given elements g_{1}, g_{2} of length k, l whose product g has length less than k + l, an application of the merging process results in a triple (f_{1}, Δ^{r}, f_{2}) of elements, such that for some h_{1}, h_{2} with h_{1}h_{2} =_{G} Δ^{r}, f_{1}h_{1} and h_{2}f_{2} are geodesic factorisations of g_{1}, g_{2}, respectively, and furthermore (f_{1}, h_{1}), (h_{2}, f_{2}) ∈ P. We call such a triple a merger of g_{1} and g_{2}; we do not claim or need g_{1}, g_{2} to have a unique merger (although we suspect that it does). Then we define the set S(g, k, l) to be the set of all triples (f_{1}, Δ^{r}, f_{2}) that arise as mergers of pairs of elements g_{1}, g_{2} of lengths k, l and with g_{1}g_{2} =_{G} g.

We compute a merger of (g_{1}, g_{2}) as the last term of a sequence of triples (g_{1}^{(t)}, Δ^{r_{t}}, g_{2}^{(t)}), defined as follows. When one or both of g_{1}, g_{2} is a signed word, we have to be careful to ensure that the resulting geodesic factorisations of g_{1} and g_{2} lie in P. We set g_{1}^{(1)} := g_{1}, r_{1} := 0, g_{2}^{(1)} := g_{2}.

Now, the t-th step of the merging process computes g_{1}^{(t+1)}, r_{t+1}, g_{2}^{(t+1)} as follows. In each of the three situations below, we choose non-identity group elements h, h′, and then define g_{1}^{(t+1)} := g_{1}^{(t)}h^{−1} and g_{2}^{(t+1)} := h^{′−1}g_{2}^{(t)} such that g_{1}^{(t+1)}h and h′g_{2}^{(t+1)} are geodesic factorisations of g_{1}^{(t)} and g_{2}^{(t)} respectively, with g_{1}^{(t+1)} ∈ P_{l}(g_{1}) and g_{2}^{(t+1)} ∈ P_{r}(g_{2}).

(i) If we can choose h, h′ with hδ^{r_{t}}(h′) = 1, then we do so with h, h′ as long as possible, and put r_{t+1} := r_{t} (we call this a cancellation move).

(ii) Otherwise, if g_{1}^{(t)} and g_{2}^{(t)} are both signed words, and we can choose

h = h′ = Δ^{ϵ} with ϵ = ±1, then do so, and put r_{t+1} := r_{t} + 2ϵ. (iii) Otherwise, if we can choose h, h′ with hδ^{r_{t}}(h′) = Δ^{ϵ} with ϵ = ±1, then

do so and put r_{t+1} := r_{t} + ϵ (we call this a Δ-extraction move).

If for some t, no pair of elements h, h′ satisfy any of these three conditions, then merging is complete, and we output (f_{1}, Δ^{r}, f_{2}) := (g_{1}^{(t)}, Δ^{r_{t}}, g_{2}^{(t)}) as a merger of (g_{1}, g_{2}). Note that we needed the conditions at each previous step that g_{1}^{(t+1)} ∈ P_{l}(g_{1}) and g_{2}^{(t+1)} ∈ P_{r}(g_{2}) to ensure that (f_{1}, Δ^{r}, f_{2}) possesses all the required properties of a merger of (g_{1}, g_{2}).

Lemma 6.8. Suppose that g_{1}, g_{2} are elements of length k, l respectively, where k ≤ l, and that (f_{1}, Δ^{r}, f_{2}) is a merger of (g_{1}, g_{2}); Let h_{1} := f_{1}^{−1}g_{1} and h_{2} := g_{2}f_{2}^{−1}. Then r ≤ k and |h_{1}|, |h_{2}| ≤ (m − 1)k.

Proof. It is clear that the process above completes in at most k stages, giving the required bound on r. At each stage of the merging process, the ratio of the lengths of the elements h, h′, stripped from g_{1}^{(t)} and g_{2}^{(t)} to give g_{1}^{(t+1)} and g_{2}^{(t+1)}, is in the interval [1/(m − 1), m − 1]. Hence the same is true for the total lengths of elements stripped off, that is, 1/(m − 1) ≤ |h_{1}|/|h_{2}| ≤ m − 1. Since |h_{1}| ≤ |g_{1}| = k and h_{2} ≤ |g_{2}| = l, we get |h_{1}|, |h_{2}| ≤ (m − 1)k, as claimed.

The definition of the merging process ensures that, for a merger (f_{1}, Δ^{r}, f_{2}) of (g_{1}, g_{2}), we have (f_{1}, h_{1}), (h_{2}, f_{2}) ∈ P. So, in order to verify that D2 holds, we just need to find polynomial bounds on S(g, k, l) and the associated set T (k, l) of powers of Δ, and a value for the constant K.

The above lemma already bounds |T (k, l)| by 2k + 1 and K by m − 1, so it remains to find a polynomial bound on S(g, k, l). In order to do this we need to explore a reduction process, which we call compression, that starts with a triple (f_{1}, Δ^{r}, f_{2}) ∈ S(g, k, l) and produces a geodesic representative of g. Reversing the compression process will then enable us to estimate the size of S(g, k, l).

So suppose that (f_{1}, Δ^{r}, f_{2}) ∈ S(g, k, l). The fact that the merging process has completed at (f_{1}, Δ^{r}, f_{2}) ensures that f_{1}, f_{2} cannot both have powers of Δ as divisors and that, if one of the two elements has such a divisor Δ^{r_{0}} and r, r_{0} ≠ 0, then r, r_{0} cannot have opposite signs. Hence we see that f_{1}, f_{2} have geodesic representatives of the form uΔ^{r_{0}}, v or u, Δ^{r_{0}}v for some r_{0} (possibly zero), where u, v are not divisible by Δ^{±1}. Then g_{1}Δ^{r}g_{2} is represented by uΔ^{r_{1}}v =_{G} uδ^{r_{1}}(v)Δ^{r_{1}}, where r_{1} = r + r_{0} has the same sign as r, and (since the merging process terminated), uδ^{r_{1}}(v) is freely reduced and also contains no powers of Δ. Then, by Lemma 6.2, if non-geodesic, uδ^{r_{1}}(v) can be reduced to a geodesic word using only unsigned length reducing τ-moves.

We describe that reduction more precisely as follows. We define u_{1} to be the shortest prefix of uδ^{r_{1}}(v) that contains u and ends at the end of a maximal alternating subword, and define v_{1} to be the remainder of the word. Then v_{1} is geodesic, and we set v_{2} := v_{1}. If u_{1} is also geodesic, then we set u_{2} := u_{1}, but otherwise we set u_{2} to be a geodesic word derived from u_{1} by a single length reducing τ-move. We set u_{2}^{(1)} := u_{2}, v_{2}^{(1)} := v_{2}.

We can now reduce u_{2}^{(1)}v_{2}^{(1)} to geodesic form through a series of words u_{2}^{(t)}v_{2}^{(t)} using a sequence of length reducing τ-moves, the i-th of which involves one alternating subword within u_{2}^{(t)} and one within v_{2}^{(t)}. Specifically, we derive u_{2}^{(t+1)}, v_{2}^{(t+1)} from u_{2}^{(t)}, v_{2}^{(t)} by either replacing a suffix _{p}(x, y) ξ_{1} in u_{2}^{(t)} and a prefix ξ_{2} (z^{−1}, t^{−1})_{n} in v_{2}^{(t)} by a suffix _{m−p}(y^{−1}, x^{−1}) δ(ξ_{1}) in u_{2}^{(t+1)} and a prefix δ(ξ_{2}) (t, z)_{m−n} in v_{2}^{(t+1)} or by replacing a suffix _{n}(x^{−1}, y^{−1}) ξ_{1} in u_{2}^{(t)} and a prefix ξ_{2} (z, t)_{p} in v_{2}^{(t)} by a suffix _{m−n}(y, x) δ(ξ_{1}) in u_{2}^{(t+1)} and a prefix δ(ξ_{2}) (t^{−1}, z^{−1})_{m−p} in v_{2}^{(t+1)}. Eventually this process produces a geodesic word u_{3}v_{3}.

Next we need to consider the reduction to geodesic form of u_{3}v_{3}Δ^{r_{1}}. We do this in two stages. First we reduce v_{3}Δ^{r_{1}} to v_{4}Δ^{r′}, using a sequence of length reducing τ-moves, each of which involves a single Δ^{±1} and an alternating subword of the opposite sign within v_{3} (or the word derived from it); at the end of this stage, either v_{4}Δ^{r′} is signed or r′ = 0.

Now if r′ = 0 we set u_{4} := u_{3}, but otherwise, we apply a further sequence of length reducing τ-moves to u_{3}Δ^{r′}, each move involving a single Δ^{±1} and an alternating subword of the opposite sign in the word derived from u′_{3}, and hence reduce u_{3}Δ^{r′} to u_{4}Δ^{s}. The fact that u_{4}δ^{r′−s}(v_{4})Δ^{s} is now a geodesic representative of u_{3}v_{3}Δ^{r_{1}} follows from the two equations u_{3}v_{4}Δ^{r′} =_{G} u_{3}Δ^{r′}δ^{r′}(v_{4}) and u_{4}δ^{r′−s}(v_{4})Δ^{s} =_{G} u_{4}Δ^{s}δ^{r′}(v_{4}). Our construction ensures that u_{4}δ^{r′−s}(v_{4}) has no divisor of the form Δ^{±1}. This is the end of compression; we use the name κ(f_{1}, Δ^{r}, f_{2}) for the group element (u_{4})_{G}.

We now want to estimate both the number of group elements that can arise as κ(f_{1}, Δ^{r}, f_{2}) out of the compression of at least one element (f_{1}, Δ^{r}, f_{2}) of S(g, k, l), and also the number of triples (f_{1}, Δ^{r}, f_{2}) ∈ S(g, k, l) for which κ(f_{1}, Δ^{r}, f_{2}) = g′ for a particular group element g′. The product of these two values will give a bound on |S(g, k, l)|.

Lemma 6.9. The size of κ(S(g, k, l)) is bounded by a polynomial in k.

Proof. Suppose that compression of (f_{1}, Δ^{r}, f_{2}) leads to u_{4}δ^{r′−s}(v_{4})Δ^{s}. We first need to relate |u_{4}| to k = |g_{1}|. We recall that |u| ≤ |f_{1}| ≤ k, |u_{1}| ≤ |u| + m − 1, and |u_{2}| ≤ |u_{1}|. Then each move from u_{2}^{(t)} to u_{2}^{(t+1)} replaces a distinct alternating subword by an alternating subword that is longer by a factor of at most m − 1, and doesn’t alter the lengths of the subwords before or after that alternating subword. Hence |u_{3}| ≤ (m−1)|u_{2}|. By the same argument |u_{4}| ≤ (m − 1)|u_{3}|. So |u_{4}| ≤ (m − 1)^{2}(k + m − 1).

Then u_{4} is a prefix of length k′ ≤ (m − 1)^{2}(k + m − 1) of w′ := u_{4}δ^{r′−s}(v_{4}), for which w′Δ^{s} is a geodesic representing g and no power of Δ divides w′; it follows that u_{4} ∈ P_{l}(g). By Corollary 6.7 we know that, for some polynomial P_{1}(x), P_{1}(k′) bounds the number of elements of P_{l}(g) represented by a word that is a prefix of length k′ of some such w. Hence, since k′ is bounded by a polynomial in k, the number of group elements represented by any such u_{4} with k′ in the appropriate range is bounded by a polynomial in k.

Lemma 6.10. The number of triples (f_{1}, Δ^{r}, f_{2}) in S(g, k, l) for which κ(f_{1}, Δ^{r}, f_{2}) is a particular element g′ ∈ G is bounded by a polynomial in k.

Proof. We recall that for elements of S(g, k, l), f_{1}, f_{2} are represented either by words uΔ^{r_{0}}, v or by words u, Δ^{r_{0}}v, where u, v have no divisors of the form Δ^{±1}. The triple (f_{1}, Δ^{r}, f_{2}) is completely determined by the above binary choice together with u_{G}, r, and r_{0} in the first case. But r (and r_{0} in the first case) is bounded above by k. Hence it is now sufficient to bound the number of choices of u_{G}. Hence the proof of this lemma is completed by application of the lemma that follows.

Lemma 6.11. Given g′ ∈ G, a polynomial in k bounds the number of group elements u_{G} associated as above with triples (f_{1}, Δ^{r}, f_{2}) in S(g, k, l) for which κ(f_{1}, Δ^{r}, f_{2}) =_{G} g′.

Proof. We reverse the steps of compression. Suppose that w = u_{4}δ^{r′−s}(v_{4})Δ^{s} is a word resulting from compression of some element of S(g, k, l), and that (u_{4})_{G} = g′.

We first examine the possible geodesics of the form u_{3}v_{3}Δ^{r′} from which w might have been derived during compression by length reducing moves.

If v_{4}Δ^{s} is unsigned, then we must have u_{3} = u_{4}, r′ = s, and (u_{3})_{G} = (u_{4})_{G} Otherwise, if δ^{r′−s}(v_{4})Δ^{s} is positive, r′ − s might be any non-negative integer bounded above by the number of maximal positive alternating subwords in u_{4}, and u_{3} could be any word derived from u_{4} by reversing r′ − s length reducing rules using Δ, while if δ^{r′−s}(v_{4})Δ^{s} is negative, s − r′ might be any non-negative integer bounded above by the number of maximal negative alternating subwords in u_{4}, u_{3} could be a word derived from u_{4} by reversing s − r′ length reducing rules using Δ^{−1}. We can check that the value of (u_{3})_{G} is determined by (u_{4})_{G} and r′ − s.

Hence there are at most (k +1) possibilities for (u_{3})_{G} for which (u_{4})_{G} =_{G} g′. We saw above that if v_{3} is unsigned or if it has the opposite sign to r′, then

|r′| ≤ k, and so can take up to 2k + 1 values. Otherwise, v_{3}Δ^{r′} is a signed word, and then r′ is uniquely determined by (v_{3}Δ^{r′})_{G}.

We next reverse the length reducing τ-moves that transformed u_{2}v_{2} to u_{3}v_{3}. Each reversed move involves replacing a subword _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} or n(x^{−1}, y^{−1})ξ(z, t)_{p} with 0 < p, n < m and p+n < m by_{m−p}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{m−n} or _{m−n}(y, x) δ(ξ) (t^{−1}, z^{−1})_{m−p}, where the left maximal alternating subword is in some u_{2}^{(t+1)} and the right one in v_{2}^{(t+1)}. Call these transformations of type (p, −n) or (−n, p). Then there are at most m^{2} such possible types. The element (u_{2})_{G} depends only on (u_{3})_{G} and the total number of τ-moves of each type. Since there are at most k such τ-moves in total, there are at most k^{m^{2}} possible elements (u_{2})_{G} for a given (u_{3})_{G}.

And u_{1} represents the same element as u_{2}. A final reversal of a τ-move on the final maximal alternating suffix of u_{2} recovers the word u_{1}, which represents the same group element as u_{2}. And the deletion of an alternating suffix of length at most m − 1 from u_{1} yields u; hence each choice of (u_{1})_{G} yields at most m choices of u.

The combination of Lemma 6.9 and Lemma 6.10 gives the required polynomial bound on S(g, k, l). Hence the proof of D2 for dihedral Artin groups is complete.

7 Artin groups of large type

Our aim in this section is to prove that Artin groups satisfying the hypotheses of Theorem 1.1 satisfy D1 and D2, and hence have rapid decay. Much of what we say is true for any large-type Artin group. But occasionally we shall need to restrict the groups we consider to those satisfying the conditions of Theorem 1.1. For those results where this is the case, we shall make it clear in the statement of the result; the remaining results are proved for all Artin groups of large type.

We assume throughout this section that G is an Artin group of large type, with notation as defined in Section 5. We may assume that not all m_{ij} are infinite, for otherwise the group is free, and rapid decay is known. For any distinct pair of generators x_{i}, x_{j}, we let G(i, j) = G(j, i) be the subgroup of G generated by x_{i} and x_{j}. We use Δ_{ij} to denote (x_{i}, x_{j})_{m_{ij}}, and δ_{ij} to denote the permutation of {x_{i}, x_{i}^{−1}, x_{j}, x_{j}^{−1}} induced by conjugation by Δ_{ij}.

The process of reducing words in G to shortlex minimal form is described in [17, Proposition 3.3]. In [17, Section 3], a leftward or rightward critical sequence is defined as a sequence of τ-moves applied to a word, in which successive moves overlap in a single letter. For a geodesic word whose maximal proper prefix is already shortlex minimal, but which is not itself lexicographically minimal, a lexicographic reduction to a shortlex minimal word can be achieved by a single leftward critical sequence, known as a leftward lex reducing sequence. Similarly, for a non-geodesic word whose maximal proper prefix is shortlex minimal, a length reduction to a shortlex minimal word can be achieved by a single rightward critical sequence followed by a single free cancellation; the combination is known as a rightward length reducing sequence.

For example, with m_{12}, m_{13}, m_{23} = 3, 4, 5 and writing a, b, c for x_{1}, x_{2}, x_{3}:

α(ab^{−2}a^{−1})cb^{2}c^{−1}b^{−1}aca^{2}ca^{−1},
αb^{−1}a^{−2}(bcb^{2}c^{−1}b^{−1})aca^{2}ca^{−1},
αb^{−1}a^{−2}c^{−1}b^{−1}c^{2}b(caca^{2}c)a^{−1},
αb^{−1}a^{−2}c^{−1}b^{−1}c^{2}bac^{2}ac(aa^{−1}),
αb^{−1}a^{−2}c^{−1}b^{−1}c^{2}bac^{2}ac,

where α is an arbitrary word, is a rightward length reducing sequence in which the critical words to which τ-moves are applied are bracketed and printed in boldface, and the final move is the free reduction of aa^{−1}.

7.1 The geodesics in Artin groups of large type

We shall need some results about geodesics in Artin groups of large type. The first of these is proved in [17].

Proposition 7.1 ([17, 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 7.2. If wa is a geodesic word for some a ∈ A and k > 1, then wa^{k} is a geodesic word for all k > 1.

Proof. Otherwise, choosing k minimal with wa^{k} non-geodesic, the group element wa^{k−1} has geodesic representatives ending both in a and in a^{−1}, contradicting Proposition 7.1 (1).

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.

Proof. Order the monoid generators of G such that x_{i}^{±1}, x_{j}^{±1} (in some order) come first, and let w′ be the shortlex least representative of g, using this ordering, with maximal {x_{i}, x_{j}}-prefix u′.

Let w be an arbitrary geodesic representative of g and let u be the maximal {x_{i}, x_{j}}-prefix of w. We consider the process of reducing w to its shortlex form w′ by considering each letter of w in turn, and reducing the prefix ending in that letter to shortlex form. Suppose that w_{0} = w, that w reduces through the sequence of words w_{1}, w_{2}, … to w_{n} = w′ and that u_{0} = u, u_{1}, …, u_{n} = u′ is the corresponding sequence of maximal {x_{i}, x_{j}}-prefixes.

By [17, Proposition 3.3], the prefix of length k in w_{k} is either already shortlex reduced, or can be reduced to shortlex form with a single leftward lex reducing sequence. Such a reduction cannot change a letter of u_{k} to a letter with name not in {x_{i}^{±1}, x_{j}^{±1}}, since that would be shortlex increasing. So either u_{k+1} = u_{k} or u_{k+1} is the shortlex reduction of u_{k}a^{s} for some a ∈ {x_{i}^{±1}, x_{j}^{±1}} and s > 0. By [17, Lemma 3.8(2)], after such a reduction, the names of the next two letters in w_{k+1} after u_{k+1} are the name of a and a generator not in {x_{i}, x_{j}}. So if subsequent reductions occur that increase the length of the maximal i, j-prefix, then they all involve adjoining the same letter a. (We can’t adjoin a and then a^{−1} or the word would not be geodesic!) So we have u′ =_{G} ua^{r} with |u′| = |u|+r. as claimed. Since the equation holds for any choice of w, we have proved that (u′)_{G} is the unique longest left divisor of g in G(i, j).

The proof for the maximal right divisor is similar.

Proposition 7.4. (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.

Proof. The proof of (1) is by induction on |v|, the result being vacuously true when |v| = 1. Let x_{i} and x_{j} be the names of l[v] and l[w], and let v = v′u, where u is the longest 2-generator suffix of v. If u has a geodesic representative ending in l[w], then the result follows from [17, Corollary 2.6], so suppose not. By Proposition 7.3, we have RD_{ij}(g) =_{G} a^{r}u for some a ∈ {x_{i}^{±1}, x_{j}^{±1}}, and also RD_{ij}(g) has a geodesic representative ending in l[w]. So, by [17, Lemma 2.8], a single τ-move can be applied to au to give a word ending in l[w]. Now, by inductive hypothesis, a single rightward critical sequence can be applied to v′ to yield a word ending in a, and following this by the above τ-move results in the required critical sequence, which completes the proof of (1).

If v is as in (2), then w has a geodesic representative ending in a^{−1}, and the result follows from (1).

In fact the above proposition provides a slightly shorter proof that Artin groups of large type have FFTP than the one in [17].

The next proposition implies that for the groups in Theorem 1.1, for a given g, i and j, the letter a arising in Proposition 7.3 is unique.

Proposition 7.5. Assume that G satisfies the hypotheses of Theorem 1.1, and let g ∈ G and x_{i}, x_{j} ∈ X with i ≠ j. Then either

(1) every geodesic word representing g has a prefix that represents LD_{ij}(g); or (2) there is a unique letter a ∈ {x_{i}^{±1}, x_{j}^{±1}}, and an element LD′_{ij}(g) ∈ G(i, j)

such that, for any geodesic representative w with maximal {x_{i}, x_{j}}-prefix u, we have LD_{ij}(g) =_{G} ua^{r} and u =_{G} LD′_{ij}(g)a^{s}, for r, s ≥ 0.

In case (1), we define LD′_{ij}(g) = LD_{ij}(g), for future reference.

Proof. Let h := LD_{ij}(g) and h′ := h^{−1}g, and suppose that case (1) does not hold. Then g has at least one geodesic representative whose maximal {x_{i}, x_{j}}- prefix u is a proper left divisor of LD_{ij}(g). Proposition 7.3 implies that h =_{G} ua^{r} with r > 0.

If a is not uniquely determined, then g has another geodesic representative with maximal {x_{i}, x_{j}}-prefix v such that h =_{G} vb^{s}, with s > 0 and b ≠ a. We may assume that the names of a and b are x_{i}, x_{j} respectively. Note that, since h has more than one geodesic representative, the vertices corresponding to x_{i}, x_{j} in the graph Γ defining G must be joined by an edge (that is m_{ij} < ∞).

Now a^{r}h′ = u^{−1}g has a geodesic representative beginning with a and another geodesic representative beginning with a letter with name x_{i′} for some i′ ≠ i, j. By Proposition 7.1, all geodesic representatives of a^{r}h′ have their longest 2-generator prefix in G(i, i′), and hence all geodesic representatives of h′ must begin with the same letter c, of which the name is x_{i′}. Furthermore, any geodesic representative of LD_{ii′}(a^{r}h′) must contain a critical subword, and similarly LD_{ji′}(b^{s}h′) contains a critical subword.

From the hypothesis of Theorem 1.1 and the fact that the vertices x_{i} and x_{j} are joined by an edge in Γ, it follows that the edges joining vertices x_{i}, x_{i′} and vertices x_{j}, x_{i′} cannot both have the label 3. So, for at least one of LD_{ii′}(a^{r}h′) and LD_{ji′}(b^{s}h′), it is true that any geodesic representative has at least four syllables. Assume without loss that this is true for LD_{ii′}(a^{r}h′). So h′ has geodesic representatives u_{1}, u_{2}, where u_{1} has a prefix in G(i, i′) with at least three syllables and u_{2} has a prefix in G(j, i′) with at least two syllables. But then, if c^{s} is the highest power of c that is a left divisor of h′, c^{−s}h′ has a geodesic representative beginning with x_{i} with a 2-generator prefix in G(i, i′) and another geodesic representative beginning with x_{j}, which contradicts Proposition 7.1 (as applied to prefixes of u_{1} and u_{2}).

So a is indeed uniquely determined. We define LD′_{ij}(g) := LD_{ij}(g)a^{−s}, where a^{s} is the maximal power of a that is a right divisor of LD_{ij}(g).

The following example shows that Proposition 7.5 fails without the (3, 3, m)- hypothesis. Let m_{12}, m_{13}, m_{23} = 4, 3, 3 and write a, b, c for x_{1}, x_{2}, x_{3}. Let g be the group element represented by the geodesic word w := babacabab. Then, since the only two geodesic representatives of the suffix cabab of w are cabab and cbaba, neither of which starts with a^{±1} or b^{±1}, we see that LD_{1,2}(g) = baba. But, by replacing aca by cac, we have g =_{G} w_{1} with w_{1} = babcacbab, and also g =_{G} (baba)c(abab) =_{G} aba(bcb)aba =_{G} w_{2} with w_{2} = abacbcaba, so LD_{1,2}(g) =_{G} v_{1}a =_{G} v_{2}b, where v_{1} and v_{2} are the maximal {a, b}-prefixes of w_{1} and w_{2}, respectively. A corresponding example can be constructed with m_{12} = m for any m with 3 ≤ m < ∞.

7.2 Verifying D1 and D2 for the Artin groups in Theorem 1.1

We assume for the remainder of the paper that G satisfies the hypotheses of Theorem 1.1: G is an Artin group of large type that satsifies the (3, 3, m)- hypothesis.

We must first define our set P of permissible geodesic factorisations (g_{1}, g_{2}). We use the notation P_{ij} to denote the set of permissible geodesic factorisations in the dihedral Artin group on G(i, j), as defined in Subsection 6.2. Recall that LD_{ij}(g) and RD_{ij}(g) were defined in Proposition 7.3 as the longest left and right divisors of g in G(i, j). Then we define P to be the set of geodesic factorisations (g_{1}, g_{2}) in G such that for every pair of generators x_{i}, x_{j}, (RD_{ij}(g_{1}), LD_{ij}(g_{2})) ∈ P_{ij}.

Our proof of D1 will involve an inductive argument. To make this work properly, we have to investigate in what circumstances we can have a geodesic factorisation (ag_{1}, g_{2}) ∈ P for some a ∈ A, with (g_{1}, g_{2}) ∉ P.

Lemma 7.6. Suppose that g ∈ G, a ∈ A, |ag| = |g| + 1, (ag_{1}, g_{2}) ∈ P(ag) but (g_{1}, g_{2}) ∉ P(g).

(1) Then ag has a geodesic representative that begins with a letter b ≠ a.

(2) If ag_{1} does not lie in any 2-generator subgroup of G, then all geodesic representatives of LD′_{ij}(ag) (as defined in Proposition 7.5) begin with b, where x_{i} and x_{j} are the names of a and b.

Proof. Suppose first that ag_{1} lies in a 2-generator subgroup G(i, j). Then (ag_{1}, g_{2}) ∈ P_{ij} and (g_{1}, g_{2}) ∉ P_{ij} implies that the factorisation (g_{1}, g_{2}) of g must be Δ_{ij}-decreasing (as defined in Section 6.2), while the factorisation (ag_{1}, g_{2}) of ag is not. So ag_{1} is divisible by Δ_{ij}, and conclusion (1) is immediate.

So now suppose that ag_{1} does not lie in a 2-generator subgroup of G. Then there exist distinct i′, j′ such that (RD_{i′j′}(ag_{1}), LD_{i′j′}(g_{2})) ∈ P_{i′j′} and (RD_{i′j′}(g_{1}), LD_{i′j′}(g_{2})) ∉ P_{i′j′}. Let h := RD_{i′j′}(ag_{1}). Since, by Proposition 7.3, RD_{i′j′}(g_{1}) is a right divisor of h, we have |h| > |RD_{i′j′}(g_{1})|. We are assuming that ag_{1} ∉ G(i′, j′), so |h| < |ag_{1}|, and ag_{1}h^{−1} cannot have a geodesic representative beginning with a, as that would imply that h was a right divisor of g_{1}. Hence all geodesic representatives of ag_{1}h^{−1} begin with some letter b with b ≠ a, and hence ag has a geodesic representative beginning with b, which proves (1).

We observe also that (RD_{i′j′}(g_{1}), LD_{i′j′}(g_{2})) must be a Δ_{i′j′}-decreasing factorisation, whereas (h, LD_{i′j′}(g_{2})) is not, so h must be a signed element divisible by Δ_{i′j′}^{±1}. Hence h has geodesic representatives beginning with letters with names x_{i′} and x_{j′}; these are suffices u′, v′ of geodesic representatives u, v of ag_{1}. Now if both u′ intersects the maximal {x_{i}, x_{j}}-prefix of u and v′ intersects the maximal {x_{i}, x_{j}}-prefix of v, we have {i, j} = {i′, j′} and hence ag_{1} ∈ G(i, j), a contradiction. This implies that ag has a geodesic representative in which the maximal {x_{i}, x_{j}}-prefix is a left divisor of ag_{1}h^{−1}. Then, by Proposition 7.5, LD′_{ij}(ag) is a left divisor of ag_{1}h^{−1}; hence, as we showed in the proof of (1), all of its geodesic representatives begin with b, and (2) is proved.

In Corollary 6.7, we proved D1 for 2-generator Artin groups. Let P′ be a polynomial such that D1 holds with P′ for each of the 2-generator subgroups G(i, j) of G.

Lemma 7.7. Let g ∈ G with |g| = m and suppose that v, w are geodesic representatives of g with f[v] ≠ f[w]. Suppose that 0 ≤ k ≤ m. Let D be the set of left divisors g_{1} of g in P_{l}(g) of length k for which all geodesic representatives begin with f[v]. Then |D| ≤ Q(k) := ∑_{j=1}^{k} P′(j).

Proof. The proof is by induction on m, the result being vacuously true for m = 1. Let the names of f[v] and f[w] be x_{i}, x_{j}, let h := LD_{ij}(g), and let h′ := LD′_{ij}(g), as defined in Proposition 7.5. Suppose that g_{1} ∈ D, with g = g_{1}g_{2}.

If g_{1} ∈ G(i, j), then g_{1} ∈ P_{l}(h). It follows immediately from Corollary 6.7 that there are at most P′(k) such choices for g_{1}.

So now suppose that g_{1} ∉ G(i, j). Since g_{1} has f[v] as unique left divisor of length 1, whereas g and hence h, by Proposition 7.3, has more than one such left divisor, h cannot be a left divisor of g_{1}.

Since g_{1} ∉ G(i, j), Proposition 7.5 implies that h′ is a left divisor of g_{1}, and so a proper divisor of h, and that h = h′a^{r} for some r > 0, a ∈ {x_{i}^{±1}, x_{j}^{±1}}. But now, since LD_{ij}(g_{1}) is certainly a left divisor of g, Proposition 7.5 also implies that h = LD_{ij}(g_{1})a^{s}, for some s > 0. We deduce that LD_{ij}(g_{1}) = h′a^{t}, with t ≥ 0. By [17, Lemma 2.8], h′a has more than one left divisor of length 1, and so cannot be a left divisor of g_{1}, so t = 0. Hence LD_{ij}(g) = h′.

Now h^{′−1}g has a geodesic representative with first letter a, whereas g′_{1} := h^{′−1}g_{1} does not. So by Proposition 7.1, all geodesic representatives of g′_{1} have the same first letter.

We claim that g′_{1} ∈ P_{l}(h^{′−1}g). If not then for some i′, j′, (g′_{1}, g_{2}) is Δ_{i′j′}- decreasing whereas (g_{1}, g_{2}) is not, and hence RD_{i′j′}(g_{1}) is longer than RD_{i′j′}(g′_{1}), Now suppose that vw is a geodesic representative of g_{1}, with w representing RD_{i′j′}(g_{1}). Then by Proposition 7.5 (2) some prefix u of vw represents h′. If u is a prefix of v, then w is a suffix of a representative of g′_{1}, and RD_{i′j′}(g_{1}) is a right divisor of g′_{1}, yielding a contradiction. So u and w must intersect non-trivially, and hence |{i, j} ∩ {i′, j′}| = 1. We may suppose that i = i′ and j ≠ j′. Then since (g_{1}, g_{2}) is not Δ_{i′j′}-decreasing, the element RD_{i′j′}(g_{1}) is divisible by Δ_{i′j′}, and so has a representative that begins with x_{j′}^{±1}; hence we can find a geodesic representative of g_{1}, and then one of g, in which the longest {x_{i}, x_{j}}-prefix is shorter than |h′|, contradicting Proposition 7.5 (2).

Now by the inductive hypothesis applied to h^{′−1}g, there are at most Q(k − |h′|) ≤ Q(k−1) possible g′_{1} and hence at most Q(k−1) possible g_{1} of length k not in G(i, j). This bounds the total number of g_{1} of length k by Q(k −1)+P′(k) = Q(k) for any k ≤ m, and so completes the inductive step.

Proposition 7.8. D1 holds with the polynomial P_{1} defined by P_{1}(n) = 2 ∑_{j=0}^{n} Q(j), where the set P and the polynomial Q are as defined above.

Proof. Let g be an element of length m and choose k with 0 ≤ k ≤ m. The proof is by induction on m, the case m = 1 being clear.

If all geodesic representatives of g begin with the same letter, then the result follows immediately from the inductive hypothesis and Lemma 7.6 (1). So suppose that g has geodesic representatives v, w with f[v] ≠ f[w], and let x_{i}, x_{j} be the names of f[v], f[w]. Assume without loss that LD′_{ij}(g) has a geodesic representative beginning with f[w].

Let D be the set of elements in P_{l}(g) of length k. Then D = D_{1} ∪ D_{2} ∪ D_{3}, where D_{1} consists of those elements of D that lie in G(i, j), D_{2} consists of those elements of D \D_{1} with at least one geodesic representative beginning with f[w], and D_{3} consists of those elements of D \D_{1} all of whose geodesic representatives begin with f[v]. Then |D_{1}| ≤ Q(k) from the 2-generator case and |D_{3}| ≤ Q(k) by Lemma 7.7.

Suppose that g_{1} ∈ D_{2}. If f[w]^{−1}g_{1} ∉ P_{l}(f[w]^{−1}g), then by Lemma 7.6 (2), all geodesic representatives of LD′_{ij}(g) begin with f[v], contrary to assumption; so f[w]^{−1}g_{1} ∈ P_{l}(f[w]^{−1}g), and the inductive hypothesis applied to f[w]^{−1}g_{1} gives |D_{2}| ≤ P_{1}(k − 1). So |D| ≤ P_{1}(k − 1) + 2Q(k) = P_{1}(k) as required.

The following lemma is of the same type as Lemma 6.3. It holds for all Artin groups of large type.

Lemma 7.9. For some i ≠ j, suppose that no nontrivial element of G(i, j) is either a left divisor of g_{1} or a right divisor of g_{2}. If g_{1}g_{2} ∈ G(i, j), then g_{1}g_{2} = 1.

Proof. Suppose g_{1}g_{2} = h with 1 ≠ h ∈ G(i, j). Since g_{1} has no element of G(i, j) as left divisor, hg_{2}^{−1} cannot be a geodesic factorisation. Let u, v be geodesic words representing h, g_{2}^{−1}. Let u′ = au′′ with a ∈ {x_{i}^{±1}, x_{j}^{±1}} be the shortest suffix of u such that u′v is non-geodesic. Then u′′v has a geodesic representative beginning with a^{−1} whereas u′′ does not. So the maximal {x_{i}, x_{j}}-prefix of that geodesic representative of u′′v cannot represent a left divisor of (u′′)_{G}, and hence by Lemma 7.3 (u′′)_{G} ≠ LD_{ij}((u′′v)_{G}). But then g_{2} must have a nontrivial right divisor in G(i, j), contrary to assumption.

It remains to verify D2. We start by defining a merging process for elements g_{1} ∈ C_{k} and g_{2} ∈ C_{l} which, as in the 2-generator case, will result in a merger (f_{1}, Δ_{ij}^{r}, f_{2}) for some i, j where, for h_{1} := f_{1}^{−1}g_{1}, h_{2} := g_{2}f_{2}^{−1}, we have h_{1}h_{2} = Δ_{ij}^{r}, (f_{1}, h_{1}) ∈ P(g_{1}) and (h_{2}, f_{2}) ∈ P(g_{2}).

As in the 2-generator case, the merging process proceeds through a series of steps, starting with g_{1}^{(1)} := g_{1}, r_{1} := 0, g_{2}^{(1)} := g_{2}, and in the t-th step we compute g_{1}^{(t+1)}, r_{t+1}, g_{2}^{(t+1)}, by choosing geodesic factorisations g_{1}^{(t+1)}h and h′g_{2}^{(t+1)} of g_{1}^{(t)} and g_{2}^{(t)} such that g_{1}^{(t+1)} ∈ P_{l}(g_{1}) and g_{2}^{(t+1)} ∈ P_{r}(g_{2}). But there is an additional complication in that the i, j in the term Δ_{ij}^{r_{t}} may change during the process.

Recall from Subsection 6.2 that there are three types of merging steps, the first being free cancellation, and the other two involving a specific Δ_{ij}. In general, they are defined in the same way as in the 2-generator case subject to the condition that, if r_{t} ≠ 0, then we must choose h, h′ ∈ G(i, j). If r_{t} = 0, then there is no such restriction on free cancellation moves whereas, for the other two types, we have h, h′ ∈ G(i, j) for the new values of i, j.

Again as in the 2-generator case, for g ∈ G, k, l ∈ ℕ k + l = m := |g| we define the set S(g, k, l) to be the set of all triples (f_{1}, Δ^{r}, f_{2}) that arise as mergers of pairs of elements g_{1}, g_{2} of lengths k, l and with g_{1}g_{2} = g. For each such triple, we have Δ = Δ_{ij} for some i, j; if r = 0, then {i, j} is not necessarily uniquely defined. There exist h_{1}, h_{2} ∈ G with h_{1}h_{2} = Δ^{r} where g_{1} = f_{1}h_{1} and g_{2} = h_{2}f_{2}, and the restrictions on the merging steps described above ensure that (f_{1}, h_{1}) ∈ P(g_{1}) and (h_{2}, f_{2}) ∈ P(g_{2}).

In order to verify D2, we have to show that |S(g, k, l)| is bounded by P (k) for some polynomial P. We decompose S as a disjoint union S_{0} ∪ S_{1} ∪ S_{2}, and establish polynomial bounds for each of those subsets.

We define S_{0} to be the subset of elements of S(g, k, l) for which r = 0 and f_{1}, f_{2} ∈ ⟨x_{i}⟩ for some generator x_{i}. Since |f_{1}| ≤ k, f_{2} = f_{1}^{−1}g, and x_{i} is determined by g, we have |S_{0}| ≤ 2k + 1.

The sets S_{1}, S_{2} are defined with respect to the elements f′′_{1}, f̂, f′′_{2} that are defined in Proposition 7.10 below. We define S_{1} to be the set of triples in S(g, k, l) \ S_{0} for which f′′_{1}f̂f′′_{2} is a geodesic factorisation of g, and S_{2} to be the others.

Proposition 7.10. Let (f_{1}, Δ^{r}, f_{2}) ∈ S(g, k, l) \ S_{0}. Then the following is true for some i ≠ j with 1 ≤ i, j ≤ n where, if r ≠ 0, i, j are determined by Δ = Δ_{ij}. There exist f′′_{1}, f′_{1}, f′′_{2}, f′_{2}, f̂ ∈ G such that

(1) f′_{1}, f′_{2}, f̂ ∈ G(i, j), but f′′_{1} has no right divisor in G(i, j) and f′′_{2} has no left divisor in G(i, j),

(2) g = f′′_{1}f̂f′′_{2}, f_{1} = f′′_{1}f′_{1}, f_{2} = f′_{2}f′′_{2}, and

(3) (f′_{1}, Δ^{r}, f′_{2}) ∈ S(f̂, k′, l′) for some k′ ≤ k and l′ ≤ l.

Furthermore, f̂ does not lie in ⟨x_{i}⟩ for any i.

Proof. Since (f_{1}, Δ^{r}, f_{2}) ∈ S(g, k, l), it is the merger of elements g_{1} ∈ C_{k} and g_{2} ∈ C_{l}, and so there exist h_{1}, h_{2} ∈ G with g_{1} = f_{1}h_{1}, g_{2} = h_{2}f_{2} and h_{1}h_{2} = Δ^{r}.

Suppose first that r ≠ 0, and hence that i, j are uniquely specified, with m_{ij} < ∞. Define f′_{1} := RD_{ij}(f_{1}), h′_{1} := LD_{ij}(h_{1}), f′_{2} := LD_{ij}(f_{2}), h′_{2} := RD_{ij}(h_{2}), k′ = |f′_{1}h′_{1}|, l′ = |h′_{2}f′_{2}| and f̂ = f′_{1}h′_{1}h′_{2}f′_{2}. Now Lemma 7.9 applied to h_{1}^{′−1}h_{1} and h_{2}h_{2}^{′−1} tells us that h′_{1}h′_{2} = h_{1}h_{2} = Δ^{r}. In other words, during the merging the right divisor (h′_{1})^{−1}h_{1} of h_{1} has cancelled with the left divisor h_{2}(h′_{2})^{−1} of h_{2}. We see also that (f′_{1}, Δ^{r}, f′_{2}) ∈ S(f̂, k′, l′) is the result of the merging of f′_{1}h′_{1} and h′_{2}f′_{2} in G(i, j). Suppose that f̂ ∈ ⟨x_{i′}⟩ for i′ = i or j. Then the application of Lemma 6.3 to f′_{1}h′_{1} and h′_{2}f′_{2} shows that free cancellation of w with w ∈ P_{r}(f′_{1}h′_{1}), w^{−1} ∈ P_{l}(h′_{2}f′_{2}) can be used to merge f′_{1}h′_{1} and h′_{2}f′_{2} to give just a power of x_{i′}, contradicting the fact that r ≠ 0. (Here we are using the factorisations in P^{1}, to ensure that such a cancellation would be permissible.)

Suppose instead that r = 0. Then h_{1} = h_{2}^{−1}. Since we are assuming that (f_{1}, Δ^{r}, f_{2}) ∉ S_{0}, we can choose distinct i, j such that f′_{1} := RD_{ij}(f_{1}) and f′_{2} := LD_{ij}(f_{2}) do not both lie in the same cyclic subgroup ⟨x_{i′}⟩ for i′ = i or j. If possible, we choose i, j such that the vertices corresponding to i, j in the graph Γ defining G are joined by an edge (equivalently, m_{ij} < ∞). Again we define h′_{1} := LD_{ij}(h_{1}), h′_{2} := RD_{ij}(h_{2}), k′ = |f′_{1}h′_{1}|, l′ = |h′_{2}f′_{2}| and f̂ = f′_{1}h′_{1}h′_{2}f′_{2}. Since h_{1} = h_{2}^{−1}, we have h′_{1} = (h′_{2})^{−1}, so in this case too (f′_{1}, Δ_{ij}^{r}, f′_{2}) ∈ S(f̂, k′, l′) is a merger of f′_{1}h′_{1} and h′_{2}f′_{2} in G(i, j) and, by Lemma 6.3, f′_{1}h′_{1}h′_{2}f′_{2} does not lie in a cyclic subgroup ⟨x_{i′}⟩ for i′ = i or j.

For triples in S_{1}, we claim that f′′_{1} ∈ P_{l}(g). Since f′′_{1} has no right divisor in G(i, j) the only way that the factorisation (f′′_{1}, f̂f′′_{2}) could be Δ-decreasing for some Δ would be with Δ = Δ_{ii′}, where x_{i′} is the name of both l[f′′_{1}] and f[f′′_{2}] and f̂ = x_{i}^{s}x_{j}^{t} for some s, t > 0. But then RD_{ii′}(f̂f′′_{2}) would have at most two syllables, and so the factorisation would still be permissible. So the claim is true.

Hence, since |f′′_{1}| ≤ k, the number of choices of f′′_{1} is bounded by P_{1}(k). For given f′′_{1} and a pair i, j, we have f̂ = LD_{ij}(f′′_{1}^{−1}g) and f′′_{2} = f̂^{−1}f′′_{1}^{−1}g. Now (f′_{1}, Δ_{ij}^{r}, f′_{2}) ∈ S(f̂, |f′_{1}h′_{1}|, |h′_{2}f′_{2}|), which we know from the dihedral case has size bounded by P_{2}^{ij}(min |f′_{1}h′_{1}|, |h′_{2}f′_{2})) ≤ P_{2}^{ij}(k). So |S_{1}| ≤ P_{1}(k) ∑_{i,j} P_{2}^{ij}(k).

In order to bound |S_{2}|, we need some further technical lemmas.

Lemma 7.11. Suppose that f′′_{1}f̂f′′_{2} is not a geodesic factorisation of g. Then f̂ = a^{s}b^{t} for some s, t > 0 where a, b ∈ {x_{i}^{±1}, x_{j}^{±1}} and a, b have different names.

Proof. Let u′′_{1}, û, u′′_{2} be geodesic words representing f′′_{1}, f̂, f′′_{2}, respectively. Suppose (for a contradiction) that û has at least three syllables. Since u′′_{1}ûu′′_{2} is not geodesic, we can by Proposition 7.4 (2) apply a rightward length reducing sequence to a prefix of it containing u′′_{1}.

If the left-hand end of the first critical subword in the sequence were to the left of û, then some τ-move in the sequence would replace a letter in the first syllable of û by a letter c with name not equal to x_{i} or x_{j}. But since c would then be followed by at least two syllables with names x_{i} and x_{j}, c would not be the leftmost letter in a critical subword, and so this would be the last τ-move in the sequence, and would not provoke a free reduction. So the left hand end of the first critical subword must be within û.

We may assume that the first τ-move of the sequence is not completely within û, since otherwise we could just replace û by the result of this move. So the first critical subword overlaps the right hand end of û and hence has its left hand end in the final syllable, a^{s} say, of û. But then a^{s}u′′_{2} is not geodesic and so, by Corollary 7.2, neither is au′′_{2}. But then f′′_{2} has a geodesic representative beginning with a^{−1}, contradicting f_{2} = f′_{2}f′′_{2} with f′_{2} = LD_{ij}(f_{2}).

Lemma 7.12. Suppose that f̂ = a^{s}b^{t} for some s, t > 0, where a, b have distinct names x_{i}, x_{j}, and that f′′_{1}f̂f′′_{2} is not a geodesic factorisation of g. Then there exists a letter c with name x_{i′} not equal to x_{i} or x_{j}, q > 0, and e_{1}, e_{2} ∈ G, such that f′′_{1}a^{s} = e_{1}c^{q} and b^{t}f′′_{2} = c^{−q}e_{2}, where e_{1}c^{q}, c^{−q}e_{2} and e_{1}e_{2} are all geodesic factorisations. Furthermore, the vertices corresponding to x_{i}, x_{j} in the graph Γ are joined by an edge; that is m_{ij} < ∞.

Proof. Let u′′_{1}, u′′_{2} be geodesic representatives of f′′_{1}, f′′_{2}. Using similar reasoning to that of the proof of the previous lemma, we see that a rightward length reducing sequence applied to the word u′′_{1}a^{s}b^{t}u′′_{2} would consist of a sequence of moves that replaced u′′_{1}a^{s} by a word ending in a letter c with name x_{i′} not equal to x_{i} or x_{j}, followed by a length reducing sequence applied to cb^{t}u′′_{2}. But then b^{t}u′′_{2} would have a geodesic representative starting with c^{−1}. Let q be maximal such that f′′_{1}a^{s} and b^{t}f′′_{2} have geodesic factorisations e_{1}c^{q} and c^{−q}e_{2} respectively.

If m_{ij} were infinite, then we would have r = 0 in Proposition 7.10, in which case we could and would have chosen one of the pairs i, i′ or j, i′, depending on which of m_{ii′} and m_{ji′} was finite rather than i, j in the proof of that proposition. So m_{ij} < ∞, which proves the final assertion in the lemma. Hence the hypothesis of Theorem 1.1 implies that at least one of the m_{ii′} and m_{ji′} is at least 4.

Let h_{1} and h_{2} be the group elements represented by e_{1}c^{q} =_{G} u′′_{1}a^{s} and c^{−q}e_{2} =_{G} b^{t}u′′_{2}, respectively. Applying Propositions 7.1 and 7.3 to these elements, we see that RD_{ii′}(h_{1}) and LD_{ji′}(h_{2}) are represented by w_{1} and w_{2}, ending in c^{q} and beginning with c^{−q}, respectively. Since w_{1} and w_{2} are not the unique geodesic representatives of RD_{ii′}(h) and LD_{ji′}(h_{2}), the above condition on the edge labels implies that at least one of w_{1} and w_{2} has at least four syllables. Hence either e_{1} has a geodesic representative v_{1} in which at least the final three syllables are powers of a and c, or e_{2} has a geodesic representative v_{2} in which at least the first three syllables are powers b and c. We see that no rightward length reducing sequence can pass through this middle section, and hence v_{1}v_{2} is geodesic, which completes the proof.

By Lemma 7.11, each element (f_{1}, Δ_{ij}^{r}, f_{2}) of S_{2} determines f′′, f̂, f′′_{2} for which the hypotheses and conclusion of Lemma 7.12 hold. Since |g| ≥ l − k, we must have q ≤ k, so there are at most 2nk possibilities for c^{q}. So assume that c^{q} is fixed. Unfortunately we have no bound on |e_{1}| as a polynomial in k. Let e_{1} = e′′_{1}e′_{1} with e′_{1} = RD_{ii′}(e_{1}). Then |e′′_{1}| < |f′′_{1}| < k and e′′_{1} ∈ P_{l}(e_{1}), so there are at most P_{1}(k) possible e′′_{1}.

We claim that the triple (f_{1}, Δ_{ij}^{r}, f_{2}) is uniquely determined by g, c^{q} and e′′_{1}. To see this note that LD_{ii′}(e′′_{1}^{−1}g) = e_{1}c^{−t} for some t ≥ 0 and, since (e_{1}, c^{q}) is a geodesic factorisation, e_{1} does not have c^{−1} as right divisor. Hence, given g, c^{q} and e′′_{1}, e′_{1} is determined as LD_{ii′}(e′′_{1}^{−1}g)c^{t}, where c^{−t} is the longest right divisor of LD_{ii′}(e′′_{1}^{−1}g) of that form. Then e_{1} and f′′_{1} are determined as e′′_{1}e′_{1} and e_{1}c^{q}a^{−s}, where a^{s} is the highest power of a that is a right divisor of e_{1}c^{q}. Then, as in the previous case, we have f̂ = LD_{ij}(f′′_{1}^{−1}g) and f′′_{2} = f̂^{−1}f′′_{1}^{−1}g, which establishes the claim.

So the number of triples (f_{1}, Δ_{ij}^{r}, f_{2}) ∈ S(g, k, l) that satisfy the conclusion of Lemma 7.12, and hence also |S_{2}|, is bounded by 2nkP_{1}(k) ∑_{i,j} P_{2}^{ij}(k).

This completes the proof that Artin groups satisfying the hypotheses of Theorem 1.1 satisfy D1 and D2, and hence also the proof of Theorem 1.1.

Acknowledgments

We would like to thank the referee of an earlier version of this paper, whose query as to whether or not Lafforgue’s results would actually apply to the groups under study led us to address this question and hence add the second of the two main results.

The first author was partially supported by the Marie Curie Reintegration Grant 230889, the third author by grants from the Mathematics Departments of the Universities of Fribourg and Neuchâtel, Switzerland, and by UK Engineering and Physical Sciences Research Council grant EP/F014945/1, Quantum Computation: Foundations, Security, Cryptography and Group Theory.

References

[1] K I Appel, On Artin groups and Coxeter groups of large type, Contemporary Mathematics 33 (1984) 50–78.

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

[3] W. Ballmann, Singular spaces of non-positive curvature, Sur les groupes hyperboliques d’après Mikhail Gromov, Progr. Math. 83, Birkhäuser Boston, Boston MA, 1990

[4] W. Ballmann, Lectures on spaces of non-positive curvature, DMV seminar 25, Birkhäuser, 1995.

[5] J. Behrstock and Y. Minsky, Centroids and the rapid decay property in mapping class groups, J. Lon. Math. Soc. 84 (2011) 765–784.

[6] T. Brady and J. McCammond, Three generator Artin groups of large type are biautomatic, J. Pure Appl. Alg. 151 (2000) 1–9.

[7] Indira Chatterji, On property RD for certain discrete groups, PhD thesis, ETH Zürich, September 2001.

[8] I. Chatterji and K. Ruane, Some geometric groups with rapid decay, Geom. Funct. Anal. 15 (2005) 311–339.

[9] P.A. Cherix, M. Cowling, P. Jolissaint, P. Julg and A. Valette, Groups with the Haagerup property (Gromov’s a-T-menability), Progr. Math. 197, Birkhäuser, Basel, 2001.

[10] L. Ciobanu, D.F. Holt and S. Rees, Rapid decay is preserved by graph

products, http://arxiv.org/abs/1110.6831, preprint 2011.

[11] J. Crisp and L. Paris, Artin groups of type B and D, Adv. Geom. 5 (2005) 607–636.

[12] C. Drutu and M. Sapir. Relatively Hyperbolic Groups with Rapid Decay Property, Int. Math. Res. Notices 19 (2005) 1181–1194.

[13] U. Haagerup, An example of a non-nuclear C^{∗}-algebra, which has the metric approximation property, Invent. Math. 50 (1978/9) 278–293.

[14] P. de la Harpe. Groupes hyperboliques, algèbres d’opérateurs et un théorème de Jolissaint, C. R. Acad. Sci. Paris Sér. I. Math. 307 (1988) 771–774.

[15] N. Higson and G. Kasparov, E-theory and KK-theory for groups which act properly and isometrically on Hilbert space, Invent. Math. 144 (2001) 23–74.

[16] N. Higson, V. Lafforgue, G. Skandalis, Counter-examples to the Baum-Connes conjecture, Geom. Funct. Anal. 12 (2002) 330–354.

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

[18] P Jolissaint, Rapidly decreasing functions in reduced C^{∗}-algebras of groups, Trans. Amer. Math. Soc. 317 (1990) 167–196.

[19] V. Lafforgue, K-théorie bivariante pour les algègbres de Banach et conjecture de Baum-Connes, Invent. Math. 149 (2002) 1–95.

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

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

[22] P. Z. Ong, Rapid decay property and small cancellation groups. Ph.D. Thesis, University of California, San Diego, 1991.

[23] T. Schick, Finite group extensions and the Baum-Connes conjecture, Geom. Topol. 11 (2007) 1767-1775.

[24] A. Valette, Introduction to the Baum-Connes conjecture. From notes taken by Indira Chatterji. With an appendix by Guido Mislin. Lectures in Mathematics ETH Zürich. Birkhäuser, Basel, 2002.

Addresses:

Laura Ciobanu, Mathematics Department, University of Neuchâtel, Rue Emile Argand 11, CH-2000 Neuchâtel, Switzerland. email: Laura.Ciobanu@unine.ch

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

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