Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Row-loop scratch: the clearing pass, the weak zero hypothesis, and the loop closure

Definition
LinearSetReconciliation327_Main_RowScratch20261121

by djwj233 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

decoderlinear-set-reconciliationrow-decodeword-ram

The scratch-handling layer of Theorem 6.5's row loop. It proves the clearing pass of Proposition 2.1 (64t2+352t+116764t^2+352t+116764t2+352t+1167 steps, zeroing exactly [0,decoderAllocEnd(t))[0,\mathrm{decoderAllocEnd}(t))[0,decoderAllocEnd(t)) and framing every address above it), the exact difference between the published zero hypothesis and the honest one the composite needs (WeakZero), and the log⁡n\log nlogn-fold row-loop closure that turns a per-iteration Sem into the loop's own time bound.

Definition code
import Mathlib
import Definitions.Def_LinearSetReconciliation327_Main_Top65Dec
import Definitions.Def_LinearSetReconciliation327_Main_DecoderLemmas
import Definitions.Def_LinearSetReconciliation327_Main_DecoderProgram
import Definitions.Def_LinearSetReconciliation327_Main_P21RunStmt
import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoding_at
import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_read
import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_key_solver
import Theorems.Thm_LinearSetReconciliation327_Main_pinsketch_decoder_verifier

/-!
# `_66_row_scratch` — the row loop's scratch region

Theorem 6.5's row loop runs Proposition 2.1's decoder `d` times in one memory.  The published
`pinsketch_decoding_at` is **one-shot**: it needs

```
hzero : ∀ a, (a < β ∨ β + L ≤ a) → s.mem a = 0          (L = wordsOf (8w) (tw))
```

because its layer copies the payload `[β, β+L)` down to `[0, L)` and then erases the source with
the *zero shadow block* `[β+L, β+2L)`.  Something must re-establish `hzero` between two calls.

This file does four things, with no `sorry` and independent of any `Solutions/*` file:

* **§1 — what must really be zero.**  The two copy passes only ever *read* `[β, β+L)` and
  `[β+L, β+2L)` and only ever *write* `[0, L)` and `[β, β+L)`.  Hence the destination window
  `[0, L)` is irrelevant, and the exact condition for the layer to land on the canonical decoder
  memory `hintMem W y []` is

  `payload on [β, β+L)` **and** `zero on [L, β)` **and** `zero on [β+L, ∞)`

  (`WeakZero`).  `layerMem_eq` proves that suffices; `weakZero_of_layerMem` proves the zero
  conditions are also *necessary*; `strong_to_weak` and `weakZero_strictly_weaker` show the
  published `hzero` is strictly stronger and that the gap is inhabited.
* **§2 — a write-only re-zeroing pass.**  `clearArray_spec` of `Sol_proposition_2_1.lean:5138`
  re-proved against the importable `Definitions` (its statement is byte-identical), together with
  `clearMem_get` / `clearMem_frame`, a `clearInit` register preamble, and the specialised
  `clearScratch` contract at `[0, decoderAllocEnd t)`.
* **§3 — per-iteration maintenance.**  `weakZero_restage`: after clearing `[0, K)` and re-staging
  the payload at `β` with `β + L ≤ K`, `WeakZero` holds again *provided memory at `≥ K` is zero*.
  `rowBody_sem` assembles one loop iteration out of its sub-stages with exact cost.
* **§4 — the idempotence escape is refuted at the prefix level.**  The key-solver stage's own
  published postcondition forces `m 79 = decoderSavedBase t = 128 + 3t ≠ 0`, i.e. a dirty word
  strictly inside the scratch `[0, decoderAllocEnd t)`.
-/

set_option autoImplicit false
set_option maxHeartbeats 800000
set_option maxRecDepth 40000
set_option linter.unusedSimpArgs false

open Finset

namespace LinearSetReconciliation327.Main
namespace R66

/-! ## 1. The exact zero region of the copy-in / copy-out layer -/

/-- Memory is zero on the half-open interval `[lo, hi)`. -/
def ZeroOn (m : ℕ → ℕ) (lo hi : ℕ) : Prop := ∀ a, lo ≤ a → a < hi → m a = 0

/-- Memory is zero from `lo` upwards. -/
def ZeroFrom (m : ℕ → ℕ) (lo : ℕ) : Prop := ∀ a, lo ≤ a → m a = 0

/-- The payload of `y` is staged in the words `[β, β + wordsOf W M)`. -/
def PayloadOn (W M β : ℕ) (y : Fin M → ZMod 2) (m : ℕ → ℕ) : Prop :=
  ∀ j, j < wordsOf W M → m (β + j) = packMem W y j

/-- **The honest per-call hypothesis**: zero on `[L, β)` and above `β + L`, where
`L = wordsOf W M`.  This is the published `hzero` *without* the requirement that the
destination window `[0, L)` be clean. -/
def WeakZero (W M β : ℕ) (m : ℕ → ℕ) : Prop :=
  (∀ a, wordsOf W M ≤ a → a < β → m a = 0) ∧ (∀ a, β + wordsOf W M ≤ a → m a = 0)

/-- The published hypothesis of `pinsketch_decoding_at`. -/
def StrongZero (W M β : ℕ) (m : ℕ → ℕ) : Prop :=
  ∀ a, (a < β ∨ β + wordsOf W M ≤ a) → m a = 0

/-- The memory produced by the driver's two copy passes: copy `[β, β+L)` to `[0, L)`, then erase
the source by copying the shadow block `[β+L, β+2L)` over it. -/
def layerMem (W M β : ℕ) (y : Fin M → ZMod 2) (m : ℕ → ℕ) : ℕ → ℕ :=
  writeArray β (writeArray 0 m (fun i => m (β + i)) (wordsOf W M))
    (fun i => writeArray 0 m (fun j => m (β + j)) (wordsOf W M) (β + wordsOf W M + i))
    (wordsOf W M)

theorem writeArray_zero_base (m f : ℕ → ℕ) (n i : ℕ) (hi : i < n) :
    writeArray 0 m f n i = f i := by
  simpa using writeArray_get 0 m f n i hi

theorem packMem_zero (W M : ℕ) (a : ℕ) : packMem W (0 : Fin M → ZMod 2) a = 0 := by
  refine Finset.sum_eq_zero fun p _ => ?_
  by_cases h : p.val / W = a ∧ (0 : Fin M → ZMod 2) p = 1
  · exact absurd h.2 (by simp)
  · simp [h]

theorem hintMem_nil (W M : ℕ) (y : Fin M → ZMod 2) (a : ℕ) :
    hintMem W y ([] : List ℕ) a = if a < wordsOf W M then packMem W y a else 0 := by
  unfold hintMem
  rfl

/-- **The layer lands on the canonical decoder memory under the weak hypothesis.**  This is the
statement `pinsketch_decoding_at`'s proof consumes (`layerMem_eq` in `Sol_p21_decode_at.lean`),
with its `hzero` replaced by `WeakZero`: the destination window `[0, L)` is never inspected. -/
theorem layerMem_eq {W M β : ℕ} {y : Fin M → ZMod 2} {m : ℕ → ℕ}
    (hpay : PayloadOn W M β y m) (hweak : WeakZero W M β m) (hβL : wordsOf W M ≤ β) :
    layerMem W M β y m = hintMem W y ([] : List ℕ) := by
  funext a
  unfold layerMem
  by_cases h1 : a < wordsOf W M
  · rw [writeArray_frame β _ _ _ a (Or.inl (by omega)),
      writeArray_zero_base m (fun i => m (β + i)) _ a h1, hpay a h1]
    rw [hintMem_nil]
    simp [h1]
  · rw [hintMem_nil, if_neg h1]
    by_cases h2 : a < β
    · rw [writeArray_frame β _ _ _ a (Or.inl h2),
        writeArray_frame 0 m _ _ a (Or.inr (by omega))]
      exact hweak.1 a (by omega) h2
    · by_cases h3 : a < β + wordsOf W M
      · have hOut : writeArray β (writeArray 0 m (fun i => m (β + i)) (wordsOf W M))
            (fun i => writeArray 0 m (fun j => m (β + j)) (wordsOf W M)
              (β + wordsOf W M + i)) (wordsOf W M) a
            = writeArray 0 m (fun i => m (β + i)) (wordsOf W M) (a + wordsOf W M) := by
          rw [show a = β + (a - β) from by omega,
            writeArray_get β _ _ _ (a - β) (by omega)]
          congr 1
          omega
        rw [hOut, writeArray_frame 0 m _ _ _ (Or.inr (by omega))]
        exact hweak.2 (a + wordsOf W M) (by omega)
      · rw [writeArray_frame β _ _ _ a (Or.inr (by omega)),
          writeArray_frame 0 m _ _ a (Or.inr (by omega))]
        exact hweak.2 a (by omega)

/-- **The zero conditions are necessary**, not merely sufficient: if the layer lands on `hintMem`
then memory was already zero on `[L, β)` and above `β + L` (the two regions no pass writes). -/
theorem weakZero_of_layerMem {W M β : ℕ} {y : Fin M → ZMod 2} {m : ℕ → ℕ}
    (heq : layerMem W M β y m = hintMem W y ([] : List ℕ)) : WeakZero W M β m := by
  constructor
  · intro a hLa haβ
    have h := congrFun heq a
    unfold layerMem at h
    rw [writeArray_frame β _ _ _ a (Or.inl haβ),
      writeArray_frame 0 m _ _ a (Or.inr (by omega))] at h
    rw [hintMem_nil, if_neg (by omega)] at h
    exact h
  · intro a ha
    have h := congrFun heq a
    unfold layerMem at h
    rw [writeArray_frame β _ _ _ a (Or.inr (by omega)),
      writeArray_frame 0 m _ _ a (Or.inr (by omega))] at h
    rw [hintMem_nil, if_neg (by omega)] at h
    exact h

/-- The published `hzero` implies the weak one. -/
theorem strong_to_weak {W M β : ℕ} {m : ℕ → ℕ} (h : StrongZero W M β m) :
    WeakZero W M β m :=
  ⟨fun a _ ha => h a (Or.inl ha), fun a ha => h a (Or.inr ha)⟩

/-- **The exact difference between the published hypothesis and the honest one is the destination
window `[0, L)`** — no more, no less. -/
theorem strongZero_iff {W M β : ℕ} {m : ℕ → ℕ} (hβL : wordsOf W M ≤ β) :
    StrongZero W M β m ↔ WeakZero W M β m ∧ ∀ a, a < wordsOf W M → m a = 0 := by
  constructor
  · intro h
    exact ⟨strong_to_weak h, fun a ha => h a (Or.inl (by omega))⟩
  · rintro ⟨hw, hlow⟩ a (ha | ha)
    · by_cases h : a < wordsOf W M
      · exact hlow a h
      · exact hw.1 a (by omega) ha
    · exact hw.2 a ha

/-- **The weakening is strict, and the relaxed hypothesis is inhabited.**  One word of junk in the
destination window `[0, L)` breaks the published `hzero`, yet the layer still produces the
canonical decoder memory — the junk is overwritten by the payload copy. -/
theorem weakZero_strictly_weaker :
    ∃ (W M β : ℕ) (y : Fin M → ZMod 2) (m : ℕ → ℕ),
      PayloadOn W M β y m ∧ WeakZero W M β m ∧ ¬ StrongZero W M β m ∧
        layerMem W M β y m = hintMem W y ([] : List ℕ) := by
  have hL : wordsOf 8 1 = 1 := by decide
  have h1 : (1 : ℕ) ≠ 0 := by omega
  refine ⟨8, 1, 1, (0 : Fin 1 → ZMod 2), (fun a => if a = 0 then 7 else 0), ?_, ?_, ?_, ?_⟩
  · intro j hj
    rw [hL] at hj
    interval_cases j
    show (if 1 = 0 then 7 else 0) = packMem 8 (0 : Fin 1 → ZMod 2) 0
    rw [if_neg h1]
    exact (packMem_zero 8 1 0).symm
  · constructor
    · intro a hj1 hj2
      omega
    · intro a ha
      have h2 : a ≠ 0 := by omega
      simp [h2]
  · intro h
    have h0 : (0 : ℕ) < 1 := by omega
    have hbad := h 0 (Or.inl h0)
    simp at hbad
  · refine layerMem_eq (W := 8) (M := 1) (β := 1) (y := (0 : Fin 1 → ZMod 2))
      (m := (fun a => if a = 0 then 7 else 0)) ?_ ?_ (by rw [hL])
    · intro j hj
      rw [hL] at hj
      interval_cases j
      show (if 1 = 0 then 7 else 0) = packMem 8 (0 : Fin 1 → ZMod 2) 0
      rw [if_neg h1]
      exact (packMem_zero 8 1 0).symm
    · constructor
      · intro a hj1 hj2
        omega
      · intro a ha
        have h2 : a ≠ 0 := by omega
        simp [h2]

/-! ## 2. `clearArray_spec`, re-proved against the importable `Definitions`

`clearMem`/`clearState`/`clearCond`/`clearBody`/`clearStmt` live in
`Def_…_DecoderProgram`; the lemmas below are the spans of `Sol_proposition_2_1.lean:5038–5161`
(with the definitions deleted, since they are already declared). -/

theorem clearMem_get (B : ℕ) (m : ℕ → ℕ) (n i : ℕ) (hi : i < n) :
    clearMem B m n (B + i) = 0 := by
  induction n with
  | zero => omega
  | succ n ih =>
      by_cases h : i = n
      · subst i
        simp [clearMem]
      · rw [clearMem, Function.update_of_ne (by omega : B + i ≠ B + n)]
        exact ih (by omega)

theorem clearMem_frame (B : ℕ) (m : ℕ → ℕ) (n a : ℕ)
    (ha : a < B ∨ B + n ≤ a) : clearMem B m n a = m a := by
  induction n with
  | zero => rfl
  | succ n ih =>
      rw [clearMem, Function.update_of_ne (by omega : a ≠ B + n)]
      exact ih (by omega)

theorem clearCond_eval (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) :
    clearCond.eval (clearState pc B L m r j) ↔ j < L := by
  simp [clearCond, Cond.eval, clearState]

theorem clearBody_spec (E : RAMEnv) (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ)
    (j : ℕ) (hj : j < L) (hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W)
    (hB : B + L ≤ 2 ^ E.W) :
    runBlock clearBody E
      { runBlock clearCond.code E (clearState pc B L m r j) with pc := pc + 2 } =
      { clearState pc B L m r (j + 1) with pc := pc + 7 } := by
  have haddr : (B + j) % 2 ^ E.W = B + j := Nat.mod_eq_of_lt (by omega)
  have hnext : (j + 1) % 2 ^ E.W = j + 1 := Nat.mod_eq_of_lt (by omega)
  have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt hW
  apply ramState_eq_of
  · simp only [clearBody, Fin.isValue, Cond.code, clearCond, clearState, runBlock_cons, execInstr,
      ↓reduceIte, one_ne_zero, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
      Function.update_of_ne, Function.update_self, Nat.zero_mod, Nat.add_right_cancel_iff,
      Nat.add_left_cancel_iff] <;> omega
  · simp only [clearBody, Fin.isValue, Cond.code, clearCond, clearState, runBlock_cons, execInstr,
      ↓reduceIte, one_ne_zero, hj, h1, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
      Function.update_of_ne, haddr, Function.update_self, hnext, Nat.zero_mod, clearMem]
  · intro d
    fin_cases d <;>
      simp only [clearBody, Fin.isValue, Cond.code, clearCond, clearState, runBlock_cons, execInstr,
        ↓reduceIte, one_ne_zero, hj, h1, runBlock_nil, ne_eq, Fin.reduceEq, not_false_eq_true,
        Function.update_of_ne, haddr, Function.update_self, hnext, Nat.zero_mod, Fin.zero_eta,
        Nat.add_left_cancel_iff, Fin.mk_one, Fin.reduceFinMk]

theorem clearBodyIter (P : Program) (E : RAMEnv) (pc B L : ℕ)
    (m : ℕ → ℕ) (r : Fin 16 → ℕ) (j : ℕ) (hj : j < L)
    (hAt : At P pc (Stmt.compile clearStmt pc))
    (hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W) :
    Sem P E (pc + clearCond.code.length + 1) pc
      { runBlock clearCond.code E (clearState pc B L m r j) with
        pc := pc + clearCond.code.length + 1 }
      (fun k s' => k = 6 ∧ s' = clearState pc B L m r (j + 1)) := by
  obtain ⟨-, -, hbody, hjmp⟩ := at_loop (c := clearCond) (b := .code clearBody) hAt
  have hbodyAt : At P (pc + 2) clearBody := by
    have h := hbody
    rw [show clearCond.code.length = 1 from rfl] at h
    simpa only [Stmt.compile] using h
  have hjmpAt : P[pc + 7]? = some (iJmp pc) := by
    have h := hjmp
    rw [show clearCond.code.length = 1 from rfl, show (Stmt.code clearBody).len = 5 from rfl] at h
    simpa using h
  have hrun : Sem P E (pc + 2) (pc + 7)
      { runBlock clearCond.code E (clearState pc B L m r j) with pc := pc + 2 }
      (fun k s' => k = 5 ∧ s' = { clearState pc B L m r (j + 1) with pc := pc + 7 }) := by
    refine Sem.mono (Sem.block P E (pc + 2) clearBody _ hbodyAt
      (by simp [clearBody]) rfl) ?_
    intro k s' h
    obtain ⟨hk, hs⟩ := h
    refine ⟨hk, ?_⟩
    rw [hs]
    exact clearBody_spec E pc B L m r j hj hW hL hB
  refine Sem.jmp_append (hAt := hjmpAt) (Sem.mono hrun ?_)
  intro k s' h
  obtain ⟨hk, hs⟩ := h
  refine ⟨by omega, ?_⟩
  rw [hs]
  rfl

theorem clearCond_exit (E : RAMEnv) (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ) :
    ({ runBlock clearCond.code E (clearState pc B L m r L) with pc := pc + 8 } : RAMState) =
      { clearState pc B L m r L with pc := pc + 8 } := by
  apply ramState_eq_of
  · rfl
  · rfl
  · intro d
    fin_cases d <;> simp [clearCond, Cond.code, runBlock_cons, runBlock_nil, execInstr, clearState]

/-- **An actual counted RAM loop clears the array and preserves all memory outside it**, with at
most `8L + 2` steps.  Verbatim `clearArray_spec` of `Sol_proposition_2_1.lean:5138`. -/
theorem clearArray_spec (P : Program) (E : RAMEnv) (pc B L : ℕ)
    (m : ℕ → ℕ) (r : Fin 16 → ℕ)
    (hAt : At P pc (Stmt.compile clearStmt pc))
    (hW : 1 < 2 ^ E.W) (hL : L < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W) :
    Sem P E pc (pc + 8) (clearState pc B L m r 0)
      (fun k s' => k ≤ 8 * L + 2 ∧ s' = { clearState pc B L m r L with pc := pc + 8 }) := by
  have h := Sem.loop P E pc clearCond (.code clearBody) hAt hW L
    (fun j => clearState pc B L m r j) (fun _ => 6)
    (fun _ => rfl)
    (fun j hj => (clearCond_eval pc B L m r j).mpr hj)
    (fun hf => (Nat.lt_irrefl L) ((clearCond_eval pc B L m r L).mp hf))
    (fun j hj => clearBodyIter P E pc B L m r j hj hAt hW hL hB)
  refine Sem.mono h ?_
  intro k s' hQ
  obtain ⟨hcost, hs⟩ := hQ
  refine ⟨?_, ?_⟩
  · have hsum : (∑ j ∈ Finset.range L, (clearCond.code.length + 1 + 6)) = 8 * L := by
      change (∑ j ∈ Finset.range L, (8 : ℕ)) = 8 * L
      exact sum_range_const_mul L 8
    rw [hsum] at hcost
    change k ≤ 2 + 8 * L at hcost
    omega
  · rw [hs]
    exact clearCond_exit E pc B L m r

/-! ### 2.1 A register preamble, and the composed clearing stage -/

/-- The canonical entry registers of `clearStmt`: `r0 = 0`, `r1 = L`, `r2 = B`, `r3 = 1`,
`r4 = 0`, `r14 = 0`, `r15 = 0`. -/
def clearInit (B L : ℕ) : List Instr :=
  [iImm r0 0, iImm r1 L, iImm r2 B, iImm r3 1, iImm r4 0, iImm r14 0, iImm r15 0]

theorem clearInit_length (B L : ℕ) : (clearInit B L).length = 7 := rfl

theorem clearInit_noBranch (B L : ℕ) : NoBranch (clearInit B L) := by
  simp [clearInit, NoBranch, Instr.NoBranchI]

theorem clearInit_run (E : RAMEnv) (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ)
    (hW : 1 < 2 ^ E.W) (hB : B < 2 ^ E.W) (hL : L < 2 ^ E.W) :
    runBlock (clearInit B L) E ⟨pc, r, m⟩ = clearState (pc + 7) B L m r 0 := by
  have h1 : (1 : ℕ) % 2 ^ E.W = 1 := Nat.mod_eq_of_lt hW
  have hB' : B % 2 ^ E.W = B := Nat.mod_eq_of_lt hB
  have hL' : L % 2 ^ E.W = L := Nat.mod_eq_of_lt hL
  apply ramState_eq_of
  · simp only [clearInit, clearState, runBlock_cons, runBlock_nil, execInstr,
      Function.update_self, Function.update_of_ne, ne_eq, Fin.reduceEq, not_false_eq_true,
      Fin.isValue] <;> omega
  · rfl
  · intro d
    fin_cases d <;>
      simp only [clearInit, clearState, runBlock_cons, runBlock_nil, execInstr, h1, hB', hL',
        Function.update_self, Function.update_of_ne, ne_eq, Fin.reduceEq, not_false_eq_true,
        Fin.isValue, Fin.zero_eta, Fin.mk_one, Fin.reduceFinMk, zero_ne_one, one_ne_zero,
        Nat.zero_mod, ↓reduceIte]

/-- The clearing stage as a `Stmt`: the preamble, then the counted clear loop. -/
def clearFull (B L : ℕ) : Stmt := .seq (.code (clearInit B L)) clearStmt

theorem clearFull_len (B L : ℕ) : (clearFull B L).len = 15 := by
  simp only [clearFull, Stmt.len, clearInit_length, clearStmt, clearCond, clearBody, Cond.code,
    List.length_cons, List.length_nil]

/-- Two runs with bounded costs glue, and the bounds add. -/
theorem Sem.trans_le {P : Program} {E : RAMEnv} {a b c : ℕ} {s : RAMState} {n₁ n₂ : ℕ}
    {s₁ s₂ : RAMState}
    (h₁ : Sem P E a b s (fun k s' => k ≤ n₁ ∧ s' = s₁))
    (h₂ : Sem P E b c s₁ (fun k s' => k ≤ n₂ ∧ s' = s₂)) :
    Sem P E a c s (fun k s' => k ≤ n₁ + n₂ ∧ s' = s₂) := by
  obtain ⟨hpc, k₁, t₁, hs₁, -, hk₁, ht₁⟩ := h₁
  obtain ⟨-, k₂, t₂, hs₂, hc, hk₂, ht₂⟩ := h₂
  refine ⟨hpc, k₁ + k₂, s₂, ?_, ?_, by omega, rfl⟩
  · rw [Nat.add_comm k₁ k₂, Function.iterate_add_apply, hs₁, ht₁, hs₂, ht₂]
  · rw [← ht₂]
    exact hc

/-- **The clearing stage, from the canonical entry state**: it zeroes `[B, B+L)`, leaves
everything else alone, and costs `8L + 9` steps. -/
theorem clearFull_sem (P : Program) (E : RAMEnv) (pc B L : ℕ) (m : ℕ → ℕ) (r : Fin 16 → ℕ)
    (hAt : At P pc (Stmt.compile (clearFull B L) pc))
    (hW : 1 < 2 ^ E.W) (hBs : B < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W) (hL : L < 2 ^ E.W) :
    Sem P E pc (pc + 15) (⟨pc, r, m⟩ : RAMState)
      (fun k s' => k ≤ 15 + 8 * L ∧
        s' = { clearState (pc + 7) B L m r L with pc := pc + 15 }) := by
  have hseq : At P pc (clearInit B L ++ Stmt.compile clearStmt (pc + (clearInit B L).length)) := by
    simpa only [clearFull, Stmt.compile, Stmt.len] using hAt
  have hsplit := At.append.mp hseq
  rw [clearInit_length] at hsplit
  have hinit : Sem P E pc (pc + 7) (⟨pc, r, m⟩ : RAMState)
      (fun k s' => k ≤ 7 ∧ s' = clearState (pc + 7) B L m r 0) := by
    refine Sem.mono (Sem.block P E pc (clearInit B L) _ hsplit.1
      (clearInit_noBranch B L) rfl) ?_
    intro k s' h
    obtain ⟨hk, hs⟩ := h
    exact ⟨by rw [hk, clearInit_length], hs.trans (clearInit_run E pc B L m r hW hBs hL)⟩
  have hclear : Sem P E (pc + 7) (pc + 7 + 8)
      (clearState (pc + 7) B L m r 0)
      (fun k s' => k ≤ 8 * L + 2 ∧
        s' = { clearState (pc + 7) B L m r L with pc := pc + 7 + 8 }) :=
    clearArray_spec P E (pc + 7) B L m r hsplit.2 hW hL hB
  refine Sem.mono (Sem.trans_le hinit hclear) ?_
  intro k s' h
  obtain ⟨hk, hs⟩ := h
  exact ⟨by omega, hs⟩

/-- **The clearing stage, from any state**: it zeroes `[B, B+L)`, leaves everything else alone,
and costs `8L + 9` steps. -/
theorem clearFull_sem_of {P : Program} {E : RAMEnv} {pc B L : ℕ} {s : RAMState}
    (hAt : At P pc (Stmt.compile (clearFull B L) pc))
    (hW : 1 < 2 ^ E.W) (hBs : B < 2 ^ E.W) (hB : B + L ≤ 2 ^ E.W) (hL : L < 2 ^ E.W)
    (hpc : s.pc = pc) :
    Sem P E pc (pc + 15) s
      (fun k s' => k ≤ 15 + 8 * L ∧
        s' = { clearState (pc + 7) B L s.mem s.regs L with pc := pc + 15 }) := by
  rw [← hpc] at hAt ⊢
  exact clearFull_sem P E s.pc B L s.mem s.regs hAt hW hBs hB hL

/-- **The row loop's clearing pass** at the decoder's own footprint `[0, decoderAllocEnd t)`. -/
theorem clearScratch_sem {P : Program} {E : RAMEnv} {pc t : ℕ} {s : RAMState}
    (hAt : At P pc (Stmt.compile (clearFull 0 (decoderAllocEnd t)) pc))
    (hW : 1 < 2 ^ E.W) (hK : decoderAllocEnd t < 2 ^ E.W) (hpc : s.pc = pc) :
    ∃ k s', k ≤ 15 + 8 * decoderAllocEnd t ∧ (step P E)^[k] s = s' ∧
      (∀ a, a < decoderAllocEnd t → s'.mem a = 0) ∧
      (∀ a, decoderAllocEnd t ≤ a → s'.mem a = s.mem a) ∧ s'.pc = pc + 15 := by
  obtain ⟨-, k, s', hstep, -, hk, hs⟩ :=
    clearFull_sem_of (L := decoderAllocEnd t) hAt hW (Nat.two_pow_pos E.W) (by omega) hK hpc
  refine ⟨k, s', hk, hstep, ?_, ?_, ?_⟩
  · intro a ha
    rw [hs]
    show clearMem 0 s.mem (decoderAllocEnd t) a = 0
    simpa using clearMem_get 0 s.mem (decoderAllocEnd t) a ha
  · intro a ha
    rw [hs]
    show clearMem 0 s.mem (decoderAllocEnd t) a = s.mem a
    simpa using clearMem_frame 0 s.mem (decoderAllocEnd t) a (Or.inr (by omega))
  · rw [hs]

/-- The clearing loop alone costs `8·decoderAllocEnd t + 2 = 64t² + 352t + 1154` steps. -/
theorem clearStmt_cost (t : ℕ) :
    8 * decoderAllocEnd t + 2 = 64 * t * t + 352 * t + 1154 := by
  rw [decoderAllocEnd_eq]
  ring

/-- With its 7-instruction register preamble the pass costs `64t² + 352t + 1167`. -/
theorem clearFull_cost (t : ℕ) :
    15 + 8 * decoderAllocEnd t = 64 * t * t + 352 * t + 1167 := by
  rw [decoderAllocEnd_eq]
  ring

/-! ## 3. Per-iteration maintenance of the weak hypothesis -/

/-- Clearing `[0, K)` and then staging the payload at `β` (with `β + L ≤ K`) re-establishes
`PayloadOn` and `WeakZero`, provided memory at `≥ K` is zero.  Nothing outside `[0, K)` and
`[β, β+L)` is read, so this is the whole precondition maintenance of one iteration. -/
theorem weakZero_restage {W M β K : ℕ} (y : Fin M → ZMod 2) (m : ℕ → ℕ)
    (habove : ∀ a, K ≤ a → m a = 0) (hβK : β + wordsOf W M ≤ K) :
    PayloadOn W M β y (fun a => writeArray β (clearMem 0 m K) (fun j => packMem W y j)
        (wordsOf W M) a) ∧
      WeakZero W M β (fun a => writeArray β (clearMem 0 m K) (fun j => packMem W y j)
        (wordsOf W M) a) := by
  have hpay : PayloadOn W M β y (fun a => writeArray β (clearMem 0 m K)
      (fun j => packMem W y j) (wordsOf W M) a) := by
    intro j hj
    show writeArray β (clearMem 0 m K) (fun j => packMem W y j) (wordsOf W M) (β + j)
      = packMem W y j
    exact writeArray_get β _ _ _ j hj
  refine ⟨hpay, ?_, ?_⟩
  · intro a hLa haβ
    show writeArray β (clearMem 0 m K) (fun j => packMem W y j) (wordsOf W M) a = 0
    rw [writeArray_frame β _ _ _ a (Or.inl haβ)]
    simpa using clearMem_get 0 m K a (by omega)
  · intro a ha
    show writeArray β (clearMem 0 m K) (fun j => packMem W y j) (wordsOf W M) a = 0
    by_cases haK : a < K
    · rw [writeArray_frame β _ _ _ a (Or.inr ha)]
      simpa using clearMem_get 0 m K a haK
    · rw [writeArray_frame β _ _ _ a (Or.inr ha)]
      rw [clearMem_frame 0 m K a (Or.inr (by omega))]
      exact habove a (by omega)

/-- Rows are decoded with the payload staged at `β` and the rest of the scratch cleared, so the
decoder's own canonical start state is reproduced: `layerMem` lands on `hintMem`. -/
theorem layerMem_restage {W M β K : ℕ} (y : Fin M → ZMod 2) (m : ℕ → ℕ)
    (habove : ∀ a, K ≤ a → m a = 0) (hβL : wordsOf W M ≤ β)
    (hβK : β + wordsOf W M ≤ K) :
    layerMem W M β y (fun a => writeArray β (clearMem 0 m K) (fun j => packMem W y j)
        (wordsOf W M) a) = hintMem W y ([] : List ℕ) := by
  obtain ⟨hpay, hweak⟩ := weakZero_restage y m habove hβK
  exact layerMem_eq hpay hweak hβL

/-! ### 3.1 One loop iteration out of its stages

The compiled row body is `setup → clear → decode → repack → inc → jmp`.  `Sem.trans` adds exact
costs, and `Sem.jmp_append` folds in the closing jump back to the loop head. -/

/-- **One iteration of the row loop**, from the body entry `a + 2` back to the head `a`, from its
four sub-stages (setup, clear, decode, repack), the two-instruction counter increment, and the
loop's trailing `jmp`. -/
theorem rowBody_sem {P : Program} {E : RAMEnv} {a : ℕ}
    {s0 s1 s2 s3 s4 s5 : RAMState} {su cl dc rp : ℕ}
    (hjmp : P[a + 2 + su + cl + dc + rp + 2]? = some (iJmp a))
    (h1 : Sem P E (a + 2) (a + 2 + su) s0 (fun k z => k = su ∧ z = s1))
    (h2 : Sem P E (a + 2 + su) (a + 2 + su + cl) s1 (fun k z => k = cl ∧ z = s2))
    (h3 : Sem P E (a + 2 + su + cl) (a + 2 + su + cl + dc) s2 (fun k z => k = dc ∧ z = s3))
    (h4 : Sem P E (a + 2 + su + cl + dc) (a + 2 + su + cl + dc + rp) s3
      (fun k z => k = rp ∧ z = s4))
    (h5 : Sem P E (a + 2 + su + cl + dc + rp) (a + 2 + su + cl + dc + rp + 2) s4
      (fun k z => k = 2 ∧ z = s5)) :
    Sem P E (a + 2) a s0
      (fun k z => k = su + cl + dc + rp + 3 ∧ z = { s5 with pc := a }) := by
  have hchain : Sem P E (a + 2) (a + 2 + su + cl + dc + rp + 2) s0
      (fun k z => k = ((su + cl + dc + rp) + 2) ∧ z = s5) :=
    Sem.trans (Sem.trans (Sem.trans (Sem.trans h1 h2) h3) h4) h5
  refine Sem.jmp_append (Q := fun k z => k = su + cl + dc + rp + 3 ∧ z = { s5 with pc := a })
    hjmp ?_
  refine Sem.mono hchain ?_
  intro k z hz
  obtain ⟨hk, hz'⟩ := hz
  subst hk
  subst hz'
  exact ⟨by omega, rfl⟩

/-- **The `d`-fold row loop closes** as soon as the per-iteration body is a `Sem` from the loop
head back to itself — which is exactly what `rowBody_sem` produces.  This is
`haltsWithin_rowLoop_shape` at `pr = 0`, `Kr = cost`: `d` iterations of a constant-cost body cost
`(cost + 5)·d·lg n`. -/
theorem rowLoop_closes {Sinit Srow Sdec Sassem Sres Scr : Stmt} {E : RAMEnv} {n d : ℕ}
    {s : ℕ → RAMState} {cost : ℕ}
    (hW : 1 < 2 ^ E.W)
    (hpc : ∀ j, (s j).pc = dRowBase Sinit)
    (hgo : ∀ j < d, d65Cond.eval (s j)) (hstop : ¬ d65Cond.eval (s d))
    (hbody : ∀ j < d, Sem (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) E
      (dRowBase Sinit + d65Cond.code.length + 1) (dRowBase Sinit)
      { runBlock d65Cond.code E (s j) with pc := dRowBase Sinit + d65Cond.code.length + 1 }
      (fun k s' => k = cost ∧ s' = s (j + 1)))
    (hn : 2 ≤ n) (hd : 1 ≤ d) :
    ∃ (k : ℕ) (s' : RAMState), (k : ℝ) ≤ ((cost : ℝ) + 5) * (d : ℝ) * lg (n : ℝ) ∧
      (step (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) E)^[k] (s 0) = s' ∧
      s'.pc = dColBase Sinit Srow := by
  have hcost : ∀ j < d, (((fun _ => cost) j : ℕ) : ℝ) ≤ (cost : ℝ) * lg (n : ℝ) ^ 0 := by
    intro j hj
    rw [pow_zero, mul_one]
  have h := haltsWithin_rowLoop_shape (cost := fun _ => cost) (Kr := (cost : ℝ)) (pr := 0)
    hW hpc hgo hstop hbody hcost (by positivity) hn hd
  simpa using h

/-! ### 3.2 The frame above the scratch: the one fact the published interface drops

The accepted `verifierProcedure_spec` (`Sol_proposition_2_1.lean:15341–15359`) concludes
`MemoryFrame (verifierWritable V (2*t)) m m'`.  The published `pinsketch_decoder_verifier` (C5)
kept only `decoderPost` and **dropped that conjunct**.  Since
`verifierWritable (decoderVerifyBase t) (2*t)` is contained in `[0, decoderAllocEnd t)`, the frame
is exactly "the verifier leaves memory at `≥ decoderAllocEnd t` alone".  These two lemmas make
that reduction, and the generic preservation step, explicit. -/

/-- The verifier frame implies invariance of everything above the decoder's scratch. -/
theorem verifierFrame_above {m m' : ℕ → ℕ} {t : ℕ}
    (h : MemoryFrame (verifierWritable (decoderVerifyBase t) (2 * t)) m m') :
    ∀ a, decoderAllocEnd t ≤ a → m' a = m a := by
  have hK : (121 : ℕ) < decoderAllocEnd t := by
    rw [decoderAllocEnd_eq]
    have h0 : 8 * t * t + 44 * t ≥ 0 := Nat.zero_le _
    omega
  intro a ha
  refine h a (fun hw => ?_)
  unfold verifierWritable verifierCoreWritable at hw
  have hE : decoderVerifyBase t + 2 * t = decoderAllocEnd t := rfl
  omega

/-- **A frame whose writable set stays inside `[0, K)` preserves zero above `K`.**  This is the
step that turns the three stage frames (`solverInitWritable`, `rootSearchWritable`,
`verifierWritable`, all inside the scratch) into "the decoder never dirties `[K, ∞)`". -/
theorem zero_above_of_frame {K : ℕ} {A : ℕ → Prop} {m m' : ℕ → ℕ}
    (hA : ∀ a, A a → a < K) (hframe : MemoryFrame A m m')
    (hzero : ∀ a, K ≤ a → m a = 0) :
    ∀ a, K ≤ a → m' a = 0 := by
  intro a ha
  have hnot : ¬ A a := fun hc => absurd (hA a hc) (by omega)
  rw [hframe a hnot]
  exact hzero a ha

/-! ## 4. The scratch is provably dirty after the key-solver stage

`pinsketch_decoder_key_solver`'s own postcondition contains `KeyReady`, whose `savedBase` field
reads `m 79 = decoderSavedBase t = 128 + 3t`.  Slot `79` is strictly inside the decoder's scratch
`[0, decoderAllocEnd t)`.  So "the decoder is idempotent on its scratch" is false at the
read + key-solver prefix: at least one word of the scratch is nonzero, for *every* input.  (The
published postcondition of the last stage, `pinsketch_decoder_verifier`, constrains memory only
through `outList`, i.e. the `regs 1` output words at `regs 0`; it says nothing about the rest of
the scratch, so no zero-after-run statement is derivable from the platform interface.) -/

theorem keySolver_scratch_dirty {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F]
    {w : ℕ} {b : Module.Basis (Fin w) (ZMod 2) F} {E : RAMEnv} {t N : ℕ} {e : ℕ → F}
    {m : ℕ → ℕ} (h : KeyReady b E t N e m) :
    ∃ a, a < decoderAllocEnd t ∧ m a ≠ 0 := by
  refine ⟨79, ?_, ?_⟩
  · rw [decoderAllocEnd_eq]; omega
  · rw [h.savedBase]
    unfold decoderSavedBase
    omega

/-- The same, directly from the published stage theorem: *every* run of the key-solver stage ends
with a nonzero word strictly inside the scratch. -/
theorem keySolver_post_dirty {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F]
    {w : ℕ} (b : Module.Basis (Fin w) (ZMod 2) F) (ι : ℕ → F) (t N : ℕ)
    (P : Program) (E : RAMEnv) (pc : ℕ) (e : ℕ → F) (m : ℕ → ℕ)
    (hAt : At P pc (Stmt.compile keySolverProcedure pc))
    (hw : 1 ≤ w) (hW : E.W = 8 * w) (hdet : E.det = detStd t N b ι) (ht : 1 ≤ t)
    (hEnd : decoderAllocEnd t < 2 ^ E.W) (h0 : ι 0 ≠ 0)
    (hh0 : E.det 0 % 2 ^ E.W = t) (hh1 : E.det 1 % 2 ^ E.W = w)
    (hh2 : E.det 2 % 2 ^ E.W = N)
    (hSaved : FieldArrayStored b m (decoderSavedBase t) (2 * t) e)
    (hTail : ∀ addr, decoderSavedBase t + 2 * t ≤ addr → m addr = 0) :
    ∃ (k : ℕ) (m' : ℕ → ℕ), k ≤ (34 * decoderCapacity t +
        (48 * decoderLength t + 187) * decoderLength t + 289) * decoderLength t +
        12 * decoderCapacity t + 385 ∧
      KeyReady b E t N e m' ∧ ∃ a, a < decoderAllocEnd t ∧ m' a ≠ 0 := by
  obtain ⟨-, k, z, hstep, -, hQ⟩ :=
    pinsketch_decoder_key_solver b ι t N P E pc e m hAt hw hW hdet ht hEnd h0 hh0 hh1 hh2 hSaved hTail
  obtain ⟨hk, m', -, hready, -⟩ := hQ
  exact ⟨k, m', hk, hready, keySolver_scratch_dirty hready⟩

/-- **The slot-79 obstruction bites the *weakened* hypothesis too**, whenever the payload base `β`
lies above the decoder's saved-syndrome block.  For `L = wordsOf W (t*w) ≤ 79` the cell `79` is in
the required-zero region `[L, β)` and is nonzero. -/
theorem keySolver_blocks_weakZero {F : Type} [Field F] [DecidableEq F] [Algebra (ZMod 2) F]
    {w : ℕ} {b : Module.Basis (Fin w) (ZMod 2) F} {E : RAMEnv} {t N : ℕ} {e : ℕ → F}
    {m : ℕ → ℕ} {β W : ℕ} (h : KeyReady b E t N e m)
    (hL : wordsOf W (t * w) ≤ 79) (hβ : 79 < β) :
    ¬ WeakZero W (t * w) β m := by
  intro hw
  have h0 : m 79 = 0 := hw.1 79 hL hβ
  rw [h.savedBase] at h0
  unfold decoderSavedBase at h0
  omega

end R66
end LinearSetReconciliation327.Main
Source
arXiv:2611.11409 (Liu, Xu, Yang, Zhou, *Linear Set Reconciliation with O(d) Additive Redundancy*), §2.1 (word-RAM model) and Theorem 6.5 (row stage); verified development of the project.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me