# Is there an Infinite increasing sequence of primes with bounded second or larger differences?

The opposite question is if for any infinite increasing sequence of primes and any $k$ the sequence of the $k$-th order differences of the elements of the sequence is unbounded.

But if the question is true then there are integers $k$ and $B$ and a sequence of primes $q_1 < q_2 < \dots$ such that $$\lvert \Delta^k q_n \rvert \le B \quad \quad \forall n=1,2,\dots$$ and it is natural to ask what can be the least value of $k$ for which such a sequence exists, can we have $k=2$?

Does somebody know of any result or heuristic in one or the other sense?

EDIT: I expect now the question to have a negative answer. The reason is that if we start with the first $k$ primes a given bound $B$, and follow every possible chain of primes with $k$th order differences bounded by $B$. From an element $q$ of one of these chains we get at most $2B+1$ possible succesors and as the "probability" of one them being prime is about $(2B+1)/\log q$ the expected number of "active chains" decreases to zero as $q$ increases.

By the way I have computed the size of the longuest chain of primes with bounded second differences starting at 2,3 and for small values of $B=2,4,6,8,10$ it gives $57, 421, 1860, 24661, 380028$, it seems to increase very roughly as $e^{2B}$, is that a reasonable estimate?.

-
If Ben Green or Terence Tao could tell us exactly where are all these arbitrarily long arithmetic progressions in the primes, that might help with k=2. Gerhard "Ask Me About System Design" Paseman, 2011.01.27 –  Gerhard Paseman Jan 28 '11 at 4:00
@Gerhard Paseman How would that help? Arbitrarily long is not the same as infinite. It is pretty clear that there can be no infinite arithmetic progression. Where would these progressions have to be to help with $k=2$? –  Alex B. Jan 28 '11 at 7:23
It was a somewhat tongue-in-cheek reference to existence proofs. But for example, if there were a sequence of such AP's, with the last term of each "close enough" to the first of the next, that would get a sequence of primes with second differences mostly 0, and possibly bounded. Gerhard "Trying Square Jaw This Time" Paseman, 2011.01.27 –  Gerhard Paseman Jan 28 '11 at 7:38

If this were known for $k=2$, it would mean that for sufficiently large $n$ and some $A$, there is always a prime between $n^2$ and $(n+A)^2$. I believe that this is still open; see Legendre's conjecture. For comparison, the Riemann Hypothesis would imply there is a prime between $n^2$ and $(n+A \log n)^2$.
It is known that for large enough $n,$ there are primes between $n^3$ and $(n+1)^3$ (and you can lower that exponent from $3$). Perhaps you can use this to construct sequences with some differences bounded, although this is not immediate to me.
So your second paragraph implies that the minimal $k$ for which the $k$-th differences are bounded is at most $k=3$. Do you have a reference? –  Alex B. Jan 28 '11 at 7:26
As the last sentence indicates, I don't have a construction which uses it, and in fact, my inclination would be to try to use the $(n+1)^3$ result on values of $k$ greater than $3$. –  Douglas Zare Jan 28 '11 at 7:50
Am I missing something? If you can construct a sequence $p_n$ of primes that grows roughly as $n^3$, then their differences grow roughly as $n^2$ and the differences of those are roughly linear. Or am I oversimplifying things? –  Alex B. Jan 28 '11 at 8:09
The deviations of the locations of the primes from the cubes is not bounded. A priori, the errors may be quadratic. So, the second differences are like $c_1 n \pm c_2 n^2$, and the third differences are like $c_1 \pm c_2 n^2$, if you don't use a careful construction. Thanks for fixing the link. –  Douglas Zare Jan 28 '11 at 8:45