# probability of non-existence of a sum subset

Given a list of distinct integers $a_1,\dots,a_n$ chosen uniformly from the interval $(-2^n,2^n)$, what is the probability that the list contains $\underline{NO\mbox{ }SUBSETS}$ that sum to another integer $b:|b|<2^n$? (what is the probability that the np complete problem SUBSET SUM does not have a subset sum)

Is the odds that there is no subset that sums to b (when b is fixed) is $\frac{1}{2}\pm\epsilon$ or $\epsilon$ or $1-\epsilon$?

The probability that a particular subset of size $k$ has sum $b$ is bounded by $\frac{C}{2^n \sqrt{k}}$, (maximized by $b=0$). Thus the probability that some subset has sum $b$ is at most the sum over $k\leq n$, which is roughly $C/\sqrt{n}$.

[EDIT:] The above is for numbers chosen uniformly with repetition. However, this makes little difference, as the probability of a repetition is much smaller, of order $n^2 2^{-n}$.

The probability will depend on $b$ (for $n \gt 1$). It is the same for $b$ and $-b$. Here is some small data:

The empty subset has sum $0$ but it goes without saying that you mean a non-empty subset, so I won't even mention that.

In the case $n=1$ the probability will be $\frac13$ in all three cases.

In case $n=2$ you end up with one of the $21$ ways to pick $2$ distinct elements from $-3,-2,-1,0,1,2,3.$ The number of these which allow a subset sum of $0,1,2$ or $3$ are $9,8,7$ or $7$

In the case $n=3$ there are $\binom{15}{3}=455$ equally likely outcomes and of these the number allowing a subset sum of $0,1,2,3,4,5,6$ or $7$ are $193,175,164,163,151,149,137$ or $134$.

It seems premature to make any conjectures based on that. It would be a little more time consuming to consider all $\binom{31}7=31465$ possibilities for $n=4$. One could either do random samples or come up with a more intelligent analysis.

• are your counts correct? For n=3. In [a1 a2 a3], pick a1=0, then a2 and a3 can be any of the other numbers for a count of 14*13. Pick a1=1. Then you have a2=-a3 or a2=-1 or a3=-1. For a2=-1 itself you have 13 different choices for a3. This partical count itself takes number of ways 0 can occur as subset to 14*13+13=195>193. – T.... Dec 2 '13 at 9:05
• I was counting out of (unordered) sets of 3 values. so $0,x,y$ occurs $\frac{14\cdot 13}{2}=91$ ways. $x,-x,y$ with $y \ne 0$ happens $14\cdot 6=84$ ways. Another $9$ are $x,y,-x-y$ for 1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 3,4 and a final $9$ of $-x,-y,x+y$ for the same choices . In all, $91+84+9+9=193.$ – Aaron Meyerowitz Dec 2 '13 at 21:39