# Do the primes contain an infinite almost arithmetic progression?

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

• Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense. – Carl Mummert Mar 22 at 16:49
• @CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight. – Zach Teitler Mar 23 at 6:50

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

• Thanks. So conjecturally $p_n = a + nd + O((\log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(\log n)$, that is too strong I take it). – Zach Teitler Mar 22 at 17:20

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

• I don't think the question requires $a_k$ to be distinct. – Wojowu Mar 22 at 16:39
• @CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide. – Wojowu Mar 22 at 16:47
• Thanks; I was reading it as $O(\sqrt{d})$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression. – Carl Mummert Mar 22 at 16:48
• @CarlMummert True! I didn't really think it through. – Zach Teitler Mar 22 at 17:17

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.