Let $X=\{x\_1,...,x\_n\}$ be a multiset of $n$ real numbers, and let $x\_1+\dots+x\_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset sums to $0$, but contains no subset itself that sums to $0$?


Or more precisely, is the following max over all multisets of size $n$ bounded above polynomially as $n$ gets large?: $max\{|f(X)| : X = \{x\_1,...,x\_n\} \land x\_1+\dots+x\_n = 0\}$ where $f(X) = \{Y \subseteq X : sumY=0 \land \forall\_{Z\subset Y}sumZ\neq0 \}$.


I'm interested in this as a bound for an algorithm. I have a feeling it doesn't grow very fast, but I'm unsure how to approach the problem.


I have tried to brute force it for small values of $x$ and have found the following values for $n \in [0,10]$: $[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$. OEIS doesn't seam to have a related entry.




---


Edit: To work against confusion, here are some examples using distinct integers only, that I believe to be optimal:



```
0: {}                    {{}}
1: {0}                   {{0}}
2: {-1,1}                {{-1,1}}
3: {-1,0,1}              {{0},{-1,1}}
4: {-2,-1,1,2}           {{-2,2},{-1,1}}
5: {-2,-1,0,1,2}         {{0},{-2,2},{-1,1}}
6: {-3,-2,-1,1,2,3}      {{-3,3},{-2,2},{-1,1},{-3,1,2},{-2,-1,3}}
7: {-6,-4,-1,1,2,3,5}    {{-1,1},{-6,1,5},{-4,-1,5},{-4,1,3},{-6,-1,2,5},{-6,1,2,3},{-4,-1,2,3},{-6,-4,2,3,5}}
8: {-8,-7,-3,1,2,4,5,6}  {{-8,2,6},{-7,1,6},{-7,2,5},{-3,1,2},{-8,-3,5,6},{-8,1,2,5},{-7,-3,4,6},{-7,1,2,4},{-8,-7,4,5,6},{-8,-3,1,4,6},{-8,-3,2,4,5},{-7,-3,1,4,5}}

```


Problem regarding subsets that sum to 0
As suggested by Christian, you may want to start by looking at the [Littlewood-Offord problem](http://en.wikipedia.org/wiki/Littlewood-Offord_problem). Here's a scaled version of Erdős' result that might be more relevant to your problem:


"If $a\_1, \dots a\_n$ are all nonzero, then for any $c$ subsums which equal $c$ is at most $\binom{n}{\lfloor n/2\rfloor}$, the bound achieved when all of the $a\_i$ are equal to $1$. and $c=\lfloor n/2 \rfloor $". 


Assume without loss of generality that all of your $a\_i$ are nonzero (any $a\_i$ which equal $0$ don't appear in any of your subsets anyway). Then that upper bound still applies in this case, and is roughly $C2^n/\sqrt{n}$ for large $n$. 


For a lower bound, we'll use the following construction: Suppose you have a set $S$ of positive integers such that the sum of all the elements in $S$ is $k$ and you have many subsets summing to $c$. Then we let 


$$S'=S \cup \{-c\} \cup \{c-k\}.$$


For every subset of $S$ summing to $c$ there is a corresponding subset of $S'$ formed by adding in $-c$. This subset has no smaller subset summing to $0$ because $S$ consisted entirely of positive integers. 


What this lower bound gives you depends on how you're counting subsets. For example, if $n$ is even the multiset 
$$[1,1,\dots,1,-\frac{n}{2}, -\frac{n}{2}]$$
with $n-2$ ones has $2\binom{n-2}{n/2-1}$ submultisets of the form $[1,1,\dots,1, -\frac{n}{2}]$ summing to $0$. For large $n$ this is about a factor of $2$ off from the lower bound. 


If you consider these subsets to all be identical, then you can instead start with $S=\{1,2,\dots,n-2\}$. You can check that for large $n$ this set has roughly $C\frac{2^{n-2}}{n^{3/2}}$ subsets summing to the same value for some $C$ (the idea is that if you take a random subset the standard deviation of its sum is only order $n^{3/2}$). So you can start with this as your $S$ and get a lower bound which is roughly $2^n n^{-3/2}$ for large $n$. 


