Abstract.
Let \(f : {\mathbb{F}}^{n}_{2} \rightarrow \{0, 1\}\) be a boolean function, and suppose that the spectral norm \(\|f\|_{A} := \sum_{r} \mid \widehat{f}(r)\mid\) of f is at most M. Then \(\mathop {f = \sum\limits^{L}_{j=1}\pm 1_{{H}_{j}}},\) where \(L \leq 2^{{{2}^{CM}}^{4}}\) and each H j is a subgroup of \({\mathbb{F}}^{n}_{2}\) . This result may be regarded as a quantitative analogue of the Cohen-Helson-Rudin structure theorem for idempotent measures in locally compact abelian groups.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author is a Clay Research Fellow, and thanks the Clay Mathematics Institute for their support. Much of this work was conducted while the second author was on a CMI-funded visit to Boston, and he thanks the first author for arranging this and the CMI for its support. Both authors would also like to thank the Massachusetts Institute of Technology for their hospitality.
Received: May 2006 Accepted: January 2007
Rights and permissions
About this article
Cite this article
Green, B., Sanders, T. Boolean Functions with small Spectral Norm. GAFA Geom. funct. anal. 18, 144–162 (2008). https://doi.org/10.1007/s00039-008-0654-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00039-008-0654-y