MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 typesetting

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+\epsr^{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+\eps}$N)^{1+\epsilon}$ by Katz--Bateman.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/ 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. 1 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+\eps}$$. And, there is work done to carry-over this progress to the other situation, for an upper bound of $N / (\log N)^{1+\eps}\$ 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