---
tag: 159KADZJKV
kind: statement
role: lemma
name: Ruzsa covering lemma
sources:
  - wikipedia: en:2240299@r1374516800
    locator: Freiman's theorem, section Tools used in the proof > Ruzsa covering lemma
    note: adopted
    mention: wikipedia://en/2240299#T4FS
    sections: [Statement]
inventory: [TTEYWQ4KK5]
---

## Statement

The Ruzsa covering lemma states the following:

Let $A$ and $S$ be finite subsets of an [[abelian group|071DDFVG4J]] with $S$ nonempty, and let $K$ be a positive real number. Then if $|A+S| \le K|S|$, there is a subset $T$ of $A$ with at most $K$ elements such that $A \subseteq T+S-S$.

This lemma provides a bound on how many copies of $S-S$ one needs to cover $A$, hence the name. The proof is essentially a greedy algorithm: