4
$\begingroup$

I cannot find the exact same question asked anywhere in this site. I know the related Green-Tao theorem but the gaps between consecutive primes can grow unbounded so it does not seem helpful to answer this question. What I have tried: assume the largest gap is D and without loss of generality it appears infinitely often. Then I try to apply the pigeonhole principle but don't know how. Thanks in advance.

Added thought: will there always be a subsequence forming an infinitely long arithmetic progression in the original sequence? I think the answer is NO.

Improve this question
$\endgroup$
10
  • 10
    $\begingroup$ Your set has positive density, hence Szemerédi's theorem applies, see en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem $\endgroup$
    – Alexander Kalmynin
    Commented Oct 1, 2021 at 13:40
  • 2
    $\begingroup$ If the gaps are bounded, say by $T$, a much easier Van der Varden theorem also helps: color $n$ to color $i\in \{1,\ldots,T\} $ if $nT+i$ belongs to your set and find a large monochromatic progression. $\endgroup$
    – Fedor Petrov
    Commented Oct 1, 2021 at 14:01
  • 1
    $\begingroup$ @FedorPetrov I suggest that you turn your comment into an answer so that this question can be closed. $\endgroup$
    – GH from MO
    Commented Oct 1, 2021 at 14:32
  • 1
    $\begingroup$ @GHfromMO ok, done $\endgroup$
    – Fedor Petrov
    Commented Oct 1, 2021 at 19:37
  • 2
    $\begingroup$ @GHfromMO, usually we close a question so that it cannot be answered. It seems odd to answer a question so that it can be closed. $\endgroup$
    – Gerry Myerson
    Commented Oct 2, 2021 at 5:48

1 Answer 1

Reset to default
9
$\begingroup$

You may of course use Szemeredi theorem, as suggested by Alexander Kalmynin.

If you need a more elementary argument, you may apply Van der Waerden theorem as follows: assuming that the gaps are bounded by $T$, color every positive integer $n$ to the color $i\in \{1,\dots,T\}$ if $nT+i$ belongs to your set (so each large enough integer gets at least one color), and find a large monochromatic arithmetic progression. It corresonds to a large progression in the initial set.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Let $S$ be the OP's set. I think we can simply define the color of a positive integer $n$ as $\min\{i\geq 1:n+i\in S\}$. By assumption, the color of each $n$ is bounded by $T$, so we used finitely many colors. By van der Waerden's theorem, there is an arbitrary long arithmetic progression $P$ which is monochromatic. If the color of $P$ is $i$, then $P+i$ is a long arithmetic progression in $S$. $\endgroup$
    – GH from MO
    Commented Oct 1, 2021 at 19:47

You must log in to answer this question.

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