Absorbing an integer ceiling and width prefactor into an exponential
ProvedNarrowDNF.WidthBound.ceil_width_le_expcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
For every , , and integer ,
The ceiling is the nonnegative-integer ceiling, viewed as a real number. This estimate preserves the explicit width chosen by the certificate construction while replacing its prefactor, power of two, and rounding term by a single exponential. It does not require an upper bound on .
Preamble
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 noncomputable section open NarrowDNF open NarrowDNF.WidthBound
Formal statement
theorem NarrowDNF.WidthBound.ceil_width_le_exp {ε a : ℝ} (hε : 0 < ε) (ha : 0 ≤ a) (d : ℕ) :
(Nat.ceil (4 * (2 : ℝ)^d * Real.exp a / ε) : ℝ) ≤
Real.exp (4 / ε + (d : ℝ) + a) := by sorrySource