MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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


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

Browse other questions tagged or ask your own question.