1. Markov type and compression, continued
1.1. Markov type, an example
has Markov type 2, and this is not obvious.
Let be a finite set with kernel , a stochastic matrix. It acts on functions on . Reversibility means that the corresponding operator on is self-adjoint. Its norm is . Let be an arbitrary map.
where reversibility and stochasticity have been used.
On the other hand,
Pick a normalized eigenfunction of : one sees that the wanted inequality boils down to
which holds, since all eigenfunctions of satisfy .
1.2. Proof of compression-speed inequality
Let be a F\o lner sequence, i.e. . The thickening
is again a F\o lner sequence, for every fixed . Furthermore, tends to 1 as tends to infinity.
Form a graph from by replacing every outgoing edge by a loop at the same vertex. The simple random walk on is stationary and reversible for the uniform distribution.
Let be a coarse embedding. Apply Markov type assumption first, then the coarse inequality.
since the simple random walk makes jumps of length at most 1. On the other hand, ignoring many terms
Until time , random walk on starting from is the same as random walk on starting from . So we may replace with . Pick , in order that
It costs nothing to assume that (otherwise, there is nothing to prove). Then
Taking a supremum over and over finite generating sets completes the proof.
1.3. More facts
It turns out that, pretty often, . This works for polycyclic groups (groups obtained from 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 , when does there exist a bi-Lipschitz map to ?
Conjecture (Cornulier-Tessera-Valette): if is amenable and has a bi-Lipschitz map to Hilbert space, then is virtually abelian (i.e. it has an abelian finite index subgroup).
Austin and Bartholdi-Erschler have constructed amenable groups with for all . 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 equals the Hilbertian compression of some finitely generated group , but their examples are non amenable.