Mathematics – Number Theory
Scientific paper
2008-01-28
Mathematics
Number Theory
Scientific paper
The problem of constructing dense subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = \Omega(n^{\log_3 2}) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is |S| = Omega({n \over {2^{2 \sqrt{2} \sqrt{\log_2 n}} \cdot \log^{1/4} n}}). 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 was reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(\sqrt{\log n}), and shows that |S| = Omega({n \over {2^{2 \sqrt{2} \sqrt{\log_2 n}}}} \cdot \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.
No associations
LandOfFree
An Improved Construction of Progression-Free Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Improved Construction of Progression-Free Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improved Construction of Progression-Free Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-157047