Algorithm of the Week: Finding Sum-Free Subsets

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.

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 2ⁿ steps, so hopefully you could do better than that.

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

Update: Results here.