I recently arXiv’ed a short note titled An Improved Upper Bound for the Sum-free Subset Constant. In this post I will briefly describe the result.
We say a set of natural numbers is sum-free if there is no solution to the equation with . The following is a well-known theorem of Erdős.
Theorem Let be a finite set of natural numbers. There exists a sum-free subset such that .
The proof of this theorem is a common example of the probabilistic method and appears in many textbooks. Alon and Kleitman have observed that Erdős’ argument essentially gives the theorem with the slightly stronger conclusion . Bourgain has improved this further, showing that the conclusion can be strengthened to . Bourgain’s estimate is sharp for small sets, and improving it for larger sets seems to be a difficult problem. There has also been interest in establishing upper bounds for the problem. It seems likely that the constant cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant could not be replaced by a number greater than by considering the set . In 1990, Alon and Kleitman improved this to . In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than . While we have not seen Malouf’s proof, we note that this can be established by considering the set . In this note we further improve on these results by showing that the optimal constant cannot be greater than .