At first sight it may seem that the greedy algorithm yields the densest subset of that is free of arithmetic progressions of length $3$ . It is not hard to show that the greedy algorithm yields the set of numbers that lack digit $2$ in their ternary development. Density of such numbers is $O(N^{\log_3 2-1})$ .

However, in 1946 Behrend[1] constructed much denser subsets that are free of arithmetic progressions. His major idea is that if we were looking for a progression-free sets in $\mathbb{R}^n$ , then we could use spheres. So, consider an $d$ -dimensional cube $[1,n]^d \cap \mathbb{Z}^d$ and family of spheres for . Each point in the cube is contained in one of the spheres, and so at least one of the spheres contains $n^d/d n^2$ lattice points. Let us call this set $A$ . Since sphere does not contain arithmetic progressions, $A$ does not contain any progressions either. Now let $f$ be a Freiman isomorphism from $A$ to a subset of $\mathbb{Z}$ defined as follows. If is a point of $A$ , then , that is, we treat $x_i$ as $i$ 'th digit of $f(x)$ in base $2n$ . It is not hard to see that $f$ is indeed a Freiman isomorphism of order $2$ , and that . If we set $d=c\sqrt{\ln N}$ , then we get that there is a progression-free subset of of size at least $N e^{-\sqrt{\ln N}(c\ln 2+2/c+o(1)}$ . To maximize this value we can set $c=\sqrt{2/\ln 2}$ . Thus, there exists a progression-free set of size at least \begin{equation*} N e^{-\sqrt{8\ln 2 \ln N}(1+o(1))}. \end{equation*} This result was later generalized to sets not containing arithmetic progressions of length $k$ by Rankin[3]. His construction is more complicated, and depends on the estimates of the number of representations of an integer as a sum of many squares. He proves that the size of a set free of $k$ -term arithmetic progression is at least \begin{equation*} N e^{-c (\log N)^{1/(k-1)}}. \end{equation*} On the other hand, Moser[2] gave a construction analogous to that of Behrend, but which was explicit since it did not use the pigeonhole principle.

References

1

Felix A. Behrend.
On the sets of integers which contain no three in arithmetic progression.
Proc. Nat. Acad. Sci., 23:331-332, 1946.
Zbl 0060.10302.

2

Leo Moser.
On non-averaging sets of integers.
Canadian J. Math., 5:245-252, 1953.
Zbl 0050.04001.

3

Robert A. Rankin.
Sets of integers containing not more than a given number of terms in arithmetical progression.
Proc. Roy. Soc. Edinburgh Sect. A, 65:332-344, 1962.
Zbl 0104.03705.