A Note on Sumsets and Restricted Sumsets

Jagannath Bhanja Harish-Chandra Research Institute Chhatnag Road, Jhunsi Prayagraj 211019 India

                  jagannathbhanja@hri.res.in

Abstract

In this note we find the optimal lower bound for the size of the sumsets HA and H Â over finite sets H, A of nonnegative integers, where HA = ⋃_{h∈H} hA and H Â = ⋃_{h∈H} h Â. We also find the underlying algebraic structure of the sets A and H for which the size of the sumsets HA and H Â is minimum.

1 Introduction

For a given finite set A of integers and for a positive integer h, the sumset hA and the restricted sumset h Â are fundamental objects in the field of additive number theory. The sumset hA is the set of integers that can be written as the sum of h elements of A, whereas the sumset h Â is the set of integers that can be written as the sum of h pairwise distinct elements of A. In this regard, two of the important problems in additive number theory are to find the best possible lower bounds for the size of the sumsets hA and h Â, and to find the structure of the finite set A for which the sumsets hA and h Â contain the minimum number of elements. These two problems have been well established in the group of integers [4, 5].

Theorem 1. [5, Theorem 1.4, Theorem 1.6] Let A be a finite set of k integers. Let h be a positive integer. Then

|hA| ≥ h(k − 1) + 1.

Moreover, if this lower bound is exact with h ≥ 2, then A is an arithmetic progression.

Theorem 2. [4, Theorem 1, Theorem 2] Let A be a finite set of k integers. Let h ≤ k be a positive integer. Then

|h Â| ≥ h(k − h) + 1.

Moreover, if this lower bound is exact with k ≥ 5 and 2 ≤ h ≤ k − 2, then A is an arithmetic progression.

Now let H be a given finite set of nonnegative integers. Define the sumset [1, p. 175]

HA := ⋃_{h∈H} hA,

and the restricted sumset

H Â := ⋃_{h∈H} h Â.

Here we are assuming that 0A = 0 Â = {0}.

For a set A and for an integer c, we let c · A = {ca : a ∈ A}. For integers a, b with a ≤ b, we also let [a, b] = {a, a + 1, …, b}.

The case H = [0, r] is more interesting and has been studied before (for recent papers, see [1, 2, 3]). Bajnok [1] defined the sumsets for an arbitrary finite set H of nonnegative integers, and asked to study similar problems like the sumsets hA and h Â over finite abelian groups. That is, find the optimal lower bound for the size of the sumsets HA and H Â, and the structure of the sets H, A for which the sumsets HA, H Â contain the minimum number of elements.

In this note, we study these two problems for the sumset HA in Section 2, and the sumset H Â in Section 3, for finite sets A of nonnegative integers (or nonpositive integers) and H of nonnegative integers. We consider two separate cases, namely

(i) the set A consists of positive integers and

(ii) the set A consists of nonnegative integers.

The cases

(iii) the set A consists of negative integers and

(iv) the set A consists of nonpositive integers,

follow from the cases (i) and (ii), respectively, as H(c · A) = c · HA and Hˆ (c · A) = c · H Â for arbitrary integers c. As consequences of our results we obtain some recent results in this direction.

In Section 2 and Section 3, we use the following notation: for a set S = {s_{1}, s_{2}, …, s_{k−1}, s_{k}} with k ≥ 2 and s_{1} < s_{2} < ⋯ < s_{k−1} < s_{k}, we write min(S) = s_{1}, min_{+}(S) = s_{2}, max(S) = s_{k}, and max_{−}(S) = s_{k−1}.

2 Regular sumset

Theorem 3. Let A be a set of k positive integers. Let H be a set of r positive integers with max(H) = h_{r}. Then

|HA| ≥ h_{r}(k − 1) + r.  (1)

This lower bound is optimal.

Proof. Let A = {a_{1}, a_{2}, …, a_{k}} and H = {h_{1}, h_{2}, …, h_{r}}, where 0 < a_{1} < a_{2} < ⋯ < a_{k} and 0 < h_{1} < h_{2} < ⋯ < h_{r}. Set

S_{1} := h_{1}A  (2)

and

S_{i} := (h_{i} − h_{i−1})A + h_{i−1}a_{k},  (3)

for i = 2, 3, …, r. Clearly S_{i} ⊆ h_{i}A for i = 1, 2, …, r, and max(S_{i}) < min(S_{i+1}) for i = 1, 2, …, r − 1. Therefore S_{1}, S_{2}, …, S_{r} are pairwise disjoint subsets of HA. Hence, by Theorem 1, we have

|HA| ≥ ∑_{i=1}^{r} |S_{i}|

= |h_{1}A| + ∑_{i=2}^{r} |S_{i}|

≥ h_{1}(k − 1) + 1 + ∑_{i=2}^{r}[(h_{i} − h_{i−1})(k − 1) + 1]

= h_{r}(k − 1) + r.  (4)

This proves (1).

To see that the lower bound in (1) is optimal, let A = [1, k] and H = [1, r]. Then HA = [1, rk], and hence |HA| = rk. This completes the proof of the theorem.

Remark 4. If A contains nonnegative integers with 0 ∈ A, then HA = h_{r}A, as h_{i}A ⊆ h_{r}A for i = 1, 2, …, r −1. Therefore, by Theorem 1, we have |HA| ≥ h_{r}(k −1)+1. Furthermore, this bound is optimal, and it can be seen by taking A = [0, k − 1] and H = [1, r].

Now we prove the inverse result of Theorem 3.

Theorem 5. Let A be a set of k ≥ 2 positive integers and H be a set of r ≥ 2 positive integers with max(H) = h_{r}. If |HA| = h_{r}(k − 1) + r, then H is an arithmetic progression of difference d and A is an arithmetic progression of difference d · min(A).

Proof. Let A = {a_{1}, a_{2}, …, a_{k}} and H = {h_{1}, h_{2}, …, h_{r}}, where 0 < a_{1} < a_{2} < ⋯ < a_{k} and 0 < h_{1} < h_{2} < ⋯ < h_{r}. Let |HA| = h_{r}(k − 1) + r. Then the sumset HA contains precisely the elements of the sets S_{i} for i = 1, …, r, which are defined in (2), (3).

First, we show that A is an arithmetic progression. Observe that the assumption |HA| = h_{r}(k − 1) + r together with (4) implies |h_{1}A| = h_{1}(k − 1) + 1. If h_{1} > 1, then from Theorem 1, it follows that the set A is an arithmetic progression. So, let h_{1} = 1. Then

S_{1} = h_{1}A = A = {a_{1}, a_{2}, …, a_{k}}.

Set

S := {a_{1}, h_{2}a_{1}, (h_{2} − 1)a_{1} + a_{2}, …, (h_{2} − 1)a_{1} + a_{k−1}}.

Clearly S ⊆ HA and max(S) = (h_{2} −1)a_{1} +a_{k−1} < (h_{2} −1)a_{1} +a_{k} = min(S_{2}). Thus S = S_{1}. In other words, (h_{2} − 1)a_{1} + a_{i−1} = a_{i} for i = 2, 3, …, k. Equivalently, a_{i} − a_{i−1} = (h_{2} − 1)a_{1} for i = 2, 3, …, k. Hence, A is an arithmetic progression.

Next we show that H is an arithmetic progression. For i = 1, 2, …, r − 1, consider the integers (h_{i+1} − h_{i})a_{1} + a_{k−1} + (h_{i} − 1)a_{k}. Clearly

max_{−}(S_{i}) = a_{k−1} + (h_{i} − 1)a_{k} < (h_{i+1} − h_{i})a_{1} + a_{k−1} + (h_{i} − 1)a_{k} < (h_{i+1} − h_{i})a_{1} + h_{i}a_{k} = min(S_{i+1}).

But we already have

max_{−}(S_{i}) = a_{k−1} + (h_{i} − 1)a_{k} < h_{i}a_{k} = max(S_{i}) < (h_{i+1} − h_{i})a_{1} + h_{i}a_{k} = min(S_{i+1}).

Thus

(h_{i+1} − h_{i})a_{1} + a_{k−1} + (h_{i} − 1)a_{k} = h_{i}a_{k} for i = 1, 2, …, r − 1.

This implies

a_{k} − a_{k−1} = (h_{i+1} − h_{i})a_{1} for i = 1, 2, …, r − 1.  (5)

Therefore

h_{2} − h_{1} = h_{3} − h_{2} = ⋯ = h_{r} − h_{r−1},

and hence the set H is an arithmetic progression. Furthermore, by (5), the set A is an arithmetic progression of difference (h_{i+1} − h_{i})a_{1}. This completes the proof of the theorem.

3 Restricted sumset

Theorem 6. Let A be a set of k positive integers and H = {h_{1}, h_{2}, …, h_{r}} be a set of positive integers with h_{1} < h_{2} < ⋯ < h_{r} ≤ k. Set h_{0} = 0. Then

|H Â| ≥ ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i}) + r.  (6)

This lower bound is optimal.

Proof. Let A = {a_{1}, a_{2}, …, a_{k}}, where a_{1} < a_{2} < ⋯ < a_{k}. Set

S_{1} := h_{1} Â  (7)

and

S_{i} := (h_{i} − h_{i−1}) Â_{i} + max(h_{i−1} Â),  (8)

for i = 2, 3, …, r, where A_{i} = {a_{1}, a_{2}, …, a_{k−h_{i−1}}}. Clearly S_{i} ⊆ h_{i} Â for i = 1, 2, …, r, and max(S_{i}) < min(S_{i+1}) for i = 1, 2, …, r − 1. Therefore S_{1}, S_{2}, …, S_{r} are pairwise disjoint subsets of H Â. Hence, by Theorem 2, we have

|H Â| ≥ ∑_{i=1}^{r} |S_{i}|

= |h_{1} Â| + ∑_{i=2}^{r} |S_{i}|

≥ h_{1}(k − h_{1}) + 1 + ∑_{i=2}^{r}[(h_{i} − h_{i−1})(k − h_{i}) + 1]

= ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i}) + r.  (9)

This proves (6).

Next to see that the lower bound in (6) is optimal, let A = [1, k] and H = [1, r] with r ≤ k. Then H Â ⊆ [1, k + (k − 1) + ⋯ + (k − r + 1)]. Therefore |H Â| ≤ rk − \frac{r(r−1)}{2}. This together with (6) implies |H Â| = rk − \frac{r(r−1)}{2}, and hence completes the proof of the theorem.

As a consequence of Theorem 6, we obtain the following corollary.

Corollary 7. Let A be a set of k nonnegative integers with 0 ∈ A. Let H = {h_{1}, h_{2}, …, h_{r}} be a set of positive integers with h_{1} < h_{2} < ⋯ < h_{r} ≤ k − 1. Set h_{0} = 0. Then

|H Â| ≥ ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i} − 1) + r + 1.  (10)

This lower bound is optimal.

Proof. Let A′ = A \ {0}. Then H Â′ ∪ {0} ⊆ H Â. This implies

|H Â| ≥ |H Â′| + 1 ≥ ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i} − 1) + r + 1.

Furthermore, the optimality of the lower bound in (10) can be checked by taking A = [0, k − 1] and H = [1, r], where k, r are positive integers with r ≤ k − 1.

The following result (which has recently been proved) is a particular case of Theorem 6 and Corollary 7.

Corollary 8. [3, Theorem 2.1, Corollary 2.1] Let A be a set of k nonnegative integers and H = [0, r] with r ≤ k. If 0 ∉ A, then

|H Â| ≥ rk − \frac{r(r − 1)}{2} + 1.

If 0 ∈ A and r ≤ k − 1, then

|H Â| ≥ rk − \frac{r(r + 1)}{2} + 1.

These lower bounds are optimal.

Now we prove the inverse theorem of Theorem 6.

Theorem 9. Let A be a set of k ≥ 6 positive integers. Let H = {h_{1}, h_{2}, …, h_{r}} be a set of r ≥ 2 positive integers with h_{1} < h_{2} < ⋯ < h_{r} ≤ k − 1. Set h_{0} = 0. If

|H Â| = ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i}) + r,

then H = h_{1} + [0, r − 1] and A = min(A) · [1, k].

Proof. Let A = {a_{1}, a_{2}, …, a_{k}}, where 0 < a_{1} < a_{2} < ⋯ < a_{k}. Let |H Â| = ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i}) + r. Then the sumset H Â contains precisely the elements of the sets S_{i} for i = 1, …, r, which are defined in (7), (8).

First, we show that A is an arithmetic progression. Since |H Â| = ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i}) + r, from (9), it follows that |h_{1} Â| = h_{1}(k − h_{1}) + 1. If h_{1} ≥ 2, then by Theorem 2, the set A is an arithmetic progression. Therefore, let h_{1} = 1.

If h_{2} ≥ 3, then h_{2} − h_{1} ≥ 2. By (9), we get |S_{2}| = |(h_{2} − h_{1}) Â_{2}| = (h_{2} − h_{1})(k − h_{2}) + 1, where A_{2} = {a_{1}, a_{2}, …, a_{k−1}}. Therefore, by Theorem 2, the set A_{2} is an arithmetic progression. To show that A is an arithmetic progression, it is left to show that a_{k} − a_{k−1} = a_{k−1} − a_{k−2}. Consider the following integers:

a_{k−2} < a_{1} + ⋯ + a_{h_{2}−1} + a_{k−2} < a_{1} + ⋯ + a_{h_{2}−1} + a_{k−1} < a_{1} + ⋯ + a_{h_{2}−1} + a_{k} = min(S_{2}).

But we already have

a_{k−2} < a_{k−1} < a_{k} < a_{1} + ⋯ + a_{h_{2}−1} + a_{k} = min(S_{2}),

where {a_{k−2}, a_{k−1}, a_{k}} ⊆ S_{1}. Thus

a_{1} + ⋯ + a_{h_{2}−1} + a_{k−2} = a_{k−1} and a_{1} + ⋯ + a_{h_{2}−1} + a_{k−1} = a_{k}.

This implies

a_{k} − a_{k−1} = a_{1} + ⋯ + a_{h_{2}−1} = a_{k−1} − a_{k−2},

and we are done.

Now let h_{2} = 2; i.e., h_{2} −h_{1} = 1. Set T_{1} := {a_{1}, a_{2}, a_{1} +a_{2}, a_{1} +a_{3}, …, a_{1} +a_{k−1}}. Clearly T_{1} ⊆ h_{1} Â ∪ h_{2} Â ⊆ H Â and max(T_{1}) = a_{1} + a_{k−1} < a_{1} + a_{k} = min(S_{2}). Therefore T_{1} = S_{1}. That is

{a_{1}, a_{2}, a_{1} + a_{2}, a_{1} + a_{3}, …, a_{1} + a_{k−1}} = {a_{1}, a_{2}, a_{3}, …, a_{k}}.

Thus a_{i} = a_{1}+a_{i−1} for i = 3, 4, …, k. Equivalently, a_{i}−a_{i−1} = a_{1} for i = 3, 4, …, k. To show that A is an arithmetic progression it is enough to show a_{2} − a_{1} = a_{k} − a_{k−1}. Consider the integer a_{2} + a_{k−1}. Since max(S_{1}) = max(T_{1}) = a_{1} + a_{k−1} < a_{2} + a_{k−1} < a_{2} + a_{k} = min^{+}(S_{2}) and max(S_{1}) = max(T_{1}) = a_{1} + a_{k−1} < a_{1} + a_{k} = min(S_{2}) < a_{2} + a_{k} = min^{+}(S_{2}), we must have a_{2} + a_{k−1} = a_{1} + a_{k}. This proves A is an arithmetic progression.

Next we show that H is an arithmetic progression. For i = 1, 2, …, r − 1, consider the following integers:

max_{−}(S_{i}) = a_{k−h_{i}} + a_{k−h_{i}+2} + ⋯ + a_{k} < a_{k−h_{i}+1} + ⋯ + a_{k} = max(S_{i})

< a_{1} + ⋯ + a_{h_{i+1}−h_{i}} + a_{k−h_{i}+1} + ⋯ + a_{k} = min(S_{i+1})

and

max_{−}(S_{i}) = a_{k−h_{i}} + a_{k−h_{i}+2} + ⋯ + a_{k} < a_{1} + ⋯ + a_{h_{i+1}−h_{i}} + a_{k−h_{i}} + a_{k−h_{i}+2} + ⋯ + a_{k} < a_{1} + ⋯ + a_{h_{i+1}−h_{i}} + a_{k−h_{i}+1} + ⋯ + a_{k} = min(S_{i+1}).

Therefore

a_{k−h_{i}+1} + ⋯ + a_{k} = a_{1} + ⋯ + a_{h_{i+1}−h_{i}} + a_{k−h_{i}} + a_{k−h_{i}+2} + ⋯ + a_{k}

for i = 1, 2, …, r − 1. This implies

a_{k−h_{i}+1} − a_{k−h_{i}} = a_{1} + ⋯ + a_{h_{i+1}−h_{i}} for i = 1, 2, …, r − 1.  (11)

Since A is an arithmetic progression, the difference between any two consecutive elements in A is same. Therefore

a_{2} − a_{1} = a_{k−h_{i}+1} − a_{k−h_{i}} = a_{1} + a_{2} + ⋯ + a_{h_{i+1}−h_{i}} for i = 1, 2, …, r − 1.

This holds, only if h_{i+1} − h_{i} = 1 for i = 1, 2, …, r − 1. Hence, H = h_{1} + [0, r − 1] and A = a_{1} · [1, k]. This completes the proof of the theorem.

Corollary 10. Let A be a set of k ≥ 7 nonnegative integers with 0 ∈ A. Let H = {h_{1}, h_{2}, …, h_{r}} be a set of r ≥ 2 positive integers with h_{1} < h_{2} < ⋯ < h_{r} ≤ k − 1. Set h_{0} = 0. If

|H Â| = ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − h_{i} − 1) + r + 1,

then H = h_{1} + [0, r − 1] and A = min(A \ {0}) · [0, k − 1].

Proof. Let A′ := A\{0}. Then the equality |H Â| = ∑_{i=1}^{r}(h_{i}−h_{i−1})(k−h_{i}−1)+r+1 implies |H Â′| = ∑_{i=1}^{r}(h_{i} − h_{i−1})(k − 1 − h_{i}) + r. Thus by Theorem 9, we get H = h_{1} + [0, r − 1] and A′ = min(A′) · [1, k − 1]. Hence, H = h_{1} + [0, r − 1] and A = min(A′) · [0, k − 1]. This proves the theorem.

The following inverse result (which has recently been proved) is a particular case of Theorem 9 and Corollary 10.

Corollary 11. [3, Theorem 2.2, Corollary 2.3] Let A be a set of k ≥ 7 nonnegative integers and H = [0, r] with 2 ≤ r ≤ k − 1. If 0 ∉ A and |H Â| = rk − \frac{r(r−1)}{2} + 1, then A = d · [1, k] for some positive integer d.

If 0 ∈ A and |H Â| = rk − \frac{r(r+1)}{2} + 1, then A = d · [0, k − 1] for some positive integer d.

4 Acknowledgement

We would like to thank Professor R. Thangadurai for carefully going through this manuscript. We would also like to thank the editor-in-chief and the anonymous referee for the helpful comments and suggestions which helped improve the article. We also acknowledge the support of the PDF scheme of Harish-Chandra Research Institute, Prayagraj.

References

[1] B. Bajnok, Additive Combinatorics: A Menu of Research Problems, Discrete Mathematics and its Applications, CRC Press, 2018.

[2] É. Balandraud, Addition theorems in 𝔽_{p} via the polynomial method, preprint, 2017.

   Available at https://arxiv.org/abs/1702.06419.

[3] J. Bhanja and R. K. Pandey, Inverse problems for certain subsequence sums in integers, Discrete Math. 343 (2020), 112148.

[4] M. B. Nathanson, Inverse theorems for subset sums, Trans. Amer. Math. Soc. 347 (1995), 1409–1418.

[5] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, 1996.

2020 Mathematics Subject Classification: Primary 11P70; Secondary 11B75, 11B13. Keywords: sumset, restricted sumset.

Received August 22 2020; revised versions received August 23 2020; February 1 2021; March 27 2021; March 28 2021. Published in Journal of Integer Sequences, March 28 2021.

Return to Journal of Integer Sequences home page.