Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

4 Answers

up vote 12 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Thanks again Niel! –  AgCl Aug 19 '10 at 12:08
add comment

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!

share|improve this answer
    
Thanks for your answer! I added the condition finite afterwards. –  AgCl Aug 17 '10 at 12:06
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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