On the number of sums and differences

Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Additive bases, including sumsets (11B13) Probabilistic theory: distribution modulo (1); metric theory of algorithms (11K99)

Review text

Let \(A\subseteq\mathbb{Z}\). All sums of \(A+A=\{a+b:a,b\in A,a\geq b\}\) are different if and only if the same is true for all differences \(\neq 0\) of \(A-A=\{a-b:a,b\in A\}\). But there are sets \(A\) such that almost all sums are represented multiply while almost all differences are different, and conversely. Using probability methods it is shown that for every \(n>n_ 0\) there are sets \(A,B\subseteq\mathbb{Z}\), \(| A|=| B|=n\) such that \(| A+A|\leq n^{2-c}\) but \(| A-A|\geq n^ 2-n^{2- c}\) and \(| B-B|\leq n^{2-c}\) but \(| B+B|\geq{1\over 2}n^ 2-n^{2-c}\), where \(c>0\) does not depend on \(n\).

Recommendations

Cited in

(49)

This page was built for publication: On the number of sums and differences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1206296)