Read-once formulas and a question of Han on the Fourier entropy-influence conjecture
For a Boolean function $f$ and a coordinate $k$, let $Q_k(f)=\sum_{S\not\ni k}|\hat f(S)\hat f(S\cup\{k\})|/I_k(f)$, where $I_k(f)$ is the influence of $k$. In his proof of a new bound towards the Fourier entropy-influence conjecture, Han asked whether there is a universal constant $c$ such that every Boolean function has a coordinate $k$ with $Q_k(f)\le c$, and observed that this would imply the conjecture. We show that the answer is negative. For balanced alternating read-once AND-OR formulas we compute $Q_k$ exactly by a one-step recursion over the levels of the formula; it is the same at every coordinate. Choosing the fan-ins so that every gate below the root is true with probability at most $1/4$ gives monotone read-once formulas of depth $L$ on at most $2\cdot 7^{L-1}$ variables with $Q_k(f)\ge L$ for every $k$, so $\min_k Q_k(f)$ grows at least like $\log_2 n/\log_2 7$. Depth two gives the tribes functions, for which $\min_k Q_k$ approaches $4$ but stays below it. The Fourier entropy-influence conjecture is known for these formulas, so the inequality in Han's question fails on a class where the conjecture holds. By contrast, the drop of the Fourier entropy under splitting on a coordinate is less than $5+\ln 4$ times the influence of that coordinate, for every read-once formula and every coordinate.
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-08
- DOI
- https://doi.org/10.5281/zenodo.24064348
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint