4
$\begingroup$

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\}$.

Improve this question
$\endgroup$
4
  • $\begingroup$ If $A$ is chosen by adding each element with probability $n^{-1/2}$, then $A-A$ covers a positive proportion of $[n]$. $\endgroup$
    – Anthony Quas
    Feb 7, 2013 at 7:08
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Feb 7, 2013 at 10:11
  • $\begingroup$ @Seva: maybe you still can get something for |A| between n^alpha and n^gamma for some alpha, gamma < 1 (edited to clarify). $\endgroup$
    – Marcin Kotowski
    Feb 7, 2013 at 15:24
  • $\begingroup$ @Anthony: do you have a reference? (although it shouldn't be too difficult to compute $\mathbb{E}|A-A|$ directly) $\endgroup$
    – Marcin Kotowski
    Feb 7, 2013 at 15:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.