The VC-dimension of quadratic residues in finite fields

Abstract

We study the Vapnik-Chervonenkis (VC) dimension of the set of quadratic residues (i.e. squares) in finite fields, ${\mathbb{F}}_q$, when considered as a subset of the additive group. We conjecture that as $q\to \infty$, the squares have the maximum possible VC-dimension, viz. $(1+o(1)){\log }_{2}q$. We prove, using the Weil bound for multiplicative character sums, that the VC-dimension is $\ge (\frac{1}{2}+o(1)){\log }_{2}q$. We also provide numerical evidence for our conjectures. The results generalize to multiplicative subgroups $\Gamma \subseteq {\mathbb{F}}_q^{\times }$ of bounded index.

22 pages, 3 figures. Accepted incorporating referee comments