Thomas Bloom and Olof Sisask: Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions, arXiv:200703528
Once again Extraordinary news regarding Roth Theorem! (I thank Ryan Alweiss for telling me about it and Rahul Santhanam for telling me about Thomas and Olof’s earlier attempts.)
Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . Roth proved that .
A few days ago Thomas Bloom and Olof Sisask proved that for some
This is an extraordinary result!!! I will tell you a little more about it below.
I just heard yesterday the sad news that Ron Graham passed away. Ron was an extraordinary mathematician and an extraordinary person. I first met Ron in Montreal in 1978 and we met many times since then. Ron will be dearly missed.
Back to the new bounds on Roth’s theorem
From an abstract of a lecture by Thomas and Olof: “This is the integer analogue of a result of Bateman and Katz for the model setting of vector spaces over a finite field, and the proof follows a similar structure.”
A catchy (weaker) formulation which goes back to Erdos and Turan is:
Let be a sequence of integers so that , then the sequence contains an arithmetic progression of length three!!
Bloom and Sisask’s result implies, of course, Van der Korput’s result that the primes contain infinitely many 3-terms arithmetic progression as well as Green’s 2005 result asserting it for every dense subset of primes.
Szemeredi’s celabrated result extended Roth’s theorem to arithmetic progression of any fixed size, and Green-Tao celebrated 2008 result asserts that the primes (or a dense subsets of primes) contain arithmetic progression of any length. (The case of 3-term AP is so far much simpler for all the results mentioned below.)
A little more about the history of the problem below the fold
Roth, Szemeredi, Heath-Brown, and Bourgain; Salem-Spencer and Behrend.
Let’s wrire . Roth proved that . Szemeredi and Heath-Brown improved it to for some $latex 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 by Elkin and is discussed here. (Look also at the remarks following that post.)
In 2010 Tom Sanders was able to refine Bourgain’s argument and proved that . A few month later Tom have managed to reach the logarithmic barrier and to prove that
We reported about this outstanding achievement in this blog post and quoted 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).”
The exponent 6 for the loglog term was improved to 4 by Thomas Bloom and recently to 3 by Thomas Schoen in his paper: Improved bound in Roth’s theorem on arithmetic progressions. Schoen uses ingredients from Bateman and Katz’s work (see below).
Cap sets – Meshulam
A closely related problem 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 $latex _n$ is a cap set of maximum size in we can ask how the function behaves. In 1995 Roy Meshulam proved, using Roth’s argument, that . Edell found an example of a cap set of size . 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. In 2007 Tom Sanders managed to achieve it , not for the cup problem, but for a related problem over Z/4Z.
Bateman and Katz
In 2011, Michael Bateman and Nets Katz improved, after many years of attempts by many, the Roth-Meshulam bound. They proved using Fourier methods that for some ! This was very exciting. See these two posts on Gowers’s blog (I,II). This raised the question if the new method allows breaking the logarithmic barrier for Roth’s theorem.
Tim Gowers proposed in 2011 polymath6 to try to break the logarithmic barrier for Roth based on the Bateman-Katz breakthrough. (Here is the wiki; and a related post by Sanders, and a document by Katz) This project did not get off the ground. We can regard the news as giving support that the polymath6 project was timely and of an appropriate level, and also as giving some support to an advantage of the conventional way of doing mathematics compared to the polymath way.
Croot-Lev-Pach-Ellenberg-Gijswijt solution to the Cap set problem via the polynomial method
Next and quite recently came a startling development – the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound . (Croot, Lev, and Pach gave an exponential improvement for the Z/4Z case (see this post) and a few weeks later Ellenberg and Gijswijt used the method for the Z/3Z case (see this post).)
A natural question that many people asked was how this development relates to improving the bounds for Roth perhaps even towards the Behrend bound. We discussed it a little over here and in other places. This is still an interesting possibility.
The new result: Bloom and Sisask
However, just a
few months few years after the Bateman-Katz result have become obsolete for the cap-set problem, the Bateman-Katz method prevailed in this wonderful breakthrough of Bloom and Sisask giving for .
An old post and poll
In an old 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 .