Embeddings of discrete groups and the speed of random walks

Assaf Naor, Yuval Peres

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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[dG(Wt,e)] ≥ ctβ, where {Wt}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 = Lp, 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 (1) := and (k+1) := (k) then α*((k)) = 1/2-21-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 C2 Cn embed into L1 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.

Original languageEnglish (US)
Article numberrnn076
JournalInternational Mathematics Research Notices
Issue number1
StatePublished - 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Embeddings of discrete groups and the speed of random walks'. Together they form a unique fingerprint.

Cite this