Notes of Valette’s lecture nr 1

My new title is


Embeddings into Hilbert spaces, and {C^*}-algebras

The leading idea is that {C^*}-algebras provide a useful tool in the study of purely metric problems. We shall not follow the history which went in the opposite direction: a topological problem (Novikov conjecture) was cast in a {C^*}-algebraic framework (Baum-Connes conjecture), and it was discovered that purely metric issues were relevant for the {C^*}-algebra problem.

Plan of the lectures


  1. Groups as metric spaces
  2. Coarse embeddings into Hilbert spaces
  3. Novikov conjecture
  4. Yu’s Property (A)
  5. {C^*}-algebras associated with groups and metric spaces
  6. {C^*}-algebraic characterizations of Property (A)


1. Groups as metric spaces


Topology urges us to understand finitely presented groups, i.e. fundamental groups of compact manifolds or simplicial complexes. To a large extent, the notions we shall encounter only depend on metrics carried by these groups.


1.1. Word length


{G} is a finitely generated group, {S} a finite symmetric generating set, {1\notin S}. For {w\in G} define its word length

\displaystyle  \begin{array}{rcl}  |w|_s =\min\{n\,|\,\exists s_1,\ldots, s_n \in S \textrm{ such that }w=s_1 s_2 \cdots s_n\}. \end{array}

Then {d_{S}(w,w')=|w^{-1}w'|} defines a left invariant distance on {G}.

Example 1 {G={\mathbb Z}^n} free abelian group, {S=\{(0,\ldots,\pm 1,\ldots 0)\}} ({|S|=2n}).

Then distance {d_{S}} coincides with {\ell^1}-norm.

Example 2 {G={\mathbb F}_n} free group on {n} generators {a_1 ,\ldots, a_n}, {S=\{a_{i}^{\pm}\}} ({|S|=2n}).

Say a word is reduced on the alphabet {a_1 ,\ldots, a_n} if obvious simplifications {a_{i}a_{i}^{-1}} or {a_{i}^{-1}a_{i}} never occur. Then {{\mathbb F}_n} is the set of reduced words, with group law given by concatenation followed by reduction. By definition, {|w|_s} is the number of letters needed to spell out {w}.

Example 3 {G=Heis({\mathbb Z})} discrete Heisenberg group, {S=\{x^{\pm},y^{\pm},z^{\pm}\}} ({|S|=6}).

{Heis({\mathbb Z})} is the set of upper triangular integer matrices with {1}‘s on the diagonal,

\displaystyle  \begin{array}{rcl}  x=\begin{pmatrix} 1&1&0 \\ 0&1&0 \\ 0&0&1 \end{pmatrix},\quad y=\begin{pmatrix} 1&0&0 \\ 0&1&1 \\ 0&0&1 \end{pmatrix},\quad z=\begin{pmatrix} 1&0&1 \\ 0&1&0 \\ 0&0&1 \end{pmatrix}. \end{array}

Every group element can be uniquely written in the form {g=x^{m}y ^{n}z^{p}}, {(m,n,p)\in{\mathbb Z}^3}. Nevertheless, as a group and as a metric space, {Heis({\mathbb Z})} is very different from {{\mathbb Z}^3}. For instance, {|z^{m^{2}}|\leq 4m}, since {z^{m^{2}}=[x^{m},y^{m}]}.

Exercise. Check that an other choice {T} of finite generating system leads to an equivalent metric, i.e. there exists a constant {C=C(S,T)} such that

\displaystyle  \begin{array}{rcl}  \frac{1}{C}\,d_T \leq d_S \leq C\,d_T . \end{array}


1.2. Cayley graphs


The mysterious distance {d_S} can be viewed as the length metric induced by a graph having {G} as a vertex set.

Definition 1 Let {G} be a group, {S} a finite symmetric subset. The Cayley graph {\mathcal{G}(G,S)} is the undirected graph with set of vertices {G}, set of edges

\displaystyle  \begin{array}{rcl}  E=\{\{x,xs\}\,;\, g\in G,\,s\in S\}. \end{array}

In other words, two vertices {x}, {y\in G} are adjacent iff {y^{-1}x\in S}.

Proposition 2 1. {\mathcal{G}(G,S)} is vertex-transitive. In fact, {G} acts simply transitively on vertices (on the left).

2. {\mathcal{G}(G,S)} is {|S|}-regular (every vertex has {|S|} neighbours).

3. {\mathcal{G}(G,S)} is connected iff {S} generates {G}.


Proof: A vertex {g} is connected to the unit element {1} iff {g} is a product of finitely many elements of {S}. \Box

From now on, we assume that {S} is generating. Then {d_S (g,h)} equals the distance between {g} and {h} as vertices in {\mathcal{G}(G,S)}.

Example 4 {G={\mathbb Z}}, {S=\{\pm 1\}}. Then {\mathcal{G}(G,S)} is the infinite simplicial line.


Example 5 {G={\mathbb Z}^2}, {S=\{(\pm 1,0),(0,\pm 1)\}}. Then {\mathcal{G}(G,S)} is the infinite square grid in the plane.


Example 6 {G=D_{\infty}}, the infinite dihedral group, i.e. the group of isometries of the simplicial line. Let {S=\{s,t\}} where {s(x)=-x} is the reflection across {0} and {t(x)=1-x} is the reflection across {1/2}. Then {\mathcal{G}(G,S)} is isomorphic to the simplicial line.

In a row, group elements are {\ldots,tsts,tst,ts,t,1,s,st,sts,stst,\ldots}.

Example 7 {G={\mathbb F}_n}, {S=\{a_{i}^{\pm}\}}. Then {\mathcal{G}(G,S)} is the {2n}-regular tree.


1.3. Amenability for graphs


Here is our first example of a property of groups which only depends on its metric. We first define it for graphs.

Let {X=(V,E)} be a locally finite, connected graph. For {A} a finite set of vertices, let

\displaystyle  \begin{array}{rcl}  \partial A=\{\textrm{edges connecting }A\textrm{ to }V\setminus A\}. \end{array}

Definition 3 The Cheeger or isoperimetric constant of {X} is

\displaystyle  \begin{array}{rcl}  h(X)=\inf\{\frac{|\partial A|}{|A|}\,;\,|A|\leq\frac{1}{2}|V|\}. \end{array}

{h(X)} measures the quality of {X} viewed as a communication network. {h(X)>\epsilon} means that every finite set of emitters can transmit information to a proportion of channels at least {\epsilon}.

Definition 4 Say that {X} is amenable if either {X} is finite or {h(X)=0}.


Example 8 {X={\mathbb Z}^d} (grid in Euclidean {d}-space). Then {h(X)=0}.

Indeed, let {A} be a subcube of size {R}. Then {|A|=R^d}, {\partial A=2d\,R^{d-1}}.

Example 9 {X=T_k}, the {k}-regular tree. Then {h(X)\geq k-2}.


Proof: First assume that {A} is a finite subtree. Let us prove by induction on {|A|} that {|\partial A|\geq (k-2)|A|}. This is obvious when {|A|=1}. Induction step: add an edge {xy} to {A} to get {A'}, with {x\in A}, {y\notin A}. Then {|\partial A'|=|\partial A|-1+(k-1)\geq(k-2)(|A|+1)=(k-2)|A'|}.

If {A} is an arbitrary finite subset of {T_k}, let {A_1 ,\ldots,A_d} be its connected components. Then

\displaystyle  \begin{array}{rcl}  |\partial A|&=&\sum_{i=1}^{d}|\partial A_i|\\ &\geq&(k-2)\sum_{i=1}^{d}|A_i|\\ &=&(k-2)|A|. \end{array}


Exercise. Show that {h(T_{k})=k-2}.

Solution. Let {S(r)} denote the sphere of integer radius {r} and {A(r)} be the ball of radius {r}. Then {|S(r)|=k(k-1)^{r-1}}, {|\partial A(r)|=|S(r+1)|=k(k-1)^r} and

\displaystyle  \begin{array}{rcl}  |A(r)|=1+\sum_{i=1}^{r}|S(i)|=1+k\frac{(k-1)^r -1}{k-2}, \end{array}

thus {(k-2)|A(r)|=k(k-1)^r-2=|\partial A(r)|-2}. Letting {r} tend to {+\infty} implies that {h(T_{k})\leq k-2}.


1.4. Amenability for groups


Definition 5 (F\o lner, 1950’s). Let {G} be a finitely generated group. Say {G} is amenable if {\forall\epsilon>0}, {\forall F\subset G} finite, there exists a finite subset {A\in G} such that

\displaystyle  \begin{array}{rcl}  \frac{|AF\Delta A|}{|A|}<\epsilon. \end{array}

Such sets are called {(F,\epsilon)}-F\o lner sets.

Theorem 6 Assume {G} is finitely generated. Then the following are equivalent.

i) {G} is amenable.

ii) Every Cayley graph of {G} is amenable.

iii) Some Cayley graph of {G} is amenable.


Proof: ii){\Rightarrow}iii) is clear.

i){\Rightarrow}ii). Let {\mathcal{G}(G,S)} be a Cayley graph. Take {\epsilon>0} and a F\o lner set for {S,\epsilon}. Then

\displaystyle  \begin{array}{rcl}  |AS\Delta A|=|\{\textrm{vertices at distance }1\textrm{ from }A\textrm{ in }\mathcal{G}(G,S)\}. \end{array}


\displaystyle  \begin{array}{rcl}  \frac{|\partial A|}{|A|}\leq|S|\frac{|AS\delta A|}{|A|}<\epsilon|S|, \end{array}

thus {h(\mathcal{G}(G,S))=0}.

iii){\Rightarrow}i). Assume {\mathcal{G}(G,S)} is an amenable graph. Fix a finite set {F\subset G} and {\epsilon>0}. Find {A\subset G} such that {\frac{|\partial A|}{|A|}<\frac{\epsilon}{n|F|}}, where {n=\max\{|w|_S \,;\,w\in F\}}. For {w\in F}, write {w=s_1 \ldots s_n}, {s_i \in S\cup\{1\}}. Then

\displaystyle  \begin{array}{rcl}  \frac{|Aw\Delta A|}{|A|} &\leq&\frac{|Aw\Delta As_2 \cdots s_n|}{|A|}+\cdots+\frac{|Aw\Delta As_n|}{|A|}\\ &\leq&\epsilon, \end{array}

showing that {G} is an amenable group. \Box

Example 10 {{\mathbb Z}^d}, {D_{\infty}} are amenable, {{\mathbb F}_n} is not.


2. Coarse embeddings


Definition 7 Let {(X,d_X)} and {(Y,d_Y)} be two metric spaces, and {f:X\rightarrow Y} a map. Say that {f} is a coarse embedding if there exist control functions {\rho_-} and {\rho_+ :{\mathbb R}_+ \rightarrow{\mathbb R}} tending to infinity at {+\infty} such that {\forall x}, {x'\in X},

\displaystyle  \begin{array}{rcl}  \rho_- (d_X (x,x'))\leq d_Y (f(x),f(x'))\leq \rho_+ (d_X (x,x')). \end{array}


Special choices for {\rho_{\pm}} lead to subclasses,

  1. quasi-isometric embeddings if {\rho_{\pm}(t)=C_{\pm}t+D_{\pm}},
  2. bi-Lipschitz embeddings if {\rho_{\pm}(t)=C_{\pm}t},
  3. isometric embeddings if {\rho_{\pm}(t)=t}.

Example 11 Different choices of finite generating system lead to a bi-Lipschitz embedding {(G,d_S)\rightarrow (G,d_T)}.


Example 12 Inclusion {({\mathbb Z}^d ,d_S)\rightarrow ({\mathbb R}^d , d_{Eucl})} is a bi-Lipschitz embedding.


Example 13 The (discontinuous, non injective) integer part map {{\mathbb R}\rightarrow {\mathbb Z}}, {x\mapsto\lfloor x\rfloor} is a quasi-isometric embedding.


Example 14 Let {X} be a metric space. Let {f:X\rightarrow\ell^{\infty}(X)}, {x\mapsto f_x} where {f_x (x')=d(x,x')-d(x_0 ,x')}. This is an isometric embedding.


Example 15 Let {X} be a tree. There is a coarse embedding of {X} into the Banach space {\ell^{p}(E)}. When {p=1}, it is an isometric embedding.


Proof: Fix a vertex {x_0}. For {x\in V}, define {f_x} as the characteristic function of the set of edges of the unique path from {x_0} to {x}. Then {f_x -f_{x'}} is supported on the unique path from {x} to {x'}, so

\displaystyle  \begin{array}{rcl}  \parallel f_x -f_{x'}\parallel_{p}=d_X (x,x')^{1/p}. \end{array}


Exercise. Let {X} be a connected graph, viewed as a metric space. Let {f:X\rightarrow Y} be a coarse embedding. Show that the control function {\rho_+} can be chosen to be linear.

Solution. Let {x}, {x'} be vertices of {X}, {k=d_X (x,x')}. Then there exists a sequence of vertices {x=x_0 ,\ldots,x_k =x'} such that {d(x_{i-1},x_{i})=1}. By the triangle inequality

\displaystyle  \begin{array}{rcl}  d_Y (f(x),f(x'))&\leq&\sum_{i=1}^{k}d_Y (f(x_{i-1}),f(x_{i}))\\ &\leq& C\,k =C\,d_X (x,x'), \end{array}

where {C=\rho_+ (1)}.

The following Proposition appears in Bekka-Chérix-Valette, [BCV].

Proposition 8 Let {G} be a finitely generated amenable group. Then {G} admits an equivariant coarse embedding into {\ell^p}, {1\leq p<+\infty}.

Equivariant means with respect to some isometric action of {G} on {\ell^p}.

Proof: Let {F_n} be an increasing sequence of finite subset of {G} whose union is {G}. Since {G} is ameanable, it admits a F\o lner sequence {A_n} relative to {F_n} and {\epsilon=2^{-n}}, i.e.

\displaystyle  \begin{array}{rcl}  \frac{|F_n A_n \Delta A_n|}{|A_n|}<2^{-n}. \end{array}

Let us embed {G} in {\ell^{p}(G\times{\mathbb N})}. Let {\xi_n} be the characteristic function of {A_n}, normalized to that its {\ell^p}-norm be equal to {1}. Let {\lambda} be the left regular representation of {G} on {\ell^p (G)}, i.e. {g\in G} acts on an {\ell^p} function {\xi} by {\lambda(g)\xi (h)=\xi(gh)}. Define {f:G\rightarrow \ell^p (G\times{\mathbb N})},

\displaystyle  \begin{array}{rcl}  g\mapsto \bigoplus_{n=1}^{\infty}n(\lambda(g)\xi_n -\xi_n). \end{array}

Given {g\in G}, there exists {n} such that {g\in F_n}. Then

\displaystyle  \begin{array}{rcl}  \parallel \lambda(g)\xi_n -\xi_n\parallel_{p}^{p}=\frac{|gA_n \Delta A_n|}{|A_n|}\leq 2^{-n}, \end{array}

so the series defining {f} converges, since {n\ll 2^{-n}}.

Define an affine isometric action of {G} on {\ell^p (G\times{\mathbb N})} as follows.

\displaystyle  \begin{array}{rcl}  \alpha(g)=\left(\bigoplus_{n=1}^{\infty}\lambda(g)\right)v+f(g). \end{array}

By construction, the action does not fix the origin {O}, and by triangle inequality,

\displaystyle  \begin{array}{rcl}  \parallel f(g)\parallel_{p}\leq\parallel \alpha(g)O-O\parallel_{p}\leq C\,|g|_S. \end{array}

To get a lower bound, set

\displaystyle  \begin{array}{rcl}  \rho_- (t)=\min\{\parallel f(g)\parallel_{p}\,;\,g\in G,\,|g|_{S}\}. \end{array}

This tends to infinity, since for every {R>0}, the set {\{g\in G\,;\,\parallel f(g)\parallel_{p}\leq R\}} is finite. \Box




[BCV] Bekka, Mohammed; Chérix, Pierre-Alain; Valette, Alain, Proper affine isometric actions of amenable groups. Novikov conjectures, index theorems and rigidity, Vol. 2 (Oberwolfach, 1993), 1–4, London Math. Soc. Lecture Note Ser., 227, Cambridge Univ. Press, Cambridge, 1995.



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 and tagged . 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s