On the distribution of the Fourier spectrum of Boolean functions
type: Item
instance of: scholarly article
title: On the distribution of the Fourier spectrum of Boolean functions
zbMATH Open document ID: 1021.43004
DOI: 10.1007/BF02785861
published in: Israel Journal of Mathematics
publication date: 2003-01-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 43A75
Mathematics Subject Classification ID: 42C10
Mathematics Subject Classification ID: 42A38
zbMATH DE Number: 1850613
zbMATH Keywords: Fourier spectrum
zbMATH Keywords: Fourier analysis
zbMATH Keywords: Boolean functions
author: Jean Bourgain
reviewed by: Gabriele Steidl
MaRDI profile type: Publication
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Q4103446
description: scientific article; zbMATH DE number 1850613