Theorem 2.3 — Unrestricted multi-answer agreement stability
OpenBirthdayEntropy.Soundness.Supplement.theorem_2_3graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , and . Let be any set of exactly distinct pairs , with and . For independent uniform selected vertices sampled with replacement, let be the probability of any conflicting bit on their common coordinates. Let count all views whose restriction belongs to , and . Then
This companion theorem has no CSP or small-error hypothesis. It includes missing views, multiple answers, , and . It is not used in the proof of Theorem 2.1; it also supports Theorem B.3.
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: maximum over all global assignments → sup' of the nonempty finite set of Boolean assignments; reason: a finite maximum is attained; there is no default empty or unbounded real supremum
Preamble
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Agreement
Formal statement
namespace BirthdayEntropy.Soundness.Supplement
/-- Theorem 2.3, PDF p4 / printed p3. Companion theorem; not used in the
proof of the goal. Full view range and arbitrary K-element vertex sets. -/
theorem theorem_2_3 (n ℓ : ℕ) (hn : 1 ≤ n) (hℓ : 1 ≤ ℓ) (hℓn : ℓ ≤ n)
(H : Finset (Vertex n ℓ)) (hH : H.card = Nat.choose n ℓ) :
fstar H ≤ 34 * ((n : ℝ) / ℓ) * qcon H := 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, Theorem 2.3, PDF p4 / printed p3