2011/08/23 by Geoffrey Iyer, Iyer, Geoffrey, Oleg Lazarev +5
Computer Science · Economics, Econometrics and Finance · #11P99 (Primary) 11K99 (Secondary) #Advanced Graph Theory Research #Economic theories and models #FOS: Mathematics #Game Theory and Voting Systems #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.1108.4500
openalex publication_date 2011/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A More Sums Than Differences (MSTD, or sum-dominant) set is a finite set A⊂ ℤ such that |A+A||δ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.