Notes of Orel Becker’s Cambridge lecture 09-05-2017

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 {d}-tuple of size {n} permutations defines a {n}-vertex directed graph {X} of outgoing degree {d}. Each edge has a label in {\{1,\ldots,d\}}. Conversely, such graphs determine permutations.

Fix a set of relators. Let {GOOD(X)} be the set of vertices fixed by relators. Say graph is {1-\delta}-GOOD if this is the proportion of GOOD vertices. Group {G} is testable if {1-\delta}-GOOD graphs can be made 1-GOOD by changing an {\epsilon}-fraction of edges.

Think of an {1-\delta}-GOOD graph as a challenge, and changing an {\epsilon}-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 {d} everywhere. The resulting {1-\delta}-GOOD graph is called a Cayley challenge.

2. Residually finiteness

Arzhantseva-Paunescu: Cayley challenges are solvable iff {G} 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 {r}. Start with a {1-\delta}-GOOD Cayley challenge {X}. Then almost all {r}-balls of {X} embed in the Cayley graph. Following Ornstein-Weiss, place a Folner set inside every such {r}-ball.These cover most of {X}, but with a lot of overlap. Extract a maximal {(1-\epsilon)}-disjoint subcover. The {\epsilon} 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 {\epsilon}-cover of all of {X}.

If each Folner set is almost isomorphic to a finite Schreier graph of {G}, 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 {G}.

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 {X}, every {r}-ball embeds in some Schreier graph of {G}, 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 {r} and a pointed set {X} with a transitive {G} action whose stabilizers are finitely generated, and returns a finite subsets of {G}.

Locality. Such a map is local if the finite subset {T} only depends on the combinatorics of the ball {B(x,r)} in {X} and not all of {X}.

Folner condition. The orbit of the marked point {x} under {T=F(r,X,x)} is {\epsilon}-Folner.

Transversality. {T} is a transversal for the cosets of some finite inex subgroup of {G}.

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 {BS(1,2)}. 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 {G={\mathbb Z}^d}, {X=G/H}. We need to produce a tile {T\subset G} which is Folner and almost isomorphic to a finite Schreier graph. We use Weiss’s general existence theorem, and construct {T} in a greedy manner. Start with the tile of {G} (i.e. {H=\{1\}}) provided by Weiss. If it fits, let us take it. Otherwise, there exist short elements in stabilizer {G_x}, let {H} be the subgroup they generate. use Weiss’s tile for {G/H}.

4. Questions

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.


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