Lewko's blog

The Eberhard-Green-Manners Sum-free Subset Theorem, and `What is Sum-free(13)?’

Posted in math.CO, Open Problem by Mark Lewko on February 19, 2013

The first research level math problem I seriously worked on (without much success) was the sum-free subset problem. A sum-free set (in an additive group) is a set that contains no solution to the equation x+y=z.  The sum-free subset problem concerns the following theorem of Erdős, which is one of the early applications of the probabilistic method.

Theorem: (Erdős, 1965) 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| + \frac{1}{3}.

The natural problem here is to determine how much one can improve on this result. Given the simplicity of the proof, it seems that one should be able to better. However, the best result to date is \frac{|A|}{3}+ \frac{2}{3} (for |A|>2) due to Bourgain (1995) using Fourier analysis. It seems likely that there is a function f(n) \rightarrow \infty such that one may take |S| \geq \frac{|A|}{3}+ f(|A|) in the above theorem, however proving this seems to be quite challenging.  On the other hand proving a good upper bound also was a longstanding open problem, namely deciding if the constant \frac{1}{3} could be replaced by a larger constant. This problem, in fact, has received a fair amount of attention over the years. In his 1965 paper Erdos states that Hinton proved that the constant is at most \frac{7}{15} \approx .467 and that Klarner improved this to \frac{3}{7}. In 1990 Alon and Kleitman improved this further to \frac{12}{29} \approx 0.414, and Malouf in her thesis (as well as Furedi) improved this further to \frac{2}{5} = .4. A couple years ago I improved this to \frac{11}{28} \approx .393 (I recently learned that Erdős claimed the same bound without a proof in a handwritten letter from 1992). More recently, Alon improved this to \frac{11}{28} - 10^{-50000} (according to Eberhard, Green and Manners, Alon’s paper doesn’t appear to be electronically available. UPDATE: Alon’s paper can be found here). All of these results (with the exception of Alon’s) proceed simply be constructing a set and proving its largest sum-free subset is at most a certain size (then an elementary argument can be used to construct arbitrarily large sets with the same constant: see this blog post of Eberhard). On the other hand, it is obvious from the statement of the theorem above that one can’t have a set whose largest sum-free subset is exactly \frac{|A|}{3}, thus a simple proof by example is hopeless. The futile industry of constructing examples aside,  I spent a lot of effort thinking about this problem and never got very far.

About a month ago Sean Eberhard, Ben Green and Freddie Manners solved this problem, showing that \frac{1}{3} is indeed the optimal constant!  I don’t yet fully understand their proof, and will refer the reader to their introduction for a summary of their ideas.  However, having learned the problem’s difficulty firsthand, I am very pleased to see it solved.

In the wake of this breakthrough on the upper bound problem, I thought I’d take this opportunity to highlight a toy case of the lower bound problem.

Definition: For a natural number n define the sum-free subset number Sum-free(n) to be the largest number such that every set of n natural numbers is guaranteed to contain a sum-free subset of size at least Sum-free(n).

Thus by Bourgain’s theorem we have that Sum-free(n) \geq \frac{n+2}{3} (and the Eberhard-Green-Manners theorem states Sum-free(n)=\frac{n}{3}+o(1)). It turns out that Bourgain’s result is sharp for sets of size 12 and smaller. However, Bourgain’s theorem only tells us that a set of size 13 must contain a sum-free subset of size 5 while it seems likely (from computer calculations) that every set of size 13 must in fact contain a sum-free subset of size 6. Indeed, I’ll even

Conjecture: Sum-free(13)=6.

While the asymptotic lower bound problem (showing that there f(|A|) \rightarrow \infty) seems very hard and is connected with subtle questions in harmonic analysis (such as the now solved Littewood conjecture on exponential sums), this problem is probably amenable to elementary combinatorics (although, it certainly does not seem easy!). Below is a chart showing what I know about the first 15 sum-free subset numbers.

 

n Bourgain’s lower bound
on Sum-free(n)
Best known upper
bound on Sum-free(n)
Upper bound set example
1 1 1 \{1\}
2 1 1 \{1,2\}
3 2 2 \{1,2,3\}
4 3 3 \{1,2,3,4\}
5 3 3 \{1,2,3,4,5\}
6 3 3 \{1,2,3,4,5,6\}
7 3 3 \{1,2,3,4,5,6,8\}
8 4 4 \{1,2,3,4,5,6,7,9\}
9 4 4 \{1,2,3,4,5,6,7,8,10\}
10 4 4 \{1,2,3,4,5,6,8,9,10,18\}
11 5 5 \{1,2,3,4,6,10,20,70,140,210,420\}
12 5 5 \{1,2,3,4,5,6,7,8,9,10,14,18\}
13 5 6 \{1,2,3,4,6,10,20,35,70,105,140,210,420\}
14 6 6 \{1,2,3,4,5,6,7,10,12,14,30,35,60,70\}
15 6 7 \{1,2,3,4,6,10,20,30,35,60,70,105,140,210,420\}
Advertisements