The inverse C-layer from any forward implementation (17): sign passes, the forward layer, sign passes, the…

The inverse C-layer from any forward implementation (17): sign passes, the forward layer, sign passes, the unit (-i)^D.

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

theorem NLogN.KFH.limpl_cinv (hρ : ρ < K) (hD : 1 ≤ D) {r : ℕ} (hr : 1 ≤ r) (hS : 1 ≤ S) (hP : 1 ≤ P)
    {Cprog : RS} {dC : ℕ} {kC : ℕ → ℕ}
    (hCimpl : LImpl (P := P) (S := S) hρ r (Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D))
      Cprog D dC kC) :
    LImpl (P := P) (S := S) hρ r (Butterfly.tens Butterfly.Cinv : Butterfly.Op (Fin D))
      (.seq (.seq (.seq (kersP K D S ρ P r MZ ((List.finRange D).map Fin.val)) Cprog)
        (kersP K D S ρ P r MZ ((List.finRange D).map Fin.val))) (kerP K D S ρ P r 0 (MU D)))
      (0 * D + D + 0 * D + 0) (2 * D + dC + 2 * D + 2)
      (fun w => D * ck (vol (Butterfly.layerShape P K D S) * r)
          (zsz ((12 * (vol (Butterfly.layerShape P K D S) * r) : ℕ) : ℤ)) (w + 2 * D) + 1 +
        kC (w + 2 * D) +
        (D * ck (vol (Butterfly.layerShape P K D S) * r)
          (zsz ((12 * (vol (Butterfly.layerShape P K D S) * r) : ℕ) : ℤ)) (w + (2 * D + dC) + 2 * D)
          + 1) +
        ck (vol (Butterfly.layerShape P K D S) * r)
          (zsz ((12 * (vol (Butterfly.layerShape P K D S) * r) : ℕ) : ℤ)) (w + (2 * D + dC + 2 * D)))

Context. The lemma belongs to the part KFH: the Proposition 14 wrapper around an arbitrary C^{⊗D} implementation: The recursion of §5.3 replaces the D individual C kernels by the batched network. The interface between the two is LImpl … (tens Cm) Cprog D dC kC: any fine IL code that maps a record array at scale F to the C-layer at scale F + D (exact, the D halvings of the kernels (25) kept as scale), widths +dC, cost kC w.

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.