Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Disjoint violated families and oriented two-view exposure

Definition
BirthdayEntropy_Soundness_Supplement_Exposure

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 an indexed Boolean exact-ternary CSP. A disjoint violated family for ggg is a set JJJ of constraint indices such that ggg violates each constraint and their three-variable scopes are pairwise disjoint. The promise is

∀g  ∃J:∣J∣≥γnand J is a disjoint violated family for g.\forall g\;\exists J:\quad |J|\ge\gamma n\quad\text{and }J\text{ is a disjoint violated family for }g.∀g∃J:∣J∣≥γnand J is a disjoint violated family for g.

Orient each selected scope as (aj,bj,cj)(a_j,b_j,c_j)(aj​,bj​,cj​) by an arbitrary permutation. For independent uniform views S,TS,TS,T, define

α=ℓ(ℓ−1)n(n−1),Λ=∣J∣α,p0=ℓnΛ,X=∑j∈J1{cj∈S, aj,bj∈T},Y=X1{S,T∉B}.\alpha=\frac{\ell(\ell-1)}{n(n-1)},\quad\Lambda=|J|\alpha,\quad p_0=\frac\ell n\Lambda,\quad X=\sum_{j\in J}\mathbf1\{c_j\in S,\ a_j,b_j\in T\},\quad Y=X\mathbf1\{S,T\notin B\}.α=n(n−1)ℓ(ℓ−1)​,Λ=∣J∣α,p0​=nℓ​Λ,X=j∈J∑​1{cj​∈S, aj​,bj​∈T},Y=X1{S,T∈/B}.

Expectations and probabilities are finite sums over all ordered view pairs, divided by (nℓ)2\binom n\ell^2(ℓn​)2. The bad-view set BBB is arbitrary. Also define the selected distinct-nonedge probability by counting ordered distinct nonadjacent pairs divided by ∣H∣2|H|^2∣H∣2; the diagonal contributes zero. These computed quantities support the additive soundness branch without changing the published graph or imposing a degree or nonisolation condition. Their theorem domains ensure positive denominators; outside those domains the raw normalized sums use Lean's total division convention.

Definition code
import Mathlib
import Definitions.Def_BirthdayEntropy_Soundness_Graph

noncomputable section
open scoped Classical

namespace BirthdayEntropy.Soundness.Supplement

/-- Appendix B.1, PDF p22 / printed p21. The indexed violated family may depend on g. -/
def DisjointViolations {n m : ℕ} (φ : CSP n m) (g : Fin n → Bool)
    (J : Finset (Fin m)) : Prop :=
  (∀ j ∈ J, φ.f j (g ∘ φ.H.M j) = false) ∧
    ∀ j ∈ J, ∀ k ∈ J, j ≠ k → Disjoint (φ.H.verts j) (φ.H.verts k)

def DisjointViolationPromise {n m : ℕ} (φ : CSP n m) (γ : ℝ) : Prop :=
  ∀ g : Fin n → Bool, ∃ J : Finset (Fin m),
    DisjointViolations φ g J ∧ γ * n ≤ (J.card : ℝ)

/-- Every ordering of a scope is admitted, independently for each indexed constraint. -/
def oriented {n m : ℕ} (φ : CSP n m) (o : Fin m → Equiv.Perm (Fin 3))
    (j : Fin m) (r : Fin 3) : Fin n := φ.H.M j (o j r)

/-- Equation (28), PDF p22 / printed p21; real subtraction in both factors. -/
def alpha (n ℓ : ℕ) : ℝ :=
  ((ℓ : ℝ) * ((ℓ : ℝ) - 1)) / ((n : ℝ) * ((n : ℝ) - 1))

def exposureLambda {m : ℕ} (n ℓ : ℕ) (J : Finset (Fin m)) : ℝ :=
  J.card * alpha n ℓ

def exposureP0 {m : ℕ} (n ℓ : ℕ) (J : Finset (Fin m)) : ℝ :=
  ratio n ℓ * exposureLambda n ℓ J

def exposureX {n m ℓ : ℕ} (φ : CSP n m) (J : Finset (Fin m))
    (o : Fin m → Equiv.Perm (Fin 3)) (S T : View n ℓ) : ℝ :=
  (J.filter (fun j => oriented φ o j 2 ∈ S.val ∧
    oriented φ o j 0 ∈ T.val ∧ oriented φ o j 1 ∈ T.val)).card

/-- Equation (29): an adversarial bad-view set, without an independence assumption. -/
def exposureY {n m ℓ : ℕ} (φ : CSP n m) (J : Finset (Fin m))
    (o : Fin m → Equiv.Perm (Fin 3)) (B : Finset (View n ℓ))
    (S T : View n ℓ) : ℝ :=
  if S ∉ B ∧ T ∉ B then exposureX φ J o S T else 0

/-- Independent uniform draws from ALL views; used only where 2≤ell and ell²≤n. -/
def viewPairMean {n ℓ : ℕ} (F : View n ℓ → View n ℓ → ℝ) : ℝ :=
  (∑ S : View n ℓ, ∑ T : View n ℓ, F S T) / (Nat.choose n ℓ : ℝ)^2

def viewPairProb {n ℓ : ℕ} (P : View n ℓ → View n ℓ → Prop) : ℝ :=
  viewPairMean (fun S T => if P S T then 1 else 0)

/-- Distinct ordered nonedges only; the diagonal contributes zero. -/
def qbad {n m ℓ : ℕ} (φ : CSP n m) (H : Finset (Vertex n ℓ)) : ℝ :=
  ((H ×ˢ H).filter (fun vw => vw.1 ≠ vw.2 ∧ ¬ (graph φ).Adj vw.1 vw.2)).card /
    (H.card : ℝ)^2

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, Appendix B.1–B.3, PDF pp22–25 / printed pp21–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