7
$\begingroup$

I would like to understand the conditions that support the Green-Tao Theorem, which established that the primes contain arbitrarily long arithmetic progressions.

I am wondering:

Q. Is it difficult to define an infinite set $S$ of natural numbers that mimics the $\sim n / \log n$ distribution of the primes (and perhaps other prime properties), but yet fails to contain arbitrarily long arithmetic progressions?

For example, $S$ might be the lucky numbers (OEIS A000959), or Hawkins' "random primes." Do either of these avoid arbitrarily long arithmetic progressions?

My intuition is that it is easier to avoid such progressions than it is to establish their existence.

MSE question unanswered: Do lucky numbers contain arbitrarily long arithmetic progressions?

Improve this question
$\endgroup$
8
  • 10
    $\begingroup$ I believe a famous conjecture of Erdős says that it is not possible to define such a set: en.wikipedia.org/wiki/…. $\endgroup$
    – Sam Hopkins
    Commented May 7, 2020 at 21:30
  • 3
    $\begingroup$ (I also remember hearing from experts that the density from Erdős's conjecture is not really believed to be the 'true' boundary for containing arbitrarily long arithmetic progressions, so in some sense the conjecture is 'misleading.') $\endgroup$
    – Sam Hopkins
    Commented May 7, 2020 at 21:32
  • 5
    $\begingroup$ See Section 2 of this survey of Gowers, which discusses this problem: arxiv.org/abs/1509.03421 $\endgroup$
    – Sam Hopkins
    Commented May 7, 2020 at 21:37
  • 2
    $\begingroup$ I can define such a set greedily, but I do not know its density. Pick the first member to be 1. Now pick the next smallest unpicked and unmarked member: this will 2. Now mark all numbers which form a three term arithmetic progression with previously picked members, and disallow those from the sequence. I get 1,2,4,5,10,11,13,14,22 . If you disallow just four terms, the sequence becomes more dense (and more challenging to construct). Gerhard "This May Be In OEIS" Paseman, 2020.05.07. $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2020 at 21:43
  • 3
    $\begingroup$ I now see that you asked a very similar question here 5 years ago: mathoverflow.net/questions/198387/… $\endgroup$
    – Sam Hopkins
    Commented May 7, 2020 at 23:16

1 Answer 1

Reset to default
11
$\begingroup$

This is likely impossible.

Indeed the largest sets known to be free of arbitrarily long arithmetic progressions asymptotically satisfy $| [ A \cap [1, n] | \lesssim_{k} n / \log^{k} n$ for all $k>1$, and it is widely believed that these examples are near maximal.

The Erdos-Turan conjecture mentioned in the comments is almost equivalent to the claim that any set of relative density greater than $n/ \log n$ contains arbitrary long arithmetic progressions. As remarked above, this is likely true for even sparser sets.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Does this mean that proving that the number $T(x)$ of twin primes below $x$ fulfills $T(x)\asymp x/\log^{2}x$ would imply that the sequence of twin primes contains arbitrarily long arithmetic progressions? $\endgroup$
    – Sylvain JULIEN
    Commented May 7, 2020 at 22:55
  • 3
    $\begingroup$ @SylvainJULIEN Well, one would need to prove density of twin-primes and prove this generalization of Erdos-Turan, bit. :-) $\endgroup$
    – Steven Stadnicki
    Commented May 7, 2020 at 23:01

Not the answer you're looking for? Browse other questions tagged .