%A LaTeX file for a 14 page document (using the AMSLaTeX package) \documentclass[12pt]{article} %\pagestyle{empty} \topmargin -.4in \textheight 9in \textwidth 6in \oddsidemargin .25 in \usepackage{amsmath,amsthm} \newtheorem{lemma}{Lemma}[section] \newtheorem{claim}{Claim}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{case}{CASE} \newtheorem{subcase}{Subcase}[case] \begin{document} \title{\sc a construction for sets of integers with distinct subset sums} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \author{Tom Bohman \\ Department of Mathematics, 2-339\\ Massachusetts Institute of Technology\\ 77 Massachusetts Ave.\\ Cambridge, MA 02139\\ {\texttt bohman@math.mit.edu}} \date{Submitted: September 9, 1997; Accepted: November 24, 1997.} \maketitle \begin{abstract} A set \(S\) of positive integers has {\em distinct subset sums} if there are \(2^{|S|}\) distinct elements of the set \( \left\{ \sum_{x \in X} x: X \subset S \right\} \). Let \(f(n) = \min\{ \max S: |S|=n {\rm \hskip2mm and \hskip2mm} S {\rm \hskip2mm has \hskip2mm distinct \hskip2mm subset \hskip2mm sums}\}\). Erd\H{o}s conjectured \( f(n) \ge c2^{n}\) for some constant \(c\). We give a construction that yields \(f(n) < 0.22002 \cdot 2^{n}\) for \(n\) sufficiently large. This now stands as the best known upper bound on \( f(n)\). \end{abstract} \section{Introduction} \pagestyle{myheadings} \markright{{\sc the electronic journal of combinatorics 5(1998), \#R3 \hfill}} \thispagestyle{empty} \footnotetext{1991 {\em Mathematics Subject Classification}. Primary 11P99; Secondary 05D10.} A set \(S\) of positive integers has distinct subset sums if the set \( \left\{ \sum_{x\in X} x : X \subset S \right\} \) has \(2^{|S|}\) distinct elements. Let \[ f(n) = \min\{ \max S: |S|=n {\rm \hskip2mm and \hskip2mm} S {\rm \hskip2mm has \hskip2mm distinct \hskip2mm subset \hskip2mm sums}\}. \] By taking the set \(S\) to be the first \(n\) powers of 2 we see that \( f(n) \le 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\H{o}s conjectured that this is not the case \cite{erdos1}. In particular, he conjectured that \( f(n) \ge c2^{n} \) for some constant \(c\), and he offered \$500 for settling this conjecture \cite{erdos1} \cite{guy} \cite{guybook}. In 1955 Erd\H{o}s and Moser proved that \( f(n) \ge 2^{n}/ (4 \sqrt n) \) \cite{erdos2} (for a proof using the second moment method see \cite[p47]{alonspen}). This remains, up to the constant, the best known lower bound (for an improvement in the constant see \cite{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) < c 2^{i} \). This then gives the bound \( f(j) < c 2^{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^{\rm th}\) set gives \( f(n) < .23513 \cdot 2^{n} \) for \(n \ge 40\) \cite{guy} \cite{guybook} \cite{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^{\rm th}\) set from the best of these sequences gives \( f(n) < .22096 \cdot 2^{n} \) for \(n \ge 67 \) \cite{lunnon}. 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 \cite{lunnon},\cite{maltby} and \cite{ans}). 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 \cite{bohman}. This paper is organized as follows. The remainder of this section is a brief discussion of the method introduced in \cite{bohman} 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 = \left\{ a_{1} > a_{2} > ... > a_{n} \right\} \) 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 \subset S\) with \( \sum I = \sum J\) (for a set of integers \(X\) we write \( \sum X\) for \( \sum_{x\in X} x\)) . This is equivalent to a condition on the differences between the integers in our set. We form the difference vector of \(S: {\mathbf 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 \({\mathbf v}\) with integer--valued components will be called {\em smooth} if \[ \left| {\mathbf v}(1) \right| \le 1 \text{ and } \left| {\mathbf v}(i)-{\mathbf v}(i+1) \right| \le 1 \text{ for } i=1,...,n-1. \] \begin{lemma} Let S be a set of n positive integers. There exists \( I,J \subset S \) such that \( I \cap J = \emptyset\) and \( \sum I = \sum J \iff\) there exists a nonzero, smooth, n--dimensional vector \( {\mathbf v} \) such that \( {\mathbf v} \cdot {\mathbf d}_{S}=0 \) \end{lemma} \begin{proof} $(\Rightarrow)$ Let \( I=\{y_{1}, y_{2}, ..., y_{k}\}, J =\{z_{1}, z_{2}, ..., z_{l}\}\), and suppose \( \sum I = \sum J \), i.e. \[ \sum_{i=1}^{k} y_{i} - \sum_{i=1}^{l} z_{i} =0. \] For appropriate choices of \( \alpha_{i} \) and \( \beta_{i} \), we have: \[ y_{i}= \sum_{j=\alpha_{i}}^{n} {\mathbf d}_{S}(j) \hskip1cm z_{i}= \sum_{j=\beta_{i}}^{n} {\mathbf d}_{S}(j). \] Notice that the \( \alpha_{i}'s \) and \( \beta_{i}'s \) are all distinct. We can write: \[ \sum_{i=1}^{k} \sum_{j=\alpha_{i}}^{n} {\mathbf d}_{S}(j) - \sum_{i=1}^{l} \sum_{j=\beta_{i}}^{n} {\mathbf d}_{S}(j) =0. \] In order to reverse the order of summation we must count how many times each \({\mathbf d}_{S}(j) \) appears in this summation. This is achieved by setting: \[ {\mathbf v}(j) = |\{i: \alpha_{i} \le j \le n\}| - |\{i: \beta_{i} \le j \le n \}|. \] Then \( {\mathbf v} \cdot {\mathbf d}_{S} \) is the sum on the left hand side of the above equation, and \({\mathbf v}\) is smooth by the distinctness of the \( \alpha_{i}'s \) and \( \beta_{i}'s \).\\ $(\Leftarrow)$ Any smooth vector can be written as the sum of \( \pm 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\). \end{proof} So, to show that \(S\) has distinct subset sums we must show that \( {\mathbf v} \cdot {\mathbf d}_{S} \neq 0 \) for all nonzero smooth vectors \( {\mathbf v} \). Let \( {\mathbf v} \) be a nonzero smooth vector. For the sets of integers we consider there is a natural way to construct a sequence \( {\mathbf w}_{n}, {\mathbf w}_{n-1}, ... , {\mathbf w}_{2} \) of approximations of \( {\mathbf v} \) that have the following two properties: \begin{enumerate} \renewcommand{\theenumi}{(\roman{enumi})} \item \( {\mathbf w}_{i} \) agrees with \({\mathbf v}\) in the \(n-i+1\) coordinates where \( {\mathbf d}_{S} \) is greatest, and \item $ {\mathbf w}_{i} \cdot {\mathbf d}_{S} = 0 $. \end{enumerate} We will show (this is the key to the proof) that \begin{enumerate} \renewcommand{\theenumi}{(\roman{enumi})} \setcounter{enumi}{2} \item If \({\mathbf w}_{2}\) is nonzero then \({\mathbf w}_{2}\) is not smooth. \end{enumerate} \noindent This implies \( {\mathbf v} \cdot {\mathbf d}_{S} \neq 0 \) because \({\mathbf w}_{2}\) agrees with \({\mathbf v}\) in exactly \(n-1\) coordinates and \( {\mathbf w}_{2} \cdot {\mathbf d}_{S} = 0 \). In the proof that follows we refine this approach by eliminating special classes of \({\mathbf v}\)'s from consideration in the course of the argument. Note that it is also the case that, for \( i=3, \dots, n\), if \( {\mathbf w}_i \) is nonzero then \( {\mathbf w}_i \) is not smooth. This fact is implied by (iii) (to see this, argue by contradiction taking \({\mathbf v}\) to be \({\mathbf 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 \({\mathbf w}_n, \dots, {\mathbf w}_2 \). \section{The construction} Let \(n\), a parameter of our construction, be some integer greater than 1. We construct an infinite dimensional difference vector \( {\mathbf d}_{n} \). This gives a sequence of sets \( S_{n,2n}, S_{n,2n+1}, \ldots \) (note that we start at a set with cardinality \(2n\)) as follows: \[ S_{n,m} = \left\{ \sum_{j=i}^{m} {\mathbf d}_{n}(j) : i =1, \ldots, m \right\}. \] Clearly, the first \(m\) coordinates of \( {\mathbf d}_{n} \) form the difference vector of \( S_{n,m} \). The vector \( {\mathbf d}_{n} \) is defined differently on two different intervals of coordinates. We call these intervals of coordinates {\em regions of definition}. For \( 1 \le i \le 2n \) (the first region of definition) we set \[ {\mathbf d}_{n}(i)= \left\{ \begin{array}{rl} 1 & \mbox{if $i=n$} \\ 4^{j-1} & \mbox{if $ i=n+j$ for $ 1 \le j \le n $ } \\ 2(4^{j-1}) & \mbox{if $ i=n-j$ for $1 \le j \le n-1$.} \end{array} \right. \]\\ For \(i\) greater than \(2n\) (the second region of definition), \({\mathbf d}_{n}(i)\) is defined recursively; in particular, \[ {\mathbf d}_{n}(i) = \sum_{j=i-{\mathbf b}_{n}(i)}^{i-1} {\mathbf d}_{n}(j) \hskip3mm {\rm for} \hskip3mm i>2n.\] To finish the construction, we define the recursive rule sequence \( {\mathbf b}_{n} \): \[ {\mathbf b}_{n}(i) = \left\{ \begin{array}{ll} n+1 & \mbox{if \(i =2n+1\) or \(i=2n+2\)} \\ n+2 & \mbox{if \(i =2n+3\)} \\ \left[ \sqrt{2(i+2-2n)} \right] & \mbox{for \( i \ge 2n+4\)} \end{array} \right. \] where \( [\cdot] \) is the nearest integer function. Thus, for example, we have \begin{gather*} {\mathbf d}_{3} = ( 8, 2, 1, 1, 4, 16, 22, 43, 86, 151, 302, \ldots ), \text{ and} \\[3mm] S_{3,6} = \left\{ 32, 24, 22, 21, 20, 16 \right\},\dots, \\ S_{3,9} = \left\{ 183, 175, 173, 172, 171, 167, 151, 129, 86 \right\}, \ldots \end{gather*} An important property of this construction is that for all \(i \neq n\) there exists an interval \(I_{i}\) of coordinates such that \(I_{i}\) is adjacent to the \(i^{\rm th}\) coordinate and \begin{equation} {\mathbf d}_{n}(i) = \sum_{j\in I_{i}} {\mathbf d}_{n}(j). \label{eq:inter} \end{equation} We can think of the \(n^{\rm th}\) coordinate as the starting point where we set \( {\mathbf d}_{n}(n)=1 \). We can then think of the rest of \( {\mathbf 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-{\mathbf b}_{i},i-1]\) on the second region of definition. The fact that each \( {\mathbf 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 \( {\mathbf b}_{n} \). Clearly, the sequence \( {\mathbf b}_{n}(2n+4), {\mathbf b}_{n}(2n+5) , \ldots \) is an increasing sequence of positive integers. It happens that \( {\mathbf b}_{n}(2n+4) = 3\) and for \(k \ge 4\) the integer \(k\) appears exactly \(k\) times in the sequence \( {\mathbf b}_{n}(2n+5), {\mathbf b}_{n}(2n+6), \ldots \) (this is easily verified from the definition of \({\mathbf b}_{n}\)). An important consequence of this (which is crucial for the proof given in Section~3) is that \begin{equation} {\mathbf b}_{n}(k) > {\mathbf b}_{n}(k-{\mathbf b}_{n}(k)) \hskip3mm {\rm for} \hskip3mm k > 2n+7. \label{eq:central} \end{equation} We can now state the central result. \begin{theorem} If \(n\) and \(m\) are integers satisfying \(n \ge 1\) and \( m \ge 2n \) then \( S_{n,m} \) has distinct subset sums. \end{theorem} There is also an alternate version of this construction. We begin with an integer \(n>0\) and construct an infinite dimensional difference vector \( {\mathbf d}_{n}' \) in a fashion similar to what is given above. First, for \( 1 \le i \le 2n+1 \) we set \[ {\mathbf d}_{n}'(i)= \left\{ \begin{array}{ll} 1 & \mbox{if $i=n+1$} \\ 4^{j-1} & \mbox{if $ i=n+1-j$ for $ 1 \le j \le n $ } \\ 2(4^{j-1}) & \mbox{if $ i=n+1+j$ for $1 \le j \le n$.} \end{array} \right. \] Then we define our recursive rule vector \( {\mathbf b}_{n}' \): \[ {\mathbf b}_{n}'(i) = \left\{ \begin{array}{ll} n+1 & \mbox{if \(i =2n+2\)} \\ n+2 & \mbox{if \(i =2n+3\) or \(i=2n+4\)} \\ \left[ \sqrt{2(i+1-2n)} \right] & \mbox{for \( i \ge 2n+5\).} \end{array} \right. \] Finally, using \( {\mathbf b}_{n}'\), we finish the construction of \( {\mathbf d}_{n}' \): \[ {\mathbf d}_{n}'(i) = \sum_{j=i-{\mathbf b}_{n}'(i)}^{i-1} {\mathbf d}_{n}'(j) \hskip3mm {\rm for} \hskip3mm i>2n+1. \] For example, we have \[ {\mathbf d}_{3}' = ( 16, 4, 1, 1, 2, 8, 32, 43, 86, 171, 200, 400, \ldots ). \] And, once again, we get a sequence of sets that correspond to this difference vector by taking \[ S_{n,m}' = \left\{ \sum_{j=i}^{m} {\mathbf d}_{n}'(j) : i =1, \ldots, m \right\} \text{ for } m \ge 2n+1. \] These sets will also have distinct subset sums. \begin{theorem} If n and m are positive integers such that \( m \ge 2n+1 \) then \( S_{n,m}' \) has distinct subset sums. \end{theorem} As we stated in the introduction this family of sequences (taking all sequences corresponding to either a \({\mathbf d}_{n}\) or a \( {\mathbf d}_{n}' \) to be one family of sequences) contains the sequences given by Conway and Guy and Lunnon. In particular, \( {\mathbf d}_{1}'\) is the difference vector corresponding to the Conway--Guy sequence (for more on the Conway--Guy sequence see \cite{bohman} and \cite{guy}), and \( {\mathbf d}_{2}\), \( {\mathbf d}_{2}'\), \( {\mathbf d}_{3}\), and \( {\mathbf 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 {\em extremely} similar to the proof of Theorem 2.1 given below. \section{Proof of Theorem 2.1} For ease of notation let \( {\mathbf d} = {\mathbf d}_{n} \) and \( {\mathbf b} = {\mathbf b}_{n} \). If \({\mathbf v}\) is an \(m\)--dimensional vector then we write \({\mathbf v} \cdot {\mathbf d}\) for the dot product of \({\mathbf v}\) with the first \(m\) coordinates of \({\mathbf d}\). We prove Theorem 2.1 by (as provided by Lemma 1.1) showing that no smooth \(m\)--dimensional vector where \(m \ge 2n\) dots with \({\mathbf d}\) to give zero. Preparatory to that discussion, we develop some lemmas concerning \({\mathbf d}\). \begin{lemma} If \({\mathbf v}\) is a smooth (\( 2n-2 \))--dimensional vector with \( |{\mathbf v}(2n-2)| \le 1 \) then \( {\mathbf v} \cdot {\mathbf d} < {\mathbf d}(2n) \). \end{lemma} \begin{proof} Since \({\mathbf v}\) is smooth, \( {\mathbf v}(i) \le i\). Since \( {\mathbf v}(2n-2) \le 1\) and \({\mathbf v}\) is smooth, \( {\mathbf v}(i) \le 2n-1-i\). So, \( {\mathbf v}(i) \le \min \{ i, 2n-1-i \} \), and \[ {\mathbf v} \cdot {\mathbf d} \le \sum_{i=1}^{2n-2} {\mathbf d}(i) \min \{ i, 2n-1-i \} = \sum_{i=1}^{n-1} \sum_{j=i}^{2n-1-i} {\mathbf d}(j) = \sum_{i=1}^{n-1} \left( {\mathbf d}(i) + {\mathbf d}(2n-i) \right)\] \[ = \sum_{i=1}^{n-1} \left( 2 \cdot 4^{n-i-1} + 4^{n-i-1} \right) = \sum_{i=1}^{n-1} \left( 4^{n-i} - 4^{n-i-1} \right) = 4^{n-1} - 4^{0} = {\mathbf d}(2n) - 1.\] \end{proof} \begin{lemma} If \(i \ge 2n-2\) then \( \sum_{j=1}^{i}{\mathbf d}(j) < {\mathbf d}(i+2)\). \end{lemma} \begin{proof} This follows from lemma 3.1 when \(i=2n-2\). For larger \(i\) the proof follows by induction: \[ {\mathbf d}(i+2) = \sum_{j=i+2-{\mathbf b}(i+2)}^{i+1} {\mathbf d}(j) \ge {\mathbf d}(i) + {\mathbf d}(i+1) >{\mathbf d}(i) + \sum_{j=1}^{i-1} {\mathbf d}(j). \] \end{proof} \begin{lemma} If \({\mathbf v}\) is a smooth \(i\)--dimensional vector where \( i \ge 2n-2 \) and \( |{\mathbf v}(i)| \le 1 \) then \( {\mathbf v} \cdot {\mathbf d} < {\mathbf d}(i+2) + {\mathbf d}(i+3) \). \end{lemma} \begin{proof} We go by induction. When \(i=2n-2\) the result follows from lemma 3.1. Suppose \({\mathbf v}\) is a smooth \(i\)--dimensional vector where \( i > 2n-2 \) and \( |{\mathbf v}(i)| \le 1 \). Let \({\mathbf 1}\) be the \(i\)--dimensional all 1's vector. Define the vector \({\mathbf z}\) by \( {\mathbf z}(j) = \max\{{\mathbf v}(j)-1, 0\} \) for \( 1 \le j \le i-1 \). Then \({\mathbf z}\) is a smooth vector with \( | {\mathbf z}(i-1)| \le 1\). Applying the inductive hypothesis to \( {\mathbf z} \) and Lemma~3.2 to \( {\mathbf 1} \cdot {\mathbf d} \) yields \[ \begin{array}{ll} {\mathbf v} \cdot {\mathbf d} & = ({\mathbf v} -{\mathbf 1}) \cdot {\mathbf d} + {\mathbf 1} \cdot {\mathbf d} \\ & \le {\mathbf z} \cdot {\mathbf d} + {\mathbf 1} \cdot {\mathbf d} \\ & < ( {\mathbf d}(i+1) + {\mathbf d}(i+2) ) + {\mathbf d}(i+2) \\ & \le {\mathbf d}(i+3) + {\mathbf d}(i+2). \end{array} \] \end{proof} Before we start the proof we also need to establish some definitions. Let \( \sigma \) be the permutation of \{1,2, \ldots, 2n\} defined by \[ \sigma(i) = \left\{ \begin{array}{ll} n+ i/2 & \mbox{if \(i\) is even} \\ n- (i-1)/2 & \mbox{if \(i\) is odd.} \end{array} \right. \] 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, \( \sigma\) is the permutation for which \( \sigma(1)=n\) and, for \( 2\le i,j \le 2n \), \( {\mathbf d}(\sigma(i)) < {\mathbf d}(\sigma(j)) \iff i < j\). We now define a set of vectors. These vectors are defined differently on the two regions of definition. For \( 2 \le i \le 2n\) let \[ {\mathbf x}_{i}(j) = \left\{ \begin{array}{rl} 1 & \mbox{if $\sigma(i)=j$} \\ -1 & \mbox{if \(j=\sigma(l)\) for some \(l 2n \) let \[ {\mathbf x}_{i}(j)= \left\{ \begin{array}{rl} 1 & \mbox{if $i=j$} \\ -1 & \mbox{if $ i-{\mathbf b}(i) \le j \le i-1$} \\ 0 & \mbox{otherwise.} \end{array} \right. \]\\ Note that \( {\mathbf x}_{1} \) is not defined. Also note that, due to (\ref{eq:inter}), \( {\mathbf x}_{i} \cdot {\mathbf d} = 0\) for \( i \in \{ 2, \ldots, m \} \). We are now ready to begin the proof. Let \({\mathbf v}\) be a smooth nonzero vector of dimension \(m\) where \( m\ge 2n\). As outlined in the introduction, we construct a sequence, \( {\mathbf w}_{m}, {\mathbf w}_{m-1}, \ldots, {\mathbf w}_{2} \), of approximations to \({\mathbf v}\). Our goal is to show that these approximations satisfy \begin{enumerate} \renewcommand{\theenumi}{(\roman{enumi})} \item \( {\mathbf w}_{i} \) agrees with \({\mathbf v}\) in the \(m-i+1\) coordinates where \( {\mathbf d} \) is greatest, \item $ {\mathbf w}_{i} \cdot {\mathbf d} = 0 $, and \item If \({\mathbf w}_{2}\) is nonzero then \({\mathbf w}_{2}\) is not smooth. \end{enumerate} To define the approximations, first set \(\rho_{m} = {\mathbf v}(m)\) and \( {\mathbf w}_{m} = \rho_{m} {\mathbf x}_{m} \). Once \( {\mathbf w}_{i+1} \) is determined let \[ \rho_{i} = \left\{ \begin{array}{ll} {\mathbf v}(i) - {\mathbf w}_{i+1}(i) & \mbox{if \(2n+1 \le i \le m-1\)} \\ {\mathbf v}(\sigma(i)) - {\mathbf w}_{i+1}(\sigma(i)) & \mbox{if \(2 \le i \le 2n\).} \end{array} \right. \] and set \( {\mathbf w}_{i} = {\mathbf w}_{i+1} + \rho_{i} {\mathbf x}_{i}\). Since each \({\mathbf w}_{i}\) is a linear combination of the \( {\mathbf x}_{i}\)'s, property (ii) holds. Property (i) is also immediate. It remains to show that \( {\mathbf w}_{2} \) is not smooth. Before doing this we establish two important properties of the sequence \( \rho_{m}, \rho_{m-1}, \ldots, \rho_{2} \). These properties follow from the smoothness of \({\mathbf v}\), and we have one property for each region of definition of \({\mathbf d}\). \begin{lemma} If \( \rho_{m} > 0 \) then \(\rho_{j} > 0\) for \( \max \{ 2n, m-{\mathbf b}(m) \} \le j \le m-1 \). \end{lemma} \begin{proof} Suppose inductively that \( \rho_{j+1}, \ldots, \rho_{m-1} > 0 \). Then, using \( j \ge m - {\mathbf b}(m) \) \[ {\mathbf w}_{j+1}(j) = - \sum_{i=j+1}^{m} \rho_{i} \le -m+j. \] Since \( \rho_{m} > 0\), we have \( {\mathbf v}(m) > 0 \). Since \({\mathbf v}\) is smooth, it follows from \( {\mathbf v}(m) > 0 \) that \( {\mathbf v}(j) \ge 1 - m +j \). Therefore, \( \rho_{j} = {\mathbf v}(j) - {\mathbf w}_{j+1}(j) \ge 1-m+j - (-m+j) = 1\). \end{proof} \begin{lemma} For \(j= \max \{i \le 2n: \rho_{i} \neq 0\) \}, \[ \rho_j \rho_{j-2}, \rho_j \rho_{j-4}, \dotsc > 0 \hskip3mm \text{ and } \hskip3mm \rho_j \rho_{j-1}, \rho_j \rho_{j-3}, \dotsc \ge 0. \] \end{lemma} \begin{proof} Without loss of generality, assume \( \rho_{j} > 0 \). Also assume \( \sigma(j) > n \); the proof for \( \sigma(j) < n \) is nearly identical to what follows. We consider inductively \( \rho_{j-i} \) for \( i = 1, \dots , j-2 \). Of course, in order to prove the Lemma we must show \begin{equation} \label{eq:clear} \begin{split} \rho_{j-i} \ge 0 & \text{ if \(i\) is odd, and }\\ \rho_{j-i} > 0 & \text{ if \(i\) is even}. \end{split} \end{equation} We begin by showing \( \rho_{j-1} \ge 0 \). Unfortunately, this must be done in two cases: \(j=2n\) and \( j <2n\). If \( j=2n \) then \( {\mathbf w}_{2n}(\sigma(2n-1)) = {\mathbf w}_{2n}(1) = -\rho_{2n} \le -1 \). By the definition of a smooth vector we have \({\mathbf v}(1) \ge -1\). Hence \( {\mathbf v}(1) \ge {\mathbf w}_{2n}(1)\), and \(\rho_{2n-1} \ge 0\). If \(j<2n\) then \( {\mathbf v}(\sigma(j+1)) = {\mathbf w}_{j}(\sigma(j+1)) =0\). The smoothness of \({\mathbf v}\) between coordinates \( \sigma(j+1) \) and \(\sigma(j+1)+1 = \sigma(j-1) \) implies \( {\mathbf v}(\sigma(i-1)) \ge -1 \). Since \( {\mathbf w}_{j}(\sigma(j-1)) = - \rho_{j} \le -1\), it follows that \( \rho_{j-1} \ge 0 \). Now, suppose (\ref{eq:clear}) holds for \( i = 1, \dots, k\) where \(k\) is odd. Let \( M = \rho_{2n+1}+\rho_{2n+2}+\rho_{2n+3} \) and \( L = \sum_{i=0}^{k-2} \rho_{j-i} \). Now, \begin{gather*} {\mathbf v}(\sigma(j-k+1)) = {\mathbf w}_{j-k+1}(\sigma(j-k+1)) = -M -L + \rho_{j-k+1}, \text{ and }\\ {\mathbf w}_{j-k}(\sigma(j-k-1)) = -M -L - \rho_{j-k+1} - \rho_{j-k}. \end{gather*} Since \({\mathbf v}\) is smooth and \( \sigma(j-k+1) - 1 = \sigma(j-k-1) \), \[ {\mathbf v}(\sigma(j-k-1)) \ge -M-L+\rho_{j-k+1}-1.\] Thus, \begin{equation} \label{eq:turtle} \begin{split} \rho_{j-k-1} & = {\mathbf v}(\sigma(j-k-1)) - {\mathbf w}_{j-k}(\sigma(j-k-1)) \\ & \ge 2\rho_{j-k+1} + \rho_{j-k} -1 \\ & \ge 1. \end{split} \end{equation} Simillarly, \begin{gather*} {\mathbf v}(\sigma(j-k)) = {\mathbf w}_{j-k}(\sigma(j-k)) = -L - \rho_{j-k+1} + \rho_{j-k}, \text{ and }\\ {\mathbf w}_{j-k-1}(\sigma(j-k-2)) = -L - \rho_{j-k+1} - \rho_{j-k} -\rho_{j-k-1}. \end{gather*} Since \( \sigma(j-k)+1 = \sigma(j-k-2) \) and \({\mathbf v}\) is smooth, \[ {\mathbf v}(\sigma(j-k-2)) \ge -L -\rho_{j-k+1} + \rho_{j-k} -1.\] It then follows from (\ref{eq:turtle}) that \begin{equation*} \begin{split} \rho_{j-k-2} & = {\mathbf v}(\sigma(j-k-2)) - {\mathbf w}_{j-k-1}(\sigma(j-k-2))\\ & \ge 2\rho_{j-k} +\rho_{j-k-1} -1 \\ & \ge 0. \end{split} \end{equation*} \end{proof} An important implication of Lemma~3.5--we will apply this in showing that \( {\mathbf w}_{2} \) is not smooth--is \begin{equation} \label{eq:forjeff} \rho_{2}\rho_{3} \ge 0. \end{equation} We now divide the argument into cases based on the dimension of \({\mathbf v}\) and the sequence of \( \rho_{i} \)'s. This argument is inductive; for all cases after Case~1 we are assuming that no smooth vector of smaller dimension dots with \({\mathbf d}\) to give zero (this assumption is only used in Case~4). Throughout these cases we assume without loss of generality that \( {\mathbf v}(m) > 0 \) and hence \(\rho_{m} >0\). \begin{case} \( m =2n \). \end{case} Since \({\mathbf v}\) is nonzero there exists \(j\) such that \( \rho_{j} \neq 0 \). Lemma~3.5 then implies that either \( \rho_{2} \neq 0 \) or \( \rho_{3} \neq 0 \). Suppose \( \rho_{2} \neq 0 \). Let \( M = \sum_{i=3}^{2n} \rho_{i} \). Then \( {\mathbf w}_{2}(n) = -M - \rho_{2} \) while \( {\mathbf w}_{2}(n+1) = -M + \rho_{2} \). Hence, \( {\mathbf w}_{2} \) is not smooth. Suppose \( \rho_{2} = 0 \) and hence \( \rho_{3} \neq 0 \). Let \( M = \sum_{i=4}^{2n} \rho_{i} \). Then \( {\mathbf w}_{2}(n) = -M - \rho_{3} \) while \( {\mathbf w}_{2}(n-1) = -M + \rho_{3} \). Hence, \( {\mathbf w}_{2} \) is not smooth. \begin{case} \( 2n+1 \le m \le 2n+3 \). \end{case} By Lemma~3.4, \( \rho_{j} > 0\) for \( 2n \le j \le m-1 \). Lemma~3.5 then implies that \( \rho_{2} > 0\) and \( \rho_{3} \ge 0\). Let \(M= \sum_{i=4}^{2n} \rho_{i}\). Then \( {\mathbf w}_{2}(n-1) = -M + \rho_{3}\) while \( {\mathbf w}_{2}(n) = -M - \rho_{3} - \rho_{2} - \rho_{2n+1}\). Therefore \( {\mathbf w}_{2}(n-1) - {\mathbf w}_{2}(n) = 2 \rho_3 + \rho_2 + \rho_{2n+1} \ge 2 \), and \({\mathbf w}_{2}\) is not smooth. \begin{case} \( m \ge 2n+4 \) and \( \rho_{2n+1}, ... \rho_{m-1} > 0 \). \end{case} Let \(M= \sum_{i=4}^{2n} \rho_{i}\). Then \( {\mathbf w}_{2}(n-1) = -M + \rho_{3}, {\mathbf w}_{2}(n) = -M - \rho_{3} - \rho_{2} - \rho_{2n+1}\), and \( {\mathbf w}_{2}(n+1) = -M - \rho_{3} + \rho_{2} - \rho_{2n+1} - \rho_{2n+2}- \rho_{2n+3} \). If \( \rho_{2} \le 0 \) then \( {\mathbf w}_{2}(n) - {\mathbf w}_{2}(n+1) = -2 \rho_{2} + \rho_{2n+2} + \rho_{2n+3} \ge 2\) and \( {\mathbf w}_{2} \) is not smooth. On the other hand, if \( \rho_{2} > 0\) then (\ref{eq:forjeff}) implies \( \rho_{3} \ge 0\). In this case \( {\mathbf w}_{2}(n-1) - {\mathbf w}_{2}(n) = 2 \rho_{3} + \rho_{2} + \rho_{2n+1} \ge 2 \) and \( {\mathbf w}_{2} \) is not smooth. \begin{case} \( m \ge 2n+4 \) and \( \exists t \ge 2n+4 \) such that \( \rho_{t-1} \le 0 \) while \(\rho_{t}, ..., \rho_{m-1} > 0\). \end{case} We begin by investigating the structure of \({\mathbf w}_{t}\). By property~(i) of \({\mathbf w}_{t}\), we have \({\mathbf w}_{t}(i) = {\mathbf v}(i) \) for \( i\ge t\). It is also clear from the definition of \( {\mathbf w}_{t}\) that \({\mathbf w}_{t}(i)=0\) for \(i t-1 \) we have \( {\mathbf b}(y+1) = {\mathbf b}(y)\). Applying (\ref{eq:central}) we get \( {\mathbf b}(t) = {\mathbf b}(y+1-{\mathbf b}(y+1)) < {\mathbf b}(y+1) = {\mathbf b}(y)\). It follows that there exists \(u\) with \( t \le u < y \) and \( {\mathbf b}(u+1) = {\mathbf b}(u) + 1\). Then \( s=u-{\mathbf b}(u)-1\) has the desired properties. Consider the vector \( {\mathbf z} = {\mathbf v} - {\mathbf w}_{t} \). Property~(ii) of \( {\mathbf w}_{t} \) implies \[ {\mathbf v} \cdot {\mathbf d} = {\mathbf z} \cdot {\mathbf d} .\] Property~(i) of \( {\mathbf w}_{t} \) implies \( {\mathbf z}(i) = 0 \) for \( i \ge t\). Since we're assuming \( \rho_{t-1} \le 0 \), we have \( {\mathbf w}_t(t-1) \ge {\mathbf v}(t-1) \). Since \( {\mathbf w}_{t}(t - {\mathbf b}(t) -1), {\mathbf w}_{t}(t-{\mathbf b}(t)), ..., {\mathbf w}_{t}(t-2), {\mathbf w}_{t}(t-1) \) is strictly decreasing and \({\mathbf v}\) is smooth, we have \({\mathbf w}_{t}(i) \ge {\mathbf v}(i)\) for \( t-{\mathbf b}(t)-1 \le i \le t-1 \). Furthermore, the existence of the double jump between \( {\mathbf w}_{t}(s) \) and \( {\mathbf w}_{t}(s+1)\) implies that \( {\mathbf w}_{t}(i) > {\mathbf v}(i)\) for \( t-{\mathbf b}(t)-1\le i \le s \). Thus, \begin{gather} \label{eq:picture} {\mathbf z}(i) \left\{ \begin{array}{ll} = 0 & \mbox{ if \( i\ge t \)}\\ \le 0 & \mbox{ if \( s+1 \le i \le t-1\)}\\ < 0 & \mbox{ if \( t - {\mathbf b}(t) -1 \le i \le s\),} \end{array} \right.\\ \intertext{and} \label{eq:prepicture} ({\mathbf z}(1), {\mathbf z}(2), \dots , {\mathbf z}(t - {\mathbf b}(t)-1)) \text{ is a smooth vector.} \end{gather} We now consider cases. \begin{subcase} \( {\mathbf z}(i) < 0 \) for \(i \le s\). \end{subcase} Clearly, \(0 > {\mathbf z} \cdot {\mathbf d} = {\mathbf v} \cdot {\mathbf d}. \)\\[3mm] For the remaining two cases let \( q = \max\{i < t- {\mathbf b}(t)-1\) : \({\mathbf z}(i) = 0 \}\). When we restrict \({\mathbf z}\) to its first \(q-1\) components (which are also the first \(q-1\) components of \({\mathbf v}\)) we get a smooth vector \({\mathbf y}\) with \( |{\mathbf y}(q-1)| \le 1 \). \begin{subcase} There exists \(r > q+1\) such that \( {\mathbf z}(r) < 0 \). \end{subcase} Since \( t \ge 2n+4 \), \( t-{\mathbf b}(t)-1 \ge 2n\). So, if \( q<2n \) then \( {\mathbf z}(2n) < 0 \). In this case we apply Lemma~3.1 to \({\mathbf y}\) to get \[ 0 > {\mathbf y} \cdot {\mathbf d} - {\mathbf d}(2n) \ge {\mathbf z} \cdot {\mathbf d} = {\mathbf v} \cdot {\mathbf d}. \] On the other hand, if \(q \ge 2n\) we apply Lemma~3.3 to \({\mathbf y}\) to get \[ 0 > {\mathbf y} \cdot {\mathbf d} - {\mathbf d}(q+1) - {\mathbf d}(q+2) \ge {\mathbf y} \cdot {\mathbf d} - {\mathbf d}(q+1) - {\mathbf d}(r) \ge {\mathbf z} \cdot {\mathbf d} = {\mathbf v} \cdot {\mathbf d}. \] \begin{subcase} For all \( r>q+1 \), \( {\mathbf z}(r) =0 \). \end{subcase} It follows from (\ref{eq:picture}) that \(s = q+1= t -{\mathbf b}(t) -1\). Furthermore, \( {\mathbf z}(i) = 0 \) for \( i > t -{\mathbf b}(t) -1 \), and hence \( {\mathbf v} \cdot {\mathbf d} = {\mathbf z} \cdot {\mathbf d} = ({\mathbf z}(1), \dots , {\mathbf z}(t - {\mathbf b}(t)-1)) \cdot {\mathbf d} \). However, by (\ref{eq:prepicture}) and our inductive hypothesis, we have \( ({\mathbf z}(1), \dots , {\mathbf z}(t - {\mathbf b}(t)-1)) \cdot {\mathbf d} \neq 0\). \begin{case} \( m \ge 2n+4 \) and \(\rho_{2n+3}, ..., \rho_{m-1} > 0\), but either \(\rho_{2n+1} \le 0\) or \( \rho_{2n+2} \le 0 \). \end{case} Suppose \( \rho_{2n+2} \le 0\). Note that, by Lemma~3.4, this implies \( m \ge 2n + 7\). We begin with a description of \( {\mathbf w}_{2n+3} \). Clearly, \[ {\mathbf w}_{2n+3}(i) = \left\{ \begin{array}{ll} -\rho_{2n+3} -\rho_{2n+4}-\rho_{2n+5} - \rho_{2n+6} & \mbox{ if \(i = 2n+2 \)} \\ -\rho_{2n+3} -\rho_{2n+4}-\rho_{2n+5} & \mbox{ if \(i = 2n+1 \)} \\ -\rho_{2n+3} & \mbox{ if \(n+1 \le i \le 2n\)} \\ 0 & \mbox{ if \( 1 \le i \le n\).} \end{array} \right. \] Since \( \rho_{2n+2} \le 0\) and \( {\mathbf v} \) is smooth we have \[ {\mathbf v}(i) \le \left\{ \begin{array}{ll} {\mathbf w}_{2n+3}(i) & \mbox{ if \( i =2n+1,2n+2 \)} \\ \min \{i,2n-1-\rho_{2n+3}-i\} & \mbox{ if \( 1 \le i \le 2n \).} \end{array} \right. \] So, for \( {\mathbf z} := {\mathbf v} - {\mathbf w}_{2n+3} \), \[ {\mathbf z}(i) \le {\mathbf y}(i) := \left\{ \begin{array}{ll} 0 &\mbox{ if \( i =2n+1,2n+2 \)} \\ \min \{i,2n-1-i\} & \mbox{ if \( 1 \le i \le 2n \).} \end{array} \right. \] Note that the restriction of \( {\mathbf z}\) to its first \(2n\) coordinates is not necessarily smooth as \( {\mathbf w}_{2n+3}(n+1) = - \rho_{2n+3}\) while \( {\mathbf w}_{2n+3}(n) = 0\). However, the restriction \( {\mathbf y}\) to its first \(2n\) coordinates is smooth, and, therefore, it follows from Lemma~3.1 that \( {\mathbf y} \cdot {\mathbf d} <0 \). It then follows from properties (i) and (ii) of \( {\mathbf w}_{2n+3} \) that \( {\mathbf v} \cdot {\mathbf d} = {\mathbf z} \cdot {\mathbf d} \le {\mathbf y} \cdot {\mathbf d} <0 \). The proof is similar if \( \rho_{2n+2} > 0 \) and \( \rho_{2n+1} \le 0 \). \section{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 \({\mathbf v}_{n}(k) = \max S_{2n,k}\). A direct calculation yields: \begin{align*} {\mathbf v}_{n}(2n) & = (1/2)2^{2n}, \\ {\mathbf v}_{n}(2n+1) & = 2/3 + (5/12)2^{2n+1}, \\ {\mathbf v}_{n}(2n+2) & = 1 + (3/8)2^{2n+2}, \\ {\mathbf v}_{n}(2n+3) & = 5/3 + (17/48)2^{2n+3} \text{ and} \\ {\mathbf v}_{n}(k+1) & = 2{\mathbf v}_{n}(k) - {\mathbf v}_{n}(k-{\mathbf b_n}(k+1)) \text{ for } k \ge 2n+3. \end{align*} Let \( {\mathbf r}_{n}(k)={\mathbf v}_{n}(k)/2^{k}\). Our goal is too find the minimum over \(k\) of \({\mathbf r}_{n}(k)\). The values of \({\mathbf v}_{n}\) listed above imply \begin{align*} {\mathbf r}_{n}(2n)&=1/2,\\ {\mathbf r}_{n}(2n+1)&= 5/12 + (1/3)2^{-2n},\\ {\mathbf r}_{n}(2n+2)&= 3/8 + 2^{-2n-2},\\ {\mathbf r}_{n}(2n+3)&= 17/48 + (5/3)2^{-2n-3} \text{ and}\\ {\mathbf r}_{n}(k+1) &= {\mathbf r}_{n}(k) - {\mathbf r}_{n}(k-{\mathbf b}_n(k+1))/2^{1+ {\mathbf b}_n(k+1)} \text{ for } k \ge 2n+3. \end{align*} Since \( {\mathbf v}_{n}(k) \) and hence \( {\mathbf r}_{n}(k) \) is positive, the sequence \( \left\{ {\mathbf r}_{n}(k) \right\}_{k=2n}^{\infty} \) is decreasing. In order to find the best upper bound on \(f(n)\) that can be obtained from the difference vector \( {\mathbf d}_{n} \) we must calculate the limit as k tends to infinity of \({\mathbf 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 \begin{align*} {\mathbf r}(3) & = 1/2,\\ {\mathbf r}(4) & = 5/12,\\ {\mathbf r}(5) & = 3/8,\\ {\mathbf r}(6) & = 17/48 \text{ and }\\ {\mathbf r}(k+1) & = {\mathbf r}(k) - {\mathbf r}(k-{\mathbf b}(k+1))/2^{1+ {\mathbf b}(k+1)} \text{ for } k \ge 6. \end{align*} where \({\mathbf b}\) is defined by \( {\mathbf b}(i) = \left[ \sqrt{2(i-1)} \right]\) (which is also known as \({\mathbf b'_{1}}\), the recursive rule for the Conway--Guy sequence). \begin{claim} \( {\mathbf r}(3+k) \le {\mathbf r}_{n}(2n+k) \le {\mathbf r}(3+k) + (1/3)2^{-2n} \) for \(k \ge 0\). \end{claim} \begin{proof} Let \( {\mathbf e} \) be the vector defined by \( {\mathbf e}(k) = {\mathbf r}_n (2n+k) - {\mathbf r}(3+k)\). For \(k \ge 6\) we have \[ {\mathbf e}(k+1) = {\mathbf e}(k) - {\mathbf e}(k-{\mathbf b}(k+1))/2^{1+ {\mathbf b}(k+1)}.\] The claim follows immediately from \begin{equation} \label{eq:obvious} {\mathbf e}(k+1) > {\mathbf e}(k)/2 \text{ for } k \ge 0, \end{equation} as (\ref{eq:obvious}) implies \( {\mathbf e}(k) \ge 0 \) for \(k\ge 0\). It is easy to see that (\ref{eq:obvious}) holds for \( k=0,1,2 \). For \(k \ge 3\) we proceed by induction: \begin{equation} \begin{split} {\mathbf e}(k+1) & = {\mathbf e}(k) - \frac{{\mathbf e}(k-{\mathbf b}(k+1))}{2^{1+ {\mathbf b}(k+1)}} \\ & > {\mathbf e}(k) - \frac{{\mathbf e}(k) \cdot 2^{{\mathbf b}(k+1)}}{2^{1+ {\mathbf b}(k+1)}} \\ & = {\mathbf e}(k)/2. \end{split} \end{equation} \end{proof} It follows from Claim~4.1 that, for \(L := \lim_{k \to \infty} {\mathbf r}(k)\), the limit as \( k \) goes to infinity of \({\mathbf r}_{n}(k)\) is between \(L\) and \( L +(1/3)2^{-2n} \). An investigation of the sets generated by \({\mathbf d}_{n}'\) reveals a similar convergence in their sequences of ratios to \({\mathbf 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 \cite{guy} 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 \( {\mathbf b} \) equals \(j-1\). We use \( {\mathbf 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 \({\mathbf r}\) we have \({\mathbf r}(p_{j}+1) = {\mathbf r}(p_{j}) - 2^{-j-1}{\mathbf r}(p_{j}-j)\). Iterating this observation we have \[ {\mathbf r}(p_{j+1}) = {\mathbf r}(p_{j}) - \sum_{i=p_{j}}^{p_{j+1}-1} 2^{-j-1}{\mathbf r}(i-j). \] But, this also can be iterated to give \[ {\mathbf r}(p_{j+m}) = {\mathbf r}(p_{j}) - \sum_{k=0}^{m-1} 2^{-j-k-1} \sum_{i=p_{j+k}}^{p_{j+k+1}-1} {\mathbf r}(i-j-k). \] Since \({\mathbf 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 \[ {\mathbf r}(p_{j}) - 3/8 \sum_{k=0}^{m-1} 2^{-j-k-1}(j+k) < {\mathbf r}(p_{j+m}) < {\mathbf r}(p_{j}) - L \sum_{k=0}^{m-1} 2^{-j-k-1} (j+k).\] A simple calculations shows that \( \sum_{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 \begin{equation} {\mathbf r}(p_{j}) - \frac{3(j+1)}{(8)2^{j}} < L < {\mathbf r}(p_{j}) - \frac{L(j+1)}{2^{j}}. \label{eq:limit} \end{equation} A simple computer calculation gives the approximation \( .2200188 < {\mathbf 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 \approx .22001865\) with an error of less than \(1.5 \cdot 10^{-7}\). Inequality (\ref{eq:limit}) can certainly be used to obtain more precise approximations of \(L\). \pagebreak \begin{thebibliography}{999} \bibitem[AS]{alonspen} N. Alon and J. Spencer, {\em The Probabilistic Method}, Wiley, 1992. \bibitem[ANS]{ans} M.D. Atkinson, A. Negro and N. Santoro, Sums of Lexicographically Ordered Sets. {\it Discrete Math} {\bf 80}(1990) 115--122. \bibitem[B]{bohman} T. Bohman, The Conway--Guy sequence and a sum packing problem of Erd\H{o}s, {\em Proceedings Amer. Math. Soc.}, {\bf 124}(1996) 3627--3636. \bibitem[CG]{cg} J.H. Conway and R.K. Guy, Sets of natural numbers with distinct subset sums, {\em Notices Amer. Math. Soc.}, {\bf 15}(1968) 345. \bibitem[Elk]{elk} N. Elkies, An improved lower bound on the greatest element of a sum--distinct set of fixed order, {\em J. Comb. Th. A}, {\bf 41}(1986) 89-94. \bibitem[E1]{erdos1} P. Erd\H{o}s, Personal communication. \bibitem[E2]{erdos2} P. Erd\H{o}s, Problems and results from additive number theory, {\em Colloq. Th\'eorie des nombres, Bruxells}(1955) 127-137. \bibitem[G1]{guy} R.K. Guy, Sets of integers whose subsets have distinct sums, {\em Ann. Discrete Math.}, {\bf 12}(1982) 141-154. \bibitem[G2]{guybook} R.K. Guy, {\em Unsolved Problems in Number Theory}, Springer-Verlag, 1981. \bibitem[L]{lunnon} W.F. Lunnon, Integer sets with distinct subset sums, {\em Math. Compute}, {\bf 50}(1988) 297-320. \bibitem[M]{maltby} R. Maltby, Bigger and Better Subset--Sums--Distinct Sets, {\em Mathematika}, to appear. \end{thebibliography} \end{document}