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!

  • 8
    $\begingroup$ Assuming the Erdős conjecture (en.wikipedia.org/wiki/…), it can't be significantly more dense than the primes. $\endgroup$ Feb 25, 2015 at 1:30
  • 1
    $\begingroup$ Do you mean "... that avoids arithmetic progressions of length $k$, as a function of $n$ and $k$"? $\endgroup$ Feb 25, 2015 at 1:45
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 25, 2015 at 3:24
  • 6
    $\begingroup$ 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 $\endgroup$
    – Lucia
    Feb 25, 2015 at 4:20
  • 1
    $\begingroup$ 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 $\endgroup$ May 8, 2020 at 13:21

2 Answers 2


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.

  • 2
    $\begingroup$ Thanks especially for the thumbnail of the construction ("projecting a high-dimensional sphere onto the integers"). $\endgroup$ Feb 25, 2015 at 11:37
  • $\begingroup$ I worked out the lower bound in detail (you can do slightly better than concentric spheres by using concentric spherical annuli and then throwing out a few terms): combinatorics.org/ojs/index.php/eljc/article/view/v18i1p59 $\endgroup$ Aug 27, 2016 at 0:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.