Lemma 2.1 of "A SUM-PRODUCT ESTIMATE IN FINITE FIELDS, AND APPLICATION", by Bourgain, Katz and Tao

Question

I am trying to understand Lemma 2.1 of this paper: https://arxiv.org/pdf/math/0301343.pdf. Can anyone explain to me explicitly the reason why we can assume WLOG that $|A||B|\leqslant |F|/2$?

Many Thanks.

Answer 1

Their explanation is a little flawed. If $A,B$ are really large then you can't remove elements without decreasing the left hand side. However in this case the Lemma is trivial. I give a formal explanation below

Suppose we prove the claim for all $A,B$ such that $|A||B|\leq |F|/2$.

Now let $A,B$ be any sets, such that $|A||B|>|F|/2$, in this case we need to show that $|A+B\xi|>|F|/10$.

Choose $b_1,b_2,...,b_n\in B$ such that $n$ is minimal for which $B':=B\backslash \{b_1,b_2,...,b_n\}$ satisfies that $|A||B'|<|F|/2$ (In other words we start remove elements arbitrarily until we reach sets of sufficiently small size, but we don't take out too many elements, once $|A||B'|<|F|/2$ we stop). We clearly have such an $n$ because if we remove everything the size will be zero.

Now, applying the theorem for $A,B'$ we see that $|A+B\xi| > |A+B'\xi|>\min (\frac{1}{2}|A||B'|,|F|/10)$ therefore it is enough to show that $|F|/5<|A||B'|$.

Recall that $|A||B'| = |A||B|-n|A|$ and $n$ is minimal such that $|A||B'|<|F|/2$. Hence $|A||B'|>|F|/2-|A|$. Therefore if $|A|<|F|/2-|F|/5$ we have what we want.

Otherwise if $A$ is large $|A|>|F|/2-|F|/5$ then the claim that $|A+B\xi|>|F|/10$ is trivial (because $|A|>|F|/10$) so we don't even need to remove elements.