Crude depth guard, natural-number form
ProvedR6.crude_guard_natcomplexity-theoryinteger-multiplicationkappa-improvement
Let with , , , and . If satisfies the crude-guard recursion (at most children with and for , and for ), then for all
In Lean:
theorem R6.crude_guard_nat (E s m d C1 : ℕ) (β : ℝ) (A : ℕ → ℕ) (hm : 2 ≤ m) (hs : 2 ≤ s)
(hβ : 0 ≤ β ∧ β ≤ 1) (hd : 1 ≤ d) (hC1 : 2 + m * Real.log s ≤ C1)
(hrec : ∀ e : ℕ, (d : ℝ) ^ β ≤ e → ∃ cs : List ℕ, cs.length ≤ s ∧
(∀ c ∈ cs, m * c ≤ (m - 1) * e) ∧ A e ≤ E + (cs.map A).sum)
(hleaf : ∀ e : ℕ, (e : ℝ) < (d : ℝ) ^ β → (A e : ℝ) ≤ 8 * (d : ℝ) ^ β) :
∀ e : ℕ, e ≤ d → A e ≤ 2 * s * (E + 8) * d ^ C1
Formalization Note. Part of the Lean formalization of the round-six κ-improvement (integer-multiplication-kappa campaign, target IntMul.Kappa.jain_round6_framework). The statement is copied verbatim from the Lean development; the platform node carries the same declaration name. Definitions it mentions live in the IntMul_Kappa_R6_Defs* bundles (on top of the published κ bundles IntMul_Kappa_K_Defs*).
Preamble
-- Round-six κ development (integer-multiplication-kappa), generated by skeleton subtraction. import Mathlib set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 open Real
Formal statement
theorem R6.crude_guard_nat (E s m d C1 : ℕ) (β : ℝ) (A : ℕ → ℕ) (hm : 2 ≤ m) (hs : 2 ≤ s)
(hβ : 0 ≤ β ∧ β ≤ 1) (hd : 1 ≤ d) (hC1 : 2 + m * Real.log s ≤ C1)
(hrec : ∀ e : ℕ, (d : ℝ) ^ β ≤ e → ∃ cs : List ℕ, cs.length ≤ s ∧
(∀ c ∈ cs, m * c ≤ (m - 1) * e) ∧ A e ≤ E + (cs.map A).sum)
(hleaf : ∀ e : ℕ, (e : ℝ) < (d : ℝ) ^ β → (A e : ℝ) ≤ 8 * (d : ℝ) ^ β) :
∀ e : ℕ, e ≤ d → A e ≤ 2 * s * (E + 8) * d ^ C1 := by sorrySource
S. Jain, round-six networks for the integer-multiplication κ-improvement campaign (https://github.com/Swapnil-jain/integer-mult-kappa, commit 5868dc7) and D. Colkitt, integer-mult-bounds (https://github.com/CrocSwap/integer-mult-bounds); target `IntMul.Kappa.jain_round6_framework`. Lean declaration `R6.crude_guard_nat`, Solutions/R6Guard.lean (lines 223–239) of the round-six development.