Pushing Behrend Around

Erdos and Turan asked in 1936: What is the largest subset S of {1,2,…,n} without a 3-term arithmetic progression?

In 1946 Behrend found an example with |S|=\Omega (n/2^{2 \sqrt 2 \sqrt {\log_2n}} \log^{1/4}n.)

Now, sixty years later, Michael Elkin pushed the the log^{1/4} n factor from the denominator to the enumerator, and found a set with  |S|=\Omega (n \log^{1/4}n/2^{2 \sqrt 2 \sqrt {\log_2n}} ). !

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 R^k  in which this body has non-zero volume is not constant, but rather it tends to infinity logarithmically with the radius of the annulus. Consequently, it becomes not trivial to estimate the volume of this body, leaving alone the the number of integer points that it contains.  In addition, most known estimates for the discrepancy  between the number of integer points and the volume assume that the dimension is fixed, and thus these estimates are inapplicable in this case.  Moreover, since the annulus is very thin, its volume is not much larger than its surface area, and thus crude estimates of the discrepancy between the number of integer points and the volume do not suffice. Showing more precise estimates involves a rather delicate analysis.”

About these ads
This entry was posted in Combinatorics, Updates and tagged , , . Bookmark the permalink.

10 Responses to Pushing Behrend Around

  1. Gil Kalai says:

    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.

  2. gowers says:

    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.

  3. Gil Kalai says:

    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 exp (log^c n)

    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 n/(log^cn) 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 n/exp (log^cn) 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?

  4. gowers says:

    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.

  5. Gil Kalai says:

    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.

  6. Pingback: An Open Discussion and Polls: Around Roth’s Theorem « Combinatorics and more

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

  8. Sorry, I miscalculated (above comment) it appears this idea does not improve
    over Elkin.

  9. Pingback: Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier | Combinatorics and more

  10. Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s