HvdH machine lemma Rsp.resP_run (One banded resampling pass on an integer list)
ProvedNLogN.Rsp.resP_runThe following holds (Lean statement, in the scope of module NLogN.HRspRes):
theorem NLogN.Rsp.resP_run (s0 : IState HS) (R : ℤ) (u : List ℤ) (Dl : List ℕ) (Ws : List (List ℤ))
(a NR n : ℕ) (RU LKs LKa LKN LR LN LNR LNW RW RD : List Item)
(hs : 0 < u.length) (ha : a < u.length) (hWs : Ws.length = NR) (hWr : ∀ W ∈ Ws, W.length = n)
(hDl : Dl.length = n) (hpre : NLogN.Rsp.pre Dl n ≤ u.length)
(hU : s0.G CU = ints u ++ RU) (hKs : s0.G Ks = .int (u.length : ℤ) :: LKs)
(hKa : s0.G Ka = .int (a : ℤ) :: LKa) (hKN : s0.G KN = .int ((u.length + NR : ℕ) : ℤ) :: LKN)
(hR : s0.G BR = .int R :: LR) (hN : s0.G BN = .int n :: LN) (hNR : s0.G BNR = .int NR :: LNR)
(hNW : s0.G BNW = .int (n * NR : ℕ) :: LNW) (hW : s0.G NLogN.Rsp.BW = ints Ws.flatten ++ RW)
(hD : s0.G BD = ints (Dl.map (Nat.cast : ℕ → ℤ)) ++ RD) :
resP.run s0 = s0.upd CU (ints (resL R Dl Ws u a n) ++ RU)
Context. The lemma belongs to the part One banded resampling pass on an integer list: resP pops u from CU, pads it cyclically (cycP), runs bandP against the tables on
BW, BD with a zero accumulator, and pushes the result back on CU.
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 8000000
theorem NLogN.Rsp.resP_run (s0 : IState HS) (R : ℤ) (u : List ℤ) (Dl : List ℕ) (Ws : List (List ℤ))
(a NR n : ℕ) (RU LKs LKa LKN LR LN LNR LNW RW RD : List Item)
(hs : 0 < u.length) (ha : a < u.length) (hWs : Ws.length = NR) (hWr : ∀ W ∈ Ws, W.length = n)
(hDl : Dl.length = n) (hpre : NLogN.Rsp.pre Dl n ≤ u.length)
(hU : s0.G CU = ints u ++ RU) (hKs : s0.G Ks = .int (u.length : ℤ) :: LKs)
(hKa : s0.G Ka = .int (a : ℤ) :: LKa) (hKN : s0.G KN = .int ((u.length + NR : ℕ) : ℤ) :: LKN)
(hR : s0.G BR = .int R :: LR) (hN : s0.G BN = .int n :: LN) (hNR : s0.G BNR = .int NR :: LNR)
(hNW : s0.G BNW = .int (n * NR : ℕ) :: LNW) (hW : s0.G NLogN.Rsp.BW = ints Ws.flatten ++ RW)
(hD : s0.G BD = ints (Dl.map (Nat.cast : ℕ → ℤ)) ++ RD) :
resP.run s0 = s0.upd CU (ints (resL R Dl Ws u a n) ++ RU) := by sorry