cost_final (KFZ CostR: the chirp procedure cost against `cLineU`)
ProvedNLogN.KFZ.cost_finalThe following holds (Lean statement, in the scope of module Solutions.KFZCostR):
theorem NLogN.KFZ.cost_final (C18 : ℝ) (hC18 : 0 ≤ C18) (A18 c18 : ℕ)
(hc : (c18 : ℝ) ≤ C18 * (((tsN n).prod * IntMul.OpenAI.Glue.rP n * (pP n + 3) : ℕ) : ℝ) *
Ncost (6 * (lg n : ℝ)) (IntMul.OpenAI.Glue.dP n) (KP n) (ℓP n) (αP n) *
(Real.log (6 * (lg n : ℝ)) + 1) ^ A18) :
((c18 + NLogN.KFZ.cBody (NLogN.KFZ.BN n) (NLogN.KFZ.BN n) (bP n) (desc18 (pP n) (ℓP n) (KP n) (tsN n)).length (pP n) (NLogN.KFZ.hN n)
D (σN n) (sBD n D) (tBD n D) + 2 : ℕ) : ℝ) ≤ (2 * C18 + Kc) * cLineU n (A18 + 2)
Context. The lemma belongs to the part KFZ CostR: the chirp procedure cost against cLineU.
Formalization Note. This lemma belongs to layer 5 of the Lean formalization (integer-multiplication-kappa campaign) of the OpenAI preprint Integer multiplication below : the uniform item-language machine (register programs over the NLogN multitape framework) assembling the Proposition 14 / Lemma 13 / Proposition 18 pieces, the resampling and chirp stages and the cost recurrences into one fixed machine, culminating in NLogN.KFTop.kappa_bound : IntMul.KappaBound (1 / 2 ^ 182) (the bound of Def_IntMul_MultitapeModel). All names refer to the definition bundles up to IntMul_Kappa_K_Defs33.
-- OpenAI-preprint / κ-improvement development (integer-multiplication-kappa), generated by skeleton subtraction.
import Definitions.Def_IntMul_Kappa_K_Defs33
set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000
set_option autoImplicit false
set_option linter.unusedSimpArgs false
set_option linter.unusedVariables false
set_option linter.unusedSectionVars false
open NLogN
open NLogN.KFZ
open IntMul NLogN.KIL KFB NLogN.KFM IntMul.OpenAI.Glue IntMul.OpenAI.RCost
attribute [local irreducible] fmA Cfm
variable {n D : ℕ} (hn : n0 ≤ n) (hD : dP n = D + 1)
include hn hD
theorem NLogN.KFZ.cost_final (C18 : ℝ) (hC18 : 0 ≤ C18) (A18 c18 : ℕ)
(hc : (c18 : ℝ) ≤ C18 * (((tsN n).prod * IntMul.OpenAI.Glue.rP n * (pP n + 3) : ℕ) : ℝ) *
Ncost (6 * (lg n : ℝ)) (IntMul.OpenAI.Glue.dP n) (KP n) (ℓP n) (αP n) *
(Real.log (6 * (lg n : ℝ)) + 1) ^ A18) :
((c18 + NLogN.KFZ.cBody (NLogN.KFZ.BN n) (NLogN.KFZ.BN n) (bP n) (desc18 (pP n) (ℓP n) (KP n) (tsN n)).length (pP n) (NLogN.KFZ.hN n)
D (σN n) (sBD n D) (tBD n D) + 2 : ℕ) : ℝ) ≤ (2 * C18 + Kc) * cLineU n (A18 + 2) := by sorry