Positive expected log-product gap for bounded ordered pairs
ProvedZeroFreeRRG.Hardcore.bounded_hardcore_expected_gapLet and . Suppose independent pairs satisfy almost surely, and both and have positive probability. Then the expected log-product supermodular gap between the all-upper, all-lower and single-coordinate-upper vectors is strictly positive. Boundedness supplies integrability. This is the strict expected gap in the hardcore Bethe monotonicity argument.
Preamble
import Mathlib open scoped Classical BigOperators open MeasureTheory Set
Formal statement
namespace ZeroFreeRRG.Hardcore
theorem bounded_hardcore_expected_gap (d : ℕ) (hd : 2 ≤ d) (θ C : ℝ) (hθ : 0 < θ) (hC : 0 ≤ C)
(π : Measure (ℝ × ℝ)) [IsProbabilityMeasure π]
(hbound : ∀ᵐ p ∂π, 0 ≤ p.1 ∧ p.1 ≤ p.2 ∧ p.2 ≤ C)
(hs : 0 < π {p | p.1 < p.2}) (hp : 0 < π {p | 0 < p.1}) :
let g := fun (xs : Fin d → ℝ × ℝ) (S : Finset (Fin d)) =>
Real.log (1+θ*∏ a, if a ∈ S then (xs a).2 else (xs a).1)
0 < ∫ xs, g xs Finset.univ - g xs ∅ - ∑ i, (g xs {i}-g xs ∅)
∂(Measure.pi fun _ : Fin d => π) := by sorry
end ZeroFreeRRG.HardcoreSource
Chen, Wang, and Zhang, Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1461.pdf, proof of Lemma 4.17, printed p. 30.