论文标题
$ {\ bbb f} _q^3 $的点产品和vapnik-chervonenkis dimension
Dot products in ${\Bbb F}_q^3$ and the Vapnik-Chervonenkis dimension
论文作者
论文摘要
给定一个$ e \ subset {\ bbb f} _q^3 $，其中$ {\ bbb f} _q $是带有$ q $ elements的字段。考虑一组“分类器” $ {\ MATHCAL H}^3_T（e）= \ {h_y：y \ in E \} $，其中$ h_y（x）= 1 $如果$ x \ cdot y = t $，$ x $，$ x \ in e $ in $ in $ in $，以及$ 0 $否则。我们将证明，如果$ | e | \ ge cq^{\ frac {11} {4}} $，带有足够大的常数$ c> 0 $，则$ {\ Mathcal H}^3_t（e）$的Vapnik-Chervonenkis维度等于$ 3 $。特别是，这意味着，对于$ {\ bbb f} _q^3 $的足够大子集，$ {\ Mathcal H}^3_t（e）$的Vapnik-Chervonenkis维度与VAPNIK-CHERVONENKIS $相同f} _q^3）$。从某种意义上说，证明使我们考虑了最复杂的可能配置，这些配置始终可以嵌入$ {\ bbb f} _q^3 $的子集中，尺寸$ \ ge cq^{\ frac {\ frac {11}} {4}}} $。
Given a set $E \subset {\Bbb F}_q^3$, where ${\Bbb F}_q$ is the field with $q$ elements. Consider a set of "classifiers" ${\mathcal H}^3_t(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 Cq^{\frac{11}{4}}$, with a sufficiently large constant $C>0$, then the Vapnik-Chervonenkis dimension of ${\mathcal H}^3_t(E)$ is equal to $3$. In particular, this means that for sufficiently large subsets of ${\Bbb F}_q^3$, the Vapnik-Chervonenkis dimension of ${\mathcal H}^3_t(E)$ is the same as the Vapnik-Chervonenkis dimension of ${\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 ${\Bbb F}_q^3$ of size $\ge Cq^{\frac{11}{4}}$.
