Lemma 18 — generalized agreement lemma
ProvedSymmetricPSM1041.ORLowerBound.Supplement.generalized_agreement_lemmacommunication-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1support-privacy
For every fixed there is , depending only on , with the following property. Let be integers, a finite alphabet, and a coloring for every . Let
and suppose that for all the functions and disagree on more than points. Then
This is the source's . The lemma drives the alphabet lower bounds for exact majority and modular counting (Theorems 23 and 24).
Formalization Note The chain is a strictly increasing map from Fin ℓ (index ) to finite subsets of Fin n. The disagreement count is taken over points lying in both sets, which for is the set of points of .
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: |Σ| = Ω_a(√p) → ∃ c > 0 depending only on a, with c·√p ≤ |Σ| for every p ≥ 1 (no threshold on p); reason: for p below any threshold P0 the hypotheses force ℓ ≥ 1 and hence Σ nonempty, so |Σ| ≥ 1 ≥ √p/√P0; shrinking c removes the threshold, so the two forms are equivalent
Preamble
import Mathlib
Formal statement
namespace SymmetricPSM1041.ORLowerBound.Supplement
open Classical in
theorem generalized_agreement_lemma :
∀ a : ℝ, 0 < a → ∃ c : ℝ, 0 < c ∧
∀ n p : ℕ, 1 ≤ p → p ≤ n →
∀ (Sig : Type*) [Fintype Sig],
∀ α : (S : Finset (Fin n)) → (i : Fin n) → i ∈ S → Sig,
∀ ℓ : ℕ, a * Real.sqrt p ≤ ℓ →
∀ Sq : Fin ℓ → Finset (Fin n), StrictMono Sq →
(∀ i : Fin ℓ, (Sq i).card = p + (i.val + 1)) →
(∀ i j : Fin ℓ, i < j →
p < (Finset.univ.filter (fun t : Fin n => ∃ (hti : t ∈ Sq i) (htj : t ∈ Sq j),
α (Sq i) t hti ≠ α (Sq j) t htj)).card) →
c * Real.sqrt p ≤ (Fintype.card Sig : ℝ) := by sorry
end SymmetricPSM1041.ORLowerBound.Supplement
Source
Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior, STOC 2027 submission #1041 (October 2026), p. 14, Lemma 18 (proof p. 14)