Arithmetic functions and learning theory

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 ${\mu }_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 $$\text{FR}({\mu }_R)\gg R^{-1\mathrm{/}4-\epsilon }$$ for every $\epsilon >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({\eta }_R)$ containing ${\mu }_R$, where ${\eta }_R\to 0$, requires at least $\mathrm{\Omega }(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.