Disjoint violated families and oriented two-view exposure
DefinitionBirthdayEntropy_Soundness_Supplement_ExposureLet be an indexed Boolean exact-ternary CSP. A disjoint violated family for is a set of constraint indices such that violates each constraint and their three-variable scopes are pairwise disjoint. The promise is
Orient each selected scope as by an arbitrary permutation. For independent uniform views , define
Expectations and probabilities are finite sums over all ordered view pairs, divided by . The bad-view set is arbitrary. Also define the selected distinct-nonedge probability by counting ordered distinct nonadjacent pairs divided by ; 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.
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