VC-Dimension of Hyperplanes over Finite Fields

Abstract

Let ${\mathbb{F}}_q^d$ be the $d$-dimensional vector space over the finite field with $q$ elements. For a subset $E\subseteq {\mathbb{F}}_q^d$ and a fixed nonzero $t\in {\mathbb{F}}_q$, let ${\mathcal{H}}_t(E)=\{h_y:y\in E\}$, where $h_y$ is the indicator function of the set $\{x\in E:x\cdot y=t\}$. Two of the authors, with Maxwell Sun, showed in the case $d=3$ that if $|E|\ge C{q}^{\frac{11}{4}}$ and $q$ is sufficiently large, then the VC-dimension of ${\mathcal{H}}_t(E)$ is 3. In this paper, we generalize the result to arbitrary dimension and improve the exponent in the case $d=3$.

9 pages, 1 figure