## Stability and testability of permutations' equations

talk by Alexander Lubotzky

#### Oded's comments

For a fixed word equation such as XY=YX,
or even a fixed system of such equations,
given oracle access to permutations $A,B:[n]\to[n]$,
they consider the question of testing whether $A$ and $B$
satisfy the equation(s).
Actually, they seek non-adaptive
proximity oblivious testers (POTs);
that is, one-sided error testers that reject objects that
at distance $\delta$ from the property with probability
at least $F(\delta)$, where $F$ is a fixed function.
Furthermore, they are particularly interested in the case
that the equations themselves provide a robust characterization
of the property (i.e., testing is performed by checking
whether the equation hold at a random assignment),
and in this case they call the equations stable.

It turns out that even in the case of a single equation,
characterizing the cases that have a non-adaptive POT
(resp., the cases that constitute robust characterization)
is extremely challenging.
While the equation XY=YX is a robust characterization,
the equation XYY=YYX has no POT.
I find this demonstration of the fragility of the question
of being a robust characterization (resp., having a POT)
extremely fascinating.

#### The original abstract

We study a new direction of research in
property testing: Permutation equations.
Let A and B be two permutations in Sym(n) that "almost commute";
are they a small deformation of permutations that truly commute?
More generally, if R is a system of word-equations
in variables X=x_1,....,x_d and A_1,....,A_d are permutations
that are almost a solution; are they near true solutions?

It turns out that the answer to this question depends only
on the group presented by the generators X and relations R.
This leads to the notions of "stable groups" and "testable groups"
and calls for some group theoretic methods for answering these questions.
We will present a few results and methods which were developed
in recent years to check whether a group is stable/testable
(e.g., using IRS's= invariant random subgroups).
We will also describe the connection of this subject
with locally testable codes as well as with
the long-standing problem of whether every group is sofic.

See Testability
of relations between permutations
by Oren Becker, Alexander Lubotzky, and Jonathan Mosheiff
(arXiv:2011.05234 [cs.DS]).

Back to
list of Oded's choices.