When Sets Are Not Sum-Dominant

Hùng Vi{ê \atop .}t Chu

Department of Mathematics Washington and Lee University Lexington, VA 24450 USA

                  chuh19@mail.wlu.edu

Abstract

Given a set A of nonnegative integers, define the sum set

A + A = {a_{i} + a_{j} | a_{i}, a_{j} ∈ A}

and the difference set

A − A = {a_{i} − a_{j} | a_{i}, a_{j} ∈ A}.

The set A is said to be sum-dominant if |A + A| > |A − A|. In answering a question by Nathanson, Hegarty used a clever algorithm to find that the smallest cardinality of a sum-dominant set is 8. Since then, Nathanson has been asking for a humanunderstandable proof of the result. We offer a computer-free proof that a set of cardinality less than 6 is not sum-dominant. Furthermore, we prove that the introduction of at most two numbers into a set of numbers in an arithmetic progression does not give a sum-dominant set. This theorem eases several of our proofs and may shed light on future work exploring why a set of cardinality 6 is not sum-dominant. Finally, we prove that if a set contains a certain number of integers from a specific sequence, then adding a few arbitrary numbers into the set does not give a sum-dominant set.

1 Introduction

1.1 Literature review

Given a set A ⊆ ℕ, define the sum set A + A = {a_{i} + a_{j} | a_{i}, a_{j} ∈ A} and the difference set A − A = {a_{i} − a_{j} | a_{i}, a_{j} ∈ A}. The set A is said to be • sum-dominant, if |A + A| > |A − A|;

• balanced, if |A + A| = |A − A|; and

• difference-dominant, if |A + A| < |A − A|.

As addition is commutative and subtraction is not, it was natural to conjecture that sumdominant sets are rare. Since Nathanson’s review of the subject in 2006 [16], research on sum-dominant sets has made considerable progress: see [5, 8, 16, 19, 20, 21] for history and overview, [6, 11, 12, 17, 22] for explicit constructions , [3, 9, 24] for positive lower bound for the percentage of sum-dominant sets, [7, 14] for generalized sum-dominant sets, and [1, 2, 4, 13, 23] for extensions to other settings.

However, much less work has been done on how to determine whether or not a given set is sum-dominant. Only recently, Mathur and Wong [10] gave an algorithm for checking if a set is sum-dominant. The algorithm computes and compares all pairs of possible sums and differences among numbers of the set. This paper instead focuses on certain types of not-sum-dominant sets that we can tell without the assistance of computers.

Nathanson [16] asked What is the smallest cardinality of a sum-dominant set?. Hegarty [6] used a clever algorithm to find A_{1} = {0, 2, 3, 4, 7, 11, 12, 14} as the smallest sum-dominant set. Furthermore, A_{1} is the unique sum-dominant set of cardinality 8, up to affine transformations. However, a human-understandable proof of the result has not been produced because of the complexity lurking behind the interaction of numbers in addition and subtraction. Nathanson [15, 18] asked for a human-understandable proof of the smallest cardinality of a sum-dominant set. This paper proves that a set of cardinality less than 6 is not sumdominant without the use of computers.

1.2 Notation

We introduce some notation.

• Let n, a, b ∈ ℕ. Define I_{n} = {0, 1, …, n−1} and [a, b] = {a, a+1, …, a+ℓ | ℓ ∈ ℕ, ℓ ≤ b − a}. So, we can write I_{n} = [0, n − 1]. Define the center of I_{n} to be (n − 1)/2, the point that is equidistant from the two endpoints.

• For (a_{i})_{i=1}^{ℓ} and a set A, we write (a_{i})_{i=1}^{ℓ} → A to mean the introduction of ℓ numbers (a_{i})_{i=1}^{ℓ} into the set A to form A ∪ {a_{i} | 1 ≤ i ≤ ℓ}.

• Given a set A and a number x, we write x ± A to mean the set {x ± a_{i} | a_{i} ∈ A}.

1.3 Main results

The following is our first result.

Theorem 1. A set A with |A| < 6 is not sum-dominant.

Though our proof is concise, we are unable to prove the cases of cardinality 6 and 7 since the level of complexity grows quite quickly. Our main technique is to argue for a lower bound for the number of equal pairs of positive differences from A − A, which confines set A to certain structures.

Our next result is about the relationship between sum-dominant sets and arithmetic progressions. Since numbers from an arithmetic progression form a balanced set, it is convenient to introduce new numbers into the set (in a clever way) and produce a sum-dominant set. Indeed, the construction of sum-dominant sets using arithmetic progressions was started by Nathanson [17] and Hegarty [6]. However, little is known about the smallest number of integers needed to turn an arithmetic progression into a sum-dominant set. We prove that the introduction of at most two numbers into a set of numbers in an arithmetic progression does not give a sum-dominant set.

Theorem 2. Let A be a set of numbers in an arithmetic progression and m_{1}, m_{2} ∈ ℕ. Then A ∪ {m_{1}, m_{2}} is not sum-dominant.

A natural question to ask is what is the minimum number of integers to add to a set formed by numbers in an arithmetic progression and have a sum-dominant set?. Let the number be k. Note that A_{1} = {3, 7, 11} ∪ {0, 2, 4, 12, 14}. Because 3, 7, 11 is an arithmetic progression, we know that 3 ≤ k ≤ 5. Though Theorem 2 is easily stated, the proof requires a clever division into cases to reduce the complexity of interactions between numbers in addition and subtraction. As a necessary condition for a set to be sum-dominant, Theorem 2 provides a powerful tool to eliminate cases in arguing about the smallest cardinality of sum-dominant sets. For example, for a set of cardinality 6, if we know that at least 4 numbers in the set form an arithmetic progression, then the set is not sum-dominant.

Our final result is another test for being sum-dominant and extends [4, Theorem 1].

Theorem 3. Let S be a subset of A, where A = {a_{k}}_{k=1}^{∞} is a strictly increasing sequence of non-negative numbers. If there exists a positive integer r such that

1. a_{k} > a_{k−1} + a_{k−r} for all k ≥ r + 1, and

2. set A does not contain any sum-dominant set S with |S| ≤ 2r + n for some n ∈ ℕ, and

3. |S| = 2r + n + ℓ for some ℓ ∈ ℕ,

Then

1. S is not sum-dominant and |S − S| − |S + S| ≥ ℓ(n + 1),

2. Let m ∈ ℕ and (b_{i})_{i=1}^{m} be integers. If m|S| + \frac{m(m+1)}{2} ≤ ℓ(n + 1), then S^{∗} = S ∪ {b_{1}, …, b_{m}} is not sum-dominant.

Example 4. For the Fibonacci numbers {0, 1, 2, 3, 5, 8, 13, …}, we have r = 3. By [4, Corollary 2], the Fibonacci numbers have no sum-dominant subsets, so we can pick any number n. Let n = 2 and ℓ = 5, for example. Since m = 1 satisfies 13m + \frac{m(m+1)}{2} ≤ 15, we know that a set of 13 Fibonacci numbers and an arbitrary integer is not sum-dominant.

Example 5. Let ρ > ϕ = \frac{1+\sqrt{5}}{2}, the golden ratio. The geometric sequence 1, ρ, ρ^{2}, ρ^{3}, … has the property that ρ^{k} > ρ^{k−1} + ρ^{k−2}. By [4, Corollary 8], this sequence has r = 2 and has no sum-dominant subsets, so we can pick any number n. Let n = 2 and ℓ = 4, for example. Since m = 1 satisfies 10m + \frac{m(m+1)}{2} ≤ 12, we know that a set of 10 numbers from the sequence and an arbitrary integer is not sum-dominant.

Section 2 proves several important results for the proof of our main theorems. Section 3, Section 4, and Section 5 prove Theorem 1, Theorem 2, and Theorem 3, respectively. Section 6 discusses some questions for future research.

2 Important results

We use the definition of a symmetric set in the sense of Nathanson [17]: a set A is symmetric with respect to a number a if A = a − A. It is easy to check that any arithmetic progression is symmetric. (The sum of the two endpoints of an arithmetic progression is the point of symmetry.) The following lemma is proved by Nathanson [17].

Lemma 6. A symmetric set is balanced.

Proposition 7. Let n ∈ ℕ and x = (n − 1) + k, where 1 ≤ k ≤ n − 1. Then x → I_{n} gives k new positive differences and k + 1 new sums.

Proof. We have (I_{n} ∪ {x}) + (I_{n} ∪ {x}) = (I_{n} + I_{n}) ∪ (x + I_{n}) ∪ {2x}. Clearly, all new sums are in

(x + I_{n}) ∪ {2x} = [(n − 1) + k, (n − 1) + (k + n − 1)] ∪ {2x}.

Let k = (n − 1) − j, where j ≥ 0. Then |((x + I_{n}) ∪ {2x}) ∩ (I_{n} + I_{n})| = j + 1. Hence, the number of new sums is |(x + I_{n}) ∪ {2x}| − (j + 1) = n + 1 − (j + 1) = n − j = k + 1.

All new positive differences are in x−I_{n} = {x−(n−1), x−(n−2), …, x} = [k, k +n−1]. Note that positive differences in I_{n} − I_{n} are [1, n − 1]. Because [k, k + n − 1]\[1, n − 1] = [n, k + n − 1]. The number of new positive differences is |[n, k + n − 1]| = k.

Lemma 8. Let x ∈ ℝ. Then {x} ∪ I_{n} is not a sum-dominant set.

Proof. If x ∈ I_{n}, we are done because I_{n} is an arithmetic progression, which is a symmetric set and thus, balanced

For n = 1, our set has at most 2 elements, which is symmetric and thus, not sum-dominant by Lemma 6.

We assume n ≥ 2. Note the number of new sums is at most (n + 1). We consider the following three cases.

Case I: 0 < x < n − 1. Arrange numbers in {x} ∪ I_{n} in increasing order. Either to the left of x or to the right of x, there are at least ⌈n/2⌉ numbers. Without loss of generality, assume that x is greater than ⌈n/2⌉ numbers in I_{n}; that is, 0 < 1 < ⋯ < ⌈n/2⌉ − 1 < x. The set of new differences has

D = {x − (⌈n/2⌉ − 1), x − (⌈n/2⌉ − 2), …, x − 0}

as a subset.

1. Subcase I.1: x − 1/2 ∈ ℤ. Because 0 < x < n − 1, x + x ∈ I_{n} + I_{n}, implying that there are at most n new sums. Since the number of new differences is at least 2|D| = 2⌈n/2⌉ ≥ n, I_{n} ∪ {x} is not sum-dominant.

2. Subcase I.2: x−1/2 ∉ ℤ. Then the set of new differences has D∪{n−1−x} as a subset. Since the number of new differences is at least 2|D∪{n−1−x}| = 2(⌈n/2⌉+1) ≥ n+2, I_{n} ∪ {x} is not sum-dominant.

Case II: n − 1 < x. We consider two subcases.

1. Subcase II.1: x ∉ ℕ. The set of new differences include x−(n−1), x−(n−2), …, x−0. Therefore, the number of new differences is at least 2n > n + 1, implying that I ∪ {x} is not sum-dominant.

2. Subcase II.2: x ∈ ℕ. If x = n, then I_{n} ∪ {x} have numbers from an arithmetic progression and so, is not sum-dominant. Let x = (n − 1) + k for some k ∈ ℕ_{≥2}. We have x − I_{n} = {k, k + 1, …, k + (n − 1)}. Because max(I_{n} − I_{n}) = n − 1, if k > n − 1, there are n new positive differences and so, I ∪ {x} is not sum-dominant. If k ≤ n − 1 by Proposition 7, there are k new positive differences and k +1 new sums, which shows that I ∪ {x} is not sum-dominant.

Case III: x < 0. Due to symmetry, this case is similar to Case II. This completes our proof.

Corollary 9. A set of numbers in an arithmetic progression in union with a singleton set cannot be sum-dominant.

Proof. Let a ∈ ℕ and m, d ∈ ℕ. Our set is A = {a, a + d, …, a + (n − 1)d, m}, where n ∈ ℕ. The set A is sum-dominant if and only if \frac{1}{d}(A − a) = \{0, 1, …, (n − 1)\} ∪ \{(m − a)/d\} is sum-dominant. Note that (m − a)/d may not be a nonnegative integer. This completes the proof.

Remark 10. Let n ≥ 2, x − 1/2 ∉ ℤ and x ∉ {−1, n}. The difference set of I_{n} ∪ {x} has at least one more number than the sum set. This remark is evident from the proof of Lemma 8. Remark 11. A set of numbers in an arithmetic progression is an example of a symmetric set. Though the result of Corollary 9 holds for any set of numbers in an arithmetic progression, it is not true for symmetric sets in general. For example, the set A_{1}\{4} is symmetric, and A_{1} is sum-dominant.

The following proposition offers upper bounds for the cardinality of the sum set and the difference set of a set A in terms of |A|. The two inequalities are not hard to prove and are used by Hegarty [6].

Proposition 12. We have the following bounds

|A + A| ≤ \frac{|A|(|A| + 1)}{2},  (1)
|A − A| ≤ |A|(|A| − 1) + 1.  (2)

The equality in (1) is achieved if the sum of any two numbers is distinct, and the equality in (2) is achieved if the difference between any two different numbers is distinct.

The next observation plays a key role in reducing the complexity of our proof that a set of too small a cardinality cannot be sum-dominant.

Observation 13. Let A ⊆ ℕ and consider A ± A. Let a_{i} < a_{j} ≤ a_{m} < a_{n} ∈ A such that a_{j} − a_{i} = a_{n} − a_{m}. If a_{j} ≠ a_{m}, we have another pair of equal positive differences a_{m} − a_{i} = a_{n} − a_{j}. If a_{j} = a_{m}, then we do not have another pair. In both cases, we have a_{j} + a_{m} = a_{i} + a_{n}, a pair of equal sums. Hence, for k pairs of equal positive differences, there exist at least k/2 pairs of equal sums.

3 Proof of Theorem 1

For clarity, we split the proof into two parts.

3.1 A set A with |A| ≤ 4 is not sum-dominant.

Proof. We proceed by case analysis of |A|.

If |A| = 1, then |A + A| = |A − A| = 1 and so, A is not sum-dominant.

If |A| = 2, suppose that A = {a_{1}, a_{2}}. Then A is symmetric with respect to a_{1} + a_{2}. By Lemma 6, A is not sum-dominant.

If |A| = 3, then A is the union of an arithmetic progression with a singleton set. By Corollary 9, A is not sum-dominant.

If |A| = 4, by Proposition 12, |A + A| ≤ 10, while |A − A| ≤ 13. Let k be the number of pairs of equal positive differences that A − A has. Then, in order that A is sum-dominant,

13 − 2k < 10 − \frac{k}{2}.

The k/2 comes from Observation 13. We have k ≥ 3. Therefore, |A − A| ≤ 13 − 3 · 2 = 7. Denote A = {a_{1}, a_{2}, a_{3}, a_{4}} with a_{1} < a_{2} < a_{3} < a_{4} and d_{i} = a_{i+1} − a_{i}. We write out all nonnegative differences in A − A

0 d_{1} d_{1} + d_{2} d_{1} + d_{2} + d_{3}
d_{2} d_{2} + d_{3}
d_{3}.

All differences in row 1 are pairwise distinct. These nonnegative differences give 7 differences in total. Because |A − A| ≤ 7, we are not allowed to have any new differences from row 2 and row 3. Clearly, d_{2} = d_{1}, which implies that a_{1}, a_{2}, a_{3} is an arithmetic progression. By Corollary 9, A is not sum-dominant.

3.2 A set A with |A| = 5 is not sum-dominant.

Proof. By Proposition 12, we know that |A + A| ≤ 15, while |A − A| ≤ 21. Let k be the number of pairs of equal positive differences. Due to Observation 13, we have 21 − 2k < 15 − \frac{k}{2}. So, k ≥ 5 and |A − A| ≤ 11. Denote A = \{a_{1}, a_{2}, …, a_{5}\} with a_{1} < a_{2} < ⋯ < a_{5} and d_{i} = a_{i+1} − a_{i}. The following lists all nonnegative differences in A − A

0 d_{1} d_{1} + d_{2} d_{1} + d_{2} + d_{3} d_{1} + d_{2} + d_{3} + d_{4}
d_{2} d_{2} + d_{3} d_{2} + d_{3} + d_{4}
d_{3} d_{3} + d_{4}
d_{4}.

Differences in row 1 are pairwise distinct and account for 9 differences in A − A. Because |A − A| ≤ 11, we are allowed to have at most one more difference from rows 2, 3, and 4.

Case I: d_{2} ≠ d_{1}. Then

A − A = {0, d_{1}, d_{2}, d_{1} + d_{2}, d_{1} + d_{2} + d_{3}, d_{1} + d_{2} + d_{3} + d_{4}}.

1. Subcase I.1: d_{2} + d_{3} = d_{1}. Because d_{1} > d_{3} and d_{3} ∈ A − A, d_{3} = d_{2}. Since d_{2} + d_{3} + d_{4} ∈ A − A, either d_{2} + d_{3} + d_{4} = d_{1} + d_{2} or d_{2} + d_{3} + d_{4} = d_{1} + d_{2} + d_{3}. Combine the former with d_{2} + d_{3} = d_{1} to have d_{2} = d_{4}. We have d_{2} = d_{3} = d_{4}, which, by Corollary 9, makes A not sum-dominant. The latter gives d_{1} = d_{4}, which, combined with d_{2} = d_{3}, makes A symmetric and thus, not sum-dominant.

2. Subcase I.2: d_{2} + d_{3} = d_{1} + d_{2}, implying d_{1} = d_{3}. Because d_{2} + d_{3} + d_{4} ∈ A − A, it must be that d_{2} + d_{3} + d_{4} = d_{1} + d_{2} + d_{3} and so, d_{1} = d_{4}. Similarly, because d_{3} + d_{4} ∈ A − A and d_{1} = d_{3} = d_{4} ≠ d_{2}, we must have d_{3} + d_{4} = d_{2}. Due to the fact that sum-dominant is preserved under affine transformations, we let a_{1} = 0 and d_{2} = 2 to have A = {0, 1, 3, 4, 5}. This set is not sum-dominant.

Case II: d_{2} = d_{1}. If d_{2} + d_{3} = d_{1} + d_{2}, then d_{1} = d_{3}. Since d_{1} = d_{2} = d_{3}, A is not sum-dominant due to Corollary 9. Therefore, d_{2} + d_{3} ≠ d_{1} + d_{2} or, equivalently, d_{1} ≠ d_{3} and

A − A = {0, d_{1}, d_{1} + d_{2}, d_{2} + d_{3}, d_{1} + d_{2} + d_{3}, d_{1} + d_{2} + d_{3} + d_{4}}.

Because d_{3} ∈ A−A and d_{3} ≠ d_{1}, we know d_{3} = d_{1}+d_{2}. Since d_{2}+d_{3}+d_{4} ∈ A−A and d_{3} > d_{1}, it must be that d_{2} + d_{3} + d_{4} = d_{1} + d_{2} + d_{3}. Hence, d_{1} = d_{4} and so, d_{1} = d_{2} = d_{4} = d_{3}/2. Due to the fact that sum-dominant is preserved under affine transformations, we let a_{1} = 0 and d_{3} = 2 to have A = {0, 1, 2, 4, 5}. This set is not sum-dominant.

We have shown that a set of cardinality 5 is not sum-dominant.

4 Proof of Theorem 2

Lemma 14. Let n ∈ ℕ and two numbers x, y ∈ ℝ such that x ± y are not integers. Then I_{n} ∪ {x, y} is not sum-dominant.

Proof. If n = 1, we know that I_{n} ∪ {x, y} is not sum-dominant because its cardinality is 3. So, we assume that n ≥ 2 and y > x. The condition x ± y ∉ ℤ guarantees that (y ± I_{n}) ∩ (x ± I_{n}) = ∅. For the proof, we let our original set be I_{n} ∪ {x} and we introduce y to the set; that is, y → I_{n} ∪ {x}. By Lemma 8, I_{n} ∪ {x} is not sum-dominant. Note that the introduction of y gives at most n + 2 new sums. We consider three cases.

Case I: 0 < y < n − 1. Similar to Case I in the proof of Lemma 8, the introduction of y into I_{n} ∪ {x} gives at least ⌈n/2⌉ new positive differences. These differences result from the interaction of y and I_{n}.

1. Subcase I.1: y − 1/2 ∉ ℤ. Similar to Subcase I.2 in the proof of Lemma 8, either (n − 1) − y or y − 0 is another new positive difference. Hence, the number of new differences is at least 2·(⌈n/2⌉+1) ≥ n+2. Therefore, I_{n}∪{x, y} is not sum-dominant.

2. Subcase I.2: y − 1/2 ∈ ℤ. Due to our condition that y ± x ∉ ℤ, causing x − 1/2 ∉ ℤ and Remark 11, the difference set of I ∪ {x} has one more number than the sum set. Also, since 2y ∈ (I_{n} + I_{n}), the number of new sums is at most n + 1. Because the number of new differences is at least 2⌈n/2⌉ ≥ n, I ∪ {x, y} is not sum-dominant.

Case II: n − 1 < y. We have two subcases.

1. Subcase II.1: y ∉ ℕ. The set of new differences includes y−(n−1), y−(n−2), …, y−0. Therefore, the number of new differences is at least 2n > n+2, implying that I ∪{x, y} is not sum-dominant.

2. Subcase II.2: y ∈ ℕ. Let y = (n − 1) + k for some k ∈ ℕ_{≥2}. The set of differences related to y is y − (I_{n} ∪ {x}) ⊇ {k, k + 1, …, k + (n − 1)}. If k > n − 1, there are n new positive differences and so, I ∪ {x, y} is not sum-dominant. If k ≤ n − 1, there are at least k new positive differences and at most k + 2 new sums by Proposition 7.

Case III: y < 0. Due to symmetry, this case is the same as Case II. We complete the proof.

Lemma 15. Let n ∈ ℕ and two numbers x, y ∈ ℝ such that x ± y are integers. Then I_{n} ∪ {x, y} is not sum-dominant.

Proof. The proof is divided into four parts, each of which deals with a specific position of x and y when being introduced to I_{n}.

Part I. n − 1 < x < y

We know that {x, y} → I_{n} gives at most 2n + 3 new sums. Case I: x, y ∉ ℕ. Then x, y → I_{n} gives the following n + 1 new differences D = {x − (n − 1), x − (n − 2), …, x − 0} ∪ {y}. Therefore, in order that I_{n} ∪ {x, y} is sum-dominant, x, y → I_{n} must give exactly 2n + 3 new sums.

1. Subcase I.1: y−x ∈ ℕ. To have 2n+3 new sums, [y+0, y+(n−1)] and [x+0, x+(n−1)] must be disjoint, implying that y − (n − 1) > x. So, y − (n − 1) is a new difference that is not in D. Hence, we have n + 2 new positive differences and so, I ∪ {x, y} is not sum-dominant.

2. Subcase I.2: y + x ∈ ℕ.

• If x − 1/2 ∉ ℤ, then y − 1 is a new positive difference not in D and we have n + 2 new positive differences.

• If x − 1/2 ∈ ℤ, then note that if y > x + 1, we have y − 1 is a new difference not in D. So, y ≤ x + 1. Because x − 1/2 ∈ ℤ and x + y ∈ ℕ, y = x + 1. Hence, we have a pair of equal sums and so, the number of new sums is at most 2n + 2. Therefore, I ∪ {x, y} is not sum-dominant.

Case II: x, y ∈ ℕ. Write x = (n − 1) + k for some k ≥ 2 and y = x + j for some j ≥ 1. Note x − I_{n} = {k, k + 1, …, k + (n − 1)}. If k > n − 1, then all numbers in x − I_{n} are new differences. Because y > x = k + (n − 1), y is another new difference. So, the number of new differences is at least 2(n+1) = 2n+2. Therefore, in order that I_{n} ∪{x, y} is sum-dominant, x, y → I_{n} must give exactly 2n + 3 new sums. Similar to Subcase I.1 above, we can show that I ∪ {x, y} is not sum-dominant. Hence, k ≤ n − 1.

If j > n − 1, then y − (I_{n} ∪ {x}) is the set of n + 1 new positive differences. In order that I ∪ {x, y} is sum-dominant, x, y → I_{n} must gives exactly 2n + 3 new sums. This is a contradiction because k ≤ n − 1, causing x + 0 ∈ [0, 2n − 2]. Hence, j ≤ n − 1.

We have shown that j, k ≤ n − 1. Suppose that k = j = n − 1. It can be easily checked that I_{n} ∪ {2n − 2, 3n − 3} is not sum-dominant. So, either k ≤ n − 2 or j ≤ n − 2.

• If k ≤ n−2, we know that x+0 = (n−1)+k ≤ 2n−3 and x+1 = (n−1)+k+1 ≤ 2n−2. Also, because j ≤ n − 1, x + 0 ≤ y + 0 ≤ x + (n − 1). So, the number of new sums is at most 2n.

• If j ≤ n − 2, then x ≤ y + 0 ≤ y + 1 ≤ (x + j) + 1 ≤ x + (n − 1). Also, because k ≤ n − 1, x + 0 ≤ (n − 1) + k ≤ 2n − 2. The number of new sums is also at most 2n.

We have shown that the number of new sums is at most 2n. Suppose that k + j > n − 1. Because y = (n − 1) + (k + j), y → I_{n} gives n new positive differences. This implies that I_{n} ∪ {x, y} is not sum-dominant. So, k + j ≤ n − 1. We consider the sum set of I_{n} ∪ {x, y}. Note that min(x + I_{n}) < min(y + I_{n}) = (n − 1) + (k + j) ≤ 2n − 2, so the set of new sums is a subset of ((y + I_{n})\(I_{n} + I_{n})) ∪ {x + y, 2x, 2y}, which is at most k + j + 3 due to Proposition 7. Indeed, Proposition 7 states that since y = (n − 1) + k + j and k + j ≤ n − 1, y → I_{n} gives k + 1 new sums (including 2y). Also by Proposition 7, y → I_{n} gives k + j new positive differences. Since 2(k + j) ≥ k + j + 3, I_{n} ∪ {x, y} is not sum-dominant.

Part II. 0 < x < n − 1 < y

Case I: If x − 1/2 ∉ ℤ, there are n new positive differences from the interaction between x and I_{n}. Since y −0 > n−1, y is another new positive difference. If x+y ∈ ℕ, y −1 is another positive difference. Hence, we do not have a sum-dominant set because we have at most 2n+3 new sums. Therefore, in order that I_{n} ∪ {x, y} is sum-dominant, y − x ∈ ℕ and x, y → I_{n} must give exactly 2n + 3 new sums, which implies that (x + [0, n − 1]) ∩ (y + [0, n − 1]) = ∅. So, y > (n − 1) + x. This inequality leads to the following two cases.

• If x > 1, then y > n and there is another new difference y − 1 > n − 1.

• If 0 < x < 1, then n − 1 < y < n. Hence, n − 1 < x + y < n + 1 and n − 2 < y − x < n. Because y − x ∈ ℕ, y − x = n − 1 or y + 0 = x + (n − 1). Since we have a pair of equal sums, the number of new sums is less than 2n + 3.

Case II: If x − 1/2 ∈ ℤ, the following are n new positive differences y − (n − 1), y − (n − 2), …, y − 0 from x, y → I_{n}. Hence, the number of new differences is at least 2n. Because 2x ∈ ℕ and 0 < 2x < 2n − 2, the number of new sums is at most 2n + 2. In order that I ∪ {x, y} is sum-dominant, there must not be a new positive difference other than the n differences above. So, the positive difference (n−1)−x must be equal to y −(n−i) for some 1 ≤ i ≤ n and so, x + y = 2n − 1 − i. Similarly, the positive difference x − 0 must be equal to y − (n − j) for some 1 ≤ j ≤ n and so, x = y − (n − j) or equivalently, x + (n − j) = y + 0. Hence, we have at least two pairs of equal sums. Therefore, the number of new sums is at most 2n. This shows that I ∪ {x, y} is not sum-dominant.

Part III. 0 < x < y < n − 1

Let k be the number such that k < x < k + 1. Case I: x + \frac{1}{2} ∉ ℤ.

1. Subcase I.1: y − x ∈ ℕ. New positive differences include

x − k < x − (k − 1) < ⋯ < x − 0 < y − 0
(k + 1) − x < (k + 2) − x < ⋯ < (n − 1) − x.

Because x + \frac{1}{2} ∉ ℤ, numbers in the two rows are pairwise distinct. We have these n + 1 new positive differences. Since 0 < y − x ∈ ℕ, there exists 0 < i < n − 1 such that y − x = i. So, y + 0 = x + i, implying that we have at most 2n + 2 new sums. Therefore, I ∪ {x, y} is not sum-dominant.

2. Subcase I.2: y + x ∈ ℕ. Because 0 < x + y < 2n − 2, we have at most 2n + 2 new sums.

• If x, y lie on the same side of the center of I_{n}, we assume that 0 < (n − 1)/2 < x < y < n − 1. The following are new differences

x − k < ⋯ < x − 1 < x − 0  (3)
(k + 1) − x < ⋯ < (n − 2) − x < (n − 1) − x < y − 0.  (4)

Because x + \frac{1}{2} ∉ ℤ, the numbers in these two rows are pairwise distinct. These are n + 1 new positive differences. Hence, I ∪ {x, y} is not sum-dominant.

• If x, y lies on two sides of the center of I_{n}, we assume that x is closer to the center than y. (If they are equidistant from the center, we have a balanced set with the same center of I_{n}). The numbers in Row 3 and Row 4 are still new positive differences. Hence, I_{n} ∪ {x, y} is not sum-dominant.

Case II: x + \frac{1}{2} ∈ ℤ. We write y = x + j for some 1 ≤ j < n − 1 − x.

1. Subcase II.1: x, y lie on one side of the center of I_{n}. Assume that 0 < \frac{n−1}{2} ≤ x < x + j < n − 1. We have

x + [0, n − 1] = [x, x + n − 1],
y + [0, n − 1] = [y, y + (n − 1)] = [x + j, x + j + (n − 1)].

Because 0 < 2x, 2y, x + y < 2n − 2, they are not new sums and so, all new sums are [x, x + n − 1] ∪ [x + j, x + j + (n − 1)], which contains n + j numbers. The following are new positive differences

x − k < x − (k − 1) < ⋯ < x − 0 < (x + j) − (j − 1) < ⋯ < (x + j) − 0.

So, there are at least 2(j + k + 1) new differences. Note that

2(j + k + 1) = 2j + 2(k + 1) > 2j + 2x ≥ 2j + 2 · \frac{n − 1}{2} = 2j + n − 1 ≥ n + j.

Hence, I_{n} ∪ {x, y} is not sum-dominant.

2. Subcase II.2: x, y lie on two side of the center of I_{n}. As above, the number of new sums is still n+j. Without loss of generality, assume that (x+j)−(n−1)/2 < (n−1)/2−x; that is, x + j is closer to the center. We have

(x + j) − [0, k + j] = {x − k, x − k + 1, …, x + j},
[x + (x + j) + 1, n − 1] − x = {x + j + 1, …, n − 1 − x}.

Because

x − k < x − k + 1 < ⋯ < x + k < x + j + 1 < ⋯ < n − 1 − x,

all these n−2x+k numbers are distinct positive differences and we have 2(n−2x+k) = 2(n − k − 1) new differences. Since 2(n − k − 1) > n + j (x + j is closer to the center), I ∪ {x, y} is not sum-dominant.

Part IV. x < 0 < n − 1 < y

If y − (n − 1) = 0 − x, we have a symmetric set, which is not sum-dominant. Without loss of generality, assume that y − (n − 1) > 0 − x. Note {x, y} → I_{n} gives at most 2n + 3 new sums. If we can show that the number of new differences is at least n + 2, then the new set is not sum-dominant. Case I: x, y ∉ ℕ. New positive differences include

0 − x < y − (n − 1) < y − (n − 2) < ⋯ < y − 0 < y − x.

Case II: x, y ∈ ℕ. Let x = −j and y = (n − 1) + k. Because y − (n − 1) > 0 − x, k > j.

1. Subcase II.1: k > n − 1 and j > n − 1. We have y − [0, n − 1] = [k, k + (n − 1)] and y − x = (n − 1) + k + j. Because

(n − 1) < j < k < k + 1 < ⋯ < k + (n − 1) < (n − 1) + k + j,

there are at least n + 2 new positive differences {j, (n − 1) + k + j} ∪ [k, k + (n − 1)]. Hence, I ∪ {x, y} is not sum-dominant.

2. Subcase II.2: k > n − 1 and j ≤ n − 1. Then 0 ≤ −j + (n − 1) = x + (n − 1) ≤ (n − 1). So, x + (n − 1) is not a new sum and so, we have at most 2n + 2 new sums. As above, there are at least n + 1 new positive differences {(n − 1) + k + j} ∪ [k, k + (n − 1)]. Hence, I ∪ {x, y} is not sum-dominant.

3. Subcase II.3: j < k ≤ n − 1. We will find all new sums from x + [0, n − 1] and y + [0, n − 1]. We have

x + [0, n − 1] = [−j, n − 1 − j] = [−j, −1] ∪ [0, n − 1 − j],
y + [0, n − 1] = [n − 1 + k, 2n − 2 + k] = [n − 1 + k, 2n − 2] ∪ [2n − 1, 2n − 2 + k].

New sums are from [−j, −1] ∪ [2n − 1, 2n − 2 + k] ∪ {2x, 2y}. (We do not count x + y because 0 ≤ x + y = (n − 1) + k − j ≤ 2n − 2.) So, there are at most j + k + 2 new sums. We find a lower bound for the number of new differences by looking at

y − [0, n − 1] = [y − (n − 1), y] = [k, (n − 1) + k] = [k, (n − 1)] ∪ [n, n + (k − 1)].

The k numbers in [n, n + (k − 1)] are new positive differences. Another new difference is y − x. So, the number of new differences is bounded below by 2(k + 1) = 2k + 2. This is bigger than j + k + 2. Hence, I ∪ {x, y} is not sum-dominant.

As these four parts consider all possible cases, we have completed the proof.

Due to the fact that being sum-dominant is preserved under affine transformation, Theorem 2 follows immediately from Lemma 14 and Lemma 15.

Remark 16. We can use Theorem 2 to simplify the proof of Theorem 1.

• For |A| = 4, we write A = {a_{1}, a_{2}, a_{3}, a_{4}}. Because a_{1}, a_{2} is an arithmetic progression, adding a_{3}, a_{4} to the set of {a_{1}, a_{2}} does not give a sum-dominant set.

• For |A| = 5, if A contains an arithmetic progression of length 3, then we are done. We look at Section 3.2 and easily eliminate Subcase I.1 and Case II, thus shortening the proof.

The trade off is that the proof of Theorem 2 is much more computationally involved.

5 Proof of Theorem 3

Proof. We first prove item 1. Let S′ = {s_{1}, s_{2}, …, s_{k−1}}, where s_{1} < s_{2} < ⋯ < s_{k−1} be a finite subset of A. We show that S = {s_{1}, s_{2}, …, s_{k−1}, s_{k}} with s_{k} > s_{k−1} is not a sum-dominant set by induction. If k ≤ 2r + n, then S is not sum-dominant by the second assumption of the theorem. If k ≥ 2r + n + 1, consider the number of new sums and differences obtained by adding s_{k}. The number of new sums is at most k. We prove that the number of new differences is at least k + n + 1.

Since k ≥ 2r + n + 1, we have k − ⌊\frac{k+n+2}{2}⌋ ≥ r. Let t = ⌊\frac{k+n+2}{2}⌋. Then, t ≤ k − r, which implies s_{t} ≤ s_{k−r}. The largest difference between elements in S′ is s_{k−1} − s_{1}; we now show that we have added at least t distinct differences greater than s_{k−1} − s_{1}. Denote s_{i} = a_{g(i)}, where g : ℤ^{+} → ℤ^{+} is an increasing function. We have

s_{k} − s_{t} ≥ s_{k} − s_{k−r} = a_{g(k)} − a_{g(k−r)}
≥ a_{g(k)} − a_{g(k)−r}
> a_{g(k)−1} − a_{1}
≥ s_{k−1} − a_{1} ≥ s_{k−1} − s_{1}.

The third inequality is due to the first assumption on {a_{n}}. Since s_{k} − s_{t} > s_{k−1} − s_{1}, we know that

s_{k} − s_{t}, …, s_{k} − s_{2}, s_{k} − s_{1}

are t differences greater than the greatest difference in S′. As we could subtract in the opposite order, the number of new differences obtained from adding s_{k} to S′ is at least

2t = 2⌊\frac{k + n + 2}{2}⌋ ≥ k + n + 1.

We have seen that by adding s_{k} to the set S′, the number of differences goes by at least n+1 more than the number of sums. Note that S′ must have at least 2r + n elements.

Next, we prove item 2. To form S^{∗}, we first add b_{1} to the set, which gives at most |S| + 1 new sums. When we add b_{2} to S^{∗} ∪ {b_{1}}, we have at most |S| + 2 new sums. Continue the process until we have added all m numbers b_{1}, b_{2}, …, b_{m} to the set, the number of new sums is at most ∑_{i=1}^{m}(|S|+i) = m|S|+ \frac{m(m+1)}{2}. Our original set S has |S −S|−|S +S| = ℓ(n+1); therefore, if m|S| + \frac{m(m+1)}{2} < ℓ(n + 1), then |S^{∗} − S^{∗}| − |S^{∗} + S^{∗}| ≥ |S − S| − (|S + S| + m|S| + \frac{m(m+1)}{2}) ≥ 0. Therefore, S^{∗} is not sum-dominant.

6 Future work

We list some natural topics for future research.

• Is there a human-understandable proof that 6 is not the cardinality of a sum-dominant set?

• What is the smallest number of integers added to a set of numbers in an arithmetic progression to have a sum-dominant set?

• Is the following conjecture true?

Conjecture 17. The union of two arithmetic progressions is not a sum-dominant set.

The case analysis in this paper is unable to solve this general case because the complexity grows quickly when more numbers are added to an arithmetic progression. The case that the minimum of one arithmetic progression is bigger than the maximum of the other is easy. If this conjecture is true, our Theorem 2 follows immediately because the set of two numbers forms an arithmetic progression.

7 Acknowledgments

First, I would like to thank professor Steven Miller at Williams College for introducing me to this interesting topic. Next, many thanks to the anonymous referee for valuable comments which helped to improve the article. Thanks to professor Kevin Beanland at Washington and Lee University for proofreading this paper. Finally, I would like to dedicate this paper to my parents and my brother for their support throughout my undergraduate years at Washington and Lee University.

References

[1] M. Asada, S. Manski, S. J. Miller, and H. Suh, Fringe pairs in generalized MSTD sets, Int. J. Number Theory 13 (2017), 2653–2675.

[2] H. V. Chu, N. Luntzlara, S. J. Miller, and L. Shao, Infinite families of partitions into MSTD subsets, preprint, 2018. Available at https://arxiv.org/abs/1808.05460.

[3] H. V. Chu, N. Luntzlara, S. J. Miller, and L. Shao, Generalizations of a curious family of MSTD sets hidden by interior blocks, preprint, 2018. Available at https://arxiv.

org/abs/1808.05501.

[4] H. V. Chu, N. McNew, S. J. Miller, V. Xu, and S. Zhang, When sets can and cannot have sum-dominant subsets, J. Integer Seq, Vol. 18, 2018.

[5] G. A. Freiman and V. P. Pigarev, Number Theoretic Studies in the Markov Spectrum and in the Structural Theory of Set Addition (Russian), Kalinin. Gos. Univ., Moscow, 1973.

[6] P. V. Hegarty, Some explicit constructions of sets with more sums than differences, Acta Arith. 130 (2007), 61–77.

[7] G. Iyer, O. Lazarev, S. J. Miller, and L. Zhang, Generalized more sums than differences sets, J. Number Theory 132 (2012), 1054–1073.

[8] J. Marica, On a conjecture of Conway, Canad. Math. Bull. 12 (1969), 233–234.

[9] G. Martin and K. O’Bryant, Many sets have more sums than differences, in Additive Combinatorics, CRM Proc. Lecture Notes, Vol. 43, Amer. Math. Soc., 2007, pp. 287– 305.

[10] T. Mathur and T. A. Wong, On the computational complexity of MSTD sets, preprint,

2018. Available at https://arxiv.org/abs/1810.07358.

[11] S. J. Miller, B. Orosz, and D. Scheinerman, Explicit constructions of infinite families of MSTD sets, J. Number Theory 130 (2010), 1221–1233.

[12] S. J. Miller and D. Scheinerman, Explicit constructions of infinite families of MSTD sets, in Additive Number Theory, Springer, 2010, pp. 229–248.

[13] S. J. Miller and K. Vissuet, Most subsets are balanced in finite groups, in M. B. Nathanson, ed., Combinatorial and Additive Number Theory — CANT 2011 and 2012, Springer Proceedings in Mathematics & Statistics, Vol. 101, 2014, pp. 147–157.

[14] S. J. Miller, S. Pegado, and L. Robinson, Explicit constructions of large families of generalized more sums than differences sets, Integers 12 (2012), #A30.

[15] M. B. Nathanson, Problems in additive number theory, V: affinely inequivalent MSTD sets, North-West. Eur. J. Math 3 (2017), 123–141.

[16] M. B. Nathanson, Problems in additive number theory. I, in Additive Combinatorics, CRM Proc. Lecture Notes, Vol. 43, Amer. Math. Soc., 2007, pp. 263–270.

[17] M. B. Nathanson, Sets with more sums than differences, Integers 7 (2007), Paper #A5.

[18] M. B. Nathanson, MSTD sets and Freiman isomorphism, Funct. Approx. Comment. Math 58 (2018), 187–205.

[19] I. Z. Ruzsa, On the cardinality of A + A and A − A, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Coll. Math. Soc. J. Bolyai., Vol. 18, 1978, pp. 933–938.

[20] I. Z. Ruzsa, Sets of sums and differences, in Seminar on Number Theory, Paris 1982–83, Progr. Math., Vol. 51, Birkhäuser, 1984, pp. 267–273.

[21] I. Z. Ruzsa, On the number of sums and differences, Acta Math. Sci. Hungar. 59 (1992), 439–447.

[22] Y. Zhao, Constructing MSTD sets using bidirectional ballot sequences, J. Number Theory 130 (2010), 1212–1220.

[23] Y. Zhao, Counting MSTD sets in finite abelian groups, J. Number Theory 130 (2010), 2308–2322.

[24] Y. Zhao, Sets characterized by missing sums and differences, J. Number Theory 131 (2011), 2107–2134.

2010 Mathematics Subject Classification: Primary 11P99; Secondary 11K99. Keywords: sum-dominant set, MSTD set.

Received March 6 2019; revised versions received May 17 2019; May 20 2019. Published in Journal of Integer Sequences, May 21 2019.

Return to Journal of Integer Sequences home page.