# Minimum real number for subset sum difference

Given a positive integer $$n$$, what is the minimum positive real number $$b(n)$$ such that for any $$a_1,\ldots,a_n\in[0,1]$$, some two subset sums differ by at most $$b(n)$$?

This is similar to subset sum problems, except it is a worst-case instead of an optimization variant.

• The answer is somewhere between $1/2^{n-1}$ (attained for the set $\{2^{i+1-n}\colon 0\le i\le n-1\}$) and $n/(2^n-1)$ (we have $2^n$ subset sums residing in the interval $[0,n]$). So, the fight can be for a logarithmic factor only.
– Seva
Mar 16 '20 at 20:56

As I wrote in my comment, the trivial bounds are $$1/2^{n-1}$$ and $$n/(2^n-1)$$. Here is a proof of the estimate $$b(n)<3\sqrt n/2^n$$; maybe it can be improved further using the same idea.
Consider the random variable $$X=c_1a_1+\dotsb+c_na_n$$ where $$c_1,\dotsc,c_n$$ independently take values $$0$$ and $$1$$, with equal probability. Writing $$S_1:=a_1+\dotsb+a_n$$ and $$S_2:=a_1^2+\dotsb+a_n^2$$, we have $$\mathbb E(X)=S_1/2$$ and $$\mathbb V(x)=S_2/4$$; hence, by Chebyshev's inequality, $$P(|X-S_1/2|\ge t) \le \frac{S_2}{4t^2}.$$ We choose $$t:=\sqrt{S_2}$$ to conclude that with probability at least $$3/4$$ we have $$|X-S_1/2|<\sqrt{S_2}$$. In other words, there are at least $$\frac34\cdot 2^n$$ $$n$$-tuples $$(c_1,\dotsc,c_n)$$ with $$c_1a_1+\dotsb+c_na_n$$ in the range $$(S_1/2-\sqrt{S_2},S_1/2+\sqrt{S_2})$$. Among these $$n$$-tuples there are two such that the corresponding sums are at most $$2\sqrt{S_2}/((3/4)\cdot 2^n-1) \approx \frac83\sqrt{|S_2|}/2^n$$ away from each other. It remains to notice that $$S_2\le n$$.