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$ – Qiaochu Yuan Feb 25 '15 at 1:30
  • 1
    $\begingroup$ Do you mean "... that avoids arithmetic progressions of length $k$, as a function of $n$ and $k$"? $\endgroup$ – Robert Israel Feb 25 '15 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$ – Gerry Myerson Feb 25 '15 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 '15 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$ – Sam Hopkins May 8 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.

| cite | improve this answer | |
  • 2
    $\begingroup$ Thanks especially for the thumbnail of the construction ("projecting a high-dimensional sphere onto the integers"). $\endgroup$ – Joseph O'Rourke Feb 25 '15 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$ – Kevin O'Bryant Aug 27 '16 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.

| cite | improve this answer | |
  • $\begingroup$ The two links seem to go to the same place. $\endgroup$ – S. Carnahan Sep 2 '15 at 0:37
  • $\begingroup$ Yes they did I think I have corrected it. $\endgroup$ – Kristal Cantwell Sep 2 '15 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.