Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2210.03789 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909275106836480 |
|---|---|
| author | McDonald, Brian Sahay, Anurag Wyman, Emmett L. |
| author_facet | McDonald, Brian Sahay, Anurag Wyman, Emmett L. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_03789 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The VC-dimension of quadratic residues in finite fields McDonald, Brian Sahay, Anurag Wyman, Emmett L. Combinatorics Number Theory 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. |
| title | The VC-dimension of quadratic residues in finite fields |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2210.03789 |