2022/03/06 by Iosevich, A., McDonald, B., Sun, M.
#52C10 #68Q32 #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2203.03046
Given a set E ⊂ \Bbb Fq3, where \Bbb Fq is the field with q elements. Consider a set of "classifiers" \mathcal H3t(E)=\hy: y ∈ E\, where hy(x)=1 if x ⋅ y=t, x ∈ E, and 0 otherwise. We are going to prove that if |E| ≥ Cq(11)/(4), with a sufficiently large constant C>0, then the Vapnik-Chervonenkis dimension of \mathcal H3t(E) is equal to 3. In particular, this means that for sufficiently large subsets of \Bbb Fq3, the Vapnik-Chervonenkis dimension of \mathcal H3t(E) is the same as the Vapnik-Chervonenkis dimension of \mathcal H3t(\Bbb Fq3). In some sense the proof leads us to consider the most complicated possible configuration that can always be embedded in subsets of \Bbb Fq3 of size ≥ Cq(11)/(4).