Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9 — average Hamming, exact and approximate agreement bounds

Open
AgreementTop736.Exact.Supplement.theorem_9

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

agreement-testingcombinatoricsmarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let XXX and Σ\SigmaΣ be finite. A valid sampling scheme has top size qkq_kqk​, tested size qhq_hqh​, and 0<qh<qk0<q_h<q_k0<qh​<qk​. Let ax>0a_x>0ax​>0 be the parent-independent inclusion probability for each element of positive marginal mass, and let ξ=min⁡xax\xi=\min_x a_xξ=minx​ax​ on that support. Suppose every element-conditioned stationary top–test–top chain has spectral gap at least γ>0\gamma>0γ>0. For any local functions FK:K→ΣF_K:K\to\SigmaFK​:K→Σ, let τ\tauτ be the rejection probability of the exact equality test, with independent parents conditional on the sampled test face.

A coordinatewise majority exists. Every such majority ggg, including every tie choice, satisfies all four conclusions:

EKd(FK,g∣K)≤qhγξτ,\mathbb E_K d(F_K,g|_K)\le\frac{q_h}{\gamma\xi}\tau,EK​d(FK​,g∣K​)≤γξqh​​τ, Pr⁡K[FK≠g∣K]≤qhγξτ,\Pr_K[F_K\ne g|_K]\le\frac{q_h}{\gamma\xi}\tau,KPr​[FK​=g∣K​]≤γξqh​​τ, ∀δ>0,Pr⁡K[d(FK,g∣K)≥δqk]≤qhγξδqkτ,\forall\delta>0,\qquad\Pr_K[d(F_K,g|_K)\ge\delta q_k]\le\frac{q_h}{\gamma\xi\delta q_k}\tau,∀δ>0,KPr​[d(FK​,g∣K​)≥δqk​]≤γξδqk​qh​​τ,

and, if ax=qh/qka_x=q_h/q_kax​=qh​/qk​ for every supported element,

EKd(FK,g∣K)qk≤τγ.\mathbb E_K\frac{d(F_K,g|_K)}{q_k}\le\frac{\tau}{\gamma}.EK​qk​d(FK​,g∣K​)​≤γτ​.

Here ddd counts differing coordinates, and the majority maximizes the label frequency under μ(⋅∣x∈K)\mu(\cdot\mid x\in K)μ(⋅∣x∈K). The inclusion probabilities may vary with xxx in the first three bounds; no variance assumption is made.

This companion theorem gives an average coordinate-error bound and its exact and approximate agreement consequences, while keeping the stronger normalized clause in the uniform-inclusion case.

Differences from the source:

  • encoding: finite probability laws and local functions on their faces → finite weighted sums over subsets and total extensions F_K on X, with comparisons restricted to K or H; reason: every source assignment extends and all extra values have no effect; all conditional hypotheses omit zero-mass faces as in Section 2
  • encoding: spectral gap of each stationary element-conditioned walk → the published Poincaré inequality with Dirichlet factor 1/2; reason: positive parent-independent inclusion gives the reversible stationary law μ_x by Section 2.2, making this the paper’s equivalent gap convention
  • encoding: ξ=min_x a_x and the coordinatewise majority with arbitrary ties → the finite minimum on positive element support, existence of a majority, and bounds for every majority choice; reason: Section 2 omits zero-mass faces; valid sampling ensures nonempty support and a finite alphabet attains every maximum
Preamble
import Mathlib
import Definitions.Def_AgreementTop736_Exact_Supplement_Hamming
Formal statement
namespace AgreementTop736.Exact.Supplement

/-- Theorem 9, p.12, all four conclusions. The Poincaré gap has the published 1/2
normalization. No uniform-inclusion or variance premise is assumed. -/
theorem theorem_9 {V : Type*} [Fintype V] [DecidableEq V]
    {α : Type*} [Fintype α] [DecidableEq α]
    (S : Scheme V) (hS : S.IsValid) (a : V → ℝ)
    (ha : ParentIndependentInclusion S a) (γ : ℝ) (hγ : 0 < γ)
    (hgap : S.HasConditionedGap γ) (F : Finset V → V → α) :
    (∃ g : V → α, S.IsCoordMajority F g) ∧
    ∀ g : V → α, S.IsCoordMajority F g →
      averageError S F g ≤ (S.n : ℝ) / (γ * inclusionMinimum S a) * S.rejectionProb F ∧
      S.disagreementProb F g ≤ (S.n : ℝ) / (γ * inclusionMinimum S a) * S.rejectionProb F ∧
      (∀ δ : ℝ, 0 < δ → approximateDisagreementProb S F g δ ≤
        (S.n : ℝ) / (γ * inclusionMinimum S a * δ * (S.N : ℝ)) * S.rejectionProb F) ∧
      ((∀ x, 0 < S.pointMass x → a x = (S.n : ℝ) / (S.N : ℝ)) →
        normalizedAverageError S F g ≤ S.rejectionProb F / γ) := by sorry

end AgreementTop736.Exact.Supplement
Source
Tali Kaufman, Huy Tuan Pham, Exact Agreement Expansion up to the Top via Non-polarity, STOC 2027 submission #736 (October 2026), p.12, Theorem 9. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/736.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me