论文标题
有限场中二次残基的VC维度
The VC-dimension of quadratic residues in finite fields
论文作者
论文摘要
我们研究了有限域中的二次残基（即正方形）的VAPNIK-CHERVONENKIS（VC）尺寸，当将$ \ Mathbb f_q $（$ \ Mathbb f_q $）视为添加剂组的子集时。我们猜想，作为$ q \ to \ infty $，正方形具有最大可能的VC维度，即。 $（1+O（1））\ log_2 q $。我们证明，使用Weil绑定的乘法字符总和，VC-dimension为$ \ geq（\ frac {1} {2} {2} + o（1））\ log_2 q $。我们还为我们的猜想提供了数值证据。结果概括为乘法子组$γ\ subseteq \ mathbb f_q^\ times $ bounded Index的$。
We study the Vapnik-Chervonenkis (VC) dimension of the set of quadratic residues (i.e. squares) in finite fields, $\mathbb F_q$, when considered as a subset of the additive group. We conjecture that as $q \to \infty$, the squares have the maximum possible VC-dimension, viz. $(1+o(1))\log_2 q$. We prove, using the Weil bound for multiplicative character sums, that the VC-dimension is $\geq (\frac{1}{2} + o(1))\log_2 q$. We also provide numerical evidence for our conjectures. The results generalize to multiplicative subgroups $Γ\subseteq \mathbb F_q^\times$ of bounded index.
