80
$\begingroup$

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.

$\endgroup$
12
  • 3
    $\begingroup$ Can you give an example of such a set not containing zero? $\endgroup$ Mar 2, 2010 at 15:07
  • 13
    $\begingroup$ ok here it is: {1,-2,3,-4,-5,-6,7,8,9} $\endgroup$ Mar 2, 2010 at 15:29
  • 4
    $\begingroup$ 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? $\endgroup$ Mar 2, 2010 at 16:37
  • 4
    $\begingroup$ @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.) $\endgroup$ Mar 2, 2010 at 18:10
  • 8
    $\begingroup$ @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). $\endgroup$ Mar 4, 2010 at 14:29

10 Answers 10

27
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ That's great news! I can't wait to read the paper. Two comments: 1) Do you know if your methods can be extended to say something about the Caccetta-Häggkvist conjecture mentioned in another answer? 2) I think I originally heard of this problem on the old mathlinks forum. If my memory serves correct the author was Vesselin Dimitrov. $\endgroup$ Jan 8, 2021 at 8:09
  • 2
    $\begingroup$ Mathlinks was the forum that was eventually turned into artofproblemsolving. I was able to do some digging and found the post where I first saw this: artofproblemsolving.com/community/u866h5999p20253 apparently the original question included the extra assumption that each element can be written as the sum of two others in a unique way up to order. When I posted this question on MO some years later I must have forgotten that extra condition. $\endgroup$ Jan 8, 2021 at 9:01
  • 1
    $\begingroup$ @GjergjiZaimi: thanks for researching the matter. Missing the uniqueness condition explains the things! $\endgroup$
    – Seva
    Jan 8, 2021 at 9:28
  • 2
    $\begingroup$ @Seva your lovely proof seems too long for a comment (I tried), but short enough for an answer (actually it is shorter than an average MO-answer). That's why I posted it as a separate answer. Feel free to incorporate it here. Congratulations again! $\endgroup$ Jan 8, 2021 at 9:51
  • 1
    $\begingroup$ @GjergjiZaimi did you ask Vesselin which solution did he have in mind (if any)? $\endgroup$ Jan 8, 2021 at 12:17
18
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Erm... You do not control the multiplicity of $x$, so you've made plenty of $x\mapsto y$ replacements. Thus, once you know that the coefficient of $y$ in the sum of $\ell_a'$ is, say $0$, it merely means that the original coefficients in the sum at $x$ and $y$ in the sum of $\ell_a$ are $N$ and $-N$ for some (possibly rather large) $N$. If you add $N\ell_x$, you screw up $z$ now. So, you want to bound the number of replacements and then they should be $z$ to something in your notation. Can you fix it? $\endgroup$
    – fedja
    Jan 8, 2021 at 14:56
  • $\begingroup$ @fedja The coefficient of $y$ is at least -1 (we have one linear form with coefficient -1, in other forms it is non-negative). The coefficient of $x$ is non-negative. The sum of coefficients of $x$ and $y$ is 1. Not so many possibilities. $\endgroup$ Jan 8, 2021 at 15:03
  • $\begingroup$ Ah, yes. Stupid me: I haven't realized it was a pure sum of forms (coefficients 1 and 0 only, not arbitrary non-negative integers). Seems to work then. Thank you! :-) $\endgroup$
    – fedja
    Jan 8, 2021 at 15:17
  • 1
    $\begingroup$ Thank you for writing the proof here in a self contained manner! $\endgroup$ Jan 8, 2021 at 21:18
17
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Isn't the Lemma you prove trivial? The comments already reduce to the case that all $a_i$'s are rational. Clearly $S \subseteq S+S$ implies $S$ contains a negative rational $x$ and a positive rational $y$. Then you have $nx+my = 0$ for some $n,m \ge 1$. $\endgroup$ Aug 20, 2020 at 1:41
11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ How do you write 1 as a sum of two positive integers? $\endgroup$ Mar 2, 2010 at 16:54
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 2, 2010 at 16:55
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Wlog
    Mar 2, 2010 at 18:15
  • $\begingroup$ 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 $\endgroup$ Mar 2, 2010 at 19:14
  • 5
    $\begingroup$ Or just take all the positive rationals :). The finiteness is crucial here as for infinite sets the conditions impose almost no restrictions. $\endgroup$ Mar 2, 2010 at 19:54
  • $\begingroup$ 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). $\endgroup$ Mar 24, 2010 at 7:54
  • $\begingroup$ 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. $\endgroup$
    – Wlog
    Mar 24, 2010 at 19:30
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Sep 17, 2010 at 16:30
  • $\begingroup$ 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... $\endgroup$ Sep 17, 2010 at 17:51
  • $\begingroup$ 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. $\endgroup$ Sep 17, 2010 at 22:50
  • 2
    $\begingroup$ 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$. $\endgroup$ Jun 10, 2014 at 12:50
  • 3
    $\begingroup$ @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. $\endgroup$
    – user49545
    Jun 10, 2014 at 19:36
1
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ So, what the bottom line is? Do you have a solution to Problem 1? Can you construct a decomposible, but zero-sum-free set in whatever abelian group? $\endgroup$
    – Seva
    Jul 31, 2020 at 19:07
  • 1
    $\begingroup$ @Seva No we do not have the complete solution to Problem 1. Everything we know is written in my answer above. $\endgroup$ Jul 31, 2020 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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