Lemma 10 shift with coefficient u = -k⁻¹ (2 ≤ k ≤ 20, k prime to Q), IL program

Lemma 10 shift with coefficient u = -k⁻¹ (2 ≤ k ≤ 20, k prime to Q), IL program.

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

theorem NLogN.KIL.shiftArrNegDiv_il_spec [NeZero Q] (i : Fin n) (c : Fin n → ZMod Q)
    (hc : ∀ j, i ≤ j → c j = 0) (A C : Shape) (hsh : sh = A ++ Q :: C)
    (hA : (Λ.pos i : ℕ) = A.length) (k : ℕ) (hk2 : 2 ≤ k) (hk20 : k ≤ 20) (hkQ : k < Q)
    (hQk : Nat.Coprime Q k) (t : IState HS) (xs : List ℤ) (Bb : ℕ) (R : List Item)
    (hlen : xs.length = AModel.vol sh) (hb : Bnd Bb xs) (hB1 : 1 ≤ AModel.vol C) (hQ1 : 1 ≤ Q)
    (hP1 : 1 ≤ AModel.vol A) (hV : zsz ((AModel.vol A * (Q * AModel.vol C) : ℕ) : ℤ) ≤ Bb)
    (hQ2 : zsz ((2 * Q : ℕ) : ℤ) ≤ Bb) (h0 : t.G 0 = ints xs ++ R) :
    Sp (shNDiv Q k (AModel.vol A) (AModel.vol C) (A.zip (csOf Λ c A))) t
      (t.upd 0 (ints (shiftArr Λ i (-(k : ZMod Q)⁻¹) c 0 xs) ++ R))
      (cShiftU A.length (AModel.vol A * (Q * AModel.vol C)) Bb)

Context. The lemma belongs to the part KIL2: multiplying the target field by c⁻¹ (Lemma 4, the inverse direction): The mirror of KIL2Mul: the records y = 0, …, Q − 1 of a block are distributed by residue, record y going to stream σ(y mod c) (a residue counter on stack 13 and a c-way branch), and the streams 0, …, c − 1 are then concatenated. Stream j holds the records y = c·z − j·Q for z ∈ [lo j, lo (j+1)) in increasing order (filt_eq), so the output position z receives record (c·z) mod Q: the permutation is y ↦ c⁻¹·y.

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.