A Lower Bound for the Fourier Entropy of Boolean Functions on the Biased Hypercube
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914387311198208 |
|---|---|
| author | Chang, Fan |
| author_facet | Chang, Fan |
| contents | We study Boolean functions on the $p$-biased hypercube $(\{0,1\}^n,μ_p^n)$ through the lens of Fourier (spectral) entropy, i.e. the Shannon entropy of the squared $p$-biased Fourier coefficients. Motivated by recent restriction-based advances on upper bounds toward the Fourier-Entropy-Influence (FEI) conjecture, we prove a complementary, sharp lower bound that decomposes the entropy into coordinate-wise contributions. Let $q:=4p(1-p)$ and define $Ψ:[0,\tfrac12]\to[0,\ln 2]$ by $Ψ(t):=h\left(\frac{1+\sqrt{1-4t^2}}{2}\right)$, where $h(u):=-u\ln u-(1-u)\ln(1-u)$. We show that for every Boolean $f:(\{0,1\}^n,μ_p^n)\to\{\pm1\}$, $$ \mathrm{Ent}_p(f) \ge \sum_{k=1}^n Ψ\left(\sqrt{q(1-q)}\cdot\mathrm{Inf}_k^{(p)}[f]\right). $$ When $p\neq \tfrac12$, this bound is tight and equality holds if and only if $f$ is a parity function. Our proof adapts the restriction-moment framework to the biased cube. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07739 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Lower Bound for the Fourier Entropy of Boolean Functions on the Biased Hypercube Chang, Fan Combinatorics Functional Analysis 06E30, 42C10, 60C05 We study Boolean functions on the $p$-biased hypercube $(\{0,1\}^n,μ_p^n)$ through the lens of Fourier (spectral) entropy, i.e. the Shannon entropy of the squared $p$-biased Fourier coefficients. Motivated by recent restriction-based advances on upper bounds toward the Fourier-Entropy-Influence (FEI) conjecture, we prove a complementary, sharp lower bound that decomposes the entropy into coordinate-wise contributions. Let $q:=4p(1-p)$ and define $Ψ:[0,\tfrac12]\to[0,\ln 2]$ by $Ψ(t):=h\left(\frac{1+\sqrt{1-4t^2}}{2}\right)$, where $h(u):=-u\ln u-(1-u)\ln(1-u)$. We show that for every Boolean $f:(\{0,1\}^n,μ_p^n)\to\{\pm1\}$, $$ \mathrm{Ent}_p(f) \ge \sum_{k=1}^n Ψ\left(\sqrt{q(1-q)}\cdot\mathrm{Inf}_k^{(p)}[f]\right). $$ When $p\neq \tfrac12$, this bound is tight and equality holds if and only if $f$ is a parity function. Our proof adapts the restriction-moment framework to the biased cube. |
| title | A Lower Bound for the Fourier Entropy of Boolean Functions on the Biased Hypercube |
| topic | Combinatorics Functional Analysis 06E30, 42C10, 60C05 |
| url | https://arxiv.org/abs/2511.07739 |