Lemma A.1 — Heavy-coordinate majority decoding
OpenBirthdayEntropy.Soundness.Supplement.lemma_A_1graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , , , and let be a set of exactly distinct Boolean labelled views. Sample selected vertices independently and uniformly with replacement. Write , , and let choose any majority bit on every heavy coordinate with , where is its incidence in the original . Let be the original-family fraction disagreeing with on at least one heavy coordinate, the strict low-incidence complement, and .
Then
The bound permits every majority tie-breaking choice and supplies the heavy-coordinate error estimate for agreement stability.
Differences from the source:
- encoding: a set of K distinct Boolean labelled views → a Finset of published Vertex (Fin n coordinates) with card = choose n ell; reason: finite sets enforce distinctness and represent every source selection; normalization is unchanged
- encoding: a partial majority assignment on heavy coordinates → a total Boolean assignment constrained only on heavy coordinates; reason: every partial assignment extends; all extensions give the same survivor family and heavy error
Preamble
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Agreement
Formal statement
namespace BirthdayEntropy.Soundness.Supplement
/-- Lemma A.1, PDF p18 / printed p17. Any heavy-coordinate majority choice. -/
theorem lemma_A_1 (n ℓ : ℕ) (hn : 1 ≤ n) (hℓ : 1 ≤ ℓ) (hℓn : ℓ ≤ n)
(H : Finset (Vertex n ℓ)) (hH : H.card = Nat.choose n ℓ)
(g : Fin n → Bool) (hg : IsMajority H g) :
heavyError H g ≤ 16 * qcon H / ratio n ℓ := by sorry
end BirthdayEntropy.Soundness.Supplement
Source
Alexandru Popa, STOC 2027 submission #907 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/907.pdf, Lemma A.1, PDF p18 / printed p17