On (not) computing the Mobius function using bounded depth circuits

2011/03/25 by Ben Green, Green, Ben
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.NT

paper · pdf · doi:10.48550/arxiv.1103.4991

10 pages, to appear in Combinatorics, Probability and Computing. A few further small corrections

openalex publication_date 2011/03/25 · arxiv created 2012/06/01 · arxiv updated 2012/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Any function F : 0,...,N-1 -> -1,1 such that F(x) can be computed from the binary digits of x using a bounded depth circuit is orthogonal to the Mobius function mu in the sense that E_{0 <= x <= N-1} mu(x)F(x) = o(1). The proof combines a result of Linial, Mansour and Nisan with techniques of Katai and Harman-Katai, used in their work on finding primes with specified digits.

Related

• Orthogonality of the Möbius function to polynomials with applications to Linear Equations in Primes over \mathbbF_p[x]
• Quadratic Uniformity of the Mobius Function
• Möbius orthogonality for q-semimultiplicative sequences
• An Elementary Proof of the Prime Number Theorem based on Möbius Function
• On a family of arithmetic series related to the Möbius function