Round-six lemma `swapE_le`
ProvedNLogN.KFUU.R6Crt.swapE_lecomplexity-theoryinteger-multiplicationkappa-improvement
An auxiliary lemma of the round-six development, published as a separate node because its proof is long or shared.
The following holds (Lean statement, in the scope of module Solutions.R6CrtCost):
theorem NLogN.KFUU.R6Crt.swapE_le (τ K : ℝ) (hK : 0 ≤ K) (hτ0 : 0 ≤ τ) (hτ1 : τ ≤ 1) (w u : ℕ) (sh : Shape)
(p T ℓ d : ℕ) (hlen : sh.length = 5) (hvol : vol sh = T) (hw : w = p + 2) (hp : 6 ≤ p)
(hu : u ≤ ℓ * d) (hℓ : 1 ≤ ℓ) (hsz : Nat.size T + w + u + 1 ≤ 4 * p) (hpT : p ≤ T) :
cSwNτ τ K w u sh ≤ K * (4 * (T : ℝ) * p * ((ℓ : ℝ) * ((d : ℝ) * Real.log p) ^ τ) +
96 * (T : ℝ) * p)
Context. CRT reversal §11: the cost arithmetic
cFwdE_nat,cBwdE_nat: the cost ofphiFE/phiBEis at most the frozennatCost(the part of KFUU'sΦother than its phase-2 swaps) pluscP2E.cP2E_split:cP2E = rest + 3 ⌈cSwNτ …⌉.T0_le,rest_le: withV_T = 2T,w = p + 2,d + 1 ≤ 2^handTlarge, both nat parts areO((d+1) T p).swapE_le: one composite swap costs≤ K (4 T p ℓ (d ln p)^τ + 96 T p).
Formalization Note. Part of the Lean formalization of the round-six κ-improvement (integer-multiplication-kappa campaign, target IntMul.Kappa.jain_round6_framework). The statement is copied verbatim from the Lean development; the platform node carries the same declaration name. Definitions it mentions live in the IntMul_Kappa_R6_Defs* bundles (on top of the published κ bundles IntMul_Kappa_K_Defs*).
Preamble
-- Round-six κ development (integer-multiplication-kappa), generated by skeleton subtraction. import Definitions.Def_IntMul_Kappa_R6_Defs14 set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 open NLogN NLogN.KFUU NLogN.KFUU.R6Crt open IntMul NLogN.KIL NLogN.KFB NLogN.KFC NLogN.KFT NLogN.KFU AModel AModelL12 NLogN.KFUU
Formal statement
theorem NLogN.KFUU.R6Crt.swapE_le (τ K : ℝ) (hK : 0 ≤ K) (hτ0 : 0 ≤ τ) (hτ1 : τ ≤ 1) (w u : ℕ) (sh : Shape)
(p T ℓ d : ℕ) (hlen : sh.length = 5) (hvol : vol sh = T) (hw : w = p + 2) (hp : 6 ≤ p)
(hu : u ≤ ℓ * d) (hℓ : 1 ≤ ℓ) (hsz : Nat.size T + w + u + 1 ≤ 4 * p) (hpT : p ≤ T) :
cSwNτ τ K w u sh ≤ K * (4 * (T : ℝ) * p * ((ℓ : ℝ) * ((d : ℝ) * Real.log p) ^ τ) +
96 * (T : ℝ) * p) := by sorrySource
S. Jain, round-six networks for the integer-multiplication κ-improvement campaign (https://github.com/Swapnil-jain/integer-mult-kappa, commit 5868dc7) and D. Colkitt, integer-mult-bounds (https://github.com/CrocSwap/integer-mult-bounds); target `IntMul.Kappa.jain_round6_framework`. Lean declaration `NLogN.KFUU.R6Crt.swapE_le`, Solutions/R6CrtCost.lean (lines 206–246) of the round-six development.