Bounded Relative Boundary Implies Narrow DNF Approximation

Abstract

Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing that, for $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\epsilon$-close under ${\mu }_p^n$ to a monotone DNF of width $\exp (O((K+1{)}^2/{\epsilon }^2))$. A separate high-bias argument completes the proof for all $p\in (0,1)$. Our proof builds on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)). Tracking Hatami's construction isolates an adaptive representation with increasing local activations and dimension-free arity and multiplicity-counted load bounds. Our main new ingredient is a bias-matched randomized shifting procedure that converts the pseudo-junta approximator into an increasing function while retaining exact measurability with respect to a controlled forced refinement of its adaptive representation. From the resulting monotone adaptive representation, we extract positive certificates and truncate them to obtain the required narrow DNF.