Finite change of measure for overlap deviations
ProvedZeroFreeRRG.Hardcore.overlap_change_of_measureLet be nonnegative weights on a finite space, let be an overlap-deviation event, a revealed-deviation event, and a good density event. Suppose on , the -weight of is at most , the -weight of is at most , and the -weight of is at most . Then the -weight of is at most . This is the finite change-of-measure decomposition in the proof of the exponential overlap bound.
Preamble
import Mathlib set_option autoImplicit false open scoped Classical BigOperators
Formal statement
theorem ZeroFreeRRG.Hardcore.overlap_change_of_measure {Ω : Type} [Fintype Ω] (p q : Ω → ℝ) (D H Good : Ω → Prop)
(L A B C : ℝ) (hp : ∀ x, 0 ≤ p x) (hq : ∀ x, 0 ≤ q x) (hL : 0 ≤ L)
(hdens : ∀ x, H x → Good x → p x ≤ L * q x)
(hmiss : (∑ x, if D x ∧ ¬ H x then p x else 0) ≤ A)
(hreference : (∑ x, if H x then q x else 0) ≤ B)
(htail : (∑ x, if ¬ Good x then p x else 0) ≤ C) :
(∑ x, if D x then p x else 0) ≤ A + L * B + C := by sorrySource
Auxiliary decomposition for Chen–Wang–Zhang, Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/1461.pdf, pp. 39–40, proof of Lemma 5.6.