pwStep_runs (`FM`: pointwise products, untwisting with carries, and recombination)
ProvedNLogN.pwStep_runsThe following holds (Lean statement, in the scope of module NLogN.SSFM2):
theorem NLogN.pwStep_runs (pF : Fin P) (n C : ℕ) (hFM : FMSpec pF iprog I n C) (s : IState NS)
(a b c : ℤ) (RV RX LC LP LN LF : List Item) (ha : 0 ≤ a ∧ a < 2 ^ n + 1)
(hb : 0 ≤ b ∧ b < 2 ^ n + 1) (hc : zsz c ≤ n)
(hV : s.G NLogN.V = .int a :: RV) (hX : s.G DX = .int b :: RX) (hC : s.G CC = .int c :: LC)
(hP : s.G PRM = .int n :: LP) (hN : s.G RN = .int (2 ^ n) :: LN)
(hF : s.G RF = .int (2 ^ n + 1) :: LF) :
IRuns I iprog (pwStep pF) s
((((s.upd NLogN.V RV).upd DX RX).upd NLogN.P1 (.int ((a * b) % (2 ^ n + 1)) :: s.G NLogN.P1)).upd CC
(.int (c + -1) :: LC)) (C + 2000 * (n + 3))
Context. The lemma belongs to the part FM: pointwise products, untwisting with carries, and recombination.
Formalization Note. This lemma belongs to the item-language (IL) layer of the integer-multiplication-kappa campaign: tape-level programs (register programs over 64 item stacks of the NLogN multitape framework, definition bundles IntMul_HvdH_M_Defs1–IntMul_HvdH_M_Defs8) that implement the data-movement primitives of the OpenAI preprint Integer multiplication below (field moves, row split/merge, shifts, the uniform Proposition 11 interchange, Lemma 12 with fine -per-element costs, Gaussian record primitives, Proposition 14 pieces) with exact list denotations from the array-model bundles IntMul_Kappa_K_Defs* and explicit cost bounds. All names refer to the definition bundles up to IntMul_Kappa_K_Defs18.
-- OpenAI-preprint / κ-improvement development (integer-multiplication-kappa), generated by skeleton subtraction.
import Definitions.Def_IntMul_Kappa_K_Defs18
set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000
open NLogN
open IntMul
variable {P : ℕ} {I : List Sym} {iprog : Fin P → IStmt NS P}
theorem NLogN.pwStep_runs (pF : Fin P) (n C : ℕ) (hFM : FMSpec pF iprog I n C) (s : IState NS)
(a b c : ℤ) (RV RX LC LP LN LF : List Item) (ha : 0 ≤ a ∧ a < 2 ^ n + 1)
(hb : 0 ≤ b ∧ b < 2 ^ n + 1) (hc : zsz c ≤ n)
(hV : s.G NLogN.V = .int a :: RV) (hX : s.G DX = .int b :: RX) (hC : s.G CC = .int c :: LC)
(hP : s.G PRM = .int n :: LP) (hN : s.G RN = .int (2 ^ n) :: LN)
(hF : s.G RF = .int (2 ^ n + 1) :: LF) :
IRuns I iprog (pwStep pF) s
((((s.upd NLogN.V RV).upd DX RX).upd NLogN.P1 (.int ((a * b) % (2 ^ n + 1)) :: s.G NLogN.P1)).upd CC
(.int (c + -1) :: LC)) (C + 2000 * (n + 3)) := by sorry