Erdos and Turan asked in 1936: What is the largest subset 
In 1946 Behrend found an example with
Now, sixty years later, Michael Elkin pushed the the 
Here is a description of Behrend’s construction and its improvment as told by Michael himself:
“The construction of Behrend employs the observation that a sphere in any dimension is convexly independent, and thus cannot contain three vectors such that one of them is the arithmetic average of the two other. The new construction replaces the sphere by a thin annulus. Intuitively, one can produce larger progression-free sets because an annulus of non-zero width contains more integer points than a sphere of the same radius does. However, unlike in a sphere, the set of integer points in an annulus is not necessarily convexly independent. To counter this difficulty I show that as long as the annulus is sufficiently thin, the set U of its integer points contains a convexly independent subset W whose size is at least a constant fraction of the size of U. The subset W is, in fact, the exterior set Ext(U) of the set U.
The set U above is the set of integer points of the the intersection of a very thin annulus with a cube. The (minimum) dimension k of the space 
Combinatorics and more 
Two recent followups to Elkin’s work are of interest.
In October, Ben Green and Julia Wolfe published an alternative proof of Elkin’s result: see
http://arxiv.org/abs/0810.0732
A few weeks ago Kevin O’Bryant extended the results to progressions of length k:
see http://arxiv.org/abs/0811.3057v2
It is a great mystery what the answer of Erdos-Turan problem is. Not only that there is a huge gap between the lower and upper bounds, I am not aware of any convincing or even unconvincing heuristic arguments, or ideas-on-record or even thoughts-on-record about where is the truth. This would be a very nice subject for a mathematical dicussion, or brain-storming, or massive collaboration, or small talk, but it is not clear how to start. If you have any idea on the matter, you are most welcomed to express them.
Gil, You’ve given me an idea for a second massive-collaboration project to try if the first one fails (or even more so if it succeeds). It’s not quite what you suggest here, but it’s closely related. I won’t say more at this stage, except that I have two heuristic arguments that the correct bound, at least for progressions of length 3, should be roughly what is given b the Behrend bound. One is the unconvincing argument that I once thought of a construction to obtain a lower bound for the triangle-removal problem and the bound that came out was exactly the Behrend bound. This argument is unconvincing because when I thought about it a bit more it became clear to me that the construction was actually very similar to Behrend’s. However, it still suggested to me that Behrend’s construction wasn’t just a clever trick, but something rather natural. The other argument I’m afraid I’ll have to be even less precise about, but I recently came up with a slightly different way of proving Roth’s theorem, which I haven’t actually written up properly so can’t guarantee the correctness of, but it looks from that argument as though there is a chance of using strong bounds for Freiman’s theorem (which seem highly plausible, even though nobody has yet managed to prove them) to obtain Behrend-type bounds in Roth. Even this might be a good “open source” project, though it would be too technical to be massively collaborative.
Dear Tim, thanks a lot for the remark!
Any heuristic argument about the answer to Erdos-Turan problem for k=3 and in particulat heuristic arguments suggesting that Behrend’s bound gives the true behavior would be great.
(I am a little confused about the description of your first argument since it seems you describe a construction similar to Behrend’s and not an argument for a macthing bound from the other direction.)
In the second heuristics, I suppose you mean that the strong bounds for Freiman’s theorem may give Behrend-type upper bounds for the Erdos-Turan problem; namely show that a set S in {1,2,…,n} without a 3-term A P has at most n/g(n) elements where g(n) behaves like
For the interested readers here is a brief description of the state of affairs:
It is known that for some constant c >0 a subset of {1,2,…,n} of size
must contain an AP of size 3 (The best value of c is due to Bourgain and it is below 1.) Getting this for c>1 will apply for 3-terms AP in primes and it looks out of reach.
For some constant 0<c<1 (c=1/2 if you take the log with base 2), it is known (Behrend) that there are sets S in {1,2,…,n} of size
without a 3-term AP.
So the gap is huge!!
If I have to draw a line in the middle I would ask: For the correct value of g(n), is g(g(n)) super logarithmic or sublogarithmic?
Just to clarify the first argument, what I meant was that when I first thought of the other construction, I was hoping that it would give a better bound than the Behrend bound, but then it gave exactly the same bound. That led me to think that perhaps there was a natural obstacle there, which might be the obvious one that it is the correct bound. When I realized that the new construction was fairly similar to Behrend’s, I felt that less strongly (since it no longer felt like an independent piece of experimental evidence) but I still had the feeling that the alternative construction had arisen in a natural enough way to suggest that that bound could be the right one. Previously, Behrend’s construction had felt like a piece of magic that left me with no clue about whether or not it could be improved.
Dear Tim,
You wrote “I recently came up with a slightly different way of proving Roth’s theorem, which I haven’t actually written up properly so can’t guarantee the correctness of, but it looks from that argument as though there is a chance of using strong bounds for Freiman’s theorem (which seem highly plausible, even though nobody has yet managed to prove them) to obtain Behrend-type bounds in Roth. Even this might be a good “open source” project, though it would be too technical to be massively collaborative.”
This is extremely interesting and I would be very interested to hear what these strong bounds for Freiman are. Proving a Behrend-type bounds in Roth seems completely off-scale and out-of-reach. (And I do not see any strong reason to believe that this is were the truth is.)
As I said, as something orthogonal to collective (or massive) efforts to prove something (like your recent polymath 1) or formulate a conjecture (polymath2) I wonder if mathematically-looking-beyond-the-horizon-discussion is possible and if it can be fruitfull. (I tend to think that it is possible, not particularly fruitfull, not entirely respectible, but can be fun anyway.) I may try to initiate such a discussion at some later time.
Pingback: An Open Discussion and Polls: Around Roth’s Theorem « Combinatorics and more
Dear Michael Elkin.
I believe your improvement on Behrend can be improved further. In fact, one can get far more than a c*log(n)^(1/2) factor improvement, we get more like a factor exp(c*log(n)^(1/2)).
The two ideas needed are as follows.
IDEA#1
the set of integer points on a sphere of radius R in n-dimensions, is uniformly distributed angularly if n>=3 when R becomes large. (Known fact.)
That means you can use integrals (e.g over spherical caps) instead of sums, etc for purposes of obtaining estimates.
IDEA#2
Forget this idea of making all the points in your spherical shell be
“convexly independent” (by which, I assume, you mean all of them are extreme points).
Instead, proceed as follows. Choose a sphere of radius r and
thickness s of the shell. Pick each integer point inside that shell to be in your set or not, by tossing a coin. Argue that the expected number of violations
of a+b=2c you will get in this way, is going to be less than a constant times
the number of points in the shell. The argument can be made because the only way to get a violation is if the two points a and b are close together which is a small-volume spherical cap, i.e. small probability of occurrence.
Throw them out; there are now no violations. In this way, at the cost of a constant factor due to the discards and cointossing, we have made (or anyhow proved the existence of) an average-free set.
The gain far exceeds the loss because you can actually make the shell thickness s be a constant power of r instead of logarithmic.
IDEA #3
By the way, Behrend was stupid to use a sphere based on the quadratic polynomial x^2. He should have based it on (x-H) * (x-H+1) for a suitable number H about halfway thru the allowed digit range.
This yields a big constant factor improvement.
Warren D. Smith
Sorry, I miscalculated (above comment) it appears this idea does not improve
over Elkin.
Pingback: Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier | Combinatorics and more
Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more
Pingback: To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem! | Combinatorics and more
Pingback: Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon | Combinatorics and more
Pingback: To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols | Combinatorics and more
Pingback: To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k) | Combinatorics and more
Pingback: Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles – Math Solution