A localized packing lemma for sets of bounded VC2-dimension
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 VC2-dimension, we show that in 𝔽pn a similar statement does hold after localization to cosets of subspaces depending on the individual translates. More precisely, given ε>0 and A⊆ 𝔽pn with VC2(A)<k, we show that there exist r≤ ε−Ok,p(1) and g1,…, gr∈ 𝔽pn with the property that for every x∈ 𝔽pn, there is a partition 𝒞x of 𝔽pn into cosets of (possibly distinct) subgroups, each of index at most exp(ε−Ok,p(1)), and a subcollection Ωx⊆ 𝒞x whose union has size at least (1−ε)|𝔽pn|, such that on each C∈ Ωx, the translate A−x looks like one of A−g1,…, A−gr, in the sense that |((A−x)Δ(A−gix,C))∩ C|<ε|C| for some 1≤ ix,C≤ r. We also prove a second version of this result in which each partition 𝒞x is the set of cosets of a single subgroup Hx of quasipolynomial index but where the bound on r is a quadruple exponential.
Related
- A threshold for full packing dimension of Hölder images of sets and measures
- A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound
- Schwarz lemma on bounded symmetric domains endowed with holomorphic invariant Kähler--Berwald metrics
- Null-additive sets and packing measures
- Fractal dimensions and quasisymmetric packing-minimalities of some homogeneous Moran sets
BibTeX
@misc{terry2026localized,
title = {{A localized packing lemma for sets of bounded $\operatornameVC_2$-dimension}},
author = {C. Terry and J. Wolf},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01101},
eprint = {2611.01101},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01101},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A localized packing lemma for sets of bounded VC_2-dimension
AU - C. Terry
AU - J. Wolf
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01101
UR - https://arxiv.org/abs/2611.01101
AB - 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 𝔽_p^n a similar statement does hold after localization to cosets of subspaces depending on the individual translates. More precisely, given ε>0 and A⊆ 𝔽_p^n with VC_2(A)<k, we show that there exist r≤ ε^−O_k,p(1) and g_1,…, g_r∈ 𝔽_p^n with the property that for every x∈ 𝔽_p^n, there is a partition 𝒞_x of 𝔽_p^n into cosets of (possibly distinct) subgroups, each of index at most exp(ε^−O_k,p(1)), and a subcollection Ω_x⊆ 𝒞_x whose union has size at least (1−ε)|𝔽_p^n|, such that on each C∈ Ω_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≤ i_x,C≤ r. We also prove a second version of this result in which each partition 𝒞_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.
ER -