Embeddings of discrete groups and the speed of random walks

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