10
$\begingroup$

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.

  • 1
    Because this may be of interest: I have asked a [follow-up question](http://cstheory.stackexchange.com/questions/260/finding-small-sets-of-integers-in-which-every-element-is-a-sum-of-two-others) on the cs-theory stack exhange website.2010-08-18

4 Answers 4

13

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 \} $$

  • 0
    Thanks, it seems to work! I have extended the question about the case with the condition that $a\in S$ implies $-a \notin S$.2010-08-17
  • 0
    Thanks! I verified that it works. I am amazed that you found an example so quickly.2010-08-17
  • 0
    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.2010-08-17
5

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

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 0strongly 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.

3

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!

  • 0
    Thanks for your answer! I added the condition *finite* afterwards.2010-08-17
2

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.