Green-Ruzsa covering lemma

Question

I am trying to understand the proof of Green-Ruzsa covering lemma from Tao-Vu book but in my humble opinion the proof is written so unclearly that I was not able to comprehend some moments even after 10 times of reading.

1. Can anyone explain how does this algorithm work? What is the essence? He writes that $X+A-A$ is also the empty set but it cannot be an empty.
2. What does "the size of $|X+A|$ increases by at least $|A|/2$, by construction, and at the first stage it increases by $|A|." mean? What is the mathematical language of that sentence?

Actually I have much more questions but firstly I would like to understand these questions. Please help to understand!

Answer 1

Let's consider the example where $A = \{1,2,4,8\}$ and $B = \{1,2,3\}$.

Step 1. Initially, $X = \emptyset$. Then $X + A - A = \emptyset$ because $X + A - A$ is formally defined as $$\{x + a - a' : x \in X, a \in A, a' \in A\}.$$ Since there are no possible choices of $x \in X$, there are no possible elements of the form $x + a - a'$.

So inially, we may choose any element $y \in B$ to add to $X$. Let's add $1$.

Step 2. Now, $X = \{1\}$. With this $X$, $X + A - A$ is no longer empty; it is the set $$\{-6,-5,-3,-2,-1,0,1,2,3,4,5,7,8\}.$$ If we are keeping track of multiplicities, then $1$ appears $4$ times (because it is $1+1-1 = 1+2-2 = 1+4-4 = 1+8-8$) while all other elements appear only once (for example, $5$ only appears as $1+8-4$).

We are looking for $y \in B$ such that $|(y + A) \cap (X+A)| \le |A|/2$, or in other words $$\big| \{y+1, y+2, y+4, y+8\} \cap \{2,3,5,9\} \big| \le 2.$$ Taking $y=1$ does not work, because then $\{y+1,y+2,y+4,y+8\} = \{2,3,5,9\}$, intersecting $\{2,3,5,9\}$ in four elements. However, either $y=2$ or $y=3$ would work:

• If $y=2$, then $\{y+1,y+2,y+4,y+8\} = \{3,4,6,10\}$, intersecting $\{2,3,5,9\}$ in only one element.
• If $y=3$, then $\{y+1,y+2,y+4,y+8\} = \{4,5,7,11\}$, also intersecting $\{2,3,5,9\}$ in only one element.

Let's pick $y=3$.

Step 3. Now, $X = \{1,3\}$. With this $X$, we get $$ X+A-A = \{-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10\} $$ where many elements appear with multiplicity, but in particular $1$ appears with multiplicity $5$ ($1 = 1+1-1 = 1+2-2 = 1+4-4 = 1+8-8 = 3+2-4$), $2$ appears with multiplicity $2$ ($2 = 1+2-1 = 3+1-2$), and $3$ appears with multiplicity $5$ ($3 = 1+4-2 = 3+1-1 = 3+2-2 = 3+4-4 = 3+8-8$). We have found a set $X$ satisfying the conclusion of the theorem

---

When the proof says

the size of $|X+A|$ increases by at least $|A|/2$, by construction, and at the first stage it increases by $|A|$

it is referring to the size of $X+A$ at the beginning of each step. In this example:

1. At the beginning of step 1, $X = \emptyset$ so $X+A = \emptyset$ as well, and $|X+A| = 0$.
2. At the beginning of step 2, $X = \{1\}$, so $X+A = \{2,3,5,9\}$, and $|X+A| = 4$. From step 1 to step 2, this size has increased by $|A|=4$, as promised. This happens because at this point, $X$ is a singleton set, so $X+A$ is a translate of $A$, and $|X+A| = |A|$.
3. At the beginning of step 3, $X = \{1,3\}$, so $X+A = \{2,3,4,5,7,9,11\}$, and $|X+A| = 7$. From step 2 to step 3, this size has increased by $3$. The proof promised us that this increase would be at least $|A|/2 = 2$, and it is.

Why does the size increase by at least $|A|/2$ after every step? Because the new element $y$ we introduce satisfies $|(y + A) \cap (X+A)| \le |A|/2$. In the next step, the new value of $X+A$ will be $(X \cup \{y\}) + A$, which can be rewritten as $(X + A) \cup (y + A)$. Since $y+A$ has $|A|$ elements, and at most $|A|/2$ of them are already in $X+A$, at least $|A|/2$ are new.

---

The essence of the proof is that:

• When there is an element we can add to $X$ that increases $|X+A|$ by a lot, we do it.
• Once there is no longer any such element, we're done and have the set $X$ the lemma wanted.
• Because we increase $|X+A|$ by a lot at every step, but it can never exceed $|B+A|$, we must stop quickly. This means that when we're done, $|X|$ is still small.