Further evidence towards the Fourier Entropy-Influence conjecture
For researchers in Boolean function analysis, this provides incremental progress on a long-standing conjecture by extending verification to additional function classes.
The paper proves the Fourier Entropy-Influence (FEI) conjecture for new classes of Boolean functions by introducing a key inequality relating entropy differences to influences, and using a stopping binary tree framework. The conjecture is verified for these classes, but no concrete numerical results are provided.
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.