Local testability in group theory, II
Joint work with Alex Lubotzky.
Positive results for amenable groups. We stick to finitely presented groups.
1. Translation into graphs
A -tuple of size permutations defines a -vertex directed graph of outgoing degree . Each edge has a label in . Conversely, such graphs determine permutations.
Fix a set of relators. Let be the set of vertices fixed by relators. Say graph is -GOOD if this is the proportion of GOOD vertices. Group is testable if -GOOD graphs can be made 1-GOOD by changing an -fraction of edges.
Think of an -GOOD graph as a challenge, and changing an -fraction of edges as a solution to the challenge.
Amenable groups come with plenty of challenges: pick a Folner set, the correponding piece of the Cayley graph, add edges to make its outgoing degree equal to everywhere. The resulting -GOOD graph is called a Cayley challenge.
2. Residually finiteness
Arzhantseva-Paunescu: Cayley challenges are solvable iff is residually finite.
I explain how residual finiteness allows to solve Cayley challenges. This relies on Ornstein-Weiss’ quasi-tiling, in Elek-Szabo style.
Fix a radius . Start with a -GOOD Cayley challenge . Then almost all -balls of embed in the Cayley graph. Following Ornstein-Weiss, place a Folner set inside every such -ball.These cover most of , but with a lot of overlap. Extract a maximal -disjoint subcover. The error is necessary.
Fact. Such a subcover covers a constant fraction of the cover.
Then iterate: cover the remaining uncovered part with smaller Folner sets, get an -cover of all of .
If each Folner set is almost isomorphic to a finite Schreier graph of , we are done. This works for residually finite groups (Weiss).
This solves Cayley challenges.
2.1. What about other challenges?
For instance, Schreier challenges, coming from Schreier graphs of .
In the abelian case, Schreier graphs are Cayley graphs of quotients, and the previous quasi-tiling method applies. However, the constants may depend on quotient.
In general, non-normal subgroups pose an extra difficulty.
3. Local testability systems
This is our technical tool. Given a general challenge , every -ball embeds in some Schreier graph of , but different Schreier graphs may occur. Folner sets are used to tile such balls. The local testability system provides such Folner sets. It takes as arguments a radius and a pointed set with a transitive action whose stabilizers are finitely generated, and returns a finite subsets of .
Locality. Such a map is local if the finite subset only depends on the combinatorics of the ball in and not all of .
Folner condition. The orbit of the marked point under is -Folner.
Transversality. is a transversal for the cosets of some finite inex subgroup of .
Local evenness. This is used to ensure that a uniform fraction of challenges will be covered.
3.1. Existence of LTS
We are able to construct LTS for abelian groups, nilpotent groups of class 2 (in fact, merely a weaker version of LTS), for . This relies on understanding all Schreier graphs.
I explain the construction in the abelian case, in a way that hints how to do for larger classes of groups.
Say , . We need to produce a tile which is Folner and almost isomorphic to a finite Schreier graph. We use Weiss’s general existence theorem, and construct in a greedy manner. Start with the tile of (i.e. ) provided by Weiss. If it fits, let us take it. Otherwise, there exist short elements in stabilizer , let be the subgroup they generate. use Weiss’s tile for .
Arzhantseva: can use it for groups approximable by amenable groups? I doubt it.
Fisher: what about the 3-dimensional SOL group? In the nilpotent case, things go wild after 3 steps, so we are stuck with SOL as well.