= Ruzsa covering lemma
{c}
{wiki}
For finite <subsets> $S,T$ of an <abelian group>, with $T$ \b[nonempty], suppose $|S+T|\leq K|T|$. Then some $X\subseteq S$ satisfies
$$
S\subseteq X+T-T,\qquad |X|\leq K.
$$
Choose a maximal family of pairwise disjoint <translates> $x+T$ with $x\in S$. Their union has size $|X||T|$ inside $S+T$, proving the cardinality bound. Maximality means that every $s+T$ meets some $x+T$. An equation $s+t=x+t'$ gives $s\in x+T-T$, proving the covering. If $S$ is empty choose $X$ empty. An empty $T$ is excluded: it would make the assumed inequality vacuous while $X+T-T$ remained empty.
Back to article page
