Convolutions of sets with bounded VC-dimension are uniformly continuous

- Department of Mathematics, Stockholm University
- More about Olof Sisask

### Editorial introduction

Convolutions of sets with bounded VC-dimension are uniformly continuous, Discrete Analysis 2021:1, 25 pp.

In recent years there has been a cross-fertilization between combinatorics and model theory, as a result of the realization that certain model-theoretic problems concerning ideas such as stable sets and NIP sets lead naturally to problems with purely combinatorial statements that relate in interesting ways to questions already considered in combinatorics.

A well-known example of this is a result of Malliaris and Shelah that shows that under a certain hypothesis one can prove Szemerédi’s regularity lemma with a much better bound. The hypothesis in question is that the graph is k-*stable*, which means that it is not possible to find vertices x1,…,xk and y1,…,yk such that xi is joined to yj if and only if i≤j.

This result has led to a burst of activity with several modifications and generalizations being proved. An early example was an arithmetic version of the result due to Terry and Wolf. Let A be a subset of Fnp and let G be the graph with vertex set Fnp and with x joined to y if and only if x+y∈A. Terry and Wolf defined A to be k-stable if and only if G is k-stable, and showed that if A is k-stable and ϵ>0, then there is a subspace V⊂Fnp of low codimension (with a very good dependence on k and ϵ) such that for every translate of V, the fraction of the translate that is contained in A is either at most ϵ or at least 1−ϵ. Later they generalized this result to one about arbitrary finite Abelian groups.

Another direction of generalization is to weaken the k-stability assumption. A graph is said to be k-NIP (this stands for “no independence property”) if the set system formed by the neighbourhoods of the vertices has VC-dimension less than k. That is, there is no set of vertices A of size k such that every subset of A is equal to A∩N(x) for some vertex x, where N(x) is the neighbourhood of x. This is weaker than k-stability because it forbids something stronger: to show that a graph is not k-stable, all we have to do is find a set A of size k with an enumeration {a1,…,ak} of its elements such that every subset of the special form {ai,ai+1,…,ak} is equal to A∩N(x) for some vertex x, whereas to show that it is not k-NIP we have to obtain all subsets of A.

A k-NIP subset A of a finite Abelian group G can now be defined to be a set A such that the graph where xy is an edge if and only if x+y∈A is k-NIP. It turns out that this too is a strong enough condition to make it possible to deduce a very much stronger regularity lemma than holds for general sets.

However, as a simple example shows, there are some differences between k-NIP sets and k-stable sets, so the results one can hope for are not quite as strong for k-NIP sets. The example is where the group G is the cyclic group Zp and A is a set of density approximately 1/2. Such a set can easily be a k-NIP set – for example, if A is an arithmetic progression, then it is a 4-NIP set (since if x,y,z,w are elements of Zp in cyclic order, then A∩{x,y,z,w} cannot equal {x,z}). However, it is not k-stable for any bounded k: if, for instance, A={0,1,…,m} then this is demonstrated by the sequences (1,2…,k) and (−1,−2,…,−k). Indeed, it turns out that no subset of Zp of density bounded away from 0 and 1 is k-stable.

A result of Alon, Fox and Zhao, also published in Discrete Analysis, shows that an NIP subset of a finite Abelian group of bounded exponent can be approximated by a union of cosets of a subgroup of bounded index, with very good dependencies between the various parameters. That result is reproved in this paper with a completely different argument that works for all Abelian groups (but with cosets of a subgroup replaced by translates of a Bohr set when the exponent is unbounded).

It is somewhat more natural to phrase the results in terms of Bohr-set continuity. The paper shows, for example, that if the sets A∩(A+x) form a system of bounded VC-dimension and |A+A| is not too large compared with A, then there is a large Bohr set B such that the convolution f of the characteristic function of A with itself has the continuity property that |f(x+d)−f(x)|≤ϵ|A| for every x and every d∈B. This easily implies an arithmetic regularity lemma (again with very good bounds) as well as establishing the polynomial Freiman-Ruzsa conjecture for sets of bounded VC-dimension.