| Version 2 |
Version 1 |
| At first sight it may seem that the greedy algorithm yields the densest subset of $\{1,2,\dotsc,N\}$ that is free of arithmetic progressions. 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^{1-\log_2 3})$. |
At first sight it may seem that the greedy algorithm yields the densest subset of $\{1,2,\dotsc,N\}$ that is free of arithmetic progressions. 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^{1-\log_2 3})$. |
| $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 |
$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*} |
\begin{equation*} |
|
N e^{-\sqrt{8\ln 2 \ln N}(1+o(1))}.
|
N e^{-\sqrt{8\ln 2 \ln N}(1+o(1)).
|
| \end{equation*} |
\end{equation*} |
| \begin{thebibliography}{1} |
\begin{thebibliography}{1} |
| \bibitem{cite:behrend_szem_low} |
\bibitem{cite:behrend_szem_low} |
| Felix~A. Behrend. |
Felix~A. Behrend. |
| \newblock On the sets of integers which contain no three in arithmetic |
\newblock On the sets of integers which contain no three in arithmetic |
| progression. |
progression. |
| \newblock {\em Proc. Nat. Acad. Sci.}, 23:331--332, 1946. |
\newblock {\em Proc. Nat. Acad. Sci.}, 23:331--332, 1946. |
| \newblock \PMlinkexternal{Zbl 0060.10302}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0060.10302}. |
\newblock \PMlinkexternal{Zbl 0060.10302}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0060.10302}. |
| \end{thebibliography} |
\end{thebibliography} |
| %@ARTICLE{cite:behrend_szem_low, |
%@ARTICLE{cite:behrend_szem_low, |
| % author = {Felix A. Behrend}, |
% author = {Felix A. Behrend}, |
| % title = {On the sets of integers which contain no three in arithmetic %progression}, |
% title = {On the sets of integers which contain no three in arithmetic %progression}, |
| % journal = {Proc. Nat. Acad. Sci.}, |
% journal = {Proc. Nat. Acad. Sci.}, |
| % volume = 23, |
% volume = 23, |
| % year = 1946, |
% year = 1946, |
| % pages = {331--332} |
% pages = {331--332} |
| %} |
%} |
