Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.5, conjunct 8: the composite decoder recovers every d-sparse set with probability 1 - epsilon

Proved
LinearSetReconciliation327.Main.conjunct8_topDec

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

correctnessdecoderlinear-set-reconciliationprobabilitytheorem-6-5

Conjunct 8 of Theorem 6.5 at the composite decoder. Let Sinit,Srow,Sdec,Sassem,Sres,ScrS_{\mathrm{init}},S_{\mathrm{row}},S_{\mathrm{dec}},S_{\mathrm{assem}},S_{\mathrm{res}},S_{\mathrm{cr}}Sinit​,Srow​,Sdec​,Sassem​,Sres​,Scr​ be the six compiled statements of the §9.2 decoder, and let

progDecOfTop(Sinit,…,Scr)\mathrm{progDecOfTop}(S_{\mathrm{init}},\dots,S_{\mathrm{cr}})progDecOfTop(Sinit​,…,Scr​)

be their composite, terminating in a halt. Fix a table specification spec, a seed-indexed deterministic table det, a seed-indexed linear sketch Hr ⁣:F2n→F2MH_r\colon \mathbb{F}_2^n\to\mathbb{F}_2^MHr​:F2n​→F2M​, constants Cd>0C_d>0Cd​>0 and ε≥0\varepsilon\ge 0ε≥0, and the decoding budget

Tdec  =  Cd d exp⁡ ⁣(Cd (lg⁡lg⁡n)2).T_{\mathrm{dec}} \;=\; C_d\, d\, \exp\!\bigl(C_d\,(\lg\lg n)^2\bigr).Tdec​=Cd​dexp(Cd​(lglgn)2).

Assume:

  1. the decoder halts — for every seed rrr and every stored payload y∈F2My\in\mathbb{F}_2^My∈F2M​ there is a halting run of progDecOfTop\mathrm{progDecOfTop}progDecOfTop under the environment spec.env(W,det,r)\mathrm{spec.env}(W,\mathrm{det},r)spec.env(W,det,r), started from decoderStart(W,y,[])\mathrm{decoderStart}(W,y,[])decoderStart(W,y,[]), of length at most TdecT_{\mathrm{dec}}Tdec​ (this is conjunct 7);
  2. worst-case correctness per seed — for every seed rrr, every x∈F2nx\in\mathbb{F}_2^nx∈F2n​ and every halting run of progDecOfTop\mathrm{progDecOfTop}progDecOfTop from decoderStart((spec.env(W,det,r)).W,Hrx,[])\mathrm{decoderStart}((\mathrm{spec.env}(W,\mathrm{det},r)).W, H_r x, [])decoderStart((spec.env(W,det,r)).W,Hr​x,[]) of length at most TdecT_{\mathrm{dec}}Tdec​, the final state's output list is exactly supp⁡x\operatorname{supp} xsuppx.

Then for every ddd-sparse x∈F2nx\in\mathbb{F}_2^nx∈F2n​,

1−ε  ≤  Pr⁡r[  ∃s′, HaltsWithin progDecOfTop (spec.env(W,det,r)) Tdec (decoderStart(W,Hrx,[])) s′ ∧ OutputsSupport s′ x  ].1-\varepsilon \;\le\; \Pr_{r}\Bigl[\;\exists s',\ \mathrm{HaltsWithin}\ \mathrm{progDecOfTop}\ (\mathrm{spec.env}(W,\mathrm{det},r))\ T_{\mathrm{dec}}\ \bigl(\mathrm{decoderStart}(W,H_r x,[])\bigr)\ s' \ \wedge\ \mathrm{OutputsSupport}\ s'\ x\;\Bigr].1−ε≤rPr​[∃s′, HaltsWithin progDecOfTop (spec.env(W,det,r)) Tdec​ (decoderStart(W,Hr​x,[])) s′ ∧ OutputsSupport s′ x].

In words: the composite decoder recovers every ddd-sparse set from its sketch, except with probability at most ε\varepsilonε over the seed — which is exactly the last conjunct of theorem_6_5, with progDec instantiated at the composite and Tdec at the paper's budget.

Why it is a theorem and not a restatement. The proof is not a composition of probabilities: because the correctness hypothesis is worst case and holds at every seed, the recovery event holds at every seed, so its probability is 111, and 1−ε≤11-\varepsilon\le 11−ε≤1 for ε≥0\varepsilon\ge0ε≥0. The ε\varepsilonε of Theorem 6.5 can therefore only enter through the six stages' own failure probabilities, never through the composition. The six stage contracts and their composition into hypothesis 2 are a separate node; hypothesis 1 is haltsWithin_topDec_final.

Formalization Note The submission is the 484-line block Solutions/_65_correct_block.lean.txt plus a root-level theorem solution; it imports only Mathlib and Definitions.Def_LinearSetReconciliation327_Main_Top65Correct, contains no sorry/admit, and #print axioms solution reports [propext, Classical.choice, Quot.sound]. The hypothesis hCorr is written out rather than as the block's C8.TopDecCorrectsSeed, because the platform preamble may contain only import Definitions.Def_* lines and that predicate lives in the solution block; the two types are definitionally equal, and the proof file bridges them with a have.

Preamble
import Definitions.Def_LinearSetReconciliation327_Main_Top65Correct
Formal statement
namespace LinearSetReconciliation327.Main

theorem conjunct8_topDec {Sinit Srow Sdec Sassem Sres Scr : Stmt} {W M n d : ℕ} {spec : TableSpec}
    (det : ℕ → ℕ) (H : spec.Seed → (Fin n → ZMod 2) →ₗ[ZMod 2] (Fin M → ZMod 2))
    {Cd eps : ℝ} (heps : 0 ≤ eps)
    (hHalt : ∀ (r : spec.Seed) (y : Fin M → ZMod 2), ∃ s' : RAMState,
      HaltsWithin (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) (spec.env W det r)
        (Cd * (d : ℝ) * Real.exp (Cd * lg (lg (n : ℝ)) ^ 2)) (decoderStart W y []) s')
    (hCorr : ∀ (r : spec.Seed) (x : Fin n → ZMod 2) (s' : RAMState),
      (∃ k : ℕ, (k : ℝ) ≤ Cd * (d : ℝ) * Real.exp (Cd * lg (lg (n : ℝ)) ^ 2) ∧
        (step (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) (spec.env W det r))^[k]
          (decoderStart (spec.env W det r).W (H r x) []) = s' ∧
        Halted (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) s') →
      OutputsSupport s' x) :
    ∀ x : Fin n → ZMod 2, (Finset.univ.filter fun i => x i = 1).card ≤ d →
      1 - eps ≤ prU (fun r : spec.Seed => ∃ s' : RAMState,
        HaltsWithin (progDecOfTop Sinit Srow Sdec Sassem Sres Scr) (spec.env W det r)
          (Cd * (d : ℝ) * Real.exp (Cd * lg (lg (n : ℝ)) ^ 2))
          (decoderStart W (H r x) []) s' ∧
        OutputsSupport s' x) := by sorry

end LinearSetReconciliation327.Main
Source
arXiv:2611.11409 (Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, *Linear Set Reconciliation with O(d) Additive Redundancy*), Theorem 6.5, PDF p.31 (printed p.30), last conjunct (`6toplevel.tex` lines 259-271, identical to Theorem 1.1); decoder of §9.2. Proved in `Solutions/_65_correct_block.lean.txt`.

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