Integrated influence bound for a bounded monotone Boolean potential
ProvedStabilityDichotomies.Approximability.integrated_monotone_bernoulli_influencesconstraint-satisfactionprobability
Let h be a monotone real-valued function of finitely many Boolean coordinates with 0 ≤ h ≤ B, and let 0 ≤ ε ≤ 1. At each p in [1−ε,1], let the coordinates be independent Bernoulli-p variables. The integral over [1−ε,1] of p times the sum of the expected forced-coordinate influences is at most B. This is the integrated influence estimate in the proof of Theorem 4.3; applying it to CSP outputs and relating it to a deletion coupling remain separate steps.
Preamble
import Mathlib noncomputable section open scoped Classical BigOperators Interval open MeasureTheory
Formal statement
theorem StabilityDichotomies.Approximability.integrated_monotone_bernoulli_influences {ι : Type} [Fintype ι]
(h : (ι → Bool) → ℝ) (B ε : ℝ) (hmono : Monotone h)
(hrange : ∀ x, 0 ≤ h x ∧ h x ≤ B) (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) :
(∫ p in (1-ε)..1, p * ∑ i : ι, ∑ x : ι → Bool,
(∏ j : ι, if x j then p else 1-p) *
(h (Function.update x i true) - h (Function.update x i false))) ≤ B := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, proof of Theorem 4.3, p. 17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf