HvdH machine lemma Rsp.j_step_run (`Japprox` on a slice: the `E` pass (`gresP` against the `E` tables) it)
ProvedNLogN.Rsp.j_step_runThe following holds (Lean statement, in the scope of module NLogN.HRspJ):
theorem NLogN.Rsp.j_step_run (p s t α : ℕ) (hs : 0 < s) (u : List (ℤ × ℤ)) (hu : u.length = s)
(s1 : IState HS) (RU RA LS LL : List Item) (hE : EParams s1 p s t α)
(hL : s1.G JL = .int ((2 * s : ℕ) : ℤ) :: LL) (S0 : IState HS) (N j : ℕ) :
jBody.run (withCtr JC S0 N j (jSt s1 p s t α u RU RA LS j)) =
withCtr JC S0 N j (jSt s1 p s t α u RU RA LS (j + 1))
Context. The lemma belongs to the part Japprox on a slice: the E pass (gresP against the E tables) iterated with signed.
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 open NLogN open NLogN.Rsp open IntMul NLogN RS set_option maxHeartbeats 16000000
theorem NLogN.Rsp.j_step_run (p s t α : ℕ) (hs : 0 < s) (u : List (ℤ × ℤ)) (hu : u.length = s)
(s1 : IState HS) (RU RA LS LL : List Item) (hE : EParams s1 p s t α)
(hL : s1.G JL = .int ((2 * s : ℕ) : ℤ) :: LL) (S0 : IState HS) (N j : ℕ) :
jBody.run (withCtr JC S0 N j (jSt s1 p s t α u RU RA LS j)) =
withCtr JC S0 N j (jSt s1 p s t α u RU RA LS (j + 1)) := by sorry