The wreath product of with has Hilbert compression exponent \frac{2}{3}

Tim Austin UCLA

Assaf Naor^{∗} Courant Institute

Yuval Peres^{†} Microsoft Research and UC Berkeley

Abstract

Let G be a finitely generated group, equipped with the word metric d associated with some finite set of generators. The Hilbert compression exponent of G is the supremum over all α ≥ 0 such that there exists a Lipschitz mapping f : G → L_{2} and a constant c > 0 such that for all x, y ∈ G we have ∥f (x) − f (y)∥_{2} ≥ cd(x, y)^{α}. In [2] it was shown that the Hilbert compression exponent of the wreath product ≀ is at most \frac{3}{4}, and in [12] was proved that this exponent is at least \frac{2}{3}. Here we show that \frac{2}{3} is the correct value. Our proof is based on an application of K. Ball’s notion of Markov type.

1 Introduction

Let G be a finitely generated group. Fix a finite set of generators S ⊆ G, which we will always assume to be symmetric (i.e. S^{−1} = S). Let d be the left-invariant word metric induced by S on G. The Hilbert compression exponent of G, which we denote by α^{∗}(G), is the supremum over all α ≥ 0 such that there exists a 1-Lipschitz mapping f : G → L_{2} and a constant c > 0 such that for all x, y ∈ G we have

∥f (x) − f (y)∥_{2} ≥ cd(x, y)^{α}.

Note that α^{∗}(G) does not depend on the choice of the finite set of generators S, and is thus an algebraic invariant of the group G. This notion was introduced by Guentner and Kaminker in [7] as a natural quantitative measure of Hilbert space embeddabililty in situations when bi-Lipschitz embeddings do not exist (when bi-Lipschitz embeddings do exist the natural measure would be the Euclidean distortion). More generally, the compression function of a 1-Lipschitz mapping f : G → L_{2} is defined as

ρ(t) inf_{d(x,y)≥t}∥f (x) − f (y)∥_{2}.

The mapping f is called a coarse embedding if lim_{t→∞} ρ(t) = ∞. Coarse embeddings of discrete groups have been studied extensively in recent years. The Hilbert compression exponents of various groups were investigated in [7, 2, 5, 16, 1]—we refer to these papers and the references therein for group-theoretical motivation and applications.

Consider the wreath product ≀ , i.e. the group of all pairs (f, x), where x ∈ and f : → has finite support, equipped with the group law (f, x)(g, y) (z ↦ f (z) + g(z − x), x + y). In this note we prove that α^{∗}( ≀ ) = \frac{2}{3}. The problem of computing α^{∗}( ≀ ) was raised explicitly in [2, 16, 1]. In [2] Arzhantseva, Guba and Sapir showed that α^{∗}( ≀ ) ∈ [\frac{1}{2}, \frac{3}{4}]. In [16] Tessera claimed to improve the lower bound on α^{∗}( ≀ ) to α^{∗}( ≀ ) ≥ \frac{2}{3}, and conjectured that α^{∗}( ≀ ) = \frac{2}{3}. Unfortunately, Tessera’s proof is flawed, as explained in Remark 1.4 of [12]; his method only yields the bound α^{∗}(Z ≀ Z) ≥ \frac{1}{3}. However, the inequality α^{∗}( ≀ ) ≥ \frac{2}{3} is correct, as shown by Naor and Peres in [12] using a different method. Here we obtain the matching upper bound α^{∗}( ≀ ) ≤ \frac{2}{3}. For the sake of completeness, in Remark 2.2 below we also present the embeddings of Naor and Peres [12] which establish the lower bound α^{∗}( ≀ ) ≥ \frac{2}{3}.

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

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

Our proof of the upper bound α^{∗}( ≀ ) ≤ \frac{2}{3} is a simple application of K. Ball’s notion of Markov type, a metric invariant that has found several applications in metric geometry in the past two decades—see [3, 11, 9, 4, 13, 10]. Recall that a Markov chain {Z_{t}}_{t=0}^{∞} with transition probabilities a_{ij} Pr(Z_{t+1} = j | Z_{t} = i) on the state space {1, …, n} is stationary if π_{i} Pr(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}].  (1)

The least such K is called the Markov type p constant of X, and is denoted M_{p}(X).

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

The notion of Markov type has been successfully applied to various embedding problems of finite metric spaces. In this note we observe that one can use this invariant in the context of infinite amenable groups as well. In a certain sense, our argument simply amounts to using Markov type asymptotically along neighborhoods of Følner sequences.

For the rest of the paper, Let G be an amenable group with a fixed finite symmetric set of generators S and the corresponding left-invariant word metric d. Let e denote the identity element of G, and let {W_{t}}_{t=0}^{∞} be the canonical simple random walk on the Cayley graph of G determined by S, starting at e. Our main result is:

Proposition 1.1. Assume that there exist c, δ, β > 0 such that for all t ∈ ,

Pr(d(W_{t}, e) ≥ ct^{β})≥ δ.  (2)

Let (X, d_{X}) be a metric space with Markov type p, and assume that f : G → X satisfies

ρ(d(x, y)) ≤ d_{X}(f (x), f (y)) ≤ d(x, y)  (3)

for all x, y ∈ G, where ρ : _{+} → _{+} is non-decreasing. Then for all t ∈ ,

ρ (ct^{β})≤ \frac{M_{p}(X)}{δ^{1/p}}t^{1/p}.

In particular,

α^{∗}(G) ≤ \frac{1}{2β}.

As an immediate corollary we deduce that α^{∗}( ≀ ) ≤ \frac{2}{3}. Indeed, ≀ is amenable (see for example [8, 14]), and it was shown by Revelle in [15] that ≀ has a set of generators (namely the canonical generators S = \{(1, 0), (−1, 0), (0, 1), (0, −1)\}) which satisfies the assumption of Proposition 1.1with β = \frac{3}{4} (see also [6] for the corresponding bound on the expectation of d(W_{t}, e)).

2 Proof of Proposition 1.1

Let {F_{n}}_{n=0}^{∞} be a Følner sequence for G, i.e., for every ε > 0 and any finite K ⊆ G, we have |F_{n}△(F_{n}K)| ≤ ε|F_{n}| for large enough n. Fix an integer t > 0 and denote

A_{n} ⋃_{x∈F_{n}}B(x, t) ⊇ F_{n},

where B(x, t) is the ball of radius t centered at x in the word metric determined by S.

For every ε > 0, there exists n ∈ such that

ε|F_{n}| ≥ |F_{n}△(F_{n}B(e, t))| = |A_{n} \ F_{n}| .  (4)

Let {Z_{t}}_{t=0}^{∞} be the delayed standard random walk restricted to A_{n}. In other words, Z_{0} is uniformly distributed on A_{n}, and for all j ≥ 0 and x ∈ A_{n},

Pr(Z_{j+1} = x|Z_{j} = x) = 1 − \frac{|(xS) ∩ A_{n}|}{|S|},

and if s ∈ S is such that xs ∈ A_{n} then

Pr(Z_{j+1} = xs|Z_{j} = x) = \frac{1}{|S|}.

It is straightforward to check that {Z_{t}}_{t=0}^{∞} is a stationary reversible Markov chain. Hence, using the Markov type p property of X, and the fact that f is 1-Lipschitz, we see that

[d_{X}(f (Z_{t}), f (Z_{0}))^{p}] ≤^{(1)} M_{p}(X)^{p}t [d_{X}(f (Z_{1}), f (Z_{0}))^{p}] ≤^{(3)} M_{p}(X)^{p}t [d(Z_{1}, Z_{0})^{p}] ≤ M_{p}(X)^{p}t.  (5)

Note that

[d_{X}(f (Z_{t}), f (Z_{0}))^{p}] ≥^{(3)} [ρ(d(Z_{t}, Z_{0}))^{p}] ≥ \frac{1}{|A_{n}|}∑_{x∈F_{n}} [ρ (d(Z_{t}, Z_{0}))^{p} |Z_{0} = x],  (6)

since the omitted summands corresponding to x F_{n} are nonnegative. If x ∈ F_{n} then B(x, t) ⊆ A_{n}; this implies that conditioned on the event {Z_{0} = x}, the random variable d(Z_{t}, Z_{0}) has the same distribution as the random variable d(W_{t}, e). The assumption (2) yields that

[ρ (d(W_{t}, e))^{p} ] ≥ ρ (ct^{β})^{p} · Pr(d(W_{t}, e) ≥ ct^{β})≥ ρ (ct^{β})^{p} · δ .  (7)

In conjunction with (6), this gives that

[d_{X}(f (Z_{t}), f (Z_{0}))^{p}] ≥ \frac{|F_{n}|}{|A_{n}|}· [ρ (d(W_{t}, e))^{p} ] ≥^{(7)} \frac{|F_{n}|}{|A_{n}|}· ρ (ct^{β})^{p} · δ ≥^{(4)} \frac{δ}{1 + ε} · ρ (ct^{β})^{p} .  (8)

Combining (5) and (8), and letting ε → 0, concludes the proof of Proposition 1.1.

Remark 2.1. Given two groups G and H, the wreath product G ≀H is the group of all pairs (f, x) where f : H → G has finite support (i.e. f (z) is the identity 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). Consider the iterated wreath products _{(k)}, where _{(1)} = and _{(k+1)} _{(k)} ≀ . In [15] it is shown that _{(k)} has a finite symmetric set of generators which satisfies the assumption of Proposition 1.1 with β = 1 − 2^{−k}. Thus α^{∗}( _{(k)}) ≤ \frac{1}{2−2^{1−k}} . In fact, as shown in [12], α^{∗}( _{(k)}) = \frac{1}{2−2^{1−k}} .

Remark 2.2. In [12] the lower bound α^{∗}( ≀ ) ≥ \frac{2}{3} is a particular case of a more general result. For the readers’ convenience we present the resulting embeddings in the case of the group ≀ .

In what follows and denote the corresponding inequality up to a universal constant. Fix α ∈ (0, 1/2) and let

{v_{g} : g : A → finitely supported, A ∈ { ∩ [n, ∞)}_{n∈} ∪ { ∩ (−∞, n]}_{n∈}}

be disjointly supported unit vectors in L_{2}( ). For (f, k) ∈ ≀ define a function ϕ_{α}(f, k) : → by

ϕ_{α}(f, k) ∑_{n>k}(n − k)^{α} · v_{f _{[n,∞)}} + ∑_{n<k}(k − n)^{α} · v_{f _{(−∞,n]}} .

Observe that ϕ_{α}(f, k) − ϕ_{α}(0, 0) ∈ L_{2}( ). Indeed, if f is supported on [−m, m] then

∥ϕ_{α}(f, k) − ϕ_{α}(0, 0)∥_{2}^{2} m (m^{2α} + |k|^{2α})+ ∑_{n∈} (|n|^{α} − |n − k|^{α})^{2} m (m^{2α} + |k|^{2α})+ ∑_{j=1}^{∞} \frac{k^{2}}{j^{2(1−α)}} < ∞.

We can therefore define F_{α} : ≀ → ⊕ ℓ_{2}( ) ⊕ L_{2}( ) by

F_{α}(f, k) k ⊕ f ⊕ (ϕ_{α}(f, k) − ϕ_{α}(0, 0)).

We claim that for every (f, k) ∈ ≀ we have

d_{≀} ((f, k), (0, 0))^{\frac{2α+1}{2α+2}} ∥F_{α}(f, k)∥_{2} \frac{1}{\sqrt{1 − 2α}} · d_{≀} ((f, k), (0, 0)),  (9)

Since the metric ∥F_{α}(f_{1}, k_{1}) − F_{α}(f_{2}, k_{2})∥_{2} is ≀ -invariant, and F_{α}(0, 0) = 0, the inequalities in (9) imply that ≀ has Hilbert compression exponent at least \frac{2α+1}{2α+2} . Letting α ↑ \frac{1}{2} shows that α^{∗}( ≀ ) ≥ \frac{2}{3}.

It suffices to check the upper bound in (9) (i.e. the Lipschitz condition for F_{α}) when (f, k) is one of the generators of ≀ , i.e. (f, k) = (0, 1) or (f, k) = (δ_{0}, 0). Observe that ∥F_{α}(δ_{0}, 0)∥_{2} = 1 and

∥F_{α}(0, 1)∥_{2}^{2} ∑_{n=1}^{∞} (n^{α} − (n − 1)^{α})^{2} \frac{1}{1 − 2α} ,

implying the upper bound in (9). To prove the lower bound in (9) assume that m ∈ is the minimal integer such that f is supported on [k − m, k + m]. Then,

∥F_{α}(f, k)∥_{2}^{2} k^{2} + ∑_{j=k−m}^{k+m} f (j)^{2} + ∑_{ℓ=1}^{m} ℓ^{2α} k^{2} + \frac{1}{m} (∑_{j∈} |f (j)|)^{2} + m^{2α+1}

(k + m + ∑_{j∈} |f (j)|)^{\frac{4α+2}{2α+2}} d_{≀} ((f, k), (0, 0))^{\frac{4α+2}{2α+2}} ,

where the penultimate inequality follows by considering the cases ∥f ∥_{1} ≥ m^{α+1} and ∥f ∥_{1} ≤ m^{α+1} separately.

References

[1] G. Arzhantseva, C. Drutu, and M. Sapir. Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. Preprint, 2006. Available at

http://xxx.lanl.gov/abs/math/0612378.

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

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

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

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

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

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

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

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

[10] M. Mendel and A. Naor. Some applications of Ball’s extension theorem. Proc. Amer. Math. Soc., 134(9):2577–2584 (electronic), 2006.

[11] A. Naor. A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces. Mathematika, 48(1-2):253–271 (2003), 2001.

[12] A. Naor and Y. Peres. Embeddings of discrete groups and the speed of random walks. Preprint, 2007.

Available at http://xxx.lanl.gov/abs/0708.0853.

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

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

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

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

    2006. Available at http://xxx.lanl.gov/abs/math/0603138.

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