IMC 2012 · Day 2 · P10

Let $B$ be a nonempty subset of $A$ for which the value of the expression $c_1 = \frac{|A + B|}{|B|}$ is the least possible. Note that $c_1 \le c$ since $A$ is one of the possible choices of $B$.

Lemma 1. For any finite set $D \subset G$ we have $|A + B + D| \le c_1 |B + D|$.

Proof. Apply induction on the cardinality of $D$. For $|D| = 1$ the Lemma is true by the definition of $c_1$. Suppose it is true for some $D$ and let $x \notin D$. Let $B_1 = \{ y \in B \mid x + y \in B + D \}$. Then $B + (D \cup \{x\})$ decomposes into the union of two disjoint sets: $$B + (D \cup \{x\}) = (B + D) \cup \bigl( (B \setminus B_1) + \{x\} \bigr)$$ and therefore $|B + (D \cup \{x\})| = |B + D| + |B| - |B_1|$. Now we need to deal with the cardinality of the set $A + B + (D \cup \{x\})$. Writing $A + B + (D \cup \{x\}) = (A + B + D) \cup (A + B_1 + \{x\})$

we count some of the elements twice: for example if $y \in B_1$, then $A + \{y\} + \{x\} \subset (A + B + D) \cap (A + B + \{x\})$. Therefore all the elements of the set $A + B_1 + \{x\}$ are counted twice and thus $$\begin{align*} |A + B + (D \cup \{x\})| &\le |A + B + D| + |A + B + \{x\}| - |A + B_1 + \{x\}| = \\ &= |A + B + D| + |A + B| - |A + B_1| \le c_1 (|B + D| + |B| - |B_1|) = c_1 |B + (D \cup \{x\})|, \end{align*}$$ where the last inequality follows from the inductive hypothesis and the observation that $\frac{|A + B|}{|B|} = c_1 \le \frac{|A + B_1|}{|B_1|}$ (or $B_1$ is the empty set).

Lemma 2. For every $k \ge 1$ we have $|\underbrace{A + \dots + A}_{k\ \text{times}} + B| \le c_1^k |B|$.

Proof. Induction on $k$. For $k = 1$ the statement is true by definition of $c_1$. For greater $k$ set $D = \underbrace{A + \dots + A}_{k-1\ \text{times}}$ in the previous lemma: $|\underbrace{A + \dots + A}_{k\ \text{times}} + B| \le c_1 |\underbrace{A + \dots + A}_{k-1\ \text{times}} + B| \le c_1^k |B|$.

Now notice that $$|\underbrace{A + \dots + A}_{k\ \text{times}}| \le |\underbrace{A + \dots + A}_{k\ \text{times}} + B| \le c_1^k |B| \le c^k |A|.$$ Remark. The proof above due to Giorgios Petridis and can be found at http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/