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 
is a subset of 
of maximum cardinality not containing an arithmetic progression of length 3. Let 
.
Roth proved that 
. Szemeredi and Heath-Brown improved it to 
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 
.) Jean Bourgain improved the bound in 1999 to 
and in 2008 to 
(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 
. Salem and Spencer improved this bound to 
. Behrend’s upper bound from 1946 is of the form 
. 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 
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 
. Somewhat surprisingly 18.18% of answerers predicted that behaves like 
for some 
. 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 
. Very recently Tom have managed to reach the logarithmic barrier and to prove that
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 
-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 
. It is called the cap set problem. A subset of 
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 
is a cap set of maximum size we can ask how the function 
behaves. Roy Meshulam proved, using Roth’s argument, that 
. Edell found an example of a cap set of size 
. So 
. Again the gap is exponential. What is the truth? Improving Meshulam’s result may be closely related to crossing the 
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…
Like this:
Like Loading...
Related
Where is Tim Gower…
Tim Gowers found bounds of the form
where 
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 
is close to Behrend’s upper bound. (I also first heard about Tom’s results from Tim Gowers a couple of weeks ago.)
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
Good question. If I remember correctly
behaves in Gowers’s proof like 
.
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
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.
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.
Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more
Pingback: Theorems Are Forever: A Great One From 1492 « Gödel’s Lost Letter and P=NP
Pingback: To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem! | Combinatorics and more
Pingback: Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon | Combinatorics and more