HvdH machine lemma ST.descLoop_spec (The recursive step, part 2: the Fermat level descriptors (namespace `N)
ProvedNLogN.ST.descLoop_specThe following holds (Lean statement, in the scope of module NLogN.HSt2):
theorem NLogN.ST.descLoop_spec (M : MulSpec) (q : Params) (he : 2 ≤ q.e) (hdh : q.dh < q.K)
(w : IState HS) (L47 L48 L49 L51 L54 : List Item)
(h47 : w.G tR = .int ((2 ^ q.e : ℕ) : ℤ) :: L47)
(h48 : w.G tRh = .int ((2 ^ (q.e - 1) : ℕ) : ℤ) :: L48)
(h49 : w.G tKd = .int ((q.K - q.dh : ℕ) : ℤ) :: L49)
(h51 : w.G tLo = .int (q.logOuter : ℤ) :: L51)
(h54 : w.G tFn = .int (q.fn : ℤ) :: L54) (B : ℕ)
(hB : 2 * q.fn + q.logOuter + q.e + 2 * q.K + 4 ≤ B) :
Spec M (descLoop q.K) w (w.upd dO (ints ((descs q.outerAxes 1).flatMap enc8) ++ w.G dO))
((q.K + 1) * 10 ^ 10 * (B + 2) ^ 2)
Context. The lemma belongs to the part The recursive step, part 2: the Fermat level descriptors (namespace NLogN.ST): descLoop K pushes ints ((descs q.outerAxes 1).flatMap enc8) onto stack 39, reading
r (47), r/2 (48), K - dh (49), logOuter (51), fn (54); scratch 41, 19,
counter 52.
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.ST open IntMul NLogN IntMul.HvdH IntMul.HvdH.Ref open NLogN.FW (Spec Desc descs enc8) set_option maxHeartbeats 4000000
theorem NLogN.ST.descLoop_spec (M : MulSpec) (q : Params) (he : 2 ≤ q.e) (hdh : q.dh < q.K)
(w : IState HS) (L47 L48 L49 L51 L54 : List Item)
(h47 : w.G tR = .int ((2 ^ q.e : ℕ) : ℤ) :: L47)
(h48 : w.G tRh = .int ((2 ^ (q.e - 1) : ℕ) : ℤ) :: L48)
(h49 : w.G tKd = .int ((q.K - q.dh : ℕ) : ℤ) :: L49)
(h51 : w.G tLo = .int (q.logOuter : ℤ) :: L51)
(h54 : w.G tFn = .int (q.fn : ℤ) :: L54) (B : ℕ)
(hB : 2 * q.fn + q.logOuter + q.e + 2 * q.K + 4 ≤ B) :
Spec M (descLoop q.K) w (w.upd dO (ints ((descs q.outerAxes 1).flatMap enc8) ++ w.G dO))
((q.K + 1) * 10 ^ 10 * (B + 2) ^ 2) := by sorry