The VC dimension of quadratic residues in finite fields.

We study the Vapnik–Chervonenkis (VC) dimension of the set of quadratic residues (i.e. squares) in finite fields, F q , when considered as a subset of the additive group. We conjecture that as q → ∞ , 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 ⩾ (1 2 + o (1)) log 2 ⁡ q. We also provide numerical evidence for our conjectures. The results generalize to multiplicative subgroups Γ ⊆ F q × of bounded index. [ABSTRACT FROM AUTHOR]