Testability in group theory (Q6076186)

In the paper under review, the authors study property testing problems concerning relations between permutations. In such problems, the input is a tuple \((\sigma_{1}, \dots, \sigma_{d})\) of permutations on \(\Omega=\{1, \dots, n \}\), and one wishes to determine whether this tuple satisfies a certain system of relations \(E\), or is far from every tuple that satisfies \(E\). If this computational problem can be solved by querying only a small number of entries of the given permutations, then the author says that \(E\) is testable. For example, when \(d=2\) and \(E\) consists of the single relation \(\mathsf{XY} = \mathsf{YX}\), this corresponds to testing whether \(\sigma_{1}\) and \(\sigma_{2}\) commutes. In [Int. Math. Res. Not. 2021, No. 20, 15574--15632 (2021; Zbl 07456010)], the first and the third author showed that set \(E=\{\mathsf{XY} = \mathsf{YX}\}\) is testable (on the other hand, the systems \(E = \{\mathsf{XZ} = \mathsf{ZX}, \mathsf{YZ} = \mathsf{ZY}\}\) and \(E=\{\mathsf{X}^{2}\mathsf{Y}=\mathsf{YX}^{2} \}\) are not testable). In the paper under review, the authors associate each system \(E\) with a group \(\Gamma=\Gamma_{E}\) and show that the testability of \(E\) depends only on \(\Gamma\) (just like in Galois theory where the solvability of a polynomial is determined by the solvability of the associated group).