On the Fourier-Walsh Spectrum on the Moebius Function

Abstract

We study the Fourier-Walsh spectrum $\{\hat{\mu }(S);S\subset \{1,...,n\}\}$ of the Moebius function $\mu$ restricted to $\{0,1,2,...,2^n-1\}\simeq \{0,1{\}}^n$ and prove that it is not captued by levels \{\hatμ(S)| \, |S|< n^{\frac 23-\epsion}\}. An application to correlation with monotone Boelean functions is given.

References in corpus (2)

• Moebius-Walsh correlation bounds and an estimate of Mauduit and Rivat
• On (not) computing the Mobius function using bounded depth circuits

Cited by in corpus (1)

• Monotone Boolean functions capture their primes