Convolutions of sets with bounded VC-dimension are uniformly continuous

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 \(x_1,\dots,x_k\) and \(y_1,\dots,y_k\) such that \(x_i\) is joined to \(y_j\) if and only if \(i\leq 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 \(\mathbb F_p^n\) and let \(G\) be the graph with vertex set \(\mathbb F_p^n\) and with \(x\) joined to \(y\) if and only if \(x+y\in 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 \(\epsilon>0\), then there is a subspace \(V\subset\mathbb F_p^n\) of low codimension (with a very good dependence on \(k\) and \(\epsilon\)) such that for every translate of \(V\), the fraction of the translate that is contained in \(A\) is either at most \(\epsilon\) or at least \(1-\epsilon\). 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\cap 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 \(\{a_1,\dots,a_k\}\) of its elements such that every subset of the special form \(\{a_i,a_{i+1},\dots,a_k\}\) is equal to \(A\cap 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\in 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 \(\mathbb Z_p\) 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 \(\mathbb Z_p\) in cyclic order, then \(A\cap\{x,y,z,w\}\) cannot equal \(\{x,z\}\)). However, it is not \(k\)-stable for any bounded \(k\): if, for instance, \(A=\{0,1,\dots,m\}\) then this is demonstrated by the sequences \((1,2\dots,k)\) and \((-1,-2,\dots,-k)\). Indeed, it turns out that no subset of \(\mathbb Z_p\) 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\cap(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)|\leq\epsilon|A|\) for every \(x\) and every \(d\in 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.