rowSplitF_spec (KFC: fine-cost `rowSplit` / `rowMerge`)
ProvedNLogN.KFC.rowSplitF_specThe following holds (Lean statement, in the scope of module Solutions.KFCRow):
theorem NLogN.KFC.rowSplitF_spec (t : IState HS) (xs : List ℤ) (P W L : ℕ) (rest : Shape) (w : ℕ)
(R L1 L2 L3 L4 : List Item)
(hlen : xs.length = AModel.vol (P :: W * L :: rest)) (hb : Bnd w xs)
(hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L) (hW : 1 ≤ W)
(h0 : t.G 0 = ints xs ++ 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 bwdF t (t.upd 0 (ints ((List.finRange W).flatMap
(fun w => rowSplit P W L rest w 0 xs)) ++ R)) (cBwdF 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.rowSplitF_spec (t : IState HS) (xs : List ℤ) (P W L : ℕ) (rest : Shape) (w : ℕ)
(R L1 L2 L3 L4 : List Item)
(hlen : xs.length = AModel.vol (P :: W * L :: rest)) (hb : Bnd w xs)
(hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L) (hW : 1 ≤ W)
(h0 : t.G 0 = ints xs ++ 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 bwdF t (t.upd 0 (ints ((List.finRange W).flatMap
(fun w => rowSplit P W L rest w 0 xs)) ++ R)) (cBwdF 1 W (P * L) (AModel.vol rest) w) := by sorry