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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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
    Commented Nov 1, 2017 at 23:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .