Lemma 4.8 — Concentration of column counts and residual
ProvedLinearSetReconciliation327.Main.lemma_4_8linear-sketchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1set-reconciliationsparse-recovery
Fix a node's input and hint , with rows and , . If each final row estimate of the exact execution has at most positions, then for all and columns : , , and .
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
- generalization: a node of the top layer or of HintSketch → any RowScheme: any row code, prediction and final-recovery procedures; reason: the proof uses only that a row reads its local support, local hint and coins; both constructions are RowSchemes, so the source claim is an instance
- encoding: Pr and E over the node randomness → uniform averages over the finite type of a permutation of [N] and the row coins; reason: this is the source law; coins for indices up to N_max beyond a shorter row are never read
Preamble
import Mathlib import Definitions.Def_LinearSetReconciliation327_Main_Basic import Definitions.Def_LinearSetReconciliation327_Main_Framework open scoped ENNReal open Finset
Formal statement
namespace LinearSetReconciliation327.Main
/-- Lemma 4.8 (Concentration), PDF p.18 (printed p.17), for a node of any row scheme. -/
theorem lemma_4_8 (sch : RowScheme) (x J : Finset ℕ) (hx : x ⊆ range sch.N) (hJ : J ⊆ range sch.N)
(hm : 1 ≤ sch.m) (D : ℕ) (hD : sch.m ≤ D) (hDJ : (J ∪ x).card ≤ D) (K : ℕ) (hK : 1 ≤ K)
(hest : ∀ (lr : sch.LocalSeed) (j : Fin sch.m), (sch.exactRowEst lr x J j).card ≤ K)
(Δ : ℝ) (hΔ : 0 < Δ) :
(∀ s : Fin sch.ℓ,
prU (fun lr : sch.LocalSeed => expU (fun lr' : sch.LocalSeed => (sch.U lr' x J s : ℝ)) + Δ <
(sch.U lr x J s : ℝ)) ≤ Real.exp (-(2 * Δ ^ 2 / (5 * (D : ℝ))))) ∧
(∀ s : Fin sch.ℓ,
prU (fun lr : sch.LocalSeed => expU (fun lr' : sch.LocalSeed => (sch.V lr' x J s : ℝ)) + Δ <
(sch.V lr x J s : ℝ)) ≤ Real.exp (-(2 * Δ ^ 2 / (5 * (D : ℝ))))) ∧
prU (fun lr : sch.LocalSeed => expU (fun lr' : sch.LocalSeed => (sch.Z lr' x J : ℝ)) + Δ <
(sch.Z lr x J : ℝ)) ≤ Real.exp (-(Δ ^ 2 / (10 * (D : ℝ) * (K : ℝ) ^ 2))) := by sorry
end LinearSetReconciliation327.Main
Source
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, STOC 2027 submission #327 (October 2026), Lemma 4.8, PDF p.18 (printed p.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.