Appending a clause changes the fixed-count mean by at most L
ProvedKSATSingleFlip.Connect.expected_count_step_boundFor any coupled sequence of clause marks, if an observable changes by at most L when a clause is inserted, and its values at each fixed prefix length are integrable, then consecutive expected observable values differ by at most L. This establishes the fixed-count mean sensitivity used in the Poisson-count argument of Lemma 2.6.
Preamble
import Mathlib set_option autoImplicit false open MeasureTheory
Formal statement
theorem KSATSingleFlip.Connect.expected_count_step_bound {Ω A : Type} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(X : ℕ → Ω → A) (F : List A → ℝ) (L : ℝ)
(hins : ∀ (xs : List A) (i : ℕ) (a : A), |F (xs.insertIdx i a) - F xs| ≤ L)
(hint : ∀ j, Integrable (fun ω => F (List.ofFn fun i : Fin j => X i.val ω)) μ)
(j : ℕ) :
|(∫ ω, F (List.ofFn fun i : Fin (j+1) => X i.val ω) ∂μ) -
(∫ ω, F (List.ofFn fun i : Fin j => X i.val ω) ∂μ)| ≤ L := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.6, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf