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

Tags: distinct sums, Erdős-Moser

One comment

Abishek · March 16, 2013 - 6:21 AM · Reply→

Can you please elaborate as to how the inequality 2^f(n) < nf(n) translates to the inequality f(n) < log_{2}(n) + loglog(n) + O(1) ? I understand the pigeonhole principle from where the top inequality comes but am unable to convert that inequality into an inequality as stated in paragraph 1.

Thanks

Distinct Sums

One comment

Leave a Reply Cancel reply

Follow webpage via email

Distinct Sums

Share this:

Like this:

One comment

Leave a Reply Cancel reply

Follow webpage via email