The following result was posted Oct 30, 2010 by Sanders.
For large n, for all A &sube [n], A &ge n(log log n)^{5}/log n then A has a 3AP.I give the history and some misc information about the result.

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 ccolorings of [W] there exists a monochromatic kAP.
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.) 
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:
 (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 kAP.
 (ER2) Let A be a set of natural numbers. If &Sigma_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences.
 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 3AP. The proof used noncombinatorial methods. For an online proofs see either Terry Tao's blog or Alex Iosevich's notes.
 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 GrahamRothchildSpencer in about 2 pages. For an online exposition of this see pages 121130 of Gasarch et al. For an online exposition of the proof for the general case see this exposition by Tao.
 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.
 Shelah obtained primitive recursive bounds on the VDW numbers. His proof was purely combinatorial.
 Gowers proved ER1 in a way that lead to much better bounds on the VDW numbers.
 A purely combinatorial proof of the Density HalesJewitt theorem was done by the polymath group. This is likely the easiest proof of ER1.
 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.
 Szemeredi and HeathBrown 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 3AP. There is a nice exposition by Green. (NOTE if you know of an online source for the original papers let me know.)
 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 3AP.
 Bourgain improved his result to: A &ge n/(log n)^{2/3o(1)}
 Sanders improved Bourgain's result to A &ge n/(log n)^{3/4o(1)}.
 Sanders NEW result is that we only need A &ge n(log log n)^{5}/log n.
Let f be a function such that for large enough n, for all A &sube [n], A &ge f(n), A has a 3AP. Assume [n] is ccolored. Some color must appear n/c times. If n/c &ge f(n) then there is a 3AP. Hence we need n/f(n) &ge c. So if n/f(n) &ge c then W(3,c) &le n.
 Roth's result yields that W(3,c) &le 2^{2O(c)}. ( Graham and Solymosi obtained this result purely combinatorially.)
 Szemeredi's and HeathBrown result yields W(3,c) &le 2^{cO(1)}.
 Bourgain's first result yields W(3,c) &le 2^{c2log c}.
 Bourgain's second result improves the exponent of c from 2 to 3/2o(1)
 Sanders's result results improve the exponent of c from 3/2o(1) to 4/3o(1).
 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 3AP. What about the other side of the ledger: How large can 3free 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 3FREE SETS. here it is.) Behrend had the largest 3free 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! ChandraFurstLipton in their paper on multiparty protocols (of all things!) showed that if A &sube [n] and A is kfree then there is a coloring of [n] with nlog n/A colors without any kAP'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^{2} 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^{0} 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 kAP's and kfree sets?
 Gowers has shown that there is a constant c such that if A &ge n/(log log n)^{c} then A has a 4AP. Gowers also proved that a function c(k) such that if A &ge n/(log log n)^{c(k)} then A has a kAP. In the paper cited he takes c(k) to be 2^{2k+9}; however, I have heard this has been improved.
 Green and Tao. have shown that there is a constant c such that if A &ge n/(log n)^{c} then A has a 4AP. Tao's website also indicates they have improved this and a paper is in preparation.
 Laba and Lacey have a construction of kfree 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.
wow, lots of breakthroughs these days
ReplyDeleteHi Bill.
ReplyDeleteIs there a website that contains the actual sets for the lower bounds obtained in your "small n" preprint.
Thanks.
It's easy to see the converse of ER2 fails. In what ways, by strengthening the hypothesis of the converse (ie the conclusion of ER2 ie "there exist arbitrarily long integer sequences with (some additional property)"), could we get the modified converse of ER2 to be true?
ReplyDeleteIt's Laba and Lacey, not Lacey and Laba.
ReplyDeleteAlas, there is no website of 3free sets.
ReplyDeleteHowever, inspired by your request I may get to work on one. (I need a new HS student
project and that might work.)
Have corrected Laba and Lacey. order.
GASARCH
Wow, that's an impressive reading list AND cool results!
ReplyDeleteAlso on the small n preprint, it doesn't surprise me that the thirds method heuristic ended up performing better than some of the others. I think the latter VC/IndSettype approach in particular is probably "too general" to really capture what's going on, whereas the former is based on a clearer insight into the problem's structure. (On the other hand, I would be quite shocked had it turned out the other way around!)
wasn't Sanders result posted on 30 OCT  that is a month back, not last week...
ReplyDeleteVery informative post!
ReplyDeleteThe other night, I noticed a perfect 3AP of lintballs stuck to my couch. It was remarkable; the total amount of lint on the couch was quite small.
The website http://www.math.uni.wroc.pl/~jwr/nonave.htm contains many examples of sets without 3term APs, many of which are known to be optimal (subject to an exhaustive search, of course).
ReplyDeleteAnon who points out that Sanders posted Oct 30 THANKS, I have corrected the post.
ReplyDeleteKevin O'Bryant who pointed to the website of actual large 3free sets.
THANKS!