Grouped removal fractions sum to at most a harmonic number
ProvedStabilityDichotomies.Bijunctive.grouped_removal_fraction_sum_le_harmonicIf the nonnegative integers count surviving candidates after successive grouped removals, then , using the zero-denominator convention.
Preamble
import Mathlib open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Bijunctive.grouped_removal_fraction_sum_le_harmonic (k : ℕ) (m : ℕ → ℕ)
(hmono : ∀ i < k, m (i+1) ≤ m i) :
(∑ i ∈ Finset.range k, ((m i - m (i+1) : ℕ) : ℝ) / m i) ≤ (harmonic (m 0) : ℝ) := 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.