DIMACS Discrete Mathematics Seminar


On the Conway-Guy Sequence


Tom Bohman
Rutgers University


CoRE Building Room 431
Busch Campus, Rutgers University


4:30 PM
Tuesday, March 28, 1995


A set S of positive integers has distinct subset sums if for any distinct subsets I and J of S the sum of the elements in I does not equal the sum of the elements in J. For example, the sets {1,2,4,8} and {3,5,6,7} have distinct subset sums. How small can the largest element of such a set be? In other words, what is

f(n)=min{max S :|S|=n and S has distinct subset sums}?

Erdos conjectures that f(n) > c2^n for some constant c. In 1967 Conway and Guy constructed an interesting sequence of sets of integers. They conjectured not only that these sets have distinct subset sums but also that they are the best possible (with respect to the largest element). I will show a technique for proving that sets of integers have distinct subset sums. This technique can be used to show that the sets from the Conway-Guy sequence (as well as some other interesting sets) have distinct subset sums. The Conway-Guy sequence now gives the best known upper bound on f(n).

Document last modified on March 27, 1995