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
    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
    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
    Oct 1, 2021 at 14:32
  • 1
    $\begingroup$ @GHfromMO ok, done $\endgroup$
    – Fedor Petrov
    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
    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
    Oct 1, 2021 at 19:47

Your Answer

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

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