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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2011 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 Bartel Jan 28 2011 at 7:23

1
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 2011 at 7:38

1 Answer

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 Bartel Jan 28 2011 at 7:26
@Alex, I don't understand your comment, how does Ingham's result imply bounded 3-differences? As a reference, check out Ingham, A. E. "On the difference between consecutive primes", Quarterly Journal of Mathematics (Oxford Series), 8, pages 255–266, (1937) – Gjergji Zaimi Jan 28 2011 at 7:43
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 2011 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 Bartel Jan 28 2011 at 8:09

1
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 2011 at 8:45
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 41, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9563745856285095, "perplexity_flag": "head"}