Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

Question

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!

Answer 1

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.

Answer 2

If a sequence avoids three term arithmetic progressions it is less than ((log log N)^4)N/log N according to "A Quantitative improvement for Roths’s Theorem On Arithmetic Progressions" which is available here

The above preprint also claims that the result of "On Roth’s Theorem On Progressions" availabe on arxiv here is in error in claiming O(((log log N)^5 N/log N) and that it should be O(((log log N)^6 N/log N).

So the upper bound even for three term arithmetic progressions is at most a factor of log log N to the fourth power better than N/log N if the preprint in the first paragraph is correct.