On (not) learning the Möbius function
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908993492877312 |
|---|---|
| author | Pozdnyakov, Alexey |
| author_facet | Pozdnyakov, Alexey |
| contents | We prove lower bounds on learning the Möbius 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öbius 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23427 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On (not) learning the Möbius function Pozdnyakov, Alexey Number Theory Machine Learning We prove lower bounds on learning the Möbius 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öbius 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. |
| title | On (not) learning the Möbius function |
| topic | Number Theory Machine Learning |
| url | https://arxiv.org/abs/2604.23427 |