Consider a simultaneous system of equations \(M\), over \(k\) permutation variables. As a running example, let \(k=2\) and let \(M\) consist of the single equation \(XY=YX\). In other words, a pair of permutations \(A\) and \(B\) over \(\{1,\ldots,n\}\) is said to satisfy \(M\) if \(A\) and \(B\) commute. Generally, we are interested in algorithmically testing whether a given tuple of \(k\) permutations satisfies \(M\).
Focusing on our running example, let \(G(A,B)\) denote the global defect of \((A,B)\), that is, the minimal normalized Hamming distance between the pair \((A,B)\) and a commuting pair of permutations. We seek an algorithm which efficiently (i.e., with running time depending on \(\epsilon\) but not on \(n\)) distinguishes between the cases \(G(A,B) = 0\) and \(G(A,B) > \epsilon\). If such an algorithm exists, the system \(M\) is called testable.
We are particularly interested in the canonical tester for \(M\). In our example, this is the algorithm which repeatedly and independently samples some \(x\) from \(\{1,\ldots,n\}\), uniformly at random, and accepts only if \(A(B(x))=B(A(x))\) in every iteration. A system \(M\) which is efficiently testable by its canonical tester is said to be stable.
We are also interested in quantitative aspects of these definitions. For example, \(M\) is said to be polynomially testable if it has a tester whose running time is polynomial in \(1/\epsilon\).
Not surprisingly, these notions are strongly connected to group theory: By thinking of a system of equations as a group presentation, it turns out that testability, stability, and their quantitative refinements, are all, in fact, group invariants. In other words, if \(M\) and \(M'\) are both presentations of the same group, and \(M\) is a testable system of equations, then \(M'\) is also testable. Perhaps more striking are the deep links between these invariants and other properties of the group. For example, we show that every presentation of an amenable group is testable.
In this talk we will briefly survey the emerging landscape of stability and testability of equations in permutations. Our focus will be a recent quantitative result: If the group presented by the system \(M\) is abelian, then \(M\) itself is polynomially stable. In particular, this theorem applies to our initial example of commuting permutations pairs, where the associated group is \(\mathbb{Z}^2\).
Based on joint works with Oren Becker and Alex Lubotzky.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)