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.