Notes of Romain Tessera’s Rennes lecture nr 2

Our main concern: let {X} be a bounded degree graph which does not coarsely embed into Hilbert space. Does this imply that {X} weakly contains an expander ? I will show that the answer is no.

1. A step towards a positive answer

Theorem 1 Let {(G_n,S_n)} be a sequence of finite Cayley graphs, {|S_n|=k}. The following are equivalent.

  1. {Cay(G_n,S_n)} does not coarsely embed in Hilbert space.
  2. There are probability measures {\mu_n} on {G_n\times G_n} such that
    1. {\mu_n\{(g,g')\,;\,d(g,g')\geq r_n\}} is bounded away from 0.
    2. Poincaré inequality holds,

      \displaystyle  \begin{array}{rcl}  \sum_{x,\,y\in G_n}|f(x)-f(y)|^2\mu_n(x,y)\leq C\frac{1}{|G_n|}\sum_{x\sim y\in G_n}|f(x)-f(y)|^2. \end{array}

The proof is by Hahn-Banach.

Question (James Lee). Can we take for {\mu_n} the normalized counting measure on {A_n\times A_n} for some subset {A_n\subset G_n} ?

This would put us very close to getting an expander in {G_n}. I will show that the answer is again no. The counterexample relies on relative property (T).

2. Relative property (T)

Definition 2 Let {G} be a finitely generated group. Let {H} be an infinite subgroup of {G}. We say that the pair {(G,H)} has relative property (T) if, for every affine isometric action of {G} on a Hilbert space, the orbits of {H} are bounded.

There is again a formulation in terms of 1-cocycles: such cocycles should be bounded along {H}.

Proposition 3 Suppose that the pair {(G,H)} has relative property (T). Let {G_n} be a sequence of finite quotients of {G}. Then there is {C>0} such that

\displaystyle  \begin{array}{rcl}  \sum_{x,\,y\in G_n}|f(x)-f(y)|^2\mu_n(x,y)\leq C\frac{1}{|G_n|}\sum_{x\sim y\in G_n}|f(x)-f(y)|^2. \end{array}

with {\mu_n} the uniform measure on the set of pairs {(x,xh)}, {h\in H}.

Clearly, this implies non embeddability into Hilbert space, but for a substantially different reason than expansion.

3. A counterexample

From now on, joint work with Goulnara Arzhantseva.

3.1. First attempt

Use {G={\mathbb Z}^2 \times Sl(2,{\mathbb Z})}, {H={\mathbb Z}^2}. This is known to have relative property (T) (Kazhdan). Take {G_n=({\mathbb Z}/n{\mathbb Z})^2 \times Sl(2,{\mathbb Z}/n{\mathbb Z})} ? Unfortunately, {Cay(Sl(2,{\mathbb Z}/n{\mathbb Z}),S)} is an expander.

3.2. Successful attempt

Replace {Sl(2,{\mathbb Z}/n{\mathbb Z})} with a sequence {T_n} of finite groups mapping onto them, but which coarsely embed into Hilbert space.

Let {n=2^k}. Let {J_k\subset Sl(2,{\mathbb Z}/n{\mathbb Z})} the index 3 subgroup generated by matrices

\displaystyle  \begin{array}{rcl}  \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix},\quad \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix},\quad \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}. \end{array}

It has order {2^{3k-1}}.

For an arbitrary group {G}, consider the following characteristic subgroups {\Gamma_0(G)=G}, {\Gamma_{k+1}(G)=} subgroup of {\Gamma_k(G)} generated by squares.

We define {H_n=F_3/\Gamma_n(F_3)}. One easily checks that {H_n} is a finite 2-group.

Lemma 4 Let {G} be a finite 3-generated group. If {|G|=2^n}, {\Gamma_n(G)=1}, therefore there is an epimorphism {H_n\rightarrow G}.

Corollary 5 There is an epimorphism {H_{3k-1}\rightarrow J_k}, mapping the standard generators to the 3 matrices above.

Theorem 6 (Arzhantseva-Guentner-Spakula 2012) The sequence {(H_n)} embeds uniformly into Hilbert space.

The interest of these examples is that the embedding does not arise from Yu’s property (A). Locally, {H_n} looks more and more like a tree. The embedding arises from a wall-space structure. The first one {H_1=({\mathbb Z}/2{\mathbb Z})^3} is a cube, and this continues.

3.3. Absence of weakly embedded expanders

Remember that {G_n} the semi-direct product {({\mathbb Z}/2^k{\mathbb Z})\times H_{3k-1}}, where each factor coarsely embeds in Hilbert space. This suffices to prove that {G_n} does not weakly contain an expander. Indeed, if there was one, compose with projection to {H_{3k-1}}. A subset {A_n} representing a positive proportion of points would be mapped to a point in {H_{3k-1}}. Thus this subset is mapped to {{\mathbb Z}/2^k{\mathbb Z}}, and therefore to Hilbert space again.

Lemma 7 Let {X_n} be an expander, let {A_n\subset X_n}, {|A_n|\geq c|X_n|}. Then, for all 1-Lipschitz maps of {A_n} to Hilbert space,

\displaystyle  \begin{array}{rcl}  \frac{1}{|A_n|^2}\sum_{x,\,y\in A_n\times A_n}|f(x)-f(y)|^2 \end{array}

stays bounded.

Indeed, use the Poincaré inequality in {X_n}. Given a function {f:A_n\rightarrow\mathcal{H}}, define {\tilde{f}:X_n\rightarrow\mathcal{H}} by {\tilde{f}=f} on {A_n} and {\tilde{f}(x)=f(z_x)} where {z_x} is the point of {A_n} closest to {x}. Then

\displaystyle  \begin{array}{rcl}  \frac{1}{|A_n|^2}\sum_{x,\,y\in A_n\times A_n}|\tilde{f}(x)-\tilde{f}(y)|^2 &\leq&\frac{1}{|X_n|^2}\sum_{x,\,y\in X_n\times X_n}|\tilde{f}(x)-\tilde{f}(y)|^2\\ &\leq&C\frac{1}{|X_n|}\sum_{x\sim y\in X_n}|\tilde{f}(x)-\tilde{f}(y)|^2\\ &\leq&C\frac{1}{|X_n|}(\sum_{x\sim y\in A_n}|\tilde{f}(x)-\tilde{f}(y)|^2\\ &&+\sum_{x\sim y\in B_1}|\tilde{f}(x)-\tilde{f}(y)|^2+\sum_{x\sim y\in B_2}|\tilde{f}(x)-\tilde{f}(y)|^2\cdots), \end{array}

where {B_i} is the set of points at distance {i} from {A_n}. Using the isoperimetric inequality in {X_n}, one shows that {|B_i|} decays exponentially. This leads to the required upper bound.


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 Workshop lecture 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