The Ruzsa triangle inequality
ProvedFamousTheorems.ruzsa_triangle_inequalityThe Ruzsa triangle inequality. For finite subsets of a group (written additively),
Setting (the Ruzsa distance), it says , whence the name. It is a basic inequality in additive combinatorics, used with the Plünnecke–Ruzsa inequality to control iterated sumsets.
Formalization note. Mathlib's Finset.ruzsa_triangle_inequality_sub_sub_sub, stated for an arbitrary (not necessarily commutative) additive group with pointwise difference sets.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open scoped Pointwise
theorem ruzsa_triangle_inequality {G : Type*} [AddGroup G] [DecidableEq G] (A B C : Finset G) :
(A - C).card * B.card ≤ (A - B).card * (C - B).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.ruzsa_triangle_inequality_sub_sub_sub`. Proof here reduces to that Mathlib result.