Do the primes contain an infinite almost arithmetic progression?

Question

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.)

Answer 1

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})$.

Answer 2

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$.

Answer 3

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.