Constructions of Sequences of Alternating Sum and Difference Dominated Sets
Yorick Herrmann, Connor Hill, Merlin Phillips, Daniel Flores, Steven J. Miller, Steven Senger · 2025
Read Constructions of Sequences of Alternating Sum and Difference Dominated Sets by Yorick Herrmann, Connor Hill, Merlin Phillips, Daniel Flores, Steven J. Miller, Steven Senger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00792.txt.
Introduction
Yorick Herrmann leads six authors in total, with Connor Hill, Merlin Phillips, Daniel Flores, Steven J Miller, and Steven Senger, on sets where sums outnumber differences. A More Sums Than Differences set has a larger sumset than difference set, which is surprising because subtraction is not commutative and was expected to give more outcomes.
Martin and O'Bryant proved a small positive percentage of sets have this property. Herrmann and his co-authors ask what extra structure a chain of such sets can have, and construct sequences alternating between sum-dominated and difference-dominated sets, each properly containing the previous one. Their first constructions fill in all missing elements between minimum and maximum, while the last is more involved and prohibits adding any such elements.
Catalog record
| CREATOR | Yorick Herrmann, Connor Hill, Merlin Phillips, Daniel Flores, Steven J. Miller, Steven Senger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00792
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constructions of Sequences of Alternating Sum and Difference Dominated Sets Yorick Herrmann, Connor Hill, Merlin Phillips, Daniel Flores, Steven J. Miller, Steven Senger Abstract . A More Sums Than Difference (MSTD) set is a finite set of integers A A where the cardinality of its sumset, A + A A+A , is greater than the cardinality of its difference set, A − A A-A . Since addition is commutative while subtraction isn’t, it was conjectured that MSTD sets are rare. As Martin and O’Bryant proved a small (but positive) percentage are MSTD, it is natural to ask what additional properties can we impose on a chain of MSTD sets; in particular, can we construct a sequence of sets alternating between being MSTD and More Difference Than Sums (MDTS) where each properly contains the previous? We provide several such constructions; the first are trivial and proceed by filling in all missing elements from the minimum to maximum elements of A A , while the last is a more involved construction that prohibits adding any such elements. 1. Introduction For a finite set of integers A , we define the sumset A+A\coloneqq\{a+b:a,b\in A\} . Similarly, we define the difference set A-A\coloneqq\{a-b:a,b\in A\} . Let \big|A\big| refer to the cardinality of A . Intuitively, because a+b=b+a for all a,b\in\mathbb{Z} , but a-b\neq b-a unless a=b , we would expect \big|A-A\big| to be larger than \big|A+A\big| [ 4 , 7 ] . However, this is not always the case. We say A is a More Sums Than Differences (MSTD) set if \big|A+A\big|\ >\ \big|A-A\big| . Alternatively, A is a More Differences Than Sums (MDTS) set if \big|A-A\big|\ >\ \big|A+A\big| . These sets are also referred to as sum-dominated or difference-dominated sets. The study of MSTD sets originated with early examples discovered by Conway \big(\{0,2,3,4,7,11,12,14\}\big) , Marica \big(\{1,2,3,5,8,9,13,15,16\}\big) [ 3 ] , and Freiman-Pigarev 1 1 1 \{0,1,2,4,5,9,12,13,14,16,17,21,24,25,26,28,29\} [ 1 ] . Nathanson later formalized the problem, proved several properties of MSTD sets, provided several methods for constructing MSTD sets, and remarked that MSTD sets should be rare [ 7 ] . Surprisingly, Martin and O’Bryant [ 4 ] proved that as n\to\infty , a positive percentage of subsets of \{1,2,\dots,n\} are MSTD, and Hegarty proved that the set Conway found is the smallest possible MSTD set in terms of cardinality and diameter [ 2 ] . Additional research has focused on explicit constructions of generalized MSTD sets [ 5 , 6 , 8 ] and generalizations to groups [ 9 ] . Many problems in number theory involve sumsets and difference sets. At the recent 2025 CANT (Combinatorial and Additive Number Theory Conference), Samuel Allen Alexander posed the problem of finding an infinite sequence of sets with A_{i-1}\subset A_{i} that alternate being MSTD and MDTS. We address this problem by presenting several methods for constructing such sequences. Before introducing these methods, we must first establish several known properties of MSTD sets, and sets in general. First, for any set of integers A , we define the dilation x\cdot A\coloneqq\{xa:a\in A\} . For all integers x,y such that x\neq 0 , the set (1) \displaystyle B\ =\ x\cdot A+\{y\}\ =\ \{xa+y:a\in A\} satisfies \big|B+B\big|=\big|A+A\big| and \big|B-B\big|=\big|A-A\big| [ 7 ] . This property ensures that any method developed on a specific subset of the integers can be extended, via dilation and translation, to the full domain of integers. Furthermore, through dilation and translation, we have that any non-trivial k -term arithmetic progression can be obtained from the interval I\ =\ \{1,2,\ldots,k\}\ :=\ [1,k]. It is also evident that \displaystyle I+I\ \displaystyle=\ [2,2k]\ (2) \displaystyle I-I\ \displaystyle=\ [1-k,k-1], so such sets have the same number of sums and differences. For instance, if A=\{1,2,3\} , then \displaystyle A+A\ \displaystyle=\ \{2,3,4,5,6\} \displaystyle A-A\ \displaystyle=\ \{-2,-1,0,1,2\} (3) \displaystyle\big|A+A\big|\ \displaystyle=\ \big|A-A\big|\ =\ 5. For a set of integers A , if there exists an a^{*}\in\mathbb{Z} such that a^{*}-A=A , then we say that A is symmetric with respect to a^{*} , and we have that \big|A+A\big|=\big|A-A\big| [ 7 ] . If A is an arithmetic progression, we have that A is symmetric to a^{*}=\min(A)+\max(A) . For instance, the arithmetic progression A=\{1,3,5\} is symmetric with respect to 6 . Many methods that are used to construct MSTD sets make use of the symmetry property [ 7 ] . For example, the set A=\{0,2,3,7,11,12,14\} is symmetric with respect to 14 , so \big|A+A\big|=\big|A-A\big| . However, adding 4 to this set forms Conway’s set, which is MSTD. We also use this symmetry property in one method presented in the paper. Section 2 of the paper presents two methods that construct the desired alternating sequence through the use of ‘filling in’ missing elements. Theorem 2.4 provides a method to construct an MDTS superset from any MSTD set, which forms the foundation for Filling in Method 1. Theorem 2.8 then builds on known constructions of MSTD sets to generate sequences with controlled growth in Filling in Method 2. Section 3 presents another constraint, requiring that any element missing from an intermediate set remains missing in all subsequent sets. Theorem 3.2 provides a method based on choosing fringe elements to control the sum and difference sets. Lastly, Section 4 summarizes the growth rate of each method. The first constructions are trivial as we add missing elements from the minimal to maximal element in our set and then append whatever left and right fringe are needed. The final construction is more interesting and involved, as we force the constructions to be non-trivial by forbidding the inclusion of any of the missing elements. We further develop such methods in a companion paper. 2. Filling in Methods For a set A\subset[a,b] , ‘filling in’ the set A refers to the process of adding some (or potentially all) missing elements of [a,b]\setminus A to A . For instance, we could fill in the set A=\{1,3,5\} by adding either 2 , 4 , or both 2 and 4 to A . We provide two methods that construct the desired sequence through the use of filling in. In each method, we first fill in A_{i-1} and subsequently adjoin elements to create either a MSTD or MDTS set A_{i} . 2.1. Filling in Method 1 Before we begin, we recall the following results, taken from Nathanson [ 7 ] . Lemma 2.1 . Let m\geq 4 and 2\leq r\leq m-3 , with m,r\in\mathbb{N} . Let B=[0,m-1]\setminus\{r\} . Then B+B=[0,2m-2] , and B-B=[-(m-1),m-1] . Definition 2.2 . For integers d\geq 1 , a d -dimensional arithmetic progression is a set of the form L\ :=\ \{a+x_{1}m_{1}+\dots+x_{d}m_{d}:\ell_{i}\leq x_{i}\leq\ell_{i}+k_{i}-1\text{ for }i=1,\dots,d\}, where a is the base point, m_{1},\dots,m_{d} are the step sizes, \ell_{1},\dots,\ell_{d} are the starting indices, and k_{1},\dots,k_{d} are the lengths in each dimension. A 0-dimensional arithmetic progression is just a single point \{a\} . Theorem 2.3 . Let m\geq 4 , m\in\mathbb{N} and let B be a subset of [0,m-1] such that B+B\ =\ [0,2m-2], and B-B\ =\ [-m+1,m+1]. Let L^{*} be a (d-1) -dimensional arithmetic progression contained in [0,m-1]\setminus B such that \min(L^{*})-1\in B and m\notin L^{*}+L^{*} . Let k\geq 2 and let L be the d-dimensional arithmetic progression L\ =\ (m-L^{*})+m*[1,k]. Let a^{*}\ =\ \min(L)+\max(L)\ =\ (k+3)m-\min(L^{*})-\max(L^{*}), and A^{*}\ =\ B\cup L\cup(\{a^{*}\}-B). Then