A localized packing lemma for sets of bounded VC 2-dimension

arXiv:2611.01101 · math.CO, math.LO · Submitted 2026-10-31 · Read on arXiv

math.CO, math.LO

Submitted: 2026-10-31

Updated: 2026-10-31

Comments: 24 pages

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: In the setting of abelian groups, Haussler's packing lemma implies that any subset of bounded VC-dimension can be approximated by one of a small number of representative translates.

Terminology

Abstract

In the setting of abelian groups, Haussler's packing lemma implies that any subset of bounded VC-dimension can be approximated by one of a small number of representative translates. While this exact statement is provably false under the weaker hypothesis that A has bounded VC 2-dimension, we show that in F p n a similar statement does hold after localization to cosets of subspaces depending on the individual translates. More precisely, given ε>0 and A F p n with VC 2(A)<k, we show that there exist r at most ε-O k,p(1) and g 1,, g r in F p n with the property that for every x in F p n, there is a partition C x of F p n into cosets of (possibly distinct) subgroups, each of index at most (ε-O k,p(1)), and a subcollection Ω x C x whose union has size at least (1-ε) F p n, such that on each C in Ω x, the translate A-x looks like one of A-g 1,, A-g r, in the sense that ((A-x)Δ(A-g i x,C)) C<εC for some 1 at most i x,C at most r. We also prove a second version of this result in which each partition C x is the set of cosets of a single subgroup H x of quasipolynomial index but where the bound on r is a quadruple exponential.

Sources

Related papers