The rearrangement inequality
ProvedFamousTheorems.rearrangement_inequalityThe rearrangement inequality. Let on a finite index set be similarly ordered (monovarying: ). Then for every permutation of ,
So a sum of products is largest when the two sequences are sorted in the same order. The inequality gives short proofs of AM–GM, Chebyshev's sum inequality and many olympiad inequalities.
Formalization note. Mathlib's Monovary.sum_mul_comp_perm_le_sum_mul, the real-valued, full-index-set case of MonovaryOn.sum_smul_comp_perm_le_sum_smul. Monovary f g means g i < g j → f i ≤ f j, which covers ties in either sequence.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem rearrangement_inequality {ι : Type*} [Fintype ι] {f g : ι → ℝ} (hfg : Monovary f g) (σ : Equiv.Perm ι) :
∑ i, f i * g (σ i) ≤ ∑ i, f i * g i := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Monovary.sum_mul_comp_perm_le_sum_mul`. Proof here reduces to that Mathlib result.