The Inverse Problem on Subset Sums, II

Jian-Dong Wu^{1}

School of Mathematical Sciences and Institute of Mathematics Nanjing Normal University Nanjing 210023 P. R. China

                wujiandong@njnu.edu.cn

Abstract

For a set T of integers, let P (T) be the set of all finite subset sums of T, and let T (x) be the set of all integers of T not exceeding x. Let B = {b_{1} < b_{2} < ⋯ } be a sequence of integers and d_{1} = 10, d_{2} = 3b_{1} + 4, and d_{n} = 3b_{n−1} + 2 (n ≥ 3). In this paper, we prove that

(i) if b_{n} > d_{n} for all n ≥ 1, then there exists a sequence of positive integers A = {a_{1} < a_{2} < ⋯ } such that, for all k ≥ 2, P (A(b_{k})) = [0, 2b_{k}]\{b_{u}, 2b_{k} −b_{u} : 1 ≤ u ≤ k};

(ii) if b_{m} = d_{m} for some m ≥ 1 and b_{n} > d_{n} for all n ≠ m, then there is no such sequence A.

We also pose a problem for further research.

1 Introduction

For a sequence of integers A = {a_{1} < a_{2} < ⋯ }, let

P (A) = {∑ ε_{i}a_{i} : a_{i} ∈ A, ε_{i} = 0 or 1; ∑ ε_{i} < ∞} .

Here 0 ∈ P (A). Burr [1] asked the following question: which sets S of integers are equal to P (A) for some A? Let B = {b_{1} < b_{2} < ⋯ } = ℕ \ S, where ℕ = {0, 1, 2, …} is the set of all natural numbers. Burr mentioned that if b_{1} > b_{0} and b_{n+1} ≥ b_{n}^{2} for all n ≥ 1, then there exists an A such that P (A) = ℕ \ B. Hegyvári [4] proved that if b_{1} ≥ b_{0} and b_{n+1} ≥ 5b_{n} for all n ≥ 1, then such A exists. The condition b_{n+1} ≥ 5b_{n} has been improved to b_{n+1} ≥ 3b_{n} + 5 by Chen and Fang [2]. Recently, Chen and the author [3] proved that, if B = {b_{1} < b_{2} < ⋯ } is a sequence of integers with b_{1} ∈ {4, 7, 8} ∪ {b : b ≥ 11, b ∈ ℕ}, b_{2} ≥ 3b_{1} + 5, b_{3} ≥ 3b_{2} + 3 and b_{n+1} > 3b_{n} − b_{n−2} for all n ≥ 3, then there exists a sequence of positive integers A = {a_{1} < a_{2} < ⋯ } such that P (A) = ℕ \ B.

1This work is supported by the National Natural Science Foundation of China (Grant No. 11371195)

and the Program of Natural Science Research of Jiangsu Higher Education Institutions of China (Grant No.

13KJD110005).

For any set T of integers and any real number x, let T (x) be the set of all integers of T not exceeding x. Let [a, b] = {n : n ∈ ℕ, a ≤ n ≤ b}, and let x + T = {x + a : a ∈ T }.

In this paper, we prove the following result.

Theorem 1. Let B = {b_{1} < b_{2} < ⋯ } be a sequence of integers, and let d_{1} = 10, d_{2} = 3b_{1}+4, and d_{n} = 3b_{n−1} + 2 (n ≥ 3). Then

(i) if b_{n} > d_{n} for all n ≥ 1, then there exists a sequence of positive integers A = {a_{1} < a_{2} < ⋯ } such that, for all k ≥ 2,

P (A(b_{k})) = [0, 2b_{k}] \ {b_{u}, 2b_{k} − b_{u} : 1 ≤ u ≤ k};

(ii) if b_{m} = d_{m} for some m ≥ 1 and b_{n} > d_{n} for all n ≠ m, then, for any sequence of positive integers A = {a_{1} < a_{2} < ⋯ }, there exists an index k ≥ 2 such that

P (A(b_{k})) ≠ [0, 2b_{k}] \ {b_{u}, 2b_{k} − b_{u} : 1 ≤ u ≤ k}.

Remark 2. Theorem 1 gives a segment version of the original problem. The symmetry of the missing set is related to the structure of a subset sum. The analogous result for P (A(b_{k} − b_{k−1})) was given in [3].

We pose a problem here.

Problem 3. Determine all sequences of integers B = {b_{1} < b_{2} < ⋯ } for which there exist two sequences of positive integers A = {a_{1} < a_{2} < ⋯ } and X = {x_{1} < x_{2} < ⋯ } such that, for all k ≥ 2,

P (A(x_{k})) = [0, 2b_{k}] \ {b_{u}, 2b_{k} − b_{u} : 1 ≤ u ≤ k}.

2 Proof of Theorem 1

First, we prove Theorem 1 (i). By the proof of [2, Theorem 1], there exists a subset A_{2} of [1, b_{2} − b_{1}] ⊂ [1, b_{2}] such that P (A_{2}) = [0, 2b_{2}] \ {b_{1}, b_{2}, 2b_{2} − b_{1}}. Suppose that k ≥ 2, A_{k} ⊆ [1, b_{k}] and

P (A_{k}) = [0, 2b_{k}] \ {b_{u}, 2b_{k} − b_{u} : 1 ≤ u ≤ k}.  (1)

We deal with the case k + 1. If b_{k+1} ≥ 3b_{k} + 5, then, by the proof of [2, Theorem 1], we can construct the required A_{k+1}. So we consider the case 3b_{k} + 3 ≤ b_{k+1} ≤ 3b_{k} + 4. Similar to the arguments in [2] and [3], we have

P (A_{k} ∪ {b_{k} + 1}) = [0, 3b_{k} + 1] \ {b_{u}, 3b_{k} − b_{u} + 1 : 1 ≤ u ≤ k},

P (A_{k} ∪ {b_{k} + 1, b_{k+1} − 2b_{k} − 1}) = [0, b_{k+1} + b_{k}] \ {b_{u}, b_{k+1} + b_{k} − b_{u} : 1 ≤ u ≤ k},

P (A_{k} ∪ {b_{k} + 1, b_{k+1} − 2b_{k} − 1, b_{k+1} − b_{k}}) = [0, 2b_{k+1}] \ {b_{u}, 2b_{k+1} − b_{u} : 1 ≤ u ≤ k + 1}.

Let

A_{k+1} = A_{k} ∪ {b_{k} + 1, b_{k+1} − 2b_{k} − 1, b_{k+1} − b_{k}}.

Thus, we have constructed a sequence of sets {A_{k}}_{k=1}^{∞} such that A_{1} ⊆ A_{2} ⊆ ⋯, A_{k+1} \A_{k} ⊆ (b_{k}, b_{k+1}] (k ≥ 1) and (1) holds for all k ≥ 2. Let A = ⋃_{k=1}^{∞} A_{k}. Then, for all k ≥ 2,

P (A(b_{k})) = [0, 2b_{k}] \ {b_{u}, 2b_{k} − b_{u} : 1 ≤ u ≤ k}.

Now we prove Theorem 1 (ii). The proof is similar to that of [3, Theorem 2].

Suppose that there exists a sequence A = {a_{1} < a_{2} < ⋯ } of positive integers such that

P (A(b_{s})) = [0, 2b_{s}] \ {b_{k}, 2b_{s} − b_{k} : 1 ≤ k ≤ s}

for all s ≥ 2. Then P (A) = ℕ\B. By [2], we may assume that m ≥ 3. Thus b_{m} = 3b_{m−1} +2. Let A(b_{m−1}) = A ∩ [0, b_{m−1}] = {a_{1}, …, a_{m′}}. Then

a_{m′+1} + P (A(b_{m−1})) = [a_{m′+1}, a_{m′+1} + 2b_{m−1}] \ B_{m,1},

where B_{m,1} = {a_{m′+1} +b_{k}, a_{m′+1} +2b_{m−1} −b_{k} : 1 ≤ k ≤ m−1}. If a_{m′+1} > 2b_{m−1} −b_{m−2}, then 2b_{m−1}−b_{m−2} ∉ P (A), a contradiction. Hence a_{m′+1} ≤ 2b_{m−1}−b_{m−2}. By a_{m′+1} ∉ A∩[0, b_{m−1}], we have a_{m′+1} > b_{m−1}.

Case 1: a_{m′+1} = b_{m−1} + 1. Similar to the arguments in [2] and [3], we have

P (A(b_{m−1}) ∪ {a_{m′+1}}) = [0, b_{m} − 1] \ B_{m,2},

where B_{m,2} = {b_{k}, b_{m} − 1 − b_{k} : 1 ≤ k ≤ m − 1}. Thus

a_{m′+2} + P (A(b_{m−1}) ∪ {a_{m′+1}}) = [a_{m′+2}, a_{m′+2} + b_{m} − 1] \ B_{m,3},

where B_{m,3} = {a_{m′+2} + b_{k}, a_{m′+2} + b_{m} − 1 − b_{k} : 1 ≤ k ≤ m − 1}. If a_{m′+2} ≤ b_{m} − 1 − b_{m−1}, then

b_{m} ∈ [a_{m′+2}, a_{m′+2} + b_{m} − 1], a_{m′+2} + b_{m−1} < b_{m} < a_{m′+2} + b_{m} − 1 − b_{m−1}.

Thus b_{m} ∈ a_{m′+2} + P (A(b_{m−1}) ∪ {a_{m′+1}}), a contradiction. If a_{m′+2} > b_{m} − 1 − b_{m−1}, then, by b_{m} − 1 − b_{m−1} ∉ P (A(b_{m−1}) ∪ {a_{m′+1}}), we have b_{m} − 1 − b_{m−1} ∉ P (A), a contradiction.

Case 2: b_{m−1} + 2 ≤ a_{m′+1} ≤ 2b_{m−1} − b_{m−2}. By b_{m} ∈ [a_{m′+1}, a_{m′+1} + 2b_{m−1}] and a_{m′+1} + b_{m−1} ≤ 3b_{m−1} − b_{m−2} < b_{m}, there exist some u_{0}(1 ≤ u_{0} ≤ m − 2) such that a_{m′+1} + 2b_{m−1} − b_{u_{0}} = b_{m} = 3b_{m−1} + 2. Hence a_{m′+1} = b_{m−1} + b_{u_{0}} + 2.

If there exist u, v with 1 ≤ u, v ≤ m − 2 such that 2b_{m−1} − b_{u} = a_{m′+1} + b_{v}, then, by a_{m′+1} = b_{m−1} + b_{u_{0}} + 2, we have b_{m−1} = b_{u} + b_{v} + b_{u_{0}} + 2 ≤ 3b_{m−2} + 2. This contradicts the condition b_{m−1} > 3b_{m−2} + 2. Hence 2b_{m−1} − b_{u} ≠ a_{m′+1} + b_{v}(1 ≤ u, v ≤ m − 2) and then

P (A(b_{m−1}) ∪ {a_{m′+1}}) = [0, b_{m} + b_{u_{0}}] \ {b_{k}, b_{m} + b_{u_{0}} − b_{k} : 1 ≤ k ≤ m − 1}.

Thus, for i ≥ 2, we have

a_{m′+i} + P (A(b_{m−1}) ∪ {a_{m′+1}}) = [a_{m′+i}, a_{m′+i} + b_{m} + b_{u_{0}}] \ B_{m,4},

where B_{m,4} = {a_{m′+i} + b_{k}, a_{m′+i} + b_{m} + b_{u_{0}} − b_{k} : 1 ≤ k ≤ m − 1}.

If a_{m′+2} > b_{m}+b_{u_{0}}−b_{m−1}, then b_{m}+b_{u_{0}}−b_{m−1} ∉ P (A), a contradiction. So b_{m−1}+b_{u_{0}}+2 = a_{m′+1} < a_{m′+2} ≤ b_{m} + b_{u_{0}} − b_{m−1}. Let b_{m−1} + b_{u_{0}} + 2 < a_{m′+i} ≤ b_{m} + b_{u_{0}} − b_{m−1}. Then

a_{m′+i} + b_{m−2} < b_{m} < a_{m′+i} + b_{m} + b_{u_{0}} − b_{m−1}.  (2)

Since b_{m} ∉ P (A), it follows that b_{m} ∉ a_{m′+i}+P (A(b_{m−1})∪{a_{m′+1}}). Hence b_{m} ∈ B_{m,4}. Thus, by (2), b_{m} = a_{m′+i} + b_{m−1}, i.e., a_{m′+i} = b_{m} − b_{m−1}. So i = 2 and a_{m′+3} > b_{m} + b_{u_{0}} − b_{m−1}. Thus

b_{m} + b_{u_{0}} − b_{m−1} = a_{m′+i} + b_{u_{0}}
∉ (P (A(b_{m−1}) ∪ {a_{m′+1}})) ∪ (a_{m′+i} + P (A(b_{m−1}) ∪ {a_{m′+1}}))
= P (A(b_{m−1}) ∪ {a_{m′+1}, a_{m′+2}}).

By a_{m′+3} > b_{m} +b_{u_{0}} −b_{m−1}, we have b_{m} +b_{u_{0}} −b_{m−1} ∉ P (A), a contradiction. This completes the proof of Theorem 1 (ii).

3 Acknowledgments

I sincerely thank my supervisor Professor Yong-Gao Chen for his valuable suggestions and useful discussions. I am also grateful to the referee for his/her valuable comments.

References

[1] S. A. Burr, in: P. Erdős, A. Rényi, V. T. Sós, eds., Combinatorial Theory and its Applications III, Coll. Math. Soc. J. Bolyai, Vol. 4, North-Holland, 1970, p. 1155.

[2] Y. G. Chen and J. H. Fang, On a problem in additive number theory, Acta Math. Hungar. 134 (2012), 416–430.

[3] Y. G. Chen and J. D. Wu, The inverse problem on subset sums, European J. Combin. 34 (2013), 841–845.

[4] N. Hegyvári, On representation problems in the additive number theory, Acta Math. Hungar. 72 (1996), 35–44.

2010 Mathematics Subject Classification: Primary 11B13. Keywords: subset sum, representation problem, Burr’s problem, complement.

Received May 7 2013; revised version received September 5 2013. Published in Journal of Integer Sequences, October 12 2013.

Return to Journal of Integer Sequences home page.