On the quadratic complexity of subsets of ${\mathbb{F}}_p^n$ of bounded $\mathrm{V}{\mathrm{C}}_2$-dimension

Abstract

In prior work, we showed that subsets of ${\mathbb{F}}_p^n$ of $\mathrm{V}{\mathrm{C}}_2$-dimension at most $k$ are well approximated by a union of atoms of a quadratic factor of complexity $(\ell ,q)$, where the complexity $\ell$ of the linear part and the complexity $q$ of the quadratic part are both bounded in terms of $k$, $p$, and the desired level of approximation $\mu$. A key tool in the proof of this result was an arithmetic regularity lemma for the Gowers $U^3$-norm by Green and Tao, which resulted in tower-type bounds (in terms of ${\mu }^{-1}$) on both $\ell$ and $q$. In the present paper we show that for sets of bounded ${\mathrm{VC}}_2$-dimension, the bound on $q$ can be substantially improved. Specifically, we will prove that any set $A\subseteq G={\mathbb{F}}_p^n$ of ${\mathrm{VC}}_2$-dimension at most $k$ is approximately equal (up to error $\mu |G|$) to a union of atoms of a quadratic factor whose quadratic complexity is at most ${\log }_p({\mu }^{-k-o(1)})$, implying that the purely quadratic component of the factor partitions the group into ${\mu }^{-k-o(1)}$ many parts. We achieve this by using our earlier result to obtain an initial quadratic factor $\mathcal{B}$, and then applying a generalization of an argument of Alon, Fox and Zhao for subsets of ${\mathbb{F}}_p^n$ of bounded $\mathrm{VC}$-dimension to the label space (also known as "configuration space") of $\mathcal{B}$. A related strategy was employed in earlier work of the authors on ${\mathrm{NFOP}}_2$ subsets of ${\mathbb{F}}_p^n$, and in work of the first author in the context of 3-uniform hypergraphs.

29 pages. Cross references updated