Henry Bradford

University of Cambridge


Quantifying permutation stability


Algebra Seminar


10th October 2023, 4:00 pm – 5:00 pm
Fry Building, 2.04


Suppose we have a (possibly infinite) system R of group relations r in k variables, and a k-tuple t of permutations of a finite set, and we want to (efficiently) check whether t satisfies the system R. We might run the following naive test: pick a few points x in the permutation domain at random, and for all relations r in R up to a given length, check whether r(t) fixes each such x. We describe R as "stable in permutations" if a tuple t which passes this test is, with high probability, at worst a slight perturbation of a genuine solution to R. In this case the computational cost of running the test is called the "stability rate" of R. Permutation stability has received a great deal of recent attention, owing to its relevance both to "property testing" questions in computer science, and to the search for a non-sofic group (with the attendant implications of the latter to group algebras; topological dynamics and operator algebras). In this talk, we show that for any increasing function F, there exist systems of equations which are stable in permutations, but whose stability rate is worse than F. Based on joint work with Oren Becker and Tianyi Zheng.





Organisers: Jack Saunders, Vlad Vankov

Comments are closed.
css.php