Many Sets Have More Sums Than Differences

摘要

Nathanson opined [6]: "Even though there exist sets A that have more sums than differences, such sets should be rare, and it must be true with the right way of counting that the vast majority of sets satisfies |A — A| > |A +A|." The origin of this sentiment is that addition is commutative but subtraction is not — the set of sums S + S := {s_1 + s_2 : s_i ε S} of a finite set S is predisposed to be smaller than the set of differences S — S := {s_1 — s_2 : s_i ε S}. More precisely, the sizes of these two sets satisfy the bounds (1) 2ISI —1< |S +S| < 1/2 | S|~2 +1/2|S|, 2|S| —1< |S+ S|< |S|~2- |S| +1. Moreover, the sizes of S + S and S — S are correlated: both lower bounds are achieved exactly for arithmetic progressions, and if either upper bound is achieved then both are achieved (such sets are called Sidon sets). Following this reasoning, one would expect that a vanishingly small proportion of the 2~n subsets of {0, 1, 2, ...,n — 1} have more sums than differences. Our purpose, however, is to show that this