The Plünnecke–Ruzsa Inequality states that for a finite subset $A$ of an abelian group $G$ with small doubling $|A+A|\le K|A|$, the iterated sum and difference sets are also small:

$|tA-sA| \le K^{t+s} |A|$.

It seems natural to expect that the optimal exponent on $K$ should actually be $K^{t+s-1}$, since we're thinking of each additional sum or difference with $A$ as magnifying the set by a factor of at most $K$.

Also, the choice of $A$ as a basis for $\mathbb{F}_2^n$ leads me to think there could be improvements on the constant in Plünnecke–Ruzsa, so that I would conjecture (roughly)

$|tA - sA| \le \frac{K^{t+s-1}}{t!s!} |A|$.

Is this possible?

I don't see a way to get improvements of either kind directly from the Plünnecke/Ruzsa/Petridis graph approach (see Petridis).


No. See for instance Exercise 2.3.5 of

Tao, Terence; Vu, Van H., Additive combinatorics, Cambridge Studies in Advanced Mathematics 105. Cambridge: Cambridge University Press (ISBN 978-0-521-13656-3/pbk). xviii, 512 p. (2010). ZBL1179.11002.

See also a number of papers of Ruzsa constructing various counterexamples, e.g.

Ruzsa, I.Z., On the number of sums and differences, Acta Math. Hung. 59, No.3-4, 439-447 (1992). ZBL0773.11010.

| cite | improve this answer | |
  • $\begingroup$ From these I can find examples of $A$ where $|A-A|$ is much bigger than $|A+A|$, and also examples of $A,B$ where $|A+tB|$ is much bigger than $K^t |A|$. Are there examples where just the iterated sumset of a single set $|tA|$ is bigger than expected? $\endgroup$ – Xiaoyu He Oct 31 '17 at 2:47
  • $\begingroup$ Yes. See for instance Section 1, Theorem 9.5 of Ruzsa's "sumsets and structure" in citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Terry Tao Nov 1 '17 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.