Boolean Functions with Small Approximate Spectral Norm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909408327368704 |
|---|---|
| author | Cheung, Tsun-Ming Hatami, Hamed Zhao, Rosie Zilberstein, Itai |
| author_facet | Cheung, Tsun-Ming Hatami, Hamed Zhao, Rosie Zilberstein, Itai |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10634 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Boolean Functions with Small Approximate Spectral Norm Cheung, Tsun-Ming Hatami, Hamed Zhao, Rosie Zilberstein, Itai Discrete Mathematics Combinatorics 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$. |
| title | Boolean Functions with Small Approximate Spectral Norm |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.10634 |