Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: a construction for sets of integers with distinct subset sums. | A CONSTRUCTION FOR SETS OF INTEGERS WITH DISTINCT SUBSET SUMS Tom Bohman Department of Mathematics 2-339 Massachusetts Institute of Technology 77 Massachusetts Ave. Cambridge MA 02139 bohman@ Submitted September 9 1997 Accepted November 24 1997. Abstract A set S of positive integers has distinct subset sums if there are 2ls l distinct elements of the set EzGXx X c S . Let f n min maxS SI n and S has distinct subset sums . Erdos conjectured f n c2n for some constant c. We give a construction that yields f n 2n for n sufficiently large. This now stands as the best known upper bound on f n . 1 Introduction A set S of positive integers has distinct subset sums if the set E X x X c s has 2 sl distinct elements. Let f n min maxs sI n and s has distinct subset sums . By taking the set s to be the first n powers of 2 we see that f n 2n-1. Some small examples the sets 3 5 6 7 and 6 9 11 12 13 for example suggest that f n could be much smaller than 2n-1. In 1931 Erdos conjectured that this is not the case E1 . In particular he conjectured that f n c2n for some constant c and he offered 500 for settling this conjecture E1 G1 G2 . In 1955 Erdos and Moser proved that f n 2ra @ n E2 for a proof using the second moment method see AS p47 . This remains up to the constant the best known lower bound for an improvement in the constant see Elk . The only improvements on the trivial upper bound on f n have been by construction. A method often used for proving upper bounds is to verify that some set of 1991 Mathematics Subject Classification. Primary 11P99 Secondary 05D10. THE ELECTRONIC .JOURNAL OF COMBINATORICS 5 1998 R3 2 i integers where i is relatively small has distinct subset sums and gives f i c2h This then gives the bound f j c2j for all j i by the following observation given a set S with distinct subset sums n elements and largest element m we construct a set S with distinct subset sums n 1 elements and largest element 2m by doubling every element in S and
