The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression.
I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid
arbitrarily long sequences of elements of $S$ in arithmetic progression?
To make this more precise (following a comment by Robert Israel),
Q. What is the cardinality of the largest subset $S_n$ of $[1,n]=\{1,2,3,\ldots,n\}$
that avoids $k$-term arithmetic progressions of elements in $S_n$,
as a function of $n$ and $k$?
As $n \to \infty$, can the density be significantly more dense than the primes density, $n / \log_e n$?
I suspect this is a well-studied question, in which case quotes and/or pointers would suffice. Thanks!
Best Answer
You are essentially asking for quantitative estimates on Szemerédi's theorem, which states that the largest subset of $[1,n]$ without a k-term arithmetic progression has size $o(n)$. To be precise, let us define $r_k(n)$ to be the largest subset of [1,n] with no k-term arithmetic progression. Then a construction due to Behrend (essentially projecting a high-dimensional sphere onto the integers) shows that $$ r_3(n) = \Omega\left(n e^{-c \sqrt{\log n}}\right), $$ while a result of Bloom (moderately improving on a result of Sanders), shows that $$ r_3(n) = O\left(n \frac{(\log \log n)^4}{\log n}\right). $$ For general $k$, the best known upper bound is due to Gowers and says that $$ r_k(n) = O\left(\frac{n}{(\log \log n)^{c_k}}\right) $$ for an appropriate $c_k$. Behrend's construction clearly provides a lower bound in this case as well, but may be improved a little by projecting a collection of concentric spheres. There is some evidence (see, for example, http://arxiv.org/pdf/1408.2568.pdf) to believe that the lower bound is closer to the truth.