Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem B.3 — Ternary compatibility graph soundness

Open
BirthdayEntropy.Soundness.Supplement.theorem_B_3

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

graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let Φ\PhiΦ be any indexed Boolean CSP on nnn variables with arbitrary predicates on exactly three distinct variables per constraint. Suppose every global assignment ggg has a family of at least γn\gamma nγn violated constraints with pairwise disjoint scopes; this family may depend on ggg. Assume 0<γ≤1/30<\gamma\le1/30<γ≤1/3, n≥16/γn\ge16/\gamman≥16/γ, and 2≤ℓ≤n2\le\ell\le\sqrt n2≤ℓ≤n​. Let K=(nℓ)K=\binom n\ellK=(ℓn​). For every set HHH of exactly KKK distinct vertices of the published compatibility graph GΦ,ℓG_{\Phi,\ell}GΦ,ℓ​,

density⁡Φ(H)≤1−γ2ℓ313600n2.\operatorname{density}_{\Phi}(H)\le1-\frac{\gamma^2\ell^3}{13600n^2}.densityΦ​(H)≤1−13600n2γ2ℓ3​.

Density counts unordered distinct edges. The quantification includes missing views, multiple different answers on one view, and locally invalid isolated vertices. There is no bounded-occurrence, nonisolation, CNF or base-gap assumption. This companion additive soundness theorem is not used in the proof of Theorem 2.1.

Differences from the source:

  • encoding: 2 <= ell <= sqrt(n) → natural-number ell with 2 <= ell and ell^2 <= n; reason: these conditions are equivalent on nonnegative integers
  • 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: a Boolean ternary CSP with assignment-dependent disjoint violations → published indexed CSP and forall g exists J of pairwise disjoint violated indices; reason: repeated scopes, arbitrary predicates and isolated variables remain allowed
Preamble
import Mathlib
import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Exposure
Formal statement
namespace BirthdayEntropy.Soundness.Supplement

/-- Theorem B.3, PDF pp24–25 / printed pp23–24. Companion theorem; not
used in the proof of the goal. No nonisolation, degree, gap or CNF assumption. -/
theorem theorem_B_3 (n m ℓ : ℕ) (φ : CSP n m) (γ : ℝ)
    (hγ0 : 0 < γ) (hγ1 : γ ≤ 1/3) (hn : 16 / γ ≤ (n : ℝ))
    (hℓ : 2 ≤ ℓ) (hℓn : ℓ^2 ≤ n) (hφ : DisjointViolationPromise φ γ)
    (H : Finset (Vertex n ℓ)) (hH : H.card = Nat.choose n ℓ) :
    density φ H ≤ 1 - γ^2 * (ℓ : ℝ)^3 / (13600 * (n : ℝ)^2) := 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 B.3, PDF p24-25 / printed p23-24

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