Erasure entropies of sparse linear DNFs

For a Boolean function f and a coordinate i, the erasure entropy Eᵢ(f) is the conditional entropy of the event i∈ U given U\, where U is drawn from the spectral distribution f². The Fourier entropy-influence conjecture is equivalent to every non-constant f having a coordinate with Eᵢ(f)=O(Infᵢ(f)). We consider monotone DNFs whose terms all have width w, any two of which share at most one variable, and in which every variable lies in at most D terms. We show that Eᵢ(f)/Infᵢ(f)=2+o(1) at every relevant coordinate, uniformly in the number of variables and terms, as w→∞ with D≤2(1-η)(w-1) for a fixed η>0, and we give an explicit error bound for each w, D and degree of i. The proof rests on a separation inequality valid for every monotone function: if the derivative Dᵢf puts little spectral weight outside a family Ω of sets and the restriction f|xᵢ=0 puts little weight on Ω, then Eᵢ/Infᵢ is close to $2$. For a linear DNF, Ω is the family of sets that contain many of the other variables of some term through i.