The erasure entropy of a forced coordinate under every bias
A monotone Boolean function $F_{k,t}$, built from a majority function on $k$ inputs with one hidden coordinate $x$ by substituting threshold functions of $2t$ fresh variables, has $x$ as the only variable lying both in a shortest minterm and in a shortest maxterm. The ratio $E_x/\mathrm{Inf}_x$ of the erasure entropy to the influence at $x$ was known to be unbounded when $k$ and $t$ grow together, and to grow linearly in $k$ for $t=1$. We show that for every fixed $t\ge1$ it equals $(1+o(1))\log_2(1/\mathrm{Inf}_x)=(1+o(1))(k-1)\log_2(1/P_t)$, where $P_t$ is the probability that a binomial variable with parameters $2t$ and $\frac12$ is at least $t$. More generally the same holds for the underlying majority function under every rational product bias $P\in(\frac12,1)$, the phase of the relevant coefficients advancing by $\arccos\frac{2P-1}{2P}$, an irrational multiple of $\pi$. At $P=\frac12$ that angle is $\frac\pi2$, and the behaviour changes: there the coefficients are values of Krawtchouk polynomials at the middle of their range, half of them vanish, and the ratio is $\frac12\log_2(1/\mathrm{Inf}_x)-\frac12\log_2\log_2(1/\mathrm{Inf}_x)+O(1)$, which we derive from an exact single-sum formula.
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.24127682
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint