Problem regarding subsets that sum to 0 - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:33:30Z http://mathoverflow.net/feeds/question/82964 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82964/problem-regarding-subsets-that-sum-to-0 Problem regarding subsets that sum to 0 Thomas Dybdahl Ahle 2011-12-08T13:34:51Z 2011-12-09T15:00:55Z <p>Let <code>$X=\{x_1,...,x_n\}$</code> be a multiset of <code>$n$</code> real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any <code>$X$</code> can have given <code>$n$</code>, such that each subset sums to <code>$0$</code>, but contains no subset itself that sums to <code>$0$</code>?</p> <p>Or more precisely, is the following max over all multisets of size <code>$n$</code> bounded above polynomially as <code>$n$</code> gets large?: <code>$max\{|f(X)| : X = \{x_1,...,x_n\} \land x_1+\dots+x_n = 0\}$</code> where <code>$f(X) = \{Y \subseteq X : sumY=0 \land \forall_{Z\subset Y}sumZ\neq0 \}$</code>.</p> <p>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.</p> <p>I have tried to brute force it for small values of <code>$x$</code> and have found the following values for <code>$n \in [0,10]$</code>: <code>$[1, 1, 1, 2, 2, 3, 5, 8, 12, 20, 32]$</code>. OEIS doesn't seam to have a related entry.</p> <hr> <p>Edit: To work against confusion, here are some examples using distinct integers only, that I believe to be optimal:</p> <pre><code>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}} </code></pre> http://mathoverflow.net/questions/82964/problem-regarding-subsets-that-sum-to-0/82979#82979 Answer by Christian Elsholtz for Problem regarding subsets that sum to 0 Christian Elsholtz 2011-12-08T16:55:13Z 2011-12-08T16:55:13Z <p>If I understand the question correctly, the following might give asymptotic answers of exponential size..</p> <p>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.</p> <p>available on Springer link. A link to some slides: <a href="http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf" rel="nofollow">http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf</a></p> <p>2) Other work on the Littlewood-Offord problem could be relevant as well.</p> http://mathoverflow.net/questions/82964/problem-regarding-subsets-that-sum-to-0/82980#82980 Answer by Gerhard Paseman for Problem regarding subsets that sum to 0 Gerhard Paseman 2011-12-08T16:56:33Z 2011-12-08T16:56:33Z <p>Here is an example that shows the bound is going to be exponential in nature.</p> <p>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 .</p> <p>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.</p> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.12.08</p> http://mathoverflow.net/questions/82964/problem-regarding-subsets-that-sum-to-0/83002#83002 Answer by Kevin P. Costello for Problem regarding subsets that sum to 0 Kevin P. Costello 2011-12-08T21:17:56Z 2011-12-09T15:00:55Z <p>As suggested by Christian, you may want to start by looking at the <a href="http://en.wikipedia.org/wiki/Littlewood-Offord_problem" rel="nofollow">Littlewood-Offord problem</a>. Here's a scaled version of Erdős' result that might be more relevant to your problem:</p> <p>"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$". </p> <p>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$. </p> <p>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 </p> <p>$$S'=S \cup {-c} \cup {c-k}.$$</p> <p>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. </p> <p>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. </p> <p>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$. </p>