Theorem 1.2: uniform narrow monotone DNF approximation at low bias
ProvedNarrowDNF.main_narrow_dnfcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
There exists an absolute constant , independent of every subsequent parameter, such that for every , , , and , every monotone Boolean function on with total resampling influence has a positive DNF satisfying
Here , where is product Bernoulli and an independent Bernoulli bit. The construction admits .
Preamble
import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.GroupWithZero.Finset import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Algebra.Order.BigOperators.Ring.Finset import Mathlib.Algebra.Order.Floor.Ring import Mathlib.Analysis.MeanInequalities import Mathlib.Analysis.SpecialFunctions.Exp import Mathlib.Analysis.SpecialFunctions.Log.Basic import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Data.Bool.Basic import Mathlib.Data.Finset.Card import Mathlib.Data.Finset.Image import Mathlib.Data.Finset.Insert import Mathlib.Data.Finset.Lattice.Fold import Mathlib.Data.Finset.Powerset import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Option import Mathlib.Data.Fintype.Pi import Mathlib.Data.Fintype.Powerset import Mathlib.Data.Nat.Choose.Bounds import Mathlib.Data.Real.Basic import Mathlib.Data.Real.Sqrt import Mathlib.Logic.Equiv.Prod import Mathlib.Order.Monotone.Basic import Mathlib.Tactic import Mathlib.Tactic.FieldSimp import Mathlib.Tactic.GCongr import Mathlib.Tactic.Linarith import Mathlib.Tactic.NormNum import Mathlib.Tactic.NormNum.RealSqrt import Mathlib.Tactic.Positivity import Mathlib.Tactic.Ring import Definitions.Def_NarrowDNF_MainStatements import Theorems.Thm_NarrowDNF_HatamiInput_hatami_arity_load import Theorems.Thm_NarrowDNF_narrowDNF_of_hatami namespace NarrowDNF end NarrowDNF open NarrowDNF
Formal statement
theorem NarrowDNF.main_narrow_dnf : NarrowDNFApproximation := by sorry
Source