The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k \geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(\sqrt{k})$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(\sqrt{k})$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(\ln k)$ or whatever.)
Best Answer
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})$.