52
$\begingroup$

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here.

Apparently, this problem is from a mathematics magazine of some university in the United States (sorry, no idea about either).

So the problem is:

Suppose $S \subset \mathbb{Z}$ (set of integers) such that

1) $|S| = 15$

2) $\forall ~s \in S, \exists ~a,b \in S$ such that $s = a+b$

Show that for every such $S$, there is a non-empty subset $T$ of $S$ such that the sum of elements of $T$ is zero and $|T| \leq 7$.

Update (Sep 13)

Here is an approach which seems promising and others might be able to take it ahead perhaps.

If you look at the set as a vector $s$, then there is a matrix $A$ with the main diagonal being all $1$, each row containing exactly one $1$ and one $-1$ (or a single $2$) in the non-diagonal position such that $As = 0$.

The problem becomes equivalent to proving that for any such matrix $A$ the row space of $A$ contains a vector with all zeroes except for a $1$ and $-1$ or a vector with all zeroes except $\leq 7$ ones.

This implies that the numbers in the set $S$ themselves don't matter and we can perhaps replace them with elements from a different field (like say reals, or complex numbers).

$\endgroup$
  • 2
    $\begingroup$ @rgrig: If S contains 0, you can just take T to be the singleton set. BTW, the problem ought to say "there is a nonempty subset T…". $\endgroup$ – ShreevatsaR Aug 14 '10 at 7:34
  • 7
    $\begingroup$ This question was posed in MathOverflow (without the condition that |S| = 15) in March, at mathoverflow.net/questions/16857/existence-of-a-zero-sum-subset . It has still not been answered. $\endgroup$ – TonyK Sep 7 '10 at 11:22
  • 10
    $\begingroup$ I just put a 100 bounty on this question. I have been trying to solve it for 2 days, with minimal progress, and I'm really frustrated! Is this an open problem or is it known that it has a solution? $\endgroup$ – Matt Calhoun Sep 8 '10 at 15:34
  • 5
    $\begingroup$ One source for this problem is maths.tcd.ie/pub/Maths/ProblemCorner/Problems-15.pdf . Unfortunately this is in Set 15, and solutions are posted only through Set 9. $\endgroup$ – Noam D. Elkies Jul 13 '14 at 2:03
  • 3
    $\begingroup$ A few hours ago I had a talk about your problem with a consultant of my habilitation thesis, Taras Banakh (CV, MO, papers). He dealt with similar problems and got interested in yours, so we are going to attack it. $\endgroup$ – Alex Ravsky Feb 4 at 20:12
16
$\begingroup$

A weaker statement, where we allow elements in $T$ to be repeated, can be proved as below:

Since we can look at the set $\{-s | s\in S \}$ we may assume there are at most $7$ positive numbers in $S$. Let each positive number be a vertex, from each vertex $s$ we draw an arrow to any vertex $a$ such that $s=a+b$. Since if $s>0$, one of $a,b$ must be positive, there is at least one arrow from any vertex. So there must be a cycle $s_1,\cdots,s_n=s_1$ with $n\leq 8$. We can let $T$ consists of $s_i-s_{i+1}$, $1\leq i\leq n-1$.

$\endgroup$
  • 1
    $\begingroup$ Why would $-s_{i+1}$ be contained in $S$ just because $n_{i+1}$ is? And why would they add to zero, if you don't regard the other summand at all? $\endgroup$ – MvG Jul 9 '14 at 14:57
5
+250
$\begingroup$

I started to write a short note devoted to the problem. Its current version is here. I introduced the following general framework for it.

Let $S$ be a subset of an abelian group. The set $S$ is called decomposable, provided each its element $a$ is decomposable, that is there exist $b,c\in S$ with $a=b+c$. Clearly, $S$ is decomposable iff $S\subset S+S$. Let $z(S)$ be the smallest size of a non-empty subset $T$ of $S$ such that $\sum T=0$, and $z(S)=\infty$, otherwise. Given a natural number $n$ put $$z(n)=\sup\{z(S): S\subset S+S\subset\mathbb R, |S|=n\},$$ that is $z(n)$ is the smallest number $m$ such that any decomposable set of $n$ real numbers has a non-empty subset $T$ of size $m$ such that $\sum T=0$.

In the above terms, your question asks to show that $z(S)\le 7$ for any decomposable set $S$ consisting of $15$ integer numbers and Gjergji Zaimi’s question asks whether $z(n)$ is finite (in another words, whether $z(n)\le n$) for each natural $n$.

I think that the proposed approaches were not successful because they don't fully exploit structure of decomposable sets. This concerns even so promising approaches as the search for cycles by curious and the summation by Hsien-Chih Chang 張顯之. In particular, these approaches don't assure that found zero-sum sequences consist of distinct elements. We shall study decomposable sets in the note.

Newertheless, our main result is the following

Proposition 3. For any $n\ge 2$, $z(n)\ge \left\lfloor\tfrac n2\right\rfloor$.

Proof. Given a natural number $k$ put $A=\{1,2,\dots, 2^{k-1}\}$ and $S=A\cup (A-(2^k-1))$. Then $|S|=2k$. The set $S$ is decomposable, because, clearly, each number but $1$ of the set $A$ is decomposable, $1=2^{k-1}+(2^{k-1}-(2^k-1))$, $2^l-(2^k-1)=2^{l-1}+(2^{l-1}-(2^k-1))$ for each $l=1,\dots, k-1$, and $1-(2^k-1)=(2^{k-1}-(2^k-1))+(2^{k-1}-(2^k-1))$.

Let $T$ be a subset of $S$ with $|T|\le k-1$ and $\sum T=0$. Then clearly $k\ge 3$ and $T$ contains at most $k-2$ positive elements. Since all of them are distinct elements of $A$, their sum is at most $2^k-2$. On the other hand, the biggest negative element of the set $A-(2^k-1)$ is $-2^{k-1}+1=-(2^k-2)/2$. Thus if $T$ contains at least two negative elements then $\sum T<0$. If $T$ contains exactly one negative element then $\sum T=0$ implies that we have a representation of $2^k-1$ as a sum of at most $k-1$ powers of $2$. with at most one power used twice. This representation collapses to a sum of at most $k-1$ distinct powers of $2$. If the representation contains a power $2^l$ with $l\ge k$ then it is bigger than $2^k-1$. Otherwise the sum is at most $2^1+2^2+\dots +2^{k-1}=2^k-2<2^k-1$. Thus $z(S)\ge k$.

A set $\{-1,0,1\}$ witnesses that $z(3)\ge 1$. To construct a decomposable set of size $2k+1$ for $k\ge 2$ put $S^+=S\cup \{2(-2^k+2)\}$. Since the set $S$ is decomposable and $-2^k+2\in S$, the set $S^+$ is decomposable too. Similarly to the above we can show that $z(S^+)\ge k$. The new case is when $T$ contains exactly one negative element $2(-2^k+2)$. Then $\sum T=0$ implies that we have a representation of $2(-2^k+2)$ as a sum of at most $k-1$ powers of $2$. not bigger than $2^{k-1}$ with at most one power used twice. This sum is at most $2^2+2^3+\dots +2^{k-1}+2^{k-1}=2^k-4+2^{k-1}<2(2^k-2).$ $\square$

We conjecture that the lower bound in Proposition 3 is tight. This conjecture is confirmed for small $n$ by the problem from your question and in the note we proved it for $n\le 5$. I’m going to finish there my draft proofs that the conjecture also holds for $n=6$ and $7$. Of course, this is not a big deal, but Tao Te Ching teaches that a journey of a thousand miles begins with a single step, so let's start. I hope that we’ll be able to continue the journey.

Update. Taras Banakh proved that any finite decomposable subset of an Abelian group contains two non-empty subsets $A$ and $B$ of $S$ such that $\sum A+\sum B=0$. On the other had, I found that a counterpart of Proposition 3 does not hold for Abelian groups. Namely, given a natural number $n$ let $S=\{1,2,\dots, 2^{n-1}\}$ be a subset of a group $\Bbb Z_{2^n-1}$. Since $2^i+2^i=2^{i+1}$ for each $0\le i\le n-2$ and $2^{n-1}+2^{n-1}\equiv 1\pmod {2^n-1}$, the set $S$ is decomposable. On the other hand, for any proper non-empty subset $T$ of $S$ we have $\sum T\equiv t\pmod {2^n-1}$ for some $0<t<2^n-1$, so $\sum T\not\equiv 0\pmod {2^n-1}$. These results are in our paper, which I am preparing to a submission to arXiv. So I’ll going to provide here a link to it soon.

$\endgroup$
0
$\begingroup$

This is not intended as an answer, but clearly is too long for comments.

Here are some approaches I have been playing around with; I would appreciate any comments, advice, or suggestions.

Clearly the condition si = sj + sk is the key thing about this problem. It seems like in order to state this as a problem (instead of as a conjecture), it must have been solved by someone, otherwise where does |T| $\leq$ 7 come from? Since we don't know for sure if the problem has been solved, I am assuming that |T| $\leq$ 7 is possibly wrong and just trying to work out the consequences of the condition.

This condition is very constrictive, and it's consequences are not at all readily apparent. One question I have is, how many independent elements can a set which satisfies the condition have? The idea of an independent element is not rigorous for a set like this, but the idea is to figure out how to formulate the idea of independent element so it is rigorous. Given a set of integers H, with |H| less than 15, is it possible to add numbers (by combining elements of H) so that H has 15 elements and satisfies the condition; if so, can we say something about the original size of H?

In this direction I have made the following (slightly trivial) observations:

A set which satisfies the condition contains:

  • at least two (distinct) positive numbers
  • at least two (distinct) negative numbers
  • at least two (distinct) numbers which are the sum of a positive and a negative number

This follows from the fact that each such set will contain a largest positive number which must be the sum of only positive numbers (similarly for negative); and the smallest positive number must be the sum of a positive and negative (similar for smallest negative number). I'm not sure how this relates to the (poorly defined) notion of "independent element", but it feels like a start in that direction.

Another idea is that the condition si = sj + sk can be "unpacked" by applying it recursively to sj and sk. My hope is that I can show that there will always be one element which can be "unpacked" so that it is equal to 8 elements in S, one of which is itself. This would of course show that the sum of the other 7 is zero.

si = sj + sk

= sl + sm + sn + sp

= sq + sr + ss + st + su + sv + sw + si

The next idea is to show that any set satisfying the condition will contain what I call a "7 cycle", which is inspired from the totally anti-symmetric unit tensor. A "7 cycle" is a kind of symmetry for the index's of si = sj + sk, I will just write down what a 7 cycle looks like, because that is more clear than explaining it.

s1 = s2 + s3

s2 = s3 + s4

s3 = s4 + s5

s4 = s5 + s6

s5 = s6 + s7

s6 = s7 + s1

s7 = s1 + s2

If it's possible to show that any set satisfying the condition contains a 7 cycle, then it's clear that the sum of s1...s7 will be zero (since it is equal to twice itself).

Another idea is a combinatorial graph theory approach. Clearly, a set satisfying the condition generates a directed graph (as pointed out in the MO link). For clarity, each number in S corresponds to a vertex, and if for example, s1 = s2 + s3, then there will be edges directed from s2 to s1 and from s3 to s1.

A question I have which I can't seem to make progress on, is: what is the minimum possible number of vertex's which have outgoing edges? (a vertex has an outgoing edge if it can be added to an element of S to obtain another element of S, also the assumptions used in the previously given "weaker statement" led to the conclusion that each vertex has an outgoing edge, and this was used to show |T| $\leq$ 7). My hope is that once I know the minimum number of vertex's with outgoing edges, I can use some sort of combinatorial reasoning to show that there will be a closed cycle with a maximum length.

Googling "zero sum subset" quickly leads to references for the EGZ theorem, and by thinking about the problem backwards, it makes sense that since this is one of the best known results for zero sum problems; that if this problem has already been solved this result might be involved in the solution somehow. I can't quite wrap my head around exactly how it will be involved, but since it is a result dealing with the integers mod N, the idea would be to somehow show that the condition forces some (possibly elaborate) modular arithmetic structure on the set S which satisfies it. (my understanding is that EGZ says that given an arbitrary set of 2n - 1 integers in $\mathbb{Z}$ mod n, there will be a subset of n elements whose sum is congruent to 0 mod n)

Yet another idea is to reformulate the problem in terms of polynomials. Given a set S which satisfies the condition, consider the 15th degree polynomial whose roots are the elements of S. Then these roots possess the symmetry that every root is the sum of two other roots; these types of polynomials might have some property which forces the sum of at most 7 elements to be zero.

I don't feel strongly that any of these approaches will ultimately prove successful, but hopefully by making this post I can help keep this question alive and inspire others to work on it.

$\endgroup$
-2
$\begingroup$

In computer science, the subset sum problem is an important decision problem in complexity theory and cryptography. There are several equivalent formulations of the problem. One of them is: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {\displaystyle {-7,-3,-2,5,8}} {\displaystyle {-7,-3,-2,5,8}}, the answer is yes because the subset {\displaystyle {-3,-2,5}} {\displaystyle {-3,-2,5}} sums to zero. The problem is NP-complete, meaning roughly that while it is easy to confirm whether a proposed solution is valid, it may inherently be prohibitively difficult to determine in the first place whether any solution exists.

The problem can be equivalently formulated as: given the integers or natural numbers {\displaystyle w_{1},\ldots ,w_{n}} w_{1},\ldots ,w_{n} does any subset of them sum to precisely {\displaystyle W} W?[1] Subset sum can also be thought of as a special case of the knapsack problem.[2] One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.

The complexity of the subset sum problem can be viewed as depending on two parameters, N, the number of decision variables, and P, the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters N and P mean something different from what they mean in the NP class of problems.)

The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. Thus, the problem is most difficult if N and P are of the same order. It only becomes easy if either N or P becomes very small.

If N (the number of variables) is small, then an exhaustive search for the solution is practical. If P (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.

Efficient algorithms for both small N and small P cases are given below.

There are several ways to solve subset sum in time exponential in {\displaystyle n} n. The most naïve algorithm would be to cycle through all subsets of {\displaystyle n} n numbers and, for every one of them, check if the subset sums to the right number. The running time is of order {\displaystyle O(2^{n}n)} O(2^{n}n), since there are {\displaystyle 2^{n}} 2^{n} subsets and, to check each subset, we need to sum at most {\displaystyle n} n elements.

A better exponential time algorithm is known which runs in time O(2N/2). The algorithm splits arbitrarily the N elements into two sets of N/2 each. For each of these two sets, it stores a list of the sums of all 2N/2 possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time O(2N/2N). However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time O(2k). Thus, each list can be generated in sorted form in time O(2N/2). Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to s in time O(2N/2). To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than s, the algorithm moves to the next element in the first array. If it is less than s, the algorithm moves to the next element in the second array. If two elements with sum s are found, it stops. Horowitz and Sahni first published this algorithm in a technical report in 1974.[3]

The problem can be solved in pseudo-polynomial time using dynamic programming. Suppose the sequence is

x1, ..., xN sorted in the increasing order and we wish to determine if there is a nonempty subset which sums to zero. Define the boolean-valued function Q(i, s) to be the value (true or false) of

"there is a nonempty subset of x1, ..., xi which sums to s". Thus, the solution to the problem "Given a set of integers, is there a non-empty subset whose sum is zero?" is the value of Q(N, 0).

Let A be the sum of the negative values and B the sum of the positive values. Clearly, Q(i, s) = false, if s < A or s > B. So these values do not need to be stored or computed.

Create an array to hold the values Q(i, s) for 1 ≤ i ≤ N and A ≤ s ≤ B.

The array can now be filled in using a simple recursion. Initially, for A ≤ s ≤ B, set

Q(1, s) := (x1 == s) where == is a boolean function that returns true if x1 is equal to s, false otherwise.

Then, for i = 2, …, N, set

Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi), for A ≤ s ≤ B. For each assignment, the values of Q on the right side are already known, either because they were stored in the table for the previous value of i or because Q(i − 1,s − xi) = false if s − xi < A or s − xi > B. Therefore, the total number of arithmetic operations is O(N(B − A)). For example, if all the values are O(Nk) for some k, then the time required is O(Nk+2).

This algorithm is easily modified to return the subset with sum 0 if there is one.

The dynamic programming solution has runtime of {\displaystyle O(sN)} O(sN) where {\displaystyle s} s is the sum we want to find in set of {\displaystyle N} N numbers. This solution does not count as polynomial time in complexity theory because B − A is not polynomial in the size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of A and B, which are exponential in their numbers of bits.

For the case that each xi is positive and bounded by a fixed constant C, Pisinger found a linear time algorithm having time complexity O(NC) (note that this is for the version of the problem where the target sum is not necessarily zero, otherwise the problem would be trivial).[4] In 2015, Koiliaris and Xu found the {\displaystyle {\tilde {O}}(s{\sqrt {N}})} {\tilde {O}}(s{\sqrt {N}}) algorithm for the subset sum problem where {\displaystyle s} s is the sum we need to find.[5]

$\endgroup$
  • $\begingroup$ I have several remarks concerning this answer. First of all, it looks as a copy of Wikipedia article related to Subset sum problem, but the author was too lazy even to put formulae into TEX environment. $\endgroup$ – Alex Ravsky Feb 6 at 21:08
  • $\begingroup$ Concerning the mathematical side, Subset sum problem is well-known to me and it is not relevant to the original question because it does prove nothing, but instead ask whether a given set contains a subset with given sum. So, it is a computer science question to find a deciding algorithm and about its computational complexity (which is, in general, NP-hard). $\endgroup$ – Alex Ravsky Feb 6 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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