Problem 2.4.8 rom Tao-Vu book

additive-combinatoricscombinatoricsdiscrete mathematics

For each $j=1,2,3,$ let $G_j$ be a $K_j$-approximate group in an
ambient group $Z$. Using the Ruzsa triangle inequality, show that
$$|G_1+G_2+G_3|\leq K_2\dfrac{|G_1+G_2||G_2+G_3|}{|G_2|}.$$ Conclude
that $$d(G_1+G_2, G_1+G_2+G_3)\leq d(G_2, G_2+G_3)+\log K_1K_2.$$
Similarly for permutations. Conclude from this and the preceding
exercise that $$d(G_1,G_2)\leq d(G_1+G_3, G_2+G_3)+2\log K_1K_2K_3.$$

This is a problem 2.4.8 from Tao-Vu book and I was able to prove the first two inequalities but cannot prove the last one.

The last inequality can be written equivalently as $$|G_1+G_2|^2|G_1+G_3||G_2+G_3|\leq(K_1K_2K_3)^4 |G_1+G_2+2G_3|^2|G_1||G_2|.$$

I have tried many ways to prove it but failed.
I'd be grateful for any help!

EDIT (Possible counterexample to the initial inequality): We claim that the inequality $$d(G_1,G_2)\leq d(G_1+G_3, G_2+G_3)+2\log K_1K_2K_3 \Leftrightarrow$$ $$|G_1+G_2|^2|G_1+G_3||G_2+G_3|\leq(K_1K_2K_3)^4 |G_1+G_2+2G_3|^2|G_1||G_2|$$ is wrong.

Let's take a look at the example which you've suggested. We consider the integer lattice $\mathbb{Z}
^2$
and let $G_1$ be an interval $[-N,N]$ on $x$-axis of $\mathbb{Z}^2$, $G_2$ be an interval $[-N,N]$ on $y$-axis of $\mathbb{Z}^2$ and $G_3=[-N,N]\times [-N,N]$ on $\mathbb{Z}^2$.

We see that each of them are approximate groups with $K_1=2$, $K_2=2$ and $K_3=4$.

Easy to see that $G_1+G_2\equiv G_3=[-N,N]\times [-N,N]$, $G_1+G_3=[-N,N]\times [-2N,2N]$, $G_2+G_3=[-2N,2N]\times [-N,N]$ and $G_1+G_2+2G_3=[-3N,3N]\times[-3N,3N]$. Our inequality becomes $$(2N+1)^6(4N+1)^2\leq 16^4(2N+1)(6N+1)^4$$ and this inequality is obviously wrong because the LHS $\sim N^8$ and the RHS is $\sim N^5$.

Best Answer

There's a typo in the exercise - what it should ask for is the inequality

$$d(G_1+G_3,G_2+G_3)\leq d(G_1,G_2)+2\log K_1K_2K_3.$$

This follows either from the given hint, or from the Ruzsa triangle inequality directly, as you say in the comments.

The inequality the exercise asks for is false, as can be seen e.g. taking $G_1=\{0\}\times P$, $G_2=P\times \{0\}$, and $G_3=P\times P$, where $P=\{-N,\ldots,N\}$ for large $N$.

(The general point is that the inequality as written in the exercise is the opposite of the heuristic that addition of sets generally -increases- the amount of additive structure present.)

Related Question