# Sets of integers in which every element is the sum of two others

i) Does there exists a nonempty subset of integers $S$, such that for all $a \in S$, there exists $b,c \in S$ such that $a = b + c$, where $a, b, c$ are distinct integers.

Edited to add: ii) Can an $S$ with these properties be finite, and also have the property that $a \in S$ implies $-a \notin S$

This question is inspired by another question, which has not been fully answered yet.

-
Because this may be of interest: I have asked a follow-up question on the cs-theory stack exhange website. – Niel de Beaudrap Aug 18 '10 at 13:52

Yes, you can take the set of integers between $-n$ and $n$ inclusive for any $n \ge 3$. Here $0 = 1 + (-1)$, $1 = 2 + (-1)$ and $x = (x - 1) + 1$ for $x \ge 2$. Similar formulae for negative values.

EDIT: Answer for new version of the question Set found by hand:

$$\{ -22, -20, -18, -16, -14, -12, -10, -2, 1, 3, 7, 8, 15, 23 \}$$

EDIT: Answer with 8 elements. If you add -12 to this set you will get set with odd number of elements. $$\{ -10, -8, -6, -2, 1, 3, 4, 5 \}$$

-
Thanks, it seems to work! I have extended the question about the case with the condition that $a\in S$ implies $-a \notin S$. – AgCl Aug 17 '10 at 12:32
Thanks! I verified that it works. I am amazed that you found an example so quickly. – AgCl Aug 17 '10 at 13:09
I find it interesting that the elements of one sign almost form an arithmetic progression starting at -10 and counting by -2 (the remaining number) like I originally tried, that parity corresponds to sign except for 8, and that those exceptions are related. It seems like there should be a general result. – Vandermonde Aug 17 '10 at 13:35

I posted an answer to this question previously, giving a finite set. That answer was incorrect: this is a different answer, which contains lower bounds on finite sets of the sort you ask for.

A set S such that (∀a ∈ S)(∃b,c ∈ S):(b≠c  and  a = b + c) we will call self-supporting: a self-supporting set S which is disjoint from −S will be strongly self-supporting.

Proposition 1. A self-supporting set must contain at least three positive elements, and three negative elements.

[Proof] A self-supporting set S is non-empty; because the property of self-support is preserved by negation of the elements, without loss of generality we may consider sets containing positive elements.

The largest positive element of S can only be formed as a sum of two other positive elements; thus it has at least three positive elements 0<c<b<a such that a = b + c. The smallest positive element cannot be formed as a sum of smaller positive elements, so S contains negative elements. By similar arguments, it must contain at least three negative elements.

As the set {−3, −2, −1, 1, 2, 3} is self-supporting, this bound is optimal.

Proposition 2. A strongly self-supporting set must contain at least four positive elements, and four negative elements.

[Proof] Suppose that S is self-supporting, but only has three positive elements 0<c<b<a. Then a = b + c. We cannot form b as a sum of c with some other positive element of S; it then follows that b can only be formed as a sum of a and −c, which implies that S is not strongly self-supporting. Thus, a strongly self-supporting set contains at least four positive elements; and similarly for negative elements.

The smaller set in flagar's answer, {−10, −8, −6, −2, 1, 3, 4, 5}, is thus a minimal-size strongly self-supporting set --- and may also be the set having elements of the smallest absolute value.

-
Thanks again Niel! – AgCl Aug 19 '10 at 12:08

The only possibilities I can think of at the moment are $S = n \mathbb{Z}$, so for now I guess the answer is technically yes. I'll try to think of others and possibly characterize all such sets. Great question!

-
Thanks for your answer! I added the condition finite afterwards. – AgCl Aug 17 '10 at 12:06

A further answer, generalizing flagar's example:

For any N ≥ 10, there exists a set of the sort you ask for which contains at most eleven elements (with fewer than eleven in the case that N < 13), and with all elements having absolute value at most N:

{−N, −N+2, −N+4, −2, 1, 3, 4, 5, N−7, N−6, N−5}.

The shorter example presented by flagar corresponds to the case N = 10.

The key to this construction was to think in terms of small sequences of almost mutually-supporting subsequences. For instance, the sequence −N, −N+2, −N+4 consist of integers which are sums of themselves, plus one of −2 or 4. We can include 4 in the set by including it in the sequence 3, 4, 5: we can support this by including 1 in the set (where 1 itself is supported as the sum of 3 and −2). We then only need a way of supporting −2: we do this with the other subsequence which includes N−6.

Each time we have a short sequence, we have a collection of integers which is easy to "support" using only a small number of other integers. So one strategy to constructing such self-supporting sets of integers is to think in terms of one or more short sequences of integers, with each sequence working to support another.

-