Notes of Antoine Gournay’s lecture nr 2

1. Markov type and compression, continued

1.1. Markov type, an example

{{\mathbb R}} has Markov type 2, and this is not obvious.

Let {Y} be a finite set with kernel {K}, a stochastic matrix. It acts on functions on {Y}. Reversibility means that the corresponding operator {K} on {\ell^2(Y,\pi)} is self-adjoint. Its norm is {\leq 1}. Let {f:Y\rightarrow {\mathbb R}} be an arbitrary map.

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(|f(Z_t)-f(Z_0)|^2)&=&\sum_i \mathop{\mathbb E}(|f(Z_t)-f(Z_0)|^2|Z_0=i)\pi(i)\\ &=&\sum_{i,j} |f(j)-f(i)|^2 K^t(i,j)\pi(i)\\ &=&\sum_{i,j} (f(j)^2+f(i)^2-2f(j)f(i)) K^t(i,j)\pi(i)\\ &=&\sum_{i,j} f(j)^2 K^t(i,j)\pi(i)+\sum_{i,j} f(i)^2 K^t(i,j)\pi(i)\\ &&+\sum_{i,j} -2f(j)f(i) K^t(i,j)\pi(i)\\ &=&2(\sum_{i,j} f(j)^2 K^t(i,j)\pi(i)-\sum_{i,j} -f(j)f(i) K^t(i,j)\pi(i))\\ &=&2\langle(I-K^t)f|f\rangle_\pi, \end{array}

where reversibility and stochasticity have been used.

On the other hand,

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(|f(Z_1)-f(Z_0)|^2)=2\langle(I-K)f|f\rangle_\pi/ \end{array}

Pick {f} a normalized eigenfunction of {K}: one sees that the wanted inequality boils down to

\displaystyle  \begin{array}{rcl}  \frac{1-\lambda^t}{1-\lambda}=1+\lambda+\cdots+\lambda^{t-1}\leq t, \end{array}

which holds, since all eigenfunctions of {K} satisfy {\lambda\leq 1}.

1.2. Proof of compression-speed inequality

Let {F_n\subset G} be a F\o lner sequence, i.e. {|\partial F_n|=o(|F_n|)}. The thickening

\displaystyle  \begin{array}{rcl}  A_n=\bigcup_{g\in F_n}B(g,t) \end{array}

is again a F\o lner sequence, for every fixed {t}. Furthermore, {\frac{|F_n|}{|A_n|}} tends to 1 as {n} tends to infinity.

Form a graph {X_n} from {A_n} by replacing every outgoing edge by a loop at the same vertex. The simple random walk on {X_n} is stationary and reversible for the uniform distribution.

Let {f:G\rightarrow B} be a coarse embedding. Apply Markov type assumption first, then the coarse inequality.

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(d(f(Z_t),f(Z_0))^p)&\leq& Kt\,\mathop{\mathbb E}(d(f(Z_1),f(Z_0))^p)\\ &\leq& K't\,\mathop{\mathbb E}(d(Z_1,Z_0)^p)\leq K't, \end{array}

since the simple random walk makes jumps of length at most 1. On the other hand, ignoring many terms

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(\rho_f(d(Z_t,Z_0))^p)&\geq& \frac{1}{|A_n|}\sum_{x\in F_n}\mathop{\mathbb E}(\rho_f(d(Z_t,Z_0))^p|Z_0=x). \end{array}

Until time {t}, random walk on {X_n} starting from {F_n} is the same as random walk {(W_k)} on {G} starting from {F_n}. So we may replace {Z_t} with {W_t}. Pick {\alpha_0<\alpha_B(G)}, in order that

\displaystyle  \begin{array}{rcl}  \rho_f(t)\geq c\,t^{\alpha_0}. \end{array}

It costs nothing to assume that {\alpha_0 p\geq 1} (otherwise, there is nothing to prove). Then

\displaystyle  \begin{array}{rcl}  \frac{1}{|A_n|}\sum_{x\in F_n}\mathop{\mathbb E}(\rho_f(d(Z_t,Z_0))^p|Z_0=x) &\geq&\frac{|F_n|}{|A_n|}\mathop{\mathbb E}(\rho_f(d(W_t,e))^p)\\ &\geq&c\frac{|F_n|}{|A_n|}\mathop{\mathbb E}(\rho_f(d(W_t,e))^{\alpha_0 p})\\ &\geq&c\frac{|F_n|}{|A_n|}\mathop{\mathbb E}(d(W_t,e))^{\alpha_0 p}\\ &\geq&c'\frac{|F_n|}{|A_n|}t^{\beta\alpha_0 p}. \end{array}

Taking a supremum over {\alpha_0<\alpha_B(G)} and over finite generating sets completes the proof.

1.3. More facts

It turns out that, pretty often, {p\alpha_B\beta=1}. This works for polycyclic groups (groups obtained from {{\mathbb Z}} by successive extension by cyclic groups) and more. This works for wreath products too.

1.4. Open problems

1. When does there exist a map that achieved the compression exponent ? For instance, when {\alpha=1}, when does there exist a bi-Lipschitz map to {L^p} ?

Conjecture (Cornulier-Tessera-Valette): if {G} is amenable and has a bi-Lipschitz map to Hilbert space, then {G} is virtually abelian (i.e. it has an abelian finite index subgroup).

Austin and Bartholdi-Erschler have constructed amenable groups {G} with {\alpha_{L^p}(G)=0} for all {p\geq 1}. Austin’s example is solvable of rank 4. Bartholdi-Erschler’s example has intermediate volume growth.

2. Values of Hilbertian compression

Arzhantseva-Drutu-Sapir show that every {c\in[0,1]} equals the Hilbertian compression of some finitely generated group {G}, but their examples are non amenable.


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