Roth's theorem and Behrend's lower bound - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:23:37Z http://mathoverflow.net/feeds/question/64211 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64211/roths-theorem-and-behrends-lower-bound Roth's theorem and Behrend's lower bound Yui Nishizawa 2011-05-07T16:33:21Z 2011-09-30T01:05:45Z <p>Roth's theorem on 3-term arithmetic progressions (3AP) is concerned with the value of $r_3(N)$, which is defined as the cardinality of the largest subset of the integers between 1 and N with no non-trivial 3AP. The best results as far as I know are that</p> <p>$CN(\log\log N)^5/\log N \ge r_3(N) \ge N\exp(-D\sqrt{\log N})$</p> <p>for some constants $C,D>0$. The upper bound is by Tom Sanders in 2010 and the lower bound is by Felix Behrend dating back to 1946. My question is this: even though the upper and lower bounds are still quite a bit apart, I hear mathematicians hinting that something close to Behrend's lower bound might be giving the correct order, such as in Ben Green's paper "Roth's theorem in the primes", and I am curious as to where this is coming from. Is it because there has been no significant improvement on the lower bound (whereas there has been lot's of work on the upper bound)? Or in analogy to a similar type of problem? Or maybe just a casual remark? Or some other reason?</p> <p>Thank you.</p> http://mathoverflow.net/questions/64211/roths-theorem-and-behrends-lower-bound/64217#64217 Answer by quid for Roth's theorem and Behrend's lower bound quid 2011-05-07T17:38:41Z 2011-09-30T01:05:45Z <p>I am looking forward to answers better than mine, but as a start:</p> <p>My understanding is that, yes, part of the reason is how difficult it is to improve the lower bound. After all, after Behrend it took 60+ years to get an improvement on it. And, it is (as far as I knnow) thus not at all clear where a much larger example should come from; e.g., there is no construction of a much larger set where one <em>suspects</em> the set has the property but one can 'just' not prove it. </p> <p>In contrast, for the upper-bound the progress was more continous with a variety of improvements over the years. And, also at the moment there is an ongoing effort (with the details of which I am unfamiliar, but there is a Polymath-project, Polymath6, see <a href="http://polymathprojects.org/" rel="nofollow">here</a>) to get further improvements. By exploiting a recent advance on a closeley related problem.</p> <p>This closely related problem is a so-called finite field analogue; instead of considering the problem for integers one rather considers it for subsets of $r$-dimensional vector-spaces over the field with $3$ elements, so <code>$\mathbb{F}_3^r$.</code></p> <p>And, let <code>$r'_3(r)$</code> denote the analogue constant. This constant <code>$r'_3(r)$</code> is very similar, but in certain aspects easier to handle. For example, for this constant <code>$r'_3(r) \ll 3^r / r$</code> is known since well more then a decade; this corresponds to $N/ \log N$ as <code>$3^r$</code> is the size of the structure. Very recently, this was improved to <code>$$r'_3(r) \ll 3^r / r^{1+\epsilon}$$.</code></p> <p>And, there is work done to carry-over this progress to the other situation, for an upper bound of <code>$N / (\log N)^{1+\epsilon}$</code> by Katz&ndash;Bateman.</p> <p>So for the upper-bound there is continous progress and further hope for progress, as there are ideas for improvement. While the lower bound somehow seems more stubborn and undpredictable.</p> <p>There are various blog posts on the finite field analogue and also the actual problem asked about.</p> <p>One by Tao <a href="http://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/" rel="nofollow">http://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/</a> yet note this is four years old, and there was progress since. (It also mentions differing opinions on he finite field analogue; so there is no universal conjecture there.)</p> <p>And a couple of recent and long ones by Gowers</p> <p><a href="http://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/" rel="nofollow">http://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/</a></p> <p><a href="http://gowers.wordpress.com/2011/01/18/more-on-the-cap-set-problem/" rel="nofollow">http://gowers.wordpress.com/2011/01/18/more-on-the-cap-set-problem/</a></p> <p><a href="http://gowers.wordpress.com/2011/02/05/polymath6-a-is-to-b-as-c-is-to/" rel="nofollow">http://gowers.wordpress.com/2011/02/05/polymath6-a-is-to-b-as-c-is-to/</a> </p> <p>So, in summary, I believe that a large part is the unclearness where a much larger bound should possibly come from; while the upper bounds seems more flexible: they are very hard to actually improve, yet there seems more hope and ideas what <em>could</em> work.</p> <p>However, as there seems to be no clear consensus on the finite field analogue, it might be the case that the opinions are actually not as fixed on the problem at hand either.</p> <p>And, to end with a purely sociological reason: if a very convincing argument was known, it should be <em>well-known</em>. So none might be known. </p> <p>I hope to be wrong on the last point, and learn one from this question. </p> http://mathoverflow.net/questions/64211/roths-theorem-and-behrends-lower-bound/64218#64218 Answer by Ben Green for Roth's theorem and Behrend's lower bound Ben Green 2011-05-07T17:40:53Z 2011-05-07T17:40:53Z <p>Dear Yui,</p> <p>It's only slightly more than a casual remark. Our inability to find a better example is certainly a big reason for believing that Behrend's bound is correct. Julia Wolf and I slightly rehashed the proof of Behrend's bound</p> <p><a href="http://arxiv.org/abs/0810.0732" rel="nofollow">http://arxiv.org/abs/0810.0732</a></p> <p>When formulated this way, I think the construction looks both fairly natural and fairly unimprovable.</p> <p>Also, there are beginning to be hints as to the correct behaviour coming from apparently similar equations such as $x_1 + x_2 + x_3 = 3x_4$. I think that Schoen and others, using work of Sanders, may have improved the bounds for this equation to $N \exp(-\log^c N)$, though I'm not certain about this.</p> <p>Despite these remarks it is not known whether better bounds for Roth's theorem follow from any other more "natural" conjectures, such as the Polynomial Freiman-Ruzsa conjecture, so any suggestion that Behrend is sharp is somewhat tenuous. Some other people think differently, I believe - that it may not be sharp.</p>