Arithmetic functions and learning theory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913037065125888 |
|---|---|
| author | Burstein, W. Iosevich, A. Sant, A. |
| author_facet | Burstein, W. Iosevich, A. Sant, A. |
| contents | We establish a connection between analytic number theory and computational learning theory by showing that the Möbius function belongs to a class of functions that is statistically hard to learn from random samples. Let $μ_R$ denote the restriction of the Möbius function to the squarefree integers in $\{1,\dots,R\}$. Using a recent lower bound of Pandey and Radziwiłł for the $L^1$ norm of exponential sums with Möbius coefficients, we prove that \[ \FR(μ_R) \gg R^{-1/4-ε} \] for every $ε>0$. We then show that, for a suitable absolute constant $c_0>0$, the class of $\{-1,1\}$-valued functions on the squarefree integers with Fourier Ratio at least $c_0$ has Vapnik--Chervonenkis dimension at least $cR$. It follows that any distribution-independent learning algorithm that succeeds uniformly on the class $\mathcal{H}_R(η_R)$ containing $μ_R$, where $η_R \to 0$, requires at least $Ω(R)$ samples. We also discuss a conditional improvement under a strong uniform bound for additive twists of the Möbius function, and we note that the same method applies to the Liouville function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14482 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Arithmetic functions and learning theory Burstein, W. Iosevich, A. Sant, A. Number Theory Classical Analysis and ODEs Statistics Theory 42B10, 42B05, 58J51, 35P20, 68Q32 We establish a connection between analytic number theory and computational learning theory by showing that the Möbius function belongs to a class of functions that is statistically hard to learn from random samples. Let $μ_R$ denote the restriction of the Möbius function to the squarefree integers in $\{1,\dots,R\}$. Using a recent lower bound of Pandey and Radziwiłł for the $L^1$ norm of exponential sums with Möbius coefficients, we prove that \[ \FR(μ_R) \gg R^{-1/4-ε} \] for every $ε>0$. We then show that, for a suitable absolute constant $c_0>0$, the class of $\{-1,1\}$-valued functions on the squarefree integers with Fourier Ratio at least $c_0$ has Vapnik--Chervonenkis dimension at least $cR$. It follows that any distribution-independent learning algorithm that succeeds uniformly on the class $\mathcal{H}_R(η_R)$ containing $μ_R$, where $η_R \to 0$, requires at least $Ω(R)$ samples. We also discuss a conditional improvement under a strong uniform bound for additive twists of the Möbius function, and we note that the same method applies to the Liouville function. |
| title | Arithmetic functions and learning theory |
| topic | Number Theory Classical Analysis and ODEs Statistics Theory 42B10, 42B05, 58J51, 35P20, 68Q32 |
| url | https://arxiv.org/abs/2604.14482 |