# On (not) learning the M"obius function

arXiv: https://arxiv.org/abs/2604.23427 · HTML: https://mlsanity.com/paper/2604.23427/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 27 references that are in the map.
- First posted on arXiv 25 Apr 2026.

## Builds on (most cited first, 5 of 5)

- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Studying number theory with deep learning: a case study with the M"obius and squarefree indicator functions](https://mlsanity.com/paper/2502.10335/) (2025)

## Abstract (arXiv)

We prove lower bounds on learning the M"obius or Liouville function with a variety of standard learning techniques, including kernel methods, noisy gradient methods, and correlational statistical query algorithms. These results follow from quantitative bounds on the correlation of M"obius with digital characters of various finite abelian groups, where the group is dictated by the type of input data the algorithm is given. Using residues mod p for many different primes corresponds to a cyclic group, and using the base p expansion for a fixed prime corresponds to an elementary abelian p-group. We also note that lower bounds of this form are closely related to certain types of digital prime number theorems.