Harmonic gap dominates the fraction of removed candidates
ProvedStabilityDichotomies.Bijunctive.harmonic_gap_ge_removed_fractionFor natural numbers , the harmonic-number difference satisfies , with the usual zero-denominator convention when . This supports summing winner-change bounds over grouped removals.
Preamble
import Mathlib open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Bijunctive.harmonic_gap_ge_removed_fraction (m n : ℕ) (hmn : m ≤ n) :
((n - m : ℕ) : ℝ) / n ≤ (harmonic n : ℝ) - harmonic m := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, feasibility-root record analysis.