rowMergeF_spec (KFC: fine-cost `rowSplit` / `rowMerge`)
ProvedNLogN.KFC.rowMergeF_specThe following holds (Lean statement, in the scope of module Solutions.KFCRow):
theorem NLogN.KFC.rowMergeF_spec (t : IState HS) {W : ℕ} (s : Fin W → List ℤ) (P L : ℕ) [NeZero W]
(rest : Shape) (w : ℕ) (R L1 L2 L3 L4 : List Item)
(hs : ∀ v, (s v).length = P * L * AModel.vol rest) (hb : ∀ v, Bnd w (s v))
(hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L)
(h0 : t.G 0 = ints ((List.finRange W).flatMap s) ++ R)
(h1 : t.G 1 = .int ((1 : ℕ) : ℤ) :: L1)
(h2 : t.G 2 = .int (W : ℤ) :: L2) (h3 : t.G 3 = .int ((P * L : ℕ) : ℤ) :: L3)
(h4 : t.G 4 = .int (AModel.vol rest : ℤ) :: L4) :
IRuns I iprog fwdF t (t.upd 0 (ints (rowMerge P W L rest 0 s) ++ R))
(cFwdF 1 W (P * L) (AModel.vol rest) w)
Context. The lemma belongs to the part KFC: fine-cost rowSplit / rowMerge: The same denotations as KIL.rowSplit_spec / KIL.rowMerge_spec, computed by bwdF / fwdF
with parameters (1, W, P·L, vol rest); cost cBwdF 1 W (P·L) (vol rest) w ≤ (2W+69)·kap w·V
(resp. cFwdF … ≤ (2W+67)·kap w·V), V = W·P·L·vol rest, w a bound on the bit size of the
entries. Also the general-shape forms swapFF_spec, swapBF_spec, moveFieldF_spec,
moveFieldBackF_spec (mirrors of KIL.swapF_spec … KIL.moveFieldBack_spec).
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 AModel
open NLogN.KFC
variable {Pp : ℕ} {I : List Sym} {iprog : Fin Pp → IStmt HS Pp}
theorem NLogN.KFC.rowMergeF_spec (t : IState HS) {W : ℕ} (s : Fin W → List ℤ) (P L : ℕ) [NeZero W]
(rest : Shape) (w : ℕ) (R L1 L2 L3 L4 : List Item)
(hs : ∀ v, (s v).length = P * L * AModel.vol rest) (hb : ∀ v, Bnd w (s v))
(hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L)
(h0 : t.G 0 = ints ((List.finRange W).flatMap s) ++ R)
(h1 : t.G 1 = .int ((1 : ℕ) : ℤ) :: L1)
(h2 : t.G 2 = .int (W : ℤ) :: L2) (h3 : t.G 3 = .int ((P * L : ℕ) : ℤ) :: L3)
(h4 : t.G 4 = .int (AModel.vol rest : ℤ) :: L4) :
IRuns I iprog fwdF t (t.upd 0 (ints (rowMerge P W L rest 0 s) ++ R))
(cFwdF 1 W (P * L) (AModel.vol rest) w) := by sorry