Primitive (b), merge: the W streams (concatenated on stack 0) merged back into P :: (W * L) :: rest, cost…

Primitive (b), merge: the W streams (concatenated on stack 0) merged back into P :: (W * L) :: rest, cost O(W · V).

The following holds (Lean statement, in the scope of module Solutions.KILRow):

theorem NLogN.KIL.rowMerge_spec (t : IState HS) {W : ℕ} (s : Fin W → List ℤ) (P L : ℕ) [NeZero W] (rest : Shape)
    (Bb : ℕ) (R L1 L2 L3 L4 : List Item)
    (hs : ∀ w, (s w).length = P * L * AModel.vol rest) (hb : ∀ w, Bnd Bb (s w))
    (hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L)
    (hV : zsz ((1 * (W * (P * L * AModel.vol rest)) : ℕ) : ℤ) ≤ Bb)
    (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) :
    fwdP.ok t ∧ fwdP.run t = t.upd 0 (ints (rowMerge P W L rest 0 s) ++ R) ∧
      fwdP.cost t ≤ cMove 1 W (P * L) (AModel.vol rest) Bb

Context. The lemma belongs to the part Primitive (b): cyclic row split / merge (rowSplit, rowMerge of AModelNet): The W streams are stored one after the other (stream 0 on top). On P :: (W * L) :: rest with B = vol rest, the concatenation of the streams is the move of the row-class digit w (r = W g + w) to the front: bwdP with parameters 1, W, P * L, B splits, fwdP merges, both in O(W · V) item moves.

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 $n\log n$ (field moves, row split/merge, shifts, the uniform Proposition 11 interchange, Lemma 12 with fine $O(1)$-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.