14
$\begingroup$

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).

$\endgroup$

1 Answer 1

19
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2017 at 2:47
  • 1
    $\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, 2017 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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