Proposition 14 around any IStmt C-layer, with one-pass phases
ProvedNLogN.KFM.p14Ph_irunsProposition 14 around any IStmt C-layer, with one-pass phases.
The following holds (Lean statement, in the scope of module Solutions.KFMPhase):
theorem NLogN.KFM.p14Ph_iruns (hρ : ρ < K) (hD : 1 ≤ D) {r p w : ℕ} (hr : 1 ≤ r) (hS : 1 ≤ S)
(hP : 1 ≤ P) {Cc : ℕ → IStmt HS Pp} {E dC : ℕ} {kC : ℕ → ℕ}
(hCimpl : SImplI Isym iprog r (fun i : Fin D => KFH.stT K D S ρ i)
(vol (Butterfly.layerShape P K D S)) (Butterfly.tens Cm : Butterfly.Op (Fin D)) Cc E dC kC)
(s : IState HS) (f : Fin HS → List ℤ) (zs : List GI) (l : List ℤ) (xs : List (Fin r → ℂ))
(hx : RecRep r p zs xs) (hl : xs.length = vol (Butterfly.layerShape P K D S))
(h0 : f 0 = gflat zs ++ l) (hC : ClN f) (hb : NLogN.KFB.GB w zs)
(hdisk : ∀ j (h : j < xs.length), ‖xs[j]‖ ≤ 1) :
∃ zs', RecRep r p zs' (Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs) ∧
NLogN.KFB.GB (p + 1) zs' ∧
(∀ j (h : j < (Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs).length)
(h' : j < (Butterfly.layerH P K D S ρ hρ xs).length), ∀ c,
‖(Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs)[j] c -
(Butterfly.layerH P K D S ρ hρ xs)[j] c‖ < Real.sqrt 2 * 2⁻¹ ^ p) ∧
IRuns Isym iprog (p14Ph P K D S ρ r E dC Cc w) (encK s f)
(encK s (Function.update f 0 (gflat zs' ++ l)))
(kC w + cWrapPh P K D S r E (zsz ((16 * (vol (Butterfly.layerShape P K D S) * r) : ℕ) : ℤ))
w dC)
Context. The lemma belongs to the part KFM 2: Proposition 14 with the phase diagonals S_D in one pass each: KFN.p14WithI implements S_D = diag i^{x_1+⋯+x_D} as D kernel passes (kersP … MS), so one
simultaneous butterfly round costs Θ(D · N · w) even before the C-layer. Lemma 16 runs ≈ ℓ
such rounds with D ≈ d, giving ℓ d V ≈ V log T: a full logarithmic factor, which Ncost
(ℓ d^{λ'} for this row) cannot absorb (MACHINE-PLAN.md, item 4, issue (A)).
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_Defs20.
-- OpenAI-preprint / κ-improvement development (integer-multiplication-kappa), generated by skeleton subtraction.
import Definitions.Def_IntMul_Kappa_K_Defs20
set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000
set_option linter.unusedSimpArgs false
set_option linter.unusedVariables false
set_option linter.unusedSectionVars false
open NLogN
open NLogN.KFM
open IntMul RS AModel KIL KFD KFB KFG KFH KFN Complex P8Lift Butterfly
variable {Pp : ℕ} {Isym : List Sym} {iprog : Fin Pp → IStmt HS Pp} {P K D S ρ : ℕ}
theorem NLogN.KFM.p14Ph_iruns (hρ : ρ < K) (hD : 1 ≤ D) {r p w : ℕ} (hr : 1 ≤ r) (hS : 1 ≤ S)
(hP : 1 ≤ P) {Cc : ℕ → IStmt HS Pp} {E dC : ℕ} {kC : ℕ → ℕ}
(hCimpl : SImplI Isym iprog r (fun i : Fin D => KFH.stT K D S ρ i)
(vol (Butterfly.layerShape P K D S)) (Butterfly.tens Cm : Butterfly.Op (Fin D)) Cc E dC kC)
(s : IState HS) (f : Fin HS → List ℤ) (zs : List GI) (l : List ℤ) (xs : List (Fin r → ℂ))
(hx : RecRep r p zs xs) (hl : xs.length = vol (Butterfly.layerShape P K D S))
(h0 : f 0 = gflat zs ++ l) (hC : ClN f) (hb : NLogN.KFB.GB w zs)
(hdisk : ∀ j (h : j < xs.length), ‖xs[j]‖ ≤ 1) :
∃ zs', RecRep r p zs' (Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs) ∧
NLogN.KFB.GB (p + 1) zs' ∧
(∀ j (h : j < (Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs).length)
(h' : j < (Butterfly.layerH P K D S ρ hρ xs).length), ∀ c,
‖(Butterfly.prop14Proc (P := P) (S := S) hρ p
(Butterfly.tens Butterfly.Cm : Butterfly.Op (Fin D)) xs)[j] c -
(Butterfly.layerH P K D S ρ hρ xs)[j] c‖ < Real.sqrt 2 * 2⁻¹ ^ p) ∧
IRuns Isym iprog (p14Ph P K D S ρ r E dC Cc w) (encK s f)
(encK s (Function.update f 0 (gflat zs' ++ l)))
(kC w + cWrapPh P K D S r E (zsz ((16 * (vol (Butterfly.layerShape P K D S) * r) : ℕ) : ℤ))
w dC) := by sorry