HvdH machine lemma AX.sapAxP_all (One resampling axis, part 4: the `S̃` axis program `sapAxP`)
ProvedNLogN.AX.sapAxP_allThe following holds (Lean statement, in the scope of module NLogN.HAx4):
theorem NLogN.AX.sapAxP_all (M : MulSpec) (p s t α m kb Bi Bo mm Φ Bacc Q Bq : ℕ) (rest : List ℕ)
(hM : MulBnd M mm Φ) (H : SapHyp p s t α Bi Bo mm Bacc Q) (HT : TabHyp p s t α Bq)
(HQ : AxQ s t m kb Bi Bo Q) (hmr : m = rest.prod)
(st : IState HS) (L : List (ℤ × ℤ)) (Rest : List Item) (hR : SapRegs p s t α m kb st)
(hD : st.G gD = gints L ++ Rest) (hL : L.length = s * m) (hLB : GB Bi L) :
sapAxP.run st = st.upd gD (gints (tensorGo [(t, sapL p s t α)] (s :: rest) L) ++ Rest) ∧
sapAxP.ok M st ∧ sapAxP.cost M st ≤ sapAxCost p s t α m kb Bi mm Φ Bacc Q Bq ∧
(tensorGo [(t, sapL p s t α)] (s :: rest) L).length = m * t ∧
GB Bo (tensorGo [(t, sapL p s t α)] (s :: rest) L)
Context. The lemma belongs to the part One resampling axis, part 4: the S̃ axis program sapAxP: sapAxP on gD = gints L ++ R (with L of dims s :: rest, m = rest.prod) computes
gints (tensorGo [(t, sapL p s t α)] (s :: rest) L) ++ R: it builds the S weight table on
aW = 39 and the step table on aD = 40, runs GL.axisP with the slice program sapSl, and
pops the two tables again. Every stack except gD is restored.
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.AX open IntMul NLogN IntMul.HvdH.Ref NLogN.GL NLogN.Rsp set_option maxHeartbeats 4000000
theorem NLogN.AX.sapAxP_all (M : MulSpec) (p s t α m kb Bi Bo mm Φ Bacc Q Bq : ℕ) (rest : List ℕ)
(hM : MulBnd M mm Φ) (H : SapHyp p s t α Bi Bo mm Bacc Q) (HT : TabHyp p s t α Bq)
(HQ : AxQ s t m kb Bi Bo Q) (hmr : m = rest.prod)
(st : IState HS) (L : List (ℤ × ℤ)) (Rest : List Item) (hR : SapRegs p s t α m kb st)
(hD : st.G gD = gints L ++ Rest) (hL : L.length = s * m) (hLB : GB Bi L) :
sapAxP.run st = st.upd gD (gints (tensorGo [(t, sapL p s t α)] (s :: rest) L) ++ Rest) ∧
sapAxP.ok M st ∧ sapAxP.cost M st ≤ sapAxCost p s t α m kb Bi mm Φ Bacc Q Bq ∧
(tensorGo [(t, sapL p s t α)] (s :: rest) L).length = m * t ∧
GB Bo (tensorGo [(t, sapL p s t α)] (s :: rest) L) := by sorry