An Open Discussion and Polls: Around Roth’s Theorem

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

How does g(n) behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is?

Update 1: for the discussion: Here are a few more specific questions that we can wonder about and discuss.

1) Is the robustness of Behrend’s bound an indication that the truth is in this neighborhood.

2) Why arn’t there analogs for Salem-Spencer and Behrend’s constructions for the cup set problem?

3) What type of growth functions can we expect at all as the answer to such problems?

4) Where is the deadlock in improving the upper bounds for AP-free sets?

5) What new kind of examples one should try in order to improve the lower bounds? Are there some directions that were already extensively explored?

6) Can you offer some analogies? Other problems that might be related?

 

Continue reading

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, Continue reading