[math-fun] sets with distinct subset sums
PROBLEM: What is the largest N such that an M-element subset of {1,2,3,...,N} exists, with all subset-sums unequal? ALMOST EQUIVALENT PROBLEM: maximize M with N fixed. BOUNDS: It appears that the arguments Moulton & I were using, and various other arguments we did not use, all prove upper and lower bounds on M which when N is large are of the form lg(N) + c*lglg(N) + lower order terms for different real constants c, where lg(X)=log(X)/log(2). The naive upper bound has c=1. My cleverer Chebyshev-based argument with optimized k=sqrt(3) gets it down to c=1/2. [Perhaps something else could do better? I am unsure whether Moulton's technique is ultimately stronger or weaker than my Chebyshev-based technique.] A lower bound arising from just letting the M-subset be 1,2,4,8,16,...,2^(M-1) which obviously has distinct subset sums from binary number system, has c=0. Tom Bohman in 1997 paper reveals this all is actually a $500 Erdos problem (thanks a lot Miller...) and claims he has the best lower bound which is N>0.22002*2^M. But this still has c=0. cite: www.combinatorics.org/Volume_5/PDF/v5i1r3.pdf Bowman also reveals the best known upper bound due to Erdos & Moser and Elkies involves, like mine, c=1/2. cite: J.Combin.Th. A 41 (1986) 89-94. So as of now I've been unable to shrink the c-window below [0, 1/2], but it turns out all those other guys over a 60 year+ period have not been able to either.
participants (1)
-
Warren Smith