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,

m a t h b b F_{q}

, when considered as a subset of the additive group. We conjecture that as

q o i n f t y

, the squares have the maximum possible VC-dimension, viz.

(1 + o (1)) l o g_{2} q

. We prove, using the Weil bound for multiplicative character sums, that the VC-dimension is

g e q (f r a c 12 + o (1)) l o g_{2} q

. We also provide numerical evidence for our conjectures. The results generalize to multiplicative subgroups

G a m m a s u b s e t e q m a t h b b F_{q}^{i} m e s

of bounded index.

This page was built for publication: The VC-dimension of quadratic residues in finite fields