Existence of a zero-sum subset

Question

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 1

The answer is in the affirmative; indeed,

If $S$ is a finite non-empty subset of any abelian group such that every element of $S$ is a sum of two other (possibly, equal to each other) elements, then $S$ has a non-empty, zero-sum subset.

For a complete proof, see this recent preprint by János Nagy, Péter Pach, and myself. The proof is a little too long to be presented here but at least, to indicate the general direction, here is our main lemma.

Lemma. Suppose that $M$ is an integer square matrix of order $n$, representable as $A-I$ where $A$ has all its elements non-negative and all row sums equal to $2$, and $I$ is the identity matrix. Then there exist nonzero vectors $u,v\in\{0,1\}^n$ such that $M^Tu=v$; that is, there exists a system of rows of $M$ such that their sum is a nonzero, zero-one vector.

In fact, for our purposes it would suffice to have any nonzero vector $u$ satisfying $M^Tu\in\{0,1\}^n$; having $u$ itself to be zero-one is an extra (compare with Bill Thurston's answer above).

The proof of the main lemma is completely elementary, by induction on $n$.

Historically, the question seems to originate from a problem contributed by Dan Schwarz to the EGMO 2012 (European Girls’ Mathematical Olympiad):

Does there exist a set of integers such that every element of the set is a sum of two other elements, while the set does not contain a finite nonempty zero-sum subset?

The answer to this question is positive since the set here is allowed to be infinite.

Answer 2

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 3

The brilliant proof of Seva, János and Péter seems pretty short for me. Here it is.

We prove the following statement which obviously implies the claim.

Let $S$ be a non-empty finite set of variables. Assume that for each $a\in S$ we have a linear form $\ell_a:=b(a)+c(a)-a$ for certain $b(a),c(a)\in S\setminus\{a\}$ (possibly $b(a)=c(a)$). Then there exists a non-empty set $A\subset S$ such that all coefficients of the linear form $\sum_{a\in A}\ell_a$ belong to $\{0,1\}$.

By induction, we may assume that this holds for smaller values of $|S|$.

Consider the multiset $T=\{b(a),c(a):a\in S\}$. We have $|T|=2|S|$. If $T$-multiplicity of every element $x\in S$ equals 2, we have $\sum_{a\in S} \ell_a=\sum_{x\in S} x$, so we may take $A=S$. If $T$-multiplicity of some $x\in S$ equals 0, just remove $x$ from $S$ ($S$ remains non-empty) and apply induction.

It remains to consider the case when $T$-multiplicity of some $z\in S$ equals 1. Say, $z=b(x)$, $\ell_x=z+y-x$ for certain $y\notin \{x,z\}$. Denote $T=S\setminus \{x,z\}$. For $a\in T$ consider the linear form $\ell_a'$, obtained from $\ell_a$ by replacing $x$ by $y$ if necessary (note that if this happens for $\ell_y$, i.e., $\ell_y=x+t-y$, then $\ell_y+\ell_x=z+t$ and we may take $A=\{x,y\}$.) By induction, the sum of several such forms $\ell_a'$ have coefficients 0's and 1's. For the corresponding forms $\ell_a$ this means either what we need, or that the coefficient of $y$ in their sum equals -1 and the coefficient of $x$ equals 1 or 2. In the latter case add $\ell_x$ to their sum.

Answer 4

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 5

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.

Answer 6

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 7

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.

Answer 8

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 9

There is a special version of this question (for $n=15$ and $m\le 7$) at Mathematics.SE. For each $n\ge 2$ I constructed a set $S$ with the property requiring $m\ge \left\lfloor\tfrac n2\right\rfloor=k$. Namely, $$S=A\cup (A-(2^k-1)),$$ where $A=\{1,2,\dots, 2^{k-1}\}$ for even $n$ and $$S= A\cup (A-(2^k-1))\cup \{2(-2^k+2)\}$$ for odd $n\ge 5$, see the proof in my answer. I conjectured that this lower bound for $m$ is tight and proved it for small $n$.

Answer 10

In this preprint (written jointly with Alex Ravsky) we prove the following partial answers to this problem. First some definitions. A non-empty subset $D$ of an Abelian group is called decomposable if $D\subset D+D=\{x+y:x,y\in D\}$. A decomposable set is called minimal decomposable if it contains no proper decomposable subsets. For a subset $Z$ of an Abelian group we put $\sum Z=\sum_{z\in Z}z$.

We consider a generalized version of the problem of Zaimi.

Problem 1. Is it true that every finite decomposable subset $D$ of an Abelian group contains a non-empty subset $Z\subset D$ with $\sum Z=0$?

Let us observe that this problem has affirmative answer for decomposable subsets of Boolean groups. We recall that a group $G$ is Boolean if $x+x=0$ for every $x\in G$.

Trivial Observation. Every decomposable subset $D$ of a Boolean group contains a subset $Z\subset D$ of cardinality $|Z|\in\{1,3\}$ such that $\sum Z=0$.

The following results, proved in this preprint are less trivial.

Theorem 1. Every finite decomposable subset $D$ of an Abelian group contains two non-empty sets $A,B\subset D$ such that $\sum A+\sum B=0$.

Theorem 2. Every decomposable subset $D\subset\mathbb R$ of cardinality $|D|\le 7$ contains a non-empty subset of cardinality $|Z|\le\frac12 |D|$ such that $\sum Z=0$.

Example 1. For every $n\ge 2$ the subset $D_n=\{2^k,2^k-2^n+1:0\le k<n\}$ of the group $\mathbb Z$ is decomposable, has cardinality $|D_n|=2n$ and the subset $Z=\{2-2^n\}\cup\{2^k:0<k<n\}$ of $D_n$ has cardinality $|Z|=n=\frac12|D_n|$ and $\sum Z=0$. On the other hand, every non-empty subset $T\subset D_n$ of cardinality $|T|<n$ has $\sum T\ne 0$.

These results suggest introducing the following characteristic $z(D)$ of a decomposable set $D$.

For a finite subset $D$ of an Abelian group let $z(D)$ be the largest number $n\le|D|+1$ such that every non-empty subset $T\subset S$ of cardinality $|T|<n$ has $\sum T\ne 0$. Therefore, $z(D)$ is equal to the smallest cardinality of a subset $Z\subset D$ with $\sum Z=0$ if such set $Z$ exists and $z(D)=|D|+1$ in the opposite case.

In terms of the function $z(\cdot)$ Problem 1, Theorem 2 and Example 1 can be reformulated as follows.

Problem 1'. Is $z(D)\le|D|$ for any finite decomposable set $D$ in an Abelian group?

Theorem 2'. Every decomposable susbet $D\subset\mathbb R$ of cardinality $|D|\le 7$ has $z(D)\le\frac12|D|$.

Example 1'. For every $n\ge 2$ there exists a subset $D_n\subset \mathbb Z$ of cardinality $|D_n|=2n$ with $z(D_n)=\frac12|S_n|$.

This suggests the following open

Problem 2. Is $z(D)\le \frac12|D|$ for any finite decomposable set $D$ in the group $\mathbb Z$?

The group $\mathbb Z$ is essential in this problem because of the following simple

Example 2. For every $n\ge 2$ the subset $D=\{2^kg:0\le k<n\}$ of a cyclic group of order $2^n-1$ with generator $g$ is decomposable and has $z(D)=n=|D|$.

For $n\in\{4,6\}$ the decomposable set $D_n$ in Example 1 is unique in the following sense.

Proposition 1. For $n\in\{2,3\}$, every decomposable set $D\subset\mathbb R$ of cardinality $|D|=2n$ with $z(D)=\frac12|D|$ is equal to $D_n\cdot r$ for some real number $r$.

This proposition suggests the following

Question. Is every finite decomposable subset $D\in\mathbb Z$ with $n=z(D)=\frac12|D|$ a homothetic copy of the decomposable set $D_n$ from Example 1?

Theorem 1 implies the following

Corollary 1. For every finite decomposable subset $D$ of an Abelian group there exists a function $f:Z\to \{1,2\}$ defined on a non-empty subset $Z\subset D$ such that $\sum_{z\in Z}f(z)\cdot z=0$.

This corollary can be compared with the following fact that can be proved by the argument extracted from the answer of Hsien-Chih Chang.

Proposition 2. For any finite minimal decomposed set $D$ in an Abelian group there exists a function $f:D\to\omega$ into non-negative integers such that $\sum_{x\in D}f(x)=|D|$ and $\sum_{x\in D}f(x)\cdot x=0$.