Sets characterized by missing sums and differences

By Yufei Zhao. 2009

46 citations recorded by the source corpus.

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We show that the probability that a uniform random subset of {0,1,…,n} is an MSTD set approaches some limit ρ>4.28×10−4. This improves the previous result of Martin and OʼBryant that there is a lower limit of at least 2×10−7. Monte Carlo experiments suggest that ρ≈4.5×10−4. We present a deterministic algorithm that can compute ρ up to arbitrary precision. We also describe the structure of a random MSTD set S⊆{0,1,…,n}. We formalize the intuition that fringe elements are most significant, while middle elements are nearly unrestricted. For instance, the probability that any “middle” element is in S approaches 1/2 as n→∞, confirming a conjecture of Miller, Orosz, and Scheinerman. In general, our results work for any specification on the number of missing sums and the number of missing differences of S, with MSTD sets being a special case.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/57d20b89564893a4fb499151843fdca0c1e1b131