Problem regarding subsets that sum to 0 - MathOverflow

Problem regarding subsets that sum to 0

2011-12-08T13:34:51Z

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}}

Answer by Christian Elsholtz for Problem regarding subsets that sum to 0

2011-12-08T16:55:13Z

If I understand the question correctly, the following might give asymptotic answers of exponential size..

1) Subsums of a Finite Sum and Extremal Sets of Vertices of the Hypercube, by Dezső Miklós, Horizons of Combinatorics, Bolyai Society Mathematical studies Vol 17, 2008.

available on Springer link. A link to some slides: http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf

2) Other work on the Littlewood-Offord problem could be relevant as well.

Answer by Gerhard Paseman for Problem regarding subsets that sum to 0

2011-12-08T16:56:33Z

Here is an example that shows the bound is going to be exponential in nature.

Pick $k > 0$ a large integer for emphasis. Pick your favorite set $F$ of $k$ distinct positive integers. Form the set $S$ of all sums formed by summing a proper nomempty subset of $F$. For your favorite set $F$, $S$ may be of size $2^k$; for my favorite set $F$ being the first $k$ postive integers, $S$ has size at most $k+1$ choose 2 .

Let's use an $F$ such that $S$ has size polynomial in $k$. Now create $M$ which is the negative of every number in $S$. Finally create the multiset $U$ which has one copy of $M$ plus enough copies of $F$ (including a fractional copy if needed, but I think one is not) to have $U$ sum to 0. $U$ has size polynomial in $k$, and at least $2^k$ obvious choices for minimal subsets which sum to 0. So I conjecture a lower bound of the form $2^{g(n)}$, where $g(n)$ is $O(n^{1/3})$ and $n$ is the size of the multiset.

You can likely tweak this to get accurate bounds, but if you are at the beginning, I think you have to prepare for potential exponential running time for your algorithm.

Gerhard "Ask Me About System Design" Paseman, 2011.12.08

Answer by Kevin P. Costello for Problem regarding subsets that sum to 0

2011-12-08T21:17:56Z

As suggested by Christian, you may want to start by looking at the 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$.