Explicit degree, load, and width budgets for the final approximation
DefinitionNarrowDNF_WidthBoundcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
For a real influence bound and error tolerance , let be the nonnegative-integer ceiling. The final arithmetic budgets are
The explicit absolute constant is , independent of dimension and bias.
These functions are the numerical choices used to combine the activation arity and load bounds, the monotonicization error budget, and certificate truncation. Their intended theorem range is and ; the subsequent arithmetic lemmas state the precise hypotheses needed to compare with . Defining the budgets does not assume or prove the structural existence of the activation family or DNF approximator.
Definition code
import Mathlib.Algebra.Order.Floor.Ring import Mathlib.Analysis.SpecialFunctions.Exp import Mathlib.Tactic.Linarith import Mathlib.Tactic.NormNum import Mathlib.Tactic.Positivity import Mathlib.Tactic.Ring namespace NarrowDNF.WidthBound end NarrowDNF.WidthBound /-! # Explicit width and error-budget arithmetic These are the final arithmetic estimates in the proof of Theorem 1.2 of the 2026-11-06 STOC revision. The source's numerical constants are retained. This module does not assume or assert the structural theorem supplying the approximator and activation family. -/ noncomputable section namespace NarrowDNF.WidthBound def influenceCeil (K : ℝ) : ℕ := Nat.ceil K def degree (K ε : ℝ) : ℕ := Nat.ceil (4000 * (influenceCeil K : ℝ) / ε) def loadBound (K ε : ℝ) : ℝ := Real.exp (160000000000 * (influenceCeil K : ℝ)^2 / ε^2) def width (K ε : ℝ) : ℕ := Nat.ceil (4 * (2 : ℝ)^(degree K ε) * loadBound K ε / ε) /-- One explicit absolute constant; no dependence on dimension or bias. -/ def absoluteConstant : ℝ := 10000000000000 end NarrowDNF.WidthBound
Source