Lemma B.2 — Robust ternary clause exposure
OpenBirthdayEntropy.Soundness.Supplement.lemma_B_2graph-theoryinformation-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Fix a global assignment to an indexed Boolean ternary CSP, and a family of constraints violated by , with pairwise disjoint three-variable scopes. Let and . Orient each scope as arbitrarily. Sample independently and uniformly from all views with replacement. Set , , , and . For any and any bad-view set with , put . Then
If additionally , then
The bad-view events need not be independent of . This full exposure estimate supports Theorem B.3 and does not assume that theorem's threshold .
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: oriented violated disjoint triples and independent uniform views → indexed constraint set, arbitrary scope permutations, and normalized sums over all ordered view pairs; reason: constraint rows have distinct coordinates and every orientation is permitted; the bad set remains adversarial
Preamble
import Mathlib import Definitions.Def_BirthdayEntropy_Soundness_Supplement_Exposure
Formal statement
namespace BirthdayEntropy.Soundness.Supplement
/-- Lemma B.2, (30)–(32), PDF pp23–24 / printed pp22–23. No n≥16/gamma
threshold is imposed. Integer ell²≤n encodes the printed ell≤sqrt(n). -/
theorem lemma_B_2 (n m ℓ : ℕ) (φ : CSP n m) (g : Fin n → Bool)
(J : Finset (Fin m)) (o : Fin m → Equiv.Perm (Fin 3))
(γ f : ℝ) (hγ0 : 0 < γ) (hγ1 : γ ≤ 1/3)
(hℓ : 2 ≤ ℓ) (hℓn : ℓ^2 ≤ n)
(hJ : DisjointViolations φ g J) (ht : γ * n ≤ (J.card : ℝ))
(hf : 0 ≤ f) (B : Finset (View n ℓ)) (hB : (B.card : ℝ) ≤ f * Nat.choose n ℓ) :
let Λ := exposureLambda n ℓ J
let p₀ := exposureP0 n ℓ J
let X := exposureX (ℓ := ℓ) φ J o
let Y := exposureY φ J o B
viewPairMean X = p₀ ∧
viewPairMean (fun S T => (X S T)^2) ≤ p₀ + p₀^2 ∧
p₀ * (1 - f / γ - Real.sqrt (f * (1 + Λ) / Λ)) ≤ viewPairMean Y ∧
(f ≤ γ * Λ / 200 →
(3/8 : ℝ) * p₀ ≤ viewPairProb (fun S T => 0 < Y S T) ∧
3 * γ * (ℓ : ℝ)^3 / (16 * (n : ℝ)^2) ≤ (3/8 : ℝ) * p₀) := 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, Lemma B.2, PDF p23 / printed p22; proof continues PDF p24 / printed p23