The VC-dimension and point configurations in ℝ^d

2025/10/15 by Iosevich, Alex, Magyar, Akos, McDonald, Alex +1
#28A78 #28A80 #42B10 #Classical Analysis and ODEs (math.CA) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.13984

Abstract

Given a set X and a collection \mathcal H of functions from X to \0,1\, the VC-dimension measures the complexity of the hypothesis class H in the context of PAC learning. In recent years, this has been connected to geometric configuration problems in vector spaces over finite fields. In particular, it is easy to show that the VC-dimension of the set of spheres of a given radius in \mathbbF_q^d is equal to d+1, since this is how many points generically determine a sphere. It is known that for E⊆ \mathbbF_q^d, |E|≥ q^d-(1)/(d-1), the set of spheres centered at points in E, and intersected with the set E, has VC-dimension either d or d+1. In this paper, we study a similar question over Euclidean space. We find an explicit dimensional threshold s_d

Citations

• Realizing trees of configurations in thin sets
• New improvement to Falconer distance set problem in higher dimensions
• VC-Dimension of Hyperplanes over Finite Fields
• VC-dimension and pseudo-random graphs
• Nonempty interior of configuration sets via microlocal partition optimization
• The VC-dimension and point configurations in \Bbb F_q²
• Areas spanned by point configurations in the plane
• On Falconer's distance set problem in the plane
• Rigidity, graphs and Hausdorff dimension

Related

• The VC-dimension and point configurations in \Bbb F_q²
• VC-Dimension and Distance Chains in \mathbbF_q^d
• VC-dimension of Salem sets over finite fields
• Spherical dimension
• Optimal Bounds on the VC-dimension