Notes of Alain Valette’s lecture nr 3

In the first and second lectures, I defined coarse embeddings and gave examples. Now I give more details.


1. Examples of spaces not embeddable into Hilbert spaces


Definition 1 Let {X_n} be a family of finite collected, {k}-regular graphs, with increasing size. Say that {X_n} is a family of expanders if there exists {\epsilon>0} such that edge expansion {h(X_n)\geq\epsilon} for all {n}.


Such things exist. Pinsker obtained them using the probabilistic method in 1967. In 1973, Margulis gave explicit examples [M].

Theorem 2 (Margulis) Fix {d\geq 3}. Let {S} be a finite symmetric generating set of {SL_d ({\mathbb Z})}. Then the family of Cayley graphs {\mathcal{G}(SL_d ({\mathbb Z}/n{\mathbb Z}),S)}, {n\geq 1}, is a family of expanders.


Cheeger-Buser’s inequality relates edge-expansion to the first non-zero eigenvalue of the Laplacian, denoted here by {\lambda_1} (beware this is denoted by {\lambda_2} in James Lee’s course). This gives a spectral expansion criterion.

Proposition 3 {(X_n)} is a family of expanders iff there exists {\epsilon'>0} such that {\lambda_1 (X_n) \geq \epsilon'} for all {n}.


Linial, London and Rabinovich proved in 1994 that expanders do not embed coarsely in Hilbert space, [LLR].

Theorem 4 Let {X=\coprod_{n}X_n} equipped with a metric such that different {X_n} are sufficiently far apart. Then {X} has no coarse embedding into Hilbert space.


Proof: By contradiction. Let {f:X\rightarrow H} be such an embedding. One can use {f} as a test function in the definition of {\lambda_1}. Indeed, choose a Hilbert basis, then each component of {f} can be used, and sum up. Thus

\displaystyle  \begin{array}{rcl}  \epsilon'&\leq&\lambda_1 (X_n)\\ &\leq&|V_n|\frac{\sum_{x\sim y}|f(x)-f(y)|^2}{\sum_{x\, y\in V_n}|f(x)-f(y)|^2}\\ &\leq&|V_n|\frac{1}{\sum_{x\, y\in V_n}|f(x)-f(y)|^2}\rho_+ (1)^2 |V_n||E_n| \end{array}


\displaystyle  \begin{array}{rcl}  \frac{1}{|V_n|^2}\sum_{x\, y\in V_n}|f(x)-f(y)|^2 \leq d_{max}\rho_+ (1)^2 . \end{array}

For every {K}, the number of pairs {(x,y)} with {d(x,y)\leq K} is less than {d_{max}^{K}|V_n|=O(|V_n|)}. For other pairs (the number of them is {\geq \Omega(|V_n|^2)}), {|f(x)-f(y)|^2 \geq\rho_- (K)^2}, so

\displaystyle  \begin{array}{rcl}  \frac{1}{|V_n|^2}\sum_{x\, y\in V_n}|f(x)-f(y)|^2 \geq\rho_- (K)^2 +o(1). \end{array}

If this holds for all {K}, contradiction. \Box

In 2000, Gromov sketched a construction of random groups containing a coarsely embedded family of expandres in their Cayley graphs. Such groups do not coarsely embed in Hilbert spaces.

Linial: with the new examples of expanders, could one simplify Gromov’s construction ? Answer: one needs large girth, so the Lubotzky-Phillips-Sarnak examples have to be used, [LPS].


2. The Novikov conjecture


Definition 5 The {G} be a finitely generated group. Let {M} be a closed oriented {n}-manifold with a map {f:M\rightarrow BG} (classifying space of {G}). Let {[M]} denote the homology fundamental class of {M}, let {L(M)} denote Hirzebruch’s {L}-class in cohomology. For {x\in H^{*}(BG,{\mathbb Q})} consider the higher signature

\displaystyle  \begin{array}{rcl}  \sigma_{x}(M,f)=\langle f^{*}(x)\smile L(M),[M] \rangle. \end{array}


The Novikov conjecture states that if {h:N\rightarrow M} is a homotopy equivalence of closed oriented manifolds. Then {\sigma_x (N,f\circ h)=\sigma_x (M,f)}.

In 2000, Guoliang Yu, [Y], proved

Theorem 6 (Yu) If (the Cayley graph of) a group coarsely embeds in Hilbert space, then {G} satisfies (NC).


Proof: The proof uses operator algebras.

  • To every group, one associates the reduced {C^*}-algebra {C_{r}^{*}(G)}.
  • To every discrete metric space {X}, one associates the Roe algebra {C^* (X)}.

Yu’s proof goes through two other conjectures.

  • (CBC) Coarse Baum-Connes conjecture: If {X} is a discrete metric space with bounded geometry, theb the {K}-theory of {C^* (X)} can be computed in terms of geometric data.
  • (SNC) Strong Novikov conjecture: For {G} a finitely generated group. The index map from the {K}-homology of {BG} to {K}-theory of {C_{r}^{*}(G)} is injective.

Here is some history. In 1980, Kasparov and Mishchenko proved that (SNC) implies (NC), showing that (NC) is a problem in operator algebras rather than topology. In 1991, Higson and Roe proved that if the Cayley graph of {G} satisfies (CBC), then {G} satisfies (SNC). In 2000, Yu proved that if a Cayley graph coarsely embeds in Hilbert space, then it satisfies (CDC). \Box


3. Yu’s Property (A)


3.1. Positive definite kernels


Definition 7 A kernel (i.e. a {2}-variable function) {\phi} on a set {X} is positive definite if the matrix {(\phi(x_i ,x_j))_{ij}} is positive definite for every {x_1 ,\ldots,x_k \in X}.

Equivalently: There exists a Hilbert space {H} and a map {f} from {X} to the unit sphere of {H} such that {\phi(x,y)=f(x)\cdot f(y)}.


Definition 8 Let {X} be a discrete metric space. Say {X} has Property (A) if there exists a sequence {\phi_n} of positive definite kernels such that

  • {\phi_n} is supported in a bounded neighborhood {U_{R(n)}} of the diagonal.
  • {\phi_n} tends to {1} uniformly on all {U_R}.


Proposition 9 If {G} is a finitely generated amenable group, then {G} has Property (A).


Proof: Let {B_n} be the {n}-ball centered at the origin. Pick a F\o lner set {A_n} for {B_{2n}}, i.e.

\displaystyle  \begin{array}{rcl}  \frac{|B_{2n}A_n \Delta A_n|}{|A_n|}<\frac{1}{n}. \end{array}

Let {\xi_n \in\ell^2 (G)} be the normalized characteristic function of {A_n}. Set

\displaystyle  \begin{array}{rcl}  \phi_n (g,h)&=&\lambda(g)\xi_n \cdot \lambda(h)\xi_n \\ &=&\frac{|h^{-1}gA_n \Delta A_n|}{|A_n|}. \end{array}


\displaystyle  \begin{array}{rcl}  1-\phi_n (g,h)\leq\frac{|A_{n}\Delta h^{-1}gA_n|}{|A_n|}<\frac{1}{n} \end{array}

if {h^{-1}g\in B_{2n}}, i.e. {(g,h)\in U_{2n}}. \Box

Proposition 10 Locally finite trees have Property (A).


Proof: Fix an end {\omega} of {X}. For {x\in X}, let {[x,\omega)} denote the ray from {x} to {\omega}. Define {A_{x,n}=B(x,n)\cap[x,\omega)}, so that {|A_{x,n}|=n+1}, and

\displaystyle  \begin{array}{rcl}  \phi_n (x,y)=\frac{1}{n+1}|A_{x,n}\cap A_{y,n}|. \end{array}

Since {\phi_n (x,y)=\frac{1}{\sqrt{n+1}}1_{A_{x,n}}\cdot \frac{1}{\sqrt{n+1}}1_{A_{y,n}}} in {\ell^2 (X)}, {\phi_n} is positive definite.

Fix {R>0}. If {d(x,y)\leq R}, let {z} be the median of {x}, {y} and {\omega}. Note that {d(x,y)=d(x,z)+d(z,y)}. {|A_{x,n}\cap A_{y,n}|=n-\max\{d(x,z),d(z,y)\}+1=n+1+o(n)} uniformly on {U_R}. \Box


3.2. Conditionally negative definite kernels


Definition 11 A kernel {\psi} on {X} is conditionally negative definite iff for every {x_1 ,\ldots, x_k \in X}, the matrix {(\psi(x_i ,x_j)_{ij})} is positive definite on the hyperplane {\sum_{i}\lambda_i =0}.

Equivalently: There exists a Hilbert space {H} and a map {f:X\rightarrow H} such that {\phi(x,y)=|f(x)-f(y)|^2}.


Proposition 12 (Yu) If a graph metric space has Property (A), then it is coarsely embeddable in Hilbert space.


Proof: Mimic the proof of coarse embeddability of amenable groups. Let {\phi_n} be positive definite kernels converging to {1} at exponential speed, i.e.

\displaystyle  \begin{array}{rcl}  x,\,y\in U_n \Rightarrow |1-\phi_n (x,y)|\leq 2^{-n}. \end{array}

By assumption, there is {f_n :X\rightarrow H} such that {\phi_n (x,y)=f_n (x)\cdot f_n (y)}. Then {1-\phi_n (x,y)=|f_n (x)-f_n (y)|^2}. In particular, {1-\phi_n} is conditionally negative definite. Set

\displaystyle  \begin{array}{rcl}  \psi(x,y)=\sum_{n=1}^{\infty}n(1-\phi_n (x,y)). \end{array}

This is again conditionally negative definite, so it comes from a Hilbertian embedding {f}. Let us check that {f} is a coarse embedding. Set

\displaystyle  \begin{array}{rcl}  \rho_- (t)=\inf\{\psi(x,y)^{1/2}\,;\,d(x,y)=t\}. \end{array}

This is proper. Indeed, if {\psi(x,y)\leq R}, then for {n=R+1}, {\phi_n (x,y)\geq 1-\frac{R}{n}>0}, so {(x,y)\in U_{n,R+1}}. \Box

The first examples of graphs coarsely embeddable into Hilbert space but not satisfying Property (A) are due to Piotr Nowak (2006). They do not have bounded geometry. Examples with bounded geometry have been constructed by Arzhantseva, Guentner and Spakula in 2011. Here is the construction. Start with a group {G}. The group {G^{(1)}} generated by all squares is normal. Iterate {n} times to get {G^{(n)}}. Then the example is {\coprod_{n\geq 1}\mathbb{F}_{2}/\mathbb{F}_{2}^{(n)}}. These are finite {2}-groups.

Linial: these are iterated lifts.

Property (A) fails here thanks to the

Theorem 13 (Roe) Let {G} be a finitely generated, residually finite group. Let {G_k} be decreasing normal subgroups with {\bigcap G_n =\{1\}}. The {G} is amenable iff {\coprod G/G_k} has Property (A).


Proving that the examples coarsely embed is not easy.




[LLR] Linial, Nathan; London, Eran; Rabinovich, Yuri; The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), no. 2, 215–245.

[LPS] Lubotzky, Alex; Phillips, R.; Sarnak, Peter; Ramanujan graphs. Combinatorica 8 (1988), no. 3, 261–277.

[M] Margulis, Grigorii; Explicit constructions of expanders. Problemy Pereda\v ci Informacii 9 (1973), no. 4, 71–80.

[Y] Yu, Guolian; The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space. Invent. Math. 139 (2000), no. 1, 201–240.


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