Infinite Sets of Integers Whose Distinct Elements Do Not Sum to a Power

Artūras Dubickas and Paulius Šarka Department of Mathematics and Informatics Vilnius University Naugarduko 24 Vilnius LT-03225 Lithuania

              arturas.dubickas@maf.vu.lt
                paulius.sarka@mif.vu.lt

Abstract

We first prove two results which both imply that for any sequence B of asymptotic density zero there exists an infinite sequence A such that the sum of any number of distinct elements of A does not belong to B. Then, for any ε > 0, we construct an infinite sequence of positive integers A = {a_{1} < a_{2} < a_{3} < … } satisfying a_{n} < K(ε)(1 + ε)^{n} for each n ∈ ℕ such that no sum of some distinct elements of A is a perfect square. Finally, given any finite set U ⊂ ℕ, we construct a sequence A of the same growth, namely, a_{n} < K(ε, U)(1 + ε)^{n} for every n ∈ ℕ such that no sum of its distinct elements is equal to uv^{s} with u ∈ U, v ∈ ℕ and s ⩾ 2.

1 Introduction

Let B = {b_{1} < b_{2} < b_{3} < … } be an infinite sequence of positive integers. In this note we are interested in the following two questions.

• For which B there exists an infinite sequence of positive integers A = {a_{1} < a_{2} < a_{3} < … } such that a_{i_{1}} + ⋯ + a_{i_{m}} ∉ B for every m ∈ ℕ and any distinct elements a_{i_{1}}, …, a_{i_{m}} ∈ A?

• In the case when the answer is ‘yes’, how dense the sequence A can be?

In his paper [2], F. Luca considered the case when B is the set of all perfect squares {1, 4, 9, 16, 25, 36, … } and of all perfect powers {1, 4, 8, 9, 16, 25, 27, 32, 36, … }. He showed that in both cases the answer to the first question is ‘yes’. In particular, it was observed in [2] that the sum of any distinct Fermat numbers 2^{2^{n}} + 1, n = 1, 2, …, is not a perfect square. Moreover, it was proved that the sum of any distinct numbers of the form a^{p_{1}p_{2}...p_{n}} + 1, n = n_{0}, n_{0} + 1, …, where a ⩾ 2 is an integer, p_{k} is the kth prime number and n_{0} = n_{0}(a) is an effectively computable constant, cannot be a perfect power.

2 Sets with asymptotic density zero

We begin with the following observation (see also [1]) which settles the first of the two problems stated above for every set B satisfying lim sup_{n→∞}(b_{n+1} − b_{n}) = ∞.

Theorem 2.1. Let m ∈ ℕ and let B = {b_{1} < b_{2} < b_{3} < … } be an infinite sequence of positive integers satisfying lim sup_{n→∞}(b_{n+1} − mb_{n}) = ∞. Then there exists an infinite sequence of positive integers A such that every sum over some elements of A, at most m of which are equal, is not in B.

Proof. Take the smallest positive integer ℓ such that b_{ℓ+1} − b_{ℓ} ⩾ 2, and set a_{1} := b_{ℓ} + 1. Then a_{1} ∉ B. Suppose we already have a finite set {a_{1} < a_{2} < ⋯ < a_{k}} such that all possible (m + 1)^{k} − 1 nonzero sums δ_{1}a_{1} + ⋯ + δ_{k}a_{k}, where δ_{1}, …, δ_{k} ∈ {0, 1, …, m}, do not belong to B. Put a_{k+1} := b_{l} + 1, where l is the smallest positive integer for which b_{l+1} − mb_{l} ⩾ 1+m+m(a_{1} +⋯+a_{k}) and b_{l} ⩾ a_{k}. Such an l exists, because lim sup_{n→∞}(b_{n+1} −mb_{n}) = ∞.

Clearly, b_{l} ⩾ a_{k} implies that a_{k+1} > a_{k}. In order to complete the proof of the theorem (by induction) it suffices to show that no sum of the form δ_{1}a_{1} + ⋯ + δ_{k}a_{k} + δ_{k+1}a_{k+1}, where δ_{1}, …, δ_{k+1} ∈ {0, 1, …, m}, lies in B. If δ_{k+1} = 0, this follows by our assumption, so suppose that δ_{k+1} ⩾ 1. Then δ_{1}a_{1} + ⋯ + δ_{k}a_{k} + δ_{k+1}a_{k+1} is greater than a_{k+1} − 1 = b_{l} and smaller than

1 + m(a_{1} + ⋯ + a_{k} + a_{k+1}) ⩽ b_{l+1} − mb_{l} − m + ma_{k+1} = b_{l+1} − mb_{l} − m + m(b_{l} + 1) = b_{l+1},

so it is not in B, as claimed. □

Recall that the upper asymptotic density \overline{d}(B) of the sequence B is defined as

\overline{d}(B) = lim sup_{N→∞} \frac{#\{n ∈ ℕ : b_{n} ⩽ N\}}{N}

(see, e.g., 1.2 in [4]). Similarly, the lower asymptotic density \underline{d}(B) is defined as \underline{d}(B) = lim inf_{N→∞} N^{−1}#\{n ∈ ℕ : b_{n} ⩽ N\}. If \overline{d}(B) = \underline{d}(B), then the common value d(B) = \overline{d}(B) = \underline{d}(B) is said to be the asymptotic density of B.

Evidently, if B has asymptotic density zero then, for any positive integer k, there are infinitely many positive integers N such that the numbers N + 1, N + 2, …, N + k do not lie in B. This implies that the condition lim sup_{n→∞}(b_{n+1} − b_{n}) = ∞ holds. Hence, by Theorem 2.1 with m = 1, for any sequence B of asymptotic density zero there exists an infinite sequence A such that the sum of any number of distinct elements of A is not in B. It is well-known that the sequence of perfect powers has asymptotic density zero, so such an A as claimed exists for B = {1, 4, 8, 9, 16, 25, 27, 32, 36, … }.

For m ⩾ 2, it can very often happen that b_{n+1} < mb_{n} for every n ∈ ℕ. For such a set B Theorem 2.1 is not applicable. However, its conclusion is true for any set B of asymptotic density zero.

Theorem 2.2. Let m ∈ ℕ and let B be an infinite sequence of positive integers of asymptotic density zero. Then there exists an infinite sequence of positive integers A such that every sum over some elements of A, at most m of which are equal, is not in B.

Proof. Once again, take the smallest positive integer ℓ such that b_{ℓ+1} − b_{ℓ} ⩾ 2, and put a_{1} := b_{ℓ} + 1. Then a_{1} ∉ B. Suppose we already have a finite set {a_{1} < a_{2} < ⋯ < a_{k}} such that all possible (m+1)^{k}−1 nonzero sums δ_{1}a_{1}+⋯+δ_{k}a_{k}, where δ_{1}, …, δ_{k} ∈ {0, 1, …, m}, do not belong to B. It suffices to prove that there exists an integer a_{k+1} greater than a_{k} such that, for every i ∈ {1, …, m}, the sum ia_{k+1} + δ_{k}a_{k} + ⋯ + δ_{1}a_{1}, where δ_{1}, …, δ_{k} ∈ {0, 1, …, m}, is not in B.

Suppose that B = {b_{1} < b_{2} < b_{3} < … }. For any h ∈ ℕ, the set {hb_{1} < hb_{2} < hb_{3} < … } will be denoted by hB. Put B_{i} := \frac{m!}{i}B for i = 1, 2, …, m. Since d(B_{i}) = 0 for each i = 1, …, m, we have d(B_{1}∪⋯∪B_{m}) = 0. Thus, for any v > m!(mS+1), where S := a_{1}+⋯+a_{k}, there is an integer u > m!a_{k} such that the interval [u, u + v] is free of the elements of the set B_{1} ∪ ⋯ ∪ B_{m}.

Put a_{k+1} := ⌊u/m!⌋ + 1. Clearly, a_{k+1} > a_{k}. Furthermore, for any i ∈ {1, …, m}, no element of B_{i} lies in [u, u + v]. Thus there is a nonnegative integer j = j(i) such that m!b_{j}/i < u and m!b_{j+1}/i > u+v. (Here, for convenience of notation, we assume that b_{0} = 0.) Hence ia_{k+1} > iu/m! > b_{j} and

ia_{k+1} + mS < ia_{k+1} + imS ⩽ i(u/m! + 1 + mS) < i(u + v)/m! < b_{j+1}.

In particular, these inequalities imply that, for each i ∈ {1, …, m}, the sum ia_{k+1} + δ_{k}a_{k} + ⋯ + δ_{1}a_{1}, where δ_{1}, …, δ_{k} ∈ {0, 1, …, m}, is between b_{j(i)} + 1 and b_{j(i)+1} − 1, hence it is not in B. This completes the proof of the theorem. □

Several examples illustrating Theorem 2 will be given in Section 5. In particular, for any ε > 0, there is a set B ⊂ ℕ with asymptotic density d(B) < ε such that for any infinite set A ⊆ ℕ some of its distinct elements sum to an element lying in B. On the other hand, there are sets B ⊆ ℕ with asymptotic density 1 for which there exists an infinite set A whose distinct elements do not sum to an element lying in B.

3 Infinite sets whose elements do not sum to a square

The second question concerning the ‘densiest’ sequence A for a fixed B seems to be much more subtle. It seems likely that this question is very difficult already for the above mentioned sequence of perfect squares {1, 4, 9, 16, 25, 36, … }. The example of Fermat numbers 2^{2^{n}} + 1, n = 1, 2, …, given above is clearly not satisfactory, because this sequence grows very rapidly.

In this sense, much better is the sequence 2^{2n−1}, n = 1, 2, …. The sum of its distinct elements

2^{2n_{1}−1} + ⋯ + 2^{2n_{l}−1} = 2^{2n_{1}−1}(1 + 4^{n_{2}−n_{1}} + ⋯ + 4^{n_{l}−n_{1}}),

where 1 ⩽ n_{1} < ⋯ < n_{l}, is not a perfect square, because it is divisible by 2^{2n_{1}−1}, but not divisible by 2^{2n_{1}}.

Smaller, but still of exponential growth, is the sequence 2 · 3^{n}, n = 0, 1, 2, …. No sum of its distinct elements is a perfect square, because

2(3^{n_{1}} + ⋯ + 3^{n_{l}}) = 2 · 3^{n_{1}}(1 + 3^{n_{2}−n_{1}} + ⋯ + 3^{n_{l}−n_{1}}) = h^{2}

implies that n_{1} is even, so 2(1 + 3^{n_{2}−n_{1}} + ⋯ + 3^{n_{l}−n_{1}}) must be a square too. However, this number is of the form 3k + 2 with integer k, so it is not a perfect square.

A natural way to generate an infinite sequence whose distinct elements do not sum to square is to start with c_{1} = 2. Then, for each n ∈ ℕ, take the smallest positive integer c_{n+1} such that no sum of the form c_{n+1} + δ_{n}c_{n} + ⋯ + δ_{1}c_{1}, where δ_{1}, …, δ_{n} ∈ {0, 1}, is a perfect square. Clearly, c_{2} = 3, c_{3} = 5. Then, as 6 + 3 = 3^{2}, 7 + 2 = 3^{2}, 8 + 5 + 3 = 4^{2}, 9 = 3^{2}, we obtain that c_{4} = 10, and so on. In the following table we give the first 18 elements of this sequence:

\begin{matrix}n & c_{n} & log c_{n} & n & c_{n} & log c_{n} \\ 1 & 2 & 0.6931 & 10 & 2030 & 7.6157 \\ 2 & 3 & 1.0986 & 11 & 3225 & 8.0786 \\ 3 & 5 & 1.6094 & 12 & 8295 & 9.0234 \\ 4 & 10 & 2.3025 & 13 & 15850 & 9.6709 \\ 5 & 27 & 3.2958 & 14 & 80642 & 11.2977 \\ 6 & 38 & 3.6375 & 15 & 378295 & 12.8434 \\ 7 & 120 & 4.7874 & 16 & 1049868 & 13.8641 \\ 8 & 258 & 5.5529 & 17 & 3031570 & 14.9245 \\ 9 & 907 & 6.8101 & 18 & 12565348 & 16.3464 \end{matrix}

Here, the values of log c_{n} are truncated at the fourth decimal place. At the first glance, they suggest that the limit lim inf_{n→∞} n^{−1} log c_{n} is positive. If so, then the sequence c_{n}, n = 1, 2, 3, …, is of exponential growth too. It seems that the sequence c_{n}, n = 1, 2, 3, …, i.e.,

2, 3, 5, 10, 27, 38, 120, 258, 907, 2030, 3225, 8295, 15850, 80642, 378295, 1049868, …

was not studied before. At least, it is not given in N.J.A. Sloane’s on-line encyclopedia of

integer sequences http://www.research.att.com/˜ njas/sequences/. We thus raise the

following problem.

• Determine whether lim inf_{n→∞} n^{−1} log c_{n} is zero or a positive number.

In the opposite direction, one can easily show that c_{n} < 4^{n} for each n ⩾ 1. Here is the proof of this inequality by induction (due to a referee). Suppose that c_{n} < 4^{n}. If c_{n+1} ⩽ c_{n} + 4^{n}, then c_{n+1} < 4^{n} + 4^{n} < 4^{n+1}. Otherwise, for each j = 1, 2, …, 4^{n}, there exists a set I = I_{j} ⊆ {1, 2, …, n} such that c_{n} + j + S(I) = s_{j}^{2}, where S(I) := ∑_{i∈I} c_{i} and s_{j} ∈ ℕ. There are 2^{n} different subsets I of {1, 2, …, n}, so the set {4^{n} − 2^{n}, …, 4^{n} − 1, 4^{n}} with 2^{n} + 1 elements contains some two indices j < j′ for which the corresponding subsets I (and so the values for S(I)) are equal. Subtracting c_{n} + j + S(I) = s_{j}^{2} from c_{n} + j′ + S(I) = s_{j′}^{2}, we deduce that j′ − j = (s_{j′} − s_{j})(s_{j′} + s_{j}). Since j′ − j ⩽ 2^{n}, we have s_{j′} + s_{j} ⩽ 2^{n}, i.e., s_{j′} ⩽ 2^{n} − 1. Hence

4^{n} − 2^{n} < j′ < c_{n} + j′ + S(I) = s_{j′}^{2} ⩽ (2^{n} − 1)^{2} = 4^{n} − 2^{n+1} + 1,

a contradiction.

Of course, c_{n} < 4^{n} implies that lim sup_{n→∞} n^{−1} log c_{n} < log 4. Our next theorem shows that, for any fixed positive ε, there is a sequence A = {a_{1} < a_{2} < a_{3} < … } whose distinct elements do not sum to a square and whose growth is small in the sense that lim sup_{n→∞} n^{−1} log a_{n} < ε.

Theorem 3.1. For any ε > 0 there is a positive constant K = K(ε) and an infinite sequence A = {a_{1} < a_{2} < a_{3} < … } ⊂ ℕ satisfying a_{n} < K(1 + ε)^{n} for each n ∈ ℕ such that the sum of any number of distinct elements of A is not a perfect square.

Proof. Fix a prime number p to be chosen later and consider the following infinite set

A := {gp^{2m} + p^{2m−1} : g ∈ {0, 1, …, p − 2}, m ∈ ℕ}.

Each element of A in base p can be written as \overline{g100 … 0} with 2m − 1 zeros, where the ‘digit’ g is allowed to be zero. So all the elements of A are distinct.

First, we will show that the sum of any distinct elements of A is not a perfect square. Assume that there exists a sum S which is a perfect square. Suppose that for every t = 1, 2, …, l the sum S contains s_{t} > 0 elements of the form gp^{2m_{t}} + p^{2m_{t}−1}, where g ∈ {0, 1, …, p − 2} and 1 ⩽ m_{1} < m_{2} < ⋯ < m_{l}. Clearly, s_{t} ⩽ p − 1. Let us write S in the form

S = s_{1}p^{2m_{1}−1} + h_{1}p^{2m_{1}} + s_{2}p^{2m_{2}−1} + h_{2}p^{2m_{2}} + ⋯ + s_{l}p^{2m_{l}−1} + h_{l}p^{2m_{l}}
= p^{2m_{1}−1}(s_{1} + h_{1}p + ⋯ + s_{l}p^{2m_{l}−2m_{1}} + h_{l}p^{2m_{l}−2m_{1}+1}) = p^{2m_{1}−1}(s_{1} + pH).

Now, since s_{1} ∈ {1, …, p − 1} and since H is an integer, we see that S is divisible by p^{2m_{1}−1}, but not by p^{2m_{1}}, so it is not a perfect square.

It remains to estimate the size of the nth element a_{n} of A. Write n in the form n = (p − 1)(m − 1) + r, where r ∈ {1, …, p − 2, p − 1} and m ⩾ 1 is an integer. Suppose that the elements of A are divided into consecutive equal blocks with p − 1 elements in each block. Then all the elements of the mth block are of the form \overline{g100 … 0} (with 2m − 1 zeros), where g = 0, 1, …, p − 2. Hence the nth element of A, where n = (p − 1)(m − 1) + r, is precisely the rth element of the mth block, i.e., a_{n} = a_{(p−1)(m−1)+r} = (r − 1)p^{2m} + p^{2m−1}. It follows that

a_{n} ⩽ (p − 2)p^{2m} + p^{2m−1} < p^{2m+1} = p^{2(n−r)/(p−1)+3} < p^{2n/(p−1)+3} = p^{3}e^{(2n log p)/(p−1)}.

Clearly, (2 log p)/(p − 1) → 0 as p → ∞. Thus, for any ε > 0, there exists a prime number p such that e^{(2 log p)/(p−1)} < 1+ε. Take the smallest such a prime p = p(ε). Setting K(ε) := p(ε)^{3}, we obtain that a_{n} < K(ε)(1 + ε)^{n} for each n ∈ ℕ. □

4 Infinite sets whose elements do not sum to a power

Observe that distinct elements of the sequence 2 · 6^{n}, n = 0, 1, 2, …, cannot sum to a perfect power. Indeed,

S = 2(6^{n_{1}} + ⋯ + 6^{n_{l}}) = 2^{n_{1}+1}3^{n_{1}}(1 + 6^{n_{2}−n_{1}} + ⋯ + 6^{n_{l}−n_{1}}),

where 0 ⩽ n_{1} < ⋯ < n_{l}, is not a perfect power, because n_{1} + 1 and n_{1} are exact powers of 2 and 3 in the prime decomposition of S. So if S > 1 were a kth power, where k is a prime number (which can be assumed without loss of generality), then both n_{1} + 1 and n_{1} must be divisible by k, a contradiction.

This example is already ‘better’ than the example a^{p_{1}p_{2}...p_{n}} + 1, n = n_{0}, n_{0} + 1, …, given in [2] not only because it is completely explicit, but also because the sequence 2 · 6^{n}, n = 0, 1, 2, …, grows slower.

As above, we can also consider the sequence 2, 3, 10, 18, …, starting with e_{1} = 2, whose each ‘next’ element e_{n+1} > e_{n}, where n ⩾ 1, is the smallest positive integer preserving the property that no sum of the form δ_{1}e_{1} + ⋯ + δ_{n}e_{n} + e_{n+1}, where δ_{1}, …, δ_{n} ∈ {0, 1}, is a perfect power. By an argument which is slightly more complicated than the one given for c_{n}, one can prove again that e_{n} < 4^{n} for n large enough.

However, our aim is to prove the existence of the sequence whose nth element is bounded from above by K(ε)(1 + ε)^{n} for n ∈ ℕ. For this, we shall generalize Theorem 2 as follows:

Theorem 4.1. Let U be the set of positive integers of the form q_{1}^{α_{1}} … q_{k}^{α_{k}}, where q_{1}, …, q_{k} are some fixed prime numbers and α_{1}, …, α_{k} run through all nonnegative integers. Then, for any ε > 0, there is a positive constant K = K(ε, U) and an infinite sequence A = {a_{1} < a_{2} < a_{3} < … } ⊂ ℕ satisfying a_{n} < K(1 + ε)^{n} for n ∈ ℕ such that the sum of any number of distinct elements of A is not equal to uv^{s} with positive integers u, v, s such that u ∈ U and s ⩾ 2.

In particular, Theorem 3 with U = {1} implies a more general version of Theorem 2 with ‘perfect square’ replaced by ‘perfect power’.

Proof. Fix two prime numbers p and q satisfying p < q < 2p. Here, the prime number p will be chosen later, whereas, by Bertrand’s postulate, the interval (p, 2p) always contains at least one prime number, so we can take q to be any of those primes. Consider the following infinite set

A := {gp^{m+1}q^{m} + p^{m}q^{m−1} : g ∈ {1, …, p − 1}, m ∈ ℕ}.

The inequality p^{m+2}q^{m+1} + p^{m+1}q^{m} > (p − 1)p^{m+1}q^{m} + p^{m}q^{m−1} implies that all the elements of A are distinct. Also, as above, by dividing the sequence A into consecutive equal blocks with p − 1 elements each, we find that

a_{n} = rp^{m+1}q^{m} + p^{m}q^{m−1}

for n = (p − 1)(m − 1) + r, where m ∈ ℕ and r ∈ {1, …, p − 2, p − 1}.

Assume that there exists a sum S of some distinct a_{n} which is of the form uv^{s}. Without loss of generality we may assume that s ⩾ 2 is a prime number. Suppose that for every t = 1, 2, …, l the sum S contains s_{t} > 0 elements of the form gp^{m_{t}+1}q^{m_{t}} + p^{m_{t}}q^{m_{t}−1}, where g ∈ {1, …, p − 1} and 1 ⩽ m_{1} < m_{2} < ⋯ < m_{l}. Clearly, s_{t} ⩽ p − 1, so, in particular, 1 ⩽ s_{1} ⩽ p − 1. Then, as above, S = p^{m_{1}}q^{m_{1}−1}(s_{1} + pqH) with an integer H. If q > p > q_{k}, then p, q ∉ U, so the equality uv^{s} = p^{m_{1}}q^{m_{1}−1}(s_{1} + pqH) implies that s|m_{1} and s|(m_{1} − 1), a contradiction.

Using a_{n} = rp^{m+1}q^{m} + p^{m}q^{m−1}, where n = (p − 1)(m − 1) + r and p < q < 2p, we find that

a_{n} < (p − 1)q^{2m+1} + q^{2m−1} < q^{2m+2} < (2p)^{2(n−r)/(p−1)+4} < (2p)^{4}e^{(2n log(2p))/(p−1)}.

For any ε > 0, there exists a positive number p_{ε} such that e^{(2 log(2p))/(p−1)} < 1 + ε for each p > p_{ε}. Take the smallest prime number p = p(ε) greater than max{p_{ε}, q_{k}}, and put K(ε, q_{k}) = K(ε, U) := 2p(ε)^{4}. Then a_{n} < K(ε, U)(1 + ε)^{n} for each n ∈ ℕ, as claimed. □

5 Concluding remarks

We do not give any lower bounds for the nth element a_{n} of the ‘densiest’ sequence A = {a_{1} < a_{2} < … } whose distinct elements do not sum to a square or, more generally, to a power. As a first step towards solution of this problem, it would be of interest to find out whether every infinite sequence of positive integers A which has a positive asymptotic density (i.e., d(A) > 0) contains some elements that sum to a square. It is essential that we can only sum distinct elements of A, because, for any nonempty set A ⊂ ℕ, there is a sumset A + A + ⋯ + A which contains a square. In this direction, we can mention the following result of T. Schoen [3]: if A is a set of positive integers with asymptotic density d(A) > 2/5 then the sumset A + A contains a perfect square. For more references on sumset related results see the recent book [5] of T. Tao and V. H. Vu.

A ‘finite version’ of the problem on the ‘densiest’ set whose elements do not sum to a square was recently considered by J. Cilleruelo [1]. He showed that there is an absolute positive constant c such that, for any positive integer N ⩾ 2, there exists a subset A of {1, 2, …, N} with ⩾ cN^{1/3} elements whose distinct elements do not sum to a perfect square. In fact, by taking the largest prime number p ⩽ N^{1/3}, we see that the set A := {p, p^{2} + p, 2p^{2} + p, …, (p − 2)p^{2} + p} with p − 1 element is a subset of {1, 2, …, N}. Since any sum of distinct elements of A is divisible by p, but not by p^{2}, we conclude that no sum of distinct elements of the set A of cardinality p − 1 ⩾ \frac{1}{2}N^{1/3} is a perfect power.

Notice that in this type of questions not everything is determined by the density of B. In fact, there are some ‘large’ sets B for which there is a ‘large’ set A whose elements do not sum to an integer lying in B. For example, for the set of all odd positive integers B = {1, 3, 5, 7, … } whose density d(B) is 1/2, the ‘densiest’ set A whose elements do not sum to an odd number is the set of all even positive integers {2, 4, 6, 8, … } with density d(A) = 1/2. On the other hand, taking B = {2, 4, 6, 8, … }, we see that no infinite sequence A as required exists. Moreover, if B is the set of all positive integers divisible by m, where m ∈ ℕ is large, then the density d(B) = 1/m is small. However, by a simple argument modulo m, it is easy to see that there is no infinite set A ⊂ ℕ (and even no set A with ⩾ m distinct positive integers) with the property that its distinct elements always sum to a number lying outside B. Indeed, if a_{1}, …, a_{m} ∈ ℕ then either at least two of the following m numbers S_{j} := ∑_{i=1}^{j} a_{i}, where j = 1, …, m, say, S_{u} and S_{v} (u < v, u, v ∈ {1, …, m}) are equal modulo m or m|S_{t}, where t ∈ {1, …, m}. Therefore, either their difference S_{v} − S_{u} = a_{u+1} + a_{u+2} + ⋯ + a_{v} or S_{t} = a_{1} + ⋯ + a_{t} is divisible by m. In both cases, there is a sum of distinct elements of {a_{1}, a_{2}, …, a_{m}} that lies in B.

It follows that if, for an infinite set B ⊂ ℕ, there exists an infinite sequence of positive integers A = {a_{1} < a_{2} < a_{3} < … } for which a_{i_{1}} + ⋯ + a_{i_{m}} ∉ B for every m ∈ ℕ and any distinct elements a_{i_{1}}, …, a_{i_{m}} ∈ A, then B must have the following property. For each m ∈ ℕ there are infinitely many k ∈ ℕ such that km ∉ B.

This necessary condition is not sufficient. Take, for instance, B := ℕ \ {j^{2} : j ∈ ℕ}. Then, for each m ∈ ℕ, there are infinitely many positive integers k, say, k = ℓ^{2}m, where ℓ = 1, 2, …, such that km = (ℓm)^{2} ∉ B. However, there does not exist an infinite set of positive integers A = {a_{1} < a_{2} < a_{3} < … } such that for any n ∈ ℕ and any distinct a_{i_{1}}, …, a_{i_{n}} ∈ A the sum a_{i_{1}} + ⋯ + a_{i_{n}} is a perfect square. See, e.g., the proposition in the same paper [2], where this was proved in a more general form with ‘perfect square’ replaced by ‘perfect power’.

Given any infinite set B ⊂ ℕ, put K := ℕ\B. Our first question stated in the introduction can be also formulated in the following equivalent form.

• For which K = {k_{1} < k_{2} < k_{3} < … } ⊂ ℕ there exists an infinite subsequence of {k_{i_{1}} < k_{i_{2}} < k_{i_{3}} < … } of K such that all possible sums over its distinct elements lie in K?

Theorem 2.1 implies that if d(K) = 1 then such a subsequence exists. On the other hand, take the sequence K of positive integers that are not divisible by m with asymptotic density d(K) = 1 − 1/m (which is ‘close’ to 1 if m is ‘large’). Then such a subsequence does not exist despite of d(K) being large. Finally, set D := {2^{2^{j}} : j ∈ ℕ} and suppose that K is the set of all possible finite sums over distinct elements of D. Then d(K) is easily seen to be 0, but for K such a subsequence exists, e.g., D.

6 Acknowledgments

We are most grateful to the referee of this paper, who not only carefully read the paper, but also made several useful suggestions and also supplied us with a few recent references. We thank A. Stankevičius, who computed the first 18 elements of the sequence c_{n}, n = 1, 2, …. This research was supported in part by the Lithuanian State Studies and Science Foundation.

References

[1] J. Cilleruelo, Solution of the Problem 38, Gaceta de la Real Sociedad Matematica Española 9 (2006), 455–460.

[2] F. Luca, Infinite sets of positive integers whose sums are free of powers, Rev. Colomb. Matem. 36 (2002), 67–70.

[3] T. Schoen, On sets of natural numbers whose sumset is free of squares, J. Comb. Theory, Ser. A 88 (1999), 385–388.

[4] O. Strauch and Š. Porubský, Distribution of Sequences: A Sampler, Schriftenreihe der Slowakischen Akademie der Wissenschaften, Peter Lang, 2005.

[5] T. Tao and V. H. Vu, Additive Combinatorics, CUP, 2006.

2000 Mathematics Subject Classification: Primary 11A99; Secondary 11B05, 11B99. Keywords: infinite sequence, perfect square, power, asymptotic density, sumset.

Received November 13 2006; revised version received December 4 2006. Published in Journal of Integer Sequences, December 4 2006.

Return to Journal of Integer Sequences home page.