Embeddings of discrete groups and the speed of random walks

Assaf Naor^{∗} Courant Institute

       naor@cims.nyu.edu

Yuval Peres^{†} Microsoft Research and UC Berkeley

                                   peres@microsoft.com

Abstract

Let G be a group generated by a finite set S and equipped with the associated left-invariant word metric d_{G}. For a Banach space X let α_{X}^{∗}(G) (respectively α_{X}^{#}(G)) be the supremum over all α ≥ 0 such that there exists a Lipschitz mapping (respectively an equivariant mapping) f : G → X and c > 0 such that for all x, y ∈ G we have ∥f (x) − f (y)∥ ≥ c · d_{G}(x, y)^{α}. In particular, the Hilbert compression exponent (respectively the equivariant Hilbert compression exponent) of G is α^{∗}(G) α_{L_{2}}^{∗}(G) (respectively α^{#}(G) α_{L_{2}}^{#}(G)). We show that if X has modulus of smoothness of power type p, then α_{X}^{#}(G) ≤ \frac{1}{pβ^{∗}(G)}. Here β^{∗}(G) is the largest β ≥ 0 for which there exists a set of generators S of G and c > 0 such that for all t ∈ we have [d_{G}(W_{t}, e)] ≥ ct^{β}, where {W_{t}}_{t=0}^{∞} is the canonical simple random walk on the Cayley graph of G determined by S, starting at the identity element. This result is sharp when X = L_{p}, generalizes a theorem of Guentner and Kaminker [20], and answers a question posed by Tessera [37]. We also show that if α^{∗}(G) ≥ \frac{1}{2} then α^{∗}(G ≀ ) ≥ \frac{2α^{∗}(G)}{2α^{∗}(G)+1} . This improves the previous bound due to Stalder and Valette [36]. We deduce that if we write _{(1)} and _{(k+1)} _{(k)} ≀ then α^{∗}( _{(k)}) = \frac{1}{2−2^{1−k}} , and use this result to answer a question posed by Tessera in [37] on the relation between the Hilbert compression exponent and the isoperimetric profile of the balls in G. We also show that the cyclic lamplighter groups C_{2} ≀C_{n} embed into L_{1} with uniformly bounded distortion, answering a question posed by Lee, Naor and Peres in [26]. Finally, we use these results to show that edge Markov type need not imply Enflo type.

1 Introduction

Let G be a finitely generated group^{1}. Fix a finite set of generators S ⊆ G, which we will always assume to be symmetric (i.e. s ∈ S ⟺ s^{−1} ∈ S). Let d_{G} be the left-invariant word metric induced by S on G. Given a Banach space X let α_{X}^{∗}(G) denote the supremum over all α ≥ 0 such that there exists a Lipschitz mapping f : G → X and c > 0 such that for all x, y ∈ G we have ∥f (x) − f (y)∥ ≥ c · d_{G}(x, y)^{α}. For p ≥ 1 we write α_{L_{p}}^{∗}(G) = α_{p}^{∗}(G) and when p = 2 we write α_{2}^{∗}(G) = α^{∗}(G). The parameter α^{∗}(G) is called the Hilbert compression exponent of G. This quasi-isometric group invariant was introduced by Guentner and Kaminker in [20]. We refer to the papers [20, 11, 3, 14, 37, 2, 36, 13] and the references therein for background on this topic and several interesting applications.

Analogously to the above definition, one can consider the equivariant compression exponent α_{X}^{#}(G), which is defined exactly as α_{X}^{∗}(G) with the additional requirement that the embedding f : G → X is equivariant (see Section 2 for the definition). As above, we introduce the notation α_{p}^{#}(G) = α_{L_{p}}^{#}(G) and α^{#}(G) = α_{2}^{#}(G). Clearly α_{X}^{#}(G) ≤ α_{X}^{∗}(G). In the Hilbertian case, when G is amenable we have α^{∗}(G) = α^{#}(G). This was proved by by Aharoni, Maurey and Mityagin [1] (see also Chapter 8 in [9]) when G is Abelian, and by Gromov for general amenable groups (see [14]).

∗Research supported in part by NSF grants CCF-0635078 and DMS-0528387.

†Research supported in part by NSF grant DMS-0605166.

1In this paper all groups are assumed to be infinite unless stated otherwise.

The modulus of uniform smoothness of a Banach space X is defined for τ > 0 as

ρ_{X}(τ) = sup\{ \frac{∥x + τy∥ + ∥x − τy∥}{2}− 1 : x, y ∈ X, ∥x∥ = ∥y∥ = 1\}.  (1)

X is said to be uniformly smooth if lim_{τ→0} \frac{ρ_{X}(τ)}{τ} = 0. Furthermore, X is said to have modulus of smoothness of power type p if there exists a constant K such that ρ_{X}(τ) ≤ Kτ^{p} for all τ > 0. It is straightforward to check that in this case necessarily p ≤ 2. A deep theorem of Pisier [31] states that if X is uniformly smooth then there exists some 1 < p ≤ 2 such that X admits an equivalent norm which has modulus of smoothness of power type p. For concreteness we note that L_{p} has modulus of smoothness of power type min{p, 2}. See Section 2 for more information on this topic.

Define β^{∗}(G) to be the supremum over all β ≥ 0 for which there exists a symmetric set of generators S of G and c > 0 such that for all t ∈ ,

[d_{G}(W_{t}, e)] ≥ ct^{β},  (2)

where here, and in what follows, {W_{t}}_{t=0}^{∞} is the canonical simple random walk on the Cayley graph of G determined by S, starting at the identity element e. In [4] Austin, Naor and Peres used the method of Markov type to show that if G is amenable and X has modulus of smoothness of power type p then

α_{X}^{∗}(G) ≤ \frac{1}{pβ^{∗}(G)}.  (3)

Our first result, which is proved in Section 2, establishes the same bound as (3) for the equivariant compression exponent α_{X}^{#}(G), even when G is not necessarily amenable.

Theorem 1.1. Let X be a Banach space which has modulus of smoothness of power type p. Then

α_{X}^{#}(G) ≤ \frac{1}{pβ^{∗}(G)}.  (4)

Since when G is amenable α^{∗}(G) = α^{#}(G), Theorem 1.1 is a generalization of (3) when X = L_{2}.

A theorem of Guentner and Kaminker [20] states that if α^{#}(G) > \frac{1}{2} then G is amenable. Since for a non-amenable group G we have β^{∗}(G) = 1 (see [25] or [43], Proposition II.8.2 and Corollary II.12.5), Theorem 1.1 implies the Guentner-Kaminker theorem, while generalizing it to non-Hilbertian targets (when the target space X is a Hilbert space our method yields a very simple new proof of the Guentner-Kaminker theorem—see Remark 2.6). Note that both known proofs of the Guentner-Kaminker theorem, namely the original proof in [20] and the new proof discovered by de Cornulier, Tessera and Valette in [14], rely crucially on the fact that X is a Hilbert space. It follows in particular from Theorem 1.1 that for 2 ≤ p < ∞, if α_{p}^{#}(G) > \frac{1}{2} then G is amenable. This is sharp, since in Section 2 we show that for the free group on two generators _{2}, for every 2 ≤ p < ∞ we have α_{p}^{#}( _{2}) = \frac{1}{2}. This answers a question posed by Tessera (see Question 1.6 in [37]).

Theorem 1.1isolates a geometric property (uniform smoothness) of the target space X which lies at the heart of the phenomenon discovered by Guentner and Kaminker. Our proof is a modification of the martingale method developed by Naor, Peres, Schramm and Sheffield in [28] for estimating the speed of stationary reversible Markov chains in uniformly smooth Banach spaces. This method requires several adaptations in the present setting since the random walk {W_{t}}_{t=0}^{∞} is not stationary—we refer to Section 2 for the details.

Given two groups G and H, the wreath product G ≀H is the group of all pairs (f, x) where f : H → G has finite support (i.e. f (z) = e_{G} for all but finitely many z ∈ H) and x ∈ H, equipped with the product

(f, x)(g, y) (z ↦ f (z)g(x^{−1}z), xy).

If G is generated by the set S ⊆ G and H is generated by the set T ⊆ H then G ≀H is generated by the set {(e_{G^{H}}, t) : t ∈ T} ∪ {(δ_{s}, e_{H}) : s ∈ S}. Unless otherwise stated we will always assume that G ≀H is equipped with the word metric associated with this canonical set of generators (although in most cases our assertions will be independent of the choice of generators).

The behavior of the Hilbert compression exponent under wreath products was investigated in [3, 37, 36, 4]. In particular, Stalder and Valette proved in [36] that

α^{∗}(G ≀ ) ≥ \frac{α^{∗}(G)}{α^{∗}(G) + 1} .  (5)

Here we obtain the following improvement of this bound:

Theorem 1.2. For every finitely generated group we have,

α^{∗}(G) ≥ \frac{1}{2} ⟹ α^{∗}(G ≀ ) ≥ \frac{2α^{∗}(G)}{2α^{∗}(G) + 1} ,  (6)

and

α^{∗}(G) ≤ \frac{1}{2} ⟹ α^{∗}(G ≀ ) = α^{∗}(G).  (7)

We refer to Theorem 3.3 for an analogous bound for α_{p}(G ≀ ), as well as a more general estimate for α_{p}(G ≀H). In addition to improving (5), we will see below instances in which (6) is actually an equality. In fact, we conjecture that (6) holds as an equality for every amenable group G.

Èrshler [17] (see also [34]) proved that β^{∗}(G ≀ ) ≥ \frac{1+β^{∗}(G)}{2}. More generally, in Section 6 we show that

β^{∗}(G ≀H) ≥ \{ \begin{matrix}\frac{1+β^{∗}(G)}{2} & if H has linear growth, \\ 1 & otherwise. \end{matrix}  (8)

Since if G is amenable then G ≀ is also amenable (see e.g. [30, 24]) it follows that for an amenable group G,

α^{∗}(G ≀ ) ≤ \frac{1}{1 + β^{∗}(G)}.  (9)

Corollary 1.3. If G is amenable and α^{∗}(G) = \frac{1}{2β^{∗}(G)} then

α^{∗}(G ≀ ) = \frac{1}{2β^{∗}(G ≀ )} = \frac{2α^{∗}(G)}{2α^{∗}(G) + 1} .

In particular, if we define iteratively G_{(1)} G and G_{(k+1)} G_{(k)} ≀ , then for all k ≥ 1,

α^{∗}(G_{(k)}) = \frac{2^{k−1}α^{∗}(G)}{(2^{k} − 2)α^{∗}(G) + 1} .

Corollary 1.3follows immediately from Theorem 1.2and the bound (9). Additional results along these lines are obtained in Section 4; for example (see Remark 3.4) we deduce that α^{∗}( ≀ ^{2}) = \frac{1}{2}.

For r ∈ let J(r) be the smallest constant J > 0 such that for every f : G → which vanishes outside the ball B(e, r) {x ∈ G : d_{G}(x, e) ≤ r}, we have

(∑_{x∈G}f (x)^{2})^{1/2} ≤ J · (∑_{x∈G} ∑_{s∈S} |f (sx) − f (x)|^{2})^{1/2}.

Let a^{∗}(G) be the supremum over all a ≥ 0 for which there exists c > 0 such that for all r ∈ we have J(r) ≥ cr^{a}. Tessera proved in [37] that α^{∗}(G) ≥ a^{∗}(G) and asked if it is true that α^{∗}(G) = a^{∗}(G) for every amenable group G (see Question 1.4 in [37]). Corollary 1.3 implies that the answer to this question is negative. Indeed, Corollary 1.3 implies that the amenable group ( ≀ ) ≀ satisfies

α^{∗}(( ≀ ) ≀ ) = \frac{4}{7} yet a^{∗}(( ≀ ) ≀ ) ≤ \frac{1}{2}.  (10)

In fact, the ratio a^{∗}(G)/α^{∗}(G) can be arbitrarily small, since if we denote _{(1)} and _{(k+1)} _{(k)}≀ then for k ≥ 2,

α^{∗}( _{(k)}) = \frac{1}{2 − 2^{1−k}} yet a^{∗}( _{(k)}) ≤ \frac{1}{k − 1}.  (11)

To prove (11), and hence also its special case (10), note that the assertion in (11) about α^{∗}( _{(k)}) is a consequence of Corollary 1.3. To prove the upper bound on a^{∗}( _{(k)}) in (11) we note that if G is a finitely generated group such that the probability of return of the standard random walk {W_{t}}_{t=0}^{∞} satisfies

[W_{t} = e] ≤ exp(−Ct^{γ})  (12)

for some C, γ ∈ (0, 1) and all t ∈ , then

a^{∗}(G) ≤ \frac{1 − γ}{2γ} .  (13)

This implies (11) since Pittet and Saloff-Coste [32] proved that for all k ≥ 2 there exists c, C > 0 such that for G = _{(k)} we have for all t ≥ 1

exp(−Ct^{\frac{k−1}{k+1}} (logt)^{\frac{2}{k+1}}) ≤ [W_{t} = e] ≤ exp(−ct^{\frac{k−1}{k+1}} (logt)^{\frac{2}{k+1}}).  (14)

The bound (13) is essentially known. Indeed, assume that J(r) ≥ cr^{a} for every r ≥ 1. Following the notation of Coulhon [12], for v ≥ 1 let Λ(v) denote the largest constant Λ ≥ 0 such that for all Ω ⊆ G with |Ω| ≤ v, every f : G → which vanishes outside Ω satisfies

Λ · ∑_{x∈G}f (x)^{2} ≤ ∑_{x∈G} ∑_{s∈S} |f (sx) − f (x)|^{2}.

Since for r ≥ 2 we have |B(e, r)| ≤ |S|^{r}, it follows immediately from the definitions that J(r)^{2} ≤ \frac{1}{Λ(|S|^{r})} . Theorem 7.1 in [12] implies that there exists a constant K > 0 such that if e^{Kt^{γ}} ≥ |S| then,

t ≥ ∫ _{|S|}^{e^{Kt^{γ}}} \frac{dv}{vΛ(v)} = ∫ 1^{\frac{Kt^{γ}}{log|S|}} \frac{log|S|}{Λ(|S|^{r})}dr ≥ log|S| ∫ 1^{\frac{Kt^{γ}}{log|S|}} J(r)^{2}dr

≥ c^{2} log|S| ∫ 1^{\frac{Kt^{γ}}{log|S|}} r^{2a}dr = \frac{c^{2} log|S|}{(2a + 1)} ((\frac{Kt^{γ}}{log|S|})^{2a+1} − 1) .

Letting t → ∞ it follows that (2a + 1)γ ≤ 1, implying (13).

Remark 1.4. In [37] Tessera asserted that if the opposite inequality to (12) holds true, i.e. if we have [W_{t} = e] ≥ exp(−Kt^{γ})for some γ ∈ (0, 1), K > 0, and every t ≥ 1, then a^{∗}(G) ≥ 1 − γ. Unfortunately, this claim is false in general.^{2} Indeed, if it were true, then using (14) we would deduce that

a^{∗}((( ≀ )≀ )≀ ) = a^{∗}( _{(4)}) ≥ \frac{2}{5} ,

but from (11)we know that a^{∗}( _{(4)}) ≤ \frac{1}{3}. On inspection of the proof of Proposition 7.2 in [37] we see that the argument given there actually yields the lower bound a^{∗}(G) ≥ \frac{1−γ}{2} (note the squares in the first equation of the proof of Proposition 7.2 in [http://arxiv.org/abs/math/0603138v3]). Thus, the original argument presented in [37] to establish the lower bound a^{∗}( ≀ ) ≥ \frac{2}{3} only proves that a^{∗}( ≀ ) ≥ \frac{1}{3}. Nevertheless, the lower bound of \frac{2}{3}, which was used crucially in [4], is correct, as follows from our Theorem 1.2. After the present paper was posted and sent to Tessera, he replaced the original argument in [37] for the lower bound α^{∗}( ≀ ) ≥ \frac{2}{3} by a correct argument, along the same lines as our proof of Theorem 1.2.

In Section 4 we show that the cyclic lamplighter group C_{2} ≀C_{n} admits a bi-Lipschitz embedding into L_{1} with distortion independent of n (here, and in what follows C_{n} denotes the cyclic group of order n). This answers a question posed in [26] and in [5]. In Section 5 we use the notion of Hilbert space compression to show that ≀ has edge Markov type p for any p < \frac{4}{3}, but it does not have Enflo type p for any p > 1. We refer to Section 5 for the relevant definitions. This result shows that there is no metric analogue of the well known Banach space phenomenon “equal norm Rademacher type p implies Rademacher p′ for every p′ < p” (see [38]). Finally, in Section 7 we present several open problems that arise from our work.

2 Equivariant compression and random walks

In what follows we will use ≍ and , to denote, respectively, equality or the corresponding inequality up to some positive multiplicative constant.

Let X be a Banach space. We denote the group of linear isometric automorphisms of X by Isom(X). Fix a homomorphism π : G → Isom(X), i.e. an action of G on X by linear isometries. A function f : G → X is called a 1-cocycle with respect to π if for every x, y ∈ G we have f (xy) = π(x)f (y) + f (x). The space of all 1-cocycles with respect to π is denoted Z^{1}(G, π). Equivalently, f ∈ Z^{1}(G, π) if and only if v ↦ π(x)v + f (x) is an action of G on X by affine isometries. A function f : G → X is called a 1-cocycle if there exists a homomorphism π : G → Isom(X) such that f ∈ Z^{1}(G, π). A mapping ψ : G → X is called equivariant if it is given by the orbit of a vector v ∈ X under an affine isometric action of G on X, or equivalently ψ(x) = π(x)v + f (x) for some homomorphism π : G → Isom(X) and f ∈ Z^{1}(G, π). Note that since the function x ↦ π(x)v is bounded, the compression exponents of ψ and f coincide. Therefore in order to bound the equivariant compression exponent of G in X it suffices to study the growth rate of 1-cocycles.

2This remark concerns the version http://arxiv.org/abs/math/0603138v3 of [37]; after we informed the author of this mistake, it was corrected in later versions of [37] .

Recall the definition (1) of the modulus of uniform smoothness ρ_{X}(τ), and that X is said to have modulus of smoothness of power type p if there exists a constant K such that ρ_{X}(τ) ≤ Kτ^{p} for all τ > 0. By Proposition 7 in [8], X has modulus of smoothness of power type p if and only if there exists a constant S > 0 such that for every x, y ∈ X

∥x + y∥^{p} + ∥x − y∥^{p} ≤ 2 ∥x∥^{p} + 2 S^{p} ∥y∥^{p}.  (15)

The infimum over all S for which (15) holds is called the p-smoothness constant of X, and is denoted S_{p}(X).

It was shown in [8] (see also [18]) that S_{2}(L_{p}) ≤ \sqrt{p − 1} for 2 ≤ p < ∞ and S_{p}(L_{p}) ≤ 1 for 1 ≤ p ≤ 2 (the order of magnitude of these constants was first calculated in [21]).

Our proof of Theorem 1.1 is based on the following inequality, which is of independent interest. Its proof is a modification of the method that was used in [28] to study the Markov type of uniformly smooth Banach spaces.

Theorem 2.1. Let X be a Banach space with modulus of smoothness of power type p, and assume that f : G → X is a 1-cocycle. Then for every time t ∈ ,

[∥f (W_{t})∥^{p}]≤ C_{p}(X)t · [∥f (W_{1})∥^{p}],

where C_{p}(X) = \frac{2^{2p}S_{p}(X)^{p}}{2^{p−1}−1}.

Theorem 2.1 shows that images of {W_{t}}_{t=0}^{∞} under 1-cocycles satisfy an inequality similar to the Markov type inequality (note that f (W_{0}) = f (e) = f (e · e) = π(e)f (e) + f (e) = 2f (e), whence f (e) = 0). We stress that one cannot apply Markov type directly in this case because of the lack of stationarity of the Markov chain {f (W_{t})}_{t=0}^{∞}. We overcome this problem by crucially using the fact that f is a 1-cocycle.

Before proving Theorem 2.1 we show how it implies Theorem 1.1.

Proof of Theorem 1.1. Observe that (4) is trivial if α_{X}^{#}(G) ≤ \frac{1}{p} (since β^{∗}(G) ≤ 1) or β^{∗}(G) = 0. So, we may assume that α^{#}(G) > \frac{1}{p} and β^{∗}(G) > 0. Fix \frac{1}{p} ≤ α < α_{X}^{#}(G) and 0 < β < β^{∗}(G). Then there exists a 1-cocycle f : G → X satisfying

x, y ∈ G ⟹ d_{G}(x, y)^{α} ∥f (x) − f (y)∥ d_{G}(x, y).

In addition we know that [d_{G}(W_{t}, e)] t^{β}. An application of Theorem 2.1 yields

[∥f (W_{t})∥^{p}] t [∥f (W_{1})∥^{p}]= t [∥f (W_{1}) − f (e)∥^{p}] t [d_{G}(W_{1}, e)^{p}]= t.  (16)

On the other hand, since pα ≥ 1 we may use Jensen’s inequality to deduce that

[∥f (W_{t})∥^{p}]= [∥f (W_{t}) − f (e)∥^{p}] [d_{G}(W_{t}, e)^{pα}]≥ ( [d_{G}(W_{t}, e)])^{pα} t^{pαβ}.  (17)

Combining (16) and (17), and letting t → ∞, implies that pαβ ≤ 1, as required.

Remark 2.2. Theorem 1.1 is optimal for the class of L_{p} spaces. Indeed let _{2} denote the free group on two generators. We claim that for every p ≥ 1,

α_{p}^{#}( _{2}) = max\{ \frac{1}{2}, \frac{1}{p}\} .  (18)

Recall the elementary fact that β^{∗}( _{2}) = 1 (see, e.g., [25]); thus Theorem 1.1 implies that α_{p}^{#}( _{2}) ≤ max\{\frac{1}{2}, \frac{1}{p}\}. In the reverse direction Guentner and Kaminker [20] gave a simple construction of a mapping f : _{2} → L_{p} satisfying ∥f (x) − f (y)∥_{p} ≥ d_{_{2}}(x, y)^{1/p} for all x, y ∈ _{2}. As noted in the MR review of [20] (MR 2160829), the map f : _{2} → L_{p} given by Guentner and Kaminker is not equivariant, but it can be easily modified to be equivariant. (We are indebted to the referee for this remark.) This implies (18) for 1 ≤ p ≤ 2. The case p ≥ 2 follows from Lemma 2.3 below.

Lemma 2.3. For every finitely generated group G and every p ≥ 1 we have α_{p}^{#}(G) ≥ α_{2}^{#}(G).

Proof. In what follows we denote the standard orthonormal basis of ℓ_{2} by (e_{j})_{j=1}^{∞}. Let γ denote the standard Gaussian measure on . Consider the countable product Ω ^{ℵ_{0}}, equipped with the product measure μ γ^{ℵ_{0}}. Let H denote the subspace of L_{2}(Ω, μ) consisting of all linear functions. Thus, if we consider the coordinate functions g_{j} : Ω → given by g(z_{1}, z_{2}, …) = z_{j} then H is the space of all functions h : Ω → of the form h = ∑ _{j=1}^{∞} a_{j}g_{j}, where the sequence (a_{j})_{j=1}^{∞} ⊆ satisfies ∑ _{j=1}^{∞} |a_{j}|^{2} < ∞, i.e. (a_{j})_{j=1}^{∞} ∈ ℓ_{2}. Note that we are using here the standard probabilistic fact (see [15]) that ∑ _{j=0}^{∞} a_{j}g_{j} converges almost everywhere,

and has the same distribution as (∑ _{i=1}^{∞} |a_{i}|^{2})^{1/2} · g_{1} (since {g_{j}}_{j=1}^{∞} are i.i.d. standard complex Gaussian random variables). This fact also implies that for every unitary operator U : ℓ_{2} → ℓ_{2},

Uz (∑_{j=1}^{∞} ⟨Ue_{k}, e_{j}⟩z_{j} )_{k=1}^{∞} ∈ Ω,

is well defined for almost z ∈ Ω, and therefore U can be thought of as a measure preserving automorphism U : Ω → Ω (we are slightly abusing notation here, but this will not create any confusion).

Fix a unitary representation π : G → Isom(ℓ_{2}) and a cocycle f ∈ Z^{1}(G, π) which satisfies

x, y ∈ G ⟹ d_{G}(x, y)^{α} ∥f (x) − f (y)∥_{2} d_{G}(x, y).  (19)

Keeping the same abuse of notation, we denote by π(x) the map on Ω associated with the unitary operator π(x). For x ∈ G and h ∈ L_{p}(Ω, μ) define π̃(x)h ∈ L_{p}(Ω, μ) by π̃(x)h(z) = h(π(x)z). By the above reasoning, since π(x) is a measure preserving automorphism of (Ω, μ), π̃(x) is a linear isometry of L_{p}(Ω, μ), and hence π̃ : G → Isom(L_{p}(Ω, μ)) is a homomorphism. Note that since all the elements of H have a Gaussian distribution, all of their moments are finite. Hence H ⊆ L_{p}(Ω, μ). We can therefore define f̃ : G → L_{p}(Ω, μ) by f̃(x) ∑ _{j=1}^{∞} ⟨f (x), e_{j}⟩g_{j} ∈ H ⊆ L_{p}(Ω, μ). It is immediate to check that f̃ ∈ Z^{1}(G,π̃) and that for every

x, y ∈ G we have ∥f̃(x) − f̃(y)∥_{L_{p}(Ω,μ)} = ∥g_{1}∥_{L_{p}(Ω,μ)} · ∥f (x) − f (y)∥_{2}. Hence f̃ satisfies (19) as well.

Remark 2.4. Lemma 2.3 actually establishes the following fact: there exists a measure space (Ω, μ) and a subspace H ⊆ ⋂ _{p≥1} L_{p}(Ω, μ) which is closed in L_{p}(Ω, μ) for all 1 ≤ p < ∞ and such that the L_{p}(Ω, μ) norm restricted to H is proportional to the L_{2}(Ω, μ) norm. For any group G, any unitary representation π : G → Isom(H) can be extended to a homomorphism π̃ : G → Isom(L_{p}(Ω, μ)). The space H is widely used in Banach space theory, and is known as the Gaussian Hilbert space. The above corollary about the extension of group actions was previously noted in [6] under the additional restriction that 1 < p 2 , as a simple corollary of an abstract extension theorem due to Hardin [22] (alternatively this is also a corollary of the classical Plotkin-Rudin theorem [33, 35]). Lemma 2.3 shows that no restriction on p is necessary, while the theorem of Hardin used in [6] does require the above restriction on p. The key point here is the use of the particular subspace H ⊆ L_{p}(Ω, μ) for which unitary operators have a simple explicit extension to a linear isometric automorphism of L_{p}(Ω, μ) for any 1 ≤ p < ∞.

We shall now pass to the proof of Theorem 2.1. We will use uniform smoothness via the following famous inequality due to Pisier [31] (for the explicit constant below see Theorem 4.2 in [28]).

Theorem 2.5 (Pisier). Fix 1 < p ≤ 2 and let {M_{k}}_{k=0}^{n} ⊆ X be a martingale in X. Then

[∥M_{n} − M_{0}∥^{p}]≤ \frac{S_{p}(X)^{p}}{2^{p−1} − 1} · ∑_{k=0}^{n−1} [∥M_{k+1} − M_{k}∥^{p}].

Proof of Theorem 2.1. By assumption f (x) ∈ Z^{1}(G, π) for some homomorphism π : G → Isom(X). Let {σ_{k}}_{k=1}^{∞} be i.i.d. random variables uniformly distributed over S. Then for t ≥ 1 W_{t} has the same distribution as the random product σ_{1} ⋯ σ_{t}.

For every t ≥ 1 the following identity holds true:

2f (W_{t})= ∑_{j=1}^{t} π (W_{j−1} )f (σ_{j}) − ∑_{j=1}^{t} π (W_{j})f (σ_{j}^{−1}) .  (20)

We shall prove (20) by induction on t. Note that every x ∈ G satisfies 0 = f (e) = f (x^{−1} · x)= π(x)^{−1}f (x) + f (x^{−1}), i.e. f (x) = −π(x)f (x^{−1}). This implies (20) when t = 1. Hence, assuming the validity of (20) for t we can use the identity 2f (xy) = 2f (x) + π(x)f (y) − π(xy)f (y^{−1})to deduce that

2f (W_{t+1}) = 2f (W_{t}σ_{t+1})
= 2f (W_{t}) + π(W_{t})f (σ_{t+1}) − π(W_{t+1})f (σ_{t+1}^{−1})
= ∑_{j=1}^{t} π (W_{j−1} )f (σ_{j}) − ∑_{j=1}^{t} π (W_{j})f (σ_{j}^{−1}) + π(W_{t})f (σ_{t+1}) − π(W_{t+1})f (σ_{t+1}^{−1})

= ∑_{j=1}^{t+1} π (W_{j−1} )f (σ_{j}) − ∑_{j=1}^{t+1} π (W_{j})f (σ_{j}^{−1}) ,

proving (20).

Define

M_{t} ∑_{j=1}^{t} π (W_{j−1} )(f (σ_{j}) − v) = ∑_{j=1}^{t} π (σ_{1} ⋯ σ_{j−1} ) (f (σ_{j}) − v) ,

and

N_{t} ∑_{j=1}^{t} π (W_{t}^{−1}W_{j})(f (σ_{j}^{−1}) − v) = ∑_{j=1}^{t} π (σ_{t}^{−1} ⋯ σ_{j+1}^{−1} ) (f (σ_{j}^{−1}) − v) ,

where v [f (W_{1})]∈ X. Note that since S is symmetric, σ_{j}^{−1} has the same distribution as σ_{j}, and therefore N_{t} has the same distribution as M_{t}. Moreover, (20) implies that 2f (W_{t})= M_{t}− π(W_{t})N_{t}− v + π(W_{t})v. Since π(W_{t}) is an isometry, we deduce that

2^{p} [∥f (W_{t})∥^{p}]≤ 4^{p−1} [∥M_{t}∥^{p}]+ 4^{p−1} [∥N_{t}∥^{p}]+ 2 · 4^{p−1}∥v∥^{p}

= 2 · 4^{p−1} [∥M_{t}∥^{p}]+ 2 · 4^{p−1} ∥ [f (W_{1})]∥^{p} ≤ 2 · 4^{p−1} [∥M_{t}∥^{p}]+ 2 · 4^{p−1} [∥f (W_{1})∥^{p}]. (21)

Note that for every t ≥ 1,

[M_{t}|σ_{0}, …, σ_{t−1}] = [∑_{j=1}^{t} π (σ_{0} ⋯ σ_{j−1} ) (f (σ_{j}) − v) |σ_{0}, …, σ_{t−1}]

= M_{t−1} + π (σ_{0} ⋯ σ_{t−1}) ( [f (σ_{t})] − v) = M_{t−1},

Hence {M_{k}}_{k=0}^{∞} is a martingale with respect to the filtration induced by {σ_{k}}_{k=0}^{∞}. By theorem 2.5,

[∥M_{t}∥^{p}]≤ \frac{S_{p}(X)^{p}}{2^{p−1} − 1} · ∑_{k=0}^{t−1} [∥M_{k+1} − M_{k}∥^{p}]= \frac{S_{p}(X)^{p}}{2^{p−1} − 1} · ∑_{k=0}^{t−1} [∥f (σ_{k}) − v∥^{p}]

≤ \frac{S_{p}(X)^{p}}{2^{p−1} − 1} · t2^{p−1} ( [∥f (W_{1})∥^{p}]+ ∥v∥^{p}) ≤ \frac{2^{p}S_{p}(X)^{p}}{2^{p−1} − 1} · t [∥f (W_{1})∥^{p}]. (22)

Combining (21) and (22) completes the proof of Theorem 2.1.

Remark 2.6. When the target space X is Hilbert space one can prove Theorem 1.1via the following simpler argument. Using the notation in the proof of Theorem 2.1 we see that for each t ∈ the random variables W_{t}^{−1} = σ_{t}^{−1} ⋯ σ_{1}^{−1} and W_{t}^{−1}W_{2t} = σ_{t+1} ⋯ σ_{2t} are independent and have the same distribution as W_{t}. Therefore Y_{1} f (W_{t}^{−1})and Y_{2} f (W_{t}^{−1}W_{2t})= π (W_{t}^{−1})f (W_{2t}) + f (W_{t}^{−1})are i.i.d., and hence satisfy

[∥f (W_{2t})∥^{2}] = [∥π (W_{t}^{−1})f (W_{2t})∥^{2}] = [∥Y_{1} − Y_{2}∥^{2}]= [∥Y_{1}∥^{2} − 2⟨Y_{1}, Y_{2}⟩ + ∥Y_{2}∥^{2}]

= 2 [∥f (W_{t})∥^{2}]− 2 ∥ [f (W_{t})]∥^{2} ≤ 2 [∥f (W_{t})∥^{2}].

By induction it follows that for every k ∈ ,

[∥f (W_{2^{k}})∥^{2}] ≤ 2^{k} [∥f (W_{1})∥^{2}].

This implies Theorem 1.1, and hence also the Guentner-Kaminker amenability criterion in terms of equivariant compression [20], by arguing exactly as in the conclusion of the proof of Theorem 1.1.

3 The behavior of L_{p} compression under wreath products

Given two groups G, H let ℒ_{G}(H) denote the wreath product G ≀H where the set of generators of G is taken to be G \ {e} (i.e. any two distinct elements of G are at distance 1 from each other). With this definition it is immediate to check (see for example the proof of Lemma 2.1 in [5]) that

(f, i), (g, j) ∈ ℒ_{G}( ) ⟹ d_{ℒ_{G}( )} ((f, i), (g, j)) ≍ |i − j| + max{|k| + 1 : f (k) g(k)}.  (23)

The case G = C_{2} corresponds to the classical lamplighter group on H.

Lemma 3.1. For every group G we have α^{∗}(ℒ_{G}( )) = 1.

Proof. As shown by Tessera in [37], α^{∗}(C_{2}≀ ) = 1 (we provide an alternative explicit embedding exhibiting this fact in Section 4 below). Therefore for every α ∈ (0, 1) there is a mapping θ : C_{2} ≀ → L_{2} satisfying

(x, i), (y, j) ∈ C_{2} ≀ ⟹ d_{C_{2}≀}((x, i), (y, j))^{α} ∥θ(x, i) − θ(y, j)∥_{2} d_{C_{2}≀}((x, i), (y, j)).  (24)

Let {ε_{z}}_{z∈G} be i.i.d. {0, 1} valued Bernoulli random variables, defined on some probability space (Ω, ). For every f : → G define a random mapping ε_{f} : → C_{2} by ε_{f} (k) = ε_{f (k)}. We now define an embedding F : ℒ_{G}( ) → L_{2}(Ω, L_{2}) by

F(f, i) θ(ε_{f} , i).

Fix (f, i), (g, j) ∈ ℒ_{G}( ) and let k_{max} ∈ satisfy f (k_{max}) g(k_{max}) and |k_{max}| = max{|k| : f (k) g(k)}. Then

∥F(f, i) − F(g, j)∥_{L_{2}(Ω,L_{2})}^{2} = [∥θ(ε_{f} , i) − θ(ε_{g}, j)∥_{2}^{2}]^{(24)} [d_{C_{2}≀}((ε_{f} , i), (ε_{g}, j))^{2}]

≍^{(23)} [(|i − j| + max{|k| + 1 : ε_{f (k)} ε_{g(k)}})^{2}] ≤ [(|i − j| + |k_{max}| + 1)^{2}] ≍^{(23)} d_{ℒ_{G}( )} ((f, i), (g, j))^{2}.

In the reverse direction note that since f (k_{max}) g(k_{max}) with probability \frac{1}{2} we have ε_{f (k_{max})} ε_{g(k_{max})}. Therefore

∥F(f, i) − F(g, j)∥_{L_{2}(Ω,L_{2})}^{2} = [∥θ(ε_{f} , i) − θ(ε_{g}, j)∥_{2}^{2}]^{(24)} [d_{C_{2}≀}((ε_{f} , i), (ε_{g}, j))^{2α}]

≍^{(23)} [(|i − j| + max{|k| + 1 : ε_{f (k)} ε_{g(k)}})^{2α}] [(|i − j| + |k_{max}| + 1)^{2α}] ≍^{(23)} d_{ℒ_{G}( )} ((f, i), (g, j))^{2α}.

This completes the proof of Lemma 3.1.

Remark 3.2. In [37] Tessera shows that if H has volume growth of order d then

α^{∗}(ℒ_{G}(H)) ≥ \frac{1}{d}.  (25)

Note that Tessera makes this assertion for ℒ_{F}(H), where F is finite (see Section 5.1 in [37], and specifically Remark 5.2 there). But, it is immediate from the proof in [37] that the constant factors in Tessera’s embedding do not depend on the cardinality of F, and therefore (25) holds in full generality. Observe that (25) is a generalization of Lemma 3.1, but we believe that the argument in Lemma 3.1 which reduces the problem to the case G = C_{2} is of independent interest.

The case H = ^{2} in (25) can be proved via the following explicit embedding. For simplicity we describe it when G = C_{2}. Fix 0 < α < \frac{1}{2} and let

{v_{y,r,g}: y ∈ ^{2}, r ∈ ∪ {0}, g : y + [−r, r]^{2} → {0, 1}, g 0}

be an orthonormal system of vectors in L_{2}. For simplicity we also write v_{y,r,0} = 0. Define ψ : C_{2} ≀ ^{2} → 2 ⊕ L_{2} by

ψ(f, x) = x ⊕ ( ∑_{y∈ ^{2}\\{x\}}∑_{r=0}^{∞} \frac{max\{1 − 2r/∥x − y∥_{∞} , 0\}}{∥x − y∥_{∞}^{\frac{3}{2}−2α}}v_{y,r,f _{y+[−r,r]^{2}}} ).

An elementary (though a little tedious) case analysis shows that ψ is Lipschitz and has compression α.

The following theorem, in combination with Lemma 3.1, contains Theorem 1.2 as a special case (note that (7) follows from (26) since clearly α^{∗}(G ≀H) ≤ α^{∗}(G)).

Theorem 3.3. Let G, H be groups and p ≥ 1. Then

min\{α_{p}^{∗}(G), α_{p}^{∗}(ℒ_{G}(H))\} ≥ \frac{1}{p} ⟹ α_{p}^{∗}(G ≀H) ≥ \frac{pα_{p}^{∗}(G)α_{p}^{∗}(ℒ_{G}(H))}{pα_{p}^{∗}(G) + pα_{p}^{∗}(ℒ_{G}(H))− 1} ,

and

min\{α_{p}^{∗}(G), α_{p}^{∗}(ℒ_{G}(H))\} ≤ \frac{1}{p} ⟹ α_{p}^{∗}(G ≀H) ≥ min\{α_{p}^{∗}(G), α_{p}^{∗}(ℒ_{G}(H))\} .  (26)

Proof. We shall start with some useful preliminary observations. Let (X, d_{X}) be a metric space, p ≥ 1, and let Ω be a set. We denote by ℓ_{p}(Ω, X; fin) the metric space of all finitely supported functions f : Ω → X, equipped with the metric

d_{ℓ_{p}}(f, g) (∑_{ω∈Ω} d_{X}(f (ω), g(ω))^{p}) ^{1/p}.

It is immediate to verify that for every (f, x), (g, y) ∈ G ≀H we have

d_{G≀H}((f, x), (g, y)) ≍ d_{ℒ_{G}(H)} ((f, x), (g, y))+ d_{ℓ_{1}(H,G)}(f, g).  (27)

Indeed, it suffices to verify the equivalence (27) when (g, y) is the identity element (e, e) of G ≀H. In this case (27) simply says that in order to move from (e, e) to (f, x) one needs to visit the locations z ∈ H where f (z) e, and in each of these locations one must move within G from e to the appropriate group element f (z) ∈ G.

Another basic fact that we will use is that for every (f, x), (g, y) ∈ G ≀H,

|{z ∈ H : f (z) g(z)}| ≤ d_{ℒ_{G}(H)} ((f, x), (g, y)).  (28)

Once more, this fact is entirely obvious: in order to move in ℒ_{G}(H) from (f, x) to (g, y) once must visit all the locations where f and g differ.

We shall now proceed to the proof of Theorem 3.3. Fix a < α_{p}^{∗}(G) and b < α_{p}^{∗}(ℒ_{G}(H)). Then there exists a function ψ : G → L_{p} such that

u, v ∈ G ⟹ d_{G}(u, v)^{a} ∥ψ(u) − ψ(v)∥_{p} d_{G}(u, v).  (29)

We also know that there exists a function ϕ : ℒ_{G}(H) → L_{p} which satisfies

u, v ∈ ℒ_{G}(H) ⟹ d_{ℒ_{G}(H)} (u, v)^{b} ∥ϕ(u) − ϕ(v)∥_{p} d_{ℒ_{G}(H)} (u, v).  (30)

Define a function F : G ≀H → L_{p} ⊕ ℓ_{p}(H, L_{p}; fin) by

F(f, x) ϕ(f, x) ⊕ (ψ ∘ f) .

Fix (f, x), (g, y) ∈ G ≀H and denote m d_{ℒ_{G}(H)} ((f, x), (g, y)) and n d_{ℓ_{1}(H,G)}(f, g). We know from (27) that d_{G≀H}((f, x), (g, y)) ≍ m + n. Now,

∥F(f, x) − F(g, y)∥_{p} = (∥ϕ(f, x) − ϕ(g, y)∥_{p}^{p} + ∑_{z∈H} ∥ψ(f (z)) − ψ(g(z))∥_{p}^{p})^{1/p}

≤ ∥ϕ(f, x) − ϕ(g, y)∥_{p} + ∑_{z∈H} ∥ψ(f (z)) − ψ(g(z))∥_{p} ^{(29)∧(30)} m + n ≍ d_{G≀H}((f, x), (g, y)).

In the reverse direction we have the lower bound

∥F(f, x) − F(g, y)∥_{p} ^{(29)∧(30)} (m^{bp} + ∑_{z∈H} d_{G}(f (z), g(z))^{ap})^{1/p}.  (31)

If ap ≤ 1 then ∑ _{z∈H} d_{G}(f (z), g(z))^{ap} ≥ (∑ _{z∈H} d_{G}(f (z), g(z)))^{ap} = n^{ap} and (31) implies that

∥F(f, x) − F(g, y)∥_{p} (m^{bp} + n^{ap})^{1/p} (m + n)^{min{a,b}} d_{G≀H}((f, x), (g, y))^{min{a,b}}.  (32)

Assume that ap > 1. It follows from (28) that |{z ∈ H : f (z) g(z)}| ≤ m. Thus, using Hölder’s inequality, we see that

∑_{z∈H} d_{G}(f (z), g(z))^{ap} ≥ \frac{1}{m^{ap−1}} (∑_{z∈H} d_{G}(f (z), g(z)))^{ap} = \frac{n^{ap}}{m^{ap−1}}.  (33)

Note that m^{bp} + \frac{n^{ap}}{m^{ap−1}} ≥ n^{\frac{abp^{2}}{ap+bp−1}} , which follows by considering the cases m ≥ n^{\frac{ap}{ap+bp−1}} and m ≤ n^{\frac{ap}{ap+bp−1}} separately. Hence,

∥F(f, x) − F(g, y)∥_{p} ^{(31)∧(33)} (m^{bp} + \frac{n^{ap}}{m^{ap−1}})^{1/p} max\{m^{b}, n^{\frac{abp}{ap+bp−1}} \}

(m + n)^{min\{b, \frac{abp}{ap+bp−1} \}}≍ d_{G≀H}((f, x), (g, y))^{min\{b, \frac{abp}{ap+bp−1} \}}. (34)

Note that when ap > 1, if b ≤ \frac{abp}{ap+bp−1} then bp ≤ 1. Therefore (32) and (34) imply Theorem 3.3.

Remark 3.4. Theorem 3.3, in combination with Remark 3.2 and the results of Section 6 below, imply that if G is amenable and H has quadratic growth then

α^{∗}(G ≀H) = min\{ \frac{1}{2}, α^{∗}(G)\} .  (35)

Thus, in particular,

α^{∗}(C_{2} ≀ ^{2}) = α^{∗}( ≀ ^{2}) = \frac{1}{2}.

To see (35) note that by Theorem 6.1 in Section 6 we have β^{∗}(G ≀H) = 1. Using (3) we deduce that α^{∗}(G ≀H) ≤ \frac{1}{2}, and the inequality α^{∗}(G ≀H) ≤ α^{∗}(G) is obvious. The reverse inequality in (35) is a corollary of Theorem 3.3 and Remark 3.2.

4 Embedding the lamplighter group into L_{1}

In this section we show that the lamplighter group on the integers, C_{2} ≀ , admits a bi-Lipschitz embedding into L_{1}. This fact will follow from a standard limiting argument once we establish that the lamplighter group on the n-cycle, C_{2} ≀C_{n}, embeds into L_{1} with distortion independent of n. We present two embeddings of C_{2} ≀C_{n} into L_{1}. Our first embedding is a variant of the embedding method used in [5]. In [5] there is a detailed explanation of how such embeddings can be discovered by looking at the irreducible representations of C_{2} ≀C_{n}. The embedding below can be motivated analogously, and we refer the interested reader to [5] for the details. Here we just present the resulting embedding, which is very simple. Our second embedding is motivated by direct geometric reasoning rather than the “dual” point of view in [5].

In what follows we slightly abuse the notation by considering elements (x, i) ∈ C_{2} ≀C_{n} as an index i ∈ C_{n} and a subset x ⊆ C_{n}. For the sake of simplicity we will denote the metric on C_{2} ≀C_{n} by ρ. The metric d_{C_{n}} will denote the canonical metric on the n-cycle C_{n}. It is easy to check (see Lemma 2.1 in [5]) that

(x, j), (y, ℓ) ∈ C_{2} ≀C_{n} ⟹ ρ((x, j), (y, ℓ)) ≍ d_{C_{n}}(j, k) + max_{k∈x△y}(d_{C_{n}}(0, k) + 1).  (36)

First embedding of C_{2} ≀C_{n} into L_{1}. We denote by α : C_{n} → C_{n} the shift α(j) = j + 1. Let us write I for the family of all arcs (i.e. connected subsets) of C_{n} of length ⌊n/3⌋ (of which there are n). We define an embedding f : C_{2} ≀C_{n} → ⨁ _{I∈I} ⨁ _{A⊆I} ℓ_{1}(C_{n}) by

f (x, j) ⨁_{I∈I} ⨁_{A⊆I} ((−1)^{|A∩α^{k}(x)|} · \frac{1_{I}(k + j) + n1_{C_{n}\I}(k + j)}{n^{2}2^{n/3}} )_{k∈C_{n}}.

It is immediate to check that the metric on C_{2}≀C_{n} given by ∥f (x, j)−f (x′, j′)∥_{1} is C_{2}≀C_{n}-invariant. Therefore it suffices to show that ∥f (x, j) − f (∅, 0)∥_{1} ≍ ρ((x, j), (∅, 0)) for all (x, j) ∈ C_{2} ≀C_{n}.

Now,

∥f (x, j) − f (∅, 0)∥_{1} ≍ ∑_{I∈I} ∑_{A⊆I} (\frac{|\{k ∈ C_{n} : 1_{I}(k) + 1_{I}(k + j) = 1\}|}{n2^{n/3}} + ∑_{\begin{matrix}k∈C_{n} \\ |A∩α^{k}(x)| odd \end{matrix}} \frac{1_{I}(k) + n1_{C_{n}\I}(k)}{n^{2}2^{n/3}})

≍ d_{C_{n}}(0, j) + \frac{1}{n^{2}2^{n/3}} ∑_{I∈I} ∑_{k∈C_{n}} |\{A ⊆ I : |A ∩ α^{k}(x)| odd\}|· (1_{I}(k) + n1_{C_{n}\I}(k))

≍ d_{C_{n}}(0, j) + \frac{1}{n^{2}} ∑_{I∈I} ∑_{\begin{matrix}k∈C_{n} \\ I∩α^{k}(x) ∅ \end{matrix}} (1_{I}(k) + n1_{C_{n}\I}(k)).  (37)

It suffices to prove the Lipschitz condition ∥f (x, j) − f (∅, 0)∥_{1} ρ((x, j), (∅, 0))for the generators of C_{2} ≀C_{n}, i.e. when (x, j) ∈ {({0}, 0), (∅, 1)}. This follows immediately from (37) since when (x, j) = (∅, 1) then the second summand in (37) is empty, and therefore ∥f (∅, 1) − f (∅, 0)∥_{1} ≍ 1 = ρ((∅, 1), (∅, 0)), and

∥f (\{0\}, 0) − f (∅, 0)∥_{1} ≍ \frac{1}{n^{2}} ∑_{I∈I} ∑_{k∈I} (1_{I}(k) + n1_{C_{n}\I}(k))≍ 1 ρ((\{0\}, 0), (∅, 0)).

To prove the lower bound ∥f (x, j)−f (∅, 0)∥_{1} ρ((x, j), (∅, 0))suppose that ℓ ∈ x is a point of x at a maximal distance from 0 in C_{n}. By considering only the terms in (37) for which α^{k}(ℓ) ∈ I we see that

∥f (x, j) − f (∅, 0)∥_{1} d_{C_{n}}(0, j) + \frac{1}{n^{2}} ∑_{I∈I} ∑_{k∈α^{−ℓ}(I)}(1_{I}(k) + n1_{C_{n}\I}(k))

≍ d_{C_{n}}(0, j) + \frac{1}{n^{2}} ∑_{I∈I} |I ∩ α^{−ℓ}(I)|+ \frac{1}{n} ∑_{I∈I} |α^{−ℓ}(I) \ I| d_{C_{n}}(0, j) + (1 + d_{C_{n}}(0, ℓ)) ρ ((x, j), (∅, 0)).

This completes the proof that f is bi-Lipschitz with O(1) distortion.

Remark 4.1. Fix s ∈ (1/2, 1) and consider the embedding f : C_{2} ≀C_{n} → ⨁ _{I∈I} ⨁ _{A⊆I} ℓ_{2}(C_{n}) given by

f (x, j) ⨁_{I∈I} ⨁_{A⊆I} ((−1)^{|A∩α^{k}(x)|} · \frac{1_{I}(k + j) + \sqrt{n}· [d_{C_{n}}(k + j, I)]^{s− \frac{1}{2}}}{n2^{n/6}} )_{k∈C_{n}}.

Arguing similarly to [5] (and the above) shows that ρ(u, v)^{s} ∥f (u) − f (v)∥_{2} ρ(u, v) for all u, v ∈ C_{2} ≀C_{n}, where the implied constants are independent of n. By a standard limiting argument it follows that α^{∗}(C_{2}≀ ) = 1. This fact was first proved by Tessera in [37] via a different approach.

Second embedding of C_{2} ≀C_{n} into L_{1}. Let J be the set of all arcs in C_{n}. In what follows for J ∈ J we let J^{∘} denote the interior of J. Let {v_{J,A}: J ∈ J, A ⊆ J} be disjointly supported unit vectors in L_{1}. Define f : C_{2} ≀C_{n} → ⊕ L_{1} by

f (x, j) (ne^{\frac{2πij}{n}} )⊕ (\frac{1}{n} ∑_{J∈J} 1_{\{j J^{∘}\}}v_{J,x∩J} ).

As before, since the metric on C_{2} ≀C_{n} given by ∥f (x, j) − f (x′, j′)∥_{1} is C_{2} ≀C_{n}-invariant, it suffices to show that ∥f (x, j) − f (∅, 0)∥_{1} ≍ ρ((x, j), (∅, 0)) for all (x, j) ∈ C_{2} ≀C_{n}. Now,

∥f (x, j) − f (∅, 0)∥_{1} ≍ d_{C_{n}}(0, j) + \frac{1}{n} ∑_{J∈J} ∥1_{\{j J^{∘}\}}v_{J,x∩J} − 1_{\{0 J^{∘}\}}v_{J,∅}∥_{1}

= d_{C_{n}}(0, j) + \frac{1}{n} ∑_{\begin{matrix}J∈J \\ x∩J=∅ \end{matrix}} |1_{\{j J^{∘}\}}− 1_{\{0 J^{∘}\}}| + \frac{1}{n} ∑_{\begin{matrix}J∈J \\ x∩J ∅ \end{matrix}} (1_{\{j J^{∘}\}}+ 1_{\{0 J^{∘}\}}) . (38)

We check the Lipschitz condition for the generators (∅, 1) and ({0}, 0) as follows:

∥f (∅, 1) − f (∅, 0)∥_{1} ≍^{(38)} 1 + \frac{1}{n} |\{J ∈ J : |\{0, 1\} ∩ J^{∘}|= 1\} | ≍ 1 = ρ((∅, 1), (∅, 0)),

and

∥f (\{0\}, 0) − f (∅, 0)∥_{1} ≍^{(38)} \frac{1}{n} |\{J ∈ J : 0 ∈ J \ J^{∘}\}| ≍ 1 = ρ((\{0\}, 0), (∅, 0)).

Hence ∥f (x, j) − f (∅, 0)∥_{1} ρ((x, j), (∅, 0)) for all (x, j) ∈ C_{2} ≀C_{n}.

To prove the lower bound ∥f (x, j)−f (∅, 0)∥_{1} ρ((x, j), (∅, 0))suppose that ℓ ∈ x is a point of x at a maximal distance from 0 in C_{n}. Then

∥f (x, j)−f (∅, 0)∥_{1} ^{(38)} d_{C_{n}}(0, j)+\frac{1}{n} ∑_{\begin{matrix}J∈J \\ ℓ∈J \end{matrix}} (1_{\{j J^{∘}\}}+ 1_{\{0 J^{∘}\}}) ≍ d_{C_{n}}(0, j)+\frac{1}{n} |\{J ∈ J : ℓ ∈ J ∧ \{0, j\} \ J^{∘} ∅\}|

d_{C_{n}}(0, j) + \frac{(ℓ + 1)(n − ℓ)}{n} ≍ d_{C_{n}}(0, j) + d_{C_{n}}(0, ℓ) + 1 ≍ ρ((x, j), (∅, 0)), (39)

Where in (39) we used the fact that the intervals {[a, b] : a ∈ {0, …, ℓ}, b ∈ {ℓ, …, n − 1}}do not contain 0 in their interior, but do contain ℓ.

Remark 4.2. A separable metric space embeds with distortion D into L_{p} if and only if all its finite subsets do. Therefore our embeddings for C_{2}≀C_{n} into L_{1} imply that C_{2}≀ admits a bi-Lipschitz embedding into L_{1}. This can also be seen via the explicit embedding F(x, j) j ⊕ (ψ(x, j) − ψ(0, 0)), where

F(x, j) ∑_{k≥j} v_{[k,∞),x∩[k,∞)} + ∑_{k≤j} v_{(−∞,k],x∩(−∞,k]} ,

and {v_{J,A}: J ∈ {[k, ∞)}_{k∈} ∪ {(−∞, k]}_{k∈}, A ⊆ J} are disjointly supported unit vectors in L_{1}.

5 Edge Markov type need not imply Enflo type

A Markov chain {Z_{t}}_{t=0}^{∞} with transition probabilities a_{ij} (Z_{t+1} = j | Z_{t} = i) on the state space {1, …, n} is stationary if π_{i} (Z_{t} = i) does not depend on t and it is reversible if π_{i} a_{ij} = π_{j} a_{ji} for every i, j ∈ {1, …, n}. Given a metric space (X, d_{X}) and p ∈ [1, ∞), we say that X has Markov type p if there exists a constant K > 0 such that for every stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n}, every mapping f : {1, …, n} → X and every time t ∈ ,

[d_{X}(f (Z_{t}), f (Z_{0}))^{p}] ≤ K^{p} t [d_{X}(f (Z_{1}), f (Z_{0}))^{p}].  (40)

The least such K is called the Markov type p constant of X, and is denoted M_{p}(X). Similarly, given D > 0 we let M_{p}^{≤D}(X) denote the least constant K satisfying (40) with the additional restriction that d_{X}(f (Z_{0}), f (Z_{1})) ≤ D holds pointwise. We call M_{p}^{≤D}(X) the D-bounded increment Markov type p constant of X. Finally, if (X, d_{X}) is an unweighted graph equipped with the shortest path metric then the edge Markov type p constant of X, denoted M_{p}^{edge}(X), is the least constant K satisfying (40) with the additional restriction that f (Z_{0})f (Z_{1}) is an edge (pointwise).

The fact that L_{2} has Markov type 2 with constant 1, first noted by K. Ball [7], follows from a simple spectral argument (see also inequality (8) in [28]). Since for p ∈ [1, 2] the metric space (L_{p}, ∥x − y∥_{p}^{p/2})embeds isometrically into L_{2} (see [42]), it follows that L_{p} has Markov type p with constant 1. For p > 2 it was shown in [28] that L_{p} has Markov type 2 with constants O ( \sqrt{p}). We refer to [28] for a computation of the Markov type of various additional classes of metric spaces.

A metric space (X, d_{X}) is said to have Enflo type p if there exists a constant K such that for every n ∈ and every f : {−1, 1}^{n} → X,

[d_{X}(f (ε), f (−ε))^{p}]

≤ T^{p} ∑_{j=1}^{n} [d_{X}(f (ε_{1}, …, ε_{j−1} , ε_{j}, ε_{j+1} , …, ε_{n}), f (ε_{1}, …, ε_{j−1} , −ε_{j}, ε_{j+1} , …, ε_{n}))^{p}], (41)

where the expectation is with respect to the uniform measure on {−1, 1}^{n}. In [29] it was shown that Markov type p implies Enflo type p. We define analogously to the case of Markov type the notions of bounded increment Enflo type and edge Enflo type.

The notions of Enflo type and Markov type were introduced as non-linear analogues of the fundamental Banach space notion of Rademacher type. We refer to [16, 10, 7, 29, 27, 28] and the references therein for background on this topic and many applications. In Banach space theory the notion analogous to bounded increment Markov type is known as equal norm Rademacher type. It is well known (see [38]) that for Banach spaces equal norm Rademacher type 2 implies Rademacher type 2 and that for 1 < p < 2 equal norm Rademacher type p implies Rademacher type q for every q < p (but is does not generally imply Rademacher type p). It is natural to ask whether the analogous phenomenon holds true for the above metric analogues of Rademacher type. Here we show that this is not the case.

It follows from Theorem 1.2 that α^{∗}( ≀ ) ≥ \frac{2}{3}. Therefore for every 0 < α < \frac{2}{3} there is a mapping F : ≀ → L_{2} such that

x, y ∈ ≀ ⟹ d_{≀} (x, y)^{α} ∥F(x) − F(y)∥_{2} d_{≀} (x, y).

Fix a stationary reversible Markov chain {Z_{t}}_{t=0}^{∞} on {1, …, n} and a mapping f : {1, …, n} → ≀ such that d_{≀} (f (Z_{0}), f (Z_{1})) ≤ D holds pointwise. Using the fact that L_{2} has Markov type 2 with constant 1 we deduce that

[d_{≀} (f (Z_{t}), f (Z_{0}))^{2α}] [∥F ∘ f (Z_{t}) − F ∘ f (Z_{0})∥ _{2}^{2}] ≤ t [∥F ∘ f (Z_{1}) − F ∘ f (Z_{0})∥ _{2}^{2}]

t [d_{≀} (f (Z_{1}), f (Z_{0}))^{2}] D^{2(1−α)} t [d_{≀} (f (Z_{1}), f (Z_{0}))^{2α}].

Thus

M_{2α}^{≤D}( ≀ ) D^{1−α} .

In particular ≀ has D-bounded increment Markov type p and edge Markov type p for every p < \frac{4}{3}.

On the other hand we claim that ≀ does not have Enflo type p for any p > 1. This is seen via an argument that was used by Arzhantseva, Guba and Sapir in [3]. Fix n ∈ and define f : {−1, 1}^{n} → ≀ by

f (ε_{1}, …, ε_{n}) ( ∑_{j=n+1}^{2n} ε_{j−n}nδ_{j}, 0),  (42)

where δ_{j} is the delta function supported at j. Then for every ε ∈ {−1, 1}^{n},

d_{≀} (f (ε), f (−ε)) ≍ n^{2}  (43)

and for every j ∈ {1, …, n},

d_{≀} (f (ε_{1}, …, ε_{j−1} , ε_{j}, ε_{j+1} , …, ε_{n}), f (ε_{1}, …, ε_{j−1} , −ε_{j}, ε_{j+1} , …, ε_{n}))≍ n.  (44)

Therefore if ≀ has Enflo type p, i.e. if (41) holds true, then for every n ∈ we have n^{2p} n^{p+1}, implying that p ≤ 1.

6 A lower bound on β^{∗}(G ≀H)

In this section we shall prove (8), which is a generalization of Èrshler’s work [17]. Namely, we will prove the following theorem:

Theorem 6.1. Let G and H be finitely generated groups. If H has linear growth (or equivalently, by Gromov’s theorem [19], H has a subgroup of finite index isomorphic to ) then β^{∗}(G ≀H) ≥ \frac{1+β^{∗}(G)}{2}. For all other finitely generated groups H we have β^{∗}(G ≀H) = 1.

Assume that G is generated by a finite symmetric set S_{G} ⊆ G and H is generated by a finite symmetric set S_{H} ⊆ H. We also let e_{G}, e_{H} denote the identity elements of G and H, respectively. Given g_{1}, g_{2} ∈ G and h ∈ H define a mapping f_{g_{1},g_{2}}^{h} : H → G by

f_{g_{1},g_{2}}^{h}(x) \{ \begin{matrix}g_{1} & if x = e_{H}, \\ g_{2} & if x = h, \\ e_{G} & otherwise. \end{matrix}

It is immediate to check that the set

S_{G≀H} {f_{g_{1},g_{2}}^{h} : g_{1}, g_{2} ∈ S_{G} and h ∈ S_{H}}

is symmetric and generates G ≀H.

From now on, we will assume that the metrics on G, H and G ≀H are induced by S_{G}, S_{H} and S_{G≀H}, respectively. Analogously we shall denote by {W_{k}^{G}}_{k=0}^{∞}, {W_{k}^{H}}_{k=0}^{∞} and {W_{k}^{G≀H}}_{k=0}^{∞} the corresponding random walks, starting at the corresponding identity elements.

Theorem 6.2. Assume that for some β ∈ [0, 1] we have

[d_{G}(W_{n}^{G}, e_{G})] n^{β},  (45)

where the implied constant may depend on S_{G}. If H has linear growth then

[d_{G≀H}(W_{n}^{G≀H}, e_{G≀H})] n^{\frac{1+β}{2}} .  (46)

If H has quadratic growth then

[d_{G≀H}(W_{n}^{G≀H}, e_{G≀H})] \frac{n}{(1 + logn)^{1−β}} .  (47)

If the random walk {W_{n}^{H}}_{n=0}^{∞} is transient then

[d_{G≀H}(W_{n}^{G≀H}, e_{G≀H})] n.  (48)

The implied constants in (46), (47) and (48) may depend on S_{G} and S_{H}.

Theorem 6.1 is a consequence of Theorem 6.2 since by Varopoulos’ celebrated result [39, 41] (which relies on Gromov’s growth theorem [19]. See [24] and [43] for a detailed discussion), the three possibilities in Theorem 6.2 are exhaustive for infinite finitely generated groups H. In the case when the random walk on H is transient, Theorem 6.2 was previously proved by Kaĭmanovich and Vershik in [24].

The following lemma will be used in the proof of Theorem 6.2.

Lemma 6.3. Define for n ∈ ,

ψ_{H}(n) \{ \begin{matrix}\sqrt{n} & if H has linear growth, \\ 1 + logn & if H has quadratic growth, \\ 1 & otherwise. \end{matrix}

Then

[|{0 ≤ k ≤ n : W_{k}^{H} = e_{H}}|^{β}] ψ_{H}(n)^{β},  (49)

and

[|W_{[0,n]}^{H}|] \frac{n}{ψ_{H}(n)},  (50)

where W_{[0,n]}^{H} {W_{0}^{H}, …, W_{n}^{H}} . Proof. By a theorem of Varopoulos [40, 41] (see also [23] and Theorem 4.1 in [43]) for every k ≥ 0,

[W_{k}^{H} = e_{H}]+ [W_{k+1}^{H} = e_{H}]≍ \{ \begin{matrix}\frac{1}{\sqrt{k+1}} & if H has linear growth, \\ \frac{1}{k+1} & if H has quadratic growth, \end{matrix}  (51)

and if H has super-quadratic growth then ∑ _{k=1}^{∞} [W_{k}^{H} = e_{H}]< ∞. Hence, if we denote

X_{n} |{0 ≤ k ≤ n : W_{k}^{H} = e_{H}}| = ∑_{k=0}^{n} 1_{{W_{k}^{H}=e_{H}}}

then it follows that

[X_{n}]= ∑_{k=0}^{n} [W_{k}^{H} = e_{H}] ≍^{(51)} ψ_{H}(n).  (52)

To prove (49) note that

[X_{n}^{2}]= ∑_{i,j=0}^{n} [W_{i}^{H} = e_{H} ∧ W_{j}^{H} = e_{H}] ≤ 2 ∑_{i=0}^{n} ∑_{k=0}^{n−i} [W_{i}^{H} = e_{H}]· [W_{k}^{H} = e_{H}]≤ 2 ( [X_{n}])^{2} ≍^{(52)} ψ_{H}(n)^{2}.

Using Hölder’s inequality we deduce that

ψ_{H}(n) ≍ [X_{n}]= [Xn^{\frac{β}{2−β}} · Xn^{\frac{2−2β}{2−β}} ]≤ ( [X_{n}^{β}])^{\frac{1}{2−β}} ( [X_{n}^{2}])^{\frac{1−β}{2−β}} ( [X_{n}^{β}])^{\frac{1}{2−β}} ψ_{H}(n)^{\frac{2−2β}{2−β}} .

This simplifies to [X_{n}^{β}] ψ_{H}(n)^{β}, which is precisely (49). We now pass to the proof of (50). For every k ∈ {1, …, n} denote by V_{1}, …, V_{k} the first k elements of H that were visited by the walk {W_{j}^{H}}_{j=0}^{∞}. Write

Y_{k} |{0 ≤ j ≤ n : W_{j}^{H} ∈ {V_{1}, …, V_{k}} }|.

Then

[Y_{k}]= ∑_{j=1}^{k} [|{0 ≤ j ≤ n : W_{j}^{H} = V_{j}}|] ≤ k ∑_{r=0}^{n} [W_{r}^{H} = e_{H}] ≍^{(52)} kψ_{H}(n).

Therefore for every k ∈ ,

[|W_{[0,n]}^{H}|≤ k] ≤ [Y_{k} ≥ n]≤ \frac{[Y_{k}]}{n} \frac{kψ_{H}(n)}{n}.

Hence we can choose k ≍ \frac{n}{ψ_{H}(n)} for which [|W_{[0,n]}^{H}|≥ k] ≥ \frac{1}{2}, implying (50).

Proof of Theorem 6.2. We may assume that n ≥ 4. Let Q_{H} : G ≀H → H be the natural projection, i.e. Q_{H}(f, x) x. Also, for every x ∈ H let Q_{G}^{x} : G ≀H → G be the projection Q_{G}^{x}(f, y) f (x).

Fix n ∈ . For every h ∈ H denote

T_{h} |{0 ≤ k ≤ n : Q_{H} (W_{k}^{G≀H})= h}|.

The set of generators S_{G≀H} was constructed so that the random walk on G ≀H can be informally described as follows: at each step the “H coordinate” is multiplied by a random element h ∈ S_{H}. The “G coordinate” is multiplied by a random element g_{1} ∈ S_{G} at the original H coordinate of the walker, and also by a random element g_{2} ∈ S_{G} (which is independent of g_{1}) at the new H coordinate of the walker. This immediately implies that the projection {Q_{H} (W_{k}^{G≀H})}_{k=0}^{∞} has the same distribution as {W_{k}^{H}}_{k=0}^{∞}. Moreover, conditioned on {T_{h}}_{h∈H} and on Q_{H} (W_{n}^{G≀H}), if h ∈ H \ {e_{H}, Q_{H} (W_{n}^{G≀H})}then the element Q_{G}^{h}(W_{n}^{G≀H})∈ G has the same distribution as W_{2T_{h}}^{G}. If h ∈ {e_{H}, Q_{H} (W_{n}^{G≀H})}and e_{H} Q_{H} (W_{n}^{G≀H})then Q_{G}^{h}(W_{n}^{G≀H})has the same distribution as W_{max{2T_{h}−1,0}}^{G}, and if e_{H} = Q_{H} (W_{n}^{G≀H})then Q_{G}^{h}(W_{n}^{G≀H})has the same distribution as W_{2T_{h}}^{G}.

These observations imply, using (45), that for every h ∈ H we have [d_{G}(Q_{G}^{h}(W_{n}^{G≀H}), e_{G})] [T_{h}^{β}]. Writing A_{ℓ} {h = W_{ℓ}^{H} ∧ h W_{[0,ℓ−1]}^{H}}we see that

[T_{h}^{β}]≥ ∑_{ℓ=0}^{⌊n/2⌋} (A_{ℓ}) · [T_{h}^{β}|A_{ℓ}]^{(49)} ∑_{ℓ=0}^{⌊n/2⌋} (A_{ℓ}) · ψ_{H}(n/2)^{β} = [h ∈ W_{[0,⌊n/2⌋]}^{H}]ψ_{H}(n/2)^{β}.

Hence,

[d_{G≀H}(W_{n}^{G≀H}, e_{G≀H})] ∑_{h∈H} [d_{G}(Q_{G}^{h}(W_{n}^{G≀H}), e_{G})] ∑_{h∈H} [T_{h}^{β}]

ψ_{H} (n)^{β} ∑_{h∈H} [h ∈ W_{[0,⌊n/2⌋]}^{H}]= ψ_{H}(n)^{β} · [|W_{[0,⌊n/2⌋]}^{H}|] ^{(50)} \frac{n}{ψ_{H}(n)^{1−β}} .

This is precisely the assertion of Theorem 6.2.

Remark 6.4. In [13] de Cornulier, Stalder and Valette show that if G is a finite group, then for every p ≥ 1 we have α_{p}^{#}(G ≀F_{n}) ≥ \frac{1}{p}, where F_{n} denotes the free group on n ≥ 2 generators. Note that in combination with Lemma 2.3 this implies that we actually have α_{p}^{#}(G ≀F_{n}) ≥ max\{\frac{1}{p}, \frac{1}{2}\}. This bound is sharp due to Theorem 1.1 and the fact that β^{∗}(G ≀F_{n}) = 1. We prove here the following stronger result, which was motivated by a question of A. Vallette (personal communication.)

Proposition 6.5. Let X be a Banach space with modulus of smoothness of power type p and suppose that G is a nontrivial group, and H is a group whose volume growth is at least quadratic. Then α_{X}^{∗}(G ≀H) ≤ \frac{1}{p}. In particular α_{p}^{∗}(G ≀F_{2}) = max\{\frac{1}{p}, \frac{1}{2}\}.

Proof. It is enough to deal with the case G = C_{2}. If H is amenable then by Theorem 6.1we have β^{∗}(C_{2}≀H) = 1, so that the required result follows from the result of [4] and the fact that X has Markov type p [28]. If H is nonamenable then it has exponential growth (see [30]). Thus γ lim_{r→∞} |B(e_{H}, r)|^{1/r} > 1, where B(x, r) denotes the ball of radius r centered at x in the word metric on H (note that the existence of the limit follows from submultiplicativity). Fix δ ∈ (0, 1) such that η \frac{(1−δ)^{2}γ}{1+δ} > 1 and let k_{0} ∈ be such that for all k ≥ k_{0} we have [(1 − δ)γ]^{k} ≤ |B(e_{H}, k)| ≤ [(1 + δ)γ]^{k}. For k ≥ k_{0} let {x_{1}, …, x_{N}} be a maximal subset of B(e_{H}, 2k) such that the balls {B(x_{i}, k/2)}_{i=1}^{N} are disjoint. Maximality implies that the balls {B(x_{i}, k)}_{i=1}^{N} cover B(e_{H}, 2k), so that

[(1 + δ)γ]^{k}N ≥ N|B(e_{H}, k)| ≥ |⋃_{i=1}^{N} B(x_{i}, k)|≥ |B(e_{H}, 2k)| ≥ [(1 − δ)γ]^{2k},

which simplifies to give the lower bound N ≥ η^{k}. Thus k logN.

Fix α ∈ [0, 1] and assume that F : C_{2} ≀H → X satisfies

x, y ∈ C_{2} ≀H ⟹ d_{C_{2}≀H}(x, y)^{α} ∥F(x) − F(y)∥ d_{C_{2}≀H}(x, y).

Our goal is to prove that α ≤ \frac{1}{p}. For every ε = (ε_{1}, …, ε_{N}) ∈ \{−1, 1\}^{N} define ψ_{ε} : H → C_{2} by ψ_{ε}(x_{i}) = \frac{1+ε_{i}}{2} , and ψ_{ε}(x) = 0 if x {x_{1}, …, x_{N}}. Let f : {−1, 1}^{N} → C_{2} ≀H be given by f (ε) = (ψ_{ε}, e_{H}). It is easy to check that for all ε, ε′ ∈ {−1, 1}^{N} we have

\frac{k}{2}∥ε − ε′∥_{1} ≤ d_{C_{2}≀H}(f (ε), f (ε′)) ≤ 4k∥ε − ε′∥_{1}.

(Indeed, to verify the right-hand inequality, let i_{1}, …, i_{m} denote the m = ∥ε − ε′∥_{1}/2 indices where ε and ε′ differ. Consider the path from f (ε) to f (ε′) in C_{2} ≀H obtained by moving the lamplighter along the shortest path in H from e_{H} to x_{i_{1}}, switching the lamp there, then moving the lamplighter to x_{i_{2}}, switching the lamp there, etc., and finally after switching the lamp at x_{i_{m}}, returning the lamplighter to e_{H}.) Metric spaces with Markov type p also have Enflo type p [29], i.e. they satisfy (41). Thus we can apply the Enflo type inequality (41) to the mapping F ∘ f : {−1, 1}^{N} → X and deduce that (Nk)^{αp} Nk^{p}. Consequently, N^{αp} Nk^{p} N(logN)^{p}. Since the last inequality holds for arbitrarily large N, we infer that αp ≤ 1.

7 Discussion and further questions

In this section we discuss some natural questions that arise from the results obtained in this paper. We start with the following potential converse to (3):

Question 7.1. Is it true that for every finitely generated amenable group G,

α^{∗}(G) = \frac{1}{2β^{∗}(G)} ?

If true, Question 7.1, in combination with Corollary 1.3, would imply a positive solution to the following question:

Question 7.2. Is it true that for every finitely generated amenable group G,

α^{∗}(G ≀ ) = \frac{2α^{∗}(G)}{2α^{∗}(G) + 1} ?

Additionally, since β^{∗}(G) ≤ 1, a positive solution to Question 7.1 would imply a positive solution to the following question:

Question 7.3. Is it true that for every finitely generated amenable group G,

α^{∗}(G) ≥ \frac{1}{2} ?

Using (27), and arguing analogously to Lemma 3.1 while using the L_{1} embedding of C_{2} ≀ in Section 4, we have the following fact:

Lemma 7.4. If a finitely generated group G admits a bi-Lipschitz embedding into L_{1} then so does G ≀ .

Question 7.5. Is it true that for every finitely generated amenable group G we have α_{1}^{∗}(G) = 1?

Since the metric space (L_{1}, \sqrt{∥x − y∥_{1}})embeds isometrically into L_{2} (see [42]), a positive solution to Question 7.5 would imply a positive solution to Question 7.3.

Our repertoire of groups G for which we know the exact value of α^{∗}(G) is currently very limited. In particular, we do not know the answer to the following question:

Question 7.6. Does there exist a finitely generated amenable group G for which α^{∗}(G) is irrational? Does there exist a finitely generated amenable group G for which \frac{2}{3} < α^{∗}(G) < 1?

In [44] Yu proved that for every finitely generated hyperbolic group G there exists a large p > 2 for which α_{p}^{#}(G) ≥ \frac{1}{p}. In view of Theorem 1.1 it is natural to ask:

Question 7.7. Is it true that for every finitely generated hyperbolic group G there exists some p ≥ 1 for which α_{p}^{#}(G) ≥ \frac{1}{2}?

We do not know the value of α_{p}^{∗}( ≀ ) for 1 < p < 2. The following lemma contains some bounds for this number:

Lemma 7.8. For every 1 < p < 2,

\frac{p}{2p − 1} ≤ α_{p}^{∗}( ≀ ) ≤ min\{ \frac{p + 1}{2p} , \frac{4}{3p}\} .  (53)

Proof. The lower bound in (53) is an immediate corollary of Theorem 3.3. Since β^{∗}( ≀ ) ≥ \frac{3}{4}, the upper bound α_{p}^{∗}( ≀ ) ≤ \frac{4}{3p} follows immediately from the results of [4] (or alternatively Theorem 1.1), using the fact that L_{p}, 1 < p < 2, has Markov type p. The remaining upper bound is an application of the fact that L_{p}, 1 < p < 2, has Enflo type p, which is similar to an argument in [3]. Indeed, fix a mapping F : ≀ → L_{p} such that

x, y ∈ ≀ ⟹ d_{≀} (x, y)^{α} ∥F(x) − F(y)∥_{p} d_{≀} (x, y).

Let f : {−1, 1}^{n} → ≀ be as in (42). Plugging the bounds in (43) and (44) into the Enflo type p inequality (41) for the mapping F ∘ f : {−1, 1}^{n} → L_{p}, we see that for all n ∈ we have n^{2pα} n^{p+1}, implying that α ≤ \frac{p+1}{2p}.

Question 7.9. Evaluate α_{p}^{∗}( ≀ ) for 1 < p < 2.

We end with the following question which arises naturally from the discussion in Section 5:

Question 7.10. Does there exist a finitely generated group G which has edge Markov type 2 but does not have Enflo type p for any p > 1?

We do not even know whether there exists a finitely generated group G which has edge Markov type 2 but does not have Markov type 2. Note that the results of Section 5 imply that if 1 < p < \frac{4}{3} then the metric space ( ≀ , d_{≀}^{p/2}) has bounded increment Markov type 2, but does not have Enflo type q for any q > \frac{2}{p}. However, this metric is not a graph metric.

Acknowledgements

We are grateful to Laurent Saloff-Coste and a referee for helpful comments.

References

[1] I. Aharoni, B. Maurey, and B. S. Mityagin. Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces. Israel J. Math., 52(3):251–265, 1985.

[2] G. Arzhantseva, C. Drutu, and M. Sapir. Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. Preprint, 2006. Available at http://arxiv.org/abs/math/0612378.

[3] G. N. Arzhantseva, V. S. Guba, and M. V. Sapir. Metrics on diagram groups and uniform embeddings in a Hilbert space. Comment. Math. Helv., 81(4):911–929, 2006.

[4] T. Austin, A. Naor, and Y. Peres. The wreath product of with has Hilbert compression exponent

    \frac{2}{3}. Preprint, 2007. Available at http://arxiv.org/abs/0706.1943.

[5] T. Austin, A. Naor, and A. Valette. The Euclidean distortion of the lamplighter group. Preprint, 2007.

    Available at http://arxiv.org/abs/0705.4662.

[6] U. Bader, A. Furman, T. Gelander, and N. Monod. Property (T) and rigidity for actions on Banach spaces. Acta. Math., 198(1):57–105, 2007.

[7] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[8] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[9] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[10] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

[11] S. Campbell and G. A. Niblo. Hilbert space compression and exactness of discrete groups. J. Funct. Anal., 222(2):292–305, 2005.

[12] T. Coulhon. Random walks and geometry on infinite graphs. In Lecture notes on analysis in metric spaces (Trento, 1999), Appunti Corsi Tenuti Docenti Sc., pages 5–36. Scuola Norm. Sup., Pisa, 2000.

[13] Y. de Cornulier, Y. Stalder, and A. Valette. Proper actions of lamplighter groups associated with free groups. Preprint, 2007. Available at http://arxiv.org/abs/0707.2039.

[14] Y. de Cornulier, R. Tessera, and A. Valette. Isometric group actions on Hilbert spaces: growth of cocycles. Preprint 2005. Available at http://xxx.lanl.gov/abs/math/0509527. To appear in Geom. Funct. Anal.

[15] R. Durrett. Probability: theory and examples. Duxbury Press, Belmont, CA, second edition, 1996.

[16] P. Enflo. Uniform homeomorphisms between Banach spaces. In Séminaire Maurey-Schwartz (1975– 1976), Espaces, L^{p}, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, page 7. Centre Math., École Polytech., Palaiseau, 1976.

[17] A. G. Èrshler. On the asymptotics of the rate of departure to infinity. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 283(Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 6):251–257, 263, 2001.

[18] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56:121–155, 1976.

[19] M. Gromov. Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math., (53):53–73, 1981.

[20] E. Guentner and J. Kaminker. Exactness and uniform embeddability of discrete groups. J. London Math. Soc. (2), 70(3):703–718, 2004.

[21] O. Hanner. On the uniform convexity of L^{p} and l^{p}. Ark. Math., 3, 1956.

[22] C. D. Hardin. Isometries on subspaces of L_{p}. Indiana Univ. Math. J., 30:449–465, 1981.

[23] W. Hebisch and L. Saloff-Coste. Gaussian estimates for Markov chains and random walks on groups. Ann. Probab., 21(2):673–709, 1993.

[24] V. A. Kaĭmanovich and A. M. Vershik. Random walks on discrete groups: boundary and entropy. Ann. Probab., 11(3):457–490, 1983.

[25] H. Kesten. Full Banach mean values on countable groups. Math. Scand., 7:146–156, 1959.

[26] J. R. Lee, A. Naor, and Y. Peres. Trees and Markov convexity. Preprint 2005. Available at

    http://arxiv.org/abs/0706.0545. To appear in Geom. Funct. Anal.

[27] M. Mendel and A. Naor.  Metric cotype.  Preprint, 2005. Available at

    http://arxiv.org/abs/math/0506201. To appear in Ann. of Math.

[28] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[29] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

[30] A. L. T. Paterson. Amenability, volume 29 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 1988.

[31] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4):326–350, 1975.

[32] C. Pittet and L. Saloff-Coste. On random walks on wreath products. Ann. Probab., 30(2):948–977, 2002.

[33] A. I. Plotkin. Isometric operators on subspaces of L_{p}. Dokl. Akad. Nauk. SSSR, 193:537–539, 1970.

[34] D. Revelle. Rate of escape of random walks on wreath products and related groups. Ann. Probab., 31(4):1917–1934, 2003.

[35] W. Rudin. L_{p}-isometries and equimeasurability. Indiana Univ. Math. J., 25:215–228, 1976.

[36] Y. Stalder and A. Valette. Wreath products with the integers, proper actions and Hilbert space compression. Geom. Dedicata, 124(1):199–211, 2007.

[37] R. Tessera. Asymptotic isoperimetry on groups and uniform embeddings into Banach spaces. Preprint,

    2006. Available at http://arxiv.org/abs/math/0603138.

[38] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.

[39] N. T. Varopoulos. Random walks on groups. Applications to Fuchsian groups. Ark. Mat., 23(1):171– 176, 1985.

[40] N. T. Varopoulos. Théorie du potentiel sur les groupes nilpotents. C. R. Acad. Sci. Paris Sér. I Math., 301(5):143–144, 1985.

[41] N. T. Varopoulos. Convolution powers on locally compact groups. Bull. Sci. Math. (2), 111(4):333– 342, 1987.

[42] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

[43] W. Woess. Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2000.

[44] G. Yu. Hyperbolic groups admit proper affine isometric actions on l^{p}-spaces. Geom. Funct. Anal., 15(5):1114–1151, 2005.