On (Not) Computing the Möbius Function Using Bounded Depth Circuits

Source 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 Möbius function μ in the sense that \[ \frac{1}{N} \sum_{0 \leq x \leq N-1} \mu(x)F(x) → 0 \quad\text{as}~~ N → \infty. \] The proof combines a result of Linial, Mansour and Nisan with techniques of Kátai and Harman, used in their work on finding primes with specified digits.