5
$\begingroup$

The theory of sumsets $A+B$ where $A$ and $B$ are finite subsets of an additive group $Z$ is extensively studied in additive combinatorics: finding long arithmetic progressions inside them, finding lots of subsets of this form, bounding its size above and below, and so on.

A fairly natural inverse question is the following.

Is there a function $f$ such that if $\lvert A\rvert\gg f(\lvert Z\rvert)$ then $A=B+C$ where $B$ and $C$ are both fairly large sets?

Since results such as Szemeredi's theorem and Ramsey theory suggest that sets can have lots of structure from cardinality conditions alone, and sumsets are very structured, this seems like a plausible hope.

The case for general finite additive groups may be too hard/trivially false, so I am (as usual in these questions) mostly interested in the cases $Z=\mathbb{Z}/N\mathbb{Z}$ and $Z=\mathbb{F}_p^n$.

I suspect that this sort of result is already known, or follows easily from another well known theorem, and would appreciate any reference and/or proof.

$\endgroup$

1 Answer 1

7
$\begingroup$

As far as I know, the only result of this sort is due to Alon, found here.

$\endgroup$
4
  • $\begingroup$ Perfect, thank you! Do you know if anything's been done relaxing the condition to distinct summands? $\endgroup$ Feb 13, 2011 at 12:58
  • $\begingroup$ @Thomas: I don't know of any further work on this besides Alon's paper and those cited therein. I suspected nobody else may have looked into it. $\endgroup$
    – Seva
    Feb 13, 2011 at 15:57
  • $\begingroup$ The link is broken... Does anybody know if the file was in fact an article of Alon? $\endgroup$ Feb 10, 2013 at 18:34
  • 1
    $\begingroup$ @J.H.S.: the link, I believe, is correct, but there seems to be some temporary problem with the Tel Aviv university server. Anyway, the paper is most certainly by Alon, entitled "Large sets in finite fields are sumsets" and published in the J. Number Theory 126 (1) (2007), pp. 110–118. $\endgroup$
    – Seva
    Feb 10, 2013 at 19:59

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.