The Ruzsa covering lemma
ProvedFamousTheorems.ruzsa_covering_lemmaThe Ruzsa covering lemma. Let be finite subsets of a group, not necessarily abelian but written additively, , with . Then there is with and
So a set with small sumset relative to is covered by few translates of . It is one of the basic tools of additive combinatorics, used in Freiman's theorem and in the passage between approximate groups and sets of small doubling.
Formalization note. Mathlib's Finset.ruzsa_covering_add (the additive form of Finset.ruzsa_covering_mul). The group is an arbitrary additive group, sumsets and difference sets are pointwise, and is real.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open scoped Pointwise
theorem ruzsa_covering_lemma {G : Type*} [AddGroup G] [DecidableEq G] {A B : Finset G} {K : ℝ} (hB : B.Nonempty)
(hK : ((A + B).card : ℝ) ≤ K * B.card) : ∃ F ⊆ A, (F.card : ℝ) ≤ K ∧ A ⊆ F + (B - B) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.ruzsa_covering_add`. Proof here reduces to that Mathlib result.