Constructing MSTD Sets Using Bidirectional Ballot Sequences
arXiv:0908.4442 · doi:10.1016/j.jnt.2009.11.005
Abstract
A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S| > |S-S|. We construct a new dense family of MSTD subsets of {0, 1, 2, ..., n-1}. Our construction gives Theta(2^n/n) MSTD sets, improving the previous best construction with Omega(2^n/n^4) MSTD sets by Miller, Orosz, and Scheinerman.
9 pages, 2 tables, 5 figures
References in corpus (4)
Cited by in corpus (19)
- Sets Characterized by Missing Sums and Differences
- Counting MSTD Sets in Finite Abelian Groups
- Entropies of weighted sums in cyclic groups and an application to polar codes
- Reduced decompositions and commutation classes
- When Sets Can and Cannot Have MSTD Subsets
- Generalizations of a Curious Family of MSTD Sets Hidden By Interior Blocks
- Analysis of Bidirectional Ballot Sequences and Random Walks Ending in their Maximum
- Distribution of missing differences in diffsets
- Sets of Cardinality 6 Are Not Sum-dominant
- Constructions of Generalized MSTD Sets in Higher Dimensions
- Fringe pairs in generalized MSTD sets
- Sums and differences of correlated random sets
- Generalized More Sums Than Differences Sets
- Generalizing the Distribution of Missing Sums in Sumsets
- Restricted-sum-dominant sets
- Pattern avoiding permutations and involutions with a unique longest increasing subsequence
- Union of Two Arithmetic Progressions with the Same Common Difference Is Not Sum-dominant
- Infinite Families of Partitions into MSTD Subsets
- The bidirectional ballot polytope