Theorem 6.5, conjunct 8: the composite decoder recovers every d-sparse set with probability 1 - epsilon
ProvedLinearSetReconciliation327.Main.conjunct8_topDecConjunct 8 of Theorem 6.5 at the composite decoder. Let be the six compiled statements of the §9.2 decoder, and let
be their composite, terminating in a halt. Fix a table specification spec, a seed-indexed deterministic table det, a seed-indexed linear sketch , constants and , and the decoding budget
Assume:
- the decoder halts — for every seed and every stored payload there is a halting run of under the environment , started from , of length at most (this is conjunct 7);
- worst-case correctness per seed — for every seed , every and every halting run of from of length at most , the final state's output list is exactly .
Then for every -sparse ,
In words: the composite decoder recovers every -sparse set from its sketch, except with probability at most 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 , and for . The 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.
import Definitions.Def_LinearSetReconciliation327_Main_Top65Correct
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