Generalized more sums than differences sets

DOI10.1016/J.JNT.2011.10.006zbMATH Open1268.11014arXiv1108.4500OpenAlexW2092498095MaRDI QIDQ412123FDOQ412123

Authors: Geoffrey Iyer, Oleg Lazarev, Steven J. Miller, Liyang Zhang 

Publication date: 4 May 2012

Published in: Journal of Number Theory (Search for Journal in Brave)

Abstract: A More Sums Than Differences (MSTD, or sum-dominant) set is a finite set $AsubsetmathbbZ$ such that $|A+A|<|A-A|$. Though it was believed that the percentage of subsets of $0,\mathrm{...},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 $|epsilo{n}_{1}A+\mathrm{...}+epsilo{n}_{k}A|>|delt{a}_{1}A+\mathrm{...}+delt{a}_{k}A|$ a positive percent of the time for all nontrivial choices of $epsilo{n}_j,delt{a}_{j}in-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$, $|epsilo{n}_{1}A+\mathrm{...}+epsilo{n}_{k}A|-|delt{a}_{1}A+\mathrm{...}+delt{a}_{k}A|=m$ a positive percentage of the time. We find the limiting behavior of $kA=A+\mathrm{...}+A$ for an arbitrary set $A$ as $koinfty$ 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$.

Full work available at URL: https://arxiv.org/abs/1108.4500

Recommendations

• Many sets have more sums than differences
• Sets with more differences than sums
• Finding and Counting MSTD Sets
• On sets with more restricted sums than differences
• Constructions of generalized MSTD sets in higher dimensions

zbMATH Keywords

\(k\)-generational sum-dominant setsMSTD setssum-dominant sets

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13) Inverse problems of additive number theory, including sumsets (11P70)

Cites Work

• Title not available (Why is that?)
• On the number of sums and differences
• Additive completion and disjoint translations
• When almost all sets are difference dominated
• Sets with more sums than differences
• On A Conjecture of Conway
• Title not available (Why is that?)
• Explicit constructions of large families of generalized more sums than differences sets
• Finding and Counting MSTD Sets
• Some explicit constructions of sets with more sums than differences
• Problems in additive number theory. I
• Many sets have more sums than differences
• Sums of Finite Sets of Integers
• Sets characterized by missing sums and differences
• Constructing MSTD sets using bidirectional ballot sequences
• Explicit constructions of infinite families of MSTD sets

Cited In (15)

• On sets with more products than quotients
• A generalization of set-difference
• Generalizations of a curious family of MSTD sets hidden by interior blocks
• Infinite Families of Partitions into MSTD Subsets
• When sets can and cannot have sum-dominant subsets
• A tight structure theorem for sumsets
• Sums and differences of correlated random sets
• Distribution of Missing Sums in Sumsets
• Constructions of generalized MSTD sets in higher dimensions
• Generalizing the distribution of missing sums in sumsets
• Distribution of Missing Differences in Diffsets
• Sets with more differences than sums
• Sets of cardinality 6 are not sum-dominant
• The union of two arithmetic progressions with the same common difference is not sum-dominant
• Fringe pairs in generalized MSTD sets

This page was built for publication: Generalized more sums than differences sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412123)