a construction for sets of integers with distinct subset sums

Tom Bohman Department of Mathematics, 2-339 Massachusetts Institute of Technology 77 Massachusetts Ave. Cambridge, MA 02139 bohman@math.mit.edu

Submitted: September 9, 1997; Accepted: November 24, 1997.

Abstract

A set S of positive integers has distinct subset sums if there are 2^{|S|} distinct elements of the set {∑_{x∈X} x : X ⊂ S}. Let f(n) = min{max S : |S| = n and S has distinct subset sums}. Erdős conjectured f(n) ≥ c2^{n} for some constant c. We give a construction that yields f(n) < 0.22002 · 2^{n} for n sufficiently large. This now stands as the best known upper bound on f(n).

1 Introduction

A set S of positive integers has distinct subset sums if the set {∑_{x∈X} x : X ⊂ S} has 2^{|S|} distinct elements. Let

f(n) = min{max S : |S| = n and S has distinct subset sums}.

By taking the set S to be the first n powers of 2 we see that f(n) ≤ 2^{n−1}. Some small examples (the sets {3,5,6,7} and {6,9,11,12,13} for example) suggest that f(n) could be much smaller than 2^{n−1}. In 1931 Erdős conjectured that this is not the case [E1]. In particular, he conjectured that f(n) ≥ c2^{n} for some constant c, and he offered $500 for settling this conjecture [E1] [G1] [G2].

In 1955 Erdős and Moser proved that f(n) ≥ 2^{n}/(4\sqrt{n}) [E2] (for a proof using the second moment method see [AS, p47]). This remains, up to the constant, the best known lower bound (for an improvement in the constant see [Elk]).

The only improvements on the trivial upper bound on f(n) have been by construction. A method often used for proving upper bounds is to verify that some set of i integers (where i is relatively small) has distinct subset sums and gives f(i) < c2^{i}. This then gives the bound f(j) < c2^{j} for all j > i by the following observation: given a set S with distinct subset sums, n elements and largest element m we construct a set S′ with distinct subset sums, n + 1 elements and largest element 2m by doubling every element in S and introducing an odd number. The first upper bound on f(n) that was found using this method was given by the Conway–Guy sequence. This is a sequence of sets of integers that John Conway and Richard Guy constructed in 1967. They showed that the first 40 sets from this sequence have distinct subset sums. The 40^{th} set gives f(n) < .23513 · 2^{n} for n ≥ 40 [G1] [G2] [CG]. This stood as the best upper bound on f(n) until the mid 1980’s when Fred Lunnon conducted a computational investigation of this problem. Lunnon found four sequences of sets of integers that beat the Conway-Guy sequence. He verified that the first 67 sets from each of these sequences have distinct subset sums. The 67^{th} set from the best of these sequences gives f(n) < .22096 · 2^{n} for n ≥ 67 [L]. We should note that these aren’t the only known constructions for a set of n integers with distinct subset sums and largest element smaller than the trivial 2^{n−1}, but they are the constructions that give the best bounds on f(n) (for some other constructions see [L],[M] and [ANS]).

1991 Mathematics Subject Classification. Primary 11P99; Secondary 05D10.

In this paper we construct a family of sequences of sets of integers which contains all five of the sequences mentioned above. We go on to prove that all sets from each of the sequences have distinct subset sums. We should note that a proof that the sets from the Conway–Guy sequence have distinct subset sums as well as a brief account of the general construction that is studied in detail here are given in [B].

This paper is organized as follows. The remainder of this section is a brief discussion of the method introduced in [B] and used here to show that a set has distinct subset sums. Section 2 contains the construction. In Section 3 we prove that the sets constructed in Section 2 have distinct subset sums. Section 4 is an analysis of the best upper bound on f(n) that can be achieved with this new construction.

Let S = {a_{1} > a_{2} > ... > a_{n}} be an arbitrary set of positive integers (note that we take these in the opposite of their natural order). We will now outline a method for proving S has distinct subset sums. We begin by considering a condition which is equivalent to the distinct subset sums condition. Note that S fails to have distinct subset sums if and only if there are disjoint I, J ⊂ S with ∑ I = ∑ J (for a set of integers X we write ∑ X for ∑_{x∈X} x) . This is equivalent to a condition on the differences between the integers in our set. We form the difference vector of S : d_{S} = (a_{1} − a_{2}, a_{2} − a_{3}, ..., a_{n−1} − a_{n}, a_{n}). The condition on the differences is determined by changing the order of summation in the distinct sums condition on subsets of S. To state the condition precisely we need the following definition: an n–dimensional vector v with integer–valued components will be called smooth if

|v(1)| ≤ 1 and |v(i) − v(i + 1)| ≤ 1 for i = 1, ..., n − 1.

Lemma 1.1. Let S be a set of n positive integers. There exists I, J ⊂ S such that I ∩J = ∅ and ∑ I = ∑ J ⟺ there exists a nonzero, smooth, n–dimensional vector v such that v · d_{S} = 0 Proof. (⇒) Let I = {y_{1}, y_{2}, ..., y_{k}}, J = {z_{1}, z_{2}, ..., z_{l}}, and suppose ∑ I = ∑ J, i.e.

∑_{i=1}^{k} y_{i} − ∑_{i=1}^{l} z_{i} = 0.

For appropriate choices of α_{i} and β_{i}, we have:

y_{i} = ∑_{j=α_{i}}^{n} d_{S}(j) z_{i} = ∑_{j=β_{i}}^{n} d_{S}(j).

Notice that the α′_{i}s and β′_{i}s are all distinct. We can write:

∑_{i=1}^{k} ∑_{j=α_{i}}^{n} d_{S}(j) − ∑_{i=1}^{l} ∑_{j=β_{i}}^{n} d_{S}(j) = 0.

In order to reverse the order of summation we must count how many times each d_{S}(j) appears in this summation. This is achieved by setting:

v(j) = |{i : α_{i} ≤ j ≤ n}| − |{i : β_{i} ≤ j ≤ n}|.

Then v · d_{S} is the sum on the left hand side of the above equation, and v is smooth by the distinctness of the α′_{i}s and β′_{i}s. (⇐) Any smooth vector can be written as the sum of ±1 multiples of characteristic vectors of intervals that have right endpoints at n and distinct left endpoints. By reversing the above process, we can see how such a set of characteristic vectors gives us sets I and J.

So, to show that S has distinct subset sums we must show that v · d_{S} ≠ 0 for all nonzero smooth vectors v. Let v be a nonzero smooth vector. For the sets of integers we consider there is a natural way to construct a sequence w_{n}, w_{n−1}, ..., w_{2} of approximations of v that have the following two properties:

(i). w_{i} agrees with v in the n − i + 1 coordinates where d_{S} is greatest, and

(ii). w_{i} · d_{S} = 0.

We will show (this is the key to the proof) that

(iii). If w_{2} is nonzero then w_{2} is not smooth.

This implies v · d_{S} ≠ 0 because w_{2} agrees with v in exactly n − 1 coordinates and w_{2} · d_{S} = 0. In the proof that follows we refine this approach by eliminating special classes of v’s from consideration in the course of the argument.

Note that it is also the case that, for i = 3, …, n, if w_{i} is nonzero then w_{i} is not smooth. This fact is implied by (iii) (to see this, argue by contradiction taking v to be w_{i}). In many cases this fact also follows from the proof given below as the proof entails a detailed step by step analysis of w_{n}, …, w_{2}.

2 The construction

Let n, a parameter of our construction, be some integer greater than 1. We construct an infinite dimensional difference vector d_{n}. This gives a sequence of sets S_{n,2n}, S_{n,2n+1}, … (note that we start at a set with cardinality 2n) as follows:

S_{n,m} = {∑_{j=i}^{m} d_{n}(j) : i = 1, …, m} .

Clearly, the first m coordinates of d_{n} form the difference vector of S_{n,m}.

The vector d_{n} is defined differently on two different intervals of coordinates. We call these intervals of coordinates regions of definition. For 1 ≤ i ≤ 2n (the first region of definition) we set

d_{n}(i) = \{ \begin{matrix}1 & if i = n \\ 4^{j−1} & if i = n + j for 1 ≤ j ≤ n \\ 2(4^{j−1}) & if i = n − j for 1 ≤ j ≤ n − 1. \end{matrix}

For i greater than 2n (the second region of definition), d_{n}(i) is defined recursively; in particular,

d_{n}(i) = ∑_{j=i−b_{n}(i)}^{i−1} d_{n}(j) for i > 2n.

To finish the construction, we define the recursive rule sequence b_{n}:

b_{n}(i) = \{ \begin{matrix}n + 1 & if i = 2n + 1 or i = 2n + 2 \\ n + 2 & if i = 2n + 3 \\ [\sqrt{2(i + 2 − 2n)}] & for i ≥ 2n + 4 \end{matrix}

where [·] is the nearest integer function. Thus, for example, we have

d_{3} = (8, 2, 1, 1, 4, 16, 22, 43, 86, 151, 302, …), and
S_{3,6} = {32, 24, 22, 21, 20, 16} , …,
S_{3,9} = {183, 175, 173, 172, 171, 167, 151, 129, 86} , …

An important property of this construction is that for all i ≠ n there exists an interval I_{i} of coordinates such that I_{i} is adjacent to the i^{th} coordinate and

d_{n}(i) = ∑_{j∈I_{i}} d_{n}(j).  (1)

We can think of the n^{th} coordinate as the starting point where we set d_{n}(n) = 1. We can then think of the rest of d_{n} as being build up recursively using I_{n+i} = [n − i + 1, n + i − 1] and I_{n−i} = [n − i + 1, n + i] on the first region of definition and I_{i} = [i − b_{i}, i − 1] on the second region of definition. The fact that each d_{n}(i) can be written as such a sum is what facilitates the use of the proof technique outlined in the introduction.

Before going on we should also note an important property of the vector b_{n}. Clearly, the sequence b_{n}(2n + 4), b_{n}(2n + 5), … is an increasing sequence of positive integers. It happens that b_{n}(2n + 4) = 3 and for k ≥ 4 the integer k appears exactly k times in the sequence b_{n}(2n + 5), b_{n}(2n + 6), … (this is easily verified from the definition of b_{n}). An important consequence of this (which is crucial for the proof given in Section 3) is that

b_{n}(k) > b_{n}(k − b_{n}(k)) for k > 2n + 7.  (2)

We can now state the central result.

Theorem 2.1. If n and m are integers satisfying n ≥ 1 and m ≥ 2n then S_{n,m} has distinct subset sums.

There is also an alternate version of this construction. We begin with an integer n > 0 and construct an infinite dimensional difference vector d′_{n} in a fashion similar to what is given above. First, for 1 ≤ i ≤ 2n + 1 we set

d′_{n}(i) = \{ \begin{matrix}1 & if i = n + 1 \\ 4^{j−1} & if i = n + 1 − j for 1 ≤ j ≤ n \\ 2(4^{j−1}) & if i = n + 1 + j for 1 ≤ j ≤ n. \end{matrix}

Then we define our recursive rule vector b′_{n}:

b′_{n}(i) = \{ \begin{matrix}n + 1 & if i = 2n + 2 \\ n + 2 & if i = 2n + 3 or i = 2n + 4 \\ [\sqrt{2(i + 1 − 2n)}] & for i ≥ 2n + 5. \end{matrix}

Finally, using b′_{n}, we finish the construction of d′_{n}:

d′_{n}(i) = ∑_{j=i−b′_{n}(i)}^{i−1} d′_{n}(j) for i > 2n + 1.

For example, we have

d′_{3} = (16, 4, 1, 1, 2, 8, 32, 43, 86, 171, 200, 400, …).

And, once again, we get a sequence of sets that correspond to this difference vector by taking

S′_{n,m} = {∑_{j=i}^{m} d′_{n}(j) : i = 1, …, m} for m ≥ 2n + 1.

These sets will also have distinct subset sums.

Theorem 2.2. If n and m are positive integers such that m ≥ 2n + 1 then S′_{n,m} has distinct subset sums.

As we stated in the introduction this family of sequences (taking all sequences corresponding to either a d_{n} or a d′_{n} to be one family of sequences) contains the sequences given by Conway and Guy and Lunnon. In particular, d′_{1} is the difference vector corresponding to the Conway–Guy sequence (for more on the Conway–Guy sequence see [B] and [G1]), and d_{2}, d′_{2}, d_{3}, and d′_{3} are the difference vectors for the sequences discovered by Lunnon.

No proof of Theorem 2.2 will be given because the proof of Theorem 2.2 is extremely similar to the proof of Theorem 2.1 given below.

3 Proof of Theorem 2.1

For ease of notation let d = d_{n} and b = b_{n}. If v is an m–dimensional vector then we write v · d for the dot product of v with the first m coordinates of d. We prove Theorem 2.1 by (as provided by Lemma 1.1) showing that no smooth m–dimensional vector where m ≥ 2n dots with d to give zero. Preparatory to that discussion, we develop some lemmas concerning d.

Lemma 3.1. If v is a smooth (2n − 2)–dimensional vector with |v(2n − 2)| ≤ 1 then v · d < d(2n).

Proof. Since v is smooth, v(i) ≤ i. Since v(2n − 2) ≤ 1 and v is smooth, v(i) ≤ 2n − 1 − i. So, v(i) ≤ min{i, 2n − 1 − i}, and

v · d ≤ ∑_{i=1}^{2n−2} d(i) min{i, 2n − 1 − i} = ∑_{i=1}^{n−1} ∑_{j=i}^{2n−1−i} d(j) = ∑_{i=1}^{n−1} (d(i) + d(2n − i))

= ∑_{i=1}^{n−1} (2 · 4^{n−i−1} + 4^{n−i−1}) = ∑_{i=1}^{n−1} (4^{n−i} − 4^{n−i−1}) = 4^{n−1} − 4^{0} = d(2n) − 1.

Lemma 3.2. If i ≥ 2n − 2 then ∑_{j=1}^{i} d(j) < d(i + 2).

Proof. This follows from lemma 3.1 when i = 2n − 2. For larger i the proof follows by induction:

d(i + 2) = ∑_{j=i+2−b(i+2)}^{i+1} d(j) ≥ d(i) + d(i + 1) > d(i) + ∑_{j=1}^{i−1} d(j).

Lemma 3.3. If v is a smooth i–dimensional vector where i ≥ 2n − 2 and |v(i)| ≤ 1 then v · d < d(i + 2) + d(i + 3).

Proof. We go by induction. When i = 2n − 2 the result follows from lemma 3.1.

Suppose v is a smooth i–dimensional vector where i > 2n − 2 and |v(i)| ≤ 1. Let 1 be the i–dimensional all 1’s vector. Define the vector z by z(j) = max{v(j) − 1, 0} for 1 ≤ j ≤ i − 1. Then z is a smooth vector with |z(i − 1)| ≤ 1. Applying the inductive hypothesis to z and Lemma 3.2 to 1 · d yields

v · d = (v − 1) · d + 1 · d
≤ z · d + 1 · d
< (d(i + 1) + d(i + 2)) + d(i + 2)
≤ d(i + 3) + d(i + 2).

Before we start the proof we also need to establish some definitions. Let σ be the permutation of {1,2, …, 2n} defined by

σ(i) = \{ \begin{matrix}n + i/2 & if i is even \\ n − (i − 1)/2 & if i is odd. \end{matrix}

This is the permutation that orders the differences in the first region of definition (note that we need no such permutation in the second region of definition as the differences are in ascending order). In other words, σ is the permutation for which σ(1) = n and, for 2 ≤ i, j ≤ 2n, d(σ(i)) < d(σ(j)) ⟺ i < j.

We now define a set of vectors. These vectors are defined differently on the two regions of definition. For 2 ≤ i ≤ 2n let

x_{i}(j) = \{ \begin{matrix}1 & if σ(i) = j \\ −1 & if j = σ(l) for some l < i \\ 0 & otherwise, \end{matrix}

and for i > 2n let

x_{i}(j) = \{ \begin{matrix}1 & if i = j \\ −1 & if i − b(i) ≤ j ≤ i − 1 \\ 0 & otherwise. \end{matrix}

Note that x_{1} is not defined. Also note that, due to (1), x_{i} · d = 0 for i ∈ {2, …, m}.

We are now ready to begin the proof. Let v be a smooth nonzero vector of dimension m where m ≥ 2n. As outlined in the introduction, we construct a sequence, w_{m}, w_{m−1}, …, w_{2}, of approximations to v. Our goal is to show that these approximations satisfy

(i). w_{i} agrees with v in the m − i + 1 coordinates where d is greatest,

(ii). w_{i} · d = 0, and

(iii). If w_{2} is nonzero then w_{2} is not smooth.

To define the approximations, first set ρ_{m} = v(m) and w_{m} = ρ_{m}x_{m}. Once w_{i+1} is determined let

ρ_{i} = \{ \begin{matrix}v(i) − w_{i+1}(i) & if 2n + 1 ≤ i ≤ m − 1 \\ v(σ(i)) − w_{i+1}(σ(i)) & if 2 ≤ i ≤ 2n. \end{matrix}

and set w_{i} = w_{i+1} + ρ_{i}x_{i}. Since each w_{i} is a linear combination of the x_{i}’s, property (ii) holds. Property (i) is also immediate.

It remains to show that w_{2} is not smooth. Before doing this we establish two important properties of the sequence ρ_{m}, ρ_{m−1}, …, ρ_{2}. These properties follow from the smoothness of v, and we have one property for each region of definition of d.

Lemma 3.4. If ρ_{m} > 0 then ρ_{j} > 0 for max{2n, m − b(m)} ≤ j ≤ m − 1.

Proof. Suppose inductively that ρ_{j+1}, …, ρ_{m−1} > 0. Then, using j ≥ m − b(m)

w_{j+1}(j) = − ∑_{i=j+1}^{m} ρ_{i} ≤ −m + j.

Since ρ_{m} > 0, we have v(m) > 0. Since v is smooth, it follows from v(m) > 0 that v(j) ≥ 1 − m + j. Therefore, ρ_{j} = v(j) − w_{j+1}(j) ≥ 1 − m + j − (−m + j) = 1.

Lemma 3.5. For j = max{i ≤ 2n : ρ_{i} ≠ 0 },

ρ_{j}ρ_{j−2}, ρ_{j}ρ_{j−4}, … > 0 and ρ_{j}ρ_{j−1}, ρ_{j}ρ_{j−3}, … ≥ 0.

Proof. Without loss of generality, assume ρ_{j} > 0. Also assume σ(j) > n; the proof for σ(j) < n is nearly identical to what follows.

We consider inductively ρ_{j−i} for i = 1, …, j − 2. Of course, in order to prove the Lemma we must show

ρ_{j−i} ≥ 0 if i is odd, and
ρ_{j−i} > 0 if i is even.

(3)

We begin by showing ρ_{j−1} ≥ 0. Unfortunately, this must be done in two cases: j = 2n and j < 2n. If j = 2n then w_{2n}(σ(2n − 1)) = w_{2n}(1) = −ρ_{2n} ≤ −1. By the definition of a smooth vector we have v(1) ≥ −1. Hence v(1) ≥ w_{2n}(1), and ρ_{2n−1} ≥ 0. If j < 2n then v(σ(j + 1)) = w_{j}(σ(j + 1)) = 0. The smoothness of v between coordinates σ(j + 1) and σ(j + 1) + 1 = σ(j − 1) implies v(σ(i − 1)) ≥ −1. Since w_{j}(σ(j − 1)) = −ρ_{j} ≤ −1, it follows that ρ_{j−1} ≥ 0.

Now, suppose (3) holds for i = 1, …, k where k is odd. Let M = ρ_{2n+1} + ρ_{2n+2} + ρ_{2n+3} and L = ∑_{i=0}^{k−2} ρ_{j−i}. Now,

v(σ(j − k + 1)) = w_{j−k+1}(σ(j − k + 1)) = −M − L + ρ_{j−k+1}, and
w_{j−k}(σ(j − k − 1)) = −M − L − ρ_{j−k+1} − ρ_{j−k}.

Since v is smooth and σ(j − k + 1) − 1 = σ(j − k − 1),

v(σ(j − k − 1)) ≥ −M − L + ρ_{j−k+1} − 1.

Thus,

\begin{aligned}ρ_{j−k−1} & = v(σ(j − k − 1)) − w_{j−k}(σ(j − k − 1)) \\ & ≥ 2ρ_{j−k+1} + ρ_{j−k} − 1 \\ & ≥ 1. \end{aligned}  (4)

Simillarly,

v(σ(j − k)) = w_{j−k}(σ(j − k)) = −L − ρ_{j−k+1} + ρ_{j−k}, and
w_{j−k−1}(σ(j − k − 2)) = −L − ρ_{j−k+1} − ρ_{j−k} − ρ_{j−k−1}.

Since σ(j − k) + 1 = σ(j − k − 2) and v is smooth,

v(σ(j − k − 2)) ≥ −L − ρ_{j−k+1} + ρ_{j−k} − 1.

It then follows from (4) that

ρ_{j−k−2} = v(σ(j − k − 2)) − w_{j−k−1}(σ(j − k − 2))
≥ 2ρ_{j−k} + ρ_{j−k−1} − 1
≥ 0.

An important implication of Lemma 3.5–we will apply this in showing that w_{2} is not smooth–is

ρ_{2}ρ_{3} ≥ 0.  (5)

We now divide the argument into cases based on the dimension of v and the sequence of ρ_{i}’s. This argument is inductive; for all cases after Case 1 we are assuming that no smooth vector of smaller dimension dots with d to give zero (this assumption is only used in Case 4). Throughout these cases we assume without loss of generality that v(m) > 0 and hence ρ_{m} > 0.

CASE 1. m = 2n.

Since v is nonzero there exists j such that ρ_{j} ≠ 0. Lemma 3.5 then implies that either ρ_{2} ≠ 0 or ρ_{3} ≠ 0.

Suppose ρ_{2} ≠ 0. Let M = ∑_{i=3}^{2n} ρ_{i}. Then w_{2}(n) = −M − ρ_{2} while w_{2}(n + 1) = −M + ρ_{2}. Hence, w_{2} is not smooth.

Suppose ρ_{2} = 0 and hence ρ_{3} ≠ 0. Let M = ∑_{i=4}^{2n} ρ_{i}. Then w_{2}(n) = −M − ρ_{3} while w_{2}(n − 1) = −M + ρ_{3}. Hence, w_{2} is not smooth.

CASE 2. 2n + 1 ≤ m ≤ 2n + 3.

By Lemma 3.4, ρ_{j} > 0 for 2n ≤ j ≤ m − 1. Lemma 3.5 then implies that ρ_{2} > 0 and ρ_{3} ≥ 0. Let M = ∑_{i=4}^{2n} ρ_{i}. Then w_{2}(n − 1) = −M + ρ_{3} while w_{2}(n) = −M − ρ_{3} − ρ_{2} − ρ_{2n+1}. Therefore w_{2}(n − 1) − w_{2}(n) = 2ρ_{3} + ρ_{2} + ρ_{2n+1} ≥ 2, and w_{2} is not smooth.

CASE 3. m ≥ 2n + 4 and ρ_{2n+1}, ...ρ_{m−1} > 0.

Let M = ∑_{i=4}^{2n} ρ_{i}. Then w_{2}(n−1) = −M +ρ_{3}, w_{2}(n) = −M −ρ_{3} −ρ_{2} −ρ_{2n+1}, and w_{2}(n+1) = −M −ρ_{3} +ρ_{2} −ρ_{2n+1} −ρ_{2n+2} −ρ_{2n+3}. If ρ_{2} ≤ 0 then w_{2}(n)−w_{2}(n+1) = −2ρ_{2} + ρ_{2n+2} + ρ_{2n+3} ≥ 2 and w_{2} is not smooth. On the other hand, if ρ_{2} > 0 then (5) implies ρ_{3} ≥ 0. In this case w_{2}(n − 1) − w_{2}(n) = 2ρ_{3} + ρ_{2} + ρ_{2n+1} ≥ 2 and w_{2} is not smooth.

CASE 4. m ≥ 2n + 4 and ∃t ≥ 2n + 4 such that ρ_{t−1} ≤ 0 while ρ_{t}, ..., ρ_{m−1} > 0.

We begin by investigating the structure of w_{t}. By property (i) of w_{t}, we have w_{t}(i) = v(i) for i ≥ t. It is also clear from the definition of w_{t} that w_{t}(i) = 0 for i < t−b(t). So, the interesting part of w_{t} is in coordinates i where t−b(t) ≤ i ≤ t−1. Set c(k) = max{l : l − b(l) ≤ k}. Then for t − b(t) ≤ i ≤ t − 1 we have

w_{t}(i) = − ∑_{j=t}^{c(i)} ρ_{j}.

Since c(k) is strictly increasing, w_{t}(t − b(t)), ..., w_{t}(t − 2), w_{t}(t − 1) is a strictly decreasing sequence of negative numbers. We will show that

∃ t − b(t) − 1 ≤ s ≤ t − 2 such that c(s + 1) = c(s) + 2 and c(s + 1) ≥ t + 1,

whence w_{t}(s+1) ≤ w_{t}(s)−2 (i.e there is a ‘double jump in w_{t} between coordinates s and s+1). The existence of such an s comes from the rule by which we constructed b. Let y = c(t−1). Note that Lemma 3.4 implies y < m. Since y+1−b(y+1) > t−1 we have b(y+1) = b(y). Applying (2) we get b(t) = b(y+1−b(y+1)) < b(y+1) = b(y). It follows that there exists u with t ≤ u < y and b(u + 1) = b(u) + 1. Then s = u − b(u) − 1 has the desired properties.

Consider the vector z = v − w_{t}. Property (ii) of w_{t} implies

v · d = z · d.

Property (i) of w_{t} implies z(i) = 0 for i ≥ t. Since we’re assuming ρ_{t−1} ≤ 0, we have w_{t}(t − 1) ≥ v(t − 1). Since w_{t}(t − b(t) − 1), w_{t}(t − b(t)), ..., w_{t}(t − 2), w_{t}(t − 1) is strictly decreasing and v is smooth, we have w_{t}(i) ≥ v(i) for t − b(t) − 1 ≤ i ≤ t − 1. Furthermore, the existence of the double jump between w_{t}(s) and w_{t}(s + 1) implies that w_{t}(i) > v(i) for t − b(t) − 1 ≤ i ≤ s. Thus,

z(i) \{ \begin{matrix}= 0 & if i ≥ t \\ ≤ 0 & if s + 1 ≤ i ≤ t − 1 \\ < 0 & if t − b(t) − 1 ≤ i ≤ s, \end{matrix}  (6)

and

(z(1), z(2), …, z(t − b(t) − 1)) is a smooth vector.  (7)

We now consider cases.

Subcase 4.1. z(i) < 0 for i ≤ s.

Clearly, 0 > z · d = v · d.

For the remaining two cases let q = max{i < t − b(t) − 1 : z(i) = 0}. When we restrict z to its first q − 1 components (which are also the first q − 1 components of v) we get a smooth vector y with |y(q − 1)| ≤ 1.

Subcase 4.2. There exists r > q + 1 such that z(r) < 0.

Since t ≥ 2n + 4, t − b(t) − 1 ≥ 2n. So, if q < 2n then z(2n) < 0. In this case we apply Lemma 3.1 to y to get

0 > y · d − d(2n) ≥ z · d = v · d.

On the other hand, if q ≥ 2n we apply Lemma 3.3 to y to get

0 > y · d − d(q + 1) − d(q + 2) ≥ y · d − d(q + 1) − d(r) ≥ z · d = v · d.

Subcase 4.3. For all r > q + 1, z(r) = 0.

It follows from (6) that s = q + 1 = t − b(t) − 1. Furthermore, z(i) = 0 for i > t − b(t) − 1, and hence v · d = z · d = (z(1), …, z(t − b(t) − 1)) · d. However, by (7) and our inductive hypothesis, we have (z(1), …, z(t − b(t) − 1)) · d ≠ 0.

CASE 5. m ≥ 2n + 4 and ρ_{2n+3}, ..., ρ_{m−1} > 0, but either ρ_{2n+1} ≤ 0 or ρ_{2n+2} ≤ 0.

Suppose ρ_{2n+2} ≤ 0. Note that, by Lemma 3.4, this implies m ≥ 2n + 7. We begin with a description of w_{2n+3}. Clearly,

w_{2n+3}(i) = \{ \begin{matrix}−ρ_{2n+3} − ρ_{2n+4} − ρ_{2n+5} − ρ_{2n+6} & if i = 2n + 2 \\ −ρ_{2n+3} − ρ_{2n+4} − ρ_{2n+5} & if i = 2n + 1 \\ −ρ_{2n+3} & if n + 1 ≤ i ≤ 2n \\ 0 & if 1 ≤ i ≤ n. \end{matrix}

Since ρ_{2n+2} ≤ 0 and v is smooth we have

v(i) ≤ \{ \begin{matrix}w_{2n+3}(i) & if i = 2n + 1, 2n + 2 \\ min\{i, 2n − 1 − ρ_{2n+3} − i\} & if 1 ≤ i ≤ 2n. \end{matrix}

So, for z := v − w_{2n+3},

z(i) ≤ y(i) := \{ \begin{matrix}0 & if i = 2n + 1, 2n + 2 \\ min\{i, 2n − 1 − i\} & if 1 ≤ i ≤ 2n. \end{matrix}

Note that the restriction of z to its first 2n coordinates is not necessarily smooth as w_{2n+3}(n + 1) = −ρ_{2n+3} while w_{2n+3}(n) = 0. However, the restriction y to its first 2n coordinates is smooth, and, therefore, it follows from Lemma 3.1 that y · d < 0. It then follows from properties (i) and (ii) of w_{2n+3} that v · d = z · d ≤ y · d < 0.

The proof is similar if ρ_{2n+2} > 0 and ρ_{2n+1} ≤ 0.

4 Calculating the new upper bound

Our first step is to construct the sequence of greatest elements of the given sequence of sets of integers. Let v_{n}(k) = max S_{2n,k}. A direct calculation yields:

v_{n}(2n) = (1/2)2^{2n},
v_{n}(2n + 1) = 2/3 + (5/12)2^{2n+1},
v_{n}(2n + 2) = 1 + (3/8)2^{2n+2},
v_{n}(2n + 3) = 5/3 + (17/48)2^{2n+3} and
v_{n}(k + 1) = 2v_{n}(k) − v_{n}(k − b_{n}(k + 1)) for k ≥ 2n + 3.

Let r_{n}(k) = v_{n}(k)/2^{k}. Our goal is too find the minimum over k of r_{n}(k). The values of v_{n} listed above imply

r_{n}(2n) = 1/2,
r_{n}(2n + 1) = 5/12 + (1/3)2^{−2n},
r_{n}(2n + 2) = 3/8 + 2^{−2n−2},
r_{n}(2n + 3) = 17/48 + (5/3)2^{−2n−3} and
r_{n}(k + 1) = r_{n}(k) − r_{n}(k − b_{n}(k + 1))/2^{1+b_{n}(k+1)} for k ≥ 2n + 3.

Since v_{n}(k) and hence r_{n}(k) is positive, the sequence {r_{n}(k)}_{k=2n}^{∞} is decreasing. In order to find the best upper bound on f(n) that can be obtained from the difference vector d_{n} we must calculate the limit as k tends to infinity of r_{n}(k).

We will not calculate this limit directly for all n. As it happens that this limit decreases as n increases, we consider the limit of these sequences. In particular, consider the sequence

r(3) = 1/2,
r(4) = 5/12,
r(5) = 3/8,
r(6) = 17/48 and
r(k + 1) = r(k) − r(k − b(k + 1))/2^{1+b(k+1)} for k ≥ 6.

where b is defined by b(i) = [\sqrt{2(i − 1)}] (which is also known as b′_{1}, the recursive rule for the Conway–Guy sequence).

Claim 4.1. r(3 + k) ≤ r_{n}(2n + k) ≤ r(3 + k) + (1/3)2^{−2n} for k ≥ 0.

Proof. Let e be the vector defined by e(k) = r_{n}(2n + k) − r(3 + k). For k ≥ 6 we have

e(k + 1) = e(k) − e(k − b(k + 1))/2^{1+b(k+1)}.

The claim follows immediately from

e(k + 1) > e(k)/2 for k ≥ 0,  (8)

as (8) implies e(k) ≥ 0 for k ≥ 0. It is easy to see that (8) holds for k = 0, 1, 2. For k ≥ 3 we proceed by induction:

e(k + 1) = e(k) − \frac{e(k − b(k + 1))}{2^{1+b(k+1)}}

> e(k) − \frac{e(k) · 2^{b(k+1)}}{2^{1+b(k+1)}}

= e(k)/2.

(9)

It follows from Claim 4.1 that, for L := lim_{k→∞} r(k), the limit as k goes to infinity of r_{n}(k) is between L and L + (1/3)2^{−2n}. An investigation of the sets generated by d′_{n} reveals a similar convergence in their sequences of ratios to r. So, L is the best upper bound on f(n) that is achieved with either of these constructions. The rest of this section consists of the calculation of L.

We follow the argument given in [G1] to determine the asymptotic upper bound on f(n) given by the Conway–Guy sequence. Let p_{j} = j(j − 1)/2 + 1; that is, p_{j} is taken to be the last index for which b equals j − 1. We use r(p_{j}) for some sufficiently large j as an approximation of L. We now calculate the difference between this estimate and subsequent terms in the sequence. By the definition of r we have r(p_{j} + 1) = r(p_{j}) − 2^{−j−1}r(p_{j} − j). Iterating this observation we have

r(p_{j+1}) = r(p_{j}) − ∑_{i=p_{j}}^{p_{j+1}−1} 2^{−j−1}r(i − j).

But, this also can be iterated to give

r(p_{j+m}) = r(p_{j}) − ∑_{k=0}^{m−1} 2^{−j−k−1} ∑_{i=p_{j+k}}^{p_{j+k+1}−1} r(i − j − k).

Since r is decreasing the terms in the inner summation are bounded between (if j is sufficiently large) 3/8 and L. So, we can conclude that

r(p_{j}) − 3/8 ∑_{k=0}^{m−1} 2^{−j−k−1}(j + k) < r(p_{j+m}) < r(p_{j}) − L ∑_{k=0}^{m−1} 2^{−j−k−1}(j + k).

A simple calculations shows that ∑_{k=0}^{m−1} 2^{−j−k−1}(j +k) = (j +1)/2^{j} −(j +m+1)/2^{j+m}. If we let m tend to infinity the second term disappears and we get

r(p_{j}) − \frac{3(j + 1)}{(8)2^{j}} < L < r(p_{j}) − \frac{L(j + 1)}{2^{j}}.  (10)

A simple computer calculation gives the approximation .2200188 < r(p_{25}) < .2200189. So, we can use the inequality on the left to get .2200185 < L. Plugging this back into the inequality on the right gives L < .2200188. So, we can make an approximation of L ≈ .22001865 with an error of less than 1.5 · 10^{−7}. Inequality (10) can certainly be used to obtain more precise approximations of L.

References

[AS] N. Alon and J. Spencer, The Probabilistic Method, Wiley, 1992.

[ANS] M.D. Atkinson, A. Negro and N. Santoro, Sums of Lexicographically Ordered Sets. Discrete Math 80(1990) 115–122.

[B] T. Bohman, The Conway–Guy sequence and a sum packing problem of Erdős, Proceedings Amer. Math. Soc., 124(1996) 3627–3636.

[CG] J.H. Conway and R.K. Guy, Sets of natural numbers with distinct subset sums, Notices Amer. Math. Soc., 15(1968) 345.

[Elk] N. Elkies, An improved lower bound on the greatest element of a sum–distinct set of fixed order, J. Comb. Th. A, 41(1986) 89-94.

[E1] P. Erdős, Personal communication.

[E2] P. Erdős, Problems and results from additive number theory, Colloq. Théorie des nombres, Bruxells(1955) 127-137.

[G1] R.K. Guy, Sets of integers whose subsets have distinct sums, Ann. Discrete Math., 12(1982) 141-154.

[G2] R.K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1981.

[L] W.F. Lunnon, Integer sets with distinct subset sums, Math. Compute, 50(1988) 297-320.

[M] R. Maltby, Bigger and Better Subset–Sums–Distinct Sets, Mathematika, to appear.