The Hatami arity-and-load theorem implies the low-bias narrow-DNF theorem
ProvedNarrowDNF.narrowDNF_of_hatamicombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Assume the following structural assertion. For each , , Boolean , and , put , where is total resampling influence. There are an increasing activation family and a -measurable Boolean with error at most , activation arity at most , and load at most . Then, for every , , , , and monotone with , there is a positive DNF such that
Preamble
import Mathlib.Algebra.BigOperators.Group.Finset.Basic 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.SpecialFunctions.Exp 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.Fintype.BigOperators import Mathlib.Data.Fintype.Pi import Mathlib.Data.Real.Basic import Mathlib.Logic.Equiv.Prod import Mathlib.Order.Monotone.Basic import Mathlib.Tactic.GCongr import Mathlib.Tactic.Linarith import Mathlib.Tactic.NormNum import Mathlib.Tactic.Positivity import Mathlib.Tactic.Ring import Definitions.Def_NarrowDNF_ActivationLoad import Definitions.Def_NarrowDNF_Adaptive import Definitions.Def_NarrowDNF_CertificateBounds import Definitions.Def_NarrowDNF_Certificates import Definitions.Def_NarrowDNF_CoordinateShift import Definitions.Def_NarrowDNF_Influence import Definitions.Def_NarrowDNF_MainStatements import Definitions.Def_NarrowDNF_ProductMeasure import Definitions.Def_NarrowDNF_ShiftProbability import Definitions.Def_NarrowDNF_WidthBound import Theorems.Thm_NarrowDNF_WidthBound_width_le_exponential import Theorems.Thm_NarrowDNF_adaptive_approximation_to_dnf namespace NarrowDNF end NarrowDNF namespace NarrowDNF.Activation end NarrowDNF.Activation namespace NarrowDNF.FiberShift end NarrowDNF.FiberShift namespace NarrowDNF.Influence end NarrowDNF.Influence namespace NarrowDNF.ProductMeasure end NarrowDNF.ProductMeasure namespace NarrowDNF.ShiftProbability end NarrowDNF.ShiftProbability namespace NarrowDNF.WidthBound end NarrowDNF.WidthBound noncomputable section open NarrowDNF
Formal statement
theorem NarrowDNF.narrowDNF_of_hatami (hHatami : HatamiArityLoad) : NarrowDNFApproximation := by sorry
Source