Do the primes contain an infinite almost arithmetic progression?

The answer is NO.

Note that any set $S$ containing an infinite almost arithmetic progression satisfies $$ \underline{\mbox{dens}}(S):= \liminf_n \frac{(\mbox{card}( S \cap [0,n]))}{n} \geq \frac{1}{d}$$

But the primes have density $0$.


Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.

The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_{n+1}-p_n=O(\sqrt{p_n})$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_{n+1}-p_n=O((\log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_{n+1}-p_n=O(p_n^{0.525})$, and assuming the Riemann hypothesis we can push this to $O(p_n^{1/2+\varepsilon})$, but not to $O(\sqrt{p_n})$. (see Wikipedia)

To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(\sqrt{k})$ term is bounded by $M\sqrt{k}$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+M\sqrt{k}$. Then $p_{n+1}\leq a_k\leq a+dk+M\sqrt{k}\leq d+p_n+M\sqrt{k}+M\sqrt{k}=p_n+O(\sqrt{k})=p_n+O(\sqrt{p_n})$.

Conversely, suppose gaps between primes are $O(\sqrt{p_n})$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(\sqrt{k})$.


The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.

On the other hand, you will be able to find a very long sequence of primes $a_k$ where

$-10000\cdot k^{1/2} ≤ a_k - (3 + 10000k) ≤ 10000 \cdot k^{1/2}$.

All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^{10000}$ where the densities of primes goes too low.