Efficient arithmetic regularity and removal lemmas for induced bipartite patterns

Efficient arithmetic regularity and removal lemmas for induced bipartite patterns, Discrete Analysis 2019:3, 14 pp.

This paper provides a common extension of two recent lines of work: the study of arithmetic regularity lemmas under the model-theoretic assumption of stability initiated by Terry and Wolf, and that of graph regularity lemmas for graphs of bounded VC-dimension provided by Lovász and Szegedy (following prior work of Alon, Fischer and Newman) and extended to hypergraphs by Fox, Pach and Suk.

Since Szemerédi’s seminal work in the 1970s, regularity lemmas have proved to be of fundamental importance in many areas of discrete mathematics. In the graph setting, a regularity lemma states that the vertex set of any sufficiently large graph can be partitioned into a bounded number of sets such that almost all pairs of parts from the partition induce a bipartite graph that looks a lot like a random graph (that is, it is a quasi-random graph, in a sense that can be made precise in several essentially equivalent ways).

An arithmetic analogue of Szemerédi’s regularity lemma was formulated and proved by Green in 2005. An important special case of Green’s lemma asserts that for any sufficiently large \(n\) and any subset \(A\) of the vector space \(\mathbb{F}_p^n\), this space can be partitioned into cosets of a subspace \(H\) of bounded codimension such that the set \(A\) behaves quasi-randomly with respect to almost every coset in the partition. (Here the quasi-random behaviour is defined in terms of the absolute value of the Fourier transform of the indicator function of the set \(A\) relative to the subspace \(H\).)

In both settings, it was shown (by Gowers and Green, respectively) that the trade-off between the number of parts in the partition and the degree of quasi-randomness obtained was necessarily of tower-type. In the case of graphs, it had already been observed many years earlier that the existence of “irregular” pairs in the partition could not in general be excluded. That is, in general, the conclusions of the regularity lemma cannot be strengthened in either setting.

The folklore example ruling out the existence of a completely regular graph partition is the half-graph, which is a bipartite graph defined on two vertex classes \(X=\{x_1,x_2,\dots,x_k\}\) and \(Y=\{y_1, y_2,\dots, y_k\}\), with edges between \(x_i\) and \(y_j\) if and only if \(i\leq j\). Malliaris and Shelah observed in 2014 that by forbidding induced copies of the half-graph (of constant size), one can indeed guarantee a completely regular partition of any sufficiently large graph. In fact, they proved an even stronger result: the number of parts of the partition depends polynomially on the regularity parameter, and the edge density between any two parts of the partition is guaranteed to be either close to 0 or close to 1.

The half-graph is known to model theorists as a particular instance of the so-called “order property” (in this case, it is a property of the formula defining the edge relation in the graph). In 2018 Terry and Wolf proved an analogue of the Malliaris-Shelah result in the arithmetic setting by considering an instance of the order property adapted to subsets of groups: a subset \(A\subseteq G\) of an abelian group \(G\) is said to have the \(k\)-order property if there exist \(x_1,x_2,\dots,x_k\), \(y_1, y_2,\dots, y_k\) in \(G\) such that \(x_i+y_j\in A\) if and only if \(i\leq j\). Terry and Wolf proved that if a set \(A\subseteq \mathbb{F}_p^n\) (for sufficiently large \(n\)) does not have the \(k\)-order property, then there exists a subspace \(H\) of \(\mathbb{F}_p^n\) such that \(A\) has density at most \(\epsilon\) or at least \(1-\epsilon\) on each coset of \(H\), and the codimension of \(H\) has a power dependence on \(\epsilon\) (with the power depending on \(k\)).

A structure that does not have the order property is called model-theoretically “stable”. Stable structures have been studied since the 1970s, and have been shown to exhibit particularly “tame” behaviour. Such stability often manifests itself as a quantifiable global property of the structure in question. A natural relaxation of stability, from the model-theoretic point of view, is that of lacking the so-called “independence property”, another model-theoretic concept that goes back to Shelah’s work in the 1970s. Indeed, structures that lack the independence property are arguably better known across mathematics as having bounded VC-dimension, a notion that was defined independently around the same time by Vapnik and Chervonenkis in the context of statistical learning theory, and that has been widely used ever since.

A graph \(G=(V,E)\) is said to have VC-dimension \(k\) if the largest set of vertices shattered by the family of neighbourhoods \(\{N_G(v):v\in V\}\) has size \(k\). (Recall that a set \(X\) is shattered by a family \(\mathcal{F}\) if for every \(X'\subseteq X\), there exists \(F\in \mathcal{F}\) such that \(X'=X\cap F\).) A regularity lemma for graphs of bounded VC-dimension had been proved, independently of any model-theoretic considerations, by Lovász and Szegedy in 2010, having already been obtained in the bipartite context by Alon, Fischer and Newman in 2007. This work was later extended to hypergraphs of bounded VC-dimension by Fox, Pach and Suk.

In the present paper the authors prove an arithmetic regularity lemma for finite abelian groups of bounded exponent under the additional assumption of bounded VC-dimension. More precisely, they show that if \(G\) is a sufficiently large abelian group of bounded exponent and \(A\subseteq G\) is a subset of VC-dimension at most \(k\) (meaning that the maximum size of a set that is shattered by the set of translates \(\{g+A:g\in G\}\) is at most \(k\)) then there exists a subgroup \(H\leqslant G\) of index at most \(\epsilon^{-k-o(1)}\) such that \(|A\Delta S|<\epsilon|H|\), where \(S\) is some union of cosets of \(H\) and \(o(1)\) tends to zero as \(\epsilon\) tends to zero.

The bound on the index is stronger than that obtained by Terry and Wolf in the context of stable subsets of \(\mathbb{F}_p^n\), and so is the error in the approximation of \(A\) by cosets of \(H\). However, the result does not imply that of Terry and Wolf because the existence of irregular cosets is not ruled out (as indeed it cannot be, as a natural arithmetic analogue of the half-graph shows that irregular cosets must exist in any partition).

In addition to Haussler’s packing lemma, a by now standard tool in the setting of bounded VC-dimension, the proof uses the celebrated Bogolyubov-Ruzsa lemma from additive combinatorics, which, in the context of a finite abelian group \(G\) of bounded exponent, states that the iterated sum set \(2B-2B\) of a set \(B\) with small doubling contains a subgroup of \(G\) of size at least a constant times \(|B|\). From their efficient arithmetic regularity lemma the authors deduce an efficient removal lemma for bi-induced patterns, with an application to property testing.

Shortly after this paper was made available as a preprint on the arXiv, a related result was proved using model-theoretic machinery by Conant, Pillay and Terry, who had previously given a model-theoretic proof of the stable arithmetic regularity lemma for general finite (not necessarily abelian) groups. While vastly more general in scope than the results obtained using combinatorial means in the present paper, Conant, Pillay and Terry’s techniques yield no quantitative dependence of the parameters.