Csdrhrt

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

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 $Msqrt{k}$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrt{k}$. Then $p_{n+1}leq a_kleq a+dk+Msqrt{k}leq d+p_n+Msqrt{k}+Msqrt{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 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$.

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

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