HvdH machine lemma CR.stC_cost (Parameter computation, part 5: costs of stages B–D and of `parP` (name)
ProvedNLogN.CR.stC_costThe following holds (Lean statement, in the scope of module NLogN.HCrPar5):
theorem NLogN.CR.stC_cost (K e : ℕ) (hK : 1 ≤ K) (he : 1 ≤ e) (t : IState HS) (LR LH : List Item)
(hR : t.G hRr = .int ((2 ^ e : ℕ) : ℤ) :: LR) (hH : t.G hRh = .int ((2 ^ (e - 1) : ℕ) : ℤ) :: LH)
(B : ℕ) (hV : 2 * (facN K).factorial * facN K + 8 * K * copQ K (2 ^ e) + 4 * K * 2 ^ e + 8 * K + 8
< 2 ^ B) :
(stC K).cost t ≤ (facN K + 20) * 10 ^ 9 * (B + 2) ^ 2
Context. The lemma belongs to the part Parameter computation, part 5: costs of stages B–D and of parP (namespace NLogN.CR).
Formalization Note. This is a lemma of the Lean development NLogN, a multitape-Turing-machine implementation of the Harvey–van der Hoeven integer multiplication algorithm, used in the proof of NLogN.FIN.theorem_1_1_nlogn : IntMul.MulTimeBound fun n => n * Real.log n. All names refer to the definition bundles IntMul_HvdH_M_Defs1–IntMul_HvdH_M_Defs8 (namespace NLogN), built on the platform model Def_IntMul_MultitapeModel and the published reference Def_IntMul_HvdH_MachineRef. The machine layer: IState HS is a state of 64 item stacks; RM programs have a semantics p.run s, a definedness predicate p.ok M s and a cost p.cost M s relative to a multiplication spec M : MulSpec; zsz z is the bit length of .
-- Harvey–van der Hoeven multitape-TM development (NLogN), generated by skeleton subtraction. import Definitions.Def_IntMul_HvdH_M_Defs8 set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 set_option linter.unusedSimpArgs false set_option linter.unusedVariables false open NLogN open NLogN.CR open IntMul RS IntMul.HvdH IntMul.HvdH.Ref set_option maxHeartbeats 4000000
theorem NLogN.CR.stC_cost (K e : ℕ) (hK : 1 ≤ K) (he : 1 ≤ e) (t : IState HS) (LR LH : List Item)
(hR : t.G hRr = .int ((2 ^ e : ℕ) : ℤ) :: LR) (hH : t.G hRh = .int ((2 ^ (e - 1) : ℕ) : ℤ) :: LH)
(B : ℕ) (hV : 2 * (facN K).factorial * facN K + 8 * K * copQ K (2 ^ e) + 4 * K * 2 ^ e + 8 * K + 8
< 2 ^ B) :
(stC K).cost t ≤ (facN K + 20) * 10 ^ 9 * (B + 2) ^ 2 := by sorry