The Fourier entropy of linear monotone DNFs on few variables
A monotone DNF is linear if any two of its terms share at most one variable. Over all linear monotone DNFs with at most eight relevant variables, of which there are $552{,}251$ isomorphism classes on exactly eight, we determine by exhaustive enumeration with certified logarithms the largest value of the ratio $H(f)/I(f)$ of Fourier entropy to total influence and the largest value of $\min_iE_i(f)/\mathrm{Inf}_i(f)$, where $E_i$ is the erasure entropy at $i$. They are $3.8891054198\ldots$ and $3.3047013224\ldots$, and each is attained by a single class. A transversal design on $21$ variables has $H/I=4.1346\ldots$, so neither value is the supremum over the class. We then give three sufficient conditions for a coordinate with $E_i\le C\,\mathrm{Inf}_i$ in a linear monotone DNF: a load certificate that assumes no bound on widths or degrees, a criterion that involves the loads of the variables of a single term only, and a bound in terms of the bias of $f$. On the affine transversal designs with $k+2\lceil\log_2k\rceil+1$ groups of $2^k$ points each, all of these conditions fail at every coordinate, as do the width and variance bounds of earlier work, while $\Pr[F=0]$ tends to zero more slowly than any exponential in the number of variables.
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.24125383
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint