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

Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like this hold for a "generic" $A$ (say, with high probability if $A$ is chosen at random)? What about $2A-A$ or similar sets? (as you can guess, interest in $2A-A$ comes from arithmetic progressions)

Of course only the case $|A| = \Omega(\sqrt{n})$ is nontrivial, and perhaps we have to assume also an upper bound on $|A|$ (e.g. $|A| \leq n^{\gamma}$ for some $\gamma <1$), since of course we could have $A = \{1, \dots, n\}$.

share|improve this question
    
If $A$ is chosen by adding each element with probability $n^{-1/2}$, then $A-A$ covers a positive proportion of $[n]$. –  Anthony Quas Feb 7 '13 at 7:08
    
How could you potentially have $|A-A|=o(n)$ if nothing prevents $A$ from being the whole set $[1,n]$, or a positive density subset thereof? –  Seva Feb 7 '13 at 10:11
    
@Seva: maybe you still can get something for |A| between n^alpha and n^gamma for some alpha, gamma < 1 (edited to clarify). –  Marcin Kotowski Feb 7 '13 at 15:24
    
@Anthony: do you have a reference? (although it shouldn't be too difficult to compute $\mathbb{E}|A-A|$ directly) –  Marcin Kotowski Feb 7 '13 at 15:28

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.