Round-six lemma `sp_dupR`
ProvedJ6Seg.KR.sp_dupRcomplexity-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.J6SegKr2):
theorem J6Seg.KR.sp_dupR {X Y Z C R : Fin HS} (hXY : X ≠ Y) (hXZ : X ≠ Z) (hYZ : Y ≠ Z) (hXC : X ≠ C)
(hYC : Y ≠ C) (hZC : Z ≠ C) (hRC : R ≠ C) (hRX : R ≠ X) (hRY : R ≠ Y) (hRZ : R ≠ Z)
(hX5 : X.val < 56) (hY5 : Y.val < 56) (hZ5 : Z.val < 56) (hC5 : C.val < 56)
(hR5 : R.val < 56) (s : IState HS) (f : Fin HS → List ℤ) (L lx lr : List ℤ)
(hX : f X = L ++ lx) (hC : f C = []) (hR : f R = (L.length : ℤ) :: lr) (B : ℕ)
(hL : Bnd B L) (hn : zsz (L.length : ℤ) ≤ B) :
Sp (dupR X Y Z C R) (encK s f)
(encK s (Function.update (Function.update (Function.update f X lx) Y (L.reverse ++ f Y)) Z
(L.reverse ++ f Z))) (cMvP L.length B)
Context. B3 (chunk kernel), part 2: register loops on managed states
Counted register loops (RS.rep with the count on top of a register) on encK states:
mvP X Y T C R: movenGaussian pairs fromXtoY, keeping each pair's orientation (gflat z ++ lxonX↦gflat z.reverseon top ofY);rdP V O C R: round pairs (rs Pon both parts) from a reversed flat list onVtoO(gsw u ++ lv↦gflat ((u.reverse).map rsG)on top ofO);rgP A Y C R: a real table as Gaussian pairs (a ++ laonA↦gflat (a.reverse.map (·, 0))on top ofY);zeroR,dropR,dupR: push zeros, drop, duplicate-move with a register count.
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_Defs64 set_option autoImplicit false set_option relaxedAutoImplicit false set_option maxHeartbeats 1000000 open J6Seg J6Seg.KR open IntMul NLogN NLogN.KIL NLogN.KFD NLogN.KFB
Formal statement
theorem J6Seg.KR.sp_dupR {X Y Z C R : Fin HS} (hXY : X ≠ Y) (hXZ : X ≠ Z) (hYZ : Y ≠ Z) (hXC : X ≠ C)
(hYC : Y ≠ C) (hZC : Z ≠ C) (hRC : R ≠ C) (hRX : R ≠ X) (hRY : R ≠ Y) (hRZ : R ≠ Z)
(hX5 : X.val < 56) (hY5 : Y.val < 56) (hZ5 : Z.val < 56) (hC5 : C.val < 56)
(hR5 : R.val < 56) (s : IState HS) (f : Fin HS → List ℤ) (L lx lr : List ℤ)
(hX : f X = L ++ lx) (hC : f C = []) (hR : f R = (L.length : ℤ) :: lr) (B : ℕ)
(hL : Bnd B L) (hn : zsz (L.length : ℤ) ≤ B) :
Sp (dupR X Y Z C R) (encK s f)
(encK s (Function.update (Function.update (Function.update f X lx) Y (L.reverse ++ f Y)) Z
(L.reverse ++ f Z))) (cMvP L.length B) := 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 `J6Seg.KR.sp_dupR`, Solutions/J6SegKr2.lean (lines 233–296) of the round-six development.