Lemma 16 — agreement lemma for majority
ProvedSymmetricPSM1041.ORLowerBound.Supplement.agreement_lemma_majoritycommunication-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1support-privacy
Write . There are an absolute constant and a threshold such that the following holds for every . Let be a finite alphabet with , and suppose that for every with we are given a coloring . Then there are sets with and such that
- , and
- and disagree on at most points:
Both sets are nonempty, since . The lemma is the combinatorial core of the alphabet lower bound for majority (Theorem 22).
Formalization Note is written (n + 1) / 2 - 1 + 1 in natural numbers, which equals for . The family takes the set together with the proof of its size bound.
Differences from the source:
- encoding: parties indexed by [n]={1,…,n} → parties indexed by Fin n; reason: the bijection i↦i+1 preserves every input and coordinate subset
- encoding: an arbitrary finite alphabet Σ → a finite type Sig in an arbitrary universe; reason: every finite set is in bijection with a finite type; only |Σ| enters the statement
- encoding: for sufficiently large n and a sufficiently small absolute constant c0 > 0 → ∃ c0 > 0, ∃ N ≥ 1, ∀ n ≥ N; reason: this is the meaning of the two existential constants; c0 and N do not depend on Σ or the family
Preamble
import Mathlib
Formal statement
namespace SymmetricPSM1041.ORLowerBound.Supplement
open Classical in
theorem agreement_lemma_majority :
∃ c₀ : ℝ, 0 < c₀ ∧ ∃ N : ℕ, 1 ≤ N ∧ ∀ n : ℕ, N ≤ n →
∀ (Sig : Type*) [Fintype Sig], (Fintype.card Sig : ℝ) ≤ c₀ * Real.sqrt n →
∀ α : (S : Finset (Fin n)) → (n + 1) / 2 - 1 + 1 ≤ S.card → (i : Fin n) → i ∈ S → Sig,
∃ (T S : Finset (Fin n)) (hT : (n + 1) / 2 - 1 + 1 ≤ T.card)
(hS : (n + 1) / 2 - 1 + 1 ≤ S.card), T ⊂ S ∧
(Finset.univ.filter (fun i : Fin n => ∃ (hiT : i ∈ T) (hiS : i ∈ S),
α T hT i hiT ≠ α S hS i hiS)).card ≤ (n + 1) / 2 - 1 := by sorry
end SymmetricPSM1041.ORLowerBound.Supplement
Source
Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior, STOC 2027 submission #1041 (October 2026), p. 13, Lemma 16 (proof pp. 13–14)