Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Click here for the most recent polymath3 research thread.

I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

Roth proved that g(n) \ge log logn. Szemeredi and Heath-Brown improved it to g(n) \ge log^cn for some 0″ src=”http://l.wordpress.com/latex.php?latex=c%3E0&bg=ffffff&fg=000000&s=0″ alt=”c>0″ /> (Szemeredi’s argument gave c=1/4.) Jean Bourgain improved the bound in 1999 to c=1/2 and in 2008 to c=2/3 (up to lower order terms).

Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size n^c.  Salem and Spencer improved this bound to g(n) \le e^{logn/ loglogn}. Behrend’s upper bound from 1946 is of the form g(n) \le e^{C\sqrt {\log n}}. A small improvement was achieved recently by Elkin and is discussed here.  (Look also at the remarks following that post.)

In an earlier post we asked: How does g(n) behave? Since we do not really know, will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? (I still don’t know if softly discussing this or other mathematical problems is a fruitful idea, but it can be enjoyable.)

We even had a poll collecting people’s predictions about g(n).  Somewhat surprisingly 18.18% of answerers predicted that g(n) behaves like (\log n)^c for some c<1. Be the answer as it may be, reaching  the logarithmic barrier was considered extremely difficult.

A couple of months ago Tom Sanders was able to refine Bourgain’s argument and proved that g(n) \ge (\log n)^{3/4}. Very recently Tom have managed to reach the logarithmic barrier and to prove that

g(n) \ge (\log n)/(\log \log n)^{5}.

Quoting from his paper: “There are two main new ingredients in the present work: the first is a way of transforming sumsets introduced by Nets Katz and Paul Koester in 2008, and the second is a result on the L_p-invariance of convolutions due to Ernie Croot and Olof Sisask (2010).”

This is a truly remarkable result.

Let me mention that a closely related problem can be asked in \Gamma=\{0,1,2\}^n. It is called the cap set problem. A subset of \Gamma is called a cap set if it contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). If A is a cap set of maximum size we can ask how the function h(n)=3^n/|A| behaves. Roy Meshulam proved, using Roth’s argument, that h(n) \ge n. Edell found an example of a cap set of size 2.2^n. So h(n) \le (3/2.2)^n. Again the gap is exponential.  What is the truth? Improving Meshulam’s result may be closely related to crossing the \log n barrier for Roth’s theorem. Two and a half years ago Tom Sanders himself managed to achieve it , not for the cup problem, but for a related problem over Z/4Z. Passing the logarithmic barrier for Roth’s theorem suddenly looks within reach. Such a development will also be amazing.

But we met a short time later…

About these ads
This entry was posted in Combinatorics, Open problems and tagged , , , , , . Bookmark the permalink.

9 Responses to Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

  1. Sunkhiroes says:

    Where is Tim Gower…

    • Gil Kalai says:

      Tim Gowers found bounds of the form g_r(n) \le (\log\log n)^{c_r} where g_r(n) is defined as in the post but with “arithmetic progressions(AP) of length 3″ replaced with “AP of length r”. To keep the post finite, I did not discuss larger AP’s, not the related questions about AP in primes, and not many other related things. Tim was also Tom’s Ph. D advisor and he also expressed his belief that g(n) is close to Behrend’s upper bound. (I also first heard about Tom’s results from Tim Gowers a couple of weeks ago.)

  2. KATRINA-KAIF-LESSONS IN SEXY-SAREE says:

    what if the value of r – ” arithmetic progressions(AP) of length 3″ replaced with “AP of length r” -> increases asymptotically?

    cheers.,
    “ISABEL-KAIF”
    via olga-and-katrina-kaif

  3. Gil Kalai says:

    A very detailed blog posting about the new results and earlier results was written by William Gasarch and is posted in “computational complexity” http://blog.computationalcomplexity.org/2010/12/breakthrough-result-on-density-and-3.html

  4. Ernie Croot says:

    This is indeed a very nice result! It would be neat if one could somehow extend this to give improvements for kAPs, k >= 4.

    I suspect that the CAP set problem in F_3^n won’t last too much longer — I expect it won’t be long before someone like Tom improves upon the Roth-Meshulam density bound of c/n (where c > 0 is some constant), to show r_3(F_3^n) = o(3^n).

    In fact, I can imagine that something like the following might do it: if the usual Roth-Meshulam Fourier proof just barely fails to show that some set S of density just below density c/n has 3APs, then one can show that that set has a very unusual sub-structure. Using a hypothetical generalization of the L^p-invariance result of myself and Olof Sisask, in combination with this substructure, I feel it ought to be possible to show that there is a quasi-random subset T of some coset a+H of some subgroup H with dim(H) > loglog(n) or something, such that |S intersect T| >> |T|. Then, using something like a finite field generalization of Green’s ideas from Roth’s Theorem in the Primes (to show that a positive density subset of a highly quasirandom set contains 3APs), one should be able to show that S intersect T has a 3AP, which then means that S has a 3AP.

  5. Gil Kalai says:

    Dear Ernie, this is very interesting. Of course the sweetest prize (The Hebrew saying is “the cherry in the cream” ok I suppose its somewhat like “the Jewel in the crown” in English) for breaking the log n barrier for 3-AP and r-AP was the results about primes until Green and Tao found the way to use quasi randomness and Szemeredi’s theorem for getting the cherry instead. It did not occur to me before that the quasi randomness idea can be used (perhaps already been used) to improve bounds on general Roth-type theorems (rather than avoid the need for better bound for specific cases). Also I wished that an opportunity will arise for an explanation of the Croot-Sisask L^p invariance result. So if you are in the mood to explain about it, this could be great.

  6. Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more

  7. Pingback: Theorems Are Forever: A Great One From 1492 « Gödel’s Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s