← All papers
First page of Bounded Relative Boundary Implies Narrow DNF Approximation

Bounded Relative Boundary Implies Narrow DNF Approximation

Chenghua Liu, Boning Meng

cs.CC Aug 31, 2026 · v2 cs.DM
The authors, with AI assistance, completed a Lean formalization of their proofs of the main DNF approximation theorem and Friedgut's conjecture.
We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

Friedgut conjectured in 1999 that every increasing family in the p-biased discrete cube with bounded relative boundary can be approximated by a family whose minimal elements have size bounded independently of the dimension and the bias. Hatami's pseudo-junta theorem gives an adaptive approximation, but its approximator need not be increasing.

Starting from Hatami's construction, made explicit with arity and activation-load bounds, the authors apply randomized bias-matched coordinate shifts. These choose an upper or lower shift with probabilities 1-p and p, which makes the approximator increasing without increasing the expected error. The result stays measurable with respect to a controlled refinement of Hatami's adaptive partition. Active 1-coordinates then form positive certificates, and keeping only the short certificates gives a monotone DNF. The proofs were formalized in Lean.

For 0<p≤1/2, every increasing Boolean function with total resampling influence at most K is ε-close under μ_p^n to a monotone DNF of width exp(O((K+1)^2/ε^2)). The full Friedgut conjecture follows for all p in (0,1).