The VC-dimension of quadratic residues and related problems

We will discuss the notion of the Vapnik--Chervonenkis (VC) dimension of a subset $S$ of a finite group $G$; explicitly this is the VC-dimension of the set family given by the translates of the subset $S$. In particular, we will discuss two recent works on this theme.

In work with Brian McDonald and Emmett L. Wyman, we investigated the VC-dimension of the set of quadratic residues in a finite field (when considered as a subset of the additive group). We conjectured that this VC-dimension is essentially as large as possible as the size of the finite field goes to infinity. Further, using the Weil bound for multiplicative character sums, we proved a lower bound that gets us halfway to our conjecture.

We also conjectured a natural generalization to higher order residues. However, recent work with Brad Rodgers on a random model of these residues suggests that the natural generalization is incorrect. We will describe our (rigorous) results in this settings which essentially determines the VC-dimension of a "randomly chosen subset" of a group.