16
$\begingroup$

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 [−nn].

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?

$\endgroup$
3
  • 1
    $\begingroup$ migrating answered questions is not a common practice and the question looks fine here. But if you want I will migrate it. $\endgroup$
    – Kaveh
    Jul 14 '12 at 22:06
  • $\begingroup$ I'm also not sure that it makes sense to migrate an answered question. $\endgroup$ Jul 16 '12 at 15:38
  • $\begingroup$ 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. $\endgroup$ Jul 16 '12 at 15:45
6
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ +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). $\endgroup$ Aug 18 '10 at 15:00
  • $\begingroup$ 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. $\endgroup$ Aug 18 '10 at 15:10
  • $\begingroup$ @Niel: I was about to comment: see my edit :-) $\endgroup$
    – Aryabhata
    Aug 18 '10 at 15:14
  • $\begingroup$ 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? $\endgroup$ Aug 18 '10 at 15:20
  • 2
    $\begingroup$ (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.) $\endgroup$ Aug 18 '10 at 15:22
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.