Local testability in group theory, I
Joint work with Orel Becker.
Let us start with a 2015 result by Arzhantseva and Paunescu: almost commuting permutations are near commuting permutations. I.e. if, with respect to normalised Hamming distance, is small, there exist commuting permutations and such that and is small. Smallness does not depend on size.
Such issues are ancient for matrices: see apparently contradicting papers by Luxemburg-Taylor 1970 and Choi 1988.
Arzhantseva and Paunescu’s statement is related to property testing in theoretical computer science: pick a random letter; if, with high probability, , then is close to a commuting pair.
BLR (Blum-Luby-Rubinfeld): let be a boolean function on -strings, there is an efficient linearity test. There exists independent on , such that if for random , then is close to a linear function.
More generally, given a property P of -strings, can one test if by testing random bits of , independent on . If so, say that is locally testable.
An important instance is when an error-correcting code. This ultimately led to the PCP theorem.
Let be a free group. Let be a set of equations in . A -solution is a tuple such that . Say the system is locally testable if , , independently on , such that -solutions are -close to solutions.
This only depends on the group , hence belongs to group theory. This appears in Glebsky-Rivera 2009.
Definition 1 Say a group is testable if, for some (or any) presentation, the set of relators is locally testable.
I prefer he word testable to Arzhantseva’s stable, which is
- Finite groups are testable (not hard, though not obvious).
- Testable sofic groups must be residually finite. Indeed, sofic means that there are plenty of challenges, i.e. near homomorphisms to . Testability implies that any is close to a true solution, i.e. a homomorphism.
- Abelian groups are testable (Arzhantseva-Paunescu).
- Most Baumslag-Solitar groups are not testable (since sofic – residually amenable – and not residually finite).
We see that testability of sofic, and especially amenable groups, is an interesting issue. For instance, Arzhantseva-Paunescu asked wether , the fundamental group of the Klein bottle (virtually abelian), is testable or not.
2.1. Amenable groups
Abels’s group is finitely generated, residually finite and solvable, it has an infinitely presented quotient. Therefore, it is not testable.
Theorem 2 A finitely generated normal subgroup of an amenable testable group must be closed in the profinite topology (i.e. must be residually finite).
We thought for some time that amenable testable groups must be LERF. LERF means that every finitely generated subgroup is closed in the profinite topology. This is not true.
Theorem 3 , are testable. Every nilpotent group of class 2 is testable.
2.2. What we do not know
Is every finitely generated nilpotent group testable? Polycyclic groups? We believe in it.
Is every solvable LERF group testable?
Is testability a commensurability invariant?
2.3. Nonamenable groups
Little is known. Free groups are testable (no approximate homomorphisms!). Testability is preserved under free products. What about direct products?
Theorem 4 A sofic group with property (T) is not testable.
I explain the proof, following Ozawa, for . It maps onto which acts 2-transitively on the projective plane . Then trivial irreducible. If testable, the approximate action on can be approximated with a true action on , thus can be approximated by other representations containing a fixed vector. This contradicts property (T).
Diaconis: seems to depend very much on which metric is used on the symmetric group.
Arzhantseva: Property is enough? Yes.