A BREAKTHROUGH result on density and 3-AP's

We use the following terminology: [n] means the set {1,...,n}. k-AP means an arithmetic progression of length k. A 3-free set is one with no 3-AP.s in it. We use the following conventions: (1)all inequalities have a big-O or big-&Omega which we do not include, and (2) we have the pointers to the papers be at the authors name when possible.

The following result was posted Oct 30, 2010 by Sanders.

For large n, for all A &sube [n], |A| &ge n(log log n)⁵/log n then A has a 3-AP.

I give the history and some misc information about the result.

1. In 1927 van der Waerden published the following theorem which is now known as van der Waerden's theorem:

   For all k, for all c, there exists W=W(k,c) such that for all c-colorings of [W] there exists a monochromatic k-AP.

   Online sources: (1) Wikipedia, (2)blog by Gilish Varma, and (3) preprint of a book by Gasarch et al .The upper bounds on W(k,c) from the original proof and the links (which are essentially the same) are BIG. In particular they are not primitive recursive. (NOTE- if you know of an online source for van der warden's original article and/or a translation into English, let me know.)
2. Erdos and Turan(you'll need to scroll down some) wanted an alternative proof of this theorem with smaller bounds. To this end they made the following conjectures:
   1. (ER1) For all k, for all &epsilon for large enough n, for all A &sube {1,...,n} such that |A| &ge &epsilon n, A has a k-AP.
   2. (ER2) Let A be a set of natural numbers. If &Sigma_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences.
   Both of these imply VDW's theorem. The hope was that they would provide new proofs with better bounds.
3. Roth showed ER1 for k=3. In fact, he showed the following: for large enough n, for all A &sube {1,...,n} such that |A| &ge n/log log n, A has a 3-AP. The proof used non-combinatorial methods. For an online proofs see either Terry Tao's blog or Alex Iosevich's notes.
4. Szemeredi proved ER1 for k=4 and then for general k. The proof for general k used VDW's theorem and hence did not provide better bounds for W(k,c). Szmeredi's Regularity Lemma which he developed to prove it, has found many many applications. His proof for k=4 was purely combinatorial. A scaled down version of it for k=3 was presented in Graham-Rothchild-Spencer in about 2 pages. For an online exposition of this see pages 121-130 of Gasarch et al. For an online exposition of the proof for the general case see this exposition by Tao.
5. Furstenberg obtained a different proof of ER1 using ergodic theory. This proof was nonconstructive and hence yielded no bounds on the VDW numbers. His technique was later used by Bergelson and Leibman to prove the poly VDW theorem and Poly HJ Theorem. Later Walters found a combinatorial proofs for both. See also the exposition by Gasarch et al.
6. Shelah obtained primitive recursive bounds on the VDW numbers. His proof was purely combinatorial.
7. Gowers proved ER1 in a way that lead to much better bounds on the VDW numbers.
8. A purely combinatorial proof of the Density Hales-Jewitt theorem was done by the polymath group. This is likely the easiest proof of ER1.
9. Green and Tao showed that the set of primes have arb large arithmetic progressions. Aside from this, there seems to have been little progress on ER2. Some people think ER2 should replace Poincare's conjectures on the list of Millennium Prizes.

That would seem to be the end of the story for now. ER1 was proven in a way that lead to better bounds on VDW numbers. But notice Roth's theorem. The condition on the density of a set that lead to a 3-AP are better than ER1. There have been improvements on Roth's theorem.

1. Szemeredi and Heath-Brown obtained the following result independently: There exists a constant d such that, for large enough n, for all A &sube [n], |A| &ge n/(log n)^d, A has a 3-AP. There is a nice exposition by Green (NOTE- if you know of an online source for the original papers let me know.)
2. Bourgain obtained the following result: for large enough n, for all A &sube [n], |A| &ge n((log log n)/log n)^0.5 A has a 3-AP.
3. Bourgain improved his result to: |A| &ge n/(log n)^2/3-o(1)
4. Sanders improved Bourgain's result to |A| &ge n/(log n)^3/4-o(1).
5. Sanders NEW result is that we only need |A| &ge n(log log n)⁵/log n.

OKAY- why is this important? It breaks a barrier that seemed very stubborn and it also leads to better bounds on W(3,c):

Let f be a function such that for large enough n, for all A &sube [n], |A| &ge f(n), A has a 3-AP. Assume [n] is c-colored. Some color must appear n/c times. If n/c &ge f(n) then there is a 3-AP. Hence we need n/f(n) &ge c. So if n/f(n) &ge c then W(3,c) &le n.

1. Roth's result yields that W(3,c) &le 2^2O(c). ( Graham and Solymosi obtained this result purely combinatorially.)
2. Szemeredi's and Heath-Brown result yields W(3,c) &le 2^cO(1).
3. Bourgain's first result yields W(3,c) &le 2^{c2log c}.
4. Bourgain's second result improves the exponent of c from 2 to 3/2-o(1)
5. Sanders's result results improve the exponent of c from 3/2-o(1) to 4/3-o(1).
6. Sanders NEW RESULT yields W(3,c) &le 2^{c(log c)5}.

The theorems above are of the form: If A is big enough then A has a 3-AP. What about the other side of the ledger: How large can 3-free sets be? There has been an empirical study for small n by Gasarch et al., an unpolished (not yet submitted) survey by Gasarch et al.. (ADDED LATER- SOMEONE POSTED A WEBSITE WHERE YOU CAN FIND ACTUAL LARGE 3-FREE SETS. here it is.) Behrend had the largest 3-free sets for about 50 years before Elkin obtained an improvement. A shorter proof of Elkin's result was given by by Green and Wolf. The current state of affairs on this was summarized in a nice blog entry by Gil Kalai.

Do these result help find lower bounds on W(3,c)? YES! Chandra-Furst-Lipton in their paper on multiparty protocols (of all things!) showed that if A &sube [n] and A is k-free then there is a coloring of [n] with nlog n/|A| colors without any k-AP's. Its an easy prob argument.

SO- how far are we from showing ER2 in the case of k=3? If Sanders NEW result could be improved to |A| &ge n/(log n)^1+&delta or even |A| &ge n/log n (log log n)^1+&delta or any function such that if you divide by n² the series converges then ER2 for k=3 would be proven. How far away is this result? A few weeks ago I would have told you that getting NEXP not in ACC⁰ was not in likely for at least 20 years. Ryan Williams proved me WRONG! Two different knowledgeable sources told me personally that the Erdos Distance Problem had reached an impasse at n^0.864. Guth and Katz proved them WRONG and me WRONG for believing them. Hence, for this one, I do not venture a guess.

What about k-AP's and k-free sets?

1. Gowers has shown that there is a constant c such that if |A| &ge n/(log log n)^c then A has a 4-AP. Gowers also proved that a function c(k) such that if |A| &ge n/(log log n)^c(k) then A has a k-AP. In the paper cited he takes c(k) to be 2^-2k+9; however, I have heard this has been improved.
2. Green and Tao. have shown that there is a constant c such that if |A| &ge n/(log n)^c then A has a 4-AP. Tao's website also indicates they have improved this and a paper is in preparation.
3. Laba and Lacey have a construction of k-free sets which it turns out was already known.

This post has 35 distinct links (UPDATE- now its 37) and mentioned four Field medalists: Roth (1958), Bourgain (1994), Gowers (1998), and Tao (2006). These are probably both complexityblog records.

For more information on this NEW result see also a nice blog posting by Gil Kalai.