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].

Theoremf(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

Advertisements

One comment

  1. Abishek · · 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: