Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
7  
ok here it is: {1,-2,3,-4,-5,-6,7,8,9} –  Hsien-Chih Chang 張顯之 Mar 2 '10 at 15:29
4  
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
3  
Irresponsibly random comment: Have you tried using difference sets? –  Sonia Balagopalan Mar 2 '10 at 16:52
3  
@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
6  
@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
show 4 more comments

6 Answers 6

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
How do you write 1 as a sum of two positive integers? –  Jonah Ostroff Mar 2 '10 at 16:54
1  
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
add comment

For every finite set of real numbers, $S =\{a_1,a_2,...,a_n\}$ which satisfies the condition of the problem, 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 that if $a_i \in S $ then $ 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$. Clearly, the existence of a closed cycle in $G_s$ with no repeat edges corresponds to a zero sum subset of $S$.

A useful fact, which I refer to as the "vertex replacement trick", is that if $V_i \rightarrow(E_j)\rightarrow V_k$, then by the defining property of $S$, we also have $V_j \rightarrow(E_i)\rightarrow V_k$.

I will say that a path $P$ is "well behaved" if no index of $S$ appears more than once in $P$, unless it occurs in an adjacent vertex/edge pair of the form $ \cdots \rightarrow V_i \rightarrow (E_i) \rightarrow \cdots$

Choose an arbitrary vertex $V_a \in G_S$, and choose an arbitrary incoming edge to $V_a$, say $E_b$. Then the initial path is:

$$P=V_c \rightarrow (E_b) \rightarrow V_a $$

Unless $0 \in S$, then every possible initial path is well behaved.

Add one vertex/edge pair to $P$, if $P$ is still well behaved then repeat until it is not. Due to the defining property of $S$, it's always possible to find another vertex to add to any given path, and since $S$ is finite, this process must eventually terminate.

$Claim:$ If $P$ is well behaved, but $P'=V_y \rightarrow (E_x) \rightarrow P$ is not, then $P'$ either contains a closed cycle with no repeat edges, or it can be transformed into one that does by applying the vertex replacement trick.

$Proof:$ If the index $x$ does not appear in $P$ but $y$ does, then we can use the vertex replacement trick to ensure that $V_y \in P$, and thus obtain a closed cycle, which by virtue of $P$ being well behaved, is guaranteed to have no repeat edges:

$$V_y \rightarrow E_x \rightarrow \cdots \rightarrow V_y$$

If the index $y$ does not appear in $P$ but $x$ does, then similarly, we use the vertex replacement trick to obtain:

$$V_x \rightarrow E_y \rightarrow \cdots \rightarrow V_x$$

In the case that $x=y$, we obtain:

$$V_x \rightarrow E_x \rightarrow \cdots \rightarrow V_x$$

Otherwise, in the case that the indices $x$ and $y$ both appear in $P$, choose the element with index of $x$ or $y$ which occurs first in $P$, and if that element is an edge, turn it into a vertex using the trick. Then remove all the elements of $P$ which occur after that vertex, and return to one of the previous cases where only one of the indices appears in $P$.

EDIT: This is a massive update/rewrite of an unfinished answer of mine from years ago. My apologies if this makes the old comments no longer relevant.

share|improve this answer
    
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
2  
I am confused. When you say that an index "appears in a path", you mean either in an edge or a vertex, right? But the first case of your proof (if $y$ appears in $p$ but $x$ does not) only works if $V_y \in P$, not if $E_y \in P$. Same issue with the second case not seeming to work if $E_x \in P$. –  David Speyer Jun 10 at 12:50
3  
@DavidSpeyer thank you for checking this. I believe you have pointed out a serious mistake in my solution, and I will update the answer again if I can find a way past a case like the one you mention. –  Matt Calhoun Jun 10 at 19:36
show 3 more comments

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

share|improve this answer
    
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
5  
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
add 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}

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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