Insertion sensitivity bounds one-clause replacement
ProvedKSATSingleFlip.Connect.insertion_implies_replacementIf inserting one element at any position in a marked-clause list changes an observable by at most L, then changing any single coordinate of a fixed-length list changes it by at most 2L. This is the deletion-and-insertion step needed for the bounded-differences estimate in Lemma 2.6.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
theorem KSATSingleFlip.Connect.insertion_implies_replacement {A : Type} (j : ℕ) (F : List A → ℝ) (L : ℝ)
(hins : ∀ (xs : List A) (i : ℕ) (a : A), |F (xs.insertIdx i a) - F xs| ≤ L)
(x : Fin j → A) (i : Fin j) (a : A) :
|F (List.ofFn x) - F (List.ofFn (Function.update x i a))| ≤ 2*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