Notes of Alex Lubotzky’s Cambridge lecture 09-05-2017

Local testability in group theory, I

Joint work with Orel Becker.

1. Testability

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, {d(A'B',B'A')} is small, there exist commuting permutations {A} and {B} such that {d(A,A')} and {d(B,B')} 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, {A'B'(i):B'A'(i)}, then {(A',B')} is close to a commuting pair.

BLR (Blum-Luby-Rubinfeld): let {f} be a boolean function on {n}-strings, there is an efficient linearity test. There exists {k} independent on {n}, such that if {f(x+y)=f(x)+f(y)} for {k} random , then {f} is close to a linear function.

More generally, given a property P of {n}-strings, can one test if {x\in P} by testing {k} random bits of {x}, {k} independent on {n}. If so, say that {P} is locally testable.

An important instance is when {P} an error-correcting code. This ultimately led to the PCP theorem.

Let {F=F_d} be a free group. Let {R_i(x_1,\ldots,x_d)} be a set of {k} equations in {Sym(n)}. A {\delta}-solution is a tuple such that {\sum_i |R_i(x)|<\delta}. Say the system is locally testable if {\forall \epsilon>0}, {\exists \delta>0}, independently on {n}, such that {\delta}-solutions are {\epsilon}-close to solutions.

This only depends on the group {G=\langle x_1;\ldots,x_d|R_1,\ldots,R_k\rangle}, 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

Examples (Glebsky-Rivera).

  • 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 {Sym(n)}. 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 {BS(1,-1)}, the fundamental group of the Klein bottle (virtually abelian), is testable or not.

2. Results

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 {G} must be closed in the profinite topology (i.e. {G/N} 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 {BS(1,-1)}, {BS(1,2)} 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 {Sl(3,{\mathbb Z})}. It maps onto {Sl(3,p)} which acts 2-transitively on the projective plane {Y=P^2(p)}. Then {\ell^2(Y)=} trivial {\oplus} irreducible. If testable, the approximate action on {Y'=Y\setminus\{point\}} can be approximated with a true action on {Y'}, thus {\ell^2_0(Y)} can be approximated by other representations containing a fixed vector. This contradicts property (T).

3. Questions

Diaconis: seems to depend very much on which metric is used on the symmetric group.

Arzhantseva: Property {\tau} is enough? Yes.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s