16
$\begingroup$

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

$CN(\log\log N)^5/\log N \ge r_3(N) \ge N\exp(-D\sqrt{\log N})$

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?

Thank you.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
19
$\begingroup$

Dear Yui,

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

http://arxiv.org/abs/0810.0732

When formulated this way, I think the construction looks both fairly natural and fairly unimprovable.

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.

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If indeed there is now matching bounds for Behrend's type examples for the question mentioned by Ben this seems to be a dramatic support for the belief by many experts that Behrend's represent the right behavior. $\endgroup$
    – Gil Kalai
    Commented May 8, 2011 at 14:43
  • 2
    $\begingroup$ I believe that Schoen and others have only managed this bound for six or more variables (e.g. $x_1+x_2+x_3+x_4+x_5=5x_6$). $\endgroup$
    – Thomas Bloom
    Commented May 9, 2011 at 5:35
  • $\begingroup$ 2 questions: Is there a reference or a link to Schoen et als result? Is there some similar result (showing exponentially small upper bound for the density) for a version of the cupset problem? $\endgroup$
    – Gil Kalai
    Commented May 25, 2011 at 15:40
  • $\begingroup$ Their paper has just been uploaded to the arXiv, giving the result for six or more variables. They also prove the same bound for the finite field case, i.e. the analogue of the capset problem. $\endgroup$
    – Thomas Bloom
    Commented Jun 9, 2011 at 15:01
  • $\begingroup$ The link is front.math.ucdavis.edu/1106.1601 If I understand correctly the finite field analogs still have Behrend-like bounds so not bounds of the form $(p-t)^n$ for t>0. $\endgroup$
    – Gil Kalai
    Commented Jul 10, 2011 at 8:44
8
$\begingroup$

I am looking forward to answers better than mine, but as a start:

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 suspects the set has the property but one can 'just' not prove it.

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 here) to get further improvements. By exploiting a recent advance on a closeley related problem.

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 $\mathbb{F}_3^r$.`

And, let $r'_3(r)$ denote the analogue constant. This constant $r'_3(r)$ is very similar, but in certain aspects easier to handle. For example, for this constant $r'_3(r) \ll 3^r / r $ is known since well more then a decade; this corresponds to $N/ \log N$ as $3^r$ is the size of the structure. Very recently, this was improved to $$ r'_3(r) \ll 3^r / r^{1+\epsilon} $$.`

And, there is work done to carry-over this progress to the other situation, for an upper bound of $N / (\log N)^{1+\epsilon}$ by Katz–Bateman.

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.

There are various blog posts on the finite field analogue and also the actual problem asked about.

One by Tao http://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/ 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.)

And a couple of recent and long ones by Gowers

http://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/

http://gowers.wordpress.com/2011/01/18/more-on-the-cap-set-problem/

http://gowers.wordpress.com/2011/02/05/polymath6-a-is-to-b-as-c-is-to/

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 could work.

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.

And, to end with a purely sociological reason: if a very convincing argument was known, it should be well-known. So none might be known.

I hope to be wrong on the last point, and learn one from this question.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .