HvdH machine lemma EX.fwdLP_all (The full `fwdL` / `exactConvL` programs, part 9: `fwdLP`)
ProvedNLogN.EX.fwdLP_allThe following holds (Lean statement, in the scope of module NLogN.HEx9):
theorem NLogN.EX.fwdLP_all (fw : LProg2 M Ctx PreW (fermatW q) CW) (hfw : FwOK fw) {m Φm : ℕ}
(hMm : MulBnd M m Φm) {kb mm Φ Bacc Qa Bq Bx CS CB Q : ℕ} {BS BB : ℕ → ℕ}
(hcfg : FwdCfgX M q kb mm Φ Bacc Qa Bq Bx CS CB m Q BS BB) (s : IState HS)
(hE : FwdEnvX q kb Ctx s) (U : List (ℤ × ℤ)) (R : List Item) (hU : s.G gD = gints U ++ R)
(hin : FwdInX q PreW BS BB m Q U) :
(fwdLP fw).run s = s.upd gD (gints (fwdL q U) ++ R) ∧
(fwdLP fw).ok M s ∧
(fwdLP fw).cost M s ≤ fwdLCost q CS CB Bx CW Q Φm ∧
(fwdL q U).length = q.S ∧ GB (BB q.K) (fwdL q U)
Context. The lemma belongs to the part The full fwdL / exactConvL programs, part 9: fwdLP: fwdLP fw = S̃ phase (loop over the axes, sapAxPper axis); ftlP fw; B̃ phase (loop over the axes,bapAxP per axis), generic in the fermatW program fw (any GL.LProg2 with
GL.FwOK, e.g. FWW.fwL). Its context Ctx (e.g. the FwCtx frame on stacks
32 … 39, 52, 53) is a precondition that survives: every axis program restores every stack
but gD.
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.EX
open IntMul NLogN IntMul.HvdH IntMul.HvdH.Ref NLogN.GL NLogN.AX NLogN.Rsp
variable {M : MulSpec} {Ctx : IState HS → Prop} {PreW : List (ℤ × ℤ) → List (ℤ × ℤ) → Prop}
{q : Params} {CW : ℕ}
set_option maxHeartbeats 4000000
theorem NLogN.EX.fwdLP_all (fw : LProg2 M Ctx PreW (fermatW q) CW) (hfw : FwOK fw) {m Φm : ℕ}
(hMm : MulBnd M m Φm) {kb mm Φ Bacc Qa Bq Bx CS CB Q : ℕ} {BS BB : ℕ → ℕ}
(hcfg : FwdCfgX M q kb mm Φ Bacc Qa Bq Bx CS CB m Q BS BB) (s : IState HS)
(hE : FwdEnvX q kb Ctx s) (U : List (ℤ × ℤ)) (R : List Item) (hU : s.G gD = gints U ++ R)
(hin : FwdInX q PreW BS BB m Q U) :
(fwdLP fw).run s = s.upd gD (gints (fwdL q U) ++ R) ∧
(fwdLP fw).ok M s ∧
(fwdLP fw).cost M s ≤ fwdLCost q CS CB Bx CW Q Φm ∧
(fwdL q U).length = q.S ∧ GB (BB q.K) (fwdL q U) := by sorry