A filtration bound for the erasure entropies of Boolean functions
For a Boolean function $f$ and a coordinate $i$, the erasure entropy $E_i(f)$ is the conditional entropy of the event $i\in U$ given $U\setminus\{i\}$, where $U$ is drawn from the spectral distribution $\hat f^2$. The Fourier entropy-influence conjecture is equivalent to the existence of an absolute $c$ such that every non-constant $f$ has a coordinate with $E_i(f)\le c\,\mathrm{Inf}_i(f)$. We bound $E_i$ from above by revealing the other coordinates one at a time and conditioning only on the last revealed coordinate that the spectral sample contains. The resulting quantity $L^\pi_i$ depends on the order $\pi$, is a sum, over the steps, of a two-variable entropy of the squared increments of the Doob martingales of $E_if$ and $D_if$, lies between $E_i$ and the binary entropy of $\mathrm{Inf}_i$, and can be minimised over all orders by a shortest-path recursion. We show that $L^\pi_i=O(\mathrm{Inf}_i)$ whenever, along the order, the probability that $i$ is pivotal both before and after the not yet revealed coordinates are resampled, times the block influence of those coordinates, is $O(\mathrm{Inf}_i^2)$. We also give an exact formula for $E_i$ under block composition, and show that a coordinate whose variable enters only through one AND of $k+1$ variables, pivotal with probability $\rho$, has $L^\pi_i/\mathrm{Inf}_i\le2+2^{-k}(2k+\log_2(1/\rho))$ for a suitable order. Conditioning on the last $r$ revealed coordinates gives a decreasing family of bounds that reaches $E_i$ at $r=n-1$.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-11
- DOI
- https://doi.org/10.5281/zenodo.24125388
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint