Hamming distance equals potential difference along a monotone Boolean pair
ProvedStabilityDichotomies.Approximability.monotone_hamming_heightconstraint-satisfactionprobability
If two Boolean assignments x and y on a finite variable set satisfy x ≤ y coordinatewise, then their Hamming distance equals the number of ones in y minus the number of ones in x. This identity relates the coupled output distance to the potential difference used in the sensitivity proof of Theorem 4.3.
Preamble
import Mathlib noncomputable section open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Approximability.monotone_hamming_height {V : Type} [Fintype V] (x y : V → Bool) (hxy : x ≤ y) :
(hammingDist x y : ℝ) =
(∑ v : V, if y v then (1 : ℝ) else 0) - ∑ v : V, if x v then (1 : ℝ) else 0 := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, proof of Theorem 4.3, pp. 16–17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf