Existence of a zero-sum subset - MathOverflow

Existence of a zero-sum subset

2010-03-02T14:23:56Z

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.

Answer by Ingdas for Existence of a zero-sum subset

2010-03-02T15:48:05Z

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}

Answer by Hsien-Chih Chang for Existence of a zero-sum subset

2010-03-02T16:30:56Z

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

Answer by Tony Huynh for Existence of a zero-sum subset

2010-03-02T16:51:35Z

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

The set of edge-labels is equal to $[n]$ (by hypothesis),
No vertex $i$ is incident to an edge with edge-label $i$ (else $0 \in S$),
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,

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.

Answer by Wlog for Existence of a zero-sum subset

2010-03-02T18:11:17Z

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

Answer by Bill Thurston for Existence of a zero-sum subset

2010-09-13T15:14:43Z

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.

Answer by Matt Calhoun for Existence of a zero-sum subset

2010-09-16T17:22:12Z

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