Sum-free subset challenge

A set of integers is called sum-free if no element of the set is the sum of any other pair of elements in the set. For example, {1, 10, 100} is sum-free.

Let’s look at pulling out a sum-free subset of a larger set. For example, if we start with {1, 2, 3, …, 10}, then {1, 5, 10} as a sum-free subset. So is {1, 2, 4, 7}. Notice in this case 1 + 2 + 4 = 7, but that’s OK because we’re only concerned with whether an element is the sum of two other elements.

[Update: Thanks to Sjoerd Visscher for pointing out that the definition of sum-free does not require that the elements of a sum be distinct. So when I said that the set {1, 2, 4, 7} is sum-free, this was wrong because 2 + 2 = 4. The set A is sum-free if the intersection of A+A with A is empty.]

Now let A be a set of integers with n elements. How large of a sum-free subset does A contain? It could be as large as n if the set A were sum-free to begin with, so that’s an upper bound. But what is a lower bound on the size of the largest sum-free subset?

There is a theorem that gives a number k such that every set of n non-zero integers contains a sum-free subset of size at least kn. You could let k be zero, but that’s no fun. Can you find a larger value of k? I’ll tell you later what value of k the theorem has. Until then, maybe you could try to find your own value.

Suppose you want to write a program to explore this empirically. For a given set, how would you find a maximal sum-free subset? Brute force examination of all subsets would take 2n steps, so hopefully you could do better than that.

What are some sets that have relatively small maximal sum-free subsets?

Other quiz/puzzle posts

16 thoughts on “Sum-free subset challenge

  1. It seems intuitively that the worst case is A = {1,…,n}. When the numbers have bigger ranges, the subsets grow, as there is less chance that the sum of two numbers is equal to another number. A short experiment with n ranging from 5 to 40 showed that k=ceil(n/2) for this class of instances.

  2. In ordered list as 1, 2, 3 … 10 the answer is the number of odd numbers. As we know summing of two odd numbers the result is always even number. Therefore every odd number is sum free.
    It would be interesting if the list is not pre ordered by definition.

  3. Igor Ostrovsky

    The problem description doesn’t say that the integers must be positive, so there will be worse cases than A = {1, 2, 3, …}

    For example, I think that the biggest sum-free subset of { -3, -2, -1, 0, 1, 2, 3 } has the size 2.

  4. The original problem did specify that the numbers must be non-zero, but it does not rule out negative numbers. I’ll update the post to include the non-zero requirement.

  5. It seems like if your set contains N Fibonacci numbers in sequence, you need to remove N/3 of them to form a sum-free subset. So I guess K = 2/3. Not sure if this is the tightest lower bound…

  6. Sorry, the language of upper/lower bounds is confusing to me sometimes. The question “how big can the maximum sum-free subset be?” clearly has answer K=1 and is not very interesting. The question “how small can the maximum sum-free subset be?” is more interesting, and I’m claiming that K=2/3 is an upper bound on this answer, presumably not tight.

  7. My version of some code for this, at least for non-negative numbers.

    #!/usr/bin/python3
    
    def sums(a):
        """ Return a list of the sums of all of the pairs of numbers in a list.
            Includes some duplicates, but it's quicker overall that way.
        """
        return (x + y for i, x in enumerate(a) for y in a[i+1:])
        
    def _msf(p, c):
        """ Find a maximum size sum-free subset given a partial solution p and
            a list of candidate remaining numbers c all of which are larger than 
            any of the values in p and not equal to any of their pairwise sums.
        """
        if len(c) == 0:
            return p
        else:
            def m():
                for i, cp in enumerate(c):
                    q = p + [cp]
                    yield _msf(q, [cc for cc in c[i+1:] if cc not in sums(q)])
            return max(m(), key=len)
            
    def msf(a):
        """ Find a maximum size sum-free subset of a list of non-negative integers. """
        return _msf([], sorted(set(a)))
    
    r = msf(range(1,31))
    print(len(r), r)
    

    Marked as Python3 but, give or take thinking it’s printing a tuple, seems to work fine in Python2 as well. Quicker, actually.

  8. Ed, Thanks for posting your code.

    The blog was interpreting your code as text. I edited your comment to add

     ... 

    around your code and that restored the formatting.

  9. Thanks John. Would it be worthwhile to add a link to your reply box on to a page about formatting? I’d never have guessed, otherwise; is that markdown or something?

  10. It is obvious that K<1, since one can always construct a set of length N that needs atleast one element removed to make it a sum-free subset. Playing with the N=3 case it is easy to see that one can always construct a sum-free subset of length 2, hence K<= 2/3, as Ian already said.
    I don't have a proof beyond this, but I suspect that the bound is tight and 2/3 is the correct answer. Intuitively the spectrum of pairwise sums will collide with values in the original set if they are small and closely packed, but not identical. Hence one would expect something as simple as {1, 2, …, N} to be a problematic case. Even in this case one could (as Asen suggested) delete the even numbers to get a sum-free subset. However notice that you can get away with deleting only the even numbers smaller than N/2, hence you can produce a sum-free subset of size N/2 + N/4 = (2/3) N.

  11. Here’s a much more concise version which is, nicely, about twice as fast. There’s a small speed improvement from not re-filtering the candidate numbers against previously tested pair sums but mostly it’s from not doing so many function calls deep in the recursion nest and from changes in the data structures (between lists, generators, sets, etc). The improvements from the data structure changes surprised me.

    A nice little programming exercise which gave me a few insights into aspects of Python I’d normally just gloss over. Thank you.

    ...
    #!/usr/bin/python3
    
    def _msf(p, c):
        """ Find a maximum size sum-free subset given a 
            partial solution, p, and a list of candidate 
            remaining numbers, c, all of which are larger 
            than any of the values in p and not equal to 
            any of their pairwise sums.
        """
        if len(c) == 0:
            return p
        else:
            return max(
                (_msf(p + [cp], 
                      [cc for cc in c[i+1:] 
                            if cc not in 
                                { cp + x for x in p }]
                     ) for i, cp in enumerate(c)),
                key=len)
            
    def msf(a):
        """ Find a maximum size sum-free subset of a list 
            of non-negative integers.
        """
        return _msf([], sorted(set(a)))
    
    r = msf(range(1, 32))
    print(len(r), r)
    ...
    
  12. Hi John, do you know a value for k where the elements of the sum *do* have to be distinct (and positive integers)? For that problem I had k=0.5, but I’m not very good at this kind of thing.

Comments are closed.