Generalized More Sums Than Differences Sets
A More Sums Than Differences (MSTD, or sum-dominant) set is a finite set A⊂Z such that ∣A+A∣<∣A−A∣. Though it was believed that the percentage of subsets of {0,...,n} that are sum-dominant tends to zero, in 2006 Martin and O'Bryant \cite{MO} proved a positive percentage are sum-dominant. We generalize their result to the many different ways of taking sums and differences of a set. We prove that ∣ε1A+...+εkA∣>∣δ1A+...+δkA∣ a positive percent of the time for all nontrivial choices of εj,δj∈{−1,1}. Previous approaches proved the existence of infinitely many such sets given the existence of one; however, no method existed to construct such a set. We develop a new, explicit construction for one such set, and then extend to a positive percentage of sets. We extend these results further, finding sets that exhibit different behavior as more sums/differences are taken. For example, notation as above we prove that for any m, ∣ε1A+...+εkA∣−∣δ1A+...+δkA∣=m a positive percentage of the time. We find the limiting behavior of kA=A+...+A for an arbitrary set A as k→∞ and an upper bound of k for such behavior to settle down. Finally, we say A is k-generational sum-dominant if A, A+A, ...,kA are all sum-dominant. Numerical searches were unable to find even a 2-generational set (heuristics indicate the probability is at most 10−9, and almost surely significantly less). We prove the surprising result that for any k a positive percentage of sets are k-generational, and no set can be k-generational for all k.