<p>For N&nbsp;&ge;&nbsp;10, one can build a strongly self-supporting set of size at most eleven, as follows:</p>

<blockquote>
  <p>{&minus;N,&nbsp;&minus;N+2,&nbsp;&minus;N+4,&nbsp;&minus;2,&nbsp;1,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;N&minus;7,&nbsp;N&minus;6,&nbsp;N&minus;5}.</p>
</blockquote>

<p>The shorter example presented in the original question corresponds to the case N&nbsp;=&nbsp;10. This is close to being optimal, as any strongly self-supporting set must have cardinality <a href="https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others/2652#2652">at least eight</a>.</p>

<p>Thus, the problem is solvable in O(log(N)) time [taken up in mundane arithmetic operations on N], yielding a set of cardinality between eight and eleven.</p>

<p>The construction for this answer was first presented for <a href="https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others/2790#2790">the math.stackoverflow question</a>, which also gives the intuition for the construction. Can we obtain smaller constructions still, <em>e.g.</em> matching the lower bound of eight for every N&gt;9? What about the cases of N&nbsp;&isin;&nbsp;{8,9}?</p>

CC BY-SA 2.5
2010-08-19T11:28:55.753Z
2010-08-19T11:28:55.753Z
2017-04-13T12:19:19.363Z
Niel de Beaudrap
<p>I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)</p>

<p>Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.</p>

<p>We can do that easily if we construct the same for N-1, and then add N to the resulting set.</p>

<p>For the base case of 23, we can start with your example set.</p>

<p>To bring the size down, we should be able to use a similar approach: </p>

<p>Construct sets which contain <code>1, N and N-1.</code></p>

<p>We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows: </p>

<ul>
<li><p>If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.</p></li>
<li><p>If N is odd construct a set for N-1 and N to resulting set.</p></li>
</ul>

<p>For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 &lt; N &lt;= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.</p>

<p>In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.</p>

<p>It might be interesting to prove some lower bounds in the case N is prime.</p>

CC BY-SA 2.5
2010-08-18T15:00:34.763Z
+1. Serves me right for posing a question with too much slack-room, I suppose. You can do the same for N>10, of course. Which leaves us with the question of constructing sets which are smaller than this (possibly minimal in size, as in #2).
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T15:10:02.557Z
For your revised answer to bring the size down: I don't follow. I gather that you want to have N "supported" (expressed as a sum of distinct elements) as 1 + (N-1). But how do you "support" N-1, then? --- Also: I'm more interested in the size, i.e. the cardinality, of the set itself, although interesting bounds on its representation may also be interesting.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T15:14:30.683Z
@Niel: I was about to comment: see my edit :-)
Aryabhata
CC BY-SA 2.5
2010-08-18T15:20:40.827Z
Consider the case of N=46. Then N/2=23; we take the example given in the question as the self-supporting set, and include N-1=45 and N=46. How then do we "support" N-1=45?
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T15:22:17.427Z
(You may wish to consider changing your nickname. Why not advertise who you actually are? It also allows me to address you without looking like I'm insulting someone, should you eventually choose to change your nickname later.)
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T15:26:36.073Z
@Niel: For N=46, You recursively generate a set which contains 23 _and_ 22. So N=45 will be possible in that case. In your case, we add 24 to your example set, and have our base cases be N=24 to N=47 (which can be generated using the linear algo).
Aryabhata
CC BY-SA 2.5
2010-08-18T17:38:14.547Z
@Niel: That was just an example to show the main point: You recursively generate sets so that 1, N _and_ N-1 belong to the set and this allows you to reduce the size to O(logn).  As I said, the base case is N=24 to N=47 (by adding 24 to your example). In any case, by adding 6,7,..., 23 to your other example, we can make it work for N=23 too.
Aryabhata
CC BY-SA 2.5
2010-08-18T18:56:42.220Z
I think I see what you're saying, but perhaps you should edit your post to more clearly describe what you mean. And please double check your base-cases: you can't add 6, 8, or 10 to the second (smaller) example in the original question.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T18:59:36.473Z
@Niel: You are right, sorry for being so unclear. I have tried to edit it to make it clearer.
Aryabhata
CC BY-SA 2.5
2010-08-18T14:49:55.943Z
2010-08-18T19:10:29.150Z
2010-08-18T19:10:29.150Z
Aryabhata
<p>This is a follow-up to <a href="https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others">this question</a> on math.stackexchange.</p>

<p>Let us say that a non-empty set S&nbsp;&sube;&nbsp;&#8484; is <strong>self-supporting</strong> if for every <em>a</em>&nbsp;&isin;&nbsp;S, there exist distinct elements <em>b,c</em>&nbsp;&isin;&nbsp;S such that <em>a</em>&nbsp;=&nbsp;<em>b</em>&nbsp;+&nbsp;c. For positive integers <em>n</em>, simple examples include the ideal S&nbsp;=&nbsp;<em>n</em>&#8484;, or (for <em>n</em>&gt;3) the integer interval [&minus;<em>n</em>,&nbsp;<em>n</em>].</p>

<p>We'll say that S is <strong>strongly self-supporting</strong> if S is disjoint from &minus;S: that is, if <em>a</em>&nbsp;&isin;&nbsp;S, then &minus;<em>a</em>&nbsp;&notin;&nbsp;S. Neither of the above examples are strongly self-supporting, because they are in fact closed under negation.
There exist finite sets which are strongly self-supporting: for instance, the sets
{−22,&nbsp;−20,&nbsp;−18,&nbsp;−16,&nbsp;−14,&nbsp;−12,&nbsp;−10,&nbsp;−2,&nbsp;1,&nbsp;3,&nbsp;7,&nbsp;8,&nbsp;15,&nbsp;23} and  {−10,&nbsp;−8,&nbsp;−6,&nbsp;−2,&nbsp;1,&nbsp;3,&nbsp;4,&nbsp;5}.</p>

<p><strong>Question #1.</strong> For a positive integer <em>N</em>&gt;0, does there exist a poly(<em>N</em>)-time [or polylog(<em>N</em>)-time] algorithm to either <strong>(i)</strong>&nbsp;produce a strongly self-supporting set whose maximum absolute value is <em>N</em>, or <strong>(ii)</strong>&nbsp;determine that no such set exists? [<strong>Edit</strong>:&nbsp;as pointed out in the oldest answer&nbsp;+&nbsp;my comment on it, there always exists such a set for <em>N</em>&nbsp;&ge;&nbsp;10.]</p>

<p><strong>Question #2.</strong> For <em>N</em>&gt;0, can you construct the strongly self-supporting set with maximum absolute value <em>N</em>, and which has the fewest possible elements?</p>

CC BY-SA 3.0
2012-07-14T22:06:21.617Z
migrating answered questions is not a common practice and the question looks fine here. But if you want I will migrate it.
Kaveh
CC BY-SA 3.0
2012-07-16T15:38:49.687Z
I'm also not sure that it makes sense to migrate an answered question.
Suresh Venkat
CC BY-SA 3.0
2012-07-16T15:45:27.387Z
As you wish, then. The fact that this question remains here has bothered me for some time since the site became a mature forum for Q&A on theoretical topics. I thought that the tone might be much better suited to the (non-research level) cs.SE; but if you don't feel that there's a significant consistency issue, then I'll stop fretting about it.
Niel de Beaudrap
<ds.algorithms><co.combinatorics>
Finding small sets of integers in which every element is a sum of two others
Niel de Beaudrap
# Finding small sets of integers in which every element is a sum of two others

(Asked by: username_0 on 2010-08-18)

This is a follow-up to [this question](https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others) on math.stackexchange.

Let us say that a non-empty set S ⊆ ℤ is **self-supporting** if for every *a* ∈ S, there exist distinct elements *b,c* ∈ S such that *a* = *b* + c. For positive integers *n*, simple examples include the ideal S = *n*ℤ, or (for *n*>3) the integer interval [−*n*, *n*].

We'll say that S is **strongly self-supporting** if S is disjoint from −S: that is, if *a* ∈ S, then −*a* ∉ S. Neither of the above examples are strongly self-supporting, because they are in fact closed under negation.
There exist finite sets which are strongly self-supporting: for instance, the sets
{−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23} and {−10, −8, −6, −2, 1, 3, 4, 5}.

**Question #1.** For a positive integer *N*>0, does there exist a poly(*N*)-time [or polylog(*N*)-time] algorithm to either **(i)** produce a strongly self-supporting set whose maximum absolute value is *N*, or **(ii)** determine that no such set exists? [**Edit**: as pointed out in the oldest answer + my comment on it, there always exists such a set for *N* ≥ 10.]

**Question #2.** For *N*>0, can you construct the strongly self-supporting set with maximum absolute value *N*, and which has the fewest possible elements?

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_1**: migrating answered questions is not a common practice and the question looks fine here. But if you want I will migrate it.  
> **username_2**: I'm also not sure that it makes sense to migrate an answered question.  
> **username_0**: As you wish, then. The fact that this question remains here has bothered me for some time since the site became a mature forum for Q&A on theoretical topics. I thought that the tone might be much better suited to the (non-research level) cs.SE; but if you don't feel that there's a significant consistency issue, then I'll stop fretting about it.  

---

## 2 answers

### Answer by username_0 on 2010-08-19. Score: 5 | Accepted answer

For N ≥ 10, one can build a strongly self-supporting set of size at most eleven, as follows:

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

The shorter example presented in the original question corresponds to the case N = 10. This is close to being optimal, as any strongly self-supporting set must have cardinality [at least eight](https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others/2652#2652).

Thus, the problem is solvable in O(log(N)) time [taken up in mundane arithmetic operations on N], yielding a set of cardinality between eight and eleven.

The construction for this answer was first presented for [the math.stackoverflow question](https://math.stackexchange.com/questions/2647/sets-of-integers-in-which-every-element-is-the-sum-of-two-others/2790#2790), which also gives the intuition for the construction. Can we obtain smaller constructions still, *e.g.* matching the lower bound of eight for every N>9? What about the cases of N ∈ {8,9}?


---

### Answer by username_3 on 2010-08-18. Score: 6

I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)

Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.

We can do that easily if we construct the same for N-1, and then add N to the resulting set.

For the base case of 23, we can start with your example set.

To bring the size down, we should be able to use a similar approach:

Construct sets which contain `1, N and N-1.`

We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows:

* If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.
* If N is odd construct a set for N-1 and N to resulting set.

For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 < N <= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.

In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.

It might be interesting to prove some lower bounds in the case N is prime.

> **Comments:**
> **username_0**: +1. Serves me right for posing a question with too much slack-room, I suppose. You can do the same for N>10, of course. Which leaves us with the question of constructing sets which are smaller than this (possibly minimal in size, as in #2).  
> **username_0**: For your revised answer to bring the size down: I don't follow. I gather that you want to have N "supported" (expressed as a sum of distinct elements) as 1 + (N-1). But how do you "support" N-1, then? --- Also: I'm more interested in the size, i.e. the cardinality, of the set itself, although interesting bounds on its representation may also be interesting.  
> **username_3**: @Niel: I was about to comment: see my edit :-)  
> **username_0**: Consider the case of N=46. Then N/2=23; we take the example given in the question as the self-supporting set, and include N-1=45 and N=46. How then do we "support" N-1=45?  
> **username_0**: (You may wish to consider changing your nickname. Why not advertise who you actually are? It also allows me to address you without looking like I'm insulting someone, should you eventually choose to change your nickname later.)  
> **username_3**: @Niel: For N=46, You recursively generate a set which contains 23 _and_ 22. So N=45 will be possible in that case. In your case, we add 24 to your example set, and have our base cases be N=24 to N=47 (which can be generated using the linear algo).  
> **username_3**: @Niel: That was just an example to show the main point: You recursively generate sets so that 1, N _and_ N-1 belong to the set and this allows you to reduce the size to O(logn).  As I said, the base case is N=24 to N=47 (by adding 24 to your example). In any case, by adding 6,7,..., 23 to your other example, we can make it work for N=23 too.  
> **username_0**: I think I see what you're saying, but perhaps you should edit your post to more clearly describe what you mean. And please double check your base-cases: you can't add 6, 8, or 10 to the second (smaller) example in the original question.  
> **username_3**: @Niel: You are right, sorry for being so unclear. I have tried to edit it to make it clearer.  

---

