# Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

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!

• Assuming the Erdős conjecture (en.wikipedia.org/wiki/…), it can't be significantly more dense than the primes. Feb 25, 2015 at 1:30
• Do you mean "... that avoids arithmetic progressions of length $k$, as a function of $n$ and $k$"? Feb 25, 2015 at 1:45
• There is some discussion in E10 of Guy, Unsolved Problems In Number Theory, although what's there may well be out of date by now. Feb 25, 2015 at 3:24
• If you're interested in lower bounds for the largest set without a $k$-AP, then Behrend's construction is still essentially the best known, and it gives a set of size $n\exp(-c\sqrt{\log n})$ for some constant $c>0$. See this recent paper of Green and Wolf: arxiv.org/pdf/0810.0732v1.pdf Feb 25, 2015 at 4:20
• Thought it would be worth linking to Section 2 of this survey of Gowers on this question as well (since it discusses this problem in detail): arxiv.org/abs/1509.03421 May 8, 2020 at 13:21

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.