Many sets have more sums than differences
By Greg Martin, Kevin O'Bryant. 2006
65 citations recorded by the source corpus.
Since addition is commutative but subtraction is not, the sumset S+S of a finite set S is predisposed to be smaller than the difference set S-S. In this paper, however, we show that each of the three possibilities (|S+S|>|S-S|, |S+S|=|S-S|, |S+S|<|S-S|) occur for a positive proportion of the subsets of {0, 1, ..., n-1}. We also show that the difference |S+S| - |S-S| can take any integer value, and we show that the expected number of omitted differences is asymptotically 6 while the expected number of missing sums is asymptotically 10. Other data and conjectures on the distribution of these quantities are also given.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/5ab504d4414f656d61101d124015c5662551d54a
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- SETS WITH MORE SUMS THAN DIFFERENCES (2006, background): “This answers a question posed by Nathanson [3].”