Notes of Tim Austin’s course

Embedding groups into Banach spaces

1. Context

1.1. Groups as metric spaces

Regard finitely generated groups {\Gamma} as geometric objects

  • either by putting some geometry on {\Gamma} itself (e.g. word metrics);
  • or ask about its actions on geometric spaces.

Word metric: form the Cayley graph {Cay(\Gamma,S)} and restrict its length metric to {\Gamma}. Example: For {\Gamma={\mathbb Z}^d} with obvious generating set {S=\{\pm e_i\}}, get {\ell_1} metric.

Two finite generating sets give equivalent word metrics. Thus {\Gamma} is a metric space only up to bi-Lipschitz equivalence.


  1. How does this metric space relate to the algebra of {\Gamma}.
  2. How understand these as metric spaces. For instance, try to compare groups to Banach spaces.

More specifically, how close can word metric on {\Gamma} be from metrics induced by maps to Banach spaces ?

Example 1 Every separable metric space embeds isometrically into {L_{\infty}}.

So we should restrict to subclasses of Banach spaces. Here are popular choices of targets.

  • Hilbert spaces (hardest of all).
  • {L_p}-spaces, {p<\infty}.
  • All uniformly convex spaces.

1.2. Uniform embeddings

Definition 1 A uniform embedding of {\Gamma} to a Banach space {X} is a map {f:\Gamma\rightarrow X} such that there exist two positive functions {\xi_{\pm}} on {{\mathbb R}_+} such that

  • {\xi_{\pm}(r)} tends to infinity with {r}.
  • For all {g}, {h\in \Gamma}, {\xi_{-}(d(g,h))\leq |f(g)-f(h)|\leq\xi_{+}(d(g,h))}.

This is a very weak notion, but

Theorem 2 (Gromov) There exist groups that do not embed uniformly into {L_2}.

Theorem 3 (Yu) Groups that embed uniformly into {L_2} satisfy Baum-Connes conjecture.

1.3. Bi-Lipschitz embeddings

Definition 4 A bi-Lipschitz embedding is such that we can take {\xi_{\pm}(r)=C_{\pm}r}.

Example 2 {{\mathbb Z}^d}, virtually {{\mathbb Z}^d}.

Are there any other ? Polynomial growth groups don’t. Exponential growth groups don’t (use Markov convexity). Open for intermediate growth groups.

1.4. Compression

To quantify where we lie in between, Guentner and Kaminker introduced compression.

Definition 5 The compression exponent {\alpha_X^* (\Gamma)} is the supremum ofnthose {\alpha\geq 0} such that there exists {f:\Gamma\rightarrow X} with {\xi_+ (r)=C_+ r} and {\xi_- (r)\geq c_- r^{\alpha}}.

Abbreviate {\alpha_{L_p}^*} by {\alpha_{p}^*}.

Theorem 6 (Guentner, Kaminker) If {\alpha_{L_2}^* (\Gamma)>\frac{1}{2}}, then {\Gamma} is exact, meaning that, among {C^*}-algebras, minimal tensor product with {C_r^* (\Gamma)} preserves exact sequences.

Example 3

  • Virtually abelian groups have {\alpha_{p}^* =1}.
  • Virtually nilpotent groups have {\alpha_{p}^* =1}.
  • Hyperbolic groups have {\alpha_{p}^* =1} (Brodskiy-Soukin).
  • {{\mathbb Z}\wr{\mathbb Z}} has {\alpha_{2}^* =\frac{2}{3}}.
  • Among all finitely generated groups, one can have any values for {\alpha_{p}^*} in {[0,1]} (Arzhantseva, Drutu, Sapir).

1.5. Random walk bound

This is a general method for getting upper bounds.

Theorem 7 (Austin, Naor, Peres) Suppose {(X_t)} is a simple random walk on an amenable group, and that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(d(X_0 ,X_t))\geq \Omega(t^{\beta}). \end{array}

Then {\alpha_2^* (\Gamma)\leq\frac{1}{2\beta}}.

(Naor, Peres): {\alpha_p^* (\Gamma)\leq\frac{1}{p^{*}\beta}}, where {p^* =2} if {p\geq 2}, {p^* =p} if {1\leq p \leq 2}.

This cannot give an upper bound less than {\frac{1}{2}} in Hilbert space.

2. Zero compression

Are there amenable groups that do worst ? Answer is yes.

Theorem 8 (Austin 2008) There exists a finitely generated amenable group (actually {4}-step solvable) such that {\alpha_p^* (\Gamma)=0} for all finite {p}.

The rest of the course will be devoted to proving this theorem. The groups are kind of ad hoc.

2.1. Strategy

The method is to embed a sequence of bad finite subsets.

Definition 9 Given a finite metric space {Y} and an map {Y\rightarrow X}, its distorsion is

\displaystyle  \begin{array}{rcl}  dist(f)=Lip(f)Lip(f^{-1}). \end{array}

The distorsion of {Y} into {X} is

\displaystyle  \begin{array}{rcl}  C_X (Y)=\inf_{f:Y\rightarrow X}dist(f). \end{array}

There are finite spaces which have large {L_p}-distorsion. Having them bi-Lipschitz embedded in {\Gamma} gives upper bounds on compression.

Lemma 10 Suppose there exist finite metric spaces {Y_n} and maps {\phi_n :Y_n \rightarrow\Gamma} and constants {L>1}, {r_n} bounded away from {0} such that

  • {diameter(Y_,)} tends to infinity.
  • {\frac{1}{L}r_n d(y,y')\leq d(\phi_n (y),\phi_n (y'))\leq Lr_n d(y,y')} for all {y}, {y'\in Y_n}.
  • {r_n \leq \Omega(diameter(Y_n)^{\epsilon})} for all {\epsilon>0}.
  • {c_{\Gamma}(Y_n)\geq\Omega(diameter(Y_n)^{\eta})} for some fixed {\eta}.

Then {\alpha_p^* (\Gamma)\leq 1-\eta}.

We loosely call {r_n} “expansion ratios”.

Proof: Let {f:\Gamma\rightarrow L_p} be {1}-Lipschitz and have {\xi_- (t)\geq C\,t^\alpha}. Then{f\circ\phi_n} has distorsion {\leq } and {\geq \Omega(diameter(Y_n)^{\eta})}. This implies {\alpha\leq 1-\eta}. \Box

2.2. Suitable finite metric spaces

One possibility (used by Gromov) would be expanders. We will use something similar, but with unbounded degree.

Consider hypercube {{\mathbb Z}_2^m} with Hamming metric. Fact: {c_2 ({\mathbb Z}_2^m)\sim\sqrt{m}}. It turns out that quotients of the hypercube are even worse.

Theorem 11 (Khot, Naor 2004) Consider a vector subspace {C\in{\mathbb Z}_2^m} of dimension {\Omega(m)} and distance {\Omega(m)} (i.e. an error-correcting code). Then, in the quotient metric,

\displaystyle  \begin{array}{rcl}  c_p ({\mathbb Z}_2^m/C^{\bot})\geq/Omega_p (m), \quad \forall p<\infty. \end{array}

Proof: First take {p=1}, use isometric embedding of {(L_1 ,\sqrt{|\cdot|_{L_1}})} to {L_2}, then use Fourier analysis. To finish, use Matousek’s interpolation lemma. \Box

Reason for optimism: These are groups.

Reason for concern: Number of generators tend to infinity.

Resolve second issue by sending these groups into non finitely generated subgroups of a finitely generated group, e.g. Lamplighter group {{\mathbb Z}_2 \wr H}.

2.3. Lamplighter group

{{\mathbb Z}_2 \wr H} is the semi-direct product of {H} and the {H}-indexed direct sum of copies of {{\mathbb Z}_2}, where {H} acts by permuting coordinates. Elements of {{\mathbb Z}_2 \wr H} are configurations of a lamps assignment (only finitely many lamps are on) {\omega\in{\mathbb Z}_2^{\oplus H}} and a lamplighter location {h\in H}.

Fix a generating set {S_H} of {H}. A generating set for {{\mathbb Z}_2 \wr H} is the set of instructions to the lamplighter: either switch the lamp at the current location on or off, or move one step away. In other words,

\displaystyle  \begin{array}{rcl}  S=\{(0,s)\,\;\,s\in S_H\}\cup\{(\pm\delta_{e_H},e_H)\}. \end{array}

Observe that {{\mathbb Z}_2^{\oplus H}} is an infinite generated subgroup.

2.4. The traveling salesman metric

The word metric on {{\mathbb Z}_2 \wr H} behave as follows. To go from {(\omega,h)} to {(\omega',h')}, one needs visit all locations in the support of {\omega\omega'}, so

\displaystyle  \begin{array}{rcl}  d((\omega,h),(\omega',h'))\geq |\mathrm{support}(\omega)\Delta\mathrm{support}(\omega')|+L, \end{array}

where {L} is the minimal length of a path in {Cay(H,S_H)} joining {h} to {h'} and visiting all sites {\mathrm{support}(\omega)\Delta\mathrm{support}(\omega')}.

Definition 12 The traveling salesman metric on {{\mathbb Z}_2^{\oplus H}}, {TS_H (\omega,\omega')}, is the minimal length of a loop in {Cay(H,S_H)} based at {e_H} and visiting all sites {\mathrm{support}(\omega)\Delta\mathrm{support}(\omega')}.

In particular,

\displaystyle  \begin{array}{rcl}  d((\omega,e_H),(\omega',e_H))\sim TS_H (\omega,\omega') . \end{array}

2.5. First step in the construction

Let us start with easy lemmas.

Lemma 13 If {H} has exponential growth, there exists {M>1} and a sequence of radii {r_j} tending to infinity such that

\displaystyle  \begin{array}{rcl}  |B(e_H ,3r_j)|\geq M^{r_j}|B(e_H ,r_j)|. \end{array}

For this {M} and these {r_j}, there are finite subsets {I_j \in H} such that

  • Pairwise distances within {I_j \cup\{e_H\}} belong to {[r_j ,10r_j]}.
  • {|I_j|:=d_j \geq M^{r_j}}.

Now identify {{\mathbb Z}_2^{d_j}} with {{\mathbb Z}_2^{I_j}\subset {\mathbb Z}_2^{\oplus H}}. The diameter is {d_j}, exponentially larger than {r_j}, and the traveling salesman distance is of the order of {r_j |\mathrm{support}(\omega)\Delta\mathrm{support}(\omega')|}, therefore the distorsion is {\geq\Omega(d_{j}^{1/2}}. This shows that

\displaystyle  \begin{array}{rcl}  \alpha_2^* ({\mathbb Z}_2 \wr H)\leq\frac{1}{2}. \end{array}

2.6. Passing to a quotient

To improve this bound, we replace {{\mathbb Z}_2^{d_j}} with a quotient. This requires quotienting {{\mathbb Z}_2^{\oplus H}} by a vectorsubspace {V} that contains some dual code {C_j^{\bot}}. For the semi-direct product to be defined, we need {V} to be {H}-invariant.

Proposition 14 There exists an amenable, exponential growth group {H} and a {H}-invariant subspace {V\subset {\mathbb Z}_2^{\oplus H}} such that for some sequence {d_n} tending to infinity, {\phi_n :{\mathbb Z}_2^{d_n}/C_n^{\bot}\rightarrow{\mathbb Z}_2^{\oplus H}/V \times H} is bi-Lipschitz, with expansion ratio {r_n \leq O(\log d_n)}.

The difficulty is making sure that the quotient map is still bi-Lipschitz.

What can go wrong ?

  • Set {V_n =} sum of translates of {C_n^{\bot}}. It will be much bigger than {C_n^{\bot}} alone.
  • Set {V=\bigoplus_n V_n}. It will be much bigger than {V_n} alone.

We need to ensure that given {u}, {v\in{\mathbb Z}_2^{d_n}} and {w_{h,m}} in {h}-translate of {C_m^{\bot}}, there is a single {w'_n \in C_n^{\bot}} such that

\displaystyle  \begin{array}{rcl}  d_{{\mathbb Z}_2 \wr H}(u,v+\sum_{h,m}w_{h,m})\geq \mathrm{const.}d(u,v+w'_{n}). \end{array}

2.7. Finding suitable group {H} and subspace {V}

To give ourselves room to move, let {H={\mathbb Z}_k \wr G}, some {k\geq 1}, where {G} is itself amenable with exponential growth.

View {{\mathbb Z}_k \wr G} as a disjoint union of {{\mathbb Z}_k^{\oplus G}}. Then as a vectorspace,

\displaystyle  \begin{array}{rcl}  {\mathbb Z}_2^{{\mathbb Z}_k \wr G}=\bigoplus_{g\in G}{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}. \end{array}

We will choose maps {\phi_n :{\mathbb Z}_2^{d_n}\rightarrow {\mathbb Z}_2^{{\mathbb Z}_k \wr G}} to actually land in {{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}} viewed as the {e_G} component of {\bigoplus_{g}{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}}. Then {V} will itself be of the form

\displaystyle  \begin{array}{rcl}  \bigoplus_{g}U_g \subset \bigoplus_{g}{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}, \end{array}

where {U_g}‘s are all related by the {G} action.

To choose {\phi_n}, observe that {{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}} does not see the {G}-action, we need only take care of the {{\mathbb Z}_k^{\oplus G}}-action.

2.8. New notational convention

From now on, elements of either {{\mathbb Z}_2^{d_n}} or, e.g., {{\mathbb Z}_k^{\oplus G}} will be called tuples and written {\mathbf{u}=(u_i)_{i=1,\ldots,d_n}}.

Elements of {{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}} will be called functions (on tuples) or finite subsets of tuples, and written {W:{\mathbb Z}_k^{\oplus G}\rightarrow{\mathbb Z}_2}.

We will obtain {\phi_n} in two steps,

  1. Find {\xi_n :{\mathbb Z}_2^{d_n}\rightarrow{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{I_n}}} where {I_n \subset G} is a well separated set with inter-point distances {r_n} as given by Lemma 13.
  2. Choose homomorphism {\kappa_n :{\mathbb Z}_2^{\oplus {\mathbb Z}_k^{I_n}} \rightarrow {\mathbb Z}_2^{\oplus {\mathbb Z}_k^{\oplus G}}}.

Then {\phi_n =\kappa_n \circ \xi_n}.

This actually breaks the difficulty.

2.9. Construction of {\xi_n}

We want {\xi_n :{\mathbb Z}_2^{d_n}\rightarrow {\mathbb Z}_2^{\oplus {\mathbb Z}_k^{I_n}}}. Let

\displaystyle  \begin{array}{rcl}  B_n =\{(\delta_y ,e_G)\,;\, y\in I_n\}\in {\mathbb Z}_k^{\oplus G}\times\{e_g\} \subset {\mathbb Z}_k \wr G. \end{array}

Observe that {d_{{\mathbb Z}_k \wr G}((\delta_y ,e_G),(\delta_{y'} ,e_G))} is of the order of {r_n} for distinct {y}, {y'\in I_n}. So {B_n} is also a set of {d_n} points, all roughly {r_n} apart (we have jumped one level up). Now pick an arbitrary isomorphism {\xi_n : {\mathbb Z}_2^{d_n}\rightarrow {\mathbb Z}_2^{B_n}\subset {\mathbb Z}_2^{\oplus {\mathbb Z}_k^{I_n}}}. It will be important to know that this already helps with translation invariance. I.e. see what translation invariance remains at the level of the finite set {{\mathbb Z}_2^{{\mathbb Z}_k^{I_n}}}.

Lemma 15 Let {k} be even. There is a {{\mathbb Z}_k^{I_n}}-invariant subgroup {E_n \subset {\mathbb Z}_2^{\oplus {\mathbb Z}_k^{I_n}}} such that

  • {\xi_n (C_n^{\bot})\subset E_n}.
  • {E_n \cap \xi_n ({\mathbb Z}_2^{d_n})=\xi_n (C_n^{\bot}}.
  • In fact, the quotient map {\bar{\xi}_n :{\mathbb Z}_2^{d_n}/C_n^{\bot}\rightarrow{\mathbb Z}_2^{{\mathbb Z}_k^{I_n}}/E_n} is bi-Lipschitz from quotient Hamming metric to quotient of traveling salesman distance.

Proof: In fact, we choose translation invariant {D_n \subset {\mathbb Z}_2^{{\mathbb Z}_k^{I_n}}} and let {E_n =D_n^{\bot}}. To do this, given {\mathbf{a}\in{\mathbb Z}_2^{d_n}}, define {L_{\mathbf{a}}\in{\mathbb Z}_2^{{\mathbb Z}_k^{I_n}}} as follows,

\displaystyle  \begin{array}{rcl}  L_{\mathbf{a}}(\mathbf{v})=\sum_{} \end{array}


\displaystyle  \begin{array}{rcl}  D_n =\{\eta +L_{\mathbf{a}}\,;\,\eta\in{\mathbb Z}_2 ,\,\mathbf{a}\in C_n\}. \end{array}

Adding {\eta} is necessary for translation invariance, since translating {L_{\mathbf{a}}} by {\mathbf{w}} adds up {\langle \mathbf{a},\mathbf{w} \rangle}.

One checks that if {U=\xi_n (\mathbf{a})} belongs to {D_n^{\bot}}, then {U\in\xi_n (C_n^{\bot})}. \Box

2.10. Construction of {\kappa_n}

First attempt: Assume {I_1 ,\ldots,I_n} are disjoint. Given {W\in {\mathbb Z}_2^{{\mathbb Z}_k^{I_n}}}, let

\displaystyle  \begin{array}{rcl}  \kappa_n (W)(\mathbf{w})=\delta_{\mathbf{0}}(\mathbf{w}_{|G\setminus (I_1 \cup\cdots\cup I_n)})W(\mathbf{w}_{|I_n}. \end{array}

For this choice, one cannot rule out conflicts between translates. One needs an extra trick to prevent translates from {\kappa_n (D_{n'}^{\bot})} {n'\leq n}, filling up something that is constant on cylinders like {\{\mathbf{w}_{|G\setminus (I_1 \cup\cdots\cup I_n)}\}\times{\mathbb Z}_k^{I_1 \cup\cdots\cup I_n}}.

To repair this, we choose a sequence {z_i \in G} such that {r_1 \ll d(e,z_1)\ll r_2 \ll d(e,z_2)\ll \cdots} and find some function {Z:{\mathbb Z}_k \rightarrow{\mathbb Z}_2} such that the constant function {1} is not a sum of translates of {A}. E.g. {A=1_{\{0,1,3,4\}}} if {k=6}. Set

\displaystyle  \begin{array}{rcl}  \kappa_n (W)(\mathbf{w})=\delta_{\mathbf{0}}(\mathbf{w}_{|G\setminus (I_1 \cup\cdots\cup I_n)})W(\mathbf{w}_{|I_n})A(w_{z_n}). \end{array}

This now prevents cancellation.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s