Primitive (b), split: all W streams of the cyclic row split, concatenated on stack 0 (arguments 1, W, P *…

Primitive (b), split: all W streams of the cyclic row split, concatenated on stack 0 (arguments 1, W, P * L, vol rest on stacks 1 … 4), cost O(W · V).

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

theorem NLogN.KIL.rowSplit_spec (t : IState HS) (xs : List ℤ) (P W L : ℕ) (rest : Shape) (Bb : ℕ)
    (R L1 L2 L3 L4 : List Item)
    (hlen : xs.length = AModel.vol (P :: W * L :: rest)) (hb : Bnd Bb xs)
    (hB1 : 1 ≤ AModel.vol rest) (hPL : 1 ≤ P * L) (hW : 1 ≤ W)
    (hV : zsz ((1 * (W * (P * L * AModel.vol rest)) : ℕ) : ℤ) ≤ Bb)
    (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) :
    bwdP.ok t ∧ bwdP.run t = t.upd 0 (ints ((List.finRange W).flatMap
        (fun w => rowSplit P W L rest w 0 xs)) ++ R) ∧
      bwdP.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.