2

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?

RFZ
  • 16,814
  • 2
    The first part is needlessly complicated - since $B$ is a finite set, there's no need to invoke Zorn's lemma here. Any finite partially ordered set contains at least one maximal element.

    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
  • @ThomasBloom, Dear Professor Bloom! Oh yes, you are definitely right! For some reason I missed that $B$ is a finite set and we do not need to invoke Zorn's lemma here. In finite partially ordered set $X$ we can always find a maximal element (the proof is based on the induction on $|X|$). Let me explain my Remark 2 one more time. I basically mean that authors omitted a sign $\leq$ because the number of translates is an integer, but $\min {\frac{|A-B|}{|A|},\frac{|A+B|}{|A|}}$ might not be an integer. So I am sure that they forgot the sign $\leq$. Am I right here? – RFZ Feb 14 '22 at 15:22

0 Answers0