I would like to discuss the Ruzsa's covering lemma from Tao-Vu book. The proof given in the book skips some details and I've decided to write all the details just to be sure that I understand everyhting in a correct way. Please read my proof and let me know is everything correct there.
Lemma 2.14 (Ruzsa's covering lemma) For any additive sets $A, B$ with common ambient group $Z$, there exists an additive set $X_+\subseteq B$ with $$B\subseteq A-A+X_+; \quad |X_+|\leq \dfrac{|A+B|}{|A|}; \quad |A+X_+|=|A||X_+|$$ and similarly there exists an additive set $X_-\subseteq B$ with $$B\subseteq A-A+X_-; \quad |X_-|\leq \dfrac{|A-B|}{|A|}; \quad |A-X_-|=|A||X_-|.$$ In particular, $B$ can be covered by $\min (\frac{|A+B|}{|A|}, \frac{|A-B|}{|A|})$ translates of $A-A$.
Proof:
I) We'll prove an existence of an additive set $X_+\subseteq B$ with desired properties. Consider the following set: $$\mathcal{C}:=\{X\subseteq B: X\neq \varnothing \ \text{and} \ (A+x)\cap (A+x')=\varnothing \ \forall x,x'\in X \ \text{such that} \ x\neq x'\}.$$ Since $B$ is an additive set, then $\mathcal{C}\neq \varnothing$ because $\{b\}\in \mathcal{C}$ for each $b\in B$.
We note that $\mathcal{C}$ is partially ordered set (by inclusion). Suppose that $T$ is a totally ordered subset of $\mathcal{C}$, then $T$ has an upper bound in $\mathcal{C}$.
Indeed, if $T=\{X_i\}_{i=1}^N,$ then consider an element $L:=\cup_{i=1}^N X_i$. It is obvious that $X_i\subseteq L$ for any $1\leq i\leq N$ (that means that $L$ is an upper bound for $T$) and also we'll prove $L\in \mathcal{C}$.
It is easy to see that $L\subseteq B$. Suppose that $t_1,t_2\in L$ such that $t_1\neq t_2$, then $t_1\in X_{i_1}$ and $t_2\in X_{i_2}$. Since $T$ is totally ordered, then WLOG assume that $X_{i_1}\subseteq X_{i_2}$. Hence $t_1,t_2\in X_{i_2}$ and since $X_{i_2}\in \mathcal{C}$, then $(A+t_1)\cap (A+t_2)=\varnothing$. It proves that $L\in \mathcal{C}$.
We were able to show that $\mathcal{C}$ is a partially ordered set and any chain in $\mathcal{C}$ has an upper bound in $\mathcal{C}$, then by Zorn's lemma $\mathcal{C}$ has a maximal element $X_+$. Since $X_+\neq \varnothing$ (because $X_+\in \mathcal{C}$ and elements of $\mathcal{C}$ are nonempty by construction), then $X+\subseteq B$ is an additive set.
i) we see that $A+X_+\subseteq A+B$, then $|A+X_+|\leq |A+B|.$ However, $A+X_+=\sqcup_{t\in X_+}(A+t)$ and the last union should be disjoint because $X_+\in \mathcal{C}$. Hence $$|A+X_+|=|\sqcup_{t\in X_+}(A+t)|=\sum \limits_{t\in X_+}|A+t|=\sum \limits_{t\in X_+}|A|=|A||X_+|\leq |A+B| \Rightarrow$$ $$|X_+|\leq \frac{|A+B|}{|A|} \ \text{and} \ |A+X_+|=|A||X_+|.$$
ii) If $X_+=B$, then obviously $B\subseteq A-A+X_+$.
Suppose that $X_+\subsetneq B.$ If $b\in X_+$, then obviously $b\in A-A+X_+.$ If $b\in B\setminus X_+,$ then $(A+b)\cap (A+x)\neq \varnothing$ for some $x\in X_+$. Hence $\exists \alpha\in A+b$ and $\alpha \in A+x$, i.e. $\alpha=a_1+b=a_2+x$ for some $a_1,a_2\in A$, then $b=a_2-a_1+x\in A-A+X_+$. Therefore, $$B\subseteq A-A+X_+.$$
Remark 1: The proof of an existence of $X_-$ follows if we apply part I) to the pair of additive sets $A$ and $-B$.
Remark 2: I am more than sure that there is a typo in the last line of statement of the lemma. It should be $B$ can be covered by $\leq\min (\frac{|A+B|}{|A|}, \frac{|A-B|}{|A|})$ translates of $A-A$.
Please let me know is my reasoning correct and what do you think about Remark 2?
I'm not sure what you mean by Remark 2. Your typo is that they omitted a $\leq$? It is true that $B$ could be covered by fewer translates of $A-A$, yes. Ruzsa's covering lemma doesn't provide the best possible covering, just an upper bound.
– Thomas Bloom Feb 14 '22 at 10:33