# Existence of a zero-sum subset

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:

Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, a_n\}$, with the property that for each $i$ there exist $j,k$ (not necessarily distinct) so that $a_i=a_j+a_k$ (i.e. every element in $S$ can be written as a sum of two elements in $S$, note that this condition is trivially satisfied if $0\in S$ as then every $x\in S$ can be written as $x+0$).

Must there exist $\{i_1,i_2,\dots, i_m\}$ (distinct) so that $a_{i_1}+a_{i_2}+\cdots +a_{i_m}=0$?

ETA: A possible reformulation can be made in terms of graphs. We can take the vertex set $\{1,\dots ,n\}$ and for each equation $a_i=a_j+a_k$ in S add an edge $[ij]$ and its "dual" $[ik]$. The idea is to find a cycle in this graph, whose dual is a matching.

-
ok here it is: {1,-2,3,-4,-5,-6,7,8,9} –  Hsien-Chih Chang 張顯之 Mar 2 '10 at 15:29
Can we show that if there is a counterexample, then there is a counterexample in integers? Or is there a possibility for a minimal example not all commensurable? –  Gerald Edgar Mar 2 '10 at 16:37
Irresponsibly random comment: Have you tried using difference sets? –  Sonia Balagopalan Mar 2 '10 at 16:52
@Gerald, pick from S a base /Q, replace its elements with rationals with different large primes as denominators, then recreate the set by transplanting the rational linear relations on the new generators. (The primes you want to use may have to exceed any that appear in numerators or denominators of sums of different coefficients that appear in the relations - but there is only a finite number of such sums.) –  Yaakov Baruch Mar 2 '10 at 18:10
@Gerald: Another way of seeing this is that the conditions $a_i = a_j + a_k$ restrict the vector $(a_1, \dots, a_n)$ to a linear subspace $L$ of $\mathbb{R}^n$. There are only $2^n-1$ conditions that a sum be 0, so each one is a hyperplane. If there is no solution then each such hyperplane intersected with $L$ is a hyperplane in that subspace. But the finite union of hyperplanes can't be the whole space, so there is some point with rational coordinates (since a hyperplane is closed -- the remaining set is open). –  Victor Miller Mar 4 '10 at 14:29

A weaker result can be obtained if we do not require the solution set to be distinct:

Lemma. There exist $i_1, \ldots, i_m$ (not necessary distinct) so that $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$.

proof. Consider the sum of all the equations $a_i=b_i+c_i$ over all $a_i \in S$, where $b_i,c_i \in S$ guaranteed by the definition of $S$, we have

$\sum_i a_i = \sum_i (b_i+c_i)$.

Noticed that the multiset {$b_i,c_i$} must contain all elements in $S$, otherwise we can remove the elements in $S \setminus$ {$b_i,c_i$}, obtaining another $S^*$ which satisfies the property.

Now since $S \subseteq$ {$b_i,c_i$}, we cancel out $\sum_i a_i$ with the same numbers in {$b_i,c_i$}, which makes the equality the form $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$ with $a_{i_k} \in$ {$b_i,c_i$}, i.e. $a_{i_k} \in S$. Since there are totally $2|S|$ elements in multiset {$b_i,c_i$} and $0 \notin S$, we have the lemma. $\square$

-- Edited at 2010/03/07 --

This conjecture is related to a special case of the Rainbow conjecture, which is highly related to the Caccetta-Häggkvist conjecture; see a survey by Sullivan.

For a digraph $G$ and edge sets $E_1, \ldots, E_k \subseteq E(G)$, denote $G_i = (V(G), E_i)$ and we say a subgraph $H$ of $G$ is rainbow if $|E(H) \cap E_i| \leq 1$ for each $i$ and $|E(H)| \geq 1$. Let $\delta_i^+(v)$ denote the outdegree of $v$ in graph $G_i$.

The Rainbow conjecture states that,

Conjecture. For a simple digraph $G$, either

• There is a rainbow (di)cycle in $G$, or
• There exists a node $v$ s.t. |{$w|\exists \text{ rainbow path from } v \rightarrow w$}| $\geq \sum_{i=1}^k \delta^{+}_{i}(v)$.

Now by constructing a digraph $G$ with directed edge $(u,v)$ in $E_w$ if $u+w = v$, there is a dicycle in $G$ iff there is a set $U$ s.t. $\sum_{x\in U} x = 0$, for $x \in S$. Since the second condition of the Rainbow conjecture can not be satisfied for $k=|S|$ and $\delta_{i}^+(v) \geq 1$ for all $i$$^@$, there must be a dicycle in $G$ with distinct colors, that is, a subset $U$ with distinct numbers.

@ The condition $\delta_{i}^+(v) \geq 1$ is wrong.

In the survey by Sullivan, the conjecture is solved for the special case that $\delta_{i}^+(v) \leq 1$ for all $v$ and all $i$, which is the case since for a given $u$ and $w$, there is at most one solution to the equation $u+v=w$, which corresponds to the directed edge $(u,v) \in E_w$.

-

I find this question intriguing. Here's one way to recast it as an integer linear programming question:

Let $M$ be a non-negative $n \times n$ integer matrix with all column sums equal to 2. Is there necessarily a vector with entries 0's and 1's in the image $V$ of $M - I$ (as a linear transformation on $\mathbb R^n$)?

Given a matrix $M$, you can form the quotient group $\mathbb Z^n / V$. Since it's a free abelian group, it can be embedded in $\mathbb R$, giving the setup as stated. Conversely, if there's a collection of real numbers satisfying equations as described, you can think of it as defining an endomorphism of the free abelian group generated by the designated vectors.

There's more I could say, but since this question is so old, I may mull it over a little longer and then post a rephrased version as a followup question. The kinds of people who see a relationship to their expertise may be different.

-

Perhaps I misunderstand the question, but isn't $S$={$1,2, \ldots n$} a counterexample? Thanks for the comments below.

Edit: I still haven't solved the problem, but I managed to translate the problem to a graph theory problem. Let $S$={$a_1, \dots, a_n$} be a minimum size counterexample. Construct a graph $G$ with vertex set $[n]$ and edge set as follows. For each $i, j \in [n]$ put an edge with label $k$ between $i$ and $j$ if $a_k=a_i+a_j$. Note, that $G$ may include loops. The graph $G$ satisfies the following conditions

1. The set of edge-labels is equal to $[n]$ (by hypothesis),
2. No vertex $i$ is incident to an edge with edge-label $i$ (else $0 \in S$),
3. No vertex $i$ is of degree 0 (else $S - a_i$ is a smaller counterexample).

Conjecture: Let $G$ be a graph satisfying (1),(2), and (3). Then there exists a subset $A$ of edges of $G$ such that

(a) the set of vertices of $G[A]$ (the subgraph induced by $A$) contains the set of edge-labels of $G[A]$

(b) $G[A]$ has maximum degree 2,

(c) each vertex of $G[A]$ which is not an edge-label of $G[A]$ has degree 1 in $G[A]$.

If such a set exists, then $S$ contains a zero-sum set. The zero-sum set is just the set indexed by the vertices of $G[A]$ which aren't edge-labels of $G[A]$ together with the degree 2 vertices of $G[A]$. I am guessing that the above conjecture is false, since it does not use any properties of the real numbers. In particular, it would imply that the original problem is true for any field.

-
How do you write 1 as a sum of two positive integers? –  Jonah Ostroff Mar 2 '10 at 16:54
here 1 can not be written as a sum of two elements from the set. If the set doesn't contain 0 then one can show that it must have at least two positive and at least two negative elements. –  Gjergji Zaimi Mar 2 '10 at 16:55
True, thanks for clarifying. –  Tony Huynh Mar 2 '10 at 16:55

I also do not have a solution to the question as posed.

I am going to try to relax the finite condition, I believe I can find an infinte set A such that it does not have a zero subsum with distinct elements.

Let A = {1, -2, 3, -5, 8, -13, ... }.

More formally $a_n = a_{n-2} - a_{n-1}$, forming an alternating Fibonacci sequence. Thus, for any $a_k \in A$, $a_k = a_{k+1} + a_{k+2}$.

This appears to work for the sum of any subset of A, except the sum of A itself, which approaches 0. This is fine if you are only looking for a finite subset, as the notation indicates to me.

I hope this helps, since it tells me that the infinite condition is important for being able to write any element as a sum of two other.

It does allow me to form a finite set with the property if I attach 0 to A and cut it off somewhere, and there don't seem to be any non-trivial solutions to the second requirement, but it does not form a counter example to the question as stated (as would any set that contains 0).

-
I am not keen on how to show that the alternating Fibonacci sequence sums to 0, but is it so that if my set was {3, -5, 8, -13, ...}, that I would not have any zero-subsums? –  Wlog Mar 2 '10 at 18:15
Going back to the original question, one also has 1/(2^i) for all integers i > j for some integer j as an infinite example of a positive subset of reals that has the representation property. If you prefer distinct members in the decomposition, something like Cantor rationals (2^j/3^k for 0<=j<=k) should also work. Gerhard "Ask Me About System Design" Paseman, 2010.03.02 –  Gerhard Paseman Mar 2 '10 at 19:14
Or just take all the positive rationals :). The finiteness is crucial here as for infinite sets the conditions impose almost no restrictions. –  Gjergji Zaimi Mar 2 '10 at 19:54
How can the sum of A approach zero?! If a discrete sequence approaches zero, then it is eventually zero. By the way, to prove your alternating Fibonacci doesn't contain a zero-sum subset S, let a(n) be the element of S that has the greatest absolute value. Then prove by induction that |a(n)|=|1+a(n-1)+a(n-3)+a(n-5)+...|. So even if S contains every element a(k) of the opposite sign to a(n) and |a(k)|<a(n)|, the sign of the sum(S) will be the same as a(n). –  Douglas S. Stones Mar 24 '10 at 7:54
Just a little bit more rep and I can post my sophomoric answers as comments instead of taking up so much screen real estate with them. I was working off of the memory of this web page when I was summing the sequence: milan.milanovic.org/math/english/alternating/alternating.html Even though I admit I had a huge blind spot in regard to GZ's comment, I still prefer this a construction like this as each element can be written as a unique sum of two other elements. –  Wlog Mar 24 '10 at 19:30

For every finite set of real numbers, $S =${$a_1,a_2,...,a_n$}, which satisfies the condition of the problem, that every element of $S$ can be written as the sum of two elements, each of which is in $S$ but not necessarily distinct, there corresponds a directed graph $G_S$ with the following construction:

Each element of $S$ is associated with a vertex in $G_S$, according to the rule $a_i \in S \rightarrow V_i \in G_S$. A vertex $V_i \in G_S$ is connected to another vertex $V_k \in G_S$ by an edge $E_j$ if and only if $a_i + a_j = a_k$. This notation for the edges reflects a special property of the directed graph $G_S$, namely that each edge of this graph is associated with an element of $S$.

A useful fact is that the number of times the edge $E_i$ appears on the graph is equal to the number of outgoing edges originating at the vertex $V_i$. This follows simply from the observation that if $a_i + a_j = a_k$, then we have both $V_i \rightarrow(E_j)\rightarrow V_k$ and $V_j \rightarrow(E_i)\rightarrow V_k$.

(The notation $V_i \rightarrow(E_j)\rightarrow V_k$ indicates that there is an edge $E_j$ directed from the vertex $V_i$ to the vertex $V_k$)

The basic idea of the solution is as follows: we will choose an arbitrary vertex $V_i \in G_S$ and construct a path $P$ which leads to $V_i$. The construction of this path is such that it will contain no repeated edges; furthermore, we will be able to continue to add vertex's to this path until we find a closed cycle. It's clear that a closed cycle in $G_S$ with no repeat edges corresponds to zero sum subset in $S$. (the sum over the numbers associated with these edges is zero)

Choose an arbitrary vertex $V_i \in G_S$. Since every vertex has at least one incoming edge, there is some vertex $V_j$ which has an outgoing edge, say $E_k$ which connects to $V_i$. So the initial path is $P = V_j \rightarrow(E_k)\rightarrow V_i$.

We will now begin adding one vertex to the path at a time, and checking for repeated edges. It will of course always be possible to find another vertex to add to the path, since every vertex in $G_S$ has at least one incoming edge.

Let's assume that we have been adding vertex's to our path $P$ with no repeated edges occurring, but then we add one more vertex, say $V_x$, and it's connecting edge is a repeat, say $E_l$. We can eliminate either one or both occurrences of the repeated edge by inserting the vertex associated with that edge into the path. This is illustrated below:

Suppose,

$P = V_x \rightarrow(E_l)\rightarrow ... V_r \rightarrow(E_l)\rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

We can eliminate one or both occurrences of the edge $E_l$ by inserting $V_l$ into the path, connecting it to either the vertex which the first occurrence of the repeated edge connects to, or else connecting it to the vertex for which the second occurrence of the repeated edge connects to, and deleting the portions of the path which occur before the insertion. In other words, the path $P$ can become:

$P = V_l \rightarrow(E_r)\rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

If the edge $E_r$ occurs already in the path, then we simply repeat the procedure, this time inserting the vertex $V_r$, and repeat, until the path contains no repeated edges.

If after this procedure is complete, the initial vertex on the path is the same as some other vertex already on the path, then we have found a closed cycle with no repeat edges.

Suppose we add a vertex to the path, say $V_x$, we find that it's outgoing edge, $E_a$, which connects to $V_y$, is repeated, furthermore suppose that the vertex $V_a$ is already part of the path, but the edge $E_x$ is not. In this case we have found a closed cycle with no repeat edges, because from $a_x + a_a = a_y$, we have $V_a \rightarrow(E_x)\rightarrow V_y$.

It might happen during the application of this procedure for constructing the path $P$, that we arrive at a cycle which alternates between 2 fixed paths; this is illustrated below:

after M iterations:

$P_M = V_x \rightarrow ... V_r \rightarrow ... \rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

After M+K iterations:

$P_{M+K} = V_y \rightarrow ... V_q \rightarrow ... \rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

and so on...

In this expression, $(V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i)$ represents the same path, while $(V_x \rightarrow ... V_r \rightarrow ...)$ and $(V_y \rightarrow ... V_q \rightarrow ...)$ represent different paths.

In order for what I call an "alternating path cycle" like this to occur, two things must be true:

• each time we add a vertex to the path, we do so in a way such that we choose the same sequence of incoming edges and vertex's for each iteration of the alternating path cycle.

• one of the vertex's appearing in one of the paths has it's corresponding edge occur twice in the other path.

The fact that an edge occurs twice in one of the paths indicates that the vertex corresponding to this edge has multiple outgoing edges, leading to different vertex's. This means that for any alternating path cycle, we will always be able to escape from the cycle by choosing a different sequence of vertex's and edges to add to the path, as illustrated below:

Suppose $P_M$ and $P_{M+K}$ are two paths which constitute the "end points" an alternating path cycle. If $V_a$ appears in path $P_M$, while edge $E_a$ occurs twice in path $P_{M+K}$; then we have a choice of two different points along the path $P_{M+K}$ for which to insert the vertex $V_a$; therefore, we are not forced to choose the same sequence of edges and vertex's to add to the path $P$, and so we violate the first condition for an alternating path cycle to occur.

And so we see that we will always be able to add another vertex's to the path $P$ which leads to our arbitrarily chosen initial vertex $V_i$; and since we can add an infinite number of vertex's to the path (one at a time) with this procedure, and the total number of available vertex's is finite, we will eventually add a repeated vertex to the path; since this path has no repeat edges by construction, this closed cycle it contains has no repeat edges, and the sum along the edges of this closed cycle is a zero sum subset of $S$.

I realize that this solution needs to be written up more rigorously. I also realize that it's very likely I have overlooked something or made a big mistake somewhere. The key issue for me is to make sure that I have properly analyzed every case of what can happen when I add one more vertex to the path $P$, to make sure that the statement "...since we can add an infinite number of vertex's to the path (one at a time) with this procedure, and the total number of available vertex's is finite, we will eventually add a repeated vertex to the path." is valid. I think the "alternating path cycle" is one thing that can go wrong, but I'm not convinced this is the only thing that can go wrong.

...

EDIT: I will use this space to respond to comments

@Gjergji: The zero sum subset of S which corresponds to a closed cycle is the sum over the edges of that cycle, so if r=l like you say, we only include in the zero sum subset the number corresponding to that edge, not the vertex; I therefore don't see r=l as a problem, but perhaps I am missing something.

In response to "I don't understand how you get a cycle with different edges...". Could you please identify which parts of my argument you object to/are confused about. It might help you to understand what I am trying to say if you draw the graph for some set S that satisfies the condition and just start constructing a path in the way I outline.

@Gjergji: I really appreciate that you have taken the time to respond twice. I am just an amateur, and I have been working on this problem for awhile, so it means a lot to me. Let me try and explain why I disagree with you about r=l.

Consider the path:

$P = V_x \rightarrow(E_r)\rightarrow V_z ... V_r \rightarrow(E_r)\rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

now I switch $V_x$ with $V_r$ and form a closed cycle where the edge $E_r$ does not appear (the closed cycle terminates immediately before the occurrence of the edge $E_r$.)

$P = V_r \rightarrow(E_x)\rightarrow V_z ... V_r \rightarrow(E_r)\rightarrow V_m \rightarrow...\rightarrow V_j \rightarrow(E_k)\rightarrow V_i$

So the cycle is $V_r \rightarrow(E_x)\rightarrow V_z ... V_r.$

-
There is many things I don't understand in this answer. When you change $V_l\to E_r$ to $V_r\to E_l$, what if $r=l$? In general I don't understand how you get a cycle with different edges, since that is pretty much another way of stating what the problem asks... –  Gjergji Zaimi Sep 16 '10 at 18:30
I understand that the cycle gives you a zero sum subset... I was asking how do you ensure the existence of the cycle. You define a "procedure" and say that you repeat it until the path contains no repeated edges. My question above (what if "r=l") is about the procedure, and shows that even after applying it the path will still have repeated edges. –  Gjergji Zaimi Sep 17 '10 at 14:15
Reply to the new edit: But if $x=r$ as well then what? I just don't think you have given enough reasons for the procedure to terminate. Also, if you can, try to reply in the comment box so the thread doesn't come in the first page after every edit, please. –  Gjergji Zaimi Sep 17 '10 at 16:30
We cannot have x=r because then we would have $a_r + a_r = a_z$ and $a_r + a_r = a_m$; and in this case we conclude $V_z = V_m$, but then we would have already found a closed cycle. I will try to respond in comments from now on. I realize I have not rigorously shown that the cycle will terminate, so I will attempt to reformulate this solution as rigorously as possible when I have some more time to work on it. My hope in posting was that some cases of things which go wrong that had not occurred to me yet might be pointed out... –  Matt Calhoun Sep 17 '10 at 17:51
Another thing that doesn't convince me is that you claim to find a closed path terminating at $V_i$ for every $i$, which is stronger than the statement in the problem (for at least one $i$). I actually think this is false and one of the sets mentioned in the comments above is probably a counterexample, but I haven't checked carefully. –  Gjergji Zaimi Sep 17 '10 at 22:50
show 1 more comment

I haven't got the answer but I do have a set so that no x and -x occur at the same time: {-8, -5, -4,-2, 1, 0.5, 1.5, 2.5, 3} But it is obviously not a counterexample because 0.5+1.5-2=0

(The empty set is a trivial solution to your question but I suppose you meant an non-empty set)

I already proved that every set $A$ with 4 elements (with $\forall a\in A, a\neq0$) must be of the form {-2x, -x, x, 2x}

-