Leo Moser

A set of positive integers is said to have distinct sums (DS) if all sums where are distinct. We are interested in understanding the function . We obtain a simple lower bound on by observing that the set has DS as long as . Therefore, . Interestingly, this lower bound is not far away from being optimal, in the sense that . First, we show an easy upper bound. Notice that we have possible sums. Since they are all bounded by the generous upper bound we obtain the following . In case this upper bound is not obvious to you, think of the pidgeonhole principle. We have at most bins and balls. Since no bin obtains two balls, we need to have . Now we see how the above upper bound can be slightly improved by cutting down the term down to half. This result is due to Erdős and Moser, see page 137 of [1].

**Theorem**: .

**Proof:** The proof is probabilistic. Let be a set with DS. Pick a subset of uniformly at random from the set of subsets and let’s consider the sum of its elements. This can be seen to be equivalent to selecting Bernoulli iid random variables , and considering . Clearly, and . Now, the rest of the proof is sketched. We leave it to the reader to fill in the details:

- Notice .
- Apply Chebyshev’s inequality to random variable .
- Finally, notice that since the sums are distinct . Combining the above inequalities gives us the desired result.
**QED**

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

### Like this:

Like Loading...

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