Theorem 1.2 — Narrow-DNF approximation
ProvedNarrowDNF.Approx.theorem_1_2combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
There is an absolute real constant such that, for every integer , every , every , every , and every coordinatewise increasing Boolean function satisfying , there is a finite monotone DNF such that
The constant is chosen before the dimension, influence bound, bias, tolerance and function. Influence is independent-coordinate resampling influence, and disagreement is the two-sided error under the actual product law. There is no mean, symmetry, Fourier-degree or term-count restriction. Both constant functions have width-zero witnesses.
This is the dimension- and low-bias-uniform approximation result; it asserts existence without an efficient-construction claim.
Differences from the source:
- encoding: coordinates [n] and bits {0,1} → Fin n and Bool with pointwise false < true; reason: coordinate relabeling preserves all source instances
- encoding: product probabilities and expectations → published Bernoulli event sums and exact real finite weighted sums; reason: the finite product law is identical and every cost is integrable
- encoding: a monotone DNF with bounded width → a finite set of positive coordinate terms, its actual evaluation, and a real bound on its natural syntactic width; reason: every finite source DNF has the same representation after deleting duplicate terms, and every such witness is a source DNF
Preamble
import Definitions.Def_NarrowDNF_Approx_DNF
Formal statement
namespace NarrowDNF.Approx
theorem theorem_1_2 :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 1 ≤ n → ∀ K : ℝ, 0 < K →
∀ p : ℝ, 0 < p → p ≤ 1 / 2 → ∀ ε : ℝ, 0 < ε → ε < 1 →
∀ f : Cube n → Bool, Monotone f → FriedgutCoalition.totalPInfl p f ≤ K →
∃ g : DNF n, (width g : ℝ) ≤ Real.exp (C * (K + 1) ^ 2 / ε ^ 2) ∧
error p f (evalDNF g) ≤ ε := by sorry
end NarrowDNF.Approx
Source
Chenghua Liu, Boning Meng, STOC 2027 submission #1509 (October 2026), Theorem 1.2, p. 2 (PDF p. 3); proof p. 9 (PDF p. 10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.