3
$\begingroup$

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}}
$\endgroup$
7
  • $\begingroup$ I can't make sense of your second paragraph. $\endgroup$ Dec 8, 2011 at 15:18
  • 1
    $\begingroup$ @Steve Huntsman: I think he is asking, given n, what is the maximum over all sets X of n real numbers which sum to zero, of the number of non-empty subsets of X whose elements sum to zero and which contain no proper non-empty subset with this property. However this doesn't seem to match up with the data so I am not sure either... $\endgroup$ Dec 8, 2011 at 16:32
  • $\begingroup$ @Thomas Dybdahl Ahle: In your data there are $11$ inputs and only $10$ outputs. Also for $n=3$ shouldn't the answer be $3$? Trivially for any $n$ the number you are looking for is at least $n$, by taking all $x_i=0.$ $\endgroup$ Dec 8, 2011 at 16:36
  • $\begingroup$ If you color the elements, for n=2k even you can have {-1,1} repeated k times for k^2 possibilities. If you aren't coloring the elements, then a few examples for small n would help in making the problem clear. Also, the maximum number should be realized by an antichain of (colored? multi-)sets, so you can use those estimates as a weak upper bound, especially since the symmetric difference of two such sets has at least two elements. Gerhard "Ask Me About System Design" Paseman, 2011.12.08 $\endgroup$ Dec 8, 2011 at 16:38
  • $\begingroup$ I suppose all numbers are nonzero integers? $\endgroup$ Dec 8, 2011 at 16:47

3 Answers 3

2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks. That's a tough bound. I actually thought of unique subsets when I wrote parent, but even though they seam more interesting, I realize that my algorithm will distinguish between all the $2^nn^{-3/2}$ subsets you found. $\endgroup$ Dec 12, 2011 at 11:03
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ You could also have $U'$ be $F$ union $M$ union a singleton number which brings the total of $U'$ to 0, and gives you at least $2^k+1$ minimal sets from a set of size less than $k^2$. Have fun tweaking this. Gerhard "Has Fun Tweaking Mathematical Objects" Paseman, 2011.12.08 $\endgroup$ Dec 8, 2011 at 17:03
  • $\begingroup$ Since I am excluding the empty set in forming $S$, I suppose I should say $2^k-1$ instead of $2^k$. In any case, for large $k$ there will be minimal subsets which have more than one negative number and just one positive number, so there will be more than enough additional desired subsets to make up for the lack. Gerhard "What's One Off Between Colleagues?" Paseman, 2011.12.08 $\endgroup$ Dec 8, 2011 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.