On the distribution of the Fourier spectrum of Boolean functions (Q1852725)

The paper is concerned with the Fourier analysis of Boolean functions. A general philosophy claims that if \(f\) defines a property of ``high complexity'', then \(\text{supp} \widehat f\) has to ``spread out''. The author illustrates this phenomenon by proving the following theorem: Let \(f= \chi_A\), \(A\subset \{-1,1\}^N\). Let \(k\in\mathbb{N}\) and \(\gamma>0\) be a fixed constant so that \(\sum_{|\widehat f(s)|<\gamma 4^{-k^2}} |\widehat f(s) |^2 >\gamma^2\), then \(\sum_{|s|> k}|\widehat f(s)|^2 \gg c_\varepsilon k^{-{1\over 2}- \varepsilon}\) for all \(\varepsilon >0\). The example of the majority function shows that this result is basically optimal.