TOPICS
Search

MSTD Set


An MSTD set, short for "more sums than differences set," is a finite set A of integers satisfying |A+A|>|A-A|, where A+A={a+b:a,b in A} and A-A={a-b:a,b in A}. It is also called sum-dominant (Martin and O'Bryant 2007). For example, A={0,2,3,4,7,11,12,14} has 26 distinct sums and 25 distinct differences. A positive proportion of all subsets of {0,...,N-1} are MSTD (Martin and O'Bryant 2007); this is a counting statement distinct from an explicit construction of a large indexed family.

For every fixed positive integer T, Khan (2026) constructs a family of MSTD subsets of {0,...,N-1} of size

 Theta_T((2^N)/((log_2^( degreesT)N)^(2^T))),

where log_2^( degreesT) denotes the T-fold iterated logarithm, and the constants and sufficiently large threshold for N may depend on T. A subfamily of the same order can be indexed so that a chosen member is generated deterministically in O_T(N^5) bit operations, without listing earlier members. A separate variant, using exhaustive search over short fringe pairs, attains Theta(2^N) members with the same O(N^5) per-member generation bound. This does not assert that the entire exponentially large family can be listed in polynomial time. Khan (2026) reports that ChatGPT suggested varying the fringe sets and assisted with the indexed-generation algorithm.


See also

Integer, Set, Sumset

Explore with Wolfram|Alpha

References

Khan, T. "An Explicit Construction of Large Families of MSTD Sets." 17 Nov 2026. https://arxiv.org/abs/2611.23338v1.Martin, G. and O'Bryant, K. "Many Sets Have More Sums than Differences." In Additive Combinatorics (Ed. A. Granville, M. B. Nathanson, and J. Solymosi). Providence, RI: Amer. Math. Soc., pp. 287-305, 2007. https://doi.org/10.1090/crmp/043/16.

Cite this as:

Weisstein, Eric W. "MSTD Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MSTDSet.html

Subject classifications