# Distinct Sums

Leo Moser

A set of positive integers $\{x_1,\ldots,x_k\}$ is said to have distinct sums (DS) if all sums $\sum_{i \in S} x_i$ where  $S \subseteq [k]$ are distinct. We are interested in understanding the function $f(n) = \max_{k}{\big(k \in N: \exists \{x_1,\ldots,x_k\} \text{~with DS}\big)}$.  We obtain a simple lower bound on $f(n)$ by observing that the set $\{1,2,2^2,\ldots,2^{k-1}\}$ has DS as long as $2^{k-1} \leq n \rightarrow k \leq \log_2{n}+1$. Therefore, $f(n) \geq \lfloor log_2{(n)} \rfloor+1$. Interestingly, this lower bound is not far away from being optimal, in the sense that $f(n) \leq (1+o(1))\log_2{n}$. First, we show an easy upper bound.  Notice that we have $2^{f(n)}$ possible sums. Since they are all bounded by the  generous upper bound $nf(n)$ we obtain the following $2^{f(n)} < nf(n) \rightarrow f(n) < \log_2{n} + \log_2{\log_2{n}}+O(1)$.  In case this upper bound is not obvious to you, think of the pidgeonhole principle. We have at most $kn+1$ bins and $2^{f(n)}$ balls. Since no bin obtains two balls, we need to have $nf(n)+1\geq 2^{f(n)}$. Now we see how the above upper bound can be slightly improved by cutting down the $\log_2{\log_2{(n)}}$ term down to half. This result is due to Erdős and Moser, see page 137 of [1].

Theorem$f(n) \leq \log_2{n} + \frac{1}{2} \log_2{\log_2{n}} + O(1)$.

Proof:  The proof is probabilistic. Let $\{x_1,\ldots,x_k\}$ be a set with DS. Pick a subset of uniformly at random from the set of $2^k$ subsets and let’s consider the sum of its elements. This can be seen to be equivalent to selecting $n$ Bernoulli iid random variables $Prob(\epsilon_i=0)=Prob(\epsilon_i=1)=\frac{1}{2}$, $i=1,..,n$ and considering  $X = \epsilon_1 x_1 + \ldots + \epsilon_k x_k$. Clearly, $E[X] = \frac{\sum_{i=1}^k x_i}{2}$ and $Var[X]= \frac{x_1^2+\ldots+x_k^2}{4}$. Now, the rest of the proof is sketched. We leave it to the reader to fill in the details:

• Notice $Var[X] \leq \frac{n^2k}{4}$.
• Apply Chebyshev’s inequality to random variable $X$.
• Finally, notice that since the sums are distinct $Prob( |X-E[X]| < \lambda n \sqrt{k}/2 ) \leq 2^{-k} (2 \times \lambda n \sqrt{k}/2 +1 )$. Combining the above inequalities gives us the desired result. QED

[1] Problems and results in additive number theory, P. Erdős