## 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.