Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 18 — exact agreement under a local distance guarantee

Open
AgreementTop736.Exact.Supplement.theorem_18

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

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

Let P0,…,PkP_0,\ldots,P_kP0​,…,Pk​ be a finite coherent layered poset of subsets of a finite ground set XXX, with layer cardinalities qjq_jqj​, positive subface counts di,jd_{i,j}di,j​, and an arbitrary top probability law μ\muμ. Fix h<kh<kh<k, 0<κ≤10<\kappa\le10<κ≤1, and a rank r∈R(κ)r\in R(\kappa)r∈R(κ) with ξk,r>0\xi_{k,r}>0ξk,r​>0. Here r∈R(κ)r\in R(\kappa)r∈R(κ) means that any error set occupying at least a κ\kappaκ fraction of an rrr-face in a supported top face is hit by a uniform hhh-face with probability at least 1/21/21/2. The detection parameter ξk,r\xi_{k,r}ξk,r​ is defined by (13)–(14).

Let FK:K→ΣF_K:K\to\SigmaFK​:K→Σ be local assignments in any finite alphabet. For each s∈{h,r}s\in\{h,r\}s∈{h,r}, suppose there exists a global assignment gsg_sgs​ with

Pr⁡K∼μ, S∼Ds(⋅∣K)[FK∣S≠gs∣S]≤Asτs,\Pr_{K\sim\mu,\ S\sim D_s(\cdot\mid K)}[F_K|_S\ne g_s|_S]\le A_s\tau_s,K∼μ, S∼Ds​(⋅∣K)Pr​[FK​∣S​=gs​∣S​]≤As​τs​,

where DsD_sDs​ samples a uniform sss-face inside KKK, and τs\tau_sτs​ is the exact (k,s)(k,s)(k,s)-test rejection probability. The two witnesses may differ. Suppose distinct restrictions of actual local assignments from any supported parents to any positive-mass rrr-face RRR differ in at least θr∣R∣\theta_r|R|θr​∣R∣ coordinates, with θr≥2κ\theta_r\ge2\kappaθr​≥2κ.

There is a globally optimal assignment ggg for which

Δ(F)=Pr⁡K[FK≠g∣K]≤4AhArξk,rτh.\Delta(F)=\Pr_K[F_K\ne g|_K]\le\frac{4A_hA_r}{\xi_{k,r}}\tau_h.Δ(F)=KPr​[FK​=g∣K​]≤ξk,r​4Ah​Ar​​τh​.

The constants AsA_sAs​ are real inputs to the deviation premises. There is no additional sign condition on them, no ordering condition between hhh and rrr, and no spectral hypothesis. Equality θr=2κ\theta_r=2\kappaθr​=2κ is included.

This companion theorem transfers the two per-layer deviation estimates to an exact global agreement bound on the general coherent layered poset.

Differences from the source:

  • encoding: finite coherent layered poset and its induced probability laws → finite face families with the coherence denominator cleared, and the published scheme instantiated at each tested rank with the same top law; reason: positive subface counts make the cleared identity equivalent and yield exactly the uniform subface, marginal and independent conditional-parent laws
  • encoding: ξ_{k,r} detects every nonempty error set → the finite minimum of singleton inclusion probabilities over supported top-element pairs; reason: equation (14) explicitly identifies the two minima; zero-mass faces are omitted throughout Section 2
  • encoding: local assignments on faces, distinct restrictions on r-faces and separate global witnesses g_s → total extensions with all comparisons restricted to their faces, supported parents and faces, and an existential deviation witness at each of h and r; reason: this represents every source instance, permits equal restrictions, and does not identify the two witnesses
  • encoding: Δ is the minimum global disagreement and Δ≤4 A_h A_r τ_h/ξ_{k,r} → a global minimizer is exhibited and its disagreement obeys the identical bound; reason: the alphabet and ground set are finite and F_∅ supplies a global candidate, so the minimum is attained
Preamble
import Mathlib
import Definitions.Def_AgreementTop736_Exact_Supplement_Transfer
Formal statement
namespace AgreementTop736.Exact.Supplement

/-- Theorem 18, p.16, (15)–(16). The two deviation witnesses may differ.
There is no ordering premise between h and r, no spectral premise, and no added
sign premise on A_h or A_r. The conclusion includes attainment of Δ. -/
theorem theorem_18 {V : Type*} [Fintype V] [DecidableEq V]
    {α : Type*} [Fintype α] [DecidableEq α]
    (P : LayeredPoset V) (hP : P.IsCoherent)
    (h r : ℕ) (hh : h < P.k) (κ : ℝ) (hκ : 0 < κ) (hκ1 : κ ≤ 1)
    (hr : P.IsHittingRank h r κ) (hξ : 0 < P.detectionMinimum r)
    (F : Finset V → V → α) (A : ℕ → ℝ) (θr : ℝ)
    (hdevh : P.HasDeviationBound h F (A h)) (hdevr : P.HasDeviationBound r F (A r))
    (hθ : 2 * κ ≤ θr) (hdist : P.HasRestrictedDistance r F θr) :
    ∃ g : V → α,
      P.optimalDistance F = (P.scheme h).disagreementProb F g ∧
      (P.scheme h).disagreementProb F g ≤
        (4 * A h * A r / P.detectionMinimum r) * (P.scheme h).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.16, Theorem 18. 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