16

This is a follow-up to this question 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?

Community
  • 1
Niel de Beaudrap
  • 8,821
  • 31
  • 70
  • 1
    migrating answered questions is not a common practice and the question looks fine here. But if you want I will migrate it. – Kaveh Jul 14 '12 at 22:06
  • I'm also not sure that it makes sense to migrate an answered question. – Suresh Venkat Jul 16 '12 at 15:38
  • 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 Jul 16 '12 at 15:45

2 Answers2

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.

Aryabhata
  • 1,855
  • 3
  • 21
  • 29
  • +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 Aug 18 '10 at 15:00
  • 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 Aug 18 '10 at 15:10
  • @Niel: I was about to comment: see my edit :-) – Aryabhata Aug 18 '10 at 15:14
  • 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 Aug 18 '10 at 15:20
  • 2
    (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 Aug 18 '10 at 15:22
  • @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 Aug 18 '10 at 15:26
  • @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 Aug 18 '10 at 17:38
  • 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 Aug 18 '10 at 18:56
  • @Niel: You are right, sorry for being so unclear. I have tried to edit it to make it clearer. – Aryabhata Aug 18 '10 at 18:59
5

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.

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, 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}?

Community
  • 1
Niel de Beaudrap
  • 8,821
  • 31
  • 70