Boolean Functions with Small Approximate Spectral Norm
<|reference_start|>Boolean Functions with Small Approximate Spectral Norm: The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of $f$ belongs to the ring of sets generated by at most $\ell(M)$ cosets, where $\ell(M)$ is a constant that only depends on $M$.   We prove that the above statement can be generalized to \emph{approximate} spectral norms if and only if the support of $f$ and its complement satisfy a certain arithmetic connectivity condition. In particular, our theorem provides a new proof of the quantitative Cohen's theorem for $\mathbb{F}_2^n$.<|reference_end|>
@article{cheung2024boolean,
    title={Boolean Functions with Small Approximate Spectral Norm},
    author={Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein},
    journal={arXiv preprint arXiv:2409.10634},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.10634},
    primaryClass={cs.DM math.CO}
}