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.