HvdH machine lemma FIN.GK_le (Final assembly, part 3: the cost of the step for `q = mkParams K N`, u)
ProvedNLogN.FIN.GK_leThe following holds (Lean statement, in the scope of module NLogN.HFin3):
theorem NLogN.FIN.GK_le {K N β W : ℕ} (h : HB K N β W) (Φf Φm : ℕ) :
GK K N Φf Φm ≤ 3 * 2 ^ (mkParams K N).logOuter * Φf +
Φm * (100 * (K + 1) * (W + 2) * 2 ^ (mkParams K N).logT) +
(10 ^ 22 * ((K + 1) ^ 2 * ((2 ^ (mkParams K N).logT + 1) * (β + 2) ^ 2)) +
10 ^ 64 * ((K + 1) ^ 2 * ((2 ^ (mkParams K N).e + 1) ^ 3 * (β + 2) ^ 12)) +
10 ^ 7 * ((N + 1) * (β + 2)))
Context. The lemma belongs to the part Final assembly, part 3: the cost of the step for q = mkParams K N, under explicit bounds.
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 set_option maxHeartbeats 8000000 set_option maxRecDepth 100000 open NLogN open NLogN.FIN open IntMul NLogN IntMul.HvdH IntMul.HvdH.Ref NLogN.ST
theorem NLogN.FIN.GK_le {K N β W : ℕ} (h : HB K N β W) (Φf Φm : ℕ) :
GK K N Φf Φm ≤ 3 * 2 ^ (mkParams K N).logOuter * Φf +
Φm * (100 * (K + 1) * (W + 2) * 2 ^ (mkParams K N).logT) +
(10 ^ 22 * ((K + 1) ^ 2 * ((2 ^ (mkParams K N).logT + 1) * (β + 2) ^ 2)) +
10 ^ 64 * ((K + 1) ^ 2 * ((2 ^ (mkParams K N).e + 1) ^ 3 * (β + 2) ^ 12)) +
10 ^ 7 * ((N + 1) * (β + 2))) := by sorry