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…