Embedding groups into Banach spaces
1.1. Groups as metric spaces
Regard finitely generated groups as geometric objects
- either by putting some geometry on itself (e.g. word metrics);
- or ask about its actions on geometric spaces.
Word metric: form the Cayley graph and restrict its length metric to . Example: For with obvious generating set , get metric.
Two finite generating sets give equivalent word metrics. Thus is a metric space only up to bi-Lipschitz equivalence.
- How does this metric space relate to the algebra of .
- How understand these as metric spaces. For instance, try to compare groups to Banach spaces.
More specifically, how close can word metric on be from metrics induced by maps to Banach spaces ?
Example 1 Every separable metric space embeds isometrically into .
So we should restrict to subclasses of Banach spaces. Here are popular choices of targets.
- Hilbert spaces (hardest of all).
- -spaces, .
- All uniformly convex spaces.
1.2. Uniform embeddings
Definition 1 A uniform embedding of to a Banach space is a map such that there exist two positive functions on such that
- tends to infinity with .
- For all , , .
This is a very weak notion, but
Theorem 2 (Gromov) There exist groups that do not embed uniformly into .
Theorem 3 (Yu) Groups that embed uniformly into satisfy Baum-Connes conjecture.
1.3. Bi-Lipschitz embeddings
Definition 4 A bi-Lipschitz embedding is such that we can take .
Example 2 , virtually .
Are there any other ? Polynomial growth groups don’t. Exponential growth groups don’t (use Markov convexity). Open for intermediate growth groups.
To quantify where we lie in between, Guentner and Kaminker introduced compression.
Definition 5 The compression exponent is the supremum ofnthose such that there exists with and .
Abbreviate by .
Theorem 6 (Guentner, Kaminker) If , then is exact, meaning that, among -algebras, minimal tensor product with preserves exact sequences.
- Virtually abelian groups have .
- Virtually nilpotent groups have .
- Hyperbolic groups have (Brodskiy-Soukin).
- has .
- Among all finitely generated groups, one can have any values for in (Arzhantseva, Drutu, Sapir).
1.5. Random walk bound
This is a general method for getting upper bounds.
Theorem 7 (Austin, Naor, Peres) Suppose is a simple random walk on an amenable group, and that
(Naor, Peres): , where if , if .
This cannot give an upper bound less than in Hilbert space.
2. Zero compression
Are there amenable groups that do worst ? Answer is yes.
Theorem 8 (Austin 2008) There exists a finitely generated amenable group (actually -step solvable) such that for all finite .
The rest of the course will be devoted to proving this theorem. The groups are kind of ad hoc.
The method is to embed a sequence of bad finite subsets.
Definition 9 Given a finite metric space and an map , its distorsion is
The distorsion of into is
There are finite spaces which have large -distorsion. Having them bi-Lipschitz embedded in gives upper bounds on compression.
Lemma 10 Suppose there exist finite metric spaces and maps and constants , bounded away from such that
- tends to infinity.
- for all , .
- for all .
- for some fixed .
We loosely call “expansion ratios”.
Proof: Let be -Lipschitz and have . Then has distorsion and . This implies .
2.2. Suitable finite metric spaces
One possibility (used by Gromov) would be expanders. We will use something similar, but with unbounded degree.
Consider hypercube with Hamming metric. Fact: . It turns out that quotients of the hypercube are even worse.
Theorem 11 (Khot, Naor 2004) Consider a vector subspace of dimension and distance (i.e. an error-correcting code). Then, in the quotient metric,
Proof: First take , use isometric embedding of to , then use Fourier analysis. To finish, use Matousek’s interpolation lemma.
Reason for optimism: These are groups.
Reason for concern: Number of generators tend to infinity.
Resolve second issue by sending these groups into non finitely generated subgroups of a finitely generated group, e.g. Lamplighter group .
2.3. Lamplighter group
is the semi-direct product of and the -indexed direct sum of copies of , where acts by permuting coordinates. Elements of are configurations of a lamps assignment (only finitely many lamps are on) and a lamplighter location .
Fix a generating set of . A generating set for is the set of instructions to the lamplighter: either switch the lamp at the current location on or off, or move one step away. In other words,
Observe that is an infinite generated subgroup.
2.4. The traveling salesman metric
The word metric on behave as follows. To go from to , one needs visit all locations in the support of , so
where is the minimal length of a path in joining to and visiting all sites .
Definition 12 The traveling salesman metric on , , is the minimal length of a loop in based at and visiting all sites .
2.5. First step in the construction
Let us start with easy lemmas.
For this and these , there are finite subsets such that
- Pairwise distances within belong to .
Now identify with . The diameter is , exponentially larger than , and the traveling salesman distance is of the order of , therefore the distorsion is . This shows that
2.6. Passing to a quotient
To improve this bound, we replace with a quotient. This requires quotienting by a vectorsubspace that contains some dual code . For the semi-direct product to be defined, we need to be -invariant.
Proposition 14 There exists an amenable, exponential growth group and a -invariant subspace such that for some sequence tending to infinity, is bi-Lipschitz, with expansion ratio .
The difficulty is making sure that the quotient map is still bi-Lipschitz.
What can go wrong ?
- Set sum of translates of . It will be much bigger than alone.
- Set . It will be much bigger than alone.
We need to ensure that given , and in -translate of , there is a single such that
2.7. Finding suitable group and subspace
To give ourselves room to move, let , some , where is itself amenable with exponential growth.
View as a disjoint union of . Then as a vectorspace,
We will choose maps to actually land in viewed as the component of . Then will itself be of the form
where ‘s are all related by the action.
To choose , observe that does not see the -action, we need only take care of the -action.
2.8. New notational convention
From now on, elements of either or, e.g., will be called tuples and written .
Elements of will be called functions (on tuples) or finite subsets of tuples, and written .
We will obtain in two steps,
- Find where is a well separated set with inter-point distances as given by Lemma 13.
- Choose homomorphism .
This actually breaks the difficulty.
2.9. Construction of
We want . Let
Observe that is of the order of for distinct , . So is also a set of points, all roughly apart (we have jumped one level up). Now pick an arbitrary isomorphism . It will be important to know that this already helps with translation invariance. I.e. see what translation invariance remains at the level of the finite set .
Lemma 15 Let be even. There is a -invariant subgroup such that
- In fact, the quotient map is bi-Lipschitz from quotient Hamming metric to quotient of traveling salesman distance.
Proof: In fact, we choose translation invariant and let . To do this, given , define as follows,
Adding is necessary for translation invariance, since translating by adds up .
One checks that if belongs to , then .
2.10. Construction of
First attempt: Assume are disjoint. Given , let
For this choice, one cannot rule out conflicts between translates. One needs an extra trick to prevent translates from , filling up something that is constant on cylinders like .
To repair this, we choose a sequence such that and find some function such that the constant function is not a sum of translates of . E.g. if . Set
This now prevents cancellation.