Boolean Functions with small Spectral Norm期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Boolean Functions with small Spectral Norm

Authors:	Ben Green Tom Sanders

Institution:	(1) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WA, England

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. Received: May 2006 Accepted: January 2007

Keywords:	Fourier transform spectral norm L ¹-norm boolean functions structure theorem
本文献已被 SpringerLink 等数据库收录！