Lemma 4.3 — Separation by random binary measurements
ProvedLinearSetReconciliation327.Main.lemma_4_3linear-sketchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1set-reconciliationsparse-recovery
For each let be independent and uniform, with . For a fixed and family , .
Differences from the source:
- encoding: 0-based or 1-based coordinates [N] → 0-based Fin N or range N, with supports as finite sets and vector addition as symmetric difference; reason: the source identifies subsets with characteristic vectors and any injection relabels the coordinates
Preamble
import Mathlib import Definitions.Def_LinearSetReconciliation327_Main_Basic open scoped ENNReal open Finset
Formal statement
namespace LinearSetReconciliation327.Main
/-- Lemma 4.3 (Separation by random binary measurements), PDF p.17 (printed p.16). -/
theorem lemma_4_3 (N q : ℕ) (S : Finset (Fin N)) (A : Finset (Finset (Fin N))) :
prU (fun β : Fin N → Fin q → ZMod 2 =>
∃ C ∈ A.erase S, ∑ v ∈ C, β v = ∑ v ∈ S, β v) ≤
((A.erase S).card : ℝ) * ((2 : ℝ) ^ q)⁻¹ := by sorry
end LinearSetReconciliation327.Main
Source
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, STOC 2027 submission #327 (October 2026), Lemma 4.3, PDF p.17 (printed p.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.