I can update my thoughts so far, perhaps someone will be interested enough to take a look at it.
--------------
Let S be a set of integers with |S| = 15. We may assume that S contains neither zero nor an inverse of another member of s, for it would make the choice for our subset T rather trivial. Furthermore, if S contains neither, it can be shown that it must contain at least three positive and three negative numbers. The proof is rather simple, just some logic steps. So take my word for it for now.
Consider now A to be the positive members of S and B to be the negative members of S. Without loss of generality, we may assume that |A| < |B|. So 3 <= |A| <= 7. Now define a graph G on A as follows: Let x, y be members of A. There exists an edge x -> y if there exists a z in S such that x = y + z. By this definition, every member of A is adjacent to at least one other member of A, because every positive number can not be written as the sum of two negative numbers. Because A is finite, there must exist a cycle X = x1, ... xk. Let k be the smallest k with this property. Then there exist Z = z1, ... zk such that
x1 = x2 + z1 = x3 + z2 + z1 = ... = x1 + zk + ... + z1.
The the sequence z1, ..., zk will sum to zero.
The way I see it, the main problem in this proof has to do with the doubles that occur in such a sequence Z. If there are no doubles in the sequence, then we have found our T. So let's assume that there are x[sub:2yewf1qi]i[/sub:2yewf1qi] and xj with i =/= j such that xi = xi+1 + z and xj = xj+1 + z. It is easy to show that z can not be a member of X. If it were, then there would exist a smaller cycle through xi, xj and z. That is not allowed since we chose X to be the smallest cycle in A. So we are left with the case that z is not a member of X. We need to proof that either we can replace z and still get a T with |T| <= 7 or that there must exist a different cycle (possibly in B) with the required properties.
I experimented some with assuming that |X| < 7. Then it's possible for z to be positive. There are some implications there, but nothing useful. We can 'expand' z a number of times till we reach a member of X. A new cycle might be possible in that way. Remember that our upper limit on the cycle size is equal to the upper limit on the amount of positive numbers in S. The other possibility is that z is in B. Maybe it's worth looking into the smallest cycle in B then? We have no guarantee that its length will be smaller than 7, but maybe we can proof that the biggest cycle in B can be no larger than the size of A. This certainly sounds plausible.. since negative numbers are absolutely required to make a cycle in the positive part of S.
--------------
The set I've been looking into most recently is S = {-8, -4, -3, -1, 2, 5, 7, 9}. It's of size 8, naturally, but the cycle 9 -> 7 -> 5 -> 9 has a complement Z which features the number 2 twice. I'm trying to find a structural way to avoid this. My work so far:
-------------
Let X be the smallest cycle x1 -> ... -> x1 in A (the positive members of S). Then 3 <= |X| <= 7, because 3 <= |A| <= 7 and |X| = 1 -> 0 in S, |X| = 2 -> S has an inverse.
Now let xi and xj be such that xi = xi+1 + z and xj = xj+1 + z and suppose that i < j. Now there are a few cases I was thinking of addressing.
- Suppose z = xk in X. Then there exists a cycle inside of X which is smaller than X itself. This is not possible since I chose X to be the smallest cycle in A.
- Suppose |X| < 7. Then there can possibly be m = |A| - |X| members of A which are not in X. So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.
The final case is when z is in B. I don't know how to approach that one.
Does this make sense?
Edit: I reread it and concluded, once again, that graph theory proof are totally unreadable without some drawing or example. So I'll just give you one.
Consider S = {-8, -4, -3, -1, 2, 5, 7, 9}. Then |S| = 8 and believe me that it satisfies the important property. Then A = {2, 5, 7, 9} and we found the cycle 9 -> 7 -> 5 -> 9 with complement {2, 2, -4}. In this case, xi = 9, xj = 7 and z = 2. Note that |X| = 3 < 4 = |A|, so m = 1. Here, z is in amongst the remaining members of A which are not in X, so z in X \ A. Note that if we expand z, we get z = 5 + -3. 5 is a member of X, which is to be expected after m expansions. Now we can construct the cycle z -> 5 -> 9 -> z (because 9 = xi) which satisfies our criterium.
The trick here is that the length of such a newly found cycle can not exceed |A|, which is what we wanted.
-------
There is no guarantee that this new cycle will not conflict, but I'm fairly confident we can repeat this process till we find a cycle in A which either doesn't have a conflict, or the conflicting z is not a member of A.
Hope this helps...
