2025/10/14 by Terry, C., Wolf, J.
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2510.12867
We show that a subset of \mathbbFpn of \mathrmVC2-dimension at most k is well approximated by a union of atoms of a quadratic factor of complexity (ℓ,q) (denoting the complexities of the linear and quadratic part, respectively), where ℓ and q are bounded by a constant depending only on k and the desired level of approximation. This generalises a result of Alon, Fox and Zhao on the structure of sets of bounded VC-dimension, and is analogous to contemporaneous work of the authors arXiv:2111.01737 in the setting of 3-uniform hypergraphs. The main result originally appeared--albeit with a different proof--in a 2021 preprint arXiv:2111.01739, which has since been split into two: the present work, which focuses on higher arity NIP and develops a theory of local uniformity semi-norms of possibly independent interest, and its companion arXiv:2111.01739, which strengthens these results under a generalized notion of stability.