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

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 \[ 1/N ∑0 ≤ x ≤ N-1 μ(x)F(x) → 0 ~~ N → ∞. \] 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.