Dot products in ${\mathbb{F}}_q^3$ and the Vapnik-Chervonenkis dimension

Abstract

Given a set $E\subset {\mathbb{F}}_q^3$, where ${\mathbb{F}}_q$ is the field with $q$ elements. Consider a set of "classifiers" ${\mathcal{H}}_t^3(E)=\{h_y:y\in E\}$, where $h_y(x)=1$ if $x\cdot y=t$, $x\in E$, and $0$ otherwise. We are going to prove that if $|E|\ge C{q}^{\frac{11}{4}}$, with a sufficiently large constant $C>0$, then the Vapnik-Chervonenkis dimension of ${\mathcal{H}}_t^3(E)$ is equal to $3$. In particular, this means that for sufficiently large subsets of ${\mathbb{F}}_q^3$, the Vapnik-Chervonenkis dimension of ${\mathcal{H}}_t^3(E)$ is the same as the Vapnik-Chervonenkis dimension of ${\mathcal{H}}_t^3({\mathbb{F}}_q^3)$. In some sense the proof leads us to consider the most complicated possible configuration that can always be embedded in subsets of ${\mathbb{F}}_q^3$ of size $\ge C{q}^{\frac{11}{4}}$.

arXiv admin note: text overlap with arXiv:2108.13231