2025/10/14 by C. Terry, Jason B. Wolf, Terry, C. +1
Computer Science · Mathematics · #Coding theory and cryptography #Digital Image Processing Techniques #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2510.12767
In prior work, we showed that subsets of \mathbbFpn of \mathrmVC2-dimension at most k are well approximated by a union of atoms of a quadratic factor of complexity (ℓ,q), where the complexity ℓ 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 μ. A key tool in the proof of this result was an arithmetic regularity lemma for the Gowers U3-norm by Green and Tao, which resulted in tower-type bounds (in terms of μ-1) on both ℓ and q. In the present paper we show that for sets of bounded VC2-dimension, the bound on q can be substantially improved. Specifically, we will prove that any set A⊆ G=\mathbbFpn of VC2-dimension at most k is approximately equal (up to error μ|G|) to a union of atoms of a quadratic factor whose quadratic complexity is at most logp(μ-k-o(1)), implying that the purely quadratic component of the factor partitions the group into μ-k-o(1) many parts. We achieve this by using our earlier result to obtain an initial quadratic factor B, and then applying a generalization of an argument of Alon, Fox and Zhao for subsets of \mathbbFpn of bounded VC-dimension to the label space (also known as "configuration space") of B. A related strategy was employed in earlier work of the authors on NFOP2 subsets of \mathbbFpn, and in work of the first author in the context of 3-uniform hypergraphs.