Theorem 6.5, conjunct 6: the composite toggle reaches the packed payload in steps
ProvedLinearSetReconciliation327.Main.conj6_assembly_crThis is conjunct 6 of Theorem 6.5 --- the toggle conjunct --- for the composite programme of the linear-set-reconciliation scheme of arXiv:2611.11409.
Fix , , a linear map , a word-RAM environment of width , a block width , child blocks with payload lengths (word-padded: ) and sketches , and a payload base for the CR block. The environment's deterministic table is the composite one:
i.e. a metadata block holding , and the address of the payload-base table, then the child blocks, then the CR block whose table is Proposition 2.3's rebased table together with the payload bases .
Hypothesis (Theorem 5.1's obligation). Each child block satisfies the run contract at the pinned block width: for every program containing the block's compilation at a base , every with , every payload base with , and every environment whose table agrees with on , the block --- started with , , --- toggles into the payload at within steps, returns to , preserves , and touches no memory cell outside the payload window. Crucially the CR block is not a hypothesis: it is discharged from Proposition 2.3's relocated toggle (cr23UpStmtAt_crSemAtW), at cost .
Conclusion. Under the arithmetic fits that make the layout non-overlapping (, , , , …), for every payload of bits and every coordinate , the composite programme progUpOfProB Sup cr23UpStmtAt admits a run of length at most
steps from the initialised state initState (packMem E.W y) i.val 0 0 to a state whose memory is the packed payload of
i.e. the composite sketch is toggled into the packed payload. The bound is the paper's: for the prologue, for the child blocks, for the failing loop test and the jump, for the dispatch to the CR block, and for the CR block.
Formalization Note. The contract is stated at the pinned block width and carries the payload-word fit : the published shape without the fit is falsifiable, since iTbl reduces a table entry modulo . The CR premise of the earlier assembly is not a hypothesis here --- it is proved, axiom-clean, inside the imported bundle.
import Definitions.Def_LinearSetReconciliation327_Main_Conj6CR
namespace LinearSetReconciliation327.Main
theorem conj6_assembly_cr
(Sup : Stmt) (E : RAMEnv) {l N t Wd Rpad : ℕ} {f : Fin l → ℕ}
{dt : Fin l → ℕ → ℕ}
{Hs : (s : Fin l) → (Fin N → ZMod 2) →ₗ[ZMod 2] (Fin (f s) → ZMod 2)}
{C : Fin N → Fin (cr23D N) → Fin (cr23M t)}
{Tu : ℝ} (hTu : 0 ≤ Tu)
(hW : 0 < E.W) (hW1 : 1 < 2 ^ E.W) (hWd1 : 1 ≤ Wd) (hWd2 : 2 ≤ Wd)
(hpad : ∀ s : Fin l, E.W * wordsOf E.W (f s) = f s)
(hUp : UpChildSemC Sup E Tu (2 ^ Wd) f Hs)
(hE : E.det = compUpDetB Wd Rpad dt (cr23DecDetAt N t C (blkTotal E.W f))
(fun s => blkOff E.W f s.val) (blkTotal E.W f))
(hN : 1 ≤ N) (htN : t ≤ N) (hEW : E.W = cr23Word N) (hBw : cr23Graph0 N ≤ Rpad)
(hWdW : 2 ^ Wd < 2 ^ E.W) (hlW : l + 1 < 2 ^ E.W)
(hRpad : 0 < Rpad) (hRfit : Rpad ≤ 2 ^ Wd) (hpayfit : Rpad + l ≤ 2 ^ Wd)
(hlWd : (l + 1) * 2 ^ Wd < 2 ^ E.W)
(hcrfit : (l + 1) * 2 ^ Wd + Rpad ≤ 2 ^ E.W)
(hpaylt : compPayBase l Wd Rpad + l ≤ 2 ^ E.W)
(hbtlt : blkTotal E.W f < 2 ^ E.W)
(hbtfit : blkTotal E.W f + wordsOf E.W (cr23R N t) ≤ 2 ^ E.W)
(y : Fin (E.W * blkTotal E.W f + (cr23R N t)) → ZMod 2) (i : Fin N) :
∃ s' : RAMState,
HaltsWithin (progUpOfProB Sup cr23UpStmtAt) E
(7 + (8 * (l : ℝ) + (l : ℝ) * Tu) + 2 + 3 + (65536 * lg ((N : ℝ) + 2) ^ 2))
(initState (packMem E.W y) i.val 0 0) s' ∧
(∀ addr < wordsOf E.W (E.W * blkTotal E.W f + (cr23R N t)),
s'.mem addr
= packMem E.W (y + compH E.W hW f (cr23R N t) Hs (cr23Sketch N t C) (Pi.single i 1)) addr) := by sorry
end LinearSetReconciliation327.Main