L_{p} compression, traveling salesmen, and stable walks

Dedicated with admiration to the memory of Oded Schramm

Assaf Naor^{∗} Courant Institute

                naor@cims.nyu.edu

Yuval Peres Microsoft Research

                                       peres@microsoft.com

Abstract

We show that if H is a group of polynomial growth whose growth rate is at least quadratic then the L_{p} compression of the wreath product ≀H equals max\{\frac{1}{p}, \frac{1}{2}\}. We also show that the L_{p} compression of ≀ equals max\{\frac{p}{2p−1} , \frac{2}{3}\}and the L_{p} compression of ( ≀ )_{0} (the zero section of ≀ , equipped with the metric induced from ≀ ) equals max\{\frac{p+1}{2p} , \frac{3}{4}\}. The fact that the Hilbert compression exponent of ≀ equals \frac{2}{3} while the Hilbert compression exponent of ( ≀ )_{0} equals \frac{3}{4} is used to show that there exists a Lipschitz function f : ( ≀ )_{0} → L_{2} which cannot be extended to a Lipschitz function defined on all of ≀ .

1 Introduction

Let G be an infinite group which is generated by a finite symmetric set S ⊆ G and let d_{G} denote the leftinvariant word metric induced by S (formally we should use the notation d_{S}, but all of our statements below will be independent of the generating set). Assume for the moment that the metric space (G, d_{G}) does not admit a bi-Lipschitz embedding into Hilbert space^{1}. In such a setting the next natural step is to try to measure the extent to which the geometry of (G, d_{G}) is non-Hilbertian. While one can come up with several useful ways to quantify non-embeddabililty, the present paper is a contribution to the theory of compression exponents: a popular and elegant way of measuring non-bi-Lipschitz embeddability of infinite groups that was introduced by Guentner and Kaminker in [33].

The Hilbert compression exponent of G, denoted α^{∗}(G), is defined as the supremum of those α ≥ 0 for which there exists a Lipschitz function f : G → L_{2} satisfying ∥f (x) − f (y)∥_{2} ≥ cd_{G}(x, y)^{α} for every x, y ∈ G and some constant c > 0 which is independent of x, y. More generally, given a target metric space (X, d_{X}) the compression exponent of G in X, denoted α_{X}^{∗}(G), is the supremum of those α ≥ 0 for which there exists a Lipschitz function f : G → X satisfying d_{X}(f (x), f (y)) ≥ cd_{G}(x, y)^{α}. When X = L_{p} for some p ≥ 1 we shall use the notation α_{p}^{∗}(G) = α_{L_{p}}^{∗}(G) (thus α_{2}^{∗}(G) = α^{∗}(G)).

∗Research supported in part by NSF grants DMS-0528387, CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

1This assumption is not very restrictive, and in fact it is conjectured that if (G, d_{G}) does admit a bi-Lipschitz embedding into Hilbert space then G must have an Abelian subgroup of finite index. We refer to [24] for more information on this conjecture and its proof in some interesting special cases.

When (X, ∥ · ∥_{X}) is a Banach space one can analogously define the equivariant compression exponent of G in X, denoted α_{X}^{#}(G), as the supremum over α ≥ 0 for which there exists a G-equivariant^{2} mapping ψ : G → X satisfying ∥ψ(x) − ψ(y)∥_{X} ≥ cd_{G}(x, y)^{α}. We write as above α_{p}^{#}(G) = α_{L_{p}}^{#}(G) and α^{#}(G) = α_{2}^{#}(G). Recall that G is said to have the Haagerup property if there exists an equivariant function ψ : G → L_{2} such that inf{∥ψ(x) − ψ(y)∥_{2} : d_{G}(x, y) ≥ t} tends to infinity with t. We refer to the book [18] for more information on the Haagerup property and its applications. Thus the notion of equivariant compression exponent can be viewed as a quantitative refinement of the Haagerup property, and this is indeed the way that bounds on the equivariant compression exponent are usually used.

The parameters α_{X}^{∗}(G) and α_{X}^{#}(G) do not depend on the choice of symmetric generating set S, and are therefore genuine algebraic invariants of the group G. In [33] it was shown that if α^{#}(G) > \frac{1}{2} then G is amenable. This result was generalized in [47], where it was shown that for p ≥ 1 if X is a Banach space whose modulus of uniform smoothness has power type p (i.e. for every two unit vectors x, y ∈ X and τ > 0 we have ∥x + τy∥_{X} + ∥x − τy∥_{X} ≤ 2 + cτ^{p} for some c > 0 which does not depend on x, y, τ) and α_{X}^{#}(G) > \frac{1}{p}, then G is amenable. It was also shown in [33] that if α^{∗}(G) > \frac{1}{2} then the reduced C^{∗} algebra of G is exact.

Despite their intrinsic interest and a considerable amount of effort by researchers in recent years, the invariants α_{X}^{∗}(G), α_{X}^{#}(G) have been computed in only a few cases. It was shown in [3] that for any α ∈ [0, 1] there exists a finitely generated group G with α^{∗}(G) = α. In light of this fact it is quite remarkable that, apart from a few exceptions, in most of the known cases in which compression exponents have been computed they turned out to be equal to 1 or 0. A classical theorem of Assouad [5] implies that groups of polynomial growth have Hilbert compression exponent 1. On the other hand, Gromov’s random groups [32] have Hilbert compression exponent 0. Bourgain’s classical metrical characterization of superreflexivity [12] implies that finitely generated free groups have Hilbert compression exponent 1 (this interpretation of Bourgain’s theorem was first noted in [33]), and more generally it was shown in [14] that hyperbolic groups have Hilbert compression 1 and in [15] that so does any discrete group acting properly and co-compactly on a finite dimensional CAT(0) cubical complex. In [57] it was shown that co-compact lattices in connected Lie groups, irreducible lattices in semi-simple Lie groups of rank at least 2, polycyclic groups and certain semidirect products with (including wreath products^{3} of finite groups with and the Baumslag-Solitar group) all have Hilbert compression exponent 1. The first example of a group with Hilbert compression exponent in (0, 1) was found in [4], where it was proved that R. Thompson’s group F satisfies α^{∗}(F) = \frac{1}{2}. Another wellstudied case is the wreath product ≀ . In [4] and independently in [54] it was shown that α^{∗}( ≀ ) ≥ \frac{1}{2} (see also [31] for a different argument which yields the weaker bound α^{∗}( ≀ ) ≥ \frac{1}{3}). Moreover it was shown in [4] that α^{∗}( ≀ ) ≤ \frac{3}{4}, and a combination of the later results of [7] and [47], which established sharp upper and lower bounds on α^{∗}( ≀ ), respectively, settles the case of the Hilbert compression exponent of ≀ by showing that α^{∗}( ≀ ) = \frac{2}{3} (nevertheless, the \frac{3}{4} upper bound on α^{∗}( ≀ ) from [4] has a special meaning which is important for our current work—we will return to this topic later in this introduction). More generally, it was shown in [47] that if we define recursively _{1} = and _{(k+1)} = _{(k)} ≀ then α^{∗}( _{(k)}) = \frac{1}{2−2^{1−k}} . In [47] it was shown that α^{∗}(C_{2} ≀ ^{2}) = \frac{1}{2}, where C_{2} denotes the cyclic group of order 2 (the lower bound of \frac{1}{2} was proved earlier in [57]). Finally, it follows from [22, 47] that α^{∗}(C_{2}≀F_{n}) = α^{#}(C_{2}≀F_{n}) = \frac{1}{2}, where F_{n} is the free group on n ≥ 2 generators (the upper bound of \frac{1}{2} on α^{∗}(C_{2}≀F_{n}) is due to [47] while the lower bound on α^{#}(C_{2} ≀F_{n}) is the key result of [22]). Many of the above results have (at least partial) variants for the L_{p} compression exponents of the groups in question—-we stated here only the case of Hilbert compression exponents for the sake of simplicity, and we refer to the relevant papers for more information.

2A mapping ψ : G → X is called G-equivariant if there exists an action τ of G on X by affine isometries and a vector v ∈ X such that ψ(x) = τ(x)v for all x ∈ G. Equivalently there exists an action π on X by linear isometries such that φ ψ − v is a 1-cocycle with respect to π (we denote this by φ ∈ Z^{1}(G, π)), i.e., for every x, y ∈ G we have φ(xy) = π(x)φ(y) + φ(x). A key useful point here is that in this case ∥ψ(x) − ψ(y)∥_{X} is an invariant semi-metric on G.

3The (restricted) wreath product of G with H, denoted G ≀H, is defined as as the group of all pairs (f, x) where f : H → G has finite support (i.e. f (z) = e_{G}, the identity element of 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}, where δ_{s} is the function which takes the value s at e_{H} and the value e_{G} on H \ {e_{H}}.

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 difficulty of evaluating compression exponents is the main reason for our interest in this topic, and our purpose here is to devise new methods to compute them. In doing so we answer questions posed in [57, 47]. One feature of the known methods for computing compression exponents is that they involve a novel interplay between group theory and other mathematical disciplines such as metric geometry, Banach space theory, analysis and probability. It isn’t only the case that the latter disciplines are applied to group theory—it turns out that the investigation of compression exponents improved our understanding of issues in analysis and metric geometry as well (e.g. in [47] compression exponents were used to make progress on the theory of non-linear type). In the present paper we apply our new compression exponent calculations to the Lipschitz extension problem, and relate them to the Jones Traveling Salesman problem. These applications will be described in detail presently.

In [57] it was shown that for all d ∈ we have α^{∗}(C_{2} ≀ ^{d}) ≥ \frac{1}{d}. A different embedding yielding this lower bound was obtained in [47], together with the matching upper bound when d = 2. Thus, as stated above, α^{∗}(C_{2} ≀ ^{2}) = \frac{1}{2}. In Section 3 we investigate the value of α_{p}^{∗}(G ≀H) when G is a general group and H is a group of polynomial growth. A key feature of our result is that we obtain a lower bound on α_{p}^{∗}(G ≀H) which is independent of the growth rate of H. In combination with the upper bounds obtained in [47], our lower bound implies the following result:

Theorem 1.1. For every p ∈ [1, ∞) and every group H of polynomial growth whose growth is at least quadratic, we have:

α_{p}^{∗}( ≀H) = α_{p}^{∗}(C_{2} ≀H) = max\{ \frac{1}{p}, \frac{1}{2}\} .  (1)

As we explain in Remark 3.3 below, the embedding from [47] which yielded the identity α_{2}^{∗} (C_{2} ≀ ^{2}) = \frac{1}{2} was based on the trivial fact, which is special to 2 dimensions, that for every A ⊆ ^{2} of diameter D, the shortest path in ^{2} which covers A has length at most O (D^{2}). It therefore turns out that the previous method for bounding α_{p}^{∗} (C_{2} ≀ ^{d}) yields tight bounds only when p = d = 2 (this is made precise in Remark 3.3). Hence in order to prove (1) we devise a new embedding which is in the spirit of (but simpler than) the multi-scale arguments used in the proof of the Jones Traveling Salesman Theorem [38] (see also [50] and the survey [53]).

To explain the connection between our proof and the Jones Traveling Salesman Theorem take two elements (f, x), (g, y) in the “planar lamplighter group” C_{2} ≀ ^{2}, i.e., x, y ∈ ^{2} and f, g : ^{d} → {0, 1} with finite support. The distance between (f, x) and (g, y) in C_{2} ≀ ^{2} is, up to a factor of 2, the shortest path in the integer grid ^{2} which starts at x, visits all the sites w ∈ ^{2} at which f (w) and g(w) differ, and terminates at y. Jones [38] associates to every set A ⊆ ^{2} of diameter 1 a sequence of numbers, known as the (squares of the) Jones β numbers, whose appropriately weighted sum is (up to universal factors) the length of the shortest Lipschitz curve covering A, assuming such a curve exists. Focusing on our proof of the fact that α_{1}^{∗} (C_{2} ≀ ^{2}) = 1, in our setting we do something similar: we associate to every (f, x) ∈ C_{2} ≀ ^{2} a sequence of real numbers such that if we wish to estimate (up to logarithmic terms) the shortest traveling salesman tour starting at x, ending at y, and covering the symmetric difference of the supports of f and g, all we have to do is to compute the ℓ_{1} norm of the difference of the sequences associated to (f, x) and (g, y). Since the statement α_{1}^{∗} (C_{2} ≀ ^{2}) = 1 does not necessarily imply that C_{2} ≀ ^{2} admits a bi-Lipschitz embedding into L_{1}, our result falls short of obtaining a constant-factor approximation of the length of this tour, which, if possible, would be an interesting equivariant version of the Jones Traveling Salesman Theorem (note that if one wishes to estimate the length of the shortest Lipschitz curve covering the symmetric difference A△B for some A, B ⊆ ^{2} one cannot “read” this just from the Jones β numbers of A and B without recomputing the Jones β numbers of A△B). In view of such a potential strengthening of the Jones Traveling Salesman Theorem, the question whether C_{2} ≀ ^{2} admits a bi-Lipschitz embedding into L_{1} remains an interesting open problem that arises from our work (which currently only yields a “compression 1” version of this statement).

In Section 6 we compute the L_{p} compression of ≀ , answering a question posed in [47]:

Theorem 1.2. For every p ∈ [1, ∞) we have:

α_{p}^{∗}( ≀ ) = max\{ \frac{p}{2p − 1} , \frac{2}{3}\} .  (2)

The fact that α_{p}^{∗}( ≀ ) is at least the right-hand side of (2) was proved in [47], so the key issue in (2) is to show that no embedding of ≀ can have a compression exponent bigger than the right-hand side of (2). We do so via a non-trivial enhancement of the Markov type method for bounding compression exponents that was introduced in [7]. In order to explain the new idea used in proving (2) we first briefly recall the basic bound from [7].

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}].  (3)

The least such K is called the Markov type p constant of X, and is denoted M_{p}(X). This important concept was introduced by Ball in [9] and has since found a variety of applications in metric geometry, including applications to the theory of compression exponents [7, 47]. We refer to [48] for examples of spaces which have Markov type p. For our purposes it suffices to mention that Banach spaces whose modulus of uniform smoothness has power type p have Markov type p [48], and therefore the Markov type of L_{p}, p ∈ [1, ∞), is min{p, 2}.

In [47] a parameter β^{∗}(G) is defined 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^{β},  (4)

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 e_{G}. The proof in [7] shows that if (X, d_{X}) has Markov type p and G is amenable then:

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

In order to prove (2) we establish in Section 5 a crucial strengthening of (5). Given a symmetric probability measure μ on G let {g_{k}}_{k=1}^{∞} be i.i.d. elements of G which are distributed according to μ. The μ-random walk {W_{t}^{μ}}_{t=0}^{∞} is defined as W_{0}^{μ} = e_{G} and W_{t}^{μ} = g_{1}g_{2} ⋯ g_{t} for t ∈ . Let ρ be a left-invariant metric on G such that B_{ρ}(e_{G}, r) = {x ∈ G : ρ(x, e) ≤ r} is finite for all r ≥ 0. Define β_{p}^{∗}(G, ρ) to be the supremum over all β ≥ 0 such that there exists an increasing sequence of integers {t_{k}}_{k=1}^{∞} and a sequence of symmetric probability measures {μ_{k}}_{k=1}^{∞} on G satisfying:

∀k ∈ ∫_{G}ρ(x, e_{G})^{p}dμ_{k}(x) < ∞ and lim_{k→∞} (t_{k}μ_{k}(G \ {e_{G}})) = ∞,  (6)

such that for all k ∈ ,

μ_{k} [ρ (W_{t_{k}}^{μ_{k}}, e_{G})] ≥ t_{k}^{β} ( _{μ_{k}} [ρ (W_{1}^{μ_{k}}, e_{G})^{p}])^{β} .

In Section 5 we prove the following result:

Theorem 1.3. If G is amenable, ρ is a left-invariant metric on G with respect to which all balls are finite, and (X, d_{X}) has Markov type p, then:

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

In (7), α_{X}^{∗}(G, ρ) denotes the supremum of those α ≥ 0 for which there exists a ρ-Lipschitz map f : G → X which satisfies d_{X}(f (x), f (y)) ≥ cρ(x, y)^{α} (we previously defined this parameter only when ρ = d_{G}). We refer to the discussion in Section 5 for more information on the parameter β_{p}^{∗}(G, ρ). At this point it suffices to note that β_{p}^{∗}(G, d_{G}) ≥ β^{∗}(G), and therefore (7) is stronger than (5), since we now consider a variant of (4) where the walk can be induced by an arbitrary symmetric probability measure, and the measure itself is allowed to depend on the time t. It turns out that (7) is a crucial strict improvement over (5), and we require the full force of this strengthening: we shall use non-standard random walks (i.e., not only the canonical walk on the Cayley graph of G), as well as an adaptation of the walk to the time t in (4), in addition to invariant metrics ρ other than the word metric d_{G}.

We establish (2) by showing that for every p ∈ [1, 2) we have β_{p}^{∗}( ≀ , d_{≀} ) = \frac{2p−1}{p^{2}} > \frac{3}{4} = β^{∗}( ≀ ) (it follows in particular that (7)is indeed strictly stronger than (5). Note that ≀ is amenable and L_{p} has Markov type p, so we are allowed to use (7)). This is achieved by considering a random walk induced on ≀ from a random walk on whose increments are discrete versions of q-stable random variables for every q > p. We refer to Section 6 for the details. We believe that there is a key novel feature of our proof which highlights the power of random walk techniques in embedding problems: we adapt the random walk on G to the target space L_{p}. Previously [44, 10, 48, 7, 47] Markov type was used in embedding problems by considering a Markov chain on the space we wish to embed which arises intrinsically, and “ignored” the intended target space: such chains are typically taken to be the canonical random walk on some graph, but a different example appears in [10], where embeddings of arbitrary subsets A of the Hamming cube ({0, 1}^{n}, ∥ · ∥_{1}) are investigated via a construction of a special random walk on A which captures the “largeness” of A. Nevertheless, in all known cases the geometric object which was being embedded dictated the study of some natural random walk, while in our computation of α_{p}^{∗}( ≀ ) the target space L_{p} influences the choice of the random walk.

Recall that we mentioned above that prior to [7] the best known upper bound [4] on α^{∗}( ≀ ) was \frac{3}{4}. An inspection of the proof of this bound in [4] reveals that it considered only points in the normal subgroup of ≀ consisting of all configurations where the lamplighter is at 0, i.e., the zero section of ≀ :

( ≀ )_{0} {(f, x) ∈ ≀ : x = 0} ≀ .

Thus [4] actually establishes the bound α^{∗}(( ≀ )_{0}, d_{≀} ) ≤ \frac{3}{4}. More generally, an obvious variant of the proof of this fact in [4] (see Lemma 7.8 in [47]) shows that for p ∈ [1, 2] we have α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) ≤ \frac{p+1}{2p}. Here we obtain the following result:

Theorem 1.4. For every p ∈ [1, ∞) we have:

α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) = max\{ \frac{p + 1}{2p} , \frac{3}{4}\} .  (8)

An alternative proof of the fact that the right-hand side of (8) is greater than α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) , which belongs to the framework of (7), is given in Section 7, where we show that for every p ∈ [1, 2] we have β_{p}^{∗} (( ≀ )_{0}, d_{≀} ) = \frac{2}{p+1} . The heart of (8) is the construction of an embedding into L_{p} of the zero section ( ≀ )_{0} which achieves the claimed compression exponent. This turns out to be quite delicate: a Fourier analytic argument establishing this fact is presented in Section 4.

It is worthwhile to note at this point that in all of our new compression computations, namely (1), (2) and (8), we claim that for some group G equipped with an invariant metric ρ and for every p ∈ [2, ∞) we have α_{p}^{∗}(G, ρ) = α_{2}^{∗}(G, ρ). This is true since because L_{2} is isometric to a subset of L_{p} we obviously have α_{p}^{∗}(G, ρ) ≥ α_{2}^{∗}(G, ρ). In the reverse direction, all of our upper bounds on L_{p} compression exponents are based on (7), and since both L_{2} and L_{p} have Markov type 2 [48] the resulting upper bound for L_{p} coincides with the upper bound for L_{2}. For this reason it will suffice to prove all of our results when p ∈ [1, 2].

In Section 8 we apply the fact that α^{∗}(( ≀ )_{0}, d_{≀} ) α^{∗}( ≀ ) to the Lipschitz extension problem. This classical problem asks for geometric conditions on a pair of metric spaces (X, d_{X}) and (Y, d_{Y}) which ensure that for any subset A ⊆ X, any Lipschitz mapping f : A → Y can be extended to all of X. Among the motivating themes for research on the Lipschitz extension problem is the belief that many classical extension theorems for linear operators between Banach spaces have Lipschitz analogs. Two examples of this phenomenon are the non-linear Hahn-Banach theorem (see for example [59, 11]), which corresponds to extension of real valued functions while preserving their Lipschitz constant, and the non-linear version of Maurey’s extension theorem [9, 48]. It turns out that our investigation of the Hilbert compression exponent of the zero section of ≀ implies the existence of a Lipschitz function f : ( ≀ )_{0} → L_{2} which cannot be extended to a Lipschitz function defined on all of ≀ :

Theorem 1.5. There exists a Lipschitz function F : ( ≀ )_{0} → L_{2} which cannot be extended to a Lipschitz function from ≀ to L_{2}.

For those who believe in the above analogy between the Lipschitz extension problem and the extension problem for linear operators, Theorem 1.5 might seem somewhat surprising: after all H = ( ≀ )_{0} is a normal subgroup of G = ≀ with G/H , so it resembles a non-commutative version of a subspace of co-dimension 1 in a Banach space, for which the Lipschitz extension problem is trivial (again by the Hahn-Banach theorem). Nevertheless, the analogy with Banach spaces stops here, as our result shows that the normal subgroup H sits in G in an “entangled” way which makes it impossible to extend certain Lipschitz functions while preserving the Lipschitz property.

To explain the connection with the Lipschitz extension problem take ψ : ( ≀ )_{0} → L_{2} which is 1-Lipschitz and ∥ψ(x) − ψ(y)∥_{2} ≥ cd_{≀} (x, y)^{3/4} for all x, y ∈ ( ≀ )_{0}, where c > 0 is a universal constant^{4}. We claim that ψ cannot be extended to a Lipschitz function Ψ defined on all of ≀ , so assume for the sake of contradiction that Ψ extends ψ and is Lipschitz. To arrive at a contradiction we need to contrast the \frac{3}{4} lower bound on the compression exponent of ψ with the Markov type 2 proof of the fact that Ψ cannot have compression larger than \frac{2}{3} from [7]. Let \{W_{t}\}_{t=0}^{∞} be the canonical random walk on ≀ starting at the identity element. Writing W_{t} = (f_{t}, x_{t}) ∈ ≀ one can see that with high probability |x_{t}| \sqrt{t}, while the distance between W_{t} and the identity element is t^{3/4}. The fact that L_{2} has Markov type 2 and Ψ is Lipschitz says that we expect ∥Ψ(W_{t}) − Ψ(W_{0})∥_{2} to be \sqrt{t}. But, if we move W_{t} to its closest point in the zero section ( ≀ )_{0} then the image under Ψ will (using the Lipschitz condition) move \sqrt{t}. Using the compression inequality for ψ we deduce that for large enough t we have \sqrt{t} ∥Ψ(W_{t}) − Ψ(W_{0})∥_{2} (t^{3/4})^{3/4} = t^{9/16}, which is a contradiction. This argument is, of course, flawed, since we are allowed to use the fact that L_{2} has Markov type 2 only for Markov chains which are stationary and reversible, and this is not the case for the canonical random walk starting at the identity element. Nevertheless, this proof can be salvaged using the same intuition: in Section 8 we consider a certain finite subset of ≀ which lies within a narrow tubular neighborhood of ( ≀ )_{0}. We then apply the same ideas to the random walk obtained by choosing a point in this subset uniformly at random and preforming a random walk on the subset with appropriate boundary conditions. We refer to Section 8 for the full details. It is perhaps somewhat amusing to note here that while the notion of Markov type was introduced by Ball [9] in order to prove an extension theorem (Ball’s extension theorem), here we use Markov type for the opposite purpose—to prove a non-extendability result.

Thus far we did not discuss the relation between the parameters α_{X}^{∗}(G) and α_{X}^{#}(G) for some Banach space X. This is, in fact, a subtle issue: it is unclear when α_{X}^{∗}(G) = α_{X}^{#}(G). Since for every p ∈ [1, ∞) the free group F_{n} on n ≥ 2 generators satisfies α_{p}^{∗}(F_{n}) = 1 yet α_{p}^{#}(F_{n}) = max\{\frac{1}{p}, \frac{1}{2}\}(see [33, 47]) it follows that the compression exponent and equivariant compression exponent can be different from each other, while in many cases we know that these two invariants coincide: for example α_{p}^{∗}(C_{2}≀F_{n}) = α_{p}^{#}(C_{2}≀F_{n}) = max\{\frac{1}{p}, \frac{1}{2}\} (see [22, 47]). A useful result of Aharoni, Maurey and Mityagin [1] for Abelian groups, and Gromov (see [24]) for general amenable groups, says that for any amenable group G we have α_{2}^{∗}(G) = α_{2}^{#}(G). This is an obviously useful fact (examples of applications can be found in [24, 8]): for example in [47] it was shown that if X is a Banach space whose modulus of uniform smoothness has power type p then for every finitely generated group G we have:

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

The bound (9) implies the bound (5) when G is amenable and X is Hilbert space due to the above reduction to equivariant mappings for amenable groups and Hilbertian targets. At the time of writing of [47] it was unclear whether (9) implies (5) in general, since an Aharoni-Maurey-Mityagin/Gromov type result was not known in non-Hilbertian settings. In Section 5 we further improve (9) by showing that if X is a Banach space whose modulus of uniform smoothness has power type p then:

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

In Section 9 we prove the following theorem:

4It isn’t quite accurate that the fact that α^{∗} (( ≀ )_{0}, d_{≀} ) = \frac{3}{4} implies the existence of such a function ψ, since all we are assured is a compression exponent lower bound of \frac{3}{4} − ε for all ε > 0. This is immaterial for the sake of the argument here in the introduction—a precise proof is given in Section 8

Theorem 1.6. For every p ∈ [1, ∞), if G is an amenable group and X is a Banach space, then there exists a Banach space Y which is finitely representable^{5} in ℓ_{p}(X) and:

α_{Y}^{#}(G) ≥ α_{X}^{∗}(G).  (11)

Moreover, if X = L_{p} then we can also take Y = L_{p} in (11), and thus α_{p}^{∗}(G) = α_{p}^{#}(G) when G is amenable.

Note also that if X has modulus of uniform smoothness of power type p then so does ℓ_{p}(X), and hence so does the space Y of Theorem 1.6. Therefore, by virtue of (11), the inequalities (9) and (10) are indeed stronger than the inequalities (5) and (7) in full generality.

We end this introduction by commenting on why so much of the literature (and also the present paper) focused on compression exponents of wreath products. The obvious answer is that groups such as ≀ are among the simplest examples of groups for which it was unknown for a long time how to compute their compression exponents. As it turns out, understanding such groups in this context required new ideas and new connections between geometric group theory and other mathematical disciplines. But, there is also a deeper reason for our interest in embeddings of wreath products. Každan’s example [40] (see also [25]) of 2 SL_{2}( ) shows that there can be two groups, each of which has positive equivariant compression exponent, yet their semidirect product fails to have a positive equivariant compression exponent, and even fails the Haagerup property. It seems challenging to characterize which semidirect products preserve the property of having positive compression exponents, and wreath products, as examples of semidirect products, are a good place to start trying to understand this fundamental question. The literature on compression exponents of wreath products shows that in many cases this operation preserves the property of having positive compression exponent, but we do not know if this is always true, even for amenable groups: the simplest such example is the groups C_{2}≀(C_{2}≀ ) for which we do not know if it has positive Hilbert compression exponent, even though both C_{2} and C_{2} ≀ have Hilbert compression exponent 1.

2 Preliminaries

In what follows we fix two groups G and H, which are generated by the symmetric finite sets S_{G} and S_{H}, respectively. The corresponding left invariant word metrics will be denoted d_{G} and d_{H}, respectively. The canonical generating set of the wreath product G ≀H is

{(e_{G}, x) : x ∈ S_{H}}∪ {(δ_{y}, e_{H}): y ∈ S_{G}},

where e_{G} : H → G denotes the constant e_{G} function and for y ∈ G the function δ_{y} : H → G takes the value y at e_{H} and the value e_{H} elsewhere.

Given a function f : H → G we denote its support by supp(f) {x ∈ H : f (x) e_{G}}. For a finite subset A ⊆ H and x, y ∈ H we let TSP(A; x, y) denote the length of the shortest path in H which starts at x, covers A, and terminates at y, i.e.,

TSP(A; x, y) inf {∑_{j=0}^{k−1} d_{H}(x_{j}, x_{j+1} ) : k ∈ , x = x_{0}, …, x_{k} = y ∈ H ∧ A ⊆ {x_{0}, …, x_{k}}}.

5A Banach space U is said to be finitely representable in a Banach space V if for every ε > 0 and every finite dimensional subspace F ⊆ U there is a linear operator T : F → V such that for every x ∈ F we have ∥x∥_{U} ≤ ∥Tx∥_{V} ≤ (1 + ε)∥x∥_{U}.

Thus

|A| + TSP(A, x, y) = d_{C_{2}≀H} ((1_{y^{−1}A}, y^{−1}x), (0, 0)),

where 0 : H → C_{2} denotes the constant 0 function. Following [47] we let ℒ_{G}(H) denote the wreath product of G with H where the set of generators of G is taken to be G \ {e_{G}} (i.e. any two distinct elements of G are at distance 1 from each other). In other words, the difference between ℒ_{G}(H) and the classical lamplighter group C_{2} ≀H is that we allow the “lamps” to have G types of different “lights”, where the cost of switching from one type of light to another is 1. Thus, with this definition it is immediate that for every (f, x), (g, y) ∈ ℒ_{G}( ) we have

d_{ℒ_{G}( )} ((f, x), (g, y)) = d_{C_{2}≀H} ((1_{y^{−1}supp(f g^{−1})}, y^{−1}x), (0, 0))= |supp (f g^{−1})|+ TSP(supp (f g^{−1}) ; x, y). (12)

Moreover, distances in the wreath product G≀H, equipped with the canonical generating set, can be computed as follows:

d_{G≀H}((f, x), (g, y)) = TSP(supp (f g^{−1}) ; x, y)+ ∑_{x∈H}d_{G}(f (x), g(x)).  (13)

The following lemma generalizes Lemma 3.1 in [47], which deals with the special case H = (in which case the proof is easier).

Lemma 2.1. Assume that G contains at least two elements. Then for any p ≥ 1 we have

α_{p}^{∗}(ℒ_{G}(H)) = α_{p}^{∗} (C_{2} ≀H).

Proof. Obviously α_{p}^{∗} (ℒ_{G}(H)) ≤ α_{p}^{∗} (C_{2} ≀H), since ℒ_{G}(H) contains an isometric copy of C_{2} ≀H. To prove the reverse direction we may assume that α_{p}^{∗} (C_{2} ≀H) > 0. Fix 0 < α < α_{p}^{∗} (C_{2} ≀H) and a mapping θ : C_{2} ≀ → L_{p} satisfying

(f, x), (g, y) ∈ C_{2} ≀H ⟹ d_{C_{2}≀H}((f, x), (g, y))^{α} ∥θ(f, x) − θ(g, y)∥_{p} d_{C_{2}≀H}((f, x), (g, y)).  (14)

Let {ε_{z}}_{z∈G\{e_{G}}}be i.i.d. {0, 1}-valued Bernoulli random variables, defined on some probability space (Ω, ). For every f : H → G define a random mapping ε_{f} : H → C_{2} by

ε_{f} (z) \{ \begin{matrix}ε_{f (z)} & if f (z) e_{G}, \\ 0 & if f (z) = e_{G}. \end{matrix}

We now define an embedding F : ℒ_{G}(H) → L_{p}(Ω, L_{p}) by

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

Given (f, x), (g, y) ∈ G ≀H denote A supp (f g^{−1}) = {z ∈ H : f (z) g(z)}. We also denote by A_{ε} ⊆ H the random subset supp(ε_{f} − ε_{g}). By definition A_{ε} ⊆ A, so that TSP(A_{ε}; x, y) ≤ TSP(A; x, y). Hence:

∥F(f, x) − F(g, y)∥_{L_{p}(Ω,L_{p})}^{p} = [∥θ(ε_{f} , x) − θ(ε_{g}, y)∥_{p}^{p}] ^{(14)} [d_{C_{2}≀H}((ε_{f} , x), (ε_{g}, y))^{p}]

= [TSP(A_{ε}; x, y)^{p}]≤ [TSP(A; x, y)^{p}] =^{(12)} d_{ℒ_{G}( )} ((f, x), (g, y))^{p}.

In the reverse direction, observe that

TSP(A; x, y) ≤ 2TSP(A_{ε}; x, y) + TSP(A \ A_{ε}; x, y),  (15)

since given a path γ that starts at x, ends at y, and covers A_{ε}, and a path δ that starts at x, ends at y, and covers A \ A_{ε}, we can consider the path that starts as γ, retraces γ’s steps from y back to x, and then continues as δ from x to y. Hence,

d_{ℒ_{G}( )} ((f, x), (g, y))^{pα} =^{(12)} TSP(A; x, y)^{pα} ^{(15)} TSP(A_{ε}; x, y)^{pα} + TSP(A \ A_{ε}; x, y)^{pα}.  (16)

But by the symmetry of our construction the random subsets A_{ε} and A \ A_{ε} are identically distributed. So, taking expectation in (16) we see that

d_{ℒ_{G}( )} ((f, x), (g, y))^{pα} [TSP(A_{ε}; x, y)^{pα}]= [d_{C_{2}≀H}((ε_{f} , x), (ε_{g}, y))^{pα}]

^{(14)} [∥θ(ε_{f} , x) − θ(ε_{g}, y)∥_{p}^{p}]= ∥F(f, x) − F(g, y)∥_{L_{p}(Ω,L_{p})}^{p}.

Thus G ≀H embeds into L_{p}(Ω, L_{p}) with compression α, as required.

A combination of Lemma 2.1 and Theorem 3.3 in [47] yields the following corollary:

Corollary 2.2. Let G, H be nontrivial groups and p ≥ 1. Then

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

and

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

We end this section with a simple multi-scale estimate for the length of traveling salesmen tours (see for example [55] for a similar estimate). For r ≥ 0 and x ∈ H we let B_{H}(x, r) {y ∈ H : d_{H}(x, y) ≤ r}be the closed ball centered at x with radius r. For a bounded set A ⊆ H and r > 0 we let N(A, r) be the smallest integer n ∈ such that there exists x_{1}, …, x_{n} ∈ H for which A ⊆ ⋃ _{m=1}^{n} B_{H}(x_{m}, r). Finally, for ℓ ≥ 0 let TSP_{ℓ}(A) denote the length of the shortest path starting from e_{H}, coming within a distance of at most 2^{ℓ−1} from every point in A, and returning to e_{H}, i.e.

TSP_{ℓ}(A) inf {∑_{j=0}^{k−1} d_{H}(x_{j}, x_{j+1} ) : k ∈ , e_{H} = x_{0}, …, x_{k} = e_{H} ∈ H, A ⊆ ⋃_{j=0}^{k} B_{H} (x_{j}, 2^{ℓ−1})} .

Thus TSP(A) TSP(A; e_{H}, e_{H}) = TSP_{0}(A) = d_{C_{2}≀H}((1_{A}, e_{H}), (0, e_{H})) is the length of the shortest path starting from e_{H}, covering A, and returning to e_{H}. We shall use the following easy bound, which holds for every k, ℓ ∈ ∪ {0}:

A ⊆ B_{H} (e_{H}, 2^{k}) ⟹ TSP_{ℓ}(A) ≤ 3 ∑_{j=ℓ}^{k} 2^{j}N (A, 2^{j−1} ).  (17)

The inequality (17) is valid when ℓ ≥ k + 1 since in that case TSP_{ℓ}(A) = 0. Now (17) follows by induction from the inequality TSP_{ℓ−1}(A) ≤ TSP_{ℓ}(A)+3·2^{ℓ−1}N (A, 2^{ℓ−2}). This inequality holds true since we can take a set C ⊆ H of size N (A, 2^{ℓ−2})such that ⋃ _{x∈C}B_{H} (x, 2^{ℓ−2})⊇ A, and also take a path Γ ⊆ H of length TSP_{ℓ}(A) which starts from e_{H}, comes within a distance of at most 2^{ℓ−1} from every point in A, and returns to e_{H}. If we append to Γ a shortest path from each x ∈ C to its closest neighbor in Γ (and back) we obtain a new path of length at most TSP_{ℓ}(A) + 2 (2^{ℓ−1} + 2^{ℓ−2}) |C| ≤ TSP_{ℓ}(A) + 3 · 2^{ℓ−1}|C| which starts from e_{H}, comes within a distance of at most 2^{ℓ−2} from every point in A, and returns to e_{H}, as required.

3 Wreath products of groups with polynomial growth

The goal of this section is to prove the following theorem:

Theorem 3.1. Let G, H be nontrivial finitely generated groups, and assume that H has polynomial growth. Then for every p ∈ [1, 2] we have:

α_{p}^{∗}(G ≀H) ≥ min\{ \frac{1}{p}, α_{p}^{∗}(G)\} .  (18)

In particular, if the growth rate of H is at least quadratic then for every p ∈ [1, 2] we have

α_{p}^{∗}( ≀H) = α_{p}^{∗}(C_{2} ≀H) = \frac{1}{p}.  (19)

Proof. We shall first explain how to deduce the identity (19). The lower bound α_{p}^{∗}( ≀H) = α_{p}^{∗}(C_{2} ≀H) ≥ \frac{1}{p} is a consequence of (18). Since for p ∈ [1, 2] the Banach space L_{p} has Markov type p (see [9]), the result of Austin, Naor and Peres [7] implies that α_{p}^{∗}(G ≀H) ≤ \frac{1}{pβ^{∗}(G≀H)}. But, as we proved in [47], since the growth of H is at least quadratic we have β^{∗}(G ≀H) = 1.

To prove (18) note that by Corollary 2.2 it is enough to show that

α_{p}^{∗}(C_{2} ≀H) ≥ \frac{1}{p}.  (20)

Recall that for r ≥ 0 and x ∈ H we let B_{H}(x, r) {y ∈ H : d_{H}(x, y) ≤ r}be the closed ball centered at x with radius r. Assume that H has polynomial growth d, i.e., that for every r ≥ 1 we have

ar^{d} ≤ |B_{H}(e, r)|≤ br^{d}  (21)

for some a, b > 0 which do not depend on r. We shall show that for every 1 < p ≤ 2 and ε ∈ (0, 1/p) there is a function F : C_{2} ≀H → L_{p} such that for all (f, x), (g, y) ∈ C_{2} ≀H we have

d_{C_{2}≀H}((f, x), (g, y))^{\frac{1}{p}−ε} ∥F(f, x) − F(g, y)∥_{p} d_{C_{2}≀H}((f, x), (g, y)),  (22)

where here, and in the remainder of the proof of Theorem 3.1, the implied constants depend only on a, b, p, d, ε. Moreover, we will show that we can take ε = 0 in (22) if (H, d_{H}) admits a bi-Lipschitz embedding into L_{p}. Note that (22) implies also the case p = 1 of Theorem 3.1 since L_{p} is isometric to a subspace of L_{1} for all p ∈ (1, 2] (see e.g. [59]).

Let Ω be the disjoint union of the sets of functions f : A → C_{2} where A ranges over all finite subsets of H, i.e.,

Ω ⋃_{\begin{matrix}A⊆H \\ |A|<∞ \end{matrix}} C_{2}^{A}.

We will work with the Banach space ℓ_{∞} (Ω), and denote its standard coordinate basis by

{v_{f} : f : A → C_{2}, A ⊆ H, |A| < ∞}.

Fix a 1-Lipschitz function φ : [0, ∞) → [0, 1] which equals 0 on [0, 1] and equals 1 on [2, ∞). For every (f, x) ∈ C_{2} ≀H define a function Ψ_{0}(f, x) ∈ ℓ_{∞} (Ω) by

Ψ_{0}(f, x) ∑_{k=0}^{∞} 2^{−(d−1)k/p} ∑_{y∈H}φ (\frac{d_{H}(x, y)}{2^{k}})v_{f _{B_{H}(y,2^{k})}}.  (23)

We shall first check that Ψ_{0} − Ψ_{0}(0, e_{H}) ∈ Z^{1}(H, π) for an appropriately chosen action π of C_{2} ≀H on ℓ_{p}(Ω). Recall that the product on C_{2} ≀H is given by (f, x)(g, y) = (f + T_{x}(g), xy), where T_{x}(g)(z) g (x^{−1}z). Given (f, x) ∈ C_{2} ≀H and a finite subset A ⊆ H define a bijection τ_{(f,x)}^{A} : C_{2}^{A} → C_{2}^{xA}by τ_{(f,x)}^{A}(h) f + T_{x}(h). Note that for all (f, x), (g, y) ∈ C_{2} ≀H and every finite A ⊆ H we have

τ_{(f,x)(g,y)}^{A} = τ_{(f,x)}^{yA} ∘ τ_{(g,y)}^{A}.  (24)

Hence if we define

π(f, x) ( ∑_{\begin{matrix}A⊆H \\ |A|<∞ \end{matrix}} ∑_{h∈C_{2}^{A}}α_{h}v_{h}) ∑_{\begin{matrix}A⊆H \\ |A|<∞ \end{matrix}} ∑_{h∈C_{2}^{A}}α_{h}v_{τ_{(f,x)}^{A}(h)},

then π is a linear isometric action of C_{2} ≀H on ℓ_{p}(Ω) for all p ∈ [1, ∞] (π(f, x) corresponds to a permutation of the coordinates and hence is an isometry. The fact that π((f, x)(g, y)) = π(f, x)π(f, y) is an immediate consequence of (24)). The definition (23) ensures that for every (f, x), (g, y) ∈ C_{2} ≀H we have Ψ_{0}((f, x)(g, y)) = π(f, x)Ψ_{0}(g, y). Hence, if we define Ψ(f, x) Ψ_{0}(f, x) − Ψ_{0}(0, e_{H}) then Ψ ∈ Z^{1}(H, π).

Note that Ψ(0, e_{H}) = 0 and

Ψ(1_{\{e_{H}\}}, e_{H}) = ∑_{k=0}^{∞} 2^{−(d−1)k/p} ∑_{y∈B_{H}(e_{H},2^{k})}φ (\frac{d_{H}(e_{H}, y)}{2^{k}})(v_{δ_{e_{H}} _{B_{H}(y,2^{k})}} − v_{0 _{B_{H}(y,2^{k})}}) = 0,

where we used the fact that φ(t) = 0 for t ∈ [0, 1]. Moreover, for every s ∈ S_{H} we have:

∥Ψ(0, s)∥ _{p}^{p} = ∑_{k=0}^{∞} 2^{−(d−1)k} ∑_{y∈H} |φ (\frac{d_{H}(s, y)}{2^{k}}) − φ (\frac{d_{H}(e_{H}, y)}{2^{k}})|^{p}

= ∑_{k=0}^{∞} 2^{−(d−1)k} ∑_{\begin{matrix}y∈H \\ 2^{k}−1≤d_{H}(e_{H},y)≤2^{k+1}+1 \end{matrix}} |φ (\frac{d_{H}(s, y)}{2^{k}}) − φ (\frac{d_{H}(e_{H}, y)}{2^{k}})|^{p}

≤ ∑_{k=0}^{∞} 2^{−(d−1)k} · 2^{−kp} |{y ∈ H : 2^{k} − 1 ≤ d_{H}(e_{H}, y) ≤ 2^{k+1} + 1} |

≤ ∑_{k=0}^{∞} 2^{−(d−1)k} · 2^{−kp} · b (2^{k+1} + 1)^{d} ≤ 4^{d}b ∑_{k=0}^{∞} 2^{−k(p−1)} 1,

Where we used the fact that p > 1. Since Ψ is equivariant and the set {(1_{{e_{H}}}, e_{H})} ∪ {(0, s) : s ∈ S_{H}} generates C_{2} ≀H, we deduce that

∥Ψ∥_{Lip} 1.  (25)

Suppose now that f : H → C_{2} and let m ∈ be the minimum integer such that supp(f) ⊆ B_{H}(e_{H}, 2^{m}). Then

∥Ψ(f, e_{H})∥_{p}^{p} ≥ ∑_{k=0}^{∞} 2^{−(d−1)k} ∑_{\begin{matrix}y∈H \\ f _{B_{H}(y,2^{k})} 0 _{B_{H}(y,2^{k})} \end{matrix}} φ (\frac{d_{H}(e_{H}, y)}{2^{k}})^{p}

≥ ∑_{k=0}^{∞} 2^{−(d−1)k} |{y ∈ H : d_{H}(e_{H}, y) ≥ 2^{k+1} ∧ supp(f) ∩ B_{H}(y, 2^{k}) ∅} |. (26)

Fix k ≤ m − 3 and denote n = N (supp(f), 2^{k−1}). Let x_{1}, …, x_{n} ∈ H satisfy

supp(f) ⊆ ⋃_{i=1}^{n} B_{H} (x_{i}, 2^{k−1}).  (27)

By the minimality of n we are ensured that the balls {B_{H} (x_{i}, 2^{k−2})}_{i=1}^{n} are disjoint and that there exists y_{i} ∈ B_{H} (x_{i}, 2^{k−1})∩ supp(f). Write

I {i ∈ {1, …, n} : d_{H}(y, e_{H}) ≥ 2^{k+1} ∀y ∈ B_{H} (x_{i}, 2^{k−2})}.

Note that if i ∈ I and y ∈ B_{H} (x_{i}, 2^{k−2})then d_{H}(y_{i}, y) ≤ d_{H}(y_{i}, x_{i}) + d_{H}(y, x_{i}) ≤ 2^{k−1} + 2^{k−2} < 2^{k}. Thus in this case supp(f) ∩ B_{H}(y, 2^{k}) ∅, and therefore

|{y ∈ H : d_{H}(e_{H}, y) ≥ 2^{k+1} ∧ supp(f) ∩ B_{H}(y, 2^{k}) ∅} | ≥ |I| |B_{H} (e_{H}, 2^{k−2})| 2^{kd}|I|.  (28)

We shall now bound |I| from below. By the minimality of m there exists z ∈ supp(f) such that d_{H}(e_{H}, z) > 2^{m−1}. By (27) there is some i ∈ {1, …n} for which d_{H}(z, x_{i}) ≤ 2^{k−1}. If y ∈ B_{H} (x_{i}, 2^{k−2})then

d_{H}(y, e_{H}) ≥ d_{H}(e_{H}, z) − d_{H}(z, x_{i}) − d_{H}(x_{i}, y) > 2^{m−1} − 2^{k−1} − 2^{k−2} ≥ 2^{k+1},

since by assumption k ≤ m − 3. This shows that |I| ≥ 1. Write J {1, …, n} \ I. For each i ∈ J there is some y ∈ B_{H} (x_{i}, 2^{k−2})for which d_{H}(e_{H}, y) < 2^{k+1}. Hence B_{H} (x_{i}, 2^{k−2}) ⊆ B_{H} (e_{H}, 2^{k+2}). Since the balls {B_{H} (x_{i}, 2^{k−2})}_{i=1}^{n} are disjoint it follows that

|J|a2^{(k−2)d} ≤^{(21)} |J| |B_{H} (e_{H}, 2^{k−2})|≤ |B_{H} (e_{H}, 2^{k+2})| ≤^{(21)} b2^{(k+2)d}.

Thus n − |I| = |J| 1, which implies that |I| n. Plugging this bound into (28) we see that for every k ≤ m − 3 we have

|{y ∈ H : d_{H}(e_{H}, y) ≥ 2^{k+1} ∧ supp(f) ∩ B_{H}(y, 2^{k}) ∅} | 2^{kd}N (supp(f), 2^{k−1}) .

In combination with (26) we see that

∥Ψ(f, e_{H})∥_{p}^{p} ∑_{k=0}^{m−3}2^{−(d−1)k} · 2^{kd}N (supp(f), 2^{k−1}) = ∑_{k=0}^{m−3}2^{k}N (supp(f), 2^{k−1}) .  (29)

We claim that

|supp(f)| + ∑_{k=0}^{m−3}2^{k}N (supp(f), 2^{k−1}) d_{C_{2}≀H}((f, e_{H}), (0, e_{H})).  (30)

Indeed, by combining (17) (with ℓ = 0) and (13) we see that

|supp(f)| + ∑_{k=0}^{m} 2^{k}N (supp(f), 2^{k−1}) d_{C_{2}≀H}((f, e_{H}), (0, e_{H})).  (31)

To check that (31) implies (30) note that is is enough to deal with the case supp(f) ∅, and that the fact that supp(f) ⊆ B_{H} (e_{H}, 2^{m}), combined with the doubling condition for (H, d_{H}), implies that for k ∈ {m − 2, m − 1, m} we have N (supp(f), 2^{k−1}) 1. Thus (31) implies (30) by inspecting the cases m < 3 and m ≥ 3 separately.

Fix ε ∈ (0, 1). By Assouad’s theorem [5] (see also the exposition of this theorem in [35]), since H has polynomial growth, and hence is a doubling metric space, there is a function θ : H → L_{p} such that for all x, y ∈ H we have

d_{H}(x, y)^{1−ε} ≤ ∥θ(x) − θ(y)∥_{p} d_{H}(x, y)^{1−ε} ≤ d_{H}(x, y).  (32)

By translation we may assume that θ(e_{H}) = 0. We can now define our embedding

F : C_{2} ≀H → ℓ_{p}(Ω) ⊕ ℓ_{p}(H) ⊕ L_{p}

by F = Ψ ⊕ f ⊕ θ (here we identify a finitely supported function f : H → C_{2} as a member of ^{H}, and hence a member of ℓ_{p}(H)). Then ∥F∥_{Lip} L 1. Thus in order to prove (22), and hence to complete the proof of Theorem 3.1, it remains to show that for all (f, x) ∈ C_{2} ≀H we have

d_{C_{2}≀H}((f, x), (0, e_{H}))^{(1−ε)/p} ∥F(f, x) − F(0, e_{H})∥_{p} = (∥Ψ(f, x)∥_{p}^{p} + |supp(f)| + ∥θ(x)∥_{p}^{p})^{1/p}.  (33)

A combination of (29) and (30) implies that there exists η > 0 which depends only on a, b, d, p, ε such that

ηd_{C_{2}≀H}((f, e_{H}), (0, e_{H}))^{1/p} ≤ (∥Ψ(f, e_{H})∥_{p}^{p} + |supp(f)|)^{1/p} = ∥F(f, e_{H}) − F(0, e_{H})∥_{p}.

Hence

∥F(f, x) − F(0, e_{H})∥_{p} ≥ ∥F(f, e_{H}) − F(0, e_{H})∥_{p} − ∥F(f, x) − F(f, e_{H})∥_{p}
≥ ηd_{C_{2}≀H}((f, e_{H}), (0, e_{H}))^{1/p} − Ld_{H}(x, e_{H})
≥ η [max{0, d_{C_{2}≀H}((f, x), (0, e_{H}))− d_{C_{2}≀H}((f, x), (f, e_{H}))}]^{1/p} − Ld_{H}(x, e_{H})
= η [max{0, d_{C_{2}≀H}((f, x), (0, e_{H}))− d_{H}(x, e_{H})}]^{1/p} − Ld_{H}(x, e_{H})
≥ \frac{η}{4}d_{C_{2}≀H}((f, x), (0, e_{H}))^{1/p}
≥ \frac{η}{4}d_{C_{2}≀H}((f, x), (0, e_{H}))^{(1−ε)/p},

provided that

d_{H}(x, e_{H}) ≤ min\{ \frac{η}{4L}d_{C_{2}≀H}((f, x), (0, e_{H}))^{1/p}, \frac{1}{2}d_{C_{2}≀H}((f, x), (0, e_{H}))\}.  (34)

But if (34) fails then d_{H}(x, e_{H}) d_{C_{2}≀H}((f, x), (0, e_{H}))^{1/p}, in which case we can use (32) to deduce that

∥θ(x)∥_{p} ≥ d_{H}(e_{H}, x)^{1−ε} d_{C_{2}≀H}((f, x), (0, e_{H}))^{(1−ε)/p},

which implies (33) and concludes the proof of (22).

Remark 3.2. Since the only reason for the loss of ε in (22) is the use of Assouad’s embedding in (32) we see that if p > 1 and (H, d_{H}) admits a bi-Lipschitz embedding into L_{p} and has at least quadratic growth then α_{p}^{∗}(C_{2} ≀H) = \frac{1}{p} is attained.

Remark 3.3. In [47] it was shown that α_{2}^{∗}(C_{2} ≀ ^{2}) ≥ \frac{1}{2} via an embedding which we now describe. We are doing so for several reasons. First of all there are some typos in the formulae given for the embedding in [47] and we wish to take this opportunity to publish a correct version. Secondly, the embedding was given in [47] without a detailed proof of its compression bounds, and since it is based on a different and simpler approach than our proof of Theorem 3.1 it is worthwhile to explain it here. Most importantly, there are several “coincidences” which allow this approach to yield sharp bounds on α_{p}^{∗}(C_{2}≀ ^{d}) only when p = 2 and d = 2, and we wish to explain these subtleties here. We will therefore first describe the embedding scheme in [47] for general p ∈ [1, 2] and d ≥ 2 and then specialize to the case p = d = 2.

Let {v_{y,r,g}: y ∈ ^{d}, r ∈ ∪ {0}, g : y + [−r, r]^{d} → {0, 1}} be a system of disjoint unit vectors in L_{p}. Fix a parameter γ > 0 which will be determined later and define for every (f, x) ∈ C_{2} ≀ ^{d} a vector F(f, x) = F_{0}(f, x) − F_{0}(0, 0) ∈ L_{p}, where

F_{0}(f, x) ∑_{y∈ ^{d}} ∑_{r=0}^{∞} \frac{max\{1 − \frac{2r}{1+∥x−y∥_{∞}} , 0\}}{1 + ∥x − y∥_{∞}^{γ}}v_{y,r,f _{y+[−r,r]^{d}}}

One checks as in the proof of Theorem 3.1 that F is equivariant with respect to an appropriate action of C_{2} ≀ ^{d} on L_{p}. Moreover, one checks that ∥F(1_{0}, 0)∥_{p} 1 and that for x ∈ {(±1, 0), (0, ±1)} we have

∥F(0, x)∥_{p}^{p} ∑_{y∈ ^{d}} ∑_{r∈[0,1+∥y∥_{∞} /2]}(\frac{1 + r}{(1 + ∥y∥_{∞} )^{2+γ}})^{p} ∑_{r=0}^{∞} ∑_{\begin{matrix}k≥0 \\ k≥2(r−1) \end{matrix}} ∑_{∥y∥_{∞} =k} \frac{(1 + r)^{p}}{(1 + k)^{(3+γ)p}}

∑_{r=1}^{∞} r^{p} ∑_{k≥r} \frac{k^{d−1}}{(1 + k)^{(2+γ)p}} ∑_{r=0}^{∞} \frac{1}{r^{p+γp−d}} < ∞, (35)

where in (35) we need to assume that

γ > \frac{d + 1 − p}{p} .  (36)

It follows that as long as (36) holds true F is Lipschitz.

For the lower bound fix (f, x) ∈ C_{2} ≀ ^{d} such that f 0 and let R ≥ 0 be the smallest integer for which there exists z ∈ supp(f) such that ∥z − x∥_{∞} = R, i.e., R is the smallest integer such that supp(f) ⊆ x + [−R, R]^{d}. Note that for every y ∈ ^{d} such that ∥y − z∥_{∞} ∈ [0, R] and every r ∈ [∥y − z∥_{∞} , (1 + R − ∥y − z∥_{∞} )/4] we have z ∈ y + [−r, r]^{d}, and hence supp(f) ∩ (y + [−r, r]^{d}) ∅, and ∥y − x∥_{∞} ≥ R − ∥y − z∥_{∞} , which implies that \frac{2r}{1+∥y−x∥_{∞}} ≤ \frac{1}{2}. Thus:

∥F(f, x)∥_{p}^{p} ∑_{k=0}^{R} ∑_{\begin{matrix}y∈ ^{d} \\ ∥y−z∥_{∞} =k \end{matrix}} ∑_{r∈[k,(1+R−k)/4]} \frac{1}{(1 + (k + R)^{γ})^{p}}

∑_{k∈[0,(1+R)/5]}(1 + k^{d−1}) · \frac{1 + R − 5k}{4} · \frac{1}{(1 + (k + R)^{γ})^{p}} R^{d+1−γp} . (37)

Note the trivial bound:

TSP(supp(f); x, x) ≤ TSP(x + [−R, R]^{d}; x, x) R^{d}.  (38)

Assuming also that γ < \frac{d+1}{p} we see that a combination of (37) and (38) implies that:

∥F(f, x)∥_{p} TSP(supp(f); x, x)^{\frac{d+1−γp}{dp}} .  (39)

Hence if we define Ψ(x) = x ⊕ F(x) ∈ ℓ_{p}^{d} ⊕ L_{p} we get the lower bound

∥Ψ(f, x)∥_{p} ∥x∥_{1} + TSP(supp(f); x, x)^{\frac{d+1−γp}{dp}} (d_{^{d}}(x, 0) + TSP(supp(f); x, x))^{\frac{d+1−γp}{dp}}

(d_{C_{2}≀^{d}} ((f, x), (0, 0)))^{\frac{d+1−γp}{dp}} . (40)

Letting γ tend from above to \frac{d+1−p}{p} in (40) we get the lower bound

α_{p}^{∗} (C_{2} ≀ ^{d}) ≥ \frac{1}{d}.  (41)

While (41) reproduces the result of [57], it yields the sharp bound α_{p}^{∗} (C_{2} ≀ ^{d}) = \frac{1}{p} only when p = d = 2, in which case the above embedding coincides with the embedding used in [47]. This is why we needed to use a new argument in our proof of Theorem 3.1. Note that if one attempts to use the above reasoning while replacing the group ^{d} by a general group H of growth rate d one realizes that it used the bound

|B_{H}(e_{H}, r + 1)|− |B_{H}(e_{H}, r)|≍ r^{d−1}.  (42)

Unfortunately the validity of (42)is open for general groups H of growth rate d. To the best of our knowledge the best known general upper bound on the growth rate of spheres is the following fact: there exists β > 0 (depending on the group H and the choice of generators) such that for every r ∈ we have

|B_{H}(e_{H}, r + 1)|− |B_{H}(e_{H}, r)| r^{d−β}.  (43)

This is an immediate corollary of a well known (simple) result in metric geometry: since |B_{H}(e, r)|≍ r^{d} the metric space (H, d_{H}) is doubling (moreover, the counting measure on H is Ahlfors-David d-regular. See [35] for a discussion of these notions). By Lemma 3.3 in [19] (see also Proposition 6.12 in [16]) if (X, d, μ) is a geodesic doubling metric measure space then for all x ∈ X, r > 0 and δ ∈ (0, 1) we have

μ (B_{X}(x, r) \ B_{X}(x, (1 − δ)r))≤ (2δ)^{β}μ (B_{X}(x, r)),  (44)

where β > 0 depends only on the doubling constant of the measure μ (see [19, 16] for a bound on β. In [49] it is shown that the bound on β from [19, 16] is asymptotically sharp as the doubling constant tends to ∞). Clearly (44) implies (43) if we let μ be the counting measure on H and δ = \frac{1}{r}. While it is natural to conjecture that it is possible to take β = 1 in (43), this has been proved when H is a 2-step nilpotent group [56], but it is unknown in general.

4 The zero section of ≀

This section is devoted to the proof of the following theorem:

Theorem 4.1. Let ( ≀ )_{0} be the zero section of ≀ , i.e. the subset of ≀ consisting of all (f, x) ∈ ≀ with x = 0, with the metric inherited from ≀ . Then for all p ∈ [1, 2] we have:

α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) = \frac{p + 1}{2p} .

Proof. The fact that α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) ≤ \frac{p+1}{2p} follows from a variant of an argument from [4]—see Lemma 7.8 in [47]. We present an alternative proof of this fact in Section 7 below.

Fix ε ∈ (0, 1). In [47] we have shown that there exists a function F_{0} : ≀ → L_{p} such that the metric ∥F_{0}(f_{,}x_{1}) − (f_{2}, x_{2})∥_{p} is ≀ -invariant and for all (f, x) ∈ Z ≀Z we have

|x|^{(1−ε)p} + ∑_{j∈} |f (j)|^{p} + max{|j|^{(1−ε)p} : f (x + j) 0} ∥F_{0}(f, x) − F_{0}(0, 0)∥_{p}^{p} d_{Z≀Z}((f, x), (0, 0))^{p}, (45)

where here, and in what follows, the implied constants depend only on p and ε. We note that while (45) was not stated as a separate result in [47], it is contained in the proof of Theorem 3.3 there—see equation (28) in [47] with a = 1 and b = 1 − ε. Alternatively (45) is explained in detail for the case p = 2 in Remark 2.2 of [7]—the same argument works when we replace in that proof L_{2} by L_{p} and let α be arbitrarily close to (p − 1)/p (instead of arbitrarily close to 1/2).

Let {e_{j,k,ℓ} : j, k, ℓ ∈ } be the standard basis of ℓ_{p}( × × ). For every (f, 0) ∈ ( ≀ )_{0} define

Φ(f, 0) = ∑_{ℓ=1}^{∞} ∑_{k=0}^{∞} ∑_{\begin{matrix}j∈ \\ |j|∈[2^{ℓ−1}−1,2^{ℓ}−1) \end{matrix}} \frac{2^{(k+(p−1)ℓ)/p}}{k + 1} exp(\frac{2πif (j)}{2^{k}} )e_{j,k,ℓ}.

Our embedding of ( ≀ )_{0} will be

F F_{0} ⊕ Φ ∈ ℓ_{p}( × × ) ⊕ L_{p}.

Observe that for every (f, 0), (g, 0) ∈ ( ≀ )_{0} we have ∥Φ(f, 0) − Φ(g, 0)∥_{p} = ∥Φ(f − g, 0) − Φ(0, 0)∥_{p}, so it will suffice to prove the required compression bounds for ∥F(f, 0) − F(g, 0)∥_{p} when g = 0.

¿From now on we shall fix (f, 0) ∈ ( ≀ )_{0}. For every ℓ, m ∈ denote

E(ℓ, m) = {j :∈ : |j| ∈ [2^{ℓ−1} − 1, 2^{ℓ} − 1) ∧ |f (j)| ∈ [2^{m}, 2^{m+1})} .

We also write M max{|j| : f (j) 0}, so that

d_{≀} ((f, 0), (0, 0)) ≍ M + ∥f ∥_{1} = M + ∑_{j∈} |f (j)| ≍ M + ∑_{ℓ=1}^{∞} ∑_{m=0}^{∞}2^{m}|E(ℓ, m)|.  (46)

Now,

∥Φ(f, 0) − Φ(0, 0)∥ _{p}^{p} = ∑_{ℓ=1}^{∞} ∑_{k=0}^{∞} ∑_{\begin{matrix}j∈ \\ |j|∈[2^{ℓ−1}−1,2^{ℓ}−1) \end{matrix}} \frac{2^{k+(p−1)ℓ}}{(k + 1)^{p}} |1 − exp(\frac{2πif (j)}{2^{k}} )|^{p}

= ∑_{ℓ=1}^{∞} ∑_{k=0}^{∞} \frac{2^{k+(p−1)ℓ}}{(k + 1)^{p}} ∑_{m=0}^{∞} ∑_{j∈E(ℓ,m)} |1 − exp(\frac{2πif (j)}{2^{k}} )|^{p} . (47)

Note that

m ≤ k − 2 ⟹ ∑_{j∈E(ℓ,m)} |1 − exp(\frac{2πif (j)}{2^{k}} )|^{p} ≍ 2^{p(m−k)}|E(ℓ, m)|.  (48)

and for all m, k ∈ ,

∑_{j∈E(ℓ,m)} |1 − exp(\frac{2πif (j)}{2^{k}} )|^{p} |E(ℓ, m)|.  (49)

Plugging (48) and (49) into (47) we see that

∥Φ(f, 0) − Φ(0, 0)∥ _{p}^{p} ∑_{ℓ=1}^{∞} ∑_{m=0}^{∞} (∑_{k=0}^{m+1} \frac{2^{k+(p−1)ℓ}}{(k + 1)^{p}} |E(ℓ, m)| + ∑_{k=m+2}^{∞} \frac{2^{k+(p−1)ℓ}}{(k + 1)^{p}} 2^{p(m−k)}|E(ℓ, m)|)

∑_{ℓ=1}^{∞} ∑_{m=0}^{∞} \frac{2^{m+(p−1)ℓ}}{(m + 1)^{p}} |E(ℓ, m)| ≤ (∑_{ℓ=1}^{∞} ∑_{m=0}^{∞}(\frac{2^{m+(p−1)ℓ}}{(m + 1)^{p}} |E(ℓ, m)|)^{1/p})^{p} . (50)

Using the fact that for all a, b ≥ 0 we have ab^{p−1} ≤ (\frac{a+b}{2})^{p} we can bound the summands in (50) as follows:

(\frac{2^{m+(p−1)ℓ}}{(m + 1)^{p}} |E(ℓ, m)|)^{1/p} \{ \begin{matrix}2^{m}|E(ℓ, m)| + \frac{2^{ℓ}}{(m+1)^{p/(p−1)}} & if E(ℓ, m) ∅, \\ 2^{m}|E(ℓ, m)| & otherwise. \end{matrix}  (51)

Note that if E(ℓ, m) ∅ then there exists j ∈ with |j| ∈ [2^{ℓ−1} − 1, 2^{ℓ} − 1) such that f (j) 0. By the definition of M this implies that 2^{ℓ} < M. Using this observation while substituting the the estimates (51) in (50) we see that

∥Φ(f, 0) − Φ(0, 0)∥ _{p} ∑_{m=0}^{∞} ∑_{ℓ=1}^{∞} 2^{m}|E(ℓ, m)| + ∑_{ℓ=1}^{⌊log_{2} M⌋}2^{ℓ} ∑_{m=0}^{∞} \frac{1}{(m + 1)^{p/(p−1)}}

∑_{ℓ=1}^{∞} ∑_{m=0}^{∞}2^{m}|E(ℓ, m)| + M ≍^{(46)} d_{≀} ((f, 0), (0, 0)). (52)

This shows that ∥F∥_{Lip} 1.

In the reverse direction write

D d_{≀} ((f, 0), (0, 0)) ≍^{(46)} M + ∑_{2^{ℓ}<M} ∑_{|j|∈[2^{ℓ−1}−1,2^{ℓ}−1)} |f (j)| ≍ ∑_{2^{ℓ}<M} (2^{ℓ} + ∑_{|j|∈[2^{ℓ−1}−1,2^{ℓ}−1)} |f (j)|)

It follows that there exists an integer ℓ < log_{2} M such that

D log(M + 1) · (2^{ℓ} + ∑_{|j|∈[2^{ℓ−1}−1,2^{ℓ}−1)} |f (j)|) .  (53)

We shall fix this ℓ from now on. Observe that

∑_{|j|∈[2^{ℓ−1}−1,2^{ℓ}−1)} |f (j)| ≍ ∑_{2^{m+1}<∥f ∥_{1}} 2^{m}|E(ℓ, m)|.

Hence there exists an integer m log(1 + ∥f ∥_{1}) such that

∑_{|j|∈[2^{ℓ−1}−1,2^{ℓ}−1)} |f (j)| 2^{m}|E(ℓ, m)| · log(1 + ∥f ∥_{1}).  (54)

We shall fix this m form now on. Combining (53) with (54) yields the bound:

D log(M + 1) · (2^{ℓ} + 2^{m}|E(ℓ, m)| · log(1 + ∥f ∥_{1}))^{(46)} (log(D + 1))^{2} · (2^{ℓ} + 2^{m}|E(ℓ, m)|). (55)

Substitute (48) into (47) to get the lower bound

∥Φ(f, 0) − Φ(0, 0)∥ _{p}^{p} ∑_{k=m+2}^{∞} \frac{2^{k+(p−1)ℓ}}{(k + 1)^{p}} 2^{p(m−k)}|E(ℓ, m)| \frac{2^{m+(p−1)ℓ}}{(m + 1)^{p}} |E(ℓ, m)| \frac{2^{m+(p−1)ℓ}}{(log(D + 1))^{p}} |E(ℓ, m)|.

Also (45) implies that

∥F_{0}(f, 0) − F_{0}(0, 0)∥_{p}^{p} M^{(1−ε)p} + 2^{mp}|E(ℓ, m)| 2^{(1−ε)ℓp} + 2^{mp}|E(ℓ, m)|.

Thus

∥F(f, 0) − F(0, 0)∥_{p} 2^{(1−ε)ℓ} + 2^{m}|E(ℓ, m)|^{1/p} + \frac{1}{log(D + 1)} · 2^{m/p}|E(ℓ, m)|^{1/p}2^{ℓ(p−1)/p}

\frac{1}{log(D + 1)} · (2^{ℓ} + 2^{m}|E(ℓ, m)|^{1/p} + 2^{m/p}|E(ℓ, m)|^{1/p}2^{ℓ(p−1)/p})^{1−ε} . (56)

We claim that

2^{ℓ} + 2^{m}|E(ℓ, m)|^{1/p} + 2^{m/p}|E(ℓ, m)|^{1/p}2^{ℓ(p−1)/p} ≥ \frac{2^{ℓ} + (2^{m}|E(ℓ, m)|)^{\frac{p+1}{2p}}}{2} .  (57)

Indeed, if (2^{m}|E(ℓ, m)|)^{\frac{p+1}{2p}} ≤ 2^{ℓ} then (57) is trivial, so assume that a (2^{m}|E(ℓ, m)|)^{\frac{p+1}{2p}} ≥ 2^{ℓ}. Since |E(ℓ, m)| = 2^{−m} · a^{2p/(p+1)} we see that

2^{ℓ} + 2^{m}|E(ℓ, m)|^{1/p} + 2^{m/p}|E(ℓ, m)|^{1/p}2^{ℓ(p−1)/p} ≥ 2^{(p−1)m/p}a^{2/(p+1)} + a^{2/(p+1)}2^{ℓ(p−1)/p}.  (58)

Note that by definition 2^{−m} · a^{2p/(p+1)} = |E(ℓ, m)| ≤ 2^{ℓ}, so 2^{m} ≥ 2^{−ℓ} · a^{2p/(p+1)}. Substituting this bound into (58) we see that

2^{ℓ} + 2^{m}|E(ℓ, m)|^{1/p} + 2^{m/p}|E(ℓ, m)|^{1/p}2^{ℓ(p−1)/p} ≥ 2^{−ℓ(p−1)/p} · a^{2p/(p+1)} + a^{2/(p+1)}2^{ℓ(p−1)/p}

≥ 2a = 2 (2^{m}|E(ℓ, m)|)^{\frac{p+1}{2p}} ,

where we used the arithmetic mean/geometric mean inequality. This completes the proof of (57).

A combination of (55), (56) and (57) yields

∥F(f, 0) − F(0, 0)∥_{p} \frac{1}{log(D + 1)} · (2^{ℓ} + (2^{m}|E(ℓ, m)|)^{\frac{p+1}{2p}} )^{1−ε}

\frac{1}{log(D + 1)} · (2^{ℓ} + 2^{m}|E(ℓ, m)|)^{(1−ε) \frac{p+1}{2p}} \frac{D^{(1−ε) \frac{p+1}{2p}}}{(log(D + 1))^{1+2(1−ε) \frac{p+1}{2p}}} D^{(1−2ε) \frac{p+1}{2p}} .

This completes the proof of Theorem 4.1.

5 General compression upper bounds for amenable groups

Let Γ be a group which is generated by the finite symmetric set S ⊆ Γ. Let ρ be a left-invariant metric on Γ such that B_{ρ}(e_{Γ}, r) = {x ∈ Γ : ρ(x, e) ≤ r} is finite for all r ≥ 0. In most of our applications of the ensuing arguments the metric ρ will be the word metric induced by S, but we will also need to deal with other invariant metrics (see Section 7).

Given a symmetric probability measure μ on Γ let {g_{k}}_{k=1}^{∞} be i.i.d. elements of Γ which are distributed according to μ. The μ-random walk {W_{t}^{μ}}_{t=0}^{∞} is defined as W_{0}^{μ} = e_{Γ} and W_{t}^{μ} = g_{1}g_{2} ⋯ g_{t} for t ∈ . Fix p ≥ 1 and assume that

∫_{Γ} ρ(x, e_{Γ})^{p}dμ(x) = _{μ} [ρ (W_{1}^{μ}, e_{Γ})^{p}] < ∞.  (59)

Let {μ_{t}}_{t=1}^{∞} be a sequence of symmetric probability measures satisfying the integrability condition (59) and define

β_{p}^{∗} ({μ_{t}}_{t=1}^{∞}, ρ) lim sup_{t→∞} log( _{μ_{t}} [ρ (W_{t}^{μ_{t}}, e_{Γ})]) ; log(t _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{p}]).  (60)

Finally we let β_{p}^{∗}(Γ, ρ) be the supremum of β_{p}^{∗} ({μ_{t}}_{t=1}^{∞}, ρ)over all sequences of symmetric probability measures {μ_{t}}_{t=1}^{∞} on Γ satisfying

∀t ∈ ∫_{Γ} ρ(x, e_{Γ})^{p}dμ_{t}(x) < ∞ and lim_{t→∞} (tμ_{t}(Γ \ {e_{Γ}})) = ∞.  (61)

When ρ is the word metric induced by the symmetric generating set S we will use the simplified notation β_{p}^{∗}(Γ, ρ) = β_{p}^{∗}(Γ). This convention does not create any ambiguity since clearly β_{p}^{∗}(Γ, ρ) does not depend on the choice of the finite symmetric generating set S (this follows from the fact that due to (61)the denominator in (60) tends to ∞ with t—we establish this fact below).

To better explain the definition (60) we shall make some preliminary observations before passing to the main results of this section. We first note that

β_{p}^{∗}(Γ, ρ) ≤ 1.  (62)

Indeed, since we are assuming that all the ρ-balls are finite there exists ρ_{0} > 0 such that for every distinct x, y ∈ Γ we have ρ(x, y) ≥ ρ_{0}. Hence for every symmetric probability measure μ on Γ which satisfies (59) we have

μ [ρ (W_{1}^{μ}, e_{Γ})^{p}] ≥ ρ_{0}^{p}μ (Γ \ {e_{Γ}}).  (63)

Hölder’s inequality therefore implies that:

μ [ρ (W_{1}^{μ}, e_{Γ})] = _{μ} [ρ (W_{1}^{μ}, e_{Γ})1_{Γ\{e_{γ}}}]

≤ μ (Γ \ \{e_{Γ}\})^{(p−1)/p} ( _{μ} [ρ (W_{1}^{μ}, e_{Γ})^{p}])^{1/p} ≤^{(63)} \frac{1}{ρ_{0}^{p−1}} _{μ} [ρ (W_{1}^{μ}, e_{Γ})^{p}]. (64)

On the other hand, by the triangle inequality we have:

μ [ρ (W_{t}^{μ}, e_{Γ})] ≤ ∑_{i=1}^{t} _{μ} [ρ (W_{i}^{μ}, W_{i−1}^{μ})] = t _{μ} [ρ (W_{1}^{μ}, e_{Γ})] ≤^{(64)} \frac{t}{ρ_{0}^{p−1}} _{μ} [ρ (W_{1}^{μ}, e_{Γ})^{p}].  (65)

It follows that if {μ_{t}}_{t=1}^{∞} are symmetric probability measures on Γ satisfying (61) then

lim sup_{t→∞} log( _{μ_{t}} [ρ (W_{t}^{μ_{t}}, e_{Γ})]) ; log(t _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{p}]) ≤^{(63)∧(65)} lim sup_{t→∞}(1 − \frac{(p − 1) logρ_{0}}{log(tμ_{t}(Γ \ \{e_{Γ}\}))+ p logρ_{0}} ) =^{(61)} 1,

implying (62). We also claim that if 1 ≤ q ≤ p < ∞ then

β_{p}^{∗}(Γ, ρ) ≤ β_{q}^{∗}(Γ, ρ).  (66)

Indeed, let {μ_{t}}_{t=1}^{∞} be symmetric probability measures on Γ satisfying (61) and note that

μ_{t} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{q}] ≤ μ_{t}(Γ \ \{e_{Γ}\})^{(p−q)/p} ( _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{p}])^{q/p} ≤^{(63)} \frac{1}{ρ_{0}^{p−q}} _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{p}].  (67)

Hence,

lim sup_{t→∞} log( _{μ_{t}} [ρ (W_{t}^{μ_{t}}, e_{Γ})]) ; log(t _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{p}]) ≤^{(67)} lim sup_{t→∞} log( _{μ_{t}} [ρ (W_{t}^{μ_{t}}, e_{Γ})]) ; log(t _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{q}]) · \frac{1}{1 + _{\frac{(p−q) logρ_{0}}{log(t _{μt}[ρ(W_{1}^{μt},e_{Γ})^{q}])}}}

≤^{(63)} lim sup_{t→∞} log( _{μ_{t}} [ρ (W_{t}^{μ_{t}}, e_{Γ})]) ; log(t _{μ_{t}} [ρ (W_{1}^{μ_{t}}, e_{Γ})^{q}]) · \frac{1}{1 + \frac{(p−q) logρ_{0}}{log(tμ_{t}(Γ\\{e_{Γ}\}))+q logρ_{0}}} ≤^{(61)} β_{q}^{∗}(Γ, ρ),

implying (66). The main result of this section is the following theorem: Theorem 5.1. Assume that Γ is amenable and that X is a metric space with Markov type p. Then for every left-invariant metric ρ on Γ such that |B_{ρ}(e_{Γ}, r)| < ∞ for all r ≥ 0 we have:

α_{X}^{∗}(Γ, ρ) ≤ \frac{1}{pβ_{p}^{∗}(Γ, ρ)}.

Remark 5.2. In [7, 47] it was essentially shown that the bound in Theorem 5.1 holds true with β_{p}^{∗}(Γ, ρ) replaced by β_{∞}^{∗} (Γ, ρ), which is a weaker bound due to (66). More precisely [7, 47] dealt with the case when all the measures μ_{t} equal a fixed measure μ, in which case the second requirement of (61) is simply that μ is not supported on {e_{Γ}}. If we restrict to this particular case we can define an analogous parameter by

β̃_{p}^{∗}(μ, ρ) = β_{p}^{∗} (\{μ, μ, μ, …\}, ρ) lim sup_{t→∞} \frac{log( _{μ} [ρ (W_{t}^{μ}, e_{Γ})])}{logt} .

and similarly by taking the supremum over all symmetric probability measures measures μ satisfying (61)we can define the parameter β̃_{p}^{∗}(Γ, ρ). An inspection of the results in [7, 47] shows that a variant of Theorem 5.1 is established there with β_{p}^{∗}(Γ, ρ) replaced by β̃_{∞}^{∗} (Γ, ρ). Thus Theorem 5.1 is formally stronger than the results of [7, 47]. As we shall see in Section 6, this is a strict improvement which is crucial for our proof of the bound α_{p}^{∗}( ≀ ) ≤ \frac{p}{2p−1} , and in Section 7 we will also need to use a family of non-identical measures {μ_{t}}_{t=1}^{∞}.

Proof of Theorem 5.1. Let {F_{n}}_{n=0}^{∞} be a Følner sequence for Γ, i.e., for every ε > 0 and any finite K ⊆ Γ, we have |F_{n}△(F_{n}K)| ≤ ε|F_{n}| for large enough n. Fix β < β_{p}^{∗}(Γ, ρ). Then there exists a sequence of symmetric probability measures {μ_{t}}_{t=1}^{∞} on Γ which satisfy (61) and β < β_{p}^{∗} ({μ_{t}}_{t=1}^{∞}, ρ). This implies that there exists an increasing sequence of integers {t_{k}}_{k=1}^{∞} for which

μ_{t_{k}} [ρ (W_{t_{k}}^{μ_{t_{k}}}, e_{Γ})] ≥ t_{k}^{β} ( _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}])^{β} ,

for all k. For every t, r ∈ consider the event

Λ_{t}(r) ⋂_{j=1}^{t} {W_{j}^{μ_{t}} ∈ B_{ρ}(e_{Γ}, r)}.

By the monotone convergence theorem for every k ∈ there exists r_{k} ∈ such that

μ_{t_{k}} [ρ (W_{t_{k}}^{μ_{t_{k}}}, e_{Γ})1_{Λ_{t_{k}}(r_{k})} ] ≥ \frac{1}{2}t_{k}^{β} ( _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}])^{β} .  (68)

Since |B_{ρ}(e_{Γ}, r_{k})| < ∞ for every k ∈ we can find n_{k} ∈ such that if we denote A F_{n_{k}}B_{ρ}(e_{Γ}, r_{k}) ⊇ F_{n_{k}} then we have (by the Følner condition with ε = 1),

|A \ F_{n_{k}}| ≤ |F_{n_{k}}| ⟹ |F_{n_{k}}| ≥ \frac{1}{2}|A|.  (69)

Fix k ∈ and let {g_{i}}_{i=1}^{∞} ⊆ Γ be i.i.d. group elements distributed according to μ_{t_{k}} such that W_{t}^{μ_{t_{k}}} = g_{1}g_{2} ⋯ g_{t} for every t ∈ . Let Z_{0} be uniformly distributed over A and independent of {g_{i}}_{i=1}^{∞}. For t ∈ define

Z_{t} \{ \begin{matrix}Z_{t−1}g_{t} & if Z_{t−1}g_{t} ∈ A, \\ Z_{t−1} & otherwise. \end{matrix}

Consider the event Ω {Z_{0} ∈ F_{n_{k}}} ∩ Λ_{t_{n_{k}}}(r_{k}). By construction when Ω occurs we have Z_{t_{k}} = Z_{0}W_{t_{k}}^{μ_{t_{k}}}. Hence

μ_{t_{k}} [ρ (Z_{t_{k}}, Z_{0})] ≥ _{μ_{t_{k}}} [ρ (Z_{0}W_{t_{k}}^{μ_{t_{k}}}, Z_{0})1_{Ω} ]

=^{(∗)} [Z_{0} ∈ F_{n_{k}}]· _{μ_{t_{k}}} [ρ (W_{t_{k}}^{μ_{t_{k}}}, e_{Γ})1_{Λ_{t_{k}}(r_{k})} ] ≥^{(68)∧(69)} \frac{1}{4}t_{k}^{β} ( _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}])^{β} , (70)

where in (∗) we used the independence of Z_{0} and {g_{i}}_{i=1}^{∞} and the left-invariance of ρ.

On the other hand fix α ∈ (0, 1) and assume that there exists an embedding f : Γ → X and c, C ∈ (0, ∞) such that

x, y ∈ Γ ⟹ cρ(x, y)^{α} ≤ d_{X}(f (x), f (x)) ≤ Cρ(x, y).  (71)

Our goal is to show that α ≤ \frac{1}{pβ}. Since β < 1 this inequality is vacuous if pα < 1. We may therefore assume that pα ≥ 1. Since {Z_{t}}_{t=0}^{∞} is a stationary reversible Markov chain, for every M > M_{p}(X) and k ∈ we have

[d_{X}(f (Z_{t_{k}}), f (Z_{0}))^{p}] ≤ M^{p}t_{k} [d_{X}(f (Z_{1}), f (Z_{0}))^{p}]

≤^{(71)} M^{p}C^{p}t_{k} [ρ(Z_{1}, Z_{0})^{p}] ≤^{(∗∗)} M^{p}C^{p}t_{k} _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}], (72)

Where in (∗∗) we used the point-wise inequality ρ(Z_{1}, Z_{0}) ≤ ρ(g_{1}, e_{Γ}) = ρ (W_{1}^{μ_{t_{k}}}, e_{Γ}). On the other hand,

[d_{X}(f (Z_{t_{k}}), f (Z_{0}))^{p}] ≥^{(71)} c^{p} [ρ (Z_{t_{k}}, f Z_{0})^{αp}]

≥^{αp≥1} c^{p} ( [ρ(Z_{t_{k}}, Z_{0})])^{αp} ≥^{(70)} \frac{c^{p}t_{k}^{αβp}}{4^{αp}} ( _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}])^{αβp} . (73)

Combining (72) and (73) we deduce that

(ρ_{0}^{p}t_{k}μ_{t_{k}}(Γ \ \{e_{Γ}\}))^{αβp−1} ≤^{(63)} (t_{k} _{μ_{t_{k}}} [ρ (W_{1}^{μ_{t_{k}}}, e_{Γ})^{p}])^{αβp−1} ≤ \frac{4^{αp}M^{p}C^{p}}{c^{p}}.  (74)

Taking k → ∞ in (74) while using the assumption (61) we conclude that αβp ≤ 1, as required.

The following theorem is a variant of Theorem 5.1 which deals with equivariant embeddings of general groups (not necessarily amenable) into uniformly smooth Banach spaces. Its proof is an obvious modification of the proof of Theorem 2.1 in [47]: one just has to notice that in that proof the i.i.d. group elements {σ_{k}}_{k=1}^{∞} need not be uniformly distributed over a symmetric generating set S ⊆ Γ—the argument goes through identically if they are allowed to be distributed according to any symmetric probability measure μ satisfying the integrability condition (59).

Theorem 5.3. Let Γ be a group and ρ a left-invariant metric on Γ such that |B_{ρ}(e_{Γ}, r)| < ∞ for all r ≥ 0. Assume that X is a Banach space whose modulus of uniform smoothness has power-type p ∈ [1, 2]. Then:

α_{X}^{#}(Γ, ρ) ≤ \frac{1}{pβ_{p}^{∗}(Γ, ρ)}.

By the results of Section 9 Theorem 5.3 implies Theorem 5.1 when X is a Banach space whose modulus of uniform smoothness has power-type p rather than a general metric space with Markov type p. Note that the former assumption implies the latter assumption as shown in [48].

6 Stable walks and the L_{p} compression of ≀

This section is devoted to the proof of the following theorem:

Theorem 6.1. For every p ∈ (1, 2) we have

β_{p}^{∗}( ≀ ) = \frac{2p − 1}{p^{2}} .

Note that since in [47] we proved that α_{p}^{∗}( ≀ ) ≥ \frac{p}{2p−1} , Theorem 5.1 implies that β_{p}^{∗}( ≀ ) ≤ \frac{2p−1}{p^{2}} .

Thus in order to prove Theorem 6.1 it suffices to show that β_{p}^{∗}( ≀ ) ≥ \frac{2p−1}{p^{2}} , which would also imply that α_{p}^{∗}( ≀ ) = \frac{p}{2p−1} . In order to establish this lower bound on β_{p}^{∗}( ≀ ) we will analyze certain symmetric random walks on ≀ which arise from discrete approximations of q-stable random variables for some q ∈ (p, 2).

6.1 Some general properties of symmetric walks on

Let X be a -valued symmetric random variable and let X_{1}, X_{2}, … be i.i.d. copies of X. For each n ∈ define S_{n} = X_{1} + ⋯ + X_{n} (and set S_{0} = 0). We also define S_{[o,n]} to be the random set {S_{0}, …, S_{n}}. We will record here for future use some general properties of the walk S_{n}. These are simple facts which appeared in various guises in the literate (though we did not manage to pinpoint cleanly stated references for them). We include this brief discussion for the sake of completeness.

Lemma 6.2. For S_{n} as above we have

[|S_{n}|] ≥ \frac{1}{4} [|S_{[0,n]}|].  (75)

Proof. Fix R ≥ 0 and denote τ min{t ≥ 0 : |S_{t}| ≥ R}. Note the following inclusion of events:

{|S_{n}| ≥ R}⊇ {τ ≤ n ∧ sign ( ∑_{k=τ+1}^{n} X_{k})= sign(S_{τ})} .

It follows that:

[|S_{n}| ≥ R] ≥ ∑_{m=0}^{n} [τ = m ∧ sign ( ∑_{k=m+1}^{n} X_{k})= sign(S_{m})] = ∑_{m=0}^{n} [τ = m] · [S_{n−m} ≥ 0]

≥^{(⋆)} \frac{1}{2} ∑_{m=0}^{n} [τ = m] = \frac{1}{2} [τ ≤ n] , (76)

where in (⋆) we used the symmetry of S_{n−m}. Note that if |S_{[0,n]}| ≥ 2R then one of the numbers {|S_{0}|, …, |S_{n}|} must be at least R. Thus

[τ ≤ n] ≥ [|S_{[0,n]}| ≥ 2R].  (77)

It follows that:

[|S_{n}|] = ∑_{R=0}^{∞} [|S_{n}| ≥ R] ≥^{(76)∧(77)} \frac{1}{2} ∑_{R=0}^{∞} [|S_{[0,n]}| ≥ 2R]

≥ \frac{1}{2} ∑_{R=0}^{∞} \frac{[|S_{[0,n]}| ≥ 2R]+ [|S_{[0,n]}| ≥ 2R + 1]}{2} = \frac{1}{4} [|S_{[0,n]}|],

as required.

The proof of the following lemma is a slight variant of the argument used to prove the first assertion of Lemma 6.3 in [47].

Lemma 6.3. Let S_{n} be as above and denote R_{n} |{k ∈ {0, …, n} : S_{k} = 0}|. Then

[R_{n} ≥ \frac{1}{2} ∑_{ℓ=0}^{n} [S_{ℓ} = 0]] ≥ \frac{1}{8}.  (78)

Proof. Since R_{n} = ∑ _{ℓ=0}^{n} 1_{{S_{ℓ}=0}} we have [R_{n}] = ∑ _{ℓ=0}^{n} [S_{ℓ} = 0] and:

[R_{n}^{2}]= ∑_{ℓ=0}^{n} [S_{ℓ} = 0] + 2 ∑_{\begin{matrix}i,j∈\{0,...,n\} \\ i<j \end{matrix}} [S_{i} = S_{j} = 0]

= [R_{n}]+ 2 ∑_{\begin{matrix}i,j∈\{0,...,n\} \\ i<j \end{matrix}} [S_{i} = 0] · [S_{j−i} = 0] ≤ [R_{n}]+ ( [R_{n}])^{2} ≤ 2 ( [R_{n}])^{2} .

Since for every nonnegative random variable Z we have [Z ≥ \frac{1}{2} [Z]] ≥ \frac{1}{4} \frac{( [Z])^{2}}{[Z^{2}]} (which is an easy consequence of the Cauchy-Schwartz inequality—see [51, 2]) we deduce that [R_{n} ≥ \frac{1}{2} [R_{n}]] ≥ \frac{1}{8}, as required.

The proof of the following lemma is a slight variant of the argument used to prove the second assertion of Lemma 6.3 in [47].

Lemma 6.4. For S_{n} as above we have:

[|S_{[0,n]}|] ≥ \frac{n + 1}{2 ∑ _{ℓ=0}^{n} [S_{ℓ} = 0]} .  (79)

Proof. Fix k ∈ {1, …, n + 1} and denote k̃ min{k, |S_{[0,n]}|}. Let V_{1}, …, Vk̃ be the first distinct k̃ integers that were visited by the walk S_{0}, S_{1}, …, S_{n}. For simplicity of notation we also set V_{j} = n + 1 when j ∈ {k̃+ 1, …, n}. Write

τ_{j} \{ \begin{matrix}min\{0 ≤ τ ≤ n : S_{τ} = V_{j}\} & j ≤ k̃, \\ n + 1 & j > k̃. \end{matrix}

Denote Y_{k} |{0 ≤ j ≤ n : S_{j} ∈ {V_{1}, …, Vk̃}}|. Then

[Y_{k}]= ∑_{j=1}^{k} [|{0 ≤ ℓ ≤ n : S_{ℓ} = V_{j}}|] = ∑_{j=1}^{k} [∑_{ℓ=0}^{n} 1_{{S_{ℓ}=V_{j}}}]= ∑_{j=1}^{k} [∑_{ℓ=τ_{j}}^{n} [S_{ℓ} = S_{τ_{j}}] | τ_{j} ]

= ∑_{j=1}^{k} [∑_{ℓ=τ_{j}}^{n} [S_{ℓ−τ_{j}} = 0] | τ_{j} ]≤ k ∑_{ℓ=0}^{n} [S_{ℓ} = 0] . (80)

Hence

[|S_{[0,n]}| ≤ k] ≤ [Y_{k} ≥ n + 1] ≤ \frac{[Y_{k}]}{n + 1} ≤^{(80)} \frac{k}{n + 1} ∑_{ℓ=0}^{n} [S_{ℓ} = 0] .  (81)

It follows that if we denote m = \frac{n+1}{∑ _{ℓ=0}^{n} [S_{ℓ}=0]} then

[|S_{[0,n]}|] = ∑_{k=1}^{n+1} [|S_{[0,n]}| ≥ k] = ∑_{k=1}^{n+1} (1 − [|S_{[0,n]}| ≤ k − 1]) ≥^{(81)} ∑_{k=1}^{⌈m⌉}(1 − \frac{k − 1}{m})

= ⌈m⌉ − \frac{⌈m⌉(⌈m⌉ − 1)}{2m}≥ \frac{⌈m⌉}{2}≥ \frac{n + 1}{2 ∑ _{ℓ=0}^{n} [S_{ℓ} = 0]} ,

as required.

6.2 An analysis of a particular discrete stable walk on

In this section we will analyze a specific random walk on which will be used in estimating β_{p}^{∗}( ≀ ). Similar bounds are known to hold in great generality for arbitrary walks which are in the domain of attraction of q-stable random variables, and not only for the walk presented below. Specifically, such general results can be deduced from Gnedenko’s local central limit theorem for convergence to stable laws (see Theorem 4.2.1 in [37]), in combination with some estimates on such walks from [29] (see section IX.8, Theorem 1 there). Since for the purpose of proving compression bounds all we need is to construct one such walk, we opted for the sake of concreteness to present here a simple self-contained proof of the required properties of a particular walk which is perfectly suited for the purpose of our applications to embedding theory.

In what follows fix q ∈ (p, 2). Define a_{1} = a_{−1} = 0 and for n ∈ ( \ {1}) ∪ {0},

a_{n} = a_{−n} = \frac{(−1)^{n}}{2q} \binom{q}{n} = \frac{(−1)^{n}}{2q} · \frac{q(q − 1) ⋯ (q − n + 1)}{n!} .  (82)

Note that since q ∈ (1, 2) the definition (82) implies that for n 1 we have a_{n} > 0. Since we defined a_{±1} to be equal 0 it follows that {a_{n}}_{n∈} ⊆ [0, ∞). An application of Stirling’s formula implies that as n → ∞ we have

a_{n} = \frac{1}{2q}\binom{n − q − 1}{n} ≍ \frac{1}{n^{q+1}},  (83)

where the implicit constants depend only on q (and are easily estimated if so desired). Note in particular that since q > p, (83) implies that

∑_{n∈} a_{n}|n|^{p} < ∞,  (84)

and

φ(θ) ∑_{n∈} a_{n}e^{inθ}  (85)

converges uniformly on [−π, π]. Moreover it is easy to compute φ(θ) explicitly:

φ(θ) = \frac{e^{iθ} + e^{−iθ}}{2} + \frac{1}{2q} ∑_{n=0}^{∞}(−1)^{n}\binom{q}{n}(e^{inθ}+ e^{−inθ}) = cosθ + \frac{(1 − e^{iθ})^{q} + (1 − e^{−iθ})^{q}}{2q}

= cosθ + \frac{2^{q/2}}{q}(1 − cosθ)^{q/2}cos(\frac{q(π − θ)}{2}) ∈ . (86)

An immediate consequence of (86) is that ∑ _{n∈} a_{n} = φ(0) = 1. Thus we can define a symmetric random variable X on by [X = n] = a_{n}. With this notation (84) becomes |X|^{p} < ∞. Another corollary of the identity (86) is that there exits ε = ε(q) ∈ (0, 1) and c = c(q) > 0 such that for every θ ∈ [−ε, ε] we have [e^{iθX}] = φ(θ) ∈ [e^{−2c|θ|^{q}}, e^{−c|θ|^{q}}]. Note also that since for every θ 0 we have |φ(θ)| < ∑ _{n∈} a_{n} = 1 there exists some δ = δ(q) ∈ (0, 1) such that for every θ ∈ [−π, −ε] ∪ [ε, π] we have |φ(θ)| ≤ 1 − δ.

Now let X_{1}, X_{2}, … be i.i.d. copies of X. Denote S_{n} = X_{1} + ⋯ + X_{n}. Then the above bounds imply that

[S_{n} = 0] = \frac{1}{2π} ∫ _{−π}^{π} ( [e^{iθS_{n}}]) dθ = \frac{1}{2π} ∫ _{−π}^{π} φ(θ)^{n}dθ

∈ \frac{1}{2π} [∫ _{−ε}^{ε} e^{−2cn|θ|^{q}}dθ − ∫_{[−π,−ε]∪[ε,π]} (1 − δ)^{n}dθ, ∫ _{−ε}^{ε} e^{−cn|θ|^{q}}dθ + ∫_{[−π,−ε]∪[ε,π]} (1 − δ)^{n}dθ].

This implies that as n → ∞ we have

[S_{n} = 0] ≍ \frac{1}{n^{1/q}}.  (87)

Substituting (87) into (79) we see that

[|S_{[0,n]}|] = [|{S_{0}, …, S_{n}}|] n^{1/q}.  (88)

In combination with (79) it follows that

[|S_{n}|] n^{1/q}.  (89)

Additionally, if we let R_{n} be as in Lemma 6.3 (for the particular symmetric walk S_{n} studied here) then by plugging (87) into (78) we get the bound

[R_{n}^{1/q}] n^{(q−1)/q^{2}}.  (90)

6.3 The induced walk on ≀ and the lower bound on β_{p}^{∗}( ≀ )

In this section we will conclude the proof of Theorem 6.1. Modulo the previous preparatory sections, the argument below closely follows the proof of Theorem 6.2 in [47].

For every n_{1}, n_{2}, n_{3} ∈ define f_{n_{1},n_{2}}^{n_{3}} : → by

f_{n_{1},n_{2}}^{n_{3}}(k) n_{1}1_{\{0\}}+ n_{2}1_{\{n_{3}\}}= \{ \begin{matrix}n_{1} & if k = 0, \\ n_{2} & if k = n_{3} ∧ n_{3} 0, \\ n_{1} + n_{2} & if k = 0 = n_{3}, \\ 0 & otherwise. \end{matrix}

Denote

x_{n_{1},n_{2},n_{3}} (f_{n_{1},n_{2}}^{n_{3}}, n_{3}) ∈ ≀ .  (91)

To better understand the meaning of this group element, note that for every (g, ℓ) ∈ ≀ we have (g, ℓ)x_{n_{1},n_{2},n_{3}} = (h, ℓ + n_{3}) where

h(k) = \{ \begin{matrix}g(k) + n_{1} & if k = ℓ, \\ g(k) + n_{2} & if k = ℓ + n_{3} ∧ n_{3} 0, \\ g(ℓ) + n_{1} + n_{2} & if k = ℓ ∧ n_{3} = 0, \\ g(k) & otherwise. \end{matrix}

Thus if we let μ be the symmetric probability measure on ≀ given by μ({x_{n_{1},n_{2},n_{3}}}) = a_{n_{1}}a_{n_{2}}a_{n_{3}}, where {a_{n}}_{n∈} are the coefficients from Section 6.2, then the walk {W_{t}^{μ}}_{t=0}^{∞} can be described in words as follows: start at (0, 0) and at each step choose three i.i.d. numbers n_{1}, n_{2}, n_{3} ∈ distributed according to the random variable X from Section 6.2. Add n_{1} to the current location of the lamplighter, move the lamplighter n_{3} units and add n_{2} to the new location of the lamplighter.

Write W_{t}^{μ} = (f_{t}, m_{t}). By the above description m_{t} has the same distribution as the walk S_{t} from Section 6.2. Fix n ∈ and for m ∈ denote T_{m} |{t ∈ {0, …, n} : m_{t} = m} |. The above description of the walk W_{t}^{μ} ensures that conditioned on {T_{m}}_{m∈} and on “terminal point” m_{n}, if k ∈ \ {0, m_{n}} then f_{n}(m) has the same distribution as S_{2T_{m}}, if m ∈ {0, m_{n}} and m_{n} 0 then f_{n}(m) has the same distribution as S_{max{2T_{m}−1,0}}, and if m ∈ {0, m_{n}} and m_{n} = 0 then f_{n}(m) has the same distribution as S_{2T_{m}}. Thus using (89) we see that

[|f_{n}(m)|] [T_{m}^{1/q}].  (92)

Fix m ∈ and for t ∈ {0, …, n} define the event A_{t} {m_{t} = m ∧ m {0, …, m_{ℓ−1}}. Note that conditioned on A_{t} the random variable T_{m} has the same distribution as R_{T_{m}}, where {R_{k}}_{k=0}^{n} is as in (90). Hence,

[T_{m}^{1/q}]≥ ∑_{t=0}^{⌊n/2⌋} (A_{t}) · [T_{m}^{1/q}|A_{t}] ∑_{t=0}^{⌊n/2⌋} (A_{t}) · n^{(q−1)/q^{2}} = n^{(q−1)/q^{2}} [m ∈ {m_{0}, …, m_{⌊n/2⌋}}] .  (93)

It follows that

[d_{≀} (W_{n}^{μ}, (0, 0))] ∑_{m∈} [|f_{n}(m)|]^{(92)} ∑_{m∈} [T_{m}^{1/q}]^{(93)} n^{(q−1)/q^{2}} ∑_{m∈} [m ∈ {m_{0}, …, m_{⌊n/2⌋}}]

= n^{(q−1)/q^{2}} [|{S_{0}, …, S_{⌊n/2⌋}}|] ^{(88)} n^{(q−1)/q^{2}} · n^{1/q} = n^{(2q−1)/q^{2}}. (94)

On the other hand it follows from (84) that [d_{≀} (W_{1}^{μ}, (0, 0))^{p}] < ∞ so we deduce from the definition of β_{p}^{∗}( ≀ ) that

β_{p}^{∗}( ≀ ) ≥ \frac{2q − 1}{q^{2}} .

Letting q → p^{+} we deduce Theorem 6.1.

Remark 6.5. The same argument as above actually shows that for every finitely generated group G and every p ∈ (1, 2] we have

β_{p}^{∗}(G ≀ ) ≥ \frac{1}{p} + (1 − \frac{1}{p}) β_{p}^{∗}(G).  (95)

This implies Theorem 6.1 since the computations in Section 6.2 show that β_{p}^{∗}( ) ≥ \frac{1}{p}. Note of course that due to Theorem 5.1we actually know that β_{p}^{∗}( ) = \frac{1}{p}. We also observe that if H is a finitely generated group whose growth is at least quadratic then β_{p}^{∗}(G≀H) = 1. Indeed we have established the fact that β_{p}^{∗}(G≀H) ≤ 1 in (62), while the lower bound follows from Theorem 6.1 in [47] which states that β^{∗}(G ≀H) = 1, combined with the obvious fact that β^{∗}(G ≀H) ≤ β_{p}^{∗}(G ≀H).

Remark 6.6. Define inductively _{(1)} = and _{k+1} = _{(k)} ≀ . Then for p ∈ (1, 2] we have β_{p}^{∗}(Z_{(1)}) = \frac{1}{p} and (95) implies that β_{p}^{∗}( _{(k+1)}) ≥ \frac{1}{p} + (1 − \frac{1}{p}) β_{p}^{∗}( _{(k)}). It follows by induction that for all k ∈ we have

β_{p}^{∗}( _{(k)}) ≥ 1 − (1 − \frac{1}{p})^{k}.  (96)

Note that α_{p}^{∗}( _{(1)}) = 1 and by [57] α_{p}^{∗}(C_{2} ≀ ) = 1 (see also the different proof of this fact in [47]). Thus Corollary 2.2 implies that

α_{p}^{∗}( _{(k+1)}) ≥ \frac{pα_{p}^{∗}( _{(k)})}{pα_{p}^{∗}( _{(k)}) + p − 1} .

It follows by induction that

α_{p}^{∗}( _{(k)}) ≥ \frac{1}{p (1 − (1 − \frac{1}{p})^{k})} .  (97)

By combining (96) and (97) with Theorem 5.1 we see that

α_{p}^{∗}( _{(k)}) = \frac{1}{p (1 − (1 − \frac{1}{p})^{k})} and β_{p}^{∗}( _{(k)}) = 1 − (1 − \frac{1}{p})^{k}.

For p ∈ (2, ∞) the same reasoning (using the fact that L_{p} has Markov type 2 [48]) shows that α_{p}^{∗}( _{(k)}) = α_{2}^{∗}( _{(k)}) and β_{p}^{∗}( _{(k)}) = β_{2}^{∗}( _{(k)}).

7 A computation of β_{p}^{∗} (( ≀ )_{0}, d_{≀} )

The purpose of this section is to prove the following result:

Theorem 7.1. Let G, H be infinite groups generated by the finite symmetric sets S_{G} ⊆ G and S_{H} ⊆ H, respectively. Let (G ≀H)_{0} = {(f, x) ∈ G ≀H : x = e_{H}} be the zero section of G ≀H. Then for all p ∈ [1, 2] we have

β_{p}^{∗} ((G ≀H)_{0}, d_{G≀H})≥ \frac{2}{p + 1} .  (98)

Specializing to the case G = H = we can apply Theorem 5.1 when ρ is the metric induced from ≀ on the amenable group (Z ≀ )_{0} to deduce that

\frac{p + 1}{2p} ≥ \frac{1}{pβ_{p}^{∗} (( ≀ )_{0}, d_{≀} )} ≥ α_{p}^{∗} (( ≀ )_{0}, d_{≀} ) =^{(Thm. 4.1)} \frac{p + 1}{2p} .  (99)

Thus in particular there is equality in (98) when G = H = .

Proof of Theorem 7.1. For every k ∈ let g_{k} ∈ G and h_{k} ∈ H be elements satisfying d_{G}(g_{k}, e_{G}) = k and d_{H}(h_{k}, e_{H}) = k. Such elements exists since G, H are assumed to be infinite. We shall write below h_{k}^{−1} = h_{−k}. Fix an even integer n ∈ . For every k ∈ [1, n/2] ∪ [−n/2, −1] and ε, δ ∈ {−1, 1} define f_{k,ε,δ}: H → G by

f_{k,ε,δ}(x) \{ \begin{matrix}g_{n}^{ε} & if x = e_{H}, \\ g_{n}^{δ} & if x = h_{k}, \\ e_{G} & otherwise. \end{matrix}

Let μ_{n} be the symmetric measure on (G ≀H)_{0} which is uniformly distributed on the 4n elements

{(f_{k,ε,δ}, e_{H}) : k ∈ [1, n/2] ∪ [−n/2, −1], ε, δ ∈ {−1, 1}}⊆ (G ≀H)_{0}.

Then the following point-wise inequality holds true:

0 < d_{G≀H}(W_{1}^{μ_{n}}, e_{G≀H})≤ 3n.  (100)

It follows in particular that the conditions in (61) hold true for the sequence {μ_{n}}_{n=1}^{∞}. Moreover, for each k ∈ [1, n/2] ∪ [−n/2, −1] the probability that in exactly one of the first n steps of the walk {W_{t}^{μ_{n}}}_{t=0}^{∞} the h_{k}

coordinate was altered is (1 − \frac{1}{n})^{n−1} > \frac{1}{3}. Therefore the expected number of of coordinates h_{k} that were altered exactly once is greater than n/3. Each such coordinate contributes n to the distance between W_{n}^{μ_{n}} and e_{G≀H}. Hence

μ_{n} [d_{G≀H}(W_{n}^{μ_{n}}, e_{G≀H})]≥ \frac{n^{2}}{3}.  (101)

It follows from the definition (60) that

β_{p}^{∗} ((G ≀H)_{0}, d_{G≀H})≥ β_{p}^{∗} (\{μ_{n}\}_{n=1}^{∞} , d_{G≀H}) ≥^{(100)∧(101)} lim sup_{n→∞} \frac{log(n^{2}/3)}{log(3^{p}n^{1+p})} = \frac{2}{p + 1} ,

as required.

8 An application to the Lipschitz extension problem

The purpose of this section is to prove the following theorem:

Theorem 8.1. There exists a Lipschitz function F : ( ≀ )_{0} → L_{2} which cannot be extended to a Lipschitz function from ≀ to L_{2}.

The key step in the proof of Theorem 8.1 is the use of the function constructed in Theorem 4.1. The other fact that we will need is Lemma 8.2 below. Recall that a Markov chain {Z_{t}}_{t=0}^{∞} is called a symmetric Markov chain on ≀ if there exists an N-point subset {z_{1}, …, z_{N}} ⊆ ≀ and an N × N symmetric stochastic matrix A = (a_{ij}) such that [Z_{0} = z_{i}] = \frac{1}{N} for all i ∈ \{1, …, N\} and for all i, j ∈ \{1, …, N\} and t ∈ we have [Z_{t+1} = x_{j}|Z_{t} = z_{i}] = a_{ij}.

The following lemma asserts that there is a fast-diverging symmetric Markov chain on ≀ which remains within a relatively narrow tubular neighborhood around the zero section ( ≀ )_{0}.

Lemma 8.2. For every ε > 0 there exists an integer n_{0}(ε) ∈ N such that for all n ≥ n_{0}(ε) there is a symmetric Markov chain {Z_{t}}_{t=0}^{∞} on ≀ which satisfies the following conditions:

1. d_{≀} (Z_{1}, Z_{0}) ≤ 4 (point-wise),

2. d_{≀} (Z_{t}, ( ≀ )_{0}) ≤ 2n^{(1+ε)/2} for all t ≥ 0 (point-wise),

3. [d_{≀} (Z_{n}, Z_{0})] n^{3/4}.

Assuming Lemma 8.2 for the moment we shall prove Theorem 8.1.

Proof of Theorem 8.1. Fix ε ∈ (0, 1/11). By Theorem 4.1 there exists a function F : ( ≀ )_{0} → L_{2} and c = c(ε) > 0 such that ∥F∥_{Lip} = 1 and for every x, y ∈ ( ≀ )_{0} we have

∥F(x) − F(y)∥_{2} ≥ cd_{≀} (x, y)^{(3−ε)/4}.  (102)

Assume for the sake of contradiction that there exists a function F̃ : ≀ → L_{2} such that F̃ _{( ≀ )_{0}} = F and ∥F̃∥_{Lip} = L < ∞.

Let n_{0}(ε) and {Z_{t}}_{t=0}^{∞} be as in Lemma 8.2 and fix n ≥ n_{0}(ε). Write Z_{t} = (f_{t}, k_{t}) and define Z_{t}^{0} = (f_{t}, 0) ∈ ( ≀ )_{0}. The second assertion of Lemma 8.2 implies that for all t ≥ 0 we have

d_{≀} (Z_{t}, Z_{t}^{0})≤ 2n^{(1+ε)/2}.  (103)

Using the Markov type 2 property of L_{2} [9] (with constant 1) and the first assertion of Lemma 8.2 we see that:

[∥F̃(Z_{n}) − F̃(Z_{0})∥_{2}^{2}] ≤ n [∥F̃(Z_{1}) − F̃(Z_{0})∥_{2}^{2}] ≤ nL^{2} [d_{≀} (Z_{1}, Z_{0})^{2}]≤ 16nL^{2}.  (104)

Note the following elementary corollary of the triangle inequality which holds for every metric space (X, d), every p ≥ 1 and every a_{1}, a_{2}, b_{1}, b_{2} ∈ X:

d(a_{1}, b_{1})^{p} ≥ \frac{1}{3^{p−1}} d(a_{2}, b_{2})^{p} − d(a_{1}, a_{2})^{p} − d(b_{1}, b_{2})^{p}.  (105)

Hence we have the following point-wise inequality:

∥F̃(Z_{n}) − F̃(Z_{0})∥_{2}^{2} ≥^{(105)} \frac{1}{3} ∥F (Z_{n}^{0})− F (Z_{0}^{0})∥_{2}^{2} − ∥F̃(Z_{n}) − F̃ (Z_{n}^{0})∥_{2}^{2} − ∥F̃(Z_{0}) − F̃ (Z_{0}^{0})∥_{2}^{2}

≥^{(102)}  \frac{c^{2}}{3}d_{≀} (Z_{n}^{0}, Z_{0}^{0})^{(3−ε)/2} − L^{2}d_{≀} (Z_{n}, Z_{n}^{0})^{2} − L^{2}d_{≀} (Z_{0}, Z_{0}^{0})^{2}
≥^{(105)∧(103)} \frac{c^{2}}{3} (\frac{1}{3}d_{≀} (Z_{n}, Z_{0})^{(3−ε)/2} − d_{≀} (Z_{n}, Z_{n}^{0})^{(3−ε)/2} − d_{≀} (Z_{0}, Z_{0}^{0})^{(3−ε)/2}) − 8L^{2}n^{1+ε}
≥^{(103)}  \frac{c^{2}}{9}d_{≀} (Z_{n}, Z_{0})^{(3−ε)/2} − 10L^{2}n^{1+ε}.  (106)

Taking expectation in (106) and using the third assertion of Lemma 8.2 we see that:

16nL^{2} ≥ [∥F̃(Z_{n}) − F̃(Z_{0})∥_{2}^{2}] ≥ \frac{c^{2}}{9} [d_{≀} (Z_{n}, Z_{0})^{(3−ε)/2}]− 10L^{2}n^{1+ε}

≥ ( [d_{≀} (Z_{n}, Z_{0})])^{(3−ε)/2} − 10L^{2}n^{1+ε} n^{3(3−ε)/8} − 10L^{2}n^{1+ε},

which is a contradiction for large enough n since the assumption ε < 1/11 implies that \frac{3(3−ε)}{8} > 1 + ε.

It remains to prove Lemma 8.2.

Proof of Lemma 8.2. Fix an integer n ∈ and ε ∈ (0, 1/4). Define two subsets U_{n}, V_{n} ⊆ ≀ by

U_{n} {(f, k) ∈ ≀ : supp(f) ⊆ [−n, n], |k| ≤ 2n^{(1+ε)/2}, |f (ℓ)| ≤ n^{2} ∀ ℓ ∈ } ,
V_{n} {(f, k) ∈ ≀ : supp(f) ⊆ [−n, n], |k| ≤ n^{(1+ε)/2}, |f (ℓ)| ≤ n^{2} − 2n ∀ ℓ ∈ } .

Then |U_{n}| ≍ (2n^{2} + 1)^{2n+1} (4n^{(1+ε)/2} + 1) and |V_{n}| ≍ (2n^{2} − 4n + 1)^{2n+1} (2n^{(1+ε)/2} + 1) so that

\frac{|V_{n}|}{|U_{n}|} 1.  (107)

Consider the set S = {x_{n_{1},n_{2},n_{3}} : n_{1}, n_{2}, n_{3} ∈ {−1, 1}}, where x_{n_{1},n_{2},n_{3}} are as defined in (91). Then S is a symmetric generating set of ≀ consisting of 8 elements. Let g_{1}, g_{2}, … be i.i.d. elements of ≀ which are uniformly distributed over S and denote W_{m} g_{1} ⋯ g_{m} = (f_{m}, k_{m}). Then by construction the sequence {k_{m}}_{m=1}^{∞} has the same distribution as the standard random walk on , i.e., the same distribution as {S_{m} = ε_{1} + ⋯+ ε_{m}}_{m=1}^{∞} where ε_{1}, ε_{2}, … are i.i.d. Bernoulli random variables (this fact was explained in greater generality in Section 6.3). Also, as shown by Èrschler [28], we have

[d_{≀} (W_{n}, (0, 0))] ≥ cn^{3/4},  (108)

where c > 0 is a universal constant. Note that since d_{≀} (x_{n_{1},n_{2},n_{3}}, (0, 0)) ≤ 4 for every n_{1}, n_{2}, n_{3} ∈ {−1, 1} we have point-wise bound

d_{≀} (W_{n}, (0, 0))≤ 4n.  (109)

Now let Z_{0} be uniformly distributed over U_{n} and independent of {g_{i}}_{i=1}^{∞}. For t ∈ define

Z_{t} \{ \begin{matrix}Z_{t−1}g_{t} & if Z_{t−1}g_{t} ∈ U_{n}, \\ Z_{t−1} & otherwise. \end{matrix}

The first two assertions of Lemma 8.2 hold true by construction. It remains to establish the third assertion of Lemma 8.2.

Consider the events E {Z_{0} ∈ V_{n}} and F {max_{m≤n}|k_{m}| ≤ n^{(1+ε)/2}}. Note that if the event E ∩ F occurs then Z_{n} = Z_{0}W_{n} since by design in this case Z_{0} ∈ V_{n} and therefore Z_{0}W_{t} cannot leave U_{n} for all t ≤ n. It follows that

[d_{≀} (Z_{n}, Z_{0})] ≥ [d_{≀} (W_{n}, (0, 0))1_{E∩F} ]= [E]( [d_{≀} (W_{n}, (0, 0))]− [d_{≀} (W_{n}, (0, 0))1_{F^{c}}])

≥^{(108)∧(109)} \frac{|V_{n}|}{|U_{n}|}(cn^{3/4} − 4n(1 − [F])) ^{(107)} cn^{3/4} − 4n(1 − [F]). (110)

For large enough n (depending on ε) we have

4n(1 − [F]) ≤ \frac{c}{2}n^{3/4},  (111)

since Doob’s maximal inequality (see e.g. [27]) implies that for every p > 1 we have

1 − [F] = [max_{m≤n}|k_{m}| > n^{(1+ε)/2}]≤ (\frac{p}{p − 1} )^{p} \frac{[|ε_{1} + ⋯ + ε_{n}|^{p}]}{n^{p(1+ε)/2}} ^{(♣)} (\frac{p}{p − 1} )^{p} \frac{(10np)^{p/2}}{n^{p(1+ε)/2}} = \frac{C(p)}{n^{pε/2}}, (112)

where in (♣) we used Khinchine’s inequality (see e.g. [46]) and C(p) depends only on p. Hence choosing p large enough in (112) (depending on ε) implies (111). Combining (110) and (111) implies that

[d_{≀} (Z_{n}, Z_{0})] n^{3/4},

which completes the proof of Lemma 8.2.

9 Reduction to equivariant embeddings

Recall that a Banach space (X, ∥ · ∥_{X}) is said to be finitely representable in a Banach space (Y, ∥ · ∥_{Y}) if for every ε > 0 and every finite dimensional subspace F ⊆ X there is a linear operator T : F → Y such that for every x ∈ F we have ∥x∥_{X} ≤ ∥Tx∥_{Y} ≤ (1 + ε)∥x∥_{X}.

Theorem 9.1. Let Γ be an amenable group which is generated by a finite symmetric set S ⊆ Γ. Fix p ≥ 1, two functions ω, Ω : [0, ∞) → [0, ∞) and a Banach space (X, ∥ · ∥_{X}) such that there is a mapping ψ : Γ → X which satisfies:

g, h ∈ Γ ⟹ ω (d_{Γ}(g, h))≤ ∥ψ(g) − ψ(h)∥_{X} ≤ Ω (d_{Γ}(g, h)).  (113)

Then there exists a Banach space Y which is finitely representable in ℓ_{p}(X) and an equivariant mapping Ψ : Γ → Y such that

g, h ∈ Γ ⟹ ω (d_{Γ}(g, h))≤ ∥Ψ(g) − Ψ(h)∥ _{Y} ≤ Ω (d_{Γ}(g, h)).  (114)

Moreover, if X = L_{p}(μ) for some measure μ then Y can be taken to be isometric to L_{p}.

Note that as a special case of Theorem 9.1 we conclude that for every p ≥ 1 if Γ is an amenable group then α_{p}^{∗}(Γ) = α_{p}^{#}(Γ).

In what follows given a Banach space X we denote by Isom(X) the group of all linear isometric automorphims of X. We shall require the following lemma in the proof of Theorem 9.1:

Lemma 9.2. Fix p ∈ [1, ∞). Let G be a finitely generated group and (Ω, F , μ) be a measure space (thus Ω is a set, F is a σ algebra, and μ is a measure on F). Assume that π_{0} : G → Isom(L_{p}(μ, F)) is a homomorphism and that f_{0} ∈ Z^{1}(G, π_{0}) a 1-cocycle. Then there exists a homomorphism π : G → Isom(L_{p}) and a 1-cocycle f ∈ Z^{1}(G, π) such that ∥f (x)∥_{L_{p}} = ∥f_{0}(x)∥_{L_{p}(μ,F)} for all x ∈ G.

Proof. Given A ⊆ L_{p}(μ, F) we denote as usual the smallest sub-σ algebra of F with respect to which all the elements of A are measurable by σ(A). Define inductively a sequence {F_{n}}_{n=1}^{∞} of sub-σ algebras of F and two sequences {U_{n}}_{n=1}^{∞}, {V_{n}}_{n=1}^{∞} of linear subspaces of L_{p}(μ, F) as follows:

U_{1} = span (⋃_{x∈G}π_{0}(x)f_{0}(G)), F_{1} σ (U_{1}), V_{1} = L_{p}(μ, F_{1}),

and inductively

U_{n+1} span (⋃_{x∈G}π_{0}(x)V_{n}), F_{n+1} σ(U_{n+1}), V_{n+1} = L_{p}(μ, F_{n+1}).

By construction for each n ∈ we have U_{n} ⊆ V_{n} ⊆ U_{n+1}, the measure space (Ω, F_{n}, μ) is separable (since G is countable) and F_{n+1} ⊇ F_{n}. Let F_{∞} be the σ-algebra generated by ⋃ _{n=1}^{∞} F_{n}. Note that for every ε > 0 and every A ∈ F_{∞} there is some n ∈ and B ∈ F_{n} such that μ(A△B) ≤ ε (this is because the set of all such A ∈ F forms a σ algebra, and therefore contains F_{∞} ). By considering approximations by simple functions we deduce that

L_{p}(μ, F_{∞} ) = \overline{⋃_{n=1}^{∞} V_{n}},  (115)

where the closure is taken in L_{p}(μ, F). We claim that for each x ∈ G we have π_{0}(x) ∈ Isom(L_{p}(μ, F_{∞} )). Indeed, by construction π_{0}(x)U_{n} = U_{n} for all n ∈ , and therefore V_{n} ⊆ π_{0}(x)V_{n+1} ⊆ V_{n+2}, which implies that π_{0}(x)L_{p}(μ, F_{∞} ) = L_{p}(μ, F_{∞} ), as required. Note also that f (G) ⊆ L_{p}(μ, F_{∞} ).

Since L_{p}(μ, F_{∞} ) is separable it is isometric to one of the spaces:

L_{p}, ℓ_{p}, , {ℓ_{p}^{n}}_{n=1}^{∞} , L_{p} ⊕ ℓ_{p}, {L_{p} ⊕ ℓ_{p}^{n}}_{n=1}^{∞} ,  (116)

where the direct sums in (116) are ℓ_{p} direct sums (see [60]). In what follows we will slightly abuse notation by saying that L_{p}(μ, F_{∞} ) is equal to one of the spaces listed in (116). The standard fact (116) follows from decomposing the measure μ _{F_{∞}} into a non-atomic part and a purely atomic part, and noting that the purely atomic part can contain at most countably many atoms while the non-atomic part is isomorphic to [0, 1] (equipped with the Lebesgue measure) by Lebesgue’s isomorphism theorem (see [34]).

If L_{p}(μ, F_{∞} ) = L_{p} then we are done, since we can take π = π_{0} _{L_{p}(μ,F_{∞} )}, so assume that L_{p}(μ, F_{∞} ) is not isometric to L_{p}. We may therefore also assume that p 2. If L_{p}(μ, F_{∞} ) = ℓ_{p} then by Lamperti’s theorem [41] (see also Chapter 3 in [30]) for every x ∈ G, since π_{0}(x) is a linear isometric automorphism of ℓ_{p} (and p 2) we have π_{0}(x)e_{i} = θ_{i}^{x}e_{τ^{x}(i)} for all i ∈ , where {e_{i}}_{i=1}^{∞} is the standard coordinate basis of ℓ_{p}, the function τ^{x} : → is one-to-one and onto and |θ^{x}| ≡ 1. Define π(x) ∈ Isom(L_{p})and f : G → L_{p} by setting for h ∈ L_{p} and t ∈ [2^{−i}, 2^{−i+1} ],

π(x)h(t) θ_{i}^{x}h (2^{i−τ^{x}(i)}t) and f (x)(t) = 2^{i/p}⟨f_{0}(x), e_{i}⟩.

It is immediate to check that π, f satisfy the assertion of Lemma 9.2.

It remains to deal with the case L_{p}(μ, F_{∞} ) = L_{p} ⊕ ℓ_{p}(S) where S is a nonempty set which is finite or countable. In this case we use Lamperti’s theorem once more to deduce that for each x ∈ G the linear isometric automorphism π_{0}(x) maps disjoint functions to disjoint functions, and therefore it maps indicators of atoms to indicators of atoms. Hence π_{0}(x)L_{p} = L_{p} and π_{0}(x)ℓ_{p}(S) = ℓ_{p}(S). Now, as above π_{0}(x) _{ℓ_{p}(S)} must correspond (up to changes of sign) to a permutation of the coordinates. Hence, denoting the projection from L_{p} ⊕ ℓ_{p}(S) onto L_{p} by Q, the same reasoning as above shows that there exists a homomorphism π′: G → L_{p} and f′ ∈ Z^{1}(G, π′) such that for all x ∈ G we have ∥f′(x)∥_{L_{p}} = ∥f_{0}(x) − Qf_{0}(x)∥_{ℓ_{p}(S)}. It follows that if we define π(x) ∈ Isom(L_{p} ⊕ L_{p}) by π(x) = π_{0}(x) _{L_{p}} ⊕π′and f : G → L_{p} ⊕ L_{p} by f (x) = (Qf) ⊕ f′ then (using the fact that L_{p} ⊕ L_{p} is isometric to L_{p}) the assertion of Lemma 9.2 follows in this case as well.

Proof of Theorem 9.1. Let {F_{n}}_{n=0}^{∞} be a Følner sequence for Γ and let 𝒰 be a free ultrafilter on . Define ℳ : ℓ_{∞} (Γ) → by

ℳ (f) = lim_{𝒰} \frac{1}{|F_{n}|} ∑_{x∈F_{n}}f (x).  (117)

It follows immediately from the Følner condition that ℳ is an invariant mean on Γ, i.e., a linear functional ℳ : ℓ_{∞} (Γ) → which maps the constant 1 function to 1, assigns non-negative values to non-negative functions and ℳ (R_{y}f) = ℳ (f) for every y ∈ Γ, where R_{y}f (x) = f (xy) (we refer to [58] for proofs and more information on this topic). Define a semi-norm ∥·∥_{ℳ ,p} on ℓ_{∞} (Γ, X) (the space of all X-valued bounded functions on Γ) by:

f ∈ ℓ_{∞} (Γ, X) ⟹ ∥f ∥_{ℳ ,p} (ℳ (∥f ∥_{X}^{p})) ^{1/p}.

This is indeed a semi-norm since invariant means satisfy Hölder’s inequality (see for example Lemma 2 on page 119 of Section III.3 in [26]). Hence if we let W = {f ∈ ℓ_{∞} (Γ, X) : ∥f ∥_{ℳ ,p} = 0} then W is a linear subspace and Y_{0} ℓ_{∞} (Γ, X)/W is a normed space. Let Y be the completion of Y_{0}.

By a slight abuse of notation we denote for y ∈ Γ and f ∈ ℓ_{∞} (Γ, X), R_{y}(f + W) R_{y}f + W, which is a well defined linear isometric automorphism of Y_{0} since ∥ · ∥_{ℳ ,p} is R_{y}-invariant. Moreover R is an action of Γ on Y_{0} by linear isometric automorphisms, and it therefore extends to such an action on Y as well.

Note that by virtue of the upper bound in (113) for every g, x ∈ Γ we have ∥ψ(xg) − ψ(x)∥_{X} ≤ Ω (d_{Γ}(g, e_{Γ})). Thus R_{g}ψ − ψ ∈ ℓ_{∞} (Γ, X) and we can define Ψ(g) ∈ Y by Ψ(g) = (R_{g}ψ − ψ) + W. Then Ψ ∈ Z^{1}(Γ, R). Moreover Ψ(e_{Γ}) = 0 and for every g_{1}, g_{2} ∈ Γ we have

∥Ψ(g_{1}) − Ψ(g_{2})∥ _{Y} = (ℳ (∥R_{g_{1}}ψ − R_{g_{2}}ψ∥_{X}^{p})) ^{1/p} ∈^{(113)} [ω (d_{Γ} (g_{1}, g_{2})), Ω (d_{Γ} (g_{1}, g_{2}))] .

This establishes (114), so it remains to prove the required properties of Y, i.e., that it is finitely representable in ℓ_{p}(X) and that it is an L_{p}(ν) space if X is an L_{p}(μ) space.

Up to this point we did not use the fact that ℳ was constructed as an ultralimit of averages along Følner sets as in (117) and we could have taken ℳ to be any invariant mean on Γ. But now we will use the special structure of ℳ to relate the space Y to a certain ultraproduct of Banach spaces. We do not know whether the properties required of Y hold true for general invariant means on Γ. We did not investigate this question since it is irrelevant for our purposes.

For each n ≥ 0 let X_{n} be the Banach space X^{F_{n}} equipped with the norm:

ψ : F_{n} → X ⟹ ∥ψ∥_{X_{n}} = (\frac{1}{|F_{n}|} ∑_{h∈F_{n}}∥ψ(h)∥_{X}^{p})^{1/p}.

Let X̃ be the ultraproduct (∏ _{n=0}^{∞} X_{n})_{𝒰} . We briefly recall the definition of X̃ for the sake of completeness (see [20, 21, 36] for more details and complete proofs of the ensuing claims). Let Z be the space (∏ _{n=0}^{∞} X_{n})_{∞} , i.e., the space of all sequences x = (x_{0}, x_{1}, x_{2}, …) where x_{n} ∈ X_{n} for each n and ∥x∥_{Z} sup_{n≥0} ∥x_{n}∥_{X_{n}} < ∞. Let N ⊆ Z be the subspace consisting of sequences (x_{n})_{n=0}^{∞} for which lim_{𝒰} ∥x_{n}∥_{X_{n}} = 0. Then N is a closed subspace of Z and X̃is the quotient space Z/N, equipped with the usual quotient norm. We shall denote an element of X̃, which is an equivalence class of elements in Z, by [x_{n}]_{n=0}^{∞}. The norm on X̃ is given by the concrete formula ∥[x_{n}]_{n=0}^{∞} ∥X̃ = lim_{𝒰} ∥x_{n}∥_{X_{n}}.

Since by construction each of the spaces X_{n} embeds isometrically into ℓ_{p}(X), by classical ulraproduct theory (see [36]) X̃ is finitely representable in ℓ_{p}(X). Moreover, if X = L_{p}(μ) for some measure μ then, as shown in [20, 21, 36], X̃ = L_{p}(τ) for some measure τ.

Define T : Y_{0} → X̃ by T(f + W) = [f _{F_{n}}]_{n=0}^{∞}. Then by construction (and the definition of W) T is well defined and is an isometric embedding of Y_{0} into X̃. Hence also Y embeds isometrically into X̃, and for ease of notation we will identify Y with \overline{T(Y_{0})}⊆ X̃. It follows in particular that Y is finitely representable in ℓ_{p}(X).

It remains to show that if X = L_{p}(μ) then Y = L_{p}(ν) for some measure ν since once this is achieved we can apply Lemma 9.2 in order to replace Y by L_{p}. We know that in this case X̃ = L_{p}(τ) but we need to recall the lattice structure on X̃ in order to proceed (since we do not know whether the action of Γ on Y extends to an action of Γ on X̃ by isometric linear automorphisms). Since each X_{n} is of the form L_{p}(μ_{n}) for some measure μ_{n}, the ultraproduct X̃ has a Banach lattice structure whose positive cone is {[x_{n}]_{n=0}^{∞} : x_{n} ≥ 0 ∀n} and [x_{n}]_{n=0}^{∞} ∧ [y_{n}]_{n=0}^{∞} = [x_{n} ∧ y_{n}]_{n=0}^{∞}, [x_{n}]_{n=0}^{∞} ∨ [y_{n}]_{n=0}^{∞} = [x_{n} ∨ y_{n}]_{n=0}^{∞} (all of this is discussed in detail in [36]). The explicit embedding of Y_{0} into X̃ ensures that x ∧ y, x ∨ y ∈ Y_{0} for all x, y ∈ Y_{0}. Moreover

if x, y ∈ Y_{0} are disjoint, i.e., |x| ∧ |y| = 0, then ∥x + y∥X̃ = (∥x∥p ; X̃ + ∥y∥p ; X̃)^{1/p}. These identities pass to the

closure Y of Y_{0} (since, for example, we know that X̃ = L_{p}(τ) and therefore convergence in X̃implies almost everywhere convergence along a subsequence). This shows that the Banach space Y is an abstract L_{p} space, and therefore by Kakutani’s representation theorem [39] (see also the presentation in [43]) Y = L_{p}(ν) for some measure ν.

10 Open problems

We list below several of the many interesting open questions related to the computation of compression exponents.

Question 10.1. Does C_{2} ≀ ^{2} admit a bi-Lipschitz embedding into L_{1}?

The significance of Question 10.1 was explained in the introduction. Since we know that α_{1}^{∗} (C_{2} ≀ ^{2}) = 1 the following question is more general then 10.1:

Question 10.2. For which finitely generated groups G and p ≥ 1 is α_{p}^{∗}(G) attained?

Somewhat less ambitiously than Question 10.2 one might ask for meaningful conditions on G which imply that α_{p}^{∗}(G) is attained. As explained in Remark 3.2, this holds true if p > 1 and G = C_{2} ≀H where H is a finitely generated group with super-linear polynomial growth which admits a bi-Lipschitz embedding into L_{p}. In particular this holds true for G = C_{2} ≀ ^{2} and p > 1. Note that not every group of polynomial growth H admits a bi-Lipschitz embedding into L_{1}, as shown by Cheeger and Kleiner [17] when H is the discrete Heisenberg group, i.e. the group of 3 × 3 matrices generated by the following symmetric set S ⊆ GL_{3}( ) and equipped with the associated word metric:

S = \{(\begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix}1 & −1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix}1 & 0 & −1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ), (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & 0 & 1 \end{matrix} )\}.

Similarly to Question 7.1 in [47] one might ask the following question:

Question 10.3. Is it true that for every finitely generated amenable group G and every p ∈ [1, 2] we have α_{p}^{∗}(G) = \frac{1}{pβ_{p}^{∗}(G)}?

It was shown in [3] the for every α ∈ [0, 1] there exists a finitely generated group G such that α_{2}^{∗}(G) = α. Since there are only countably many finitely presented groups the set

Ω_{p}^{∗} {α_{p}^{∗}(G) : G finitely presented} ⊆ [0, 1]

is at most countable for every p ∈ [1, ∞) (though it seems to be unknown whether or not it is infinite). One can similarly define the set Ω_{p}^{#} of possible equivariant compression exponents of finitely presented groups. Several restrictions on the relations between these sets follow from the following inequalities which hold for every finitely generated group G: for every p ≥ 1 we have α_{p}^{∗}(G) ≥ α_{2}^{∗}(G) since L_{2} embeds isometrically into L_{p} (see e.g. [60]). Similarly Lemma 2.3 in [47] states that α_{p}^{#}(G) ≥ α_{2}^{#}(G). Since L_{q} embeds isometrically into L_{p} for 1 ≤ p ≤ q ≤ 2 (see [59]) we also know that in this case α_{p}^{∗}(G) ≥ α_{q}^{∗}(G). For every 1 ≤ p ≤ q the metric space (L_{p}, ∥x − y∥_{p}^{p/q})embeds isometrically into L_{q} (for 1 ≤ p ≤ q ≤ 2 this follows from [13, 59] and for the remaining range this is proved in Remark 5.10 of [45]). Hence if p ∈ [1, 2] and p ≤ q then α_{q}^{∗}(G) ≥ max\{\frac{p}{q}, \frac{p}{2}\}· α_{p}^{∗}(G) and if 2 ≤ p ≤ q then α_{q}^{∗}(G) ≥ \frac{p}{q}α_{p}^{∗}(G).

Question 10.4. Evaluate the (at most countable) sets Ω_{p}^{∗}, Ω_{p}^{#}. Is Ω_{p}^{∗} finite or infinite? How do the sets Ω_{p}^{∗}, Ω_{p}^{#} vary with p? Is it true that Ω_{p}^{∗} = Ω_{p}^{#}?

In this paper we computed α_{p}^{∗}(( ≀ )_{0}, d_{≀} ). Note that the metric on the zero section ( ≀ )_{0} is not equivalent to a geodesic metric. This fact makes it meaningful to consider embeddings of (( ≀ )_{0}, d_{≀} ) into L_{p} which are not necessarily Lipschitz, leading to the following question:

Question 10.5. For every α_{1} > 0 evaluate the supremum over α_{2} ≥ 0 such that there exists an embedding f : ( ≀ )_{0} → L_{p} which satisfies

x, y ∈ ( ≀ )_{0} ⟹ cd_{≀} (x, y)^{α_{2}} ≤ ∥f (x) − f (y)∥_{p} ≤ d_{≀} (x, y)^{α_{1}},

for some constant c.

We believe that the methods of the present paper can be used to answer Question 10.5 at least for some additional values of α_{1} (we dealt here only with α_{1} = 1), but we did not pursue this research direction.

Question 10.6. The present paper contributes methods for evaluating compression exponents of wreath products G ≀H in terms of the compression exponents of G and H. This continues the lines of research that originated in [4] and continued in [31, 57, 54, 7, 47, 22]. It would be of great interest (and probably quite challenging) to design such methods for more general semi-direct products G H.

In Theorem 3.1 we computed α_{p}^{∗}(C_{2} ≀H) when H has polynomial growth. It seems likely that our methods yield non-trivial compression bounds also when H has intermediate growth. But, it would be of great interest to design methods which deal with the case when H has exponential growth. A simple example of this type is the group C_{2} ≀(C_{2} ≀ ), for which we do not even know whether the Hilbert compression exponent is positive.

Question 10.7. In our definition of L_{p} compression we considered embeddings into L_{p} because it contains isometrically all separable L_{p}(μ) spaces. Nevertheless, the embeddings that we construct take values in the sequence space ℓ_{p}. Does there exist a finitely generated group G for which α_{p}^{∗}(G) α_{ℓ_{p}}^{∗}(G)? Is the ℓ_{p} compression exponent of a net in L_{p} equal to 1? Note that for p 2 the function space L_{p} does not admit a bi-Lipschitz embedding into the sequence space ℓ_{p}—this follows via a differentiation argument (see [11]) from the corresponding statement for linear isomorphic embeddings (see [52]).

The subtlety between embeddings into L_{p} and embeddings into ℓ_{p} which is highlighted in Question 10.7 was pointed out to us by Marc Bourdon.

Subsequent developments

Since the posting of this article, several interesting results were posted on problems that were discussed here. In the breakthrough result [23], de Cornulier, Stalder and Valette proved that if G and H have the Haagerup property then so does G ≀H. In [42], Li proved that for p ∈ [1, 2], if α_{p}^{∗}(G) > 0 and α_{p}^{∗}(H) > 0 then also α_{p}^{∗}(G ≀H) > 0. In [6], Austin constructed an example of a finitely generated amenable group G such that α_{p}^{∗}(G) = 0 for all p ∈ [1, ∞).

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] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an appendix on the life and work of Paul Erdős.

[3] G. Arzhantseva, C. Drutu, and M. Sapir. Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. J. Reine Angew. Math., 633:213–235, 2009.

[4] 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.

[5] P. Assouad. Plongements Lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

[6] T. Austin. A finitely generated amenable group with very poor compression into Lebesgue spaces. Preprint available at http://arxiv.org/abs/0909.2047, 2009.

[7] T. Austin, A. Naor, and Y. Peres. The wreath product of with has Hilbert compression exponent \frac{2}{3}. Proc. Amer. Math. Soc., 137(1):85–90, 2009.

[8] T. Austin, A. Naor, and A. Valette. The Euclidean distortion of the lamplighter group. Preprint, 2007. To appear in Disc. Comput. Geom.

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

[10] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[11] 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.

[12] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

[13] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Fonctions de type positif sur les espaces L^{p}. C. R. Acad. Sci. Paris, 261:2153–2156, 1965.

[14] N. Brodskiy and D. Sonkin. Compression of uniform embeddings into Hilbert space. Topology Appl., 155(7):725–732, 2008.

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

[16] J. Cheeger. Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal., 9(3):428–517, 1999.

[17] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. Preprint, 2006. To appear in Ann. Math.

[18] P.-A. Cherix, M. Cowling, P. Jolissaint, P. Julg, and A. Valette. Groups with the Haagerup property, volume 197 of Progress in Mathematics. Birkhäuser Verlag, Basel, 2001. Gromov’s a-T-menability.

[19] T. H. Colding and W. P. Minicozzi, II. Liouville theorems for harmonic sections and applications. Comm. Pure Appl. Math., 51(2):113–138, 1998.

[20] D. Dacunha-Castelle and J.-L. Krivine. Ultraproduits d’espaces d’Orlicz et applications géométriques. C. R. Acad. Sci. Paris Sér. A-B, 271:A987–A989, 1970.

[21] D. Dacunha-Castelle and J. L. Krivine. Applications des ultraproduits à l’étude des espaces et des algèbres de Banach. Studia Math., 41:315–334, 1972.

[22] Y. de Cornulier, Y. Stalder, and A. Valette. Proper actions of lamplighter groups associated with free groups. C. R. Acad. Sci. Paris, 346(3-4):173–176, 2008.

[23] Y. de Cornulier, Y. Stalder, and A. Valette. Proper actions of wreath products and generalizations.

Preprint available at http://arxiv.org/abs/0905.3960v1, 2009.

[24] Y. de Cornulier, R. Tessera, and A. Valette. Isometric group actions on Hilbert spaces: growth of cocycles. Geom. Funct. Anal., 17(3):770–792, 2007.

[25] P. de la Harpe and A. Valette. La propriété (T) de Kazhdan pour les groupes localement compacts (avec un appendice de Marc Burger). Astérisque, (175):158, 1989. With an appendix by M. Burger.

[26] N. Dunford and J. T. Schwartz. Linear operators. Part I. Wiley Classics Library. John Wiley & Sons Inc., New York, 1988. General theory, With the assistance of William G. Bade and Robert G. Bartle, Reprint of the 1958 original, A Wiley-Interscience Publication.

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

[28] A. G. Èrschler. 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.

[29] W. Feller. An introduction to probability theory and its applications. Vol. II. John Wiley & Sons Inc., New York, 1966.

[30] R. J. Fleming and J. E. Jamison. Isometries on Banach spaces: function spaces, volume 129 of Chapman & Hall/CRC Monographs and Surveys in Pure and Applied Mathematics. Chapman & Hall/CRC, Boca Raton, FL, 2003.

[31] Ś. R. Gal. Asymptotic dimension and uniform embeddings. Groups Geom. Dyn., 2(1):63–84, 2008.

[32] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1):73–146, 2003.

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

[34] P. R. Halmos. Measure Theory. D. Van Nostrand Company, Inc., New York, N. Y., 1950.

[35] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[36] S. Heinrich. Ultraproducts in Banach space theory. J. Reine Angew. Math., 313:72–104, 1980.

[37] I. A. Ibragimov and Y. V. Linnik. Independent and stationary sequences of random variables. Wolters-Noordhoff Publishing, Groningen, 1971. With a supplementary chapter by I. A. Ibragimov and V. V. Petrov, Translation from the Russian edited by J. F. C. Kingman.

[38] P. W. Jones. Rectifiable sets and the traveling salesman problem. Invent. Math., 102(1):1–15, 1990.

[39] S. Kakutani. Concrete representation of abstract (L)-spaces and the mean ergodic theorem. Ann. of Math. (2), 42:523–537, 1941.

[40] D. A. Každan. On the connection of the dual space of a group with the structure of its closed subgroups. Funkcional. Anal. i Priložen., 1:71–74, 1967.

[41] J. Lamperti. On the isometries of certain function-spaces. Pacific J. Math., 8:459–466, 1958.

[42] S. Li.  Compression bounds for wreath products.  Preprint available at

    http://arxiv.org/abs/0907.5017, 2009.

[43] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

[44] N. Linial, A. Magen, and A. Naor. Girth and Euclidean distortion. Geom. Funct. Anal., 12(2):380–394, 2002.

[45] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[46] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[47] A. Naor and Y. Peres. Embeddings of discrete groups and the speed of random walks. Int. Math. Res. Not., 2008. Article ID rnn076, 34 pages, doi:10.1093/imrn/rnn076.

[48] 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.

[49] A. Naor and T. Tao. Random martingales and the Hardy-Littlewood maximal inequality. Preprint, 2007.

[50] K. Okikiolu. Characterization of subsets of rectifiable curves in R^{n}. J. London Math. Soc. (2), 46(2):336–348, 1992.

[51] R. Paley and A. Zygmund. A note on analytic functions in the unit circle. Proc. Camb. Phil. Soc., 28:266–272, 1932.

[52] A. Pelczyński. Projections in certain Banach spaces. Studia Math., 19:209–228, 1960.

[53] R. Schul. Analyst’s traveling salesman theorems. A survey. In In the tradition of Ahlfors-Bers. IV, volume 432 of Contemp. Math., pages 209–220. Amer. Math. Soc., Providence, RI, 2007.

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

[55] J. M. Steele. Probability theory and combinatorial optimization, volume 69 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.

[56] M. Stoll. On the asymptotics of the growth of 2-step nilpotent groups. J. London Math. Soc. (2), 58(1):38–48, 1998.

[57] R. Tessera. Asymptotic isoperimetry on groups and uniform embeddings into Banach spaces. To appear in Comment. Math. Helv., preprint vailable at http://arxiv.org/abs/math/0603138, 2006.

[58] S. Wagon. The Banach-Tarski paradox. Cambridge University Press, Cambridge, 1993. With a foreword by Jan Mycielski, Corrected reprint of the 1985 original.

[59] 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.

[60] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.