Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
Perfect, thank you! Do you know if anything's been done relaxing the condition to distinct summands? –  Thomas Bloom Feb 13 '11 at 12:58
    
@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. –  Seva Feb 13 '11 at 15:57
    
The link is broken... Does anybody know if the file was in fact an article of Alon? –  J. H. S. Feb 10 '13 at 18:34
1  
@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. –  Seva Feb 10 '13 at 19:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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