Weighted sum comparison under a bounded-fiber map
ProvedZeroFreeRRG.Hardcore.bounded_fiber_weighted_sumSuppose a map from a finite set T into H has at most B preimages per point, and the weight at each point of T is at most C times the weight at its image. If the weights on H and C are nonnegative, the sum over T is at most BC times the sum over H.
Preamble
import Mathlib set_option autoImplicit false open scoped Classical BigOperators
Formal statement
theorem ZeroFreeRRG.Hardcore.bounded_fiber_weighted_sum {X : Type*} [DecidableEq X]
(T H : Finset X) (F : X → X) (w : X → ℝ) (B : ℕ) (C : ℝ)
(hC : 0 ≤ C) (hw : ∀ y ∈ H, 0 ≤ w y)
(hmap : ∀ x ∈ T, F x ∈ H)
(hfiber : ∀ y ∈ H, (T.filter (fun x => F x = y)).card ≤ B)
(hbound : ∀ x ∈ T, w x ≤ C * w (F x)) :
(∑ x ∈ T, w x) ≤ (B : ℝ) * C * ∑ y ∈ H, w y := by sorrySource
Chunyang Wang et al., Zero-freeness for random regular graphs up to the replica symmetry breaking threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/1461.pdf, Appendix E.3, proof of Lemma 4.20, Step 1 (supporting argument).