Metrics on diagram groups and uniform embeddings in a Hilbert space

METRICS ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS IN A HILBERT SPACE G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR Abstract. We give first examples of finitely generated groups having an intermediate, with values in (0,1), Hilbert space compression (which is a numerical parameter measuring the distortion required to embed a metric space into Hilbert space). These groups include certain diagram groups. In particular, we show that the Hilbert space compression of Richard Thompson’s group Fis equal to 1/2, the Hilbert space compression of ZoZis between 1/2 and 3/4, and the Hilbert space compression of Zo(ZoZ) is between 0 and 1/2. In general, we find a relationship between the growth of Hand the Hilbert space compression of ZoH. 1. Introduction The study of uniform embeddings of metric spaces into Hilbert space was initiated by Gromov. Definition 1.1. Let (Γ, d) be a metric space. Let Hbe a separable Hilbert space. A map f: Γ → H is said to be a uniform embedding [8] if there exist non-decreasing functions ρ1,ρ2from [0,∞) to itself such that (1) ρ1(d(x, y)) ≤ kf(x)−f(y)kH≤ρ2(d(x, y)) for all x, y ∈Γ; (2) limr→+∞ρi(r) = +∞for i= 1,2. Gromov suggested that a finitely generated group G(viewed as a metric space with a word length metric) uniformly embeddable into Hilbert space should satisfy the Novikov Conjecture [9, page 67]. That was proved in [27], see also [25, 18]. 1991 Mathematics Subject Classification. 20F65. Key words and phrases. Richard Thompson’s group F, diagram groups, Hilbert space compression, subgroup distortion. The work of the first two authors has been supported by the Swiss National Science Foundation, No. PP002-68627. They also acknowledge the hospitality of the Centre de Recerca Matem`atica (Barcelona) during autumn 2004. The work of the third author has been supported in part by the NSF grant DMS 0245600. 1 2 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR Guoliang Yu introduced a Følner-type condition on finitely generated groups G, called property A, which is a weak form of amenability and which guaranties the existence of a uniform embedding of the metric space into Hilbert space [27]. That property is interesting in itself because it turned out to be equivalent to the exactness of G, and to the existence of an amenable action of Gon a compact space (see [26] for a detailed discussion of property A). Among “classical” groups for which property A has not been proved so far, is the R. Thompson group F, which is the group of all piecewise linear orientation preserving self-homeomorphisms of the unit interval with finitely many dyadic singularities and all slopes integer powers of 2. It is not known whether Fis amenable or not, so the question about a weak amenability is interesting. It is worth noticing that, by a result of Niblo and Reeves, a group acting properly and cellularly by isometries on a CAT(0) cubical complex has the Haagerup property [23]. In particular, by a result of Farley [7], this holds for diagram groups over finite semigroup presentations. Moreover, this holds for all countable diagram groups because they can be embedded into a certain “universal” diagram group [14] . It follows immediately from the definition of the Haagerup property that such a group can be embedded uniformly into Hilbert space. However, the interaction between the Haagerup property and Guoliang Yu’s property A is rather complicated [5, Ch. 1.3], [17, 25]. Notice that amenable groups satisfy both the Haagerup property and property A. Ghas property A =⇒Gis uniformly embedded into ~ w w?Hilbert space ~ w w Gis a countable =⇒Gacts properly and =⇒Ghas Haagerup diagram group cellularly by isometries property on a CAT(0) cubical complex Guentner and Kaminker [17] introduced a natural quasi-isometry invariant of a group that shows how close to a quasi-isometry can a uniform embedding of a group into a Hilbert space be. Definition 1.2. (cf.[17, Def. 2.2]) The Hilbert space compression of a finitely generated discrete group Gis the number R(G), which is the supremum of all α≥0 for which there exists a uniform embedding of Ginto a METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 3 Hilbert space with ρ1(n) = Cnαwith a constant C > 0 and linear ρ2(see Definition 1.1). By [17], Hilbert space compression strictly greater than 1/2 implies property A. Any group that is not uniformly embeddable into a Hilbert space (such groups exist by [10]) has Hilbert space compression 0. It is proved in [17] that free groups have Hilbert space compression 1 (although there are no quasi-isometric embeddings of a free group of rank >1 into a Hilbert space [2, 21]1). More generally, by Campbell and Niblo [4], any discrete group acting properly, co-compactly on a finite dimensional CAT(0) cubical complex has Hilbert space compression 1. Note that till now there were no examples of groups with compression strictly between 0 and 1. One of our main results is the following. Theorem 1.3. The Hilbert space compression of R. Thompson’s group F equals 1/2. In particular, this shows that the result by Guentner and Kaminker on groups with compression strictly greater than 1/2 cannot be applied to F. However, one can extract a stronger fact from [17]. Suppose that a finitely generated group Ghas a uniform embedding into Hilbert space with linear ρ2(n) and ρ1À√n(i.e. limn→∞ ρ1(n)/√n=∞). The proof of [17, Theorem 3.2] shows that property A holds for Gin this case. For R. Thompson’s group Fwe actually show that ρ1≤C√nlog nfor some constant C. Question 1.4. Is it true that there exists a uniform embedding of Finto Hilbert space with linear ρ2and ρ1À√n? If the answer is positive, then Fhas property A. It is known [11, 13, 7] that geometric properties of Fare better understood when Fis considered as a diagram group. Recall that a diagram group is the fundamental group of the space of positive paths on a directed 2-complex [14] (an equivalent definition in terms of semigroup presentations from [11] is given below). For example, Fis the diagram group of the dunce hat considered as a directed 2-complex with one vertex, one edge xand one directed cell x=x2. Our interest in uniform embeddings for diagram groups was stimulated in part by a connection with certain metric properties of diagram groups which have been studied independently before. Recall that elements of a diagram group Gcan be represented by diagrams, which are plane cellular 1We thank D. Sonkin for bringing these papers to our attention. 4 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR complexes subdivided into a number of regions (cells). This allows one to introduce a canonical diagram metric distdon Gsuch that the distd(g1, g2) is the number of cells in the diagram with minimal number of cells representing the element g−1 1g2. This metric is left invariant. It is proper provided the corresponding directed 2-complex (semigroup presentation) is finite or when the diagram group is finitely generated. It is known (this is proved in Burillo [3] using a different terminology) that for the R. Thompson group Fconsidered as a diagram group of the dunce hat, the diagram metric is bi-Lipschitz equivalent to the word metric. We say that a finitely generated diagram group satisfies property B if its diagram metric is bi-Lipschitz equivalent to the word metric. Theorem 1.5. ] The Hilbert space compression of a finitely generated diagram group with property B is at least 1/2. Question 1.6. Do all finitely generated diagram groups satisfy property B? We think that is a very interesting question. In [11, 14], it is proved that there are (finitely presented) diagram groups containing all countable diagram groups as subgroups. Such diagram groups are called universal. One of these diagram groups (in this paper it is denoted by U) corresponds to the semigroup presentation hx, a |x2=x3, ax =ai. Theorem 1.7. The universal diagram group Usatisfies property B. Notice that Theorem 1.7 does not imply (at least directly) a positive answer to Question 1.6. Indeed, Ucontains the direct product G=F2×F2 of two free groups of rank 2 (which is a countable diagram group). By a result of Mikhailova [22], the group Gcontains a non-recursively distorted subgroup H. Hence the word metric on a diagram group may not be equivalent to the metric induced by the embedding of Hinto U. Certainly Theorem 1.7 implies that all undistorted subgroups of Usatisfy property B. Clearly the diagram metric on a finitely generated diagram group does not exceed a constant times the word metric. An easy argument shows that for any finitely generated diagram group, there exists a recursive function f(n) such that the word metric does not exceed f(distd). Besides the R. Thompson group F, the restricted wreath product ZoZis another typical representative of the class of diagram groups. It corresponds to the presentation ha, b, b1, b2, c |ab =a, bc =c, b =b1, b1=b2, b2=bi [13]. It also satisfies property B. Hence Theorem 1.5 can be applied. The group ZoZis amenable, so it satisfies property A, but the next theorem shows that the compression of that group is not 1. METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 5 Theorem 1.8. The Hilbert space compression of the restricted wreath product ZoZbelongs to [1/2,3/4]. Question 1.9. What is the Hilbert space compression of ZoZ? Finally we prove the following general result. Theorem 1.10. Let Hbe a finitely generated group with a super-polyno- mial growth function. Then the Hilbert space compression of ZoHis at most 1/2. This theorem immediately implies Corollary 1.11. The Hilbert space compression of the group Zo(ZoZ)is at most 1/2. Note that the group Zo(ZoZ) is amenable and so it satisfies property A. Thus property A does not imply that Hilbert space compression is bigger than 1/2. It is not known whether Zo(ZoZ) is a diagram group (the most probable answer seems to be negative). Thus Theorem 1.5 does not apply and we do not know if the Hilbert space compression of this group is exactly 1/2. Question 1.12. What is the Hilbert space compression of the group Zo (ZoZ)? Are there amenable groups with Hilbert space compression 0 or arbitrary close to 0? Finally, we would like to mention that our proof of Theorem 1.5 yields actually a stronger result. Namely, a lower bound on the the equivariant Hilbert space compression RG(G) which is the Hilbert space compression defined by restricting to G-equivariant uniform embeddings of Ginto Hilbert spaces equiped with actions of Gby affine isometries [17, Section 5]. Theorem 1.13. The equivariant Hilbert space compression of a finitely generated diagram group with property B is at least 1/2. The estimate 1/2 cannot be improved since RG(G)>1/2 implies amenability [17] and there are non-amenable diagram groups with property B 2. Moreover, one can see from the proof that the diagram metric of a finitely generated diagram group is a conditionally negative definite function on the group. Recall that a function ψ:G→R, satisfying ψ(g) = ψ(g−1) is said to be conditionally negative definite if Pψ(gig−1 j)cicj≤0 for all n∈Nand g1, . . . , gn∈G, c1, . . . , cn∈Rsuch that Pci= 0. The existence of a continious conditionally negative definite function ψ:G→[0,∞) with limg→∞ ψ(g) = ∞is equivalent to the a-T-menability [1], hence to the Haagerup approximation property [5]. For more applications see [16] and references therein. 2We thank Y. de Cornulier for this remark. 6 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR 2. Preliminary information about diagram groups 2.1. Diagram groups. Let us briefly recall the concept of a diagram group and some terminology from this area. Details can be found in [11]. For the reasons of the present paper, it is enough to use the definition in terms of semigroup presentations given in [11] rather than an equivalent definition from [14]. Let Xbe an alphabet. We denote by X∗the set of all words over Xand by X+the set of all nonempty words. The length of a word wis denoted by |w|. Let P=hX| Ri be a semigroup presentation. Here Rconsists of ordered pairs of nonempty words over X. We always assume that if (u, v)∈ R, then (v, u)/∈ R. A triple of the form (p, u =v, q) is called an atomic 2-path, where p, q ∈ X∗, (u, v)∈ R∪R−1. The following labelled plane graph is called an atomic diagram (over P): s s s s p u q v Here each segment labelled by a word wis subdivided into |w|edges labelled by the letters of w. (Segments have a left-to-right orientation.) Notice that each atomic diagram has the top path (in our case it is labelled by puq) and the bottom path (labelled by pvq). This atomic diagram is defined uniquely by a 2-path (p, u =v, q) so we will often use this notation for the atomic diagram itself. Suppose that we have a sequence ∆1, . . . , ∆kof atomic diagrams. Let us consider the case when the bottom label of each ∆i(1 ≤i<k) coincides with the top label of ∆i+1. We can thus identify the bottom path of ∆iwith the top path of ∆i+1 (1 ≤i < k) to obtain the new labelled plane graph denoted by ∆ := ∆1◦ ··· ◦ ∆k(the concatenation of the above atomic diagrams). One can naturally define the top path (which will be the top path of ∆1) and the bottom path (the bottom path of ∆k) of ∆. For every word w∈X+, we define the trivial diagram denoted by ε(w), which is the interval labelled by w. Its top and bottom paths coincide with itself. METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 7 Definition 2.1. Adiagram ∆over a semigroup presentation Pis either a trivial diagram, or a concatenation of atomic diagrams over P. The diagrams are considered identical whenever they are isotopic as labelled plane graphs. For a diagram ∆, its top and bottom paths will be denoted by d∆eand b∆c, respectively. They start at the same vertex denoted by ι(∆) and end at the same vertex denoted by τ(∆). The diagram itself is situated “between” its top and bottom paths. If w0is the label of the top path of ∆ and w00 is the label of its bottom path, then we say that ∆ is a (w0, w00)-diagram. Given two diagrams ∆0and ∆00, one can define their concatenation denoted by ∆0◦∆00, provided the labels of b∆0cand d∆00ecoincide. For every word w∈X+, the set of all (w, w)-diagrams over Pforms a monoid with ε(w) as a unit. For any diagram ∆, by ∆−1we denote the mirror image of ∆ with respect to the axis connecting ι(∆) and τ(∆)). Clearly, the top (bottom) path of ∆ becomes the bottom (top) path of ∆−1. Here is an example of two diagrams over hx|x3=x2i: s s s s s s s s sssss ss ss s s ss s ss The label of each edge of these diagrams is x. Notice that each cell in a diagram can be considered as a diagram itself. If the cell corresponds to a relation u=v, we shall denote this diagram by (u=v). Let ∆ be a diagram over P. Suppose that it contains a pair of cells π0,π00 such that the bottom path of π0coincides with the top path of π00 and the top label of π0equals the bottom label of π00. In this case we say that the cells π0and π00 form a dipole in ∆. One can define the operation of removing the dipole. Namely, given a dipole formed by π0,π00, we first remove the common boundary of these cells and then glue dπ0ewith bπ00c(the paths we glue have the same label). We get a new diagram over Pthat has fewer cells. Proceeding in such a way, we get to a diagram that has no dipoles, called a reduced diagram. Kilibarda [19, 20] proved that the process of cancelling dipoles in diagrams is confluent, that is, the result does not depend on the order in 8 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR which we remove the dipoles. Two diagrams are called equivalent if the corresponding reduced diagrams are the same. For every word w∈X+, the set of all reduced (w, w)-diagrams with operation “concatenation followed by removing all dipoles” is a group [11, Lemma 5.2], denoted by D(P, w). Definition 2.2. The group D(P, w) is called a diagram group over a semigroup presentation Pwith base w. Example 1.[11, Ex. 6.4] The diagram group D(P, x) over the semigroup presentation P=hx|x2=xiwith base xis R. Thompson’s group Fthat has the following group presentation: hx0, x1, x2, . . . |xjxi=xixj+1 (j > i)i. There is one more important binary operation on diagrams. Given two diagrams ∆1, ∆2over P, one can identify τ(∆1) and ι(∆2). This gives a new diagram over Pdenoted by ∆1+ ∆2. This operation is associative but not commutative. 2.2. Universal diagram groups. In [14], Guba and Sapir found finitely presented diagram groups each of which contains every countable diagram group as a subgroup. Such diagram groups are called universal. For instance, the diagram group U=D(P, a), where P=hx, a |x3=x2, ax =ai is universal. It has the following Thompson-like group presentation: hx0, x1, x2, . . . |xjxi=xixj+1 (j−i > 1) i. It is easy to see that Ucan be generated by x0,x1,x2. Indeed, xn=xxn−2 0 2 for all n≥3 (ab=b−1ab by definition). (In fact this group is finitely presented [14].) We are going to describe explicitly the procedure of expressing an element of Uas a word in generators x0,x1,x2, . . . . Let g∈Ube represented by an (a, a)-diagram ∆ over P. One can decompose ∆ into a product of atomic diagrams. It is easy to see that the atomic diagrams that can occur have the form (1, a =ax, xm)², where m≥0, ²=±1 or the form (axk, x2=x3, xm)², where k, m ≥0, ²=±1. In the first case we assign the identity to the atomic diagram and in the second case we assign to it the element x² m. Multiplying these elements, we get an expression for the element g∈U, see [14, Section 6]. Given a diagram Ξ over hx|x3=x2i, we can canonically assign a diagram ∆ over hx, a |x3=x2, ax =aias follows. First we take the sum ε(a) + Ξ and then add a number of cells of the form a=ax on the top to make the top label equal a. Then we add a number of cells of the form METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 9 ax =aon the bottom in order to make the bottom label also equal a. The result is an (a, a)-diagram that represents an element of the group U. On the above picture, where two diagrams over hx|x3=x2iare drawn, the described operation leads to the following elements of U, respectively: x3x−1 1x−1 0x−2 3x−1 1and x−1 1x0. Notice that the way to decompose a diagram into the product of atomic factors is not unique in general. For the first case, we always chose the rightmost cell that can be included into the next atomic factor. This procedure will be described later in details. 3. Main Results Definition 3.1. Let Mbe a set and p, q :M→[0,∞) be arbitrary functions. Then p¹qif there exists a constant c > 0 such that p(m)≤cq(m) for every m∈M. These functions are equivalent, p∼q, if p¹qand q¹p. Let Gbe a group generated by a set Σ. For any g∈G, we denote by `Σ(g) the length of the shortest word over Σ±1that represents g. Notice that if Gis finitely generated, then all functions of the form `Σare equivalent for all finite sets of generators. Therefore, the function g7→ `(g) is unique up to equivalence. The function `on Gdefines the word length metric on Gas follows: the (word) distance between g1, g2∈Gis `(g−1 1g2). We will also omit the subscript Σ on `if the generating set of Gis clear. Let G=D(P, w) be a diagram group over a semigroup presentation P with base w. Let ψ:H ,→Gbe an embedding of a finitely generated group Hinto G. Definition 3.2. We say that ψ:H ,→Gis a B-embedding, whenever #(h)∼`(h) for all h∈H. Here #(h) is the number of cells in the reduced (w, w)-diagram representing ψ(h). An obvious argument implies that #(g)¹`(g) in all cases. Indeed, let Cbe the maximum number of cells that represent generators of H. Then any element that has length nin these generators can be represented by a diagram over Pwith at most Cn cells. However, not every embedding of the above form is a B-embedding. Example 2.Let us consider the direct product G=F2×F2of two free groups of rank 2. It is known that this is a diagram group, see, for example, [11, Section 8]. By a well-known result of Mikhailova [22], there is a finitely generated subgroup Hin Gwith undecidable membership problem. This implies that no recursive function f(n) can have the property `(h)≤f(#(h)) for all h∈H. The most important case is when G=D(P, w) is a finitely generated diagram group and H=Gwith the identical embedding ψ. 16 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR form xy =xand yz =zon the bottom to make the bottom label also equal xz. The result is an (xz, xz)-diagram ∆. Let us denote by othe vertex on the bottom path of ∆ that splits this path into the product of two edges. Clearly, the vertex ois contained in Ξ and splits it into a sum. Let Ξ = Ξk+···+ Ξ0+ Ξ−1+··· + Ξ−m, where each Ξj(−m≤j≤k) is a (y, y)-diagram and the vertex osubdivides Ξ into the sum of the two summands. All the Ξjthat form the first summand satisfy j≥0, the ones that form the second summand satisfy j < 0. (Notice that each of the summands can be empty.) Let gj∈Gbe the element of D(P, y) represented by Ξj(−m≤j≤k). We also define gj= 1 for any integer jnot in [−m, k]. Then, according to [13, Example 10], the diagram ∆ represents the element hof the group Gohtiof the following form: (td, φ), where d,φare defined as follows. The exponent don tis the difference between the number of (z, yz)-cells and the number of (yz, z)-cells in ∆. The function φfrom Z=htiis defined by the rule φ(tj) = gjfor any integer j. It remains to estimate the length of h. We will use Lemma 3.6. We see that the length of hequals (3) k X j=−m `(gj) + M, where Mis the length of the shortest path in the Cayley graph of Z=hti that starts at the identity, ends at tdand visits all those vertices tjfor which gj6= 1. It is clear that M≤2(k+m+ 1) + |d|. Obviously, |d|does not exceed the number of cells in ∆. It is also clear that k+m+ 1 is the number of (x, xy)-cells plus the number of (z, yz)-cells in ∆. This implies M=O(N). Since G=D(P, y) has property B, there exists a constant C > 0 such that the length of each g∈Gdoes not exceed C·#(g), where #(g) denotes the number of cells in the reduced diagram over Prepresenting g. Therefore, the first summand in (3) does not exceed C(#(g−m) + ···+ #(g0) + ···+ #(gk)) ≤CN. Thus we finally have that the length of hin GoZis O(N). ¤ Corollary 3.8. Let P=ha, b, b1, b2, c |ab =a, bc =c, b =b1, b1=b2, b2= bi. Then the restricted wreath product ZoZhas property B as a diagram group D(P, ac). Indeed, Zis the diagram group over hb, b1, b2|b=b1, b1=b2, b2=bi with protected base b. Let Hbe a finitely generated group with fixed generating set. By its growth function γ(n) (with respect to this set of generators) we mean the METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 17 number of elements in the ball of radius naround the identity in the Cayley graph of H. Theorems 1.8 and 1.10 will follow from the next result. Theorem 3.9. Let Hbe a finitely generated group with fixed generating set. Suppose that its growth function satisfies the condition γ(n)ºnkfor some k > 0. Then the Hilbert space compression αof the group ZoHsatisfies the following inequality: α≤1 + k/2 1 + k. Proof. Let xbe a generator of Zin the wreath product ZoH. Every element in ZoHis a pair (b, φ) where b∈H,φis a function g7→ xmgfrom Hto Z with finite support. Let Bnbe the ball of radius naround 1 in the Cayley graph of H. Consider the set Xn={wb=b−1x2n+1−|b|b|b∈Bn}, where `(b) is the length of b. Obviously, wbhas the form (1, φb) in ZoH, where the support of φbis {b}and φb(b) = x2n+1−`(b). Notice that `(xr) = |r|in hxifor all r∈Z. Hence by Lemma 3.6, the length of wbin ZoH equals 2n+1−`(b)+M, where M= 2`(b). Therefore, `(wb) = 2n+1+`(g) is always between 2n+ 1 and 3n+ 1. Clearly, all elements of Xnpairwise commute. The number of them is exactly γ(n). It is easy to see that for every choice of ²b∈ {1,−1}, b ∈Bn, the length of the element w=Qb∈Bnw²b bis greater than nγ(n). Indeed, whas the form (1, φ) in ZoH, where supp(φ) = Bnand φ(b) = x2n+1−`(b)for all b∈Bn. Hence the length of wis at least X b∈Bn `(φ(b)) = X b∈Bn (2n+ 1 −`(b)) > nγ(n) by Lemma 3.6. Consider the skew cube spanned by Xnin ZoHand its image in Hunder the uniform embedding f. The sides of the skew cube in Hdo not exceed Cn for some constant nsince our group is finitely generated. So the sum of squares of sides does not exceed C22γ(n)−1γ(n)n2. On the other hand, the number of diagonals is 2γ(n)−1. Hence by the Skew Cube Inequality, there exists a diagonal of the skew cube in Hwhich does not exceed Cnpγ(n). Thus there exist two points in the Cayley graph of Gat distance d≥nγ(n) whose images under fare at distance at most Cnpγ(n). If ρ1(d) = Kdα for some constant K > 0 in the definition of the uniform embedding, then Cnpγ(n)≥K(nγ(n))α. Hence n1−αº(γ(n))α−1/2ºnk(α−1/2). 18 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR This implies 1 −α≥k(α−1/2) and so α≤(1 + k/2)/(1 + k). ¤ Theorem 3.10. The Hilbert space compression of the restricted wreath product ZoZbelongs to [1/2; 3/4]. Proof. The lower bound follows from Theorem 1.5 and the fact that ZoZ satisfies property B as a diagram group D(P, ac) over P=ha, b, b1, b2, c | ab =a, bc =c, b =b1, b1=b2, b2=bi(Corollary 3.8). The upper bound follows from Theorem 3.9 with G=Z. Indeed, the growth function of Zis linear, that is, γ(n)ºnkfor k= 1. Hence α≤ (1 + k/2)/(1 + k) = 3/4. ¤ Recall that a finitely generated group has a super-polynomial growth whenever its growth function γ(n) exceeds nkfor all k≥1. Theorem 3.11. Let Hbe a finitely generated group with super-polynomial growth. Then the Hilbert space compression of ZoHis at most 1/2. Proof. Indeed, γ(n)ºnkimplies α≤(1 + k/2)/(1 + k). The right-hand side of this inequality approaches 1/2 as k→ ∞.¤ Corollary 3.12. The Hilbert space compression of the group Zo(ZoZ)is at most 1/2. References [1] M.E.B. Bekka, P.-A. Cherix, A. Valette, Proper affine isometric actions of amenable groups, Novikov conjectures, index theorems and rigidity, Vol. 2 (Oberwolfach, 1993), 1–4, London Math. Soc. Lecture Note Ser., 227, Cambridge Univ. Press, Cambridge, 1995. [2] J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. [3] J. Burillo, Quasi-isometrically embedded subgroups of Thompson’s group F, J. Algebra 212 (1999), no. 1, 65–78. [4] S.J. Campbell and G.A. Niblo, Hilbert space compression and exactness for discrete groups. http://arXiv.org/abs/math.GR/0403456 [5] P.-A. Cherix, M. Cowling, P. Jolissaint, P. Julg and A. Valette, Groups with the Haagerup property. Gromov’s a-T-menability. Progress in Mathematics, 197. Birkh¨auser Verlag, Basel, 2001. [6] M. Deza and H. Maehara, H. A few applications of negative-type inequalities, Graphs Combin. 10 (1994), no. 3, 255–262. [7] D. Farley, Finiteness and CAT(0) properties of diagram groups, Topology 42 (2003), no. 5, 1065–1082. [8] M. Gromov, Asymptotic invariants of infinite groups, Geometric group theory, Vol. 2(Sussex, 1991), 1–295, London Math. Soc. Lecture Note Ser., 182, Cambridge Univ. Press, Cambridge, 1993. METRIC ON DIAGRAM GROUPS AND UNIFORM EMBEDDINGS 19 [9] M. Gromov, Problems (4) and (5), Novikov conjectures, index theorems and rigidity, Vol. 1(S. Ferry, A. Ranicki and J. Rosenberg, editors), London Mathematical Society Lecture Note Series, 226. Cambridge University Press, Cambridge, 1995, 67. [10] M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146. [11] V. S. Guba and M. V. Sapir, Diagram groups, Mem. Amer. Math. Soc. 130 (1997), no. 620, viii+117 pp. [12] V. S. Guba and M. V. Sapir, The Dehn function and a regular set of normal forms for R. Thompson’s group F, J. Austral. Math. Soc. (Ser. A) 62 (1997), 315–328. [13] V. S. Guba, M. V. Sapir, On subgroups of the R. Thompson group Fand other diagram groups, Mat. Sb. 190 (1999), no. 8, 3–60; translation in Sb. Math. 190 (1999), no. 7-8, 1077–1130. [14] V. S. Guba and M. V. Sapir, Diagram groups and directed 2-complexes: homotopy and homology. http://arXiv.org/abs/math.GR/0301225 [15] V. S. Guba and M. V. Sapir, Diagram groups are totally orderable. http://arXiv.org/abs/math.GR/0305153 [16] E. Guentner and J. Kaminker, Exactness and the Novikov conjecture, Topology 41 (2002), no. 2, 411–418; Addendum to this paper: Topology 41 (2002), no. 2, 419–420. [17] E. Guentner and J. Kaminker, Exactness and uniform embeddability of discrete Groups. http://www.arxiv.org/math.GR/0309166 [18] N. Higson, Bivariant K-theory and the Novikov conjecture, Geom. Funct. Anal. 10 (2000), no. 3, 563–581. [19] V. Kilibarda. On the algebra of semigroup diagrams. PhD Thesis, Univ. of Nebraska – Lincoln, 1994. [20] V. Kilibarda, On the algebra of semigroup diagrams, Int. J. of Alg. and Comput. 7 (1997), 313–338. [21] N. Linial and M. Saks, The Euclidean distortion of complete binary trees, Discrete Comput. Geom. 29 (2003), no. 1, 19–21. [22] K. A. Mikhailova, The membership problem for direct products of groups, DAN SSSR 119 (1958), 1103–1105 (Russian). [23] G.A. Niblo, L.D. Reeves, Groups acting on CAT(0) cube complexes, Geom. Topol. 1(1997), 7. [24] W. Parry, Growth series of some wreath products, Trans. Amer. Math. Soc. 331 (1992), no. 2, 751–759. [25] G. Skandalis, J. L. Tu, and G. Yu, The coarse Baum-Connes conjecture and groupoids, Topology 41 (2002), no. 4, 807–834. [26] J.-L. Tu, Remarks on Yu’s property A for discrete metric spaces and groups, Bull. Soc. Math. France 129 (2001), 115–139. [27] G. Yu, The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math. 139 (2000), no. 1, 201–240. 20 G. N. ARZHANTSEVA, V. S. GUBA, AND M. V. SAPIR Section de Math´ ematiques, Universit´ e de Gen` eve, CP 64, 1211 Gen` eve 4, Switzerland E-mail address:[email protected] Dep. of mathematics, Vologda State University, 6 S. Orlov St., Vologda, 160600, Russia E-mail address:[email protected] Department of mathematics, Vanderbilt University, USA E-mail address:[email protected]