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.


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

  • $\begingroup$ Perfect, thank you! Do you know if anything's been done relaxing the condition to distinct summands? $\endgroup$ – Thomas Bloom Feb 13 '11 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 '11 at 15:57
  • $\begingroup$ The link is broken... Does anybody know if the file was in fact an article of Alon? $\endgroup$ – José Hdz. Stgo. Feb 10 '13 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 '13 at 19:59

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.