VC-dimension of Salem sets over finite fields

Abstract

The VC-dimension, introduced by Vapnik and Chervonenkis in 1968 in the context of learning theory, has in recent years provided a rich source of problems in combinatorial geometry. Given $E\subseteq {\mathbb{F}}_q^d$ or $E\subseteq {\mathbb{R}}^d$, finding lower bounds on the VC-dimension of hypothesis classes defined by geometric objects such as spheres and hyperplanes is equivalent to constructing appropriate geometric configurations in $E$. The complexity of these configurations increases exponentially with the VC-dimension. These questions are related to the Erdős distance problem and the Falconer problem when considering a hypothesis class defined by spheres. In particular, the Erdős distance problem over finite fields is equivalent to showing that the VC-dimension of translates of a sphere of radius $t$ is at least one for all nonzero $t\in {\mathbb{F}}_q$. In this paper, we show that many of the existing techniques for distance problems over finite fields can be extended to a much broader context, not relying on the specific geometry of circles and spheres. We provide a unified framework which allows us to simultaneously study highly structured sets such as algebraic curves, as well as random sets.

32 Pages, 6 Figures