Lewko's blog

An improved upper bound for the sum-free subset constant

Posted in math.CO, Paper, Uncategorized by Mark Lewko on August 27, 2010

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 $A$ is sum-free if there is no solution to the equation $x+y=z$ with $x,y,z \in A$. The following is a well-known theorem of Erdős.

Theorem Let $A$ be a finite set of natural numbers. There exists a sum-free subset $S \subseteq A$ such that $|S| \geq \frac{1}{3}|A|$.

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 $|S| \geq \frac{|A|+1}{3}$. Bourgain  has improved this further, showing that the conclusion can be strengthened to $|S| \geq \frac{|A| + 2}{3}$. 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 $1/3$ cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant $\frac{1}{3}$ could not be replaced by a number greater than $3/7 \approx .429$ by considering the set $\{2,3,4,5,6,8,10\}$. In 1990, Alon and Kleitman improved this to $12/29 \approx .414$. In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than $4/10 = .4$.  While we have not seen Malouf’s proof, we note that this can be established by considering the set $\{1,2,3,4,5,6,8,9,10,18\}$. In this note we further improve on these results by showing that the optimal constant cannot be greater than $11/28 \approx .393$.