A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here.

Apparently, this problem is from a mathematics magazine of some university in the United States (sorry, no idea about either).

So the problem is:

Suppose $S \subset \mathbb{Z}$ (set of integers) such that

1) $|S| = 15$

2) $\forall ~s \in S, \exists ~a,b \in S$ such that $s = a+b$

Show that for every such $S$, there is a non-empty subset $T$ of $S$ such that the sum of elements of $T$ is zero and $|T| \leq 7$.

Update (Sep 13)

Here is an approach which seems promising and others might be able to take it ahead perhaps.

If you look at the set as a vector $s$, then there is a matrix $A$ with the main diagonal being all $1$, each row containing exactly one $1$ and one $-1$ (or a single $2$) in the non-diagonal position such that $As = 0$.

The problem becomes equivalent to proving that for any such matrix $A$ the row space of $A$ contains a vector with all zeroes except for a $1$ and $-1$ or a vector with all zeroes except $\leq 7$ ones.

This implies that the numbers in the set $S$ themselves don't matter and we can perhaps replace them with elements from a different field (like say reals, or complex numbers).

A weaker statement, where we allow elements in $T$ to be repeated, can be proved as below:

Since we can look at the set $\{-s | s\in S \}$ we may assume there are at most $7$ positive numbers in $S$. Let each positive number be a vertex, from each vertex $s$ we draw an arrow to any vertex $a$ such that $s=a+b$. Since if $s>0$, one of $a,b$ must be positive, there is at least one arrow from any vertex. So there must be a cycle $s_1,\cdots,s_n=s_1$ with $n\leq 8$. We can let $T$ consists of $s_i-s_{i+1}$, $1\leq i\leq n-1$.

I started to write a short note devoted to the problem. Its current version is here. I introduced the following general framework for it.

Let $S$ be a subset of an abelian group. The set $S$ is called decomposable, provided each its element $a$ is decomposable, that is there exist $b,c\in S$ with $a=b+c$. Clearly, $S$ is decomposable iff $S\subset S+S$. Let $z(S)$ be the smallest size of a non-empty subset $T$ of $S$ such that $\sum T=0$, and $z(S)=\infty$, otherwise. Given a natural number $n$ put $$z(n)=\sup\{z(S): S\subset S+S\subset\mathbb R, |S|=n\},$$ that is $z(n)$ is the smallest number $m$ such that any decomposable set of $n$ real numbers has a non-empty subset $T$ of size $m$ such that $\sum T=0$.

In the above terms, your question asks to show that $z(S)\le 7$ for any decomposable set $S$ consisting of $15$ integer numbers and Gjergji Zaimi’s question asks whether $z(n)$ is finite (in another words, whether $z(n)\le n$) for each natural $n$.

I think that the proposed approaches were not successful because they don't fully exploit structure of decomposable sets. This concerns even so promising approaches as the search for cycles by curious and the summation by Hsien-Chih Chang 張顯之. In particular, these approaches don't assure that found zero-sum sequences consist of distinct elements. We shall study decomposable sets in the note.

Newertheless, our main result is the following

Proposition 3. For any $n\ge 2$, $z(n)\ge \left\lfloor\tfrac n2\right\rfloor$.

Proof. Given a natural number $k$ put $A=\{1,2,\dots, 2^{k-1}\}$ and $S=A\cup (A-(2^k-1))$. Then $|S|=2k$. The set $S$ is decomposable, because, clearly, each number but $1$ of the set $A$ is decomposable, $1=2^{k-1}+(2^{k-1}-(2^k-1))$, $2^l-(2^k-1)=2^{l-1}+(2^{l-1}-(2^k-1))$ for each $l=1,\dots, k-1$, and $1-(2^k-1)=(2^{k-1}-(2^k-1))+(2^{k-1}-(2^k-1))$.

Let $T$ be a subset of $S$ with $|T|\le k-1$ and $\sum T=0$. Then clearly $k\ge 3$ and $T$ contains at most $k-2$ positive elements. Since all of them are distinct elements of $A$, their sum is at most $2^k-2$. On the other hand, the biggest negative element of the set $A-(2^k-1)$ is $-2^{k-1}+1=-(2^k-2)/2$. Thus if $T$ contains at least two negative elements then $\sum T<0$. If $T$ contains exactly one negative element then $\sum T=0$ implies that we have a representation of $2^k-1$ as a sum of at most $k-1$ powers of $2$. with at most one power used twice. This representation collapses to a sum of at most $k-1$ distinct powers of $2$. If the representation contains a power $2^l$ with $l\ge k$ then it is bigger than $2^k-1$. Otherwise the sum is at most $2^1+2^2+\dots +2^{k-1}=2^k-2<2^k-1$. Thus $z(S)\ge k$.

A set $\{-1,0,1\}$ witnesses that $z(3)\ge 1$. To construct a decomposable set of size $2k+1$ for $k\ge 2$ put $S^+=S\cup \{2(-2^k+2)\}$. Since the set $S$ is decomposable and $-2^k+2\in S$, the set $S^+$ is decomposable too. Similarly to the above we can show that $z(S^+)\ge k$. The new case is when $T$ contains exactly one negative element $2(-2^k+2)$. Then $\sum T=0$ implies that we have a representation of $2(-2^k+2)$ as a sum of at most $k-1$ powers of $2$. not bigger than $2^{k-1}$ with at most one power used twice. This sum is at most $2^2+2^3+\dots +2^{k-1}+2^{k-1}=2^k-4+2^{k-1}<2(2^k-2).$ $\square$

We conjecture that the lower bound in Proposition 3 is tight. This conjecture is confirmed for small $n$ by the problem from your question and in the note we proved it for $n\le 5$. I’m going to finish there my draft proofs that the conjecture also holds for $n=6$ and $7$. Of course, this is not a big deal, but Tao Te Ching teaches that a journey of a thousand miles begins with a single step, so let's start. I hope that we’ll be able to continue the journey.

Update. Taras Banakh proved that any finite decomposable subset of an Abelian group contains two non-empty subsets $A$ and $B$ of $S$ such that $\sum A+\sum B=0$. On the other had, I found that a counterpart of Proposition 3 does not hold for Abelian groups. Namely, given a natural number $n$ let $S=\{1,2,\dots, 2^{n-1}\}$ be a subset of a group $\Bbb Z_{2^n-1}$. Since $2^i+2^i=2^{i+1}$ for each $0\le i\le n-2$ and $2^{n-1}+2^{n-1}\equiv 1\pmod {2^n-1}$, the set $S$ is decomposable. On the other hand, for any proper non-empty subset $T$ of $S$ we have $\sum T\equiv t\pmod {2^n-1}$ for some $0<t<2^n-1$, so $\sum T\not\equiv 0\pmod {2^n-1}$. These results are in our paper, which I am preparing to a submission to arXiv. So I’ll going to provide here a link to it soon.