An improved construction of progression-free sets

The problem of constructing dense subsets S of {1, 2, ..., n} that contain no three-term arithmetic progression was introduced by ErdAs and Turan in 1936. They have presented a construction with vertical bar S vertical bar = Omega(n(3)(log)2) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is vertical bar S vertical bar = Omega(n/2(2 root 2) root log(2)(n) . log(n)(1/4)). Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend has been reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(root log n), and shows that vertical bar S vertical bar = Omega (n/2(2 root 2) root log(2)(n) .log(1/4) n). In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained. We also present an application of our proof technique in Discrete Geometry.