Chebyshev's sum inequality
ProvedFamousTheorems.chebyshev_sum_inequalityChebyshev's sum inequality. Let be real functions on a finite set that are similarly ordered on (monovarying). Then
Equivalently, the average of the products is at least the product of the averages. It is a discrete analogue of the positive correlation of increasing functions, and it follows from the rearrangement inequality by summing over cyclic shifts.
Formalization note. Mathlib's MonovaryOn.sum_mul_sum_le_card_mul_sum, the real-valued case of MonovaryOn.sum_smul_sum_le_card_smul_sum. MonovaryOn f g s means that for , implies .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem chebyshev_sum_inequality {ι : Type*} (s : Finset ι) {f g : ι → ℝ} (hfg : MonovaryOn f g s) :
(∑ i ∈ s, f i) * ∑ i ∈ s, g i ≤ (s.card : ℝ) * ∑ i ∈ s, f i * g i := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `MonovaryOn.sum_mul_sum_le_card_mul_sum`. Proof here reduces to that Mathlib result.