Supermodularity of the finite log-product potential
ProvedZeroFreeRRG.Hardcore.log_product_set_supermodularLet be nonnegative for every element of a finite index set, and let . For a subset , form the vector taking on and elsewhere, and set . Then has nonnegative mixed differences when two distinct elements outside are inserted. This is the finite-coordinate supermodularity required in the hardcore comparison.
Preamble
import Mathlib open scoped BigOperators
Formal statement
namespace ZeroFreeRRG.Hardcore
theorem log_product_set_supermodular {ι : Type} [Fintype ι] [DecidableEq ι] (θ : ℝ) (hθ : 0 ≤ θ)
(x y : ι → ℝ) (hx : ∀ i, 0 ≤ x i) (hxy : ∀ i, x i ≤ y i)
(S : Finset ι) (i j : ι) (hi : i ∉ S) (hj : j ∉ S) (hij : i ≠ j) :
Real.log (1+θ*∏ a, (if a ∈ insert i (insert j S) then y a else x a)) +
Real.log (1+θ*∏ a, (if a ∈ S then y a else x a)) ≥
Real.log (1+θ*∏ a, (if a ∈ insert i S then y a else x a)) +
Real.log (1+θ*∏ a, (if a ∈ insert j S then y a else x a)) := 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.