Groups, Manifolds, and Complexes

Yale University, New Haven CT

Investigators

Abstract

A question of considerable importance in science concerns the stability of solutions to equations that model systems of interest. A general form of the question asks: Given an approximate solution, is there necessarily also an exact solution that is close to the approximate solution? This question has been studied intensively in many directions, with answers depending on the specific system and the exact meaning of "approximate solution" and "close." The current research project develops such a theory for equations in sets of permutations. This case is of special interest for two reasons: Firstly, it can be interpreted as a "local testability" question, a subject of great interest in computer science. Namely, it is part of a series of problems of the following flavor: a very large string of letters is given, and one wants to check its properties by knowing only a few of the letters. A second reason is that it turns out that the question under study in this project is intimately related to some deep concepts in abstract algebra. It is thus a project of a very interdisciplinary nature, involving a blend of several areas of mathematics and computer science. In more detail, the project deals with property testing within group theory. Property testing is a direction of research in computer science that looks for methods to check a property of a given object, say a long vector of 0's and 1's, by looking only at a small number of random bits of it. The following question is of this type. Given a word w(X,Y) built from elements X and Y of the symmetric group of permutations on a set T, assume that for two permutations A and B, w(A,B) leaves unchanged some randomly selected elements of T. Can it be inferred that w(A,B) is the identity, or at least, that A and B are close to a pair of permutations A' and B' for which w(A',B') is the identity? It turns out that the answer to this question depends only on the structure of the (usually infinite) group whose presentation by generators and relations is given by these words. This suggests a concept of testability (or stability) in group theory. The main objective of this project is to develop a set of tools to determine which groups are testable and which are not. The project will also explore connections with amenability, Kazhdan's Property (T), and sofic groups.