Rapid Decay is Preserved by Graph Products

Laura Ciobanu, Derek F. Holt and Sarah Rees

28th October 2011

Abstract

We prove that the rapid decay property (RD) of groups is preserved by graph products defined on finite simplicial graphs. 2000 Mathematics Subject Classification: 20E06, 43A15, 46L99. Key words: rapid decay, graph products, free and direct products, length functions, normal forms.

1 Introduction

The main result proved in this paper is that the graph product of finitely many groups with the rapid decay property (RD) has the same property. This is stated formally in Section 4 as Theorem 4.1.

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

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

Following Jolissaint [17], a group G is said to have RD if the operator norm ||.||_{∗} for the group algebra ℂG is bounded by a constant multiple of the Sobolev norm ||.||_{2,r,ℓ}, a norm that is a variant of the l^{2} norm weighted by a length function ℓ for G.

More precisely, RD 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} the standard l^{2} norm, and ||.||_{2,r,ℓ} the Sobolev norm of order r with respect to ℓ. So we have:

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

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

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

A brief introduction to RD is given in [2]; it is relevant to the Baum-Connes and Novikov conjectures (see an account in [22]). RD was originally studied by Jolissaint [17], after it emerged from work of Haagerup [11], who proved it for free groups. Jolissaint extended Haagerup’s methods to prove it for classical hyperbolic groups (i.e. discrete cocompact groups of isometries of hyperbolic space), and to prove that free and direct products of groups with RD inherit the property, as do subgroups; de la Harpe [14] extended Jolissaint’s arguments for classical hyperbolic groups to derive RD for word hyperbolic groups. More recently, Drutu and Sapir have shown that a group that is hyberbolic relative to a family of parabolic subgroups with RD must itself have RD [9]. In all this work the proofs focus on the factorisations of geodesic words. Other authors prove RD through examination of actions of the group [21, 2].

The graph product construction is a natural generalisation of both direct and free products. Given a finite simplicial graph Γ with a group attached to each vertex, the associated graph product is the group generated by the vertex groups with the added relations that elements of groups attached to adjacent vertices commute; the representation of such a group as a graph product of directly indecomposable groups is proved to be unique [20].

Right-angled Artin groups [3] (also known as graph groups) and right-angled Coxeter groups arise in this way, as the graph products of infinite cyclic groups and cyclic groups of order 2 respectively, and have been widely studied; some groups with rather interesting properties arise via graph products, including a group (a subgroup of a right-angled Artin group) that has FP but is not finitely presented [1] and a group (F_{2} × F_{2}) with insoluble subgroup membership problem [19]. Both right-angled Artin groups and right-angled Coxeter groups are already known to possess RD, through their actions on CAT(0) cube complexes [2] (indeed all finite rank Coxeter groups possess RD for this reason [6]).

Graph products were introduced by Green in her PhD thesis [10] where, in particular, a normal form was developed and the graph product construction was shown to preserve residual finiteness; this work was extended by Hsu and Wise in [13] where, in particular, right-angled Artin groups were shown to embed in right-angled Coxeter groups and hence to be linear. The preservation of semihyperbolicity, automaticity (as well as asynchronous automaticity and biautomaticity) and the possession of a complete rewrite system under graph products is proved in [12], necessary and sufficient conditions for the preservation of hyperbolicity in [18], the question of when the group is virtually free in [16], of orderability in [7]. Automorphisms and the structure of centralisers for graph products of groups have been the subject of recent study, and in particular graph products defined over random graphs have provoked some interest for their applications [8, 5, 4].

Our proof that the graph product construction preserves rapid decay will build on the methods used by Jolissaint for direct and free products [17]. We use a reformulation of RD due to Jolissaint, explained in Section 2 below, which compares norms on elements of ℂG with restricted support. We examine in Section 3 the geodesic decompositions of elements in a graph product, and show that they satisfy particularly useful properties, which will be applied in our proof. Section 4 states our main result, Theorem 4.1, and reduces its proof to the proof of a further technical condition, which is similar to that of Jolissaint’s reformulation, but easier to verify in the context of graph and free products; the same condition is used in [17] for free products. The remaining two sections are devoted to the proof of Proposition 4.3, thereby completing the proof of Theorem 4.1

2 A reformulation of the rapid decay property

By [17, Lemma 2.1.3], any length function ℓ on G is equivalent to one with ℓ(G) ⊆ ℕ and ℓ(g) > 0 ∀g ≠ 1. Since RD is invariant under length equivalence, by [17, Remark 1.1.7], we shall assume from now on that all length functions have this property.

Given a length function ℓ on G, and k ∈ ℕ, we define C_{k}(ℓ) to be the set {g ∈ G | ℓ(g) = k}. We write χ_{k} for the characteristic function on C_{k}, and for ϕ ∈ ℂG, we write ϕ_{k} for the pointwise product ϕ.χ_{k}.

It is proved by Jolissaint [17, Proposition 1.2.6] that RD for G is equivalent to the following condition:

(∗) There exist c, r > 0 such that ∀ϕ, ψ ∈ ℂG, k, l, m ∈ ℕ :

||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} ≤ c||ϕ_{k}||_{2,r,ℓ}||ψ_{l}||_{2} if |k − l| ≤ m ≤ k + l,
||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} = 0  otherwise.

It follows from the properties of a length function that ||(ϕ_{k} ∗ ψ_{l})_{m}||_{2} = 0 for m outside the range [|k − l|, k + l]. Hence we shall establish RD 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}.

3 Graph products

Graph products of groups are studied in detail in [10], and we shall make use of the results from that thesis. Let Γ = (V, E) be a finite simplicial graph, together with vertex groups G_{v} for each v ∈ V. The associated graph product G is defined to be the quotient of the free product of the groups G_{v} by the normal closure of all the commutators [g, g′] for which g ∈ G_{v}, g′ ∈ G_{w} and {v, w} is an edge of the graph. We write G = G(Γ; G_{v}, v ∈ V).

Given such a group G, we define K to be the set of cliques of the associated graph Γ, which we can identify with a set of subsets of the vertex set V of Γ. We define K_{m} to be the subset of K of cliques of size m. Given any subset J of V we define G_{J} to be the subgroup of G generated by the elements of its subgroups G_{v} with v ∈ J. It follows from [10, Proposition 3.31] that G_{J} is naturally isomorphic to the graph product defined by the induced subgraph of Γ with vertex set J. If J is a clique, then G_{J} is the direct product of its vertex groups.

Every element of the group G can be written as a product y_{1} ⋯ y_{k} for k ≥ 0 and with each y_{i} in a vertex group G_{v_{i}}; that is, each element of the group has a representation as a word over the set S = ∪_{v∈V} (G_{v} \ {1}). We call such a representation an expression, the elements y_{i} the syllables of the expression, and say that the expression has syllable length k; we define the syllable length of g, λ(g), to be the minimum of the syllable lengths of expressions for g, and say that an expression for g is reduced if it has syllable length λ(g). The function λ is easily seen to be a length function, but it is not the one that we shall use to prove RD.

We define Λ_{k} = {g ∈ G : λ(g) = k}.

Note that when G is a free product, every expression for which consecutive y_{i}s come from distinct vertex groups is reduced, and each reduced expression corresponds to a distinct element of G. That is not true in general. But it is proved in [10, Theorem 3.9] that any expression for g can be transformed to any reduced expression by a sequence of replacements of the form y′y → yy′ where y, y′ belong to commuting vertex groups, or y′y′′ → y, where y′y′′ = y is a relation holding between three elements of one of the vertex groups, or deletion of y′y′′ where the y′, y′′ are mutually inverse elements of a vertex group. Hence any reduced expression for an element g involves the same syllables, but the order of the syllables in the expression is not determined.

We shall need to estimate the number of factorisations of elements in graph products. For g ∈ Λ_{k+l}, we use the notation

F_{k}^{l}(g) := {(g_{1}, g_{2}) | g =_{G} g_{1}g_{2}, λ(g_{1}) = k, λ(g_{2}) = l},
F_{k}^{l} := sup_{g∈Λ_{k+l}} |F_{k}^{l}(g)|.

Similarly, given a clique J ∈ K and g ∈ Λ_{k+l+|J|}, we use the notation

F_{k}^{l}(J, g) := {(g_{1}, s, g_{2}) | g =_{G} g_{1}sg_{2}, λ(g_{1}) = k, λ(g_{2}) = l, s ∈ G_{J}, λ(s) = |J|},
F_{k}^{l}(J) := sup_{g∈Λ_{k+l+|J|}} |F_{k}^{l}(J, g)|.

By considering factorisations of g^{−1}, we see that F_{k}^{l} = F_{l}^{k} and F_{k}^{l}(J) = F_{l}^{k}(J).

Let g, h ∈ G. We say that h is a left divisor of g, if λ(g) = λ(h) + λ(h^{−1}g), or, equivalently, if h has a minimal expression v that is a prefix of a minimal expression w for g. We define right divisors similarly.

We shall need

Lemma 3.1. For each J ∈ K, F_{k}^{l}(J) is bounded by a polynomial in min(k, l).

Proof. Since F_{k}^{l}(J) = F_{l}^{k}(J), it is sufficient to prove that F_{k}^{l}(J) is bounded by a polynomial in k.

Let g ∈ Λ_{m} with m ≥ k + l, and consider factorisations g = g_{1}sg_{2} with g_{1} ∈ Λ_{k}, g_{2} ∈ Λ_{l}, and s ∈ G_{J} with λ(s) = |J|.

We start by bounding the number of left divisors g_{1} of g with g_{1} ∈ Λ_{k}. Suppose that y_{1}y_{2} ⋯ y_{m} is a reduced expression for g, with each y_{i} an element of a vertex group. Then g_{1} = y_{σ(1)} ⋯ y_{σ(k)}, where σ is a permutation of {1, …, m}. When we transform the original expression y_{1}y_{2} ⋯ y_{m} to the new expression, using shuffles, there is no need to swap any of the syllables in g_{1} among themselves, so we can assume that σ(1) ≤ σ(2) ≤ ⋯ ≤ σ(k).

Let us call the syllable y_{σ(i)} with 1 ≤ i ≤ k unconstrained if its vertex group commutes with the vertex groups of each of y_{σ(i+1)}, …, y_{σ(k)}. (In particular, y_{σ(k)} is unconstrained.)

We claim that g_{1} is uniquely determined by its unconstrained syllables y_{σ(i)} with 1 ≤ i ≤ k. To show this, suppose that g_{1}, g′_{1} ∈ Λ_{k} are left divisors of g corresponding to permutations σ, σ′ of {1, …, m}, where g_{1}, g′_{1} have the same unconstrained syllables. Suppose that g_{1} ≠ g′_{1}, and let i be maximal such that y_{σ(i)} is a syllable of g_{1} but not of g′_{1}. Then, by assumption, y_{σ(i)} is not unconstrained, so there exists j with i < j ≤ k such that y_{σ(i)} does not commute with y_{σ(j)}. By maximality of i, y_{σ(j)} is a syllable of g′_{1}. Since y_{σ(i)} and y_{σ(j)} do not commute, y_{σ(i)} must remain to the left of y_{σ(j)} after any shuffles of g. So y_{σ(i)} must be a syllable of g′_{1}, a contradiction.

If there were two unconstrained syllables in g_{1} from the same vertex group G_{v}, they could be moved together, thereby shortening the expression; hence there is at most one. Since g_{1} has syllable length k, an unconstrained syllable y_{σ(i)} in g_{1} from G_{v} must be among the first k syllables in y_{1}y_{2} ⋯ y_{m} that come from G_{v}. Hence there are k + 1 possible ways of selecting (0 or 1) syllables of y_{1}y_{2} ⋯ y_{m} from G_{v} that will be unconstrained in g_{1}. This gives (k + 1)^{|V |} choices in total for the unconstrained syllables of g_{1}, and hence (k + 1)^{|V |} choices for the left divisor g_{1}.

Similarly, we have an upper bound of (|J| + 1)^{|V |} for the number of left divisors of length |J| of g_{1}^{−1}g for a given g_{1}. In fact, the bound for the number of choices for s is (|J|+1)^{|J|}, as s ∈ G_{J}. The right divisor g_{2} is then completely determined by g, g_{1} and s. This results in the inequality F_{k}^{l}(J) ≤ (k+1)^{|V |}(|J|+1)^{|J|}, giving the required polynomial bound in k.

Lemma 3.2. Suppose that g, h_{1}, h_{2} ∈ L with g =_{G} h_{1}h_{2}, h_{1} ∈ Λ_{k}, h_{2} ∈ Λ_{l}, and g ∈ Λ_{k+l−q} with q > 0. Then h_{1} =_{G} g_{1}s_{1}w and h_{2} =_{G} w^{−1}s_{2}g_{2}, where:

(1) s_{1}, s_{2} ∈ J for some J ∈ K, and λ(s_{1}) = λ(s_{2}) = λ(s_{1}s_{2}) = |J|,

(2) q = |J| + 2λ(w).

Proof. Suppose first that there is no cancellation between h_{1} and h_{2}, that is, when we reduce the expression h_{1}h_{2}, no syllable becomes equal to the identity. Then pick a right divisor s_{1} of h_{1}, and a left divisor s_{2} of h_{2}, both minimal with respect to syllable length, such that λ(s_{1}s_{2}) = λ(s_{1}) + λ(s_{2}) − q. Minimality ensures that every syllable of s_{1} (or s_{2}) must merge without cancelling with a symbol of s_{2} (or s_{1}). So λ(s_{1}) = λ(s_{2}) = λ(s_{1}s_{2}), the syllables within each of s_{1} and s_{2} must commute, and there is a clique J ⊂ Γ of size q such that s_{1}, s_{2}, s_{1}s_{2} ∈ G_{J}.

If there is cancellation between h_{1} and h_{2}, then we can find a right divisor w of h_{1} such that w^{−1} is a left divisor of h_{2}. We choose w of maximal syllable length, so that h_{1} = h′_{1}w and h_{2} = w^{−1}h′_{2} for some h′_{1}, h′_{2} ∈ G, and no cancellation occurs between h′_{1} and h′_{2}. Applying the above argument to h′_{1} and h′_{2}, we find a clique J of size q − 2λ(w), a right divisor s_{1} of h′_{1}, and a left divisor s_{2} of h′_{2}, with λ(s_{1}) = λ(s_{2}) = λ(s_{1}s_{2}) = |J|.

4 Main result

We prove

Theorem 4.1. Suppose that G = G(Γ; G_{v}, v ∈ V) is a graph product of groups defined with respect to a finite simplicial graph Γ = (V, E), and suppose that each vertex group G_{v} satisfies RD. Then G satisfies RD.

The proof generalises Jolissaint’s proof in [17] of RD for free products, which is itself a generalisation of Haagerup’s proof for free groups. We use the result of [17, Lemma 2.1.2], which implies (although it is not stated explicitly) that RD is preserved by taking direct products, and rely on the existence of polynomial bounds relating to factorisation in graph products proved in Lemma 3.1 and Lemma 3.2.

The following easy consequence of the Cauchy-Schwarz inequality will be used frequently.

Lemma 4.2. For any positive integer M and real numbers a_{1}, …, a_{M},

(∑_{i=1}^{M} a_{i})^{2} ≤ M (∑_{i=1}^{M} a_{i}^{2}) .

The proof of Theorem 4.1 that follows depends on Proposition 4.3, which is stated within the proof; we defer the proof of that to Section 6.

Proof of Theorem 4.1: For each v ∈ V we choose a length function ℓ_{v} on G_{v} with respect to which G_{v} has rapid decay. Then, given g ∈ G and a reduced expression g = y_{1} ⋯ y_{k} for G, with y_{j} ∈ G_{v_{j}}, we define

ℓ(g) = ∑_{j=1}^{k} ℓ_{v_{j}}(y_{j}).

That ℓ is both well defined and a length function follows easily from [10, Theorem 3.9]. On subgroups G_{J} with J ∈ K, we see that ℓ restricts to ℓ_{J}, defined in the same way as a sum of functions ℓ_{v_{j}} with v_{j} ∈ J; it follows from [17, Lemma 2.1.2] that G_{J} satisfies RD with respect to ℓ_{J}.

We prove rapid decay with respect to the length function ℓ by verifying the condition (∗∗) of Section 2. But rather than prove that directly we shall deduce it from a condition on the length function λ, that is stated as Proposition 4.3.

Recall that Λ_{k} is defined as the set {g ∈ G : λ(g) = k}. We now define χ_{(k)} to be the characteristic function on Λ_{k} and ϕ_{(k)} to be the pointwise product ϕ.χ_{(k)}. In general a function labelled with the subscript (k) is understood to have support on Λ_{k}.

We shall prove the following in Section 6.

Proposition 4.3. ∃ c, r > 0 such that for all ϕ, ψ ∈ ℂG, k, l, m ∈ ℕ, and |k − l| ≤ m ≤ k + l,

||(ϕ_{(k)} ∗ ψ_{(l)})_{(m)}||_{2} ≤ c||ϕ_{(k)}||_{2,r,ℓ}||ψ_{(l)}||_{2}.

To derive our main result from this proposition, we shall use it to deduce the condition (∗∗) of Section 2, that is, we shall deduce the similar condition in which restrictions to Λ_{k}, Λ_{l}, Λ_{m} are replaced by restrictions to C_{k}, C_{l}, C_{m}. (But note that both of the length functions λ and ℓ are involved in the proposition statement.) Jolissaint’s proof of RD for free products follows exactly the same strategy, and the argument below is basically his, with some slight modification of notation to match our own. We suppose that k, l, m are fixed in the appropriate range. We write ϕ′ rather than ϕ_{k} and ψ′ rather than ψ_{l}, to make our notation less cumbersome.

Since ℓ(g) ≥ 1 for all g ∈ G \ {1}, we have C_{k} ⊆ ∪_{j=0}^{k}Λ_{j} and C_{l} ⊆ ∪_{i=0}^{l}Λ_{i}, and hence ϕ′ = ∑_{j=0}^{k} ϕ′_{(j)}, ψ′ = ∑_{i=0}^{l} ψ′_{(i)}. Similarly, for fixed j, we have |(ϕ′_{(j)} ∗ ψ′)_{m}(g)| ≤ | ∑_{p=0}^{m}(ϕ′_{j} ∗ ψ′)_{(p)}(g)|, for all g ∈ G. (Note that we dropped the restriction to C_{m} on the right hand side of this inequality.) Hence

||(ϕ′_{(j)} ∗ ψ′)_{m}||_{2}^{2} ≤ ∑_{p=0}^{m} ||(ϕ′_{(j)} ∗ ψ′)_{(p)}||_{2}^{2}.

Now, in any product of group elements g_{1}g_{2} = g with g_{1} ∈ Λ_{i}, g_{2} ∈ Λ_{j}, g ∈ Λ_{p}, we must have p ≤ i + j, i ≤ p + j, j ≤ p + i. Hence in each of the terms (ϕ′_{(j)} ∗ ψ′)_{(p)} in the sum on the right hand side of the above inequality, for fixed j and p, the support of ψ′ lies in the union of the Λ_{i} with |j − p| ≤ i ≤ j + p, and so

∑_{p=0}^{m} ||(ϕ′_{(j)} ∗ ψ′)_{(p)}||_{2}^{2} ≤ ∑_{p=0}^{m} || ∑_{i=|j−p|}^{j+p}(ϕ′_{(j)} ∗ ψ′_{(i)})_{(p)}||_{2}^{2}

Since there are at most 2j + 1 values of i in each of the ranges [|j − p|, j + p], we can use Lemma 4.2 to bound the right hand side above by

(2j + 1) ∑_{p=0}^{m} ∑_{i=|j−p|}^{j+p} ||(ϕ′_{(j)} ∗ ψ′_{(i)})_{(p)}||_{2}^{2}.

It follows from Proposition 4.3 that, for |j − i| ≤ p ≤ j + i,

||(ϕ′_{(j)} ∗ ψ′_{(i)})_{(p)}||_{2} ≤ c||ϕ′_{(j)}||_{2,r,ℓ}||ψ′_{(i)}||_{2}.

For other values of p, the left hand side is zero. Hence

||(ϕ′_{(j)} ∗ ψ′)_{m}||_{2}^{2} ≤ c^{2}(2j + 1)||ϕ′_{(j)}||_{2,r,ℓ}^{2} ∑_{p=0}^{m} ∑_{i=|j−p|}^{j+p} ||ψ′_{(i)}||_{2}^{2}.

Since |i − j| ≤ p ≤ i + j, for a given value of i, there are at most 2j + 1 values of p in the above summation, and so we have

||(ϕ′_{(j)}∗ψ′)_{m}||_{2}^{2} ≤ c^{2}(2j+1)^{2}||ϕ′_{(j)}||_{2,r,ℓ}^{2} ∑_{i=0}^{j+m} ||ψ′_{(i)}||_{2}^{2} ≤ c^{2}(2j+1)^{2}||ϕ′_{(j)}||_{2,r,ℓ}^{2}||ψ′||_{2}^{2}.

Now, using the triangle inequality together with Lemma 4.2 again, we have

||(ϕ_{k} ∗ ψ_{l})_{m}||_{2}^{2} = ||(ϕ′ ∗ ψ′)_{m}||_{2}^{2} ≤ (∑_{j=0}^{k} ||ϕ′_{(j)} ∗ ψ′)_{m}||)^{2}

≤ (k + 1) ∑_{j=0}^{k} ||(ϕ′_{(j)} ∗ ψ′)_{m}||^{2}

≤ c^{2}(k + 1) ∑_{j=0}^{k}(2j + 1)^{2}||ϕ′_{(j)}||_{2,r,ℓ}^{2}||ψ′||_{2}^{2}
≤ c^{2}(k + 1)(2k + 1)^{2}||ϕ_{k}||_{2,r,ℓ}^{2}||ψ_{l}||_{2}^{2}
= P (k)||ϕ_{k}||_{2}^{2}||ψ_{l}||_{2}^{2},

where the polyonomial P has degree 3 + 2r. So we have deduced (∗∗).

The proof of the theorem will be complete once Proposition 4.3 is proved. □

5 Technicalities of the proof of Proposition 4.3

In an attempt to make the proof of Proposition 4.3 more readable we start with some technical results and definitions.

For a function ϕ_{(k)} and p ≥ 0, we can define functions ϕ_{(k−p)}^{(p)} and ^{(p)}ϕ_{(k−p)} by

ϕ_{(k−p)}^{(p)}(u) = \{ \begin{matrix}\sqrt{∑_{w∈Λ_{p}} |ϕ_{(k)}(uw)|^{2}} & if u ∈ Λ_{k−p} \\ 0 & otherwise \end{matrix}

(p)ϕ_{(k−p)}(u) = \{ \begin{matrix}\sqrt{∑_{w∈Λ_{p}} |ϕ_{(k)}(w^{−1}u)|^{2}} & if u ∈ Λ_{k−p} \\ 0 & otherwise \end{matrix}

Note that these functions are non-negative real-valued; we shall sometimes make use of that fact as we bound sums.

Lemma 5.1.

||ϕ_{(k−p)}^{(p)}||_{2}^{2} ≤ F_{k−p}^{p}||ϕ_{(k)}||_{2}^{2} and ||^{(p)}ϕ_{(k−p)}||_{2}^{2} ≤ F_{k−p}^{p}||ϕ_{(k)}||_{2}^{2}.

Proof.

||ϕ_{(k−p)}^{(p)}||_{2}^{2} = ∑_{u∈Λ_{k−p}} ∑_{w∈Λ_{p}} |ϕ_{(k)}(uw)|^{2}
≤ F_{k−p}^{p} ∑_{h∈Λ_{k}} |ϕ_{(k)}(h)|^{2}
= F_{k−p}^{p}||ϕ_{(k)}||_{2}^{2}

The second inequality follows similarly, since F_{k−p}^{p} = F_{p}^{k−p}.

For 0 ≤ i ≤ k and g ∈ Λ_{k−i}, we define functions ϕ_{(i)}^{g} and ^{g}ϕ_{(i)} by

ϕ_{(i)}^{g}(v) = \{ \begin{matrix}ϕ_{(k)}(vg) & if vg ∈ Λ_{k} \\ 0 & otherwise \end{matrix}
gϕ_{(i)}(v) = \{ \begin{matrix}ϕ_{(k)}(gv) & if gv ∈ Λ_{k} \\ 0 & otherwise \end{matrix}

6 Proof of Proposition 4.3

Proof. First we deal with the case where m = k + l. By Lemma 4.2, for each g ∈ Λ_{k+l} we have

|ϕ_{(k)} ∗ ψ_{(l)}(g)|^{2} = | ∑_{(h_{1},h_{2})∈F_{k}^{l}(g)} ϕ_{(k)}(h_{1})ψ_{(l)}(h_{2})|^{2}
≤ F_{k}^{l} ∑_{(h_{1},h_{2})∈F_{k}^{l}(g)} |ϕ_{(k)}(h_{1})|^{2}|ψ_{(l)}(h_{2})|^{2}.

Hence

||(ϕ_{(k)} ∗ ψ_{(l)})_{(k+l)}||_{2}^{2} ≤ F_{k}^{l} ∑_{g∈Λ_{k+l}} ∑_{(h_{1},h_{2})∈F_{k}^{l}(g)} |ϕ_{(k)}(h_{1})|^{2}|ψ_{(l)}(h_{2})|^{2}
≤ F_{k}^{l} ∑_{h_{1}∈Λ_{k},h_{2},∈Λ_{l}} |ϕ_{(k)}(h_{1})|^{2}|ψ_{(l)}(h_{2})|^{2}
= F_{k}^{l} ∑_{h_{1}∈Λ_{k}} |ϕ_{(k)}(h_{1})|^{2} ∑_{h_{2}∈Λ_{l}} |ψ_{(l)}(h_{2})|^{2}
= F_{k}^{l}||ϕ_{(k)}||_{2}^{2}||ψ_{(l)}||_{2}^{2},

which proves (∗∗). So now suppose that m = k + l − q, for q > 0, and that g ∈ Λ_{k+l−q}. By Lemma 3.2, for each factorisation of g as a product h_{1}h_{2} with h_{1} ∈ Λ_{k}, h_{2} ∈ Λ_{l}, there is a 5-tuple (g_{1}, g_{2}, s_{1}, s_{2}, w) of elements with syllable lengths k − q + p, l − q + p, q − 2p, q − 2p, p, for which h_{1} = g_{1}s_{1}w, h_{2} = w^{−1}s_{2}g_{2}, s := s_{1}s_{2} ∈ G_{J} has syllable length q − 2p, and s_{1}, s_{2}, s are all elements of G_{J} for some J ∈ K_{q−2p}.

For ease of notation we now define, for s ∈ G_{J},

F(J, s) := {(s_{1}, s_{2}) ∈ G_{J} × G_{J} : s = s_{1}s_{2}},
F_{J}(J, s) := {(s_{1}, s_{2}) ∈ G_{J} × G_{J} : s = s_{1}s_{2}, λ(s_{1}) = λ(s_{2}) = |J|}.

Now for any g ∈ Λ_{k+l−q}, |ϕ_{(k)} ∗ ψ_{(l)}(g)| is bounded above by

∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}(g_{1}, s, g_{2}) ∈ \\ F_{k−q+p}^{l−q+p}(J, g) \end{matrix}} ∑_{(s_{1},s_{2})∈F(J,s)} ∑_{w∈Λ_{p}} |ϕ_{(k)}(g_{1}s_{1}w)ψ_{(l)}(w^{−1}s_{2}g_{2})|,

by the triangle inequality.

By Cauchy-Schwarz

∑_{w∈Λ_{p}} |ϕ_{(k)}(g_{1}s_{1}w)ψ_{(l)}(w^{−1}s_{2}g_{2})| ≤ \sqrt{∑_{w∈Λ_{p}} |ϕ_{(k)}(g_{1}s_{1}w)|^{2}}\sqrt{∑_{w∈Λ_{p}} |ψ_{(l)}(w^{−1}s_{2}g_{2})|^{2}}

= ϕ_{(k−p)}^{(p)}(g_{1}s_{1}) ×^{(p)}ψ_{(l−p)}(s_{2}g_{2})
= ^{g_{1}}ϕ_{(q−2p)}^{(p)}(s_{1}) ×^{(p)}ψ_{(q−2p)}^{g_{2}}(s_{2}).

Further,

∑_{(s_{1},s_{2})∈F_{J} (J,s)} ^{g_{1}}ϕ_{(q−2p)}^{(p)}(s_{1}) ×^{(p)}ψ_{(q−2p)}^{g_{2}}(s_{2}) ≤ ^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}(s),

where the convolution here is over G_{J}, not over G.

Then we apply the Lemma 4.2 to see that

|ϕ_{(k)} ∗ ψ_{(l)}(g)|^{2} ≤ ( ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}(g_{1}, s, g_{2}) ∈ \\ F_{k−q+p}^{l−q+p}(J, g) \end{matrix}} ^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}(s))^{2}

≤ MF(k, q, l) ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}(g_{1}, s, g_{2}) ∈ \\ F_{k−q+p}^{l−q+p}(J, g) \end{matrix}} (^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}(s))^{2} .

where MF(k, q, l) := ∑_{p=1}^{⌊q/2⌋} ∑_{J∈K_{q−2p}} F_{k−q+p}^{l−q+p}(J) is bounded by Q(k) for some polynomial Q, by Lemma 3.1, and since there are finitely many possible cliques J. Hence

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

≤ Q(k) ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}g_{1} ∈ Λ_{k−q+p} \\ s ∈ G_{J} , \\ g_{2} ∈ Λ_{l−q+p} \end{matrix}} (^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}(s))^{2}

= Q(k) ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}g_{1} ∈ Λ_{k−q+p} \\ g_{2} ∈ Λ_{l−q+p} \end{matrix}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}})||_{2;G_{J}}^{2} .

But now, since RD holds with respect to ℓ_{J} in each of the groups G_{J}, we have

||^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} ≤ c_{J}^{2}||^{g_{1}}ϕ_{(q−2p)}^{(p)}||_{2,r_{J} ,ℓ_{J};G_{J}}^{2} ||^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} .

We deduce easily from this that

∑_{\begin{matrix}g_{1} ∈ Λ_{k−q+p}, \\ g_{2} ∈ Λ_{l−q+p} \end{matrix}} ||^{g_{1}}ϕ_{(q−2p)} ∗ ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} ≤ c_{J}^{2} ∑_{g_{1}∈Λ_{k−q+p}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)}||_{2,r_{J} ,ℓ_{J};G_{J}}^{2} ×

∑_{g_{2}∈Λ_{l−q+p}} ||^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} .

Then, for c = max c_{J} and r = max r_{J}, we have

∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}g_{1} ∈ Λ_{k−q+p} \\ g_{2} ∈ Λ_{l−q+p} \end{matrix}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)} ∗^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2}

≤ c^{2} ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ( ∑_{g_{1}∈Λ_{k−q+p}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)}||_{2,r_{J} ,ℓ_{J};G_{J}}^{2} ∑_{g_{2}∈Λ_{l−q+p}} ||^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} )

≤ c^{2} ( ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{g_{1}∈Λ_{k−q+p}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)}||_{2,r,ℓ_{J};G_{J}}^{2} ) ×

( ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{g_{2}∈Λ_{l−q+p}} ||^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} ) .

But

∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{g_{1}∈Λ_{k−q+p}} ||^{g_{1}}ϕ_{(q−2p)}^{(p)}||_{2,r,ℓ_{J};G_{J}}^{2}

= ∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{\begin{matrix}g_{1} ∈ Λ_{k−q+p}, \\ s ∈ G_{J} \\ w ∈ Λ_{p} \end{matrix}} |ϕ_{(k)}(g_{1}sw)|^{2}(1 + ℓ_{J}(s))^{2r}.

Since ⌊q/2⌋ ≤ k and the number of sets J is bounded, Lemma 3.1 implies that the number of factorisations of a fixed g′ ∈ Λ_{k} as g_{1}sw in the above sum is at most P (k) for some polynomial P. So the sum is bounded above by

P (k) ∑_{g′∈Λ_{k}} |ϕ_{(k)}(g′)|^{2}(1 + ℓ(g′))^{2r} = P (k)||ϕ_{(k)}||_{2,r,ℓ}^{2},

and similarly

∑_{\begin{matrix}p = 1, \\ J ∈ K_{q−2p} \end{matrix}}^{p=⌊q/2⌋} ∑_{g_{2}∈Λ_{l−q+p}} ||^{(p)}ψ_{(q−2p)}^{g_{2}}||_{2;G_{J}}^{2} ≤ P (k)||ψ_{(l)}||_{2}^{2}.

Hence

||(ϕ_{(k)} ∗ ψ_{(l)})_{(m)}||_{2}^{2} ≤ c^{2}Q(k)P (k)^{2}||ϕ_{(k)}||_{2,r,ℓ}^{2}||ψ_{(l)}||_{2}^{2}
≤ c^{2}||ϕ_{(k)}||_{2,r+deg(Q)+2 deg(P),ℓ}^{2}||ψ_{(l)}||_{2}^{2},

where the final inequality uses the fact that k ≤ ℓ(g) for all g ∈ Λ_{k}. This completes the proof of Proposition 4.3.

Acknowledgments

The first author was partially supported by the Marie Curie Reintegration Grant 230889. The third author would like to thank the Mathematics Departments of the Universities of Fribourg and Neuchâtel, Switzerland, for their hospitality and generous support.

References

[1] M.Bestvina and N.Brady, Morse theory and finiteness properties of groups, Invent. Math. 129 (1997) 445–470.

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

[3] R. Charney, An introduction to right-angled Artin groups, Geom. Dedicata 127 (2007) 141–158.

[4] R. Charney and M. Farber, Random groups arising as graph products, preprint

[5] R. Charney, K. Ruane, N. Stambaugh, A. Vijayan, The automorphism group of a graph product with no SIL, Illinois J. Math 54 (2010) 249–262.

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

[7] I. Chiswell, Ordering graph products of groups, preprint.

[8] A. Costa and M. Farber, Topology of random right-angled Artin groups, preprint 2009

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

[10] Elizabeth Green, Graph products of groups, Ph D thesis, University of Leeds, 1990.

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

[12] S. Hermiller and J. Meier, Algorithms and geometry for graph products of groups, J. Algebra,171 (1995), no. 1, 230-257.

[13] T. Hsu and D. Wise, On linear and residual properties of graph products, Michigan Math. J. 46 (1999) 251–259.

[14] P. de la Harpe, Groupes hyperboliques, algèbres d’opérateurs et un théorème de Jolissaint, Comptes Rendus des Séances de l’Académie des Sciences. Série I. Mathématique, 307, 1988 (14), 771–774.

[15] S.P. Humphries, On representation of Artin groups and the Tits conjecture J. Alg. 169 (1994) 847–862.

[16] M. Lohrey and G. Senizergues, When is a graph product of groups virtually free? Comm. Alg 35 (2007) 617–621.

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

[18] J. Meier, When is the graph product of hyperbolic groups hyperbolic?, Geom. Dedicata 61 (1996), 29–41.

[19] K.A. Mihailova, The occurrence problem for direct products of groups (Russian), Dokl. Akad. Nauk. SSSR 119 (1958) 1103–1105.

[20] D. Radcliffe, Rigidity of graph products of groups, Alg. Geom. Top 3 (2003) 1979-1088.

[21] J.Ramagge, G.Robertson and T.Steger, A Haagerup inequality for Ã_{2} ×Ã_{1} and Ã_{2} buildings, GAFA 8 (1988), 702–731.

[22] 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 Verlag, Basel, 2002. x+104 pp. ISBN: 3-7643-6706-7.

L. Ciobanu, Mathematics Department, University of Fribourg, Chemin du Museé 23, CH-1700 Fribourg, Switzerland

E-mail address: Laura.Ciobanu@unifr.ch

D. F. Holt, Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK

E-mail address: Derek.Holt@wwarwick.ac.uk

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

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