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

preprint2022arXivOpen access

Abstract

Given a set E⊂Fq3E \subset {\Bbb F}_q^3, where Fq{\Bbb F}_q is the field with qq elements. Consider a set of "classifiers" Ht3(E)={hy:y∈E}{\mathcal H}^3_t(E)=\{h_y: y \in E\}, where hy(x)=1h_y(x)=1 if x⋅y=tx \cdot y=t, x∈Ex \in E, and 00 otherwise. We are going to prove that if ∣E∣≥Cq114|E| \ge Cq^{\frac{11}{4}}, with a sufficiently large constant C>0C>0, then the Vapnik-Chervonenkis dimension of Ht3(E){\mathcal H}^3_t(E) is equal to 33. In particular, this means that for sufficiently large subsets of Fq3{\Bbb F}_q^3, the Vapnik-Chervonenkis dimension of Ht3(E){\mathcal H}^3_t(E) is the same as the Vapnik-Chervonenkis dimension of Ht3(Fq3){\mathcal H}^3_t({\Bbb 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 Fq3{\Bbb F}_q^3 of size ≥Cq114\ge Cq^{\frac{11}{4}}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.