Supercritical drift of the soft-field potential
OpenKSATSingleFlip.Connect.soft_field_supercritical_driftThere is an absolute ε₀ in (0,1/10) such that, for γ ≤ 1, 0 < ε ≤ ε₀, r ≥ 1, mᵣ ≤ 16 and mᵣ₊₁ ≥ 1+ε, the potential increment satisfies hᵣ₊₁−hᵣ ≥ ε²/7. This is the complete supercritical drift assertion of Lemma 4.6.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_SoftField import Mathlib set_option autoImplicit false open MeasureTheory KSATSingleFlip.Connect open scoped ENNReal
Formal statement
theorem KSATSingleFlip.Connect.soft_field_supercritical_drift :
∃ ε0 : ℝ, 0 < ε0 ∧ ε0 < 1/10 ∧ ∀ (γ ε : ℝ) (r : ℕ),
γ ≤ 1 → 0 < ε → ε ≤ ε0 → 1 ≤ r →
(massM (nuIter γ r)).toReal ≤ 16 →
1 + ε ≤ (massM (nuIter γ (r+1))).toReal →
ε^2/7 ≤ hPot (nuIter γ (r+1)) - hPot (nuIter γ r) := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 4.6, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf