Suppose that X is a finite set of positive integers. The sumset of two subsets A and B of X is defined as A+B={a+b:a\in A, b\in B}. Then, what is the number of subsets of X which are neither the non-trivial sumsets of any two other subsets of X nor the non-trivial summands of any other subsets of X? Also, please suggest some useful references in this area.
Thanking you in advance,
Sudev
The number of such subsets depends too much of the values, to say something in general. Take the set {1,2}. Because {1} + {1} = {2}, the sets you ask about are the empty set and the total set, and their number is 2. Take now {1,3}. There is no more addition of subsets making a subset, so all subsets match your condition and the number you ask about is 4. This extreme variation for a trivial example suggests that there is no concise answer - just a long discussion for every set taken appart.
The number of such subsets depends too much of the values, to say something in general. Take the set {1,2}. Because {1} + {1} = {2}, the sets you ask about are the empty set and the total set, and their number is 2. Take now {1,3}. There is no more addition of subsets making a subset, so all subsets match your condition and the number you ask about is 4. This extreme variation for a trivial example suggests that there is no concise answer - just a long discussion for every set taken appart.
I just reconsider the nature of the empty set in the given example. Always empty set + empty set = empty set. (the set of sums of elements of the empty set is of course empty...) So for {1,2} the ony subset which is neither sum nor sumand of another subset(s) is the total set {1,2} itself. In the case of {1,3} there are three such subsets: {1}, {3} and {1,3}. The rest of commentary remains correct.
You might have already seen this http://arxiv.org/pdf/1407.5028.pdf. Are you also considering an algorithmic solution to the problem?
Dear Prof. Osinenko,
I want to know whether there is any exact formula for finding the the number of subsets of X which have the required properties.
You might try computing the values for the cases: X = {1,2,...,n}. This will give a sequence a(n) which you can look up in the OEIS at http://oeis.org/ and if you are lucky you might find something there of value.
Is Mihai right? I'm not sure I understand the question.
If X = {1, 2, 3, 4} and A = {1,2} and B = {3,4} then is the sumset A+B={4, 5, 6}?
In general if there are n elements in set X then there are 2^n subsets.
Now if A = {2} and B = {3} then does A+B = {5}. But this wouldn't count because it equaled {1} + {4}.
Suppose a is the least element of X, where X is any set of integers with card(X) = n, and C is a subset of X that does not contain a, then C = {a} + {x-a: x in C}. Clearly if C contains a then it cannot be the sum A + B of subsets A,B of X. Thus the number of subsets of X that are not of the form A+B for subset A,B of X is the number of subsets of X that contains a, namely, 2^(n-1).
I'm not sure what you mean by "...nor the non-trivial summands of any other subsets of X".
You can check this book
http://books.google.pt/books?id=PqlQjNhjkKUC&hl=es&source=gbs_similarbooks
I'm still trying to understand the question.
Suppose X = {1,2,3,5}.
Then X has 2^4 possible subsets. But {2,3} is out because it is the sumset of {1,2} and {1}. Then are {1,2} and {1] out because they are summands of {2,3}?
If so, we're left with just two subsets - {1,3,5} and {1, 2, 3, 5}.
- Badges
- Science topic
- Similar topics
- Mathematics