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
    Commented 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
    Commented 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
    Commented 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
    Commented Feb 7, 2013 at 15:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .