## 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}$

$\Box$

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}$

So

$\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}$

$\Box$

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$

References

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