Further evidence towards the Fourier Entropy-Influence conjecture
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913174837526528 |
|---|---|
| author | González, María José MacManus, Paul Pereyra, María Cristina |
| author_facet | González, María José MacManus, Paul Pereyra, María Cristina |
| contents | The Fourier Entropy-Influence (FEI) conjecture states that the Fourier entropy of Boolean functions is uniformly bounded by their total influence. It has been verified for canonical examples such as disjoint tribes and for some classes of Boolean functions such as symmetric functions and read-$k$ decision trees (with a constant that depends linearly on $k$). In this note we present new classes of Boolean functions that verify the FEI conjecture. The key element is an inequality controlling the difference between the entropy of a function $f$ and the average of the entropies of $f^{\pm}$, the sub-functions obtained by setting $x_m=\pm1$ for some $m$, by the $m$-influence of $f$. If this key inequality were to hold for Boolean functions, then the full FEI conjecture would follow by induction. We introduce the notion of a stopping binary tree and observe that functions that satisfy the key inequality at the branching nodes of the tree and the FEI conjecture at the stopping nodes will satisfy the FEI conjecture. We identify some classes of functions that fit this framework and, along the way, demonstrate some results that we hope the experts in this fascinating field might find useful. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00246 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Further evidence towards the Fourier Entropy-Influence conjecture González, María José MacManus, Paul Pereyra, María Cristina Combinatorics Discrete Mathematics Classical Analysis and ODEs 94D10 94A17 43A75 The Fourier Entropy-Influence (FEI) conjecture states that the Fourier entropy of Boolean functions is uniformly bounded by their total influence. It has been verified for canonical examples such as disjoint tribes and for some classes of Boolean functions such as symmetric functions and read-$k$ decision trees (with a constant that depends linearly on $k$). In this note we present new classes of Boolean functions that verify the FEI conjecture. The key element is an inequality controlling the difference between the entropy of a function $f$ and the average of the entropies of $f^{\pm}$, the sub-functions obtained by setting $x_m=\pm1$ for some $m$, by the $m$-influence of $f$. If this key inequality were to hold for Boolean functions, then the full FEI conjecture would follow by induction. We introduce the notion of a stopping binary tree and observe that functions that satisfy the key inequality at the branching nodes of the tree and the FEI conjecture at the stopping nodes will satisfy the FEI conjecture. We identify some classes of functions that fit this framework and, along the way, demonstrate some results that we hope the experts in this fascinating field might find useful. |
| title | Further evidence towards the Fourier Entropy-Influence conjecture |
| topic | Combinatorics Discrete Mathematics Classical Analysis and ODEs 94D10 94A17 43A75 |
| url | https://arxiv.org/abs/2606.00246 |