MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $ A $ be a set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $ |B|> \frac{|A|}{3} $ (a result of Erdős). It is conjectured that RHS can be improved to $\frac{|A|}{3} +10$. Is there any evidence/heuristic justification for this conjectured bound?

(A set $B$ is sum-free if it contains no solution to $x+y=z$.)

share|cite|improve this question
2… – Seva Dec 3 '13 at 14:53
What is "an additive set"? What is "a sum free-free set"? – Gerry Myerson Dec 3 '13 at 22:55
I am following the book additive combinatorics by tao,vu. I will soon add the definitions – Koushik Dec 4 '13 at 4:08
thanks seva. seems quite informative on this problem. – Koushik Dec 4 '13 at 4:11
up vote 15 down vote accepted

This is a notorious problem. It is my impression that a lot of talent people have looked at it, without much progress. Ben Green has an excellent talk on the topic (in part) which can be viewed here:

There is nothing special about constant 10 in the statement in Tao and Vu's book. It is generally believed that $|B| \geq \frac{|A|}{3} + f(|A|)$ is true for some function $f(\cdot) \rightarrow \infty$. Indeed, I think many people (including myself) are willing to conjecture that one may even take $f(x) = c_{\epsilon} x^{1/2-\epsilon}$. The current record is the slightly improved estimate of $|B| \geq \frac{|A|+2}{3}$, due to Bourgain.

Let me first try to explain why improving Erdős' result is so difficult. The proof of Erdős' theorem proceeds by constructing the sum-free subset probabilistically and showing the expected size is $|A|/3$. Generally, when one is working with analytic tools (Holder's inequality, interpolation, level set decomposition, etc) if one assumes (for contradiction) that an estimate is sharp one can usually extract a fair amount of structural information about the hypothetical example. One can then use this structure to try to improve the result. (This is perhaps one of the reasons why it is common to see long sequences of papers, each marginally improving the results of the previous, for analytic problems.) On the other hand, it seems nearly impossible to extract structural information from elementary probabilistic arguments. (Indeed, combinatorics has many examples of longstanding bounds proven by very elementary probabilistic arguments).

On the other hand, as I have already mentioned, Bourgain did manage to get a very small improvement. Bourgain's idea was to reinterpret Erdős' proof in the language of Fourier analysis. Roughly speaking, in this language the expectation in Erdős' argument corresponds to the constant term in a Fourier series. One can then try to exploit the rest of the terms in the Fourier series (which are oscillatory and depend in an indirect way on the arbitrary set $A$). With a fair amount of case analysis he was able to extract an additional 1/3 from the non-zero terms of the Fourier series. In principle, one could try to push this further, but the case analysis becomes unwieldy very quickly. Indeed, Bourgain's $2/3$ is sharp for sets of size 12 and smaller, so any further improvement needs to somehow make use of at least 13 distinct elements of the set.

This all said, there is a known path to progress on this problem. Using his Fourier analysis approach, Bourgain proved the following inequality: $$|B| \geq \frac{|A|}{3} + c\frac{E(A)}{\log(|A|)}$$ where $E(A) = || \sum_{a \in A} e(ax) ||_{L^{1}[0,1]}$. Recall that $E(A) \sim \log(|A|)$ when $A$ is an arithmetic progression. Thus, this doesn't immediately imply anything new (one check that the constant $c$ is small). On the other hand, Littlewood's (second most famous) conjecture states $E(A) \gg \log(|A|)$ for every set $A \subset \mathbb{Z}$. This was proven independently by Konyagin and McGehee, Pigno and Smith in the early 1980's. Thus, in some sense Bourgain's estimate (plus the Littlewood conjecture) just barely misses an improvement.

These ideas still hold a lot of potential, however. The only known near extremals to the inequality $E(A) \gg \log(|A|)$ are `nearly' generalized arithmetic progressions. On the other hand, it isn't hard to see generalized arithmetic progressions have large sum-free subsets. Thus if one could classify near extremizers to the inequality $E(A) \gg \log(|A|)$, then one could likely get an improvement to Erdős' theorem. Indeed, I believe Ben Green has proven some formal implications along these lines. It should be mentioned that the classification of extermals to $E(A) \gg \log(|A|)$ (after considering the $L^4$ norm and applying Balog-Szemeredi-Gowers) looks very similar to (but not quite) Freiman's theorem. Connections along these lines have have been quite useful in the related theory of indempotent's (see the work of Green and Sanders and Sanders). However, it seems more ideas are needed to make progress on the sum-free subset problem.

share|cite|improve this answer
thanks.your answer contains everything i wanted to know. i was wondering where on earth did 10 come from – Koushik Dec 4 '13 at 7:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.