Given a set X, the notion of VC-dimension provides a way to measure randomness in collections of subsets of X. Specifically, the VC-dimension of a collection S of subsets of X is the largest integer d (if it exists) such that some d-element subset Y of X is ""shattered"" by S, meaning that every subset of Y can be obtained as the intersection of Y with some element of S. In this talk, we will focus on the case that X is a group G, and S is the collection of left translates of some fixed subset A of G. The goal is to understand the structure of A, under the assumption that S has finite VC-dimension. In order to make this meaningful for finite groups, we fix a finite bound d on the VC-dimension, and allow the group G and the set A to vary. Our main result is that under these assumptions, A is approximately a union of translates of a large Bohr set in G, which is a special kind of well-structured subset of G behaving somewhat like a subgroup. We will also discuss further assumptions which allow the Bohr set to be replaced by an actual subgroup of G, and also yield better control on the approximation of A. These results qualitatively generalize recent work of several authors on strengthened arithmetic regularity lemmas for finite abelian groups, and are proved using the model theory of pseudofinite groups (although no prior knowledge of model theory will be assumed). This is joint work with A. Pillay and C. Terry.
Thu, 07/06/2018 - 14:15 to 15:15
Manchester Building (Hall 2), Hebrew University Jerusalem